CS3510 Algorithms

CS3510 Algorithms Spring 2024 9:30-10:45AM TR IC103

People

Lecturer: Abrahim Ladha
TAs:
- Saigautum Bonam
- Aditya Kumaran
- Saahir Dhanani
- Rohit Arunachalam
- Richard Zhang
- Diksha Holla
- Isha Vohra
- Navya Khanna
- Kartik Sinha
- Bharat Goyal
- Shresha Das
- Siri Tanguturi
- Ryan Ma
For office hour times, see the schedule on canvas. They are subject to change.
Office hours are located in CCB 331, the third floor of the CoC building, across the Klaus bridge.
My Office is in CCB 207B, third floor. I have an open door policy. If my door is open, I am available to ask questions.

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. These include the CLRS book, the Klienberg Tardos book, and Algorithms by Erickson. I will mostly post reading from DPV and from CLRS. It is expected you read these sections along with the posted notes.

Evaluation

Five exams, including the final, each worth 20%
Your lowest exam score is dropped effectively making the final optional
Problem sets, worth 20%

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

No.	Date	Subject	Notes	DPV book	DPV PDF	CLRS	other
01	Jan 09	Introduction and Divconquer	notes	pg 1-10	pg 11-20
02	Jan 11	The Master Theorem and MergeSort	notes	pg 49-53	pg 53-59	pg 29-39, 93-106
03	Jan 16	Arithmetic	notes	pg 11-15,18-19,45-47,56-57	pg 21-24, 28, 51-53,62-63
04	Jan 18	Cryptography	notes	pg 16-34	pg 25-34
	Jan 23	Review
	Jan 25	Exam 1
05	Jan 30	DFS, Topsort, SCC	notes	pg 80-95	pg 87-100
06	Feb 01	BFS, Dijkstra	notes	pg 104-117	pg 109-122
07	Feb 06	Kruskals	notes	pg 127-138	pg 133-145
08	Feb 08	Bellman-Ford and Floyd-Warshall	notes
	Feb 13	Review
	Feb 15	Exam 2
09	Feb 20	Dynamic Programming	notes				Competitive Programmer’s Handbook
10	Feb 22	Longest Subsequences	notes	157-166	162-170	390-396
11	Feb 27	Chain Matrix Multiplication	notes			370-378
12	Feb 29	Knapsack	notes
	Mar 05	Review
	Mar 07	Exam 3
13	Mar 12	NP-completeness	notes	all ch8		all ch 34	Erickson
14	Mar 14	Satisfiability, Mario	notes				Mario,Many more
15	Mar 26	Independent Set, Vertex Cover	notes
16	Mar 28	Subset Sum and Knapsack	notes
17	Apr 02	Review
	Apr 04	Exam 4
	Apr 09	Max-Flow Min-Cut Theorem	notes			all of ch26	Erickson ch10
18	Apr 11	Linear Programming	notes
19	Apr 16	LP Duality	notes
20	Apr 18	Randomization
21	Apr 23	Approximation
	Dec 12	Final Exam

Other Resources

Last Semester’s Notes

Erickson’s Free Book

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.