Course Contents (Syllabus):
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.
Elective course, 3rd year
Prerequisites and/or related courses:
Discrete Mathematics, Introduction to Programming, Object-oriented Programming, Data Structures, Graph Theory, Theory of Computation
Objectives:
- Analysis of algorithms (proof of correctness and complexity)
- Methods for designing algorithms
- Computationally ‘hard’ problems
- Parallel and Distributed algorithms
Teaching Methods:
Theory lectures (4h/week) and additionally seminars (2h/ 3 weeks) solving exercises.
Assessment methods:
One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.
Teaching Material: Notes
Recommended reading:
- Introduction to Algorithms, T. Cormen, C. Leiserson, R. Rivest, C. Stein, Panepistimiakes Ekdosis Kritis, 2012 (in Greek).
- Algorithm Design, J. Kleinberg, E. Tardos, Ekdosis Klidarithmos EPE, 2009 (in Greek)
- Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, Ekdosis Klidarithmos EPE, 2009 (in Greek)
- Design and Analysis of Algorithms, L. Anany, Ekdosis A. Tziola and Sons A. E., 2008 (in Greek).
Bibliography:
- Introduction to Algorithms, T. Cormen, C. Leiserson, R. Rivest, C. Stein, Panepistimiakes Ekdosis Kritis, 2012 (in Greek).
- Algorithm Design, J. Kleinberg, E. Tardos, Ekdosis Klidarithmos EPE, 2009 (in Greek)
- Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, Ekdosis Klidarithmos EPE, 2009 (in Greek)
- Algorithms and Complexity, E. Zachos, Notes, National Technical University of Athens, 2007 (in Greek).
- Algorithms, P. Bozanis, Ekdosis A. Tziola and Sons A. E., 2006 (in Greek).
- Design and Analysis of Algorithms, L. Anany, Ekdosis A. Tziola and Sons A. E., 2008 (in Greek).
- The design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ullman. Addison-Wesley Publishing Company, 1974.
- Computers and Intractability: A Guide to the Theory of NP-Completeness, M. Garey, D. Johnson. W. H. Freeman and Company, 1979
- Design and Analysis of Distributed Algorithms, N. Santoro. Wiley, 2006
- The Mobile Agent Rendezvous Problem in the Ring, E. Kranakis, D. Krizanc, E. Markou. Morgan & Claypool Publishers, 2010