מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 7/שאלות

1

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

1. עבור המימוש הראשון, אנא מצא סדרת $\displaystyle m$ פעולות, שמתוכן $\displaystyle n$ הן פעולות Make-Set, שסיבוכיותה הכוללת היא $\displaystyle \Theta (m+n^{2})$.
2. עבור המימוש השני, אנא מצא סדרת $\displaystyle m$ פעולות, שמתוכן $\displaystyle n$ הן פעולות Make-Set, שסיבוכיותה הכוללת היא $\displaystyle \Theta (m+n\cdot \log(n))$.

שימו לב: בסעיף השני הזנח שגיאות עיגול, או, לחלופין, הנח ש$\displaystyle n$ הוא חזקה שלמה של 2.

2

אנא הוכחה את המשפט הבא:

משפט: פתרון $\displaystyle T(n)=\max _{1\leq i\leq n/2}[T(i)+T(n-i)+\Theta (i)]$ הוא $\displaystyle O\left(n\cdot \log(n)\right)$ .

3

נתון גרף $\displaystyle G=(V,E)$. הגרף דליל, ולכן רוצים להשתמש בייצוג רשימה. עם זאת, סיבוכיות מימוש הפונקציה E(G) שראינו בכיתה, דהיינו $\displaystyle \Theta (|E|+|V|)$, גבוהה מדי לטעמנו.

אנא הסבר כיצד לשנות את המימוש כך שסיבוכיות הפונקציה תרד ל$\displaystyle \Theta (|E|)$, מבלי להגדיל את סיבוכיות הפונקציות האחרות. אנא הסבר בקצרה (רצוי בתרשים) את השינויים הנדרשים, וכתוב את הפסוודו-קוד לפונקציה E(G).

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

4

נתון גרף $\displaystyle G=(V,E)$ ברשימת שכנויות.

1. רוצים לחשב, לכל צומת $\displaystyle v\in V$, את דרגת היציאה שלו (כלומר, כמה קשתות יוצאות ממנו). מה הסיבוכיות הנדרשת?
2. רוצים לחשב, לכל צומת $\displaystyle v\in V$, את דרגת הכניסה שלו (כלומר, כמה קשתות נכנסות אליו). מה הסיבוכיות הנדרשת?

5

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

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

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

6

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

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

7

אנא הוכח שכל אחת מהפעולות למעבר על כל איברי העץ שראינו Post-Order In-Order, וIn-Order), פועלת בזמן לינארי במספר האיברים בעץ.