# 234218 Data
Structures I summer 2005

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:
- Sorting:
- Naive methods,
- The Lower bound,
- Quick Sort,
- Heap Sort,
- Bucket and Radix Sort.

- Hashing.
- Tries.
- Applications:
- Graphs:
- Representations,
- Toplogical Sort,
- Mininimum Spanning
Trees,

- Garbage Collection.

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

**Instructors:**

Prof. Alon Itai (```
itai@cs.technion.ac.il
```

)

PostScript, in Hebrew.

Copyright © 2005 by Alon Itai .

- Introduction
- Big
O
- Arrays
- Lists
- Randomized Skip Lists
- Queues,
Stacks
- Trees
- Definitions
- Average time to Constuct a Binary Tree
- AVL
trees
- Deterministic Skip Lists
- Union/Find

- Sorting

recursive and iterative tree search
- Hashing
- Tries
- Graphs
- Representations and Topological Sort
- Minimum
Spanning Trees

- Garbage
collection

Recitation Booklet

### Recitation Booklet

PostScript, in Hebrew.

.

- Class
Excercise 1
- Class
Excercise 2
- Class
Excercise 3
- Class
Excercise 4

· Exercise 1

· Exercise 2
Solution

__·
Exercise
3__ Solution

__·
Computer
Homework 1__

· Computer
Homework 2

PostScript, in Hebrew; some include solutions.