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

Note to students who have already taken this course and want to take the CompSci 260 portion of the masters exam: In accordance with new rules effective Fall 2011, the CompSci 260 portion of the 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 end of the second week of classes. The mechanism and exact deadline for signing up will be posted here when it is finalized.

Course Information:

• 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, 5:15PM, ICS 174. (Note that this is 15 later than the nominal start time listed in the Schedule of Classes)
  • Discussion: (Immediately following the lecture in the same room)
  • The first class meeting will be Thursday, September 22.
  • There will be no class on the following University holiday:
    • Thursday, November 24 (Thanksgiving)
  • Note: You are required to enroll in the discussion section as well as the lecture.
    
    Generally, the plan will be 80 minutes of lecture followed by a short break and then the discussion section. But this is only a general plan. On occasion the lecture may be longer than usual. On occasion I may give an additional lecture during the discussion period, either to make up for a missed lecture or to ensure that we cover the entire course syllabus. Quizzes may be given during either the lecture or the discussion section.
    
    If you have scheduling conflicts that make it impossible to attend either the lecture of the discusion, you should not take this course this quarter. Any request that special allowances be made because you are unable to attend the regularly scheduled lecture or discussion sections will not receive a sympathetic response.
• Final Exam:
  • The final exam will be held Thursday, December 8 at 4:00PM.
  • In accordance with new department policy established in 2011, the 260 portion of the Masters Exam will be integrated with the course examination structure. Exact details of how this this will be implemented will beposted here.
• Quizzes: There will be two in-class quizzes:
  • Thursday, October 20, 5:15-8PM
  • Thursday, November 17, 5:15-8PM. Click here for information on regrade requests for Quiz 2.
• Drop/Add Policy If you are considering adding or dropping, please carefully read the following items.
  • For the first two weeks of the quarter, all adds and drops will be handled automatically through the Registrar's WebReg system.
  • After the second week of classes, adds and drops will only be allowed in extraordinary circumstances, and they must be approved by the Associate Dean for Graduate Studies.
  • This course will also be offered Winter Quarter 2012, so if you are unable to enroll in the present offering you can still take it next quarter.
• Grading: The grading will be based on two quizzes and a final exam, at the dates and time announced above. The grade will be computed as follows:
  • Quizzes, 50% (25% each)
  • Final exam, 50%
• 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, along with some other algorithms books, has been 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].