Data Structures and Algorithms (Level 1/C)

Dr John A. Bullinaria

I no longer teach this module, but this web-page is now sufficiently widely used that I will leave it in place. It was the main source of information for the module, containing all the lecture notes, assignments and model answers, links to external resources, details about the continuous assessment and examination, and so on, for the academic year 2017/18.

Module Outline

This module will introduce the principal fundamental data structures and algorithms used in computer science. Data structures will be formulated to represent information in such a way that it can be conveniently and efficiently manipulated by the algorithms that are developed. The ideas will be presented abstractly, although examples will be given in the language used in the programming workshop module.

Aims, Learning Outcomes and Assessment

For formal details about the aims, learning outcomes and assessment you should look at the official Module Description and Syllabus.

The module is assessed by 80% Examination and 20% Continuous Assessment.

There are only two past examination papers for this module: 2016 and 2017. However, Part B of the Foundations of Computer Science examination papers for the five years before that also provide good examples of what to expect in this year's examination: 2011, 2012, 2013, 2014, 2015.

If you fail this module at first attempt, there will be an opportunity to resit it by examination only in August, or you can repeat the whole module the following year.

Lecture and Help Session Times and Locations

Each week there will be two one-hour lectures:

* Tuesdays 12noon - Law LT1 (303)

* Tuesdays 4pm - Avon Room

Plus two optional one-hour help sessions for anyone who needs them:

* Mondays 12noon - Weeks 2-11 - Education Vaughan Jeffreys (135)

* Thursdays 4pm - Weeks 2-11 - Muirhead G15

Continuous Assessment Assignments

There will be four marked Assignments. The first will provide feedback but not contribute to the final module mark. The other three will contribute equally to the Continuous Assessment mark which is 20% of the overall module mark. An Assignment will be published on the Friday of each of weeks 1, 3, 5, 7, with your work to be submitted in .pdf format via the Canvas VLE by 5pm on the Monday just over two weeks later. Model answers will be made available shortly after each deadline. Marks and feedback will be available within two weeks of each deadline. A fifth Assignment will be published in week 9, with model answers provided in week 11, but that will not be marked and will not contribute to your module mark.

The easiest way to produce your answers will probably be by using a word processing package such as Microsoft Word or the free OpenOffice Writer. To save the time it can take to produce nice diagrams in those packages, a selection of relevant diagrams has been collected together in a Microsoft Word File for you to cut, paste and edit to produce your answers.

If you miss an Assignment deadline, you will receive a mark of zero for that Assignment. If you think you had a good excuse, you need to convince the Welfare Team to inform the module lecturer to waive the Assignment because you had acceptable mitigating circumstances.

Further details about the Assignments and associated help sessions will be given in the first lecture.

Assignments and Model Answers

The Assignments and Model Answers will be posted here as they become available.

Assignment 1 - Solutions

Assignment 2 - Solutions

Assignment 3 - Solutions

Assignment 4 - Solutions

Assignment 5 - Solutions

Lecture Plan

The material in the Lecture Notes will be followed quite closely. A paper copy will be distributed by the School Office in the first week of spring term.

The lecture schedule is roughly:

Lecture 1 : Introduction

Lecture 2 : Arrays, Iteration, Invariants

Lecture 3 : Lists, Recursion, Stacks, Queues, Sets

Lecture 4 : Searching

Lecture 5 : Efficiency and Complexity

Lectures 6-7 : Trees, Quad Trees, Binary Trees

Lectures 8-9 : Binary Search Trees, B-Trees

Lectures 10-11 : Priority Queues and Heap Trees

Lectures 12-15 : Sorting Algorithms

Lectures 16-17 : Storing and Hash Tables

Lectures 18-20 : Graphs

Lecture 21 : Overview of Whole Module

Each lecture will work through the relevant section of the notes, providing additional details, explanations and examples on the board. Remember to bring your copy of the lecture notes to each lecture! You will need to augment the printed lecture notes with your own notes made during the lectures. There will be plenty of time set aside in the lectures for answering your questions. The whole process will be most successful if you take the time to read through the relevant section of the lecture notes before each lecture. You should also seek clarification from books and web-sites that cover the same topics in slightly different ways.

Lecture Log

This will be updated after each lecture.

Lecture 1 (9 January) : Introduction, Arrays, Iteration
Module web-site, Lecture notes sections 1.1 - 1.5, 2.1 - 2.2

Lecture 2 (9 January) : Invariants, Lists, Recursion
Lecture notes sections 2.3, 3.1 - 3.2

Lecture 3 (16 January) : Stacks, Queues, Sets, Searching a list
Lecture notes sections 3.3 - 3.6

Lecture 4 (16 January) : Search Algorithms, Efficiency and Complexity
Lecture notes sections 4.1 - 4.4, 5.1 - 5.3

Lecture 5 (23 January) : Complexity Classes, Trees, Quad Trees
Lecture notes sections 5.4 - 5.5, 6.1 - 6.2

