Η/Υ 432: Δομές Δεδομένων - Υποχρεωτικό μάθημα 3^ου εξαμήνου

Χειμερινό Εξάμηνο Ακ. Έτους 2006-2007

Τμήμα Πληροφορικής

Γενικά | Ανακοινώσεις | Ημερολόγιο | Διαφάνειες Διαλέξεων & Άλλο Υλικό

Τελική Βαθμολογία (grades_ds_total_Sep2007.xls) εξεταστικής Σεπτεμβρίου. Ώρες Γραφείου για να δείτε γραπτά και quiz: Πέμπτη, 18/10, ώρα 11:00-13:00 (στο γραφείο μου)

Τελική Βαθμολογία (grades_ds_total_am.xls) εξεταστικής Ιανουαρίου. Ώρες Γραφείου για να δείτε γραπτά και quiz: Παρασκευή, 21/9, ώρα 11:00-13:00 (στο γραφείο μου)

ΕΠΕΙΓΟΝ!!!! Το 2o και το 3ο quiz που αντιστοιχεί στις σειρές ασκήσεων 3&4 και 5&6 θα γίνει το Σάββατο, 21/4/2007, ώρα 10:00-15:00, στο αμφιθέατρο και στην αίθουσα Ι5. Η εξέταση θα γίνει με κλειστές σημειώσεις για τις σειρές 3 και 4, και με ανοικτές σημειώσεις για τις σειρές 5&6.

Η προθεσμία παράδοσης της προγραμματιστικής άσκησης είναι στις 16 Απριλίου (την ίδια ώρα και με τον ίδιο τρόπο όπως αναγράφεται στην άσκηση). Το ίδιο ισψύει και φια την 5η σειρά (ασκήσεις 1, 2 και 3 της μικτής σειράς 5&6 που σας έχει δοθεί). Η 4η άσκηση της σειράς θα παραδοθεί την Πέμπτη 19/4/2007 στις ώρες γραφείων των βοηθών.

Οι σειρές ασκήσεων 1,2,3 και 4 έχουν διορθωθεί και θα μοιράζονται την Πέμπτη, 19/4/2007 στο γραφείο των βοηθών του μαθήματος (ώρες γραφείου των βοηθών).

H 3η σειρά ασκήσεων έχει προθεσμία την Τρίτη 12/12 και όχι 12/1 όπως αναγραφόταν αρχικά.
Το 1o quiz που αντιστοιχεί στις 2 πρώτες σειρές ασκήσεων θα γίνει το Σάββατο, 2/12, ώρα 10:00-13:00, στο αμφιθέατρο και στην αίθουσα Ι5 (προσέξτε ότι η ώρα έχει αλλάξει από 12:00-15:00 σε 10:00-13:00!!!!!!). Η εξέταση θα γίνει με κλειστές σημειώσεις.
Το εργαστήριο της 2ης ομάδας που χάθηκε την Τρίτη, 31/10 λόγω Γενικής Συνέλευσης θα γίνει τελικά την Παρασκευή, 10/11, ώρα 1-3.

Διδάσκουσα:                                           Παναγιώτα Φατούρου
Γραφείο:                                                  26 (Α´ ορόφου)
Ώρες Γραφείου:                                      Δευτέρα: 12:00-14:00, Τετάρτη: 12:00 – 14:00
Ηλεκτρονική Διεύθυνση:
Τηλέφωνο:                                              (26510) 98808

Βοηθοί Μαθήματος:                                 Καλλιμάνης Νικόλαος & Κοσμάς Ελευθέριος, Πεχλιβάνη Φωτεινή & Χριστοδουλίδου Μαρία
Γραφείο Βοηθών:                                      Α25
Ώρες Γραφείου Βοηθών:                          Πέμπτη, 13:00-15:00
Ηλεκτρονική Διεύθυνση Μαθήματος:

Ώρες και Αίθουσες Διδασκαλίας

Δευτέρα, 15:00-17:00, στο αμφιθέατρο.
Τετάρτη, 15:00-17:00, στο αμφιθέατρο.

