Please let us know if you have any trouble downloading, displaying, or printing anything on the course web site!
Lecture notes for graphs are available in two parts: part 1 and part 2.
Lecture notes for dynamic programming are available in four parts: part 1, part 2, part 3, part 4.
There will be a fifth quiz Friday Nov. 6, on dynamic programming. Also on Nov. 6, the first part of the programming project is due. Sample inputs are: instance01 and instance02 , and a sample output is solution01 ; keep in mind that solutions are not unique! The deadline for this first part of the project was extended to Nov. 13.
The fourth homework was assigned Oct. 26, and is due November 9.
Solution sketches for the midterm are here.
The fifth quiz is here .
The fifth homework will be assigned Nov. 11, and is due November 23.
The schedule of the final exam is available: Friday, Dec. 11, 10:30-12:30.
The insertion sort pseudocode, with part of the analysis, is available here .
The first quiz is here .
The second quiz is here .
The office hours are: Monday 2:00 - 3:00 PM and Wednesday 3:00 - 4:00 PM in room SB 229B, or by appointment. However, the office hours for Wednesday August 26 are canceled due to the 20th International Symposium of Mathematical Programming. The first quiz is Friday, August 28. Every student must take the quiz. It covers material listed as "preliminary" in the syllabus. Most is covered in Sections 3, 10, and 12 in the textbook and the Appendices A, B, C.1, C.2, and C.2.
The second quiz, covering asympthotic notation, will be Friday Sept. 18, during the recitation. Every student (including those in Section 03) must take the Friday quizzes unless we agree that you cannot.
Lecture notes on asymptotic notation are here .
The first homework was assigned Sept. 9 and is due Sept. 21. This is the second version - which changes problem 4 according to the class of Sept. 9.
The lecture notes on heaps are here ,
Print the lecture notes on binary search trees , and on binary search trees rotations .
You can download the high-level pseudocode for the greedy multiple-machines scheduling algorithm..
I found on the web the following tutorial on 2-4 trees. See also the wiki page and the wiki page on 2-4 trees. Both references on 2-4 trees describe operations exactly as we need for 2-3 trees. 2-4 trees also have top-down implementations which may be faster by a constant factor. See also lecture notes from U.C. Riverside
The pseudocode for the merge step of mergesort and for the partition procedure of quicksort is available here. You can also download C++ code for quicksort.
You can download lecture notes for recurrence relations, which include the Master Theorem.
The second homework was assigned Sept. 23, and is due Oct. 5.
Friday Oct. 2 there will be a quiz, the data structures studied in class: heaps and search trees. This third quiz was not intended with IDs in the range 1..k, but arbitrary integers.
There will be a fourth quiz Friday Oct. 16, on recurrence relations. Closed books and notes other than the notes we distribute. The fourth quiz is now available.
The third homework was assigned Oct. 7, and is due Oct. 19. Solutions will be posted on Oct. 26th after the class, after which no student solutions will be accepted.
The midterm is Oct. 28, in class, closed notes and closed books except for notes provided by me. Topics to be covered: everything from the class except dynamic programming:
Midterm scores will be posted on blackboard by Friday night. (actually, the last scores were posted Monday morning).
Solution sketches for homework 1 are here.
Solution sketches for homework 2 are here.
Solution sketches for homework 3 are here.