ECS 222A: Design and Analysis of Algorithms

MWF 10-11:50 in 1062 Bainer
CRN #70927

REVIEW QUESTION SESSION: Tues Mar 15, 7pm, in the regular classroom.

FINAL: Thurs Mar 17, 10:30 AM, in the regular classroom.

Professor: Nina Amenta
Office Hour:Tues 11-12 in 3015 Kemper

Teaching Assistant:Susan Margulies, smargulies"at"ucavis.edu
Office Hours: Mon 11-12.
Discussion Section: Thurs 2-3, Art 217

Textbook: Corman, Leiserson, Rivest and Stein
Introduction to Algorithms, 2nd Edition
We will supplement the text with research papers and and handouts.


Introduction

This is the graduate algorithms class. We will study various tools and techniques:

We will use these tools for a variety of problems, with emphasis on:

Format

There will be 4 homeworks, an in-class midterm and a final. Review questions will be distributed before the final and midterm. The final will be held at the official time, Thur March 17 10:30-12:30.

Prerequisites:

I assume you have had an undergraduate course in algorithms such as ECS 122a. I assume you know the material covered in that course, including heaps, heapsort and quicksort, Djikstra's MST algorithm, single-source and all-pairs shortest path algorithms, and dynamic programming. Some of the homework will be intended to remind you of this material, even though we do not cover it in class. We will, however, go over NP-completeness again.

Page numbers in the book for all of these topics can be found on the Web page for this Fall's 122a.

Homework

Homework solutions should be typed. They are due at the begining of class. If you want to add pictures and equations by hand, feel free. Or, you might want to take this opportunity to learn LaTeX.

Links

These links should help you find more information on some of the many complicated topics that we touch on. People teach entire courses on topics that we cover in one lecture!

Lectures and Reading

Lectures will be videotaped. If you miss class, you can see the lecture on any later date at 1101 Hart Hall (you need to show student ID). Call 752-2911 for the hours.

Schedule of lectures and readings

Grading

Grades will be determined using this formula:


Homework 30%
Midterm 30%
Final 40%

Homework should be turned in at the begining of class on the day that it is due, or submitted in electronic form before the class meeting.

Each student will have two free late days per semester (including weekends). After that we will take 10% off for every day that a homework assignment is late.