Ώρες και Αίθουσα Φροντιστηρίου-Εργαστηρίου

Αλλαγή Ώρας: Τρίτη, 16:00-18:00.

Σύνοψη Μαθήματος

Το μάθημα θα εστιάσει στη μελέτη βασικών δομών δεδομένων, όπως π.χ. πινάκων, λιστών, στοιβών, ουρών, δένδρων κλπ., καθώς και πιο πολύπλοκων δομών δεδομένων, όπως ισοζυγισμένων δένδρων, κ.α. Επίσης, θα μελετηθεί η τεχνική του κατακερματισμού, καθώς και δομές δεδομένων για την υλοποίηση απλών συνόλων και συνόλων με ειδικές λειτουργίες, και δυναμικών λεξικών.

Βιβλία

q Harry Lewis and Larry Denenberg, “Data Structures and Their Algorithms”, HarperCollins Publishers, Inc., New York, 1991.

q Ιωάννης Μανωλόπουλος, Δομές Δεδομένων: Μια προσέγγιση με Pascal, Εκδόσεις Art of Text, Θεσσαλονίκη.

Το βιβλίο που θα σας μοιραστεί είναι το 2^ο από τα παραπάνω. Το μάθημα θα βασιστεί σε μεγάλο βαθμό και στο 1^ο βιβλίο. Οι διαφάνειες του μαθήματος μαζί με τις σημειώσεις που μπορείτε να κρατάτε κατά την παράδοση και οποιοδήποτε άλλο υλικό σας μοιραστεί θα είναι αρκετά για να διεκπεραιώσετε επιτυχώς το μάθημα.

Πρόγραμμα

1^η εβδομάδα	Εισαγωγή, Ανάλυση Αλγορίθμων, Δείκτες & Δυναμική Αποθήκευση στη C, Πίνακες
2^η εβδομάδα	Λίστες
3^η εβδομάδα	Λίστες
4^η εβδομάδα	Δένδρα
5^η εβδομάδα	Λίστες & Δένδρα: Υλοποίηση Συνόλων
6^η εβδομάδα	Λίστες & Δένδρα: Υλοποίηση Συνόλων
7^η εβδομάδα	Ισοζυγισμένα Δένδρα: Υλοποίηση Δυναμικών Λεξικών
8^η εβδομάδα	Ισοζυγισμένα Δένδρα: Υλοποίηση Δυναμικών Λεξικών
9^η εβδομάδα	Ισοζυγισμένα Δένδρα: Υλοποίηση Δυναμικών Λεξικών
10^η εβδομάδα	Κατακερματισμός
11^η εβδομάδα	Κατακερματισμός
12^η εβδομάδα	Σύνολα που υποστηρίζουν ειδικές λειτουργίες

Εργασίες και Βαθμολόγηση

Κατά τη διάρκεια του εξαμήνου θα δοθεί ένας αριθμός εργασιών. Οι εργασίες θα αποτελούνται από θεωρητικές και προγραμματιστικές ασκήσεις. Ο προγραμματισμός θα γίνει σε γλώσσα C. Κάθε εργασία θα πρέπει να επιστρέφεται πριν από την αναγραφόμενη ημερομηνία και ώρα προκειμένου να μπορεί να βαθμολογηθεί με άριστα. Για τη βαθμολόγηση εργασιών που παραδίδονται καθυστερημένα ισχύει ο εξής αλγόριθμος:

§ Αν η παράδοση της εργασίας γίνει μέχρι και τρία 24ωρα μετά την προθεσμία, η εργασία βαθμολογείται με μείωση βαθμού κατά 1.0/10.0 μονάδα για κάθε μέρα καθυστέρησης.

§ Αν η παράδοση της εργασίας γίνει αφού έχουν περάσει τρία 24ωρα μετά τη λήξη της προθεσμίας, η εργασία βαθμολογείται με άριστα το 5.0/10.0.

