דרישות קדם: מבני נתונים ואלגוריתמים או יעילות של חישובים.
לקורס שתי מטרות. האחת היא לחשוף את הסטודנטים למבחר של טכניקות מתקדמות באלגוריתמיקה, והשנייה היא לתת לסטודנטים הזדמנות לחוות את הרוח העכשווית במחקר אלגוריתמי.
נושאי הקורס יבחרו מתוך הרשימה הבאה.
מושגי יסוד: בעיות אופטימיזציה, אלגוריתמי קירוב, סכימות קירוב פולינומיאליות, אלגוריתמים הסתברותיים מסוג Monte-Carlo ו Las-Vegas.
בעיות קירוב בסיסיות: בעיית כיסוי הקדקודים (Vertex Cover),בעיית כיסוי הקבוצות (Set Cover), בעיית הסוכן הנוסע (Traveling Sales Person) , בעיית הסכום החלקי (Subset Sum).
השיטה ההסתברותית ויישומה לקירוב Max-Cut ו Max-Sat.
שיטת העיגול האקראי (Randomized Rounding) ויישומה ל Max-Sat.
דגימה מקרית ויישומה לקירוב מספר ההשמות המספקות נוסחאת DNF, למשפט Occam בלמידה חישובית, ולבדיקת תכונות מקורבת.
בעיות Online.
אלגוריתמים מבוזרים ומקביליים.