Algorithmics I

About this course

The lecture will give an introduction into the theory of algorithms. We will start with tools for analyzing the running time of algorithms, in particular master theorems. Then we will introduce important design principles for efficient algorithm (divide & conquer, greedy algorithms, dynamic programming). For each of these design principles we will see examples from various areas (e.g., computer arithmetic, sorting, searching, graph algorithms). At the same time, we wil develop problem specific data structures, like Fibonacci heaps.

Expected learning outcomes

LO1: The students know basic analysis techniques and design principles
LO2: Apply basic analysis techniques and design principles to concrete algorithmic problems

Indicative Syllabus

• Divide and Conquer algorithms
• Greedy algorithms
• Dynamic programming 
• Algorithms for words, trees and graphs
• Sorting algortihms
• Basic data structures (e.g. binary search trees)