Computer Science 282

Design and Analysis of Efficient Algorithms

Fall 2005

Instructor: Chris Brown, mail ( brown@cs.rochester.edu ).
Time: TTh 11:05-12:20
Location: Computer Studies Building 632.

TA and office hours:

Pedagogical Philosophy: As always, I see this CS course as part of a Liberal Education .

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

Reserves and other resources: The text is on reserve in Carlson. Here is the 282 Course and Reserves Page at Library. Different styles appeal to different people differently, and you may want to supplement your library with other Algorithms texts. See amazon.com or other more specialized on-line vendors, or look for author names like Johnsonbaugh and Schaefer, Kleinberg and Tardos, Weiss, Aho, Hopcroft, Ullman...

Prerequisites: MTH150 Discrete Mathematics and CSC172 Data Structures

Content: How does one design programs and ascertain their efficiency? Advanced data structures such as balanced tree schemes. Divide-and-conquer techniques, string processing, graph algorithms, combinatorial search, optimization, and decision problems, network flow, linear programming, fast fourier transform.

Possibly Helpful Material: Theory Math Cheat Sheet
172 Math Review: Math Preliminaries and Math Prelim. Exercises and Answers
Textbook Errata .

SFS results

SFSs 1-11 (19 Oct 05) in percent of possible points (include one guy who has probably dropped, so the real min is 43). max 85, min 24, ave 63, median 68.

Course Midterms

Here are The First Midterm and The Second Midterm (no answers, sorry!).

Schedule

Ignore all administrative announcements (homework assignments, test dates, etc.) in any pointed-to material. The only relevant administrative info is on this page itself.
Date Topic (Reading Due) HW Assigned HW Collected
Sep. 01 Th Intro, Ch. 1,2; App A, B, C: Ch.2 1 *
Sep. 06 Tu Ch. 3, 4: Alg. Anal. Math. Preview, Recur, Induct. Example 2 *
Sep. 08 Th Ch. 7: QuickSort * *
Sep. 13 Tu Ch. 6: HeapSort 3 1,2
Sep. 15 Th Ch. 8: LinSort * *
Sep. 20 Tu Ch. 9: Order Statistics, adversary1 , adv1a . 4 3
Sep. 22 Th Ch. 11: Hashing * *
Sep. 27 Tu Ch. 12: Binary Search Tree 5 4
Sep. 29 Th Ch. 13: Red-Black Tree * *
Oct. 4 Tu Ch. 14: Augmenting Data Structures 6 5
Oct. 6 Th Ch. 15: Dynamic Programming * *
Oct. 11 Tu Ch. 15: Dynamic Programming * *
Oct. 13 Th Ch. 16: Greedy Algorithms 7 6
Oct. 18 Tu Ch. 16: Greedy Algorithms * *
Oct. 20 Th Midterm 1 * *
Oct. 25 Tu Ch. 17: Amortized Analysis 8 7
Oct. 27 Th Ch. 18: B-Trees * *
Nov. 1 Tu Ch: 22: Graph Traversal 9 8
Nov. 3 Th Ch. 24 (.0,.1,.4,.5), 25.3: Adv. Sh. Pth, ASP 2. * *
Nov. 8 Tu Ch. 26: MaxFlow, MaxFlow2, MaxFlowDemo. 10 9
Nov. 10 Th Ch. 29: Linear Programming For Example. * *
Nov. 15 Tu Ch. 29: Linear Programming cont 11 10
Nov. 17 Th Ch. 33: Computational Geometry * *
Nov. 22 Tu Ch. 33: Computational Geometry (cont) 12 11
Nov. 24 Th Thanksgiving (U.S.) * *
Nov. 29 Tu Ch. 30: FFT 13 12
Dec. 1 Th Ch. 30: FFT * *
Dec. 6 Tu DES and AES Encryption Algorithms. Ba byDES , AttackDES , AES Spec., (pp. 1-16 about). * 13
Dec. 8 Th Ch. 30: Midterm 2 * *

Grading

*Success Facililitation Surveys are documents you produce in class to help the professor and TA Facilitate Your Success.

**You may bring a double-sided letter-size piece of paper with notes to the midterms.

Homework Rules

Homework should be deposited in the 282 box outside Van Durme's office (CSB 615) no later than the start of class (that is, no later than 11:05 AM) on the due date.

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 (thus you should each indicate each other). Please start a new page for each problem on your solutions (else some penalties may apply).

Late homework is bad logistically for the graders and it's bad for you to put work off hoping your life is going to get simpler. It never does. You only learn this material by doing problems, so we'll use a tried-and-true formula that should encourage promptness and reward improvement. You should always hand in something (called first) on the due date. Then you have four extra days to hand in an improved and expanded second version. Your final grade is (first + 2* second)/3, or first if no second . So e.g. missing first means your max possible is 66, but if first is worth only 50 it can be raised to 83. Make sure your second submission includes your first (so you should make a copy of first) and then mark the places where you have changed or added answers so the TAs only need to look at the relevant changes.

This course follows The University Policy on Academic Honesty .

You may be interested in some more details on typical AH pitfalls and how to avoid them.

Official Final Exam Date

THERE IS NO FINAL EXAM. NOTHING DUE (OR ACCEPTED) AFTER 8 DECEMBER.
brown @ cs rochester edu