Εργασία 2

Last updated on Mar 23, 2021

Ανακοινώθηκε: 10/4/2020
Προθεσμία παράδοσης: ~~9/5/2020~~ 16/5/2020 23:59
10-15% του συνολικού βαθμού στο μάθημα
Link εγγραφής: https://classroom.github.com/a/7r3sD2Me
Repository: https://github.com/chatziko-k08/2020-project-2

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

Άσκηση 1 (20%)

Στο ADTVector module, καθώς και στην υλοποίησή του μέσω Dynamic Array, προσθέστε την ακόλουθη λειτουργία:

// Επιστρέφει τον αριθμό βημάτων που πραγματοποίησε η συνάρτηση
// vector_* που κλήθηκε τελευταία (όποια και να ήταν αυτή).

int vector_steps(Vector vector);

Πχ, αν η τελευταία συνάρτηση που κλήθηκε ήταν η vector_insert_last, και δεν έγινε resize, τότε η vector_steps θα πρέπει να επιστρέψει 1. Ως συνήθως, ως “βήμα” θεωρούμε οποιοδήποτε αριθμό εντολών σταθερού χρόνου, δηλαδή που ο χρόνος εκτέλεσής τους δεν εξαρτάται από τον αριθμό στοιχείων $n$ του vector. Προσοχή: μια εντολή μπορεί από μόνη της να εκτελεί πολλά βήματα, πχ μια realloc που αντιγράφει πολλά στοιχεία (ο χρόνος εκτέλεσής της εξαρτάται από το $n$).

Στη συνέχεια, φτιάξτε ένα πρόγραμμα vector_insert_steps που να υπολογίζει τον αριθμό βημάτων που εκτέλεσε η vector_insert_last ως συνάρτηση του $n$, για $1 \le n \le 10000$, στις ακόλουθες περιπτώσεις:

real-time: για κάθε $n$ υπολογίζουμε τον αριθμό βημάτων που εκτελεί η vector_insert_last όταν το vector περιέχει $n$ στοιχεία τη στιγμή της κλήσης.
amortized-time: για κάθε $n$ υπολογίζουμε το μέσο αριθμό βημάτων που εκτελεί η vector_insert_last για $n$ διαδοχικά inserts ξεκινώντας από κενό vector (δηλαδή σύνολο βημάτων / $n$).

Το πρόγραμμα θα καλείται ως vector_insert_steps <type> όπου <type> = real | amortized και θα τυπώνει τα αποτελέσματα στην έξοδό του σε comma separated (CSV) format, ως εξής:

1,<steps for n=1>
2,<steps for n=2>
...

Στη συνέχεια, δημιουργήστε γραφικές παραστάσεις για τις δύο αυτές περιπτώσεις, στις οποίες το $n$ θα είναι στον άξονα x, και ο αριθμός βημάτων στην άξονα y. Μπορείτε να χρησιμοποιήσετε όποιο πρόγραμμα θέλετε για τις γραφικές παραστάσεις (πχ οποιοδήποτε spreadsheet, Google Sheets, LifreOffice Calc, Excel, κλπ, μπορεί να διαβάσει το format αυτό και να παράγει γραφικές παραστάσεις).

Στο README.md πρέπει να προσθέσετε τις γραφικές παραστάσεις (σαν εικόνες), και να τις ερμηνεύσετε πολύ συνοπτικά, με βάση τις πολυπλοκότητες που είδαμε στο μάθημα.

Bonus (5%): πραγματοποιήστε την ίδια διαδικασία για οποιαδήποτε άλλη λειτουργία, οποιουδήποτε άλλου ADT θέλετε (πχ ADTPriorityQueue).

Άσκηση 2 (20%)

Ο ADT Bidirectional List (ADTBList) είναι παρόμοιος με τον ADTList, αλλά επιπλέον παρέχει

σειριακό traversal και προς τις δύο κατευθύνσεις
εισαγωγή πριν από κάποιο κόμβο
διαγραφή του ίδιου του κόμβου (όχι του επόμενου)

Οι λειτουργίες περιγράφονται στο include/ADTBList.h στο repository της εργασίας.

