Applications open for 2022 entry Apply now

Discrete Structures

15 Credits

This course introduces students to the mathematical “tools” (e.g. proof techniques), data structures and algorithms that form the foundation of computer science. At the same time, it explains how these concepts are used in modern, real-world applications.

In this course, students have the opportunity to learn: (i) how data are represented on a computer; (ii) basic logical operations on data and how they can be combined to implement more complex relations; (iii) basic data structures (e.g. sets, sequences, lists, trees, and graphs) and algorithms to manipulate them (e.g. sorting an array) or query them (e.g. finding shortest paths in a graph); and (iv) basic mathematical techniques (e.g. counting or induction) and how they can be used to estimate the space and time complexity of algorithms (i.e. their growth) as a function of the input size.

This course is suitable for graduate students of disciplines other than computing who are keen to acquire new (or deepen their existing) knowledge of computing.

Indicative Topics

  • Number representations (e.g. binary and hexadecimal)
  • Logic, logical operators
  • Integer functions
  • Combinatorics: sets, counting and probability
  • Sequences, sums, and series (e.g. arithmetic and geometric)
  • Basic data structures: array, list, stack, queue, hash tables
  • Graphs, their representation and elementary algorithms (e.g. spanning trees)
  • Algorithms for searching and sorting
  • Recursion, mathematic induction, and recurrences
  • Runtime analysis: Big-O notation and complexity classes