Morals

Here is a collection of morals and tips/tricks our section has come up with. This is intended to be a review of section as well as a homework helper and study resource for exams! Click here to go back to my CS 331 resources page.

Section 1 - Proof Techniques

• In induction proofs, try to "find" the inductive hypothesis in the inductive step. For example, if you're proving an algebraic identity for the n+1 case, try to isolate the expression for the n case (from the extra terms you get from the n+1) and use the truth of the inductive hypothesis to proceed.
• For induction on graphs, you typically want to induct on edges and vertices. This will not always be correct, but works often, since deleting an edge or a vertex in a graph is a simple procedure, whereas reducing the degree by 1 would require a lot more care.
• There is no "correct" way to prove something. It's important to be familiar with several proof techniques so that your bag of tricks doesn't get exhausted.
• If a statement seems cumbersome to prove directly (e.g. have to consider too many cases) or you feel like formalizing your argument is tricky, try proving by contradiction.

Section 2 - Graph Algorithms

• BFS finds the fewest number of edges from a source node to any other nodes: it's a shortest path algorithm if all edges have the same weight.
• DFS is useful for cycle detection in directed graphs

Greedy Algorithms

• The structure of swapping arguments is a contradiction argument: assume the optimal solution differs from the greedy one. Then you can make a small change (or swap) to the optimal solution that makes it look more like the greedy one. If this can only increase the score of the optimal, then you have arrived at a contradiction.
• For a stays-ahead argument, induction is typically helpful. You generally want to list out all choices made by the greedy and optimal algorithms, and show by induction that at each step the greedy algorithm stays ahead.

Exam Review

• Practice a variety of proof techniques: don't be restricted to one plan of attack.
• Read my exam tips!