Εργασία 3

Last updated on Feb 14, 2022

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

Άσκηση 1 (30%)

Η υλοποίηση του ADT Map μέσω πίνακα κατακερματισμού που υπάρχει στο modules/UsingHashTable/ADTMap.c χρησιμοποιεί open addressing. Στις διαλέξεις είδαμε επίσης την εναλλακτική επιλογή του separate chaining (που έχει την ίδια πολυπλοκότητα).

Μια απλή παραλλαγή του separate chaining είναι να εισάγουμε τα στοιχεία κάθε κάδου σε ένα ADT Set, αντί για μία λίστα. Κατά τα άλλα οι λειτουργίες υλοποιούνται όπως ακριβώς στο separate chaining.

Τροποποιήστε την υπάρχουσα υλοποίηση ώστε να χρησιμοποιεί την παραπάνω παραλλαγή του separate chaining. Μπορείτε να χρησιμοποιήσετε οποιαδήποτε υλοποίηση του ADT Set επιθυμείτε από το lecture-code. Η υλοποίησή σας θα πρέπει να περνάει το αντίστοιχο test (tests/ADTMap_test.c) χωρίς leaks.

Στο README.md, περιγράψτε την πολυπλοκότητα των search και insert στην υλοποίηση αυτή, για όλους τους συνδυασμούς worst/average-case και real/amortized-time, και συγκρίνετέ τες με αυτή της κλασσικής υλοποίησης separate chaining (μέσω συνδεδεμένων λιστών). Οι λειτουργίες του ADT Set μπορείτε να υποθέσετε ότι έχουν λογαριθμική πολυπλοκότητα.

Άσκηση 2 (35%)

Υλοποιήστε τον ADT Graph, έναν μη κατευθυνόμενο γράφο με βάρη. Οι λειτουργίες του περιγράφονται στο include/ADTGraph.h.

Οποιαδήποτε δεδομένα μπορούν να χρησιμοποιηθούν ως κορυφές (οι κορυφές δηλαδή είναι τύπου Pointer), αλλά κάθε κορυφή είναι μοναδική με βάση τη συνάρτηση compare. Η υλοποίηση πρέπει να χρησιμοποιεί μια παραλλαγή του πίνακα γειτνίασης, όπου αντί για πίνακα θα χρησιμοποιήσετε τον ADT Map. Το Map θα αντιστοιχεί:

Ζευγάρι κορυφών (GraphVertexPair)  =>  βάρος της αντίστοιχης ακμής (int)

Ο τύπος GraphVertexPair ορίζεται στο ADTGraph.h. Οι κορυφές που δεν ενώνονται με μία ακμή δεν θα περιέχονται στο Map (ή εναλλακτικά μπορούν να περιέχονται με βάρος INT_MAX). Υπάρχει ήδη ένα κενό αρχείο modules/UsingAdjacencyMap/ADTGraph.c προς υλοποίηση.

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

Για τον έλεγχο της υλοποίησης δημιουργήστε κατάλληλο test tests/ADTGraph_test.c (δε χρειάζεται συνάρτηση main).

Bonus (10%): προσθέστε μια συνάρτηση Map graph_shortest_path_nexts(Graph graph), όπου για κάθε ζευγάρι v1,v2, αντί για το μήκος του συντομότερου μονοπατιού, θα επιστρέφει τον επόμενο κόμβο του v1, στο συντομότερο μονοπάτι ανάμεσα στα v1 και v2. Δηλαδή αν το μονοπάτι είναι v1 -> a -> b -> c -> v2, τότε στο Map θα υπάρχει η αντιστοίχηση (v1,v2) => a (που σημαίνει: για να πας από το v1 στο v2, ξεκίνα από το a).

Αυτό μπορεί να γίνει με μια απλή παραλλαγή του αλγόριθμου Floyd-Warshall. Από το Map αυτό, μπορούμε αν θέλουμε να κατασκευάσουμε εύκολα το πλήρες μονοπάτι ανάμεσα σε οποιεσδήποτε κορυφές. Στο παραπάνω παράδειγμα, είναι σαφές ότι στο Map θα υπάρχει και η αντιστοίχηση (a,v2) => b, αφού το συντομότερο μονοπάτι από το a στο v2 αναγκαστικά θα είναι το a -> b -> c -> v2, και επίσης (b,v2) => c, κλπ.

Άσκηση 3 (35%)

