CS3510 Algorithms

CS3510 Algorithms Fall 2024 2-3:15PM MW Howey L1

People

Lecturer: Abrahim Ladha
TAs:
- Richard Zhang (Head TA)
- Diksha Holla
- Isha Vohra
- Navya Khanna
- Kartik Sinha
- Shresha Das
- Ryan Ma
- Sachitt Arora
- Miles Gordon
- Taiki Aiba
- Frank Qiang
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	DPV book	DPV PDF	CLRS	other
01	Aug 19	Introduction and Divconquer	pg 1-10	pg 11-20
02	Aug 21	The Master Theorem and MergeSort	pg 49-53	pg 53-59	pg 29-39, 93-106
03	Aug 26	Arithmetic	pg 11-15,18-19,45-47,56-57	pg 21-24, 28, 51-53,62-63
04	Aug 28	Quicksort	pg 16-34	pg 25-34	pg 170
	Sep 04	Review
	Sep 09	Exam 1
05	Sep 11	DFS, Topsort, SCC	pg 80-95	pg 87-100
06	Sep 16	BFS, Dijkstra	pg 104-117	pg 109-122
07	Sep 18	Kruskals	pg 127-138	pg 133-145
08	Sep 23	Bellman-Ford and Floyd-Warshall
	Sep 25	Review
	Sep 30	Exam 2
09	Oct 02	Dynamic Programming				Competitive Programmer’s Handbook
10	Oct 07	Longest Subsequences	157-166	162-170	390-396
11	Oct 09	Chain Matrix Multiplication			370-378
12	Oct 16	Knapsack
	Oct 21	Review
	Oct 23	Exam 3
13	Oct 28	NP-completeness	all ch8		all ch 34	Erickson
14	Oct 30	Satisfiability, Mario				Mario,Many more
15	Nov 04	Independent Set, Vertex Cover
16	Nov 06	Subset Sum and Knapsack
17	Nov 11	Review
	Nov 13	Exam 4
	Nov 18	Max-Flow Min-Cut Theorem			all of ch26	Erickson ch10
18	Nov 20	Linear Programming
19	Nov 25	LP Duality
20	Dec 2	Randomization
	Dec 11	Final Exam (2:40-5:30PM)

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.

Integrity policy

Submission of any work not your own can result in anything from a zero on the assignment to a report to OSI.