CMPT 307 - Data Structures and Algorithms - Fall'09

Instructor | Times & dates | Homeworks & midterm | Lectures

Announcements

In preparation for the final exam, here is a reminder on various things related to the exam
- Types of questions in the exam
  - Theory questions: definitions, algorithms or their mathematics, theorems, proofs that can be found in the textbook(s) and lecture notes
  - Problems from homeworks: similar to the midterm there will be several problems (that you will need to solve) from homeworks 1 - 8
  - Problems that are not from homeworks: there will be 1-2 problems SIMILAR to those from the homeworks and on the SAME TOPICS
  You can have a look at the sample exam posted below to see what kind of questions you may expect
- Topics covered
  - theory questions: all topics we have studied, from Stable Matching to Network Flows, see lecture notes for exact content, and don't forget to read about parts explicitly marked as required
  - problems from homeworks: all problems from homeworks 1-8
  - problems not from homeworks: all topics and types of problems covered by the homeworks 1-8
- Time and Place
  - Thursday, December 17, 8:30 - 11:30, AQ 3181
- Before the exam, Office Hours
  - I will have office hours on
    - Tuesday, December 15, from 12:00 till 17:00, or will stay longer if needed
    - Wednesday, December 16, from 13:00 till 16:00
  - During the exam
    - Books, lecture notes, and notes of any other kind, calculators are NOT allowed. The only thing you need for the midterm is a pen or pencil.
  - After the exam
    - I will post the exam results and overall grades on the Gradebook, probably, Friday (December 18) afternoon. You will then have an opportunity to discuss your grade on Saturday from 10:00 to 12:00. However, don't consider this as an invitation to try to improve your grade and don't expect it is going to be easy. I will change your grade only in the case of a significant oversight from our side.
A sample final exam is posted
In preparation to the midterm I would like to remind you several things.
- Topics covered:
  - Stable Matching
  - Sorting
  - Order Statistics
  - Elemementary data structures (stacks, queues, trees, hash tables)
- Problems that can be included in the midterm are only those in Assignments 1 - 4, or rather parts of them.
- Books, lecture notes, and notes of any other kind, calculators are NOT allowed. The on\ ly thing you need for the midterm is a pen or pencil.
- Time:
  Thursday, October 29, the regular class time and the regular room
- Office hours:
  Since I will be away during the midterm week, and someone else will be running the midterm (and classes) instead of me, there will be no my office hours during that week. Instead, I will have extra office hours on Friday, October 23, from 10am to 2pm, or by appointment. You can also ask the TA, she knows this area very well, or ask me over email.
Solutions to Homework 3 are due Thursday, October 15, at the beginning of the class.
Solutions to Homework 2 are due Thursday, October 8, at the beginning of the class.
Solutions to Homework 1 are posted.
Note that according the request of the publisher, they are password protected, as well as homework problems themselves. To access solutions and problems, you will need to type in your SFU account name and password.
Please let me know if you experience any problems with that.
The deadline for submitting your first homework is Thursday, September 24.

How to hand in your work
There are 3 ways to hand in a work:

-- Bring it to the class on Thursday and put it on my desk before the class starts.
-- Put it into the assignment box. Assingment boxes are located in the CS Instructional Lab, ASB 9838. This is next to the room tutorials used to be, and the room where TA's office hours are. To enter the room you need an access card or someone's help. Ask insde on where the boxes are. BE CAREFUL! Put your work into the right box! I will not receive wrongly placed works until it is too late!
-- Bring it to my office and if I am not in, slide your work under the door.

Deadline

The last point of time you can hand in your work without penalty is when I return to my office after the class. Some pints will be taken off for late submission. The exact amount of points taken will be decided on case-by-case basis.
THERE IS ABSOLUTELY NO SUBMISSIONS AFTER I POST SOLUTIONS ON THE WEBSITE. This will usually happen the same evening or next morning.

Submission server.
Although a paper copy of your work is mandatory, I encourage you to also submit your works through the Submission Server. This prevents any disagreements about the time of submission, and insures against misplacing or losing your work.

To use the Submission Server go to

https://submit.cs.sfu.ca/

and follow the instructions. Your password is initially set to your 9 digit student number, or if you have used the Submission Server or the GradeBook in the past, it is the same as before.
Archived Annoncements

Course information handout: in PostScript and in PDF

Course Text: "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, McGraw Hill, MIT Press
References:

"Algorithm Design" by Jon Kleinberg and Eva Tardos, Addison Wesley, 2005
"The Art of Computer Programming. Vol. 1,2,3,4" by D. E. Knuth, Addison Wesley
"Concrete Mathematics" by R. L. Graham; D. E. Knuth; and O. Patashnik, Addison-Wesley, 1994

Instructor: Andrei Bulatov (abulatov@cs.sfu.ca), Office: TASC 8013

TAs:

Mohammad Tayebi, email: mohammad.tayebi@gmail.com
Pariya Raoufi, email: pariya.raoufi@gmail.com

Where and When

Lectures: Tu 2:30-4:20 in AQ 3154
Th 2:30-3:20 in AQ 3154
Office Hours by Instructor: Th 15:30-17:00, in TASC 8013 (or by appointment).
Office Hours by TAs: Tu 11:00-12:00 in ASB 9838 TA Office 1.

Important dates

Assignments due:
- Assignment 1 is due Thursday, September 24.
- Assignment 2 is due Thursday, October 8.
- Assignment 3 is due Thursday, October 15.
- Assignment 4 is due Thursday, October 22.
- Assignment 5 is due Thursday, November 5.
- Assignment 6 is due Thursday, November 12.
- Assignment 7 is due Thursday, November 19.
- Assignment 8 is due Thursday, November 26.
Midterm:
- Thursday, October 29, regular time: 14:30 - 15:20, regular room AQ 3154
Final exam: Thurssday, December 17, 8:30 - 11:30, AQ 3181

Homeworks and Midterms

Homework 1 [ ps ] [ pdf ]
Outline Solutions to Homework 1 [ ps ] [ pdf ]
Homework 2 [ ps ] [ pdf ]
Outline Solutions to Homework 2 [ ps ] [ pdf ]
Homework 3 [ ps ] [ pdf ]
Sample Midterm [ ps ] [ pdf ]
Homework 4 [ ps ] [ pdf ]
Outline Solutions to Homework 3 [ ps ] [ pdf ]
Homework 5 [ ps ] [ pdf ]
Outline Solutions to Homework 4 [ ps ] [ pdf ]
Outline Solutions to Midterm [ ps ] [ pdf ]
Homework 6 [ ps ] [ pdf ]
Outline Solutions to Homework 5 [ ps ] [ pdf ]
Homework 7 [ ps ] [ pdf ]
Outline Solutions to Homework 6 [ ps ] [ pdf ]
Homework 8 [ ps ] [ pdf ]
Outline Solutions to Homework 7 [ ps ] [ pdf ]
Sample Final Exam [ ps ] [ pdf ]
Outline Solutions to Homework 8 [ ps ] [ pdf ]

Lectures

I will post slides I use in class.