Υλοποιήστε ένα module MyStudies.h το οποίο θα επιτρέπει την αποθήκευση στοιχείων για φοιτητές και την εξαγωγή στατιστικών για αυτούς. Η περιγραφή των λειτουργιών υπάρχει στο include/MyStudies.h (διαβάστε το προσεκτικά!).

Για την υλοποίησή σας μπορείτε να δημιουργήσετε οποιεσδήποτε δομές δεδομένων επιθυμείτε (θα χρειαστείτε παραπάνω από μία), και να χρησιμοποιήσετε όλους τους ADTs και τις αντίστοιχες υλοποιήσεις που είδαμε στο μάθημα (αντιγράψτε ελεύθερα ό,τι θέλετε από το lecture-code).

Μοναδικοί κανόνες:

  • Όλες οι λειτουργίες (insert/remove/queries) θα πρέπει να εκτελούνται σε χρόνο το πολύ $Ο(\log n)$ όπου $n$ ο συνολικός αριθμός εγγραφών στο σύστημα.

  • Η ms_top_by_year(year, number) (και παρομοίως για την ms_bottom_by_year) επιστρέφει number εγγραφές οπότε ο χρόνος εκτέλεσής της αναγκαστικά εξαρτάται από το number. Πάρα ταύτα, για σταθερό number θα πρέπει να παραμένει $O(\log n)$. Δηλαδή, αν πχ αυξάνονται οι εγγραφές και κάθε φορά καλούμε τις συναρτήσεις με το ίδιο number, ο χρόνος εκτέλεσης θα πρέπει να αυξάνεται λογαριθμικά ως προς το $n$.

  • Ο χρόνος εκτέλεσης της ms_average_by_year θα πρέπει να εξαρτάται (το πολύ λογαριθμικά) από τον αριθμό διαφορετικών ετών για τα οποία υπάρχουν φοιτητές, και όχι από τον αριθμό των φοιτητών. Παρομοίως, η ms_city_rank θα πρέπει να εξαρτάται μόνο από τον αριθμό των διαφορετικών πόλεων.

Στο tests/MyStudies_test.c υπάρχουν έτοιμα tests για το module, η υλοποίησή σας θα πρέπει να τα περνάει χωρίς leaks (τα tests είναι αρκετά απλά, μπορείτε φυσικά να προσθέσετε και δικά σας).

Στο README.md περιγράψτε σύντομα τις δομές που υλοποιήσατε και εξηγήστε την πολυπλοκότητα κάθε λειτουργίας.

Bonus (10%): Η υλοποίηση του ADT Map της Άσκησης 1 έχει κάποια πλεονεκτήματα σε σχέση με την “κλασσική” υλοποίηση από το lecture-code. Δημιουργήστε ένα test για το MyStudies.h module που να αναδεικνύει τα πλεονεκτήματα αυτά, δηλαδή να εκτελείται σημαντικά γρηγορότερα για την υλοποίηση της Άσκησης 1. Για το σκοπό αυτό θα πρέπει να φτιάξετε όχι μόνο πολλές εγγραφές, αλλά και κατάλληλα διαμορφωμένες ώστε η κλασσική υλοποίηση να έχει τη χειρότερη δυνατή συμπεριφορά.

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

Παρατηρήσεις

  1. Όπως πάντα, μπορείτε να συζητάτε ελεύθερα τους αλγορίθμους (αρκεί να μην ανταλλάσσετε κώδικα). Μη διστάσετε να σχεδιάσετε συνεργατικά τις δομές που θα χρησιμοποιήσετε, να τις συζητάτε στο piazza, κλπ.

  2. Η άσκηση αυτή περιλαμβάνει (αλλαγμένες) κάποιες από τις βασικές λειτουργίες της φετινής Εργασίας 1 του Κ22 Λειτουργικά Συστήματα (Τμήμα Περιττών). Θα διαπιστώσετε ότι, έχοντας υλοποιήσει με γενικό και οργανωμένο τρόπο τις διάφορες δομές που χρειάζεστε, μια τέτοια εργασία βγαίνει αρκετά εύκολα, καθώς όλη η πολυπλοκότητα των δομών κρύβεται πίσω από τα αντίστοιχα modules. Αν έχετε υλοποιήσει έστω και μερικώς την άσκηση αυτή, είστε πλήρως προετοιμασμένοι για ένα από τα πιο απαιτητικά προγραμματιστικά μαθήματα της σχολής!