CompSci 161 - Design and Analysis of Algorithms - Spring, 2008 (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
  • MWF 3:00-3:50 PM, ICS 174 (Prof. Dillencourt)
• Discussion Sections:
  • MW 2:00-2:50PM, PSCB 120 (Mr. Lu)
  • MW 4:00-4:50PM, DBH 1500 (Mr. Lu)

Instructor

• Professor Michael Dillencourt
  Office: DBH 4086
  Office hours: MW 5-6PM
  Email: dillenco@ics.uci.edu, but see note on email below

Teaching Assistant

• Mr. Yiming Lu, ymingl@uci.edu.
  Office hours: Tu 3:00-5:00 PM, ICS 406B

Reader

• Ms. Vesna Memisevic vmemisev@uci.edu.
  Office hours (for discussion of specific homework grading issues only): TuTh 2:00-2:50PM DBH 4082

Email for questions

• All email with questions about course material should be sent to the following email address: compsci161-questions@ics.uci.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/CSE23 and ICS 51 or CSE31/EECS31 with grades of C or better;
• ICS 6D/Mathematics 6D;
• ICS 6B/Mathematics 6B;
• Mathematics 6G or 3A;
• Mathematics 2B;
• satisfactory completion of the lower division writing requirement.

• 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:
  • 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. Note that our current plans are to offer CompSci 161 in every quarter, including the summer.
    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:
  • The current drop policy has been discussed in class. Send me email if you have questions about it.

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. This component of the grade will be based on:
  • Homework (7 assignments, the lowest homework score will be dropped.)
• 44% - Midterms: 2 midterms, to be given in lecture:
  • Midterm 1: Friday April 25, 3:00-3:50PM (during regularly scheduled lecture.)
  • Midterm 2: Friday May 23, 3:00-3:50PM (during regularly scheduled lecture.)
• 46% - Final exam: Monday June 9, 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 to the distribution center 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 in the ICS Distribution Center.

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. Click here to see who is the grader for each homework assignment.
• 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.

Makeup Exam Policy

1. For unforeseeable emergency circumstances, such as a medical emergency, documentation will be required.
2. An absence from an exam due to a foreseeable circumstance must be approved in advance. (See note 3)
   • Note that a work conflict is NOT a valid reason: the examination times are announced at the beginning of the quarter, so there is plenty of time to plan your work schedule.
3. If you wait until after the exam to get a foreseeable excuse approved, and it is not approved, you will receive a grade of zero (0) on the exam.
4. If I accept your reason for missing an exam, at my option I may either (1) give you a makeup exam or (2) assign your grade on the basis of the remaining course work that you did not miss.
5. If I do give a makeup exam, I may give it less weight than announced on the course web page.

Schedule of Midterms, Final, and Homework due dates

• The two midterms will be Friday April 25 and Friday May 23, and will take the entire lecture period (3:00-3:50 PM).
• The Final Exam will be Monday, June 12 and will take two hours (4:00-6:00 PM)
• The schedule for the quarter is shown in the following table.

Homework Assignments

• All homework assignments are due at the date and time indicated, in the ICS Distribution Center. Homework deadlines are firm. Late homework will not be accepted.
• While you are strongly encouraged to do your own work, you may collaborate with others. If you collaborate with others:
  1. Please indicate on your assignment with whom you have collaborated. It will not affect your grade on the assigment.
  2. Turn in your homework in your own handwriting (i.e., do not simply photocopy someone else's work and cross out their name.)
• 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 10% 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

• Introduction; mathematical review; asymptotic notation.
• Basic data structures
• Sorting and Selection
• Greedy algorithms
• Divide and Conquer
• Dynamic Programming
• Graph algorithms
• Text processing/string matching
• Computational Geometry
• NP-completeness