| Area of Mathematics: | Computational and Applied Mathematics (ECAM) |
||
| Semester: | 6ο | ||
| Course ID: | 62401 | ||
| Course Type: | Elective | ||
| Teaching hours per week: | Theory: 3 | Practice: 0 | Laboratory: 0 |
| ECTS : | 5 | ||
| Eclass: | |||
| Instructors: | |||
Description
Introduction to Algorithms and Complexity. Design and Analysis Techniques: Greedy, Divide and Conquer, Dynamic Programming. Graph Algorithms: Depth First Search, Breadth First Search, Minimum Spanning Tree, Shortest Paths. Sorting Algorithms. Matrix Multiplication. Polynomial Complexity and NP-hard problems. Decision problems. Combinatorial Optimization. Complexity Classes P and NP. NP-complete problems and Polynomial Reductions. The Knapsack problem. The Traveling Salesman problem. Approximation Algorithms. Parallel and Distributed Algorithms.
Bibliography
- Design and Analysis of Distributed Algorithms, N. Santoro. Wiley, 2006
- The design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ullman. Addison-Wesley Publishing Company, 1974.
- The Mobile Agent Rendezvous Problem in the Ring, E. Kranakis, D. Krizanc, E. Markou. Morgan & Claypool Publishers, 2010
- Computers and Intractability: A Guide to the Theory of NP-Completeness, M. Garey, D. Johnson. W. H. Freeman and Company, 1979
