Εργαστήριο 4 - Ουρές προτεραιότητας μέσω σωρού και ταξινομημένης λίστας

Last updated on May 10, 2023

Προθεσμία τελικής παράδοσης: Κυριακή 21/5, 23:59.

Καλώς ήρθατε στο τέταρτο εργαστήριο του μαθήματος Δομές Δεδομένων και Τεχνικές Προγραμματισμού. Για οποιαδήποτε απορία προκύψει κατα την διάρκεια του εργαστηρίου ρωτήστε τους βοηθούς, τον υπεύθυνο εργαστηρίου ή/και στείλτε στο piazza. Καλή αρχή!

1. Κατεβάστε τον κώδικα του εργαστηρίου

Όπως σε όλα τα εργαστήρια, ο κώδικας δίνεται μέσω Git. Για να τον κατεβάσετε:

  1. Επισκεφτείτε τον παρακάτω σύνδεσμο: https://classroom.github.com/a/5TEBzBV8
    • Δεν θα σας ζητηθεί ξανά αντιστοίχιση account (εφόσον το έχετε ήδη κάνει)
    • Αναλυτικές οδηγίες, αν χρειάζεστε, υπάρχουν στο Εισαγωγικό Εργαστήριο.
  2. Αφού ολοκληρώσετε το προηγούμενο βήμα, κατεβάστε με git clone το προσωπικό σας repository (όπου <username> το username σας στο github):
    git clone https://github.com/chatziko-k08/2023-lab-4-<username>

2. Υλοποίηση ADTPriorityQueue μέσω σωρού

Ο κώδικας του εργαστηρίου, περιέχει (μεταξύ άλλων):

  • modules/UsingHeap/ADTPriorityQueue.c Υλοποίηση του ADT PriorityQueue μέσω σωρού.

  • tests/ADTPriorityQueue_test.c Unit test για τον ADT PriorityQueue. Τρέχοντας make στο tests directory παράγεται το εκτελέσιμο UsingHeap_ADTPriorityQueue_test το οποίο εκτελεί τα unit tests χρησιμοποιώντας την παραπάνω υλοποίηση.

    Προσοχή: το make φτιάχνει και ένα δεύτερο εκτελέσιμο UsingADTList_ADTPriorityQueue_test για την άσκηση 3! Ως συνήθως, με make <executable> μπορείτε να φτιάξετε μόνο το ένα από τα δύο, αν θέλετε.

Αρχικά εξοικειωθείτε με τα παραπάνω αρχεία, και εκτελέστε το test. Διαβάστε και κατανοήστε τη λειτουργία του κώδικα. (Ο κώδικας είναι ακριβώς ο ίδιος με εκείνον του lecture-code).

Στη συνέχεια, παρατηρήστε ότι η υλοποίηση της pqueue_create στην περίπτωση που περάσουμε ένα vector values αρχικών τιμών (δηλαδή η λειτουργία naive_heapify) δεν είναι βέλτιστη! Εξηγήστε στο README.md τι πολυπλοκότητα έχει η υπάρχουσα υλοποίηση.

Στη συνέχεια τροποποιήστε την, με τον αποδοτικό αλγόριθμο heapify που είδαμε στις διαλέξεις. Βεβαιωθείτε, τρέχοντας το test, ότι η νέα υλοποίηση δουλεύει σωστά. Τι πολυπλοκότητα έχει;

3. Υλοποίηση ADTPriorityQueue μέσω ταξινομημένης λίστας

Δημιουργήστε μια νέα υλοποίηση του ADTPriorityQueue μέσω ταξινομημένης λίστας. Η υλοποίηση θα χρησιμοποιεί μια λίστα (ADTList) η οποία θα πρέπει να διατηρείται ταξινομημένη μετά από κάθε λειτουργία.

  • Ένας κενός ορισμός κάθε συνάρτησης υπάρχει στο modules/UsingADTList/ADTPriorityQueue.c
  • Για test χρησιμοποιούμε το ίδιο με την άσκηση 2 (tests/ADTPriorityQueue_test.c), αφού το test ελέγχει τις λειτουργίες του ADTPriorityQueue ανεξαρτήτως του πώς είναι υλοποιημένες.
  • Τρέχοντας make στο tests directory παράγεται το εκτελέσιμο UsingADTList_ADTPriorityQueue_test το οποίο εκτελεί τα unit tests χρησιμοποιώντας τη νέα υλοποίηση μέσω ADTList. Τα tests αυτά προφανώς θα αποτυγχάνουν μέχρι να ολοκληρώσετε την υλοποίησή σας, η οποία θα πρέπει να τα περνάει (και χωρίς leaks).

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

Ειδικά για την pqueue_create με vector αρχικών τιμών values, μπορείτε αν θέλετε να χρησιμοποιήσετε την “απλή” υλοποίηση που τις προσθέτει μία-μία. Θα πρέπει επίσης να εξηγήσετε την πολυπλοκότητά της, όπως για όλες τις λειτουργίες. Προαιρετικά: υλοποιήστε έναν πιο αποδοτικό τρόπο.

Οπως και στο εργαστήριο 3, όλες οι συναρτήσεις υλοποιούνται με 5-10 γραμμές κώδικα, δε χρειάζονται κατεβατά.

Παράδοση

Ολα τα αρχεία που φτιάξατε πρέπει να τα κάνετε commit και push στο github.