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, two in-class quarterly exams, 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 will alternate
between written assignments that you are to do on your own
and 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+Reci+Bonus | 15% (see below) |
| Quarterly exams (in
class) | 10% (5% each) |
| Midterm exam (in class) | 15% |
| Final exam | 25% |
Recitations
- Everyone is expected to go to their recitation
section. 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.
- Recitations are also your chance to earn easy points
(see "online quizzes+recitation+bonus" below).
Exams
- There will be two quarterly exams, one midterm, and one final exam
- Quarterlies and Midterm will be offered in class
- Quarterlies will be 30 min long and the midterm will
take the full class period.
Online Quizzes
- There will an online quiz most weeks, for a total of 12.
- 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+Recitation+Bonus
- 15% of your grade is allocated to "Online Quizzes +
Recitation + Bonus". This works as follows. Each quiz
is worth 1 point. Attending recitation is worth 0.4
points. We will occasionally give out bonus problems
worth 1-3 points. We total them up and cap at 15.
E.g., the easiest way to get full credit is to attend
all 15 recitations (for a total of 6 points) and get an
average of 75% on the 12 quizzes.
Homeworks
There will be written homeworks and oral presentations,
described below.
Written HWs
- You should work on written homeworks by
yourself. 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.
- Typed homework is not required, but strongly encouraged. 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 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.
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 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 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. Blum or Prof. Gupta as early as possible.
Academic Integrity
Finally, feel free to contact any member of the course staff to clarify
these policies.