15-750: Algorithms in the Real World, Fall 2023

Course Description

The course covers a broad set of topics in algorithms design and analysis, with an emphasis on their applications. 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) become reasonably proficient at using these tools; and, (c) 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 data structures and algorithmic principles, randomized algorithms, hashing and streaming, flows and linear programming, convex optimization, linear algebraic algorithms, spectral algorithms, compression, and algorithms for error correction.

Change in Course Title

Until 2021, the course 15-750 was called Graduate Algorithms. The change in name is meant to emphasize that the course is aimed at graduate students who wish to learn algorithmic principles with an emphasis on their applications in the real world. See the pages for the 15-750 offerings from Spring 2022, Spring 2021 and Spring 2020.

The name Algorithms in the Real World used to correspond to the course number 15-853 (see F19 version and older webpages). The current 15-750 course has many similarities with the old 15-853, including a common philosophy and a large number of topics. Hence we merged the courses into one.

Syllabus

Here is a tentative schedule for the course. Broadly, we plan to cover (potentially a subset):
  1. A refresher on basic algorithmic principles: greedy, divide-and-conquer, dynamic programming, and their applications
  2. Hashing and Randomization
  3. String Algorithms
  4. Streaming algorithms (a.k.a. algorithms for big data)
  5. High-dimensional data: dimensionality reduction, nearest neighbor
  6. Flows and Cuts, Graph Partitioning
  7. Linear Programming and Duality, and Convex Programming
  8. Compression
  9. Error Correcting Codes
  10. Continuous Optimization, gradient descent, multiplicative weights
  11. Online Decision-Making: Competitiveness and Regret

Course Policies

Effort and Criteria for Evaluation:

Your grade will depend on HWs, exams, and class participation.

The grading breakdown is: 32% for the midterm, 32% for the final exam, 32% for the homeworks, and 4% for attendance/class participation in lectures/Piazza/office hours.

Homeworks:

Homeworks are due at 11:59pm on the due date. They must be submitted via gradescope. For each homework, there will be a two-day (48 hours) no-questions-asked extension. Two-days independently for each HW; this does not accumulate. Students can use this extension for any valid reason without having to ask the instructor. We do not plan to provide additional extensions (barring truly exceptional circumstances).

We're happy with clear legible handwritten homeworks, to start off. However, if your legibility turns out to be a problem, we may require you to typeset your homeworks.

Collaboration policy: Excluding problems specifically marked "solo", you may collaborate in a group of 2-3 people. We require that collaborations be "whiteboard" collaborations. This means that you can discuss problems and solutions with your group on a "whiteboard"; after this, each person should go away and write their own solutions, which they then submit. That is, collaboration should be limited to talking about the problems, so that your write-up is written entirely by you. No written work may be shared. You must list all members of your group on your submission; please write "none" if you had no collaborators. In all cases, if you use any resources other than the course notes/slides, you must cite them.

Prerequisites:

We will assume basic knowledge in algorithms, probability, and linear algebra. We urge you to brush up on them if you are rusty --- we can point you to books or lecture notes on them. The use of linear algebra and probability is ubiquitous across all of CS, just like the use of algorithms. Learning those topics will not be a waste of your time, whether you take this course or not. See below for some resources to help you brush up.

Textbook:

There is no mandatory textbook for the course. We will provide lecture notes, or reading from books. Some good books include:

We assume basic discrete mathematics (counting, basic probability, basic graphs theory, basic linear algebra). Some resources include:


FAQs:


Accommodations for Students with Disabilities:

If you have a disability and are registered with the Office of Disability Resources, we request you use their online system to notify us of your accommodations and discuss your needs with us as early in the semester as possible. We will work with you to ensure that accommodations are provided as appropriate. If you suspect that you may have a disability and would benefit from accommodations but are not yet registered with the Office of Disability Resources, we encourage you to contact them at access@andrew.cmu.edu.

Make-ups for the midterm/final must be arranged at least one week in advance, barring extreme situations. Please make sure to document any health problems you might have.

Diversity in the Classroom

In this course, we strive to treat everyone with respect, and provide everyone with the best learning experience we can. We believe that diversity, equity, and inclusion should be our goals, not only because they fuel excellence and innovation, but because these are just. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally, or for others.

Academic Integrity

Honesty and transparency are important features of good scholarship. On the flip side, plagiarism and cheating are serious academic offenses with serious consequences. If you are discovered engaging in either behavior in this course, you will earn a failing grade on the assignment in question, and further disciplinary action may be taken. For a clear description of what counts as plagiarism, cheating, and/or the use of unauthorized sources, please see the University Policy on Academic Integrity and the Carnegie Mellon Code on Academic Integrity.

Please recall that for the (non-solo) homework problems, your submission must contain the names of person(s) you collaborated with. You are not allowed to look at online resources or books when solving the homeworks (except for resources provided on the course webpage).

Your Health & Well-being

Part of making sure that you enjoy the course involves taking care of yourself. Do your best to maintain a healthy lifestyle this semester by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.

If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit http://www.cmu.edu/counseling/. Consider reaching out to a friend, faculty or family member you trust for help getting connected to the support that can help.


Back to course main page.