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 |