Algorithms and Complexity
Description

The concept of efficient computation - computing resources - time, space. Algorithms complexity, optimal algorithms. Basic algorithm designing and analyzing techniques. Divide-and-Conquer. Greedy algorithms. Minimum spanning tress, the algorithms of Prim and Kruskal. Undirected graphs: depth-first-search. Cut points and biconnected components. Matching in bipartite graphs. Directed graphs: finding strongly connected components. Depth-first-search. Shortest path: Dijkstra, Bellman-Ford, topological ordering and shortest paths in directed acyclic graphs. Problem complexity. Examples. Computational models. Turing machine. Non-deterministic Turing machine. Universal Turing machine. Complexity classes and general relations among complexity classes. The concepts of reduction (logarithmic space – polynomial time) and completeness. The classes P and NP. NP-completeness. Cook’s Theorem. Some NP-complete problems (satisfiability and variants, graph-theoretic problems, integer programming). Strong and weak NP-completeness.

Division: Computational Mathematics and Informatics
Instructors:

Recommended Literature:

Program of Studies:
Undergraduate Studies
Semester: H
ECTS: 6
Hours per week (Lec/Tut/L): 2/2/0
Code: IC438
Course type: Elective
Compulsory course for the specialization
"Informatics and Computational Mathematics"
Erasmus students: No




keyboard_arrow_up