# Module 06-22754 (2011)

## Foundations of Computer Science

## Level 1/C

Dan Ghica | Semester 1 | 10 credits |

John Bullinaria | Semester 2 | 10 credits |

Co-ordinator: Dan Ghica

Reviewer: Peter Breuer

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

- Basic imperative programming, e.g.
- Arrays and the for-loop
- Streams and the while-loop
- Macros, subroutines, stacks
- Functions, procedures, and methods
- Values and locations

- Basic abstract data types, e.g.
- Array-based implementation of lists
- Linked list implementation of lists
- Stacks
- Queues

- Abstract data structures, e.g.
- Binary search trees. Representation, insertion, deletion, binary search, traversal.
- Heap-trees. Array representation, applications in priority queues and sorting.
- Graphs. Pointer and array-based representations.
- Sets. Representations, typical problems, some algorithms.
- Balanced binary search trees. Representation, insertion, deletion.
- Multiway Trees. B-trees, tries.

- Algorithms
- Complexity classes. Main definition, understanding of the main classes occurring in practice, determining the complexity class of a given algorithm.
- Sorting. Principles of sorting, sorting by comparison and its complexity. The main sorting algorithms (e.g., Insertion Sort, Selection Sort, Bubblesort, Heapsort, Quicksort, Mergesort), their applicability to different data structures, their complexity, strengths and weaknesses. Sorting by distribution.
- Searching. Sequential and binary searching, suitable data structures.
- Graph algorithms. Shortest path, spanning tree, traversal.
- Storing. Tables and hashing, chaining and open addressing collision handlers. Storing in trees.

### 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 [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]