Time: TTh 11:05-12:20

Location: Computer Studies Building 632.

TA and office hours:

- Ben Van Durme: ( vandurme@cs.rochester.edu ). 0830-0930 Friday or by Appointment.
- Jon Ruskin: ( jruskin@cs.rochester.edu ) or ( jr003m@mail.rochester.edu ). TBA

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 .

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

- SFSs*: 15%
- Midterm 1**: 20%
- Midterm 2**: 20%
- Homework: 45%

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

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.

brown @ cs rochester edu