Εργασία 2

Last updated on Feb 14, 2022

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

Η εργασία αυτή εξετάζει ένα πλήθος διαφορετικών δομών που επιτρέπουν random-access στα αποθηκευμένα στοιχεία, δηλαδή γρήγορη πρόσβαση σε κάθε στοιχείο με βάση τη θέση του.

Άσκηση 1 (20%)

Η υλοποίηση του ADT Vector που είδαμε στο μάθημα χρησιμοποιεί Dynamic Arrays. Είδαμε επίσης ότι είναι δυνατόν να υλοποιήσουμε έναν ADT χρησιμοποιώντας έναν άλλο (πχ υλοποιήσαμε τον ADT Stack χρησιμοποιώντας τον ADT List).

Στην άσκηση αυτή καλείστε να δημιουργήσετε μια εναλλακτική υλοποίηση του ADT Vector, χρησιμοποιώντας εσωτερικά τον ADT Map. Η βασική ιδέα είναι απλή: μέσω του Map θα αντιστοιχίσουμε κάθε θέση ενός στοιχείου στο αντίστοιχο στοιχείο. Πχ αν το Map περιέχει την αντιστοίχηση 3 => "foo" σημαίνει ότι το στοιχείο "foo" βρίσκεται στη θέση 3 του Vector που υλοποιούμε.

Μία κενή υλοποίηση υπάρχει στο αρχείο modules/UsingADTMap/ADTVector.c, εσείς καλείστε να συμπληρώσετε κατάλληλα τους τύπους και να υλοποιήσετε όλες τις συναρτήσεις. Όλες οι υλοποιήσεις είναι πολύ απλές (max 5-6 γραμμές κώδικα), εφόσον το Map κάνει τη βασική δουλειά.

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

  • είτε να κάνει compile το test με την original υλοποίηση μέσω Dynamic Array:
    make UsingDynamicArray_ADTVector_test
  • είτε να κάνει compile το ίδιο test με τη νέα υλοποίηση μέσω Map:
    make UsingADTMap_ADTVector_test (ρυθμισμένο να τρέχει με Ctrl-Shift-B)

Όλες οι λειτουργίες, εκτός της vector_find, θα πρέπει να είναι αποδοτικές (δεν πρέπει να διατρέχουν όλα τα στοιχεία του map). Η υλοποίησή σας θα πρέπει να περνάει με επιτυχία το test χωρίς leaks (καμία αλλαγή δεν επιτρέπεται στο test).

Τέλος, στο README.md αναφέρετε αν υπάρχει κάποια λειτουργία που έχει καλύτερη πολυπλοκότητα στη νέα υλοποίηση απ’ ότι στην κλασσική. Για την υλοποίηση του Map μπορείτε να υποθέσετε ότι όλες οι λειτουργίες εκτελούνται σε χρόνο $O(\log n)$ worst-case real-time.

Άσκηση 2 (20%)

Ο ADT Deque (double-ended queue, προφέρεται “deck”) είναι παρόμοιος με τον ADTVector, επιτρέποντας random-access σε όλα τα στοιχεία με βάση τη θέση τους, αλλά επιπλέον παρέχει:

  • εισαγωγή στοιχείων στην αρχή του deque (επιπλέον της εισαγωγής στο τέλος)
  • διαγραφή του πρώτου στοιχείου (επιπλέον της διαγραφής του τελευταίου)

Προσοχή: κατά την εισαγωγή ή διαγραφή στην αρχή του deque, τα στοιχεία φαινομενικά μετακινούνται, δηλαδή το στοιχείο στη θέση 3 θα βρεθεί στη θέση 4 μετά από μια εισαγωγή στην αρχή, και στη θέση 2 μετά από διαγραφή.

Οι λειτουργίες περιγράφονται στο include/ADTDeque.h στο repository της εργασίας. Είναι όλες όμοιες με τις αντίστοιχες του ADTVector.h με εξαίρεση τις deque_insert_first και deque_remove_first.

Υλοποιήστε τον τύπο αυτό χρησιμοποιώντας εσωτερικά τον ADT Map, ουσιαστικά δηλαδή προσαρμόζοντας την υλοποίηση του ADT Vector από την Άσκηση 1. Η υλοποίηση πρέπει να βρίσκεται στο modules/UsingADTMap/ADTDeque.c.

Προσοχή: η υλοποίηση πρέπει να είναι αποδοτική, καμία λειτουργία εκτός της deque_find δεν πρέπει να διατρέχει όλα τα στοιχεία του deque. Πχ οι deque_insert_first και deque_remove_first δεν πρέπει να τροποποιούν όλα τα περιεχόμενα του Map, παρόλο που φαινομενικά οι θέσεις των στοιχείων “αλλάζουν”. Σκεφτείτε πώς μπορεί να γίνει αυτό, η λύση είναι απλή.

