Here is a list of reading assignments corresponding to the material presented in class. Remember, reading goes beyond the material covered in lecture, offering more examples problems, and more detailed proofs than what can be covered during regular lecture time. Reading is a fundamental part of the workload for this course, and all students are expected to read the chapters from the textbook as assigned.
The list of reading assignments is tentative, and will be expanded and modified as we move on with the course. Treat it as a reference of what has been covered so far (or what you are supposed to have already read), and what you can expect to see in the coming week if you wish to read ahead.
Week 1: Chapter 1 (Introduction), Chapter 2 (Basics), Chapter 3 (Graphs). This is quite a bit of reading, but it should be mostly review from what you have already learned in prerequisite courses.
Week 2-3: Chapter 4: Greedy Algorirhms. Specific topics covered in class: interval scheduling (4.1, 4.2), minimum spanning trees (4.5, 4.6), and clustering (4.7). Read the entire chapter for more applications and examples, including the solved exercises.
Week 3-4: Chapter 5: Divide and Conquer. Topics covered in class: Mergesort (5.1), Recurrence Relations (5.2), Counting inversions (5.3), and Fast Fourier Transform and fast polynomial multiplication (5.6). As usual, you should read the entire chapter for additional examples of divide and conquer algorithms.
Week 4-5: Chapter 6: Dynamic Programming. Topics covered in class: Weighted Interval Scheduling (6.1), Memoization and Iterative algorithms (6.2), Subset-sum (6.4), Sequence alignment problems (6.4, 6.5, 6.6). For additional examples and applications read also 6.3, 6.8, 6.9, 6.10.
Midterm: The midterm exam is scheduled on Monday February 11, during regular class time, on the first day of week 6. The exam covers all of Chapters 1-6. Here is a sample midterm from a previous quarter. Your midterm exam will be somehow different in format, but you can still use it as preparation material. Additional resources to prepare for the exam can be found here
Week 6-7: Network Flow (Chapter 7). We will cover most of the chapter, starting from the problem definition (7.1) and application to bipartite matching (7.5), and followed by algorithms and applications.
Week 8: NP and computational intractability (Chapters 8 and 10).
Week 9: Approximation Algorithms (Chapter 11).
Week 10: Review
Homework 1: Due Wednesday, January 30, 2019. Submission via gradescope.
Homework 2: Due Friday, February 8.
Homework 3: Due Saturday February 23. (tex file, for your convenience, not needed to work on the assignment.)
Homework 4: Due Wednesday March 6. (tex file, for your convenience, not needed to work on the assignment.)
Homework 5: Due Thursday March 14. (tex file, for your convenience, not needed to work on the assignment.)