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

• Course Instructor:
  • Professor Michael Dillencourt
  • Email: dillenco@ics.uci.edu
  • Office Hours: Click here. I am also available after discussion section for questions.
  • Office: DBH 4086
• The class meeting times are:
  • Lecture: Tu Th, 3:30PM, ICS 223
  • Discussion: Immediately following the lecture, in the same room.
• Adding the class: Demand for the class may be higher than 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 2009, so if you are unable to enroll in the present offering you can still take it next quarter.
• The grading will be based on a final exam and some combination of quizzes, graded homework, and and/or a midterm exam. The exact formula will depend on class enrollment and whether we are assigned a reader for the course. It will be announced the first week of class.
• The schedule of exams is as follows:
  • Midterms, quizzes: TBA
  • Final Exam: Tuesday, December 9, 4:00 PM
• Homework 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].