Υλοποιήστε τον τύπο αυτό χρησιμοποιώντας διπλά συνδεδεμένες λίστες, δηλαδή συνδεδεμένες λίστες όπου κάθε κόμβος περιέχει δείκτες προς τον επόμενο αλλά και τον προηγούμενο. Μία κενή υλοποίηση υπάρχει στο modules/UsingDoublyLL/ADTBList.c. Μπορείτε φυσικά να χρησιμοποιήσετε τμήματα κώδικα από την υλοποίηση του ADT List. Όλες οι λειτουργίες (εκτός της find) θα πρέπει να είναι $O(1)$. Μπορείτε να χρησιμοποιήσετε dummy κόμβους, αλλά είναι προαιρετικό.

Επίσης, υλοποιήστε test για τις λειτουργίες του ADTBList. Ένα κενό test υπάρχει στο tests/ADTBList_test.c, και πάλι μπορείτε να επαναχρησιμοποιήσετε τα αντίστοιχα τμήματα του ADTList_test.c. Τα tests θα πρέπει να καλύπτουν όλες τις λειτουργίες και η υλοποίηση να τα περνάει χωρίς leaks.

Άσκηση 3 (20%)

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

Από άποψη διεπαφής, ένα τρόπος να γίνει αυτό είναι να εισάγουμε την έννοια του κόμβου (όπως στους περισσότερους άλλους ΑΤΔ), και

Η pqueue_insert να επιστρέφει τον κόμβο του στοιχείου που προστέθηκε (τον οποίο μπορούμε να αποθηκεύσουμε όπου θέλουμε).
Να προστεθεί η ακόλουθη συνάρτηση.

// Αφαιρεί τον κόμβο node ο οποίος μπορεί να βρίσκεται σε οποιαδήποτε θέση της ουράς
// (μη ορισμένη συμπεριφορά αν δεν ανήκει στην ουρά).

void pqueue_remove_node(PriorityQueue pqueue, PriorityQueueNode node);

Δημιουργήστε μια υλοποίηση αυτής της επέκτασης του ADTPriorityQueue, χρησιμοποιώντας τον ADTSet (δηλαδή μια εξαρτημένη δομή, χωρίς χρήση σωρού). Ο ADTSet ενδείκνυται για αυτό το σκοπό αφού παρέχει και διάταξη και αφαίρεση οποιουδήποτε στοιχείου. Στο include/ADTPriorityQueue.h υπάρχουν όλες οι δηλώσεις (μαζί με τις νέες συναρτήσεις), από την άλλη το modules/UsingADTSet/ADTPriorityQueue.c πρέπει να το δημιουργήσετε εσείς, μαζί με το αντίστοιχο Makefile, κλπ.

Στο tests/ADTPriorityQueue_test.c υπάρχουν tests για όλες τις λειτουργίες (συμπεριλαμβανομένων και των νέων). Η υλοποίησή σας πρέπει να τα περνάει χωρίς leaks.

Σημειώσεις:

Για την υλοποίηση του ADTSet μπορείτε να χρησιμοποιήσετε το modules/UsingBinarySearchTree/ADTSet.c που υπάρχει στο repository (ή και κάποια άλλη, αν επιθυμείτε).
Μπορείτε να θεωρήσετε ότι στην ουρά δεν υπάρχουν ισοδύναμα στοιχεία (δηλαδή στοιχεία για τα οποία compare(a, b) == 0), το οποίο διευκολύνει την υλοποίηση αφού και ο ADTSet δεν επιτρέπει διπλά στοιχεία.
Εφόσον υπάρχει η έννοια του κόμβου, προστίθεται και η συνηθισμένη συνάρτηση pqueue_node_value που επιστρέφει την τιμή ενός κόμβου.
Η συνάρτηση pqueue_update_order (που αφορά την άσκηση 4) δεν χρειάζεται να υλοποιηθεί. Πρέπει όμως να προσθέσετε μια κενή υλοποίηση για να κάνει compile το test. Αν επιπλέον θέλετε και να μην αποτυγχάνει το αντίστοιχο test λόγω της κενής υλοποίησης, μπορείτε να το παραλείψετε εκτελώντας το ως εξής:
```
./UsingADTSet_ADTPriorityQueue_test --skip update_order
```

Bonus (10%):

