Question: Designing and analysing a divide-and-conquer algorithm: The input is an array A[1],...,A[n] of ints, and one has to decide, whether the sum of the numbers

Designing and analysing a divide-and-conquer algorithm: The input is an array A[1],...,A[n] of ints, and one has to decide, whether the sum of the numbers is odd. (Remember the rules: even + even = even, even + odd = odd, odd + odd = even.) Take care only to use int-arithmetic (as in Java). For example, for array (1,2,3) the answer is NO, and for array (2,3,6) the answer is YES. (i) Specify how to split the array A. [2 marks] (ii) Specify how the results for the subproblems are combined into a solu- tion for array A. [4 marks] (iii) Specify the base case(s) and how to handle them. [1 marks] (iv) Write down a recurrence which describes the run-time of your algo- rithm. [2 marks] (v) Solve the recurrence by using the (simplified) Master Theorem (state which case applies), obtaining a-expression. [1 marks] (vi) Explain in a few words an alternative algorithm for solving this prob- lem, and state the asymptotic run-time for it. Compare the run-time for your above clever (divide-and-conquer) algorithm with that run- time. State which algorithm is asymptotically better, or whether they are asymptotically equally good.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

Question Designing and analysing a divide-and-conquer algorithm: The input is an array A[1],... , A[n] of int's, and two long's p, q. So the elements of A are 32-bit signed integers, while p,q are...

can someone solve this Modern workstations typically have memory systems that incorporate two or three levels of caching. Explain why they are designed like this. [4 marks] In order to investigate...

A discrete sequence {xn} can be converted into a continuous representation x(t) = ts X n= (t n ts) xn, where ts is the sampling period. (a) State two characteristic properties of Dirac's function. [2...

(a) Describe how to construct the function cpo ((D E), v) of two cpos (D, vD) and (E, vE). Prove that ((D E), v) is a cpo. (b) The function uncurry is inverse to the function curry; it takes a...

Consider the trigonometric series a0 2 + X r=1 (ar cos rx + br sin rx) where a0, a1, a2, . . . and b1, b2, . . . are constants and suppose that f(x) is a periodic function of x with period 2. (a)...

In this question you will be asked to reflect on a project you have been involved in or observed, in which a design evolved, or could have evolved, through applying a theory of user behaviour. You...

A creative engineer suggests structuring the TLB so that not all the bits of the presented address need match to result in a hit. Suggest how this might be achieved, and what might be the costs and...

answer the question clearly You are building a flight-control system for which a convincing safety case must be made. Would you assign the tasks of safety requirements engineering, test case...

ttth Suppose that the sequence of bags {Bn | n N} is recursively enumerated by the computable function e(n, x) = fn(x), [7 marks] Hence prove that the set of all recursive bags cannot be recursively...

In a Hopfield neural network configured as an associative memory, with all of its weights trained and fixed, what three possible behaviours may occur over time in configuration space as the net...

(1 point) The force F on an object is the product of the mass m and the acceleration a. In this problem, assume that the mass and acceleration both depend on timer, hence so the does the force. That...

Megalo Mart sold 1,000 units last month which yielded the income statement below. Sales $20,000 Variable Expenses 12,000 Contribution Margin 8,000 6.000 Net Income $2,000 Answer the questions that...

Homework Assignment # 3 Bond Pricing Both Bond Sam and Bond Dave have 6 . 5 percent coupons, make semiannual payments, and are priced at par value. Bond Sam has 3 years to matarity, whereas Bond Dave...

Seved Help 14 Wisconsin Snowmobile Corp. is considering a switch to level production Cost efficiencies would occur under level production, and aftertax costs would decline by $31,500, but inventory...

Explain the difference between Job Analysis, Job Classification, and Job Evaluation.

What does Processing of an OLAP Cube accomplish?

After designing a Multidimensional Database in Visual Studio, what are the next steps that build the Database in the Analysis Services Instance? How is the build out of the Analytical Services...