## Data Structures (0368.2158)

Messages to Students: The exam on July 25 will be with closed books

### Instructors:

Prof. Hanoch Levy (hanoch@math.tau.ac.il)
Dr. Yossi Matias (matias+ds@math.tau.ac.il)

### Teaching Assistants:

Guy Kindler (puzne@math.tau.ac.il)
Eran Halperin (heran@math.tau.ac.il)

### Text books:

Intoduction to Algorithms, by Cormen, Leiserson and Rivest.
Data Structures and Algorithms, by Aho, Hopcroft and Ullman.
The course follows both books. Recommended purchase - first book (to be used by other courses).

### Course syllabus:

The course will deal with data strucutres and their use in the design of efficient algorithms.
Subjects: Groth of functions and asymptotic notation; amortized analysis; recurrences: the substitution, master, and iteration methods; elementary strucutres: lists, stacks, queues; trees: ordered trees, binary trees, labeled trees and expression trees; set representation and manipulation; dictionary and hash tables.

### Tentative course outline

• Class 1 :
Introduction
Recursion (review)
• Class 2 :
Complexity
Master Theorem
• Class 3 :
Elementary Structures: Lists, Stacks, Queues.
• Class 4 :
Trees: basic concepts. Ordered tress, labeled trees, expression trees. Binary trees and Huffman Coding.
• Class 5 :
Dictionary and Hashing. Open and Closesd Hash. Expected value complexity analysis. Hash functions. Rehashing. Reorganization. Universal Hashing. Doubling.
• Class 6:
Hash (continue): Perfect Hash, Doubling.
• Class 7:
Multilist, sparse matrices, multiple-representation of data, Priority Queue (Heaps).
• Class 8:
Binary search trees
• Class 9 :
Red-Black Trees.
• Class 10 :
2-3 trees, B-trees, Merge-find trees
• Class 11 :
Merge-find trees (cont.). Near Constant Complexity. Sorting: Simple sort, Quick Sort (algorithm, worst-case and average complexity).
• Class 12 :
Sorting: Heap Sort and use for partial sort, bin sort. Order Statistics.

### Course material

These are partial set of course notes (PowerPoint presentation in Hebrew).

The final grade will be composed of the following:
Final Exam: 80%, Homework assignments: 10%, Final project: 10%.

### Tirgul, homeworks and project

Messages to Students: The exam on July 25 will be with closed books