Courses

The concept of efficient computing - computational resources - time, memory. Algorithm complexity, optimal algorithms. Basic techniques in algorithm analysis and design. Greedy algorithms. The "Divide and Conquer" technique and algorithms. Generated minimum cost trees: Kruskal and Prim's algorithms. Undirected graphs: Depth-first search. Finding partition points and biconnected components. The Matching problem in bipartite graphs. Directed graphs: Finding strongly connected components. Depth-first search. Minimal paths: Dijkstra, Bellman-Ford, topological ordering and minimal paths in DAGs (Directed Acyclic Graphs). Complexity of problems. Examples. Computational models. The Turing machine. Nondeterministic Turing machine. Universal Turing machine. Complexity classes and general relations between complexity classes. The concepts of reduction (logarithmic space - polynomial time) and completeness and their importance. The classes P and NP. Definitions. NP-completeness. Cook's Theorem. Some NP-complete problems (satisfiability and variations, graph-theoretic problems, integer programming). Strong and weak NP-completeness.