# Search result: Catalogue data in Spring Semester 2020

CAS in Computer Science | ||||||

Focus Courses and Electives | ||||||

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

263-4656-00L | Digital Signatures | W | 4 credits | 2V + 1A | D. Hofheinz | |

Abstract | Digital signatures as one central cryptographic building block. Different security goals and security definitions for digital signatures, followed by a variety of popular and fundamental signature schemes with their security analyses. | |||||

Objective | The student knows a variety of techniques to construct and analyze the security of digital signature schemes. This includes modularity as a central tool of constructing secure schemes, and reductions as a central tool to proving the security of schemes. | |||||

Content | We will start with several definitions of security for signature schemes, and investigate the relations among them. We will proceed to generic (but inefficient) constructions of secure signatures, and then move on to a number of efficient schemes based on concrete computational hardness assumptions. On the way, we will get to know paradigms such as hash-then-sign, one-time signatures, and chameleon hashing as central tools to construct secure signatures. | |||||

Literature | Jonathan Katz, "Digital Signatures." | |||||

Prerequisites / Notice | Ideally, students will have taken the D-INFK Bachelors course "Information Security" or an equivalent course at Bachelors level. | |||||

263-4660-00L | Applied Cryptography Number of participants limited to 150. | W | 8 credits | 3V + 2U + 2P | K. Paterson | |

Abstract | This course will introduce the basic primitives of cryptography, using rigorous syntax and game-based security definitions. The course will show how these primitives can be combined to build cryptographic protocols and systems. | |||||

Objective | The goal of the course is to put students' understanding of cryptography on sound foundations, to enable them to start to build well-designed cryptographic systems, and to expose them to some of the pitfalls that arise when doing so. | |||||

Content | Basic symmetric primitives (block ciphers, modes, hash functions); generic composition; AEAD; basic secure channels; basic public key primitives (encryption,signature, DH key exchange); ECC; randomness; applications. | |||||

Literature | Textbook: Boneh and Shoup, “A Graduate Course in Applied Cryptography”, Link. | |||||

Prerequisites / Notice | Ideally, students will have taken the D-INFK Bachelors course “Information Security" or an equivalent course at Bachelors level. | |||||

263-5806-00L | Computational Models of Motion for Character Animation and Robotics | W | 6 credits | 2V + 2U + 1A | S. Coros, M. Bächer, B. Thomaszewski | |

Abstract | This course covers fundamentals of physics-based modelling and numerical optimization from the perspective of character animation and robotics applications. The methods discussed in class derive their theoretical underpinnings from applied mathematics, control theory and computational mechanics, and they will be richly illustrated using examples ranging from locomotion controllers and crowd simula | |||||

Objective | Students will learn how to represent, model and algorithmically control the behavior of animated characters and real-life robots. The lectures are accompanied by programming assignments (written in C++) and a capstone project. | |||||

Content | Optimal control and trajectory optimization; multibody systems; kinematics; forward and inverse dynamics; constrained and unconstrained numerical optimization; mass-spring models for crowd simulation; FEM; compliant systems; sim-to-real; robotic manipulation of elastically-deforming objects. | |||||

Prerequisites / Notice | Experience with C++ programming, numerical linear algebra and multivariate calculus. Some background in physics-based modeling, kinematics and dynamics is helpful, but not necessary. | |||||

272-0300-00L | Algorithmics for Hard Problems Does not take place this semester. This course d o e s n o t include the Mentored Work Specialised Courses with an Educational Focus in Computer Science A. | W | 5 credits | 2V + 1U + 1A | ||

Abstract | This course unit looks into algorithmic approaches to the solving of hard problems, particularly with moderately exponential-time algorithms and parameterized algorithms. The seminar is accompanied by a comprehensive reflection upon the significance of the approaches presented for computer science tuition at high schools. | |||||

Objective | To systematically acquire an overview of the methods for solving hard problems. To get deeper knowledge of exact and parameterized algorithms. | |||||

Content | First, the concept of hardness of computation is introduced (repeated for the computer science students). Then some methods for solving hard problems are treated in a systematic way. For each algorithm design method, it is discussed what guarantees it can give and how we pay for the improved efficiency. A special focus lies on moderately exponential-time algorithms and parameterized algorithms. | |||||

