| Instructor |
Greg Plaxton
(office hours M 3:30-4:30 and Th 3-4, TAY 3.132; email: plaxton at cs)
|
| |
|
| Teaching Assistant |
Muhibur Rasheed (office hours W 11:30-12:30 and F 2:30-3:30,
location ENS 31NQ Desk 2; email: muhibur at cs). Directions to ENS
31NQ: (1) take the elevator down to "LB" (lower basement); (2) exit
the elevator to the right; (3) keep going down the hallway, which will
curve to the right; (4) enter room 31NR, which will be on your left;
(5) go through 31NR to a smaller room, which is 31NQ; (6) there are
six desks marked 1 through 6. |
| |
|
| Extended Office
Hours | Each of the four office hours listed above
will be extended half an hour (e.g., M 3:30-5 instead of M 3:30-4:30)
if there is a test or an assignment due during the week following the
office hour. Example: Suppose that an assignment is due at 10am on
Wednesday, September 23. Then every office hour between 10am on
Wednesday, September 16 and 10am on Wednesday, September 23 will be
extended by half an hour. |
| |
|
| Class Time |
MWF 10-11 |
| |
|
| Class Location |
CPE 2.210 |
| |
|
| Textbook |
The textbook for the course is Algorithm Design by Kleinberg
and Tardos (Addison-Wesley, 2006).
|
| |
|
| Course Outline |
The following major topics will be covered: analysis of
algorithms, graph algorithms, greedy algorithms, divide-and-conquer,
dynamic programming, network flow, NP-completeness, approximation
algorithms, randomized algorithms. See the schedule for a more detailed lecture plan.
|
| |
|
| Assignments |
There will be six assignments. Most of the assignments will have
two parts. The first part consists of exercises for each student to
solve and turn in separately. The second part, entitled "Programming
& Problem Solving", includes additional exercises and/or programming
tasks related to a particular computational problem that we will be
studying in greater depth. The second part may be done with a
partner, and you are encouraged to do so. |
| |
|
| Quizzes |
Many of the lectures will include a brief quiz based on material from
the previous lecture. The quizzes are open book/notes. As explained
in the section below entitled "Overall Raw Score", all of your low
quiz scores will be dropped in the computation of your course grade.
If you miss a quiz for any reason (legitimate or otherwise), your
score for that quiz will be a zero, so it will be dropped. |
| |
|
| Tests |
There will be three in-class tests. The tests will be closed book and
closed notes; you are only allowed to bring one page of notes (both
sides may be used). The first test will be held on Monday,
September 28 and will cover all of the course material up to
September 25. The second test will be held on Friday, October
30 and will cover all of the course material from September 30 to
October 28. The third test will be held on Friday, December 4
and will cover all of the course material from November 2 onward.
Please try to arrive in class a few minutes early on the test dates;
this will allow us to start the test right at the beginning of the
class period. |
| |
|
| Make-Up Tests |
Please note that no make-up tests will be given in this course. If a
student has a legitimate and properly documented excuse for missing
one of the tests, the missing test score will be estimated as the
average of the other two test scores. More complicated scenarios,
e.g., where a student misses two tests for legitimate reasons, will be
treated on a case-by-case basis. In the event of a non-excused
absence, a score of zero will be assigned. |
| |
|
| Overall Raw Score |
Each student's overall raw score, out of 100 points, will be
determined from performance on the six assignments, the quizzes, and
the three tests. Assignment 0 is worth 4 points, and Assignments 1
through 5 are each worth 8 points, for a total of 44 points. The
remainder of the raw score is determined as follows. Let x denote
your average score on the tests (expressed as a fraction, e.g., if you
have a 70% test average, then x is 0.7), let n denote the total number
of quizzes, let A denote the set of quizzes on which you scored higher
than your test average, let y denote your average score (again
expressed as a fraction) over the quizzes in set A, and let w denote
32 * |A| / n. Then your raw score out of 56 for the quizzes and tests
is (56 - w) * x + w * y. Example 1: Mary doesn't take any of the
quizzes, but she scores 100% on all three tests. Mary's raw score for
the quizzes and tests is 56 out of 56. Example 2: Joe enjoys a brief
quiz -- and aces all of them -- but, for unknown reasons, he refuses
to participate in any sort of "test". Joe's raw score for the quizzes
and tests is 32 out of 56. Example 3: Pat has a test average of 75%,
and gets better than 75% on 27 out of a total of 36 quizzes. The
average of Pat's top 27 quiz scores is 90%. Pat's raw score for the
quizzes and tests is (56 - 24) * 0.75 + 24 * 0.9 = 45.6 out of 56, or
81.43%. |
| |
|
| Letter Grades |
The mapping from overall raw scores to letter grades will depend
somewhat on the overall performance of the class. The nominal A/A-
cutoff is 90; A-/B is 85; B+/B is 80; B/B- is 75; B-/C+ is 70; C+/C is
65; C/C- is 60. These nominal cutoffs will not be increased; for
example, a student achieving a raw score of 90 is guaranteed to
receive an A in the course. However, these cutoffs might be lowered
if necessary in order to improve the grade distribution. |
| |
|
| Feedback |
Throughout the semester, please feel free to provide feedback to the
instructor regarding any aspect of the course. |
| |
|
| Academic Honesty |
See the following deparmental
document.
|