Course schedule

The table below gives the material covered in class, and points to the corresponding section in the text books.

Date Material Comments and References
Aug. 21 Administrative issues Syllabus handed
Aug. 23 What is an efficient algorithm? Worst-case versus average case complexity. [M] Chap. 1 and 3.2; [B] Chap. 1.
Aug. 28 Probability, permutations, summation formulas. [M] Chap. 3.4; [B] 1.3
Aug. 30 Euler-Maclaurin formula [M] Chap. 2; [B] 3.4.
.
Sept. 4 Mathematical Induction [M] Chap. 2; [B] 3.4.
Sept. 6 Elements of number theory Lecture; Homework 1 due!
Sept. 11 Analysis of algorithms and Growth of Functions [M] Chap. 3.2; [B] 1.4, 1.5.
Sept. 13 Asymptotic notations [M] 3.2, [B} 1.5
Sept. 18 Analysis of Algorithms [M] Chap. 3.5; [B] 3.6.; Homework 2 due!
Sept. 20 Asymptotics: hierarchy of growth Lecture
Sept. 25 Asymptotics: equivalence Lecture
Sept. 27 Asymptotics: more Lecture
.
Oct. 2 Asymptotics: more Lecture
Oct. 4 Analysis of Algorithms: A search Algorithm [B] 1.6 Homework 3 due!
Oct. 6 Binary search [B] 1.6 Read [B] Sec. 1.6.3
Oct. 9 OCTOBER BREAK
Oct. 11 Recurrences [M] Chap. 3.5; [B] 3.6.;
Oct. 16 MIDTERM Homework 4 due
Oct. 18 Divide-and-conquer recurrences Lecture; Aho, Hopcroft, Ullman book.
Oct. 23 Application of Divide-and-Conquer: Sorting [B] 4.6; [M] 6.4.3
Oct. 25 Sorting Algorithms [B] 4.4; [M] 6.4.4
Oct. 30 Lower Bound on Sorting [B] 4.7; [M] 6.4.6
.
Nov. 1 Lower Bound [B] 4.7,
Nov. 6 Sorting: Quicksort [B] 4.4; [M] 6.4.4
Nov. 8 TD> Sorting: Heaps and HeapSort [B] 4.8; [M] 6.4.5
Nov. 13 Algorithms on Sequences [B] 4.8; [M] 6.4.5
Nov. 15 String Pattern Matching [B] 4.7; [M] 6.4.6
Nov. 20 String Pattern Matching [M] 6.5
Nov. 27 Introdcution to Graphs [B] Chap 7; [M] Chap 7
Nov. 29 DST and Shortest Path [B] Chap 7; [M] Chap 7
.
Dec. 4 Shortest paths and Biconnected componets [B] Chap 7; [M] Chap 7 Homework 5 and 6 due
Dec. 6 Finding Strongly Connected Components [B] Chap 7; [M] Chap 7
.
Dec. 12 FINAL EXAM 3:20pm- 5:20pm CL50