# Search result: Catalogue data in Autumn Semester 2018

Computer Science Teaching Diploma More informations at : Link | ||||||

Additional Requirements (ETH-Masterstudents in PHYS/MATH/CSE) | ||||||

Part 1 | ||||||

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

252-0057-00L | Theoretical Computer Science | O | 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? | |||||

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-0061-00L | Systems Programming and Computer Architecture | O | 7 credits | 4V + 2U | T. Roscoe | |

Abstract | Introduction to systems programming. C and assembly language, floating point arithmetic, basic translation of C into assembler, compiler optimizations, manual optimizations. How hardware features like superscalar architecture, exceptions and interrupts, caches, virtual memory, multicore processors, devices, and memory systems function and affect correctness, performance, and optimization. | |||||

Objective | The course objectives are for students to: 1. Develop a deep understanding of, and intuition about, the execution of all the layers (compiler, runtime, OS, etc.) between programs in high-level languages and the underlying hardware: the impact of compiler decisions, the role of the operating system, the effects of hardware on code performance and scalability, etc. 2. Be able to write correct, efficient programs on modern hardware, not only in C but high-level languages as well. 3. Understand Systems Programming as a complement to other disciplines within Computer Science and other forms of software development. This course does not cover how to design or build a processor or computer. | |||||

Content | This course provides an overview of "computers" as a platform for the execution of (compiled) computer programs. This course provides a programmer's view of how computer systems execute programs, store information, and communicate. The course introduces the major computer architecture structures that have direct influence on the execution of programs (processors with registers, caches, other levels of the memory hierarchy, supervisor/kernel mode, and I/O structures) and covers implementation and representation issues only to the extend that they are necessary to understand the structure and operation of a computer system. The course attempts to expose students to the practical issues that affect performance, portability, security, robustness, and extensibility. This course provides a foundation for subsequent courses on operating systems, networks, compilers and many other courses that require an understanding of the system-level issues. Topics covered include: machine-level code and its generation by optimizing compilers, address translation, input and output, trap/event handlers, performance evaluation and optimization (with a focus on the practical aspects of data collection and analysis). | |||||

Lecture notes | - C programmnig - Integers - Pointers and dynamic memory allocation - Basic computer architecture - Compiling C control flow and data structures - Code vulnerabilities - Implementing memory allocation - Linking - Floating point - Optimizing compilers - Architecture and optimization - Caches - Exceptions - Virtual memory - Multicore - Devices | |||||

Literature | The course is based in part on "Computer Systems: A Programmer's Perspective" (3rd Edition) by R. Bryant and D. O'Hallaron, with additional material. | |||||

Prerequisites / Notice | 252-0029-00L Parallel Programming 252-0028-00L Design of Digital Circuits | |||||

252-0026-00L | Algorithms and Data Structures | O | 7 credits | 3V + 2U + 1A | M. Püschel, D. Steurer | |

Abstract | This course is about fundamental algorithm design paradigms, classic algorithmic problems, and data structures. The connection between algorithms and data structures is explained for geometric and graph problems. For this purpose, fundamental graph theoretic concepts are introduced. | |||||

Objective | An understanding of the design and analysis of fundamental algorithms and data structures. | |||||

Content | Es werden grundlegende Algorithmen und Datenstrukturen vorgestellt und analysiert. Dazu gehören auf der einen Seite Entwurfsmuster für Algorithmen, wie Induktion, divide-and-conquer, backtracking und dynamische Optimierung, ebenso wie klassische algorithmische Probleme, wie Suchen und Sortieren. Auf der anderen Seite werden Datenstrukturen für verschiedene Zwecke behandelt, darunter verkettete Listen, Hashtabellen, balancierte Suchbäume, verschiedene heaps und union-find-Strukturen. Weiterhin wird Adaptivität bei Datenstrukturen (wie etwa Splay-Bäume) und bei Algorithmen (wie etwa online-Algorithmen) beleuchtet. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert. Hierfür werden grundlegende Konzepte der Graphentheorie eingeführt. | |||||

Literature | Th. Ottmann, P.Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011 | |||||

Part 2 | ||||||

Number | Title | Type | ECTS | Hours | Lecturers | |

252-0209-00L | Algorithms, Probability, and Computing | W | 8 credits | 4V + 2U + 1A | E. Welzl, M. Ghaffari, A. Steger, D. Steurer, P. Widmayer | |

Abstract | Advanced design and analysis methods for algorithms and data structures: Random(ized) Search Trees, Point Location, Minimum Cut, Linear Programming, Randomized Algebraic Algorithms (matchings), Probabilistically Checkable Proofs (introduction). | |||||

Objective | Studying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory. | |||||

Lecture notes | Will be handed out. | |||||

Literature | Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest; Randomized Algorithms by R. Motwani und P. Raghavan; Computational Geometry - Algorithms and Applications by M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. |

- Page 1 of 1