Course Policies
Grading
There will be two inclass midterms, and a final during the
finals period. There will also be 7 homework assignments and
a collection of short online quizzes. The 7 homework
assignments contain some written assignments that you are to
do on your own 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) 
Online Quizzes + Checkin Videos + Bonus 
11% (see below) 
Midterm exams (in
class) 
30% (15% each) 
Final exam 
24% 
Recitations
 Everyone is expected to go to recitation; however, you may
attend any section that you want.
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.
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 11
quizzes. Most quizzes will be out Thursday after lecture and due Saturday 11:59pm;
you can ask for help with them on Friday in recitations.
 You will be tested on the material from the previous 23
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 + Checkin Videos + Bonus
11% of your grade is allocated to "Online Quizzes + Checkin Videos + Bonus". This works as follows.
 Quiz:
Each quiz is worth 1 point. There are 11 quizzes.
 Recitation Attendance/Participation + Checkin Videos:
The course staff will award a total of 3 points for recitation attendance/participation.
Alternatively, you may choose to submit a short (3060 seconds) weekly checkin
videos to your TA (through a DM) on the 451 Students Slack.
In these checkin videos, you may ask about quizzes, give course feedback,
clarify lecture material or talk about anything you particularly liked/found
interesting over the past week. We discourage asking homework problems since it
would be more appropriate in OH or on Piazza.
We expect these videos to be submitted between the last lecture of the week and
5:00pm Friday. You'll be able to signup for a TA to send these videos to in the
first week of the class (check Piazza); they will be assigned to you all semester long.
They will be your best point of reference if you have issues with course logistics.
 Bonus Questions:
Finally, we may occasionally give out bonus problems
worth 12 points.
 We total the points up from online quizzes,
checkin videos, and bonus, and cap at 11.
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 individual or group problem. You should
work on all individual problems by yourself. Group problems can be done
in groups of up to 3. Please remember to cite your group members. If you have
questions, come to office hours. 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 reread 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. 2448 hours late: 20 percent
off. You may not handin 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.
Nontransferrable. 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,4, and 7) has
four (4) problems. One of these will be a programming
problem. The other three will be regular problems for oral
presentations.
 These homeworks are your chance for collaboration. 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 60minute time slots (there
will be an electronic signup sheet reachable from the
course home page). At the presentation, each member of the
group will spend 1520 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.
 If you are nervous about your presentation, you may in
addition hand in a written sketch of your solution as
well. (This is optional.) We will then take this writeup
into consideration in determining your grade on the
assignment.
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. (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 plagiarismdetection
software on the submissions. Please do not copy!
Solving the Homework
Ideally, this is how you should approach
the homework.
 Read the material taught in class, and make sure you understand all
the definitions, algorithms, theorems and proofs.
 Read the homework problem. Carefully.
 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, nonnegative weights)?
 The notion of subproblem (divideandconquer, dynamic programming,
induction) is a recurring theme in this class. Try to identify and solve
the subproblems 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).
 When you write down your solution, reread 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.
 We will have a course Slack for weekly checkin
videos that will be submitted to your TA through a DM. You may use the Slack channel to clear
up conceptual questions with other students and share anything interesting. We will have TAs
monitor
the Slack but we won't be active in answering student questions; please use the Piazza if you
want an
answer from the staff. Feel free to use the Slack to communicate with your group.
 Make sure you don't post questions to piazza/Slack 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
AhoHopcroftUllman book. See also
some excellent
lecture notes by Jeff Erickson at UIUC.
`
Your Health & Wellbeing

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 4122682922 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
 Makeups 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. Woodruff 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.