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

The subject aims to cover:

- (i) General problem solving strategies and techniques, e.g.
- useful paradigms, e.g.
- dynamic programming,
- divide and conquer,
- etc.

- analysis of algorithms and data structures, e.g.
- abstract data types,
- program proof / correctness,
- analysis and estimation of space and time complexity,
- etc.

- useful paradigms, e.g.
- (ii) A selection of important computational problems, e.g.
- sorting,
- retrieval/searching,
- etc.

- (iii) A selection of important algorithms and data structures,
- (a) as a "tool kit" for the working programmer,
- (b) as example solutions to (ii),
- (c) as examples of solved problems, to gain insight into (i).

On completing the subject you should be able to apply these general problem solving strategies or algorithmic paradigms:

**Divide and conquer****Dynamic Programming****Greedy strategy****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. Prove termination.**Analyse**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.**Code**the algorithm in the programming language of the subject.

For a given abstract data type (ADT) you should be able to:

- Specify its properties by giving
**rules**/ equations that its constructors and/or operators must obey. **Manipulate**expressions, e.g. to show that different expressions are equivalent in value.**Code**its data representation and operators in the programming language of the subject.

You should be familiar with these important problems and their solutions (alphabetic order):

- connectedness in graphs
- minimum spanning trees
- numerical problems - e.g. solving f(x)=0 and integration
- ordering problems in directed acyclic graphs (DAGs)
- searching (retrieval, dictionary tables, index structures)
- shortest paths in graphs
- sorting
- string searching / matching, exact and approximate
- traversal of various data structures

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 (various), un-rooted

© L. Allison 2004,

School of Computer Science and Software Engineering, Monash University, Australia 3168 Created with "vi (Linux + Irix)", charset=iso-8859-1