Table of links incoming soon to help manage the length of this page.

Study Guide

Optional exercises are either C problems, B problems, or A problems. C problems are at the same level as the exercises, and generally require that you only be able to mechanically carry out the algorithms. B problems are harder problems that require you to really know what's going on (the midterm had plenty of these). A problems are problems that either cover tangential material (like how Kosaraju-Shamir works), require deep comprehension of the material, involve very clever tricks, or perhaps even all 3.

Don't be intimidated by its length. I tried to be as comprehensive as possible.

Undirected Graphs

Key Concepts

Graph Representation
There are many possible internal representations of a graph. We discussed three. You should be familiar with the tradeoffs for each.

• List of edges
• Adjacency matrix
• Adjacency lists
- We use these in 226, because we assume that our graphs are sparse.

Important graph problems

• Is there a path between s and t?
• Is there a cycle in the graph? How do you find the nodes in a cycle?
• Is a graph bipartite?
• Euler tour. Is there a cycle that uses every edge exactly once?
• Hamilton tour. Is there a cycle that uses every vertex exactly once?
• Planarity problem. Find a vertex layout that results in no crossing edges (see this online game for a fun (?) look at the problem)
• Graph isomorphism. Are two graphs the same graph (but with different vertex names)

One important meta-point is that it is non-trivial to determine the difficulty level of a graph problem. For example, finding an Euler tour is polynomial time and the algorithm is non-trivial but not hideously complex. By contrast, finding a Hamilton tour is an intractable problem. Planarity can be solved in linear time, but it's a rather complex algorithm to follow. Graph isomorphism is particularly notable since its tractability has remained elusive despite decades of research.

Important graph tools

• DFS. You should know this algorithm absolutely cold by the time the exam comes around. For example, you should be able to write DepthFirstSearch.java in your sleep, and the run time if we use adjacency lists (E + V) should be scorched into your neurons.
• BFS. You should have the same level of familiarity as with DFS.
You should understand that almost any problem you care to solve with unweighted graphs can be solved with one of these two algorithms. You should understand when each is appropriate to use.

Graph client design pattern (used for 4.1, 4.2, 4.3, and 4.4). Instead of creating highly complex classes that support basic graph operations AND solution of important graph problems, we have a basic class (e.g. Graph) that gives us basic operations, and special purpose clients that solve subproblems on a graph (e.g. ConnectedComponents(Graph g)).

Recommended Problems

C level

1. Fall 09 Final, #2a
2. Textbook: 4.1.12

B level

1. Fall 09 Final, #2b
2. Fall 10 Final, #2c
3. Textbook: 4.1.14, 4.1.10
4. New (4/2/2013): What is the run time for DFS or BFS if we use an adjacency matrix insted of adjacency lists?

A level

1. Fall 12 Final, #15
2. Textbook: 4.1.33

Directed Graphs

Key Concepts

Using directed graphs vs. undirected graphs. Know when to use each. This should be fairly natural. For example, you'd use an undirected graph to represent friend connections between Facebook users, and a directed graph to represent following connections on Twitter.

BFS and DFS are directed graph algorithms. Many canonical unweighted digraph problems (e.g. shortest paths and reachability) can be solved using code that is effectively identical to code for solving problems on unweighted graphs.

Important digraph problems.

• Topological sort.
• What is a topological sort?
• Is it unique?
• What are the conditions under which a graph has a topological sort?
• How do you compute a topological sort?
• What is the run time to find a topological sort if we use adjacency lists?
• Bonus: How can you use the idea of a topological sort to find a Hamilton tour (usually an NP complete problem)?
• Strongly connected component identification.
• What is a strongly connected component (SCC) (also sometimes called a strong component)?
• Given Q strong components, how do we know that there is SOME sequence of Q depth-first-searches where each search finds exactly one of our Q strong components? See slides 60-64.
• How do we find that sequence? Step 1 of Kosaraju-Sharir.

Important digraph tools.

• Preorder, postorder, and reverse postorder.
What are these and how do we find them using DFS? What is the run time to find each order if we use adjacency lists?
• Topological sort.
• Kosaraju-Sharir algorithm.
• What does the first step provide? An ordering of our vertices that allows us to find the SCCs.
• What does the second step do? Finds all the strongly connected components using the ordering provided by the first step.
• What are the steps? 1. Run DFS on G^R to compute reverse postorder of G^R. 2. Start V depth-first-searches (one for each node) in the order given by first step.
• What is the run time if we use adjacency lists?

