## 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:
• Compression
• Clustering

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

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