Computational Thinking (HS 2020)
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.
- Course language: Written English, Spoken German
- Lecture by Roger Wattenhofer, Wednesdays 8-10 on Zoom https://ethz.zoom.us/j/96078321156. The recordings will be published below.
- Exercises organized by Lukas Faber, Wednesdays from 10-11 on Zoom https://ethz.zoom.us/j/96078321156
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