[CSE2304]
[progress]
CSE2304, Plan 2000
- 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
- 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