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