Data Structures (0368.2158)
Messages to Students:
The exam on July 25 will be with closed books
Instructors:
Prof. Hanoch Levy
(hanoch@math.tau.ac.il)
Dr. Yossi Matias
(matias+ds@math.tau.ac.il)
Teaching Assistants:
Guy Kindler
(puzne@math.tau.ac.il)
Eran Halperin
(heran@math.tau.ac.il)
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:
Groth 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

Class 1 :
Introduction
Recursion (review)

Class 2 :
Complexity
Master Theorem

Class 3 :
Elementary Structures: Lists, Stacks, Queues.

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.
Doubling.

Class 6:
Hash (continue): Perfect Hash, Doubling.

Class 7:
Multilist, sparse matrices,
multiplerepresentation of data,
Priority Queue (Heaps).

Class 8:
Binary search trees

Class 9 :
RedBlack Trees.

Class 10 :
23 trees, Btrees, Mergefind trees

Class 11 :
Mergefind trees (cont.). Near Constant Complexity. Sorting:
Simple sort, Quick Sort (algorithm, worstcase 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
Course material
These are partial set of course notes (PowerPoint presentation in Hebrew).
Grades:
The final grade will be composed of the following:
Final Exam: 80%, Homework assignments: 10%, Final project: 10%.
Tirgul, homeworks and project
Details will be given in the
Tirgul Home Page.
Messages to Students:
The exam on July 25 will be with closed books
Last updated Decmeber 8, 1998