University of Auckland    Department of Computer Science     Courses    COMPSCI 220 SC    Lectures  Web Site Map

Lectures

Times: Tuesday, Thursday, Friday 4pm
Place: MLT1 (Maths/Physics building)
There will be 11 lectures in each section. The lecture to be cancelled will be announced by the lecturer.

Lecture notes/slides

The lecture material closely follows the required textbook: An Introduction to Algorithms, Data Structures and Formal Languages 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.

Nevil's Lectures

  • Lecture slides are available. They are constantly under development.
  • Below is an approximate lecture schedule. We will not cover all topics in the textbook Section A, but will stick to the book quite closely. Please read the corresponding sections in the textbook before lectures, and bring the book to class.
    1. What is algorithm analysis? Motivating examples.
    2. Estimating running time of simple algorithms. Why we measure running time asymptotically.
    3. Techniques for using asymptotic notation.
    4. The problem of sorting. Quadratic time sorting methods.
    5. Recursive sorting methods: Mergesort, Quicksort. Some useful recurrences and elementary methods of solution.
    6. Quicksort.
    7. Heapsort. Selection. Lower bound on comparison-based sorting complexity.
    8. The problem of searching. Table ADT. Binary search. Binary search trees.
    9. Hashing.
    10. Selected topic/overflow.
    11. Selected topics/overflow.

Michael Dinneen's Lectures

  • Lecture slides are available in interactive form and handout form.
  • Below is an approximate lecture schedule. Please read the corresponding sections in the textbook before lectures.
    1. Basic graph definitions.
    2. Graph ADT (data structures) and their implementations.
    3. Graph traversals.
    4. BFS and DFS details. Priority-first search.
    5. Acyclic digraph. Topological ordering.
    6. Graph connectivity.
    7. Girth. Bipartite graphs. Graph coloring.
    8. Weighted digraphs. Distance and diameter.
    9. Single-source shortest path problem.
    10. All-pairs shortest path problem.
    11. Minimum spanning tree problems.
    12. Hard graph problems. Overflow and review.

Cris Calude's Lectures

  • Lecture slides are available at Cris' local 220 page.
  • Below is an approximate lecture schedule. Please read the corresponding sections in the textbook before lectures.
    1. Introduction to finite state machines.
    2. DFA and languages accepted.
    3. Properties of DFAs and regular languages.
    4. More examples of DFA.
    5. The idea of nondeterminism.
    6. Properties of NFA.
    7. L(NFA) = L(DFA) = regular languages.
    8. Examples of NFA.
    9. Minimizing automata.
    10. Patern matching.
    11. Review.

Jump to

Quick links

Index
Course Page
People

Lectures
Tutorials

Assignments
Tests and Exams

Resources

Handbook
Personal Profile

Cheating Policy

Search: