[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.

```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)
-- 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
```

^CSE2304^ and 1999 >progress>.