Course Policies
Caveat emptor: this document is a draft and subject to
change until the first day of classes.
Grading
There will be one in-class midterm and a final during the
finals period. There will also be a collection of
in-recitation or online quizzes. Some of the HWs will require oral
presentation and other that are strictly written.
| 7 Written
Homeworks | 30% |
| 3 Oral
Homeworks | 15% |
| Quizzes (in recitation) | 5% |
| Midterm exam (in class) | 16% |
| Final exam | 32% |
| Class Participation | 2% |
Recitations
- Everyone is expected to go to their recitation
section. Remember, in most of the recitations, there are in-recitation
quizzes, which are worth points.
- 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 one midterm and one final exam
- Midterm will be offered in class
- Each midterm exam is designed to be doable in 1 hour,
however you will be given the entire duration
Quizzes
- There will a quiz (
either given at the beginning
of the recitation, or online) most weeks.
- 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.
- We will drop the two lowest score quizzes.
Homeworks
There will be written homeworks and oral presentations.
Written HWs
- All written homeworks should be submitted electronically via
autolab. Due dates are on
Tuesdays Thursdays, 11:59PM.
- Typed homework is not required, but it is your
responsibility to make sure your handin is legible, and
typesetting can help with that. LaTeX (see Miktex for
Windows machines) is a good typesetting system for
documents with lots of math; you probably 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.
- 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 via autolab 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.
- You may work in groups of 2-3. However, each person
should hand-in their own writeup. That is, collaboration
should be limited to talking about the problems, so that
your writeup is written entirely by you and not copied
from your partner. Please try to limit collaboration to
just verbal discissions. In addition, list all members of
your group on your written HWs.
- If you
use any reference or webpage or a solution from any other
class (including past iterations of 451), you must cite it.
Oral HWs
- The oral-presentation homeworks 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. Carefully.
- Spend at least one hour thinking about each problem by yourselves. This is the vital part of
understanding the course's material. You will get stuck, that's ok. When you do, here are
some suggestions to help you get past it.
- Come up with a dummy example, over a small number of item, and try to solve it. 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 a
graph? a 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.
- Only after you gave the problem a serious amount of thinking, try to
collaborate, ask on Piazza, or come to the TAs for guidance.
- Write down the solution, by yourselves. Re-read what you've
wrote. Make sure the solution is exact, and answers specifically what
you've been asked about. It should be clear, but it need not necessarily
be long.
Bboards:
- We will be using
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. Gupta as early as possible.
Academic Integrity
Finally, feel free to contact any member of the course staff to clarify
these policies.