Information and Communication

Content of the course

Information theory was developed by Claude E. Shannon in the 1950s to investigate the fundamental limits on signal-processing operations such as compressing data and on reliably storing and communicating data. These tasks have turned out to be fundamental for all of computer science.

In this course, we introduce the basics of probability theory and then study concepts such as (conditional) Shannon entropy and mutual information. Then, we treat Shannon's theorems about data compression and channel coding. We will also cover some aspects of information-theoretic security for encryption.

Intended Learning Outcomes

At the end of the course, you are able to

• Define Shannon entropy and Mutual Information and compute these quantities on examples.
• Work with joint discrete random variables (conditioning, Bayes' rule)
• Define basic discrete probability distributions (Bernoulli, Binomial, Geometric) and compute their expected value and variance
• State Jensen's inequality for convex and concave functions
• Use entropy diagrams to read off and find new relations between entropic quantities
• State Shannon's theorem about perfectly secure encryption
• Compute a d-ary Huffman code
• Describe how much a given source can be compressed and give a way to do it
• Define basic channels (binary symmetric, erasure channel)
• State Shannon's noisy channel-coding theorem
• Study a slightly more advanced topic about information and communication
• Present this topic to the class
• Write a final report about it

The contents of the course might vary depending on the previous knowledge of the participants.

Course website

Updated information about the course can be found on https://staff.science.uva.nl/c.schaffner/courses/infcom/2014/

Prerequisites

Basic calculus, e.g. working with logarithms. Also, basic notions of discrete probability (as learned e.g. in stochastiek 1) are helpful, but are not a strict requirement. This course is well-suited for students who are pursuing a double bachelor in mathematics and computer science.

Study Material

The material will be presented on slides and black-boards lectures. The following are good references:

• [CF] Ronald Cramer, Serge Fehr: The Mathematical Theory of Information, and Applications, lecture notes, Version 2.0
• [CT] Thomas M. Cover, Joy A. Thomas. Elements of information theory, 2nd Edition. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4.
• [MacKay] David J. C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1

Schedule

please check Datanose for the definite times and locations.
It is important to show up personally for the first lecture on Monday, 5 January at 9:00 in SP B0.203, because the details of the course will be further organised then. If you cannot make it on Monday, but you want to attend the course nevertheless, please send me an email.

Language

The lectures will be given in English. The homework and final report might be written in Dutch, and the presentation can be delivered in Dutch, but the use of English is encouraged.

Credits, homework, final presentation, report

This is a 6 ECTS course, which will keep you busy full-time (40h/week) for the month of January 2015. There will be lectures in the first two weeks (5-16 January) and homework exercises to solve and hand in. In the third week of the course, you choose a topic from this list and study it. In the final week, you present the topic to the class and write a final report about this topic.

Grades

Your grade for the final presentation will be determined by the quality of the presentation, your ability to answer questions about the subject (we will use this list for the evaluation).

The final presentation counts 1/3 towards your final grade of the course, 1/3 will be determined by the report, and 1/3 will be determined by the average of the 3 homework exercises.

Preliminary course schedule for January 2015

Date	Content	Homework
Mon, 5 Jan 2015, 9:00-10:00	Overview and organisation of the course It is essential to attend this first lecture if you want to follow the course. Slides #1
Mon, 5 Jan 2015, 10:00-12:00	Discrete Probability Theory Section 2.1 of [CF]
Mon, 5 Jan 2015, 13:00-15:00	Exercise session (on Discrete Probability Theory)	Homework #1
Tue, 6 Jan 2015, 15:00-17:00	Jensen's inequality, Exercise session (on Discrete Probability Theory) Handout Jensen's inequality
Wed, 7 Jan 2015, 9:00-12:00	Entropy, Mutual Information, Entropy Diagrams Section 3 of [CF] Slides #2
Wed, 7 Jan 2015, 13:00-15:00	Exercise session (on Entropy)	Homework #2
Thu, 8 Jan 2015, 13:00-15:00	Exercise session
Fri, 9 Jan 2015, 9:00-11:00	Exercise session
Mon, 12 Jan 2015, 13:00-15:00	Markov chains, Data-Processing Inequality, Fano's inequality, Definition of Perfectly Secure Encryption Sections 2.8-2.10 of [CT], Section 4 of [CF]
Tue, 13 Jan 2015, 13:00-15:00	Perfectly Secure Encryption: One-time Pad and Shannon's theorem, Data Compression Section 4 of [CF], Section 5.1 of [CF] Insecurity of Key Reuse in OTP Entropy of Alice in Wonderland  Hex Editor with statistics  Slides #5	Homework #3
Wed, 14 Jan 2015, 13:00-15:00	Data Compression: symbol codes, properties, source-coding theorem, Kraft's inequality, Huffman codes Section 5 of [CF], Chapter 5 of [CT], Chapter 5 of [MacKay]
Thu, 15 Jan 2015, 13:00-15:00	Exercise session
Fri, 16 Jan 2015, 13:00-15:00	Exercise session
Tue, 27 Jan 2015, 13:00-15:30	Student presentations 13:00 - 14:00 Ismani/Sander: Zero-error channel coding theory Slides Report 14:30 - 15:30 Lucas/Sebastian: Shannon's noisy-channel coding theorem Slides Report
Wed, 28 Jan 2015, 13:00-15:30	Student presentations 13:00 - 14:00 Jorn/Timo: Markov processes: Entropy Rates of a Stochastic Process Slides Report 14:30 - 15:30 Wicher: Data compression in practice: Lempel-Ziv & Co. Report
Thu, 29 Jan 2015, 13:00-15:00	Student presentations 13:00 - 14:00 Olaf/Julian: Codebreaking of Traditional Cipher Systems Slides Report

Life after "Information & Communication"

If you got hooked on the world of entropies, you have several options after the course to pursue the topics of information theory and cryptography:

• Talk to Christian about the possibilities of doing a semester project or bachelor project in information theory or cryptography. He can also hook you up with other people at the ILLC, at CWI or in the rest of the world, working on different aspects of information theory.
• Follow Ronald de Wolf's master course about quantum computing at the university of Amsterdam, starting Spring 2015.
• Follow this mastermath course about crypology by Marc Stevens and Tanja Lange, starting in Spring 2015.
• Follow Harry Buhrmans's master course about computational complexity at the university of Amsterdam, starting Fall 2015.
• Follow various online classes such as Raymond W. Yeung's Information Theory course, Dan Boneh's crypto, crypto II, Jon Katz's crypto class or Umesh Vazirani's course about quantum computing.