Computational thinking

Learning Results

Upon successful completion students will have sufficient knowledge of

• the basic tools for analyzing algorithms,
• the general purpose algorithmic techniques like Divide and Conquer, Dynamic Programming, Greedy principle,
• elementary notions from graph theory and algorithms for solving typical graph problems like finding the shortest path, the maximum spanning tree, etc.,
• the fundamental complexity classes like P, NP, NP-complete.

The material presented in this course is fundamental and essential for the students to be able to attend other subject-specific courses.

Skills acquired

Retrieve, analyse and synthesise data and information, with the use of necessary technologies, Work in teams, Work in an interdisciplinary team, Advance free, creative and causative thinking

This course presents mathematical tools for analyzing algorithms, formal algorithmic technics, fundamental graph algorithms and basic complexity classes.

In particular, the course material includes

• mathematical methods for calculating elementary computational operations (ECO) executed by iterative algorithms
• solution methods for recurrence relations for calculating the ECOs of recursive algorithms
• asymptotic analysis of algorithms: classes O, Ω, ο, ω,
• general purpose algorithmic techniques like Divide and Conquer, Dynamic Programming, Greedy principle,
• typical graph algorithms like the Bfs algorithm, the Dfs algorithm, the Dijkstra‘s algorithm for finding shortest paths in a graph, algorithms for finding the maximum spanning tree (Prim’s algorithm, Krukal’s algorithm, etc)
• decision problems and their complexity classes: P. NP, NP-complete. Reductions and equivalence relations between problems.

1. Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT Press
2. Dasgupta, Papadimitriou, Vazirani, Algorithms, ‎ McGraw-Hill
3. Roughgarden, Algorithms Illuminated –Parts I, II, III , Soundlikeyourself Publishing
4. Kleinberg, Tardos, Algorithm design, Pearson