CompSci 260 - Fundamentals of the Design and Analysis of Algorithms - Winter, 2017 (Dillencourt)
Special office hour Monday March 20, 10:45-11:50 AM,
Note to students who have already taken this course and want to take the
CompSci 260 portion of the masters exam:
The CompSci 260 portion of the Comprehensive Masters Exam will be integrated
with the Final Exam.
- To read how this will work, click
You must sign up for this exam before the
The procedure for signing up is posted
Last modified: March 19, 2017
- Course Instructor:
- Professor Michael Dillencourt
- Email: dillenco at ics dot uci dot edu.
Please see note on email, below.
- Office Hours: Click here.
I am also available after class for questions.
- Office: DBH 4086
- Mr. Jia Chen
- Email: jiac5 at uci dot edu
- Office hours and location: TBA
- Class meetings:
- Lecture: Tu Th 3:30-4:50 PM, in MSTB 118
- Discussion: T 5:00-5:50 PM, in PSCB 120
- Generally, the class will meet for about 80 minutes and there will be
no organized discussion section afterwards.
On these occasions, the discussion section will function as an office hour.
- On occasion we may use the full discussion section.
Examples of when this may occur are:
- We may use the discussion section for discussion of the homework,
or for the return and discussion of graded quizzes or midterms.
- On pre-announced occasions, I may give a longer lecture. When this
happens we will break after the scheduled lecture and move to the discussion
- I will assume that all students in the class do not have conflicts with the
TuTh 3:30-6:00 time.
If you have scheduling conflicts that make it impossible to attend class
regularly, you should not take this course this quarter.
Any request that special allowances be made because you are unable to attend
class regularly will not receive a sympathetic response.
- Final Exam:
- The Final Exam will be held Tuesday, March 21 at 4:00 PM
in MSTB 118.
- Midterm Exams:
- There will be two midterm exams, to be held on the following dates:
- Midterm 1: Thursday, February 9
- Midterm 2: Thursday, March 9
- The midterm exams will be given in lecture.
They will last 80 minutes.
- No make up midterm exams will be given,
no matter how valid your reason for missing it.
Instead, I will assign a grade based on how you do on the final exam.
So if you miss a midterm exam, plan to do really well on the final exam.
- Drop/Add Policy
- For the first two weeks of the quarter,
all adds and drops will be handled automatically through the
Registrar's WebReg system.
- When the two-week period expires:
- All students on the wait list will be automatically added to the class
- From that point on, drops will not be allowed. (Exceptions will only
be allowed in truly extaordinary circumstances preapproved by the
Associate Dean for Graduate Studies on a case-by-case basis).
- The grading will be based on the homework,
the two midterm exams, and the final exam, according to the following weights:
- Homework: 5%
- Midterm 1: 24%
- Midterm 2: 24%
- Final exam: 47%
- The policy for assigning grades will be as follows:
- Excellent or superior performance in the course will result in an A or
- Adequate performance in the course will result in a B+ or B grade.
- Poor performance in the course may result in a grade of C or lower.
- The standard for passing the CompSci 260 portion of the Masters Exam
will be performing at an excellent or superior level (i.e., A- or better)
on the final exam.
- Under certain circumstances, upon request, I may give a grade of
S or U (Satisfactory of Unsatisfactory) rather than a letter grade.
Such a grade will be assigned only if you request it and
I approve your request.
I will only approve such a request if you have not already taken this class
in a previous offering.
If you think you might want be assigned an S/U grade instead of a letter
grade, you should talk to me.
- Homework problems: Recommended homework assignments will be
posted weekly. Starting with the second homework assignment,
a few of the problems will be collected and graded by the reader.
Click here for the homework assignments
- Course textbook:
The course will cover the first eight chapters of this book, along with a
small number of supplementary readings.
- Kleinberg and Tardos, Algorithm Design, Addison Wesley, 2006.
- Note on Email:
If you send me email about the course, please do the following
(The reason for the first request is self-explanatory. The second and the
third are because I occasionally get email from non-UCI-students asking for
help on problems, and I want to weed them out.)
Please include the string "CompSci 260:" at the start of the subject line
(to ensure that it gets
past my spam filter).
Please include your name and student number in the message.
If you are not writing me from your official UCI email address, please
cc your official UCI email address.
- Course announcements will be sent via email to all students enrolled
in the class.
- If for some reason you are not receiving these announcements, you can
view the archive by
- For the first two weeks or so,
until enrollments and the class mailing list stabilize,
I will also post course announcements here.
- Course notes:
- Course notes, in the form of slides used for the lectures,
will be available on line. Note that you are responsible for all material
covered in lecture, discussion, and the relevant portions of the textbook,
even if it does not appear in the lecture notes.
- Click here for course notes
(registered students only).
- List of topics. The following schedule is approximate and may
change over the course of the quarter.
- Week 1:
Introduction. The Stable marriage problem. [KT Chapter 1].
- Week 2:
Basics of Algorithm Analysis. [KT Chapter 2].
- Week 3:
Basics of Graph Algorithms. [KT Chapter 3].
- Week 4:
Greedy Algorithms. Shortest Paths. Minimum Spanning Trees. [KT Chapter 4].
- Week 5:
Divide and Conquer, part 1. [KT Sections 5.1-5.5].
- Week 6:
Divide and Conquer, part 2. [KT Sections 5.5, 13.5].
- Week 7:
Dynamic Programming, part 1. [KT Sections 6.1-6.3].
- Week 8:
Dynamic Programming, part 2. [KT Sections 6.4-6.9].
- Week 9:
Network Flow. [KT Sections 7.1-7.3].
- Week 10:
NP-completeness, part 1. [KT Sections 8.1-8.2].
NP-completeness, part 2. [KT Sections 8.3-8.5].