| Date: | Topic: | Readings: | Lecture notes and handouts: |
| Jan 16 | Administration. Introduction to the course. Intro to pseudocode. | Lecture 1 | |
| Jan 21 | NO CLASS | ||
| Jan 23 | Algorithm analysis: asymptotic notation, time complexity | Chapter 1, Chapter 2 | Lecture 2 |
| Jan 28 | Problem set 1 assigned Algorithm analysis: asymptotic notation, time complexity |
Chapter 3 | Lecture 3 Problem Set 1 |
| Jan 30 | Algorithm analysis: asymptotic notation, time complexity | Lecture 4 | |
| Feb 4 | Stacks, Queues | Chapter 10, pp.197-204 | Lecture 5 |
| Feb 6 | Problem set 1 due - Problem set 2 assigned Lists: singly and doubly linked lists |
Chapter 10, pp.204-209 | Lecture 6
Problem Set 2 |
| Feb 11 | Induction and Recursion | Chapter 4, pp.62-75 | Lecture 7 |
| Feb 13 | Problem set 2 due - Problem set 3 assigned Induction and Recursion |
Chapter 4, pp.62-75 | Lecture 8
Problem Set 3 |
| Feb 18 | NO CLASS (Midterm recess) | ||
| Feb 20 | NO CLASS (Midterm recess) | ||
| Feb 25 | Review for Exam 1 | Lecture 9 | |
| Feb 27 | EXAM 1 | ||
| March 3 | Problem set 3 due Trees: terminology and representation.Traversal algorithms. |
Chapter 10, pp. 214-217 | Lecture 10 |
| March 5 | Problem set 4 assigned Binary Search Trees |
Chapter 12, pp.253-268 | Lecture 11Problem Set 4 |
| March 10 | Binary Search Trees | Lecture 12 | |
| March 12 | Problem set 4 due |
||
| March 17 | Self balancing binary search trees Algorithm Design: divide and conquer | Chapter 13, sec. 13.2, pp.277-279 | Lecture 13 |
| March 19 | Problem set 5 assigned Sorting: merge sort and quick sort |
Chapter 2, sec. 2.3, pp.27-40 Chapter 7, pp.145-159 |
Lecture 14
Problem Set 5 |
| March 24 | Hashing | Chapter 11 | Lecture 15 |
| March 26 | Hashing | Chapter 11 | Lecture 16 |
| March 31 | Problem set 5 due Review for Exam 2 |
Lecture 17 | |
| April 2 | EXAM 2 | ||
| April 7 | Heaps | Chapter 6 | Lecture 18 |
| April 9 | Sorting in linear time:Counting sort, Radix sort, Bucket sort | Chapter 8 | Lecture 19 |
| April 14 | Graphs: terminology, representations of graphs, BFS and DFS | Chapter 22, pp. 525-552 | Lecture 20 |
| April 16 | Problem set 6 assignedGraphs algorithms: BFS, DFS, Topological sort Minimum Spanning Trees, Kruskal's algorithm Shortest Path, Dijkstra's algorithm | Chapter 22, pp. 525-552 Chapter 23, pp. 561-570 Chapter 24, pp. 580-587, pp. 595-599 | Lecture 21 Problem Set 6 |
| April 21 | NO CLASS (Spring recess) | ||
| April 23 | NO CLASS (Spring recess) | ||
| April 28 | Problem set 6 dueRed-Black trees | Lecture 22 Final Review | |
| April 30 | Final exam |