Distributed Computing
ETH Zurich

Computational Thinking (HS 2022)

Course catalogue Previous year

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 and social developments. Computational thinking is more than programming a computer -- rather it is thinking in abstractions. Consequently, computational thinking has become a fundamental skill for everyone, not just computer scientists. For example, designing an electronic circuit relates directly to computation. Mathematical functions which can easily be computed but not inverted are at the heart of understanding data security and privacy. Machine learning on the other hand has given us fascinating new tools to teach machines how to learn function parameters. Thanks to clever heuristics, machines now appear to be capable of solving complex cognitive tasks. In this class, we study all these and more 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.

This course follows the flipped classroom paradigm. Students will self-study all important concepts by

The lecture will also feature weekly paper exercise sessions to learn all the important concepts, with questions on the level of exam questions.

The whole class meets every two weeks. In each meeting,

Students can win a 1/4 bonus grade for the exam, by

News

Programming Challenges

Exam

Lecture Material

Chapter Title Lecture Notes Lecture Videos Exercises & Solutions 3rd Party Tutorials
Introduction
22.09.2022
PDF
Python Cheat Sheet
Python Basics Notebook
From C++ to Python
Chapter 1
Algorithms
06.10.2022
PDF 1:1
PDF 2:1
Notebook
Algorithms Playlist
Recursion etc. (1.1-1.3)
Dynamic Programming (1.4)
O Notation (in 1.1)
Linear Programming (1.5)
Linear Relaxation (1.6)
Flows (1.7)
Summary Chapter 1
Exercise 1 PDF
Solutions 1 PDF
Exercise 1 Notebook
Solutions 1 Notebook
Exercise 2 PDF
Solutions 2 PDF
Exercise 2 Notebook
Solutions 2 Notebook
Recursion and Backtracking [p]
Dynamic Programming
Linear Programming [b][s]
Chapter 2
Complexity
20.10.2022
PDF 1:1
PDF 2:1
Notebook
Complexity Playlist
P and NP (2.1)
NP Hard (2.2)
Boolean Formulas (2.3)
Boolean Circuits (2.4)
Vertex Cover Approximation (2.6)
Bin Packing Approximation (2.7)
TSP Approximation (2.8)
Knapsack FPTAS (2.9)
Summary Chapter 2
Exercise 3 PDF
Solutions 3 PDF
Exercise 3 Notebook
Solutions 3 Notebook
Exercise 4 PDF
Solutions 4 PDF
Exercise 4 Notebook
Solutions 4 Notebook
P vs. NP [p]
3-SAT ≤ Mario [p][s]
Load Balancing Approximation [s]
Chapter 3
Cryptography
03.11.2022
PDF 1:1
PDF 2:1
Notebook
Cryptography Playlist
Perfect Encryption (3.1)
Key Exchange (3.2)
Public Key Cryptography (3.3-3.4)
Digital Signatures (3.5)
Cryptographic Hashing (3.6)
Public Key Infrastructure (3.7)
Zero Knowledge Proofs (3.9)
Commitment Schemes (3.10)
Multiparty Computation (3.12)
Summary Chapter 3
Exercise 5 PDF
Solutions 5 PDF
Exercise 5 Notebook
Solutions 5 Notebook
Exercise 6 PDF
Solutions 6 PDF
Exercise 6 Notebook
Solutions Notebook
Man in the Middle [p]
Zero Knowledge Proofs [p]
Chapter 4
Databases
17.11.2022
PDF 1:1
PDF 2:1
Notebook
Databases Playlist
Dictionaries (4.1)
Hashing (4.2)
Database Basics (4.3-4.4)
SQL Basics (4.5)
Modeling and Joins (4.6-4.8)
Summary Chapter 4
Exercise 7 PDF
Solutions 7 PDF
Exercise 8 PDF
Solutions 8 PDF
Exercise 8 Notebook
Solutions 8 Notebook
SQL Select Demo
SQL Murder Mystery [p]
SQL Injection [p][a]
Chapter 5
Machine Learning
01.12.2022
PDF 1:1
PDF 2:1
Notebook
Machine Learning Playlist
Linear Regression (5.1)
Feature Modeling (5.2)
Generalization and Overfitting (5.3)
Bias-Variance Tradeoff (5.4)
Regularization (5.5)
Gradient Descent (5.6)
Logistic Regression (5.7)
Decision Trees (5.8)
Machine Learning Evaluation (5.9)
Summary Chapter 5
Exercise 9 PDF
Solutions 9 PDF
Exercise 9 Notebook
Solutions 9 Notebook
Exercise 10 PDF
Solutions 10 PDF
Exercise 10 Notebook
Solutions 10 Notebook
Linear Regression Formula
ML Overview [b][p][s]
Chapter 6
Neural Networks
15.12.2022
PDF 1:1
PDF 2:1
Notebook
Neural Networks Playlist
Neural Networks (6.1)
Gradient Descent (5.6)
Backpropagation (6.3)
Backpropagation Math (6.3)
Universal Approximation (6.2)
Convolutional Neural Networks (6.6)
Recurrent Neural Networks (6.6)
Attention in Neural Networks (6.6)
Reinforcement Learning (6.8)
Summary Chapter 6
Exercise 11 PDF
Solutions 11 PDF
Exercise 12 PDF
Solutions 12 PDF
Exercise 12 Notebook
Solutions 12 Notebook
Neural Networks [p][s]
Convolution [p]
Chapter 7
Computability
22.12.2022
PDF 1:1
PDF 2:1
Computability Playlist
Halting Problem (7.1)
Turing Machine (7.2)
Bathroom Tiles (7.3)
Post Correspondence Problem (7.4)
Summary Chapter 7
Exercise 13 PDF
Solutions 13 PDF
Exercise 13 Notebook
Solutions 13 Notebook
Exercise 14 PDF
Solutions 14 PDF
Undecidable [p]
Unsolvable [p]