Dr. Ellen Gethner

CSC 5451, Graduate Algorithms (Fall 2008)

Syllabus

automatically updated on 21 August 2008

  1. The Student Webpage is partially ready. It contains a copy of Homework 0, which is due on September 4th in class. If you have trouble logging on to the Student Webpage, then contact Shawn, our webmaster, at shawn atsign mccarthysoftware dot com.
  2. Be sure to send Shawn an email with a recognizable digital photo of yourself if you wish.

[ Instructor, Grader and our Office Hours | Class Time and Room | Textbook | Prerequisites | Objectives | Grades | Schedule | Student Page | Academic Deadlines (pdf) ]

Instructor

Dr. Ellen Gethner


Email: ellen dot gethner at cudenver dot edu
Office: North Classroom 2604-A3
Phone: (303) 556 2358
Office hours: 6:45-8:45pm T, Th; 2:30-3:30pm Tues, and by appointment

Teaching Assistant/Grader

To be announced


Email:
Office: Raytheon Lab
Office hours: To be announced

Class Time and Room

Tuesdays and Thursdays 5:30-6:45pm, North Classroom 1326

Textbook (required)

Cormen, et. al., Introduction to Algorithms, 2nd edition, McGraw Hill, 2001 (available in the campus bookstore).

Prerequisites

(Equivalent to UCD) CSC 3412, which itself has Discrete Structures as a prerequisite.

Course Objectives

Grades

Course Schedule and Outline


We will study the following topics (the instructor may choose to add to and/or subtract from the list of topics as the semester progresses):

Schedule (subject to change)
Lecture Date Topic Reading/Comments Assignments
1. Aug. 12 Introduction. Mathematical Induction, Fibonacci numbers, recurrences (review). Chapters 1-4 (review)
2. Aug. 14 Fibonacci numbers and the Euclidean Algorithm Chapters 1-4 (review)
3. Aug. 19 Euclidean Algorithm, Asymptotics, Master Theorem Chapters 1-4 (review)
4. Aug. 21 Master Theorem, Dynamic Programming (Knapsack Problem) Especially 4-3 and 4-4
null Aug. 26 and 28 Democratic National Convention: Campus Closed All Week
5. Sep. 2 Dynamic Programming: Knapsack problem and Sequence comparisons 15-3 for Dynamic Programming overview and 15-1, 15-2 for extra examples
6. Sep. 4 Dynamic programming, continued. Start of Greedy algorithms. Greedy Sheduling problem, design and proof of optimality. pp. 382-392 + class notes A hard copy of homework 0 is due in class.
7. Sep. 9 Dynamic Scheduling problem. Huffman encoding (greedy data compression): design. pp. 382-392 + class notes
8. Sep. 11 Huffman encoding: implementation and proof of correctness. pp. 183-185 and class notes
9. Sep. 16 Begin Graph Theory and Graph Algorithms pp. 923-931 and class notes
10. Sep. 18 Graph Theory and Algorithms: the party problem class notes and pp 1080-1084
11. Sep. 23 Graph theory: basics and begin planar graphs; adjacency matrix versus adjacency list class notes and pp 528-529
12. Sept. 25 Graph Coloring: chromatic number; scheduling and map coloring; history of the Four Color Problem (now Four Color Theorem) class notes
13. Sept. 30 Euler's formula and average degree; Proof of the six color theorem; Proof of the five color theorem; Proof of the four color theorem. Greedy coloring algorithm is in assignment 3, problem 5. class notes
14. Oct. 2 Chromatic number, M-Pire graphs, and thickness-two graphs: an open problem. class notes
15. Oct. 7 Earth-Moon graphs and PCB testing. Begin shortest path algorithms class notes and pp 580-588
16. Oct. 9 Single Source Shortest Paths. Dijkstra's Algorithm; Bellman-Ford Algorithm class notes and pp 580-588 and pp 591-601
17. Oct. 14 Midterm Examination You may bring one page of notes (both sides) to class to use during the exam.
18. Oct. 16 Dijkstra example, Bellman-Ford Algorithm, and begin Network Flows; side trip to Linear Programming 24-1,24-2,24-3, class notes and pp 643-647
19. Oct. 21 Network Flows, continued. Network Flow hall of fame. Ford-Fulkerson class notes and pp 643-647
20. Oct. 23 Application of the Network Flow problem: Max Flow/Min Cut Theorem class notes
21. Oct. 28 Number Theoretic Algorithms pp. 923-931 and class notes; free pdf files from Discrete Mathematics with Algorithms by Albertson and Hutchinson can be found here.
22. Oct. 30 Number Theoretic Algorithms
23. Nov. 4 RSA 31-7 and class notes
24. Nov. 6 RSA continued. Quantum Cryptography and the breakage of RSA. class notes
25. Nov. 11 Fast Fourier Transform and Polynomial Multiplication class notes
26. Nov. 13 NP Completeness explained by way of 3SAT and (graph) 3-colorability
27. Nov. 18 Computational Aspects of Escher Tilings
28. Nov. 20 Yet Another Look at the Four Color Theorem
null Nov. 24-30 Fall Break Happy Thanksgiving
29. Dec. 2 To be decided
30. Dec. 4 To be decided
31. FINAL EXAM date and time to be determined by registrar. You may bring one page of notes (both sides) to class to use during the exam. Last office hour session: time to be determined