Data Structures (0368.2158)
Prof. Hanoch Levy
Dr. Yossi Matias
The material covered during the semester (First semester 1998/9):
Class 1 :
From problems to algorithms to computer programs
[Cormen: Chapter 1].
Class 2 :
Complexity (finished), 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.
The doubling method for maintaining dynamic tables.
Amortized complexity and the accounting method.
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.
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.
Completion of heaps.
Count sort, bin-sort, radix sort. Order statistics.
Class 9 :
Completion of order statistics.
Class 10 :
Completion of 2-3 trees. B-trees. Red-Black Trees.
Class 11 :
Merge-find trees. Perfect hashing (handouts available in
Class 12 :