Practice hub

Θεωρήστε το πρόβλημα του ανεξάρτητου συνόλου:

INDEP: Δοθέντος ενός μη κατευθυνόμενου γράφου $G$ με $n$ κόμβους και ενός μη αρνητικού ακεραίου $k\le n$, περιέχει ο $G$ $k$-ανεξάρτητο σύνολο; (Ένα $k$-ανεξάρτητο σύνολο είναι $k$ κόμβοι που ανά 2 δεν συνδέονται με ακμή.)

i. Αποδείξτε ότι το πρόβλημα INDEP ανήκει στην κλάση $NP$.

ii. Αποδείξτε ότι όταν το $k$ έχει σταθερή τιμή, π.χ. $k=1000$, τότε το πρόβλημα INDEP ανήκει στην κλάση $P$. (Να περιγραφεί σύντομα σε φυσική γλώσσα ο αλγόριθμος και να δοθεί η πολυπλοκότητα.)

Θέλουμε να υπολογιστεί η ακολουθία $b_1,b_2,b_3,\dots ,b_n$ που προκύπτει από τον αναδρομικό τύπο

με τους 3 αρχικούς όρους $b_1=b_2=b_3=1$. Έστω $RB(n)$ ο αλγόριθμος που στηρίζεται απευθείας στην αναδρομική σχέση. (Δίνεται ότι $3^{1/3}=1,44$.)

i. Γράψτε σε φυσική γλώσσα τον αλγόριθμο $RB(n)$. ii. Δείξτε ότι ο $RB(n)$ είναι εκθετικός, με πολυπλοκότητα $\Omega (1,44^n)$. iii. Αν χρησιμοποιήσουμε δυναμικό προγραμματισμό (αλγόριθμος $DB(n)$), πόσα υποπροβλήματα θα οριστούν; iv. Δικαιολογήστε ότι η πολυπλοκότητα του $DB(n)$ είναι γραμμική. v. Ποιος αλγόριθμος είναι ταχύτερος;

Θεωρήστε το 0-1 πρόβλημα του σακιδίου: μεγιστοποίησε ${\sum }_{i=1}^n{c}_i{x}_i$ υπό τον περιορισμό ${\sum }_{i=1}^n{a}_i{x}_i\le b$, με $x_i\in \{0,1\}$, όπου τα $c_i,a_i,b$ είναι ακέραιοι.

i. Περιγράψτε σε φυσική γλώσσα έναν άπληστο αλγόριθμο $KNAPSACK(n,c_i,a_i,b)$ που επιστρέφει μια εφικτή λύση. ii. Υπολογίστε την πολυπλοκότητά του. iii. Για το στιγμιότυπο $c=(16,9,7,15,10,1)$, $a=(8,5,4,9,6,1)$, $b=12$, εφαρμόστε τον αλγόριθμο. iv. Μπορεί ο αλγόριθμος να επιστρέφει πάντα τη βέλτιστη λύση και να είναι πολυωνυμικός; v. Με δυναμικό προγραμματισμό, πόσα υποπροβλήματα χρειάζονται; Δώστε την αναδρομική σχέση.

Θεωρήστε τα προβλήματα: ελαχιστοποίηση κόστους ενός δέντρου επικάλυψης (mst) σε ένα γράφο, και ελαχιστοποίηση του κόστους ενός Χαμιλτονιανού κύκλου (TSP) σε έναν πλήρη γράφο.

i. Να δοθούν τα αντίστοιχα προβλήματα απόφασης $D(ST)$ και $D(TSP)$.

ii. Με την υπόθεση ότι $P\ne NP$: το $D(ST)$ ανήκει στην $P$; στην $NP$; είναι $NP$-complete; Και αντίστοιχα για το $D(TSP)$.

Δίνεται ένας απλός μη κατευθυνόμενος γράφος $G=(V,E,W)$ με $|V|$ κόμβους, $|E|$ ακμές και $W$ μια συνάρτηση βάρους στις ακμές. Η αναπαράσταση του $G$ είναι σε λίστες γειτνίασης. Μια συνεκτική συνιστώσα του $G$ είναι ένας υπογράφος του, μεγιστικός ως προς την έγκλιση, για τον οποίο ισχύει ότι για κάθε δύο κορυφές του υπάρχει μονοπάτι που τις συνδέει.

