Computational Thinking

Abstract

We learn: algorithmic principles, dynamic and linear programming, complexity, P vs. NP, approximation, reductions, cryptography, zero-knowledge proofs, relational databases, SQL, machine learning, regression, gradient descent, decision trees, deep neural networks, universal approximation, advanced layers and architectures, reinforcement learning, Turing machines, computability, and more.

Objective

Computation is everywhere, but what is computation actually? In this lecture we will discuss the power and limitations of computation. Computational thinking is about understanding machine intelligence: What is computable, and how efficiently? Understanding computation lies at the heart of many exciting scientific, social and even philosophical developments. Computational thinking is more than programming a computer, it means thinking in abstractions. Consequently, computational thinking has become a fundamental skill for everyone, not just computer scientists. For example, functions which can easily be computed but not inverted are at the heart of understanding data security and privacy. The design of efficient electronic circuits is related to computational complexity. Machine learning on the other hand has given us fascinating new tools to teach machines how to estimate functions. Thanks to clever heuristics, machines now appear to be capable of solving complex cognitive tasks. In this class, we study various problems together with the fundamental theory of computation. The course uses Python as a programming language. Python is popular and intuitive, a programming language that looks and feels a bit like human instructions. The lecture will feature weekly exercises. This course follows the flipped classroom paradigm. Students will self-study all important concepts by reading a chapter in the script, and by watching a few short video clips. The class meets every two weeks to answer questions, and for a quiz on the current topic.

Content

Computation is everywhere, but what is computation actually? In this lecture we will discuss the power and limitations of computation. Computational thinking is about understanding machine intelligence: What is computable, and how efficiently? Understanding computation lies at the heart of many exciting scientific, social and even philosophical developments. Computational thinking is more than programming a computer, it means thinking in abstractions. Consequently, computational thinking has become a fundamental skill for everyone, not just computer scientists. For example, functions which can easily be computed but not inverted are at the heart of understanding data security and privacy. The design of efficient electronic circuits is related to computational complexity. Machine learning on the other hand has given us fascinating new tools to teach machines how to estimate functions. Thanks to clever heuristics, machines now appear to be capable of solving complex cognitive tasks. In this class, we study various problems together with the fundamental theory of computation. The course uses Python as a programming language. Python is popular and intuitive, a programming language that looks and feels a bit like human instructions. The lecture will feature weekly exercises. This course follows the flipped classroom paradigm. Students will self-study all important concepts by reading a chapter in the script, and by watching a few short video clips. The class meets every two weeks to answer questions, and for a quiz on the current topic.

Resources