Εδώ
| Βιβλίο |
|
|
| Τίτλος | Εισαγωγή στους Αλγορίθμους | Introduction to Algorithms (3rd ed.) |
| Συγγραφείς | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein |
| Γλώσσα | Ελληνική | Αγγλική Εδώ |
| Εβδομάδα | Ημερομηνία | Αντικείμενο διάλεξης | Μελέτη ελλ. βιβλίο |
| 1 | 07/03/2024 | α) Εισαγωγή στην έννοια του αλγορίθμου β) Insertion sort και Merge sort γ) Ρυθμός αύξησης συναρτήσεων |
Κεφ. 1 Κεφ. 2 Κεφ. 3 I2A_SLIDES_SORTING |
| 2 | 11-14/03/2024 | α) Ασκήσεις β) Αλγόριθμοι Διαίρει-και-Βασίλευε (Binary search, Recurrences) γ) Master theorem, Akra-Bazzi theorem |
Κεφ. 4 Binary Search demo I2A_SLIDES_MASTER Akra-Bazzi theorem |
| 3 | 21/03/2024 | α) Διαίρει-και-Βασίλευε: Strassen πολλαπλασιαμός πινάκων β) Κάτω όριο των comparison-based αλγορίθμων ταξινόμησης γ) (Deterministic) Quicksort |
Κεφ. 4 Κεφ. 7 Κεφ. 8.1 MergeSort demo, MergeSort code QuickSort demo I2A_SLIDES_DIVIDE_and_CONQUER |
| 4 | 28/03/2024 | α) Quicksort. Ανάλυση Μέσης Περίπτωσης β) Υπολογιστική Γεωμετρία: Εύρεση του Πλησιεστέρου Ζεύγους Σημείων γ) Bucket sort. Πιθανοκρατική ανάλυση |
Κεφ. 5 Κεφ. 7 Κεφ. 8.4 Κεφ. 33.4 Average case analysis of Quicksort Closest Pair of Points HeapSort demo |
| 5 | 01-04/04/2024 | α) Order statistics (i-th smallest, median) β1) The Dictionary problem: Cuckoo hashing β2) The Dictionary problem: Bloom filter β3) The Dictionary problem: B^(+)-δένδρα |
Κεφ. 9 Κεφ. 18 CuckooHashing demo (και ανάλυση) BloomFilter demo Bloom Filter πιθανότητα σφάλματος |
| 6 | 08-11/04/2024 | α) Άπληστοι αλγόριθμοι α1) Knapsack problem (Fractional) α2) Huffman encoding α3) Interval Scheduling [proof: the greedy stays ahead] α4) Optimal cache replacement with perfect knowledge of the future [proof: the exchange argument] a5) Dominating Sets |
Κεφ. 16 Greedy algorithms: Interval scheduling, Interval partitioning, Shortest-paths Belady's optimal offline caching (και απόδειξη) |
| 7 | 15-18/04/2024 | α) Δυναμικός Προγραμματισμός α1) Weighted Interval Scheduling α2) Longest Common Subsequence α3) 0/1 Knapsack α4) Edit Distance β) Γραμμικός Προγραμματισμός β1) Weighted Vertex Cover γ) Ταύτιση συμβολοσειρών γ1) Αλγόριθμοι: Απλοϊκός, Morris-Pratt, Knuth-Morris-Pratt |
Κεφ. 15 Κεφ. 29 (έως 29.2) Κεφ. 32 (32.1, 32.4) Weighted Interval Scheduling Longest Common Subsequence Knapsack & String Alignment 0/1 Knapsack animation Linear Programming Linear Programming in Matlab Traveling Salesman Problem and DP Pattern matching: Naive, Morris-Pratt, Knuth-Morris-Pratt |
| 8 | 22-25/04/2024 | α) Graph-Theoretic αλγόριθμοι α1) Depth/Breadth traversal β) Minimum Spanning Tree β1) Αλγόριθμος Kruskal β2) Αλγόριθμος Prim |
Κεφ. 22 Κεφ. 23 |
| 9 | 13-16/05/2024 | Shortest-paths |
Κεφ. 24 Κεφ. 25 Bellman-Ford SPs, All-Pairs-SPs (Matrix, Floyd-Warshall) |
| 10 | 20-23/05/2024 | α) Maximum-flow β) Maximum-flow/min-cut applications |
Κεφ. 26 Ford-Furkeson demo |
| 11 | 27-30/05/2024 | α) NP and computational intractability β) Polynomial-time reductions: By simple equivalence, By special case to general case, By encoding with gadgets |
Κεφ. 34 about NP |
| 12 | 03-06/06/2024 | α) NP-completeness β) Approximation algorithms |
Κεφ. 34 Κεφ. 35 Approximation algorithms (Load balancing, set cover) Approximation algorithms |
| 13 | ΑΠΟ ΑΝΑΠΛΗΡΩΣΗ | α) Υπολογιστική Γεωμετρία: Εύρεση του Κυρτού περιβλήματος (convex hull) συνόλου σημείων β) Online (competitive) algorithms |
Κεφ. 17.3 Κεφ. 33.3 Convex Hull - Graham scan Competitive algorithms |