Επιτρέψτε στην υλοποίησή σας διπλά στοιχεία, παρόλο που δεν τα υποστηρίζει ο ADTSet. Για να συμβεί αυτό πρέπει να εισάγετε κάτι διαφορετικό στο Set, όχι απλά τις τιμές.
Υλοποιήστε και τη συνάρτηση pqueue_update_order από την άσκηση 4. Για να γίνει αυτό μπορεί να χρειαστεί να προσθέσετε επιπλέον λειτουργίες στον ADTSet, αν δε σας αρκούν αυτές που παρέχει.

Άσκηση 4 (20%)

Ένας άλλος σημαντικός περιορισμός της κλασσικής ουράς προτεραιότητας είναι ότι δεν μπορεί να αλλάξει η διάταξη ενός στοιχείου μετά την εισαγωγή του. Πχ το παρακάτω είναι λάθος:

int* a = create_int(10);
pqueue_insert(pqueue, a);
// ...
*a = 20;    // λάθος, η ουρά δεν μπορεί να γνωρίζει ότι το στοιχείο ξαφνικά μεγάλωσε!

Από άποψη διεπαφής, μπορούμε να επιτρέψουμε τέτοιες αλλαγές κάνοντας την pqueue_insert να επιστρέφει τον νέο κόμβο (όπως στην άσκηση 3) και προσθέτοντας την παρακάτω συνάρτηση.

// Ενημερώνει την ουρά μετά από αλλαγή της διάταξης της τιμής του κόμβου node.
// Η μόνη επιτρεπτή χρήση είναι η εξής:
// 1. Αλλαγή της διάταξης του κόμβου node
//    (αλλάζοντας τα περιεχόμενα του αντίστοιχου value)
// 2. Κλήση της συνάρτησης pqueue_update_order για αποκατάσταση της σειράς.
//
// Ανάμεσα στα βήματα 1 και 2 ΔΕΝ επιτρέπεται:
// - η αλλαγή οποιουδήποτε άλλου κόμβου
// - η κλήση οποιασδήποτε άλλης συνάρτησης pqueue_*

void pqueue_update_order(PriorityQueue pqueue, PriorityQueueNode node);

Οπότε η παρακάτω χρήση επιτρέπεται:

int* a = create_int(10);
PriorityQueueNode node = pqueue_insert(pqueue, a);
// ...
*a = 20;    // αλλαγή στοιχείου, πρέπει να κάνουμε update_order!
pqueue_update_order(pqueue, node);

Τροποποιήστε την υπάρχουσα υλοποίηση του ADTPriorityQueue μέσω σωρού (modules/UsingHeap/ADTPriorityQueue.c), προσθέτωντας την παραπάνω συνάρτηση pqueue_update_order, αλλά και τη pqueue_remove_node της άσκησης 3. Η υλοποίηση θα πρέπει να περνάει τα υπάρχοντα tests (tests/ADTPriorityQueue_test.c) χωρίς leaks.

Σημειώσεις:

Στην υλοποίηση πρέπει να προστεθεί η έννοια των κόμβων που στην προηγούμενη υλοποίηση δεν υπήρχε. Ο σωρός δηλαδή αποθηκεύει κόμβους, όχι απλά τιμές.
Στους κόμβους, πέρα από τις τιμές, μπορείτε φυσικά να αποθηκεύετε και οποιαδήποτε άλλη πληροφορία σας είναι χρήσιμη.
Προσοχή στο γεγονός ότι τα updates και removes δεν θα πρέπει να αλλάζουν τα περιεχόμενα των κόμβων. Δηλαδή το pqueue_node_value(pqueue, node) στο παραπάνω παράδειγμα θα πρέπει πάντα να επιστρέφει a, ανεξάρτητα από τη θέση στην οποία έχει μετακινηθεί ο κόμβος.
Αλγοριθμικά, οι λειτουργίες αυτές μπορούν να γίνουν με πολύ μικρή τροποποίηση των αλγορίθμων εισαγωγής και διαγραφής σε σωρό που είδαμε στο μάθημα.
Είναι χρήσιμο να σχεδιάσετε στο χαρτί τη λογική της υλοποίησης, τους αλγορίθμους, κλπ, πριν ξεκινήσετε να γράφετε κώδικα, όπως κάνουμε και στις διαλέξεις.
Όλες οι λειτουργίες θα πρέπει να είναι αποδοτικές ($O(\log n)$ ή καλύτερα).

