Algorithms and Data Structures: COMPSCI 220 Semester 2, City Campus

Note that there will be no lectures in the first week of semester. You are expected to use this time to review the material on the Maths Checklist and in Appendix E of the textbook.

Lecture notes/slides

The lecture material closely follows the required textbook: An Introduction to Algorithms, Data Structures and Formal Languages (2nd edition) by M.J. Dinneen, G. Gimel'farb and M.C. Wilson (Pearson NZ). Reporting new errors will earn you a small bonus for your course grade.
Note that the course content has changed in 2010. We will not be covering Part III of the textbook, Formal Languages.

Below is an approximate lecture schedule. We will stick to the textbook quite closely but will not cover all topics as they appear in the book. Read the corresponding sections in the textbook before lectures and bring the book to class.

First week

Tuesday 19 July, Wednesday 20 July, Friday 22 July: No lectures. The programme for this week is self-study. Please review the Maths Checklist and Appendix E of the textbook. Come Week 2, you need to be familiar with the content there.

Part 1 and 2 (Mark Wilson)

• Chapters 1 and 2 (with strong reference to Appendix E).
• Lecture slides and notes are available from the 220 Resource pages on Cecil.
• 1. 26 July: Algorithm and data structure overview
  2. 27 July: Algorithm Analysis: what and why, limitations
  3. 29 July: Algorithm Analysis: simple examples
  4. 2 Aug: Algorithm Analysis: asymptotic notation, big-Oh, big-Theta, big-Omega
  5. 3 Aug: Array-based lists
  6. 5 Aug: Linked lists
  7. 10 Aug: Stack/Queue ADT
  8. 11 Aug: The problem of Sorting; lower bound on comparison-based sorting
  9. 12 Aug: Quadratic sorting algorithms: selection sort, insertion sort
  10. 16 Aug: Useful recurrence relations; mergesort
  11. 17 Aug: Quicksort, including average-case analysis
  12. 19 Aug: Binary Trees (full, complete, balanced); generalize to m-ary trees
  13. 23 Aug: Binary Trees (preorder, inorder, postorder): tree traversal with iterator
  14. 24 Aug: Binary Heaps, Heapsort
  15. 26 Aug: Priority Queues, selection
  • 30 Aug: Mid-semester break
  • 31 Aug: Mid-semester break
  • 2 Sep: Mid-semester break
  • 6 Sep: Mid-semester break
  • 7 Sep: Mid-semester break
  • 9 Sep: Mid-semester break
  16. 13 Sep: The problem of Searching. Table ADT. Binary search
  17. 14 Sep: Binary Search Trees (balancing); AVL, Red-Black, AA, B-Tree
  18. 16 Sep: Mid-semester test (in lecture time)

Part 3 (Nevil Brownlee)

• Chapter 3.
• Lecture slides are available from the 220 Lectures page on Cecil
• 19. 20 Sep: Hash Tables: basics
  20. 21 Sep: Hash Tables: collision resolution
  21. 23 Sep: Hashing: probabilistic analysis

Part 4 (Ulrich Speidel)

• Chapters 4, 5 and 6
• Lecture slides and notes: To be advised.
• 22. 27 Sep: Graphs and digraphs definitions (includes free trees)
  23. 28 Sep: Graph ADT and implementations
  24. 30 Sep: Graph traversal algorithms (overview)
  25. 4 Oct: Breadth-first, depth-first, priority-first search
  26. 5 Oct: DAGS, topological sorting
  27. 7 Oct: Graph connectivity; strongly connected components
  28. 11 Oct: Cycles, girth, graph coloring
  29. 12 Oct: Bipartite graphs (2-colouring, matching)
  30. 14 Oct: Edge-weighted digraphs and optimisation problems
  31. 18 Oct: Single-source shortest shortest paths (Dijkstra)
  32. 19 Oct: All-pairs shortest paths (Floyd)
  33. 21 Oct: Minimum spanning trees, review of (harder) graph problems for CS (possibly if we get to this)