Preparatory Courses (PreMaster), Auflagenkurse
Six different PreMaster courses will be given, distributed over the academic year from October to September. Below you find short descriptions of the contents of those courses.
 Mathematics 1 & 2

Mathematics 1
This course covers the basic definitions and results from linear algebra and calculus as required in various areas of computer science, e.g. algorithms and data structures, computer graphics, cryptography and security, network design.
At the end of the course, students will be able to apply concepts and results from linear algebra and calculus to new applications. They will be able to prove simple results in linear algebra and calculus.
Content Linear Algebra
 groups, rings, fields
 vector spaces, basis, dimension, subspaces
 endomorphisms, rank, image, kernel, matrices
 linear systems of equations, Gauss elimination
 determinants, eigenvalues, eigenvectors, diagonaliozation
Content Calculus
 sequences and infinite series
 continuity, ε/δ formulations
 diffferentiability, derivatives
 integrals
Mathematics 2
This course covers the basic definitions and results from combinatorics, probability theory and stochastic as required in various areas of computer science, e.g. algorithms and data structures, cryptography and security, network design, network protocols. Furthermore, it covers the basics of several statistical tests.
At the end of the course, students will be able to apply concepts and results from combinatorics and stochastic to new applications. They will be able to prove simple results in combinatorics and stochastic. Students will be able to apply the basics of statistics to empirical studies.
Content Combinatorics
 counting
 graphs, paths, trees, connected components, dags,...
 modelling with graphs
Content Probability Theory
 discrete probability theory
 independence, random varaibles, expectation, variance
 bounds: Markov, Chebyshev, Chernoff
 distributions: binomial, Poisson
 continuous probability theory
 density function, cumulative probability
 normal distribution
 law of large numbers, central limit theorem
 basics of statistics: quantile, confidence interval, hypothesis tests, regression
 Software Engineering 1 & 2

Software Engineering 1
The module Software Engineering 1 provides an introduction into programming. It covers the basics of imperative and objectoriented programming languages. The language used for practical exercises is Ja
Contents:
 imperative programming: variables, assignment, iteration, conditional, datatypes, functions, parameter passing mechanisms
 objectoriented programming: classes, methods, inheritance, dynamic method binding, interfaces
 generic datatypes
 elements of functional programming: lambda expressions in Java
 specification of syntax of programming languages (contextfree grammars, derivation trees, BackusNaurForm)
A large part of the course are lab exercises.
Software Engineering 2
The module Software Engineering 2 covers relevant foundational topics of modelbased software development as well as of relational database design.
Content Modelbased software development:
 modelbased software development process models
 domainspecific modeling language (syntax, semantics)
 UML (Unified Modeling Language): class diagram, use case diagrams, sequence diagrams, statecharts, activity diagrams
 modelbased testing techniques
Content Relational Database Systems:
 relational data model (integrity constraints, relational algebra, and relational calculus)
 SQL (data definition language, data integrity, data manipulation language, query language)
 query optimization
 functional dependencies and database schema design (3rd NF and BCNF)
 transactions (atomicity, recovery, synchronisation) Exercises: paper and pen (3 times per week)
 Soft Skills

This module treats two main aspects of socalled soft skills:
 Presentation skills for technical material in texts and talks, efficient reading of technical texts. Common pitfalls like copyright problems and plagiarism are addressed. This part takes about 3 lectures to complete. We will do a miniseminar with assignments and discuss the produced results in class.
 Core project management skills: project setups, usual work procedures, documentation aspects, selfmanagement, time management, IT tools to use in project management. This takes about 6 lectures. We will also do small miniproject to apply these techniques in practice.
 Models and Algorithms 1 & 2

Models and Algorithms 1
The goal of Models and Algorithm 1 is to provide basic knowledge on data structures and algorithms and their analysis.
Introduction to Design and Analysis of Algorithms
 pseudocode
 runtime analysis with Onotation
 introductory examples
Basic data structures
 arrays, queues, stacks
 heaps and heapsort
 search trees
 hashing
Basic graph algorithms
 shortest paths
 minimum spanning tree
 network flow
Algorithm design techniques
 greedy algorithms
 divide and conquer
 dynamic programming
