- The course
**is not**(mainly) about programming in**C**. - The course
*is*about problem solving with computers and algorithms & data structures. - The course just
*happens*to use**C**as the programming language that prac' work etc. is done in. It is necessary that you be(come) expert in the specified programming language ...**C**. - Algorithms will be presented in pseudo-code,
**C**or other programming language(s) as convenient.

The following topics will be covered, not in this order:

- Algorithmic problem solving, correctness, complexity
**Correctness**, termination, logic, assertions, loop invariants, pre- and post-conditions©

L

.

A

l

l

i

s

o

n

**Complexity**, time and space complexity, best average and worst case, O( ), recurrence relations, estimation of complexity**Abstract Data Types**(**ADTs**), e.g. Boolean, Integer, Stack, Queue, List, Tree**Recursion**, e.g. Fib', Towers of Hanoi, permutations, partition- Trees, parse trees, tree traversals
- Dynamic programming strategy, e.g. edit distance on strings
- Divide and conquer strategy, e.g. Hirschberg, multiplication, merge sort, etc.
- Lookup Table (dictionary table) ADT
- Hashing revised, string searching algorithms
- Table by balanced tree, search, insertion, deletion, eg. AVL-tree
- Other tree structures, e.g. PATRICIA, Trie, 2-3-Tree, 2-3-4-Tree, B-Tree, Suffix tree
- Graphs, directed/undirected and weighted/unweighted
- Directed Graphs
- Shortest paths, connectivity
- Undirected Graphs
- minimum spanning tree, Prim's alg', Kruskal's alg'

**Numerical**computing, limited accuracy, solving f(x)=0, integration, rectangle, trapezoidal rule, Simpson's rule

Some specific problems, algorithms and data structures (alphabetic order):

**Graphs**(directed), shortest paths, Dijkstra's algorithm, Floyd's algorithm, connectedness, Warshall's algorithm, topological sort, critical path analysis etc.**Graphs**(undirected), minimum spanning tree, Prim's algorithm, Kruskal's algorithm**Linked Lists**, ADT properties, cons, nil, empty, hd (head, first), tl (tail, rest, next), append**Priority Queue**e.g. by**Heap**data structure, upHeap and downHeap**Partition**data structure (aka union-find, disjoint set)**Queue**, empty, pushq, popq, ADT properties**Searching**, lookup tables, ADT properties, search, insertion, deletion**Sorting**, bubble sort, selection sort, insertion sort, merge sort, quick sort, heap sort, complexity, correctness,*stability***Stack**, empty, push, pop, ADT properties**String searching**, naive, Rabin, Boyer-Moore**Traversal**of linked lists, trees, graphs, depth-first, breadth-first, other**Trees**, binary, sorted, balanced, n-ary

Some general algorithmic strategies or paradigms:

**Divide and conquer****Dynamic Programming****Greedy****Recursion**, linear, binary, n-ary, mutual

For a given algorithm you should be able to:

- Prove its correctness using logic and pre- & post-conditions, assertions, loop invariants as appropriate.
- Give its best-, average- and worst-case time- and space-complexity where possible, or give estimates otherwise.
- Demonstrate its operation on simple examples using diagrams etc.

© L. Allison 2000,

School of Computer Science and Software Engineering, Monash University, Australia 3168