
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 (extended) Euclidean algorithm, 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, maximum flows, stable matching and clustering problems
 solve secondorder linear recurrence relations using characteristic polynomials
 recognise and apply properties of groups
 know and recognise several constructions of groups
 know and work with group homomorphisms and isomorphisms and understand their role in the more general context of mathematics
 work with rings and fields
 apply the (extended) Euclidean algorithm to integers and polynomials
 investigate and understand when two algebraic structures are isomorphic
 understand and describe several applications of Algebra, such as cryptography, the word problem, symmetries and isomorphisms of structures



The first two weeks of the study unit “Algorithmic 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, minimum spanning trees. General algorithmic techniques that are introduced are divide and conquer, as well as dynamic programming.
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 core algorithmic techniques in discrete optimization, next to shortest paths and spanning trees also algorithms for network flows, stable matchings and clustering, the power of duality on the example of maximum flows and minimum cuts, and learn how to solve combinatorial counting problems by means of (secondorder, linear) recurrence relations using the characteristic polynomial.
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 constructions for groups and the understanding of structurepreserving maps. As to applications of algebraic structures, the course addresses encryption based on RSA, the word problem, symmetries and isomorphisms in adjacent mathematical domains.
Topics covered in this course are:
 An overview of algebra and algebraic structures
 Constructions of groups: integers, integers modulo n, groups of matrices, groups of symmetry, groups of functions, finitely generated groups, cyclic groups
 Basics in group theory: group operations, cosets, the Lagrange Theorem, group homomorphisms and isomorphisms, quotients, free groups, group presentation
 Rings and ideals; fields
 Applications of algebra, including encryption, data analysis and the recognition of structurepreserving transformations




 VoorkennisLinear maps between vector spaces; calculations with matrices; properties of real and complex numbers; working with functions and relations 
Bachelor Applied Mathematics 
Bachelor Technische Natuurkunde 
  Verplicht materiaalBookDiscrete and Combinatorial Mathematics: An Applied Introduction, Ralph P. Grimaldi, Pearson, 2003 (5th ed.). ISBN: 9780201726343 
 CanvasLecture Notes, to be provided online 

 Aanbevolen materiaalWerkvormenOverig onderwijsAanwezigheidsplicht   Ja 

 ToetsenExam


 