[CSE2304] <2001< [plan] >2003>

CSE2304 Algorithms and Data Structures, Progress 2002

 NB. Page numbers do not necessarily correspond exactly to lecture numbers:                     [21/22] [23/24] The notes are for sale in the bookshop

Week 1 starts Monday March 4

• 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.

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.

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': lookup Tables, 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)

• 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)

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

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)

 NB. Past papers are under [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