Graph Theory
Course Contents (Syllabus):
Basic Graph Parameters. Directed Graphs, Cliques, Bipartite and Planar Graphs. Euler and Hamilton Cycles. Minimum Spanning Trees, Depth First Search, Breadth First Search, Shortest Paths. Maximum Flows. The Matching problem. NP-complete problems: Vertex Cover, Vertex Coloring, Maximum Clique.
Elective course, >= 3rd year
Prerequisites and/or related courses:
Discrete Mathematics, Data Structures, Algorithms and Complexity.
Objectives:
- Modeling algorithmic problems in graphs
- Analyzing and proving graph properties
- Graph Algorithms
Teaching Methods:
Theory lectures (4h/week) and additionally seminars (2h/ 3 weeks) solving exercises.
Assessment methods:
One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.
Teaching Material: Notes
Recommended reading:
- Graph Theory and Algorithms, I. Manolopoulos, A. Papadopoulos, K. Tsichlas, Ekdosis Neon Technologion Mon. EPE, 2013 (in Greek).
- Introduction to Graphs, L. Kirousis, X. Mpouras, P. Spirakis, Y, Stamatiou, Ekdosis G. Dardanos - K. Dardanos O.E., 1999 (in Greek).
Distributed Computing
Course Contents (Syllabus):
Distributed algorithms by autonomous agents. Examples in geometric environments, communication networks, distributed databases, internet. Models of computation. Basic algorithms for message-passing systems. Algorithms and models of computation for robots in 2D/3D space. Algorithms for mobile agents in networks. Implementation and visualization of distributed algorithms. The Look-Compute-Move model. Synchronous and asynchronous systems. The Rendezvous (Gathering) problem. The Pattern problem. The Exploration problem. Faulty networks with hostile nodes. Algorithms for discovering hostile nodes. Fault tolerant algorithms. The Graph Searching problem. Reliable communication in faulty environments.
Post-graduate course.
Prerequisites and/or related courses:
Discrete Mathematics, Design and Analysis of Algorithms, Graph Theory, Theory of Computation, Distributed Systems
Bibliography:
- Algorithmic Theory of Distributed Computing (in greek), Markou, E., Kranakis, E., Pagourtzis, A., & Krizanc, D. (2015). Kallipos, Open Academic Editions. https://dx.doi.org/10.57713/kallipos-476