16 βαθμολογήστε ερωτήσεις αλγορίθμων σχεδίασης και ανάλυσης-cs1201;

1. (α) Τι είναι ο αλγόριθμος διαίρει και βασίλευε; Εξηγήστε τη γενική προσέγγιση των αλγορίθμων διαίρει και βασίλευε. (6 βαθμοί)

(β) Χρησιμοποιήστε την προσέγγιση διαίρει και βασίλευε για να σχεδιάσετε έναν αλγόριθμο για να βρείτε το ελάχιστο στοιχείο σε έναν πίνακα n στοιχείων. Αναλύστε τη χρονική πολυπλοκότητα του αλγορίθμου σας. (10 βαθμοί)

2. (α) Εξηγήστε την έννοια του κατακερματισμού και των τεχνικών επίλυσης σύγκρουσης. (6 βαθμοί)

(β) Θεωρήστε έναν πίνακα κατακερματισμού μεγέθους m και ένα σύνολο n στοιχείων που πρόκειται να κατακερματιστούν. Ας υποθέσουμε ότι τα στοιχεία είναι ομοιόμορφα κατανεμημένα μεταξύ των υποδοχών m. Ποια είναι η πιθανότητα σύγκρουσης όταν n =m/2; Αναλύστε τον μέσο αριθμό συγκρίσεων που απαιτούνται για την επιτυχή εισαγωγή όλων των στοιχείων στον πίνακα κατακερματισμού χρησιμοποιώντας γραμμική ανίχνευση. (10 βαθμοί)

3. (α) Περιγράψτε την έννοια του δυναμικού προγραμματισμού και εξηγήστε πώς διαφέρει από την προσέγγιση διαίρει και βασίλευε. (6 βαθμοί)

(β) Χρησιμοποιήστε δυναμικό προγραμματισμό για να λύσετε το πρόβλημα κοπής ράβδου, όπου μια ράβδος μήκους n μπορεί να κοπεί σε μικρότερες ράβδους και κάθε ράβδος μήκους i έχει τιμή p[i]. Ο στόχος είναι να βρείτε τα μέγιστα έσοδα που μπορείτε να αποκτήσετε κόβοντας τη ράβδο σε μικρότερα κομμάτια. Αναλύστε τη χρονική και χωρική πολυπλοκότητα του αλγορίθμου σας. (10 βαθμοί)

4. (α) Εξηγήστε την έννοια της πληρότητας NP και τη σημασία της στην ανάλυση αλγορίθμων. (6 βαθμοί)

(β) Να αποδείξετε ότι το ακόλουθο πρόβλημα είναι NP-πλήρες:Δεδομένου ενός συνόλου n στοιχείων με τα αντίστοιχα βάρη και τις τιμές τους, προσδιορίστε εάν υπάρχει ένα υποσύνολο αυτών των στοιχείων του οποίου το συνολικό βάρος είναι μικρότερο ή ίσο με ένα δεδομένο όριο και του οποίου το σύνολο η τιμή μεγιστοποιείται. (10 βαθμοί)

5. (α) Εξηγήστε την έννοια της απόσβεσης ανάλυσης αλγορίθμων. Γιατί χρησιμοποιείται και ποια είναι τα οφέλη του; (6 βαθμοί)

(β) Πραγματοποιήστε μια αποσβεσμένη ανάλυση της δομής δεδομένων στοίβας, όπου οι λειτουργίες push και pop είναι οι μόνες λειτουργίες που επιτρέπονται. Προσδιορίστε τη μέση χρονική πολυπλοκότητα κάθε λειτουργίας. (10 βαθμοί)

6. (α) Περιγράψτε τον αλγόριθμο του Kruskal για την εύρεση του ελάχιστου εκτεινόμενου δέντρου ενός σταθμισμένου μη κατευθυνόμενου γραφήματος. (6 βαθμοί)

(β) Εφαρμόστε τον αλγόριθμο του Kruskal στο παρακάτω γράφημα και βρείτε το ελάχιστο εκτεινόμενο δέντρο:

```

(1)---2---(3)

/ |

/ |

5/4

-----------

(4)---6---(5)

```

Υπολογίστε το συνολικό βάρος του ελάχιστου δέντρου που εκτείνεται. (10 βαθμοί)

7. (α) Εξηγήστε την έννοια ενός τοπολογικού είδους κατευθυνόμενου ακυκλικού γραφήματος (DAG). (6 βαθμοί)

(β) Εκτελέστε μια τοπολογική ταξινόμηση στο ακόλουθο DAG:

```

(1) -> (2) -> (3)

\ /

-> (4)

```

Δώστε τη σειρά των κορυφών στην τοπολογική ταξινόμηση. (10 βαθμοί)

8. (α) Περιγράψτε την έννοια των δυαδικών δέντρων αναζήτησης (BSTs). Εξηγήστε πώς χρησιμοποιούνται τα BST για αποτελεσματικές λειτουργίες αναζήτησης και εισαγωγής. (6 βαθμοί)

(β) Εισαγάγετε τα ακόλουθα στοιχεία σε ένα αρχικά κενό BST:20, 10, 30, 5, 15, 25, 35. Σχεδιάστε το BST που προκύπτει και αναλύστε τη χρονική πολυπλοκότητα της αναζήτησης ενός στοιχείου σε αυτό το BST. (10 βαθμοί)

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