תקצירי תשובות

להלן תקצירי תשובות המבחן, מועד א':

שאלה 1 בטופס 1, שאלה 8 בטופס 2-
$g(n) = \Theta(T(n))$

שאלה 2 בטופס 1, שאלה 9 בטופס 1-
$\Theta(1)$

שאלה 3 בטופס 1, שאלה 2 בטופס 2-
א + ג נכונות
גם כל אחת מהן לבד קיבלה ניגוד חלקי

שאלה 4 בטופס 1, שאלה 3 בטופס 2-
$N + 2 - \log_2 N$
מכיוון שמעטים פתרו את השאלה הזאת,
התשובה הנכונה קיבלה ניקוד נוסף, והתשובה
$N$
קיבלה גם היא ניקוד מלא.

שאלה 5 בטופס 1, שאלה 4 בטופס 2-
worst case $O(\log n)$, amortized $O(1)$

שאלה 6 בטופס 1, שאלה 5 בטופס 2-
$\log_2 n$
מספר סטודנטים נימקו נכון, אבל בחרו "אף תשובה אינה נכונה".
נתנו ניקוד במקרה כזה.

שאלה 7 בטופס 1, שאלה 1 בטופס 2-
$\Omega(n \log n \log n)$
הרבה סטודנטים בחרו "אף תשובה אינה נכונה" ובנימוק רשמו
$\Omega(n \log n \log (n \log n))$
או תשובה דומה. במקרה כזה נתנו את רוב הנקודות.

שאלה 8 בטופס 1, שאלה 6 בטופס 2-
גובה העץ המירבי הוא
$\Theta (log n)$

שאלה 9 בטופס 1, שאלה 7 בטופס 2-
pre-order או post-order

שאלה 10א-
נמיין את המערך הקטן ונמזג
$O(N)$

שאלה 10ב-
נזהה את האיברים המבולגנים ע"י השוואה לשכנים
(בדרך כלל לא מספיק להשוות לשכן אחד, כי אז לא נדע מי מהם לא במקום)
נמיין אותם, ונחזיר למקומות שהוצאנו מהם לפי הסדר החדש.
$O(N)$

שאלה 10ג-
נשתמש ב-
finger tree
$O(N)$

שאלה 11א-
חיפוש מקסימום במערך
$O(N)$

שאלה 11ב-
שומרים את כל המקסימות מהסעיף הקודם במערך.
בסוף בעזרת אלגוריתם בחירה מוצאים את הגדולים מבניהם.
$O(N)$

שאלה 11ג-
שומרים את $N$ הציונים הטובים ביותר עד כה.
בכל פעם מוצאים את $N$ הגבוהים מתוך $2N$ שכוללים את ה-$N$ ששמרנו ואת ה-$N$ שהגיעו השנה.
$O(N)$