Sluiten Help Print
 Cursus: 202001360
 202001360Algorithmic Discrete Mathematics
 Cursus informatie
Cursus202001360
Studiepunten (ECTS)5
CursustypeOnderwijseenheid
VoertaalEngels
Contactpersoonprof.dr. M.J. Uetz
E-mailm.uetz@utwente.nl
Docenten
 Vorige 1-5 van 86-8 van 8 Volgende 3
 Tutor dr.ir. P. van 't Hof Docent dr.ir. R. Langerak Tutor R.F.J. van Lingen Docent dr. B. Manthey Tutor dr. L. Pehlivan
Collegejaar2020
Aanvangsblok
 2A
AanmeldingsprocedureZelf aanmelden via OSIRIS Student
Inschrijven via OSIRISJa
 Cursusdoelen
 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 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
 Inhoud
 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 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 forth week are devoted to structural, algorithmic, and combinatorial problems that lie in the core of discrete and combinatorial mathematics: Students under- stand 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 (second order, linear) recurrence relations using the characteristic polynomial, as well as generating functions.
 Participating study
 Bachelor Applied Mathematics
 Participating study
 Bachelor Technical Computer Science
 Module
 Module 7
Verplicht materiaal
Book
 Discrete and Combinatorial Mathematics: An Applied Introduction, Ralph P. Grimaldi, Pearson, 2003 (5th ed.). ISBN: 978-0201726343
Aanbevolen materiaal
-
Werkvormen
Assessment
 Aanwezigheidsplicht Ja

Hoorcollege

Opdracht

Vragenuur

Werkcollege

Toetsen
 Algorithmic Discrete Mathematics
 Sluiten Help Print