CPSC 413 - Fall 2002

News

Final grades are available here.

L01 (Jacobson) students: if you need to see Prof. Jacobson about your grade, please contact him (jacobs@cpsc.ucalgary.ca) and make an appointment.

Dec 11 - A pencil case and an ID card were left after the final exam. If either are yours, come pick them up in ICT 612 (Dr. Jacobson's office).
Dec 11 - Unclaimed quizes can be picked up in ICT 612 (Dr. Jacobson's office.
Dec 9 - Solutions to Quiz 8 and 9 have been posted.
Dec 5 - A number of practice problems for the final exam, including a practice final with format similar to ours, have been posted (see the "handouts" page).
Nov 28 - For Quiz 7, an example where the output of the greedy algorithm is not optimal is 2 processors and jobs with execution times 9,8,7,6,5 (greedy output is 20, optimal solution is 18).
Nov 25 - Solutions to Quiz 7 have been posted.
Nov 17 - Solutions to Quiz 6 have been posted.
Nov 5 - Solutions to the midterm are available (see the "handouts" page).
Oct 29 - Solutions to the practice midterm are available (see the "handouts" page).
Oct 28 - Solutions to Quiz 5 have been posted.
Oct 28 - Room change - The 413 midterm review organized by CSUS (Tuesday Oct. 29 at 7pm) will now be held in ENA 201.
Oct 25 - Practice problems for the midterm are available (see the "handouts" page).
Oct 22 - CSUS will hold a 413 midterm review on Tuesday Oct. 29, at 7pm, in TRB 102. It's free for CSUS members and 5$ otherwise (membership cards will be sold at the door).
Oct 21 - Quiz 5 will cover dynamic programming only (not divide-and-conquer)
Oct 17 - Solutions to Quiz 4 have been posted.
Oct 7 - Solutions to Quiz 3 have been posted.
Sept 30 - All labs (including the quiz) are cancelled during Thanksgiving week (Oct 14-18)
Sept 27 - Solutions to Quiz 2 have been posted.
Sept 23 - Solutions to Quiz 1 have been posted.
Sept 16 - Lecture 1 (Jacobson, TR 15:30-16:45) is moved to ENE 243.

Tentative Course Schedule

Week Topic Sections of the textbook

9/09 Introduction; Growth of functions. Chapter 1; Chapter 2: 2.1, 2.2; Chapter 3.

16/09 Growth of functions. Chapter 3, Appendix A.

23/09 Recurrences. Chapter 4.

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

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

14/10 Dynamic Programming. Chapter 15: 15.2.

21/10 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)

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

4/11 Greedy Algorithms. Chapter 23 (continued). Chapter 24: 24.3

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

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

25/11 NP-Completeness. Chapter 34: 34.4, 34.5.

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

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

Week	Topic	Sections of the textbook
9/09	Introduction; Growth of functions.	Chapter 1; Chapter 2: 2.1, 2.2; Chapter 3.
16/09	Growth of functions.	Chapter 3, Appendix A.
23/09	Recurrences.	Chapter 4.
30/09	Recurrences; Divide-and-Conquer.	Chapter 4; Chapter 2: 2.3.
7/10	Divide-and-Conquer.	Chapter 28: 28.2; Chapter 9: 9.3; Chapter 30: 30.2.
14/10	Dynamic Programming.	Chapter 15: 15.2.
21/10	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)
28/10	Greedy Algorithms.	Chapter 16: 16.1, 16.2. Chapter 23 (start).
4/11	Greedy Algorithms.	Chapter 23 (continued). Chapter 24: 24.3
11/11	Greedy Algorithms; Approximation Algorithms.	Chapter 35: 35.1, 35.2 (not 35.2.2).
18/11	NP-Completeness.	Chapter 34: 34.1 to 34.3 (except circuit satisfiability).
25/11	NP-Completeness.	Chapter 34: 34.4, 34.5.
2/12	NP-Completeness.	Chapter 34: 34.3 (circuit satisfiability).

CPSC 413, Design and Analysis of Algorithms I (Fall 2002)