CPSC 413 - Winter 2004

News

Unofficial final grades are available here.

CSUS will hold a review for CPSC 413 at 2pm on Friday (April 23rd), in ST 143.

Term grades are available here. The quiz mark (out of 40) is calculated based on your best 9 of 10 quizes. Please notify us of any corrections.

Prof. Jacobson's office hours for this week are:

Thursday, April 22: 15:00-17:00

Friday, April 23: 14:00-16:00

Prof. Lemieux's office hours for this week are:

Wednesday, April 21: 14:00-16:00

Friday, April 23: 13:00-15:00

The final exam will take place Monday, April 26, 12:00-15:00, ICT 102. Please note that no books or calculators will be permitted, but you may bring one 8.5 x 11 sheet of notes.

April 13 - Solutions to Quiz 10 have been posted (see the "quizzes" page).
April 7 - Solutions to Quiz 9 have been posted (see the "quizzes" page).
March 29 - Solutions to Quiz 8 have been posted (see the "quizzes" page).
March 29 - Quiz 9 on April 1 will cover greedy approximation algorithms (and this is not an April Fool's Day joke!).
March 25 - Two old final exams have been posted (see the "handouts" page).
March 22 - Solutions to Quiz 7 have been posted (see the "quizzes" page).
March 22 - The last three quizes will take place on March 25, April 1, and April 8.
March 22 - Solutions to the midterm have been posted (see the "handouts" page).
The CSUS midterm review will be on Wed, March 10 at 17:00 in ICT 121. This event is free to CSUS members - non-CSUS members may purchase a membership at the door for $5.
March 8 - Solutions to Quiz 6 have been posted (see the "quizzes" page).
March 1 - Solutions to Quiz 5 have been posted (see the "quizzes" page).
Feb 18 - Quiz 5 will be held on Feb 26 (the first thursday after reading week) and will cover the divide-and-conquer algorithm design technique.
Feb 18 - Solutions to Quiz 4 have been posted (see the "quizzes" page).
Feb 11 - Quiz 4 (Thursday, Feb 12) will cover all aspects of recurrences including Master Theorem, iteration method, and the "guess and prove" method. A statement of the Master Theorem will be provided on the quiz paper.
Feb 9 - Solutions to Quiz 3 have been posted (see the "quizzes" page).
Feb 9 - Handouts on inductive proofs for the substitution (guess and prove) method have been posted (see the "handouts" page).
Feb 5 - Techniques for bounding sums and recurrences (guess and prove method) will be covered on tonight's quiz.
Feb 2 - Solutions to Quiz 2 have been posted (see the "quizzes" page).
Jan 29 - Chris Marriott will be covering labs T08 and T11 until Feb 23.
Jan 29 - Techniques for bounding sums will not be covered on tonights quiz.
Jan 28 - Handouts on bounding sums and recurrences have been posted (see the "handouts" page).
Jan 26 - Solutions to Quiz 1 have been posted (see the "quizzes" page).
Jan 15 - 3 handouts related to asymptotic notation have been posted (see the "handouts" page).
Jan 13 - The room for Tutorial 10 has been changed to ST63.
Dec 2 - Some math review problems are available (see the "handouts" page).

Tentative Course Schedule

Week Topic Sections of the textbook

12/01 Introduction; Growth of functions. Chapter 1; Chapter 2: 2.1, 2.2; Chapter 3.

19/01 Growth of functions. Chapter 3, Appendix A.

26/01 Recurrences. Chapter 4.

02/02 Recurrences; Divide-and-Conquer. Chapter 4; Chapter 2: 2.3.

09/02 Divide-and-Conquer. Chapter 28: 28.2; Chapter 9: 9.3; Chapter 30: 30.2.

23/02 Dynamic Programming. Chapter 15: 15.2.

01/03 Dynamic Programming. Chapter 15: 15.3 (but not memoization), 15.4, and 0-1 Knapsack Problem (not in the textbook but described on p.382)

08/03 Greedy Algorithms. Chapter 16: 16.1, 16.2. Chapter 23 (start).

15/03 Greedy Algorithms. Chapter 23 (continued). Chapter 24: 24.3

22/03 Greedy Algorithms; Approximation Algorithms. Chapter 35: 35.1, 35.2 (not 35.2.2).

29/03 NP-Completeness. Chapter 34: 34.1 to 34.3 (except circuit satisfiability).

05/04 NP-Completeness. Chapter 34: 34.4, 34.5.

12/04 NP-Completeness. Chapter 34: 34.3 (circuit satisfiability).

Assignments:	PS:	1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11	PDF:	1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11
Solutions:	PS:	1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11	PDF:	1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11

Week	Topic	Sections of the textbook
12/01	Introduction; Growth of functions.	Chapter 1; Chapter 2: 2.1, 2.2; Chapter 3.
19/01	Growth of functions.	Chapter 3, Appendix A.
26/01	Recurrences.	Chapter 4.
02/02	Recurrences; Divide-and-Conquer.	Chapter 4; Chapter 2: 2.3.
09/02	Divide-and-Conquer.	Chapter 28: 28.2; Chapter 9: 9.3; Chapter 30: 30.2.
23/02	Dynamic Programming.	Chapter 15: 15.2.
01/03	Dynamic Programming.	Chapter 15: 15.3 (but not memoization), 15.4, and 0-1 Knapsack Problem (not in the textbook but described on p.382)
08/03	Greedy Algorithms.	Chapter 16: 16.1, 16.2. Chapter 23 (start).
15/03	Greedy Algorithms.	Chapter 23 (continued). Chapter 24: 24.3
22/03	Greedy Algorithms; Approximation Algorithms.	Chapter 35: 35.1, 35.2 (not 35.2.2).
29/03	NP-Completeness.	Chapter 34: 34.1 to 34.3 (except circuit satisfiability).
05/04	NP-Completeness.	Chapter 34: 34.4, 34.5.
12/04	NP-Completeness.	Chapter 34: 34.3 (circuit satisfiability).

CPSC 413, Design and Analysis of Algorithms I (Winter 2004)