Όλες οι εργασίες θα πρέπει να έχουν παραδοθεί πριν από την εξέταση ή την επίλυσή τους. Για τις εργασίες ενδεχόμενα να υπάρχει γραπτή εξέταση. Πολύ καλές εργασίες μπορεί να βαθμολογηθούν με βαθμό μεγαλύτερο του 10.

Το μάθημα θα έχει εργαστήριο. Το εργαστήριο θα γίνεται κάθε Τρίτη 16:00-18:00. Το εργαστήριο δεν είναι υποχρεωτικό αλλά συνεισφέρει μισή μονάδα στο βαθμό σας.

Ο προγραμματισμός, όπως και η έκθεση, είναι μια ατομική εργασία. Καθένας πρέπει ατομικά να κατανοήσει το πρόβλημα και να σκιαγραφήσει μια πιθανή λύση του. Οι λύσεις των ασκήσεων, καθώς και τα προγράμματα που θα σας ζητηθούν πρέπει να είναι αποτέλεσμα προσωπικής σας δουλειάς (μπορείτε όμως να ρωτάτε τους βοηθούς του μαθήματος και τη διδάσκουσα για τις απορίες σας).

Μπορείτε να χρησιμοποιήσετε οποιονδήποτε υπολογιστή για τις προγραμματιστικές ασκήσεις σας. Για τη βαθμολόγηση της άσκησής σας όμως, το πρόγραμμα θα εκτελείται στα μηχανήματα κάποιου εργαστηρίου του Τμήματος. Επομένως, όσοι από εσάς επιθυμούν να εργαστούν σε άλλα μηχανήματα θα πρέπει να σιγουρευτούν ότι ο κώδικας τους τρέχει σωστά και στα παραπάνω μηχανήματα.

Είστε υπεύθυνοι για την κακή χρήση του λογαριασμού σας. Το password σας θα πρέπει να παραμείνει μυστικό και ο λογαριασμός σας να χρησιμοποιείται μόνο από εσάς. Φροντίστε η προστασία του καταλόγου στον οποίο βρίσκονται οι ασκήσεις σας να μην επιτρέπει ανάγνωση (ή ακόμη χειρότερα εγγραφή) από άλλους (χρησιμοποιήστε την εντολή chmod).

Στην τελική εξέταση επιτρέπεται να έχετε μαζί σας το βιβλίο και τις διαφάνειες του μαθήματος (δεμένες) αλλά όχι άλλες σημειώσεις. Στην τελική εξέταση θα πρέπει όλοι οι εξεταζόμενοι φοιτητές να έχουν μαζί τους το πάσο (ή οποιοδήποτε άλλο αναγνωριστικό).

Ο τελικός βαθμός θα εξαρτηθεί τόσο από τη βαθμολογία των ασκήσεων, όσο και από την επίδοση των φοιτητών στην τελική εξέταση, ως εξής:

Εργαστήριο: μισή μονάδα bonus

Σειρές Ασκήσεων: 25%

Τελική Εξέταση: 75%

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

Παρακολούθηση

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

Παρατήρηση

Θα βοηθήσει πολύ να έχετε διεκπεραιώσει με επιτυχία τα μαθήματα της «Εισαγωγής στον Προγραμματισμό» και της «Εισαγωγής στους Η/Υ», καθώς και το μάθημα «Προγραμματισμός σε C».

Άλλη σχετική βιβλιογραφία

Sahni, Δομές Δεδομένων, Αλγόριθμοι και Εφαρμογές στη C++, Μετάφραση: Γιάννης Θεοδωρίδης & Γιάννης Μανωλόπουλος, Εκδόσεις Τζιόλα, 2004.
Γεώργιος Φ. Γεωργακόπουλος, Δομές Δεδομένων: Έννοιες, Τεχνικές, Αλγόριθμοι, Πανεπιστημιακές Εκδόσεις Κρήτης, Ηράκλειο 2002.
Cormen, Leiserson and Rivest, “Introduction to Algorithms”, MIT Press, 1990. Το 1ο μέρος του βιβλίου κυκλοφορεί μεταφρασμένο από τις Πανεπιστημιακές Εκδόσεις Κρήτης.