Επίσης, στο αρχείο tests/ADTDeque_test.c υπάρχει ένα ελλιπές test για τον ADT Deque, ουσιαστικά περιέχει copy-paste τα αντίστοιχα tests του ADTVector_test.c. Εσείς πρέπει να προσθέσετε tests για τις deque_insert_first και deque_remove_first (ως συνήθως, δεν χρειάζονται εξαντλητικά tests, αλλά πρέπει οι βασικές λειτουργίες να ελέγχονται). Η υλοποίησή σας θα πρέπει να περνάει όλα τα tests χωρίς leaks.

Άσκηση 3 (20%)

Δημιουργήστε μια νέα υλοποίηση του ADT Deque (Άσκηση 2) μέσω Dynamic Array. H λογική είναι παρόμοια με την υλοποίηση του ADT Vector που είδαμε στο μάθημα: το array θα πρέπει να γίνεται resize όταν γεμίσει, διπλασιάζοντας κάθε φορά το μέγεθός του.

Η βασική διαφορά έγκειται στον τρόπο που χειριζόμαστε την deque_insert_first (και deque_remove_first). Κατά την προσθήκη ενός στοιχείου στην αρχή δεν θέλουμε:

  • ούτε να μετακινήσουμε όλα τα στοιχεία (θα ήταν πολύ αργό)
  • ούτε να κάνουμε resize αν υπάρχει έστω και μία κενή θέση στο array.

Η λύση είναι το array να είναι “κυκλικό”, δηλαδή η πρώτη θέση του array να θεωρείται ότι είναι “επόμενη” της τελευταίας θέσης και αντίστροφα. Με τον τρόπο αυτό μπορούμε να κάνουμε προσθήκες και διαγραφές και στα δύο άκρα, και να κάνουμε resize μόνο όταν γεμίσουν όλα τα στοιχεία του πίνακα. Ως συνήθως, μερικά διαγράμματα στο χαρτί θα σας βοηθήσουν να βρείτε τον ακριβή αλγόριθμο για κάθε λειτουργία.

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

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

Άσκηση 4 (20%)

Στην υλοποίηση του ADT Vector μέσω Dynamic Array που είδαμε στο μάθημα, η πολυπλοκότητα της vector_insert_last είναι $O(1)$ amortized-time. Το “amortized” είναι σημαντικό, γιατί παρόλο που τα resizes είναι σπάνια, όταν συμβαίνουν η συγκεκριμένη εισαγωγή έχει αναγκαστικά γραμμική πολυπλοκότητα, εφόσον πρέπει να αντιγραφούν όλα τα στοιχεία.

Μπορεί να φαίνεται αδύνατο να αποφύγουμε αυτό το πρόβλημα, αλλά στην πραγματικότητα ένα σχετικά απλό trick μας επιτρέπει να πετύχουμε εισαγωγή σε σταθερό real-time χρόνο. Δηλαδή κανένα απολύτως insert να μην καθυστερεί, ούτε καν όταν συμβαίνει resize!

Η βασική ιδέα είναι η ακόλουθη:

  • Όταν γεμίσει ο πίνακας, δημιουργούμε έναν νέο με διπλάσιο μέγεθος, όπως και στην κλασσική υλοποίηση.
  • Όμως δεν αντιγράφουμε αμέσως τα στοιχεία του παλιού array στο νέο (αφού αυτό ακριβώς οδηγεί στη γραμμική real-time πολυπλοκότητα).
  • Αντιθέτως αντιγράφουμε μόνο ένα παλιό στοιχείο στον νέο πίνακα, και προσθέτουμε βέβαια και το νέο στοιχείο που κάναμε insert (και οδήγησε στο resize). Οπότε η λειτουργία αυτή είναι σταθερού χρόνου.
  • Αυτό σημαίνει ότι πρέπει να κρατήσουμε και τον παλιό πίνακα, αφού πολλά στοιχεία είναι ακόμα εκεί. Και φυσικά οι λειτουργίες vector_get_at και vector_set_at θα πρέπει να αναζητούν το στοιχείο είτε στον παλιό είτε στον νέο πίνακα, ανάλογα με τη θέση του στοιχείου.
  • Σε κάθε μελλοντικό insert, πέρα από το νέο στοιχείο που προσθέτουμε, αντιγράφουμε και ένα ακόμα από τα παλιά στον νέο πίνακα. Εφόσον αντιγράφουμε σταθερό αριθμό στοιχείων, η πολυπλοκότητα παραμένει σταθερή!
  • Όταν ο νέος πίνακας γεμίσει, σημαίνει ότι έχουμε κάνει αρκετά inserts ώστε όλα τα παλιά στοιχεία να έχουν αντιγραφεί στον νέο πίνακα. Οπότε ο παλιός πίνακας μπορεί να ελευθερωθεί (και βέβαια να δημιουργήσουμε έναν ακόμα μεγαλύτερο, αφού ο προηγούμενος γέμισε, συνεχίζοντας την ίδια διαδικασία).
  • Οι διαγραφές μπορούν να προσαρμοστούν ανάλογα (σκεφτείτε τον τρόπο).

