TWiki> CS401 Web>WebLeftBar>ReadingAssignments (revision 20)EditAttach

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.
Topic attachments
I Attachment Action Size Date Who Comment
PDFpdf SortingLowerBound.pdf manage 95.3 K 2012-09-29 - 03:02 UnknownUser  
Edit | Attach | Print version | History: r24 | r22 < r21 < r20 < r19 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r20 - 2012-11-18 - 02:01:13 - 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