Distribution List

1. Course Syllabus
2. There are past video lectures online for some of the topics covered in the class. I will point you to those when appropriate. The past videos are found at
   video list of past lectures
   
   
3. Current lectures will also be videod and put online. The link to those is Videos of current lectures
   
   
4. A Running class outline and recap
   
   
5. Introduction to complexity and rules of the game
6. First homework, due Friday October 1.
7. A rant on induction - useful if you are unsure about how to do inductive proofs
8. Solving recurrence relations by unwrapping and the master method
9. Another exposition on the master method for solving divide and conquer recurrences
10. Second homework, due Monday October 10. Don't wait until the last minute to start this, even though you have more than a week.
11. A full proof of correctness of the algorithm to count the number of inversions.
12. Permanent office hours for the TA and Gusfield are listed on the updated course syllabus.
13. The Midterm will be Monday October 25.
14. To do the unwrapping for a recurrence problem on Homework 2, you can assume that the base case is T(n) = cn for some constant c. What c is exactly will not influence the asymptotic solution.
15. The algorithm Select (S,k) is on page 728 of the book. In my printing it defines it as the k'th largest element in S, but that is clearly wrong - it is the k'th smallest element.
16. For a complete derivation of the mean of the geometric distribution, see page 228, Example 6.4 in the following: a chapter on expected value You only need to read page 228, but the chapter is a good introduction to expected value, especially the early part of the chapter. You will need to understand the expected value of a geometric distribution when we analyze randomized Select and randomized Quicksort.
17. Third homework, due Weds. October 20. This homework is very conceptually oriented. Don't wait
18. Prof. Gusfield is out of town and will not have office hours on thursday.
19. Solutions to hw 1 The ID and password given in class on weds. should work now. Please let me know if it does not.
20. Solutions to hw 2
21. Fourth homework, due Weds. October 27.
22. The midterm is open book and class notes (notes you took or anything distributed on the class website, but no additional materials or electronics) and will cover material and topics through the class yesterday, October 20.
23. Solutions to hw 3
24. Please bring a small blue book (if you see this in time), with regular lined pages, for the midterm exam. Do not bring an engineering blue book that is filled with graph paper.
25. On HW 4, problem 5, you can assume that the road is straight with no turns or curves. For extra credit, try to solve the problem where the road is not assumed to be straight. I don't know a solution for that case.
26. Solutions to Midterm
27. Fifth homework, due Friday November 5. Start early - I think it may be hard.
28. Midterm scores out of 100 pts: Mean 69, median 72, highest grad student 100, highest undergrad 99. Your score should be available on smartsite. If smartsite also reports a course grade, ignore that.
29. Garrett is back and will make office hours.
30. Notes on the unique-decypherability problem.
31. Sixth homework, due Weds. November 17.
32. Notes on traceback for the maximum weight independent set problem on a tree.
33. ud.pl Perl program to determine if a code is UD.
34. Notes on the Z-algorithm
35. Professor Gusfield will not have office hours on thursday Nov. 17
36. *MODIFIED* Seventh homework, due Weds. November 24. Problem 3 has changed a bit (to clarify it) since homework 7 was first posted. Also, the tone of problem 2 makes it seem that the conjecture is surely correct. It might not be, so don't exclude that possibility.
37. Professor Gusfield's office hour on tuesday Nov. 23 will be 2-3 instead of 12-1. Sorry for the last minute change.
38. Solutions to hw 4
39. Eight homework, due Friday Dec. 3. Problem 3 was corrected monday evening, so reload if you downloaded before then.
40. Solutions to hw 5 The solution to the tree coloring DP problem as corrected monday evening, so reload if you downloaded before then.
41. Partial Solutions to hw 6
42. Partial Solutions to hw 7 The solution for problem 4 has been corrected, Dec. 8.
43. Gusfield will have office hours tuesday Dec. 7 12-1 and Garrett will have office hours weds. Dec. 8 12-1.
44. The final exam is Dec. 8 6-8 in the classroom. The exam will be open book and notes the same way as the midterm. Everything in the course is fair-game for the exam, including material from the last lecture and homework. However, the emphasis will be on material since the midterm. Please bring a small bluebook (not grid ruled) and a sharp enough and dark enough pencil (or pen) to make it easy to read your writing.
45. Solutions to hw 8
46. The portion of chapter 8 that was covered in class is sections 8.1, 8.2, 8.3 and part of the first page of section 8.4 (until the start of circuit SAT, which we did not cover). Nothing else in chapter 8 was covered.
47. Solutions to final exam Don't look if you haven't taken it yet.
48. Monday Dec. 13. The final exam is graded and you should be able to see your final exam score on Smartsite, but there are still some homeworks to grade so course grades have not been assigned. The median and mean on the final were 73, 69. The max possible was 125 and the highest score was 121. If smartsite reports a course grade, ignore that.