Lecture 6 (23 January) : Binary Trees
Lecture notes sections 6.3 - 6.8

Lecture 7 (30 January) : Binary Search Trees
Lecture notes sections 7.1 - 7.6

Lecture 8 (30 January) : BSTs: Deletions, Checking and Outputting
Lecture notes sections 7.7 - 7.8

Lecture 9 (6 February) : Balancing BSTs, B-Trees, Trees as Arrays
Lecture notes sections 7.9 - 7.12, 8.1

Lecture 10 (6 February) : Priority Queues and Heap Trees
Lecture notes sections 8.2 - 8.5

Lecture 11 (13 February) : Heapify, Merging, Binomial Trees and Heaps
Lecture notes sections 8.6 - 8.8

Lecture 12 (13 February) : Fibonacci Heaps, Sorting Strategies, O(n^2) Sorting Algorithms
Lecture notes sections 8.9 - 8.10, 9.1 - 9.7

Lecture 13 (20 February) : Stability, Tree Sort, Heapsort
Lecture notes sections 9.8 - 9.10

Lecture 14 (20 February) : Divide and Conquer Algorithms, Quicksort
Lecture notes sections 9.11 - 9.12

Lecture 15 (27 February) : Merge Sort, Sort Comparisons, Non-Comparison Sorts
Lecture notes sections 9.13 - 9.16

Lecture 16 (27 February) : Introduction to Hash Tables
Lecture notes sections 10.1 - 10.7

Lecture 17 (6 March) : Hash Table Collisions and Efficiency
Lecture notes sections 10.7 - 10.11

Lecture 18 (6 March) : Graphs: Representations, Planarity, Traversals
Lecture notes sections 11.1 - 11.5

Lecture 19 (13 March) : Shortest Paths: Dijkstra's and Floyd's Algorithms
Lecture notes sections 11.6 - 11.7

Lecture 20 (13 March) : Minimal Spanning Trees, TSP and VRP, Epilogue
Lecture notes sections 11.8 - 11.9, 12

Lecture 21 (24 April) : Revision Lecture
Overview and answers to questions from the audience (Revision Checklist)

Recommended Books

The Recommended Books for this part of the module are:

Title Author(s) Publisher, Date Comments
Data Structures and Algorithm Analysis Clifford A. Shaffer Dover, 2011 Freely available online
Foundations of Computer Science Al Aho & Jeff Ullman Freeman, 1992 Freely available online
Fundamental Data Structures Wikipedia Authors Wikipedia, 2015 Freely available online
Data Structures and Algorithms in Java Michael Goodrich & Roberto Tamassiar Wiley, 2010 Ties in with Java programming
Data Structures and Algorithms with Object-Oriented Design Patterns in Java Bruno R. Preiss Wiley, 1999 Ties in with Java programming
Computer Science: An Overview J. Glenn Brookshear Pearson, 2008/2012 "Comprehensive overview of what computer science is all about"
Data Structures and Algorithms Al Aho, John Hopfcroft & Jeff Ullman Addison-Wesley, 1983 Further Reading
Structure and Interpretation of Computer Programs Harold Abelson, Gerald Sussman & Julie Sussman MIT Press, 1996 Further Reading
Algorithms Richard Johnsonbaugh & Marcus Schaefer Pearson, 2004 Further Reading

The three free books and other freely available online resources should be sufficient for most students.

Useful Links

Whilst online resources like Wikipedia should always be treated with caution, Wikipedia does contain a number of useful entries on the subject of this module, for example:

Algorithms Programming paradigms
Imperative programming Declarative programming
Data structures Abstract data types
Algorithmic paradigms Design Patterns
Greedy algorithms Pseudocode
Collections Arrays
Loops Proof by Induction
Invariants Loop Invariants
Linked lists Recursion
Stacks Queues
Doubly linked lists Sets
Linear Search Binary Search
Computational complexity Big O notation
Trees Quad trees
Binary trees Binary search trees
Self-balancing BST Tree rotation
AVL trees B-trees
Priority queues Heap trees
Binomial heaps Fibonacci heaps
Sorting algorithms External sorting
Bubble sort Insertion sort
Selection sort Tree sort
Heapsort Divide and conquer
Quicksort Merge sort
Radix sort Hash tables
Graphs Graph data structures
Graph homeomorhism Graph connectivity
Planar graphs Kuratowski's theorem
Graph traversals Shortest path problem
Dijkstra's algorithm Floyd's algorithm
Minimal spanning trees Prim's algorithm
Kruskal's algorithm Travelling Salesman Problem
Vehicle Routing Problem Heuristics

Sometimes it is instructive to see a direct comparison of the various sorting algorithms, e.g.:

Sorting Algorithm Comparisons

Sorting with sound effects might be considered more entertaining than educational, e.g.:

Sorting Algorithms with Sound Effects

Further links will be added to this list as the module progresses.

This page is maintained by John Bullinaria. Last updated on 4 September 2018.