מבני נתונים ואלגוריתמים
  Data Structures and Algorithms

0512.2510

צוות הקורס:
 

מרצה:  פרופ' דנה רון, danaron@tau.ac.il, בניין "הנדסת תוכנה", 201.

מתרגלות:  לירון דוד, lirondavid@gmail.com,  בניין "הנדסת תכנה",  313.
                 טליה עדן, talyaa01@gmail.com,  בניין "הנדסת תכנה", 210.
           

בודקי תרגילים:   לילך בן-זקן,  benzakon@mail.tau.ac.il,  עידן גדנסקי, idangdanski@mail.tau.ac.il, בועז פיש boazfish@mail.tau.ac.il,

שעות קבלה: בתיאום מראש בדואר אלקטרוני.

אתר הקורס:  הכניסה דרך אתר Moodle: http://moodle.tau.ac.il                                          

נושאים:

• הקדמה: חיפוש איבר במערך ממוין, חיפוש בינארי.  הגדרת סדר הגודל של פונקציה.

        ניתוח נכונות וזמן ריצה של אלגוריתמים.

• בעיית המיון (Sorting): מיון הכנסה (Insertion Sort).  מיון מיזוג (Merge Sort). מיון "מהיר" ((Quick Sort . חסם תחתון למיון במודל ההשוואות ומושג עץ ההכרעה (Decision Tree). מיון  "ספירה" (Counting Sort).
• טיפוסי נתונים מופשטים (Abstract Data Types) ומבני נתונים: מחסנית ותור. תור קדימויות וממוש ע"י ערימה (Heap). עצי חיפוש בינאריים ועצי 2-3. טבלאות ערבול. קבוצות זרות.
• טכניקות אלגוריתמיות: פרדיגמת "הפרד ומשול"  (Divide and Conquer).   אלגוריתמים חמדניים (Greedy Algorithms). תכנון דינאמי (Dynamic Programming).
• אלגוריתמים על גרפים: ייצוג גרפים. חיפוש על גרפים, זרימה ברשתות, עץ פורש עם משקל מינימאלי.

ספרות:

ספר הקורס הוא:          1. Introduction to Algorithms,  Corman, Leiserson, and Rivest (CLR)

לספר ישנן גרסאות ומהדורות רבות, וכן תרגום לעברית (של האוניברסיטה הפתוחה). אין חשיבות מיוחדת לגרסה או למהדורה.  
ספר נוסף:                       2. Data Structures and Algorithms,  Aho, Hopcroft, and Ullman (AHU)

מרכיבי הציון

• תרגילים עיוניים: 10% מהציון הסופי. יינתן תרגיל כל שבוע או שבועיים.
• מבחן סוף סמסטר: 90% מהציון הסופי

Data Structures and Algorithms

0512.2510

Lecturer: Prof. Dana Ron, danaron@tau.ac.il, “Software Engineering” building, room 201

Teaching Assistants:
      Liron David,  lirondavid@gmail.com,  “Software Engineering” building, room 313
      Talya Eden,  talyaa01@gmail.com,  “Software Engineering” building, room 210

Graders:
       Lilach Ben-Zakon,  benzakon@mail.tau.ac.il,  Idan Gdanski,  idangdanski@mail.tau.ac.il
       Boaz Fish, boazfish@mail.tau.ac.il

Office hours shold be coordinated by email

Course website: access through Moodle - http://moodle.tau.ac.il  

Subjects covered in the course

• Introduction: Searching in a sorted array, Binary search. Asymptotic notations. Analysis of correctness and running time of algorithms.
• Sorting: Insertion Sort, Merge Sort, Quick Sort. Lower bound for sorting in the comparison model and the notion of a Decision Tree. Counting Sort.
• Abstract Data Types and Data Structures: Stack and Queue, Priority Queue and its implementation by a Heap, Binary Search Trees and 2-3 Trees, Hash tables, Union-Find (disjoint sets).
• Algorithmic techniques: Divide and Conquer, Greedy algorithms, Dynamic Programming.
• Graph algorithms: Represenation of graphs, searching on graphs, Network Flow, Minimim Weight Spanning Tree (MST).

Textbooks

• Introduction to Algorithms (2^nd ed.),  Corman, Leiserson, Rivest, Stein (or Introduction to Algorithms (1^sted.),  Corman, Leiserson, Rivest                     (
• Data Structures and Algorithms,  Aho, Hopcroft, and Ullman

 The final grade of the course is based on 10% homework assignments (given weekly or biweekly), and 90% final exam.