ALGORITHMS AND COMPLEXITY
| Title | ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ / ALGORITHMS AND COMPLEXITY |
| Code | ΣΜΥ031 |
| Faculty | Sciences |
| School | Mathematics |
| Cycle / Level | 2nd / Postgraduate |
| Teaching Period | Winter/Spring |
| Coordinator | Georgios Rachonis |
| Common | No |
| Status | Active |
| Course ID | 600025967 |
Programme of Study: PMS Tmīmatos Mathīmatikṓn (2025-2030)
Registered students: 0
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| STATISTIKĪ, MONTELOPOIĪSĪ KAI YPOLOGISTIKES METHODOI | Elective Courses belonging to the selected specialization | Spring | - | 10 |
| Academic Year | 2025 – 2026 |
| Class Period | Spring |
| Faculty Instructors | |
| Weekly Hours | 3 |
| Total Hours | 39 |
| Class ID | 600268440
|
Course Type 2021
Specialization / Direction
Mode of Delivery
- Face to face
Digital Course Content
- e-Study Guide https://qa.auth.gr/en/class/1/600268440
Learning Outcomes
Students will understand in depth the concept of algorithm complexity and especially the notions of polynomial and exponential complexity. They will be familiar with the classification of various problems based on the complexity of their solutions. Furthermore, they will obtain knowledge for exact and approximate algorithms, as well as heuristic and metaheuristic algorithms.
General Competences
- Apply knowledge in practice
- Work autonomously
- Work in an international context
- Generate new research ideas
Course Content (Syllabus)
Algorithm. Types of complexity. Categorization of algorithms. Examples of polynomial time algorithms. Problem complexity. Problem classification acoording to their complexity and their classes. Exact and approximate algorithms. Heuristic and metaheuristic algorithms. Examples of practical exact algorithms with exponential complexity.
Keywords
Algorithm. Complexity of algorithms. Polynomial and exponential complexity.
Educational Material Types
- Notes
- Book
Course Organization
| Activities | Workload | ECTS | Individual | Teamwork | Erasmus |
|---|---|---|---|---|---|
| Lectures | 39 | ✓ | |||
| Reading Assigment | 258 | ||||
| Exams | 3 | ✓ | |||
| Total | 300 |
Student Assessment
Student Assessment methods
- Written Exam with Multiple Choice Questions (Summative)
- Written Exam with Extended Answer Questions (Formative)
- Oral Exams (Formative)
- Written Exam with Problem Solving (Formative)
Bibliography
Additional bibliography for study
"Computational Complexity"
by Ch. Papadimitriou
"Introduction to Algorithms"
by T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein
"Computational Complexity: A Modern Approach"
by S. Arora, B. Barak
Last Update
01-12-2024
