CS110 – Combinatorics for Computer Science 1

TIMETABLE TEACHING MATERIAL
Credits 10
Level SHE Level 1
Prerequisites None
Availability Semester 2
Elective Yes
Contact 11 lectures/11 tutorials (2 hours)
Assessment 100% coursework
Lecturer Professor Einar Steingrimsson

Aims and Objectives

The aim of this class is to introduce the basic combinatorial tools of computer science, to train students in mathematical thinking and reasoning that is pertinent to computer science, and to present that reasoning in rigorous written text.

Learning Outcomes

On completion of the class, a student should be able:

  1. To enumerate sets of discrete objects (e.g. binary strings with restrictions on where 1s may appear, words representing paths between two points on a grid).
  2. To deal with questions about the probability of a discrete structure having a certain property by using their knowledge of enumeration.
  3. To show how to prove some simple enumerative facts about discrete objects by non-constructive methods.
  4. To present solutions in a clear and rigorous manner, both written and orally.

Syllabus

In this class students will first learn how to enumerate sets and sequences that occur in theoretical computer science, e.g. binary strings of a given length that contain no two consecutive 1s. These enumerations will generally involve expressions containing binomial coefficients and/or recursion equations, and students are taught how to deal with such expressions.

This idea of set enumeration is built upon in the direction of discrete probability via counting arguments. During this, students will learn about binomial distributions and the expectations of random variables in the discrete setting. Following this, attention turns to combinatorial methods and arguments. Combinatorial games, induction on discrete structures, discrete mathematical arguments such as tiling and pigeon hole principle are among the topics covered in the latter part of the class.

Assessment and Exemption

Students will typically be set four assignments. There is an individual oral examination at the end of the class to validate the marks achieved in the four assignments.

Resit

The resit for the class will take the form of individual assignments as well as an individual oral examination.

Indicative Reading*

*This list is indicative only – the class lecturer may recommend alternative reading material. Please do not purchase any of the reading material listed below until you have confirmed with the class lecturer that it will be used for this class.

Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer by Tom Jenkyns and Ben Stephenson (Springer, 2012).

Sets, Logic and Maths for Computing (Undergraduate Topics in Computer Science) by David Makinson, 2nd edition (Springer, 2009)

How to Count: An Introduction to Combinatorics by R.B.J.T. Allenby and Alan Slomson (Chapman and Hall/CRC, 2010)