Topic outline

• Χειμερινό Εξάμηνο 2020-2021
  

  Χειμερινό Εξάμηνο 2020-2021

  Διδάσκοντες
  

  • Δημήτρης Φωτάκης, Αναπλ. Καθηγητής ( fotakis@cs.ntua.gr )
  • Δώρα Σούλιου, Ε.ΔΙ.Π ( dsouliou@mail.ntua.gr )
  • Θανάσης Λιανέας, Μεταδιδάκτορας ( lianeas@corelab.ntua.gr )

  
  

  Επικοινωνία και Πληροφορίες

  • Μπορείτε να απευθύνετε τις ερωτήσεις σας στη διεύθυνση:  algo@corelab.ntua.gr

  
  

  Βοηθοί Διδασκαλίας

  • Λουκάς Κάβουρας, Υ.Δ. ( lkavouras@corelab.ntua.gr )
    
  • Αλβέρτος Καλαβάσης, Υ.Δ. ( kalavasis@corelab.ntua.gr )
    
  • Αγγελική Μαθιουδάκη, Υ.Δ. ( tmathiou@corelab.ntua.gr )
  • Παναγιώτης Πατσιλινάκος, Υ.Δ. ( patsilinak@corelab.ntua.gr )
    
  • Αγάπη Ρισσάκη, Υ.Δ. ( arissaki@corelab.ntua.gr )
  • Ελένη Ψαρουδάκη, Υ.Δ.( epsaroudaki@corelab.ntua.gr )

  
  

  Βοηθοί Γραπτών Ασκήσεων

  • Ιωάννης Αναγνωστίδης
  • Ιωάννης Μαυροθαλασσίτης
    
  • Παναγιώτης Ράπτης
  • Κωνσταντίνος Σταυρόπουλος
  • Δημήτριος Χρήστου
    

  
  

  Βοηθοί Προγραμματιστικών Ασκήσεων

  • Παναγιώτης Κωστοπαναγιώτης
  • Χαρίλαος Πίπης 
  • Μιλτιάδης Στούρας
  • Δημήτριος Χρήστου
    

  
  

  Πρόγραμμα Διαλέξεων
  

  To μάθημα θα ξεκινήσει να γίνεται μέσω Webex, σύμφωνα με το πρόγραμμα της ΣΗΜΜΥ (αν κριθεί απαραίτητο, μπορεί σε συνεννόηση με τους εγγεγραμμένους στο μάθημα, να μετακινηθούμε στο MS Teams). 
  
  

  • κάθε Δευτέρα 15:00-17:00 (Webex link:  https://centralntua.webex.com/centralntua/j.php?MTID=m9ee2021e2f48378afcd1646a1b45bdff ).
  • κάθε Πέμπτη 17:00-19:00 (Webex link:  https://centralntua.webex.com/centralntua/j.php?MTID=m2ca2f3dfcc6ac539d56967a49b527a8c ).

  
  

  Οι διαλέξεις θα ξεκινήσουν την Πέμπτη, 8 Οκτωβρίου, 2020. 
  

  Κάθε Πέμπτη γίνονται πρόσθετες διαλέξεις για τους μεταπτυχιακούς φοιτητές. Σχετικά με το περιεχόμενο και το πρόγραμμα των διαλέξεων, δείτε τη σελίδα του μεταπτυχιακού μαθήματος. 
  

  Την Πέμπτη, 8 Οκτωβρίου, 2020, στις 19:15, μετά την ολοκλήρωση της διάλεξης για το προπτυχιακό, θα γίνει η πρώτη συνάντηση των διδασκόντων με τους μεταπτυχιακούς φοιτητές, για να οριστικοποιηθεί η ακριβής ώρα των πρόσθετων διαλέξεων και αν θα γίνονται online ή δια ζώσης. 

  
  

  Ώρες Γραφείου

  • κάθε Πέμπτη 16:00-17:00 (Webex link: https://centralntua.webex.com/centralntua/j.php?MTID=m0345e80abbc703bf78cfafaa98d97a00 )

  
  

  • Ανακοινώσεις Forum
  • Υποβολή Απαντήσεων Γραπτής Εξέτασης Σεμπτεμβρίου Assignment
• Υλικό
  

  Υλικό

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

  • Προγραμματιστικές Ασκήσεις: Μια απλή συνάρτηση σε C για να διαβάζετε γρήγορα την είσοδο όταν αυτή αποτελείται από μη αρνητικούς ακέραιους και τα testcases είναι πολύ μεγάλα.
  • Σύντομη Εισαγωγή στη Θεωρία Γραφημάτων (σημειώσεις του Δ. Φωτάκη).
  • Συμπληρωματικές σημειώσεις του Δ. Φωτάκη. Καλύπτουν μόνο ένα μέρος της ύλης του μαθήματος.
  • Ένα ενδιαφέρον άρθρο από τον 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 για τη σημασία και τις εφαρμογές του προβλήματος.
  • Ένα ενδιαφέρον άρθρο για τον Donald Knuth: The Yoda of Silicon Valley 
    

  
  

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

  • 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. J. Erickson. Algorithms, 1st edition, 2019. 
     
  6. G. Brassard, P. Bratley: Algorithmics: Theory and Practice, Prentice-Hall, 1988. 
  7. Sara Baase, Allen Van Gelder, Computer Algorithms: Introduction to Design and Analysis, 3rd edition, Addison Wesley Longman, 2000.
  8. Alfred V. Aho, John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Series in Computer Science and Information Processing, 1974.
  9. Dexter C. Kozen, The Design and Analysis of Algorithms, Springer, 1991.
  10. A. Levitin: Ανάλυση και Σχεδίαση Αλγορίθμων, Εκδόσεις Τζιόλα, 2007.
  11. G. J. E. Rawlings: Αλγόριθμοι: Ανάλυση και Σύγκριση, Εκδόσεις Κριτική, 2004.

  
  

  
  
• Διαλέξεις
  

  Διαλέξεις

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

  
  
• Ασκήσεις
  

  Ασκήσεις

  Γραπτές Ασκήσεις

  • 1η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 9/11/2020.  
  • 2η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 8/12/2020. 
  • 3η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 13/1/2021.  
    
  • 4η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 12/2/2021.  

  
  

  Προγραμματιστικές Ασκήσεις

  • 1η σειρά προγραμματιστικών ασκήσεων (αρχεία εισόδου). Προθεσμία υποβολής: 22/11/2020. 
    
  • 2η σειρά προγραμματιστικών ασκήσεων (αρχεία εισόδου). Προθεσμία υποβολής: 27/12/2020.  
    
  • 3η σειρά προγραμματιστικών ασκήσεων (αρχεία εισόδου). Προθεσμία υποβολής: 19/4/2021.  
  • 4η σειρά προγραμματιστικών ασκήσεων (αρχεία εισόδου). Προθεσμία υποβολής: 19/4/2021.

  
  

  Παρατηρήσεις για τις ασκήσεις
  

  
  

  • Οι προγραμματιστικές ασκήσεις υποβάλλονται (source code) στον grader, και αξιολογούνται ηλεκτρονικά. Η προθεσμία υποβολής λήγει τα μεσάνυχτα της ημέρας παράδοσης. Για την υποβολή, θα χρησιμοποιήσετε τα login name και password που έχετε για το moodle του μαθήματος. Τα προγράμματά σας πρέπει να είναι σε C/C++, να διαβάζουν την είσοδο από το standard input, και να τυπώνουν την έξοδο στο standard output. Μια υποβολή θεωρείται επιτυχής (και συνεχίζει στο στάδιο της αξιολόγησης) αν "περάσει" επιτυχώς τα επιλεγμένα test cases για το αντίστοιχο ερώτημα. Η αξιολόγηση γίνεται με αντίστοιχα (κοινά για όλους, αλλά διαφορετικά από αυτά που ελέγχονται κατά την υποβολή) test cases, μετά την λήξη της προθεσμίας. Με κάθε άσκηση, θα δίνεται και ένας αριθμός test cases (με τις απαντήσεις τους), που μπορείτε να χρησιμοποιήσετε για προκαταρκτικό έλεγχο των λύσεων σας.
  • Στις γραπτές ασκήσεις να γράφετε ονοματεπώνυμο και αριθμό μητρώου. Η υποβολή γίνεται αποκλειστικά στο moodle. Η προθεσμία λήγει στις 05:59 της επομένης της ημέρας παράδοσης. Εάν δοθεί παράταση θα ανακοινωθεί εδώ.
  • Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
  • Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά, π.χ. αφού αφιερώσετε ικανό χρόνο ατομικής προσπάθειας), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τη λύση. Πανομοιότυπες διατυπώσεις θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές ασκήσεων.
  • Για απορίες πάνω στις ασκήσεις και στη θεωρία μπορείτε να υποβάλετε ερωτήσεις στις ώρες γραφείου.