## Hans-Joachim Böckenhauer: Catalogue data in Autumn Semester 2020 |

Name | Dr. Hans-Joachim Böckenhauer |

Consultation hours | By appointment |

Address | Professur Algorithmen und Didaktik ETH Zürich, CAB F 11 Universitätstrasse 6 8092 Zürich SWITZERLAND |

Telephone | +41 44 632 81 83 |

Fax | +41 44 632 13 90 |

hjb@inf.ethz.ch | |

URL | http://www.ite.ethz.ch/people/hjb/ |

Department | Computer Science |

Relationship | Lecturer |

Number | Title | ECTS | Hours | Lecturers | |
---|---|---|---|---|---|

252-0057-00L | Theoretical Computer Science | 7 credits | 4V + 2U | J. Hromkovic, H.‑J. Böckenhauer | |

Abstract | Concepts to cope with: a) what can be accomplished in a fully automated fashion (algorithmically solvable) b) How to measure the inherent difficulty of tasks (problems) c) What is randomness and how can it be useful? d) What is nondeterminism and what role does it play in CS? e) How to represent infinite objects by finite automata and grammars? | ||||

Learning objective | Learning the basic concepts of computer science along their historical development | ||||

Content | This lecture gives an introduction to theoretical computer science, presenting the basic concepts and methods of computer science in its historical context. We present computer science as an interdisciplinary science which, on the one hand, investigates the border between the possible and the impossible and the quantitative laws of information processing, and, on the other hand, designs, analyzes, verifies, and implements computer systems. The main topics of the lecture are: - alphabets, words, languages, measuring the information content of words, representation of algorithmic tasks - finite automata, regular and context-free grammars - Turing machines and computability - complexity theory and NP-completeness - design of algorithms for hard problems | ||||

Lecture notes | The lecture is covered in detail by the textbook "Theoretical Computer Science". | ||||

Literature | Basic literature: 1. J. Hromkovic: Theoretische Informatik. 5th edition, Springer Vieweg 2014. 2. J. Hromkovic: Theoretical Computer Science. Springer 2004. Further reading: 3. M. Sipser: Introduction to the Theory of Computation, PWS Publ. Comp.1997 4. J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley 2006. 5. I. Wegener: Theoretische Informatik. Teubner. More exercises and examples in: 6. A. Asteroth, Ch. Baier: Theoretische Informatik | ||||

Prerequisites / Notice | During the semester, two non-obligatory test exams will be offered. | ||||

252-0866-00L | Digital Medicine I: Introduction to Programming Only for Human Medicine BSc | 2 credits | 2G | H.‑J. Böckenhauer, D. Komm | |

Abstract | This lecture gives an introduction to programming in Python and an overview of basic problem solving strategies and design principles for efficient algorithms and data structures. | ||||

Learning objective | To learn basic principles of programming in Python and to apply them for implementing algorithmic approaches for solving simple computational problems. | ||||

Content | This lecture has two goals. On the one hand, an introduction to programming is given, using Python as a sample language. This introduction includes the basic programming principles such as truth values, variables, data types, conditional statements, loops, and functions. On the other hand, basic data structures (like stacks, queues, or search trees) and important concepts of algorithm design are presented and implemented in Python to efficiently solve basic algorithmic tasks on these data structures. The main focus lies on general-purpose design techniques for efficient algorithms, such as the greedy method, dynamic programming, or the divide and conquer strategy. These techniques are demonstrated with many examples from practice. | ||||

Lecture notes | All learning materials will be provided during the course. |