Summary of CSC2040 A+DS 1998, provided by Kim Marriott. NB. Topic number does not match lecture number, there being 18 topics and ~25 lectures.
Fundamentals 1 Review of C and elementary datastructures -- binary tree insertion and traversal -- implementation of stack 2 Recursion and recursion removal -- dynamic programming version of Fibonacci -- non-recursive pre-order traversal 3 Correctness of algorithms -- proofs by induction -- proof for factorial 4 Complexity analysis of algorithms These slotted in where appropriate for the assignments 9 C and UNIX -- Command line arguments -- file I/O -- Make 10 Programming Tips -- profiling a C program -- design, style, testing, debugging, efficiency -- go through answer to one of the assignments -- mention debuggers Sorting 5 elementary sorting review -- selection sort -- insertion sort -- quicksort (recursive and non-recursive) 6 radix sort -- radix exchange sort -- distribution (bucket) sort -- straight radix sort 7 priority queues and heap sort -- top down heap sort -- bottom up heap sort 8 mergesort and external sorting -- merging arays and merging lists -- top down merge sort (array and list) -- example of bottom up merge sort -- example of balanced multiway merge Searching 11 elementary searching review -- sequential (linear) search -- binary search -- interpolation search -- binary search tree (search and insertion) 12 balanced trees -- 2-3-4 tree (search and insertion) -- red-black tree (search and insertion) 13 hashing -- example of separate chaining -- linear probing -- example of double hashing 14 digital search -- digital search tree (search and insertion) -- example of radix search trie -- patricia tree (search and (many) examples of insertion) 15 external searching -- example of indexed seq access -- example of B tree -- example of extendible hashing (search and insertion) NB. Some lectures were split into two since they also covered the assignment, answers or whatever. Graph Algorithms ?about 5 lectures? 16 elementary algorithms -- depth first traversal (recursive, non-recursive) -- breadth first traversal 17 weighted graphs -- priority first traversal -- minimum spanning tree & shortest path 18 connectivity -- simple union-find -- better union-find