Το μάθημα αποτελεί μία πλήρη περιήγηση στις τεχνικές σχεδιασμού και μαθηματικής αναλύσεως των αλγορίθμων, με έμφαση στις ιδιότητές τους από την σκοπιά της υπολογιστικής πολυπλοκότητάς τους. Τα καλυπτόμενα θέματα περιλαμβάνουν: τεχνικές σχεδιασμού αλγορίθμων, όπως διαίρει-και-βασίλευε, άπληστοι αλγόριθμοι, δυναμικός προγραμματισμός, και γραμμικός προγραμματισμός. Επίσης, διδάσκονται αλγόριθμοι γραφημάτων σχετιζόμενοι με ζευγνύοντα δένδρα, συντομότερα μονοπάτια, ροές και ταιριάσματα). Διδάσκονται ακόμη τυχαιοκρατικοί και ‘online’ αλγόριθμοι. Τέλος γίνεται εισαγωγή στην πληρότητα NP και τις τάξεις της, καθώς και στους προσεγγιστικούς αλγορίθμους.

Το μάθημα καλύπτει τις βασικές αρχές του σχεδιασμού και ανάλυσης αλγορίθμων.

Με την επιτυχή ολοκλήρωση του μαθήματος ο φοιτητής /τρια θα είναι σε θέση να:

• γνωρίζει να αναλύει αλγορίθμους και να εκτιμά την συμπεριφορά τους στην χειρότερη, την μέση και την επιμερισμένη περίπτωση
• γνωρίζει και εφαρμόζει τις θεμελιώδεις τεχνικές σχεδίασης αλγορίθμων (διαίρει και βασίλευε, απληστία, δυναμικός προγραμματισμός, γραμμικός προγραμματισμός)
• γνωρίζει τυχαιοκρατικούς και online αλγορίθμους
• γνωρίζει πώς να εφαρμόζει βασικούς αλγορίθμους που αφορούν τα γραφήματα
• διακρίνει τις κλάσεις πολυπλοκότητας και να γνωρίζει τις προσεγγιστικές τεχνικές επίλυσης προβλημάτων NPC

Τελικός βαθμός μαθήματος: 20% εργασία + 25% οι τρεις σειρές προβλημάτων + 55% βαθμός τελικής εξέτασης

Από μια εβδομάδα για καθένα από τα κάτωθι group ζητημάτων:

Εισαγωγή στην έννοια του αλγορίθμου
Insertion sort και Merge sort
Ρυθμός αύξησης συναρτήσεων

Αλγόριθμοι Διαίρει-και-Βασίλευε (Binary search, Recurrences)
Master theorem

Διαίρει-και-Βασίλευε: Strassen πολλαπλασιαμός πινάκων
Κάτω όριο των comparison-based αλγορίθμων ταξινόμησης
(Deterministic) Quicksort

Randomized Quicksort. Πιθανοκρατική ανάλυσης μέσης επίδοσης του Randomized Quicksort
Bucket sort. Πιθανοκρατική ανάλυση
Περίληψη βασικών δομών δεδομένων: Συνδεδεμένες Λίστες, (Κυκλικές) Ουρές, Δένδρα, Σωρός (Ταξινόμηση με σωρό)

Order statistics (i-th smallest, median)
The Dictionary problem: Hashing
The Dictionary problem: Cuckoo hashing
The Dictionary problem: Bloom filter
The Dictionary problem: B^(+)-δένδρα

Άπληστοι αλγόριθμοι
Knapsack problem (Fractional)
Huffman encoding
Interval Scheduling [proof: the greedy stays ahead] Optimal cache replacement with perfect knowledge of the future [proof: the exchange argument] Vertex cover

Δυναμικός Προγραμματισμός
Weighted Interval Scheduling
Longest Common Subsequence
0/1 Knapsack
Edit Distance
Γραμμικός Προγραμματισμός
Weighted Vertex Cover

Graph-Theoretic αλγόριθμοι
Depth/Breadth traversal
Minimum Spanning Tree
Αλγόριθμος Kruskal
Αλγόριθμος Prim

Shortest-paths

Maximum-flow
Maximum-flow/min-cut applications

NP and computational intractability
Polynomial-time reductions: By simple equivalence, By special case to general case, By encoding with gadgets

NP-completeness
Approximation algorithms

Online (competitive) algorithms