# Module 06-22754 (2013)

## Foundations of Computer Science

## Level 1/C

Dan Ghica | Semester 1 | 10 credits |

John Bullinaria | Semester 2 | 10 credits |

### Outline

The module will 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.

### 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:

1 demonstrate understanding of the principles of algorithmic programming

2 demonstrate understanding of abstract models of data and computation

3 make informed choices between alternative ways of implementation, justifying choices on grounds such as time and space complexity or considerations of numerical accuracy

4 explain and apply data structures such as binary trees, heap-trees, graphs and tables, together with their internal representations and relevant algorithms

5 select, with justification, appropriate data structures to ensure efficient implementation of an algorithm (e.g. searching, insertion, deletion or sorting)

6 explain the differences between basic complexity classes of algorithms (constant, linear, quadratic, logarithmic, exponential)

7 argue that algorithms are correct, and derive their time complexity

8 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

Contact Hours: 68

### Assessment

Sessional: 3 hr examination (80%), continuous assessment (20%).

Supplementary (where allowed): 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

- 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]
- MEng Computer Science/Software Engineering [4754]
- MEng Computer Science/Software Engineering with an Industrial Year [9501]
- MSci Computer Science [4443]
- MSci Computer Science with an Industrial Year [9509]
- MSci Computer Science with Study Abroad [5576]
- 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]