Βιβλίο | ![]() |
![]() |
Τίτλος | Εισαγωγή στους Αλγορίθμους | 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 |
Γλώσσα | Ελληνική | Αγγλική Εδώ |
Βιβλίο | ![]() |
![]() |
![]() |
![]() |
![]() |
Τίτλος | Algorithm Design Σχεδιασμός Αλγορίθμων |
Approximation Algorithms (Downloadable behing UTh' IP) |
Probability and Computing Randomization and Probabilistic Techniques in Algorithms and Data Analysis |
Algorithms | The Algorithm Design Manual (Downloadable behing UTh' IP) |
Εβδομάδα | Ημερομηνία | Αντικείμενο διάλεξης | Μελέτη ελλ. βιβλίο |
1 | 28/02-03/03/2022 | α) Εισαγωγή στην έννοια του αλγορίθμου β) Insertion sort και Merge sort γ) Ρυθμός αύξησης συναρτήσεων |
Κεφ. 1 Κεφ. 2 Κεφ. 3 |
2 | 07-10/03/2022 | α) Ασκήσεις (asymp. notation, Bubble sort, inversions counting) β) Αλγόριθμοι Διαίρει-και-Βασίλευε (Binary search, Recurrences) γ) Master theorem |
Κεφ. 4 Binary Search demo |
3 | 14-17/03/2022 | α) Διαίρει-και-Βασίλευε: Strassen πολλαπλασιαμός πινάκων β) Κάτω όριο των comparison-based αλγορίθμων ταξινόμησης γ) (Deterministic) Quicksort |
Κεφ. 4 Κεφ. 7 Κεφ. 8.1 QuickSort demo |
4 | 21-24/03/2022 | α) Randomized Quicksort. Πιθανοκρατική ανάλυσης μέσης επίδοσης του Randomized Quicksort β) Bucket sort. Πιθανοκρατική ανάλυση γ) Περίληψη βασικών δομών δεδομένων: Συνδεδεμένες Λίστες, (Κυκλικές) Ουρές, Δένδρα, Σωρός (Ταξινόμηση με σωρό) |
Κεφ. 5 Κεφ. 6 Κεφ. 7 Κεφ. 8.4 Κεφ. 10 HeapSort demo |
5 | 28-31/03/2022 | α) Order statistics (i-th smallest, median) β1) The Dictionary problem: Hashing β2) The Dictionary problem: Cuckoo hashing β3) The Dictionary problem: Bloom filter β4) The Dictionary problem: B^(+)-δένδρα |
Κεφ. 9 Κεφ. 11 Κεφ. 16 CuckooHashing demo (και ανάλυση) BloomFilter demo Bloom Filter πιθανότητα σφάλματος |
6 | 04-07/04/2022 | α) Άπληστοι αλγόριθμοι α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) Vertex cover |
Κεφ. 16 Belady's optimal offline caching (και απόδειξη) |
7 | 11-14/04/2022 | α) Δυναμικός Προγραμματισμός α1) Weighted Interval Scheduling α2) Longest Common Subsequence α3) 0/1 Knapsack α4) Edit Distance β) Γραμμικός Προγραμματισμός β1) Weighted Vertex Cover |
Κεφ. 15 Κεφ. 29 (έως 29.2) Weighted Interval Scheduling Longest Common Subsequence Knapsack & String Alignment Linear Programming Traveling Salesman Problem and DP |
8 | 02-05/05/2022 | α) Graph-Theoretic αλγόριθμοι α1) Depth/Breadth traversal β) Minimum Spanning Tree β1) Αλγόριθμος Kruskal β2) Αλγόριθμος Prim |
Κεφ. 22 Κεφ. 23 |
9 | 09-12/05/2022 | Shortest-paths |
Κεφ. 24 Bellman-Ford SPs, All-Pairs-SPs (Matrix, Floyd-Warshall) |
10 | 16-19/05/2022 | α) Maximum-flow β) Maximum-flow/min-cut applications |
Κεφ. 26 Ford-Furkeson demo |
11 | 23-26/05/2022 | α) NP and computational intractability β) Polynomial-time reductions: By simple equivalence, By special case to general case, By encoding with gadgets |
Κεφ. 34 about NP |
12 | 30/05-02/06/2022 | α) NP-completeness β) Approximation algorithms |
Κεφ. 34 Κεφ. 35 |
13 | 04/06/2022 | Online (competitive) algorithms | Κεφ. 17.3 Competitive algorithms |