CSE2304 Algorithms and Data Structures, Progress 2002
Week 1 starts Monday March 4
- Lecture 1 Wed':
admin', assessment, abstract data types (ADT), ADT Tree,
grammar, parse tree (also see
- 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.
Week 2 starts Monday March 11 (all: Prac0; A: Tute1)
- 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.
Week 3 starts Monday March 18 (A: Prac1; B: Tute1)
- 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.
Week 4 starts Monday March 25 (A: Tute2; B:Prac1; Fri-->12th)
- Lecture 7 Wed':
edit distance, examples, applications, simple O(|A|*|B|)-time algorithm,
space complexity, (just) an example of dynamic programming.
NB. Easter Friday March 29 - Sunday April 7
Week 5 starts Monday April 8 (A: Prac2; B: Tute2; 12th-->19th)
- Lecture 8 Wed':
Hirschberg's algorithm, example of (i) divide and conquer,
and (ii) trade-off of
time (×2) for space (O(n2)-->O(n)).
- Lecture 9 Fri':
hashing revison + quadratic probing,
binary search tree (but not deletion)
Week 6 starts Monday April 15 (A: Tute3; B: Prac2; 19th-->26th)
- Lecture 10 Wed': deletion from a binary search tree;
definition of and insertion in AVL trees
- Lecture 11 Fri'
Tries and PATRICIAs
Week 7 starts Monday April 22 (19th-->26th)
|Half way, re-read the
- 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
Week 8 starts Monday April 29 (A: Prac3; B:Tute3)
- 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.
Week 9 starts Monday May 6 (A: Tute4; B:Prac3)
- 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.
Week 10 starts Monday May 13 (A: Prac4; B:Tute4)
Week 11 starts Monday May 20 (A: Tute5; B: Prac4)
- 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.
Week 12 starts Monday May 27 (A: Prac5; B: Tute4)
- 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
Week 13 starts Monday June 3 (A: - ; B: Prac5)
- Lecture 24 Wed'
solve f(x)=0, integration - rectangle, trapezoidal and Simpson's rule.
- Lecture 25 Fri'
© L. Allison,
School of Computer Science and Software Engineering,
Monash University, Australia 3800.
Created with "vi (Linux & IRIX)", charset=iso-8859-1