Algorithms and Complexity

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

Updated: 4-Oct-2017                                                                               email: emarkou@ucg.gr