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
|