Last revised on: 1/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
|
1/14
|
Learning Algorithms by Examples Guest Lecturer Professor Gene Itkis |
Chapters 1, 2; Appendix A, B1-3 | |
|
2
|
1/16
|
Administrivia algorithms in the real world binary search |
Chapter 3; Appendix C slides |
HW1 is assigned |
|
3
|
1/21
|
Divide and Conquer I:
Merge sort Master Theorem |
Chapters 4, 7 slides |
|
|
4
|
1/23
|
Randomized Algorithm I and Divide and Conquer II:
Quick Selection Quicksort |
Chapters 5,7 slides |
HW 1 is due and HW2 is assigned |
|
5
|
1/28
|
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 |
|
|
6
|
1/30
|
Sorting in linear time: Radix sort Bucket sort |
Chapter 8 slides |
|
|
7
|
2/04
|
Greedy Algorithm I: Huffman codes |
Chapter 16 slides |
|
|
8
|
2/06
|
Greedy Algorithm II: Scheduling and Selection what are heuristics? |
Chapter 16
slides |
HW 2 is due and HW3 is assigned |
|
8
|
2/11
|
Dynamic Programming I |
Chapter 15
slides |
|
|
10
|
2/13
|
Dynamic Programming II
Guest Lecturer: Benjamin Hescott |
Chapter 15 slides |
Friday, February 14, 2003 is the without getting a W |
|
11
|
2/18
|
No Class |
Tuesday with Monday's Schedule | |
|
12
|
2/20
|
Hashing | Chapter 11; slides |
HW3 is due and HW4 is assigned |
|
13
|
2/25
|
Quiz (Cover Lectures 1-10) | HW4 is assigned; | |
|
14
|
2/27
|
Search Tree I | Chapters 10, 12 slides | |
|
15
|
3/4
|
Search Trees II | Chapters 12, 13 slides | |
|
16
|
3/6
|
Search Tree III: Guest lecture by Professor Steve Homerb | Chapters 13, 14 (no slides) | HW4 is due and HW5 is
assigned; |
|
17
|
3/11
|
No Class |
Spring Break | |
|
18
|
3/13
|
No Class |
Spring Break | |
|
19
|
3/18
|
Graph Search Algorithm I:S BFS |
Chapter 22 slides | |
|
20
|
3/20
|
Graph Search Algorithm II: DFS |
Chapter 22 slides |
|
|
21
|
3/25
|
DFS, DAG and Strongly Connected Components | Chapter 21 slides |
|
|
22
|
3/27
|
Union-Find | Chapter 21 slides | HW5 is due and HW6 is assigned |
|
23
|
4/1
|
Minimum Spanning Trees | Chapter 23 slides | |
|
24
|
4/3
|
Midterm (Cover Lectures 1-22) | Chapters all before | |
|
25
|
4/8
|
Shortest Path I | Chapter 24,25 slides | |
|
26
|
4/10 |
Midterm and Quiz reviewing | Chapter 25 | HW6 is due and HW7 is assigned |
|
27
|
4/15
|
Shortest Path II | Chapter 25 slides | |
|
28
|
4/17
|
Matrix Operations | Chapter 28-1, 28-2 slides | |
|
29
|
4/22
|
Matrix Operations and All Pair Shortest Paths I | Chapter 25 slides | |
|
30
|
4/24
| Stable Marriage Problem |
|
|
|
31
|
4/29
|
Approximation Algorithms: Traveling-salesman problem |
Chapter 35.2 | |
|
32
|
5/01
|
Algorithm for the New Age: What to learn next?
Complexity Cryptography Parallel Algorithms Randomized Algorithms Approximation Algorithm On-Line Algorithms Mathematical Programming Computational Geometry Numerical Algorithms Algorithms in the real world smoothed analysis |
HW7 is due | |
|
Finally
|
May 8 Thursday 9:00-11:00 am in Room MCS 148.
|
FINAL (Cover ALL Lectures) | ALL Chapters | GOOD LUCK and THANKS FOR YOUR HARD WORK |