Data Structures (0368.2158)
Instructors:
Prof. Hanoch Levy
(hanoch@math.tau.ac.il)
Dr. Tova Milo
(milo@math.tau.ac.il)
Teaching Assistants:
Oded Schwartz
(odeds@math.tau.ac.il)
Eran Halperin
(heran@math.tau.ac.il)
This page will be modified during the course, and will outline
the classes
Text books:
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).
Course syllabus:
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.
Tentative course outline. The actual order of the classes differs
from this outline. The actual material may vary as well.
-
Class 1 :
Introduction
Recursion (review)
-
Class 2 :
Complexity
Master Theorem
-
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 :
Red-Black Trees.
-
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.
http://www.cs.tau.ac.il/~baraksoreq/hanoch_site/Courses/ds.01-02.html
For a list of actual material covered so far click here
Copies of slides to be shown at during the semester:
File5
File6
RedBlack Tree
Perfect Hash
Splay Hash
Tirgul, homeworks and project
Details will be given in the Tirgul Home Page.
Last updated February 6, 2000
redesigned by barak soreq