## Data Structures (0368.2158)

### Messages to Students:

### Instructors:

Prof. Hanoch Levy (hanoch@cs.tau.ac.il)

### Teaching Assistants:

Oded Schwartz (odedsc@cs.tau.ac.il) Assaf Shapira (asafico@post.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.

For a list of actual material covered so far click here

Copies of slides to be shown at during the semester:

File1

File2

File3

File4

File5 , File5-new

File6 , File6-new

RedBlack_tree , RedBlack-tree-new

Perfect-Hash , Perfect-Hash-new

Splay-tree , Splay-tree--new

### Tirgul, homeworks and project

Details will be given in the Tirgul Home Page.

### Last updated October 12, 2002

redesigned by barak soreq