Advanced Algorithms and Data Structures: A Study of Selection, Partitioning, and Red-Black Tree Operations

Covers advanced algorithms and data structures.

Sophia Johnson

Contributor

4.4

5 months ago

Preview (2 of 3 Pages)

100%

Purchase to unlock

Loading page image...

Advanced Algorithms and Data Structures: A Study of Selection, Partitioning, and Red-Black Tree OperationsQ1.(a)Algorithm to find the second smallest element in a list.Suppose that the numbers area0,a1,…,an−1.On the first pass comparea2kwitha2k+1for0≤k<(n−1)/2;ifa2k>a2k+1, interchange them.On the second pass comparea4kwitha4k+2for0≤k<(n−2)/4;ifa4k>a4k+2, interchange the pair⟨a4k,a4k+1⟩with the pair⟨a4k+2,a4k+3⟩.On thei-th pass comparea2ikwitha2ik+2i−1for0≤i<(n−2i−1)/2i;ifa2ik>a2ik+2i−1, interchange the blocks of length2i−1beginning ata2ikanda2ik+2i−1. This continues aslong asn−2i−1>0, i.e., untiln≤2i−1; thus, if the last pass is them-th pass, then2m−1<n≤2m, or⌈lgn⌉=m. The smallestnumber in the set is nowa0, and every other number in the set has lost exactlyone comparison, so we’ve maden−1comparisons.The numbers that are nowa2ifori=0,…,m−1are the numbers that lost toa0in direct comparisons;every number in the set that is neithera0nor one of thesemnumbers lost a direct comparison to oneof thesemmnumbers and therefore cannot be the second-smallest number in the set. Thus, thesecond-smallest number is the smallest of thea2ifori=0,…,m−1. There aremofthese numbers, so ittakesm−1comparisons to find the smallest.Altogether, then, this algorithm takes(n−1)+(m−1)=n−1+⌈lgn⌉−1=n+⌈lgn⌉−2(b)algorithmtofindthe3rdsmallestelementinalist,We can use Max Heap for finding the k’th smallest element. Following is algorithm.1) Build a Max-Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)2) For each element, after the k’th element (arr[k] to arr[n-1]), compare it with root of MH.……a) If the element is less than the root then make it root and call heapify for MH……b) Else ignore it.// The step 2 is O((n-k)*logk)3) Finally, root of the MH is the kth smallest element.Time complexity of this solution is O(k + (n-k)*Logk)Q2. The kth quantiles of an n-element setWeuse a modifiedPARTITIONthat is given an index to the pivot to be used as its last inputparameter.You start withKTH-QUANTILES(A, 1, n, 1, k-1, k)recursion.----

Loading page image...

Preview Mode

This document has 3 pages. Sign in to access the full document!

Report

Study Now!

XY-Copilot AI

Unlimited Access

Secure Payment

Instant Access

24/7 Support

Document Chat

Document Details

Subject

Information Technology

Advanced Algorithms and Data Structures: A Study of Selection, Partitioning, and Red-Black Tree Operations

Study Now!

Document Details

Related Documents

DevOps and Its Importance Study Notes

Veeam Certified Engineer VMCE-V12

Modules 1 - 3 Basic Network Connectivity and Commu

Notes CCNA

CCNA 200-301 Portable Command Guide 5th Edition 20

CCNA 200-301 Portable Command Guide 5th Edition 22

CCNA 200-301 Portable Command Guide 5th Edition 36

Foundations of Novell Networking Section 26

Modulo 7 DHCPv4

Build and troubleshooting Integration Challenge

Company

Explore

Study Tools