Description:

This course is an introductory course about Algorithms for second year undergraduate students. It covers the following topics:

• The concept of algorithms and their underlying complexity. Fundamental notions for the complexity analysis of algorithms and the required mathematical background.
• Techniques for solving recurrences.
• The quicksort algorithm and lower bounds for sorting.
• Dynamic programming, the optimal subproblem property and matrix-chain multiplication.
• Greedy algorithms, the 0-1 knapsack problem and the fractional knapsack problem.
• Graph representations, breadth-first search, depth-first search and topological sort.
• Minimum spanning trees: Kruskal’s and Prim’s algorithms.
• Single-source shortest paths and all-pairs shortest paths.
• Algorithms for string
• Introduction to computational

Aims – Learning Outcomes

This course aims to introduce students to the concept of algorithms and the basic principles for their design and complexity analysis.

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

• Understand in depth the concept of the algorithm.
• Familiarize themselves with the theoretical background and the techniques necessary in order to solve recurrences and analyze algorithms in terms of their complexity.
• Become proficient in the application of efficient algorithms for searching, sorting, solving dynamic programming problems, traversing graphs, computing the minimum spanning trees and finding the shortest paths from a given source.
• Understand introductory notions from the theory of Computational Complexity.

Syllabus:

Week #1: Introduction to algorithms and their complexity.

Week #2: Growth of functions and asymptotic notation.

Week #3: Techniques for solving recurrences.

Week #4: Divide and conquer.

Week #5: Sorting algorithms.

Week #6: Dynamic programming.

Week #7: Greedy algorithms.

Week #8: Elementary graph algorithms.

Week #9: Algorithms for graph traversal.

Week #10: Algorithms for minimum spanning tress.

Week #11: Algorithms for computing single source shortest paths.

Week #12: String matching algorithms.

Week #13: Introduction to the theory of Computational Complexity.

• “ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ”, Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Εκδόσεις ΙΤΕ - Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN 978-960-524-473-6, 2016
• “ΑΛΓΟΡΙΘΜΟΙ”, Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Εκδόσεις Κλειδάριθμος ΕΠΕ, ISBN 978-960-461-211-6, 2009
• “ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ”, 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/DDI189/)

Evaluation methods:

Written exams (100%) including:

• creative thinking,
• analytic and synthetic ability,
• problem solving and
• elements of theory.

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