CoE 161 S2 AY 2022-2023

• 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