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

Lecture notes

 Week Lecture notes Topics Last update #1 Week01.pdf Analyzing algorithms: (1) correctness – loop invariant, (2) time complexity – asymptotic behaviour; Asymptotic: Theta-, Big-O-, Big-Omega-, o- and omega- notation; Relational properties of asymptotic notation May 6, 22:07 #2 Week02.pdf MergeSort.ppt Divide&Conquer, MergeSort, Recurrences, Solving recurrences: Substitution method (guess and prove), Recursion tree method, Master method, Sorting overview, Heap: max-heap and min-heap property, Height of the heap May 13, 23:35 #3 Week03.pdf Max-Heapify.ppt Max-Heapify, Building heap, HeapSort, Priority queues and their implementation with heaps: Extract-Max and Increase-Key, A lower bound for comparison-based sorting, Decision tree, QuickSort, Partitioning May 21, 00:02 #4 Week04.pdf factorial.pdf Performance of QuickSort in the worst and base cases, Randomized QuickSort, Probability, Conditionals probabilities, Independence, Random variables, Expected values (linearity) May 27, 22:05 #5 Week05.pdf Analysis of Randomized QuickSort, Generating random permutations June 3, 22:16 #6 Week06.pdf Average case of QuickSort, A lower bound of average running time of comparison sorts, Sorting in linear time: Bucket-Sort, Counting-Sort and Radix-Sort, Stability of sorting algorithms Extra Assignment Problem 1 (3%) June 10, 22:07 #7 Week07.pdf Selection problem: minimum and maximum, the i-th smallest element, Dynamic sets, Hash tables: chaining, unsuccessful and successful searches, Hash functions Extra Assignment Problem 2 (1.5%) June 17, 22:01 #8 Week08.pdf Universal hashing: definition, average case, sequence of operations, Construction of a universal class of hash functions, Open addressing, Uniform hashing, Linear probing, Quadratic probing, Double hashing, Analysis of open-addressing: unsuccessful search, insert and successful search June 25, 00:27 #9 Week09.pdf Binary search trees: searching, minimum/maximum, successor/predecessor, insertion and deletion July 16, 00:50 #10 Week10.pdf Red-black trees: RB properties, black-height, The bound on the height of RB tree, Rotations, Insertion – RB-Insert-Fixup, Deletion – RB-Delete-Fixup (extra black token) July 16, 00:34 #11 Week11.pdf Dynamic programming: 1. Characterize the structure of optimal solution, 2. Recursive solution, 3. Computing optimal costs, 4. Constructing the optimal solution; Problems: Matrix-chain multiplication, Longest common subsequence, All-pair shortest paths and matrix multiplication, Floyd-Warshall algorithm for All-pair shortest paths July 22, 23:54 #12 Week12.pdf Greedy algorithms: 1. Activity selection problem, 2. Huffman codes, 3. Scheduling Extra Assignment Problem 3 (2%) July 29, 14:07 #13 Weel13.pdf MST.pdf Minimum spanning tree: Kruskal’s and Prim’s algorithms, Approximation algorithms: The traveling-salesman problem August 5, 13:23

Course Information
Assignments