Chapter 24: Lookup Tables and Hashing

(IV Standard Data Structures, V Standard Algorithms)

Name a way to retrieve data faster than a binary search. a lookup or hash table

1. Explain how lookup tables work.
   • implements a map
   • the key is converted either directly or through some simple formula to an integer
   • the integer is used as the index of an array

2. List the properties of a good hash table
   • easy to calculate
   • map all values into a range that is not too large
   • cover the range uniformly and avoid collisions

3. State the 2 principle ways of avoiding collisions with a hash table.
   • chaining--implementing a bucket using a chining technique such as a binary search tree
   • probing-- using a function to sort the the colliding value into a different spot on the table.

4. Name a disadvantage of a hash table over a binary search tree or sorted list. It's difficult to quickly travese the table in ascending order of keys.
5. Correctly use java .util's HashSet and HashMap classes.

Homefun: Read Chapter 18; Exercises  5, 6, 7

Programming Assignments: Lab 24.3 Cryptogram Solver, Lab 24.6 Search Engine

Test: Chap 24

Chapter 25: Heaps and Priority Queues

(IV Standard Data Structures, V Standard Algorithms)

1. Define the following terms
   • full binary tree
   • complete binary tree
   • heap.
   • min-heap
   • max-heap.

2. Correctly implement a heap.
3. Correctly implement a heap as a priority queue.
4. Correctly use Heapsort.

Homefun: Read Chapter 18; Exercises 1, 2, 3

Programming Assignments: Lab 25.4 A Do-It-Your-Self Priority Queue, Lab 25.5 Heapsort

Test: Chap 18 Objectives 1-5

Special Topics

Imbedded Processors

Assignment:

1.      Program the Javalin stamp so that it blinks the LED.

2.      Add a transceiver so that the Javalin stamp sends a request to blink the LSD across the room wirelessly