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.
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.
Your grade will depend on HWs, exams, and class participation.
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.
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.
There is no mandatory textbook for the course. We will provide lecture notes, or reading from books. Some good books include:
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.
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.
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.