# Computational Thinking (HS 2020)

Course catalogue

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. 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. To give just one more example: How can we design the best electronic circuit for a given problem? In this class, we study various problems together with the fundamental theory of computation.

The weekly lectures will be based on blackboard discussions and coding demos, supported by a script and coding examples. 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, on paper and in Python.

## Errata

• The solution to exercise 5 question 1 was corrected to use the version of El Gamal signatures from the script.
• In Chapter 3, the proof of Theorem 3.22 has been fixed by replacing a spurious \cdot with an '=' sign.
• There was a typo in Definition 2.6: The function r maps to the tuple (X_B, Y_B) not (Y_B, Y_B). The download below features the corrected version.
• We added a paragraph for 2d) for exercise 7
• The solution to question 1b in Exercise 8 was corrected.
• In Definition 5.5, d has been updated for consistency with the dimension of matrix X
• The proof of Theorem 5.6 has been corrected (a transpose was missing in the differentiation step)
• There was a mistake in Definition 5.19: The expectation over x has to come outside and after squaring.
• There was a mistake in Definition 7.23: grid square (i,j) needs to have the same tile as grid squares (i+w, j) and (i, j+h).
• In question 1a) of exercise 13 the notation was changed from T to T'.

## News

• 11.02.2021: We had the Q&A session yesterday. You can find a recording here
• 26.10.2020: We will switch to virtual only starting this week. You can join the live lectures and exercises at https://ethz.zoom.us/j/96078321156
• 21.09.2020: We will now use the ETH offered livestream as primary means for remote students to attend
• 16.09.2020: The lectures & exercises started

## Exam

• The exam will take place on Monday, February 15, from 9am to 11am .
• The exam questions are in English, answers can be in German, English, or a combination of both
• You are allowed to bring any written material you like (lecture notes, books, personal notes,...), but no electronic devices whatsoever (no calculator, phone, laptop, headphones,...).
• The exam will last 2 hours and consist of 120 points
• Here, we collected an overview of what you can expect in the exam: Exam Overview
• Old exam questions

## Lecture Material

Chapter Title Lecturer Lecture Notes Exercises Solutions Responsible Assistant Recordings
Introduction
16.09.2020
Roger Wattenhofer PDF
Python Basics
Chapter 1
Algorithms
16.09.2020
23.09.2020
Roger Wattenhofer PDF 1:1
PDF 2:1
Notebook

Exercise 1 Notebook
Exercise 2 PDF
Exercise 2 Notebook
Solutions 1 PDF
Solutions 1 Notebook
Solutions 2 PDF
Solutions 2 Notebook
Henri Week 1
Week 2
Chapter 2
Complexity
30.09.2020
7.10.2020
Roger Wattenhofer
Andras Papp
PDF 1:1
PDF 2:1
Notebook
Exercise 3 PDF
Exercise 3 Notebook
Exercise 4 PDF
Exercise 4 Notebook
Solutions 3 PDF
Solutions 3 Notebook
Solutions 4 PDF
Solutions 4 Notebook
Robin
Andras
Week 3
Week 4
Chapter 3
Cryptography
14.10.2020
21.10.2020
Zeta Avarikioti
Roger Wattenhofer
PDF 1:1
PDF 2:1
Notes
Notebook
Exercise 5 PDF
Exercise 5 Notebook
Exercise 6 PDF
Exercise 6 Notebook
Solutions 5 PDF
Solutions Notebook
Solutions 6 PDF
Solutions Notebook
Ard
Tejaswi
Zeta
Week 5
Week 6
Chapter 4
Data and Storage
28.10.2020
04.11.2020
Roger Wattenhofer PDF 1:1
PDF 2:1
Notebook
Exercise 7 PDF
Exercise 7 Notebook
Exercise 8 PDF
Exercise 8 Notebook
Solutions 7 PDF
Solutions 7 Notebook
Solutions 8 PDF
Solutions 8 Notebook
Kobi
Simon
Week 7
Exercise 7
Week 8
Exercise 8
Chapter 5
Machine Learning
11.11.2020
18.11.2020
Roger Wattenhofer PDF 1:1
PDF 2:1
Notebook
Exercise 9 PDF
Exercise 9 Notebook
Exercise 10 PDF
Exercise 10 Notebook
Solutions 9 PDF
Solutions 9 Notebook
Solutions 10 PDF
Solutions 10 Notebook
Beni
Zhao
Week 9
Exercise 9
Week 10
Exercise 10
Chapter 6
Neural Networks
25.11.2020
02.12.2020
Roger Wattenhofer PDF 1:1
PDF 2:1
Notebook
Exercise 11 PDF
Exercise 11 Notebook
Exercise 12 PDF
Exercise 12 Notebook
Solutions 11 PDF

Solutions 12 PDF
Solutions 12 Notebook
Damian
Oliver
Week 11
Exercise 11
Week 12
Exercise 12
Chapter 7
Computability
09.12.2020
16.12.2020
Roger Wattenhofer PDF 1:1
PDF 2:1
Exercise 13 PDF
Exercise 13 Notebook Exercise 14 PDF
Solutions 13 PDF
Solutions 13 Notebook Solutions 14 PDF
Robin
Andras
Week 13
Exercise 13
Week 14