ECS 223 - Algorithm Design and Analysis - Spring 2011

Course Information Sheet

March 26, 2011


You are responsible for everything on this handout. Please read it.

Lectures

T,Th 1:40-3 125 Wellman.

Instructor

  • Chip Martel. Kemper Hall , #3049. Phone: 752-2651. email: martel@cs.ucdavis.edu. Office hours: Friday 12:45-1:45, and Tuesday 11:45-12:40

    Midterm

    There will be be two midterms in this class (around May. 3, and June 2).

    Final

    No final exam (2nd midterm will be a final of sorts).

    Textbook

    Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques , by Uzi Vishkin. (link to notes on main class page)
  • We will also cover a few advanced topics from research papers.

    Course Syllabus

  • Parallel models, relationship between models and algorithms
  • PRAM algorithms (majority of the class): Summation, Prefix Sums, Sorting, Selection, 2-3 Trees, Maximum Finding, List ranking, Graph Algorithms,
  • Advanced topics: other models (BSP, logP), GPU systems, Map-Reduce, others

    Course Web page

    We will maintain useful information on the course Web page: http://www.cs.ucdavis.edu/~martel/223.
  • Visit this page regularly to see what's new. If you miss a handout, get it from here. The smartsite page for this class will also be used occassionally for restricted handouts.

    Grading

    There will be periodic problem sets (~3) (35%), first midterm (30%), and second midterm (35%).

    Homeworks

    Homeworks are due by 5PM on the due date. They can be turned in in class, to my office, or my mailbox (or by email). Homeworks will be graded on clarity of presentatation as well as correctness.

    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. Typeset solutions are always appreciated.