Algorithm Design and Analysis Course ID 15651 Description This course is intended for SCS graduate students. This course is about the design and analysis of algorithms. We study specific algorithms for a variety of problems, as well as general design and analysis techniques. Specific topics include searching, sorting, algorithms for graph problems, efficient data structures, lower bounds and NP-completeness. A variety of other topics may be covered at the discretion of the instructor. These include parallel algorithms, randomized algorithms, geometric algorithms, low level techniques for efficient programming, cryptography, and cryptographic protocols. Key Topics 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. Required Background Knowledge 15251, 15210, 21241. The course relies on mathematical thinking and proofs, and requires the ability to program in a compiled language. Course Relevance Students interested in working with 3D data. Examples include: physical/numerical simulation, computer vision, computer graphics, robotics, architecture/art/design, medical or anatomical data analysis. Course Goals 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. Learning Resources Piazza, Gradescope, Autolab, On-line quizzes. Optional textbooks (many free) are linked on the course website. Assessment Structure 4 Written Homeworks: 20%, 3 Oral Homeworks: 15%, Online Quizzes: 10%, 2 Midterms: 30%, Final: 25% Extra Time Commitment This course 15-651 is for graduate students. Undergraduates should enroll in 15-451. Course Link https://www.csd.cs.cmu.edu/course-profiles/15-451-Algorithm-Design-and-Analysis
