Algorithms and Complexity (6ΕΠ05)
Instructor : Evripides Markou
Assistant : Giachoudis Nikolaos
Course typeElective
Semester6
TermSpring Semester
ECTS5
Teaching hours3
Laboratory hours
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.
Course objectives
  • Analysis of algorithms (proof of correctness and complexity)
  • Methods for designing algorithms
  • Computationally ‘hard’ problems
  • Parallel and Distributed algorithms
Textbooks/Bibliography
  • Εισαγωγή στους Αλγόριθμους (σε έναν τόμο), T. Cormen, C. Leiserson, R. Rivest, C. Stein, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012
  • Αλγόριθμοι, S. Dasgupta, C. Papadimitriou, U. Vazirani, Εκδόσεις Κλειδάριθμος ΕΠΕ, 2009
  • Σχεδιασμός Αλγορίθμων, J. Kleinberg, E. Tardos, Εκδόσεις Κλειδάριθμος ΕΠΕ, 2009
  • Αλγόριθμοι και Πολυπλοκότητα, Ε. Ζάχος, Σημειώσεις, Εθνικό Μετσόβιο Πολυτεχνείο, 2007
  • Αλγόριθμοι, Π. Μποζάνης, Εκδόσεις Α. Τζιολα & Υιοί Α. Ε., 2006
  • Ανάλυση και σχεδίαση αλγορίθμων, L. Anany, Εκδόσεις Α. Τζιολα & Υιοί Α. Ε., 2008
  • 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
Assessment method
One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.
Course material
Notes