Programme And Module Handbook
Course Details in

If you find any data displayed on this website that should be amended, please contact the Curriculum Management Team.

Module Title Combinatorics and Communication Theory
Department Mathematics
Module Code 06 19601
Module Lead Deryk Osthus
Level Honours Level
Credits 20
Semester Full Term
Pre-requisites Foundation and Abstraction - (06 22512)
Restrictions Optional for: All MSci programmes in Mathematics, BSc Mathematical Sciences, BSc Mathematical Sciences with Study in Continental Europe, All programmes including a Major in Mathematics, All JH programmes
Contact Hours Lecture-46 hours
Seminar-0 hours
Tutorial-10 hours
Project supervision-0 hours
Demonstration-0 hours
Practical Classes and workshops-0 hours
Supervised time in studio/workshop-0 hours
Fieldwork-0 hours
External Visits-0 hours
Work based learning-0 hours
Guided independent study-0 hours
Placement-0 hours
Year Abroad-0 hours
Description The first part of the module will give an introduction to several combinatorial structures, which have applications in different areas. Topics are likely to include combinatorial games, applications of counting principles to discrete probability and basic Ramsey theory. (Here Ramsey theory can be viewed as a formalization of the notion that `complete disorder is impossible’ – this surprising phenomenon will be investigated for graph colourings and arithmetic properties of the integers).
The second part of the module consists of an introduction to information theory and coding theory. The aim here is to transmit information (i) efficiently and (ii) reliably over a noisy channel. For (i), the main result will be Shannon’s noiseless coding theorem, which relates coding efficiency to the entropy of a source. For (ii), we will discuss error correcting codes, including several linear codes, such as Hamming codes. Both parts of the module are linked by the methods and ideas that are used.
Learning Outcomes By the end of the module the student should be able to:
  • Be familiar with basic combinatorial structures
  • Understand and be able to apply fundamental results on finite sets, codes and communication over a noisy channel
  • Apply the basic techniques introduced in the lectures
Assessment 19601-01 : Raw Module Mark : Coursework (0%)
19601-02 : Final Module Mark : Coursework (100%)
Assessment Methods & Exceptions Assessments: 19601-01: Exam : Exam (CT) - Written Unseen (90%)
19601-02 : Continuous Assessment : Coursework or class Tests (10%)
Reading List Jukna, S. 2001. Extremal Combinatorics. Springer-Verlag.
Welsh, D. 1988. Codes and Cryptography. Oxford University Press.