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. (The NP-completeness proof of Subset-Sum.)
  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. (The proof of the Cook-Levin Theorem.)
  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).
Topic attachments
I Attachment Action Size Date Who Comment
PDFpdf SortingLowerBound.pdf manage 95.3 K 2012-09-29 - 03:02 UnknownUser  
Topic revision: r24 - 2012-12-08 - 17:40:33 - Main.sggharib
 
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF