Description:

This is an advanced course about special topics in Algorithms for undergraduate students. It covers the following topics:

• Basic concepts of parallel algorithms with emphasis on multithreaded algorithms and dynamic multithreading. Models for multithreaded computation. A multithreaded implementation of Merge Sort.
• Efficient algorithms for solving systems of linear equations and for matrix inversion.
• Zero sum games. Discrete and fast Fourier transform.
• Elementary number theoretic algorithms. Euclid’s greatest common divisor algorithm. Modular arithmetic and Solving modular linear equations. The Chinese remainder theorem. The RSA public key algorithm.
• Randomized algorithms, random variables and expected values. The Metropolis Algorithm and Simulated Annealing.
• Introduction to approximation algorithms. The vertex-cover problem. The traveling-salesman problem. The set-covering problem. A randomized approximation algorithm for MAX 3-SAT.

Aims – Learning Outcomes

This course aims to introduce students to some special advanced topics in algorithms of great practical value.

Upon successful completion of this course, the students will be able to:

• Understand in depth the concept of parallel and multithreaded algorithms.
• Familiarize themselves with the theoretical background and the techniques necessary in order to solve linear programming problems.
• Become proficient in the application of the Simplex algorithm.
• Understand some important elementary number-theoretic algorithm and the theoretical background of public key cryptosystems.
• Familiarize themselves with the concept of approximation and randomized algorithms.
• Grasp notions from the theory of Computational Complexity, such as reducibility, NP-completeness and the complexity classes P, NP and PSPACE.

Syllabus:

Week #1: Basic concepts of parallel algorithms with emphasis on multithreaded algorithms and dynamic multithreading. Models for multithreaded computation. A multithreaded implementation of Merge Sort.

Week #2: Efficient algorithms for solving systems of linear equations and for matrix inversion.

Week #3: Introduction to linear programming, standard and slack forms. Formulation of problems into linear programs.

Week #4: Transformation into standard and slack form. The Simplex algorithm. The notion of duality in linear programming.

Week #5: Zero sum games. Discrete and fast Fourier transform.

Week #6: Elementary number theoretic algorithms. Euclid’s greatest common divisor algorithm. Modular arithmetic.

Week #7: Solving modular linear equations. The Chinese remainder theorem. The RSA public key algorithm.

Week #8: Randomized algorithms, random variables and expected values.

Week #9: The Metropolis Algorithm and Simulated Annealing.

Week #10: Introduction to approximation algorithms. The vertex-cover problem.

Week #11: The traveling-salesman problem. The set-covering problem.

Week #12: A randomized approximation algorithm for MAX 3-SAT.

Week #13: The class P of polynomial problems and the class NP of polynomial-time verifiable problems. The concept of reducibility and NP-completeness. Some characteristic NP-complete problems. The class PSPACE.

• “ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ”, Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Εκδόσεις ΙΤΕ - Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN 978-960-524-473-6, 2016
• “ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ”, Jon Kleinberg, Eva Tardos, Εκδόσεις Κλειδάριθμος ΕΠΕ, ISBN 978-960-461-207-9, 2009
• “ΑΝΑΛΥΣΗ ΚΑΙ ΣΧΕΔΙΑΣΗ ΑΛΓΟΡΙΘΜΩΝ”, Neapolitan Richard, Εκδόσεις Broken Hill Publishers Ltd, ISBN 978-992-535-111-4, 2023

Educational and learning methods:

• Face to face lectures
• The learning process is supported through the Ionian University e-learning platform (https://opencourses.ionio.gr/courses/DDI210/)

Evaluation methods:

Individual assignments (100%) emphasizing:

• knowledge assimilation,
• creative thinking,
• analytic and synthetic ability,
• written exposition and
• capacity for original work.

The above criteria are communicated to the students during the first teacher-student meeting.