i. Να δοθεί αλγόριθμος σε φυσική γλώσσα, βέλτιστης πολυπλοκότητας, που βρίσκει τις συνεκτικές συνιστώσες του $G$. ii. Να υπολογιστεί η πολυπλοκότητα του αλγορίθμου.

Θεωρούμε την $f(n)=c^{\sqrt{n\log n}}$ με $c>1$. Βρες αν είναι $O\left((n\log n{)}^{{\log }^{2}n}\right)$ ή $\Omega \left((n\log n{)}^{{\log }^{2}n}\right)$.

Η συνάρτηση $g(n)=2^{\sqrt{\log n}}$ είναι $\Theta (n)$, $o(n)$ ή $\omega (n)$;

Ένα πρόβλημα $\Pi$ επιλύεται με τους παρακάτω δύο αναδρομικούς αλγορίθμους για στιγμιότυπα μεγέθους $n$:

• Ο $A_1$ διασπά το πρόβλημα σε 9 υποπροβλήματα μεγέθους $n/3$ και συνθέτει τις λύσεις σε χρόνο $n$.
• Ο $A_2$ διασπά το πρόβλημα σε 2 υποπροβλήματα μεγέθους $n/2$ και συνθέτει τις λύσεις σε χρόνο $cn$ για κάποια σταθερά $c$.

Γράψε τις αναδρομικές εξισώσεις χρόνου εκτέλεσης των $A_1,A_2$ και λύσε τες με το Θεώρημα Κυριαρχίας.

Hamiltonian Path (Η): δίνεται γράφος $G$ με $n$ κόμβους και δύο κόμβοι $s$ και $t$. Υπάρχει μονοπάτι από τον $s$ στον $t$ που περνά από κάθε κόμβο του $G$ ακριβώς μία φορά;

Δείξε ότι το πρόβλημα $H$ ανήκει στην κλάση NP.

Minimum Spanning Tree (MST): δίνεται γράφος $G=(V,E,W)$ με $n$ κόμβους και μη αρνητικά βάρη στις ακμές μέσω της $W$. Να βρεθεί ένα συνδετικό δέντρο (spanning tree) ελαχίστου βάρους.

i. Γράψε το αντίστοιχο πρόβλημα απόφασης ${\text{MST}}_D$. ii. Δείξε ότι ${\text{MST}}_D\in \text{NP}$. iii. Δείξε ότι ${\text{MST}}_D\in \text{P}$.

Ο δήμος θέλει να εγκαταστήσει κολώνες φωτισμού σε $n$ πιθανές θέσεις κατά μήκος ενός δρόμου. Για εξοικονόμηση κόστους δεν τοποθετεί κολώνες σε δύο διαδοχικές θέσεις. Κάθε θέση $x_i$ έχει φωτεινότητα ${\phi }_i$· στόχος είναι ένα υποσύνολο μη-διαδοχικών θέσεων με τη μέγιστη συνολική φωτεινότητα («μέγιστο ανεξάρτητο υποσύνολο»).

Παράδειγμα 7 θέσεων με φωτεινότητες $[8,40,20,16,32,36,24]$ (για $x_1,\dots ,x_7$). Π.χ. τα ανεξάρτητα $\{x_1,x_3,x_5,x_7\},\{x_2,x_4,x_6\},\{x_2,x_5,x_7\},\{x_1,x_4,x_7\}$ έχουν φωτεινότητες $84,92,96,48$.

1. Ο εξής άπληστος αλγόριθμος επιλέγει το καλύτερο ανάμεσα στο σύνολο των κορυφών με περιττούς δείκτες και σε αυτό με άρτιους δείκτες. Είναι βέλτιστος; Αν όχι, δώσε αντιπαράδειγμα. 2. Σχεδίασε αλγόριθμο δυναμικού προγραμματισμού που βρίσκει τη μέγιστη συνολική φωτεινότητα (δώσε την αναδρομική σχέση). 3. Δώσε τον χρόνο εκτέλεσης — πρέπει να είναι πολυωνυμικός ως προς το $n$ και ανεξάρτητος των τιμών φωτεινότητας. 4. Εκτέλεσε τον αλγόριθμο στο παραπάνω παράδειγμα.

