ICS 161, Spring 2005:
Design and Analysis of Algorithms
General Course Information
- Coursework. Coursework will consist of weekly homeworks,
two midterms, and a comprehensive final exam. The overall grade
will be determined 10% from homework, 25% from each midterm, and
40% from the final. However, you must pass the final exam in order to pass
the class.
Group work on homeworks is permitted; each
student should turn in his or her own copy of the homeworks.
Homeworks will usually be assigned in lecture on Fridays and due
at the ICS distribution center on the following Friday (by
whenever the distribution center closes that day).
Late homework assignments will not be accepted.
Homeworks will not be graded due to the limited grading resources
available in ICS at this time; instead, you will receive a score based
only on the number of homeworks turned in.
Homework submissions that do not appear to be serious attempts at
solving the assigned problems will not be counted.
Exams will be graded normally, however.
Students are strongly encouraged to do all homeworks;
our experience is that failure to do homeworks has been
strongly correlated with failure to pass this class.
- Exam policy.
Several students have been caught cheating in recent offerings of 161,
most often due to similarity of their answers.
In addition to the procedures of the
ICS
Cheating Policy, students caught cheating on exams will be given a
failing grade in the class.
In addition, students will not be allowed to get up and leave during the
last ten minutes of each exam; instead, they must remain quietly in
their seats until all exams have been collected.
- Text. The course text will be "Algorithm Design" by
Goodrich and Tamassia. Students are expected to own a copy and
to read the relevant chapters and sections. The homework problems
will be assigned from this text.
- Course times. The course meets Mondays, Wednesdays, and Fridays,
3:00 - 3:50 in IERF 101.
There are three discussion sections, each of
which will meet once a week for fifty minutes,
on Wednesdays at 4:00, 5:00, and 6:00.
All students
should be enrolled both in the lecture and in one of the discussion
sections. Attendance at the discussion section is not mandatory, but
is strongly encouraged. At the discussion sections, teaching assistants
will go over homework and midterm solutions, give additional examples of
topics covered in the lecture, and be available to answer questions.
- Instructors and office hours. The course will be taught
by David Eppstein (office hours: MW 4-5, Thu 2-3).
We also have two TAs: Nodari Sitchinava (office hours TTh 11-12 in the
ICS trailers, room 127A) and Michael Nelson (office
hours Tues 2-3 and Fri 9-10 in CS 458F)
and one reader (wangn@uci.edu).
- Bulletin board.
The ics.161 bulletin board
is available for course news and announcements.
If you have a question about the course that you feel would
be of general interest or wish to post anonymously, ics.161 is also
appropriate for that.
- Drop policy.
All drop requests should be
performed by giving Prof. Eppstein a completely filled-in drop card,
at office hours or by appointment. Drop cards will not be
signed or accepted at the lecture.
Drops will only be accepted during the first two weeks of class.
Once your drop card has been signed, further coursework from you will
not be graded.
- Add policy.
All students who wish to add must give
Prof. Eppstein a filled-in add card by Friday,
April 8, at office hours or by appointment.
Add cards will not be
signed or accepted at the lecture.
I will then verify your eligibility
for the course with the ICS student affairs office, and as space and
teaching assistance availability
permits will announce availability of signed add cards on the ics.161
bulletin board.
Add requests will be prioritized in the following order: (1) students who
were incorrectly dropped because of faulty prerequisite checks, (2) ICS
or CE students who will be able to graduate this quarter if they pass
161, and who have not taken the class previously, and (3) ICS or CE
students who will be able
to graduate this quarter if they pass 161, and have previously taken but
not passed the course. Adds will only be accepted for
students meeting the course prerequisites.
If you intend to add, you should turn in all homework assignments
as they are due; I expect to complete all adds prior to the first
midterm.
Tentative Schedule
- Apr. 4: Intro/review [Goodrich & Tamassia, chapter 1]
- Apr. 6-8: Comparison sorting [2.4,4.1,4.3]
Homework due Friday, April 15: R-1.7, R-4.4, R-4.5, R-4.9, C-4.10
- Apr. 11-13-15: Integer sorting & selection; lower bounds [4.4-4.7]
Homework due Friday, April 22: R-4.14, R-4.16, R-4.17, R-4.18
- Apr. 18-20: Divide and conquer, master theorem, integer arithmetic,
primality testing
[5.2,10.1]
- Apr. 22: FIRST MIDTERM
- Apr. 25-27-29: Dynamic programming [5.3]
Homework due May 6: R-5.9, R-5.11, R-5.12, C-5.10
- May 2-4-6: Graph representation, traversal, ordering [6]
Homework due Friday, May 13: R-6.4, R-6.6, R-6.7, R-6.10
- May 9-11: Shortest paths 7.1,7.2
- May 13-16: Minimum spanning trees [7.3]
Homework due Friday, May 20: R-7.1, C-7.2, C-7.3
- May 18-20-23-25: String algorithms [9]
Homework due Friday, May 27: R-7.8, R-7.9, R-9.1, R-9.4
- May 30: Memorial day holiday
- May 27: SECOND MIDTERM
- Jun. 1-3: Computational Geometry [12]
Homework due Friday, June 10: C-12.11, C-12.15, C-12.18
- Jun 6-8-10: NP-completeness and approximation [13]
Wiki
Some of the students enrolled in this offering of ICS 161 have set up an
ICS 161 Wiki
containing course notes, homework assignments, wikipedia links, and
other useful information. It's not official course material but you may
find it useful, and I'm sure additional help making the course notes
accurate would be appreciated.
Other Course-Related Information
The following material is from previous years' offerings of ICS 161.
These offerings were based on different texts
(Baase and Cormen-Leiserson-Rivest), and covered a somewhat
different range of topics. You may find this material useful, but it is not
required reading.
David Eppstein, Information
& Computer Science, UC
Irvine, 5 Jan 2001.