Problem 3 (25 points) Code analysis // A[l...n] is an array of n elements function fun...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Problem 3 (25 points) Code analysis // A[l...n] is an array of n elements function fun (A[]) 1. Create new array temp [n] 2. temp [1] A [1]; k=2; 3. for (i-2; i<-n; i++) if 4. (A[i] >= sum (A, i)) temp [k] -A[i]; k++; 5. 6. 7. return temp [] 1. [15 points] Consider the algorithm shown above. a) (2 pts) What does the algorithm do? Justify your answer. b) (2 pts) What is the output of the algorithm on input array A = [1, 3, 5, 7, 15, 2, 4, 40, 50, 100]? c) (4 pts) Analyze the algorithm and determine its running time as a function of n. Use the Big-O() notation and consider the behavior of the algorithm on the worst possible input. d) (7 pts) Come up with a better algorithm for the same problem. For example if your algorithm in part (c) was (say) O(n), you should produce an algorithm that is strictly less than O(n), like O(n) or O(n), etc... while (i <= n) ( if (A[i] < 0) return 0; function sum (A[], i) 2. [10 points] Analyze the running time of the following two pieces of code. Give the best upper bounds for these. FA( A[1...n]) // array of size n res= 0; i = 1; for (j0; j <n; j+-2) res += A[j]; 1. s = 0 2. for (j-1; j<i; j++) s += A[j] 3. 4. return s i-i 2; } return res; FB (A[1...n] // array of size n res = 0; for (i = 0; i < n/2; i++) { res + A[i] 2; for (j-n; j> 0; j--) { res + FA (j); return res; Problem 3 (25 points) Code analysis // A[l...n] is an array of n elements function fun (A[]) 1. Create new array temp [n] 2. temp [1] A [1]; k=2; 3. for (i-2; i<-n; i++) if 4. (A[i] >= sum (A, i)) temp [k] -A[i]; k++; 5. 6. 7. return temp [] 1. [15 points] Consider the algorithm shown above. a) (2 pts) What does the algorithm do? Justify your answer. b) (2 pts) What is the output of the algorithm on input array A = [1, 3, 5, 7, 15, 2, 4, 40, 50, 100]? c) (4 pts) Analyze the algorithm and determine its running time as a function of n. Use the Big-O() notation and consider the behavior of the algorithm on the worst possible input. d) (7 pts) Come up with a better algorithm for the same problem. For example if your algorithm in part (c) was (say) O(n), you should produce an algorithm that is strictly less than O(n), like O(n) or O(n), etc... while (i <= n) ( if (A[i] < 0) return 0; function sum (A[], i) 2. [10 points] Analyze the running time of the following two pieces of code. Give the best upper bounds for these. FA( A[1...n]) // array of size n res= 0; i = 1; for (j0; j <n; j+-2) res += A[j]; 1. s = 0 2. for (j-1; j<i; j++) s += A[j] 3. 4. return s i-i 2; } return res; FB (A[1...n] // array of size n res = 0; for (i = 0; i < n/2; i++) { res + A[i] 2; for (j-n; j> 0; j--) { res + FA (j); return res;
Expert Answer:
Answer rating: 100% (QA)
1 Given Algorithm Analysis a What does the algorithm do Explanation The algorithm processes an input array A of n elements and creates a new array tem... View the full answer
Related Book For
Calculus Of A Single Variable
ISBN: 9781337275361
11th Edition
Authors: Ron Larson, Bruce H. Edwards
Posted Date:
Students also viewed these programming questions
-
Rachelle has purchased a fairly new home valued at $275,000. What should she budget for her annual maintenance costs?
-
The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 1-5. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...
-
Find the inverse of each of the given matrices by the method of Example 1 of this section. Data from Example 1 Find the inverse of the matrix First, we interchange the elements on the principal...
-
The comparative condensed statements of financial position of Garcia SLU are presented below. GARCIA SLU Comparative Condensed Statements of Financial Position December 31 Instructions (a) Prepare a...
-
Suppose an economist develops an economic model and finds that it works great in theory but fails in practice. What should the economist do next?
-
What is the relationship between technical reviews and System Development Processes (Figure 12.2)? System System Definition Procurement Phase Phase System / Product Life Cycle System System...
-
Analyzing Items to Be Included in Inventory Based on its physical count of inventory in its warehouse at year-end, December 31, 2011, Madison Company planned to report inventory of $34,500. During...
-
Explain what artificial intelligence analytics are and how they impact today's society, both positively and negatively CO3: Explain and assess the implications of big data analytics in political and...
-
Bestseller Book's binding department has beginning inventory of 5,000 units and $20,000, consisting of $10,000 of direct materials and $10,000 of conversion costs. During the period, the department...
-
Identify the basic provisions of the Sarbanes-Oxley Act that specifically deal with ethics and Independence and research how this Act has affected auditors since it was established in 2002. Be sure...
-
Mancon Trading has provided the following cash book summary (bank columns only) for August 2020. Dr Aug 2020 1 7 12 20 27 1 6 Bal blf Cash 7 9 Richard T Chan Cash Cash Book RM 1,400 100 400 150 120...
-
Following the template provided for the bank reconciliation, prepare a bank reconciliation (in full format with description of each reconciled amount) for the following company: Bank Statement of...
-
Assume IBM market quote 189.78 - 189.99 and last price is $189.78. Refer to matrix below to answer this question, to construct a June 190 and June 175 bear put spread. Show all calculations. June...
-
Figure I shows a JSP program output of a simple registration form. Your program will prompt a user to insert his/her information and click submit, the submitted data should be stored in a Database....
-
Rather than using to see the waveform of current or voltage in the scope, an rms meter can be used along with a digital display. Look in the help window for the RMS bock and drag it to your file. O...
-
The city of Wesley adopted the modified approach for reporting its roads and bridges. The city met the GAAP requirements for having an asset management system, making periodic assessments, and...
-
Refer to Exercise 8.S.I. Construct a scatterplot of the data. Does the appearance of the scatterplot indicate that the pairing was effective? Explain. Exercise 8.S.I. A volunteer working at an animal...
-
Find the indefinite integral and check the result by differentiation. (csc x cot x 2x) dx
-
Find the derivative of the function. y = ln 4x/ x - 6
-
Find the indefinite integral. sin x /cos x dx
-
In an audit of a corporation that has a bond issue outstanding, the trust indenture is reviewed and confirmation as to the issue is obtained from the trustee. List eight matters of importance to the...
-
Robertson Company had accounts receivable of \(\$ 200,000\) at December 31, 200X, and had provided an allowance for uncollectible accounts of \(\$ 6,000\). After performing all normal auditing...
-
Tom Jones, CPA, is auditing the financial statements of a manufacturing company with a significant amount of trade accounts receivable. Jones is satisfied that the accounts are properly summarized...
Study smarter with the SolutionInn App