Recommended Problems

C level

1. Spring 08 Final, #1a, #1b
2. Fall 08 Final, #1a, #1b
3. Fall 10 Final, #3a
4. Spring 12 final, #3a, #3ab

B level

1. Spring 08 Final, #1c, #1d
2. Fall 08 Final, #1c
3. Fall 10 Final, #3b
4. Fall 10 Final, #2d, #2e
5. Textbook: 4.2.10, 4.2.20

A level

1. Fall 2008, #11
2. 4.2.19, 4.2.22 (exam will not require you to know why Kosaraju-Sharir works)
3. 4.2.27
4. 4.2.40

Just for fun

1. Write code similar to (or copy) the webcrawler shown in lecture slide 48.

Minimum Spanning Trees

Definition of a weighted graph and an MST.

• What is the MST?
• Under what conditions is it unique?
• How many edges are in the MST?

Cuts.

• What is a cut?
• How many cuts are there for a graph with V vertices?
• Cut property - given a cut, the crossing edge between the two partitions belongs to the MST. This is the most important point of this lecture, and you should be very familiar with the proof.

Manually performing Kruskal's and Prim's algorithms. These are easy and you should be able to do them even under the influence of powerful sedatives.

Why Kruskal's and Prim's algorithms work. You should understand the "Fundamental Idea" slide (#37) in the flipped lecture.

Implementing Kruskal's and Prim's algorithms.

• What sort of data do we track in Kruskal's algorithm, and what data structures do we use to track this data? (See code on slide 51)
• What is the resulting run time for typical implementations of these data structures?
• What sort of data do we track in Lazy Prim's algorithm, and what data structures do we use to track this data?
• What is the resulting run time for typical implementations of these data structures?
• For Eager Prim's, why do we track vertices instead of edges? What does this do to our space requirements?
• What is the special data structure that we use to track vertices and their best known distance?
• How do we change the priority of a vertex using this special data structure (you should be able to give an example of a method call)?

Recommended Problems

C level

1. Spring 08 Final, #2a, #2b
2. Fall 08 Final, #2a, #2b
3. Fall 09 Final, #1b
4. Fall 09 Final, #3a, #3c
5. Fall 10 Final, #4a, #4b
6. Fall 10 Final, #3a, #3b
7. Spring 12 Final, #4a, #4b
8. Would Kruskal's or Prim's algorithm work with weighted directed graphs?

B level

1. Fall 09 Final, #3b
2. Fall 12 Final, #4a, #4b, #4c, #4d
3. Textbook 4.3.8 - this is a particularly handy concept!
4. Textbook 4.3.12
5. Textbook 4.3.13
6. Textbook 4.3.20
7. True or False: Given any two components that are generated as Kruskal's algorithm is running (but before it has completed), the smallest edge connecting those two components is part of the MST.
8. Textbook 4.3.19 - to be clear, they mean that the PQ is implemented with a sorted list.
Note the solution on the booksite is for an unsorted list. That's also a fine problem.

A level

1. Spring 08 Final, #3
2. Fall 09 Final, #3d
3. Textbook 4.3.26

Just for fun

1. Figure out if Kruskal's, Prim's Lazy, or Prim's Eager algorithm are faster on "typical" graphs. Use the code from the booksite.

Shortest Paths

Key Concepts

Graph Representation

• Use DirectedEdge instead of Edge.
• Adjacency list only tracks edges pointing out of node.

Shortest path representation

• Can represent shortest path as a tree.
• In Java, we represent the shortest path tree with two arrays: distTo[] and edgeTo[].

Edge relaxation

• What does it mean to relax an edge? Update shortest path tree (edgeTo[] and distTo[]) to reflect the information contained in that edge. What does it mean to relax a vertex?
• The code for relax should be second nature.
• What is the shortest paths optimality condition? Why is it true?
• What is the generic shortest path algorithm? Why does it always eventually get the right answer?

Manually performing Dijkstra's, Acyclic Shortest Paths, and Bellman Ford - These should be very easy to manully execute.

Bellman Ford algorithm

• Sequence of edge relaxations: Relax all the edges. Then relax them all again. And again. Repeat this V times. You are done.
• Runtime is obviously EV.
• Proof: After ith relaxation of all E edges, we have the shortest path containing i edges. There are at worst V-1 edges between any two vertices in the shortest path tree (otherwise it is not a tree).
• Sledgehammer of algorithms. Works on any graph except a graph with negative cycles. However, we don't really care, because a negative cycle has no definition of shortest path (since you can just go in the negative loop more times and get there sooner).

Dijkstra's algorithm

• Important invariant: Once a vertex belongs to the shortest path tree, its distTo and edgeTo can never change. Why is this invariant true? How does it prove correctness?
• Why is the runtime (V + E) log V? Why do the book and slides just say E log V? If we change our priority queue implementation, how does this runtime change (in general - no need to write Fibonacci heap runtimes on your cheat sheet)?
• How is Dijkstra's algorithm similar to Prim's algorithm? How is it dffferent?

Acyclic shortest paths

• Why does it work?
• Why is the run time E + V?

Recommended Problems

C level

1. Fall 2009 Final, #4
2. Fall 2010 Final, #5
3. Textbook 4.3.1 and 4.4.1

B level

1. Spring 2008 Final, #11 (this should be very easy if you've done Seam Carving!)
2. Fall 2011 Final, #4
3. Spring 2012 Final, #5
4. Fall 2012 Final, #5
5. Think about how to solve the undirected version of the shortest paths problem. Why is it easy for graphs with positive edge weights? Why is it hard if we include negative edge weights?
6. Textbook 4.4.25
7. Since Prim's and Dijkstra's algorithms are so similar, why do we need to check for cycle in Prim's, but not in Dijkstra's?
8. Textbook 4.4.42 and 4.4.44

A level

1. Fall 2008 Final, #11 (I remember getting asked this at a career fair as a freshman!)
2. Textbook 4.4.34
3. Textbook 4.4.37

Max-Flow

Key Concepts

Graph Representation

• Use FlowEdge instead of DirectedEdge.
• Adjacency list tracks nodes pointing towards and away from node (why?).

Max-flow, min-cut, and Ford-Fulkerson basics

• What is a flow? Assignment of value to every edge.
• What is the max-flow problem? What is the min-cut problem?
• How do we find an augmenting path from s to t? BFS, but with the special rule that we don't traverse a forward (backward) edge if it is full (empty).
• Given a max-flow, how do we find a min-cut? Try to find an augmenting path using algorithm above. The s side of the s-t cut is every vertex reachable from the source.

Ford-Fulkerson details

• How do we prove that it always terminates with integer weights?
• How do we know the answer is right if it terminates?
• Why can't we use the same argument that we used for the generic shortest paths algorithm?
• What are some different strategies for picking a path? Why is DFS potentially very bad?

Recommended Problems

C level

1. Fall 2011, #11
2. Spring 2012, #11
3. Fall 2012, #6

B level

1. Textbook 6.36
2. Textbook 6.38

A level

1. Textbook 6.37

String sorts

Key Concepts

• String - sequence of characters from a finite ordered alphabet. In Java, our alphabet is the set of all 16 bit integers (representing unicode characters).
• Radix - just another word for 'base' as in the base of a number system. For example, the radix for words written in lowercase English letters is 26. For number written in arabic numerals it is 10.
• Radix sort - a sort that works with one character at a time (by grouping objects that have the same digit in the same position).
• Note: I will use 'character' and 'digit' interchangably in this study guide.

Manually performing LSD, MSD, and 3-way radix quicksort. Should be doable in your sleep.

LSD.

• Requires fixed length strings (can pad end of strings with 'smaller-than-everything' character).
• Requires 2NW charAt calls. Why?
• Requires 7WN + 3WR array accesses. Why?
• Why do we consider these run times to be linear, despite the fact that they involve products WN and WR?
• Requires N + R space. Why?
• What sorting technique is used in LSD? Would a standard technique (e.g. Quicksort) work? Does the sort need to be stable?
• For a fixed alphabet and key size, what are the best case and worst case inputs for LSD?

MSD.

• What sorting technique is used in MSD? Would a standard technique (e.g. Quicksort) work? Does the sort need to be stable?
• How much memory does MSD use? Why is MSD so memory hungry? What sort of inputs result in the gratest memory usage?
• Why is it so important to switch to insertion sort (or another sort) for small subarrays? Why did we not have to do this in MSD?
• For a fixed alphabet and key size, what are the best and worst case inputs for MSD?
• What is the role of our special charAt(char, int) method?

3-way radix quicksort.

• Same thing as MSD, but uses 3-way partioning instead of key-indexd counting!
• Compared to MSD, why is it less important to switch to insertion sort (or naother sort) for small subarrays?
• What is the role of our special charAt(char, int) method?
• Why is 3-way radix quicksort faster, even though it does more character compares than MSD on average?

Implementation issues.

• Why does the special charAt method have a significant impact on performance?
• What sorts of inputs are especially good for LSD, MSD, and 3-way radix quicksort?
• What sorts of inputs are especially bad for LSD, MSD, and 3-way radix quicksort?

Recommended Problems

C level

1. Spring 2012 Final, #6

B level

1. Fall 2008 Final, #6
2. Fall 2012 Final, #7
3. Spring 2008 Final, #12
4. Textbook 5.1.8, 5.1.10

A level

1. How could we avoid the performance hit form our special charAt function?
2. What makes MSD cache unfriendly?
3. The difference between MSD and 3-way radix quicksort is that when recursion depth is i, MSD fully sorts all keys by the ith character using key indexed counting, and 3-way quicksort merely partitions on the ith character. Both of these processes take linear time, but key-indexed counting gets us closer to our final goal. Succintly state why we opt to use the equally slow but less-powerful partitioning procedure.
4. Textbook 5.1.22. The results may surprise you.

Tries

Key Concepts

• Length of our String keys given by L.
• Alphabet size is R.
• You should be able to build an R-way Trie and TST. You should be able to search a R-way Trie and TST. You should be able to delete from an R-way trie. You should appreciate how a TST can become unbalanced with inserts.
• Given a graphical depiction of a TST or Trie, you should be able to tell which keys are in the trie.

• With String keys, we don't want to think about counting compareTo() or hashCode() and equals() calls. Why? What do we think about instead?
• Know (but you do not have to prove) that LLRBs take order of growth lg² N charAt() calls. Based on this, a hit is order L + lg² N.
• Understand why hash tables are L charAt() calls on a hit or miss (assuming no collisions!)

• Special structure such that you only look at each letter one time. Trivially, misses and hits have a max run time of L.
• Be aware that for random inputs, search misses only take an average of log_R N, which is order of growth lg N.
• Why do R-way tries use such a huge amount of memory? How much memory in terms of L and R? How does this same problem affect run time?
• What are the two ways of determining that a key does NOT exist in a trie?

• When looking for a single character, why is it possible to follow as many as R links before you complete the search for that character?
• If the TST is balanced, typical case inserts and hits cost L + lg N character compares, and typical misses cost lg N character compares.
• If the TST is not balanced, worst case hits, misses, and inserts all include H, where H is the height of the tree.

Recommended Problems

C level

1. Spring 2008 Final, #5
2. Spring 2008 Final, #4
3. Fall 2011 Final, #8
4. Fall 2012 Final, #8
5. Textbook 5.2.3, 5.2.4

B level

1. Fall 2009 Final, #5
2. Spring 2012 Final, #9
3. Textbook 5.2.21 (just design the API)
4. When would we want to use an R-way trie instead of a TST?
5. Give a worst case input that causes a TST to be unbalanced (and thus slow).
6. Is the number of character compares in an R-way trie strictly better than for an LLRB? For a hash table? Is a trie guaranteed to be faster in overall run time than an LLRB or a hash table?

A level

1. When might we want to use a hash table instead of a TST?
2. What would happen if we had an R-way trie where we keep our next nodes in a linked list? How would this affect memory performance? Timing? What if we used an LLRB? A hash table?
3. Repeat Spring 2013 midterm problem #8, but assume your keys are Strings instead of Comparables.

Substring Matching

Key Concepts

• Substring search problem: Find an instance (or all instances) of a substring of length M in a string of length N.
• Sustring must be precisely defined (no *s or |s).
• You should be able to manually use a KMP DFA, and you should be able to manually carry out Boyers-Moore and Rabin Karp.

• How do you construct the DFA? How much time does it take if you re-simulate every time you have a mismatch? It's ok if you don't fully understand the linear time construction process.
• What are the best case run times for DFA construction and DFA simulation? The worst case run time?

• What is the mismatched character heuristic? Why do we use the rightmost character?
• Why is the mismatched character heuristic strictly suboptimal? Why do we use it then -- because the basic idea is very similar to KMP and you'll learn it if you ever really need to.
• What is the best case run time? The worst case run time?
• What sort of inputs result in best and worst case performance?

• If we know mod(ABCDEFG, R), how do we compute mod(BCDEFGH, R) in constant time (where A through H are arbitrary digits of a number from some alphabet of radix R)?
• What are the Las Vegas and Monte Carlo versions of Rabin-Karp? Why does it not really matter which one we use? If you were worried, which one would YOU use?
• How would we extend Rabin-Karp to efficiently search for any one of P possible patterns in a text of length N? How would this technique compare to using KMP or Boyer-Moore for the same task?

Recommended Problems

C level

1. Spring 2008 Final, #6
2. Fall 2009 Final, #6
3. Fall 2012 Final, #10

B level

1. Fall 2009 Final, #5
2. Fall 2009 Final, #10 [great problem!]
3. Fall 2010 Final, #10
4. Fall 2011 Final, #6
5. Spring 2012 Final, #7
6. Fall 2012 Final, #9
7. Give an example of when you might want to use KMP? Boyer Moore? Rabin Karp?

A level

1. Fall 2010 Final, #10
2. Fall 2012 Final, #14
3. Give an example of when you might prefer to use the Monte Carlo version of Rabin Karp over the Las Vegas version.
4. Textbook: 5.3.22
5. Textbook: 5.3.26

Regular Expressions

Key Concepts

• Understand the regular expression syntax. Don't get the order of operations wrong like we did in our PollEverywhere question.
• Know how to write simple regular expressions. We will not ask you to do this on the final.

• Understand how to manually simulate an NFA operating on a string.
• What happens on a mismatch? All states that don't match are removed from the set of valid states. This may result in an NFA that is not in ANY state. The NFA does NOT go back to state 0.
• Why does an NFA only tell you if an ENTIRE string matches a regular expression, not whether or not some substring matches?
• Given a string and and a regular expression, how do we tell if any substring of the string matches the regular expression? (Hint: Make a new regular expression)
• How does graph search play a role? Does it matter if we use DFS or BFS? Would it ever make sense to use an undirected graph in the regular expression context? A weighted graph?

• Understand how to build an NFA from a regular expression. If you know how to do this using the stack-based method, you can do this process without even thinking.
• Our NFA construction process is not the only valid construction process. There are other equally valid ones. Ours is just the simplest that Bob and Kevin could come up with.
• Our NFAs are non-unique representations of a given regex (as discussed in lecture).
• Why are there no more than 3M epsilon transitions? Why is this fact vitally important to the NM worst case run time for simulation?
• Since DFAs have worst case run time N, and all regexes go with some DFA, why don't we just use those?
• Advanced and important topic mentioned in passing during lecture that won't be covered on the final: There is no regex that can compile a regex into a DFA. However with a DFA and a stack, you can do this just fine (specifically, this process doesn't require a Turing machine). Compiling Java into class fiels, by contrast, does require a Turing machine.

