DM582: Advanced Algorithms

• Have knowledge of basic algorithms and data structures as well as implementations of such in an imperative programming language, including stacks, queues, search trees, and priority queues, as well as sorting methods and basic graph algorithms.
• Have knowledge of algorithm design techniques and be able to analyze algorithms using asymptotic analysis and be able to compare asymptotic results.
• Be able to use basic mathematical argumentation, including logical expressions, proofs by induction and contradiction, counting techniques, and discrete probability theory.

• Apply the topics on discrete probability theory to estimate the expected running time of algorithms
• Develop and analyze basic randomized algorithms
• Apply techniques from universal hashing to choose hash functions with good expected performance
• Formulate a flow-model for problems resembling those covered in the course
• Apply techniques from the course to assess the amortized time complexity of operations on a data structure

• Randomized algorithms
• Probabilistic analysis of algorithms
• The probabilistic method
• Universal and perfect hashing
• Flows in networks
• Amortized analysis

At the faculty of science, teaching is organized after the three-phase model, i.e., intro, training, and study phase.

• Intro phase: 40 lessons
• Training phase: 30 lessons

A modified variant of a classic lecture is used in the intro phase, where foundational concepts and methods are presented theoretically as well as through examples on concrete data. Questions and discussions are encouraged. The training phase revolves around exercises and discussion topics relating to the material introduced in the preceding intro phase hours. During the training hours, the students can work specifically with the more challenging topics. Questions that arise during the study phase can be brought up during meeting times.