Concepts of Computation

Module outline

Discrete mathematics, mathematical logic and algorithms form the underlying language of computer hardware and software. Digital computers are machines literally built out of memory and logic (logical gates). The same elements appear in all programming languages; hence the importance of this knowledge for understanding information technology. In this module we introduce these areas. The focus will be not just on the technical aspects but also on how these abstract concepts manifest themselves in reality.

Aims

To provide students with the basic mathematical and algorithmic tools of Computer Science.

Syllabus

• Numbers from the digital computer point of view (Binary, Hexadecimal, 2s Complement, Floating Point, Integers)
• Binary Logic and Boolean Circuits
• Sets and the universal and existential quantifiers
• O–notation and the important complexity classes
• Pattern matching and sorting
• Binary search
• Graph algorithms such as Breadth First Search, Depth First Search, Dijkstra’s algorithm
• State machines and regular expressions
• Basic probability
• Histograms

Prerequisites

None

Timetable

All dates and timetables are listed in the programme handbooks of individual programmes.

Coursework

5 Moodle quizzes. Each quiz will cover the material of up to three sessions. The quizzes will be on Moodle and hence automatically checked. This will ensure feedback immediately after the deadline.

Assessment

By 2-hour written examination and quizzes, weighted at 90% and 10% respectively.

Recommended reading

David Makinson, Sets, Logic and Maths for Computing. 2012, Springer

Seymour Lipschutz, Marc Lipson. Schaum's Outline of Discrete Mathematics. 3^rd ed 2009