1.12. The method for solving au + bv = gcd(a, b) described in Section 1.2 is some- what inefficient. This exercise describes a method to compute u and v that is well suited for computer implementation. In particular, it uses very little storage. (a) Show that the following algorithm computes the greatest common divisor g of the positive integers a and b, together with a solution (u, v) in integers to the equation au + bv = gcd(a, b). 1. Set u = 1, g = a, x=0, and y = b 2. If y = 0, set v = (g- au)/b and return the values (g, u, v) 3. Divide g by y with remainder, g = qy+t, with 0≤ 0. Modify your program so that it returns a solution with u > 0 and u as small as possible. [Hint. If (u, v) is a solution, then so is (u+b/g, v-a/g).] Redo (c) using your modified program.

1.12. The method for solving au + bv = gcd(a, b) described in Section 1.2 is some- what inefficient. This exercise describes a method to compute u and v that is well suited for computer implementation. In particular, it uses very little storage. (a) Show that the following algorithm computes the greatest common divisor g of the positive integers a and b, together with a solution (u, v) in integers to the equation au + bv = gcd(a, b). 1. Set u = 1, g = a, x=0, and y = b 2. If y = 0, set v = (g- au)/b and return the values (g, u, v) 3. Divide g by y with remainder, g = qy+t, with 0≤ 0. Modify your program so that it returns a solution with u > 0 and u as small as possible. [Hint. If (u, v) is a solution, then so is (u+b/g, v-a/g).] Redo (c) using your modified program.

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

Related questions

Q: 3.6 Describe the recursive subproblem for this problem. In other words, fill in the blank below:…

A: maxCalories[x] = # for all i from 0 to n-1

Q: Now suppose that n is not 2i for any integer i. How would we change the algorithm so that it handles…

A: If you are wondering just how slowly a program can run, consider the algorithm below. Assume the…

Q: Use NumPy to complete the following task(s). 6. Solve Assignment 5.1 #2a. [2 2 3 4] 02 32 0 0 1 1 Lo…

A: Linear algebra is a fundamental branch of mathematics that deals with the study of vectors, vector…

Q: a) Give a recursive algorithmto solve the following recursive function (hint: use Fibonacci as a…

A: It is an algorithm which calls itself for solving smaller sub problems which operates on subset of…

Q: Let A[1...n,1...n] be a 2D array of positive integers with n rows and n columns. Let…

A: Answer :

Q: Use Numpy to complete the following task(s). 9. Solve Assignment 5.1 #4b. 4. Let A = [2] b. Confirm…

A: Define the matrix A.Define the identity matrix I with the same dimensions as A.Subtract 3 times the…

Q: #include using namespace std; int genFibonacci(int n) { int fibo[n+2]; fibo [0] = 0; fibo[1] = 1;…

A: - We need to explain the question provided regarding dynamic programming.

Q: In chess, a walk for a particular piece is a sequence of legal moves for that piece, starting from a…

A: a) If you find the solution doubtful or doesn't match with your answer provided, or you feel that I…

Q: Problem 5 Simplify the following CFG using the three simplification techniques introduced in our…

A: Simplify the CFG using three simplification technique

Q: Suppose there is a robot that builds a copy of itself in 2 hours. The copy then starts to build…

A: The solution is given below for the above given question:

Q: A certain recursive algorithm takes an input list of n elements. Divides the list into yn sub-lists,…

A: Answer: I have given answered in the handwritten format in brief explanation.

Q: Consider the set A = {blue, yellow, green}. Prove or disprove the statements below. a) Vx E A, x…

A: Given Data : Set A = { blue , yellow , green }

Q: orithms to enumerate these sets. (You do not need to discuss the mechanics of constructing Turing…

A: It is defined as a step-by-step procedure that defines a set of instructions that must be carried…

Q: b) Determine all values of x for which [p(x) ^q(x)]^r(x) results in a true statement.

A: Given additional information: r(x): x>0 (open statement, true for all positive integers) p(x): x…

Q: Write a program for solving summation puzzles by enumerating and testing all possible…

A: Make a PuzzleSolve class. Determine the amount of unique letters in the equation in the…

Q: a. Correctness of dynamic programming algorithm: Usually, a dynamic programming algorithm can be…

A: “Since you have posted multiple questions, we will provide the solution only to the first question…

Q: olve using JAVA only Given a square chess board of size N, solve the N queens problem. ONLY…

A: Solved using Java only

Q: Problem 2 Consider a recursion relation of the form with initial condition an. Part A an= pan-1+1…

A: The function can be defined in such a way that it computes the nth term of the recursion relation an…

Q: A. Construct a RECURSIVE solution for following iterative solution to find a value in a…

