Syllabus
Course description
The objective of this course is to study general computational problems, with a focus on the principles used to design those algorithms. Efficient data structures will be discussed to support these algorithmic concepts. Topics include: run-time analysis, divide-and-conquer algorithms, dynamic programming algorithms, network flow algorithms, linear and integer programming, large-scale search algorithms and heuristics, efficient data storage and query, and NP-completeness. This is not a programming course; instead, it will focus on the design and analysis of algorithms for general classes of problems. This course is not open to Computer Science graduate students, who should consider taking 15-651 instead.
Transferable skills:
- Given a problem statement, students will be able to design an algorithm to return a valid solution.
- Given a proposed algorithm, students will be able to analyze its asymptotic runtime and correctness.
- Given a solution (e.g. an algorithm for solving a problem, or an algorithm analysis, perhaps generated via AI), determine if the argument in the solution is flawed.
Coursework will consist of 6 in-class quizzes, weekly tutorial sections (with a participation component), 2 midterms, and a final. The midterms will be non-cumulative, while the final will cover everything from the class.
All lectures will be entirely in-person; there will NOT be any recordings made available of the lectures themselves. However, we will generally try to make pre-lecture notes from the instructor available, and also point to relevant readings for each lecture. You are however responsible for anything that is stated during lecture, even things that may not have been written down on the pre-lecture notes, so you may wish to consult your classmates if you miss class.
Online questions and discussions will be conducted via Piazza. General questions should be public to the rest of the class, but you may use private notes to communicate with just the teaching staff. As there are 5 of us on the teaching staff, please use private notes on Piazza instead of emailing us, as this way we can ensure that all of us get the message.
Reference resources
There is no required textbook. All of the material to be tested will be covered in lectures and tutorials.
However, for most lectures, we will provide references to Algorithm Design by Jon Kleinberg and Eva Tardos (KT) for further reading for interested students. Another reference text is Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (CLRS).
Furthermore, we will also make available a Google NotebookLM's, trained on the Fall 2024 version of the lecture notes and the current Fall 2026 class. While we strongly encourage students to come to our office hours and use Piazza for questions, we understand that many students will also use chatbots to help them study and understand the material. In the past, we have encoutered problems with chatbots either hallcuinating wrong answers, or giving explanations that use esoteric data structures that even the instructors have never heard of. In the latter case, the explanations are not pedagogically useful because they don't teach you how to reason and think about algorithms. Thus, we hope that by providing chatbots specifically scoped to this course, we can avoid some of those problems. Keep in mind, however, that the course material and design changes somewhat each semester, so occasionally the chatbot may refer to the old Fall 2024 version, which does NOT fully reflect this semester's course.
Cross-listed numbers
- 02-613: for MSCB, MSAS, and MSQBB program graduate students.
- 15-650: for any other graduate students
- 15-351: for undergraduates
All the courses have the same structure, lectures, TAs, etc., though the tutorials are separated by number. There may be additional questions for students signed up under one of the graduate numbers on certain assignments. The grading curve may be computed separately in each of the three courses (though historically there typically is not a statistically significant difference in distributions).
Classroom etiquette
To minimize disruptions and in consideration of your classmates, I ask that you please arrive on time and do not leave early. If you must do so, please do so quietly. Laptop use is discouraged; their use detracts significantly from the benefit of coming to class (wouldn't it have been more fun to spend an hour scrolling Tiktok at home?) and also provides a distraction for other students. If you must use your laptop, please turn the sound off, type quietly, and sit as far towards the back of the room as possible.
We will also regularly ask for audience participation / votes. This is not graded, but participating in the votes will make the class more enjoyable for all of us.
Ungraded exercises
Each week, we will release a series of ungraded exercises. You should treat these exercises as homework, as learning to solve them will help prepare you for the quizzes and exams. Indeed, on every quiz, at least one of the quiz questions will be verbatim from the ungraded exercises and another will be similar to the ungraded exercises.
We will not post solutions, because the only point of these exercises is to help you practice. We have found in the past that sometimes students will read solutions and think they understand, but that does not actually prepare you for solving these problems under the time pressure of a quiz or exam, and we are trying to slightly increase the friction of that temptation. However, you are welcome to ask your TAs, your friends, or even an AI tutor for help solving the problems or even full solutions if you think that will help you learn; just keep in mind that the memorizing the solutions is not an effective way of succeeding in this class.
Aside: if there is an overwhelming consensus from students that you want me to post solutions, I will do so, since I have them available. It is my professional opinion though that on average, students learn less when the solutions are just a click away.
Partner quizzes
Twice in each of the three modules, we will have an in-class quiz (see schedule). You may choose a partner for the quiz, with whom you will turn in a single solution. However, you may not choose the same partner twice. You may choose your partner in advance or at the start of the quiz. Once you have started working with a partner, however, you cannot change your partner for that quiz. You are allowed, but discouraged, from doing the quizzes solo. At the start of class, you may also put your name forward for us to assign you a partner.
As stated above, at least one quiz question will be verbatim from the ungraded exercises, and another quiz question will be similar to the ungraded exercises. There will of course also be entirely novel questions. Quizzes are closed-book and electronics-free unless otherwise specified.
Quiz solutions should be as short, clear, and concise as possible. We will be taking marks off for long, meandering solutions to otherwise short problems, even if all of the reasoning is technically correct. Brevity is the soul of wit. Quiz questions that ask for an algorithm should provide: a clear English description, an argument that the algorithm is correct, and an analysis of the running time. Note: your goal is to explain the algorithm to a human, not a computer—as such, detailed pseudocode or source code is usually not the best way to explain an algorithm. Do not use pseudocode to obscure your answer. There will also be quiz questions that ask you to read and evaluate a provided solution to a problem, such as you might get from generative AI; for those questions, your goal will be to determine if the solution is right, and if it is not right, describe the flaw in the solution.
Although the quizzes will be on paper, all of the quizzes will be scanned into Gradescope afterwards. Regrade requests should be made via Gradescope within 1 week of of the quiz being returned, or they will be automatically rejected.
Quiz drop tokens: In keeping with the philosophy of Universal Design for Learning, we understand that you may fall ill or have other unavoidable conflicts during the semester. You are adults and we trust that you can determine these conflicts yourself. Thus, we are giving every student two quiz drop tokens. You may choose to use these two tokens any time before the module exam. If you use a drop token, we will replace that quiz score with your exam score for that module. As an example, you may choose to drop both quizzes for a module, and have the entire module grade be your midterm and tutorial participation, but then you must do all the other four quizzes.
Exams
At the end of each of the three modules, there will be an out-of-class exam. For module 3, this will be the final exam, to be scheduled by the registrar, following all CMU regulations—there will be NO exceptions for the final other than as proscribed in CMU regulations. For modules 1 and 2, the midterm exams will be in the evening, from 7-9pm on the specified Tuesdays in the calendar. All three exams will be classic, closed book, paper exams, to be taken individually. They will then be graded and scanned into Gradescope. Any regrade requests must be made no later than 1 week after the exam is returned to you.
Academic integrity
You may never use, look at, study, or copy any answers from other students during quizzes or exams (except as explicitly allowed). You may not use any electronic aids or cheat sheets, except as explicitly otherwise allowed. Violations will be dealt with harshly.
See the university's policy on academic integrity. In part it reads "unauthorized assistance refers to the use of sources of support that have not been specifically authorized in this policy statement or by the course instructor(s) in the completion of academic work to be graded. Such sources of support may include but are not limited to advice or help provided by another individual, published or unpublished written sources, and electronic sources." You should be familiar with the policy in its entirety.
You may use generative AI to assist you in your studying if you so choose. However, be mindful that it's giving you correct answers. Indeed, one of the learning objectives for this class is for you to practice reading answers of unknown provenance with a critical eye. We will provide some resources to help with vetting generative AI during the class.
Tutorials
Tutorials will be led by your brilliant TAs, who will review basics, go over some of the content taught the previous week, and provide extra practice problems. You should have signed up for a tutorial corresponding to your course number when you signed up for the class; if you haven't please do as these are an important part of the course pedagogy.
At the end of every tutorial will be a very short (~1-2 minute) Check-In Problem. If you have paid attention during tutorial, these problems should be straight-forward; we expect everyone to get high marks on these problems. These are intended as an early warning system so the teaching team can spot problems.
Tutorial Make-up: We understand that some students may not be able to attend every recitatation, or may have accommodations that necessitate alternate arrangements. As such, in the interest of universal design, you may also submit a 3 page handwritten report summarizing the week's lectures.
The pedagogical goal of the tutorials is to ensure that you are keeping up in class on a weekly basis; a make-up report is another way to demonstrate that you are keeping pace.
These reports should be turned in to your TA at the start of the following tutorial of at their office hours.
Grading
There will be two midterms and a final exam, as well as partner quizzes and tutorial participation. The class will be divided into three modules, bookended by the three exams (two midterms and final).
Within each module, 10% of the grade will be tutorial (check-in problem or make-up report), 40% will be the partner quizzes, and 50% will be the exam at the end of the module. If you do better on the exam than your overall module score, then your module score will be replaced by your exam score.
At the end of the semester, your final mark will be the arithmetic mean of the three module scores. However, if you either completed or were excused for every tutorial, quiz, and exam, we will instead use the weighted average of the modules grades: ([lowest module score]*2 + [medium module score]*3 + [high module score]*4)/9. Basically, we will lower the weight of your worst module by increasing the weight from your best module, but only if you don't skip anything.
Accommodations for students with disabilities
If you have a disability and have an accommodations letter from the Disability Resources office, we encourage you to discuss your accommodations and 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.
Excused absences:
Students claiming an excused absence for an exam or midterm must supply
documentation (such as a doctor’s note) justifying the absence. Absences for religious observances
must be submitted by email to the instructor during the first two weeks of the semester.
We have made sure that none of the quizzes or exams fall on any of the holidays listed on the CMU interfaith holiday guide, but if we missed one, please let us know.
For any excused exams, we will arrange a make-up exam at a mutually convenient time.
Excused quizzes will have the weight of the quiz shifted onto the following exam.
Frequently Asked Questions
Is there some extra work I can do to improve my grade?
No, we cannot make exceptions to the course work and grading policy. If you are concerned about your grade, please see me or one of the TAs ASAP. There will be no exceptions to this policy during or after the class has completed. This is a class with nearly 100 students, and it is our duty to ensure that the class is fair for everyone.
I have to be out of town, and I would like a make-up on the quiz. Can I have one?
No. This is the point of your two free quiz drops.
I already know all of the algorithmic basics. Can I skip module 1?
You may use your two free quiz drops to shift quizzes 1a and 1b onto midterm 1, and complete in advance the four tutorial make-up reports. If you do that, you can in theory skip all of the lectures and tutorials and come straight to the module 1 exam. We strongly discourage this.
Final note on class difficulty and struggling
If you've made it this far in the syllabus, I salute you. I did want to add a personal note though, which is that you should be aware that this is a hard class. We cover a lot of advanced material pretty fast, and y'all come from a variety of backgrounds. Masters students who come from a biology background may find Module 1 and the algorithmic review more difficult, while some of the undergrads who've already seen that material before may breeze through it. On the other hand, those same undergrads who might breeze through module 1 may suddenly find the class harder when we get to advanced techniques like amortized analysis in module 2. So, don't be discouraged if you find yourself struggling in parts of the class; that's expected, and after all, it's my job to challenge you to learn cool new things. Having said that, good luck and have fun! -Prof. Yu