Recommended Problems

C level

1. Spring 2008 Final, #8
2. Fall 2008 Final, #8
3. Fall 2009 Final, #7
4. Fall 2010 Final, #9
5. Spring 2012 Final, #10
6. Spring 2012 Final, #11
7. 5.4.1, 5.4.2

B level

1. Fall 2011 Final, #7
2. Textbook 5.4.16, 5.4.17, 5.4.18

A level

None!

Just for fun

1. 5.4.13

Data Compression

Key Concepts

• Why compress? To save space AND time.
• How does compression work? Compression takes advantage of structure within data.
• What sort of data does not compress well? Random data.
• How do we characterize the randomness of data? The Kolmogorov complexity.
• Lossy compression can further reduce file sizes by throwing away unimportant information.
• What is the compression ratio?
• Why can no compression algorithm possibly compress all bit streams?
• What fraction of bitstreams can be compressed in half by a general purpose algorithm?

• Takes advantage of repeated binary digits.
• How do you handle runs of length more than 2^M?

• Basic idea: Variable length codewords to represent fixed length characters. More common characters are represented by shorter codewords.
• What is a prefix free code? Why is it important that Huffman coding use a prefix free code? Would encoding work with a non-prefix free code? Would decoding work?
• Why is it necessary to transmit the coding trie? Why don't we have to do something similar with run length encoding or LZW?
• Why do we typically use an array for encoding and a trie for decoding?
• You do not need to know the ins and outs of the Huffman code. However, you should conceptually understand the idea of transmitting/reading the trie using an inorder traversal.