Leendert Ammeraal, «Προγραμματισμός και Δομές Δεδομένων στη C», Μ. Γκιούρδας, 1989.

K. Mehlhorn and S. Näher, “LEDA”, Cambridge University Press, 1999.
Niklaus Wirth, «Αλγόριθμοι & Δομές Δεδομένων», Κλειδάριθμος, 1990.
C. J. Van Wyk, “Data Structures and C Programs”, Addison-Wesley Publishing Company, 1988.
Ομάδα Waite, C: Βήμα-Προς-Βήμα, Εκδότης Γκιούρδας, Αθήνα 1991.
B. Kernighan & D. Ritchie, Η Γλώσσα Προγραμματισμού C, Εκδόσεις Κλειδάριθμος, Αθήνα 1990.

Ανακοινώσεις

Η 5η & 6η σειρά ασκήσεων είναι διαθέσιμη (ds-homework5.pdf).
Νέα έκδοση διαφανειών σε κόκκινα-μαύρα δένδρα (red-black-trees-trasparencies.pdf).
Το 2o quiz που αντιστοιχεί στις σειρές ασκήσεων 3 και 4 θα γίνει το Σάββατο, 13/1, ώρα 11:00-14:00, στο αμφιθέατρο και στην αίθουσα Ι5. Η εξέταση θα γίνει με κλειστές σημειώσεις.
H προγραμματιστική άσκηση είναι διαθέσιμη (ds-homework-C.pdf).
H 4η σειρά ασκήσεων είναι διαθέσιμη (ds-homework4.doc).
To μάθημα που χάθηκε στις 23/10 θα αναπληρωθεί την Παρασκευή, 15/12, ώρα 13:00-15:00 στην αίθουσα Ι2.
H 3η σειρά ασκήσεων έχει προθεσμία την Τρίτη 12/12 και όχι 12/1 όπως αναγραφόταν αρχικά.
H 3η σειρά ασκήσεων είναι διαθέσιμη (homework3.pdf).
To μάθημα που χάθηκε στις 15/11 θα αναπληρωθεί την Πέμπτη, 7/12, ώρα 18:00-20:00 στην αίθουσα Ι5.
ΕΠΕΙΓΟΝ!!!! Το 1o quiz που αντιστοιχεί στις 2 πρώτες σειρές ασκήσεων θα γίνει το Σάββατο, 2/12, ώρα 10:00-13:00, στο αμφιθέατρο και στην αίθουσα Ι5 (προσέξτε ότι η ώρα έχει αλλάξει από 12:00-15:00 σε 10:00-13:00!!!!!!). Η έξεταση θα γίνει με κλειστές σημειώσεις.
Το εργαστήριο της 2ης ομάδας που χάθηκε την Τρίτη, 31/10 λόγω Γενικής Συνέλευσης θα γίνει τελικά την Παρασκευή, 10/11, ώρα 1-3.
H 2η Σειρά Ασκήσεων είναι διαθέσιμη (ds-homework2.doc).
H 1η σειρά ασκήσεων είναι διαθέσιμη (ds-homework1.doc).
Οι σημειώσεις του μαθήματος είναι διαθέσιμες (slides.pdf).
Προσοχή! Το εργαστήριο ξεκινά την Τρίτη, 24/10, ώρα 16:00-18:00.

Πρόγραμμα εργαστηρίων:

Τρίτη, 24/10 lab1.doc

Τρίτη, 31/10 lab2.doc

Τρίτη, 7/11 lab3.doc

Τρίτη, 14/11 lab1.doc

Τρίτη, 21/11 lab2.doc

Τρίτη, 28/11 lab3.doc

Τρίτη, 5/12 lab1.doc

Τρίτη, 12/12 lab2.doc

Τρίτη, 19/12 lab3.doc

