For course-related announcements see the individual courses' pages. Please note that all pages linked to below are in Greek.

## Undergraduate courses

**Introduction to Computer Programming** (fall semester)

Introduction to Computer Science. Algorithms and Data Structures, programs, programming languages. Pascal. Specification, design, coding, verification, documentation and maintenance of programs. Basic data structures, control structures, procedures, recursion, parameter passing.

**Introduction to Computer Science** (spring semester)

The goal of this course is to introduce students to fundamental computer principles and various areas of Computer Science. The course covers subjects of Theoretical Computer Science (logic for Computer Science, automata, formal grammars, computability and complexity), number representation and operations (binary arithmetic, number systems, binary representation, fixed point and floating point operations, encoding), computer architecture (processor architecture, instruction format-machine language, assembly language, memory organization-peripheral devices-storage devices), as well as an introduction to system software (operating system, compiler-interpreter), applications (databases, file management, etc), and various programming paradigms (functional, logical, object-oriented programming).

**Foundations of Computer Science** (fall semester)

Introduction to fundamental computing principles and notions: computational problems as formal languages, models of computation, computability, algorithms, complexity classes, completeness, automata, formal grammars, hardness results, logic in computer science. The course also offers an introduction to the functional programming paradigm with the Haskell programming language and a set of lab assignments that help in demonstating and clarifying some of the theoretical concepts taught.

**Algorithms & Complexity** (fall semester)

Techniques for asymptotic program analysis and algorithm selection criteria. Algorithm design techniques: divide and conquer, dynamic programming, greedy algorithms. Applications to graph theory (depth-first search, breadth-first search, minimum spanning tree, shortest path). Sorting and searching. Algebraic problems (evaluation of polynomials, matrix multiplication). Polynomial-time algorithms and NP-complete problems.

**Computability & Complexity** (spring semester)

Computability: Logical foundation of computer science. Historical review on the problem of decidability of mathematical statements, and solvability or computability of problems. Simple equivalent models of computation: Turing machines, WHILE programs. Induction and recursion, encoding and semantics. Fixed-point theory. Arithmetic hierarchy. Relations between complexity classes. Reductions and completeness. Oracles. Polynomial hierarchy. Probabilistic, interactive and counting classes. Advanced topics from the theory of formal grammars. Applications to programming language syntax.

**Number Theory & Cryptography** (fall semester)

Classical cryptography: Caesar, Vigenere, coincidence index, Kasiski test. Shannon's perfect secrecy, one-time pad. Symmetric cryptography. Block cryptosystems: Feistel networks, DES, AES. Operation modes. Message authentication codes (MACs). Stream ciphers. Νumber theory: modular arithmetic, quadratic residues, Chinese Remainder Theorem, Legendre's theorem, Euler's "phi" function, Legendre and Jacobi symbols. Primality tests: Fermat, Solovay-Strassen, Miller-Rabin, AKS algorithm. Factorisation: rho method, Dixon, B-smoothness. Public-key cryptography. RSA and Rabin cryptosystem. Disrete logarithm and ElGamal cryptosystem. Diffie – Hellman key exchange. Cryptographic assumptions and reductions. Digital signatures: RSA, ElGamal, DSS, one-time, blind, undeniable signatures. Hash functions. Zero knowledge identification schemes: Fiat-Shamir and Feige-Fiat-Shamir. Computational Complexity theory. Arthur-Merlin games, interactive proof systems. Zero knowledge proofs.

**Automata & Computational Models** (spring semester)

Languages and their representations. Grammars, context-sensitive and context-free grammars. Finite automata and regular grammars. Pushdown automata. Turing Machines. Automata and language recognition. Applications in programming languages syntax. (Un)decidability and complexity problems.

## Graduate courses

**Theoretical Computer Science I: Algorithms & Complexity** (fall semester)

*Computational Models - Turing Machines*: Problems, Algorithms and Languages. Equivalence of Computational Models, Turing Machines, Time and Space bounds, multiple strings,
linear speedup, nondeterminism.
*Computability & Undecidability*: The Universal Turing Machine, Simulation, Diagonalization, The Halting Problem,
Recursive and Recursive Enumerable Sets. Rice's Theorem, Recursive Unseparability, Second-Order Logic, Undecidability-Incompleteness, Fagin's Theorem.
*Complexity Classes*: Complexity measures, time and space classes, Hierarchy Theorems, Gap Theorem.
*Space Computation*: The classes **L** and **NL**, Savitch's Theorem, Immerman-Szelepscényi Theorem, Undirected Reachability and Reingold's Theorem.
*Reductions & NP-Completeness*: Different types of reductions (Karp, Cook, Cook[1], tt) and relations among them, **NP**-completeness, Cook's Theorem,
**NP**-complete problems, pseudopolynomial algorithms, Ladner's Theorem, density, sparse sets, The "Berman-Hartmanis" conjecture, NP-isomorphism, padding.
*Function Problems*: The classes co**NP** and Δ**NP**, Function classes and reductions, the classes **PLS** and **PPAD**.
*Randomized Computation*: Randomized algorithms and complexity classes, quantifier notation and related results, Error reduction, semantic and syntactic classes,
the "P vs BPP" question.
*Non-Uniform Complexity*: Boolean circuits, the class P_{/poly}, Turing Machines with advice, parallel computation, circuit lower bounds, natural proofs.
*Oracles & The Polynomial Hierarchy*: Oracles and oracle classes, the polynomial-time hierarchy and related theorems, The BPP Theorem, Operator-defined classes.
*Interactive Proofs*: The class **IP**, Arthur-Merlin games, Shamir's Theorem, Probabilistically Checkable Proofs and the PCP Theorem.
*-Counting Complexity*: The class #**P** and #**P**-completeness, Toda's Theorem, Gaps, the class **TotP**.
*Parameterized Complexity*: Fixed-Parameter Tractability, FPT Reductions, The Classes para**NP**, **XP** and **W[P]**, The W-Hierarchy and the A-Hierarchy.

**Theoretical Computer Science II: Computational Complexity** (spring semester - every 4 years)

**Theoretical Computer Science II: Number Theory & Cryptography** (spring semester - every 4 years)

**Theoretical Computer Science II: Parallel Algorithms & Complexity** (spring semester - every 4 years)

**Theoretical Computer Science II: Advanced Data Structures** (spring semester -every 4 years)

**Theoretical Computer Science II: Computational Geometry** (spring semester - every 4 years)

**Network Algorithms & Complexity** (spring semester)

**Cryptography & Complexity** (fall semester)

**Approximation Algorithms** (spring semester)

**Algorithmic Game Theory** (spring semester)

**Social Networks** (spring semester)

**Logic, Automata and Games** (εαρινό εξάμηνο)

## Past courses

**Fortran and Object Oriented Programming** (spring semester)

Introduction to Fortran programming language: simple data types, variables, constants, expressions, statements. Control
structures: if-then-else, do loop, do while. Programming methodology: iteration, recursion, data structures, algorithms.
Arrays, records, linked lists. Dynamic memory allocations. Subroutines and functions, parameter passing. Input, output, files. Foundations of object-oriented programming: abstract data types, classes, objects, methods, encapsulation, inheritance, polymorphism. Interconnection to other programming languages. Software engineering principles: specifications, design, implementation, verification, documentation and maintenance.