Close Help Print
 Course module: 202001360
 202001360Algorithmic Discrete Mathematics
 Course info
Course module202001360
Credits (ECTS)5
Course typeStudy Unit
Language of instructionEnglish
Lecturer(s)
 Previous 1-5 of 106-10 of 10 Next 5
 Lecturer dr. A. Antoniadis Contactperson for the course dr. A. Antoniadis Examiner dr. A. Antoniadis Lecturer dr.ir. P. van 't Hof Lecturer dr. J. de Jong
Starting block
 2A
RemarksPart of module 7 AM/TCS. Minor students: please register for the minor!
Application procedureYou apply via OSIRIS Student
Registration using OSIRISYes
 Aims
 body { font-size: 9pt; font-family: Arial } table { font-size: 9pt; font-family: Arial } 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 second-order linear recurrence relations using characteristic polynomials
 Content
 body { font-size: 9pt; font-family: Arial } table { font-size: 9pt; font-family: Arial } 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, worst-case and average-case. 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.  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 (second-order, linear) recurrence relations using the characteristic polynomial.
 Module
 Module 7
 Participating study
 Bachelor Applied Mathematics
 Participating study
 Bachelor Technical Computer Science
Required materials
Book
 Discrete and Combinatorial Mathematics: An Applied Introduction, Ralph P. Grimaldi, Pearson, 2003 (5th ed.). ISBN: 978-0201726343
Canvas
 Lecture Notes to be made available online
Recommended materials
-
Instructional modes
Assessment
 Presence duty Yes

Assignment

Lecture

Q&A

Tutorial

Tests
 Algorithmic Discrete Mathematics
 Close Help Print