Skip to main content

Unit information: Communication, complexity and number theory in 2018/19

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
Unit code COMS20002
Credit points 10
Level of study I/5
Teaching block(s) Teaching Block 1 (weeks 1 - 12)
Unit director Dr. Bernhard
Open unit status Not open
Pre-requisites

COMS11700 (unless taken as co-requisite)

Co-requisites

COMS11700 (unless taken as pre-requisite)

School/department Department of Computer Science
Faculty Faculty of Engineering

Description

The unit aims to develop students' knowledge of and skills in algebra, and introduce students to basic concepts of coding and information 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).

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.

Together, algebra and coding/information theory are foundations for the mathematics required to reason about modern cryptography.

Intended learning outcomes

After following this unit you should be able to

  • Reproduce the axioms and basic theorems of elementrary algebra
  • Solve simple algebraic problems, either symbolically or computationally
  • Explain the concept of, and perform arithmetic operations in finite fields
  • Use the concept of information-theoretic entropy to solve simple problems relating to communication and security
  • Describe the goals and limitations of source and channel encoding and use taught methods to meet these goals and quantify the limitations

Teaching details

Each week (except Explore Week) there will be 2 hours of lectures and a 1-hour lab session.

Assessment Details

One summative 2-hour exam worth 80% of the unit mark. 4 pieces of coursework worth 5% each of the unit mark.

Reading and References

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

Feedback