Models and Algorithms 2
The goal of Models and Algorithms 2 is to provide basic knowledge about computability and complexity of computational problems, especially about concepts like undecidability, NPcompleteness, and approximating and randomized algorit
Introduction to computability
 Regular grammars and finite automata
 Turing machines and decidability
 Undecidable languages: diagonalization, reduction
 Nondeterminism
Introduction to complexity
 Complexity classes: P and NP
 NPcompleteness: NPcomplete problems, master reduction, reductions
 Approximation algorithms: for example for knapsack, coloring, vertex cover and TSP problems
 Randomized algorithms: e.g. randomized Quicksort, randomized rounding
 Systems 1 & 2

Systems 1
This course gives an introduction into the design of digital circuits and systems, including design at the gate level and design of more complex systems at the register transfer level, and into the organisation and design of modern computer systems, in particular the efficient interplay of hardware and software in processor desig
Learning Objectives
After attending this course, students are able to
 describe the design flow for digital systems from specification to realisation
 explain and apply models and methods of Boolean algebra and automata theory to digital systems design
 realise digital designs of medium complexity
 analyse and evaluate digital designs with respect to given design goals
 describe the organisation of modern computer systems
 describe and apply basic design principles guiding computer systems design
 analyse and evaluate computer systems with respect to performance and cost metrics
 create simple assembly language programs
Highlevel structure of lecture and exercises
 Introduction to digital design: signals, continuous vs. discrete, analog vs. digital, digital and binary systems
 Models at the logic level: switches, gates, Boolean algebra, Boolean functions, representations for Boolean functions
 Combinational logic design: combinational circuits, canonical representations, complete gate sets, design goals, minimisation of twolevel (K diagram) and multilevel logic
 Sequential logic design: models of time, latches, flipflops, register, counters, automata (finite state sets, deterministic, complete), structures of sequential circuits (Mealy, Moore), equivalence, reduction, state minimisation, state encoding
 Binary numbers and codes: positional notation systems, unsigned and signed fixed point numbers, floating point numbers, basic arithmetic, binary codes
 Register transfer level: combinational elements (multiplexer, encoder, ...), sequential elements (registers, memories), arithmetic components (add/sub/multiply/divide), controller and data path, register transfer level design steps and examples
 Technological realisation: physics basics, semiconductors, transistors in MOS structure, realising switches and gates in MOS technology, design and manufacturing of integrated circuits, Moore's law, trends in nanoelectronics
 Introduction to computer architecture: classes of computers, trends in technology and cost
 Instruction set architecture and assembly language: MIPS instruction set and assembly programming, the roles of compiler, linker, assembler and loader, classifications of instruction set architectures, IA32 architecture
 Performance evaluation: processor performance equation, contributing factors, performance evaluation metrics, Amdahl's law
 Processor design: MIPS datapath and controller, singlecycle implementation, multicycle implementation
 Pipelining: principle and achievable speedup, MIPS datapath and controller for pipelining, structural hazards, data hazards (forwarding), control hazards (delay slots, static and dynamic branch prediction)
 Memory hierarchy: technology trends, direct mapped and setassociative caches (mapping and finding cache blocks, replacement strategies, writing blocks to memory), processor performance including the memory hierarchy, memory organisation, basic cache optimisation techniques, virtual memory (brief introduction), translation lookaside buffer, case studies for memory hierarchies
 Advanced concepts: deep pipelining, pipeline scheduling, multiple issue processors (superscalar, VLIW)
Exercises
 Pencil and paper exercises: Boolean algebra, logic functions, design of combinational and sequential functions, number representations and codes, arithmetic components, register transfer level design, processor performance, processor design, memory hierarchies
 practical MIPS assembler programming
