CompSci 161 - Design and Analysis of Algorithms - Fall, 2009 (Dillencourt)

Contents

• Class meetings
• Instructor
• Teaching Assistant/Reader
• Email for questions
• Course Announcements
• Course Prerequisites
• Drops/Adds
• Course Books
• Grading
• Picking up Graded Assignments
• Regrade policy
• Makeup Exam policy
• Schedule of Midterms, Final, and Homework due dates
• Homework Assignments
• Academic Dishonesty (cheating)
• Course notes
• Additional material covered in class
• List of Topics and Reading Assignments

Class meetings

• Lecture: MW 3:00-4:20PM SSL 228 (Prof. Dillencourt)
• Discussion Sections:
  • Section 1: M 4:30-5:20PM SSL 228 (Mr. Simons)
  • Section 2: W 4:30-5:20PM SSL 228 (Mr. Simons)

Instructor

• Professor Michael Dillencourt
  Email: dillenco at ics dot uci dot edu, but but see email for questions below
  Office: DBH 4086
  Office hours: click here

Teaching Assistant

• Joe Simons
  Email: jsimons at uci dot edu
  Office: ICS 406B
  Office hours: M 10-10:50, F 10-10:50

Reader

• Marco Cesarano
  Email: mcesaran at uci dot edu
  Office hours (for discussion of specific homework grading issues only): TBA

Email for questions

• All email with questions about course material should be sent to the following email address: compsci161-questions at ics dot uci dot edu. This is an alias for the instructor, the TA, and the reader, and ensures that we all see your message and the response. It also gives you better turnaround time. Also, please include the string "CompSci 161:" at the beginning of the subject line, and include your name and student number in the message.

Course Announcements

• Course announcements will be sent via email to all students enrolled in the class.
• Click here for the archive of these messages.

Course prerequisites

• ICS 23 or ICS H23 or CSE 23, with a grade of C or better;
• ICS 51 or CSE 31 or EECS 31, with grade of C or better;
• ICS 6D or Mathematics 6D;
• ICS 6B or Mathematics 6B;
• Mathematics 6G or 3A;
• Mathematics 2B.

• The School WILL DROP students from courses for which they have not satisfied the prerequisites. If you find you have been dropped from a course, please check the prerequisite list at http://www.ics.uci.edu/ugrad/current/degrees and contact the ICS Student Affairs Office at http://www.ics.uci.edu/ugrad/current/index.php BEFORE enrolling in the course again. However, meeting the prerequisites does not guarantee a space in the class.

Drops/Adds

• The course is set for EAD (Electronic Add Drop). This means that 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 NOT BE ALLOWED, with possible exceptions made for extraordinary and unforeseeable circumstances.
• Adds/Missing Prerequisites:
  • If you are not allowed to enroll, or are dropped from the course, because you are missing a prerequisite, there are two possible causes.
    1. If you are indeed missing the prerequisites, please do not ask me to sign your add card. (If you ask, I will say no.) Instead, take the courses you need to satisfy the prerequisite requirement, and enroll in the course in a subsequent quarter, after you have satisfied the prerequisite requirement.
    2. If an error was made (i.e., if you really have satisfied the prerequisite), contact the ICS Student Affairs Office (SAO). If they have informed me that you have indeed satisfied the prerequisite, I will sign your add card during the third week of classes. This should be done early, as the prerequisite verification process may take some time.
• Drops:
  • I intend to follow the ICS policy, which is to allow drops only during the first two weeks, with possible exceptions made for extraordinary and unforeseeable circumstances.

Course Books

• [GT] Goodrich and Tamassia, Algorithm design : foundations, analysis, and Internet examples, Wiley, 2002. Online errata page .

• [BvG] Baase and van Geldin, Computer Algorithms, 3rd edition, Addison-Wesley, 2000.
• [CLRS] Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 2nd edition, MIT Press, 2001. Online errata page .
• [KT] Kleinberg and Tardos, Algorithm design, Pearson/Addison-Wesley, 2006.

Grading

• 10% - Homework/Quiz grade. This component of the grade will be based on:
  • Homework (6 assignments, the lowest homework score will be dropped.)
  • Possible unannounced quizzes to be given in lecture.
• 45% - Midterms: 2 midterms, to be given in lecture:
  • Midterm 1: Monday October 26, 3:00-4:20PM (during regularly scheduled lecture.)
  • Midterm 2: Monday November 23, 3:00-4:20PM (during regularly scheduled lecture.)
• 45% - Final exam: Monday December 7, 4:00-6:00PM.

• If you believe a homework assignment or an exam was graded incorrectly, you may request a regrade as described under Regrade policy below.
• At various times during the quarter a tentative scale and tentative grades will be announced. These are intended to give you an idea of how you are doing in the course. The tentative grades are generally straight letter grades. "Plus" and "minus" grades will be used for the final grades.
• Scale cutoffs are interpreted as rational numbers rather than integers. For example, if your course average is 82.8 and the cutoff for the next higher grade is 83, you would receive the lower grade, since 82.8 is less than 83.0. In other words, your course average is not "rounded up to the next highest integer" or "rounded to the nearest integer."
• On rare occasions, students who have received a grade of zero on a homework assigment (because we never received it) report that they turned it in and "it must have been lost." We have no way of verifying such claims. Our policy of dropping one assignment ensures that no student is penalized if this happens, provided the student has turned in all homework assignments.

