Please ensure Javascript is enabled for purposes of website accessibility

Παρουσίαση/Προβολή

Επιλέχθηκε εικόνα

ERASMUS: Introduction to Algorithms 2026-2027

(23Υ205) -  Christos Zaroliagis

Περιγραφή Μαθήματος

This course introcudes the students to fundamental techniques for the design and analysis of algorithms.

Syllabus

  1. Elementary Concepts in the Design and Analysis of Algorithms

The concept of algorithm, applications and importance of algorithms. The concept of efficiency, a model for measuring efficiency, methods for analyzing the complexity of algorithms, technological importance of efficient algorithms.

  1. Basic Concepts in the Analysis and Complexity of Algorithms

Efficiency and time complexity, optimal algorithms, methods in analyzing the complexity of algorithms, asymptotic complexity, correctness of algorithms.

  1. Elementary Algorithms and Data Structures

Arrays, lists, stacks, queues, trees. Algorithms for finding the minimum or maximum in a set of elements. Algorithms for merging sorted lists, insertion sort, binary search, counting element tuples. Heap, priority queues, and their application in sorting (heapsort).

  1. Stable Matching

Problem formulation and applications. The propose-and-reject algorithm. Correctness and complexity analysis of the algorithm. Efficient implementation of the algorithm.

  1. The Divide-and-Conquer Technique

Generic description of the divide-and-conquer technique. The merge-sort algorithm. The algorithm for counting inversions. Recurrence relations and methods for their solution.

  1. Graphs and Graph Algorithms

Graphs as fundamental model of networks and systems. Basic properties and features of graphs. Graph connectivity. Graph traversal and searching algorithms: breadth-first-search (BFS), depth-first-search (DFS). Extensions/applications of BFS and DFS for computing connected components, topological sorting, strongly connected components, and for checking graph bipartiteness.

  1. The Greed Technique

Generic description of the greed technique. Scheduling algorithms: interval scheduling, scheduling all intervals, scheduling to minimize lateness. Network optimization algorithms: minimum spanning tree (Kruskal’s and Prim’s algorithms), shortest paths (Dijkstra’s algorithms). Efficient implementation of network optimization algorithms.

  1. The Dynamic Programming Technique

Generic description of the dynamic programming technique. Efficient application and implementation of dynamic programming. Algorithms for weighted interval scheduling and knapsack problems.

Ημερομηνία δημιουργίας

Τετάρτη 16 Οκτωβρίου 2024

Σελίδα μαθήματος

  • Περίγραμμα

    Course Objectives/Goals

    Upon conclusion of the course the students ought to be able to:

    • Understand fundamental algorithmic concepts and techniques.
    • Apply basic techniques for the solution of fundamental algorithmic problems.
    • Apply basic analysis methods for determining the complexity of algorithms.
    • Apply basic mathematical methods for determining the correctness of algorithms.
    • Understand how to implement efficiently the algorithms taught, and to how to tackle practical issues encountered during implementation.

     

    Upon conclusion of the course the students are expected to have the following skills/competences:

    • Abstracting the core algorithmic sub-problems from given complex problems.
    • Use basic techniques for designing algorithms for fundamental and more complex problems.
    • Use basic methods for analyzing the complexity and correctness of algorithms.
    • Implement efficiently fundamental algorithms using basic techniques and data structures.

    Bibliography

    • J. Kleinberg and E. Tardos, Algorithm Design, Pearson Addison-Wesley, 2006.
    • T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 3rd Edition, MIT Press, 2009.
    • Mehlhorn and P. Sanders, Algorithms and Data Structures – The Basic Toolbox, Springer, 2008.

    Assessment Methods

    Coursework and final exam (oral and/or written).