מרצה/ים:
פרופ' דני כהן-אור
פרופ' חנוך לוי
מתרגל/ים:
יניר קלימן
תיאור:
שיעורי בית
תרגילים תיאורטיים:
מהווים 10% מהציון הסופי.
תרגילים מעשיים:
מהווים 10% מהציון הסופי.
סיכומים:
נושאי השיעור:
- מערכים ורשימות
- מימושים
נושאי השיעור:
- רשימות
- סימוני O ו- theta
נושאי השיעור:
- אמורטיזציה
- תורים ומחסניות
נושאי השיעור:
- אמורטיזציה - מונה בינארי:
- ספירה ישירה
- שיטת הבנק
- שיטת הפוטנציאל
נושאי השיעור:
- מילונים
- עצים
- עצי חיפוש
נושאי השיעור:
- פתירת משוואות רקורסיה:
- הצבה (לנחש פתרון
- Brute Force
- שיטת המאסטר
נושאי השיעור:
- עצי חיפוש בינאריים - אנליזה
- עצי אדום שחור
נושאי השיעור:
- מעבר על עץ
- שאלות עם עצים
נושאי השיעור:
- עץ א"ש - אנליזת מחיקה מהעץ
- order statistics בעץ א"ש
- finger rbTrees
- splay trees
- B-Trees
נושאי השיעור:
- עצים אדומים-שחורים
נושאי השיעור:
- ערימות מינימום
- אלגוריתם דייקסטרה (Dijkstra)
- מימוש של ערימה
- בניית ערימה ממערך
- B-Trees - ניתוח זמן ריצה
- מעבר מעצי 2-4 לעצים אדומים שחורים
נושאי השיעור:
- ערימות מינימום
נושאי השיעור:
- עצים בינומיים
- ערימות בינומיות
- ערימות בינומיות עצילות
- ערימות פיבונאצ'י והתחלה של ניתוח זמן ריצה
נושאי השיעור:
- ערימות בינומיות
- ערימות פיבונאצ'י
נושאי השיעור:
- ערימות פיבונאצ'י - סוף ניתוח זמן ריצה
- בעיית המיון
- אלגוריתמי מיון
- quick sort - ניתוח
- הוכחת חסם תחתון על ה worst case
נושאי השיעור:
- מיונים
- הוכחת חסמים תחתונים
- רדוקציות לבעיית המיון
נושאי השיעור:
- מיון - חסם תחתון על ה average case
- מיונים "מהירים"
- כאשר המספרים ידועים מראש - count sort
- כאשר המספרים הם מתוך תחום נתון - Bin sort
- כאשר הקלט הוא מחרוזות באורך נתון - Radix sort
- מיון קלט "כמעט ממוין"
- Insertion sort
- Finger RBTrees
- selection - מציאת האיבר ה k במערך
- רעיונות לפתרון (מיון/מציאת k מינימומים/שימוש בערימה/שימוש בערמה קטנה)
- select רנדומלי (בהסתמך על בחירת pivot, כמו ב quick sort)
- הוכחת חסם מקרה ממוצע על select רנדומלי
נושאי השיעור:
- מיונים מהירים
- רדוקציות לחיפוש בינארי
נושאי השיעור:
- Select בזמן ליניארי (worst case)
- select דינאמי - order statistics
- מילון ללא יחס סדר:
- וקטור ביטים
- Hash
- Hash:
- hash פתוח - רשימות מקושרות
- hash סגור - rehash/cuckoo
- hash פתוח - ניתוח ביצועים
- hash יוניפורמי
- משפחות אוניברסליות
נושאי השיעור:
- selection
- סטטי - select ליניארי
- דינאמי - order statistics
נושאי השיעור:
- מציאת קבוצה אוניברסלית
- האש סגור, ניתוח זמן
- הגדלת טבלת ה hash
- Perfect Hashing
- מבוא ל union-find
נושאי השיעור:
- Hash
נושאי השיעור:
- union-find:
- union by rank
- path comression
- הרכבת פונקציות
- פונקציית אקרמן (Ackermann)
- פונקציית ה tower ופונקציית ה *log
- ניתוח זמן ריצה, הוכחת זמן amortized של *log לפעולה
נושאי השיעור:
- union-find