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:
  • The in-class Final Exam has been cancelled because of the University response to the COVID-19 situation. The updated policy was announced at the start of class on March 11. Slides that accompanied the announcement, Information on final exam option.
• 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.
    • Midterm 1: Wednesday, February 5. List of topics (updated February 3). Instructions (Read them before the exam).
    • Midterm 2: Wednesday, March 4. List of topics (updated March 2). Instructions (Read them before the exam).
  • 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
  1. Please include the string "CompSci 260:" at the start of the subject line (to ensure that it gets past my spam filter).
  2. Please include your name and student number in the message.
  3. 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].