CMSC451 Design and Analysis of Computer Algorithms, Summer 2023

Note: Course information is tentative and subject to change.

Instructor: Nathaniel Grammel (ngrammel AT umd DOT edu).

Office Hours: In-person office hours are in the open area outside IRB 2207, virtual are in my Zoom room (link on ELMS and Piazza)

I am also available in person or virtually by appointment. Please feel free to reach out to me if you’d like to set up a time to meet outside of these scheduled office hours.

Lecture: Monday–Friday, 2:00pm–3:20pm in CSI 1121. In-person attendance in lecture is not required, though you are encouraged to come in-person if you are able. However, exams must be taken in person; they will be on July 28 and August 18. Please plan accordingly.

Lecture materials will be made available online. If you cannot attend in-person lectures, you are expected to watch the lecture recordings and encouraged to come to virtual office hours with questions.

Piazza: We will use Piazza extensively throughout the course. Make sure you are signed up for the Piazza course. Piazza allows us to discuss the topics from class, and you may ask any questions about the material there. Assignments, lecture recordings, and announcements will also be made available there. If you are registered for the course, you should have been added to the Piazza already. If you have not, please reach out to me by email.

Textbook: The primary textbook is Algorithm Design by Jon Kleinberg and Éva Tardos. A good supplemental textbook (not required) is Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani.

Overview

CMSC451 is an upper-level undergraduate course on the design and analysis of algorithms. The course presents fundamental techniques for designing efficient algorithms, proving their correctness, and analyzing their performance. Topics include greedy algorithms, divide and conquer algorithms, graph algorithms, dynamic programming, linear programming, computational intractability, approximation algorithms, and randomized algorithms.

Prerequisites

The main course prerequisite is CMSC351. You should be familiar with discrete mathematics (mathematical induction, logic, sets, combinatorics, probability), data structures (lists, stacks, queues, heaps, graphs), and some basic algorithms such as sorting (quicksort, mergesort, heapsort) and basic graph algorithms (Dijkstra’s, minimum spanning trees). If you have questions about this background material, please reach out to the instructor.

Grading

There will be several written homework assignments throughout the course. Assignments will be submitted and returned via gradescope. Assignments are to be done individually, and all work submitted must be your own. You are allowed (and encouraged) to discuss the problems with your classmates, but make sure that all work you submit is your own.

There will be two exams. The tentative grading breakdown is:

  • 40% Homework
  • 30% Exam 1 (July 28)
  • 30% Exam 2 (August 18)

Note that while in-person lecture attendance is not required, exams must be taken in person in the classroom during the scheduled class time.

