(a) Write the pseudocode for a Divide-and-Conquer algorithm that finds the index of the minimum element...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
(a) Write the pseudocode for a Divide-and-Conquer algorithm that finds the index of the minimum element of an array. Hints: • Emulate the pseudocode examples in our text, e.g. the first lines could be Algorithm Minim(A, 1, r) //Input: ... O O //Output: ... o If... //base case o Else ... //recursive case The base-case of the recursion is when 1 = r, i.e. the array has only 1 element. What is the minimum in this case? • Just like Binary Search or MergeSort, divide the array in half at each step. Let m be the index of the middle element. Use 1 = left and r = right, as in the above-mentioned algorithms. • It is OK to assume that the nr. of elements is a power of 2: n = 2k, so do not worry about floors and ceilings. Simply use integer division by 2. Write complete pseudocode here: (b) What is the basic operation that we should count for the order of growth? Argue that the best-, worst- and average-cases are all identical. (Explain in words, do not calculate anything yet!) (c) Write the Master Theorem for the recursion, identify a, b, d, and find the theta for C(n). (d) Solve the recursion by back-substitution for n = 2k, and find the exact solution for C(n). Hint: You will have to use the summation for the geometric series in App. A. ● (a) Write the pseudocode for a Divide-and-Conquer algorithm that finds the index of the minimum element of an array. Hints: • Emulate the pseudocode examples in our text, e.g. the first lines could be Algorithm Minim(A, 1, r) //Input: ... O O //Output: ... o If... //base case o Else ... //recursive case The base-case of the recursion is when 1 = r, i.e. the array has only 1 element. What is the minimum in this case? • Just like Binary Search or MergeSort, divide the array in half at each step. Let m be the index of the middle element. Use 1 = left and r = right, as in the above-mentioned algorithms. • It is OK to assume that the nr. of elements is a power of 2: n = 2k, so do not worry about floors and ceilings. Simply use integer division by 2. Write complete pseudocode here: (b) What is the basic operation that we should count for the order of growth? Argue that the best-, worst- and average-cases are all identical. (Explain in words, do not calculate anything yet!) (c) Write the Master Theorem for the recursion, identify a, b, d, and find the theta for C(n). (d) Solve the recursion by back-substitution for n = 2k, and find the exact solution for C(n). Hint: You will have to use the summation for the geometric series in App. A. ●
Expert Answer:
Answer rating: 100% (QA)
Solutions Step 1 A Pseudocode for DivideandConquer Algorithm Algorithm FindLargestPositionarr left right Input An array arr of n numbers left index left proper index right Output The function of the b... View the full answer
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
The Boswell Corporation forecasts its sales in units for the next four months as follows: March April May June 11,000 13,000 10,500 9,000 Boswell maintains an ending inventory for each month in the...
-
1. Insert a module and create a subroutine named Receipt(). Excel 2. Place a button with the name "Generate Receipt" that would link to this subroutine when clicked. Do the following parts from 3 to...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Q1. During November, these transactions took place in Singer Inc., a company that uses job order costing: a) Materials purchased on account $35,600. b) Materials issued to fill requisitions on job...
-
In a recent survey conducted by the Pew Research Center, a random sample of adults 18 years of age or older living in the continental United States was asked their reaction to the word socialism. In...
-
Lott Company uses a job order cost system and applies overhead to production on the basis of direct labor costs. On January 1, 2017, Job 50 was the only job in process. The costs incurred prior to...
-
Following are errors, frauds, or other circumstances that an auditor might encounter as a result of applying audit tests to long-term debt as of the balance sheet date: a. Detailed long-term debt...
-
Swanton Company currently sells three products: desk calendars, pen sets, and paper-clip holders. The company is thinking of discontinuing the production and sale of paper-clip holders. However,...
-
Obtain the public financial records for at least 3 years for 1 domestic and 1 global organization selected in Wk 3. Analyze the current and expected performance of each organization using financial...
-
It took a long time but the Securities and Exchange Commission finally acted and held auditors responsible for the fraud that occurred in banks during the financial recession. Surprisingly to some,...
-
1. Create a research question that investigates how effectively living standards can be measured. M
-
1. Define capital budgeting, explain why it is important, differentiate between security valuation and capital budgeting, and state how project proposals are generally classified. 2. Calculate net...
-
An FI has purchased (borrowed) a one-year $10 million Eurodollar deposit at an annual interest rate of 6 percent. It has invested these proceeds in one-year Euro () bonds at an annual rate of 6.5...
-
After coming up with an innovative idea for a new product, you paid $2000 to an industrial designer to draw the blueprints and found a factory in China that agreed to produce the product for you for...
-
A. What is the price of a call option with a strike of $80 and a maturity of 2.5 years? The underlying asset is currently trading at $75. The risk-free rate is 8% and the volatility of the underlying...
-
If f(x) = 4 + 4x - 5x, find f'(-5).
-
The position of an electron is given by r=3tc-4tj+2k (i) Find v\t at t=2 seconds
-
If your school has a subscription to the FASB Codification, go to aaahq.org/ ascLogin.cfm to log in and prepare responses to the following. (a) What is the stock dividend? (b) What is a stock split?...
-
Show that for any integers n 0 and 0 k n, the expression ( n k ) achieves its maximum value when k = n/2 or k = n/2.
-
Show how in polynomial time we can transform one instance of the traveling-salesman problem into another instance whose cost function satisfies the triangle inequality. The two instances must have...
-
The chirp transform of a vector a = (a 0 , a 1 , . . . ,a n - 1 ) is the vector y= (y 0 , y 1 , . . . ,y n - 1 ), where y k = n-1 j=0? aj z kj and z is any complex number. The DFT is therefore a...
-
The life \(T\) in hours of a vibration transducer is found to follow exponential distribution \[p_{T}(t)= \begin{cases}\lambda e^{-\lambda t}, & t \geq 0 \\ 0, & t <0\end{cases}\] where \(\lambda\)...
-
Fill in the Blank. If any parameter of a vibrating system is not known precisely, the resulting vibration is called ____________ vibration.
-
The probability distribution function, \(P(\widetilde{x})\), denotes a. \(P(x \leq \tilde{x})\) b. \(P(x>\widetilde{x})\) c. \(P(\tilde{x} \leq x \leq \tilde{x}+\Delta x)\)
Study smarter with the SolutionInn App