234218 Data Structures I Fall 1997

• Information Page (Postscript)
• Prerequisites
• Syllabus
• Staff (1997)
• Course Notes
  • Lecture Slides
  • Recitation Booklet
• Homework
• Tests from Previous Semesters
• Grades
  MOED A 1996
  • Statistics

• 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,
  • Bucket and Radix Sort.
• Hashing.
• Tries.
• Applications:
• Graphs:
  • Representations,
  • Toplogical Sort,
  • Mininimum Spanning Trees,
• Garbage Collection.

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

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 )

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
    1. Representations and Topological Sort
    2. Minimum Spanning Trees
12. Garbage collection

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