CSE 417 Divide & Conquer (pt2) - University of Washington

CSE 417

Divide & Conquer (pt 2)

Famous Examples

Reminders

> HW2 due Friday

> Problem 2 correction

¨C 7 week periods: 6 to fit model, last to test model

> don¡¯t want test your model on the same data

¨C 10 periods (1-7, 2¨C8, ..., 10-16) and 51 penalties ~> 510 combinations

¨C scatter plot demo

¨C HW2 ML approach (Lasso) is generally useful

> your code only depends on #parameters and ranges

Divide & Conquer Review

> Apply the steps:

1. Divide the input data into 2+ parts

2. Recursively solve the problem on each part

3. Combine the sub-problem solutions into a problem solution

> Key questions:

1. Can you solve the problem by combining solutions from sub-problems?

2. Is that easier than solving it directly?

> Use master theorem to calculate the running time

Outline for Today

>

>

>

>

Integer multiplication

Matrix multiplication

Fast Fourier Transform

Integer multiplication again

Integer Multiplication

> Processor provides ability to multiply small ( Multiplying arbitrary-size integers is a classic problem

¨C doesn¡¯t come up often in real programming

¨C and when it does, just use a library: java.math.BigInteger

> Does come up in coding interviews sometimes (sadly)

> These algorithms illustrate the techniques well

¨C but all use non-obvious insights!

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download