CSE2304 Progress 2000

CSE2304 Algorithms and Data Structures, Progress 2000

Semester [dates] and [holidays]

#1: 17 March 2000, #2: 31 March 2000, #3: 14 April 2000, #4: 5 May 2000, #5: 19 May 2000.

L.Allison

This record will be added to after each lecture.

Lecture 1: (Wed' 1 March 2000)
Administrivia, lectures, prac's, tutes, assessment. Abstract data type (ADT), examples, notation.
Lecture 2: (Fri' 3 March 2000)
ADT's, examples, ADT List, ADT Tree, parse tree, applications.

A strike was called in an industrial dispute between staff and Monash (au). Lecture 3 was therefore given, with part of #4, on Friday 10/3.

Lecture 3 (Wed' 8 March 2000)
Program proof using assertions, pre|post-conditions and loop invariants, (i) proof if terminates and (ii) terminates.
Lecture 4 (Fri' 10 March 2000)
Selection sort and insertion sort, not so much for themselves but as examples or case studies for program proof.

Lecture 5 (Wed' 15 March 2000)
The heap data structure and priority queues, time complexity. Use in heap sort. Heap sort's properties.
Lecture 6 (Fri' 17 March 2000)
Divide and conquer sorts: merge sort, quick sort. Partitioning and the Dutch national flag problem.

Lecture 7 (Wed' 22 March 2000)
Edit distance problem definition, example, applications, solution by dynamic programming strategy.
Lecture 8 (Fri' 24 March 2000)
Hirschberg's algorithm for edit-distance, another example of divide and conquer, trades time (x2) for space (O(n²)--->O(n)).

Lecture 9 (Wed' 29 March 2000)
The Abstract Data Type (ADT) Table - clear, insert, delete, search and ?empty? Can be Implemented in various ways.

NB. Crash revision course in hashing and in [Quadratic probing], covered in lecture#11.

Lecture 10 (Fri' 31 March 2000)
AVL-tree is height balanced (+/-1), insertion may require rebalancing; there are Left-2, Left-3, Right-2 and Right-3 cases. (NB. AVL-tree deletion not examinable.)

Lecture 13: (Wed' 12 April 2000)
Searching for a substring pattern in a text - naive, Rabin's, and Boyer-Moore algorithms.
Lecture 14: (Fri' 14 April 2000)
Graphs, directed / undirected, weighted / unweighted.

Lecture 15: (Wed' 19 April 2000)
Dijkstra's single-source shortest paths algorithm, Warshall's transitive closure (connectivity) algorithm, & Floyd's all-pairs shortest paths algorithm.

Easter: Friday 21 April - Friday 28 April (Sunday 30 April) 2000
Anzac Day: Tuesday 25 April 2000

Some solutions for tutes [#1 to #3 (click)].

Lecture 16: (Wed' 3 May 2000)
Minimum Spanning Trees, Prim's algorithm (c.f. Dijkstra's paths alg').
Lecture 17: (Fri' 5 May 2000)
Minimum spanning tree, Kruskal's algorithm, vertex partition / union-find.

Lecture 18: (Wed' 10 May 2000)
Directed acyclic graph (DAG), topological sort, critical path analysis.
Lecture 19: (Fri' 12 May 2000)
The suffix tree data structure and its applications.

Lecture 20: (Wed' 17 May 2000)
1. problem solving: given A[size], i, j, and k, efficiently(!) exchange A[i..j-1] with A[j..k-1]

e.g. A[ ] = -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 and i=4, j=8, k=14

A[ ] -> -3, -2, -1, 0, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 11, 12, 13 --after

2. Linear recursion, time complexity, recurrence relation (proof by induction), recursion removal by iteration with stack, tail recursion (to slide 9).
Lecture 21: (Fri' 19 May 2000)
Continue lecture #20 at Binary recursion (10), complexity. N-ary recursion . . .

Lecture 22: (Wed' 24 May 2000) [Continue 20/21]
. . . e.g. N-queens problem. Design principles (L #21) . . .
Lecture 23: (Fri' 26 May 2000)
1. Continue L #21 from `balance', slide 8.
2. L #23: Numerical computation, IEEE floating point standard, limited accuracy . . .

Lecture 24: (Wed' 31 May 2000)
. . . more numerical computation, solving f(x)=0, numerical integration.
Lecture 25: (Fri' 2 June 2000) Revision.

e.g.	A[ ] =	-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 and i=4, j=8, k=14
e.g.	A[ ] ->	-3, -2, -1, 0, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 11, 12, 13 --after