CS 170
Efficient Algorithms and Intractable Problems

Profs. James Demmel
and Jonathan Shewchuk

Spring 2001
Tuesdays and Thursdays, 12:30-2:00 pm
100 Lewis Hall

Notes on Shannon's Theorem and Lempel-Ziv compression.

Required Readings

Information

Work

Lectures

The following schedule is tentative. There will definitely be changes as the semester progresses, so check here periodically. Midterm dates may also change! In the readings, ``CLR'' is shorthand for the Cormen, Leiserson, and Rivest textbook.

Homeworks and projects that are currently available can be accessed by clicking on them. All homeworks and projects are due Fridays at 4 pm. Written homeworks may be submitted to Jenny Gonzalez in the CS main office, or to the CS 170 box in 283 Soda. The projects is submitted electronically.

Topic Readings Due Friday
1: January 16 Overview; Fibonacci numbers Notes, Sections 1-3; CLR, Chapters 2, 7 .
2: January 18 Algorithm design; recurrences Notes, Sections 4-7; CLR, Chapters 3, 4 Homework 1
3: January 23 Graphs and trees Notes, Sections 8-10; CLR, Section 23.1 .
4: January 25 DFS, topological sort Notes, Sections 11-14; CLR, Sections 23.3, 23.4 Homework 2
5: January 30 Connected components Notes, Section 15; CLR, Section 23.5 .
6: February 1 BFS, Dijkstra's algorithm Notes, Sections 16, 17; CLR, Sections 23.2, 25.1, 25.2 Homework 3
7: February 6 Bellman-Ford algorithm Notes, Sections 18-21; CLR, Sections 25.3, 25.4 .
8: February 8 Minimum spanning trees Notes, Section 22; CLR, Chapter 24 Homework 4
9: February 13 Disjoint sets Notes, Sections 23-25; CLR, Chapter 22 .
10: February 15 MIDTERM I covers Lectures 1-8 (no, not 9) Homework 5
11: February 20 Huffman coding Notes, Sections 26, 27; CLR, Sections 17.1-17.3 .
12: February 22 Dynamic programming I Notes, Sections 28-31; CLR, Sections 16.1-16.3 Homework 6
13: February 27 Dynamic programming II Notes, Sections 32, 33; CLR, Sections 26.1, 26.2 .
14: March 1 Linear programming I Notes, Sections 34, 35 Homework 7
15: March 6 Linear programming II Notes, Sections 36-38 .
16: March 8 Network flows Notes, Sections 39-43; CLR, Sections 27.1-27.3 Homework 8
17: March 13 NP-completeness I Notes, Sections 44-47; CLR, Sections 36.1-36.3 .
18: March 15 NP-completeness II Notes, Section 48 Project 1
19: March 20 NP-completeness III Notes, Sections 49, 50; CLR, Sections 36.4, 36.5 .
20: March 22 NP-completeness IV Notes, Section 51; CLR, Section 37.1 Homework 9
March 26-30 Spring Recess . .
21: April 3 NP-completeness V Notes, Section 51; CLR, Section 37.2 .
22: April 5 Matrix multiplication I Notes, Sections 52-55; CLR, Sections 31.1, 31.2 Homework 10
23: April 10 Matrix multiplication II Notes, Sections 56-59; CLR, Sections 31.4, 31.5 .
24: April 12 MIDTERM II covers Lectures 1-21 (no, not 22 or 23) Homework 11
25: April 17 Fourier transforms Notes, Sections 60-62; CLR, Sections 32.1, 32.2 .
26: April 19 Computational geometry I CLR Sections 35.1, 35.2 Homework 12
27: April 24 Computational geometry II CLR Section 35.3 .
28: April 26 Number theory I Notes, Sections 65-69; CLR, Sections 33.1, 33.2 Homework 13
29: May 1 Number theory II Notes, Sections 70-74; CLR, Sections 33.3, 33.4 .
30: May 3 Number theory III Notes, Sections 75, 76; CLR, Sections 33.5-33.7 Homework 14
31: May 8 Review . .

The FINAL EXAM is Wednesday, May 16 from 5 pm to 8 pm in 230 Hearst Gym.

Course Description

Concepts and basic techniques in the design and analysis of algorithms; models of computation; lower bounds; algorithms for optimum search trees, balanced trees, and union-find algorithms; numerical and algebraic algorithms; combinatorial algorithms. Turing machines, how to count steps, deterministic and nondeterministic Turing machines, NP-completeness. Unsolvable and intractable problems.

Prerequisites: CS 61B, Mathematics 55 (or CS 70).

Grading

Mail inquiries to cs170@cory.eecs.berkeley.edu