| 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. |
| Learning 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. |
| Lecture notes | The script is available here: https://disco.ethz.ch/courses/coti/ |
| Prerequisites / Notice | This class is suitable for students who have a basic understanding of programming.
For additional Python programming experience we recommend attending the CodeJam lab: https://disco.ethz.ch/courses/codejam/
For practical deep learning exerience we recommend attending the HODL lab: https://disco.ethz.ch/courses/hodl/ |
Competencies | | Subject-specific Competencies | Concepts and Theories | assessed | | Techniques and Technologies | assessed | | Method-specific Competencies | Analytical Competencies | assessed | | Decision-making | fostered | | Media and Digital Technologies | assessed | | Problem-solving | assessed | | Social Competencies | Communication | fostered | | Personal Competencies | Adaptability and Flexibility | assessed | | Creative Thinking | assessed | | Critical Thinking | assessed | | Integrity and Work Ethics | fostered | | Self-awareness and Self-reflection | fostered | | Self-direction and Self-management | fostered |
|
Performance assessment as a semester course