1) מהי סיבוכיות מינמלית למיון מערך בגודל N:
א. לפחות N^2
ב. לפחות N
ג. לפחות N*log(n)
ד. קיום ידוע רק אלגוריתם בN*log(n), אוליי ישפרו בעתיד.

2) האלגוריתם הטוב ביותר למציאת חציון במערך לא ממוין עובד
בסיבוכיות:
א. log(n)
ב. N
ג. 1
ד. n*log(n)

3) ומציאת חצין במערך ממוין?
א. log(n)
ב. N
ג. 1
ד. n*log(n)

4) סיבוכיות האלגוריתם Qsort במקרה הגרוע ביותר:
א. exp(n)
ב. N^2
ג. N*log(n)
ד. תלוי.

5) סיבוכיות הזכרון הנוסף של אלגוריתם merge sort:
א. N
ב. 1
ג. N*log(n)
ד. log(n)
ה. N^2

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

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

8) כמה צבעים שונים צריך בשביל לצבוע את מפת הכוכב קריפטון ב'
כך שכל שני מדינות שכנות יצבעו בצבע אחר?
א. 4 או פחות.
ב. 5 או פחות.
ג. 6 או פחות.
ד. אי אפשר לחסום.
ה. כל התשובות שגויות.

9) אלו מהבעיות הבאות לא ידועה כNP קשה. (לא ידוע אלגוריתם
פולינומי ואילו אפשר לבדוק האם פתרון נכון בזמן פולינומי,
ואם כן ימצא אלגוריתם פולינומי, אזי P=NP)
א. בעיית הריצוף(בהנתן אוסף בלטות ריבועיות עם קצוות צבעוניים,
האם אפשר לרצף שטח מסוים כך שקצוות סמוכים יהיו תמיד באותו
צבע?)
ב. Maximum weight Matching, בהנתן גרף לא מכוון ממושקל,
חלק את הצמתים לזוגות כך שסכום משקלי הקשתות שמחברים
את הזוגות יהיה מקסימלי.
ג. ספיקות פסוקים. בהנתן פסוק לוגי(תוצאה של AND OR ו NOT)
האם יש אוסף ערכים שניתן לתת למשתנים כך שערך הפסוק יהיה
אמת?
ד. בעיית האריזה, בהנתן n עצמים בגודל שונה כל אחד,כמה
ארגזים בגודל קבוע L צריך בשביל לארוז את כולם.
ה. כל התשובות שגויות.