Data Structures (0368.2158)
Prof. Yossi Matias
This page will be modified during the course, and will outline
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.
Growth of functions and asymptotic notation;
recurrences: the substitution, master, and iteration methods;
elementary strucutres: lists, stacks, queues;
trees: ordered trees, binary trees, labeled trees and
set representation and manipulation;
dictionary and hash tables.
Tentative course outline
For a list of actual material covered so far click here
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.
Hash (continue): Perfect Hash.
Multilist, sparse matrices,
multiple-representation of data,
Priority Queue (Heaps).
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.
These are partial set of course notes (PowerPoint presentation in Hebrew).
(Note: these notes may change during the semester.)
The final grade will be composed of the following:
Final Exam: 90%,
Project: 10%. The project is mandatory.
Homework assignments: Submission of at least 80% of the assignment is mandatory.
Tirgul, homeworks and project
Details will be given in the
Tirgul Home Page.
Last updated March 12, 2002