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

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)

In the past



Updated: 4-Oct-2017                                                                               email: emarkou@ucg.gr