This question is to be attempted individually. Consider the following pseudocode: int f(int n) { if...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
This question is to be attempted individually. Consider the following pseudocode: int f(int n) { if (n>1) { f(n/2); f(n/2); } } } for (int i = 1; i <= g(n); i++) { println("Hello world!"); } f(n/2); int g(int n) { int sum = 0; for (int i = 1; i <= n; i++) sum += i; return sum; Here println() is a function that prints a line of text. Assume n is a power of 2. (a) Express the return value of g(n) in terms of n. [5 marks] (b) What is the time complexity of g(n), in terms of n and in big-O? [5 marks] (c) Let T(n) be the number of lines printed by f(n). Write down a recurrence formula for T(n), including the base case. [5 marks] (d) Solve the recurrence in (c), showing your working steps. For full credit give the exact answer (not big-O) and do not use Master Theorem. [20 marks] Question 2 (65 marks) This question can be attempted in groups. There are n samples that need to be tested for coronavirus. The testing process (known as PCR) involves using a special machine, testing one sample at a time, which is both time- consuming and expensive. Thus, we would like to have a method that is better than the trivial method of testing each sample one by one sequentially. Fortunately this is possible because we expect most samples to return a negative result (not containing the virus), and so we can 'combine' multiple samples to be tested together. For example, we can take one drop from each of the samples 1, 2, 3 to form a new sample, and test this mixed sample. If it returns a negative result, then all samples 1, 2, 3 are negative. But if it returns a positive result, we only know some of them contain the virus and not which one(s), or indeed how many of them, contain the virus, and further tests are needed. Assume each individual sample contains sufficient contents so many drops can be taken from each of them, and that if a sample contains the virus, any drop taken from it will contain the virus. (a) Suppose we know that exactly one of the n samples contains the virus. Design an algorithm for identifying it that takes O(log n) tests. [20 marks] (b) Suppose instead we know that at most one of the n samples contains the virus. Design an algorithm for identifying the positive sample (or determine that there are none) using as few tests as you can. [20 marks] (c) Suppose instead we know that at most two of the n samples contain the virus. Repeat (b). [25 marks] In each part, you should: state the algorithm in pseudocode; • explain (in words) some intuition behind your algorithm, and/or why it correctly identifies the positive samples; • explain mathematically (e.g. via solving a recurrence formula) the number of tests taken by your algorithm; • explain whether you think your algorithm is optimal by proving as good a lower bound as you can. You can assume n is some "nice" number such as powers of 2; state your assumptions. (You can have different assumptions in each part if you want.) Marking criteria Question 1 will be marked based on correctness, according to the given mark distribution. Partially correct answers will get partial marks. Correct steps following earlier wrong results (e.g. stating the wrong recurrence but solving the wrong one correctly) will still yield most of the allocated marks. Each part of Question 2 will be marked roughly according to this table: 0-20% Barely any idea about the algorithm. 20-40% 40-50% 50-60% 60-70% 70-80% 80-90% 90-100% There are some ideas towards a correct algorithm (i.e. it will identify the correct positive samples) but they would not lead to anywhere near the upper bounds expected. Pseudocode / explanation analysis all very wrong or missing. Some correct ideas but incomplete, or would not lead to the upper bounds expected. Pseudocode or explanation missing or wrong. Analysis missing, or wrong, or follows the incomplete ideas "correctly" to lead to sub-optimal bounds. Have the correct main ideas that would lead to the upper bounds expected, but this is not matched by the analysis. Some of pseudocode / explanation / analysis missing or wrong, while the others are in the right direction but have errors. Ideas mostly correct. At most one of the required elements missing or wrong. Analysis have errors or do not lead to the required bounds. Ideas mostly correct. Pseudocode have some errors. Analysis lead to correct bounds but have errors. Everything is mostly correct, with some small mistakes. Upper and lower bounds match asymptotically (up to big-O). Everything is mostly correct, with some small mistakes. Upper and lower bounds match including multiplicative constants. In both questions, you can use the Master Theorem unless otherwise stated (but you should show the steps in using it). Where manual solving of recurrence is required, solving with Master orem instead (and tly) will yield 40% of the allocated This question is to be attempted individually. Consider the following pseudocode: int f(int n) { if (n>1) { f(n/2); f(n/2); } } } for (int i = 1; i <= g(n); i++) { println("Hello world!"); } f(n/2); int g(int n) { int sum = 0; for (int i = 1; i <= n; i++) sum += i; return sum; Here println() is a function that prints a line of text. Assume n is a power of 2. (a) Express the return value of g(n) in terms of n. [5 marks] (b) What is the time complexity of g(n), in terms of n and in big-O? [5 marks] (c) Let T(n) be the number of lines printed by f(n). Write down a recurrence formula for T(n), including the base case. [5 marks] (d) Solve the recurrence in (c), showing your working steps. For full credit give the exact answer (not big-O) and do not use Master Theorem. [20 marks] Question 2 (65 marks) This question can be attempted in groups. There are n samples that need to be tested for coronavirus. The testing process (known as PCR) involves using a special machine, testing one sample at a time, which is both time- consuming and expensive. Thus, we would like to have a method that is better than the trivial method of testing each sample one by one sequentially. Fortunately this is possible because we expect most samples to return a negative result (not containing the virus), and so we can 'combine' multiple samples to be tested together. For example, we can take one drop from each of the samples 1, 2, 3 to form a new sample, and test this mixed sample. If it returns a negative result, then all samples 1, 2, 3 are negative. But if it returns a positive result, we only know some of them contain the virus and not which one(s), or indeed how many of them, contain the virus, and further tests are needed. Assume each individual sample contains sufficient contents so many drops can be taken from each of them, and that if a sample contains the virus, any drop taken from it will contain the virus. (a) Suppose we know that exactly one of the n samples contains the virus. Design an algorithm for identifying it that takes O(log n) tests. [20 marks] (b) Suppose instead we know that at most one of the n samples contains the virus. Design an algorithm for identifying the positive sample (or determine that there are none) using as few tests as you can. [20 marks] (c) Suppose instead we know that at most two of the n samples contain the virus. Repeat (b). [25 marks] In each part, you should: state the algorithm in pseudocode; • explain (in words) some intuition behind your algorithm, and/or why it correctly identifies the positive samples; • explain mathematically (e.g. via solving a recurrence formula) the number of tests taken by your algorithm; • explain whether you think your algorithm is optimal by proving as good a lower bound as you can. You can assume n is some "nice" number such as powers of 2; state your assumptions. (You can have different assumptions in each part if you want.) Marking criteria Question 1 will be marked based on correctness, according to the given mark distribution. Partially correct answers will get partial marks. Correct steps following earlier wrong results (e.g. stating the wrong recurrence but solving the wrong one correctly) will still yield most of the allocated marks. Each part of Question 2 will be marked roughly according to this table: 0-20% Barely any idea about the algorithm. 20-40% 40-50% 50-60% 60-70% 70-80% 80-90% 90-100% There are some ideas towards a correct algorithm (i.e. it will identify the correct positive samples) but they would not lead to anywhere near the upper bounds expected. Pseudocode / explanation analysis all very wrong or missing. Some correct ideas but incomplete, or would not lead to the upper bounds expected. Pseudocode or explanation missing or wrong. Analysis missing, or wrong, or follows the incomplete ideas "correctly" to lead to sub-optimal bounds. Have the correct main ideas that would lead to the upper bounds expected, but this is not matched by the analysis. Some of pseudocode / explanation / analysis missing or wrong, while the others are in the right direction but have errors. Ideas mostly correct. At most one of the required elements missing or wrong. Analysis have errors or do not lead to the required bounds. Ideas mostly correct. Pseudocode have some errors. Analysis lead to correct bounds but have errors. Everything is mostly correct, with some small mistakes. Upper and lower bounds match asymptotically (up to big-O). Everything is mostly correct, with some small mistakes. Upper and lower bounds match including multiplicative constants. In both questions, you can use the Master Theorem unless otherwise stated (but you should show the steps in using it). Where manual solving of recurrence is required, solving with Master orem instead (and tly) will yield 40% of the allocated
Expert Answer:
Answer rating: 100% (QA)
aThe function gn calculates the sum of the first n positive integers which is equal to n n 1 2 Therefore the return value of gn can be expressed as gn ... View the full answer
Related Book For
Database management systems
ISBN: 978-0072465631
3rd edition
Authors: Raghu Ramakrishan, Johannes Gehrke, Scott Selikoff
Posted Date:
Students also viewed these algorithms questions
-
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...
-
Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...
-
Design considerations for the bumper B on the train car of mass M require use of a nonlinear spring having the load-deflection characteristics shown in the graph. Select the proper value of K so that...
-
Consider an increasing marginal-cost depletable resource with no effective substitute. (a) Describe, in general terms, how the marginal user cost for this resource in the earlier time periods would...
-
Suppose that you are a DBA. What data dimensions would you describe to top-level managers to obtain their support for endorsing the data administration function?
-
Assume the Black-Scholes framework. You are given: (i) The stock, whose current price is 100, pays dividends continuously at a rate proportional to its price. (ii) The stocks volatility is 0.35....
-
An engineering student correctly answers \(85 \%\) of all questions she attempts. What is the probability that the first incorrect answer was the fourth one?
-
Alpha Products, Inc., is having a problem trying to control inventory. There is insufi cient time to devote to all its items equally. Here is a sample of some items stocked, along with the annual...
-
In a class of 25 students, 15 were math majors, 17 were computer science majors, and 9 were dual majors in math and computer science. Part: 0 / 4 Part 1 of 4 Use the Venn Diagram tool to illustrate...
-
1. What might Lewis have done to avoid the result in this case? Discuss. 2. Suppose that Lewis had already been reimbursed for the two vehicles that had been sold, and Whitney sought to obtain the...
-
Explain the concept of ergonomics and its importance in manual work design Provide 3 examples of how ergonomic principles can enhance workplace safety and productivity. Discuss the role of...
-
Write the pseudocode that evaluates the following quantifiers and returns a boolean value. Assume you have two arrays (a[], and b[]) of size n, and the function P(x, y) takes a single input from a,...
-
Simplify the equations using Boolean algebra and show work: (5 points) i. ((A+BC')'+D(E+F')')' ii. AB + ABC + ABCD + ABCDE + ABCDEF iii. A'(A+B) +(B+AA) (A+B') iv. (A + B)'(C+D+ E)' + (A + B)' v. AB'...
-
Suppose we had the following shares; Share Amount Invested Expected Return APPLE $10,250 0.06 BUNNINGS $15,250 0.08 CEMEX $20,250 0.10 DELTA $6,250 0.14 a. What are the portfolio weights? (3 marks)...
-
Consider the following Python program. Suppose that the user runs this program and when prompted, types 5 as input. nint (raw_input ("Enter a number: ")) n = n + 10 n = n/3.0 nint (n) n "n" + str(n)...
-
Write a C program to calculate w with the following equations? Show the output. a. w=x%y-y% x-z%x-x% z b. w=x/z+y/z+ (x+y) / z c. w = x/z+y/z+x*y/z d. w = x/y/y/x+z/y/(y/x) Used-x=3, y = 5, z=7 I...
-
In an experiment, consumers indicated that a $20 cup of coffee tastes better than a $3 cup of coffee. However, they could not tell the difference when the price information was not given. This is...
-
Why are stocks usually more risky than bonds?
-
What main conclusions can you draw from the discussion of the five basic file organizations discussed in Section 8.4? Which of the five organizations would you choose for a file where the most...
-
Explain the difference between Hash indexes and B+-tree indexes. In particular, discuss how equality and range searches work, using an example.
-
Suppose that a DBMS recognizes increment, which increments an integer- valued object by 1, and decrement as actions, in addition to reads and writes. A transaction that increments an object need not...
-
What methods can a company use to raise capital?
-
Does higher expected inflation increase, decrease, or have no effect on the required rate of return?
-
What are some of the advantages of equity financing?
Study smarter with the SolutionInn App