Department of Computer Science

CPSC 500: Fundamentals of Algorithm Design and Analysis -- Fall 2005


Instructor: David Kirkpatrick

Office: ICICS/CS X739

Contacts: phone: 604-822-4777; email: kirk@cs.ubc.ca

Lectures: Tuesday and Thursday, 09:30-11:00, CEME 1212

Prerequisites: Graduate standing or consent of instructor. Students are expected to be familiar with the basic (senior undergraduate level) concepts in algorithm design (such as divide-and-conquer, greedy algorithms, dynamic programming) and analysis (such as solving recurrences, basic probability theory, and amortized analysis), as well as basic data structures (such as heaps and balanced trees). Mathematical formulations and proofs are central to both the presentation of the material and student performance in the course.

Course Objectives: The course is an introductory graduate course on algorithms, focusing on both design (including associated data structures) and analysis (including both efficiency and correctness). The course builds on the introductory treatment of the same material provided by a standard undergraduate level algorithms course (CPSC 320, here at UBC), presenting more advanced algorithms, analysis techniques, and computational frameworks than can be covered in a first course. It is also intended as a broad-based introduction to graduate level topics in the design and analysis of algorithms, providing a foundation for other (existing or potential) more advanced and focused (algorithmic) theory courses such as computational geometry, distributed algorithms, randomized algorithms, graph algorithms, etc. The objective of the course is to expose students to basic techniques in algorithm design and analysis, fundamental problem domains, and applications. Although specific problems (and lectures) cut across several of these dimensions, the material can be classified in terms of the following issues:

Text: Much of the material for the course will be drawn from the text Introduction to Algorithms (Second Edition), by Cormen, Leiserson, Rivest and Stein (McGraw Hill). This will be supplemented by material from other texts and recent journal/conference papers.

Evaluation:There will be 5-7 homework assignments, one midterm exam a final exam, and an optional project/paper. Approximate evaluation scheme: 30% assignments, 20% midterm, 40% final exam and 10% instructor's discretion (including class participation). Please contact the instructor if you have any questions.

ANNOUNCEMENTS:
  (October 11) Our Midterm Exam will be held in class on Thursday, Oct 20. You will be responsible for material covered up to and including the lecture on October 13.
  (October 11) Question 2(a) of Assignment 3 is somewhat misleading. (It resulted from modifying what was a slightly more involved question). You may find it easier to disregard the range restriction on the inputs.

Handouts and Assignments: All course handouts and assignments will be posted here.
 
Handout Date_Posted
Course_Information.pdf September 10
 
 
Assignment Date_Posted Date_Due
Asst1.pdf Sept 13 Sept 20
Asst2.pdf Sept 22 Sept 29
Asst3.pdf Oct 11 Oct 13
Asst4.pdf Oct 27 Nov 03
Asst5.pdf Nov 10 Nov 22
Asst6.pdf Nov 25 Dec 01
 

Scribe Notes: Scribe notes will be posted here (final versions are marked with a *). (Scribes should use the following template in preparing their notes.)
 
Lecture Scribe Notes
1 Mike Wood Sept_13*.pdf
2 Andrei Lifchits Sept_15*.pdf
3 Nels Anderson Sept_20*.pdf
4 Man Hon Chan Sept_22*.pdf
5 Ting Wang Sept_27*.pdf
6 Arjun Singh Sept_29*.pdf
7 Brett Cannon Oct_04*.pdf
8 Thomas Fritz Oct_06*.pdf
9 Brad Bingham Oct_11*.pdf
10 Kate Sherwood Oct_13*.pdf
11 Steve Chang Oct_18.pdf
12 MIDTERM EXAM
13 Aaron Barsky Oct_25.pdf
14 Jelena Sirovljevic Oct_27.pdf
15 Mark Schmidt Nov_01.pdf
16 Shuang Hao Nov_03.pdf
17 Matthew C./Yury K. Nov_08.pdf
18 Alfred Pang Nov_10.pdf
19 Brad Atcheson Nov_15.pdf
20 Gang Peng Nov_17.pdf
21 Wang, Ting Nov_22.pdf
22 Matthew C./Yury K. Nov_24.pdf
23 ?? Nov_29.pdf
24 Gitika Agarwal Dec_01.pdf