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

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

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

שאלה 1

(~24 נקודות)

אנא כתוב אלגוריתם יעיל המקבל כקלט מערך A של מספרים שלמים חיוביים, ומספר שלם חיובי t כלשהו, ומוציא כפלט True או False בהתאם לשאלה האם קיימת תת-קבוצה של הערכים בA שסכום איבריה הוא בדיוק t.

דוגמה: נניח שהמערך הוא $\displaystyle A=[2,1,10,40,20]$, ו$\displaystyle t=52$. התשובה היא True, מפני ש$\displaystyle 2+10+40=52$.

אנא הבע סיבוכיות תשובתך במונחי $\displaystyle n$ ו$\displaystyle t$.

שאלה 2

(~24 נקודות)

נתון גרף לא-מכוון וקשיר $\displaystyle G=(V,E)$, וכן טבלת עלויות לקשתות Weights. ידוע שאין שתי קשתות בעלות אותו המשקל: לכל שתי קשתות $\displaystyle e_{1}$ ו$\displaystyle e_{2}$, בהכרח Weights[e1] ≠ Weights[e2]. אנא הוכח או הפרך את הטענה הבאה: לגרף קיים עץ פורש מינימום יחידי.

שאלה 3

(~24 נקודות)

נתונה מטריצה בת $\displaystyle n$ עמודות ו$\displaystyle m=2^{n}-1$ שורות. כל כניסה במטריצה היא 0 או 1, ולכן כל שורה מתארת מספר בינרי בעל $\displaystyle n$ ביטים. השורות אינן מסודרות בסדר ידוע, אך ידוע שאין שתי שורות זהות. מכאן נובע שחסרה שורה להשלמת כל $\displaystyle 2^{n}$ המספרים האפשריים בעלי $\displaystyle n$ ביטים.

דוגמה: עבור $\displaystyle n=2$, ייתכן שהשורה הראשונה היא המערך [0, 1] (המתאר בבינרית את המספר 1), השורה השנייה היא המערך [1, 1] (המתאר בבינרית את המספר 3), והשורה השלישית היא המערך [0, 0] (המתאר בבינרית את המספר 0). השורה החסרה היא המערך [1, 0] (המתאר בבינרית את המספר 2).

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

רמז נסה להפוך את הבעיה לבעיה קטנה בחצי (בערך) בזמן לינארי.

שאלה 4

(~24 נקודות)

באפליקציה מסויימת, יש צורך במבנה נתונים התומך בפעולות Insert(pq, v),‏ Delete-Min(pq),‏ וMin(pq).‏ משמעות פעולות אלו היא בדיוק זו של תור קדימויות - מדובר במבנה נתונים המשתמש באיזושהי השוואה כדי לספק את האיבר הקטן בכל עת.

1. ידוע שבאפליקציה זו, מספר הפעולות הצפוי מסוג Delete-Min(pq) וMin(pq) הוא זניח יחסית למספר הפעולות הצפוי מסוג Insert(pq, v).‏ אנא הצע מימוש כך שInsert(pq, v) יהיה יעיל ככל האפשר. מה סיבוכיות שתי הפעולות האחרות במימוש שהצעת?
2. האם ייתכן מימוש לתור קדימויות בו הן Insert(pq, v) והן Delete-Min(pq) יעבדו בזמן $\displaystyle O(1)$?

שימו לב: #בסעיף הראשון, עליך למצוא יעיל ככל האפשר לInsert(pq, v). אין צורך למצוא מימוש יעיל במיוחד לשתי הפעולות האחרות. אפשר לפתור את הסעיף השני גם מבלי לפתור את הסעיף הראשון.

שאלה 5

(~14 נקודות)

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

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

רמז צייר גרף שבו כל אדם הוא צומת. מה יקרה אם תמחק צומת כלשהו והקשתות היוצאות ממנו?