Lecture notes | Unterlagen und Folien werden zur Verfügung gestellt. | |||||

Literature | J. Hromkovic: Algorithmics for Hard Problems, Springer 2004. R. Niedermeier: Invitation to Fixed-Parameter Algorithms, 2006. M. Cygan et al.: Parameterized Algorithms, 2015. F. Fomin, D. Kratsch: Exact Exponential Algorithms, 2010. | |||||

272-0302-00L | Approximation and Online Algorithms | W | 5 credits | 2V + 1U + 1A | H.‑J. Böckenhauer, D. Komm | |

Abstract | This lecture deals with approximative algorithms for hard optimization problems and algorithmic approaches for solving online problems as well as the limits of these approaches. | |||||

Objective | Get a systematic overview of different methods for designing approximative algorithms for hard optimization problems and online problems. Get to know methods for showing the limitations of these approaches. | |||||

Content | Approximation algorithms are one of the most succesful techniques to attack hard optimization problems. Here, we study the so-called approximation ratio, i.e., the ratio of the cost of the computed approximating solution and an optimal one (which is not computable efficiently). For an online problem, the whole instance is not known in advance, but it arrives pieceweise and for every such piece a corresponding part of the definite output must be given. The quality of an algorithm for such an online problem is measured by the competitive ratio, i.e., the ratio of the cost of the computed solution and the cost of an optimal solution that could be given if the whole input was known in advance. The contents of this lecture are - the classification of optimization problems by the reachable approximation ratio, - systematic methods to design approximation algorithms (e.g., greedy strategies, dynamic programming, linear programming relaxation), - methods to show non-approximability, - classic online problem like paging or scheduling problems and corresponding algorithms, - randomized online algorithms, - the design and analysis principles for online algorithms, and - limits of the competitive ratio and the advice complexity as a way to do a deeper analysis of the complexity of online problems. | |||||

Literature | The lecture is based on the following books: J. Hromkovic: Algorithmics for Hard Problems, Springer, 2004 D. Komm: An Introduction to Online Computation: Determinism, Randomization, Advice, Springer, 2016 Additional literature: A. Borodin, R. El-Yaniv: Online Computation and Competitive Analysis, Cambridge University Press, 1998 | |||||

401-3052-05L | Graph Theory | W | 5 credits | 2V + 1U | B. Sudakov | |

Abstract | Basic notions, trees, spanning trees, Caley's formula, vertex and edge connectivity, 2-connectivity, Mader's theorem, Menger's theorem, Eulerian graphs, Hamilton cycles, Dirac's theorem, matchings, theorems of Hall, König and Tutte, planar graphs, Euler's formula, basic non-planar graphs, graph colorings, greedy colorings, Brooks' theorem, 5-colorings of planar graphs | |||||

Objective | The students will get an overview over the most fundamental questions concerning graph theory. We expect them to understand the proof techniques and to use them autonomously on related problems. | |||||

Lecture notes | Lecture will be only at the blackboard. | |||||

Literature | West, D.: "Introduction to Graph Theory" Diestel, R.: "Graph Theory" Further literature links will be provided in the lecture. | |||||

Prerequisites / Notice | Students are expected to have a mathematical background and should be able to write rigorous proofs. NOTICE: This course unit was previously offered as 252-1408-00L Graphs and Algorithms. | |||||

401-3632-00L | Computational Statistics | W | 8 credits | 3V + 1U | M. H. Maathuis | |

Abstract | We discuss modern statistical methods for data analysis, including methods for data exploration, prediction and inference. We pay attention to algorithmic aspects, theoretical properties and practical considerations. The class is hands-on and methods are applied using the statistical programming language R. | |||||

Objective | The student obtains an overview of modern statistical methods for data analysis, including their algorithmic aspects and theoretical properties. The methods are applied using the statistical programming language R. | |||||

Content | See the class website | |||||

Prerequisites / Notice | At least one semester of (basic) probability and statistics. Programming experience is helpful but not required. |

- Page 2 of 2 All