Dr. Ellen Gethner

CSC 5451, Graduate Algorithms--Online (Fall 2021)

Syllabus

automatically updated on 15 August 2021

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

Instructor

Dr. Ellen Gethner


Email: ellen dot gethner at ucdenver dot edu
Office: LW 817.
Phone: 303 315 1405
Office hours: call the CS office to make a zoom appointment 303 315 1405

Teaching Assistant/Grader

Stuti Adarsh

Class Time and Room

Online and self-paced: All Material (lecture notes, videos of lectures, homework assignments, exams, quizzes, etc) for the entire semester are available on Canvas.

Textbook (required)

Cormen, et. al., Introduction to Algorithms, 3rd edition, McGraw Hill, 2009 (available in the campus bookstore and many other places...)

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):

Suggested Schedule: This is a self-paced online course. Due dates for quizzes and exams will not change.

All Lectures are Videotaped and Available on Canvas

Lecture Date Topic Reading/Comments Quizzes
1. Aug. 24 Introduction. Mathematical Induction, Fibonacci numbers, recurrences (review). Chapters 1-4 (review)
2. Aug. 26 Fibonacci numbers and the Euclidean Algorithm Chapters 1-4 (review)
3. Aug. 31 Euclidean Algorithm, Asymptotics, Master Theorem Chapters 1-4 (review)
4. Sep 2 Master Theorem, Dynamic Programming (Knapsack Problem) Especially 4-3 through 4-6
5. Sep. 7 Dynamic Programming: Knapsack problem and Sequence comparisons 15-3 for Dynamic Programming overview and 15-1, 15-2 for extra examples. Copy of Quiz 0, with your partner, is due no later than 12pm: upload on canvas. Open book, open notes, open friends, open internet.
6. Sep. 9 Dynamic programming, continued. Start of Greedy algorithms. Greedy Sheduling problem, design and proof of optimality. 16-1 through 16-3 + class notes
7. Sep. 14 Dynamic Scheduling problem. Huffman encoding (greedy data compression): design. 16-1 through 16-3 + class notes
8. Sep. 16 Huffman encoding: implementation and proof of correctness. 16-1 through 16-3 + class notes + handout
9. Sep. 21 Begin Graph Theory and Graph Algorithms 22-1 through 22-3 + class notes Copy of Quiz 1, with your partner, is due today no later than 12pm: upload on canvas. Open book, open notes, open friends, open internet.
10. Sep. 23 Graph Theory and Algorithms: the party problem 22-1 through 22-3 + class notes
11. Sep. 28 Graph theory: basics and begin planar graphs; adjacency matrix versus adjacency list 22-1 through 22-3 + class notes
12. Sept. 30 Graph Coloring: chromatic number; scheduling and map coloring; history of the Four Color Problem (now Four Color Theorem) class notes
13. Oct. 5 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 Copy of Quiz 2, with your partner, is due today by 12pm: upload on canvas. Open book, open notes, open friends, open internet.
14. Oct. 7 Chromatic number, M-Pire graphs, and thickness-two graphs: an open problem. class notes
15. Oct. 12 Earth-Moon graphs and PCB testing. Begin shortest path algorithms class notes and Chapter 24
16. Oct. 14 Single Source Shortest Paths. Dijkstra's Algorithm; Bellman-Ford Algorithm class notes and Chapter 24
17. Oct. 19 Copy of Examination One, with your partner, is due today by 12pm: upload on canvas. Open book, open notes, open friends, open internet. Study hard: form a study group and have some fun!
18. Oct. 21 Dijkstra example, Bellman-Ford Algorithm, and begin Network Flows; side trip to Linear Programming Chapter 24, class notes, and 29-1 and 29-2
19. Oct. 26 Network Flows, continued. Network Flow hall of fame. Ford-Fulkerson class notes and 26-1 and 26-2 and handout Copy of Quiz 3, with your partner, is due today by 12pm: upload on canvas. Open book, open notes, open friends, open internet.
20. Oct. 28 Application of the Network Flow problem: Max Flow/Min Cut Theorem class notes
21. Nov 2 Factorization of Integers is time consuming class notes and 31-9
22. Nov. 4 Probabalistic Algorithm for Primality Testing class notes and 31-8
23. Nov. 9 RSA class notes and 31-1 through 31-7 Copy of Quiz 4, with your partner, is due by 12pm: upload on canvas. Open book, open notes, open friends, open internet.
24. Nov. 11 RSA continued. Quantum Cryptography and the breakage of RSA. class notes
25. Nov. 16 Fast Fourier Transform and Polynomial Multiplication class notes and 30-1 and 30-2 (See 30-3 for implementation)
26. Nov. 18 NP Completeness explained by way of 3SAT and (graph) 3-colorability class notes and Chapter 34
null Nov. 22-28 Fall Break Happy Thanksgiving
27. Nov. 30 Computational Geometry: Art Gallery Theorem class notes and Chapter 33 for other applications Copy of Quiz 5, with your partner, is due today by 12pm: upload on canvas. Open book, open notes, open friends, open internet.
28. Dec 2 Research Presentation on Thickness of Graphs
29. Dec 7 Copy of Examination Two, with your partner, is due by 12pm today: upload on canvas. Open book, open notes, open friends, open internet. Study hard: form a study group and have some fun!
30. Dec. 9 Research presentation on Escher Tiling
31. Monday, Dec. 14 Office hours to be determined