Άσκηση 5 (20%)

Στην υλοποίηση του ADTSet μέσω BST που είδαμε στις διαλέξεις, οι λειτουργίες set_first, set_last, set_next, set_previous έχουν όλες πολυπλοκότητα $O(h)$ καθώς πρέπει να διασχίσουν ένα μονοπάτι από τη ρίζα προς τα φύλλα. Αυτό σημαίνει ότι η πλήρης διατεταγμένη διάσχιση του δέντρου (με το συνηθισμένο for loop) θα είναι $Ο(n\cdot h)$, το οποίο μπορεί να μην είναι επιθυμητό σε κάποιες εφαρμογές.

Μία σχετικά απλή λύση για να υλοποιήσουμε όλες τις παραπάνω συναρτήσεις σε χρόνο $Ο(1)$ είναι, πέρα από τη δενδρική δομή, να διατηρούμε ταυτόχρονα τους κόμβους σε μια bidirectional λίστα, με διατεταγμένη σειρά. Αν έχουμε τη λίστα η υλοποίηση των συναρτήσεων είναι πολύ απλή, η μόνη δυσκολία έγκειται στην ανανέωση της λίστας σε κάθε insert και remove.

Τροποποιήστε την υλοποίηση του ADTSet μέσω BST (modules/UsingBinarySearchTree/ADTSet.c) ώστε οι συναρτήσεις διάσχισης να είναι σταθερού χρόνου. Η υλοποίηση θα πρέπει να περνάει τα υπάρχοντα tests (tests/ADTSet_test.c) χωρίς leaks.

Σημειώσεις:

Πριν ξεκινήσετε τις αλλαγές, μελετήστε προσεκτικά την υπάρχουσα υλοποίηση και βεβαιωθείτε ότι κατανοείτε πλήρως πώς ο κώδικας σχετίζεται με τους αλγορίθμους που είδαμε στις διαλέξεις.
Για την αμφίδρομη λίστα έχετε 2 επιλογές:
1. Χρήση του έτοιμου ADTBList από την άσκηση 2. Στη περίπτωση αυτή μπορείτε μέσα σε κάθε SetNode να κρατάτε το αντίστοιχο BListNode της λίστας.
2. Υλοποίηση της διπλά συνδεδεμένης λίστας μέσα στο BST, δηλαδή προσθήκη δεικτών prev,next σε κάθε κόμβο.
Επιλέξτε ό,τι προτιμάτε.
Η ενημέρωση της λίστας σε κάθε διαγραφή ή εισαγωγή μπορεί να γίνει σε σταθερό χρόνο, χωρίς επιπλέον διάσχιση του δέντρου. Αν πάλι προτιμάτε να διασχίσετε το δέντρο μπορείτε να το κάνετε. Έτσι και αλλιώς η εισαγωγή και διαγραφή είναι $O(h)$, οπότε το να προσθέσετε άλλη μία $O(h)$ υπο-λειτουργία δεν αλλάζει την πολυπλοκότητα.
Όπως και στην άσκηση 4, είναι χρήσιμο να σχεδιάσετε στο χαρτί τη λογική της υλοποίησης, τους αλγορίθμους, κλπ, πριν ξεκινήσετε να γράφετε κώδικα, όπως κάνουμε και στις διαλέξεις.

Bonus (10%):

Υλοποιήστε και τους 2 τρόπους διαχείρισης της λίστας (ADTBList και εσωτερικά στο BST).
Προσθέστε μια συνάρτηση set_remove_node η οποία διαγράφει έναν κόμβο σε $O(1)$ (και tests για τη λειτουργία αυτή). Αυτό είναι δυνατόν από τη μία επειδή δίνεται ο κόμβος σαν όρισμα (δε χρειάζεται αναζήτηση), και αφετέρου λόγω της δυνατότητας εύρεσης του επόμενου/προηγούμενου στοιχείου σε σταθερό χρόνο. Πιθανόν όμως να χρειαστείτε και κάτι ακόμα…