Unit 1 Dictionaries

6 lecture hours

• Dictionary Abstract Data Type
• Implementation of Dictionaries
• Hashing: Review of Hashing
• Hash Function
• Collision Resolution Techniques in Hashing
• Separate Chaining
• Open Addressing
• Linear Probing
• Quadratic Probing
• Double Hashing
• Extendible Hashing

Unit 2 Skip Lists

5 lecture hours

• Need for Randomizing Data Structures and Algorithms
• Search and Update Operations on Skip Lists
• Probabilistic Analysis of Skip Lists
• Deterministic Skip Lists

Unit 3 Trees

• Binary Search Trees
• AVL Trees
• Red Black Trees
• Splay Trees 08 19

Unit 4 Text Processing

11 lecture hours

• Sting Operations
• Brute-Force Pattern Matching
• The Boyer- Moore Algorithm
• The Knuth-Morris-Pratt Algorithm
• Standard Tries
• Compressed Tries
• Suffix Tries
• The Huffman Coding Algorithm
• The Longest Common Subsequence Problem (LCS)
• Applying Dynamic Programming to the LCS Problem

Unit 5 Computational Geometry

10 lecture hours

• One Dimensional Range Searching
• Two Dimensional Range Searching
• Constructing a Priority Search Tree
• Searching a Priority Search Tree
• Priority Range Trees

Unit 6 Recent Trends in Hashing, Trees, and various computational geometry

• methods for efficiently solving the new evolving problem 05 10