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

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(n²)-->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)

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