15-451/651: Algorithm Design and Analysis (Spring 2025)

Policies

Grades

There will be two midterms: one during week five and one during week ten, and a final during the finals period. There will also be homework assignments. The homework assignments will consist of six written assignments (some of which include one programming problem which requires you to implement an efficient algorithm) and three oral presentation assignments that you will do in groups of three.

Assessment	Grade weight
Homeworks	30%
Recitation Attendance	5%
Midterm exams	20% + 15% = 35%
Final exam	30%

Homework problems are weighted by their point values. The two midterm exams will be weighted based on whichever you perform better on. We will give a higher weight to the exam on which you earn a higher score.

There are no predetermined letter grade cutoffs. These are determined at the end of the semester based on everyone's performance. We will post approximate cutoffs based on midterm grades in the middle of the semester. Overall letter grades may be curved at the end of the class. Graduate students (15-651) may receive plus or minus grades. Undergraduates (15-451) can not be given plus or minus grades.

Homeworks

There will be written homeworks (some with a programming problem) and oral presentation homeworks, described below.

Written HWs

• Most written homeworks will have 2-3 problems. These will mostly be proof-based problems involving the design, analysis, or use of algorithms. Some of the written homeworks include one programming problem (see below).
• The written problems on these homeworks should be submitted on Gradescope by 11:59PM on the due date. Homework may be submitted up to two days late, with a 10% deduction for each late day. Homework may not be submitted more than two days late without an approved extension. Each student has 2 grace days, which will remove the first 2 of these 10% deductions that they receive.
• Written homework must be typeset and worded clearly. LaTeX is strongly recommended.
  • Each problem has a specified page limit that you should try to stick within.
  • You must use US-letter-size paper and should not decrease the font size below 10pt nor decrease the margin size to less than 1 inch, nor typeset your work in any other way that attempts to circumvent the page limit (e.g., removing all spacing between lines/paragraphs).
  • Math should be typeset in math mode using display math when appropriate (for example, if inline math causes the line spacing to change, that math should be moved to display math instead). Named operators should use text font, not math font. For example, you should write , not .
  • Within reason, figures and diagrams do not count towards the page limit. (To not count toward the page limit, figures and diagrams should complement the explanations in the text, they should not be a substitute for a written explanation.)
• Some points will be awarded for each assignment for following these style guidelines.

Oral HWs

• Each oral homework will have 3 regular written-style problems.
• You may work in groups of up to three to solve the problems, and will be asked to present your solutions in these groups in 60-minute time slots between the Wednesday and Friday following their release.
• You are not required to submit anything to Gradescope for an oral assignment. We will enter your scores based on your presentation.
• Grades will typically be assigned to the entire group for their presentation, but may individually differ in some circumstances.

Programming Problems

• The solutions to programming problems will be submitted via Gradescope. It will be judged on correctness and running time against a set of automated tests.
• The officially supported languages are C++ and Python. By officially supported, we mean that we guarantee that the problems are solvable in those languages, and that the course staff have sufficient expertise to assist you in debugging problems written in these languages. We will also try to support C, Java, OCaml, and Rust. We do not guarantee that every problem will be doable in these language (though most should be) and we do not guarantee that a TA will be able to help you debug these languages. Use them only if you are confident with them.
• We may ask you to implement a theoretically efficient algorithm to solve the problem, and we reserve the right to manually deduct points from solutions that exhibit slow worse-case behaviour but successfuly use clever heuristics to pass all of our test cases within the time limit.
• Our submission system will run plagiarism-detection software on the submissions. All code submitted must be entirely your own. You should not refer to any online references aside from language documentation.
• You also get 2 grace days for the programming problems, which are distinct from the written homework grace days. (The rest of the late penalty policy is the same: 10% off per day, maximum 2 days late.)

Bonus Problems

• The homework assignments may occasionally contain bonus problems. If you complete one of these problems, your scores on that problem will replace your lowest homework problem score (unless it is itself your lowest score).
• Bonus problems cannot replace the scores of programming assignments.
• Partial credit will only be awarded to bonus problems for substantially correct answers.

Exams

• There will be two midterms and one final exam. The midterm exams will be limited in scope (midterm one will cover all of the content preceeding it, and midterm two will cover the content after midterm one). The final exam is cumulative, i.e., it will cover all of the contents of the course.
• The midterm exams are scheduled in the evenings at 7:00PM - 9:30PM on the Tuesdays of Weeks 5 and 10 (February 11th and March 25th). You must attend unless you have an approved, important and unavoidable conflict.
• Make-ups exams must be arranged at least one week in advance, barring extreme situations. We will provide a form to fill out if you wish to apply for a make-up exam. Approval of make-up exams is subject to instructor discretion, verification from your academic advisor, and availability of proctors.
• The final exam is scheduled by the university during the exam period. It will be three hours long.

