Assignments & Grading
There will be two inclass midterms and a final during the
finals period. There will also be nine homework assignments. The nine homework
assignments contain some written assignments that you will complete by yourself,
and some oral presentation assignments that you will do in groups of three.
6 Written Homeworks 
30% (5% each) 
3 Oral Homeworks 
12% (4% each) 
Recitation Attendance 
3% 
Midterm exams (in
class) 
30% (15% each) 
Final exam 
25% 
Overall letter grades will be curved at the end of the class. Master's students will
accordingly receive standard plus and minus grades.
Homeworks
There will be written homeworks and oral presentations,
described below.
Written HWs

Most written HWs will have 34 problems. These will mostly be proofbased
problems involving the design, analysis, or use of algorithms, but may also
include programming questions requiring implementation.

All written work you submit must be entirely your own. You should not
discuss the problems except with course staff, nor reference materials outside
of those provided by this course in F22 and its prerequisites. Referencing
other material is cheating.

The written problems on these homeworks should be submitted on
Gradescope by 11:59PM on the Wednesday
following their release, with a 10% deduction for each day later than that.
That Friday is the last day a homework may be submitted, for 80% credit.
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 recommended
(guide
and HW template).

Based on TA availability, we will grade either some or all of the questions.
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, and Python.
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. All code submitted must be entirely your own, even in
cases when the course staff allows you to discuss with groups. 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.)
Oral HWs

Each oral homework will have 3 regular writtenstyle problems.

You may work in groups of up to three to solve the regular problems,
and will be asked to present your solutions in these groups in
60minute time slots between the Wednesday and Friday following their
release.

Grades will typically be assigned to the entire group for their
presentation, but may individually differ.

Oral homeworks will not have programming components.
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.
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).

Partial credit will only be awarded to bonus problems
for substantially correct answers.
Exams

There will be two midterms and one final exam.

Midterms will be offered in class and will
take the full class period. The final will
be offered during the final exam week.

The formats will be given closer to the date.
See the schedule for the exam dates.
Recitations

Recitations represent a significant portion of your
exposure to problems and problemsolving techniques
in this class. You may be tested on the techniques
presented here as well as material taught in the
case that the lecture is unable to cover all of a
week's content.

Recitation handouts will be released on Thursday.
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 on Friday evening. These
make great references for how to write up proofs
of different styles for your homework.

We encourage that you remain in your consistent
recitation, but if you have a conflict in some
week you may attend another recitation that works
better for you. If there are room capacity issues
we will ask those not officially assigned to a
given recitation to leave.
Resources:

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 timeintensive, this will provide relatively
less help with programming anomalies.
All office hours will be in person. Students not present in the
room will be removed from the queue.

We will use Piazza
for online discussions and course announcements. It is
the best place to ask logistical and debugging questions
but will provide relatively less help with problem solving.
Please ask public questions unless your question requires
revealing details of your homework solutions.

We will use Gradescope
to collect written homework submissions and facilitate regrade
requests.

We will use Canvas
to collect combined student grades from all sources.

We will use Panopto
to post lecture recordings for students who miss lecture or want
to revisit it.

We will use Box to host
solutions to past recitations and homework for your perusal.
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 send an email to Magdalen Dobson on our course staff 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. Anderson or Prof. Woodruff as early as possible.
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).
The above is not an exhaustive list of academic integrity violations, and if
you are ever uncertain about what is allowed you should ask the course staff.
If you cheat in the class we will penalize you and report you to the university.
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.