Along the way, we will encounter the notion of approximation algorithms for optimization problems, as well as algorithms for other models of computation such as streaming, online and distributed computing.
Background and pre-requisites
The course requires as pre-requisites (a) an undergraduate level discrete structures class, as well as (b) UG-level data-structures or algorithms course. Specifically, the instructor will assume knowledge of notions from graph theory, probability and calculus. Here are some links where you can brush up on the basics:
- Chapters 1-5 of https://algs4.cs.princeton.edu/home/
- Chapters 1, 2, 6, 12 of http://www.cs.utah.edu/~bhaskara/courses/LehmanLeighton.pdf
Course email: firstname.lastname@example.org
Instructor (Prof Aditya Bhaskara) office hours: Tue, Thu (1:30-2:30 PM). These will be held in MEB 3470.
TA office hours will be
- Vivek Gupta (email@example.com- Wednesday 2:00 pm to 4:00 pm in MEB 3423)
- Pegah Nokhiz (firstname.lastname@example.org - Mondays 10:30 am to 12:30 pm in MEB 3421)
- Kanchana Ruwanpathirana (email@example.com - Friday 9:00 am to 11:00 am in MEB 3423)
The course has six homeworks, the best five of which will count towards your grade. Together, HWs will account for 60% of your grade. We will also have an in-class mid-term (1 hr 15 min) and an in-class final exam (2 hrs). These will count for 15% and 25% of your grade respectively.
The midterm will be on Thursday, October 03 (10:45 - 12:05)
The date for the final exam is determined by the university. This year, it will be on Wednesday, December 11 (10:30 - 12:30).
A detailed overview of the course policies can be found on: CS 6150 - Course Policies
What is the texbook for the course?
As is fairly common with graduate-level courses, we will not follow a single textbook. The lecture slides, videos and notes/links posted will be the main resources. However, given the fairly fundamental nature of the topics covered, there are many excellent resources! Here is a small subset:
- Book by J. Kleinberg, E. Tardos. Algorithm Design.
- Classic, comprehensive textbook by T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms.
- Book by S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms.
- Lecture notes by Jeff Erickson (an excellent set of notes, and many cool exercises).
- Book by R. Motwani, P. Raghavan. Randomized Algorithms.
- Book by C. Moore, S. Mertens. Nature of Computation (another fascinating read, for the slightly advanced students).
Why are there no programming assignments?
The aim of the course is to introduce the ideas behind designing and analyzing algorithms. We will thus use only pseudocode to describe algorithms. That said, students should be able to implement any algorithm we see in class.
I will not be able to attend class. Will videos and/or notes suffice?
Starting this year, unfortunately you cannot take the course if you are not able to attend in person. This is because in the past, despite the best efforts of the TAs, we have had a few lectures in which recording has failed, resulting in a bad experience for students.
Week 1 (August 20, 22). Topics: Introduction, course overview, basic review.
Lecture 1: Introduction to the course, logistics, analysis basics, data structures (overview, examples). [Video] [Slides] [Notes]
Lecture 2: Data structures for sets of integers, strings. [Slides] [Video] [Notes]
Week 2 (August 27, 29). Topics: Divide and conquer, analyzing recurrences.
Lecture 3: Divide and conquer algorithms. Inductive analysis via recurrences. [Video][Slides] [Notes -- Book chapter]
Lecture 4: Divide and conquer, more examples. [Video][Slides][Notes -- Book chapter]
Week 3 (September 3, 5). Topics: Divide and conquer (contd.), dynamic programming.
Lecture 5: Conclude divide and conquer -- linear time selection. [Video][Slides][Notes]
Lecture 6: Dynamic programming: subset sum, sub-problems. [Video][Slides] [Old survey by Bellman] [Interview with Bellman about the origins][Notes]
Week 4 (September 10, 12). Topics: Dynamic programming (contd.), Greedy algorithms.
Week 5 (September 17, 19). Topics: Greedy paradigm (contd.), local search
Week 6 (September 24, 26). Topics: Graph algorithms (continued)
Lecture 11: Shortest paths in graphs [Video][Slides][Notes -- book chapter]
Lecture 12: Shortest paths (contd.) [Video][Slides][Notes -- book chapter; pay attention to sections 4.4.1 and 4.4.2; we saw the latter in class]
Week 7 (October 1, 3). Topics: Flows and cuts
Week 8 (October 15, 17). Randomized algorithms
Week 9 (October 22, 24). Randomized algorithms (continued)
Week 10 (October 29, 31). Randomized algorithms (continued)
Week 11 (November 5, 7). Optimization and linear programming
Week 12 (November 12, 14). Misc topics: algorithmic fairness, online algorithms
Week 13 (November 19, 21). NP completeness
Week 14 (November 26). Intractability (contd.)
Week 15 (December 3, 5). Course review
The syllabus page shows a table-oriented view of the course schedule, and the basics of course grading. You can add any other comments, notes, or thoughts you have about the course structure, course policies or anything else.
To add some comments, click the "Edit" link at the top.