CPSC 413 - Winter 2003

News

Final grades are available here. Note that an entry of -1 indicates an excused absence and has been treated as a no-mark in calculating final grades.

Term grades are available here. Note that an entry of -1 indicates an excused absence and will be treated as a no-mark in calculating final grades. Please notify Dr. Jacobson of any corrections before April 30.

April 14 - A practice final exam is available (see the "handouts" page).
April 14 - Solutions to Quiz 10 have been posted (see the "quizzes" page).
April 8 - Due to the cancellation of Quiz 9, the 50% quiz mark will be made up of the best 8 of 9 quizzes.
April 2 - Quiz 9 (Thursday April 3) will cover greedy approximation algorithms.
April 2 - Solutions to Quiz 8 have been posted (see the "quizzes" page). I've also added the
March 26 - Quiz 8 (Thursday March 27) will cover greedy algorithms, especially material from the previous week's lectures.
March 25 - A small correction has been made to question 1b in the solution to Quiz 7.
March 24 - Solutions to Quiz 7 have been posted (see the "quizzes" page). I've also added the promised (but forgotten - sorry!) link to the Quiz 6 solutions.
March 20 - Solutions to Quiz 6 have been posted (see the "quizzes" page).
March 11 - A small correction to the solution for Question 5 on the midterm has been made.
March 10 - Quiz 6 (Thursday March 13) will cover dynamic programming.
March 7 - Solutions to the midterm are available (see the "handouts" page).
March 5 - Solutions to Quiz 5 have been posted (see the "quizzes" page).
March 4 - Prof. Scheidler (L03) will have extra office hours on Thursday, March 6 from 1:30 - 4:00.
March 4 - Prof. Jacobson (L04) will have extra office hours on Thursday, March 6 from 2:30 - 4:30.
Feb 28 - CSUS is running a midterm tutorial on Tuesday, March 4 starting at 17:00 in ENE 241. You need to be a CSUS member to attend, and memberships will be sold at the door.
Feb 28 - The midterm exam takes place Thursday, March 6 from 18:00 - 20:00 (2 hours long) in MFH 162. It will cover everything up to and including todays lecture (dynamic programming). No extra material (calculators, notes, etc.) will be permitted. The Master Theorem will be stated on the exam paper, but all other definitions (including O-notation, etc.) are your responsibility.
Feb 26 - There will be no assignment this week. However, a number of midterm practice problems can be found in the midterms from previous offerings of the course. Links to these web sites can be found on the "external pages" page.
Feb 26 - Quiz 5 (Thursday Feb 27) will cover divide-and-conquer.
Feb 24 - Solutions to Quiz 4 have been posted (see the "quizzes" page).
Feb 12 - Solutions to Quiz 3 have been posted (see the "quizzes" page).
Feb 5 - Quiz 3 (Thursday Feb 3) will cover analysis of iterative algorithms (including bounding sums) and the guess and prove method for recurrence solving (i.e., the material covered during last week's lectures --- Jan 27 to Jan 31). In general, every quiz will test the material covered in the previous week's lectures.
Feb 4 - Solutions to Quiz 2 have been posted (see the "quizzes" page).
Jan 28 - Solutions to Quiz 1 have been posted (see the "quizzes" page).
Jan 23 - L04 (Jacobson) on MWF 12:00-12:50 is moved to ST 135.
Dec 9 - Some math review problems are available (see the "handouts" page).

Tentative Course Schedule

Week Topic Sections of the textbook

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

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

27/01 Recurrences. Chapter 4.

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

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

24/02 Dynamic Programming. Chapter 15: 15.2.

03/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)

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

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

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

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

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

14/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
13/01	Introduction; Growth of functions.	Chapter 1; Chapter 2: 2.1, 2.2; Chapter 3.
20/01	Growth of functions.	Chapter 3, Appendix A.
27/01	Recurrences.	Chapter 4.
03/02	Recurrences; Divide-and-Conquer.	Chapter 4; Chapter 2: 2.3.
10/02	Divide-and-Conquer.	Chapter 28: 28.2; Chapter 9: 9.3; Chapter 30: 30.2.
24/02	Dynamic Programming.	Chapter 15: 15.2.
03/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)
10/03	Greedy Algorithms.	Chapter 16: 16.1, 16.2. Chapter 23 (start).
17/03	Greedy Algorithms.	Chapter 23 (continued). Chapter 24: 24.3
24/03	Greedy Algorithms; Approximation Algorithms.	Chapter 35: 35.1, 35.2 (not 35.2.2).
31/03	NP-Completeness.	Chapter 34: 34.1 to 34.3 (except circuit satisfiability).
07/04	NP-Completeness.	Chapter 34: 34.4, 34.5.
14/04	NP-Completeness.	Chapter 34: 34.3 (circuit satisfiability).

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