15-451/651 Algorithm Design and Analysis 15-451/651 - COURSE PROFILECourse Level: Undergraduate/GraduateUnits: 12Special 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:Efficient data structuresLower bounds and NP-completenessApproximation algorithmsRandomized algorithmsGeometric algorithmsLow level techniques for efficient programmingLinear programmingOn-line algorithmsGraph algorithms (including maximum flow and matchings)StreamingString algorithmsMost Recent Syllabus: https://www.cs.cmu.edu/~15451/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 providedSample Assignment: not provided4 Written Homeworks: 20%3 Oral Homeworks: 15%Online Quizzes: 10%2 Midterms: 30%Final: 25%Sample Exam: not providedSample Lecture Recording: https://scs.hosted.panopto.com/Panopto/Pages/Sessions/List.aspx#folderSets=15&folderID=%222d165709-dee6-4ebc-9cae-30cac5ce12c0%22Course Goals/Objectives:Understanding of the design and analysis on algorithms for a variety of problemsDevelop 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:PiazzaGradescopeAutolabOn-line quizzesOptional textbooks (many free) are linked on the course website.Prerequisites Required: 15-210 and 21-241 and 15-251Minimum Grades in Prereqs:C in 15-210, D in 21-241, C in 15-251Corequisites: NonePrerequisite for: Anti-requisites: NoneCross-Listed: 15-651Substitutes: 18-202 for 21-241, 21-235 for 21-241, 21-242 for 21-241, 21-341 for 21-241Related Courses: NoneReservations: Some reservations are for Undergraduates in Computer Science; Some reservations are for UndergraduatesMS students should take 15-651. CSD Ph.D. students should likely take a more advanced algorithms class.Department Website:College Website:Updated November 2017https://www.csd.cs.cmu.eduhttps://www.cs.cmu.edu/ Back to Course Profile List