Data Structures (0368.2158)
Messages to Students: January 14, 07: Tomororw, Monday 15/1/07 THERE WILL BE A CLASS
Prof. Hanoch Levy (firstname.lastname@example.org)
Oded Schwartz (email@example.com)
Danny Feldman (firstname.lastname@example.org )
This page will be modified during the course, and will outline the classes
Intoduction to Algorithms, by Cormen, Leiserson and Rivest.
Data Structures and Algorithms, by Aho, Hopcroft and Ullman.
The course follows both books. Recommended purchase - first book (to be used by other courses).
The course will deal with data strucutres and their use in the design of efficient algorithms.
Subjects: Growth of functions and asymptotic notation; amortized analysis; recurrences: the substitution, master, and iteration methods; elementary strucutres: lists, stacks, queues; trees: ordered trees, binary trees, labeled trees and expression trees; set representation and manipulation; dictionary and hash tables; Perfect Hash. Search trees (Binary trees). Priority Queue (Heap). Union-Find DS. Balanced trees: 2-3 tree, B-Tree, AVL, Red-Black., Splay. Sorting and order statistics. Advanced topics if time permits (e.g. Blum Filter, Minimum-subject-to-constraint tree)
Tentative course outline. The actual order of the classes differs from this outline. The actual material may vary as well.
- Class 1 :
- Class 2 :
- Class 3 :
Elementary Structures: Lists, Stacks, Queues.
Doubling and amortized complexity.
- Class 4 :
Trees: basic concepts. Ordered tress, labeled trees, expression trees. Binary trees and Huffman Coding.
- Class 5 :
Dictionary and Hashing. Open and Closesd Hash. Expected value complexity analysis. Hash functions. Rehashing. Reorganization. Universal Hashing.
- Class 6:
Hash (continue): Perfect Hash.
- Class 7:
Multilist, sparse matrices, multiple-representation of data, Priority Queue (Heaps).
- Class 8:
Binary search trees
- Class 9 :
- Class 10 :
2-3 trees, B-trees, Merge-find trees
- Class 11 :
Merge-find trees (cont.). Near Constant Complexity. Sorting: Simple sort, Quick Sort (algorithm, worst-case and average complexity).
- Class 12 :
Sorting: Heap Sort and use for partial sort, bin sort. Order Statistics.
For a list of actual material covered so far click here
Copies of slides to be shown at during the semester:
File5 , File5-0405,File5-0607
File4 (2nd part - probability-0607)
Perfect-Hash , Perfect-Hash-new ,Perfect-Hash-0607
File6 , File6-0405 , File6-0607
RedBlack_tree , RedBlack-tree-0405 ,>RedBlack-tree-0607
Minimium subject-to constraint
Tirgul, homeworks and project
Details will be given in the Tirgul Home Page.
Last updated February 19, 2007