234218 Data Structures I summer 2005


Prerequisites

234122 MATAM and (234144 Discrete Mathematics or 104286 Combinatorics)

Syllabus


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 )


Course Notes

Lecture Slides

PostScript, in Hebrew.
Copyright © 2005 by Alon Itai .

  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
  8. Sorting
    recursive and iterative tree search
  9. Hashing
  10. Tries
  11. Graphs
    1. Representations and Topological Sort
    2. Minimum Spanning Trees
  12. Garbage collection

Recitation Booklet

Recitation Booklet

PostScript, in Hebrew.
.

  1. Class Excercise 1
  2. Class Excercise 2
  3. Class Excercise 3
  4. Class Excercise 4

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.