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

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

שש בעיות, בלי בחירה, חמש הטובות שוקלות 18 נקודות, השישית 10.

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

הבעיה השלישית נראתה סבירה, ואחרי שחשבתי עליה כעשרים שניות הפיתרון צץ במוחי:

3) נתון גרף לא מכוון וצומת מסויים בו, רוצים למצוא עץ פורש מינימלי שדרגת הצומת הנתון מקסימלית בו.

צבעתי את הקשתות היוצאות מהצומת באדום והרצתי Prim עם העדפה לקשתות אדומות מבין קשתות שוות (ואז יש מספר מקסימלי של קשתות שיוצאות מהצומת ולכן דרגתו בעץ מקסימלית).

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

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

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

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

(בטבלה גם נשמרים מצביעים לתאים שמהם חושב התא הנוכחי כדי לחשב את תת הסדרה)

לדעתי זה מרוויח לי די ביושר עוד 18 נקודות.

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

2) בהנתן גרף מכוון ומספר טבעי לבדוק האם אפשר לחלק משקלים -1 ו0 לקשתות הגרף כך שלא יהיו מעגלים שליליים.

הפיתרון הוא כמובן פשוט, להריץ SCC ובכל רק"ח שיש בו יותר מאיבר אחד לאפס את כל הקשתות ולספור כמה קשתות איפסנו ולהשוות עם המספר שניתן. חשבתי על זה אבל כנראה מחוסר השינה משהו התבלבל לי לי במוח וחשבתי שיש לנו משקל +1 במקום 0 ואז לא ידעתי איך לאזן את המינוסים עם פלוסים, ובעצם לא היה צריך לאזן אלא לאפס הכול =( כתבתי סתם זיון שכל בדקה האחרונה שלא מקנה לי כלום כי הוא לא נכון (הפתרון ההתחלתי שלי שהוא סתם בודק כמה קשתות צריך להסיר כדי שלא יהיה מעגל, לא יודע מה זה קשור (DFS ולהוריד קשתות אחוריות) =(. מה שנותן לי בדיוק 0 נקודות.

את הסעיף השני עשיתי גם בדקה האחרונה אבל נראה לי נכון, הייתי צריך למצוא בגרף מסעיף קודם בהנתן מישקול מתאים ושאין מעגלים שליליים, למצוא מסלולים קצרים ביותר מצומת נתון. שיניתי מינוסים לפלוסים וזה הפך להיות מסלולים ארוכים ביותר והרצתי Dijkstra עם לקיחת צומת במרחק מקסימלי במקום מינימלי ואפילו זכרתי שDijkstra רץ בזמן ליניארי במשקולות כאלה! מה שנותן לי 3-5 נקודות, כי לא היה לי זמן להוכיח שזה נכון, למרות שכתבתי שזה ברור =\. (זאת הייתה הבעיה השישית הגרועה שלי, וחבל, היא הייתה קלה, אבל הייתי לחוץ לעשות כמה שיותר מהאחרות =(((

4) בהנתן גרף וזרימה מקסימלית לקחו K קשתות והוסיפו לכל אחת קיבול 0.5, למצוא זרימה מקסימלית חדשה:

אפילו טרחתי והראיתי מקרה שאין בו משהו יותר מהיר מפשוט להריץ FF בדיוק K פעמים. (המקרה: מסלול יחיד עד לצומת שממנו יוצאות K הקשתות, כולן היו רוויות, ומקודקוד שני של כל קשת יוצאת קשת לבור, שאר הקיבולים גדולים מספיק כדי להוסיף איזה K\2 יחידות זרימה). שזה נותן לי 18 נקודות וחשדות כבדים שפספסתי פה משהו, זה היה קל מידי מכדי להיות אמיתי =\\

5) למצוא תבנית בטקסט כאשר נתון אינדקס K כך שמותר לתווים בתבנית במקומות K עד K+6 להיות שונים מהטקסט:

זיון שכל ארוך ולא בטוח בעצמו על איך לשנות KMP, אני לא אפרט פה כי אין לי כוח וזה באמת חפירה. מה שכן, הוספתי מאחורה פיתרון-שטות של לבדוק 2 בחזקת 7 (128) אפשרויות של שבעת התווים כשאני שם X במקום התוו כדי לסמן אי התאמה בטוחה ובשאר התאמה בטוחה, בכל פיתרון פונקציית הפרפיקסים מחושבת מחדש ואחרת בהתאם לתווים, והיפוך שיוויון ואי-שיוויון באינדקסים מתאימים בKMP עצמו. בסה"כ זה נראה לי גם נכון, נו אז מה שהרצתי את זה 128 פעמים, זה ליניארי =) שזה בתקווה נותן לי 16-18 נקודות, אולי יוריד כי ההסבר מעפאן =\

6) למרות שלא הייתי בטוח בתכנות הלינארי אפילו כשיצאתי מהמבחן, בדקתי במחברת דוגמה דומה שעשינו בכיתה וראיתי שעד כמה שאני זוכר את הפיתרון שלי צדקתי =) היינו צריכים לנסח בעיית Multicommodity min-cost flow בצורת תכנות ליניארי, אם הייתי עובר על הדוגמאות ביותר מהינף מבט הייתי עושה את זה בערך בעשרים שניות =\ שזה נותן לי 9 נקודות.

הסעיף האחרון היה אלגוריתם קירוב, עד עכשיו אין לי מושג איך למצוא אותו, אם מישהו יגיד לי הוא יקבל פרס ;)

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

השאלה הייתה כזו: בהנתן קבוצה V בוחרים ממנה M שלשות Ei=(ai,bi,ci) , האינדקס מאחד עד M. רוצים קבוצה S חלקית לV מינימלית כך שלכל שלשה יש איבר בשלשה שנמצא בS. רוצים לעשות את זה בקירוב טוב ויעיל ככל האפשר.

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

אח"כ כתבתי את ההיוריסטיקה: נעבור על כל השלשות ומכל שלשה נוסיף איבר שאינו בS. לא ידעתי כמובן איזה קירוב זה ואיך להוכיח אותו.

אח"כ עוד היוריסטיקה: לכל איבר מתוך השלשות נספור כמה פעמים הוא מופיע בכל השלשות. נוסיף איבר שמופיע הכי הרבה פעמים לS, נמחוק את השלשות שהוא הופיע בהן, נספור לכל האיברים מחדש וכן הלאה. אלגוריתם Greedy נחמד, רק מה, אין לי מושג איזה יחס קירוב זה נותן ואם בכלל =\

אני בספק שהוא ייתן לי ניקוד על ההיוריסטיקות ה"נפלאות" האלו, אך אני נותן נקודה 1 לבעיה, כי בטח המרצה נחמד =)

בסה"כ להערכתי יש לי 18+18+18+(16-18)+(3-5)+9+1=87-83. שזה די גרוע, אבל תמיד אפשר לקוות לפקטור! =) ובכל מקרה, אם אני באמת הולך לנהל את החיים (=הלימודים =P  ) שלי כמו שאני מתכנן עכשיו, לא תהיה לי בעיה לגשת למועד ב' של העסק הזה בספטמבר.

טוב, עכשיו יאללה ללמוד ללוגיקה ותוכנה, לחרוש כמו איכר אינדונסי, שנל שנל ארבייטן! =)