Course Policies

Grading

There will be two in-class midterms and a final during the finals period. There will also be 7 homework assignments and a collection of short online quizzes on Canvas. The 7 homework assignments contain some written assignments with both SOLO and GROUP problems (see below for details) and some oral presentation assignments that you will do in groups of three.

4 Written Homeworks	20% (5% each)
3 Oral Homeworks	15% (5% each)
Bonus Problems	1% per problem (see below)
Online Quizzes + Recitation Attendance	12% (see below)
Midterm exams (in class)	30% (15% each)
Final exam	23%

Bonus Questions

• The homework assignments may occasionally contain bonus questions. These are written problems, and they are worth about the same as any other homework problem, and are added into the total homework grade. The maximum total percent that can be obtained via the homework category is 35%.
• Bonus problems may be quite challenging, but we are unable to assist with them in office hours or Piazza.

Recitations

• Everyone is expected to go to recitation. You may attend any section that you want; however, it is the best to attend the one you registered for, so that we avoid exceeding room capacities during the pandemic. If you want to attend a different one write to the TA whose recitation you’re not attending and the one whose recitation you want to attend ahead of time. Do not attend recitations in person if you have COVID-19 symptoms. Contact Student Health Services as soon as possible.
• Recitations are a chance to engage in more discussion than is usually possible in a large lecture, with a focus on the process of solving algorithmic problems. Recitations will occasionally contain new material as well, on which you may be tested.
• In case you are not feeling well or have some important duties and must miss a recitation, if you notify your usual recitation TA in advance and send in a check-in video in time, you will receive attendance credit for the week.

Check-in Videos

If you cannot attend recitation, in order to receive attendance credit, you must notify your usual recitation TA in advance and then send a check-in video where you briefly explain one concept from the same week's lectures, or summarize the approach to a recitation problem. Feel free to talk about other thoughts as well; although, keep the length to only 2-3 minutes. Do not include homework questions or urgent requests in check-in videos. Please email them to your recitation TAs by 11:59pm the Sunday following the recitation.

Exams

• There will be two midterms and one final exam.
• Midterms will be offered in class and will take the full class period. See the schedule for the exam dates.
• The format will be given closer to the date.

Online Quizzes

• There will an online quiz most weeks, for a total of 12 quizzes. Most quizzes will be out Thursday after lecture and due Saturday 11:59pm.
• You will be tested on the material from the previous 2-3 lectures. You may refer to the course materials to solve the quizzes.
• Quizzes are designed to make sure you are keeping up with the material presented in lectures. If you are, you will find most of the problems easy.

Online Quizzes + Recitation Attendance

12% of your grade is allocated to "Online Quizzes + Recitation Attendance". This works as follows.

• Quiz: Each quiz is worth 1 point. There are 12 quizzes.
• Recitation Attendance/Participation + Check-in Videos: The course staff will award a total of 3 points for recitation attendance/participation.
• We total the points up from online quizzes and recitation attendance, and cap at 12.

Homeworks

There will be written homeworks and oral presentations, described below.

Written HWs

• Each written HW will have four (4) problems. One of these will a programming problem. (See the section on programming problems below for more details on these.) The other three problems will be written problems.
• Each question will be labeled as a SOLO or GROUP problem. You should work on all SOLO problems by yourself. GROUP problems can be done in groups of up to 3. Group work is limited to brainstorming about the problems. All submitted written solutions and code must be written by you and you alone. You are expected to work with the same people on group problems in a given week, but may change your groups between different assignments. Please remember to cite your group members in your submission. If you have questions, come to office hours. If you have questions on a group problem you are encouraged to come as a group, but only one group member should put your group on the queue for group problems at a time. Or, post on Piazza for clarification questions.
• The written problems on these homeworks should be submitted electronically via gradescope. Homeworks will be due at 11:59PM on their due date.
• Based on TA availability, we will sometimes grade a subset of the written HW. Your grade will be scaled based on the number of questions we grade.
• You must typeset your homework. This makes your HWs legible, and the writing forces you to (re)think through the answers. Of course, merely typesetting your HW is no guarantee of legibility. Please re-read over your submissions! If we cannot understand what you've submitted, you may lose points.
• LaTeX (see Miktex for Windows machines) is a good typesetting system for documents with math. Here's a LaTeX guide by Adam Blank, and a Latex template for Hwks. You can customize it as you like.
• You will lose points for late submissions. Up to 24 hours late: 10 percent off. 24-48 hours late: 20 percent off. You may not hand-in submissions past 48 hours after the deadline.
• Each student also gets 2 "grace/mercy days", aka "10% off off coupons". These will be automatically applied to counteract up to 20% total in lateness penalties. Not good on hwks turned in more than 48 hours late. Non-transferrable. Void where prohibited.
• Do not do web searches to try to find solutions to the homework problems. Do not use sites that compile solutions to homework problems. This is cheating. (Also see the academic integrity section below.)

Oral HWs

