Assignment

# 03

Advance

Algorithm Analysis

SUBMITTED BY:

MAHEEN SHAHID 17-MS-CSc-26

SANA NASEER 17-MS-CSc-33

ANEELA ASLAM 17-MS-CSc-44

SUBMITTED TO:

DR. JAVED IQBAL

MSCS(Fall 2K17)

University of Engineering and

Technology Taxila

A Review on Divide and

Conquer Sorting Algorithm

Abstract

Appropriate

organization of data in a database system needs special operations like

insertion, deletion, sorting, searching and traversing etc. Sorting categorizes

the data in a specific order which makes other operations easier. Hence a

better sorting algorithm increases the effectiveness of each of the succeeding

operations. Among numerous Sorting Techniques, Divide and Conquer algorithms grasp

potential since most of them may put less load both in terms of Space as well

as processor time. Similar to all Sorting methods Divide and Conquer algorithms

follow both Iterative as well as Recursive approaches. In this paper, we have charted

some of the conventional and newly proposed Divide and Conquer sorting

algorithms.

Key words— DBMS, Divide and Conquer, Greedy, Hierarchical Bubble

Sorting, Nested Grid Files, non-Manhattan Channel Routing,

Introduction

Researches in several database

management systems have given enlargement to various sorting algorithms among

which Divide and Conquer techniques holds the most potential in terms of both

Space complexity as well as Time complexity . Sorting can be done either in

iterative or recursive way. The recursive method is mostly based on Inductive

steps which can easily be formulated in terms of Divide and Conquer approach. The

Divide and Conquer approach has been employed in many conventional sorting

algorithms like Merge Sort, Quick Sort, Heap Sort, Radix Sort, etc. They

generally follow a time complexity of O(n log2 n).

Literature review

2 Thomas A.Mueck and

Manfred J. Schauer offered two order query execution algorithms for both

Balanced and Nested Grid files that uses greedy and Divide and Conquer methods

respectively. It reduces the length of r sequences for both read and writes and

pass DBMS access disk plans for supplementary execution.

3 J. –T. Yan

surveyed a Hierarchical Bubble Sorting non Manhattan Channel Routing problem

and proposed an alternate algorithm with a complexity of O (hn) where n is

number of terminals and h is number of routing tracks. It represents sequences

of left-swap and right-swap passes. It follows a top-down approach where the

swap operations are mapped to a particular track.

2 Ellis Horowitz and

Alessandro Zorat articulated a divide and conquer model to enhance

computational speed for parallel processing. If the number of processors

increases with number of elements, N the time complexity is reduced to O (N).

COMPARISON OF LATELY PROPOSED

DIVIDE AND CONQUER SORTING ALGORITHM

Paper(1) : Order

Query Execution algorithms for both Balanced and Nested Grid Files

Overview

In this framework, we elaborate the

construction of disk access plans for sort order queries in balanced and

nested grid files. The key idea is to use the order information contained in

the directory of the multi attribute search structure. The presented

algorithms are shown to yield a significant decrease in the number of disk

I/O operations by appropriate use of the order information.

Properties

The two algorithms

use Greedy and Divide and Conquer approaches respectively. It reduces the

read/write sequences and passes the disk access plans to DBMS query processor

for further execution.

Efficiency

Divide and Conquer

approach requires less number of I/O operations and buffer gates. Storage

consumption is less. Worst case run time for construction phase is O(nh) and

processing phase is O(n+th)

Limitations

If the buffer page

pool is not controlled by the query processor, then the algorithm fails.

Applications

Spatial and

commercial DBMS that rely on B-Tree or single key hash structures for index

maintenance.

Paper(2) : Divide and Conquer

for Parallel Processing

Overview

In this paper a

realistic model for divide-and-conquer based algorithms is postulated; the

efficiency of some algorithms is then analyzed, taking into account all

relevant parameters of the model (time, data movement and number of

processors.)

Properties

It combines the

dynamically express parallelism with the principle of Divide and Conquer

