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

### Introduction to Programming

Algorithms and programming languages. Programming with C. Program structure. Stepwise refinement. Variables and operators. Statements, data structures, arrays, structures, pointers, functions. Call by value and by reference. Structured programming. Debugging.

### 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, 4th 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).

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