University of California, San Diego

La Jolla, CA 92093-0114

**Office:** 4111 Applied Physics and Mathematics Building (APM)

**Phone:** (858) 534-1332;` ` **Fax:** (858) 534-7029;` `

**Email: ** russell@cs.ucsd.edu

Jeff Edmonds textbook, covered chapters (postscript) . Jeff Edmonds textbook, covered chapters (PDF) . This is a work in progress by Prof. Jeff Edmonds of York University, which can be used as a supplementary textbook. Please send comments to jeff@cs.yorku.ca. He appreciates feedback.

- Tues, 3:30-4:30, EBU-1 6307A, Qian
- Wed.,12-2, EBU-1, 6307, Huayong
- Thurs., 9-10:50, EBU-1, 6307, Mikhail
- Fri, 2-3, EBU-1 6307A, Max

- Phoebe Shubsuwan pshubsuw@ucsd.edu
- (Branden) Li : liwan@ucsd.edu
- Justin: jnemeth@ucsd.edu
- Vinh Huynh: v2huynh@ucsd.edu

- Class Description (Postscript)
- Class Description (PDF)
- Calibration homework, due January 13(ps)
- Calibration homework, due January 13 (pdf)
- Calibration homework, answer key (ps)
- Calibration homework, answer key (pdf)
- Calibration homework, implementation answer key (ps)
- Calibration homework, implementation answer key (pdf)
- Homework 1, due January 27(ps)
- Homework 1, due January 27(pdf)
- Homework 1, answer key (ps)
- Homework 1, answer key(pdf)
- homework 1, implementation answer key by Ari Frank (ps)
- homework 1, implementation answer key by Ari Frank (pdf)
- Sample Midterm-- use to study for Practice Midterm (2/4) and Midterm (2/18) (ps)
- Sample Midterm-- use to study for Practice Midterm (2/4) and Midterm (2/18) (pdf)
- Sample Midterm answer key-- use to study for Practice Midterm (2/4) and Midterm (2/18) (ps)
- Sample Midterm answer key-- use to study for Practice Midterm (2/4) and Midterm (2/18) (pdf)
- Practice Midterm answer key-- use to study for Midterm (2/18) (ps)
- Practice Midterm answer key-- use to study for Midterm (2/18) (pdf)
- Homework 2, due Feb. 15(ps)
- Homework 2, due Feb. 15 (pdf)
- Homework 2, answer key (ps)
- Homework 2, answer key(pdf)
- Homework 3, due March 3(ps)
- Homework 3, due March 3 (pdf)
- Homework 3, answer key(ps)
- Homework 3, answer key(pdf)
- Homework 4, due March 10(ps)
- Homework 4, due March 10(pdf)
- Homework 4, answer key(ps)
- Homework 4, answer key(pdf)
- Sample Final -- use to study for final Monday, March 14. (ps)
- Sample Final -- use to study for final Monday, March 14. (pdf)
- Sample Final Answer Key -- use to study for final Monday, March 14. (ps)
- Sample Final Answer Key -- use to study for final Monday, March 14. (pdf)

- Euclid's GCD algorithm (ps)
- Euclid's GCD algorithm (pdf)
- Using Preprocessing and data structures: Heap sort and skylines (ps)
- Using Preprocessing and data structures: Heap sort and skylines (pdf)
- Using Preprocessing and data structures: Views (ps)
- Using Preprocessing and data structures: views (pdf)
- Data structures for graph representations: is a graph a forest? (ps)
- Data structures for graph representations: is a graph a forest? (pdf)
- Data structures for graph representations: searching a graph (ps)
- Data structures for graph representations: searching a graph (pdf)
- Including costs for arithmetic and amortized analysis: Euclid's GCD algorithm revisited (ps)
- Including costs for arithmetic and amortized analysis: Euclid's GCD algorithm revisited (ps)
- Divide and Conquer: Mergesort and All pairs binary tree distances (which we didn't cover in class this year) (ps)
- Divide and Conquer: Mergesort and All pairs binary tree distances (which we didn't cover in class this year) (pdf)
- Divide and Conquer: Integer Multiplication, the Master Theorem (ps)
- Divide and Conquer: Integer Multiplication, the Master Theorem (pdf)
- Divide and Conquer: When (not) to use the Main Recurrence Theorem (ps)
- Divide and Conquer: When (not) to use the Main Recurrence Theorem (pdf)
- Backtracking: Introduction and Maximum Independent Set (ps)
- Backtracking: Introduction and Maximum Independent Set (pdf)
- Backtracking: Graph coloring: generalizing problems to allow recursive solutions; Why greedy algorithms are dangerous (ps)
- Backtracking: Graph coloring: generalizing problems to allow recursive solutions; Why greedy algorithms are dangerous (pdf)
- Greedy algorithms compared to back-tracking: The Modify-the-solution method, event scheduling (ps)
- Greedy algorithms compared to back-tracking: The Modify-the-solution method, event scheduling (pdf)
- Greedy algorithms : The Modify-the-solution method, Kruskal's minimum spanning tree algorithm (ps)
- Greedy algorithms : The Modify-the-solution method, Kruskal's minimum spanning tree algorithm (pdf)
- Data structures for disjoint sets and Kruskal's minimum spanning tree algorithm Intro to dynamic programming (ps)
- Data structures for disjoint sets and Kruskal's minimum spanning tree algorithm Intro to dynamic programming (pdf)
- Dynamic programming: the minimum cost benches problem (ps)
- Dynamic programming: the minimum cost benches problem (pdf)
- Dynamic programming: the shortest path problem (ps)
- Dynamic programming: the shortest path problem (pdf)

- Leeann Bent's Order Notation Summary Sheet (ps)
- Leeann Bent's Order Notation Summary Sheet (PDF)
- Using Data Structures Summary Sheet (postscript)
- Using Data Structures Summary Sheet (PDF)
- Divide and Conquer Summary Sheet (postscript)
- Divide and Conquer Summary Sheet (PDF)
- Backtracking Summary Sheet (ps)
- Backtracking Summary Sheet (PDF)
- Greedy Algorithms Summary Sheet (ps)
- Greedy Algorithms Summary Sheet (PDF)
- Dynamic Programming Summary Sheet (ps)
- Dynamic Programming Summary Sheet (pdf)