Welcome to introductory algorithms. We have four main sections.

- Divide and Conquer
- Graph Algorithms
- Dynamic Programming
- NP-completeness

We will follow the book Algorithms by Dasgupta, Papadimitriou, and Vazirani but there are other excellent books:

- Algorithm Design by Kleinberg, Tardos
- I may refer to pieces from this book over the DPV book

- Algorithms by Jeff Erickson
- This book is available online for free.

- Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein
- Computational Intractability: A Guide to Algorithmic Lower Bounds by Demaine, Gasarch, Hajiaghayi
- This book is more of a sucessor to the Gary and Johnson book
- Where it intersects with this class is on NP-completeness

I may occasionally pull from these books. I recommend you follow and read the DPV book.

- Lecturer: Abrahim Ladha
- TAs:
- Malav Patel (Head)
- Himanshu Goyal
- Kuhuk Pandya
- Mansi Bhandari
- Saigautam Bonam
- Stephan Huan
- Bharat Goyal
- Aditya Kumaran
- Shresha Das
- Rohit Arunachalam
- Eric (Jiacheng) Shang
- Aditya Kaushik
- Saahir Dhanani
- Joseph Gulian

- Office Hours are on the second floor of Klaus inbetween the two theory labs.

- Five exams, each worth 20%
- Your lowest exam score is dropped
- The last exam will take place during the final
- If you are happy with your grade, the final is effectively optional

- Problem sets, worth 20%

This is subject to change as I realize what takes more or less time.

Date | Subject | Reading (book) | Reading (PDF) | Reading (CLRS) | Notes | Other |
---|---|---|---|---|---|---|

01/10/23 | Introduction | pg 1-10 | pg 11-19 | notes | ||

01/12/23 | Arithmetic | pg 11-15,45-47 | pg 21-24,51-53 | |||

01/17/23 | Divide and Conquer | pg 48-54 | pg 54-59 | |||

01/19/23 | Cryptography | pg 23-34 | pg 28-42 | notes | ||

01/24/23 | Fast Fourier Transform | pg 57-70 | pg 64-78 | notes | ||

01/26/23 | Topological Sorting | pg 80-91 | pg 91-101 | notes | ||

01/31/23 | Review | |||||

02/02/23 | Exam 1 | |||||

02/07/23 | Strongly Connected Components | pg 91-95 | pg 101-105 | notes | ||

02/09/23 | Kruskal's Algorithm | pg 127-137 | pg 133-142 | notes | ||

02/14/23 | Dijkstra's Algorithm | pg 104-117 | pg 109-122 | notes | ||

02/16/23 | Max Flow Min Cut Theorem | pg 198-204 | pg 199-205 | notes | ||

02/21/23 | Review | |||||

02/23/23 | Exam 2 | |||||

02/28/23 | Bellman-Ford | pg 115-120,156-157 | pg 122-125,161-162 | |||

03/02/23 | Longest Subsequences | pg 390-396 | ||||

03/07/23 | Chain Matrix Multiplication | pg 168-171 | pg 174-175 | pg 370-377 | ||

03/09/23 | Knapsack | |||||

03/14/23 | Review | |||||

03/16/23 | Exam 3 | |||||

03/28/23 | Introduction to NP-completeness | notes pre notes | ||||

03/30/23 | Satisfiability | notes pre notes | ||||

04/04/23 | Independent Set, Vertex Cover | pre notes | ||||

04/06/23 | Clique, Subset Sum | notes pre notes | ||||

04/11/23 | Super Mario is NP-hard | pre note | paper | |||

04/13/23 | Review | |||||

04/18/23 | Exam 4 | |||||

04/20/23 | Monte-Carlo | pre note | ||||

04/25/23 | Shor's Algorithm | notes |

As a member of the Georgia Tech community, I am committed to creating a learning environment in which all of my students feel safe and included. Because we are individuals with varying needs, I am reliant on your feedback to achieve this goal. To that end, I invite you to enter into dialogue with me about the things I can stop, start, and continue doing to make my classroom an environment in which every student feels valued and can engage actively in our learning community.