^CSE2304^ <2002< [plan]

## CSE2304 Algorithms and Data Structures, Progress 2003

### NB. 16/1/2003 Provisional: Subject to change!

 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] [21/22] [23/24] 2/2003: The notes are for sale in the bookshop

## Week 1 starts Monday 3 March 2003

• 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, and use(!), the [unix prac] system.

## Week 2 starts Monday 10 March 2003 (Prac 0, Tute 1)

• Lecture 3 Wed' : Logic for program verification = correctness + termination (e.g. on a familiar algorithm)
• Lecture 4 Fri' : Logic for program verification (e.g. on two familiar sorts)

## Week 3 starts Monday 17 March 2003 (Prac 1A, Tute 1)

• Lecture 5 Wed' : (i) the heap, (ii) priority queue (by heap), (iii) heap sort, its complexity etc.
• Lecture 6 Fri' : other fast sorting algorithms: merge sort, and (dutch national flag for) quick sort ...

## Week 4 starts Monday 24 March 2003 (Prac 1B, Tute 2)

• Lecture 7 Wed' : ... finish quick sort and then start edit-distance
• Lecture 8 Fri' : Hirschberg's algorithm, divides and conquers, O(m*n)-time, but only O(n)-space.

## Week 7 starts Monday 14 April 2003

• Lecture 13 Wed' : String search algorithms, naive, Rabin's and (the key idea of) Boyer & Moore's

NB. Easter Friday 18 April - Sunday 27 April 2003

## Week 8 starts Monday 28 April 2003 (Prac 3A, Tute 3)

• Lecture 14 Wed' : Graphs
• Lecture 15 Fri' : Dijkstra's single-source shortest paths algorithm, Warshall's transitive closure,...

## Week 13 starts Monday 2 June 2003 (Prac 5B)

Semester 1 ends Friday 6 June 2003.

© L. Allison, School of Computer Science and Software Engineering, Monash University, Australia 3800.
Created with "vi (Linux & Solaris)",   charset=iso-8859-1