CompSci/CSE 161 - Design and Analysis of Algorithms - Fall, 2012 (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
• Missed 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 2:00-2:50PM ICS 174 (Prof. Dillencourt)
• Discussion Section: MW 4:00-4:50PM ICS 174 (Mr. Flynn)
• First class meeting: Monday, January 9 (lecture and discussion)

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

• Mr. Patrick Flynn
  Email: pflynn at ics dot uci dot edu but see email for questions below
  Office Hrs: Tu 2:00-2:50PM, Th 12:00-12:50PM
  Office Location: ICS 464E. (Note: this is the same building where the class meets.)

Reader

• Mr. Quan Nguyen
  Email: quann1 at uci dot edu
  Office hours: by appointment, to discuss assignments/exam problems he has graded.

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 6B or Mathematics 6B;
• ICS 6D or Mathematics 6D;
• 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//degrees/index.php and contact the ICS Student Affairs Office( http://www.ics.uci.edu/ugrad/sao/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.
• Adds: You should be able to add automatically during the first two weeks (see above). If not, and the reason is a missing prerequisite, see below. If there is some other reason why you cannot add the course electronically during the first two weeks, let me know NOW.
• 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 waive the prerequisite. (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) or the Student Affairs Office in your home school. If (and only if) they inform me that you have indeed satisfied the prerequisite, we will take the necessary steps to allow you to enroll in the class.
• Drops:
  • IF YOU ARE GOING TO DROP THE COURSE, YOU HAVE TO DROP BEFORE THE END OF THE SECOND WEEK. Otherwise, you will need the Dean's signature, and that will not be automatically granted. See the ICS Undergraduate Student FAQ for more information

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-8 assignments (Final number is 6). I will drop your lowest homework score. If you take both midterms, I will also drop your second-lowest homework score. See Missed Exam Policy.
  • Possible unannounced quizzes to be given in lecture.
• 45% - Midterms: 2 midterms, to be given in lecture:
  • Midterm 1: Friday February 3 (during regularly scheduled lecture.)
  • Midterm 2: Friday March 2 (during regularly scheduled lecture.)
• 45% - Final exam: Friday March 23, 1:30PM-3:30PM.

• 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 other homework assignments and taken the midterms.

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 of when the graded asignments are returned. 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 will be discussed in class.
  • If you miss both midterm exams, you will be given a grade on the midterms based on your performance on the final exam, less a 5% penalty.
• Because of the above policy, no makeup exams will be given.
• In essence, this means that midterms are optional (subject to a relatively small penalty for missing both of them). However, it is strongly recommended that you take both midterms, for several reasons:
  1. Preparing for the midterms encourages you to organize the material incrementally rather than waiting for the last minute.
  2. If you miss the midterms and have a "bad day" on the final, then you are guaranteed a poor grade in the course.
  3. If you miss a midterm, we will no longer drop your second-lowest homework score.
  4. If you skip the first midterm planning to take the second one and then you have a valid emergency that forces you to skip the second midterm, the 5% penality will come into play.
• NOTE: a midterm is optional only if you do not receive a copy first, 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.
• I will consider exceptions to this policy only in exceptional, documentable circumstances. If you are unable to attend the midterms for a reason that is foreseeable in advance, I will only consider an exception if you tell me in advance. A work conflict is not a valid excuse. If you cannot arrange for time off from work to attend the class, you should not be taking the class.

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 (2:00PM) on the due date. The deadline is firm.
• Late homework will be accepted according to the following sliding scale:
  • Homework turned in after the start of the lecture, but before the end of the lecture will be penalized 10%.
  • Homework turned after the end of the lecture, but before the start of the following discussion section, will be penalized 50%.
  • Homework turned in after that will not receive credit.
• Homework turned in by any other means will be deemed to have been turned in when it is physically encountered. For example, if you place your homework in my mailbox instead of coming to lecture, your homework will be deemed to have been turned in when I next check my mailbox after the lecture. If this happens to be after the next discussion section, then you will not receive credit for the homework assignment.
• 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, even though they might receive a lower grade on the homework assignment itself. 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/optional 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/optional reading: [CLRS] chapters 6,7,8
• Week 4: Greedy Algorithms; Divide and Conquer algorithms; Midterm 1.
  • Required reading: [GT] 5.1-5.2
  • Additional/optional reading: [CLRS] Chapter 16; Section 4.3; Section 28.2
• Week 5: Selection Problems, Lower bound proofs
  • Required reading: [GT] 4.7
  • Additional/optional reading: [CLRS] Chapter 9; [BvG] Chapter 3
• Weeks 6-8: Graph algorithms; Midterm 2
  • Required reading: [GT] 6.1-6.3; 6.4.1; 6.4.4; 7.1; 7.3; 4.2
  • Additional/optional reading: [CLRS] 22.1;23; 24.3; 21
• Week 9: Computational geometry
  • Required reading: [GT] 12;
• Week 10: Dynamic Programming
  • Required reading: [GT] 5.3; 6.4.2; 7.2
  • Additional/optional reading: [CLRS] Chapter 15; [KT] Chapter 6