Resources

The DPV textbook is very helpful to read combined with the Udacity lectures. If you want to prepare, just start watching the lectures and reading the book. The schedule varies slightly every semester, but here's a sample schedule that correlates the resources above based on the last two fall semesters.

Week Topic DPV Ch. KT Ch. Videos
1 Dynamic Programming 6 6 DP1, DP2, DP3
2 RSA Cryptosystem 1 RA1, RA2
3 Divide & Conquer 1 2 5 DC1, DC3, DC4
4 Divide & Conquer 2 2 5 DC5, DC2
5 Bloom Filters & Exam 1 RA3
6 Graph Algorithms 1 3, 4 3 GR1, GR2
7 Graph 2 and Max-Flow 1 5.1, 7 3, 7 GR3, MF1
8 Max-Flow 2 7 7 MF2, MF3, MF5
9 Max-Flow 3 + Exam 2 7 7 MF4
10 NP-Completeness 8 8 NP1, NP2, NP3
11 Linear Programming (LP) 7 LP1, LP2, LP3
12 NP and LP 11 LP4
13 More Complexity 8 8 NP4, NP5
14 Thanksgiving Break
15 Markov Chains & PageRank GR4
16 Final exam

GA takes a lot of time and practice, practice, practice. It's a theory class not a programming class, so the way to get good at it is doing lots of homework problems (even beyond those assigned) and generalizing your understanding of how to solve many types of problems. Do a few practice problems everyday and use other resources beyond the textbook and videos to clarify and extend your understanding.

Homework is worth very little of your overall grade (5%) but is highly recommended to complete to prepare for the 2 midterms and 1 final, which are the bulk of your grade (85%). There is also one Python project, which counts for 10%.

Suggested DPV Problems

The following problems are from the DPV textbook and are highly recommended to improve your understanding of the material. They're ordered similar to the sample schedule above. Problem x.y refers to x.y at the end of chapter x (e.g., 1.11 is a problem at the end of chapter 1).

Category Problem Description
Big-O 0.1 Big-O
Mod 1.11 Divisible by 35
Mod 1.12 22^2006 mod 3
Mod 1.13 Multiple of 31
Mod 1.20 Find inverses
Mod 1.25 2125 mod 127
RSA 1.27 RSA by hand
RSA 1.28 RSA p=7, q=11
RSA 1.42 RSA with prime modulus
DP 6.1 Contiguous Sum
DP 6.2 Hotel stops with min penalty
DP 6.3 Yuckdonald's
DP 6.4 Dictionary lookup
DP 6.5 Pebbling a checkerboard
DP 6.6 Table multiplication
DP 6.7 Palindromic subsequence
DP 6.8 Longest common substring
DP 6.11 Longest common subsequence
DP 6.17 Making change 1 (unlimited)
DP 6.18 Making change 2
DP 6.19 Making change k
DP 6.20 Optimal binary search tree
DP 6.26 Alignment
D&C 2.5 Solve recurrences
D&C 2.7 Roots of unity
D&C 2.8 FFT
D&C 2.9a FFT
D&C 2.14 Remove duplicates from array
D&C 2.16 Find in infinite sorted array
D&C 2.17 Fixed point
Graph 3.3 Topological ordering
Graph 3.4 SCC algorithm
Graph 3.5 Reverse of graph
Graph 3.8 Pouring water
Graph 3.15 Computopia
Graph 4.14 Shortest paths through v0
MF 7.10 Max-flow=min st-cut
MF 7.17 Bottleneck edges
MF 7.18ab Max-flow variants
MF 7.19 Verifying max-flow
MST 5.9 Unique lightest edge
MST 5.22a Cycle property
NP 8.1 TSP opt. vs. search
NP 8.3 Stingy SAT
NP 8.4abc Clique-3
NP 8.8 Exact 4-SAT
NP 8.10a Subgraph isomorphism
NP 8.14 Clique+IS
NP 8.19 Kite
LP 7.1 LP example
LP 7.2 Duckwheat
LP 7.3 Cargo plane
LP 7.4 LP for Duff beer
LP 7.5 LP for canine products
LP 7.6 Unbounded with optimal
LP 7.7 LP scenarios
LP 7.8 Best fit line
LP 7.11 Dual to the example
LP 7.12 Prove LP solution optimal
LP 7.18cd LP max-flow variants

Class History

CS 8803-GA

This course was known as CS 8803-GA for Fall 2017, Spring 2018, and Fall 2018. It was originally taught by Eric Vigoda (who did the Udacity lectures), but Gerandy Brito took over in Fall 2018. Dr. Vigoda's course pages were:

Other

Prior to GA, CS 6505 Computability, Complexity, & Algorithms was OMSCS's required algorithms course. It was replaced in Fall 2017 with GA. An on-campus version of CCA is still taught. Resources from either of those sites may be useful in GA.

OMSCS's algorithms courses have had 4 instructors in 5 years: Charlie Brubaker, Chris Pryby, Eric Vigoda, Gerandy Brito.