Εργασία 2

Last updated on Feb 20, 2023
  • Ανακοινώθηκε: 27/4/2022
  • Προθεσμία παράδοσης: 22/5/2022 29/5/2022 23:59
  • 16% του συνολικού βαθμού στο μάθημα
  • Link εγγραφής: https://classroom.github.com/a/w6lvQypI
  • Repository: https://github.com/chatziko-k08/2022-project-2-<github-username>

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

Άσκηση 1 (20%)

Η υλοποίηση του ADT Queue που είδαμε στο μάθημα χρησιμοποιεί τον ADT List. Στην άσκηση αυτή καλείστε να δημιουργήσετε μια εναλλακτική υλοποίηση του ADT Queue, χρησιμοποιώντας εσωτερικά τον ADT Stack.

Η βασική ιδέα είναι απλή: τα δεδομένα τα αποθηκεύουμε σε μια στοίβα, οπότε η queue_insert_back απλά προσθέτει το στοιχείο στη στοίβα. Η queue_remove_front από την άλλη θέλει περισσότερη δουλειά, αφού το στοιχείο που θέλουμε να αφαιρέσουμε βρίσκεται στη “βάση” της στοίβας (όχι στην κορυφή). Πρέπει λοιπόν να αφαιρέσουμε όλα τα στοιχεία από τη στοίβα, αποθηκεύοντάς τα προσωρινά σε οποιαδήποτε δομή θέλετε (πχ σε ένα vector), και να τα προσθέσουμε και πάλι στη στοίβα (εκτός φυσικά από αυτό που αφαιρείται).

Μία κενή υλοποίηση υπάρχει στο αρχείο modules/UsingADTStack/ADTQueue.c, εσείς καλείστε να συμπληρώσετε κατάλληλα τους τύπους και να υλοποιήσετε όλες τις συναρτήσεις. Όλες οι υλοποιήσεις είναι πολύ απλές (max 10 γραμμές κώδικα), εφόσον ο ADT Stack κάνει τη βασική δουλειά.

Στο αρχείο tests/ADTQueue_test.c υπάρχει το test του ADT Queue από το lecture-code. Επίσης το tests/Makefile είναι ρυθμισμένο ώστε:

  • είτε να κάνει compile το test με την original υλοποίηση μέσω ADT List:
    make UsingADTList_ADTQueue_test
  • είτε να κάνει compile το ίδιο test με τη νέα υλοποίηση μέσω ADT Stack:
    make UsingADTStack_ADTQueue_test (ρυθμισμένο να τρέχει με Ctrl-Shift-B)

Όλες οι λειτουργίες, εκτός της queue_remove_front, θα πρέπει να είναι αποδοτικές (δεν πρέπει να διατρέχουν όλα τα στοιχεία της στοίβας). Για την queue_front, θα πρέπει να σκεφτείτε πώς μπορεί να γίνει αυτό. Η υλοποίησή σας θα πρέπει να περνάει με επιτυχία το test χωρίς leaks (καμία αλλαγή δεν επιτρέπεται στο test). Επίσης θα πρέπει να καλείται σωστά η destroy function που δέχεται ως παράμετρο η queue_create.

Τέλος, στο README.md αναφέρετε την πολυπλοκότητα της κάθε λειτουργίας (υποθέτωντας ότι όλες οι λειτουργίες του ADT Stack εκτελούνται σε χρόνο $O(1)$).

Άσκηση 2 (20%)

Η υλοποίηση ουράς μέσω στοίβας της Άσκησης 1 έχει το μειονέκτημα ότι η queue_remove_front είναι μη αποδοτική. Υπάρχει όμως καλύτερος τρόπος, αν αντί για μία στοίβα, αποθηκεύουμε τα δεδομένα μας σε δύο στοίβες!

  • Στην πρώτη στοίβα εισέρχονται τα δεδομένα (όπως στην Άσκηση 1)
  • Η δεύτερη στοίβα αρχικά είναι κενή. Οταν κληθεί για πρώτη φορά η queue_remove_front, τότε εξάγουμε όλα τα δεδομένα από την πρώτη στοίβα και τα προσθέτουμε στη δεύτερη. Αυτό έχει ως αποτέλεσμα να αντιστραφεί η σειρά τους, οπότε το στοιχείο προς αφαίρεση βρίσκεται πλέον στην κεφαλή της δεύτερης στοίβας. Οσο η δεύτερη στοίβα περιέχει στοιχεία, η αφαίρεση είναι εύκολη, μέχρι να αδειάσει οπότε και επαναλαμβάνουμε την ίδια διαδικασία.

