Unit 5: Reductions and branch and bound Flashcards
Hashing
Alternative data structure for the dictionary problem.
Observation: Usually only a small subset of all possible keys is stored.
Idea: Instead of searching through a set of data elements using key comparisons, one can calculate the (exact) position of an element in storage (usually an array) by using arithmetic operations.
Hashing: basics
Hash table
- We assume that the hash table
Thas a fixed sizemand uses an array with indices0, ..., m-1. - For a hash table of size
mthat currently storesnkeys (elements), we denote α = n/m its load factor.
Load factor
For a hash table of size m that currently stores n keys (elements), we denote its load factor:
α = n/m
Hashing: basics
Hash function
We choose a hash function h: K → {0, ..., m-1} that assigns every key k ∈ K a unique hash value.
(however, more than one key can be assigned the same hash value)
Advantages of hashing
Runtime for the operations search, insert and remove is constant Θ(1) in the ideal case and assuming that h(s) can be calculated in constant time.
3 Limitations of hashing
- Whenever
h(k) = h(k')fork≠k', i.e. two distinct keys obtain the same hash value, we say that we have a collision. -
Θ(1)d only holds if we assume that the number of collisions is negligible. - Worst-case runtime is still
O(n)
2 Characteristics of a “good” hash function
- The aim is a uniform distribution of the used keys to the bucekts
0, ..., m-1of the hash table. - Small changes to the keys should lead to a distinct and possible independent hash value.
Hash functions
Modulo method
Assumption: k∈N (keys are natural numbers.
Calculation: h(k) = k mod m
Hash functions
Properties of the Modulo method
Properties:
- the hash function can be calculated very efficiently.
- the right choice of m is very important. To ensure uniformity, a good choice for m is usually a prime number.
Modulo method
Bad choices for m
-
m = 2ⁱ: Only the lastibits play a role. -
m = 10ⁱ: Analogously for decimal numbers. -
m = rⁱ: Analogously forr-adic numbers. -
m = rⁱ ± jfor smalljcan be problematic.’’’
’’’ e.g. m = 2⁷ - 1 = 127 . p=112 in ASCII.h("pt") = (112 · 128 + 116) mod 127 = 14452 mod 127 = 101h("tp") = (116 · 128 + 112) mod 127 = 14960 mod 127 = 101
(Keys with different ordering of the same letters obtain the same hash value)
Hash functions
Multiplication method
Assume k∈N.
Let A be an irrational number.
Calculation:h(k) = ⌊m (k · A - ⌊ k · A ⌋) ⌋
- The key is mutiplied with
Aand only the fractional part is kept. - This provides a value in
[0, 1), which is multiplied with the table sizemand rounded.
Observation that confirms uniformity: For a sequence 1, 2, 3, …, i of keys it holds that k · A - ⌊ k · A ⌋ of the next key k=i+1 always lies in a largest interval of the values of the previous keys, 0 and 1.
Multiplication method: choice for A
In general: the choice of m is not of importance as long as A is an irrational number.
Best choice for A: The golden ratio
A = ɸ⁻¹ = (√5 - 1) / 2
ɸ⁻¹ = limₙ
Open hashing: idea
All elements are directly placed into the array, every slot in the array is marked with a flag
fᵢ ∈ {free, used, free again}
Handling of collisions:
If a slot is used, consider other slots in a certain predefined order (probing).
Open hashing: probing
- Every slot
i=0, 1, ..., m-1is marked by a flagfᵢ ∈ {free, used, free again{. -
fᵢ = freefor everyiin the initial hash table. - At insertion, the new element will be added at the first slot marked with
freeorfree again, the flag is then updated toused. - The search iterates the slots until the key is found or a slot is marked with
free(in which case the key is not there). - After removal of an element, the flag is set to
free again.
Linear probing
Given: a normal hash functionh': K → {0, 1, ..., m-1}
Linear probing: For every i = 0, 1, ..., m-1, we set:h(k, i) = (h'(k) + i) mod m
Linear probing: problems
Problems:
- After insertions, the probability for a new key to be inserted at a certain slot becomes non-uniform.
- After a slot is used, the probability for the insertion of a key at the next slot changes.
- Long consecutive sequences of used slots have a tendency to grow faster than shorter ones.
- This effect amplifies, since long sequences combine more easily to create even longer ones.
- As a consequence of this phenomenon (primary clustering), the efficiency of the hash table deteriorates drastically once the load factor
⍺gets closer to 1.
Quadratic probing
Idea: To avoid the primary clustering of linear probing, quadratic probing uses a quadratically growing distance to probe a new slot.
Given: A normal hash function:h': K → {0, 1, ..., m-1}
Quadratic probing: probing function:h(k, i) = (h'(k) + c₁i + c₂i²) mod m
Here c₁ and c₂ are carefully chosen constants.
Double hashing
Idea: The efficiency of uniform probing can already be almost achieved if one uses a second hash function instead of a randomized probing order.
Given: 2 hash functions:
h₁, h₂: K → {0, 1, ..., m-1}
Double hashing: We set (for i = 0, 1, ..., m-1):
h(k, i) = (h₁(k) + ih₂(k)) mod m
Choice of h₂(k): The probing order must reach all slots 0, ..., m for every key k. This implies that h₂(k) ≠ 0 and that it must not divide
Á la Brent
Idea: If at insertion of a key, a probed slot j is used with k' = T[j].key, then set:j₁ = ( j + h₂(k) ) mod mj₂ = ( j + h₂(k') ) mod m
If j₁ is used but j₂ is free, move k' to j₂ to make space for k at j.
Analysis of Brent’s improvement
Number of probes: On average (for large m and n):
- Unsuccessful search ≃ 1 / (1 - ɑ)
- Successful search < 2.5 (independent ɑ for ɑ ≤ 1)
Advantage: Average time for a successful search is constant even in the extreme event that ɑ = 1.
Open Hashing
Suitability and reorganization
- Open hashing methods only allow a load factor of at most 1.
- Load factors close to 1 are in general bad, since the number of probing steps can get very large.
- If necessary, a reorganisation is required, i.e. completely new hash table (e.g. with double the size) is populated if more elements need to be stored than originally anticipated.
- Open hashing methods are usually well-suited whenever the number of elements to be stored is known in advance and elements are rarely or not at all removed.
Tractable problems
We say that a problem is efficiently solvable, if it can be solved in polynomial time.
I.e. for such a problem, there is a O(n^c) algorithm, where:
-
n= input size -
c= constant
Efficiently solvable problems are also referred to as tractable problems.
Cobham-Edmonds Assumption
- The assumption that tractability can be considered the same as solvability in polinomial time.
- Pioneered by Alan Cobham and Jack Edmonds, who proposed this assumption in the 1960s.
- The assumption has become the predominant assumption in computer science over the last 50 years.
Cobham-Edmonds Assumption
Justification
- In practice, polynomial time algorithms usually have small constants and exponents (e.g. linear, quadratic, or cubic)
- Overcoming the exponential bound of brute-force algorithms usually goes hand-in-hand with significant structural and combinatorial insights into the problem.
Cobham-Edmonds Assumption
Exceptions and Criticism
- Some polynomial time algorithms have huge constants and exponents and are considered useless in practice.
- Some exponential time algorithms are considered highly useful in practice since their worst-case pehaviour only occurs rarely or the problem instances are sufficiently small.
- For huge datasets, even linear time algorithms may be too slow.
Decision problem
- A problem whose solution is either YES or NO
- In contrast to functional or optimization problems that return a solution or set of solutions.
- Typically: every functional or optimization problem has a natural corresponding decision problem and vice versa.
Define
Polynomial time reduction
A polynomial time reduction from a problem X to a problem Y is an algorithm A that - for every instance x of X computes an instance y of Y such that:
-
xis a YES-instance ofXif and only ifyis a YES-instance ofY(equivalence). -
Aruns in polynomial time, i.e. there is a constantcsuch that given an instancexofXwith sizen,Acomputes the corresponding instanceyofYin timeO(n^c)
We write X ≤ pY if there is a polynomial time reduction from X → Y
X ≤ pY intuition
If X ≤ pY, “X can be polynomially reduced to Y”, then intuitively
“Y is at least as hard as X”
