10 Review

Slide1: 

review class? Tue Dec 12. Which is 2 days before exam Cook’s talk The P vs NP Problem and its Place in Complexity Theory Day and Date: Tuesday, December 5, 2006 Time: 4:00 p.m. Place: N638 Ross Building

Meta Algorithms: 

Meta Algorithms I try to provide a unified way to think about each algorithm type. Follow my fixed set of steps. Even if you don’t get the details of the algorithm correct, at least get the right structure. Try to match the parts of the new problem with the parts of the meta algorithm. eg instances, solutions, bird question, …

Slide3: 

Iterative Algorithms

Partial Correctness: 

Partial Correctness Proves that IF the program terminates then it works <PreCond> & <code> Þ <PostCond>

No Assumptions: : 

No Assumptions: Suppose a Martian jumped into the top of the loop. All you would know is that <loop-invariant> was true. It alone must provide enough information so that, after going around the loop, you can establish that the loop invariant is again true.

Algorithm Termination: 

Algorithm Termination You need to define some Measure of progress to prove that your algorithm eventually terminates.

More of the Input Loop Invariant: 

More of the Input Loop Invariant The input consists of an array of objects We have read in the first i objects. We will pretend that this prefix is the entire input. We have a solution for this prefix plus some additional information

More of the OutputLoop Invariant: 

More of the Output Loop Invariant The output consists of an array of objects I have produced the first i objects. Produce the i+1st output object. i to i+1 Done when output n objects.

Restricted Search Space Loop Invariant: 

Restricted Search Space Loop Invariant Maintain a sublist. If the key is contained in the original list, then the key is contained in the sublist. key 25

Slide10: 

For all major algorithms covered. Learn pre and post conditions. Learn the Loop Invariant Learn how to make progress while maintaining the LI. Iterative Algorithms

Friends & Strong Induction: 

MULT(X,Y): If |X| = |Y| = 1 then RETURN XY Break X into a;b and Y into c;d e = MULT(a,c) and f =MULT(b,d) RETURN e 10n + (MULT(a+b, c+d) – e - f) 10n/2 + f Friends & Strong Induction Consider your input instance Allocate work Construct one or more subinstances Assume by magic your friends give you the answer for these. Use this help to solve your own instance. Do not worry about anything else. Who your boss is. How your friends solve their instance. X = 3 Y = 1 XY=3 X = 3 Y = 2 XY=6 X = 6 Y = 3 XY=18

Slide12: 

Trust your friends to solve subinstances. The subinstance given must be must be an instance to the same problem. smaller Combine solution given by friends to construct your own solution for your instance. Focus on one step. Do not talk of their friends friends friends. Solve small instances on your own. Friends - Strong Induction View of Recursion.

Slide13: 

We know found nodes are reachable from s because we have traced out a path. If a node has been handled, then all of its neighbors have been found. Graph Search l

Graph Search: 

Graph Search Queue: Handle in order found. Breadth-First Search Stack: Handle most recently found Depth-First Search Priority Queue: Handle node that seems to be closest to s. Shortest (Weighted) Paths:

Slide15: 

Dijkstra's Handled Nodes Found Nodes Handled paths go through handled edges through any number of handled nodes followed by last edge to an unhandled node. For handled w, d(w) is the length of the shortest paths to w. Handle node with smallest d(u). d(v) is the length of the shortest handled path to v.

DFS: 

DFS s a c h k f i l m j e b g d s,1 Found Not Handled Stack <node,# edges> a,1 c,2 i,0

Linear Order: 

Linear Order a b h c i d j e k f g b l When take off stack add to backwards order c i,j,k,d,e,g,l,f

Slide18: 

Ingredients: Instances: The possible inputs to the problem. Solutions for Instance: Each instance has an exponentially large set of solutions. Cost of Solution: Each solution has an easy to compute cost or value. Specification Preconditions: The input is one instance. Postconditions: An valid solution with optimal cost. (minimum or maximum) Optimization Problems

Network Flow: 

Solution: The amount of flow F<u,v> through each edge. Flow F<u,v> cant exceed capacity c<u,v>. No leaks, no extra flow. For each node v: flow in = flow out u F<u,v> = w F<v,w> Network Flow

Network Flow: 

Value of Solution: Flow from s into the network minus flow from the network back into s. rate(F) = u F<s,u> - v F<v,s> Goal: Max Flow Network Flow

Min Cut: 

