Exam 1 review

Greedy

A Greedy Algorithm is an algorithm whose solution applies the same choice rule at each step over and over until no more choices can be made.

• Stating and Proving a Greedy Algorithm
• State your algorithm (“at this step, make this choice”)
• Greedy Choice Property (Exchange Argument)
• Inductive Structure
• Optimal Substructure
• “Simple Induction”
• Asymptotic Runtime

Divide and conquer

Stating and Proving a Dividing and Conquer Algorithm

• Describe the divide, conquer, and combine steps of your algorithm.
• The combine step is the most important part of a divide and conquer algorithm, and in your recurrence this step is the “f (n)”, or work done at each subproblem level. You need to show that you can combine the results of your subproblems somehow to get the solution for the entire problem.
• Provide and prove a base case (when you can divide no longer)
• Prove your induction step: suppose subproblems (two problems of size n/2, usually) of the same kind are solved optimally. Then, because of the combine step, the overall problem (of size n) will be solved optimally.
• Provide recurrence and solve for its runtime (Master Method)

Maximum Flow

Given a weighted directed acyclic graph with a source and a sink node, the goal is to see how much “flow” you can push from the source to the sink simultaneously.

Finding the maximum flow can be solved by the Ford-Fulkerson Algorithm. Runtime (from lecture slides): $O(F (|V | + |E |))$.

Fattest Path improvement: $O(log |V |(|V | + |E |))$

Min Cut-Max Flow: the maximum flow from source $s$ to sink $t$ is equal to the minimum sum of an $s-t$ cut.

A cut is a partition of a graph into two disjoint sets by removing edges connecting the two parts. An $s-t$ cut will put $s$ and $t$ into the different sets.