Design and Analysis of Algorithms

Tentative Syllabus. Subject to change.

CS 3510 + CS 3511, Spring 2024

Time: Tue/Thu 12:30-1:45pm.
Location: CCB 16
Office hours: TBA. No office hours during first week.
Instructor: Jan van den Brand
TA: Joseph Gulian (Head TA), Jayanee Venkat, Yash Arora, Sera Biju, Amit Singh, Ritvik Chandrashekhar, Max Zhang, Daniel You, Allen Chang, Aditiya Kalyanam, Anubha Mahajan, Dhruv Sharma, Yongyu Qiang, Vivek Atmuri.

Course Page

We use Piazza for announcements, discussions, lecture notes, etc. Please always ask your questions on the discussion board rather than by email.
It is your responsibility to check Piazza for assignments, announcements, and review material.
Canvas is only used for grades and linking to Piazza and Gradescope.

Other Material

The lectures roughly follow the book “Algorithms” by Dasgupta, Papadimitriou, and Vazirani.
Here is a list of good books/resources if you are interested in further reading:

“Algorithms” by Dasgupta, Papadimitriou, and Vazirani
“Algorithms” by Erickson. Free version at https://jeffe.cs.illinois.edu/teaching/algorithms
“Algorithm Design” by Kleinberg and Tardos
“Introduction to Algorithms” by Cormen, Leiserson, Rivest, and Stein
“Algorithms Illuminated” by Roughgarden: videos at http://www.algorithmsilluminated.org
CS 3510 lecture videos by Abernethy at https://gt-cs-3510.github.io/

CS 3510 vs 3511

Students taking CS 3511 (the honors version of CS3510) will have lectures joint with CS3510. Questions on exam and homework may be different.

Exams

There will be 5 exams, 1 hour each. For exam dates, see schedule at the end of the syllabus.
The exams will take place during the usual lecture time (12:30-1:45) in the usual lecture hall (CCB 16). The 5th exam is during the final exam week and will also take place 12:30-1:45.

Homework

There will be problem sets/homework. I expect there to be ~2 problem sets per chapter (see bottom of this page for the list of chapters).
The questions will be theory/proof-based problems but there will also be the occasional programming assignments (ie implement an algorithm).

You are encouraged to collaborate and work in groups, but you must write your own solutions. You must write the names of students you worked with on your homework.
You may look up reference material online and in textbooks to help with your homework but you may not look up, copy, or paraphrase answers to homework questions.
We will use Gradescope for submission and grading.
Solutions must be properly typed pdf. Handwritten solutions will not be accepted. LaTeX (via overleaf or otherwise) is strongly recommended.

Course Policies (late-submission, re-take exam, sickness, etc)

Late-submission of homework:
You can have a total of 8 late days (~1 per problem set) throughout the semester that you can use to submit problem sets late. You can use up to 2 late days per problem set. Any partial day counts as a full day. This budget of 8 late days is intended for events like unexpected illness, but any reason for late submission is fine and you do not need to justify/explain the late submission.
Re-take exam:
If you missed one of the first four exams for extreme circumstances that were out of your hand (e.g., sickness), then you can retake that exam during the last day of class. You cannot retake more than one exam. You cannot retake the 5th/final exam.
Please contact us as soon as possible when it is clear that you cannot take an exam.

For fairness to all students, no other exceptions to these policies will be made for individual students, except for the disability policy.

Disability policy

Students with disabilities who require accommodations for access and participation in this course should register with the Office of Disability Services (ODS). Please contact ODS here:
https://disabilityservices.gatech.edu/.

Regrade requests

Regrade requests can be made for factual errors. Regrade requests cannot be made when the grader did not understand your solution. It is your responsibility to make your answers clear for the graders to understand.

Grade

The final grade will be a weighted average of exams (80%) and homework (20%).
The worst exam grade is dropped. If you are happy with the grade of your first 4 exams, the 5th exam is effectively optional.
The average will determine your final grade. Grade thresholds are A - 90%, B - 80%, C - 70%, D - 60%. The thresholds may change in the future, but they can only change in your favor.
We may reduce the maximum number of points of problem sets/exams, meaning you can reach 100% even with small mistakes. However, the score is capped at 100% per problem set/exam.

Georgia Tech Honor Code

Please read the Georgia Tech Honor Code here:
https://policylibrary.gatech.edu/student-life/academic-honor-code.
Penalties for academic misconduct include getting a zero for an assignment or for the course, see here:
https://osi.gatech.edu/process/academic-misconduct-sanctioning-guidelines.

Topics

The list of topics is as follows. Each topic consists of ~2 weeks of classes.

Divide and Conquer

Graph algorithms

Dynamic Programming

NP Completeness

Other Topics (linear programs, approximation, and/or randomness)

Schedule

This schedule is tentative and subject to change.

Tue		Thu
01/09	Big-O	01/11	Divide&Conquer
01/16	Divide&Conquer	01/18	Divide&Conquer
01/23	Review	01/25	Exam 1
01/30	Graph Algorithms	02/01	Graph Algorithms
02/06	Graph Algorithms	02/08	Graph Algorithms
02/13	Review	02/15	Exam 2
02/20	Dynamic Programming	02/22	Dynamic Programming
02/27	Dynamic Programming	02/29	Dynamic Programming
03/05	Review	03/07	Exam 3
03/12	P, NP, Complexity	03/14	P, NP, Complexity
03/19	Spring Break	03/21	Spring Break
03/26	P, NP, Complexity	03/28	P, NP, Complexity
04/02	Review	04/04	Exam 4
04/09	Open Topics	04/11	Open Topics
04/16	Open Topics	04/18	Open Topics
04/23	Review (Retake exam)	04/25	No class (exam period)
04/30	No class (exam period)	05/02	Exam 5