What's New:

1. Sep 30, 2008: Hsiu-Chin Lin marked the assignments for this section. Stop by her office hour if you have questions on marking (pls do so Today or any time this week).
2. Sep 24, 2008: "The art of computer programming", by Donald E. Knuth, Volume 3, Chapter 5 is devoted for Sorting.
   "Computers and intractability: a guide to the theory of NP-completeness", by Michael R. Garey and David S. Johnson, is an excellent book on why we need to study computational complexity, and many many elegant NP-completeness proofs. (Nonetheless, we will not cover much in 204; Take 304 if you are interested.)
3. Sep 6, 2008: Office hour set at Fridays, 1:10-2:10pm.
4. Aug 30, 2008: Section page up. The main course webpage (course outline) in moodle is located here.

Lecture Topics & Calendar:

Week	Date	Lecture topics	Additional resources/comments
14	Dec 1	33: Main ideas and basic concepts (Chap 34)	Sample Final
	Dec 3	Review of Final Assignment #5 due in class	Assignment #5 back on Dec 10, from my office (Marker: Amin)
	Dec 12	2:00-4:00pm: Final Exam in CAB 269	Grades pre-assigned by Dec 18, finalized by Dec 22
1	Sep 3	1: Course introduction, basic concepts (Chap 1.1)
	Sep 5	2: Getting started with insertion sort (Chap 1.2, 2.1, 2.2)	Assignment #1 on Chapters 1-3, ready in moodle
2	Sep 8	3: Insertion sort: analysis (Chap 2.2)	L.I. swapped to Lecture 2
	Sep 10	4: Merge sort: analysis (Chap 2.3); big O (Chap 3.1)
	Sep 12	5: Growth of functions (Chap 3.1, 3.2, Appendix A)
3	Sep 15	6: Recurrence and iterated substitution (Chap 2.3, 4.1)	Assignment #2 on Chapters 4, 6, 7, ready in moodle
	Sep 17	7: More iterated substitution, recursion tree method (Chap 4.2)
	Sep 19	8: Iterated substitution leading to Master Theorem (Chap 4.3, 4.4.1)	No Chap 4.4.2; Today covered only the first 6 slides
4	Sep 22	9: More dicussion on Master Theorem, and heaps (Chap 4.3, 6.1) Assignment #1 due in class
	Sep 24	10: Heap properties & construction, heapsort algorithm (Chap 6.2, 6.3, 6.4)
	Sep 26	11: More discussion on heapsort, priority queue (Chap 6.4, 6.5)
5	Sep 29	12: Quicksort algorithm, correctness (Chap 7.1)	Assignment #1 back (Marker: Hsiu-Chin)
	Oct 1	13: Quicksort: WC & BC running time (Chap 7.2)
	Oct 3	14: Quicksort: AC running time, and a randomized version (Chap 7.3, 7.4)	Assignment #3 on Chapters 8.1, 15, ready in moodle
6	Oct 6	15: Two kinds of trees and decision tree lower bound (Chap 8.1) Assignment #2 due in class
	Oct 8	16: Dynamic programming concepts w/Fibonacci numbers (Page 56, Chap 15.1)
	Oct 10	Midterm #1 review
7	Oct 13	Thanksgiving
	Oct 15	Midterm #1 in class (Coverage: Assignments 1 & 2)	Assignment #2 back Tuesday (Marker: Babak)
	Oct 17	17: Matrix-chain multiplication, DP characteristics (Chap 15.2, 15.3)
8	Oct 20	18: Longest common subsequence (Chap 15.4)
	Oct 22	19: An activity-selection, or scheduling, problem (Chap 16.1) Assignment #3 due in class	Assignment #4 on Chapters 16 & 22, ready in moodle
	Oct 24	20: Elements of the greedy strategy (Chap 16.2)
9	Oct 27	21: Graph notions and Breadth-First-Search (Appendix B.4, Chap 22.1-2)	Slides 7-9 skipped
	Oct 29	22: Breadth-First-Search (Chap 22.2)	Assignment #3 back (Marker: Hsiu-Chin)
	Oct 31	23: Depth-First-Search (Chap 22.3)
10	Nov 3	24: Biconnected components (undirected version of Chap 22.5)	Sample Midterm #2 (no solutions will be posted)
	Nov 5	25: Topological sort (Chap 22.4)	Assignment #5 on Chapters 23-25, ready in moodle
	Nov 7	26: Greedy algorithms and the MST problem (Chap 23.1) Assignment #4 due in class
11	Nov 10	Fall term class break
	Nov 12	27: Prim's & Kruskal's MST algorithms (Chap 23.2)
	Nov 14	Review of Midterm #2	Assignment #4 back (Marker: Babak)
12	Nov 17	Midterm #2 in class (Coverage: Assignments 3 & 4)
	Nov 19	28: Kruskal's MST algorithm (Chap 23.2)
	Nov 21	29: SSSP problem and Bellman-Ford's algorithm (Chap 24.1)
13	Nov 24	30: Prim's MST algorithm and Dijkstra's SSSP algorithm (Chap 24.2-3)
	Nov 26	31: APSP problem and the first algorithm (Chap 25.1)
	Nov 28	32: Floyd-Warshall's APSP algorithm (Chap 25.2)

Smart Studying Scheme:

It is strongly recommended that you understand the topics in the lecturing days. Leaving them behind causes serious trouble according to former CMPUT 204 students. Some key points of success are listed in the following. (Nonetheless, following them all does not necessarily guarantee high marks.)

• Lecturing contents:
  • Before the lectures, print out the agenda and have (at least) 30 minutes going through the related textbook chapters (appendix);
  • After the lecture, have (at least) 30 minutes going through the slides and the related textbook chapters (appendix) again.
  • Do not take notes during the lectures. Listen, think, and comprehend the contents.
  • Turn to either instructors (after lecture or office hours) or TAs (seminars, emails, newsgroup) for the parts you don't understand well.
• Assignments:
  • After reviewing the lecture contents, solve the related questions in the assignments. Students are encouraged to discuss and study in small groups. Nonetheless, software may be applied to scan for plagiarism/cheating.
  • Turn to instructors or TAs for help, ONLY after you have seriously thought about the questions for some time. Otherwise you won't understand 100%.
• Midterms:
  • Check with TAs and/or instructors to make sure you can solve every question in the Midterms.
  • Don't miss any one of the questions! Similar questions might occur again in the Final Exam.
• Using office hours:
  • Take advantage of the office hours! If you do have time conflicts, send emails to request an appointment.
• The expected hours per week: at least 10.