• Basic idea: Fixed length codewords to represent variable length strings. More common characters are represented by shorter codewords.
• Why do we typically use a trie for encoding and an array for decoding?
• How do you handle the 'strange' case (where a codeword is seemingly not in the table during decoding)?

• The Kolmogorov Complexity of a string S is the length of the shortest Java program (including all relevant libraries) that can output S.
• Given: a string S, a program P of length L in programming language X that outputs S, why can we always find a Java program of length L + C, where C is some constant that depends on our choice of X (but not S or L)?
• Why does the given fact above prove that no programming language is capable of compressing
• Why is it impossible to write a program which finds the Kolmogorov Complexity of a given string?
• Are there any strings for which Kolmogorov Complexity can be found? Yes!

Recommended Problems

C level

1. Spring 2008 Final, #4
2. Fall 2008 Final, #7
3. Fall 2011 Final, #10b
4. Textbook 5.5.3
5. Why is the Kolmogorov complexity of "a" (relatively) easy to find?

B level

1. Fall 2011 Final, #10a
2. Textbook 5.5.13
3. Textbook 5.5.17
4. Is the Kolmogorov complexity of π small or large?

A level

1. Fall 2012 Final, #13
2. Textbook 5.5.23 (don't know the answer myself, I'm quite curious)

Reductions and Intractability

