CompSci 260 - Fundamentals of the Design and Analysis of Algorithms - Winter, 2020 (Dillencourt)
Course Announcements: Click here.
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
here.
-
You must sign up for this exam before the
signup deadline.
The procedure for signing up is posted
here.
Course Information:
- Course Instructor:
- Professor Michael Dillencourt
- Email: dillenco at ics dot uci dot edu.
Please see note on email, below.
- Office Hours:
- M 1:15-2PM.
- Friday, March 13: 2:15-3:30PM
I am also available after class for questions.
- Office: DBH 4086
- TA:
- Ms. Disi Ji
- Email: disij at uci dot edu.
- Office hours: by appointment
- Class meetings:
- Lecture: M W 3:30-4:50PM, in ICS 174
- Discussion:
- M W 5:00-5:50PM, in ICS 174
- No lecture or discussion on the following University holidays:
- Monday, January 20 (Martin Luther King, Jr. Day)
- Monday, February 27 (Presidents' Day)
- Purpose of discussion session
- 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.
- The two midterm exams will run from 3:30 to 5:50, using the
time for both the lecture and discussion sections
- Make sure that you can attend class during the period from
5:00-6:00 M W, even though we will not always have class
them.
- Final Exam:
- Midterm Exams:
- There will be two midterm exams, given on the following days.
The exams will be given in the lecture/discussion room.
While you may not need all the time, you should plan on staying through
the scheduled end of the discussion section on those days.
- 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).
- Grading:
- 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
A-.
- 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.
A few problems will be collected and graded.
Click here for the homework assignments
- Course textbook:
- Kleinberg and Tardos, Algorithm Design, Addison Wesley, 2006.
The course will cover the first eight chapters of this book, along with a
small number of supplementary readings.
- Note on Email:
If you send me email about the course, please do the following
-
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.
(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.)
- 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
clicking 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 Matching 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].
Last modified: March 19, 2020