This module introduces 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.
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 six years provide a good idea of what to expect in this year's examination: 2008, 2009, 2010, 2011, 2012, 2013.
Each week there will be two one-hour lectures:
Plus three optional exercise help sessions for those who need them:
The Continuous Assessment Exercises will be run slightly differently to the first Semester:
There will be one Exercise Sheet per week for the first ten weeks, each contributing equally to the final Continuous Assesssment mark. The Exercise Sheets will be available on the Thursday/Friday of each week (N), with the work to be submitted by 12noon on the Friday of the following week (N+1), and the marked work and feedback available from 12noon on the Friday of the week following that (N+2).
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 that 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 (based on earlier versions created by Martín Escardó and Manfred Kerber) 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
Lectures 2-3 : Arrays, Lists, Stacks, Queues, Sets
Lecture 4 : Efficiency and Complexity
Lectures 5-6 : Trees, Quad Trees, Binary Trees
Lectures 7-8 : Binary Search Trees, B-Trees
Lectures 9-10 : Heap Trees, Priority Queues
Lectures 11-14 : Sorting Algorithms
Lectures 15-16 : Storing and Hash Tables
Lectures 17-21 : Graphs
Lectures 22-23 : 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.
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 Algorithms with Object-Oriented Design Patterns in Java | Bruno R. Preiss | Wiley, 1999 | Freely available online |
| Data Structures and Algorithms in Java | Michael Goodrich & Roberto Tamassiar | Wiley, 2010 | 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 two free books and other freely available online resources should be sufficient for most students.
| Abstract data types | Arrays | ||
| Linked lists | Stacks | ||
| Queues | Sets |
Further links will be added to this list as the module progresses.