CSE2304 Algorithms and Data Structures, Progress 2003

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

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 5 starts Monday 31 March 2003 (Prac 2A, Tute 2)

• Lecture 9 Wed' : Lookup tables
• Lecture 10 Fri' : AVL-trees

Week 6 starts Monday 7 April 2003 (Prac 2B, Tute 3)

• Lecture 11 Wed' : Tries, PATRICIAs
• Lecture 12 Fri' : 2-3-trees, 2-3-4-trees leading to B-trees

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 9 starts Monday 5 May 2003 (Prac 3B, Tute 4)

• Lecture 16 Wed' : ... Floyd's all-pairs shortest paths algorithm.
  Minimum Spanning Trees, Prim's algorithm &...
• Lecture 17 Fri' : ... Kruskal's algorithm

Week 10 starts Monday 12 May 2003 (Prac 4A, Tute 4)

• Lecture 18 Wed' : Directed acyclic graphs (DAGs)
• Lecture 19 Fri' : Suffix trees (and ``Woolloomooloo''), now try Suggan Buggan, Boomahnoomoonah, Waaia,...

Week 11 starts Monday 19 May 2003 (Prac 4B, Tute 5)

• Lecture 20 Wed' : recursion (to binary r') ...
• Lecture 21 Fri' : ... n-ary recursion.
  design techniques...

Week 12 starts Monday 26 May 2003 (Prac 5A, Tute 5)

• Lecture 22 Wed' : ... design techniques continued
• Lecture 23 Fri' : numerical ...

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

• Lecture 24 Wed' : ... integration (slide 7+)
• Fri' : --- no lecture ---

Semester 1 ends Friday 6 June 2003.