EPL035: Data Structures and Algorithms for ECE
by Demetris Zeinalipour
Department of Computer Science
University of Cyprus

Quick Links

WebMail
CS Courses

EPL035: Schedule

 

Week

   Περιγραφή PDF
1 Δ. Περιγραφή Συμβολαίου,  Δομές Δεδομένων και Αλγόριθμοι

Αλγόριθμοι και Πολυπλοκότητα, Οργάνωση Δεδομένων και Δομές Δεδομένων

Syllabus

Lecture 1

  Φ. Αρχές Προγραμματισμού: Συμβολοσειρές 
(Στόχος: Επανάληψη Βασικών Αρχών Προγραμματισμού από EPL034)

Εισαγωγικές Έννοιες σε Strings (Αρχικοποίηση, Ανάγνωση & Εκτύπωση), Πίνακες από Strings, Συναρτήσεις Βιβλιοθήκης <string.h>, Υλοποίηση Συναρτήσεων Βιβλιοθήκης

Ανάθεση Άσκησης 1 (Strings)

Lecture 2

AS1

  Δ. Αρχές Προγραμματισμού: Δείκτες & Πίνακες

Αριθμητική Δεικτών, Δείκτες και Πίνακες, Παραδείγματα

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

AS2

 

Δ.

Αφηρημένοι Τύποι Δεδομένων (Στοίβες, Ουρά, Κυκλική Ουρά)

Αφηρημένοι Τύποι Δεδομένων (ΑΤΔ), Οι ΑΤΔ Στοίβα και Ουρά, Υλοποίηση των ΑΤΔ Στοίβα και Ουρά με Στατική Δέσμευση Μνήμης

Lecture 8
4

Δ.

Στοίβες: Υλοποίηση  & Εφαρμογές (με Δυναμική Δέσμευση)

Υλοποίηση Στοιβών με Δυναμική Δέσμευση Μνήμης, Εφαρμογή Στοιβών 1: Αναδρομικές συναρτήσεις, Εφαρμογή Στοιβών 2: Ισοζυγισμός Παρενθέσεων

Lecture 9
  Φ. Φροντιστήριο: Μελέτη παραδείγματος Στοίβας με Δυναμική Δέσμευση Μνήμης

Παράδοση Άσκησης 2 (στο Moodle, Τετάρτη στις 12:00)

stack1.c

stack2.c

  Δ. Λίστες: Υλοποίηση & Εφαρμογές

Ευθύγραμμες Απλά Συνδεδεμένες Λίστες, Ευθύγραμμες Διπλά Συνδεδεμένες Λίστες

Lecture 10
5 Δ. Ολοκλήρωση Διάλεξης 7 - Διπλά Συνδεδεμένες Λίστες

Πολυπλοκότητα Αλγορίθμων / Επανάληψη Χρήσιμων Μαθηματικών Ορισμών

Πρόβλημα, Στιγμιότυπο, Αλγόριθμος, Εμπειρική - Θεωρητική Ανάλυση Αλγορίθμων, Εργαλεία εκτίμησης πολυπλοκότητας: οι τάξεις Ο(n), Ω(n), Θ(n), Παραδείγματα Ανάλυσης Πολυπλοκότητας, Χρήσιμοι μαθηματικοί ορισμοί, Μαθηματική Επαγωγή

Lecture 11
  Φ.

Πολυπλοκότητα Αλγορίθμων / Επανάληψη Χρήσιμων Μαθηματικών Ορισμών

Εργαλεία εκτίμησης πολυπλοκότητας: οι τάξεις Ο(n), Ω(n), Θ(n), Παραδείγματα Ανάλυσης Πολυπλοκότητας, Χρήσιμοι μαθηματικοί ορισμοί, Μαθηματική Επαγωγή


Lecture 11

AS3

  Δ. Πολυπλοκότητα Αλγορίθμων / Επανάληψη Χρήσιμων Μαθηματικών Ορισμών

Παραδείγματα Ανάλυσης Πολυπλοκότητας, Χρήσιμοι μαθηματικοί ορισμοί, Μαθηματική Επαγωγή

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 18

  Δ. Εισαγωγή σε Γράφους

Ορισμοί & Υλοποίηση, Μέθοδοι διάσχισης Γράφων

Lecture 19
10 Δ. Βοηθητικές αναδρομικές ασκήσεις σε Δένδρα Tutorial 20
  Φ. Παράδοση Άσκησης 4 (στο Moodle, Τετάρτη στις 12:00) 
Ανάθεση Άσκησης 5 (Δένδρα) και επεξήγηση

AS5

  Δ. Γράφοι: Τοπολογική Ταξινόμηση

Ολοκλήρωση Διάλεξης 19

Τοπολογική Ταξινόμηση: DAGs, Αλγόριθμοι, Εφαρμογές

Lecture 21
11 Δ. Ελάχιστα Γεννητορικά Δένδρα σε Γράφους

Εφαρμογές, Ο αλγόριθμος του Prim

Lecture 22

Φ. Βοηθητικές Ασκήσεις σε Γράφους I



Tutorial 23

Δ.  Ελάχιστα Γεννητορικά Δένδρα σε Γράφους (συνέχεια)

Ο αλγόριθμος του Kruskal.

Lecture 24
12 Δ. Βραχύτερα Μονοπάτια σε Γράφους

Ο αλγόριθμος του Dijkstra.

Lecture 25
  Φ. Βοηθητικές Ασκήσεις σε Γράφους II

Παράδοση Άσκησης 5 (στο Moodle, Τετάρτη στις 12:00) 

Ανάθεση Άσκησης 6 (Γράφοι)

Tutorial 26

AS6

  Δ. Κατακερματισμός (Hashing)

Ανασκόπηση Προβλήματος και Προκαταρκτικών Λύσεων, Bit-Διανύσματα, Τεχνικές Κατακερματισμού & Συναρτήσεις Κατακερματισμού, Διαχείριση Συγκρούσεων με Αλυσίδωση

Lecture 27
13 Δ. Κατακερματισμός (Hashing)

Διαχείριση Συγκρούσεων με Ανοικτή Διεύθυνση 
a) Linear Probing, b) Quadratic Probing c) Double Hashing

Lecture 28
  Φ. Ολοκλήρωση διαφανειών Κατακερματισμού Ασκήσεις σε Κατακερματισμό

Διατεταγμένος Κατακερματισμός (Ordered Hashing), Συμπαγής Κατάλογοι (Bloom Filters), Επανακατακερματισμός (Rehashing), Εφαρμογές Κατακερματισμού, Βοηθητικές Ασκήσεις σε Κατακερματισμό.

Παράδοση Άσκησης 6 (στο Moodle, Τετάρτη στις 12:00)

Tutorial 29

  Δ.  Σωροί και Ταξινόμηση Σωρού Lecture 30

Παρασκευή 2/12 - Λήξη Μαθημάτων

9-23 / 12 - Εβδομάδα Τελικών Εξετάσεων

ΤΕΛΙΚΗ ΕΞΕΤΑΣΗ

Ημέρα: 16/12/11
Ωρα: 8:30-11:30
Τοποθεσία: Πανεπιστημιούπολη, ΧΩΔ01-108


Copyright © Department of Computer Science, University of Cyprus