ECS 222A - Algorithm Design and Analysis - Winter 2012

Course Information Sheet

December 12, 2012

Lectures

Instructor

• Chip Martel. Kemper Hall, #3049. Phone: 752-2651. email: martel AT cs DOT ucdavis DOT edu.
• Office hours (starting 1/10)): . Friday 10:15:-11:15 , Tuesday. 1:15-2:15, and by appointment.

  Teaching Assistant

  • Baldwin-Brown, Luke . email: : ljbaldwinbrown AT ucdavis DOT edu. Office hours: W,2-3; Th 2:10-3
  • Room: 55 Kemper

  Midterm

  There will be one midterm in this class (~ 2/10). Exams will be open book and notes.

  Final

  The Final will be at the scheduled time: W 3/21 10:30-12:30 AM .

  Prerequisites

  Minimal prerequisites are ECS 20 (formerly known as ECS 100) and ECS 122A. Familiarity with standard algorithms as well as enough mathematical sophistication to follow and create formal arguments is critical to success in this class. Knowledge of basic probability theory is also important as we will do a number of probability based arguments. The syllabus contains a description of those chapters in the text which people should already be familliar with.

  Textbook

  Algorithm Design, by J. Kleinberg and E. Tardos We will cover the more advanced material. Much of the material in chapters 1-5 is expected to be familiar.

  Course Web page

  We will maintain useful information on the course Web page: http://www.cs.ucdavis.edu/~martel/222a.
• Visit this page regularly to see what's new. If you miss a handout, get it from here.
• There is also a web page on the myucdavis site. Some secure information (grades and problem set solutions) will be posted to that site.

  Grading

  There will be periodic problem sets (35%), a midterm (23%), and a final (42%). Note that you must get a passing average on the two exams to pass this course.

  Homeworks

  Homework is due at noon on the due date (it can be turned in to the TA (hard copy or electronic) or put in the homework box in 86 Kemper Hall (). Please put your homeworks into the correct box for this class.

• Much of what one learns in this course comes from trying to solve the homework problems, so work hard on them. Doing a conscientious job on the homeworks is the best preparation for the exams. We hope that you will ultimate solve the majority of the problems, but don't be surprised if some of them stump you; some of the problems may be quite challenging.

  Your solutions should be terse, correct, and legible. Understandability of the solution is as necessary as correctness. Expect to lose points if you provide a "correct" solution with a not-so-good writeup. As with an English paper, you can't expect to turn in a first draft: it takes refinement to describe something well. See the sample writeup (under problem sets on the main page). Typeset solutions are always appreciated.

  If you can't solve a problem, briefly indicate what you've tried and where the difficulty lies. Don't try to pull one over on us.