ReadingAssignments < CS401

CS401 Web>WebLeftBar>ReadingAssignments (2012-12-08, Main.sggharib) (raw view)EditAttach
---+ Reading Assignments
 I strongly recommend the following reading before the relevant classes.

   1 [Monday, August 27] Kleinberg and Tardos, Chapter 1.
   1 [Wednesday, August 29] Kleinberg and Tardos, Sections 2.1, 2.2, and 2.4. Skim 2.3.
   1 [Wednesday, September 5] Kleinberg and Tardos, Chapter 3.
   1 [Friday, September 7] Kleinberg and Tardos, Chapter 4.1.
   1 [Wednesday, September 12] Kleinberg and Tardos, Chapter 4.2.
   1 [Friday, September 14] Kleinberg and Tardos, Chapter 4.4.
   1 [Monday, September 17] Kleinberg and Tardos, Chapter 4.5.
   1 [Friday, September 21] Kleinberg and Tardos, Chapter 4.6 and 4.7.
   1 [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.
   1 [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).
   1 [Friday, September 28] Here are some lecture notes for our discussion on sorting lower bounds (which is not in the text): [[%ATTACHURL%/SortingLowerBound.pdf][SortingLowerBound.pdf]].
   1 [Monday, October 1] Kleinberg and Tardos, Chapter 5.3 (counting inversions).
   1 [Wednesday, October 3] Kleinberg and Tardos, Chapter 5.4 (closest pair of points).
   1 [Friday, October 5] Kleinberg and Tardos, Chapter 5.5 (integer multiplication).
   1 [Monday, October 8] Kleinberg and Tardos, Chapter 6.1 (weighted interval scheduling).
   1 [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 .
   1 [Friday, October 12] Kleinberg and Tardos, Chapter 6.3.
   1 [Monday, October 15] Kleinberg and Tardos, Chapter 6.4.
   1 [Wednesday, October 17] Kleinberg and Tardos, Chapter 6.6.
   1 [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.
   1 [Monday, October 22] Kleinberg and Tardos, Chapter 7.1.
   1 [Friday, October 26] Kleinberg and Tardos, Chapter 7.2.
   1 [Friday, Nov 2] Kleinberg and Tardos, Chapter 7.3.
   1 [Monday, Nov 5] Kleinberg and Tardos, Chapter 7.5.
   1 [Wednesday, Nov 7] Kleinberg and Tardos, Chapter 7.6.
   1 [Friday, Nov 9] Kleinberg and Tardos, Chapter 7.7.
   1 [Monday, Nov 12] Kleinberg and Tardos, Chapter 7.11.
   1 [Wednesday, Nov 14] Kleinberg and Tardos, Chapter 8.1-8.3.
   1 [Monday, Nov 19] The reference for this lecture is pages 320-322 of Introduction to the Theory of Computation by Michael Sipser, 3rd Edition. (The NP-completeness proof of Subset-Sum.)
   1 [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. (The proof of the Cook-Levin Theorem.)
   1 [Friday, Nov 30] A review of Turing machines, the Church-Turing thesis, and non-determinism.
   1 [Monday, Dec 3] Proof of the Cook-Levin theorem (Sipser, pages 304-311, 3rd edition).
   1 [Friday, Dec 7] An introduction to the PCP theorem (Modern Computational Complexity, Arora and Barak, Chapter 11).