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 |
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 |
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 |
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 |
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 |
Analysis of Randomized QuickSort, Generating random permutations |
June 3, 22:16 |
|
|
#6 |
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 |
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 |
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 |
Binary search trees: searching, minimum/maximum, successor/predecessor, insertion and deletion |
July 16, 00:50 |
|
|
#10 |
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 |
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 |
Greedy algorithms: 1. Activity selection problem, 2. Huffman codes, 3. Scheduling Extra Assignment Problem 3 (2%) |
July 29, 14:07 |
|
|
#13 |
Minimum spanning tree: Kruskal’s and Prim’s algorithms, Approximation algorithms: The traveling-salesman problem |
August 5, 13:23 |
Course
Information
Assignments
Last modified: 06-08-2008 00:38