Key Concepts

• We consider problems solvable in polynomial time to be efficient.
• Important real world note: There are two common definitions for P and NP. The classic definition defines the classes in terms of decision problems. A later (but also quite common) definition is in terms of search problems. For simplicity, we used decision problems in our lecture, but many other sources use the search problem version. The two definitions are very similar and have the same real world implications, but they are not quite the same.
• To make matters even a bit more confusing, I used P to represent the class of all problems solvable in polynomial time, and NP the class of all decision problems solvable in polynomial time.
• Bottom line: Whether we're talking about the decision or search problem formulation, the fundamental idea is that P is the a of problems that can be solved in polynomial time, and NP is the a of problems whose solution can be verified in polynomial time.
• Completeness: What conditions are necessary for a problem to be Q-complete, where Q is some set of problems?
• What did Rabin/Levin do?
• What did Karp do?
• What is a reduction?
• Why is solving an NP complete problem such a big deal?
• Amusing fact: There exists a well defined algorithm (that you can already write in Java) that solves NP problems in time P, but it's polynomial time only if P = NP. Wikipedia has the scoop. It's madness!
• The most common argument against Searle's Chinese Box is the systems argument (namely that the dude in the box is acting as part of a larger system). I happen to strongly agree with this. I still won't let you blow me up and reassemble me.

Recommended Problems

Note: The Spring 2013 final will not feature one of those really sneaky reduction problems (typically part a of the B level and A level problems below). However, we will probably ask you about how reductions work.

C level

1. Textbook 6.52

B level

1. Textbook 6.57
2. Textbook 6.61, but replace "search" with "decision" to match our terminology from class.
3. Textbook 6.62
4. Spring 2008 Final, #8
5. Fall 2008 Final, #12
6. Fall 2009 Final, #11
7. What does the Venn diagram look like for NP-Complete and NP?
8. If P=NP, then why is the set of NP-Complete problems the same as P?

A level

1. Fall 2010 Final, #10
2. Fall 2011 Final, #13
3. Spring 2012 Final, #13
4. Fall 2012 Final, #15