אלגוריתמים — ניתוח ועיצוב
מיון, אלגוריתמים על גרפים, תכנון דינמי, ואסטרטגיות חמדניות. ניתוח מדוקדק עם סימון אסימפטוטי, נוסחאות נסיגתיות, והוכחות נכונות.
יסודות: יעילות ואסימפטוטיקה
מודל ה-RAM, ספירת פעולות, וסימון O / Θ / Ω שעומד בבסיס כל ניתוח בהמשך
מיון
מיונים מבוססי-השוואה, חסמים תחתונים, ואלגוריתמי מיון בזמן ליניארי
בחירה (Selection)
מציאת סטטיסטיקות סדר ב-O(n) בתוחלת וב-O(n) במקרה הגרוע
טבלאות גיבוב (Hash Tables) ועצי חיפוש בינאריים
חיפוש ב-O(1) בממוצע באמצעות hashing ופעולות מסודרות ב-O(log n) באמצעות BSTs מאוזנים
הפרד ומשול (Divide & Conquer) ו-FFT
פירוק רקורסיבי, משפט ה-Master, וכפל פולינומים ב-O(n log n)
אלגוריתמים על גרפים
סיורים, מסלולים קצרים, וזיהוי מעגלים על גרפים מכוונים ולא-מכוונים
עצי פורש מינימליים ו-Union-Find
האלגוריתמים של Kruskal ו-Prim, ומבנה הנתונים Union-Find עם דחיסת מסלולים
ערימות וערימות בינומיות
ערימות בינאריות, עצים בינומיים, הערימה הבינומית הניתנת למיזוג, וערימת Fibonacci העצלה
תכנון דינמי (DP)
תת-בעיות חופפות, מבנה אופטימלי, memoization ו-tabulation
אלגוריתמים חמדניים וניתוח אמורטיזציוני
טיעוני החלפה, קידוד Huffman, ושיטות accounting ו-potential