Για το εργαστήριο του μαθήματος υπάρχουν τρία τμήματα των 56 ατόμων. Τα τμήματα θα κάνουν το εργαστήριο εναλλάξ. Έτσι, κάθε τμήμα θα κάνει ένα εργαστήριο κάθε 3η Τρίτη. Το εργαστήριο ξεκινά την Τρίτη, 24 Οκτωβρίου 2006 με το πρώτο τμήμα (για να δείτε ποιοι φοιτητές συμμετέχουν σε αυτό το τμήμα δείτε το αρχείο lab1.doc).

Οι διαφάνειες των διαλέξεων έχουν φωτοτυπηθεί στο τυπογραφείο του Πανεπιστημίου και μπορείτε να τις παίρνετε από το γραφείο της κ. Σουλίου (2ος όροφος). Η ηλεκτρονική έκδοση όλων των διαφανειών είναι επίσης διαθέσιμη (pdf, ps.gz, pdf.gz).
E-mailing Λίστα Μαθήματος
Για το μάθημα υπάρχει e-mailing λίστα η οποία θα χρησιμοποιείται για την αποστολή e-mail σε όλους τους φοιτητές που έχουν δηλώσει το μάθημα. Οι φοιτητές υποχρεούνται να εγγραφούν στη λίστα.

Οι φοιτητές θα πρέπει να εγγραφούν στη λίστα μέχρι τις 25/10. Για να εγγραφείτε στη λίστα αρκεί να στείλετε ένα ηλεκτρονικό μήνυμα (e-mail) στη διεύθυνση

με κενό θέμα και σώμα:

Η εγγραφή στη λίστα είναι υποχρεωτική. Όποιος φοιτητής δεν εγγραφεί στη λίστα, δεν θα λαμβάνει τα e-mails που αποστέλλονται και δεν θα γνωρίζει σημαντικά θέματα που αφορούν το μάθημα. Το e-mail address της λίστας είναι . Όλα τα e-mails προς αυτή τη διεύθυνση θα λαμβάνονται από όλους τους φοιτητές που έχουν εγγραφεί στη λίστα. Οι φοιτητές υποχρεούνται να εξετάζουν καθημερινά το e-mail τους ώστε να ενημερώνονται έγκαιρα για τα μηνύματα που αποστέλλονται στη λίστα.
Γενικές Πληροφορίες για το μάθημα (syllabus.doc).

Ημερολόγιο

Δευτέρα

Τρίτη

Τετάρτη

Πέμπτη

Παρασκευή

9/10

Γενικές Πληροφορίες για το μάθημα (syllabus).

Εισαγωγή. Μελέτη κεφ. 1, Μανωλόπουλος. Επανάληψη στη C (έμφαση σε records, pointers). Εύκολο βιβλίο για εντελώς αρχάριους σε C: "Ομάδα Waite, C: Βήμα-Προς-Βήμα, Εκδότης Γκιούρδας"

Βοηθητικό Υλικό: Ενότητες I.1, I.2, I.3 και I.4, "Εοσαγωγή στους αλγόριθμους", Cormen, Leiserson, Rivest, Πανεπιστημιακές Εκδόσεις Κρήτης. Επίσης, για όσους διαβάζουν αγγλικά, Chapter 1 & Section 2.1, Lewis, Denenberg, "Data Structures & Their Algorithms".

10/10

11/10

12/10

13/10

16/10

Αργία λόγω εκλογών

17/10

18/10

Αλγόριθμοι, Πολυπλοκότητα, Μαθηματική Επαγωγή, Μελέτη διαφανειών. Μελέτη κεφαλαίου 1, Μανωλόπουλος. Επανάληψη στη C (έμφαση σε records, pointers).

19/10

20/10

23/10

Αργία λόγω εκλογών

24/10

lab1.doc

Υλοποίηση απλής λίστας

Ανάρτηση 1ης σειράς ασκήσεων

25/10

Συμβολισμοί Ο, Ω,Θ. Αναδρομικές σχέσεις.Επίλυση Ασκήσεων. Μελέτη διαφανειών

26/10

27/10

30/10

Επίλυση ασκήσεων. Πίνακες. Μελέτη διαφανειών. Μελέτη Κεφαλαίου 2, Μανωλόπουλος.

