[A+DS] >1999>

CSC2040 Algorithms and Data Structures 1998

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.

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

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

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

^CSE2304^ and 1999 >progress>.