Data Structures and Algorithms Data Structures and Algorithms (Level 1/C) Dr John A. Bullinaria j.a.bullinaria@cs.bham.ac.uk 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.
