The module as a whole is designed to introduce the fundamental concepts of Computer Science, such as the representation of data in computer memory, programming constructs, data models and data structures, and the analysis of algorithms. The ideas will be presented abstractly, although examples will be given in the language used in the parallel programming workshop modules. This half-module will concentrate on studying the development of efficient data structures and algorithms.
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.
You should be spending approximately 100 hours in total on the second semester half of this module, including 2 to 4 hours per week on the Continuous Assessment exercises.
Part B of the examination papers for the last seven years provide a good idea of what to expect in this year's examination: 2008, 2009, 2010, 2011, 2012, 2013, 2014.
Each week there will be two one-hour lectures:
* Mondays 12noon - Aston Webb WG05.
* Thursdays 2pm - Law LT1.
Plus three optional one-hour exercise help sessions for anyone who needs them:
* Tuesdays 12noon - Weeks 2-11: Mech Eng B04.
* Thursdays 4pm - Weeks 2-11: Law LT2.
* Fridays 1pm - Weeks 2-11: Mech Eng B04.
The Continuous Assessment Exercises will be run slightly differently to the first Semester:
There will be one assessed Exercise Set per week for the first ten weeks, with a little over one week to complete each of them. The Exercise Sets will be available on the Thursday/Friday of each week (N), with the work to be submitted in .pdf format via the Canvas VLE by 11pm on the Sunday of the following week (N+1). The marks and feedback will be available from 11pm on the Sunday of the week following that (N+2). Each Exercise Set will contribute equally to the final Continuous Assesssment mark, with the total mark computed by simple averaging of the individual marks.
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 Exercise deadline, you will receive a mark of zero for that exercise. If you think you had a good excuse, you need to convince the Welfare Team to inform the markers to waive the exercise because you had acceptable mitigating circumstances.
Further details about the exercises and associated help sessions will be given in the first lecture.
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 term.
The lecture schedule is roughly:
Lecture 1 : Introduction
Lecture 2 : Arrays, Lists, Stacks, Queues, Sets
Lecture 3 : Searching Algorithms
Lecture 4 : Efficiency and Complexity
Lectures 5-6 : Trees, Quad Trees, Binary Trees
Lectures 7-8 : Binary Search Trees, B-Trees
Lectures 9-10 : Priority Queues and Heap Trees
Lectures 11-14 : Sorting Algorithms
Lectures 15-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 1 (12 January) : Introduction, Arrays
Module web-site, Lecture notes sections 1.1 - 1.5, 2.1
Lecture 2 (15 January) : Lists, Stacks, Queues
Lecture notes sections 2.2 - 2.4
Lecture 3 (19 January) : Doubly linked lists, Sets, Searching
Lecture notes sections 2.5 - 2.6, 3.1 - 3.4
Lecture 4 (22 January) : Efficiency and Complexity, Trees in general
Lecture notes sections 4.1 - 4.5, 5.1
Lecture 5 (26 January) : Quadtrees, Binary Trees
Lecture notes sections 5.2 - 5.4
Lecture 6 (29 January) : Binary Tree Algorithms, Binary Search Trees
Lecture notes sections 5.5 - 5.7, 6.1 - 6.4
Lecture 7 (2 February) : Binary Search Tree Algorithms
Lecture notes sections 6.5 - 6.8
Lecture 8 (5 February) : Self Balancing BSTs, B-Trees, Trees as arrays
Lecture notes sections 6.9 - 6.11, 7.1
Lecture 9 (9 February) : Priority Queues and Heap Trees
Lecture notes sections 7.2 - 7.4
Lecture 10 (12 February) : Binary Heapify algorithm; Binomial and Fibonacci Heaps
Lecture notes sections 7.5 - 7.7
Lecture 11 (16 February) : Sorting Strategies, O(n^2) Sorting Algorithms
Lecture notes sections 8.1 - 8.7
Lecture 12 (19 February) : Stability, Tree Sort, Heapsort
Lecture notes sections 8.8 - 8.9
Lecture 13 (23 February) : Divide and conquer algorithms, Quicksort
Lecture notes sections 8.10 - 8.11
Lecture 14 (26 February) : Merge Sort, Comparison Sort Comparisons
Lecture notes sections 8.12 - 8.13
Lecture 15 (2 March) : Non-Comparison Sorts; Introduction to Hash Tables
Lecture notes sections 8.14 - 8.15, 9.1 - 9.6
Lecture 16 (5 March) : Hash Table Collisions and Efficiency
Lecture notes sections 9.7 - 9.10
Lecture 17 (9 March) : Applications of Hash Tables
Guest Lecture by Bram Geron (Slides)
Lecture 18 (16 March) : Graphs: Representations, Planarity, Traversals
Lecture notes sections 10.1 - 10.5
Lecture 19 (23 March) : Shortest Paths, Dijkstra's and Floyd's Algorithms, TSP and VRP
Lecture notes sections 10.6 - 10.7, 10.9
Lecture 20 (26 March) : Minimal Spanning Trees, Epilogue and Overview
Lecture notes sections 10.8, 11
Lecture 21 (30 April) : Revision Lecture
Overview of everything covered in the module (Checklist)
The Recommended Books for this part of the module are:
| Title | Author(s) | Publisher, Date | Comments |
|---|---|---|---|
| Foundations of Computer Science | Al Aho & Jeff Ullman | Freeman, 1992 | Freely available online |
| Data Structures and Algorithm Analysis | Clifford A. Shaffer | Dover, 2011 | Freely available online |
| Fundamental Data Structures | Wikipedia Authors | Wikipedia, 2014 | 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:
| Sorting Algorithms with Sound Effects |
Further links will be added to this list as the module progresses.
