
At the end of the course the student is able to:
 use and explain elementary data structures like lists, heaps, binary trees, and priority queues
 use and explain elementary algorithms like sorting, traversing and updating data structures, and basic optimization problems
 analyse the time complexity of algorithms and operations on data structures, e.g. using the Master Theorem or recursions, and use dynamic programming
 use and understand the Euclidean algorithm, in fact the “grand daddy of all algorithms” (Knuth), in particular its computational efficiency, and its relevance in applications such as, e.g., RSA public key encryption
 use, explain and design algorithms on graphs and networks, such as computation of shortest paths, spanning trees and maximum flows
 solve second order linear recurrence relations using characteristic polynomials or generating functions
 solve complex combinatorial counting problems using the method of (linear or exponential) generating functions
 Apply the (extended) Euclidean algorithm to integers and polynomials.
 recognise and apply properties of groups
 to derive the symmetry group of a given set and to calculate the number of orbits with the aid of Burnside’s Theorem.
 work with ring and integral domains
 recognise under what conditions an integral domain is a field
 to work with the concept of vector space over an arbitrary field
 work with the classification of finite fields
 work with simple examples of linear code
 investigate and understand when two algebraic structures are isomorphic
 use and explain all components of RSA public key encryption, including all algorithmic underpinnings



The first two weeks of “Discrete Mathematics” are devoted to the understanding of elementary data structures, and their use in the design and theoretical analysis of classic discrete algorithms. This includes basic principles and techniques to analyse the time and space complexity of algorithms, worstcase and averagecase. The data structures include heaps, binary trees, as well as priority queues. Algorithms that are dealt with are for sorting, computational problems with permutations, the Euclidean algorithm to compute the greatest common divisor, the computation of shortest paths, and minimum spanning trees. General algorithmic techniques that are introduced are divide and conquer, as well as dynamic programming. (Some of these algorithms are implemented using the Python programming language, as part of the graph isomorphism implementation project.)
The third and fourth weeks are devoted to structural, algorithmic, and combinatorial problems that lie in the core of discrete and combinatorial mathematics: Students understand the algorithmic power of duality on the example of maximum flows and minimum cuts, the characterization of graph classes by means of forbidden minors on the example of planarity, and learn how to solve advanced combinatorial counting problems using two different techniques, namely solving (secondorder, linear) recurrence relations using the characteristic polynomial, as well as generating functions.
The "Algebra" part of the course provides an introduction to abstract algebra and some of its applications. Three families of algebraic structures are introduced and studied: groups, rings and fields. Roughly speaking groups are generalisations of the set of integers equipped with addition. Rings are generalisations of the set of integers equipped with both addition and multiplication. Fields are generalisations of the set of rational numbers equipped with addition, multiplication and division by nonzero numbers. The generalisations go as far as finite structures and structures in which the operation(s) are noncommutative. The backbones of the course are permutations, finite fields. Permutations and symmetries are used in certain counting problems, such as in how many essentially different ways, taking into account the symmetries, can we paint the faces of a cube using three colours. The theory of groups and rings is used to analyse a specific public key crypto system known as RSA. Also the algorithmic principles behind RSA are treated, e.g. the Euclidean algorithm and modular exponentiation. As an application of the theory of finite fields, a brief introduction to finite codes is provided.
Topics covered:
 Integers and integers module n
 Group Theory, Orbits, Stabilizers
 Cosets & Lagrange Theorem
 Counting problems: Burnside’s theorem
 Rings and Fields
 Polynomial Rings
 Finite Fields
 Linear codes
 RSA Public Key Encryption





Bachelor Applied Mathematics 
  Required materialsRecommended materialsInstructional modesTestsExam


 