Algorithmic Graph Theory (ΠΛ4)

Graduate Courses Outlines - Department of Mathematics

General

School	School of Science
Academic Unit	Department of Mathematics
Level of Studies	Graduate
Course Code	ΠΛ4
Semester	2
Course Title	Algorithmic Graph Theory
Independent Teaching Activities	Lectures (Weekly Teaching Hours: 3, Credits: 7.5)
Course Type	Special Background
Prerequisite Courses	-
Language of Instruction and Examinations	Greek
Is the Course Offered to Erasmus Students	Yes (in English)
Course Website (URL)	See eCourse, the Learning Management System maintained by the University of Ioannina.

Learning Outcomes

Learning outcomes	This course aims at introducing to students fundamental algorithmic techniques for solving problems related and modeled by graphs. After successfully passing this course the students will be able to: Understand graph theory. Design and analyze algorithms for graph problems. Understand difficult problems on graph classes.
General Competences	Search for, analysis and synthesis of data and information, with the use of the necessary technology Working independently Team work Project planning and management All the above will give to the stundetns the opportunity to work in an international multidisciplinary environment.

Syllabus

1. Fundamental Graph Theory
2. Algorithmic and Combinatorial Graph Problems
3. Complexity Classes and Parameterized Algorithms
4. Chordal graphs, Comparability graphs, Split graphs
5. Permutation graphs, Interval graphs, Cographs, Threshold graphs
6. Algorithmic problems and width parameters

Teaching and Learning Methods - Evaluation

Delivery	In the class
Use of Information and Communications Technology	Use of projector and interactive board during lectures.
Teaching Methods	Activity Semester Workload Lectures 39 Study and analysis of bibliography 78 Preparation of assignments and interactive teaching 70.5 Course total 187.5
Student Performance Evaluation	Written work (50%) Essay / report (20%) Public presentation (30%)

Attached Bibliography

• Cormen, Leiserson and Rivest, Introduction to Algorithms, MIT Press, 1990. (επίσης μεταφρασμένο από τις Πανεπιστημιακές Εκδόσεις Κρήτης)
• Δομές δεδομένων, αλγόριθμοι και εφαρμογές c++, Sahnii Sartaj, Εκδόσεις α. Τζιόλα
• Αλγόριθμοι σε C++, μέρη 1-4: θεμελιώδεις έννοιες, δομές δεδομένων, ταξινόμηση, αναζήτηση, Robert Sedgewick, Εκδόσεις Κλειδάριθμος
• Αλγοριθμοι σε C, μέρη 1-4: θεμελιώδεις έννοιες, δομές δεδομένων, ταξινόμηση, αναζήτηση, Robert Sedgewick, Εκδόσεις Κλειδάριθμος
• Mark Allen Weiss, Data Structures & Algorithm Analysis in Java, Addison-Wesley
• Clifford A. Shaffer, Data Structures and Algorithm Analysis, ebook, http://people.cs.vt.edu/shaffer/Book/
• A. Aho, J. Hopcroft, J. Ullman, (1983). Data Structures and Algorithms, Addison-Wesley.
• Baase, S., Computer Algorithms - Introduction to Design and Analysis, Second Edition, , Addison Wesley, Reading, Massachusetts, 1988.
• Knuth, D., The Art of Computer Programming - Vol. 1 Fundamental Algorithm, Addison Wesley, Reading, Massachusetts, 1973.
• Knuth, D., The Art of Computer Programming - Vol. 2 SemiNumerical Algorithm, Addison Wesley, Reading, Massachusetts, 1973.
• Knuth, D., The Art of Computer Programming - Vol. 3 Sorting and Searching, Addison Wesley, Reading, Massachusetts, 1973.