approach. The amount of parallelism depends on the processed data and varies

when the program is being executed

Efficiency

The different

instantiations of recursive procedures need not be kept track by the writer.

If the number of processors, P increases with number of elements, n the time

complexity is reduced to O (n).

Limitations

The process is

highly efficient only if large number of processors is available.

Applications

Parallel

Processors

Paper(3) : Algorithm against Hierarchical Bubble

Sorting Based non-Manhattan Channel Routing problem

Overview

In the paper,

based on an optimality-oriented swap-direction selection and a

‘divide-and-conquer’ technology, a hierarchical BSNMCR (HBSNMCR) problem is

formulated and an O(hn) optimal algorithm is proposed, where h is the number

of routing tracks in a HBSNMCR solution, for h/spl les/k.

Properties

It performs the

operation by dividing the overall pass into left swap pass and right swap

pass which are further subdivided respectively. The top to bottom swap

operations are mapped into a single track.

Efficiency

It has a

complexity of O(hn) where n is the number of terminals and h is number of

routing tracks

Weaknesses

It requires more

space.

Applications

VLSI design

automation

PAPER(4): Spatial Divide and Conquer with Motion

Cues for Tracking through Clutter

(Zhaozheng Yin and Robert Collins

Department of Computer Science and Engineering

The Pennsylvania State University

{zyin, rcollins}@cse.psu.edu)

Properties

A spatial divide

and conquer approach is used to subdivide

foreground and background into smaller regions, with different

features being selected to distinguish between different pairs of object and

background regions.

Efficiency

weight images

produced by the divide and conquer approach are quite good for distinguishing

the motorcycle from its surrounding background, and that motion detection

results alone would not succeed, due to motion clutter.

Weaknesses

It requires more

space.

Applications

Different Spatial Dividing Methods Different

subdivisions of the scene background will generate different weight images

for tracking.

PAPER(5): Bit-width Optimization by

Divide-and-Conquer for

Fixed-point Digital Signal Processing Systems

Jaeyong Chung, Member, IEEE, Lok-Won Kim, Member,

IEEE

Properties

We define a

special class of designs called innerfork-

free designs, and unlike greedy-based methods including , we guarantee

them the optimal solutions even for non-convex objective functions in the

discrete solution space. For general designs, our method is applied after

partitioning and transforms the solution space of N variables to that of Nf

variables, where N is the number of signals and Nf is the number of fork

signals. Our algorithm generates the efficient frontier in a single run and

allows designers to explore the trade-off between area and error at a

negligible runtime cost. Unlike the methods relying on optimization packages

as in , our optimization method is transparent..

Efficiency

the maximal vector problem can be solved in ?(?????) where ??is the

size of the given set of ??dimensional

vectors. The next subsection introduces pruning techniques to keep the size

of Pareto sets small.

Weaknesses

1)heuristics play a big role and the quality of results is

not guaranteed.

2) with the exception of greedy methods, the runtime is

prohibitively long or we need to run it for a long time with the hope that we

may obtain better results.

3) many existing methods relyon generic optimization

packages and the optimization process is not transparent.

Applications

The five designs

include a degree 4 polynomial approximation to log(1 x), the RGB-to-YCbCr

color space converter, the2-2 matrix multiplication using Strassen’s

algorithm, cubic B-splines, and 8 8 Discrete Cosine Transform.

Paper(6): A divide-and-conquer bound for aggregate’s quality and algebraic

connectivity

Properties

We establish a divide-and-conquer bound for

aggregate’s quality and algebraic connectivity, as defined for weighted

undirected graphs. Aggregate’s quality is used in the context of

aggregation-based multigrid methods as a tool for the design of robust

multigrid solvers. Although initially introduced for discretized partial

differential equations aggregate’s quality is now also used for graph

Laplacian systems .Aggregate’s quality is defined on a set of vertices, also

called aggregate, and measures the maximal impact on the multigrid

convergence of representing this set of vertices by a single vertex.

Efficiency

Recursive application requires overall

O(|V| + |E|)

