Υλικό

Διαφάνειες Μαθήματος

• Διάλεξη 2/10/2017: Διαδικαστικά-Οργανωτικά. Εισαγωγή - Βασικές Έννοιες.
• Διάλεξη 5/10/2017: Ασυμπτωτικός Συμβολισμός.
• Διάλεξη 9/10/2017: Δομές Δεδομένων. Ουρές Προτεραιότητας: Σωρός. Heapsort. Κάτω φράγμα ταξινόμησης με συγκρίσεις.
• Διάλεξη 12/10/2017: Ταξινόμηση σε γραμμικό χρόνο: counting sort, radix sort (διαφάνειες από το μάθημα του ΜΙΤ - δείτε επιπλέον: 1, 2, 3). Διαχείριση συνόλων: Union - Find.
• Διάλεξη 16/10/2017: Μέθοδος Διαίρει-και-Βασίλευε: mergesort, δένδρα αναδρομής (διαφ. 1-14).
• Διάλεξη 19/10/2017: Μέθοδος Διαίρει-και-Βασίλευε: Master Theorem, απόδειξη και εφαρμογές, πολλαπλασιασμός αριθμών και πινάκων (διαφ. 15-24).
  
• Διάλεξη 23/10/2017: Μέθοδος Διαίρει-και-Βασίλευε: πράξεις μεγάλων αριθμών, αριθμητική υπολοίπων, ανταλλαγή κλειδιού Diffie-Hellman. Αριθμοί Fibonacci (διαφ. 25-31).
  
• Διάλεξη 30/10/2017: Ταξινόμηση Quicksort: ανάλυση χειρότερης και μέσης περίπτωσης. Πιθανοτική Quicksort. Χωρική πολυπλοκότητα. Animated slides.
• Διάλεξη 2/11/2017: Το πρόβλημα της επιλογής: πιθανοτικός και ντετερμινιστικός αλγόριθμος.
• Διάλεξη 6/11/2017: Άπληστοι αλγόριθμοι: επιλογή δραστηριοτήτων, χρωματισμός διαστημάτων, κλασματικό σακίδιο. Βελτιστότητα υπο-λύσεων και άπληστης επιλογής.
• Διάλεξη 9/11/2017: Κωδικοποίηση Huffman: άπληστος αλγόριθμος, prefix-free κώδικες. Συζήτηση λύσεων 1ης σειράς γραπτών και 1ης σειράς προγραμματιστικών ασκήσεων. 
• Διάλεξη 13/11/2017: Δυναμικός προγραμματισμός: διωνυμικοί συντελεστές, διακριτό πρόβλημα σακιδίου (0-1 Knapsack). Ψευδοπολυωνυμικοί αλγόριθμοι.  (Διαφ. 1-13).
• Διάλεξη 20/11/2017: Δυναμικός προγραμματισμός. Βελτιωμένες μέθοδοι ΔΠ για 0-1 Knapsack: αναδρομή με απομνημόνευση, μέθοδος Nemhauser-Ullmann. Προβλήματα αθροίσματος υποσυνόλου και διαμέρισης. (Διαφ. 14-23)
• Διάλεξη 23/11/2017: Παραδείγματα δυναμικού προγραμματισμού: ελάχιστες διαδρομές σε DAG, μέγιστη αύξουσα υπακολουθία, διορθωτική απόσταση. (Διαφ. 1-86)
• Διάλεξη 30/11/2017: Αλγόριθμοι δυναμικού προγραμματισμού: αλυσιδωτός πολλαπλασιασμός πινάκων, πρόβλημα σακιδίου με επανάληψη, πρόβλημα πλανόδιου πωλητή. Διαφ: Παραδείγματα δυναμικού προγραμματισμού (87-112 & 146-170) και Δυναμικός προγραμματισμός (24-41).
• Διάλεξη 4/12/2017: Αλγόριθμοι γράφων. Αναζήτηση κατά Πλάτος (BFS). Αναζήτηση κατά Βάθος (DFS), τοπολογική διάταξη (Διαφ. 1-14).
• Διάλεξη 7/12/2017: Αλγόριθμοι γράφων. Ισχυρά συνεκτικές συνιστώσες μέσω DFS (Δαφ. 15-19). Συντομότερες διαδρομές: σ.δ. από μία αφετηρία, αλγόριθμος Bellmann-Ford, σ.δ. σε DAG (Διαφ. 1-16).
• Διάλεξη 11/12/2017: Συντομότερες διαδρομές. Αλγόριθμος Dijkstra. All-pairs shortest paths: αλγόριθμος Floyd-Warshall (Διαφ. 17-35). Ελάχιστα συνδετικά δένδρα: αλγόριθμοι Prim, Kruskal, Boruvka.
• Διάλεξη 18/12/2017: Το πρόβλημα Μέγιστης Ροής - Ελάχιστης Τομής. Αλγόριθμος Ford-Fulkerson, βελτιώσεις Edmonds-Karp. Αναγωγή του προβλήματος Μέγιστου Ταιριάσματος στο πρόβλημα Μέγιστης Ροής.
• Διάλεξη 19/12/2017: (Έκτακτο μάθημα) Συζήτηση λύσεων 2ης σειράς γραπτών και 2ης σειράς προγραμματιστικών ασκήσεων. 
• Διάλεξη 21/12/2017: Μηχανές Turing και Υπολογισιμότητα. Έλεγχος παλίνδρομων: άνω φράγματα σε ΤΜ με 1 και 2 ταινίες. Πολυπλοκότητα επικοινωνίας (communication complexity): ιδιότητα τετραγώνου, κάτω φράγματα για έλεγχο ισότητας και παλίνδρομων. (Σημειώσεις Ν. Λεονάρδου.)
• Διάλεξη 8/1/2018: Πολυπλοκότητα, αναγωγές, πληρότητα (διαφ. 1-10). Συζήτηση κάτω φράγματος πολλαπλασιασμού και αναφορά άνω φραγμάτων. Αναγωγή ύπαρξης τριγώνου σε γράφο στον τετραγωνισμό πίνακα. Αναγωγή πολλαπλασιασμού πινάκων στον τετραγωνισμό πίνακα. Αναγωγή ταξινόμησης στην κατασκευή Huffman code. (Σημειώσεις Ν. Λεονάρδου.)
• Διάλεξη 11/1/2018: Προβλήματα ικανοποιησιμότητας λογικών προτάσεων: SAT, kCNF, 3CNF, DNF in P, 2CNF in P (Πολυπλοκότητα, αναγωγές, πληρότητα διαφ. 11-12). Αλγόριθμοι για το πρόβλημα Vertex cover: ακριβής, παραμετρικός, προσεγγιστικός (σημειώσεις Ν. Λεονάρδου).
• Διάλεξη 18/1/2018: Μη-ντεντερμινισμός, NP-πληρότητα. (Δείτε και διαφ. Στ. Νικολόπουλου.)
  
  
  

