NB.
Page numbers do not necessarily correspond exactly to lecture numbers:
[01]
[02]
[03]
[04]
[05]
[06]
[07]
[08]
[09]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21/22]
[23/24]The notes are for sale in the bookshop |

- Lecture 1 Wed':
admin', assessment,
*abstract*data types (ADT), ADT Tree, grammar, parse tree (also see [this]). - Lecture 2 Fri': List ADT, prove a theorem on append, Tree ADT, slow and fast versions of Tree flatten. Proof of non-existence of an algorithm.

**Also see the
[unix prac'] system.**

- Lecture 3 Wed': Looking at a familiar algorithm, binary search (which most programmers get wrong), as a formal algorithm, its correctness to be proven. Also debunk a common misconception about the search.
- Lecture 4 Fri': Two more familiar algorithms, the object being the formal arguments (logic) about why they work (are correct), also stability, time- and space-complexity.

Make sure that you look at
the example input and output in the prac 1 specification.

- Lecture 5 Wed': priority queue (NB. not an ordinary queue), heap, upheap(), heap sort, downheap(), examples.
- Lecture 6 Fri': Recursive O(n.log(n))-time sorts, merge sort (postfix) and quick sort (prefix) including partition & Dutch National Flag problem, and the sorts' properties.

- Lecture 7 Wed':
edit distance, examples, applications, simple O(|A|*|B|)-time algorithm,
space complexity, (just) an
*example*of dynamic programming.

- Lecture 8 Wed':
Hirschberg's algorithm, example of (i) divide and conquer,
and (ii) trade-off of
time (×2) for space (O(n
^{2})-->O(n)). - Lecture 9 Fri': lookup Tables, hashing revison + quadratic probing, binary search tree (but not deletion)

- Lecture 10 Wed': deletion from a binary search tree;

definition of and insertion in AVL trees - Lecture 11 Fri' Tries and PATRICIAs

Half way, re-read the
[plan]. |

- Lecture 12 Wed'
B-tree and its relatives, 2-3- and 2-3-4-tree.
**NB.**correction to slide 4. - (
**Anzac Day Thursday April 25**) - Lecture 13 Fri'
string searching algorithms

Re-read the CSE2304[prerequisite knowledge]. |

- Lecture 14 Wed' graphs, directed & undirected, weighted & unweighted, examples, `adjacent', adjacency matrix, adjacency lists, sparse & dense graphs.
- Lecture 15 Fri' directed graphs: Dijkstra's single source shortest paths algorithm, Floyd's all-pairs shortest paths algorithm, Warshall's transitive closure algorithm for unweighted graphs.

- Lecture 16 Wed'
spanning tree,
*minimum*spanning tree (MST), redundancy, cycles, Prim's MST algorithm. - Lecture 17 Wed'
Kruskal's MST algorithm using
priority-queue and
*union-find*.

- Lecture 18 Wed' directed acyclic graphs (DAGs), topological sort, critical path analysis, examples
- Lecture 19 Fri' string search, suffix trees and [Woolloomooloo]!

- Lecture 20 Wed' linear recursion, complexity (recurrence relation & solution), removal of linear recursion by introducing own stack, tail recursive special case, equivalent iterative program.
- Lecture 21 Fri' continue ...
binary recursion, complexity, n-ary recursion, examples
partition an integer, n-queens.

- Lecture 22 Wed'
some general design principles,
cache partial results (dynamic programming),
look for atrenative representations of data (e.g. Ukkonen's edit-distance),
balance between
sub-problems, ... - Lecture 23 Fri'
... estimating complexity empirically.

[Numerical] numerical (in)accuracy ...

NB. Past papers areunder [past years]. |

- Lecture 24 Wed' [...] solve f(x)=0, integration - rectangle, trapezoidal and Simpson's rule.
- Lecture 25 Fri' [Revision]

© L. Allison, School of Computer Science and Software Engineering, Monash University, Australia 3800. Created with "vi (Linux & IRIX)", charset=iso-8859-1