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 (Inorder, Preorder, Postorder).

Class 5 :
Tree (cont.).
Expression trees.
Binary trees. Huffman Code.
Data Structures for Sets. Dictionary. Storing sets in bitvector,
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.
23 Trees.
BTrees.

Class 10 :
Mergefind 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. RedBlack Trees.

Class 13:
Perfect hashing (handouts available in
postscript
or
pdf).
Last updated January 20 , 2000