## Teaching

### 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

- 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

- 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

- 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).

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)

### In the past

Updated: 21-Sep-2021                                                                               email: e<lastname>@dib.uth.gr