(α) (10 μονάδες) Να κατασκευάσεις ένα κατευθυνόμενο γράφημα με πέντε κορυφές, εκ των οποίων μία θα είναι η κορυφή-πηγή $s$ (με εισερχόμενο βαθμό 0), 5 ακμές, και ένα μη-αρνητικό κύκλο, για το οποίο ο αλγόριθμος του Dijkstra λειτουργεί σωστά. Να αιτιολογήσεις σύντομα την απάντησή σου.

(β) (10 μονάδες) Να εφαρμόσεις πλήρως κατάλληλο αλγόριθμο στο γράφημα ώστε να υπολογίσεις σωστά τη συντομότερη απόσταση όλων των κορυφών από την $s$. Να κατασκευάσεις έναν πίνακα ο οποίος για κάθε βήμα θα δείχνει τις τρέχουσες αποστάσεις από την $s$.

Ένας πίνακας $n$ στοιχείων $[1\dots n]$ έχει ένα πλειοψηφικό στοιχείο αν γνήσια πάνω από τα μισά του στοιχεία είναι ίδια. Τα στοιχεία δεν είναι μεταξύ τους συγκρίσιμα (π.χ. ιερογλυφικά ή χρώματα), αλλά μπορούμε σε σταθερό χρόνο να αποφασίσουμε αν δύο στοιχεία είναι ίδια. Περίγραψε έναν αλγόριθμο που βρίσκει το πλειοψηφικό στοιχείο σε χρόνο $O(n\log n)$ και αιτιολόγησε την ορθότητά του.

Ένα τέλειο ταίριασμα σε ένα γράφημα είναι ένα σύνολο ακμών έτσι ώστε κάθε κορυφή να περιέχεται σε ακριβώς μία ακμή. Περίγραψε σε φυσική γλώσσα έναν άπληστο αλγόριθμο γραμμικού χρόνου που αποφασίζει αν ένα δέντρο έχει τέλειο ταίριασμα ή όχι, και αιτιολόγησε με 1-2 προτάσεις την ορθότητά του (δηλαδή γιατί επέλεξες αυτό το κριτήριο άπληστης επιλογής).

Αν $f(n)={\log }_{n}n$ και $g(n)=4$, κύκλωσε ποιες από τις παρακάτω σχέσεις ισχύουν:

(i) $f=O(g)$ · (ii) $f=o(g)$ · (iii) $f=\Omega (g)$ · (iv) $f=\omega (g)$ · (v) $f=\Theta (g)$ · (vi) οι $f,g$ είναι μη-συγκρίσιμες.

Ποια από τα παρακάτω προβλήματα γνωρίζουμε ότι είναι NP-πλήρη;

(i) Ισομορφισμός Γραφημάτων · (ii) Ικανοποιησιμότητα Λογικών Προτάσεων (SAT) · (iii) Παραγοντοποίηση Ακεραίων · (iv) Κύκλος Hamilton.

Αν $f(n)=2^{{\log }_{2}n}$ και $g(n)=n^{{\log }_{2}n}$, κύκλωσε ποιες σχέσεις ισχύουν: (i) $O$ · (ii) $o$ · (iii) $\Omega$ · (iv) $\omega$ · (v) $\Theta$ · (vi) μη-συγκρίσιμες.

Αν $f(n)=n^{1+\tan \phi }$, με $\phi \in [0,2\pi ]$, και $g(n)=n^2$, κύκλωσε ποιες σχέσεις ισχύουν: (i) $O$ · (ii) $o$ · (iii) $\Omega$ · (iv) $\omega$ · (v) $\Theta$ · (vi) μη-συγκρίσιμες.

Αν $T(n)=T(\sqrt{n})+1$, κύκλωσε ποια ισχύουν:

• (i) $T(n)\in o(n)$
• (ii) $T(n)\in O(1)$
• (iii) $T(n)\in o(2^n)$
• (iv) $T(n)\in O({\log }_2{\log }_{2}n)$

Αν $T(n)=2T(n/2)+n$, κύκλωσε ποια ισχύουν:

• (i) $O(n{\log }_{2}n)$
• (ii) $o(n)$
• (iii) $O(n)$
• (iv) $o(n^3)$