Δημιουργήστε μια υλοποίηση modules/UsingRealTimeDynamicArray/ADTVector.c που να προσφέρει εισαγωγή και εξαγωγή σε real-time σταθερό χρόνο, με βάση την παραπάνω λογική.

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

Bonus (5%):

Τροποποιήστε τον ADT Vector ώστε να παρέχει τον αριθμό βημάτων που πραγματοποίησε η συνάρτηση vector_* που κλήθηκε τελευταία. Στη συνέχεια, χρησιμοποιήστε την υλοποίηση αυτή για να δημιουργήσετε γραφικές παραστάσεις που να δείχνουν τον αριθμό βημάτων που εκτελούν οι vector_insert_last και vector_remove_last στην κλασσική και τη νέα υλοποίηση, σαν συνάρτηση του $n$ (το $n$ θα είναι στον άξονα x, και ο αριθμός βημάτων στην άξονα y). Μπορείτε να δείτε την Άσκηση 1 της περσινής εργασίας για να πάρετε ιδέες.

Bonus (10%):

Προσαρμόστε την υλοποίηση του ADT Deque της Άσκησης 3 ώστε να παρέχει εισαγωγή και εξαγωγή σε σταθερό real-time χρόνο (ίδια λογική με την Άσκηση 4).

Άσκηση 5 (20%)

Στην κλασσική του εκδοχή ο ADT Set δεν παρέχει random-access πρόσβαση στα στοιχεία του set (πρόσβαση δηλαδή με βάση τη θέση τους). Είναι όμως χρήσιμο για πολλές εφαρμογές να μπορούμε να έχουμε πρόσβαση στο στοιχείο στη θέση pos, όπου οι “θέσεις” ακολουθούν τη διάταξη των στοιχείων στο set. Δηλαδή το στοιχείο στη θέση πχ 2 είναι το τρίτο σε διάταξη (πηγαίνοντας από το μικρότερο στο μεγαλύτερο, πάντα αναφορικά με την compare που δίνεται).

Προσθέστε στον ADTSet.h δύο λειτουργίες set_get_at και set_set_at, παρόμοιες με τις αντίστοιχες του ADT Vector. Στη συνέχεια επεκτείνετε την υλοποίηση modules/UsingBinarySearchTree/ADTSet.c, προσθέτοντας τις δύο αυτές λειτουργίες. Η υλοποίηση θα πρέπει να είναι αποδοτική, με πολυπλοκότητα το πολύ $O(h)$ (μια μη αποδοτική υλοποίηση θα ληφθεί υπόψη αλλά με penalty). Είστε ελεύθεροι να τροποποιήσετε την υπάρχουσα υλοποίηση όπως θέλετε (πχ να αποθηκεύετε επιπλέον πληροφορίες που χρειάζεστε), υπό τον όρο ότι η πολυπλοκότητα των λειτουργιών δεν επιτρέπεται να χειροτερέψει.

Τέλος προσθέστε tests για τις set_get_at, set_set_at στο tests/ADTSet_test.c. Η υλοποίησή σας θα πρέπει να περνάει τα tests (τόσο τα νέα, όσο και τα υπάρχοντα) χωρίς leaks.

Σημείωση: η set_set_at(set, pos, value) θα πρέπει να αντικαθιστά στο στοιχείο στη θέση pos με value. Εφόσον οι θέσεις ακολουθούν τη διάταξη, το νέο στοιχείο value θα πρέπει να μπει στη σωστή του θέση με βάση τη διάταξη, η οποία πιθανόν να είναι διαφορετική από την pos.

Bonus (10%):

Επαναλάβετε την ίδια άσκηση για την υλοποίηση modules/UsingAVL/ADTSet.c του ADT Set, όπου οι συναρτήσεις θα πρέπει να έχουν πολυπλοκότητα $O(\log n)$.