Distributed Computing
ETH Zurich

Computational Thinking (HS 2023)

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, 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.

Organization

This course follows the flipped classroom paradigm. You (the student) will self-study all important concepts by

We have weekly paper exercise sessions to learn all the important concepts, with questions on the level of exam questions.

For each topic, the whole class meets every two weeks on Thursday. Each class meeting is organized as follows:

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

News

Exam

Lecture Material

Chapter Title Lecture Notes Lecture Videos Exercises & Solutions 3rd Party Tutorials
Introduction & Python
21.09.2023
PDF
Python Cheat Sheet
Notebook
Python Playlist
Python Basics (Page 1)
Python Advanced (Page 2)
Python for Programmers
Chapter 1
Algorithms
05.10.2023
PDF 1: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
19.10.2023
PDF 1: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]
Connecting All 7 Chapters [p]
Chapter 3
Cryptography
02.11.2023
PDF 1: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 6 Notebook
Man in the Middle [p]
Zero Knowledge Proofs [p]
Chapter 4
Databases
16.11.2023
PDF 1: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 Notebook by Philipp Huth
SQL Cheat Sheet by Philipp Huth
SQL Select Demo
SQL Murder Mystery [p]
SQL Injection [p][a]
Chapter 5
Machine Learning
30.11.2023
PDF 1: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
14.12.2023
PDF 1: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
21.12.2023
PDF 1: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]