• Each oral homework (Homeworks 2, 5, and 7) has four (4) problems. One of these will be a programming problem. The other three will be regular problems for oral presentations.
• Please form groups of three. The members of your group will work together to solve all four problems.
• For the lone programming problem, you must then write the solution program by yourself! The submission process is the same as for the other homeworks.
• For the three oral presentation problems, you will present your solutions, as a group, to one of the course staff. Presentations will be given in 60-minute time slots (there will be an electronic sign-up sheet released on Piazza). At the presentation, each member of the group will spend 15-20 minutes presenting one of the problems. The instructor/TA will decide who presents which problem, but when one member is presenting, other members are allowed to chime in too. In the end, the three presentations together will determine the score for the group. However, we reserve the right to give different members different scores when we believe it is warranted.

Programming Problems

• The solutions to programming problems will be submitted via Autolab. Your program will read its input from standard input and output to standard output. It will be judged on correctness and running time. The languages accepted are Java, C, C++, Ocaml, SML, Rust. (Sorry, no Python this semester.) More details will appear on piazza.
• For tips and further instructions on the programming problems, see here
• Our submission system will run plagiarism-detection software on the submissions. Please do not copy!
• You also get 4 grace days for the programming problems, which are applied independently of the written homework late days. (The rest of the late penalty policy is the same: 10% off per day, maximum 2 days late.)

Solving the Homework

Ideally, this is how you should approach the homework.

1. Read the material taught in class, and make sure you understand all the definitions, algorithms, theorems and proofs.
2. Read the homework problem. Carefully.
3. If you get stuck, here are some suggestions to get past it:
   • Come up with a small example, and see how you would solve that. This is particularly helpful when you're trying to follow an algorithm, or when devising a counter example.
   • Which algorithms / techniques / heuristics taught in class are applicable to the problem at hand? When do they fail and for what reason?
   • Reduce the problem to a problem taught in class. Can the problem be represented as tree? a graph? a flow network? maybe to a less general instance of the problem itself (a graph with negative weight to a graph with unique, non-negative weights)?
   • The notion of sub-problem (divide-and-conquer, dynamic programming, induction) is a recurring theme in this class. Try to identify and solve the sub-problems of the problem at hand.
   • If you are still stuck, come to office hours. Sometimes just a brief meeting can get you pointed in the right direction (or help to back you up from a wrong path, to use a DFS analogy).
4. When you write down your solution, re-read what you've written. Is the solution understandable? Does it answer specifically what you've been asked about? Your answers should be clear, and often they will be short.

Bboards:

• We will use Piazza for online discussions and course announcements.
• Make sure you don't post questions to piazza that give away solutions (or even give hints).
• Piazza is best used for announcements, clarifications, and short queries. If you want to discuss problem solving, or need advice on how to get unstuck, please come to office hours! We are here to help you.

Textbooks:

• Several of the topics we teach, particularly the more advanced ones, are not covered in the standard Algorithms textbooks. Hence we will provide lecture notes covering all the material in this course.
• However, we would like you to have a book to give you more detailed coverage. (Or to give you an alternative perspective if you find our own confusing!) We recommend you get one of the following:
  • Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein (hereafter referred to as "CLRS"). It's big, it's fairly expensive, but it is the gold standard of algorithms books with a lot of material. Based on the Algorithms course at MIT.
  • Algorithms, by Dasgupta, Papadimitriou, and Vazirani (herafter referred to as "DPV"). Smaller, cheaper, more informal. A relatively new book based on Algorithms courses at UC Berkeley and UCSD. A preliminary (incomplete) version is available here.
• Specific readings in CLRS and DPV will be listed on the course schedule. It is recommended that you skim the reading before lecture, with a more thorough read afterwards.
• Other helpful material can be found in: Algorithm Design by J. Kleinberg and E. Tardos, Data Structures and Network Algorithms by R. E. Tarjan, Randomized Algorithms by Motwani and Raghavan, Programming Pearls by J. Bentley, Introduction to Algorithms: a Creative Approach by U. Manber, and the classic Aho-Hopcroft-Ullman book. See also some excellent lecture notes by Jeff Erickson at UIUC.

`

Your Health & Well-being

• We want you to learn cool new things in the course, things that will be useful for your life and career. And we want you to have fun learning this material! Part of making sure you have the right experience 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.

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 and also come and see us to discuss your needs 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.

Other Policies

Lateness and Absence

• Make-ups for the exams and the final must be arranged at least one week in advance, barring extreme situations. Make sure to document any health problems you might have. If you need special accommodations, please contact Prof. Sleator or Prof. Shi as early as possible.

Academic Integrity

• We will assume that you understand the issues and do not need a detailed explanation here: in a nutshell, collaboration is healthy, but plagiarism and cheating are serious academic offenses with serious consequences. (And yes, doing web searches for homework solutions is cheating, as is looking at others' solutions for HWs where we do not allow collaboration.) If you cheat in the class we will penalize you and report you to the authorities. Issues will be handled in accordance with the University Policy on Academic Integrity. Please also see the the Carnegie Mellon Code on Academic Integrity.

Finally, feel free to contact any member of the course staff to clarify these policies.