ALGORITHMS AND COMPLEXITY
| Title | ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ / ALGORITHMS AND COMPLEXITY |
| Code | NGE-07-01 |
| Faculty | Sciences |
| School | Informatics |
| Cycle / Level | 1st / Undergraduate |
| Teaching Period | Winter |
| Coordinator | Georgios Christodoulou |
| Common | Yes |
| Status | Active |
| Course ID | 40002972 |
Programme of Study: PPS-Tmīma Plīroforikīs (2019-sīmera)
Registered students: 69
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| GENIKĪ KATEUTHYNSĪ | YPOCΗREŌTIKO KATA EPILOGĪ | 7 | 4 | 5 |
| Academic Year | 2020 – 2021 |
| Class Period | Winter |
| Instructors from Other Categories | |
| Weekly Hours | 3 |
| Class ID | 600176715
|
Course Type 2021
Specialization / Direction
Course Type 2016-2020
- Scientific Area
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
- Face to face
Digital Course Content
- e-Study Guide https://qa.auth.gr/en/class/1/600176715
- eLearning: https://elearning.auth.gr/course/view.php?id=8618
Erasmus
The course is also offered to exchange programme students.
Language of Instruction
- Greek (Instruction, Examination)
- English (Examination)
Prerequisites
Required Courses
- NCO-01-04 DISCRETE MATHEMATICS
- NCO-02-02 PROBABILITIES & STATISTICS
- NCO-02-03 DATA STRUCTURES
- NCO-04-03 ALGORITHMS
Learning Outcomes
Knowledge: Understand the mapping of problems to algorithmic solutions (such as graph problems). Understand the performance limitations of algorithms for specific problem categories. Understand different complexity classes (P, NP, NP hard, NP complete). Learn different techniques for solving difficult problems through the use of algorithms (such as exponential algorithms, randomized algorithms, approximation algorithms)
Skills: Understand algorithm reductions (the relationship between different problems with regards to their computational demands)
General Competences
- Adapt to new situations
- Make decisions
- Work autonomously
- Design and manage projects
- Advance free, creative and causative thinking
Course Content (Syllabus)
Linear Programming (e.g., duality, simplex method, interior point algorithms). Number-theoretic algorithms (e.g., modular arithmetic, primality testing, integer factorization). Randomized algorithms. Approximation algorithms. Probabilistic analysis. Online algorithms and competitive analysis. Local Search.
Keywords
Complexity, Algorithms
Educational Material Types
- Notes
- Slide presentations
- Book
Use of Information and Communication Technologies
Use of ICT
- Use of ICT in Course Teaching
Course Organization
| Activities | Workload | ECTS | Individual | Teamwork | Erasmus |
|---|---|---|---|---|---|
| Lectures | 39 | ✓ | |||
| Reading Assigment | 48 | ✓ | ✓ | ||
| Written assigments | 60 | ✓ | ✓ | ||
| Exams | 3 | ✓ | |||
| Other / Others | |||||
| Total | 150 |
Student Assessment
Description
Written exams on the covered material (book, lecture notes, presentations, exercises). Comprehension theoretical/programming exercises whose grade is additive to the grade of the final exams.
Student Assessment methods
- Written Exam with Short Answer Questions (Summative)
- Written Exam with Extended Answer Questions (Summative)
- Performance / Staging (Formative, Summative)
- Written Exam with Problem Solving (Formative, Summative)
Bibliography
Course Bibliography (Eudoxus)
1. Michael Sipser. Εισαγωγή στην Θεωρία Υπολογισμού. Πανεπιστημιακές Εκδόσεις Κρήτης, 2007.
2. J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005.
Additional bibliography for study
1. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein: Εισαγωγή στους Αλγόριθμους, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012.
Last Update
10-04-2022
