|Course Level: Undergraduate/Graduate||Units: 12||Special Permission Required: No |
(if yes, please see Notes)
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.
|Key Topics:||Background Knowledge:||Assessment Structure:|
Most Recent Syllabus: https://www.cs.cmu.edu/~15451/
- 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)
- 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
Sample Exam: 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/
|Learning Resources:||Pre-reqs, Cross list, Related:||Notes:|
- 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
|MS students should take 15-651. CSD Ph.D. students should likely take a more advanced algorithms class.|
|Department Website:||College Website:||Updated November 2017|
|https://www.csd.cs.cmu.edu||https://www.cs.cmu.edu/|| Back to Course Profile List|