Recitations

• Recitations represent a significant portion of your exposure to problems and problem-solving techniques in this class. You may be tested on the content and techniques presented in recitation on the exams.
• Recitation attendance is taken and used as part of your final grade. You do not have to attend every single week to earn full attendance credit. You have two attendance grace days, i.e., you must attend at least 11 out of the 13 recitations to recieve full credit.
• Recitation handouts will be released on Thursdays. We highly recommend that you look over these in advance and consider how you might solve the problems, as this will give you far better practice for the homework and exams than if you're first exposed to them in recitation, where due to time constraints we have to go over the solutions shortly afterwards. Solutions to the recitations will be uploaded to Box shortly after recitations. These make great references for how to write up proofs of different styles for your homework.
• Theree are two types of recitations: review-heavy and problem-heavy. You may choose to attend any recitation based on which fits your needs better. We encourage that you remain in a consistent recitation once you have chosen one, but if you have a conflict in some week you may attend another recitation that works better for you.

Regrades

• Mistakes may occasionally happen during grading. If you believe your work has been graded incorrectly, you may submit a regrade request for that problem on Gradescope by the regrade request deadline (which will typically be one week after the grades for that homework have been released).
• Regrades may be reviewed by a different TA than the one who originally graded the problem, and the problem will be regraded entirely. This means that you may lose points if the original grader mistakenly awarded too many points, and your overall grade may therefore decrease.
• You must not submit regrade requests simply because you wanted a higher grade. Regrade requests must point out a specific error in the grading and justify why more points should be awarded.
• Occasionally, errors may be discovered during regrading that apply to many students' submissions. In this case, we may regrade several or all students' submissions, even those who have not submitted a regrade request. Your grade may therefore change during regrading (either increase or decrease) even without you specifically submitting a regrade request.

Extensions and excused absenses

• Extensions must be requested by filling out the extension request form. Do not email the TAs or the instructors directly to request an extension.
• Extension requests should be accompanied by a valid reason to support the need for an extension. That being said, if the matter is sensitive (for example, a medical or disability related issue), you should not supply evidence to us directly. Instead, you should have somebody familar with the matter, e.g., your academic advisor, RA, house fellow, or ODR advisor, contact us to confirm the need for an extension.
• Extensions should generally be for only 24 or 48 hours. For any extension request longer than 48 hours, you must have your academic advisor contact us and confirm the need for a long extension. We will only grant extensions of this length in extreme circumstances. For extensions of at most 48 hours, you do not need your academic advisor's confirmation.
• You have two recitation attendance grace days that allow you to miss at most two recitations and still recieve full attendance credit. If you have a legitimate and unavoidable reason to miss more than two recitations, you should also fill out this form to request an excused absence. We may provide additional excused absences from recitation, but only in extreme circumstances, as the two grace days should be enough for most students to cover legimate absences.

Communication and getting help

• We will use Ed for online discussions and important course announcements. It is strongly recommended to have email notifications enabled for Ed messages, as we may post important exam information, etc.
• You may use Ed to ask conceptual questions about the course content and the homework problems. If your question does not reveal any details about the solution to a homework problem (e.g., your question is about a lecture, a rectitation problem, or is a clarification about a homework problem that does not give away part of the solution), then your post must be public. You may post anonymously. Conversely, any post that reveals information about the solution to a homework problem must be private.
• We will offer office hours as specified on the course calendar. These are the best places to ask conceptual questions and get help when you're stuck on a homework problem. Since not every TA is familiar with every available programming language and debugging is quite time-intensive, this will provide relatively less help with programming anomalies.
• All office hours are strictly in person without advanced approval. Students not present in the room will be removed from the queue. If you require remote office hours for a medical reason, please contact us in advance to arrange this.

Accommodations for Students with Disabilities

• If you have a disability and are registered with the Office of Disability Resources, we encourage you to use their online system to notify us of your accommodations. 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. We can not provide any accomodations that have not been explicitly approved by ODR.
• To recieve accomodations on exams, you must register to take the exam with the Office of Disability Resources at their testing center. We are unable to provide accommodations in the main exam sessions. Note that you must register separately and specifically for each exam!
• Accomodations can not be applied retroactively. You may apply for accomodations partway through the semester, but they can only be applied to future assessment.

Academic Integrity

• Collaboration is healthy in the circumstances in which it is explicitly permitted, but plagiarism and cheating are serious academic offenses with serious consequences. Searching online for homework solutions or even similar problems, algorithmic ideas, or code (including of standard algorithms and datastructures) are all classified as cheating, as is getting advice from anyone not in your group (on group problems) or on course staff or looking at anyone's written solutions (even those of your group members). You should read our course policies on academic integrity and the University Policy on Academic Integrity.