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 | No |
| Status | Active |
| Course ID | 40002972 |
Programme of Study: PPS-Tmīma Plīroforikīs (2019-sīmera)
Registered students: 1
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| GENIKĪ KATEUTHYNSĪ | YPOCΗREŌTIKO KATA EPILOGĪ | 7 | 4 | 5 |
| Academic Year | 2013 – 2014 |
| Class Period | Winter |
| Faculty Instructors | |
| Weekly Hours | 4 |
| Class ID | 40049948
|
Course Type 2016-2020
- Background
- General Knowledge
- 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/40049948
- At the Website of the School: http://delab.csd.auth.gr/~tsichlas/algorithms.html
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
Understand the mapping of problems to algorithmic solutions (e.g., as graph problems, linear
programs. Use advanced algorithmic techniques (e.g., randomization, approximation) to solve problems. Apply advanced analysis techniques (e.g., amortized, probabilistic, etc.) to algorithms.
General Competences
- Adapt to new situations
- Make decisions
- Work autonomously
- Design and manage projects
- Advance free, creative and causative thinking
Course Content (Syllabus)
Advanced data structures (e.g., Fibonacci heaps). String-based data structures and algorithms (e.g., suffix arrays, suffix trees, tries). 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. Amortized analysis. Probabilistic analysis. Online algorithms and competitive analysis. Local Search.
Keywords
Complexity, Algorithms, Data Structures
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 | 52 | ✓ | |||
| Reading Assigment | 40 | ||||
| Written assigments | 20 | ✓ | ✓ | ||
| Other / Others | 13 | ||||
| Total | 125 |
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
19-09-2013
