2. For this problem consider the Average problem stated below. Average Input: A sequence of n integers A= (a), a2 . am). Output: meQ such that m=- a, a) Using pseudocode state an algorithm that solves the Average problem using a loop. b) Identify the loop invariant for the loop in your algorithm that will help you prove your algorithm is correct. That is, state the loop invariant as a proposition of the kind "After iteration i of the loop.". c) Using induction prove that your loop invariant holds for each iteration i. d) Using the loop invariant show that your algorithm is correct.

2. For this problem consider the Average problem stated below. Average Input: A sequence of n integers A= (a), a2 . am). Output: meQ such that m=- a, a) Using pseudocode state an algorithm that solves the Average problem using a loop. b) Identify the loop invariant for the loop in your algorithm that will help you prove your algorithm is correct. That is, state the loop invariant as a proposition of the kind "After iteration i of the loop.". c) Using induction prove that your loop invariant holds for each iteration i. d) Using the loop invariant show that your algorithm is correct.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

A problem called S reduces to a problem called T if a T solver can be used as a subroutine to solve S. In pseudocode: Solves(...): ... SolveT(...) ... Assuming that this reduction is correct, answer the following questions regarding what the reduction tells us. If we know that an algorithm exists for solving Problem S, what does that tell us about Problem T? [ Select] If we know that an algorithm cannot exist for solving Problem S, what does that tell us about Problem T? [ Select] If we know that an algorithm exists for solving Problem T, what does that tell us about Problem S? [ Select ] [ Select ] An algorithm cannot exist for solving Problem S,r solving Problem T, what does that tell us about Nothing An algorithm exists for solving Problem S
A problem called S reduces to a problem called T if a T solver can be used as a subroutine to solve S. In pseudocode: Solves(...): ... SolveT(...) Assuming that this reduction is correct, answer the following questions regarding what the reduction tells us. If we know that an algorithm exists for solving Problem S, what does that tell us about Problem T? [ Select ] [ Select ] An algorithm exists for solving Problem T An algorithm cannot exist for solving Problem T solving Problem S, what does that tell us about Nothing If we know that an algorithm exists for solving Problem T, what does that tell us about Problem S? [ Select ] If we know that an algorithm cannot exist for solving Problem T, what does that tell us about Problem S? [Select ]
4. Consider the following recursive algorithm. ALGORITHM Q(n) //Input: A positive integer n if n = 1 return 1 else return Q(n – 1) + 2 * n – 1 a. Set up a recurrence relation for this function's values and solve it to deter- mine what this algorithm computes. b. Set up a recurrence relation for the number of multiplications made by this algorithm and solve it. c. Set up a recurrence relation for the number of additions/subtractions made by this algorithm and solve it.
A. Construct a RECURSIVE solution for following iterative solution to find a value in a circular-linked list B. Analyze the runtime complexity (correctly explain the scenario, show how much work would be done, and represent the work using asymptotic notations, i.e. big O), of the given iterative solution and your recursive solution for the best case scenario and the worse case scenario. C. prove the correctness of your recursive solution by induction /**@param value - a value to search for@return true if the value is in the list and set the current reference to itotherwise return false and not updating the current reference*/public boolean find(T value){ if(this.cur == null) return false; //get out, nothing is in here Node<T> tmp = this.cur; //start at the current position if(tmp.data == value) return true; // found it at the starting location tmp = tmp.next; //adv. to next node, if there is one while(tmp != cur) { if(tmp.data == value){ this.cur = tmp;…
In the divided and conquer algorithm for computing the maxima set of a given set A of n points in 2D, we split the points into left and right halves, recur on each half, and then merge the results. Let MSL and MSR be the return value of these recursive calls. Which of the following statements is true about these sets. Select all that apply. MSR is a maximum set of the right half. Every point in MSL belongs in the maximum set of A. MSL is a maximum set of the left half. Every point in MSR belongs in the maximal set of A.
Write a fraction calculator program that adds, subtracts, multiplies, and di-vides fractions. Your program should check for the division by 0, have and use the following functions (a) reduce - reduces a given fraction.(b) flip - reduces a given fraction and flips the sign if the denominator is negative.(c) add - finds the reduced sum of a pair of given fractions.
Q2. The following algorithm returns the product of two numbers, a and b. The parameters x and y are natural numbers. First, prove the correctness of the algorithm. Then, analyze the time complexity of the algorithm in the worst case scenario. function mult (a, b) if b = 0: return 0 else if b is odd: return (mult (2a, b/2 ) +a) else: return (mult (2a, b/2 ) )
Determine and prove the loop invariant (initialization, maintenance and termination) for the following pseudocode. Make sure that the loop invariant tells something about the functionality of the following pseudocode. Notes that are worth taking: The following pseudocode is a Euclidian Algorithm that computes for the GCD of two integers.
Please do not give solution in image format thanku Implement the following recursively using sudo code: Suppose an elevator which is on a floor on n. For this elevator to go from the nth floor to the base(ground) floor, it should go to every floor under the nth floor. Let's consider an elevator on the 4th floor. This elevator 1st comes on the third(3rd) floor. 4th-> 3rd then 3rd-> 2nd then 2->1 and next 1->0(ground floor) The recursive equation defined is F(n)=1+F(n-1)
L 1. a. Write an algorithm to permutate the given 'n' numbers a₁, az, a3, ... an to a'1 < a'2 < a'3<...< a'n within e(n) in best-case scenario. b. Derive the worst-case tight-bound notation of the algorithm stated in Question 1.
Correct answer will be upvoted else downvoted. you can choose any substring of a containing exactly k characters 1 (and arbitrary number of characters 0) and reverse it. Formally, if a=a1a2…an, you can choose any integers l and r (1≤l≤r≤n) such that there are exactly k ones among characters al,al+1,…,ar, and set a to a1a2…al−1arar−1…alar+1ar+2…an. Find a way to make a equal to b using at most 4n reversals of the above kind, or determine that such a way doesn't exist. The number of reversals doesn't have to be minimized. Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤2000). Description of the test cases follows. Each test case consists of three lines. The first line of each test case contains two integers n and k (1≤n≤2000; 0≤k≤n). The second line contains string a of length n. The third line contains string b of the same length. Both strings consist of characters 0 and 1. It is guaranteed that the sum of n over all…
Python Programming Lab: You are given N sets of integers A1,A2,…,AN. For each valid i, let's denote the elements of the set Ai by {ci,1,ci,2,…,ci,|Ai|}. Find the number of ways to choose a sequence (a1,a2,…,aN) such that: ai∈Ai for each valid I ai≠ai+1 for each valid i and a1≠aN. Since this number may be large, compute it modulo 998,244,353. Write a python code to print a single line containing one integer the number of ways to choose (a1,a2,…,aN) Input Case: 3 3 1 2 3 2 1 2 2 2 3 Output: 3