Princeton Alogorithm COS226 Week

image.png

reduction

problem x reduces to problem y if you can use an algorithm that solves Y to help solve X.

image.png

for example, to find the median of N items: we can sort N items, then return item in the middle
so problem find the median can reduce to problem sort

image.png

Problem X linear-time reduces to problem Y if X can be solved with:
・Linear number of standard computational steps.
・Constant number of calls to Y.

Establish lower bound:
・If X takes Ω(N log N) steps, then so does Y.
・If X takes Ω(N 2) steps, then so does Y

Mentality.
・If I could easily solve Y, then I could easily solve X.
・I can’t easily solve X.
・Therefore, I can’t easily solve Y.

prove two problems X and Y have same complexity

・First, show that problem X linear-time reduces to Y.
・Second, show that Y linear-time reduces to X.
・Conclude that X and Y have the same complexity

Integer multiplication

image.png
https://www.jianshu.com/p/dc67e4a3c841

Matrix multiplication

image.png

Reductions are important in theory to:
・Design algorithms.
・Establish lower bounds.
・Classify problems according to their computational requirements.
Reductions are important in practice to:
・Design algorithms.
・Design reusable software modules.

stacks, queues, priority queues, symbol tables, sets, graphs
sorting, regular expressions, Delaunay triangulation
MST, shortest path, maxflow, linear programming

・Determine difficulty of your problem and choose the right tool

QUIZ

Q1 Longest path and longest cycle.

image.png

add a new path (with new vertices) between s and t. then call LongestCycle, found the cycle and remove the path we add, it is the answer for LongestPath

Q2 3Sum and 4Sum

image.png

define M=1+max|ai|, add all the number with M. then all the number in input is positive, if 3 sum have solution we should delete 3M, therefore we need to add -3M into the input, then call 4 sum, because -3M is only negative number, if answer exists, it must appear in the result.
other 3 are 3sum answer

Q3 3Sum and 3Linear

image.png

we also define the same M as above.
but a wrong design, it to mark ai + M, and -(ai + 4M), because it will break ai + aj - 8ak = 0,
we want -8 *(ak + M) + ai + 4M + aj + 4M = 0 but aj + M + ak + M -(ai+4M) = 0 is possible.

because aj + M is in range （0， 2M）
-(ai + 4m) is in range (-3m,-5m)
2 * （0， 2M） overlap -(-3m,-5m)

so we should make 2 * (range for ai,aj) will not overlap 1 * (range for ak)
we could build ai+8M, and -(ak + 2M)
ai+8M is in range (7M, 9M), -aj - 2M is in range (-3M, -M)
-2 *(-3M, -M) < (7M, 9M)

course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226