Computers and Technology, 11.11.2019 21:31 AshantiLiz990

Consider the following program specification: input: an integer n > 0 and an array - 1)] of n integers. output: the largest index s such that a[s] is the smallest value in - 1)].for example, if n = 10 and a = [ 4, 8, 1, 3, 1, 5, 4, 7, 1, 2 ] (so a[0] = 4, a[1] = 8, then the program would return 8, since the smallest value in a is 1 and the largest index at which 1 appears is index 8.consider the following implementation: indexofmin(n, a)(1) i ← 1(2) m ← a[0](3) s ← 0(4) while i < n(5) if a[i] ≤ m then(6) m ← a[i](7) s ← i(8) end(9) i ← i + 1(10) end(11) return s
in the implementation above, line numbers are given so you can refer to specific lines in your answers and ← is used to indicate assignment. part a (18 points)use induction to establish the following loop invariant right before the while test in line (4) is executed: 0< i ≤ nm = a[s]m = min a[0 .. (i - 1)] (i. e., m is the minimum value in that appears in the array a between indices 0 and i - 1, inclusive)s is the largest index at which min a[0 .. (i - 1)] appears
hints and tips: use only one induction proof and prove each of the four parts of the invariant in your base case and inductive step. you may assume that i and s will always be integers (i. e., you don't have to prove this).part b (7 points)prove the correctness of the implementation by arguing partial correctness and termination.

Answers: 3

Show answers

Another question on Computers and Technology

Computers and Technology, 21.06.2019 20:30

Write 150 words on what kind of website would you like to make in the future? what sites would you like to model yours after?

Answers: 2

Answer

Computers and Technology, 22.06.2019 19:50

Write a car class having two private member variables called tank and speed. write public methods called pumpgas and gofast. the method pumpgas gets an integer for gas that must be pumped. that value needs to be added to tank (no more than 20 gallons). it must return the amount of gas that is purchased ($4 per gallon). the method gofast should increase the speed by 5 each time it is called.write a constructor for the above class that initialized both variables to zero.write a tostring to display both the tank and speed when the car is printed.modify the car class to implement the interface comparable and an interface called carinter having the public methods in carinter.write the main program to create an array of size 5 of type car. create 5 car objects having each location of the array to refer to one of the cars. test the pumpgas, gofast, equals method on the array items. write an enhanced loop to print all the car values (using a tostring written last time).write a generic method to find the minimum of four items. pass int, double, char, string and car objects to test this method.

Answers: 1

Answer

Computers and Technology, 23.06.2019 10:20

Suppose there is a relation r(a, b, c) with a b+-tree index with search keys (a, b).1. what is the worst-case cost of finding records satisfying 10 < a < 50 using this index, in terms of the number of records n1, retrieved and the height h of the tree? 2. what is the worst-case cost of finding records satisfying 10 < a < 50 and 5 < b < 10 using this index, in terms of the number of records n2 that satisfy this selection, as well as n1 and h defined above? 3. under what conditions on n1 and n2, would the index be an efficient way of finding records satisfying the condition from part (2)?

Answers: 1

Answer

Computers and Technology, 23.06.2019 19:30

What are loans to a company or government for a set amount of time

Answers: 1

Answer

You know the right answer?

Consider the following program specification: input: an integer n > 0 and an array - 1)] of n...

Questions