Techniques for the design and analysis of algorithms, an introduction to the theory of computational complexity. Techniques for asymptotic estimation of computational complexity, criteria for algorithm selection, polynomial-time algorithms. Divide-and-conquer algorithms, estimation of computational complexity for recursive algorithms using the Master Theorem, mergesort, quicksort, selection, closest pair of points, convex hull. Linear-time sorting. Binary search, interpolation search, list update, amortized analysis. Greedy algorithms, proof of correctness using the exchange argument. Dynamic Programming, knapsack problem, longest common subsequence, longest increasing subsequence, optimal linear partitioning, matrix chain multiplication, the traveling salesman problem. Graph algorithms. Shortest paths, computing shortest paths with label update, Bellman-Ford, Dijkstra's, Floyd-Warshall and Johnson's algorithms. Maximum flow and minimum cut, Ford-Fulkerson and Edmonds-Karp algorithms, applications. Computability and computational complexity. Complexity classes and reductions. The classes P and NP, NP-complete problems. Space complexity classes. Approximation algorithms, vertex cover, set cover, the traveling salesman problem. Probabilistic algorithms, algorithm for minimum cut. Laboratory: A series of algorithmic problems to be solved in C++.
- Teacher: Δημήτριος Φωτάκης
Τομέας: Τεχνολογίας Πληροφορικής και Υπολογιστών
Κατεύθυνση: Πληροφορικής, Ροή Λ
ECTS : 6
Study Load : theory 4, lab 1
Language : el
Learning Outcomes : The course comprises the core course in the broader area of Algorithms and Computational Complexity. Elements of algorithmic thinking and the approach applied by the field of computational complexity, some basic concepts of algorithm design and analysis, and some fundamental algorithms are taught in scattered core courses (Computer Programming, Programming Techniques, Foundations of Computer Science). Given this, the course material aims to provide students with a comprehensive, systematic, and in-depth view of the area of Algorithms and Computational Complexity. Specifically, the course material covers and addresses in a unified and systematic way: The basic techniques for the design and analysis of efficient data structures and algorithms (such as the concept of hierarchical organization and data management for the area of data structures, and the techniques of divide-and-conquer, greedy algorithms, dynamic programming and local improvement). Specific data structures and algorithms as a result of applying these techniques (e.g., priority queues, disjoint set management, sorting algorithms, algorithms for computing minimum spanning trees and shortest paths, and algorithms for computing maximum cut/minimum flow). Furthermore, the course material attempts a systematic introduction to the basic principles of Computational Complexity, starting with a systematic approach to the fundamental concept of reduction and its applications in the area of algorithms and computational complexity, and delving into the theory of NP-completeness. The course is accompanied by a laboratory component, where students are asked to solve algorithmic problems in an optimal way, designing and implementing their algorithms. The goal of the course is for students to acquire sufficient cognitive background and fluency in applying all the above concepts, ideas, and techniques in the field of Algorithms and Computational Complexity.