CS 282 DESIGN & ANALYSIS OF EFFICIENT ALGORITHMS

Fall 2012

• Instructor: Henry Kautz
• TAs: Tim Kopp (graduate TA), Yan Xing & Sean Esterkin (undergraduate TAs)
• Class: Tuesday & Thursday 11:05am-12:20pm, Meloria Hall 221
• Workshops: Wednesday 6:00-6:45pm (Yan Xing) and Thursday 7:30-8:15pm (Sean Esterkin), CSB 601
  
• Final Exam: None

Office Hours:

Facebook Discussion Group: https://www.facebook.com/groups/159217487617318/

Textbook: [DPV] = Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani (a draft is available online), 2006.
Note: this registrar's schedule listed a different text (Cormen, Leiserson, Rivest, & Stein); you may return that text or keep it for general reference.

Other resources/recommended reading (all on a 2 hour reserve in the library):
Introduction to Algorithms (3rd edition), T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2009
Algorithm Design, J. Kleinberg and E. Tardos, 2005.
The Design and Analysis of Algorithms, D. Kozen, 1991.
The Design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ulman, 1974.
Algorithms Algorithms, R. Johnsonbaugh, M. Schaefer, 2003.
How to Think About Algorithms Algorithms, J. Edmonds, 2008.
Probability and Computing: Randomized Algorithms and Probabilistic Analysis, M. Mitzenmacher, E. Upfal, 2005.
Randomized Algorithms, R. Motwani, P. Raghavan, 1995.
Approximation Algorithms, V. Vazirani, 2004.

Prerequisites: CSC172 OR MTH172

Clusters: N1CSC008, N1CSC011, N4CSC011

Description: How does one design programs and ascertain their efficiency? Divide-and-conquer techniques, string processing, graph algorithms, mathematical algorithms. Advanced data structures such as balanced tree schemes. Introduction to NP-completeness and intractable combinatorial search, optimization, and decision problems.

Grading: Your final grade will be based on 1/2 exams (in class) and 1/2 assignments. Students requiring accomodations for testing or classroom participation should notify the instructor at the start of the semester, and suitable arrangements will be made. Assignment due dates and quizzes are not intended to be scheduled on religious holidays; if one is scheduled in error, please notify the instructor so it can be rescheduled. Make-up exams will be allowed only for students who have made previous arrangements (at least two days before the exam) with the instructor due to a conflict with a university sponsored activity, or who can provide a medical excuse signed by a doctor.

Homework Rules: You may work on your own or with other students in the class on the homework problems, but you must each write up your solutions separately, without any written aid. In other words, do not write up your final solution while actively collaborating, and do not refer to any notes you made while collaborating. Your assignment must clearly indicate the names of the other students with whom you worked. Assignments should be turned in in printed form. Assignments that do not require creating an executable program should be typed or neatly writing using block letters (not cursive); points will be deducted for assignments that are hard to read.

Assignments can be turned in at the class before the due date, or in CSB 708 (Melissa Singkhamsack's office, administrative assistant to Prof. Kautz). Late assignments will be accepted only under the following conditions:

• Serious illness, as demonstrated by a medical excuse signed by a medical professional.
• Out of town travel for university purposes, such as attending a scientific conference or playing on a university sports team. In all such cases, the instructor must be notified 48 hours in advance of the deadline of the reason for the delay.

Being unable to complete an assignment on time for reasons such as vacation travel or non-university activies is not an acceptable excuse. The grade for late assignments will be reduced by 20% per day late.

Academic Honesty: Turning in work that was copied from another person, the internet, or any other source without explicit citation of the original creator(s) is plagerism. All cases of plagerism will be referred to the university Council on Academic Honesty. Punishments for plagerism include failing the class and expulsion from the university.

Schedule: There is no class on Tuesday 8 October (Fall Break) and Thursday 28 November (Thanksgiving Break). There is no final exam.

Calendar