מבני נתונים

נהוג לאמר "מבנה נתונים טוב וקוד גרוע עדיפים בהרבה על ההיפך". אכן, כדי לפתור בעיות מאתגרות בצורה יעילה ואלגנטית, יש צורך בארגון חכם ונכון של הנתונים באמצעות מבני נתונים. מבני נתונים הוא תחום לימוד בסיסי במדעי המחשב ופיתוח תוכנה. בקורס נציג וננתח מבני נתונים קלאסיים ואלגוריתמים המתבססים עליהם. דגש מיוחד ינתן להבנת הקשר בין מבנה הנתונים והיעילות של האלגוריתמים שמשתמשים בו. הנושאים שנכסה במסגרת הקורס כוללים: סיבוכיות זמן ומקום: מקרה הטוב ביותר, הרע ביותר, הממוצע ו amortized analysis (ניתוח לשיעורין). נשתמש בחסמים O, Ω, Θ. בין מבני הנתונים שנלמד: רשימה מקושרת, מחסנית, תור, ערמה בינרית, עצי חיפוש בינארי, עצי AVL וכן b-trees, פונקציות ערבול, Disjoint Union / Find. בנוסף לאלגוריתמים הקשורים ישירות למבנה הנתונים, נלמד גם אלגוריתמי מיון מבוססי השוואות (מיון ערמה, quick sort, merge sort), מיונים בזמן לינארי (radix sort, counting sort and bucket sort), אלגוריתמים על סדר סטטיסטי (Ordered Statistics, מציאת חציון median-of-median algorithm). ספר הקורס: Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. קיים תרגום לעיברית של הספר בהוצאת האוניברסיטה הפתוחה.