Course Policies
Grading
There will be two in-class midterms, and a final during the
finals period. There will also be 7 homework assignments.
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+Bonus | 10% (see below) |
| Midterm exams (in
class) | 30% (15% each) |
| Final exam | 25% |
Recitations
- 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 midterm exams and one final exam
- Each midterm will take a full class period.
Online Quizzes
- There will an online quiz most weeks, for a total of 10 quizzes..
- You will be tested on the material from the previous 2-3
lectures.
- Quizzes are designed to be easy, assuming you are keeping
up with the lectures.
Online Quizzes+Bonus
- 10% of your grade is allocated to "Online Quizzes +
Bonus". This works as follows. Each quiz is worth 1.25
points. We will occasionally give out bonus problems
worth 1-3 points. We total them up and cap at 10.
E.g., you can get full credit by doing an average of 80%
on the 10 quizzes.
Homeworks
There will be written homeworks and oral presentations,
described below.
Written HWs
- You should work on written homeworks by
yourself. There should be no collaboration on
these HWs. If you have questions, come to office
hours. Or, post on Piazza for clarification
questions.
- All written homeworks should be submitted electronically
via
gradescope. Homeworks will
be due at 11:59PM on their due
date. See this page for
instructions.
- We require that you typeset your homework. We think this
not only makes your HWs legible, but the writing forces
you to (re)think through the answers.. LaTeX (see Miktex
for Windows machines) is a good typesetting system for
documents with lots of math; you may know it from taking
15-251. (LaTeX
guide by Adam Blank.) Here is a
Latex template for Hwks.
You can customize it as you like.
- Merely typesetting your HW is not a guarantee of
legibility. So please read over your submissions to ensure
they are readable. If we cannot understand what you've
submitted, you may lose points.
- You will lose points for late submissions. Up to 24
hours late: 10 points off. 24-48 hours late: 20 points
off. If you want to submit more than 48 hours late, you will
lose 75 points. Moreover, you cannot submit electronically after
48 hours, and
must contact your TA to submit. At this point solutions will be posted and you may look at them, though anything handed in should be put into your own words
- Each individual student has two (2) mercy days over the
course of the semester to extend the deadline for written
homeworks.
- If you use any reference or webpage or material from
any other class (including past iterations of 451), you
must cite it, else it will be considered cheating.
Oral HWs
- The oral-presentation homeworks are your chance for
collaboration. It will be done in groups of three. Each
of these assignments will consist of three problems. The
members of your group will work together to solve the
problems -- so here, collaboration is
required. You will then present your solutions,
as a group, to one of the course staff.
- Presentations will be given in 1-hour time slots (there
will be an electronic sign-up sheet reachable from the
course home page). At the presentation, each member of the
group will spend 15 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. We will then take this writeup into consideration
in determining your grade on the assignment.
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, 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).
- 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.
-
For almost all questions related to the class, it makes sense to use
Piazza instead of email. It is faster: you can get a response to
your questions from any of the staff members or even from your
classmates, instead of waiting for the staff member you
emailed. Also, your queries (and their answers) can help your
classmates who have the same questions.
- Make sure you don't post questions to piazza that give away
solutions (or even give hints).
Textbooks:
-
We will provide lecture notes covering all the material in this
course, but we would like you to have a book to give you more
detailed coverage (as well as 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.
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. Kingsford as early as possible.
Academic Integrity
Finally, feel free to contact any member of the course staff to clarify
these policies.