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

The module Software Engineering 1 provides an introduction into programming. It covers the basics of imperative and object-oriented programming languages. The language used for practical exercises is Ja

Contents:

• imperative programming: variables, assignment, iteration, conditional, datatypes, functions, parameter passing mechanisms 
• object-oriented programming: classes, methods, inheritance, dynamic method binding, interfaces 
• generic datatypes 
• elements of functional programming: lambda expressions in Java 
• specification of syntax of programming languages (context-free grammars, derivation trees, Backus-Naur-Form)

A large part of the course are lab exercises.

Software Engineering 2

The module Software Engineering 2 covers relevant foundational topics of model-based software development as well as of relational database design.

Content Model-based software development:

• model-based software development process models
• domain-specific modeling language (syntax, semantics)
• UML (Unified Modeling Language): class diagram, use case diagrams, sequence diagrams, statecharts, activity diagrams
• model-based 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)

This module treats two main aspects of so-called 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 mini-seminar with assignments and discuss the produced results in class.
• Core project management skills: project setups, usual work procedures, documentation aspects, self-management, time management, IT tools to use in project management. This takes about 6 lectures. We will also do small mini-project to apply these techniques in practice.

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

• pseudo-code
• runtime analysis with O-notation
• 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, NP-completeness, 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
• NP-completeness: NP-complete 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

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

High-level 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 two-level (K diagram) and multi-level logic
• Sequential logic design: models of time, latches, flip-flops, 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 nano-electronics
• 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, IA-32 architecture
• Performance evaluation: processor performance equation, contributing factors, performance evaluation metrics, Amdahl's law
• Processor design: MIPS datapath and controller, single-cycle implementation, multi-cycle 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 set-associative 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 look-aside 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 high-level summary of software-oriented 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., system-level 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. module-based 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.

High-level 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, connection-oriented.
• 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 high-level interrupts. Write a signal handler in (typically, in C). Test it, e.g., SIGHUP or SIGTERM handler.
• Write multi-threaded programs in C. Write multi-process programs in C. Test performance on multi-core machines. Test things like thread/process creation time. Write programs for inter-process communication between processes, using shared memory.
• Use a scheduling simulator to play with scheduling algorithms.
• Write semaphore-based 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. Full-fledged 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.

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