Value Solution C=<U,V>: cap(C) = how much can flow from U to V = uU,vV c<u,v> Min Cut s t Goal: Min Cut

Network Flow: 

u v f<u,v>/c<u,v> 0/c<v,u> Flow Graph u v Augmentation Graph c<u,v>-F<u,v> F<u,v>+c<v,u> c<u,v> F<u,v> c<v,u> Network Flow

Network Flow: 

u v F<u,v>/c<u,v> 0/c<v.u> Flow Graph u v Augmentation Graph c<u,v>-F<u,v> F<u,v>+c<v,u> c<u,v> F<u,v> c<u,v> Network Flow

Max Flow = Min Cut: 

Theorem: For all Networks MaxF rate(F) = MinC cap(C) Prove:  F,C rate(F)  cap(C) Max Flow = Min Cut Prove:  flow F, alg either finds a better flow F or finds cut C such that rate(F) = cap(C) Alg stops with an F and C for which rate(F) = cap(C) F witnesses that the optimal flow cant be less C witnesses that it cant be more.

Max Flow = Min Cut: 

Given Flow F Construct Augmenting Graph GF Find path P Let w be the max amount flow can increase along path P. Increase flow along path P by w. i.e newF = oldF + w × P -w Max Flow = Min Cut

Max Flow = Min Cut: 

Given Flow F Construct Augmenting Graph GF Find path P using BFS, DFS, or generic search algorithm No path Max Flow = Min Cut

Max Flow = Min Cut: 

Let Falg be this final flow. Let cut Calg=<U,V>, where U are the nodes reachable from s in the augmented graph and V not. Claim: rate(Falg) = cap(Calg) Max Flow = Min Cut

Slide28: 

Abstract Out Essential Details Cost: 29, 8, 1, 2

Slide29: 

Optimization Problems with a Greedy Algorithm Instances: A set of objects and a relationship between them. Cost of Solution: The number of objects in solution or the sum of the costs of objects

Fixed vs Adaptive Priority: 

Fixed vs Adaptive Priority Fixed Priority: Sort the objects from best to worst and loop through them. Adaptive Priority: Greedy criteria depends on which objects have been committed to so far. At each step, the next “best’’ object is chosen according to the current greedy criteria. Searching or re-sorting takes too much time. Use a priority queue.

Fixed vs Adaptive Priority: 

Fixed vs Adaptive Priority

Slide32: 

We have not gone wrong. There is at least one optimal solution consistent with the choices made so far. Initially no choices have been made and hence all optimal solutions are consistent with these choices.

Slide33: 

Let optSLI denote one. Proof changes optSLI into optSours and proves it is a valid solution is consistent both with previous and new choices. is optimal ?

Slide34: 

Alg commit to or reject each object. Has giving a “solution” S. $ opt sol consistent with these choices. S must be an optimal solution. Alg returns S .

Proof Greedy Algorithm Works: 

Proof Greedy Algorithm Works Looks hard, but they all have the same structure. Take my proof structure. Change what the instances, solutions, & costs are. Change what the greedy criteria is. Change the change step. Change the proof that the changed solution is valid consistent optimal The rest is the same.

Optimization Problems: 

Optimization Problems Don’t mix up the following What is an instance What are the objects in an instance What is a solution What are the objects in a solution What is the cost of a solution Greedy algorithm What does the algorithm do & know What does the prover do & know What does the fairy god mother do & know Recursive Backtracking / Dynamic Programming What does the algorithm do & know What does the little bird do & know What does the friend do & know

Slide37: 

Designing Recursive Back Tracking Algorithm What are instances, solutions, and costs? Given an instance I, What question do you ask the little bird? Given a bird answer k  [K], What instance subI do your give your friend? Assume he gives you optSubSol for subI. How do you produce an optSol for I from the bird’s k and the friend’s optSubSol? How do you determine the cost of optSol from the bird’s k and the cost of the friend’s optSubSol? Try all bird’s answers and take best of best. Review

Slide38: 

Recursive Back Tracking Algorithm Dynamic Programming Algorithm Given an instance I, Imagine running the recursive alg on it. Determine the complete set of subI ever given to you, your friends, their friends, … Build a table indexed by these subI Fill in the table in order so that nobody waits. the cost of its optimal solution advice given by the bird Run the recursive alg with bird’s advice to find the solution to your instance. Review

Dynamic Programmingdon’ts : 