Με ποιο άπληστο κριτήριο λειτουργεί ο αλγόριθμος του Dijkstra;

(i) Επιλογή συντομότερου γείτονα από την τελευταία ακμή που προστέθηκε · (ii) Επιλογή της κορυφής με τη μικρότερη απόσταση από την αφετηρία · (iii) Επιλογή ακμής ελάχιστου βάρους σε μία δεδομένη τομή · (iv) Επιλογή του συντομότερου σε πλήθος ακμών μονοπατιού.

Λύνουμε ένα πρόβλημα με δυναμικό προγραμματισμό συμπληρώνοντας έναν πίνακα με τιμές $\text{OPT}(i,j)$, για $i=1\dots n$ και $j=1\dots m$. Ποια από τα παρακάτω μπορούμε να πούμε με βεβαιότητα ότι δεν αντικατοπτρίζει τη χρονική πολυπλοκότητα;

(i) $O(n)$ · (ii) $O(mn)$ · (iii) $o(m^2{n}^2)$ · (iv) $O(m{n}^2)$.

Όμοια, λύνουμε ένα πρόβλημα με DP συμπληρώνοντας έναν πίνακα τιμών $\text{OPT}(i)$ για $i=1\dots n$. Ποια μπορούμε να πούμε με βεβαιότητα ότι δεν αντικατοπτρίζει τη χρονική πολυπλοκότητα;

(i) $O(n)$ · (ii) $O(n^2)$ · (iii) $O(1)$ · (iv) $O({\log }_{2}n)$.

Εάν $P\ne NP$, ποια από τα παρακάτω δεν ανήκουν στο $P$;

(i) Κωδικοποίηση Huffman · (ii) Συντομότερο Μονοπάτι · (iii) Μακρύτερο Μονοπάτι · (iv) Ικανοποιησιμότητα Λογικών Προτάσεων (SAT).

Ποιον αλγόριθμο χρησιμοποιούμε για να αποφασίσουμε αν ένα κατευθυνόμενο γράφημα έχει αρνητικό κύκλο; (Αρκεί να τον αναφέρεις ονομαστικά.)

Δίνεται το παρακάτω μη-κατευθυνόμενο γράφημα με 6 κορυφές $A,B,C,D,E,F$ και ακμές (με τα βάρη τους):

• $C-D=1$
• $B-E=3$
• $A-C=5$
• $A-B=5$
• $C-B=5$
• $D-E=5$
• $D-F=10$

(α΄) Πόσα διαφορετικά ελάχιστα επικαλύπτοντα δέντρα (ΕΕΔ) έχει το γράφημα; (β΄) Σχεδίασε τα διαφορετικά ΕΕΔ (αν υπάρχουν).

Θέλουμε να επισκεφτούμε μία ακολουθία από $n$ αξιοθέατα ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n$ σε μία πόλη. Οι μόνες επιλογές μετακίνησης είναι ταξί ή ηλεκτρικό πατίνι, του οποίου η μίσθωση ισχύει για 4 διαδρομές. Με ταξί, η μετάβαση από το ${\alpha }_{i-1}$ στο ${\alpha }_i$ κοστίζει $c_i$ (η μετάβαση στο πρώτο αξιοθέατο είναι δωρεάν). Η ενοικίαση πατινιού κοστίζει σταθερά $S$. Ορίζουμε $\text{OPT}(i)$ = το ελάχιστο κόστος για να επισκεφθούμε τα ${\alpha }_1,\dots ,{\alpha }_i$.

(i) Ποια τιμή δίνει το ελάχιστο συνολικό κόστος; (ii) Όρισε αναδρομικά το $\text{OPT}(i)$. (iii) Ποια είναι η χρονική πολυπλοκότητα και γιατί;

Σχεδίασε έναν αποδοτικό αλγόριθμο που, δοσμένων δύο θετικών ακεραίων $m$ και $n$, υπολογίζει την τιμή $m^n$, και αιτιολόγησε την ορθότητα και την πολυπλοκότητά του. Για ευκολία θεώρησε ότι $n=2^k$ και ότι το γινόμενο δύο ακεραίων γίνεται σε σταθερό χρόνο.