A: code- public boolean findRecursive(T value) { if (this.cur == null) return false; //get…

Q: Consider a recursive function, called f, that computes powers of 3 using only the + operator. Assume…

A: The question presents two recursive functions to compute powers of 3 using only the addition…

Q: Give a recursive definition for the set of all strings of a’s and b’s that begins with an a and ends…

A: GIVEN: Give a recursive definition for the set of all strings of a’s and b’s that begins with an a…

Q: Consider a scenario in which you are presented with a data set of length K. Write a simple recursive…

A: Recursive Algorithm:- A recursive algorithm is one that uses "smaller (or simpler)" input data to…

Question

1.12. The method for solving au + bv = gcd(a, b) described in Section 1.2 is some-
what inefficient. This exercise describes a method to compute u and v that is well
suited for computer implementation. In particular, it uses very little storage.
(a) Show that the following algorithm computes the greatest common divisor g of
the positive integers a and b, together with a solution (u, v) in integers to the
equation au + bv = gcd(a, b).
1. Set u = 1, g = a, x=0, and y = b
2. If y = 0, set v = (g- au)/b and return the values (g, u, v)
3. Divide g by y with remainder, g = qy+t, with 0≤<t<y
4. Set s = uqx
5. Set ux and g = y
6. Set xs and y = t
7. Go To Step (2)
(b) Implement the above algorithm on a computer using the computer language of
your choice.
(c) Use your program to compute g
-
gcd(a, b) and integer solutions to the equa-
tion au + bv = g for the following pairs (a, b).
(527, 1258)
(228, 1056)
(i)
(ii)
(iii)
(163961, 167181)
(iv) (3892394, 239847)
(d) What happens to your program if b = 0? Fix the program so that it deals with
this case correctly.
(e) It is often useful to have a solution with u > 0. Modify your program so that
it returns a solution with u > 0 and u as small as possible. [Hint. If (u, v) is a
solution, then so is (u+b/g, v-a/g).] Redo (c) using your modified program.

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1: Introduction

VIEW

Step 2: Solution with Explanation

VIEW

Solution

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 3 steps with 4 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

The recursive algorithm below takes as input an array A of distinct integers, indexed between s andf, and an integer k. The algorithm returns the index of the integer k in the array A, or ?1 if the integerk is not contained within A. Complete the missing portion of the algorithm in such a way that you makethree recursive calls to subarrays of approximately one third the size of A.• Write and justify a recurrence for the runtime T(n) of the above algorithm.• Use the recursion tree to show that the algorithm runs in time O(n).FindK(A,s,f,k)if s < fif f = s + 1if k = A[s] return sif k = A[f] return felseq1 = b(2s + f)=3cq2 = b(q1 + 1 + f)=2c... to be continued.else... to be continued.
An argument is expressed in English below. The domain is the set of people attending a party. Every person who was late to the party left the party early. There is a person who was late to the party and was not happy. .. There is a person who left the party early and was not happy. The form of the argument is: x (P(x) → Q(x)) 3X (P(x) ^ ¬R(x)) .: 3x (Q(x) ^ ¬R(x)) Select the definitions for predicates P, Q, and R. P(x): Pick Q(x): Pick R(x): Pick
Let ∑={a,b} and T be the set of words in ∑* that have no consecutive a’s (i.e. there cannot be 2 or more a’s in a row). (a) Give a recursive definition for the set T. (b) Use your recursive definition to show that the string “abbaba” is in T. (c) Is your recursive definition uniquely determined? Explain why or why not.
Design and implement a program that implements Euclid’s algorithm for finding the greatest common divisor of two positive integers. The greatest common divisor is the largest integer that divides both values without producing a remainder. In a class called DivisorCalc, define a static method called gcd that accepts two integers, num1 and num2. Create a driver to test your implementation. The recursive algorithm is defined as follows:gcd (num1, num2) is num2 if num2 <= num1 and num2evenly divides num1gcd (num1, num2) is gcd(num2, num1) if num1 < num2gcd (num1, num2) is gcd(num2, num1%num2) otherwise
The correct statements are: A set is countable iff it is either finite or countably infinite. The set of natural numbers is countable. The power set of the set of natural numbers is countable. For any Σ Ø, Σ* is countably infinite.
a. Given the following recursive mysterious method (in pseudocode), can you figure out what it computes? b. What is the time complexity? c. What would the following method return when the array is i. [38, 24, 10, 22, 6, 9, 5, 12] ii. [10, 14, 19, 26, 31, 42, 27, 44] [14, 16, 15, 17, 18, 20, 29, 10] initially called as MysteryEven(array, size, 1) boolean MysteryEven(int array, int size, int element){ if (element > size/2) return true; one= 2*element: two= 2*element+1; if (two array[one] || array[element] > array[two]) return false; else return true && MysteryEven(array, size, element++); 거 else if (array[element]> array[one]) return false; else return true;
Problem 4 We can use lists of numbers like l to represent a mathematical vector. Recall from math classes that a vector is an object with a magnitude and direction. The magnitude is the sqrt of the sum of the squares (for a vector (x,y) it's the Pythagorean theorem for the magnitude (x^2 + y^2)**(1/2)). For a vector of any other length, the formula generalizes to (l[0]^2 + l[1]^2 + l[2]^2 + ... )**(1/2). For this problem use l from Problem 1 and a for loop to compute the magnitude of l with the result stored in l_mag. For l above, its magnitude is 12.96. Python gives you the ** exponentiation operator to raise a number to a power. You could also import math and use math.sqrt(). l = [1, 2, 3, 4, 5, 7, 8] Please give proper explanation and typed answer only.