Βοηθητικό Υλικό: Ενότητες I.1, I.2, I.3 και I.4, "Εισαγωγή στους αλγόριθμους", Cormen, Leiserson, Rivest, Πανεπιστημιακές Εκδόσεις Κρήτης. Επίσης, για όσους διαβάζουν αγγλικά, Chapter 1 & Section 2.1, Lewis, Denenberg, "Data Structures & Their Algorithms".

31/10

Το εργαστήριο δεν έγινε λόγω της Γενικής Συνέλευσης των Φοιτητών

lab2.doc

1/11

Επίλυση Ασκήσεων. Λίστες - Στοίβα.

Μελέτη διαφανειών. Μελέτη Ενοτήτων 3.1 και 3.2.1, Μανωλόπουλος

Για όσους διαβάζουν αγγλικά, Section 3.1, 3.2 (Stack representation in contiguous memory), Lewis, Denenberg, "Data Structures & Their Algorithms".

2/11

3/11

6/11

Στατικές Στοίβες - Στατικές Ουρές.

Μελέτη διαφανειών. Μελέτη Ενοτήτων 3.2.1, 3.2.2, 3.2.3, Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά, Section 3.2 (Queue representation in Contiguous memory), Lewis, Denenberg, "Data Structures & Their Algorithms".

Προθεσμία για την 1η σειρά

Ανάρτηση 2ης σειράς ασκήσεων

7/11

Υλοποίηση απλής λίστας

lab3.doc

8/11

Στατικές Ουρές - Συνδεδεμένες Στοίβες.

Μελέτη διαφανειών. Μελέτη Ενοτήτων 3.2.3, 3.2.4, 3.3, 3.4.1 Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά, Section 3.2 (Queue representation in Contiguous memory, Stack representation in Linked Memory), Lewis, Denenberg, "Data Structures & Their Algorithms".

9/11

10/11

Προσοχή!!!!

Αναπλήρωση εργαστηρίου 2ης ομάδας που χάθηκε στις 31/10 λόγω Γενικής Συνέλευσης Φοιτητών

lab2.doc

Υλοποίηση απλής λίστας

13/11

Συνδεδεμένες Ουρές. Στοίβες και Αναδρομή. Διασχίσεις Λιστών.

Μελέτη διαφανειών. Μελέτη Ενοτήτων 3.4.2 και 3.3, Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά, Sections 3.2 (Queue representation in linked memory) & 3.3 (επιλεκτικά) & 3.4 (επιλεκτικά), Lewis, Denenberg, "Data Structures & Their Algorithms".

14/11

lab1.doc

Υλοποίηση λίστας - Περνώντας δείκτες ως παραμέτρους σε συναρτήσεις

Άσκηση: Να υλοποιηθεί η ListDelete(int x), η οποία ψάχνει για ένα στοιχείο στη λίστα και αν το βρει το διαγράφει από τη λίστα

15/11

Αναβολή μαθήματος

16/11

Προθεσμία για τη 2η σειρά

17/11

20/11

Διπλά Συνδεδεμένες Λίστες. Εισαγωγή στα Δένδρα.

Μελέτη διαφανειών. Μελέτη Ενοτήτων 3.4.3 και 3.4.4, Μανωλόπουλος

Για όσους διαβάζουν αγγλικά, Sections 3.5 & 4.1 Lewis, Denenberg, "Data Structures & Their Algorithms".

21/11

lab2.doc

Υλοποίηση λίστας - Περνώντας δείκτες ως παραμέτρους σε συναρτήσεις

22/11

Δένδρα. Είδη Δένδρων. Λειτουργίες σε Δένδρα. Υλοποίηση Δένδρων

Μελέτη διαφανειών.

Για όσους διαβάζουν αγγλικά, Sections 4.2, 4.3 & 4.4 (Representation of Binary Trees & Representation of Ordered Trees) Lewis, Denenberg, "Data Structures & Their Algorithms".

23/11

24/11

27/11

Δένδρα. Υλοποίση Πλήρων Δυαδικών Δένδρων. Διασχίσεις Δένδρων.

