מבני נתונים ואלגוריתמים - מחברת קורס/מבחן סופי מועד א' סמסטר ב' 2007 - שאלות

הבהרה בנוגע לשימוש בלשון זכר: כדי למנוע סרבול מיותר, וכמקובל בשפה העברית, ננקטת לעתים לשון זכר בהתייחסות אל כלל הגולשות והגולשים ובמתן שמות לערכים. אנא קבלו זאת בהבנה.

הנחיות החומר המותר בשימוש במבחן זה הוא כל דף (מודפס) שמקורו באתר הקורס, כולל דפים שעליהם הערות בכתב יד. כל חומר אחר אסור בשימוש במבחן. השימוש בכל מכשיר אלקטרוני (כולל מחשבון) אסור בשימוש במבחן. אנא שים לב שלצד כל שאלה מופיע מספר הנקודות (המשוער) שלה, ושסכום הנקודות במבחן הוא 110. שאלה מספר 5 היא קשה, וממומלץ שתפתור אותה לאחר שפתרת את שאר השאלות. ייתכן שמספר הנקודות שיוענק לשאלה יהיה נמוך ממה שכתוב (מבלי לפגוע בסכום הנקודות). לא יינתנו פקטורים מעבר לכך. בכל שאלה, אם תציין במפורש שאינך עונה עליה - תקבל 15% מערכה. בתשובה שבה אתה משתמש בתכנון דינמי, 70% מהניקוד יוענק לפתרון נכון, מוכח, ויעיל, המוצא את מחיר הפתרון הטוב ביותר. 100% מהניקוד יוענק לפתרון העונה על הדרישות הנ"ל, אך מדפיס במפורט גם את פרטי הפתרון.

שאלה 1

(~20 נקודות)

בכיתה למדנו כבר על עצי חיפוש בינריים. שאלה זו עוסקת בווריאציה. עץ Foo-Bar מוגדר כך:

1. כל צומת הוא אחד משני סוגים: צומת Foo או צומת Bar.
   1. צומת Bar מחזיק מפתח אחד ו(עד ל)2 ילדים (כמו הצמתים הרגילים שראינו).
   2. צומת Foo מחזיק 2 מפתחות ו(עד ל3 ילדים.
2. העץ מקיים את את תכונת הFoo-Bar - לכל צומת x:
   1. כל מפתח בתת-עץ שמאלי של מפתח כלשהו, קטן או שווה לו.
   2. כל מפתח בתת-עץ ימני של מפתח כלשהו, גדול או שווה לו.
3. כל המסלולים משורש העץ לעלה ריק (Nil) בעל אותו אורך בדיוק.

דוגמה: צומת Bar צומת Bar.

דוגמה: צומת Foo צומת Foo.

דוגמה: עץ Foo-Bar להלן דוגמה לעץ Foo-Bar תקין. בעץ זה 3 צמתים (2 מסוג Bar, ו1 מסוג Foo). יש לו 4 מפתחות, וגבהו 2. עץ Foo-Bar.

אנא הוכח שעץ Foo-Bar הוא לוגריתמי: אם יש בו $\displaystyle n$ מפתחות וגבהו הוא $\displaystyle h$, אז $\displaystyle h=O(\log(n))$.

שימו לב: אל תתייחס לשאלה כיצד ליצור עץ כזה, או כיצד להכניס ולהוציא מפתחות ממנו - זה לא רלוונטי.

שאלה 2

(~15 נקודות)

נתון גרף $\displaystyle G=(V,E)$ מכוון וקשיר מצומת $\displaystyle s\in V$ כלשהו. לכל קשת יש מחיר. רוצים למצוא את המסלול הזול ביותר מs לכל צומת u כלשהו, אך תחת העדפה למסלולים שארכם (כלומר, מספר קשתותיהם) זוגי. $\displaystyle x$ מציין גודל קנס כלשהו. אם מסלול כלשהו מ$\displaystyle s$ ל$\displaystyle u$ הוא אי-זוגי, יש להוסיף למחיר מסלול זה קנס בגובה $\displaystyle x$.

אנא תאר אלגוריתם המקבל כקלט את הגרף, טבלת עלויות לקשתות, וגודל הקנס, ומוצא את מחיר המסלול הזול ביותר (במובן שאותו הסברנו כרגע) לכל צומת $\displaystyle u$. אנא הוכח נכונות ונתח סיבוכיות.

שאלה 3

(~20 נקודות)

בשאלה זו עליך להוכיח חסם תחתון על $\displaystyle T(n)$, מספר עצי החיפוש הבינריים השונים בעלי $\displaystyle n$ מפתחות שונים זה מזה.

דוגמה: נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1,2$. יש 2 עצים מתאימים: עצי חיפוש בינריים בעלי המפתחות 1 ו2. נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1,2,3$. יש 5 עצים מתאימים: עצי חיפוש בינריים בעלי המפתחות 1, 2, ו3.

מהדוגמה נוכל להסיק כי

$\displaystyle T(0)=T(1)=1$, $\displaystyle T(2)=2$, $\displaystyle T(3)=5$.

אנא הוכח ש$\displaystyle T(n)=\Omega (2^{n})$, כלומר שמספר עצי החיפוש הבינריים גדל בצורה אקספוננציאלית.

שאלה 4

(~35 נקודות)

רשת החומוסיות מק-לאפה מתכננת להקים סניפים רבים לאורך רחוב איבן-גבירול בתל אביב. $\displaystyle m_{1},m_{2},\ldots m_{n}$ מציינים את מספרי הבתים ברחוב בהם יש מקום פנוי להקמת סניף חדש. הרשת שוקלת היכן להקים את הסניפים החדשים:

1. מסקר שוק, הרשת מעריכה שבבית מספר $\displaystyle m_{i}$ רווחיה הצפויים יהיו $\displaystyle p_{i}$ ‏($\displaystyle p_{i}$ הוא מספר חיובי כלשהו).
2. הרשת אינה מוכנה להקים שני סניפים שמרחקם זה מזה הוא פחות מ$\displaystyle k$‏ ($\displaystyle k$ הוא מספר שלם חיובי כלשהו).

דוגמה: אם $\displaystyle k=20$ והרשת בוחרת להקים סניף בבית מספר 135, אסור לה להקים סניף בבית מספר 143, שכן $\displaystyle 143-135<20$.

אנא כתוב אלגוריתם יעיל המקבל את המערך M (המכיל את מספרי הבתים), את המערך P (המכיל את הרווחים הצפויים), ואת המספר k (המציין את מגבלת המרחק), ומדפיס את מספרי הבתים שהקמת הסניפים בהם צפוייה למקסם את הרווחיות. אנא הוכח נכונות ונתח סיבוכיות.

שאלה 5

(~20 נקודות)

במסיבה כלשהי יש $\displaystyle n$ אנשים; חלקם לחץ ידיים זה עם זה. כעת יש להושיב אותם משני צידי שולחן. אנא הוכח שאפשר להושיב אותם באופן כזה כך שכל אחד יושב מול לפחות חצי מהאנשים שאתם לחץ יד.

דוגמה: נניח שבמסיבה יש שלשה אנשים: 1,‏ 2,‏ ו3, ורק 1 ו2 לחצו ידיים זה עם זה. אכן אפשר להושיב את 1 ו3 בצד אחד של השולחן, ואת 2 בצד השני.