# 234218 Data Structures I Fall 1997

## Prerequisites

234122 MATAM and (234144 Discrete Mathematics or 104286 Combinatorics)

## Syllabus

• Intoduction:
• Data structures, definition vs. implementations,
• Computational complexity and big O notation.
• Arrays.
• Lists:
• Linear Lists,
• General List Structures,
• Skip Lists.
• Queues and Stacks.
• Representations of Queues and Stacks,
• Postfix notation,
• Run-time Stack and Recursion.
• Trees:
• Definition, properties, traversal,
• Search Trees,
• AVL Trees,
• 2-3 Trees,
• Deterministic Skip Lists.
• Sets:
• Union/Find.
• Sorting:
• Naive methods,
• The Lower bound,
• Quick Sort,
• Heap Sort,
• Hashing.
• Tries.
• Applications:
• Graphs:
• Representations,
• Toplogical Sort,
• Mininimum Spanning Trees,
• Garbage Collection.

## Bibliography

1. Harry Lewis and Larry Denenberg, Data structures & their algorithms, Harper Collins, 1991.
2. Cormen, Leiserson and Rivest, Introduction to Algorithms, McGraw-Hill, 1990.

## Staff

Instructors:
Prof. Alon Itai (``` itai@cs.technion.ac.il ```)
Prof. Benny Chor (``` benny@cs.technion.ac.il ```)

Assistants:
Maria Zapolotsky Office 303C, phone 829 -4362 (``` zmaria@cs.technion.ac.il ```)
Niv Gilboa (``` gilboa@cs.technion.ac.il ```)
Oleg Ledeniov (``` olleg@cs.technion.ac.il ```)
Dmitry Levinson (``` dlevy@cs.technion.ac.il ```)

## Course Notes

### Lecture Slides

PostScript, in Hebrew.
1. Introduction
2. Big O
3. Arrays
4. Lists
5. Randomized Skip Lists
6. Queues, Stacks
7. Trees
1. Definitions
2. Average time to Constuct a Binary Tree
3. AVL trees
4. Deterministic Skip Lists
5. Union/Find (only representation #4)
8. Sorting
recursive and iterative tree search
9. Hashing
10. Tries
11. Graphs
12. Garbage collection

Recitation Booklet

### Recitation Booklet

PostScript, in Hebrew.
.

## Homework

• Exercise 1
• Exercise 2 Solution
• Exercise 3 Solution
• Computer Homework 1
• Computer Homework 2

• ## Tests from Previous Semesters

PostScript, in Hebrew; some include solutions.