Σημειώσεις - Συμπληρωματικό Υλικό

• Προγραμματιστικές Ασκήσεις: Μια απλή συνάρτηση σε C για να διαβάζετε γρήγορα την είσοδο όταν αυτή αποτελείται από μη αρνητικούς ακέραιους και τα testcases είναι πολύ μεγάλα.
• Σύντομη Εισαγωγή στη Θεωρία Γραφημάτων (σημειώσεις του Δ. Φωτάκη). Για τις βασικές έννοιες της Θεωρίας Γραφημάτων δείτε ακόμη τις ακόλουθες διαφάνειες: Εισαγωγή στη Θεωρία Γραφημάτων, και Βασικές Έννοιες της Θεωρίας Γραφημάτων: 1η, 2η, και 3η σειρά.
• Συμπληρωματικές σημειώσεις του Δ. Φωτάκη. Καλύπτουν μόνο ένα μέρος της ύλης του μαθήματος.
• Εξαιρετικές σημειώσεις του Jeff Erickson σε δυναμικό προγραμματισμό (με πολλά παραδείγματα και πολλές ασκήσεις).
• Ένα ενδιαφέρον άρθρο από τον Bernard Chazelle: The Algorithm: Idiom of Modern Science.
• Ένα ενδιαφέρον άρθρο από τον Jeff Ullman σχετικά με την θεωρητική και την πειραματική αξιολόγηση των αλγορίθμων: Experiments as Research Validation – Have We Gone too Far?
• Ένα review από τους Andrew Goldberg και Robert Tarjan των γνωστών αποδοτικών αλγόριθμων για το πρόβλημα της Μέγιστης Ροής. Το review είναι εξαιρετικά ενδιαφέρον, το ίδιο και το video για τη σημασία και τις εφαρμογές του προβλήματος.

Προτεινόμενες Ασκήσεις (με τις λύσεις τους) και Παραδείγματα

• 1η σειρά: Ασυμπτωτικός συμβολισμός, αναδρομικές σχέσεις, ταξινόμηση.
• 2η σειρά: Άπληστοι αλγόριθμοι, δυναμικός προγραμματισμός.
• 3η σειρά: Αλγόριθμοι γραφημάτων, Ελάχιστο Συνδετικό Δέντρο.
• 4η σειρά: Συντομότερα Μονοπάτια, Μέγιστη Ροή, Αναγωγές.
• 5η σειρά: Παραδείγματα αναγωγών (διαφάνειες).

Βιβλιογραφία

1. Thomas Cormen, Charles Leiserson, Ronald Rivest and Cliff Stein: "Introduction to Algorithms", 3rd edition, MIT Press, 2009.
2. J. Kleinberg, E. Tardos: "Algorithm Design", Addison-Wesley, 2005.
3. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani: "Algorithms", MacGraw-Hill, 2006 (Μπορείτε να βρείτε draft έκδοση του βιβλίου αυτού εδώ).
4. J. Edmonds. How to Think About Algorithms. Cambridge University Press, 2008.
5. G. Brassard, P. Bratley: "Algorithmics: Theory and Practice", Prentice-Hall.
6. Sara Baase, Allen Van Gelder, "Computer Algorithms: Introduction to Design and Analysis", 3rd edition, Addison Wesley Longman, 2000.
7. Alfred V. Aho, John E. Hopcroft, "The Design and Analysis of Computer Algorithms", Addison-Wesley Series in Computer Science and Information Processing, 1974.
8. Dexter C. Kozen, "The Design and Analysis of Algorithms", Springer, 1991.
9. A. Levitin: "Ανάλυση και Σχεδίαση Αλγορίθμων", Εκδόσεις Τζιόλα, 2007.
10. G. J. E. Rawlings: "Αλγόριθμοι: Ανάλυση και Σύγκριση", Εκδόσεις Κριτική, 2004.