CompSci 260 - Fundamentals of the Design and Analysis of Algorithms - Fall, 2009 (Dillencourt)

This course will be offered again in the following quarter (Winter, 2010).

• Course Instructor:
  • Professor Michael Dillencourt
  • Email: dillenco at ics dot uci dot edu
  • Office Hours: Click here. I am also available after discussion section for questions.
  • Office: DBH 4086
• Class meetings:
  • Lecture: Tu Th, 3:30PM, DBH 1500
  • Discussion: TuTh 5-6:20PM (Immediately following the lecture, in the same room.)
  • The discussion section will be used for the following purposes.
    • Discussion of homework problems
    • Quizzes (see below). These may be given during the lecture, or during the discussion, or during the lecture and extending into the discussion. The approximate timing for any one particular quiz will be announced at least one class in advance.
    • Make-up lectures (see below).
    If you have a schedule conflict that prevents you from attending either the lectures or the discussions (or both), then you should NOT take the course this quarter.
    This course will be offered again during Winter Quarter 2010.
  • The first class meeting will be Thursday, September 24.
  • There will be no class on the following University holidays:
    • Thursday, November 26 (Thanksgiving)
  • Make-up lectures: I may occasionally cancel a lecture and compensate for this by holding a make-up lecture during the discussion section on another day. If I cancel a lecture, I will announce it in advance.
• Adding the class: Demand for the class appears likely to exceed the number of available slots in the class. WebReg lets students into the class until the class fills up, and then puts students on a waiting list which is a FIFO queue. The class is configured for Electronic Add/Drop (EAD). This means that after the quarter starts the waiting list is maintained by the WebReg system. If somebody drops the class during the first two weeks, the student at the front of the waiting list will be automatically added to the class. This has two consequences:
  1. I will not sign add cards, because EAD handles enrollment automatically.
  2. If you are on the waiting list and decide you do not want to take this course, it is your responsibility to remove yourself from the waiting list. If not, you run the risk that you will be enrolled in a class you do not wish to take.
  This course will also be offered Winter Quarter 2010, so if you are unable to enroll in the present offering you can still take it next quarter.
• Dropping the class: If are going to drop the class, you must do it during the first two weeks so that somebody else can add the class. Please note:
  1. You can drop the class electronically during the first two weeks, using the WebReg system.
  2. Once the first two weeks are past, you cannot drop the class electronically, and I will not sign drop cards. So if you are still enrolled in the class after two weeks you are in the class for the entire quarter.
  Summary: if you intend to drop the course, do it now.
• Grading (Revised October 27, 2009): The grading will be based on three quizzes and a final exam, according to the following formula:
  • Final exam: 50%
  • Quiz average: 50%
  I will compute your quiz average using two different weightings functions. Your average will be the maximum of the results of the two computations.
  • Weighting 1: All three quizzes weighted the same (1/3 each)
  • Weighting 2: Quiz 1 weighted 1/4, quiz 2 weighted 1/4, quiz 3 weighted 1/2
  Note that makeup quizzes will not be given. If you miss a quiz, I will assign you a grade on that quiz based on your score on the final exam. In principle, this means that quizzes are optional, but it is recommended that you take them all. Once I give you a copy of the quiz, taking it is no longer optional: if you don't turn it in, you will receive a score of zero.
• The schedule of quizzes and exams is as follows:
  • Quizzes (Revised October 27)
    • Quiz 1: Tuesday, October 6
    • Quiz 2: Tuesday, October 20
    • Quiz 3: Tuesday, November 17
  • Final Exam: Tuesday, December 8, 4:00 PM
• Homework problems
  • I will be assigning recommended homework problems. These problems extend and complement the material presented in the lectures and in the text. Although the homework will not be collected or graded, it is strongly recommended that you solve the problems. We will discuss the solutions to the problems in the discussion sections.
  • 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.
  This book, and some other algorithms books, will be placed on reserve in the science library.
• 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, in the form of transparencies 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]. Dynamic Programming, part 1. [KT Sections 6.1-6.3].
  • Week 7: Dynamic Programming, part 2. [KT Sections 6.4-6.9].
  • Week 8: Network Flow. [KT Sections 7.1-7.3].
  • Week 9: Linear programming [Notes to be provided]. NP-completeness, part 1. [KT Sections 8.1-8.2].
  • Week 10: NP-completeness, part 2. [KT Sections 8.3-8.5].