Skip to main content

# Unit information: Communication, complexity and number theory in 2015/16

Please note: you are viewing unit and programme information for a past academic year. Please see the current academic year for up to date information.

Unit name Communication, complexity and number theory COMS20002 10 I/5 Teaching Block 2 (weeks 13 - 24) Dr. Stam Not open COMS11700 (unless taken as co-requisite) COMS11700 (unless taken as pre-requisite) Department of Computer Science Faculty of Engineering

## Description

The unit aims to develop students' knowledge of and skills in algebra, and introduce students to basic concepts of coding theory, information theory, and complexity theory.

Tak am abitry pce o Eslignh txt, and you can remove and change a fair number of letters yet with some effort, a reader can still reconstruct the original text. In the modern world, where most data is binary, is it still possible to compress and correct errors? How hard can reconstructing the original data be?

This unit explores the limits of efficient and effective communication from a theoretical perspective (why it is possible based on information theory) with practical applications (how to do it using coding theory) and provides a theoretical framework to argue about the complexity of computations in general (computational complexity theory).

To enable the practical applications, the unit also provides an introduction to algebra, with an emphasis on basic results and the ability to perform algebraic operations.

## Intended learning outcomes

After following this unit you should be able to

• Reproduce the axioms and basic theorems of elementary algebra
• Solve simple algebraic problems, either symbolically or computationally
• Describe the goals and limitations of source and channel encoding and use taught methods to meet these goals and quantify the limitations
• Describe the main complexity classes and how they relate to each other
• Classify computational problems by providing reductions to a set of problems of known complexity

## Teaching details

2 hours of lecture per week, augmented by a weekly 1 hour lab session for the first six weeks and a weekly 1 hour tutorial for the final six weeks.

## Assessment Details

Summative: 2 hour exam (80%) and a practical assessment (20%) of the ability to solve algebraic problems using taught computational methods.

## Reading and References

M. Sipser (2006), Introduction to the Theory of Computation (2nd ed.)