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

וכמובן, הפרטים העסיסיים! הייתה בחירה של 3 שאלות מתוך 4, בבחינה של 3 שעות.

הלכתי ישר על השאלה הראשונה, כי היא הייתה נורא בסיסית, אבל עדיין לקח לי 40 דקות להזכר בניסוח המדוייק ובהוכחה כי למדתי הכול בחפיף. השאלה הייתה על האלגוריתם ההסתברותי למציאת עצים פורשים מינימליים של קרגר והחבר'ה, ובסה"כ הייתי צריך לנסח ולהוכיח את למת הדגימה שעליה הסתמכה האנליזה ההסתברותית. אחרי שסיימתי, ראיתי שזה לקח לי חצי עמוד ו-40 דקות, ונהייתי מודאג לגבי שאר השאלות.

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

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

השאלה השנייה הייתה שימוש בשינוי קנה המידה (Scaling) של גולדברג, בוואריאציה מסויימת על קנה המידה, ואפילו בלי להכנס לפרטים של האלגוריתם העיקרי, אלא רק ברמה שינוי קנה המידה! למרות זאת, אפילו את זה לא זכרתי טוב, וחירטטתי את שינוי קנה המידה כשאני נזכר בעוד ועוד פרטים חדשים ומנסה לסדר אותם כדי שקנה המידה ייצא בסדר. השאלה הייתה עם אלגוריתם עיקרי שפותר את הבעיה למשקל שחסום מלמטה ע"י n-, אז לפחות הבנתי שבוואריאציה הזאת אני יכול לעשות שינוי קנה מידה לא רק ב-2, אלא ב-n+1 (למרות שנראה כאילו האחרים וגם המרצה התכוונו לשינוי קנה מידה ב-n, אבל גם n+1 אמור לעבוד, ובכל מקרה זה לא משנה אסימפטוטית). עם כל החרטוטים, וההוספה של משקול שתי פונקציות הפוטנציאל ברבע שעה האחרונה (שהסתברה להיות מוצלחת), משום מה חיסרתי קבועה מפונקציית המשקל החדשה, כדי שזה כביכול יסתדר עם האלגוריתם העיקרי, למרות שזה דווקא מסתדר בלי, ועם כנראה שלא. אני מקווה שהמרצה יהיה נחמד ולא יוריד על זה הרבה נקודות, למרות שכתבתי אפילו הסבר עילג עם מלמול לגבי מעגלים שליליים שמנסה להצדיק את זה.

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

בסה"כ כנראה שפתרתי 2 שאלות טוב, ואחת עם טעות מעצבנת, אז זה 93-95 אם המרצה יהיה נחמד, ו-85-90 אם הוא יהיה טיפה פחות נחמד.

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

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