Εργασία 3

Last updated on Mar 23, 2021

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

Άσκηση 1 (30%)

Η υλοποίηση του ADT Map μέσω πίνακα κατακερματισμού που υπάρχει στο modules/UsingHashTable/ADTMap.c χρησιμοποιεί open addressing. Τροποποιήστε την ώστε να χρησιμοποιεί separate chaining. Για τις λίστες μπορείτε να χρησιμοποιήσετε είτε τον ADT List, είτε δική σας υλοποίηση.

Η υλοποίησή σας θα πρέπει να περνάει το αντίστοιχο test (tests/ADTMap_test.c) χωρίς leaks.

Άσκηση 2 (30%)

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

Οποιαδήποτε δεδομένα μπορούν να χρησιμοποιηθούν ως κορυφές (οι κορυφές δηλαδή είναι τύπου Pointer). Η υλοποίηση πρέπει να χρησιμοποιεί λίστες γειτνίασης, και η αντιστοίχηση μιας κορυφής με την αντίστοιχη λίστα θα πρέπει να γίνεται με την υλοποίηση του ADT Map από την Άσκηση 1. Κάθε κορυφή είναι μοναδική με βάση τη συνάρτηση compare (αν ο χρήστης θέλει να εισάγει πολλές φορές την ίδια κορυφή μπορεί να χρησιμοποιήσει τις μεθόδους που είχαμε δει για εισαγωγή διπλών στοιχείων σε ένα Set). Υπάρχει ήδη ένα κενό αρχείο modules/UsingAdjacencyLists/ADTGraph.c προς υλοποίηση.

Η υλοποίηση της graph_shortest_path θα πρέπει να γίνει με τον αλγόριθμο Dijkstra. Μια πλήρης λύση απαιτεί τη χρήση ουράς προτεραιότητας στον αλγόριθμο Dijkstra (λύσεις χωρίς ουρά προτεραιότητας θα γίνουν δεκτές με κάποιο penalty).

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

  • Χρήση ουράς προτεραιότητας που επιτρέπει αλλαγές (ή διαγραφή), πχ αυτή που έχετε υλοποιήσει στην Εργασία 2.
  • Αντί να αλλάξετε την προτεραιότητα, μπορείτε να προσθέσετε ξανά το ίδιο στοιχείο στην ουρά με νέα προτεραιότητα (αλλά προσοχή να αγνοείτε τα “διπλά” αυτά στοιχεία κατά την εξαγωγή).

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

Άσκηση 3 (40%)

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

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

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

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

  • Η dm_get_records (επιστρέφει εγγραφές που πληρούν συγκεκριμένα κριτήρια) επιστρέφει πολλές εγγραφές οπότε ο χρόνος εκτέλεσής της αναγκαστικά εξαρτάται από τον αριθμό $m$ των εγγραφών που επιστρέφονται. Πάρα ταύτα, για σταθερό $m$ θα πρέπει να παραμένει $O(\log n)$. Δηλαδή, αν πχ αυξάνονται οι εγγραφές και κάθε φορά καλούμε την dm_get_records με κριτήρια που επιστρέφουν ακριβώς $m=10$ εγγραφές, ο χρόνος εκτέλεσης θα πρέπει να αυξάνεται λογαριθμικά ως προς το $n$.

  • Η dm_count_records (επιστρέφει τον αριθμο $m$ των εγγραφών που πληρούν συγκεκριμένα κριτήρια) θα πρέπει να τρέχει σε χρόνο καλύτερο από $O(m)$ (λύσεις $O(m)$ δεν είναι αποδεκτές). Αυτό πχ απαγορεύει το να καλέσουμε απλά την dm_get_records και να μετρήσουμε πόσες εγγραφές επέστρεψε, χρειαζόμαστε γρηγορότερη λύση.

    Από την άλλη, ο χρόνος εκτέλεσης μπορεί να εξαρτάται από τον αριθμό των διαφορετικών τιμών country, disease, date που πληρούν τα κριτήρια. Ο αριθμός αυτός είναι $m$ σε worst-case, αλλά στην πράξη θεωρούμε ότι παραμένει μικρός. Πχ μπορεί να έχουμε $m=10^6$ εγγραφές, αλλά μόλις 100 διαφορετικούς συνδυασμούς country, disease, date.

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

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

Bonus (10%): Το παίρνετε αν η dm_count_records στην υλοποίησή σας τρέχει σε χρόνο $O(\log n)$ χωρίς να εξαρτάται από κανέναν άλλο παράγοντα (πχ δεν εξαρτάται από τον αριθμό των διαφορετικών συνδυασμών country, disease, date).

Bonus (10%): Τα tests που δίνονται είναι αρκετά απλά. Υλοποιήστε νέα tests προσπαθώντας να καλύψετε όσο το δυνατόν καλύτερα τις διάφορες λειτουργίες. Τα tests σας θα δοκιμαστούν σε όλες τις εργασίες που παραδίδονται. Το bonus το παίρνετε αν

  • το test είναι σωστό
  • ανακαλύψει κάποιο bug σε κάποια εργασία που δεν το ανακαλύπτει το test που σας δίνεται!

Το test θα πρέπει αν εισάγει το πολύ 1000 εγγραφές (για να τρέξει γρήγορα).

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

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

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