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

Lecture notes/slides (2016)

The lecture material closely follows the recommended textbook: An Introduction to Algorithms and Data Structures (4th edition) by M.J. Dinneen, G. Gimel'farb and M.C. Wilson (2016). The course follows the textbook closely. This free electronic edition of the textbook has been revised and shortened by Dr. Michael Dinneen in line with the current curriculum and placed in the Resource section of the course page.

Weekly schedule and venue

This schedule is current as per 28 Feb 2016. Please check Student Services Online for any updates.

• Wednesday 3 - 4 pm, MLT1 (303-G23)
• Thursday 4 - 5 pm, ENG 1401 (401-401)
• Friday 2 - 3 pm, MLT1 (303-G23)

Lecture Recordings

Like Internet packet delivery, this is a "best effort" service only, and the recording may fail or have poor quality for some lectures. Also, since the recording starts automatically, the first four or five minutes might be "noise". By the today's University regulations, the recorded lectures must be posted only via CANVAS (see Modules section).

Due to an unforeseen technical problem, our regular recording started only on Wednesday, March 9 (from Lecture 04). In addition, a low-quality manually organised recording of Lecture 02 is posted on CANVAS, too.

Planned lecture topics by date

• Lecture slides and notes will be available from this web page (click blue lecture titles).

• Week 1: 29 Feb - 04 Mar 2016
  1. 02/03: Course introduction; math background: sets; logarithms; series, etc.
  2. 04/03: Analysing complexity of algorithms: Basic concepts and definitions.
  3. 05/03: Running time evaluation: Quadratic vs. linear time.
• Week 2 : 07 Mar - 11 Mar 2016
  4. 09/03: "Big-Oh", "Big-Omega", and "Big-Theta": Properties and rules.
  5. 10/03: Running time evaluation: Worst-case and average-case performance.
  6. 11/03: Recurrent algorithms: Divide-and-conquer principle.
• Week 3: 14 Mar - 18 Mar 2016
  7. 16/03: Efficiency of data sorting: Insertion sort
  8. 17/03: Insertion sort: Analysis of complexity
  9. 18/03: Mergesort: Big Theta(n log n) complexity.
• Week 4: 21 Mar - 24 Mar 2016 (Easter break: 25 Mar - 29 Mar 2016)
  10. 23/03: Quicksort: Analysis of complexity.
  11. 24/03: Heaps, heap operations, and Heapsort.
• Week 5: 30 Mar - 01 Apr 2016
  12. 31/03: Data selection. Lower complexity bound for sorting.
  13. 31/03: Data searching and binary search.
  14. 01/04: Binary search trees and balanced trees.
• Week 6: 04 Apr - 08 Apr 2016
  15 - 17. 06/04 - 08.04: Hash tables: basics; collision resolution; universal hashing.
• Week 7: 11 Apr - 15 Apr 2016
  • 13/04: No lecture.
  • 14/04: Mid-semester test   in lecture time, 4:05 - 4:55 pm.
  • 15/04: no lecture.
• Week 8: 18 Apr - 22 Apr 2016: Mid-semester break
• Week 9: 25 Apr - 29 Apr 2016
  18 - 20. 27/04 - 29/04: (Di)graphs definitions. Graph ADT and implementations. Traversal algorithms and depth-first search.
• Week 10: 02 May - 06 May 2016
  21 - 23. 04/05 - 06/05: Breadth-first and priority-first search. DAGs, topological sorting. Connectivity and strongly connected components.
• Week 11: 09 May - 13 May 20916
  • 11.05: No lecture (Graduation day)
  24 - 26. 12/05 - 13.05: Cycles, girth, graph colouring. Bipartite graphs (2-colouring; matching). Edge-weighted digraphs. Optimisation.
• Week 12: 16 May - 20 May 2016
  27 - 29. 18/05 - 20/05: Single-source shortest paths: Dijkstra's and Bellman-Ford algorithm. All-pairs shortest paths: Floyd's algorithm.
• Week 13: 23 May - 27 May 2016
  30 - 32. 25/05:- 27/05 Minimum spanning trees: Prim's and Kruskal's algorithms. Examples of (harder) graph problems.
• Week 14: 30 May - 03 June 2016
  33 - 34. 01/06: Course review. (only new slides; other review materials (mostly, examples of solutions and algorithms) are copied from the above lectures 01 - 32).
  • 02/06: no lecture.
  • 03/06: no lecture.