Δίνεται ένας μη κατευθυνόμενος γράφος $G=(V,E,W)$ με $|V|$ κόμβους, $|E|=\Theta (|V|)$ ακμές, και $\Delta (v)$ ο βαθμός του κόμβου $v$.

i. Να δοθεί η πολυπλοκότητα των $\text{BFS}()$, $\text{DFS}()$ στον $G$.

ii. Να δοθεί αλγόριθμος σε φυσική γλώσσα που βρίσκει τους γείτονες $N(v)$ ενός κόμβου $v$ του $G$ και να υπολογιστεί η πολυπλοκότητά του όταν: (α) η αναπαράσταση του $G$ είναι με λίστες γειτνίασης· (β) η αναπαράσταση του $G$ είναι με πίνακα γειτνίασης.

Το γυμναστήριο της γειτονιάς σας απέκτησε πρόσφατα μια υπερσύγχρονη πλατφόρμα δόνησης, ένα πολύ ακριβό όργανο που υπόσχεται μυϊκή ενδυνάμωση. Πολλοί αθλούμενοι θέλουν να τη χρησιμοποιήσουν: κάθε αίτημα $i$ χαρακτηρίζεται από έναν χρόνο έναρξης $s_i$, έναν χρόνο λήξης $e_i$ και μια συνδρομή $p_i$ που είναι διατεθειμένος να πληρώσει. Υπάρχει μόνο μία πλατφόρμα, οπότε δεν μπορούν να εξυπηρετηθούν δύο αιτήματα που επικαλύπτονται χρονικά. Το γυμναστήριο θέλει να επιλέξει ένα υποσύνολο $S\subseteq \{1,2,\dots ,n\}$ μη επικαλυπτόμενων αιτημάτων ώστε να μεγιστοποιηθεί το συνολικό άθροισμα των συνδρομών.

(Α) Θεωρήστε τον εξής άπληστο αλγόριθμο: ταξινόμησε τα αιτήματα κατά φθίνουσα συνδρομή, διάλεξε το πρώτο, και κατόπιν, σαρώνοντας τη λίστα, διάλεξε κάθε επόμενο αίτημα που είναι συμβατό (δεν επικαλύπτεται) με όσα έχεις ήδη επιλέξει. Επιλύει ο αλγόριθμος αυτός το παραπάνω πρόβλημα; Αν όχι, δώστε αντιπαράδειγμα.

(Β) Βρείτε την τιμή $P[n]$ (συνολικό άθροισμα των συνδρομών) της βέλτιστης λύσης.

Σημείωση μεταγραφής: το πρωτότυπο είναι αχνό σκαναρισμένο φύλλο με $n=7$ αιτήματα. Παρακάτω διδάσκουμε πλήρως τη μέθοδο και τη δουλεύουμε σε ένα καθαρό, αντιπροσωπευτικό στιγμιότυπο.

(Α) Να επιλυθεί η αναδρομική εξίσωση $T(n)=3T(2n/3)+c$, όπου $T(1)=\Theta (1)$ και $c$ μια σταθερά θετική, με χρήση του Θεωρήματος Κυριαρχίας (Master Theorem).

(Β) Η ακολουθία $t_1,t_2,\dots ,t_n$ είναι αποθηκευμένη στον μονοδιάστατο πίνακα $H$ υπό δομή σωρού (max-heap). Κάποιος όρος $t_s$ αλλάζει και παίρνει μικρότερη τιμή. Ο νέος πίνακας $H$ ενδέχεται να μην είναι πλέον σωρός.

i. Να δοθεί σύντομα ένας αναδρομικός αλγόριθμος $RA(H,i)$ που διατηρεί στον $H$ τη δομή σωρού. ii. Να δοθεί η αναδρομική σχέση $S(n)$ που περιγράφει την πολυπλοκότητα του αλγορίθμου στη χείριστη περίπτωση. iii. Να επιλυθεί η $S(n)$, με $S(1)=\Theta (1)$. iv. Εφαρμόστε τον αλγόριθμο για έναν εσωτερικό κόμβο που κρατούσε την τιμή $14$, όταν αυτή αλλάζει σε $13$ και όταν αλλάζει σε $6$ (τα παιδιά του κόμβου κρατούν τις τιμές $8$ και $10$).

