Problem 1 Using Euclidean Algorithm, Find gcd(1750; 201): Problem 2 (a)List all
ID: 3814687 • Letter: P
Question
Problem 1 Using Euclidean Algorithm, Find gcd(1750; 201):
Problem 2 (a)List all the steps used by Maximum Finding Algorithm to Önd the maximum of the list 10; 12; 9; 15; 2; 14 (b) List all the steps used to search for 6 in the sequence 2; 4; 5; 7; 6; 8; 9; 11 using the linear search algorithm.
Problem 3 Build the Hu§man coding tree for the string "taaaakkkkeeeehoome". What is the total number of bits needed to encode the string?
Problem 4 List all the steps used to search for 6 in the sequence 1; 3; 4; 5; 7; 6; 8; 9; 10 using the binary search algorithm.
Explanation / Answer
Solution for Problem 1:
The Euclidean algorithm is a technique for quickly finding the Greatest Common Divisor of two integers.
The algorithm to find the GCD(A, B) is as follows:
Let's consider the given problem now. We have to find the GCD(1750, 201).
Here, A = 1750 and B = 201.
Step 1: As none of the integers is 0, which means we have to write A in the quotient form (use long division method to find that 1750/201 = 8 with a remainder of 142) which is:
1750 = (201 x 8) + 142
Now finding the GCD(201, 142)
Step 2: Here A = 201, B = 142. Again none of the integers are 0, which means we have to write 201 in quotient form as:
201 = (142 x 1) + 59
Now finding GCD(142, 59).
Step 3: Here A = 142, B = 59. None of the integer's 0. Writing 142 in quotient form|:
142 = (59 x 2) + 24
Finding GCD (59, 24)
Step 4: Now A = 59, B = 24, none of the integer's being 0, writing 59 in quotient form:
59 = (24 x 2) + 11
Now to find GCD(24, 11).
Step 5: In a similar fashion GCD(59, 24) = GCD(24, 11) = GCD(11, 2) = GCD(2, 1) = GCD (1, 0)
Step 6: At this step GCD(1, 0), we have A = 1 and B = 0. Since B = 0, the GCD(A, B) = A which is 1.
Hence the GCD(1750, 201) = 1.
Hope this helps...
BEST WISHES!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.