CMPUT 204: Algorithms I (Section A2/EA2, Fall 2008)

Time
Monday
Tuesday
Wednesday
Thursday
Friday
11:00-11:50
 
 
F03/EF03 (CAB 377)
 
 
12:00-12:50
A2/EA2 (CAB 269)
 
A2/EA2 (CAB 269)
 
A2/EA2 (CAB 269)
12:30-13:20
 
F02/EF02 (ACB 229)
 
 
 
13:10-14:10
 
 
 
 
Office Hour
17:00-17:50
F01/EF01 (CAB 357)
 
 
 
 
 
Instructor: Guohui Lin
Office Hour: Fridays 1:10-2:10pm, confirm your coming by email pls (ghlin@cs)
ATH 343
492-3737
TAs: Babak Bostan
Office Hour: TBA (bostan@cs)
 
 
Amin Jorati
Office Hour: TBA (jorati@cs)
 
 
Hsiu-Chin Lin
Office Hour: Tuesdays 1:30-2:30pm (hsiuchin@cs)
ATH 133
 


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.

  Last modified: December 12 2008 14:22:13  © Guohui Lin