Θεωρήστε ένα γράφο $G=(V,E,W)$ με $|V|=n$, $|E|=m$ και $W$ μια συνάρτηση που ορίζει θετικά ακέραια βάρη στις πλευρές. Έστω $S\subseteq V$. Θέλουμε να βρούμε ένα δέντρο $T=(V^{\prime },E^{\prime })$ υπογράφο του $G$ ελάχιστου βάρους που περιέχει το $S$. Θεωρήστε το πρόβλημα $\Pi$ όπου $|S|=n$.

(i) Να γραφεί το πρόβλημα απόφασης ${\Pi }_A$ του $\Pi$. (ii) Να δειχθεί ότι ${\Pi }_A$ ανήκει στην κλάση $NP$. (iii) Να δειχθεί ότι ${\Pi }_A$ ανήκει στην κλάση $P$.

Χαρακτήρισε (Σ)ωστό ή (Λ)άθος: «Αν γνωρίζουμε ότι $P\ne NP$, τότε το πρόβλημα της εύρεσης συντομότερου μονοπατιού ανάμεσα σε δύο κορυφές ενός γραφήματος δεν είναι πολυωνυμικά επιλύσιμο.»

Χαρακτήρισε (Σ)ωστό ή (Λ)άθος: «Αν $f(n),g(n)$ είναι θετικές συναρτήσεις με $f(n)\ne g(n)$, τότε $f(n)+g(n)=\Theta (\max \{f(n),g(n)\})$.»

Χαρακτήρισε (Σ)ωστό ή (Λ)άθος: «Ο αλγόριθμος Bellman-Ford ανήκει στην κατηγορία των άπληστων αλγορίθμων.»

Χαρακτήρισε (Σ)ωστό ή (Λ)άθος: «Αν $T(n)=2T(n-1)+\Theta (n)$, τότε $T(n)=O(n^2)$.»

Χαρακτήρισε (Σ)ωστό ή (Λ)άθος: $1+2+\cdots +n=\Theta (n^2)$.

Δίνεται ένα δίκτυο επαρχιακών πόλεων στο ίδιο υψόμετρο, συνδεδεμένων με αυτοκινητόδρομους. Εν όψει του χειμώνα, οι πόλεις θέλουν να μπορούν να καθαρίζουν το συντομότερο συνολικό μήκος δρόμων ώστε να παραμένει δυνατή η μετάβαση από κάθε πόλη σε κάθε άλλη. Το δίκτυο έχει 5 πόλεις $A,B,C,D,E$ και τους δρόμους: $A-B,A-C,A-E,B-C,B-D,B-E,C-D,D-E$.

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

(β) Εφάρμοσε κατάλληλο αλγόριθμο — αναφέροντας υποχρεωτικά ποιος είναι — στο παραπάνω οδικό δίκτυο για να βρεις μία βέλτιστη λύση (με τα μήκη που έδωσες στο ερώτημα α).

Δοσμένης μιας δυαδικής συμβολοσειράς $S$ της μορφής $1^m{0}^n$ (όπου τα $m$ και $n$ είναι άγνωστα, αλλά το $k=m+n$ γνωστό), περίγραψε σε φυσική γλώσσα έναν αλγόριθμο που βρίσκει το $n$ — το πλήθος των εμφανίσεων του $0$ — σε $O(\log k)$ χρόνο, και δικαιολόγησε την ορθότητα και την πολυπλοκότητά του.

Υπόδειξη: ποια αναδρομική σχέση πρέπει να διέπει την $T(k)$ ώστε να ισχύει $T(k)=O(\log k)$;

Στην πρώτη μέρα ενός φεστιβάλ παρουσιάζονται δύο συγκροτήματα. Από το τέλος της συναυλίας του πρώτου μέχρι την έναρξη του δεύτερου μεσολαβεί χρόνος $T$. Σε αυτό το διάστημα η διοργανώτρια εταιρεία θα προβάλει διαφημίσεις χορηγών (χωρίς επαναλήψεις). Έχουν καταθέσει προτάσεις $n$ εταιρείες· η διαφήμιση $i$ έχει διάρκεια $t_i$ και αποφέρει κέρδος $p_i$ (όλα θετικοί ακέραιοι). Ορίζουμε $\text{OPT}(i,t)$ = το μέγιστο κέρδος από τις διαφημίσεις $1,\dots ,i$ με συνολική διάρκεια το πολύ $t$.

