## Data Structures (0368.2158)

### Instructors:

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

### The material covered during the semester (First semester 1998/9):

• Class 1 :
Introduction
Recursion (review)
From problems to algorithms to computer programs
Pseudo Language
Complexity (started)
[Cormen: Chapter 1].
• Class 2 :
Complexity (finished), recurrences, Master Theorem.
[Cormen Ch. 2, 3, 4] Lists (started).
[Cormen 11].
• Class 3 :
Elementary Data Structures: Lists (abstract), array implementation, linked list, double linked list, cursors, stacks, queues. The use of stacks for recursion implementation.
The doubling method for maintaining dynamic tables. Amortized complexity and the accounting method.
Trees: Definitions.
• Class 4 :
Trees: Ordered trees, Tree traversal (In-order, Preorder, Postorder). Expression trees. Binary trees. Huffman Code.
Data Structures for Sets. Dictionary. Storing sets in bit-vector, in linked list, in array.
Advanced dictionary representation: Hash table. Closed (open addressing) hash, Open (chaining) Hash. Average complexity of open hash.
• Class 5 :
Hash tables cont.: Average complexity of closed hash, rehashing functions, universal hashing.
Heaps.
• Class 6:
Sorting: bubble sort (worst case & average case analysis), insertion sort, selection sort (swap analysis vs comparisons), quicksort - worst case & average case analysis. discussion on upper and lower bounds in algorithms.
• Class 7:
Completion of heaps.
• Class 8:
Count sort, bin-sort, radix sort. Order statistics.
• Class 9 :
Completion of order statistics. 2-3 trees.
• Class 10 :
Completion of 2-3 trees. B-trees. Red-Black Trees.
• Class 11 :
Merge-find trees. Perfect hashing (handouts available in postscript or pdf).
• Class 12 :