Transform & Conquer
Transform & Conquer
Definition
Transform & Conquer is a general algorithm design technique which works in two stages.
STAGE 1: (Transformation stage): The problem’s instance is modified, more amenable to solution
STAGE 2: (Conquering stage): The transformed problem is solved
The three major variations of the transform & conquer differ by the way a given instance is transformed:
1. INSTANCE SIMPLIFICATION: Transformation of an instance of a problem to an instance of the same problem with some special property that makes the problem easier to solve.
Example: list pre-sorting, AVL trees
2. REPRESENTATION CHANGE: Changing one representation of a problem’s instance into another representation of the same instance.
Example: 2-3 trees, heaps and heapsort
3. PROBLEM REDUCTION: Transforming a problem given to another problem that can be solved by a known algorithm.
Example: reduction to graph problems, reduction to linear programming
Presorting
• Presorting is an example for instance simplification.
• Many questions about lists are easier to answer if the lists are sorted.
• Time efficiency of the problem’s algorithm is dominated by the algorithm used for sorting the list.
NOTE:
No comparison based sorting algorithm can has a better efficiency than nlogn in the worst case
Example: Problem of checking element uniqueness in an array:
• Limitation of brute-force algorithm:
Compares pairs of the array’s elements until either two equal elements are found or no more pairs were left. Worst case efficiency = Θ(n2)
• Using presorting:
Presorting helps to sort the array first and then check only its consecutive elements: if the array has equal elements, a pair of them must be next to each other
ALGORITHM PresortElementUniqueness( a[0…n-1])
//solves the element uniqueness problem by sorting the array first
//i/p: An array A of orderable elements
//o/p: Returns “true” if A has no equal elements, “false” otherwise
Analysis:
• Input size: n – array size
• Basic operation: key comparison
• Running time = sum of the time spent on sorting AND time spent on checking consecutive elements.
Therefore:
Example: Searching problem
• Brute-force solution:
Sequential search using brute-force methods needs n comparisons in the worst case, Worst case efficiency = Θ(n)
• Using presorting:
Presorting sorts the array first and then even if binary search is applied to search the key, the running time is:
Running time = time required to sort the array + time required to search the key using binary search
NOTE:
Using presorting, the solution is inferior to sequential search using brute force. BUT if the list is searched many number of times, then presorting is advantageous.
Comments
Post a Comment