Kinldy Answer Q no 05 and than Qno 06 I need it really urgent 6. [10] Prove byin

Question

Kinldy Answer Q no 05 and than Qno 06 I need it really urgent

6. [10] Prove byinduction that your closed formula from 5(c) is the number of times that the givenstatement is executed for a problem of size n.Note: if your proof is simply a proof that you have a correct closed formula for your recurrence from 5(c), then you will not get anymarks for this question. Your proof must refer back to the program in order to be correct. The lines of the code are numbered in order to makeiteasier for you to refer to them in your proof.
The Java code for this question:

5. Consider the ReadRear Java method given on the last page of this assignment. (a) [10] Draw pictures that show the data structure each time a checkpoint is reached for the problems of sizes one, two, three and four specified as input as follows (same format as for assignment #1 Part B: the first integer n-digit is the number of items in the list and this is followed by n_digit integers) 278 3654 4 1302 and indicate for each instance, the number of times the marked statement is executed while creating the linked list. [5] A loop invariant is a statement about a loop used to prove properties about a loop. Fill in a correct function for f(k) in the following loop invari- ant and then prove that your loop invariant is correct by induction. (b) 3- Loop invariant: At checkpoint #2 of the kh teration of the while loop, the current pointer will be pointing to cell number f(k) on the linked list where the cells are numbered starting with cell [5] Set up a recurrence which counts the number of times that the statement with the comment /I Statement to count. is executed for a given value of n and justify your formula. [5] Solve your recurrence from (c) to get a closed formula. one (c) (d)

Explanation / Answer

(c) T(n) = T(n-1) + n-2 for n>1
T(1) = 0

(d)

For basic condition: let n = 2. Then first time the condition "while (current.next != null)" is encountered then there is only one number in the list. So current.next is null, so loop is never entered.
So T(2) must be 0.
From the relation T(2) = T(1)+0 = 0

Let us assume T(n) has the right answer for the count of statement. For calculating T(n+1), first we have to add n numbers. The number of times the statement is executed is same as T(n). Now while we are going to add the (n+1) number, current will start from beginning. The loop will stop only when we reached the nth number, so to go from 1st to nth number, there has to be n-1 executions of current = current.next.

So T(n+1) = T(n) + n-1

Hence proved by induction.

Related Questions

Navigate

• Browse (All)
• Browse K
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.