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.