Εργασία 2

Last updated on May 23, 2024
  • Ανακοινώθηκε: 18/5/2024
  • Προθεσμία παράδοσης: 7/6/2024 23:59
  • 16% του συνολικού βαθμού στο μάθημα
  • Link εγγραφής: https://classroom.github.com/a/v_-4qS33
  • Repository: https://github.com/chatziko-k08/2024-project-2-<github-username>

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

Στην εργασία αυτή καλείστε να υλοποιήσετε ενα module set_utils, το οποίο παρέχει χρήσιμες βοηθητικές συναρτήσεις για τον ADT Set. Θα φτιάξουμε δύο διοφορετικές υλοποιήσεις:

  • μία γενική η οποία θα πρέπει να δουλεύει για οποιαδήποτε υλοποίηση του ADT Set.
  • και μία ειδική για Binary Search Trees, η οποία θα παρέχει καλύτερη πολυπλοκότητα.

Προσοχή: όλες οι συναρτήσεις προς υλοποίηση σε όλες τις ασκήσεις είναι εξαιρετικά απλές, καμία δεν απαιτεί παραπάνω από 20-30 γραμμές κώδικα (συχνά και λιγότερο). Ο σκοπός της εργασίας είναι η κατανόηση των δομών, όχι η παραγωγή τεράστιου όγκου κώδικα.

Άσκηση 1 (20%)

Στο αρχείο modules/UsingADTSet/set_utils.c υπάρχει ο κορμός της γενικής υλοποίησης του set_utils. Η υλοποίηση αυτή θα πρέπει να δουλεύει για οποιοδήποτε ADT Set (πχ για Set βασισμένο σε BST ή BTree), χωρίς να γνωρίζει την ακριβή δομή υλοποίησης του Set.

Στο αρχείο αυτό, υλοποιήστε αρχικά τις παρακάτω λειτουργίες:

// Δημιουργεί και επιστρέφει ένα Set που περιέχει όλα τα στοιχεία του
// Vector vec, με διάταξη compare.
// (Διπλά στοιχεία αντιμετωπίζονται ως συνήθως, κάθε εισαγωγή
//  αφαιρεί το προηγούμενο από το set.)

Set set_from_vector(Vector vec, CompareFunc compare);

// Δημιουργεί και επιστρέφει ένα Vector που περιέχει όλα τα στοιχεία
// του set με τη σειρά διάταξης.

Vector set_to_vector(Set set);

Όλες οι συναρτήσεις έχουν εξαιρετικά απλή υλοποίηση, χρησομοποιώντας τις αντίστοιχες λειτουργίες του ADT Set.

Στο αρχείο tests/set_utils_test.c υπάρχει ο κορμός ενός test για το set_utils module. Το αντίστοιχο Makefile έχει ρυθμιστεί ώστε να παράγει 2 εκτελέσιμα που τεστάρουν τη γενική υλοποίηση:

  • UsingADTSet_BST_set_utils_test: test της γενικής υλοποίησης, χρησιμοποιώντας Set βασισμένο σε BST.
  • UsingADTSet_BTree_set_utils_test: test της γενικής υλοποίησης, χρησιμοποιώντας Set βασισμένο σε BTree.

Στο αρχείο tests/set_utils_test.c προσθέστε tests για τις δύο λειτουργίες που υλοποιήσατε. Όλα τα tests θα πρέπει να περνάνε χωρίς leaks και για τις δύο υλοποιήσεις του ADT Set.

Τέλος στο README.md αναφέρετε την πολυπλοκότητα κάθε λειτουργίας, η οποία εξαρτάται από την υλοποίηση του ADT Set.

Άσκηση 2 (20%)

Ολοκληρώστε τη γενική υλοποίηση στο modules/UsingADTSet/set_utils.c προσθέτωντας τις υπόλοιπες τρεις λειτουργίες:

// Καλεί τη συνάρτηση f(set, value) σε κάθε στοιχείο του set με τη σειρά
// διάταξης. Για απλότητα, θεωρούμε ότι η f δεν μεταβάλλει το set (δεν
// προσθέτει ή αφαιρεί στοιχεία).

void set_traverse(Set set, TraverseFunc f);

// Δημιουργεί και επιστρέφει ένα set που περιέχει τα στοιχεία και
// των δύο Sets set1, set2. Τα αρχικά sets δεν μεταβάλλονται.
// (Διπλά στοιχεία αντιμετωπίζονται ως συνήθως, κάθε εισαγωγή
//  αφαιρεί το προηγούμενο από το set.)
//
// Τα δύο Set οφείλουν να έχουν την ίδια διάταξη με τη συνάρτηση compare,
// αλλιώς η συμπεριφορά είναι μη ορισμένη.

Set set_merge(Set set1, Set set2, CompareFunc compare);

// Επιστρέφει την k-οστή τιμή του set με τη σειρά διάταξης, δηλαδή
// το μικρότερο στοιχείο αν k == 0, το δεύτερο μικρότερο αν k == 1,
// κλπ. Η συμπεριφορά είναι μη ορισμένη αν k >= set size.

Pointer set_find_k_smallest(Set set, int k);

Στη συνέχεια προσθέστε tests για τις λειτουργίες αυτές στο tests/set_utils_test.c. Όλα τα tests θα πρέπει να περνάνε χωρίς leaks και για τις δύο υλοποιήσεις του ADT Set.

Τέλος στο README.md αναφέρετε την πολυπλοκότητα κάθε λειτουργίας, η οποία εξαρτάται από την υλοποίηση του ADT Set.

Άσκηση 3 (20%)

