^CSE2304^ [plan]

CSE2304 Algorithms and Data Structures, Progress 2004

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] [22] [23]; the notes are for sale in the bookshop.

Tutes	[1] [2] [3] [4] [5].
Pracs	[0] [1] [2] [3] [4] [5]

Net: Bib' [1] [2], [Alg's], [C].

Check this page regularly!

Week 1 starts Monday 1 March

[Introduction], admin', and the start: abstract algorithms and data types (v. programs), parsing arithmetic expressions and parse trees (see prac1).
[Lists and trees] doing algebra on data structures (lists and trees).

Week 2 starts Monday 8 March ([Tute1], [Prac0])

[Proving] programs correct. Note, the particular algorithm is just an illustrative example; the topic is the method of proof. (But also note that a common "optimization" of binary search (3-way test) slows down the algorithm on average!)
[Proving] more programs correct. Note, the particular algorithms are just illustrative examples; the topic is the analysis itself.

Week 3 starts Monday 15 March ([Tute1], [Prac1A])

[Heap], priority queue, and heap sort. Read the code for upHeap, downHeap and Heap sort, and note how the assertions and pre- & post-conditions prove the algorithms correct. Make sure that you use the demo's [1] & [2].
Two more [fast sorting] algorithms -- merge sort and quick sort. Make sure that you use the demo's [1] & [2]. Note, 1. cannot sort faster than O(n.log n)-time under reasonable general conditions, 2. the [Dutch] national flag problem yields an easy-to-program version of `partition' for use in quick sort. (Search the [bib'] if you want refs to insitu merge in O(n)-time and O(1)-space.)

Week 4 starts Monday 22 March ([Tute2], [Prac1B])

[Edit distance] and the simplest O(|A|*|B|)-time and -space [algorithm] -- make sure you use the web demo'. It is an example of dynamic programming -- a fairly general algorithmic strategy.
[Hirschberg's] algorithm applied to edit distance; an example of divide and conquer (and of dynamic programming). Note the trade-off of number of instructions executed (×2±) for space (n²--->n). Make sure that you use the web [demo'].

Week 5 starts Monday 29 March ([Tute2], [Prac2A])

[Tables] -- dictionary/ lookup tables by unsorted array, sorted array, hashing, and binary search trees. Use the BST (and AVL) [demo].

The cheater checker is up and ready to accept student submissions for pracs 2 to 5. Students who don't submit will receive a mark of zero. The cheater checker is [here] --K 31/3/'04. Read, and keep for your records, any email that the cheater checker sends you (e.g. "submission unsuccessful"!).

[AVL] height-balanced trees, insertion, L2 L3 (R2 R3) rotations, height v. n (contents). Use the AVL (and BST) [demo]!

Week 6 starts Monday 5 April

[Tries], and PATRICIAs, for storing strings (over some alphabet), words, time of insert, search (& delete) operations O(|word|)-time, independent of n.
Good Friday holiday

Easter, Friday 9 April - Friday 16 April 2004

Tim B' is running extra consultation classes for CSE2303 and CSE2304 in building 75 room G28 Tuesday afternoons for the rest of the semester.
Also see the instructions about the cheater checker, [above].

Week 7 starts Monday 19 April ([Tute3], [Prac2B])

[2-3- to B-] trees, a logical progression from 2-3- to 2-3-4- to B-trees. B-trees are often used to index very large collections of data stored on disc (and for other purposes).
[String searching] algorithms -- naive, Rabin, and Boyer-Moore. You must use the web [demo'], and experiment with different pattern and text lengths and contents. (If you want to see the other details of B' M' "view source".)

Week 8 starts Monday 26 April ([Tute3], [Prac3A])

Introduction to [graphs], [(edge-) weighted | unweighted] × [directed | undirected] graphs; adjacent, connected; sparse, dense; adjacency matrix, adjacency lists.
[Paths] Dijkstra's single-source shortest paths algorithm, Warshall's transitive closure (connectedness) algorithm, [homework: Floyd's all-pairs shortest paths algorithm; try the [demo']] ...

Week 9 starts Monday 3 May ([Tute4], [Prac3B])

Pracs 1 and 2 (Clayton): 33 absentees and 10 exempts to date, counted as 0 (exempts get their average mark overall so expect those marks to go up) --K, 5 May.	/12	#
	11,12 9,10 7,8 5,6 3,4 0,1,2	70 63 39 27 20 22

... [Prim's] minimum spanning tree algorithm. It is a good exercise to use the demo' to generate a random graph, then draw the graph, find the MST by working through the algorithm by hand, and finally use the demo' to check your MST.
[Kruskal's] minimum spanning tree algorithm, same remarks about the demo' as for Prim's. Make sure that you know under what conditions Prim's as better than Kruskal's, and v.v., and why.

Week 10 starts Monday 10 May ([Tute4], [Prac4A])

[DAGs] i.e. directed acyclic graphs, depth-first traversal of DAGs and its application to topological sorting and to critical path analysis.
[Suffix trees] -- an "advanced" data structure for indexing a long "text". It can be built, and traversed, in linear-time, |text|-time. Once built, a pattern can be searched for in |pattern|-time. It can solve these problems in linear-time: (i) longest repeated substring, (ii) longest common (to >1 files) substring, (iii) longest palindrome. You do need to know how to build one for a short text, but do not need to know the linear-time algorithm. "Mississippi" is un-Australian, of course; you might prefer "Woolloomooloo" (note 1×W, 3×`l', 1×`m', 8×`o').

e.g. 1/10₁₀ = 1/1010₂ = 0.0(0011₂)^{^.}

         0.0 0 0 1 1 0 0 1 1 ...
       _______________________
1 0 1 0) 1.0 0 0 0 0 0 0 0 0 0
         - 1 0 1 0
         ---------
             1 1 0 0
           - 1 0 1 0
             -------
                 1 0 0 0 0
                 - 1 0 1 0
                 ---------
                      etc.

e.g. f(x)

range

integral

sin x

0..π

[-cos x]

= 2

E.g. For just two intervals, 0..π/2 and π/2..π.

Rectangle rule:	(1/sqrt(2)+1/sqrt(2))&pi/2 = &pi/sqrt(2) = 3.14/1.41 = 2.2.
Trapezoidal rule:	(0/2+1+0/2)π/2 = π/2 = 1.57.
Simpson rule:	(1×0+4×1+1×0)(π/2)/3 = 2×π/3 = 6.28/3 = 2.1.

NB. Would use many more intervals in reality, and thus get closer to the true answer (2.0).

Week 11 starts Monday 17 May ([Tute5], [Prac4B])

[Numerical] algorithms, limited accuracy of floating point, rounding errors (c.f. [Babbage]'s difference engine [#2] "has seven orders of difference and will calculate to thirty one [decimal] figures.", i.e. 90+ binary figures). Solving f(x)=0. ...
... numerical integration, rectangle rule, trapezoidal rule, Simpson's rule. The last uses quadratics over pairs of intervals. Quadratic g(x)=ax²+bx+c. Two intervals, 0..w and w..2w, three boundaries 0, w & 2w:

g(0) = c = p, say,

g(w) = aw²+ bw+c = q,

g(2w) = 4aw²+2bw+c = r.

Integrate g(x), get (ax³)/3+(bx²)/2+cx.
For range of 0..2w integral is (8aw³)/3+2bw²+2cw = (8aw²+6bw+6c)w/3 = (r+4q+c)w/3.

Week 12 starts Monday 24 May ([Tute5], [Prac5A])

[Rec'n], uses (e.g. fast integer & matrix multiplication;) and varieties of recursion, linear recursion, recurrence relation for complexity, removal of (linear) recursion, tail recursion ~ loop, binary recursion (e.g. merge-sort, quick-sort, Hirschberg)...

Recursion is related to self-reference in English.

... binary recursion, general pattern, complexity (under certain rather strict assumptions), n-ary recursion (note n can vary), combinatorial problems e.g. partitions of an integer n>=0.

Week 13 starts Monday 31 May ([Prac5B])

[Design] principles, do not do unnecessary work (e.g. use heap, not sorting, in Kruskal's alg'), do not repeat work (e.g. use D[,] matrix in edit distance), look for alternative representations (e.g. Ukkonen's O(n.d) edit dist' alg'), balance (e.g. indexed sequential file, and in divide & conquer), greedy strategy (might give an optimal algorithm, can be useful even if not), empirical estimation of complexity.
No lecture. Check notice board for consultation times up to the exam.

--- end ---

Created with "vi (Linux & Solaris)", charset=iso-8859-1

g(0) =	c	= p, say,
g(w) =	aw²+ bw+c	= q,
g(2w) =	4aw²+2bw+c	= r.