Last revised on: 08/15/03 3:19 PM
Reading assignments are given according to the main text book (Cormen et
al).
| Lec# |
Date
|
Topic and/or Event | Reading | Notes |
|
1
|
9/4
|
Class Organization
Class Webpage Introduction and Readings (Guest Lecturer) |
Chapters 1, 2; Appendix A, B1-3 | |
|
2
|
9/9
|
algorithms in the real world binary search |
Chapter 3; Appendix C slides |
HW1 is assigned |
|
3
|
9/11
|
Divide and Conquer I:
Merge sort Master Theorem |
Chapters 4, 7 slides |
|
|
4
|
9/16
|
Randomized Algorithm I and Divide and Conquer II: (Guest Lecturer)
Quick Selection Quicksort |
Chapters 5,7 slides |
|
|
5
|
9/18
|
Divide and Conquer III:
Multiplication Finding the closest pair of points |
Chapter 33.4; Problem 30-1, page
844 and slides of this lecture on multiplication
slides |
HW 1 is due and HW2 is assigned |
|
6
|
9/23
|
Sorting in linear time: Radix sort Bucket sort |
Chapter 8 slides |
|
|
7
|
9/25
|
Greedy Algorithm I: Huffman codes |
Chapter 16 slides |
|
|
8
|
9/30
|
Greedy Algorithm II: Scheduling and Selection what are heuristics? |
Chapter 16
slides |
|
|
9
|
10/2
|
Dynamic Programming I |
Chapter 15
slides |
HW2 is due and HW3 is assigned |
|
10
|
10/7
|
Dynamic Programming II | Chapter 15 slides |
|
|
11
|
10/9
|
Hashing |
Chapter 11 slides |
|
|
12
|
10/14
|
No Class | ||
|
13
|
10/16
|
Quiz 1 (Cover Lectures 1-10) | ||
|
14
|
10/21
|
Search Tree I | Chapters 10, 12 slides | HW3 is due and HW4 is assigned |
|
15
|
10/23
|
Search Trees II | Chapters 12, 13 slides | |
|
16
|
10/28
|
Search Tree III | Chapters 13, 14 | |
|
17
|
10/30
|
Graph Search Algorithm I: BFS |
Chapter 22 slides | |
|
18
|
11/4
|
Graph Search Algorithm II: DFS |
Chapter 22 slides | |
|
19
|
11/6
|
Midterm (Cover Lectures 1-17) | Chapters all before | |
|
20
|
11/11
|
Graph Search Algorithm III | Chapter 22 slides |
HW4 is due and HW5 is
assigned; |
|
21
|
11/13
|
DFS, DAG and Strongly Connected Components | Chapter 21 slides |
|
|
22
|
11/18
|
Union-Find | Chapter 21 slides | |
|
23
|
11/20
|
Minimum Spanning Trees | Chapter 23 slides | |
|
24
|
11/25
|
Quiz 2 (Cover Lectures 1-22) | Chapters all before | HW6 is assigned |
|
25
|
11/27
|
No Class |
Happy Thanksgiving | |
|
26
|
12/2
| Shortest Path I | Chapter 24,25 slides | HW5 is due |
|
27
|
12/4
|
Shortest Path II | Chapter 25 slides | |
|
28
|
12/9
|
Matrix Operations | Chapter 28-1, 28-2 slides | |
|
29
|
12/11
|
Matrix Operations and All Pair Shortest Paths I | Chapter 25 slides | HW6 is due |
|
Finally
|
Dec. 16th, 3--5 pm
|
FINAL (Cover ALL Lectures) | ALL Chapters | GOOD LUCK and THANKS FOR YOUR HARD WORK |