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
Timetables
Indicative timetables can be found in the handbooks available on programme pages. Personalised teaching timetables for students are available via My Birkbeck.
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. 3rd ed 2009