operations. with only few (or even no) recursive steps max operation are

Close to 1.

Limitations

Less optimize when we use popular aggregation

approach is multiple pairwise aggregation, in which unknowns are merged into

pairs, then the pairs are merged again into groups of size at most 4, and so

on, until the average size of the aggregates reaches a prescribed value. The

quality one wants to optimize is the quality of the final aggregate; however,

for the reasons of cost the construction algorithm is based on the quality of

the original pairs and the ?c parameter for the merged pairs of aggregates. It

is therefore important to know that optimizing these latter quantities one implicitly

tends to optimize ? through the upper bound.

Applications

The divide-and-conquer bound can be used in several ways. First,

it recursive application provides a quick albeit likely imprecise procedure

for estimating the quality of a vertex set, or the algebraic connectivity of

a graph.

Another possibility is to use the bound in with only few (or

even no) recursive steps. The resulting estimate of aggregate’s quality or

algebraic connectivity is then accurate enough if both arguments of the max

operation are close to 1.

Paper(7)Divide

and Conquer Partitioning Techniques for Smart Water

Networks

Properties

The authors

developed a software, called SWANP (Smart Water Network Partitioning) that

allows finding automatically the optimal layout of District Meter Areas based

on a multi-level algorithm. This paper compare SWANP with other procedures

for WNP.

Efficiency

With

reference to the specific results obtained in this study, the SWANP software

showed better results with respect to the HGP and WSC procedures in terms of

both hydraulic performance and minimization of the number of edge cuts, while

the MAS procedure provided a better result only in terms of edge cuts.

Limitations

The

simulation results obtained with SWANP are not comparable with their layout,

because the number of nodes and the flow to assign to each source in a WNS

depend on network topology and hydraulic characteristics. If the algorithms

tries to match the balance constraint, as happens in a WNP, hydraulic

performance can be significantly worsen

Applications

the papers

should provide a clear definition of their “divide and conquer” aims, possibly

using the classification in Water Network Partitioning (WNS) and Water

Network Sectorization (WNS);

Paper(8): A simple expected running time analysis for

randomized

“divide and conquer” algorithms

Properties

We

present a simple combinatorial method for analyzing the expected running time

of such algorithms, and prove that under very weak assumptions this expected running

time will be asymptotically equivalent to the running time obtained when

problems are always split evenly into two sub problems of size n/2.

Efficiency

If f (k) = ? (k) as

with randomized Quicksort then it will take ? (n log n).

it

takes ? (log n) expected

time to perform a randomized binary search for a random element in an n-element

sorted array (here, f (k)= ? (1))

Limitations

In

this situation, the decision of which sub problem to recursively solve is no

longer a random event, and in order to obtain a bound on worst-case running

time we must conservatively assume that the algorithm always recurses on the

larger of its two sub problems. Here our methods break down, since there no

longer seems to be simple expression for Exk.

Applications

many randomized “divide and conquer” algorithms,

in which sub problems solved recursively

Conclusion:

The Divide and

Conquer sorting methods solve the problem of complexity as they follow both

recursive and iterative path while handling the data. Their complexity to sort

the data is very less as compared to usual iterative approaches generally O(n

log2n). The Divide and

Conquer sorting algorithms has a extensive array of uses in DBMS, in numerous

record keeping systems for instance telephone directories, dictionaries, bank

directories, etc.

References

1 E. Horowitz and A.

Zorat, “Divide-and-Conquer for Parallel Processing”, IEEE Transactions on

Computers, vol. C-32, no. 6, pp.582585, June 1983

2 T. A.Mueck and M.

J. Schauer, “Optimizing Sort Order Query Execution in Balanced and Nested Grid

Files”, IEEE Transactions on Knowledge and Data Engineering, vol. 7, no. 2, pp. 246-260, April 1995

3 J. –T. Yan, “Hierarchical bubble-sorting-based

non-Manhattan channel routing”, IEE Proc.-Comput. Digit. Tech, vol. 147, no. 4,

pp. 215-220, July 2000