|
Please email ASAP Rohan Fernandes so we can compile an email list for
announcements. |
| Date |
Topic |
Notes. No PPTs, I decided to
teach on the white board. |
| Jan 19 |
RAM model, Asymptotics |
Jan 16: MLK's day. |
| Jan 26 |
Recurrences, Sorting, Worstcase linear time selection |
Jan 22-24, SODA, Miami. Homework 1. Due Feb 6. |
| Feb 02 |
Lower bounds for selection, worst/average case sorting, detecting permutations |
Homework 2,
due Feb 13. |
| Feb 09 |
Hashing, Universal hashing,
perfect hashing. Read: binary search trees and other simple data structures (except Red-Black trees). Read Hashing (not open addressing). |
Homework 3,
due Feb 20. |
| Feb 16 |
Divide and conquer, Dynamic
Programming. Read: how to multiply many matrices. |
Homework 4,
due Feb 27. |
| Feb 23 |
Karp-Rabin fingerprints.
Application to pattern matching. 2DPDA and string matching. Closest pairs in randomized linear time |
Homework 5.
Feb 20: President's day. |
| Mar 02 |
Closest pairs in randomized
linear time. Randomized algorithm for string matching with wildcards and (boolean, integer) convolutions. |
Homework 6,
due March 20. |
| Mar 09 |
All Pairs Shortest Paths using
Matrix Multiplication (result by Raimund Seidel) |
Read basic graph algorithms
(depth/breadth first searches, minimum spanning tree, shorest path problems, DAG and topological sorting. |
| Mar 16 |
SPRING RECESS (Mar 11--19) |
|
| Mar 23 |
||
| Mar 30 |
||
| Apr 06 |
Apr 3--7, ICDE, Atlanta. |
|
| Apr 13 |
||
| Apr 20 |
Apr 20-22 at SDM, MD. |
|
| Apr 27 |
Last day of classes (Last day of
classes is May 1) |
|
| May 04 |
||
| May 11 |