(α) Ποια τιμή δίνει το μέγιστο κέρδος; (β) Γράψε τον αναδρομικό τύπο του $\text{OPT}(i,t)$. (γ) Χρονική πολυπλοκότητα του υπολογισμού όλων των υποπροβλημάτων — αιτιολόγησε. (δ) Πολυπλοκότητα για τον εντοπισμό των διαφημίσεων που δίνουν το μέγιστο κέρδος. (ε) Σε ποιο γνωστό πρόβλημα αντιστοιχεί αν επιπλέον κάθε διαφήμιση πρέπει να προβληθεί σε σταθερό διάστημα $[s_i,s_i+t_i]$ εντός του $[0,T]$;

Αν $f(n)={\sum }_{i=1}^n{i}^2$ και $g(n)=n^2{\log }_{2}n$, κύκλωσε ποιες σχέσεις ισχύουν: (i) $O$ · (ii) $o$ · (iii) $\Omega$ · (iv) $\omega$ · (v) $\Theta$ · (vi) μη-συγκρίσιμες.

Ποια από τα παρακάτω προβλήματα δεν γνωρίζουμε αν είναι NP-πλήρη;

(i) Κωδικοποίηση Huffman · (ii) Μέγιστο Μονοπάτι (Longest Path) · (iii) Παραγοντοποίηση Ακεραίων · (iv) Μονοπάτι Hamilton.

Αν $f(n)={\sum }_{k=1}^n\frac{1}{k}$ και $g(n)={\log }_2\left(\sqrt{{\log }_{2}n}\right)$, κύκλωσε ποιες σχέσεις ισχύουν: (i) $O$ · (ii) $o$ · (iii) $\Omega$ · (iv) $\omega$ · (v) $\Theta$ · (vi) μη-συγκρίσιμες.

Αν $T(n)=2T(n/2)+n^3$, κύκλωσε ποια ισχύουν: (i) $\Omega (n^2)$ · (ii) $O(n^3)$ · (iii) $\Theta (n^3{\log }_{2}n)$ · (iv) $\Theta (n^3)$.

Αν $T(n)=2T(\sqrt{n})+1$, κύκλωσε ποια ισχύουν:

• (i) $\Theta (n)$
• (ii) $\Theta ({\log }_{2}n)$
• (iii) $\Theta (\sqrt{n})$
• (iv) $\Omega (2^n)$

Ποιος/οι από τους παρακάτω αλγόριθμους δεν λειτουργεί ορθά σε γραφήματα που έχουν αρνητικά βάρη στις ακμές τους;

(i) Αλγόριθμος Prim · (ii) Αλγόριθμος Αναζήτησης κατά Πλάτος (BFS) · (iii) Αλγόριθμος Dijkstra · (iv) Αλγόριθμος Bellman-Ford.

Λύνουμε ένα πρόβλημα με DP συμπληρώνοντας έναν πίνακα τιμών $\text{OPT}(i,j)$, για $i=1\dots n$, $j=1\dots m$. Ποιες επιλογές μπορούμε να πούμε με βεβαιότητα ότι δεν αντικατοπτρίζουν τη χρονική πολυπλοκότητα;

(i) $O(n^3)$ · (ii) $O(m)$ · (iii) $O(n)$ · (iv) $O(m^2{n}^2)$.

Λύνουμε ένα πρόβλημα με DP συμπληρώνοντας έναν πίνακα τιμών $\text{OPT}(i)$ για $i=1\dots n$. Ποιες μπορούμε να πούμε με βεβαιότητα ότι δεν αντικατοπτρίζουν τη χρονική πολυπλοκότητα; (i) $O(n)$ · (ii) $O(n^2)$ · (iii) $O(1)$ · (iv) $O({\log }_{2}n)$.

Ποια από τα παρακάτω αποτελούν ορθά φράγματα στην πολυπλοκότητα της εύρεσης της μέγιστης κοινής υπακολουθίας δύο συμβολοσειρών με $m$ και $n$ χαρακτήρες;

(i) $O(n)$ · (ii) $O(n^2{m}^2)$ · (iii) $O(n{\log }_{2}m)$ · (iv) $\Theta (mn{\log }_{2}n)$.