Ως συνήθως, μερικά διαγράμματα στο χαρτί θα σας βοηθήσουν να βρείτε τον ακριβή αλγόριθμο για κάθε λειτουργία.

Η υλοποίηση πρέπει να βρίσκεται στο modules/UsingADTStack/ADTQueue_alt.c. Επίσης πρέπει να τροποποιήσετε το tests/Makefile ώστε να κάνει compile το tests/ADTQueue_test.c με τις δύο υλοποιήσεις των ασκήσεων 1 και 2 (δεν επιτρέπεται να έχετε διαφορετικό test για κάθε υλοποίηση). Η υλοποίηση σας θα πρέπει να είναι αποδοτική και να περνάει όλα τα tests χωρίς leaks.

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

Άσκηση 3 (20%)

Στο ADTQueue module, και στις 3 υλοποιήσεις του (τις δύο που υλοποιήσατε, και την original υλοποίηση μέσω ADT List), προσθέστε την ακόλουθη λειτουργία:

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

int queue_steps(Queue queue);

Πχ, αν η τελευταία συνάρτηση που κλήθηκε ήταν η queue_insert_back στην Άσκηση 2, και η δεύτερη στοίβα ήταν γεμάτη, τότε η queue_steps θα πρέπει να επιστρέψει 1. Ως συνήθως, ως “βήμα” θεωρούμε οποιοδήποτε αριθμό εντολών σταθερού χρόνου, δηλαδή που ο χρόνος εκτέλεσής τους δεν εξαρτάται από τον αριθμό στοιχείων $n$ της ουράς. Οι λειτουργίες των ADTList και ADTStack που χρησιμοποιούνται εσωτερικά στις υλοποιήσεις θεωρούμε ότι εκτελούνται σε $O(1)$.

Στη συνέχεια, φτιάξτε ένα πρόγραμμα programs/queue_benchmark/queue_benchmark.c το οποίο θα εκτελεί διαδοχικά $9000$ inserts και removes, σε αναλογία 2 προς 1. Δηλαδή το πρόγραμμα θα κάνει 2 inserts, 1 remove, άλλα 2 inserts, άλλο ένα remove, κλπ, μέχρι συνολικά να εκτελεστούν 9000 λειτουργίες.

Το πρόγραμμα θα πρέπει επίσης να υπολογίσει τον αριθμό βημάτων που εκτέλεσε η υλοποίηση της ουράς, στις ακόλουθες περιπτώσεις:

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

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

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

Θα πρέπει να φτιάξετε ένα Makefile το οποίο να κάνει compile το πρόγραμμα αυτό (χωρίς αλλαγές) με τις 3 υλοποιήσεις της ουράς, παράγοτας 3 εκτελέσιμα (queue_benchmark_using_list, queue_benchmark_using_stack και queue_benchmark_using_stack_alt).

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

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

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

Άσκηση 4 (20%)

Στο ADTSet module, προσθέστε μια λειτουργία:

Set set_create_from_sorted_values(CompareFunc compare, DestroyFunc destroy_value, Vector values);

Η συνάρτηση αυτή δημιουργεί ένα set, το οποίο περιέχει τα στοιχεία του vector values, τα οποία πρέπει να δίνονται ταξινομημένα σε αύξουσα σειρά. Τροποποιήστε την υλοποίηση modules/UsingBinarySearchTree/ADTSet.c, προσθέτωντας τη λειτουργία αυτή.

Στη συνέχεια, τροποιήστε το test tests/ADTSet_test.c ώστε να ελέγχει τη νέα λειτουργία. Πέρα από τη δημιουργία ενός set μέσω της set_create_from_sorted_values, θα πρέπει επίσης να ελέγχεται ότι σε ένα τέτοιο set λειτουργούν σωστά όλες οι λειτουργίες (insert, remove, κλπ).

