CS 170 Efficient Algorithms and Intractable Problems
Profs.
James Demmel |
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.
Prerequisites: CS 61B, Mathematics 55 (or CS 70).