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.
Coursework will consist of weekly homeworks, weekly recitation sections (with short attention quizzes), 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. We will generally try to make pre-lecture notes from the instructor available, and also point to relevant readings for each lecture.
Online questions and discussions will be conducted via Piazza. You should post questions there, though please be careful not to give away any answers to problems. 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 6 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 texts
The primary reference text is Algorithm Design by Jon Kleinberg and Eva Tardos (KT). Another reference text is Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (CLRS).
Cross-listed numbers
- 02-613: for MSBIC or MSCB 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 recitations 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 will be computed separately in each of the three courses.
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.
Homework
Homework will be due on a weekly basis every Tuesday at 8pm. New homework will be released no later than Tuesday each week. We will NOT accept any late homework. This is because we will be posting solutions shortly after the deadline—especially for the homeworks due right before midterms, we feel providing the solutions may be helpful in your studying. Thus, there is no fair way to accept late homeworks. Having said that, if you are up to a few hours late, and we don't notice before we've posted the solutions or started grading, we won't penalize you—it's still late, but if we don't notice, there's no harm done.
Homework must be handwritten and submitted online (either scanned or written on a tablet) to Gradescope. Your midterms and final exam will be handwritten, so we want you to practice in that format.
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.
Homework problems that ask for an algorithm should present: 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.
Regrade requests should be made via Gradescope within 1 week of the homework being returned. Keep in mind that a regrade is exactly that, and there's not only no guarantee your score will go up, but it may go down if we spot additional errors while regrading.
Homework 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 three homework drop tokens. In order to use a drop token, you must post a private message to the instructors on Piazza either (1) before the grades come out if you turned in the homework, or (2) within 2 weeks if you did not turn in the homework. You may use these drop tokens for any reason, but you only get three of them.
If you use a drop token, we will simply not take that homework into account for the module grade. Note that if a module has 5 homeworks worth 15% (see grading below), where each homework happens to be worth the same number of points, and you drop a homework, then the homeworks overall will be worth only 12/97*100%, because one of the five homeworks did not count. Note that some homeworks will have more questions and be worth proportionally more.
Academic integrity and collaboration
You may discuss homework problems with classmates. You must list the names of the class members with whom you worked at the top of each solution (if you worked with Jane Doe on problems 1 and 2, you should write down her name as a collaborator in the solution for both problems). However, you must write up your own solution independently! "Independently means – at least – that you cannot look at another person's homework, you cannot have them look at yours to see if it is correct, you cannot take detailed notes from a discussion and edit them into your homework, and you cannot sit in a group and continue discussing the homework while writing it up. The intent of this rule is: you can gather around a chalkboard with your fellow students and discuss how to solve the problems. Then you must all walk away and write the answers up separately.
This collaboration rule is partly for your own benefit; we obviously have no way to enforce it, but most of your grade comes from the exams, and we are trying to encourage you to do homework in a way that will best prepare you for the exams. Having said that, we often find some people who have copied each other's homeworks. Such instances are referred to the University according to the academic integrity violation policy, which is then out of our hands.
You may never use, look at, study, or copy any answers or exams from previous semesters of this course, except as we explicitly make available to you. No excuses will be accepted for copying others' work (from the current or past semesters), and 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.
In particular: use of previous semester's answer keys or online solution manuals for graded work is absolutely forbidden. Turning in output from generative artificial intelligence tools is also strictly forbidden. Any use of such material will be dealt with as an academic integrity violation. (Aside, using ChatGPT to learn general information about a topic is allowed, but just be careful that it's giving you correct answers.)
Recitations and Attention Quizzes
For the first time for this course, by popular demand, we are introducing recitations. These recitations will be led by your brilliant TAs, who will go over some of the content taught the previous week, and provide extra practice problems. You should have signed up for a recitation 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 recitation will be a very short (~1-2 minute) Attention Quiz. If you have paid attention during recitation, these quizzes should be straight-forward; we expect everyone to get high marks on these quizzes.
Attention Quiz Make-up Report: 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-5 page handwritten report summarizing the lectures covered by the quiz.
The pedagogical goal of the attention quiz 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 are due online no later than the Friday after each quiz, but may be submitted for any reason to replace your quiz mark.
Alternately, do keep in mind that if you perform better on the end-of-module exam than your homeworks and quizzes, your module grade will be entirely the exam (see Grading below).
Grading
There will be two midterms and a final exam, as well as homework and recitation participation. The class will be divided into three modules, bookended by the three exams (two midterms and final). Students who go to the recitations and do homework will have that factored into their grades. Alternately, students can also be assessed entirely on exam performance. The teaching staff will compute your grade both ways at the end of the semester, and give you the higher of the scores.
More precisely, within each module, 15% of the grade will be homework, 5% will be recitation attention quizzes, and 80% 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 (average) of your grades in the three modules. Alternately, if you turn in and get a nonzero score on all homework assignments and all recitation quizzes that are not dropped, then we will reweight the modules in your favor by computing the following weighted average: ([lowest module score]*2 + [medium module score]*3 + [high module score]*4)/9. Basically, if you bomb one midterm, you can move a portion of the weight onto your best performing module, assuming you have been completing all the work in the class.
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.
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 over 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 an extension on my homework. Can I have one?
No. This is a very large class, and it is not possible to accommodate individualized deadlines for everyone. You can always turn your homework or quiz make-up reports in early or remotely on Gradescope. Alternately, the homework drop tokens are no-questions-asked, so you may use those instead.
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
