**This course has been discontinued. The new course is CS 8803: Graduate Algorithms**

You may still find the course content useful. Check out the Spring 2015 Homework Assignments!

Some prep resources are listed below - the seed for this section comes courtesy of Dr. Joyner, who collated and sent out a wonderful e-mail with CCA prep resources prior to the Fall 2016 offering, as well as Jim Ecker, Dominic Follett-Smith, and the folks of #cs6505.

The general consensus is that the course videos are enjoyable but do not go deeply enough into the concepts to be useful for the nuts and bolts of working problems on exams. Dr. Pryby, the longtime instructor for CCA, has recorded a set of much more detailed videos. They will be posted here when someone gets around to asking him if it's OK to post them here. Maybe that someone is you!

# Official Pre-Req List

- Formal Logic
- Combinatorics
- Graph Theory
- Modular Arithmetic
- Linear Algebra
- Probability
- Algorithms
- Time and Space Complexity

# Prep Resources

## Most Highly Recommended

- Erik Demaine's MIT Algorithms lectures.
- Harry Porter's lectures on Computability.
- The textbooks Discrete Mathematics and Its Applications and Introduction to the Theory of Computation, especially the focus on proofs. Both are recommended for the class

## Mathematical Proofs

- Daniel Velleman's How to Prove It: A Structured Approach
- Richard Hammack's Book of Proof (Creative Commons)
- Ted Sundstrom's Mathematical Reasoning Writing and Proof (Creative Commons) - there is also an associated series of screencast lectures
- If time is limited, you may prefer this short tutorial video

## Other Mathematics

- Tom Leighton's MIT Mathematics for Computer Science lectures
- Lynda's tutorial on Discrete Math
- Gilbert Strang's Linear Algebra lectures may be helpful if you struggle with dynamic programming

## MOOCs

- UCSD's Data Structures and Algorithms Specialization on Coursera. (To take for free, find the courses in the catalog rather than the specialization page, then select Audit.)
- Princeton's Algorithms, Part I and Algorithms, Part II on Coursera.
- Stanford's Algorithms: Design and Analysis, Part 1 and Algorithms: Design and Analysis, Part 2 on Coursera.
- Michael Littman's Intro to Algorithms on Udacity, if you log in with a non-Georgia Tech Udacity account.
- The lectures for CS6505 on Udacity, if you log in with a non-Georgia Tech Udacity account.
- Roughgarden's first and second classes in Algorithms.
- Dan Gusfield's UC Davis lectures.

## Specific Course Topics

### Algorithms

Intro to Algorithm Design & Analysis

- MIT 6.042J Spring 2012 Notes Chapter 14
- CLRS Chapter A
- CLRS Chapter 1
- MIT 6.006 Fall 2011 Lecture 3-7

Divide-and-Conquer

Probabilistic Analysis & Randomized Logarithms

- CLRS Chapter C
- CLRS Chapter 5
- MIT 6.042J Fall 2010 Lecture 14-21
- MIT 6.046J Spring 2015 Lecture 6-8

Dynamic Programming

Greedy Algorithms

- CLRS Chapter B
- CLRS Chapter 16
- MIT 6.046J Spring 2015 Lecture 12 Recitation 6

Amortized Analysis

- CLRS 17
- MIT 6.046J Spring 2015 Lecture 5

Graph Algorithms

- MIT 6.042J Fall 2010 Notes Chapter 5-6
- MIT 6.042J Fall 2010 Lecture 6-10
- CLRS Chapter 22-25
- MIT 6.006 Fall 2011 Lecture 13-18

Flows in Networks

### Computability Theory

Turing Machines

- Sipser Chapter 3
- Harry Porter Lectures 26 - 31
- Udacity Lessons 1-2

Counting

- MIT 6.042J Fall 2010 Notes Chapter 13
- MIT 6.042J Fall 2010 Lecture 9-13

Decidability

- Sipser Chapter 4
- Harry Porter Lectures 32 - 39
- Udacity Lessons 3-4

Mapping Reducibility

- Sipser Chapter 5
- * Harry Porter Lectures 40 - 48
- Udacity Lessons 5

### Complexity Theory

Complexity Space

- Chapter 7 of Sipser
- Chapter 34 of CLRS
- MIT 6.006 Fall 2011 Lecture 23 Recitation 23
- MIT 6.046J Spring 2015 Lecture 16
- Harry Porter Lectures 58 - 64
- ADUNI Algorithms Lecture 16
- Udacity Videos

### Simplex

- A demonstration simplex solver freely available on the web

## Fun Stuff

- Michael Rabin's Turing Centennial Conference talk on the history of computability