Μελέτη διαφανειών. Μελέτη Ενοτήτων 4.2, 4.3.1, Μανωλόπουλος

Για όσους διαβάζουν αγγλικά, Sections 4.4 (Representation of Complete Binary Trees) & 4.5 (Stack Based Traversals), Lewis, Denenberg, "Data Structures & Their Algorithms".

28/11

lab3.doc

Υλοποίηση λίστας - Περνώντας δείκτες ως παραμέτρους σε συναρτήσεις

29/11

Δένδρα. Διασχίσεις Δένδρων. Νηματικά δένδρα. Εισαγωγή στα Λεξικά.

Μελέτη διαφανειών. Μελέτη Ενότητας 4.3.2, Μανωλόπουλος

Για όσους διαβάζουν αγγλικά, Sections 4.5 (Threaded Trees, Implementing Level-Order Traversal), 6.1 & 6.2, Lewis, Denenberg, "Data Structures & Their Algorithms".

30/11

1/12

Ανάρτηση 3ης σειράς ασκήσεων

4/12

Υλοποίηση Λεξικών με ταξινομημένες λίστες - Λίστες Παράλειψης.

Μελέτη διαφανειών. Μελέτη Ενοτήτων 8.1, 8.2 και 8.3, Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά, Section 6.3 (Ordered Lists & Binary Search), Lewis, Denenberg, "Data Structures & Their Algorithms".

5/12

lab1.doc

Υλοποίηση Δένδρου

6/12

Λίστες Παράλειψης.

Μελέτη διαφανειών. Μελέτη Ενότητας 3.4.5, Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά, Section 6.3 (Skip Lists), Lewis, Denenberg, "Data Structures & Their Algorithms".

7/12

Ταξινομημένα Δένδρα Δυαδικής Αναζήτησης.

Μελέτη διαφανειών. Μελέτη Ενότητας 4.4, Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά, Section 6.4 (Binary Search Trees, Insertion & Deletion), Lewis, Denenberg, "Data Structures & Their Algorithms".

Αναπλήρωση μαθήματος που χάθηκε στις 15/11. Ώρα μαθήματος: 6-8

8/12

11/12

AVL Δένδρα -Εισαγωγή.

Μελέτη διαφανειών. Μελέτη Ενοτήτων 5.1 και 5.2, Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά, Section 7.1 (AVL Trees - Insertion), Lewis, Denenberg, "Data Structures & Their Algorithms".

12/12

lab2.doc

Υλοποίηση Δένδρου

Προθεσμία για την 3η σειρά

Ανάρτηση 4ης σειράς ασκήσεων

13/12

AVL Δένδρα -Διαγραφή. 2-3 Δένδρα.

Μελέτη διαφανειών. Μελέτη Ενότητας 5.2, Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά, Section 7.1 (AVL Trees - Deletion), Lewis, Denenberg, "Data Structures & Their Algorithms".

14/12

Ανάρτηση Προγραμματιστικής Άσκησης (ds-homework-C.pdf)

15/12

2-3 Δένδρα. Splay Δένδρα.

Μελέτη διαφανειών. Μελέτη Ενότητας 5.6, Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά, Section 7.2 (2-3 Trees) & 7.3 (Self-Adjusting Binary Search Trees), Lewis, Denenberg, "Data Structures & Their Algorithms".

Αναπλήρωση μαθήματος που χάθηκε λόγω εκλογών στις 23/10. Ώρα: 13:00-15:00

18/12

Splay Δένδρα. Κοκκινόμαυρα Δένδρα.

Μελέτη διαφανειών. Μελέτη Ενότητας 5.6, Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά: Section 7.3 (Self-Adjusting Binary Search Trees), Lewis, Denenberg, "Data Structures & Their Algorithms". Μελέτη Κεφαλαίου 14 (Red-Black Trees), Cormen, Leiserson & Rivest, "Introduction to Algorithms".

19/12

lab3.doc

Υλοποίηση Δένδρου

20/12

