Algorithms and Complexity

Course ID
6ΕΠ05
Επίπεδο
Undergraduate
Είδος
Optional (compulsory)
Εξάμηνο
6
Περίοδος
Spring Semeter
ECTS
5
Ώρες Θεωρίας
3
Ώρες Εργαστηρίου
-

Instructor

Assistant

Giaxoudis Nikolaos

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

  • ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ , Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, ΙΤΕ/ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΚΡΗΤΗΣ,  1η/2016, ΗΡΑΚΛΕΙΟ ΚΡΗΤΗΣ, 59359780
  • ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ, JON KLEINBERG, EVA TARDOS, “ΕΚΔΟΣΕΙΣ ΚΛΕΙΔΑΡΙΘΜΟΣ ΕΠΕ”, 1η/2009, ΑΘΗΝΑ, 13898
  • ΑΛΓΟΡΙΘΜΟΙ, SANJOY DASGUPTA, CHRISTOS PAPADIMITRIOU, UMESH VAZIRANI, ΕΚΔΟΣΕΙΣ ΚΛΕΙΔΑΡΙΘΜΟΣ ΕΠΕ, 1η/2009, ΑΘΗΝΑ, 13583
  • Αλγόριθμοι, 2η Έκδοση, Μποζάνης Παναγιώτης Δ., “ΕΚΔΟΣΕΙΣ Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε. “, 1η/2006, ΘΕΣ/ΝΙΚΗ, 68369726
  • Ανάλυση και Σχεδίαση Αλγορίθμων, 3η Έκδοση, Levitin Anavy, Mάνος Ρουμελιώτης (επιμέλεια), ΕΚΔΟΣΕΙΣ Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε., 3η/2018, ΘΕΣ/ΝΙΚΗ, 68370088
  • ΑΛΓΟΡΙΘΜΙΚΗ ΘΕΩΡΙΑ ΚΑΤΑΝΕΜΗΜΕΝΩΝ ΥΠΟΛΟΓΙΣΜΩΝ, ΕΥΡΙΠΙΔΗΣ ΜΑΡΚΟΥ, “Ελληνικά Ακαδημαϊκά Ηλεκτρονικά Συγγράμματα και Βοηθήματα – Αποθετήριο “”Κάλλιπος””” ,  1η/2016, ΑΘΗΝΑ, 59303549

Assessment method

One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.

Course material

Notes