Systems 2
This module is a highlevel summary of softwareoriented systems lectures as taught in many typical CS Bachelor programs; typical examples would be Introduction to Operating Systems, Introduction to Computer Networks, or a Distributed Systems class.
The emphasis is on practical aspects, enabling participants to work productively closer to the systems interface. This entails both practical work (using, e.g., a shell, writing BASH scripts, ...) as well as programming work (using, e.g., systemlevel OS APIs like the socket interface or the process management interfac
Main content
Techniques, facts:
 Concurrency vs. parallelism; processes, threads. Programming abstractions for that.
 Simple schedulers: round robin, FCFS, MLFB
 Coordination techniques: why are they needed (race conditions, concurrent access), examples for such techniques (lock variable, semaphore, condition variables)
 Deadlock as a phenomenon; simple techniques for avoidance
 Networking: shared medium with MAC protocol, Internet and routing, transport (TCP, semantics).
 Distributed systems: client/server. Server models (one process, multiple threads, ...). Programming models. Enable participants to write a simple web application.
Skills
 Linux command line interface, bash with simple bash programming
 Compile a Linux kernel, kernel modules (monolithic kernel vs. modulebased kernel?)  this is optional.
 Makefiles: what are they, why needed
 Simple concurrent/parallel programming. Eg. matrix multiplication with varying number of threads
 Optionally: Write a very simple scheduler in a simulation environment
 A little bit of C, a little bit of Python (needed for the web framework).
 Socket programming
 Writing a SIMPLE client/server application using sockets (ECHO)
 Optionally: Web frameworks: use a simple Web framework to build a web application.
Highlevel structure of lecture and exercises
Rough lecture schedule
 Execution model of a program, context of a processor/memory, instruction pointer in CPU. (Skip: Caching) Minimal ideas about assembler > simplified
 Calling a subroutine, from there to interrupt handling. notion to switch between execution threads. Notion of threads and concurrent, interleaved execution. Thread table. Programming models.
 introduction to C
 Generalize to processes: protection between executing threads. Explain requirements for memory management. Protection context. Process switches. Process table. Process states. Blocking as a new notion for processes. Programming models, again.
 Scheduling: goal, simple mechanisms. Preemption yes/no.
 Coordination mechanisms: locks, semaphores. Integration with process management.
 Programming patterns with semaphores. critical section. producer/consumer. reader/writer (only one, best focus on reader/writer). (time permitting: priority inversion., concept of a deadlock
 Memory management. Start from simple swapping, relocation, address indirection, virtual memory. Address translation.
 Virtual memory: paging strategies. Understand relation to process management. Time scales!
 NEtworking 1: packets, shared medium, MAC protocols.
 Networking 2: Internet.
 Networking 3: Transport layer, basic ideas about TCP's jobs and mechanisms. Socket interface. Libraries like AMQP (here only simple things; patterns below in distributed systems?).
 Networking 4: Example socket programming. ECHO server, basic concepts. Connectionless, connectionoriented.
 Distributed Systems 1: Client/server. Web server. Hierarchies of servers. Server farms.
 Distributed Systems 2: Web frameworks. Programming for distributed systems. Tools. (Also things like: version control e.g., GIT; build server like Jenkins; remote management tools like Ansible or Puppet; Vagrant).
Exercises will be decided jointly with participants. Examples include, but are not limited to or comprising all of the following ones:
 CPU simulator: To understand instruction pointer, context, interrupts. (To be coordinated with PreMaster course Systems 1)
 A brief C introduction; write example programs in C.
 Signals as highlevel interrupts. Write a signal handler in (typically, in C). Test it, e.g., SIGHUP or SIGTERM handler.
 Write multithreaded programs in C. Write multiprocess programs in C. Test performance on multicore machines. Test things like thread/process creation time. Write programs for interprocess communication between processes, using shared memory.
 Use a scheduling simulator to play with scheduling algorithms.
 Write semaphorebased programs in different variants. Many examples. Try them out. Write alternative implementations of semaphores (e.g., different release scheduling in Passeeren).
 Write socket programs in C. Write AQMP programs in Python, using different patterns.
 Write a simple Web application, using a Web framework. database backend, etc. Fullfledged development and deployment cycle (DevOps): code in GIT, deploy by vagrant, install by ansible, triggered checkout.
Teaching style
This module will likely be a Reading class/inverted class room, depending on number of participants! Participants will be assigned textbook chapters to read and discuss them in class. Likely, one class meeting per week, with an additional homework discussion meeting.
 Foundations of HumanComputerInteraction

Today, learnability, accessibility and the barrier free utilization of software systems are mandatory in systems design. Basic challenges are to develop means and tools which convey the design rationale to the user and which help to identify unnecessary cognitive burdens not associated with the task to be accomplished. A methodological repertoire is needed to support the design process from its very beginning. The required knowledge and competences comprise essential physiological and psychological concepts and theories, as well as tools and techniques for system design and legal requirements.
Topics
 Basic principles of cognition
 Design guidelines and heuristics
 Natural user interfaces
 Cooperation support
 Social media design
 Enterprises 2.0
 Usability engineering
 International standards
 Ethical and legal requirement