תשובה 1
כל האיברים בעץ שדרגתו $j$ הוכנסו לפני כל האיברים בעץ שדרגתו $i$.
לכן, האיברים בעץ עם הדרגה $j$ קטנים מכל האיברים בעץ עם הדרגה $i$.
תשובה 2
א. נשתמש במיון בסיס.
גודל הבסיס הוא 4 אותיות, בכל מילה יש $t$ אותיות, ויש $n$ מילים.
סה"כ זמן הריצה הוא $O(nt) = O(m)$.
ב. אנחנו ממינים $n$ מחרוזות, לפי החסם התחתון שלמדנו למיון במודל ההשוואות בכיתה,
נקבל חסם תחתון של $\Omega(n \log n)$.
מכיוון שייתכן והמחרוזות שונות רק באותיות האחרונות שלהן, נצטרך לקרוא את כל הקלט, והקבל חסם תחתון $\Omega(m)$.
סה"כ קיבלנו $\Omega(m + n \log n)$.
ג. פעולת partition משנה את סדר האיברים במערך באופן הבא -
מ-$k1$ עד $p-1$ כל המחרוזות שהאות ה-j-ית שלהם קטנה מ-C, אם יש כאלה.
מ-$p$ עד $q$ האיברים שהאות ה-j-ית שלהם זהה ל-C,
ומ-$q+1$ עד $k2$ אלה שהאות ה-j-ית שלהם גדולה מ-C, אם יש כאלה.
ד. שתי השורות הראשונות דורשות זמן כגודל המערך שבו אנחנו מטפלים עכשיו,
שתי הקריאות הרקורסיביות הראשונות פועלות על מערך שגודלו הוא לכל היותר חצי מהגודל המקורי,
השורה האחרונה מקדמת את האות j שבה אנחנו נמצאים במחרוזות p עד q, היא נקראת עד $t$ פעמים לכל מחרוזת.
מניתוח כמו של Quicksort בתוספת $O(nt)$ עבודה נקבל $O(m + n \log n)$.
תשובה 3
א. עבור כל איבר אנחנו מטפסים במקרה הגרוע מעלה לשורש.
זמן הריצה הוא לכן $O(n \log n)$.
ב. ראשית נמקם את כל האיברים בעלים,
אחר כך נעלה שכבה אחר שכבה מלמטה למעלה, ובכל צומת נשים את הערך של הקטן מבניו.
עבור כל צומת נבצע השוואה אחת ולכן זמן הריצה הוא כמספר הצמתים - $O(n)$.
ג. במקרה הגרוע נצטרך להכפיל את המערך, ולתקן את התוכן שלו בהתאם, זמן הריצה לפעולה יהיה $O(n)$.
בניתוח אמורטייזד נוכל לחייב את זמן הריצה של הכפלת המערך על הפעולות שקדמו ללא הכפלת המערך, הניתוח דומה להכפלת מערך כמו שנלמדה בכיתה.
אבל, עדיין יתכן שכל איבר יצטרך לפעפע מעלה לשורש, וזמן הריצה אמורטייזד לפעולה הוא $O(\log n)$.
תשובה 4
א. $2/5 \cdot 3/4 = 3/10$.
ב. $1- 3/5 \cdot 2/4 = 7/10$.
ג. זמן הריצה מורכב מעבודה לינארית על המערך, קריאה רקורסיבית על B שגודלו כ-$n/4$, וקראיה רקורסיבית על A1 או A2 שאת גודלם חסמנו בסעיפים הקודמים.
סה"כ $T(n) = O(n) + T(n/4) + T(7n/10)$.
ד. מכיוון ש-$1/4 + 7/10 < 1$, הניתוח דומה לזה של אלגוריתם הבחירה שראינו בכיתה - $O(n)$.
תשובה 5
א. ניצור מערך דו-מימדי של ערכים בולאניים כך שלכל צומת יהיו עמודה ושורה, וכל תא יציין אם קיימת קשת או לא.
זמן האיתחול הוא $O(n^2)$, שאר הפעולות דורשות זמן קבוע.
ב. נשתמש בעץ חיפוש שמכיל את כל הקשתות (מכיוון שיש סדר על הצמתים קל באופן טבעי להגדיר סדר על הקשתות).
זמן הריצה לשלושת הפעולות הוא $O(\log n)$.
ג. נשתמש בטבלת האש בגודל המתאים שתכיל את הקשתות.
תוחלת זמן הריצה לכל אחת מהפעולת היא $O(1)$.
ד. נשתמש במבנה union-find על הצמתים.
פעולת האיתחול תצור קבוצה לכל צומת.
פעולת Add-Edge תבצע union בין הצמתים,
ופעולת Connected? תבדוק אם הם באותה קבוצה.
זמן הריצה אמורטייזד לשתי הפעולות הוא $O(\alpha(n))$.
