מבני נתונים

תשע״ג

• הרצאה 1 ←

  מערכים ורשימות
  מימושים

• תרגול 1 ←

  רשימות
  סימוני O ו- theta

• הרצאה 2 ←

  אמורטיזציה
  תורים ומחסניות

• תרגול 2 ←

  אמורטיזציה - מונה בינארי:
  
  ספירה ישירה
  שיטת הבנק
  שיטת הפוטנציאל

• הרצאה 3 ←

  מילונים
  עצים
  עצי חיפוש

• תרגול 3 ←

  פתירת משוואות רקורסיה:
  
  הצבה (לנחש פתרון
  Brute Force
  שיטת המאסטר

• הרצאה 4 ←

  עצי חיפוש בינאריים - אנליזה
  עצי אדום שחור

• תרגול 4 ←

  מעבר על עץ
  שאלות עם עצים

• הרצאה 5 ←

  עץ אש - אנליזת מחיקה מהעץ
  order statistics בעץ אש
  finger rbTrees
  splay trees
  B-Trees

• תרגול 5 ←

  עצים אדומים-שחורים

• הרצאה 6 ←

  ערימות מינימום
  אלגוריתם דייקסטרה (Dijkstra)
  מימוש של ערימה
  בניית ערימה ממערך
  B-Trees - ניתוח זמן ריצה
  מעבר מעצי 2-4 לעצים אדומים שחורים

• תרגול 6 ←

  ערימות מינימום

• הרצאה 7 ←

  עצים בינומיים
  ערימות בינומיות
  ערימות בינומיות עצילות
  ערימות פיבונאצ'י והתחלה של ניתוח זמן ריצה

• תרגול 7 ←

  ערימות בינומיות
  ערימות פיבונאצ'י

• הרצאה 8 ←

  ערימות פיבונאצ'י - סוף ניתוח זמן ריצה
  
  בעיית המיון
  אלגוריתמי מיון
  quick sort - ניתוח
  הוכחת חסם תחתון על ה worst case

• תרגול 8 ←

  מיונים
  הוכחת חסמים תחתונים
  רדוקציות לבעיית המיון

• הרצאה 9 ←

  מיון - חסם תחתון על ה average case
  מיונים מהירים
  
  כאשר המספרים ידועים מראש - count sort
  כאשר המספרים הם מתוך תחום נתון - Bin sort
  כאשר הקלט הוא מחרוזות באורך נתון - Radix sort
  
  מיון קלט כמעט ממוין
  
  Insertion sort
  Finger RBTrees
  
  selection - מציאת האיבר ה k במערך
  
  רעיונות לפתרון (מיון/מציאת k מינימומים/שימוש בערימה/שימוש בערמה קטנה)
  select רנדומלי (בהסתמך על בחירת pivot, כמו ב quick sort)
  הוכחת חסם מקרה ממוצע על select רנדומלי

• תרגול 9 ←

  מיונים מהירים
  רדוקציות לחיפוש בינארי

• הרצאה 10 ←

  Select בזמן ליניארי (worst case)
  select דינאמי - order statistics
  מילון ללא יחס סדר:
  
  וקטור ביטים
  Hash
  
  Hash:
  
  hash פתוח - רשימות מקושרות
  hash סגור - rehash/cuckoo
  hash פתוח - ניתוח ביצועים
  hash יוניפורמי
  משפחות אוניברסליות

• תרגול 10 ←

  selection
  
  סטטי - select ליניארי
  דינאמי - order statistics

• הרצאה 11 ←

  מציאת קבוצה אוניברסלית
  האש סגור, ניתוח זמן
  הגדלת טבלת ה hash
  Perfect Hashing
  מבוא ל union-find

• תרגול 11 ←

  Hash

• הרצאה 12 ←

  union-find:
  
  union by rank
  path comression
  הרכבת פונקציות
  פונקציית אקרמן (Ackermann)
  פונקציית ה tower ופונקציית ה *log
  ניתוח זמן ריצה, הוכחת זמן amortized של *log לפעולה

• תרגול 12 ←

  union-find