# Module 06-22754 (2012)

## Foundations of Computer Science

## Level 1/C

Dan Ghica | Semester 1 | 10 credits |

John Bullinaria | Semester 2 | 10 credits |

Co-ordinator: Dan Ghica

Reviewer: Martin Escardo

The Module Description is a strict subset of this Syllabus Page.

### Aims

The aims of this module are to:

- introduce the fundamental concepts of Computer Science
- support and underpin the programming modules
- introduce advanced abstract data types and standard operations on the same and demonstrate their various representations based on arrays and pointers
- discuss the advantages and disadvantages of the different representations of data types
- introduce the main algorithms for fundamental tasks such as sorting and searching and examine their complexity
- introduce basic concepts of numerical calculations

### Learning Outcomes

On successful completion of this module, the student should be able to:

- explain principles of imperative programming
- explain the importance of abstract models of computation and data
- make informed choices between alternative ways of implementation, justifying choices on grounds such as time and space complexity or considerations of numerical accuracy
- explain and apply data structures such as binary trees, heap-trees, graphs and tables, together with their internal representations and relevant algorithms
- select, with justification, appropriate data structures to ensure efficient implementation of an algorithm (e.g. searching, insertion, deletion or sorting)
- explain the differences between basic complexity classes of algorithms (constant, linear, quadratic, logarithmic, exponential)
- argue that algorithms are correct, and derive their time complexity
- select, with justification, appropriate algorithms for basic tasks such as searching, including reference to the algorithm's complexity class

### Teaching methods

2 hrs lecture, 1 hr exercise class per week

### Assessment

- Sessional: 3 hr examination (80%), continuous assessment (20%).
- Supplementary: By examination only.

### Detailed Syllabus

- Introduction to Semester 1
- Basics of functional programming
- Recursion
- Induction
- Complexity
- Lists
- Numeric data types
- Trees
- Queues
- Combinators
- Functional programming in Java
- Introduction to Semester 2
- Basic data types
- Arrays, Linked-Lists
- Stacks, Queues, Sets

- Efficiency and Complexity
- Measuring efficiency
- Complexity classes and Big-O notation

- Trees
- Representations and primitive operators
- Quad Trees
- Binary Trees
- Binary Search Trees, B-Trees
- Heap Trees, Priority Queues

- Sorting Algorithms
- General principles and strategies
- Insertion Sort, Selection Sort, Bubblesort
- Tree Sort, Heapsort
- Quicksort, Merge Sort
- Non-Comparison Sorts

- Storing Data
- Storing in Trees
- Hash Tables
- Handling Collisions

- Graphs
- Representations
- Traversals and Planarity
- Shortest Paths (Dijkstra's and Floyds' Algorithms)
- Minimal Spanning Trees (Prim's and Kruskal's Algorithms)
- Travelling Salesmen and Vehicle Routing Problems

### Programmes containing this module

- BEng Computer Science/Software Engineering [4753]
- BEng Computer Science/Software Engineering with an Industrial Year [9500]
- BSc Artificial Intelligence & Computer Science [0144]
- BSc Artificial Intelligence & Computer Science with an Industrial Year [9502]
- BSc Computer Science [4436]
- BSc Computer Science with an Industrial Year [9499]
- BSc Computer Science with Business Management [5914]
- BSc Computer Science with Business Management with an Industrial Year [9503]
- BSc Computer Science with Study Abroad [5571]
- BSc Mathematics and Computer Science [5196]
- BSc Mathematics and Computer Science with an Industrial Year [9495]
- BSc Pure Mathematics and Computer Science [5249]
- BSc Pure Mathematics and Computer Science with an Industrial Year [9497]
- MEng Computer Science/Software Engineering [4754]
- MEng Computer Science/Software Engineering with an Industrial Year [9501]
- MSci Mathematics and Computer Science [5197]
- MSci Mathematics and Computer Science with an Industrial Year [9496]
- MSci Pure Mathematics and Computer Science [5256]
- MSci Pure Mathematics and Computer Science with an Industrial Year [9498]