Instructor:
Dan Gildea

Time: TTh 11:05-12:20

Location: Computer Studies Building 632.

TAs and office hours:

- Kirk Kelsey: Wed 11am-12pm, CSB 621
- Ashwin Lall: Mon 2-3pm, CSB 627
- David Sloan: Mon 5-6pm, CSB 703

Textbook:
*Introduction to Algorithms*, Thomas Cormen, Charles
Leiserson, Ronald Rivest, and Clifford Stein.
MIT Press, 2001.

Prerequisites: MTH150 Discrete Mathematics and CSC172 Data Structures

How does one design programs and ascertain their efficiency? Divide-and-conquer techniques, string processing, graph algorithms, mathematical algorithms. Advanced data structures such as balanced tree schemes. Introduction to NP-completeness and intractable combinatorial search, optimization, and decision problems.

Date | Lecture | HW Assigned |
HW Collected |
---|---|---|---|

Sep. 3 Th | Course Organization | * | * |

Sep. 7 Tu | Chapter 2: Getting Started | * | * |

Sep. 9 Th | Chapter 6: Heap Sort | 1 | * |

Sep. 14 Tu | Chapter 7: Quicksort | * | * |

Sep. 16 Th | Chapter 8: Sorting in Linear Time | 2 | 1 |

Sep. 21 Tu | Chapter 9: Median and Order Statistics | * | * |

Sep. 23 Th | Chapter 11: Hashing | 3 | 2 |

Sep. 28 Tu | Chapter 12: Binary Search Tree | * | * |

Sep. 30 Th | Chapter 13: Red-Black Tree | 4 | 3 |

Oct. 5 Tu | Chapter 13: Red-Black Tree (cont'd) | * | * |

Oct. 7 Th | Chapter 14: Augmenting Data Structures | * | 4 |

Oct. 12 Tu | Problem Session 1 covering Assignments 1 through 4 | * | * |

Oct. 14 Th | Midterm No. 1 covering Chapters 2, 6-9, 11-13 | * | * |

Oct. 19 Tu | Chapter 15: Dynamic Programming | 5 | * |

Oct. 21 Th | Chapter 15: Dynamic Programming (cont'd) | * | * |

Oct. 26 Tu | Chapter 15: Dynamic Programming (cont'd) | 6 | 5 |

Oct. 28 Th | Chapter 16: Greedy Algorithms (excluding matroids) | * | * |

Nov. 2 Tu | matroids, Chapter 17: Amortized Analysis | 7 | 6 |

Nov. 4 Th | Chapter 18: B-Tree | * | * |

Nov. 9 Tu | Chapter 18: B-Tree (cont'd) | 8 | 7 |

Nov. 11 Th | Chapter 19: Binomial Heaps | * | * |

Nov. 16 Tu | Problem Session 2 covering Assignments 5, 6, 7, and 8 | * | 8 |

Nov. 18 Th | Midterm No. 2 covering Chapters 14 through 18 | * | * |

Nov. 23 Tu | solutions to midterm 2 | * | * |

Nov. 30 Tu | Chapter 22: Graph Algorithms | 9 | * |

Dec. 2 Th | Chapter 21: Disjoint Sets; Chapter 20: Fibonacci Heaps | * | * |

Dec. 7 Tu | Chapter 23: Minimum Spanning Tree; Chapter 24: Single-Source Shortest Path | * | 9 |

Dec. 9 Th | Chapter 25: All-Source Shortest Path | * | * |

- Final exam: 35%
- Homeworks: 30%
- Two midterms: 15% each
- Class participation: 5%

gildea @ cs rochester edu December 9, 2004