CS3510 Algorithms

Spring 2023 9:30-10:45AM Instructional Center 103

Course Information

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.

People

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.

Evaluation

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%

Schedule

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

Statement of Intent for Classroom Inclusivity

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.