Schedule

  • Monday July 10: Logistics, overview, algorithm basics, stable matching example
    • Textbook Reading: Chapter 1 of Algorithm Design.
    • Lecture Recording on Piazza
    • Definitions and Algorithm Pseudocode from the Whiteboard: (link)
  • Tuesday July 11: Stable Matching continued.
    • Chapter 1 of Algorithm Design
    • Lecture Recording on Piazza
  • Wednesday July 12: Finish Gale-Shapley analysis, Big-Oh.
    • Chapter 2 of Algorithm Design
    • Lecture Recording on Piazza
  • Thursday July 13: Graphs and BFS
    • Chapter 3 of Algorithm Design
    • Useful Reference Sheet from Dave Mount: (link)
    • Lecture Recording on Piazza
    • Homework 1 Posted (Piazza), Due 7/17
  • Friday July 14: Graph algorithms (BFS, connectivity)
    • Chapter 3 of Algorithm Design
    • Lecture Recording on Piazza
  • Monday July 17: BFS continued (bipartiteness)
    • Chapter 3 of Algorithm Design
    • Lecture Recording on Piazza
    • HW1 Due by 11:59PM
  • Tuesday July 18: bipartiteness, strongly connected components, DAGs
    • Chapter 3 of Algorithm Design
    • Lecture Recording on Piazza
  • Wednesday July 19: DFS (via recursion and stacks), DAGs, SCCs
    • Section 3.4 of Dasgupta, Papadimitriou, Vazirani (see here)
    • Lecture Recording on Piazza
  • Thursday July 20: Topological Sorting / Linearization via DFS, SCC decomposition, Greedy Algorithms (Dijkstra, Prim)
    • Section 3.4 of Dasgupta, Papadimitriou, Vazirani
    • Lecture Recording on Piazza
    • HW2 Posted, Due by July 25 at 11:59PM
  • Friday July 21: Greedy Algorithms (Dijkstra, Prim, Kruskal, Interval Scheduling)
    • Chapters 4.4, 4.5, and 4.1 in Algorithm Design
    • Lecture Recording on Piazza
  • Monday July 24: Proofs for Greedy Algorithms
    • Chapters 4.4, 4.5 in Algorithm Design
    • Recording on Piazza
  • Tuesday July 25: Finish Greedy Algorithms (Interval Scheduling, Set Cover), Divide and Conquer (Closest Pair of Points)
    • Chapters 4.1, 5.4 of Algorithm Design (Review of mergesort in Chapter 5.1)
    • Lecture Recording on Piazza
    • HW2 Due by 11:59PM on Gradescope
  • Wednesday July 26: Divide and Conquer (Polynomial Multiplication, FFT)
    • Chapter 5.6 of Algorithm Design
    • Lecture Recording on Piazza
  • Thursday July 27: Shortest Paths Revisited: Negative Weights (Bellman-Ford, Dynamic Programming)
    • Chapter 6.8 of Algorithm Design
    • Lecture Recording on Piazza
  • Friday July 28: First Exam (Covers Topics up to and including Divide and Conquer)
  • Monday July 31: Dynamic Programming (Bellman-Ford, Floyd-Warshall)
    • Chapter 5.6 of Algorithm Design for Bellman-Ford. Floyd-Warshall not in textbook (see notes on Piazza; also helpful are these notes from Dave Mount and section 6.6 of the DPV book)
    • Lecture Recording on Piazza
  • Tuesday August 1: Dynamic Programming (Interval Scheduling, Knapsack)
    • Chapters 6.1 (Weighted Interval Scheduling) and 6.4 (Knapsack) of Algorithm Design
  • Wednesday August 2: Linear Programming
    • Not in textbook (see lecture notes or section 7.1 of DPV)
    • Optional Reading: an interesting article here about the discovery of the Ellipsoid algorithm (the first worst-case polynomial time algorithm for solving LPs) by Leonid Khachiyan, and its treatment in the press
    • Lecture recording on Piazza
  • Thursday August 3: Network Flows, Max Flow
    • Chapter 7.1 of Algorithm Design
    • Lecture Recording on Piazza
  • Friday August 4: Ford-Fulkerson Algorithm
    • Chapter 7.1 of Algorithm Design
    • Lecture Recording on Piazza
  • Monday August 7: Minimum Cuts and Duality
    • Chapter 7.2 of Algorithm Design
    • Lecture Recording on Piazza
  • Tuesday August 8: Max Flow-Min Cut, Duality
    • Chapter 7.2 Algorithm Design
    • Lecture Recording on Piazza
    • Optional Reading: Chapters 7.3, 7.4 of Algorithm Design, and these notes on Ford-Fulkerson and Edmonds-Karp.
  • Wednesday August 9: Bipartite Matching and Reductions
    • Chapters 7.5, 8.1 of Algorithm Design
    • Lecture Recording on Piazza
  • Thursday August 10: Reductions
    • Chapters 8.1, 8.2 of Algorithm Design
    • Lecture Recording on Piazza
  • Friday August 11: NP-completeness
    • Chapters 8.3, 8.4 of Algorithm Design
    • Lecture Recording on Piazza
  • Monday August 14: Approximation Algorithms (Load Balancing, Set Cover)
    • Chapters 11.1, 11.3 of Algorithm Design
    • Lecture Recording on Piazza
  • Tuesday August 15: Approximation Algorithms (Load Balancing, Set Cover Cont.)
    • Chapters 11.1, 11.3 of Algorithm Design
    • Lecture Recording on Piazza
  • Wednesday August 16: Approximation Algorithms (Knapsack PTAS)
    • Chapter 11.8 of Algorithm Design
  • Thursday August 17: Approximation and Randomized Algorithms (LP Rounding, Set Cover, Vertex Cover, MAX-SAT)
    • Chapters 11.6 (LP Rounding for Vertex Cover), 13.5 (Randomized Quicksort), 13.10 (Load Balancing, Balls and Bins), and 13.4 (MAX-3SAT) of Algorithm Design
    • Randomized LP Rounding for MAX-SAT is covered in these lecture notes from Deeparnab Chakrabarty): link
  • Friday August 18: Exam
Web Accessibility