Η υλοποίηση που φτιάξαμε έχει το πλεονέκτημα ότι δουλεύει για οποιοδήποτε ADT Set (πχ Set βασισμένο σε BST ή BTree). Αλλά έχει το μειονέκτημα ότι σε κάποιες περιπτώσεις είναι μη βέλτιστη (αφού δεν μπορεί να εκμεταλλευτεί τις ιδιαιτερότητες της κάθε δομής).

Στη συνέχεια θα δημιουργήσουμε μια ειδική υλοποίηση για Set βασισμένα σε BST, η οποία θα γνωρίζει την ακριβή δομή του Set και θα μπορεί να τη χρησιμοποιήσει ώστε να βελτιώσει την πολυπλοκότητα των λειτουργιών. Ο κορμός της υλοποίησης αυτής υπάρχει στο αρχείο modules/UsingBinarySearchTree/set_utils.c, στο οποίο υπάρχουν και οι δηλώσεις των structs του BST ώστε να μπορούμε να έχουμε πρόσβαση στη δομή του BST.

Υλοποιήστε αρχικά τις λειτουργίες set_to_vector και set_traverse, οι οποίες θα πρέπει να εκτελούνται σε χρόνο $O(n)$.

Το Makefile των tests έχει ρυθμιστεί ώστε να παράγει το εκτελέσιμο UsingBinarySearchTree_set_utils κάνοντας link το tests/set_utils_test.c με την ειδική υλοποίηση του set_utils. Ως συνήθως, όλες οι λειτουργίες θα πρέπει να περνάνε το test χωρίς leaks.

Άσκηση 4 (20%)

Συνεχίζοντας την ειδική υλοποίηση, προσθέστε τη λειτουργία set_from_vector, με τις παρακάτω σημαντικές ιδιότητες:

  • Η υλοποίηση θα πρέπει πάντα να παράγει balanced δέντρο (με ύψος $\log n$).
  • Η υλοποίηση θα πρέπει να τρέχει σε $O(n)$ όταν η πλειοψηφία των στοιχείων του Vector βρίσκονται ήδη στη σωστή διάταξη (αν όχι και πάλι θα πρέπει να δουλεύει, αλλά με χειρότερη πολυπλοκότητα).

Αυτό μπορεί να υλοποιηθεί ως εξής:

  • Αρχικά απομονώνουμε τα στοιχεία που βρίσκονται σε λάθος διάταξη, και τα ταξινομούμε (αυτό γίνεται γρήγορα αν ο αριθμός των στοιχείων είναι μικρός).
  • Ενσωμετώνουμε τα στοιχεία που ταξινομήσαμε στα υπόλοιπα που ήταν ήδη ταξινομημένα, ώστε να έχουμε όλα τα στοιχεία σε σωστή διάταξη.
  • Τέλος δημιουργούμε σε $Ο(n)$ ένα δέντρο από τα ταξινομημένα στοιχεία
    (σκεφτείτε τον αλγόριθμο, είναι απλός, και περιγράψτε τον στο README).

Τέλος υλοποιήστε τη set_merge η οποία θα πρέπει να τρέχει σε χρόνο $O(n1+n2)$, όπου $n1,n2$ ο αριθμός στοιχείων των set1, set2 αντίστοιχα.

Όλες οι λειτουργίες θα πρέπει να περνάνε το test χωρίς leaks.

Άσκηση 5 (20%)

Προσθέστε την τελευταία λειτουργία set_find_k_smallest της ειδικής υλοποίησης, η οποία θα πρέπει να εκτελείται σε $O(h)$, όπου $h$ το ύψος του δέντρου, χωρίς να εξαρτάται από το $k$.

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

Η υλοποίηση θα πρέπει να περνάει το test χωρίς leaks.

Bonus 1 (5%):

Το παίρνετε αν ο κώδικας της set_to_vector είναι πανομοιότυπος στη γενική και την ειδική υλοποίηση, και το ίδιο συμβαίνει και για τη set_merge (και φυσικά οι πολυπλοκότητες παραμένουν σωστές). Δηλαδή θέλουμε κώδικα ο οποίος να είναι ταυτόχρονα γενικός, και να δίνει βέλτιστη πολυπλοκότητα στην ειδική υλοποίηση.

Bonus 2 (10%):

Προσθέστε μια ειδική υλοποίηση modules/UsingBTree/set_utils.c του set_utils module για Set βασισμένα σε BTree. Προσαρμόστε το Makefile των tests ώστε να ελέγχει την υλοποίηση αυτή. Περιγράψτε τέλος στο README τις πολυπλοκότητες των λειτουργικών, που θα πρέπει να είναι βέλτιστες.

Tests και εκτέλεση στο github

Για να βεβαιωθείτε ότι ο κώδικας που παραδίδετε είναι σωστός, σε κάθε commit στο github γίνεται αυτόματα compilation και εκτελούνται τα tests. Τα αποτελέσματα του ελέγχου αυτού βρίσκονται στον παρακάτω σύνδεσμο:

https://github.com/chatziko-k08/2024-project-2-<github-username>/actions

Επιλέξτε το τελευταίο commit, μετά run-tests, και θα δείτε τα αποτελέσματα σε 6 ενότητες:

  • make UsingADTSet_BST_set_utils_test
  • Run UsingADTSet_BST_set_utils_test
  • make UsingADTSet_BTree_set_utils_test
  • Run UsingADTSet_BTree_set_utils_test
  • make UsingBinarySearchTree_set_utils_test
  • Run UsingBinarySearchTree_set_utils_test

Καμία άσκηση δε θα γίνει δεκτή αν ο αντίστοιχος κώδικας δεν κάνει compile. Επίσης, καμία άσκηση δε θα θεωρηθεί πλήρως σωστή αν δεν περνάνε σωστά τα tests.