Fundamentals of Computing

• Credit value: 15 credits at Level 7
• Convenor: Professor Michael Zakharyaschev
• Assessment: problem-solving worksheets (20%) and a two-hour examination (80%)

Discrete mathematics, computer arithmetic and logic, and the related fundamental areas of data structures and algorithms, lie at the heart of any modern study of computer science. Any understanding of how computers operate and how to use them effectively and efficiently, in terms of either their hardware or software, inevitably involves numerous mathematical concepts.

In this module we introduce and develop mathematical notions, data structures and algorithms that are used in various areas of computer science, in particular those required for other modules of the programme.

Indicative syllabus

• Arithmetic for computers
• Digital logic
• Elements of set and graph theories
• Finite state machines (automata) and regular languages
• Turing machines
• Algorithms: design and analysis; computational complexity; data structures
• Sorting and searching; algorithms on graphs

By the end of this module, you will understand:

• the mathematical and algorithmic foundations of computing
• fundamental models of computation, computer arithmetic and logic
• commonly encountered data structures and algorithms
• the notion of algorithmic complexity and how it affects the efficiency of programs.