Graduate Algorithms at Georgia Tech covers many key algorithms, design techniques and analysis. Each algorithm covered in class is well documented elsewhere, so instead of walking through them, this is a hub of resources I found useful while taking the class.
Questions, corrections, additions? @kirk on slack or connect with me on LinkedIn
Advice:
- Prepare early. Make a habit of working through as many problems as you can.
- A large exposure to many problem types is more useful than completely solving a smaller set of problems.
- If an idea doesn't click with one resource, use a different resource.
General Resources:
- The official text is DPV: Dasgupta, Papadimitriou, Vazirani
- Algorithm Design (Kleinberg, Tardos)
- KT slides and solutions
- CLRS. The classic. Solutions here & here.
Lectures:
This MIT OCW course is an excellent add on resource.
I've created YouTube playlists for most of the GT lectures:
I'll add the rest here if time permits.
Notes and Flash cards:
- Dr. Vigoda's notes can be found on the course website
- Dan Frakes put together an excellent set of course notes
- Ryan Peach and Sam Sussman created a full set of flash card decks
- Ian Parberry's Lecture Notes: Serves as an excellent "cheat sheet" to many ideas covered.
Topics:
Dynamic Programming:
Dynamic programming is a general algorithm design approach used on many problems. Recursive (top down) and tabular (bottom up) are the two types of approaches, but this class exclusively uses the tabular approach. Practicing many DP problems is key.
- Dynamic Programming pattern overview: Berkeley
- Tushar Roy has an excellent DP series
- Lists of the top N DP problems. If you can solve these efficiently, you'll do well in this section. Top 50, top 20, top 10.
- Geeks for Geeks has a great tutorial series and collection of practice problems
- Leetcode Dynamic Programming
NP Completeness:
- Extra lectures on complexity and reductions: here & here
- Limits to Computing
- Other notes: here & here
Others:
- Linear Programming: A Concise Introduction – Ferguson
- Graph pattern overview: Berkeley
- Note: There are quite a few other topics covered (eg: DC, FFT, RSA, bloom filters) so this list isn't yet comprehensive.
Runtime Complexity Cheat Sheet:
I should also point out that this class is a good start to preparing for technical interviews. Solving problems in interview format isn't covered, but Pramp is an excellent way to practice your interview skills. If you'd like to practice, join me here on Pramp.
Questions, corrections, additions? @kirk on slack or connect with me on LinkedIn
