15-451/651 Algorithm Design and Analysis

Frequency Offered: Generally offered every fall and spring semester - confirm course offerings for upcoming semesters by accessing the university Schedule of Classes.

Course Relevance (who should take this course?): This course is for undergraduate students interested in modern, theoretical algorithm design techniques as well as provable guarantees of algorithm correctness and running time.

• Efficient data structures
• Lower bounds and NP-completeness
• Approximation algorithms
• Randomized algorithms
• Geometric algorithms
• Low level techniques for efficient programming
• Linear programming
• On-line algorithms
• Graph algorithms (including maximum flow and matchings)
• Streaming
• String algorithms

The course relies on mathematical thinking and proofs, and requires the ability to program in a compiled language. (15-251, 15-210, 21-241)

Sample class notes: not provided

Sample Assignment: not provided

• 4 Written Homeworks: 20%
• 3 Oral Homeworks: 15%
• Online Quizzes: 10%
• 2 Midterms: 30%
• Final: 25%

Sample Lecture Recording: https://scs.hosted.panopto.com/Panopto/Pages/Sessions/List.aspx#folderSets=15&folderID=%222d165709-dee6-4ebc-9cae-30cac5ce12c0%22

• Understanding of the design and analysis on algorithms for a variety of problems
• Develop skills to reason about and prove properties of algorithms such as their correctness and running time.
• Understand how data structures can provide space-efficient ways to quickly answer queries about data, and understand how these data structures can be used to build efficient algorithms.
• Understand analysis techniques such as amortized analysis, probabilistic analysis, and minimax optimality.
• Understand how and why randomness can be used to provide efficient solutions to some problems.
• Learn to implement advanced algorithms efficiently.
• Use the concept of approximation to find efficient algorithms for hard problems.
• Use the theory of NP-completeness and other lower bounding techniques to argue for the difficulty of some problems.

Course Website: https://www.cs.cmu.edu/~15451/

• Piazza
• Gradescope
• Autolab
• On-line quizzes
• Optional textbooks (many free) are linked on the course website.

• Prerequisites Required: 15-210 and 21-241 and 15-251
• Minimum Grades in Prereqs:
  C in 15-210, D in 21-241, C in 15-251
• Corequisites: None
• Prerequisite for: 
• Anti-requisites: None
• Cross-Listed: 15-651
• Substitutes: 18-202 for 21-241, 21-235 for 21-241, 21-242 for 21-241, 21-341 for 21-241
• Related Courses: None
• Reservations: Some reservations are for Undergraduates in Computer Science; Some reservations are for Undergraduates