Picking up Graded Assignments

• Graded assignments can be picked up from the TA. The best time and place for doing this is the discussion section.

Regrade Policy

• If you believe that a homework assignment has been graded incorrectly, please contact the grader directly. Please do this within 1 week after the graded asignments are made available in the distribution center. Regrade requests made after this may be rejected. Generally, homework assignments will be graded by the Reader. Exceptions will be noted and posted.
• If you believe that a midterm exam has been graded incorrectly, submit a regrade request as described in the course regrade policy for the midterm exams. Be sure to follow the guidelines and to turn your request in on time.

Missed Exam Policy

• The following policy applies for this offering of the course:
  • If you miss a midterm exam, you will be given a grade on the midterm based on your performance on the final exam. The exact mechanism for assigning this grade was discussed in class.
• Because of the above policy, no makeup exams will be given.
• In essence, this means that midterms are optional. However, it is strongly recommended that you take the midterms. If you miss the midterms and perform poorly on the final, then you will receive a poor grade in the course.
• NOTE: a midterm is optional only if you do not receive a copy it, which means either you either do not attend class that day or you elect to leave the classroom before midterms are handed out. Once a copy of the midterm has been handed to you, you will receive a grade on it. If you turn it in blank, this grade will be zero.

Schedule of Midterms, Final, and Homework due dates

• The following table shows the dates of all exams and the due dates for the homework assignments.
• The homework assignment due dates are subject to change, but the exam dates are fixed.

Homework Assignments

• All homework assignments are due in class at the start of lecture (3PM) on the due date. The deadline is firm.
• Late homework will be accepted only on the due date and according to the following sliding scale:
  • Homework turned in after the start of the lecture, but before the start of the 4:30PM discussion, will be penalized 25%.
  • Homework turned after the start of the 4:30PM discussion but before it ends, will be penalized 50%.
  • No homework will be accepted after the conclusion of the 4:30PM discussion section.
• Homework turned in in some other manner (e.g., pushed under my office door or placed in my mailbox) will be deemed to have been turned in at the time when I encounter it.
• While you are strongly encouraged to do your own work, you may collaborate with others. If you collaborate with others:
  1. Indicate on your assignment with whom you have collaborated. Doing so will not adversely affect your grade on the assigment. (However, if you collaborate and do not indicate on your assignment that you have collaborated with someone, this may affect your grade adversely; see note 3, below)
  2. Turn in your homework in your own handwriting (or, if you type it, type it in yourself) and in your own words. If you follow this rule, then it is highly improbable that you and your collaborator would word every solution in exactly the same way.
  3. If you collaborate with others and do not follow the above rules, then you may received a reduced score, pehaps as low as 0, on the homework.
• Note that this policy of allowing collaboration on the homework is a departure from the normal, stricter rules in many ICS courses.
• It is the experience of the instructor that students who do the homework by themselves get more out of the course and tend to do better on the exams. Keep in mind that the homework is only a small portion of the course grade.
• Click here for the homework assignments

Academic Dishonesty

• Copying from others during an examination, communicating exam answers with other students during an examination, or using unauthorized materials during an examination.
• Allowing another student to copy off your work during an examination.
• Tampering with an examination after it has been corrected, then returning it for more credit.
• Forging add/drop/change cards and other enrollment documents, or altering such a document after signatures have been obtained.
• Intentionally disrupting the educational process in any way.

Course Notes

• Copies of course notes will be made available. The mechanism for distributing the notes will be discussed in class.
• The notes consist primarily of copies of the transparencies used in class.
• Click here for more information.

Additional material covered in class

• Links to additional material covered in class will be added here as appropriate.

List of Topics and Reading Assignments

• Week 1: Introduction; mathematical review; asymptotic notation.
  • Required reading: [GT] chapter 1
  • Additional reading: [CLRS] chapters 1,2,3
• Weeks 2-3: Basic data structures; sorting
  • Required reading: [GT] 2.1-2.4; 4.1; 4.3-4.6
  • Additional reading: [CLRS] chapters 6,7,8
• Weeks 4: Greedy Algorithms; Divide and Conquer algorithms
  • Required reading: [GT] 5.1-5.2
  • Additional reading: [CLRS] Chapter 16; Section 4.3; Section 28.2
• Week 5: Midterm 1; Selection Problems, Lower bound proofs
  • Required reading: [GT] 4.7
  • Additional reading: [CLRS] Chapter 9; [BvG] Chapter 3
• Weeks 6-7: Graphs algorithms
  • Required reading: [GT] 6.1-6.3; 6.4.1; 6.4.4; 7.1; 7.3; 4.2
  • Additional reading: [CLRS] 22.1;23; 24.3; 21
• Weeks 7-8: Computational geometry; String/text processing
  • Required reading: [GT] 12; 9.1; 9.2
• Weeks 9-10: Midterm 2; Dynamic Programming
  • Required reading: [GT] 5.3; 6.4.2; 7.2
  • Additional reading: [CLRS] Chapter 15; [KT] Chapter 6