Fundamentals of Computing
Discrete mathematics, mathematical 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.
- Digital logic. Arithmetic for computers.
- Elements of set theory.
- Finite state machines (automata). Nondeterministic automata.
- Regular languages.
- Context-free languages and pushdown automata.
- Turing machines. Universal Turing machines. Undecidable problems.
- Data structures: representations and operations.
- Lists, stacks, queues and deques.
- Trees, forests, binary trees.
- Tree traversal and other operations; binary search trees.
- Organisation of disk storage; methods of file organisation; B-trees.
- Design and analysis of algorithms. Sorting and searching.
Students taking this module must be also be currently taking (or have previously taken) a suitable programming module (Programming in Java, or Introduction to Software Development). With the permission of the Programme Director, other students may take this module if they have equivalent appropriate programming experience.
AssessmentBy 3-hour written examination and coursework exercises, weighting 80% and 20% respectively.
- D. Patterson and J. Hennessy, Computer Organization and Design: The Hardware/Software Interface. Morgan Kaufmann; 3 edition, 2007
- E. Kinber and C. Smith, Theory of Computing. A gentle introduction. Prentice Hall, 2001