Created: Tue 04 Sep 2012
- Lecture: Mon/Wed 2:40--4:30pm
- Room: 022 International Villiage
There are no formal prerequisites for this course. However, this is a
fast-paced, intensive, PhD-level course, and as such, a certain level
of mathematical sophistication and background familiarity with
algorithms will be assumed. If you are not a PhD candidate in the
College of Computer and Information Science, you must obtain approval
from the instructor to attend this course.
Errata for this text are available on-line. If you are concerned that
something in the text might be a typo, please check the errata
available here: Errata for
Introduction to Algorithms.
- Introduction to Algorithms (third edition) by
Cormen, Leiserson, Rivest, and Stein. (Required)
- There will be weekly written assignments, generally handed out on
Wednesdays and due the following Wednesday. Some of the exercises
will be routine, but others will be more challenging. I do not
expect you to solve all of the homework problems, but I hope that you
will benefit from working on the more difficult ones. A few hints
on the homework assignments:
- Start early: Difficult problems are not typically
solved in one sitting. Start early and let the ideas come to you
over the course of a few days.
- Be rigorous: Each problem has a (sometimes
unwritten) requirement that you prove your algorithm
correct and analyze its running time. To obtain full credit
for a problem, it is necessary to fulfill this requirement.
- Be concise: Express your algorithms at the proper
level of detail. Give enough details to clearly present your
solution, but not so many that the main ideas are obscured.
English is the best way to express an algorithm; revert to pseudocode
only if necessary.
- Work with others: Some of the problems will
be difficult, and it will often be helpful to discuss them
with others. Feel free to form study groups. However, the
idea is for everyone to understand the problems and experience
working through the solutions, so you may not simply
"give" a solution to another classmate. In particular, each
student must write up his or her own homework
solutions and must not read or copy the solutions of
others. If you work with others on a problem, you
must note with whom you discussed the problem at the
beginning of your solution write-up.
- Homework is due at the beginning of class on the
announced due date. You will be granted one homework extension,
to be used at your discretion, no questions asked. After the
first late assignment, unexcused late assignments will be
penalized 20% per calendar day late. I normally will not accept
assignments after the date on which the following assignment is
due or after the solutions have been handed out, whichever comes
first. If you will have a valid reason for turning in an
assignment late, please see me in advance to obtain
- We will employ a somewhat unusual grading scheme. Each homework
assignment will have n problems, and each problem will
be worth k points. You will be required to attempt any
m problems. (The parameters n, m and
k will vary from assignment to assignment.)
These m problems will be graded
in the usual manner: you will receive full or partial credit out
of k points. You may also choose to attempt the remaining
n-m problems. These problems will be graded as follows.
Say that you would have received a score of j points
if this problem had been graded normally. If j is less than
k/2, then you will receive zero out of zero points, as if
you had not attempted the problem. Otherwise, you will receive
2j out of 2j points. Note that attempting extra
problems can only help you. Your grade on an assignment
will be reported by two numbers: the points you obtain and the
points you effectively attempt. Your homework grade at the
end of the term will be calculated as the sum of the points you obtained
divided by the sum of the points you effectively attempted.
- The purpose of this policy is threefold:
- It is designed so as not to penalize you for skipping some
- It is designed to encourage you to attempt all of the problems.
- It is designed specifically to discourage you from writing up long
answers which you suspect are incorrect, in the hopes of picking up a
point or two.
- Note: Your free late assignment and any unexcused
late assignments will only be graded for regular problems. Excused
late assignments (e.g., due to illness) will be graded for
both regular and extra credit.
- There will be a midterm and a final exam, each
of which will be take-home. Unlike the homework assignments, you may
only discuss exam problems with Professor Aslam.
- Homeworks: 50%
- Midterm: 25%
- Final: 25%
- All work submitted for credit must be your own.
- You may discuss the homework problems with your classmates
and Professor Aslam. You must acknowledge
the people with whom you discussed your work, and you must write
up your own solutions. Any written sources used (apart from the text)
must also be acknowledged; however, you may not consult
any solutions from previous years' assignments whether they are
student or faculty generated.
- Please ask if you have any questions about academic honesty as it
applies to CS7800.