Course: CMPT-307 Data Structures and Algorithms [2008-2]
Instructor: Jan Manuch (jmanuch@sfu.ca)
TA: Louisa Harutyunyan (lha22@fas.sfu.ca)

 

Course information


Lectures:

Day

Time

Room

 Remarks

Tuesdays

5:30pm – 8:10pm 

HCC 1800

 



Office hours:

Who

Day

Time

Room

  Remarks 

instructor 

Mondays

5:00pm – 6:15pm

TASC1 9405 (Burnaby)

 Phone: 778-782-7256

 

instructor

Tuesdays

3:30pm – 5:20pm

HCC 2146

 Phone: 778-782-5172

instructor

August 6, 2008

4:00pm – 6:00pm

TASC1 9405

final preparation office hours

instructor

August 7, 2008

5:00pm – 6:00pm

TASC1 9405

final preparation office hours

instructor

August 8, 2008

5:00pm – 7:00pm

HCC 2146

final preparation office hours

 

Remark: If neither of these times suits you, we can agree an extra time via e-mail.

 

Objective:

The objective of this course is to introduce concepts and problem-solving techniques that are used in the design and analysis of efficient algorithms.  This is done by studying various algorithms, algorithmic techniques, and data structures.

 

Topics:

·         Introduction and Mathematical Preliminaries:  Asymptotic notation, Models of computation, Basic probability theory.

·         Sorting and Order Statistics:  Heapsort, Quicksort, Non-comparison sorts, Lower bounds, Median-finding, Selection.

·         Dictionaries:  Binary search trees, Height-balanced trees, B-trees, Splay trees.

·         Priority Queues:  Heaps, Binomial Heaps, Fibonacci Heaps.

·         Randomized algorithms, Average case analysis, Amortized analysis.

·         Dynamic programming, Greedy algorithms, Graph algorithms.

·         Other topics depending on available time.

 

Marking scheme:

What

Date

Time

Room

 Weight 

Solutions

 12 assignments 

 

 

 

 21% 

 

 midterm 1

 Tuesday, June 3, 2008

 5.30pm-6.30pm 

 HCC 1800

 20% 

solutions

 midterm 2

 Tuesday, July 8, 2008

 5.30pm-6.40pm 

 HCC 1800

 20% 

solutions

 final 

 Friday, August 8, 2008

 7pm-10pm

 HCC 1800

 39% 

solutions

 

Remarks:

  1. At most 50% of each midterm can be shifted to the final. That is: if your performance on the final is better than on a midterm, the weight of the midterm will be adjusted to 10% and the weight of the final will increase by 10%. No other changes to the marking scheme are possible!

 

 Textbooks:

Authors

Name

Edition

Year

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein

Introduction to Algorithms

2nd edition

2001

 

Academic Honesty

Academic Honesty plays a key role in our efforts to maintain a high standard of academic excellence and integrity. Students are advised that ALL acts of intellectual dishonesty are subject to disciplinary action by the School; serious infractions are dealt with in accordance with the Code of Academic Honesty (T10.02) (http://www.sfu.ca/policies/teaching/t10-02.htm). Students are encouraged to read this code.


Lecture notes
Assignments

Last modified: 14-08-2008 12:39