Εάν $P\ne NP$, ποια προβλήματα δεν ανήκουν στο $P$;

(i) 2-Ικανοποιησιμότητα (2-SAT) · (ii) Κάλυμμα Κορυφών (Vertex Cover) · (iii) Σακίδιο (Knapsack) · (iv) Μέγιστο Επικαλύπτον Δέντρο.

Εφάρμοσε τον αλγόριθμο του Dijkstra στο παρακάτω γράφημα με αφετηρία την κορυφή $a$. Η απάντηση αρκεί να περιέχει τον πλήρη πίνακα που διατηρεί ο Dijkstra σε κάθε βήμα. Το γράφημα έχει 6 κορυφές $a,b,c,d,e,f$ και τις ακμές (με τα βάρη τους):

• $a-d=1$
• $a-c=5$
• $a-b=4$
• $c-b=2$
• $d-b=3$
• $d-e=5$
• $b-e=1$
• $e-f=2$

Σε ποιες από τις παρακάτω κλάσεις γραφημάτων ο αλγόριθμος της τοπολογικής ταξινόμησης επιστρέφει ορθά το ζητούμενο αποτέλεσμα για κάθε γράφημα της κλάσης;

(i) Γραφήματα με θετικά βάρη στις ακμές τους · (ii) Άκυκλα κατευθυνόμενα γραφήματα · (iii) Δέντρα · (iv) Διμερή γραφήματα.

Εργαζόμαστε ως ταμίες σε κατάστημα. Τα χαρτονομίσματα/κέρματα που μπορούμε να επιστρέψουμε ως ρέστα έχουν αξία $1,10,25$ ευρώ (απεριόριστα). Στόχος: όταν δίνουμε ρέστα, να χρησιμοποιούμε το μικρότερο πλήθος κερμάτων.

Μπορούμε να πετύχουμε τον στόχο επιλέγοντας πάντα το κέρμα με τη μεγαλύτερη αξία που δεν ξεπερνά το υπόλοιπο ποσό; (i) ΝΑΙ · (ii) ΟΧΙ. Αιτιολόγησε την απάντηση.

Ένα ζευγάρι με ονόματα $s_1$ και $s_2$ θέλει να ονομάσει τον σκύλο του με ένα όνομα που να περιέχει και τα δύο ονόματά τους ως υπακολουθίες, και να είναι το συντομότερο δυνατό. Π.χ. για ΓΑΒ και ΜΙΑΟΥ, το ΜΙΓΑΒΟΥ ή το ΓΜΙΑΟΥΒ είναι έγκυρα, αλλά όχι το ΓΑΒΜΙΑΟΥ (πολύ μακρύ). Σχεδίασε αλγόριθμο Δυναμικού Προγραμματισμού που βρίσκει το βέλτιστο μήκος για συμβολοσειρές $s_1,s_2$ μηκών $m,n$.

Ορίζουμε $\text{OPT}(i,j)$ = το μήκος της συντομότερης συμβολοσειράς που περιέχει ως υπακολουθίες τα πρώτα $i$ στοιχεία της $s_1$ και τα πρώτα $j$ στοιχεία της $s_2$.

(i) Το βέλτιστο μήκος δίνεται από την τιμή $\text{OPT}(\_,\_)$. (ii) Γράψε την αναδρομική σχέση. (iii) Ποια η χρονική πολυπλοκότητα και γιατί;

Έχουμε $n$ φοιτητές/τριες· το άτομο $i$ καταθέτει ένα αίτημα με χρόνο διεκπεραίωσης $t_i$. Τοποθετούμε τα $n$ αιτήματα σε μια σειρά $\pi$ και τα διεκπεραιώνουμε ένα-ένα. Ο συνολικός χρόνος αναμονής του ατόμου $i$ ισούται με τον χρόνο των αιτημάτων που διεκπεραιώθηκαν πριν το δικό του (με βάση τη σειρά $\pi$) συν τον δικό του χρόνο $t_i$.

(α) Με ποιο άπληστο κριτήριο επιλέγουμε τη σειρά $\pi$ ώστε να ελαχιστοποιήσουμε τον χρόνο αναμονής; (β) Απόδειξε τυπικά την ορθότητα του κριτηρίου.