Resources
- Udacity Lectures
- Required textbook: DPV = Algorithms by Dasgupta, Papadimitriou, and Vazirani
- Optional textbook: KT = Algorithm Design by Kleinberg and Tardos
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 | Videos Length (Min) |
|---|---|---|---|---|---|
| 1 | Dynamic Programming 1 | 6 | 6 | DP1, DP2 | 62, 59 |
| 2 | Dynamic Programming 2 | 6 | 6 | DP2, DP3 | 59, 53 |
| 3 | Divide & Conquer 1 | 2 | 5 | DC1, DC2, DC3 | 30, 34, 15 |
| 4 | Divide & Conquer 2 | 2 | 5 | DC4, DC5 | 34, 33 |
| 5 | Exam 1 | ||||
| 6 | Graph Algorithms | 3, 4, 5.1 | 3 | GR1, GR2, GR3 | 60, 30, 36 |
| 7 | Flow on Networks | 7 | 7 | MF1, MF2, MF3, MF4, MF5 | 24, 26, 14, 19, 28 |
| 8 | RSA Cryptosystem | 1 | RA1, RA2 | 44, 72 | |
| 9 | Exam 2 | ||||
| 10 | NP-Completeness | 8 | 8 | NP1, NP2, NP3 | 50, 30, 35 |
| 11 | Linear Programming (LP) | 7 | LP1, LP2, LP3 | 29, 8, 30 | |
| 12 | NP and LP, More Complexity | 8 | 8, 11 | LP4, NP4, NP5 | 48, 20, 12 |
| 13 | Exam 3 | ||||
| 14 | Thanksgiving Break | ||||
| 15 | Markov Chains (Optional) | ||||
| 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.
Check out the official OMSCS page for a recent syllabus: https://www.omscs.gatech.edu/cs-6515-intro-graduate-algorithms
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 the required algorithms course for OMSCS. 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.