KEMBAR78
Transform and Conquer, Presorting | PDF | Time Complexity | Algorithms And Data Structures
Scribd
Upload
299 views2 pages

Transform and Conquer, Presorting

The document discusses the concept of transform-and-conquer, which involves modifying a problem's instance to facilitate its solution, with variations including instance simplification, representation change, and problem reduction. It highlights the technique of presorting, which improves the efficiency of algorithms by sorting lists before further operations, and provides examples of its application in checking element uniqueness, computing a mode, and searching for values. The document also outlines the efficiency of various sorting algorithms and their relevance in different problem-solving contexts.

Uploaded by

hima bindu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
299 views2 pages

Transform and Conquer, Presorting

The document discusses the concept of transform-and-conquer, which involves modifying a problem's instance to facilitate its solution, with variations including instance simplification, representation change, and problem reduction. It highlights the technique of presorting, which improves the efficiency of algorithms by sorting lists before further operations, and provides examples of its application in checking element uniqueness, computing a mode, and searching for values. The document also outlines the efficiency of various sorting algorithms and their relevance in different problem-solving contexts.

Uploaded by

hima bindu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Unit-III

Transform and Conquer: Presorting, heapsort, Problem Reduction


Space and Time Tradeoffs: Sorting by counting, Naïve string matching, Input enhancement in
string Matching: Horspool’s and Boyer-Moore algorithm.

Transform-and-conquer
Transform-and-conquer method works as two-stage procedure. First, in the transformation
stage, the problem’s instance is modified to be more amenable to solution. Then, in the
second or conquering stage, it is solved.

There are three major variations of transform and conquer:


1. Transformation to a simpler or more convenient instance of the same problem—we call
it instance simplification.
2. Transformation to a different representation of the same instance—we call it
representation change.
3. Transformation to an instance of a different problem for which an algorithm is already
available—we call it problem reduction.

Presorting
Presorting is a technique where lists are sorted before performing further operations on them.
This can simplify many problems and improve the efficiency of certain algorithms.

Many questions about a list are easier to answer if the list is sorted. The efficiency of
algorithms that involve sorting depends on the sorting algorithm used. Sorting algorithms can
be categorized into elementary algorithms (like selection sort, bubble sort, and insertion sort)
which are quadratic (i.e, O(n2)) in the worst and average cases, and advanced algorithms (like
mergesort and quicksort) which have better efficiency O(n log n).

Examples of Presorting

Example 1: Checking Element Uniqueness in an Array


To Determine if all elements in an array are unique.

Brute-force Solution is to compare each pair of elements until duplicates are found or all
pairs are checked. Worst-case efficiency in this case is Θ(n2).

Presorting Solution is to sort the array first, then check consecutive elements for duplicates.
Efficiency in this case is Θ(nlogn) (due to sorting) + Θ(n) (for checking) =Θ(nlogn).
ALGORITHM PresortElementUniqueness(A[0..n − 1])
sort the array A
for i ← 0 to n − 2 do
if A[i] = A[i + 1] return false
return true

Example 2: Computing a Mode.


To find the value that occurs most frequently in a list.

Brute-force Solution is to compute frequencies of all distinct values.


Worst-case efficiency in this case is Θ(n2).

Presorting Solution is to sort the array first, then find the longest run of adjacent equal
values.
Efficiency in this case is Θ(nlogn) (due to sorting) + Θ(n) (for finding mode) =Θ(nlogn).

ALGORITHM PresortMode(A[0..n − 1])


sort the array A
i←0
modefrequency ← 0
while i ≤ n − 1 do
runlength ← 1; runvalue ← A[i]
while i + runlength ≤ n − 1 and A[i + runlength] = runvalue
runlength ← runlength + 1
if runlength > modefrequency
modefrequency ← runlength; modevalue ← runvalue
i ← i + runlength
return modevalue

Example 3: Searching Problem


Problem: Search for a given value in an array.

Brute-force Solution is to use sequential search.


Worst-case efficiency is Θ(n).

Presorting Solution is to sort the array first, then apply binary search.
Efficiency is Θ(nlogn) (due to sorting) + Θ(logn) (for binary search) = Θ(nlogn).

Presorting is less efficient than sequential search for a single search but is justified if multiple
searches are performed.

Applications of Presorting
1. Geometric Algorithms: Sorting points by coordinates or other criteria simplifies
problems like the closest-pair and convex-hull problems.
2. Directed Acyclic Graphs (DAGs): Topological sorting can simplify finding longest
and shortest paths.
3. Greedy Algorithms: Often require presorting of inputs as part of their operations.

You might also like