Lectures

• Tuesday 11:35 am - 1:25 pm: Tamaki Lecture Theatre 731.201 (10 min break)
• Thursday 12:35 pm - 1:25 pm: Tamaki Lecture Theatre 721.201

If you miss a lecture, it is your responsibility to catch up the material. Ask your lecturer for help.

Lecture schedule / lecture notes / handouts

This schedule is provisional and might be amended (e.g. due to students feedback)

• Brief course overview
• Part A: Introduction to Algorithm Analysis (Lecturer - Dr Mike Barley; textbook - Part I)

  Day	Lecture	Topic	Colour slides	Lecture notes
  March 3, 2009	1	Efficiency of Algorithms	Slides 01
  March 5, 2009	2	Big-Oh, Big-Omega, and Big-Theta Tools	Slides 02
  			Big Oh examples
  March 11, 2008	4	Time Complexity of Algorithms	Slides 04	Notes 04
  	5	Basic Recurrence Relations	Slides 05	Notes 05
  			Telescoping: an example
  March 13, 2008	-	[(No lecture - all CS Department lectures cancelled)]
  March 18, 2008	6	Complexity of Insertion and Shell's Sort	Slides 06	Notes 06
  			Lect. 1-6: exercises with solutions
  	7	Complexity of Mergesort and QuickSort	Slides 07	Notes 07
  March 20, 2008	8	Complexity of Heapsort	Slides 08	Notes 08
  March 25, 2008	-	[University holiday: no lectures and tutorials]
  March 27, 2008	9	Lower Bound for Sorting Complexity; Data Search	Slides 09	Notes 09
  April 1, 2008	10	Binary Search Trees	Slides 10	Notes 10
  	11	Symbol Tables and Hashing	Slides 11	Notes 11
  			Lect. 7-11: exercises with solutions
  			(i) Sorting: Java SortMeth class
  			(ii) Java program TestFibonacciNum to compare iterative and recursive computation of Fibonacci numbers

  Additional reading: a comprehensive set of animated notes prepared by Associate Professor John Morris in 1998.
  Although the curriculum covered by these notes differs from our course, you will find many useful discussions
  and very interesting examples and animations (if some of them are not working, please, report to the author: his mail is on the bottom of his text).

• Part B: Introduction to Graph Algorithms (Lecturer - Dr Mark Wilson; textbook: Part II)

  Day	Lecture	Topic
  2008-04-03	12	The Graph ADT
  2008-04-08	13	Graph data structures
  	14	Graph traversals, BFS and DFS
  2008-04-10	15	Applications of BFS/DFS
  2008-04-22	16	Applications of BFS/DFS
  	17	Applications of BFS/DFS
  2008-04-24		MIDTERM TEST
  2008-04-29	18	Weighted graphs
  	19	SSSP
  2008-05-01	20	APSP
  2008-05-03	21	MST
  	22	Other graph problems

  • Lecture slides, as used in lecture, are available. They are under continual improvement, so don't look too far ahead of the current lecture material. They will be in final form by the end of the lecture period.
  • Handout versions will also be made available: Graphs | Graph traversal applications | Weighted graphs

• Part C: Automata and Pattern Matching (Lecturer - Prof. Cristian (Cris) S. Calude; textbook - Part III). Lectures notes and supporting material