| Lect. | Date | Topics | Reading |
|---|---|---|---|
| 1 | Sept. 3 |
Introduction, Model of computation, complexity measures,
worst-case complexity | CLR: Chapt. 1 |
| 2 | Sept. 5 |
Big-Oh, Big-Omega, Big-Theta notation,
summation techniques, recurrence relations |
CLR: Chapt. 2, 3
BB: Chapt. 1, 3 |
| 3 | Sept. 10 |
Recurrence relations: expansion
and substitution methods |
CLR: Chapt. 4
BB: Sect. 4.7 |
| 4 | Sept. 12 |
Recurrence relations: induction method
Sorting: merge sort |
CLR: Chapt. 3
BB: Sect. 1.6, 7.4 |
| 5 | Sept. 17 |
Sorting: merge sort, heap sort
Time and Space complexity |
CLR: Chapt. 7
BB: Sect. 5.7 |
| 6 | Sept. 19 |
Quick sort, worst-case running
average-case analysis |
CLR: Chapt. 8
BB: Sect. 7.4.2 AHU: CHapt. 3 |
| 7 | Sept. 24 | Comparison trees, lower bound on comparison-based
sorting,
radix and bucket sort. Selection: Expected linear-time algorithm |
CLR: Chapt. 9, 10
AHU: Chapt. 3 |
| 8 | Sept. 26 | Selection: Worst-case linear-time algorithm | CLR: Chapt. 10
AHU: Chapt. 3 BB: Section 7.5 |
| 9 | Oct. 1 | Binary search trees | CLR: Chapt 13 |
| 10 | Oct. 3 | Red-black trees: Definition, insertion and merge procedures | CLR: Chapt 14 |
| 11 | Oct. 8 |
Red-black trees: Deletion procedure
External-memorydata structures |
CLR: Chapt 14
CLR: Chapt 19 |
| 12 | Oct. 10 |
B-trees: Definition; search and insertion procedures
Read the deletions procedure from the textbook |
CLR: Chapt 19 |
| 13 | Oct. 15 | Midterm exam | |
| 14 | Oct. 17 | Dynamic programming: Matrix multiplication | CLR: Chapt 16 |
| 15 | Oct. 22 | Fall Break | |
| 16 | Oct. 24 |
Dynamic programming: Longest common subsequence Greedy algorithms: Bin packing |
CLR: Chapt 16,17 BB: Chapt. 8,13 |
| 17 | Oct. 29 | Greedy algorithms: Scheduling, binary codes | CLR: Chapt 17 |
| 18 | Oct. 31 | Graph algorithms: Terminology, breadth first search | CLR: Chapt 23 |
| 19 | Nov. 5 | Geometric algorithms: Convex hull | CLR: Chapt 35 |
| 20 | Nov. 7 |
Geometric algorithms: Sweep-line technique
Segment intersection |
CLR: Chapt 35 |
| 21 | Nov. 12 |
Graph algorithms: Depth first search,
applications of dfs, topological sort |
CLR: Secs 23.3, 23.4 |
| 22 | Nov. 14 | Amortized analysis: accounting method, potential method | CLR: Chapt 18 |
| 23 | Nov. 19 |
Union-find data structure: array and linked-list
representations
Spanning tree and minimum spanning tree |
CLR: Secs 22.1, 22.2
CLR: Sec 24.1 |
| 24 | Nov. 21 |
Union-find data structure:
Amortized running time of
linked-list representation, tree representation, path compression |
CLR: Secs 22.2, 22.3 |
| 25 | Nov. 26 | Minimum spanning tree, Kuskal's algorithm | CLR: Secs 24.1, 24.2 |
| 26 | Nov. 28 | Thanksgiving Break | |
| 27 | Dec. 3 |
All pair shortest paths: Floyd-Warshal algorithm
Single source shortest path: Dijkstra's algorithm Read Sections 25.1 and 26.1 also. |
CLR: Secs 26.2
CLR: Secs 25.1, 25.2 |
| 28 | Dec. 5 |
Randomized algorithms:
Las Vegas and Monte Carlo algorithms Checking polynomial identity, matching Hashing, universal hashing, skip lists |
Two Handouts |
| 29 | Dec. 10 |
Skip lists: data structure, insertion, membership
NP Completeness: Definition Examples: satisfiability, vertex cover, hamiltonian cycle |
Handout
CLR: Chapt 36 |
| 30 | Dec. 12 |
NP Completeness: Polynomial-time reduction
Independent set, vertex cover, clique Hamiltonian cycle, traveling salesperson |
CLR: Chapts 36 |
Agarwal's Home Page