Course Schedule (tentative)

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
Guest Lecturer: Benjamin Hescott

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;

Friday, March 7 is the last day to drop a class with a W

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