Instance Simplification: Transform to simpler instance of same problem.
Example — Presorting an array will make many problems easier (searching, median, uniqueness).
- This applies also to topological sort and many geometric algorithms.
Representation Change: Different representation of same instance.
Problem Reduction:
Sorting is important for lots of algorithms, which means the efficiency of the sort is super important.
Factoid — The fastest sorting algorithm in the world is n \log n
Q: Search for k in A[0..n-1]
A:
We can first sort A, and then do a binary search.
\text{Sort} + \text{Binary Search} = n \log n + \log n
Q: Determine if A[0..n-1] has unique elements.
A:
Sort, then scary array to check pairs of adjacent elements.
\text{Sort} + \text{Check Pairs} = O(n \log n) + O(n)
Q: Given a set of keys S and a search keyk, find and occurrence of k in S, if any.
Real-World Uses — File size, dynamic of data.
A: ???
Suppose we implement a dictionary with a BST.
Recall — Efficiency depends on tree’s height.
Efficiency:
Recall — BST works worst on unbalanced trees. This is problematic if our operations gradually make our tree worse.
Solutions:
- AVL
- red-black
- 2-3
- 2-3-4
- ???
AVL Tree: BST in which, for every node, the difference between the heights of its right and left subtrees (balance factor) is at most 1.
Note — Height of empty tree defined as -1.
Balance Factor Examples: