Answered: 1. You, Alice and Bob are working on…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

1. You, Alice and Bob are working on recursive search algorithms and have been studying a
variant of binary search called trinary search. Alice has created the following pseudocode
for this algorithm:
TSearch(A[a...b], t)
If a > b return -1
Let p1 = a + Floor((b - a)/3)
If A[p1] = t return p1
If A[p1] > t return TSearch(A[a...p1-1],t)
Let p2 = a + Ceiling(2(b - a)/3)
If A[p2] = t return p2
If A[p2] > t return TSearch(A[p1+1...p2-1],t)
Return TSearch(A[p2+1...b],t)
EndTSearch
a) State a recurrence relation that expresses the number of operations carried out by
this recursive algorithm when called on an input array of size n.
b) Bob has heard that trinary search is no more efficient than binary search when
considering asymptotic growth. Help prove him correct by using induction to show
that your recurrence relation is in Θ(log2 n) as well.
i. Split the tight bound into and upper (big-O) and lower (big-Ω).
ii. For each bound select a function from Θ(log2 n) to use in your proof, like
a log2 n or a log2 n −b. Remember there are typically multiple ways to prove
the theorem using different choices of functions.
iii. Use induction to prove your bound. Include all parts of the proof including
base case, inductive hypothesis and inductive case. Be as precise as possible
with your language and your math. Remember it’s possible to get stuck at this
point if you have selected the wrong function in the last step.
3 EX TR A CR E D I T PRO BL E M
2. Alice and Bob wonder if the same conclusion can be drawn about variants of merge sort
algorithm. Alice has an idea for a 4-way merge sort that:
i) splits the unsorted list into 4 parts,
ii) sorts each recursively, and then
iii) merges them together with three calls to the merge function.
Help them by proving this variant is also Θ(n log2 n) by following these steps:
a) Generate pseudocode for an algorithm based on this idea.

b) Create a recurrence relation expressing the number of operations carried out by
your algorithm.
c) Prove your recurrence relation is in Θ(n log2 n) using induction and/or other tech-
niques.

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions