Policies · Schedule · Syllabus

MIDTERM, Thursday, March 12, 6:00-9:00 p.m., Clark A103

Week | Dates | Topics | Material |
---|---|---|---|

1 | 1/22 | Quick review of asymptotic analysis, recurrences, divide-and-conquer (No recition this week.) | Handout on big-O analysis;
Cormen text: Chapters 1, 2, 3 through page 56, 4.1, 4.5.; On-line Python tutorial |

2 | 1/27, 1/29 | Review of asymptotics, recurrences, divide-and-conquer; How to read texts and papers in our field, sorting networks. | Ch. 8 of a previous edition of our textbook; "Sorting networks" to be posted. |

3 | 2/3, 2/5 | Examples of divide-and-conquer. Convolution | Ch. 30 |

4 | 2/10, 2/12 | Fast-Fourier Transform (FFT) -- another example of divide-and-conquer | Ch. 30 |

5 | 2/17, 2/19 | FFT, All-pairs shortest paths | Chs. 30, 25 |

6 | 2/24, 2/26 | All-pairs shortest paths, randomized algorithms, randomized Quicksort | Ch. 25; Sections 5.1, 5.2, 5.3, Ch. 7 |

7 | 3/2, 3/4 | Randomized Quicksort, Randomized Selection | Chapter 7, Chapter 9 |

8 | 3/9, 3/11 | Randomized algorithms, randomized search trees | The Design and Analysis of Algorithms, Ch. 13 on e-reserve |

Spring break | |||

9 | 3/25 | Randomized data structure for point location. | deBergCh6.pdf on E-reserve |

10 | 3/30, 4/1 | Point location, Hash tables, Amortized analysis | deBergCh6.pdf, Cormen Ch. 11 through 11.2, and Ch. 17, Data Structures and Network Algorithms - Search Trees on e-Reserve |

11 | 4/6, 4/8 | Amortized analysis | Data Structures and Network Algorithms - Search Trees, Section 4.3 only. |

12 | 4/13, 4/15 | Network flows and reductions | Cormen, Chapter 26 through Section 26.3 |

13 | 4/20, 4/22 | Approximation algorithms | Cormen, Ch. 35 |

14 | 4/27, 4/29 | Topic to be determined |