Computer Science 282

Design and Analysis of Efficient Algorithms

Fall 2004

Homework Assignments

Instructor: Dan Gildea
Time: TTh 11:05-12:20
Location: Computer Studies Building 632.

TAs and office hours:

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.

Schedule

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 * *

Grading

You may work with one other person on homeworks, but you must each write up your solutions separately. If you work with another person, indicate who you worked with on your solution. Please start a new page for each problem on your solutions, and include your name on each page, so the TAs can divide up the problems for grading. Exams are closed book.

Final Exam

Monday Dec 20, 8:30-11:30am, CSB 632.
gildea @ cs rochester edu
December 9, 2004