Algorithms in the Real World

Course ID 15750

Doctoral Breadth Course: Algorithms and Complexity - (*)
Classes marked with "*" (star) are appropriate for any CSD doctoral or 5th year master's student.

The course covers a broad set of topics in algorithms design and analysis. The goal is to cover tools and algorithms that give students the ability to (a) recognize which tool or method to apply to problems, (b) to become reasonably proficient at using these tools, and (c) to be able to reason about the correctness and performance of the resulting algorithms. The course webpage for this semester will list the tentative list of topics to be covered; these will include basic graph algorithms, randomized algorithms, hashing and streaming, flows and linear programming, convex optimization, and linear algebraic algorithms. Please refer to https://www.cs.cmu.edu/~csd-grad/courseschedules22.html for the most recent schedule updates.

Key Topics
Some basic graph algorithms: trees, matchings; Hashing and Randomization; Streaming algorithms (a.k.a. algorithms for big data); Flows and Cuts, Graph Partitioning; Linear Programming and LP Duality; Convex Programming; Continuous Optimization, gradient descent, multiplicative weights; High-dimensional data: nearest neighbor, dimensionality reduction; Random walks; Online algorithms; NP completeness and Approximation Algorithms

Required Background Knowledge
We will assume basic knowledge in algorithms, probability, and linear algebra.

Course Relevance
This is a graduate breadth (aka star) course aimed at students who have learned some basic undergraduate algorithms material (probably not 15-451, see the FAQ), and want to get a broader/deeper understanding of algorithms. (Students aiming to specialize in theoretical CS should consider 15-850 Advanced Algorithms instead.)

Course Goals
The goal is to cover tools and algorithms that give students the ability to (a) recognize which tool or method to apply to problems, (b) to become reasonably proficient at using these tools, and (c) to be able to reason about the correctness and performance of the resulting algorithms.

Learning Resources
lecture notes from selected texts;

Assessment Structure
Your grade will depend on HWs, exams, and class participation. We have ~7 HWs (including HW0), roughly every other week. Some may be solved with collaboration, some solved individually. There will be one midterm and one final exam. Both will be during the class times. We expect you to attend the lectures, and will give you some points for attendance/class participation.
The rough breakdown will be 32% each for the exams (midterm and finals), 32% for the homeworks, and 4% for attendance/class participation in lecture or Piazza.

Course Link
http://www.cs.cmu.edu/~15750/