Concepts of Computation
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.
To provide students with the basic mathematical and algorithmic tools of Computer Science.
- 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
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.
By 2-hour written examination and quizzes, weighted at 90% and 10% respectively.
David Makinson, Sets, Logic and Maths for Computing. 2012, Springer
Seymour Lipschutz, Marc Lipson. Schaum's Outline of Discrete Mathematics. 3rd ed 2009