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
Data Structures
Course Contents (Syllabus):
Introduction to Algorithms. Abstract Data Types. Array, List, Stack, Queue, Heap. Sorting Algorithms. Trees and Graphs. Binary Search Trees, AVL, Red-Black Trees. Sets, Union-Find and Dictionary Structures. Hashing. Heaps and Priority Queues.
Required course, 2nd year
Prerequisites and/or related courses:
Discrete Mathematics, Introduction to Programming, Object-oriented Programming, Algorithms and Complexity, Graph Theory
Objectives:
- Introduction to algorithms
- Abstract Data Types
- Analysis (proof of correctness and complexity) of basic and advanced data structures
Teaching Methods:
Theory lectures (4h/week) and lab exercises (1h/week).
Assessment methods:
One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.
Teaching Material: Notes, Slides
Recommended reading:
- Data structures, P. Bozanis, Ekdosis A. Tziola and Sons A. E., 2006 (in Greek).
- Data structures, algorithms and applications in C++, Sahnii Sartaj, Ekdosis A. Tziola and Sons A. E., 2004 (in Greek).
Graph Theory
Course Contents (Syllabus):
Basic Graph Parameters. Directed Graphs, Cliques, Bipartite and Planar Graphs. Euler and Hamilton Cycles. Minimum Spanning Trees, Depth First Search, Breadth First Search, Shortest Paths. Maximum Flows. The Matching problem. NP-complete problems: Vertex Cover, Vertex Coloring, Maximum Clique.
Elective course, 4th year
Prerequisites and/or related courses:
Discrete Mathematics, Data Structures, Algorithms and Complexity.
Objectives:
- Modeling algorithmic problems in graphs
- Analyzing and proving graph properties
- Graph 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:
- Graph Theory and Algorithms, I. Manolopoulos, A. Papadopoulos, K. Tsichlas, Ekdosis Neon Technologion Mon. EPE, 2013 (in Greek).
- Introduction to Graphs, L. Kirousis, X. Mpouras, P. Spirakis, Y, Stamatiou, Ekdosis G. Dardanos - K. Dardanos O.E., 1999 (in Greek).
Theory of Computation
Course Contents (Syllabus):
Finite automata and regular expressions. Pushdown automata and context-free grammars. Turing machines and Church's thesis. Undecidability. Computational complexity.
Elective course, 3rd year
Prerequisites and/or related courses:
Discrete Mathematics, Introduction to Programming, Object-oriented Programming, Algorithms and Complexity, Graph Theory
Objectives:
- Automata and formal grammars
- Turing Machines- Determinism vs non-determinism
- Unsolvability
- Polynomial hierarchy
- P vs NP
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:
- M. Sipser, ‘’Introduction to Theory of Computation’’, Panepistimiakes Ekdosis Kritis, 2007 (in Greek).
- H. R. Lewis & Ch. Papadimitriou, ‘’ Elements of Computation’’, Kritiki, 2005 (in Greek).
Bibliography:
- M. Sipser, ‘’Introduction to Theory of Computation’’, Panepistimiakes Ekdosis Kritis, 2007 (in Greek).
Algorithms and Complexity in Biology
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. Polynomial Complexity and NP-hard problems. Decision problems. Combinatorial Optimization. Complexity Classes P and NP. NP-complete problems and Polynomial Reductions. The Protein Folding problem in the Hydrophobic-Polar model and the Levinthal’s paradox (NP-hardness results and approximation algorithms). The Longest Common Subsequence problem (known algorithms and hardness in P).
Post-graduate course.
Prerequisites and/or related courses:
Discrete Mathematics, Algorithms and Complexity, Graph Theory, Theory of Computation, Computational Biology
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)