CoE 161 S2 AY 2021-2022

• Introduction to Information and Complexity
  • Introductory course on information theory and computational complexity. We'll start from Shannon's information theory and Turing's theory of computation, then move to the theory of Kolmogorov complexity.

• Semester Offered: 2nd semester
• Course Credit: Lecture: 3 units

Prerequisites

• EEE 111 (Introduction to Programming and Computation)
• EEE 137 (Probability, Statistics and Random Processes in Electrical and Electronics Engineering)

Course Goal

• Introduce fundamental tools and frameworks to understand information and complexity in the design of computer systems.
• Introduce fundamental tools for determining the minimum amount of computational resources needed to algorithmically solve a problem.
  • Information Theory
  • Computational Complexity Theory

Content

This course covers information theory and computational complexity in a unified way. It develops the subject from first principles, building up from the basic premise of information to Shannon's information theory, and from the basic premise of computation to Turing's theory of computation. The duality between the two theories leads naturally to the theory of Kolmogorov complexity. The technical topics covered include source coding, channel coding, rate-distortion theory, Turing machines, computability, computational complexity, and algorithmic entropy, as well as specialized topics and projects.

We want to answer the question: How good is my solution (e.g. algorithm, architecture, system, etc.) to a computer engineering problem?

• Information Theory: data representation efficiency
  • What is information?
  • How do we measure information?
• Computational Complexity: complexity in time and space
  • Complexity of algorithms
  • Complexity of objects/data

General Guidelines for AY 2021-2022

• Since we are offering this class remotely, there will be several changes to our normal course delivery:
• There will be no face-to-face lecture classes. All materials will be made available via this site and on our UVLE page.
• Please email our instructors for access to our UVLE page.
• There will be more emphasis on student-centric activities, e.g. analysis, design, and simulations. Thus, you will be mostly "learning by doing". In this context, we will set aside an hour every week for consultations and questions via video-conferencing.
• Grades will be based on the submitted deliverables from the activities. Though we will not be very strict regarding the deadlines, it is a good idea to keep up with the class schedule and avoid cramming later in the semester.

Instructor Details

• Louis Alarcon, Ph.D.
  • Email: louis.alarcon@eee.upd.edu.ph
  • Consultation time: TBD
• Ryan Antonio
  • Email: ryan.albert.antonio@eee.upd.edu.ph
  • Consultation time: Mon, 9:00 AM - 4:00 PM; T-F 9:00 AM - 10:00 AM; Consulting beyond 4:00 PM is okay but may change depending on availability. Usually out every weekend.

Syllabus

Module	Topics	Outcomes	Resources	Activities
1	Introduction to Information Theory Engaging introduction to information theory Probability review for warm up	Understand the basis of information theory. Appreciate the breadth and implications of information theory. Quick review about probability.		2S2122 Activity 1.1: Probability exercises 2S2122 Activity 1.2: First coding exercise
2	Mathematical Fundamentals of Information Theory Information and entropy Conditional entropy and mutual information	Understand the basis of Information Theory. Appreciate the breadth and implications of Information Theory. Derive an expression for Entropy and its bounds. Apply these to some theoretical exercises.		2S2122 Activity 2.1: Theoretical Exercises 2S2122 Activity 2.2: How many bits is the English language?
3	Channels and Channel Capacity Discrete noiseless channel Discrete noisy channel Noise in images	Understand the role of mutual information in noisy channels. Observe how conditional entropy and mutual information measure noise.		2S2122 Activity 3.1: Theoretical Exercises 2S2122 Activity 3.2: Images and Noise
4	Coding Theory Source coding Uniquely decodable codes Huffman codes Independence and Markov chains Nonnegativity of information measures The data-processing inequality	Decode a message compressed using a prefix-free code. Optimally encode redundant messages based on the entropy of the source. Understand the implications of modeling a system using Markov chains, and from Fano's inequality, determine the bounds of the probability of error in these systems.		2S2122 Activity 4.1: Theoretical Exercises 2S2122 Activity 4.2: Huffman Coding
5	Data Compression (2 weeks) Lossless data compression by replacement schemes Arithmetic coding	Discover several types of data compression techniques. Learn how to apply how information theory quantifies these strategies.		2S2122 Activity 5.1: Theoretical Exercises 2S2122 Activity 5.2: Data compression 1 2S2122 Activity 5.3: Data Compression 2
6	Turing Machines (2 weeks) What are Turing machines? Decidability Reducibility	Understand fundamental mathematical properties of computer hardware and software. Determine what can and cannot be computed.		2S2122 Activity 6.1: Theoretical Exercises 2S2122 Activity 6.2: The Turing Machine
7	Kolmogorov Theory of Complexity (2 weeks) Time complexity Space Complexity Intractability	Investigate if time, memory, or other computing resources can solve computational problems.		2S2122 Activity 6.1: Theoretical Exercises 2S2122 Activity 6.2: Analyzing sorting algorithms

References

• Stone, J.V. , Information Theory: A Tutorial Introduction, Sebtel Press, 2015.
• Michael Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2013.
• Cristopher Moore and Stephan Mertens, The Nature of Computation, Oxford University Press, Inc., 2011, USA.
• Applebaum, D. , Probability and Information: An Integrated Approach, Cambridge University Press, 2008.
• Yeung, R., Information Theory and Network Coding., Springer, 2008.
• Cover, T. M, Thomas, J. A., Elements of Information Theory, 2ed., Wiley-Interscience, 2006.
• Hankerson, D.R., Harris, G.A., Johnson, P.D. , Introduction to Information Theory and Data Compression, CRC Press, 2003.
• MacKay, D. , Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003.

Additional Reading Materials

• Robert M. Gray, Entropy and Information Theory 1st ed. (corrected), Springer-Verlag New York 2013.
• Sanjeev Arora and Boaz Barak. (2009), Computational Complexity: A Modern Approach (1st ed.), Cambridge University Press, New York, NY, USA.
• Jon Kleinberg and Christos Papadimitriou, Computability and Complexity, Computer Science: Reflections on the Field, Reflections from the Field, Natl. Academies Press, 2004.
• Jones, Neil D., Computability and Complexity: From a Programming Perspective, 1997, The MIT Press, Cambridge, Massachusetts.