Assignment# 03 AdvanceAlgorithm Analysis SUBMITTED BY: MAHEEN SHAHID 17-MS-CSc-26SANA NASEER 17-MS-CSc-33ANEELA ASLAM 17-MS-CSc-44 SUBMITTED TO:DR. JAVED IQBALMSCS(Fall 2K17) University of Engineering andTechnology TaxilaA Review on Divide andConquer Sorting Algorithm AbstractAppropriateorganization of data in a database system needs special operations likeinsertion, deletion, sorting, searching and traversing etc. Sorting categorizesthe data in a specific order which makes other operations easier. Hence abetter sorting algorithm increases the effectiveness of each of the succeedingoperations. Among numerous Sorting Techniques, Divide and Conquer algorithms grasppotential since most of them may put less load both in terms of Space as wellas processor time. Similar to all Sorting methods Divide and Conquer algorithmsfollow both Iterative as well as Recursive approaches. In this paper, we have chartedsome of the conventional and newly proposed Divide and Conquer sortingalgorithms.

Key words— DBMS, Divide and Conquer, Greedy, Hierarchical BubbleSorting, Nested Grid Files, non-Manhattan Channel Routing, IntroductionResearches in several databasemanagement systems have given enlargement to various sorting algorithms amongwhich Divide and Conquer techniques holds the most potential in terms of bothSpace complexity as well as Time complexity . Sorting can be done either initerative or recursive way. The recursive method is mostly based on Inductivesteps which can easily be formulated in terms of Divide and Conquer approach. TheDivide and Conquer approach has been employed in many conventional sortingalgorithms like Merge Sort, Quick Sort, Heap Sort, Radix Sort, etc. Theygenerally follow a time complexity of O(n log2 n).

Literature review2 Thomas A.Mueck andManfred J. Schauer offered two order query execution algorithms for bothBalanced and Nested Grid files that uses greedy and Divide and Conquer methodsrespectively. It reduces the length of r sequences for both read and writes andpass DBMS access disk plans for supplementary execution.3 J.

–T. Yansurveyed a Hierarchical Bubble Sorting non Manhattan Channel Routing problemand proposed an alternate algorithm with a complexity of O (hn) where n isnumber of terminals and h is number of routing tracks. It represents sequencesof left-swap and right-swap passes.

It follows a top-down approach where theswap operations are mapped to a particular track.2 Ellis Horowitz andAlessandro Zorat articulated a divide and conquer model to enhancecomputational speed for parallel processing. If the number of processorsincreases with number of elements, N the time complexity is reduced to O (N). COMPARISON OF LATELY PROPOSEDDIVIDE 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 andConquer sorting methods solve the problem of complexity as they follow bothrecursive and iterative path while handling the data. Their complexity to sortthe data is very less as compared to usual iterative approaches generally O(nlog2n). The Divide andConquer sorting algorithms has a extensive array of uses in DBMS, in numerousrecord keeping systems for instance telephone directories, dictionaries, bankdirectories, etc.

References1 E. Horowitz and A.Zorat, “Divide-and-Conquer for Parallel Processing”, IEEE Transactions onComputers, 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 GridFiles”, IEEE Transactions on Knowledge and Data Engineering, vol. 7, no.

2, pp. 246-260, April 1995 3 J. –T. Yan, “Hierarchical bubble-sorting-basednon-Manhattan channel routing”, IEE Proc.

-Comput. Digit. Tech, vol. 147, no. 4,pp.

215-220, July 2000