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.
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.
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
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.
The Assignments and Model Answers will be posted here as they become available.
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.
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)
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.
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.
