מבני נתונים
2013 סמסטר ב' (אביב)
מרצים: פרופ' דני כהן אור, פרופ' חנוך לוימתרגל: יניר קלימן
אתר הקורס: במודל!
שיעורי בית
שיעורי הבית מתחלקים לשתי קבוצות:
תרגילים תיאורטיים:
ינתנו כמעט בכל שבוע, להגשה בתיבת העץ מספר 4 בשרייבר (ליד חדר 5).
מהווים 10% מהציון הסופי.
תרגילים מעשיים:
ינתנו שני תרגילים מעשיים הסמסטר עם משקל שווה. התרגילים יעשו בזוגות.מהווים 10% מהציון הסופי.
סיכומים:
שבוע ראשוןהרצאה 1 לא התקיימהתרגול 1לא התקיים
שבוע שלישיהרצאה 3*אמורטיזציה
*תורים ומחסניות
תרגול 3
-שיטת הבנק
-שיטת הפוטנציאל
*תורים ומחסניות
תרגול 3
- אמורטיזציה - מונה בינארי:
-שיטת הבנק
-שיטת הפוטנציאל
שבוע רביעיהרצאה 4
תרגול 4
- Brute force
-שיטת המאסטר
- מילונים
- עצים
- עצי חיפוש
- סיכום
תרגול 4
- פתירת משוואות רקורסיה:
- Brute force
-שיטת המאסטר
שבוע שישיהרצאה 6לא התקיימה - פסחתרגול 6לא התקיים - ספח
שבוע שביעיהרצאה 7
תרגול 7
- עץ א"ש - אנליזת מחיקה מהעץ
- order statistics בעץ א"ש
- finger rbTrees
- splay trees
- B-Trees
- סיכום
תרגול 7
- עצים אדומים-שחורים
- סיכום
שבוע שמיניהרצאה 8
תרגול 8
- ערימות מינימום
- אלגוריתם דייקסטרה (Dijkstra)
- מימוש של ערימה
- בניית ערימה ממערך
- B-Trees - ניתוח זמן ריצה
- מעבר מעצי 2-4 לעצים אדומים שחורים
- סיכום
תרגול 8
- ערימות מינימום
- סיכום
שבוע תשיעיהרצאה 9
תרגול 9
- עצים בינומיים
- ערימות בינומיות
- ערימות בינומיות עצילות
- ערימות פיבונאצ'י והתחלה של ניתוח זמן ריצה
- סיכום
תרגול 9
- ערימות בינומיות
- ערימות פיבונאצ'י
- סיכום
שבוע עשיריהרצאה 10לא התקיימה - בחירות!תרגול 10לא התקיים - כדי להישאר בסנכרון עם ההרצאה
שבוע אחת עשרההרצאה 11
אלגוריתמי מיון
quick sort - ניתוח
הוכחת חסם תחתון על ה worst case
תרגול 11
- ערימות פיבונאצ'י - סוף ניתוח זמן ריצה
אלגוריתמי מיון
quick sort - ניתוח
הוכחת חסם תחתון על ה worst case
תרגול 11
- מיונים
- הוכחת חסמים תחתונים
- רדוקציות לבעיית המיון
- סיכום
שבוע שתיים עשרההרצאה 12
כאשר המספרים הם מתוך תחום נתון - Bin sort
כאשר הקלט הוא מחרוזות באורך נתון - Radix sort
Finger RBTrees
select רנדומלי (בהסתמך על בחירת pivot, כמו ב quick sort)
הוכחת חסם מקרה ממוצע על select רנדומלי
תרגול 12
- מיון - חסם תחתון על ה average case
- מיונים "מהירים"
כאשר המספרים הם מתוך תחום נתון - Bin sort
כאשר הקלט הוא מחרוזות באורך נתון - Radix sort
- מיון קלט "כמעט ממוין"
Finger RBTrees
- selection - מציאת האיבר ה k במערך
select רנדומלי (בהסתמך על בחירת pivot, כמו ב quick sort)
הוכחת חסם מקרה ממוצע על select רנדומלי
תרגול 12
- מיונים מהירים
- רדוקציות לחיפוש בינארי
- סיכום
שבוע שלוש עשרההרצאה 13
Hash
hash סגור - rehash/cuckoo
hash פתוח - ניתוח ביצועים
hash יוניפורמי
משפחות אוניברסליות
תרגול 13
דינאמי - order statistics
- Select בזמן ליניארי (worst case)
- select דינאמי - order statistics
- מילון ללא יחס סדר:
Hash
- Hash:
hash סגור - rehash/cuckoo
hash פתוח - ניתוח ביצועים
hash יוניפורמי
משפחות אוניברסליות
תרגול 13
- selection
דינאמי - order statistics
שבוע ארבע עשרההרצאה 14
תרגול 14
- מציאת קבוצה אוניברסלית
- האש סגור, ניתוח זמן
- הגדלת טבלת ה hash
- Perfect Hashing
- מבוא ל union-find
- סיכום
תרגול 14
- Hash
- סיכום
