| |
EPL035: Data Structures and Algorithms for ECE
|
Quick Links
|
| EPL035: Schedule |
|
Week |
Περιγραφή | ||
| 1 | Δ. | Περιγραφή Συμβολαίου, Δομές
Δεδομένων και Αλγόριθμοι
Αλγόριθμοι και Πολυπλοκότητα, Οργάνωση Δεδομένων και Δομές Δεδομένων |
Syllabus |
| Φ. | Αρχές Προγραμματισμού: Συμβολοσειρές (Στόχος: Επανάληψη Βασικών Αρχών Προγραμματισμού από EPL034) Εισαγωγικές Έννοιες σε Strings (Αρχικοποίηση, Ανάγνωση & Εκτύπωση), Πίνακες από Strings, Συναρτήσεις Βιβλιοθήκης <string.h>, Υλοποίηση Συναρτήσεων Βιβλιοθήκης Ανάθεση Άσκησης 1 (Strings) |
Lecture 2 | |
| Δ. | Αρχές Προγραμματισμού: Δείκτες
& Πίνακες
Αριθμητική Δεικτών, Δείκτες και Πίνακες, Παραδείγματα |
Lecture 3 | |
| 2 | Δ. | Αρχές Προγραμματισμού: Ολοκλήρωση
Διάλεξης 3, Δείκτες
και Πίνακες
Πίνακες Δεικτών, Παραδείγματα, Πολυδιάστατοι πίνακες, Πέρασμα παραμέτρων σε προγράμματα C |
Lecture 4 |
| Φ. | Αρχές Προγραμματισμού: Δομές
Δεδομένων και Ενώσεις (struct / union) Δομές, φωλιασμένες δομές, τρόποι δήλωσης δομών, δομές ως παράμετροι σε συναρτήσεις, δείκτες σε δομές, χρήση ενώσεων. Παράδοση Άσκησης 1 (στο Moodle, Τετάρτη στις 12:00) |
Lecture 5 | |
| Δ. | Αρχές Προγραμματισμού:
Διαχείριση Μνήμης & Δυναμικές Δομές Δεδομένων
Δυναμικές Δομές Δεδομένων Γενικά, Δυναμική Δέσμευση/Αποδέσμευση Μνήμης, Δομή τύπου structure – Αυτοαναφορικές δομές, Η δήλωση typedef στη C
|
Lecture 6 | |
| 3 |
Δ. |
Αρχές Προγραμματισμού: Ολοκλήρωση
Διάλεξης 5,6, Αναδρομή
Η έννοια της αναδρομής, Μη-αναδρομικός / Αναδρομικός Ορισμός Συναρτήσεων, Παραδείγματα Ανάδρομης: Παραγοντικό, Δύναμη, Αριθμοί Fibonacci, Αφαίρεση της Αναδρομής |
Lecture 7 |
|
Φ. |
Φροντιστήριο: Ολοκλήρωση
Διάλεξης
7, Επεξήγηση
/ Συζήτηση Άσκησης 2 Ανάθεση Άσκησης 2 (Δομές, Δείκτες, Δυναμική Δέσμευση Μνήμης και Αρχεία) |
Lecture 7 |
|
|
Δ. |
Αφηρημένοι Τύποι Δεδομένων (Στοίβες,
Ουρά, Κυκλική Ουρά)
Αφηρημένοι Τύποι Δεδομένων (ΑΤΔ), Οι ΑΤΔ Στοίβα και Ουρά, Υλοποίηση των ΑΤΔ Στοίβα και Ουρά με Στατική Δέσμευση Μνήμης |
Lecture 8 | |
| 4 |
Δ. |
Στοίβες: Υλοποίηση & Εφαρμογές
(με
Δυναμική Δέσμευση)
Υλοποίηση Στοιβών με Δυναμική Δέσμευση Μνήμης, Εφαρμογή Στοιβών 1: Αναδρομικές συναρτήσεις, Εφαρμογή Στοιβών 2: Ισοζυγισμός Παρενθέσεων |
Lecture 9 |
| Φ. | Φροντιστήριο: Μελέτη παραδείγματος Στοίβας με Δυναμική
Δέσμευση Μνήμης Παράδοση Άσκησης 2 (στο Moodle, Τετάρτη στις 12:00) |
stack1.c | |
| Δ. | Λίστες: Υλοποίηση & Εφαρμογές
Ευθύγραμμες Απλά Συνδεδεμένες Λίστες, Ευθύγραμμες Διπλά Συνδεδεμένες Λίστες |
Lecture 10 | |
| 5 | Δ. | Ολοκλήρωση Διάλεξης 7 - Διπλά
Συνδεδεμένες Λίστες
Πολυπλοκότητα Αλγορίθμων / Επανάληψη Χρήσιμων Μαθηματικών Ορισμών Πρόβλημα, Στιγμιότυπο, Αλγόριθμος, Εμπειρική - Θεωρητική Ανάλυση Αλγορίθμων, Εργαλεία εκτίμησης πολυπλοκότητας: οι τάξεις Ο(n), Ω(n), Θ(n), Παραδείγματα Ανάλυσης Πολυπλοκότητας, Χρήσιμοι μαθηματικοί ορισμοί, Μαθηματική Επαγωγή |
Lecture 11 |
| Φ. |
Πολυπλοκότητα Αλγορίθμων / Επανάληψη Χρήσιμων Μαθηματικών Ορισμών Εργαλεία εκτίμησης πολυπλοκότητας: οι τάξεις Ο(n),
Ω(n), Θ(n), Παραδείγματα Ανάλυσης Πολυπλοκότητας,
Χρήσιμοι μαθηματικοί ορισμοί, Μαθηματική Επαγωγή
|
Lecture 11 |
|
| Δ. | Πολυπλοκότητα Αλγορίθμων / Επανάληψη
Χρήσιμων Μαθηματικών Ορισμών
Παραδείγματα Ανάλυσης Πολυπλοκότητας, Χρήσιμοι μαθηματικοί ορισμοί, Μαθηματική Επαγωγή |
Lecture 11 | |
| 6 | Δ. | Παραδείγματα Ανάλυση Πολυπλοκότητας
Παραδείγματα Ανάλυσης Πολυπλοκότητα, Γραμμική και Δυαδική Αναζήτηση |
Lecture 12 |
| Φ. | Αναδρομικές Σχέσεις - Ανάλυση
Πολυπλοκότητας
Αναδρομικές Σχέσεις, Παραδείγματα Ανάλυσης
Πολυπλοκότητα, Γραμμική
και Δυαδική Αναζήτηση Ανάθεση Άσκησης 3 (Ανάλυση Πολυπλοκότητας |
ecture 12 | |
| Δ. | Αλγόριθμοι Ταξινόμησης (SelectionSort,
InsertionSort)
Οι αλγόριθμοι ταξινόμησης: SelectionSort,
InsertionSort, Ανάλυση Πολυπλοκότητας, Σύγκριση |
Lecture 13 | |
| 7 | Δ. | Ολοκλήρωση Διάλεξης 13 - Συγκριση SelectionSort / InsertionSort
Αλγόριθμοι Ταξινόμησης (Mergesort, BucketSort) Οι αλγόριθμοι ταξινόμησης: MergeSort, BucketSort, Ανάλυση Πολυπλοκότητας, |
Lecture 14 |
| Φ. | Αλγόριθμοι Ταξινόμησης (Mergesort,
BucketSort)
Οι αλγόριθμοι ταξινόμησης: MergeSort, BucketSort, Ανάλυση Πολυπλοκότητας, Παράδοση Άσκησης 3 (εκτυπωμένο στο γραφείου του Υπεύθυνου Εργαστηρίου σας, Τετάρτη στις 12:00) |
Lecture 14 | |
| Δ. | Αλγόριθμοι Ταξινόμησης (QuickSort)
Ο αλγόριθμος QuickSort, Έμμεση Ταξινόμηση, Εξωτερική Ταξινόμηση |
Lecture 15 | |
| 8 | Ενδιάμεση Εξέταση - Δευτέρα 24 Οκτωβρίου 2011 (μέχρι και τους Αλγόριθμους Ταξινόμησης) | --- | |
Φ. |
Ανάθεση Άσκησης 4
(Γραμμικες Δομές) |
AS4  |
|
| Δ. | Εισαγωγή σε Δενδρικές Δομές Δεδομένων
Εισαγωγή σε δενδρικές δομές δεδομένων, Ορισμοί και πράξεις, Αναπαράσταση δενδρικών δομών δεδομένων στη μνήμη, Διάσχιση Δέντρων. |
Lecture 16 | |
| 9 | Δ. | Δυαδικά Δέντρα & Δυαδικά Δέντρα
Αναζήτησης
Δυαδικά Δένδρα, Δυαδικά Δένδρα Αναζήτησης, Πράξεις Εισαγωγής, Εύρεσης Στοιχείου, Διαγραφής Μικρότερου Στοιχείου |
Lecture 17 |
| Φ. | Β-δέντρα
Εισαγωγή & Ισοζυγισμένα Δένδρα, 2-3 Δένδρα, Περιγραφή Πράξεων της Εισαγωγής και αναφορά σε άλλες πράξεις, Β-δένδρα |
||
| Δ. | Εισαγωγή σε
Γράφους
Ορισμοί & Υλοποίηση, Μέθοδοι διάσχισης Γράφων |
Lecture 19 | |
| 10 | Δ. | Βοηθητικές αναδρομικές ασκήσεις σε Δένδρα | Tutorial 20 |
| Φ. | Παράδοση Άσκησης 4 (στο
Moodle, Τετάρτη στις 12:00)
Ανάθεση Άσκησης 5 (Δένδρα) και επεξήγηση |
||
| Δ. | Γράφοι: Τοπολογική
Ταξινόμηση
Ολοκλήρωση Διάλεξης 19 Τοπολογική Ταξινόμηση: DAGs, Αλγόριθμοι, Εφαρμογές |
Lecture 21 | |
| 11 | Δ. | Ελάχιστα
Γεννητορικά
Δένδρα σε Γράφους
Εφαρμογές, Ο αλγόριθμος του Prim |
Lecture 22 |
| Φ. | Βοηθητικές
Ασκήσεις σε Γράφους I
|
Tutorial 23 |
|
| Δ. | Ελάχιστα
Γεννητορικά Δένδρα σε Γράφους (συνέχεια)
Ο αλγόριθμος του Kruskal. |
Lecture 24 | |
| 12 | Δ. | Βραχύτερα Μονοπάτια σε Γράφους
Ο αλγόριθμος του Dijkstra. |
Lecture 25 |
| Φ. | Βοηθητικές Ασκήσεις σε Γράφους II Παράδοση Άσκησης 5 (στο Moodle, Τετάρτη στις 12:00) Ανάθεση Άσκησης 6 (Γράφοι) |
|
|
| Δ. | Κατακερματισμός (Hashing)
Ανασκόπηση Προβλήματος και Προκαταρκτικών Λύσεων, Bit-Διανύσματα, Τεχνικές Κατακερματισμού & Συναρτήσεις Κατακερματισμού, Διαχείριση Συγκρούσεων με Αλυσίδωση |
Lecture 27 | |
| 13 | Δ. | Κατακερματισμός (Hashing)
Διαχείριση Συγκρούσεων με Ανοικτή Διεύθυνση |
Lecture 28 |
| Φ. | Ολοκλήρωση διαφανειών Κατακερματισμού
Ασκήσεις σε Κατακερματισμό
Διατεταγμένος Κατακερματισμός (Ordered Hashing), Συμπαγής Κατάλογοι (Bloom Filters), Επανακατακερματισμός (Rehashing), Εφαρμογές Κατακερματισμού, Βοηθητικές Ασκήσεις σε Κατακερματισμό. Παράδοση Άσκησης 6 (στο Moodle, Τετάρτη στις 12:00) |
||
| Δ. | Σωροί και Ταξινόμηση Σωρού | Lecture 30 |
|
|
Παρασκευή 2/12 - Λήξη Μαθημάτων 9-23 / 12 - Εβδομάδα Τελικών Εξετάσεων |
|||
|
ΤΕΛΙΚΗ ΕΞΕΤΑΣΗ Ημέρα: 16/12/11 |
|||
