ICS 161, Spring 2005:
Design and Analysis of Algorithms

General Course Information

• Coursework. Coursework will consist of weekly homeworks, two midterms, and a comprehensive final exam. The overall grade will be determined 10% from homework, 25% from each midterm, and 40% from the final. However, you must pass the final exam in order to pass the class. Group work on homeworks is permitted; each student should turn in his or her own copy of the homeworks. Homeworks will usually be assigned in lecture on Fridays and due at the ICS distribution center on the following Friday (by whenever the distribution center closes that day). Late homework assignments will not be accepted. Homeworks will not be graded due to the limited grading resources available in ICS at this time; instead, you will receive a score based only on the number of homeworks turned in. Homework submissions that do not appear to be serious attempts at solving the assigned problems will not be counted. Exams will be graded normally, however. Students are strongly encouraged to do all homeworks; our experience is that failure to do homeworks has been strongly correlated with failure to pass this class.
  
  
• Exam policy. Several students have been caught cheating in recent offerings of 161, most often due to similarity of their answers. In addition to the procedures of the ICS Cheating Policy, students caught cheating on exams will be given a failing grade in the class. In addition, students will not be allowed to get up and leave during the last ten minutes of each exam; instead, they must remain quietly in their seats until all exams have been collected.
  
  
• Text. The course text will be "Algorithm Design" by Goodrich and Tamassia. Students are expected to own a copy and to read the relevant chapters and sections. The homework problems will be assigned from this text.
  
  
• Course times. The course meets Mondays, Wednesdays, and Fridays, 3:00 - 3:50 in IERF 101. There are three discussion sections, each of which will meet once a week for fifty minutes, on Wednesdays at 4:00, 5:00, and 6:00. All students should be enrolled both in the lecture and in one of the discussion sections. Attendance at the discussion section is not mandatory, but is strongly encouraged. At the discussion sections, teaching assistants will go over homework and midterm solutions, give additional examples of topics covered in the lecture, and be available to answer questions.
  
  
• Instructors and office hours. The course will be taught by David Eppstein (office hours: MW 4-5, Thu 2-3). We also have two TAs: Nodari Sitchinava (office hours TTh 11-12 in the ICS trailers, room 127A) and Michael Nelson (office hours Tues 2-3 and Fri 9-10 in CS 458F) and one reader (wangn@uci.edu).
  
  
• Bulletin board. The ics.161 bulletin board is available for course news and announcements. If you have a question about the course that you feel would be of general interest or wish to post anonymously, ics.161 is also appropriate for that.
  
  
• Drop policy. All drop requests should be performed by giving Prof. Eppstein a completely filled-in drop card, at office hours or by appointment. Drop cards will not be signed or accepted at the lecture. Drops will only be accepted during the first two weeks of class. Once your drop card has been signed, further coursework from you will not be graded.
  
  
• Add policy. All students who wish to add must give Prof. Eppstein a filled-in add card by Friday, April 8, at office hours or by appointment. Add cards will not be signed or accepted at the lecture. I will then verify your eligibility for the course with the ICS student affairs office, and as space and teaching assistance availability permits will announce availability of signed add cards on the ics.161 bulletin board. Add requests will be prioritized in the following order: (1) students who were incorrectly dropped because of faulty prerequisite checks, (2) ICS or CE students who will be able to graduate this quarter if they pass 161, and who have not taken the class previously, and (3) ICS or CE students who will be able to graduate this quarter if they pass 161, and have previously taken but not passed the course. Adds will only be accepted for students meeting the course prerequisites. If you intend to add, you should turn in all homework assignments as they are due; I expect to complete all adds prior to the first midterm.
  
  

Tentative Schedule

• Apr. 4: Intro/review [Goodrich & Tamassia, chapter 1]
• Apr. 6-8: Comparison sorting [2.4,4.1,4.3]
  Homework due Friday, April 15: R-1.7, R-4.4, R-4.5, R-4.9, C-4.10
• Apr. 11-13-15: Integer sorting & selection; lower bounds [4.4-4.7]
  Homework due Friday, April 22: R-4.14, R-4.16, R-4.17, R-4.18
• Apr. 18-20: Divide and conquer, master theorem, integer arithmetic, primality testing [5.2,10.1]
• Apr. 22: FIRST MIDTERM
• Apr. 25-27-29: Dynamic programming [5.3]
  Homework due May 6: R-5.9, R-5.11, R-5.12, C-5.10
• May 2-4-6: Graph representation, traversal, ordering [6]
  Homework due Friday, May 13: R-6.4, R-6.6, R-6.7, R-6.10
• May 9-11: Shortest paths 7.1,7.2
• May 13-16: Minimum spanning trees [7.3]
  Homework due Friday, May 20: R-7.1, C-7.2, C-7.3
• May 18-20-23-25: String algorithms [9]
  Homework due Friday, May 27: R-7.8, R-7.9, R-9.1, R-9.4
• May 30: Memorial day holiday
• May 27: SECOND MIDTERM
• Jun. 1-3: Computational Geometry [12]
  Homework due Friday, June 10: C-12.11, C-12.15, C-12.18
• Jun 6-8-10: NP-completeness and approximation [13]

Wiki

Other Course-Related Information

• Lecture notes from Winter 1996
• Sample exams from Winter 1998
• Python implementations of various algorithms, more Python algorithm implementations, and still more Python algorithms.