Dynamic Programming don’ts When looping over the subinstances be clear what the set of subinstances are which is currently being solved, i.e. which instance is cost(i,j)? If you know that the set of subinstances are the prefixes of the input, i.e. <a1,a2, …, ai>, then don’t have a two dimensional table. Table[1..n,1..n]. Don’t loop over i and loop over j if j never gets mentioned again.

Dynamic Programmingdon’ts : 

Dynamic Programming don’ts .When trying all bird answers be clear what the set of bird answers are, which is currently being tried, & what it says about the solution being looked for. When getting help from your friend, be clear what the subinstance is that you are giving him How do you use the current instance and the birds answer to form his subinstance. Don’t simply say cost(i-1,j-1)

Dynamic Programmingdon’ts : 

Dynamic Programming don’ts .Think about what the base cases should be. Don’t make an instances a base cases if they can be solved using the general method. % is used to start a comment. Don’t put it in front of code.

Slide43: 

History of Classifying Problems GCD Matching Halting There are lots of important search problems exponential time to search poly time to verify given witness Circuit-Sat Problem: Does a circuit have a satisfying assignment. Non-Deterministic Polynomial Time SAT

Slide44: 

Key: Given an instance I (= <G,k>) and a solution S (= subset of nodes) there is a poly-time alg Valid(I,S) to test whether or not S is a valid solution for I. Poly-time in |I| not in |S|. |S| cant be too big. Valid Not Valid Formal definition: Prob  NP iff  poly time Valid such that Prob(I) =  S Valid(I,S) Non-Deterministic Poly-Time Decision Problems (NP)

Slide45: 

Key: If the instance has a valid solution A non-deterministic (fairy god mother) could prove it to you by giving you such a solution as a witness. You could check that it is valid. You could convince your boss. Valid Non-Deterministic Poly-Time Decision Problems (NP)

Slide46: 

Key: If the instance does not have a valid solution A non-deterministic (fairy god mother) could prove it to you by giving you ???? You have no way to convince your boss. k=5 Non-Deterministic Poly-Time Decision Problems (NP)

Reductions: 

Reductions Reduction: Design a fast algorithm for one computational problem, using a supposedly fast algorithm for another problem as a subroutine. Use to compare the two problems. Even if we don’t know whether they can be solved in polynomial time or not, we can learn that either they both can or neither can. We can also learn that they have a similar “structure.”

Reductions: 

Reductions Design a fast algorithm for Palg using a supposed fast algorithm for Poracle as a subroutine. We will only consider reductions of this simple form.

Reductions: 

Reductions If there is a fast algorithm for Palg then there is a fast algorithm for Palg then there is not fast algorithm for Poracle If there is not a fast algorithm for Palg If there is a fast algorithm for Poracle If there is not a fast algorithm for Poracle ? ? We give a fast algorithm for Palg using a supposed fast algorithm for Poracle as a subroutine. ? ? ?? ??

Reductions: 

Reductions Notation: Palg ≤poly Poracle Palg is “at least as easy as” Poracle (Modulo polynomial terms.) Poracle is “at least as hard as” Palg (Modulo polynomial terms.) Conclusions: The problems have a similar underling structure. We give a fast algorithm for Palg using a supposed fast algorithm for Poracle as a subroutine.

Slide51: 

GCD Circuit-Sat Problem: Does a circuit have a satisfying assignment. Let’s compare the problems in NP SAT None are harder than SAT! NP-Complete Problems

Slide52: 

GCD NP-Complete Problems Problem Pnew is NP-Complete Pnew not too hard. Pnew  NP Pnew Test in poly-time if a given solution is valid

Slide53: 

GCD NP-Complete Problems Problem Pnew is NP-Complete Pnew not too hard. Pnew  NP Pnew not too easy  Prob’  NP, Prob’ poly Pnew Pnew poly Prob’

Slide54: 

GCD SAT SAT is NP-Complete! NP-Complete Problems

Slide55: 

GCD NP-Complete Problems Problem Pnew is NP-Complete Pnew not too hard. Pnew  NP Pnew not too easy Sufficient to show Pnew poly SAT Because then Pnew poly SAT poly Prob’ By Cook, Pnew = Prob’ poly SAT Pnew SAT =

Slide56: 

A very large class of problems: Industry would love to solve them quickly We don’t know how. If we could solve one quickly, Þ we could solve all quickly. If one impossible to solve quickly Þ all impossible to solve quickly. NP-Complete Problems

End: 

End