Lecture:MWF 2:10-3:00 PM in 1062 Bainer
Discussion Section:F 9:00-9:50 AM in 1062 Bainer

Professor: Nina Amenta
Office Hours:Mon 3-4, Wds 11-12 in 3015 Kemper

Teaching Assistant:Juan Lang
Office Hours: Tu 10:30-11:30 and Fri 10-11, Kemper 3104.

Reader: Minya Dai, mdai "at" ucdavis.edu
Office Hours:TBA

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

Introduction

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

• Data structures - heaps, union-find, hash tables
• Divide and conquor
• Randomized algorithms
• Dynamic programming
• Greedy algorithms
• Graph algorithms
• NP-complete problems and approximation algorithms
• Exhaustive search and branch and bound

Format

Prerequisites:

I assume you have had an undergraduate course in data structures such as ECS 110. I assume you know the material covered in that course, including stacks, heaps, some kind of balanced binary search trees, several sorting algorithms, and basic graph algorithms such as depth-first and breadth-first traversal, topological sort and minimum spanning tree.

Homework

Lectures and Reading

Here is the schedule of lectures and readings

Exams

There will be two in-class midterms and a final. The final will be on the regularly scheduled date, Dec 16. The midterms (tentatively) will be in class, on Oct 28 and Nov 23.

Grading