Data Structures (0368.2158)
Prof. Hanoch Levy
Dr. Yossi Matias
The material covered during the semester (First semester 1999/00):
Class 1 :
From problems to algorithms to computer programs
[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.
Class 4 :
The doubling method for maintaining dynamic tables.
Amortized complexity and the accounting method.
Trees: Ordered trees,
Tree traversal (In-order, Preorder, Postorder).
Class 5 :
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.