Question

In: Computer Science

Question 1 The GCD is the greatest common denominator. Euclid found that if A=Bx +R then...

Question 1

The GCD is the greatest common denominator. Euclid found that if A=Bx +R then GCD(A,B)=GCD(A,R). Prove this is true. Show working

Question 2

The approach Euclid in calculating the GCD used was novel as it was an ________process to solve a complex problem, hence formed the first _______.

Question 3

The difference between a breadth first search (BFS) and a depth first search (DFS) is that in the DFS you traverse all the first branch before proceeding to the next branch.

a) True

b) False

Question 4 If a Graph is defined as a diagram showing the relation between variable quantities, typically of two variables, each measured along one of a pair of axes at right angles, OR a diagram representing a system of connections or interrelations among two or more things by a number of distinctive dots, lines, bars, etc, which is correct?
1. The first definition as graphs need axes
2. The second definition as more general so covers all graphs
3. Neither as they are too vague

Question 5

Find a c such that f(n) is O(n2) when f(n) = 1/4 n2 + 15 n + 115. Justify this answer.

Question 6

If f(n)= 10* log n then Big-O of f(n) is O(n)

a) True

b) False

Expert Solution

I have answered all rather than only 4. Comment for any queries.

Thank you.

venereology answered 1 hour ago

3. In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf)...

3. In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers. The greatest common divisor of a and b is written as gcd (a, b), or sometimes simply as (a, b). For example, gcd (12, 18) = 6, gcd (−4, 14) = 2 and gcd (5, 0) = 5. Two numbers are called co-prime or relatively prime...

Write a C function gcd that returns the greatest common divisor of two integers. The greatest...

Write a C function gcd that returns the greatest common divisor of two integers. The greatest common divisor (GCD) of two integers is the largest integer that evenly divides each of the two numbers.

the following is the euclid 2,300 year old algorithm for fining the greatest common divisorof two...

the following is the euclid 2,300 year old algorithm for fining the greatest common divisorof two positive integers I an J step Operation 1. get two positive integers as input; call the larger value I and the smaller value J. 2. Divide I by J, and call rhe remainder R. 3. If R is no 0, then reset I to the value of J, reset J to the cslue of R, and go back to step 2 4. print out...

Let m, n be natural numbers such that their greatest common divisor gcd(m, n) = 1....

Let m, n be natural numbers such that their greatest common divisor gcd(m, n) = 1. Prove that there is a natural number k such that n divides ((m^k) − 1).

In C++ The greatest common divisor (GCD) of two integers in the largest integer that evenly...

In C++ The greatest common divisor (GCD) of two integers in the largest integer that evenly divides each of the numbers. Write a function called GCD that has a void return type, and accepts 3 parameters (first two by value, third by reference). The function should find the greatest common divisor of the first two numbers, and have the result as its OUTGOING value. Write a main function that asks the users for two integers, and uses your function to...

Using python pls!!!!! Write a recursive function gcd(m,n) that returns the greatest common divisor of a...

Using python pls!!!!! Write a recursive function gcd(m,n) that returns the greatest common divisor of a pair of numbers. The gcd of m and n is the largest number that divides both m and n. If one of the numbers is 0, then the gcd is the other number. If m is greater than or equal to n, then the gcd of m and n is the same as the gcd of n and m-n. If n is greater than...

Find the greatest common divisor d = gcd(527, 341). Show all calculation steps. We assume that...

Find the greatest common divisor d = gcd(527, 341). Show all calculation steps. We assume that the modulus is a positive integer. But the definition of the expression a mod n also makes perfect sense if n is negative. Determine the following: a. 7 mod 4 b. 7 mod -4 c. -7 mod 4 d. -7 mod -4

1. Because it is the common denominator that we use to compare products and decide which...

1. Because it is the common denominator that we use to compare products and decide which ones we will buy, money functions as a(n): a. commercial tool. b. store of value. c. measure of value. d. medium of exchange. e. accepted resource. 2. Your grandmother left you $10,000 in her will with the specific request that you use this money for the down payment on a house. Since you're still in college, you know that buying a house is a...

Question 1 Given two integers x and y, the following recursive definition determines the greatest common...

Question 1 Given two integers x and y, the following recursive definition determines the greatest common divisor of x and y, write gcd(xy). Write a recursive function, gcd, that takes two integers as parameters and returns the greatest common divisor of numbers. Also write a program to test your function. Write a recursive function, reverseDigits, that takes an integer as a parameter and returns the number with the digits reversed. Also write a program to test your application.

For an integer k, define f(k) = gcd(11k + 1, 7k + 3). (a) Compute R...

For an integer k, define f(k) = gcd(11k + 1, 7k + 3). (a) Compute R = {f(k): k ∈ Z}. (b) For each n ∈ R, find a set Dn such that, for every integer k, f(k) = n if and only if k ∈ Dn. Is there any solution without using the 'mod' for b?