Syllabus for CSC 5451, Dr. Ellen Gethner

Dr. Ellen Gethner

CSC 5451, Graduate Algorithms--Hybrid (Fall 2022)

Syllabus

automatically updated on 20 July 2022

[ 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.
Office hours: call or email the CS office to make a zoom appointment-- 303-315-1408 or computerscience@ucdenver.edu (office hours shown below)

Tuesday 12:30-3pm on zoom until further notice
Wednesday 12:30-3pm on zoom until further notice

Teaching Assistant/Grader

TBA

Class Time, Days, and Room: 12:30-1:45pm on Mondays and Wednesdays in Lawrence Street Center Room 840 (Midterm and Final only)

Online/hybrid and self-paced; only the midterm and final exams will be in person: All Material (lecture notes, videos of lectures, homework assignments, quizzes, etc) for the entire semester are available on Canvas. The midterm and final exams will both be in person on the dates and times specified in the schedule.

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

We will develop proficiency in the design and analysis of algorithms. In particular, we will learn how to design algorithms, prove that they are correct, measure their efficiency, and discuss methods for determining if their performance can be improved.

Grades

Homework and Quizzes. Homework assignments (six) will count toward thirty percent of your grade and will assessed by way of a quiz (quiz x is directly related to homework x for x=0 to 5), which you will do with an assigned team and upload one copy for all of you to canvas by 12:30pm on the due date. HOMEWORK IS NOT HANDED IN. Each assigment will have an assortment of straightforward problems as well as challenging problems. One to two weeks after the assignment has been posted, a quiz containing problems related to the content of of the homework problems and associated lectures, will be due. When writing your solution to the quiz problem, write your ideas even if you do not believe you have a complete solution. Be sure to be neat, write in complete sentences, and do not leave out any steps: clarity of exposition may contribute toward a positive score. Please talk to one another about the assignments: study groups can be fun and productive.

Quiz Grades: There will be no make-up quizzes so be sure to upload your quiz by 12:30pm on the due date. I will drop the lowest quiz score. This means that you may choose to miss one quiz and the score of 0 will be dropped. Quiz due dates are posted on the schedule below as well as on canvas. All quizzes are available now. You will work with a team (3-4 people) and upload one copy of your quiz to canvas no later than 12:30pm on the due date as shown in the Schedule.
Examinations:
- There will be two examinations, each worth thirty-five percent of your grade. The midterm and final will be in person and done on your own (without your team). See the Schedule for the dates and location of the exams.
- Midterm exam is done on your own in class (room, date, and time shown in the schedule). NO EXCEPTIONS: A missed or late exam will be assigned a score of 0.
- The final exam is done on your own (without your team) in class; see the Schedule for the location, date, and time. NO EXCEPTIONS: A missed exam will be assigned a score of 0.

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

Design and Analysis Techniques
- Divide and Conquer
- Greedy
- Dynamic
- Reduction
Basic Algorithms (subject to change)
- Algorithms involving sequences and sets: order statistics, string manipulation, data compression
- Graph Algorithms: network flows, planarity, matching, graph coloring
- Algebraic Algorithms: polynomial multiplication, Fast Fourier Transform
Advanced Topics if time permits; as well, supplementary videos on applications will be posted on Canvas
- Randomized algorithms
- Cryptography: RSA, zero knowledge proofs, quantum cryptography
- Computational Geometry

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