## 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:

- Data structures - hash tables, skip lists, tries
- Randomized algorithms
- Max-flow and linear programming
- NP-complete problems and approximation algorithms
- Markov processes

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.
- Homework 1, assigned Jan 10, due in class
at the begining of lecture, Wds Jan 19.
- Homework 2, assigned Jan 24, due in class Wds Feb 2.
- Problems for before the midterm,
distributed Feb 4.
- Homework 3, assigned Feb 14, due in class Feb 23.
- Homework 4, assigned Mar 2, due in class Mar 11.
- Solutions for HW 4.
- Problems for before the final,
distributed Mar 14.

### 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.