Princeton Alogorithm COS226 Week
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
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.pnghttps://www.jianshu.com/p/dc67e4a3c841
Matrix multiplication
image.pngReductions 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.pngadd 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.pngdefine 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.pngwe 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