Η υλοποίησή σας θα πρέπει να έχει γραμμική πολυπλοκότητα, να παράγει ένα ισοζυγισμένο δέντρο, και να περνάει τα tests χωρίς leaks.

Bonus (5%):

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

Bonus (5%):

Επαναλάβετε την ίδια άσκηση (υλοποίηση της set_create_from_sorted_values) για την υλοποίηση του ADT Set μέσω B-Trees.

Άσκηση 5 (20%)

Στο μάθημα είδαμε ότι υπάρχουν πολλοί διαφορετικοί τύποι ισοζυγισμένων (balanced) δέντρων, δηλαδή δέντρων όπου το ύψος τους είναι λογαριθμικό ως προς τον αριθμό των στοιχείων (πχ complete, AVL, B-Trees). Τα Lazy Binary Search Trees (LazyBST) είναι ένας εναλλακτικός τύπος ισοζυγισμένου δέντρου, όπου το rebalancing γίνεται με “τεμπέλικό” τρόπο. Ολες οι λειτουργίες γίνονται ακριβώς όπως ένα απλό BST, χωρίς να μας απασχολεί να διατηρήσουμε το δέντρο ισυζυγισμένο. Αυτό, φυσικά, έχει ως αποτέλεσμα το δέντρο να αρχίσει να “γέρνει”, και σε κάποιο κόμβο, το αριστερό υποδέντρο να αποκτήσει μέγεθος (αριθμό στοιχείων) διπλάσιο από το δεξί (ή αντίστροφα).

Στην περίπτωση αυτή, πραγματοποιούμε ανακατασκευή ολόκληρου του υποδέντρου με ρίζα τον κόμβο αυτό. Μεταφέρουμε όλα τα στοιχεία σε ένα ταξινομημένο vector, και στη συνέχεια φτιάχνουμε ένα νέο (ισοζυγισμένο) υποδέντρο (όπως κάναμε στην Άσκηση 4). Παρόλο που η ανακατασκευή αυτή έχει προφανώς γραμμικό κόστος, μπορούμε να δείξουμε ότι γίνεται αρκετά σπάνια, ώστε η amortized πολυπλοκότητα όλων των λειτουργιών να παραμένει $O(\log n)$. Επιπλέον, για να αποφύγουμε την ανακατασκευή μικρών δέντρων, θα έχουμε σαν περιορισμό να ανακατασκευάζουμε μόνο υποδέντρα με ύψος από 4 και άνω.

Δημιουργήστε μια υλοποίηση modules/UsingLazyBST/ADTSet.c του ADT Set, χρησιμοποιώντας τη δομή αυτή. Η υλοποίηση πρέπει να περιλαμβάνει και τη συνάρτηση set_create_from_sorted_values από την Άσκηση 4, και ο κώδικας της συνάρτησης αυτής καθώς και της ανακατασκευής του δέντρου θα πρέπει να είναι κοινός. Για να ισχύσει το amortized $O(\log n)$ θα πρέπει όλες οι λειτουργίες να παραμείνουν $O(h)$ (όπως στα BST) και η ανακατασκευή του δέντρου να γίνεται σε χρόνο $O(n)$.

Προσοχή: η ανακατασκευή του δέντρου θα πρέπει να γίνεται στο “ψηλότερο” unbalanced σημείο. Μπορεί δηλαδή δύο κόμβοι να χρειαστούν ανακατασκευή, και ο ένας να είναι πρόγονος του άλλου. Θα πρέπει στην περίπτωση αυτή να γίνει μία μόνο ανακατασκευή (στον πρόγονο).

Bonus (5%):

Επαληθεύσετε πειραματικά (με γραφικές παραστάσεις), ότι οι λειτουργίες του LazyBST έχουν όντως amortized πολυπλοκότητα $O(\log n)$.

Bonus (10%):

Η προσθήκη των στοιχείων του υποδέντρου σε ένα vector θα μπορούσε πολύ εύκολα να επιτευχθεί διασχίζοντας το υποδέντρο μέσω της set_next. Τι πολυπλοκότητα όμως θα είχε αυτό; Μπορείτε να τροποποιήσετε την set_next ώστε η κομψή αυτή λύση να είναι και αποδοτική;