Κοκκινόμαυρα Δένδρα. Επίλυση Ασκήσεων.

Μελέτη διαφανειών.

Για όσους διαβάζουν αγγλικά, Κεφαλαίου 14 (Red-Black Trees), Cormen, Leiserson & Rivest, "Introduction to Algorithms".

Το 1ο μέρος του βιβλίου υπάρχει και σε μετάφραση από τις Πανεπιστημιακές εκδόσεις Κρήτης. Τίτλος: "Εισαγωγή στους Αλγόριθμους", Μετάφραση: Ιωάννης Παπαδόγγονας, Επιστημονική Επιμέλεια: Γεώργιος Γεωργακόπουλος. Το κεφάλαιο των κόκκινων μαύρων δένδρων που μας ενδιαφέρει είναι το κεφάλαιο 13.

21/12

Προθεσμία για την 4η σειρά

Ανάρτηση 5ης Σειράς

22/12

Διακοπές Χριστουγέννων

8/1

Κατακερματισμός.

Μελέτη διαφανειών. Μελέτη Ενοτήτων 9.1, 9.3.2, 9.3.3, Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά: Section 8.3 (Chaining Strategies), Lewis, Denenberg, "Data Structures & Their Algorithms".

9/1

Κατακερματισμός.

Μελέτη διαφανειών. Μελέτη Ενοτήτων 9.3.1, 9.4, Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά: Section 8.3 (Open Addressing Strategies) , Lewis, Denenberg, "Data Structures & Their Algorithms".

10/1

Συναρτήσεις Κατακερματισμού. Ουρές Προτεραιότητας. Union-Find.

Μελέτη διαφανειών. Μελέτη Ενοτήτων 9.2, 9.5, 9.6 Μανωλόπουλος.

Για όσους διαβάζουν αγγλικά: Section 8.5 (Hashing by Division, Perfect Hashing of Static Data, Universal Classes of Hash Functions) & 9.1, 9.2 (χωρίς αποδείξεις θεωρημάτων), Lewis, Denenberg, "Data Structures & Their Algorithms".

11/1

12/1

15/1

Φροντιστηριακή Απασχόληση

Προθεσμία Προγραμματιστικής Άσκησης

16/1

Φροντιστηριακή Απασχόληση

17/1

Φροντιστηριακή Απασχόληση

Προθεσμία για την 5η & 6η σειρά

18/1

19/1

Διαφάνειες Διαλέξεων & Άλλο Υλικό

5η & 6η σειρά ασκήσεων (ds-homework5.pdf).

Νέα έκδοση διαφανειών σε κόκκινα-μαύρα δένδρα (red-black-trees-trasparencies.pdf).

Προγραμματιστική άσκηση (ds-homework-C.pdf).

4η σειρά ασκήσεων (ds-homework4.doc).
3η σειρά ασκήσεων (homework3.pdf).
2η Σειρά Ασκήσεων (ds-homework2.doc).
1η Σειρά Ασκήσεων (ds-homework1.doc).
Οι διαφάνειες των διαλέξεων έχουν φωτοτυπηθεί στο τυπογραφείο του Πανεπιστημίου και μπορείτε να τις παίρνετε από το γραφείο της κ. Σουλίου (2ος όροφος). Η ηλεκτρονική έκδοση όλων των διαφανειών είναι επίσης διαθέσιμη (pdf, ps.gz, pdf.gz).
Γενικές Πληροφορίες για το μάθημα (syllabus.doc).

Τελευταία τροποποίηση: 18/12/06
Κατασκευή και συντήρηση των σελίδων: Παναγιώτα Φατούρου

Τρίτη, 24/10	lab1.doc
Τρίτη, 31/10	lab2.doc
Τρίτη, 7/11	lab3.doc
Τρίτη, 14/11	lab1.doc
Τρίτη, 21/11	lab2.doc
Τρίτη, 28/11	lab3.doc
Τρίτη, 5/12	lab1.doc
Τρίτη, 12/12	lab2.doc
Τρίτη, 19/12	lab3.doc