Dr. Ellen Gethner

CSC 5451, Graduate Algorithms (Fall 2007)

Syllabus

automatically updated on 30 August 2007

  1. The Student Webpage is up and running. If you have trouble logging in, contact Tony at tthompson at tkparch dot com.
  2. Send a recognizable digital photo of yourself to Tony at tthompson at tkparch dot com from your preferred e-mail address as soon as possible.

[ 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 (Use at your own risk)
Office hours: 4:00-5:00pm and 8:15-9:15pm M, W; 11:30am-12:30pm Tues (and by appointment)

Teaching Assistant/Grader

Rachel Terrell


Email: RACHEL dot TERRELL at email dot cudenver dot edu
Office: Raytheon Lab
Office hours: To be announced

Class Time and Room

Mondays and Wednesdays 7:00-8:15pm, North Classroom 1324

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. Each student must sign and return a prerequisite agreement form to receive any credit for any assignment or exam. If this form is not returned by the 3rd week, the student will be administratively dropped from the course.

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 Criteria a-k
1. Aug. 20 Introduction. Mathematical Induction, Fibonacci numbers, recurrences (review). Chapters 1-4 (review) a,b,i
3. Aug. 22 Fibonacci numbers and the Euclidean Algorithm Chapters 1-4 (review) a,b,i
4. Aug. 27 Euclidean Algorithm, Asymptotics, Master Theorem Chapters 1-4 (review) a,b,g,i
5. Aug. 29 Master Theorem, Dynamic Programming (Knapsack Problem) Especially 4-3 and 4-4 A hard copy of homework 0 is due in class. a,b,e,i
null Sep. 3 Labor Day Holiday: No Class
6. Sep. 5 Dynamic Programming: Knapsack problem and Sequence comparisons 15-3 for Dynamic Programming overview and 15-1, 15-2 for extra examples a,b,e,i,k
7. Sep. 10 Dynamic programming, continued. Start of Greedy algorithms. Greedy Sheduling problem, design and proof of optimality. pp. 382-392 + class notes a,b,e,i
8. Sep. 12 Dynamic Scheduling problem. Huffman encoding (greedy data compression): design. pp. 382-392 + class notes a,b,e,i
9. Sep. 17 Huffman encoding: implementation and proof of correctness. pp. 183-185 and class notes a,b,g, i
10. Sep. 19 Begin Graph Theory and Graph Algorithms pp. 923-931 and class notes a,b,e,i
11. Sep. 24 Graph Theory and Algorithms: the party problem class notes and pp 1080-1084
12. Sep. 26 Graph theory: basics and begin planar graphs; adjacency matrix versus adjacency list class notes and pp 528-529
13. Oct. 1 Graph Coloring: chromatic number; scheduling and map coloring; history of the Four Color Problem (now Four Color Theorem) class notes
14. Oct. 3 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
15. Oct. 7 Chromatic number, M-Pire graphs, and thickness-two graphs: an open problem. class notes
16. Oct. 9 Earth-Moon graphs and PCB testing. Begin shortest path algorithms class notes and pp 580-588
17. Oct. 15 Single Source Shortest Paths. Dijkstra's Algorithm; Bellman-Ford Algorithm class notes and pp 580-588 and pp 591-601
18. Oct. 17. 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
17. Oct. 22 In-class closed-book mid-term exam: material covered to be determined. You may bring one page of notes (both sides) to class to use during the exam.
20. Oct. 24 Network Flows, continued. Network Flow hall of fame. Ford-Fulkerson class notes and pp 643-647
21. Oct. 29 Application of the Network Flow problem: Max Flow/Min Cut Theorem class notes
22. Oct. 31 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.
23. Nov. 5 Number Theoretic Algorithms
24. Nov. 7 RSA 31-7 and class notes
25. Nov. 12 RSA continued. Quantum Cryptography and the breakage of RSA. class notes
26. Nov. 14 Fast Fourier Transform and Polynomial Multiplication class notes
null Nov. 19-25 Fall Break Happy Thanksgiving
27. Nov. 26 NP Completeness explained by way of 3SAT and (graph) 3-colorability
28. Nov. 28 Computational Aspects of Escher Tilings
29. Dec. 3 Yet Another Look at the Four Color Theorem
30. Dec. 5 TBA
31. To be decided Last office hour session
32. To be decided 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.