CompSci 260 - Fundamentals of the Design and Analysis of Algorithms - Winter, 2018 (Dillencourt)
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: Fevruary 23, 2018
- 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
- Ms. Nailah Alhassoun
- Email: nailah at uci dot edu.
- Office hours: by appointment
- Class meetings:
- Lecture: Tu Th 3:30-4:50 PM, in MSTB 118
- Tu 5:00-5:50 PM, in MSTB 120
- Th 5:00-5:50 PM, in MSTB 118
- No lecture or discussion on Tuesday, January 16
- On Thursday January 11 and Thursday January 18, I will continue the
lecture in the discussion section to make up for the cancelled
class on January 16
- Discussion section is for discussion of homework, exams, etc.
- If nothing is planned I will use it as an extended office hour to
answer questions. However, if nobody is there, I will leave rather than
staying until the end.
- Note that the discussion section meets in a different room from the
lecture on Tuesdays.
On Thursdays, it is the same room as the lecture.
- Make sure that you can attend class during the period from
5:00-6:00 Tu Th, even though we will not always have class
- Final Exam:
- The Final Exam will be held Tuesday, March 20 at 4:00 PM.
The location will most likely be the same as the lecture room.
If this is not the case I will let you know well in advance.
- Midterm Exams:
- There will be two midterm exams, given on the following days.
The exams will be given in the lecture/discussion room (they are the same
While you may not need all the time, you should plan on staying through
the scheduled end of the discussion section on those days.
- Midterm 1: Thursday, February 8
- Midterm 2: Thursday, March 8
- 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
Starting week 3, a few problems will be collected and graded.
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
- 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].