Skip to content Search
Search our website:

Fundamentals of Computing

Short name: FOC
SITS code: COIY058H7
Credits: 15 credits
Level: 7
Module leader: Michael Zakharyaschev

Aims

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.

Syllabus

  • 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.

Prerequisites

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.

Timetable

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

Assessment

By 3-hour written examination and coursework exercises, weighting 80% and 20% respectively.

Recommended reading

  • 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