Διαλέξεις

(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση στο βιντεοσκοπημένο μέρος των διαλέξεων. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).

• Διάλεξη 8/10/2020: Εισαγωγή και διαδικαστικά. Εισαγωγικές έννοιες, ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας.
• Διάλεξη 12/10/2020: Ασυμπτωτικός Συμβολισμός (εκτενής επανάληψη), αποδοτικοί αλγόριθμοι, fine-grained complexity (απλή αναφορά, δείτε διαφάνειες, διαφάνειες και survey, για περισσότερες πληροφορίες). 
• Διάλεξη 15/10/2020: Δομές δεδομένων, abstract data types, λεξικό, hash tables (δείτε σημειώσεις και εκτενείς σημειώσεις για περισσότερες πληροφορίες) ουρές προτεραιότητας, σωρός (εκτενής επανάληψη).
• Διάλεξη 19/10/2020: Σωρός (γρήγορη επανάληψη), heapsort, κάτω φράγμα στη χρονική πολυπλοκότητα συγκριτικών αλγόριθμων ταξινόμησης (εκτενής επανάληψη). Union - Find. 
• Διάλεξη 22/10/2020: Λίγο περισσότερες δομές δεδομένων: Range Sum Queries και Binary Indexed Trees, Range Minimum Queries και Lowest Common Ancestor.
  
• Διάλεξη 26/10/2020: Tries (απλή αναφορά). Ταξινόμηση σε γραμμικό χρόνo (links με σχετικό υλικό: 1, 2, 3, 4, 5). Αλγόριθμοι Διαίρει-και-Βασίλευε: mergesort, master theorem.
• Διάλεξη 29/10/2020: Master theorem και εφαρμογές. Πλησιέστερο ζεύγος σημείων. 
• Διάλεξη 2/11/2020: Quicksort, πιθανοτική Quicksort. Το πρόβλημα της επιλογής. 
• Διάλεξη 5/11/2020: Ντετερμινιστική επιλογή σε γραμμικό χρόνο. Αναζήτηση: Γραμμική αναζήτηση, δυαδική αναζήτηση, αναζήτηση με παρεμβολή. Σημειώσεις με την θεωρητική ανάλυση της αναζήτησης με παρεμβολή. 
• Διάλεξη 9/11/2020: Εφαρμογές δυαδικής αναζήτησης σε προβλήματα βελτιστοποίησης. Άπληστοι Αλγόριθμοι. 
• Διάλεξη 12/11/2020: Άπληστοι Αλγόριθμοι.
• Διάλεξη 19/11/2020: Δυναμικός προγραμματισμός.
• Διάλεξη 23/11/2020: Δυναμικός προγραμματισμός (σύντομος και πρόχειρος κώδικας που λύνει το παράδειγμα του matrix-chain multiplication που είδαμε στις διαφάνειες του μαθήματος). 
• Διάλεξη 26/11/2020: Παραδείγματα και ασκήσεις σε δυναμικό προγραμματισμό.
• Διάλεξη 30/11/2020: Παραδείγματα και ασκήσεις σε δυναμικό προγραμματισμό, συζήτηση και υποδείξεις για ασκήσεις 2ης σειράς. 
• Διάλεξη 3/12/2020: Αναζήτηση κατά Πλάτος και Αναζήτηση κατά Βάθος, υπολογισμός γεφυρών και σημείων κοπής.
• Διάλεξη 7/12/2020: Αναζήτηση κατά Βάθος, τοπολογική ταξινόμηση, υπολογισμός ισχυρά συνεκτικών συνιστωσών. Ελάχιστο Συνδετικό Δέντρο: άπληστος αλγόριθμος, ορθότητα.
• Διάλεξη 10/12/2020: Ελάχιστο Συνδετικό Δέντρο: αλγόριθμοι Kruskal, Prim και Boruvka, ασκήσεις (μοναδικότητα, bottleneck spanning tree, second best spanning tree). Συντομότερα μονοπάτια από μία αρχική κορυφή: βασικές έννοιες.
• Διάλεξη 14/12/2020: Συντομότερα μονοπάτια από μία αρχική κορυφή: αλγόριθμος Bellman-Ford. Συντομότερα μονοπάτια σε DAG, αλγόριθμος Dijkstra. Ασκήσεις.
• Διάλεξη 17/12/2020: Συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών: αλγόριθμος Floyd-Warshall, αλγόριθμος Johnson. Μέγιστη ροή - ελάχιστη τομή.
• Διάλεξη 21/12/2020: Μέγιστη ροή - ελάχιστη τομή: Αλγόριθμος Ford-Fulkerson, βελτιώσεις Edmonds-Karp. Μηχανές Turing και Υπολογισιμότητα.
• Διάλεξη 22/12/2020: Υπολογιστική Πολυπλοκότητα. Αναγωγές.
• Διάλεξη 7/1/2021: Αναγωγές. Μη Ντετερμινισμός.
• Διάλεξη 11/1/2021: Η κλάση NP. NP-Πληρότητα και NP-πλήρη προβλήματα.
• Διάλεξη 14/1/2021: NP-Πλήρη Προβλήματα. Παραδείγματα Αναγωγών.
• Διάλεξη 18/1/2021: Περισσότερα παραδείγματα αναγωγών. Χωρική Πολυπλοκότητα.