>!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN"> CMPT 307 Homepage

Welcome to CMPT 307 Homepage

ANNOUNCEMENTS

Quiz 2: October 29, 2013.

Course Title: Data Structure and Algorithms

Course No: CMPT 307 D100"

Instructor: B. Bhattacharya (binay@cs.sfu.ca)

TA: Nevil Anto (nanto@sfu.ca)

Textbook: Algorithm Design by Kleinberg and Tardos; Addison Wesley

Reference: Introduction to Algorithms, 2nd ed., Cormen, Lieserson, Rivest and Stein; MIT Press
(Online access is available 24 x 7. Limited to 5 simultaneous users)

Lecture Hours:

Tuesday 10:30-11.20 Location AQ3003
Thursday 9:30-11.20 Location C9000

First Lecture: Sep-04-2013

Last Lecture: Dec-??-2013

TA Office Hour (location: ASB9838_TA_2)

	Monday	Tuesday	Wednesday	Thursday	Friday
	2:00-3:00		2:00-3:00		2:00-3:00

Instructor Office Hour (location: TASC I 8017)

Monday, Tuesday and Thursday 1:00-2:00pm

Course Outline:

CMPT 307

Lecture Slides from Kleinberg-Tardos:

Lecture Notes Links

Link to the online copy of the book in the library:
Introduction to Algorithms by Corman, Lieserson, Rivest, Styn

Reference Text

Reminder of topics covered in the class:

September 3: Discussed course organization, prerequisites for the course, and topics to be covered.
    Read textbook 1.1 and slides on stable matching.

September 5: Stable matching problem: definition, matching, perfect matching, unstable pair,
    testing a perfect matching for stability and its runtime analysis, Gale Shapley algorithm and its implementation issues.
    Read textbook 1.2-2.5 and slides on Algorithm Analysis.
    A practice problem on stability testing is assigned.
September 10: Discussed four problems of section 1.2 (interval scheduling, weighted interval scheduling, bipartite graph matching,
    independent set in graphs), showed various implementation issues for the interval
    scheduling problem. Started chapter 2: talked about the definition of "efficiency".
    Practice problems: Exercises 1 and 3 (page 67 of the text)
September 12: List of problems considered are: search in a list of ordered and unordered points, matrix multiplication,
    gcd and independent set. Various implementation issues are discussed. Tools to analyze these agorithms are discussed.
    Defined big O, big Omega and big Theta. Comaprison of growth rates of various interesting functions are discussed.
September 17 Finished asymptotics. Functions looked at are logarithms, polynomials, exponentials. Class disturbed by a fire alarm.
    Read section 2.5, and Chapter 3 (sections 3.1 through 3.5).
September 19 Finished heaps (2.5), introduced graphs, various definitions and properties, graph representations.
    Read the sections on breadth-first and depth-first.
    Hints to the assignment questions and other issues are considered here Assorted
September 24 Covered BFS and DFS traversal algorithms on graphs. Implementation issues (using queues and stacks)
    are discussed. Discussed BFS trees on different classes of graphs: trees, cycles, bipartite graphs, complete graphs etc.
    Read the sections on digraphs and topological order (sections 3.5, 3.6).
September 26 Finished Chapter 3; Covered directed acyclic graphs and topological ordering of nodes in a DAG;
    Implementation issues are discussed.
    Quiz 1 will cover materials from Chapter 1, 2 and 3. You can expect questions from the assignments.
October 1 Quiz 1. The solution to the quiz could be found here.
October 3 Started Greedy strategy (Chapter 4). Discussed Interval scheduling, interval partitioning,
    minimum latenes scheduling. The the follow up issues could be found here.
    Please read section section 4.4 (shortest paths) for the next class.
October 8 Finished minimum lateness scheduling. Started Dijkstra's shortest path algorithms.
October 10 Discussed implementation issues of Dijkstra's algorithm. Minimum spanning tree algorithms
     of Prim and Kruskal discussed (section 4.5). Read section 4.6.
October 15 Cut property and cycle property discussed, Union-Find algorithm started.
October 17 Completed Chapter 4. Sections not covered are 4.3, 4.8 and 4.9. I will cover 4.8 later.
    I will start the chapter on divide-and-conquer. Please read sections 5.1 and 5.2.
October 22 Master's theorem discussed. Solution hints to some problems in Chapter 4 are provided here
October 24 Follow up to Master theorem. Further recurrence relations.
October 29 Quiz 2 conducted.
October 31 Problems considered are: counting inversions in a list of numbers, finding the closest
    pair in a set of planar points, and integer multiplication.
November 5 Strassen's method of matrix multiplication is covered. Section 5.6 is skipped.
November 7 Finished closest pair problem. Started dynamic programming. Coin change problem and weighted interval scheduling discussed.
November 12 Finished weighted interval scheduling. Started segmented least squares method.
    Read sections 6.2, 6.3 and 6.4.
November 14 Segmented least squares, Knapsack problems and Shortest path problems discussed. Handed out quiz2.
     Skipped sections 6.5, 6.6, 6.7.
November 17 Solution to quiz2 is here.
November 19 Finished dynamic programming topic. We covered sections 6.1,6.2, 6.3, 6.4, 6.8, 6.9.
    Read sections 13.3, 13.5, 13.6 on randomized divide-and-conquer.
November 21 Started the topic on randomized algorithms (Chapter 13) of the text. We covered random variables and their expectation (section 13.3).
    We then discussed randomized select(section 13.5) and quicksort(section 13.6).
November 26 Finished the section on hashing (chapter 13.6). Discussed universal hashing technique.
November 28 Quiz 3 is scheduled.
December 6 Solution to quiz3 is here.

Homework assignments:

The homeworks will not be collected. These homeworks are designed to prepare you for the in-class quiz test.

First assignment posted on September 13, 2013. ( Solution posted on September 27, 2013.)
Second assignment posted on September 13, 2013. (Solution hints posted on September 27, 2013.)
Third assignment posted on October 15, 2013.
Fourth assignment posted on November 7, 2013.
Fifth assignment posted on November 15, 2013.
Topics covered in chapter 13 posted on December 6, 2013.

Practice problems:

Practice problems to prepare for the final.
Set 1 posted on December 6, 2013. Part solution posted on December 6, 2013.

Last modified: Mon Sep 3, 2013