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.