## 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 1999/00):

• Class 1 :
Introduction
Recursion (review)
From problems to algorithms to computer programs
Pseudo Language
[Cormen: Chapter 1].
• Class 2 :
Complexity , recurrences, Master Theorem.
[Cormen Ch. 2, 3, 4]
• Class 3 :
Elementary Data Structures: Lists (abstract), array implementation, linked list, double linked list, cursors, stacks, queues. The use of stacks for recursion implementation. [Cormen 11].
• Class 4 :
The doubling method for maintaining dynamic tables. Amortized complexity and the accounting method. Trees: Definitions. Trees: Ordered trees, Tree traversal (In-order, Preorder, Postorder).
• Class 5 :
Tree (cont.). 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.
Class 6 :
Hash Table (cont.). Closed (open addressing) hash, Open (chaining) Hash. Average complexity of open hash.
• Class 7 :
Hash tables cont.: Average complexity of closed hash, rehashing functions, universal hashing.
Heaps.
• Class 8:
Heaps (cont.). Multilists. Combined data structures. Binary search trees.
• Class 9:
Average search time in Binary Search Trees. 2-3 Trees. B-Trees.
• Class 10 :
Merge-find trees. Near Constant Complexity. Sorting: bubble sort (worst case & average case analysis), insertion sort, selection sort (swap analysis vs comparisons), quicksort - worst case & average case analysis. Heapsort and use for partial sort.
• Class 11 :
Merge Sort (iterative vs recursion), Count sort, Bin sort, Radix Sort, discussion on upper and lower bounds in algorithms, lower bound for sorting.
• Class 12:
Order Statistics. Red-Black Trees.
• Class 13:
Perfect hashing (handouts available in postscript or pdf).