Reading Assignments

I strongly recommend the following reading before the relevant classes.

1. [Monday, August 27] Kleinberg and Tardos, Chapter 1.
2. [Wednesday, August 29] Kleinberg and Tardos, Sections 2.1, 2.2, and 2.4. Skim 2.3.
3. [Wednesday, September 5] Kleinberg and Tardos, Chapter 3.
4. [Friday, September 7] Kleinberg and Tardos, Chapter 4.1.
5. [Wednesday, September 12] Kleinberg and Tardos, Chapter 4.2.
6. [Friday, September 14] Kleinberg and Tardos, Chapter 4.4.
7. [Monday, September 17] Kleinberg and Tardos, Chapter 4.5.
8. [Friday, September 21] Kleinberg and Tardos, Chapter 4.6 and 4.7.
9. [Monday, September 24] Kleinberg and Tardos, Chapter 5.1. Please read up also on the Master Theorem, which is not in Kleinberg and Tardos, for example at http://en.wikipedia.org/wiki/Master_theorem. Aside: If you're interested in data compression, I encourage you to read Chapter 4.8 on Huffman codes in Kleinberg and Tardos as independent (ie optional) reading.
10. [Wednesday, September 26] Please read up on Annihilators for solving recurrences, as well as the Master Theorem's statement, at http://compbio.cs.uic.edu/~tanya/teaching/cs401/notes/recurrences.pdf (link courtesy of Prof. Berger-Wolf).
11. [Friday, September 28] Here are some lecture notes for our discussion on sorting lower bounds (which is not in the text): SortingLowerBound.pdf.
12. [Monday, October 1] Kleinberg and Tardos, Chapter 5.3 (counting inversions).
13. [Wednesday, October 3] Kleinberg and Tardos, Chapter 5.4 (closest pair of points).
14. [Friday, October 5] Kleinberg and Tardos, Chapter 5.5 (integer multiplication).
15. [Monday, October 8] Kleinberg and Tardos, Chapter 6.1 (weighted interval scheduling).
16. [Wednesday, October 10] Kleinberg and Tardos, Chapter 6.2, and the following link on Coin Changing (from Northeastern University, College of Computer and Information Science): http://www.ccs.neu.edu/home/jaa/CSG713.04F/Information/Handouts/dyn_prog.pdf .
17. [Friday, October 12] Kleinberg and Tardos, Chapter 6.3.
18. [Monday, October 15] Kleinberg and Tardos, Chapter 6.4.
19. [Wednesday, October 17] Kleinberg and Tardos, Chapter 6.6.
20. [Friday, October 19] No assigned reading, Shi covered Floyd-Warshall algorithm for all-pairs shortest paths in class. For reference purposes, please see Cormen, Leiserson, Rivest, and Stein's book "Introduction to Algorithms" for an exposition of this topic.
21. [Monday, October 22] Kleinberg and Tardos, Chapter 7.1.
22. [Friday, October 26] Kleinberg and Tardos, Chapter 7.2.
23. [Friday, Nov 2] Kleinberg and Tardos, Chapter 7.3.
24. [Monday, Nov 5] Kleinberg and Tardos, Chapter 7.5.
25. [Wednesday, Nov 7] Kleinberg and Tardos, Chapter 7.6.
26. [Friday, Nov 9] Kleinberg and Tardos, Chapter 7.7.
27. [Monday, Nov 12] Kleinberg and Tardos, Chapter 7.11.
28. [Wednesday, Nov 14] Kleinberg and Tardos, Chapter 8.1-8.3.
29. [Monday, Nov 19] The reference for this lecture is pages 320-322 of Introduction to the Theory of Computation by Michael Sipser, 3rd Edition.
30. [Monday, Nov 26] The reference for the next few lectures is pages 304-311 of Introduction to the Theory of Computation by Michael Sipser, 3rd Edition.
31. [Friday, Nov 30] A review of Turing machines, the Church-Turing thesis, and non-determinism.
32. [Monday, Dec 3] Proof of the Cook-Levin theorem (Sipser, pages 304-311, 3rd edition).
33. [Friday, Dec 7] An introduction to the PCP theorem (Modern Computational Complexity, Arora and Barak, Chapter 11).