Algorithms

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 matching.
• Introduction to computational complexity.

1. “ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ”, Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Εκδόσεις ΙΤΕ - Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN 978-960-524-473-6, 2016
2. “ΑΛΓΟΡΙΘΜΟΙ”, Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Εκδόσεις Κλειδάριθμος ΕΠΕ, ISBN 978-960-461-211-6, 2009
3. “ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ”, Jon Kleinberg, Eva Tardos, Εκδόσεις Κλειδάριθμος ΕΠΕ, ISBN 978-960-461-207-9, 2009

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.