Ch. 7 Flashcards
(11 cards)
Space-for-time algorithms
- Input enhancement - store extra information to be used later in problem solving i.e. counting sorts and string search
- Prestructuring - make accessing elements easier i.e. hashing or B-trees
Sorting by Counting
For each item, count how many items are less than the item, and that will be its final position.
O(n^2)
Distribution Counting Sort
- Count # of items of each value
- Count the # of items ≤ each value
- Move all items to their exact final position
Horspool’s Algorithm
Search for a string pattern within a text:
- Preprocess the pattern to generate a shift table that determines how much to shift the pattern when a mismatch occurs.
- Always makes a shift based on the text’s character c aligned with the last character in the pattern.
Boyer-Moore Algorithm
Search for a string pattern within a text:
- Create a bad-symbol table for how much to shift upon a mismatch
- Create a good-suffix table for how much to shift based on the matched part of the pattern.
Hashing
Very efficient method for implementing a dictionary. Map keys of a given file of size n into a table of size m using a predefined hash function.
Collisions
Two different keys have the same hash address.
Open Hashing
Each cell is a header of a linked list of all keys hashed to it.
Closed hashing
- One key per cell
- In case of collision, find another cell by linear probing or double hashing
- Only works if table size m ≥ number of keys n
Linear probing
Occupy the next available cell, and wrap back to the beginning of the table when the end is reached.
B-tree
Similar to 2-3 tree, but each node may have up to m children in an m-way tree.
1. Number of keys in each non-leaf node is one less than the number of its children.
2. All non-leaf nodes except root have at least ⌈m/2⌉ children
3. Root is a leaf or has anywhere from two to m children.
4. Leaf node has no more than m-1 keys.
5. m must be odd.
