Solved: The recursive algorithm given below can be used to compute gcd(a, b) where a and b are non-negative integer, not both zero. procedure gcd(a, b) if a > b then gcd(a, b) := gcd(b, a) else if a = 0 then gcd(a, b) := b else if a = 1 then gcd(a, b) := 1 else if a and b are even then gcd(a, b) := 2gcd(a/2, b/2) else if a is odd and b is even then gcd(a, b) := gcd(a, b/2) else gcd(a, b) := gcd(a, b − a) Use this algorithm to compute (a) gcd(124, 244) (b) gcd(4424, 2111).

12) Suppose that a room contains 10 cats and 15 dogs. How many ways are there to form a committee consisting of 6 of these animals if it must have more dogs than cats?

Let S={a, b, c, d, e}. Find the number of ways to select 7 elements from S when repetition is allowed. The order in which the elements are chosen does not matter

How many solutions are there to the equation x1+x2+x3+x4+x5+x6= 25 where the xi(for i= 1,2,3,4,5,6) are non-negative integers?

Compute the number of distinct arrangements of the characters ABBCCCDDDDEEEEE

How many bit strings can be formed by using seven 1s and nine 0s?

Which is the following statements is True? Every path is a trail but every walk is not a trail Every walk is a trail but every path is not a trail. Both paths and walks are trails. Neither a path nor a walk is a trail 1 point L…

Q.Which of the following can be a degree sequence of a simple graph? {4,4,3,2,1} {4,3,2,1} {4,4,3,2} {4,2,2,2,2} Q.If G is a connected simple graph and e,f and g are edges of G, then which of the following is/are true: There …

Width of a tree is defined as the largest distance(number of edges in the shortest path) between any two vertices. What is the smallest possible width of the tree with 100 vertices? 1 2 99 101 1 point How many complete graphs w…

Find a counter example to the following universally quantified statements, where the domain for all variables consist of all integers. ∀x, x^2, <=x^3.

given: f(n) = 3f(n/2) + 5n^3 where n=2k and f(1) = 2 find f(n) and a big -0 estimate of f(n)

Given: An=3an-1 - 4an-3 + f(n) find the particular soulution an^(p) when a) f(1) = n2(2)^n b) f(n) = n(3)^n

a) How many cards must be selected from a standard deck of 52 cards to guarantee that at least three cards of the same suit are chosen? b) How many must be selected to guarantee that at least three hearts are selected?

Statement: “If n is any even integer, then ” Using Direct proof method

make a truth table (~p∧q) ∨ (p∧~q)

The sum of two even numbers is even. Using Direct proof method

“The product of two odd numbers is odd.” Using Direct proof method

Consider the following sequence of successive numbers of the 2k -th power: 1, 2^2k, 3^2k, 4 ^2k, 5 ^2k, ... Show that the difference between the numbers in this sequence is odd for all k ∈ N.

In a class of 30 students, 11 students like mathematics, 12 students like geography, and 12 students do not like mathematics nor geography. How many students like mathematics and geography

11 integers are arbitrarily chosen. Prove that 2 of them have the same unit digit

There are some people (more than 1 person) in a party. Prove that 2 of them have the same number of friends in the party ( Hint: friendship is a mutual relation)

You have given a function λ : R → R with the following properties (x ∈ R, n ∈ N): λ(n) = 0 , λ(x + 1) = λ(x) , λ (n +1/2)=1 Find two functions p, q : R → R with q(x) not equal to 0 for all x such that λ(x) = q(x)(p(x) + 1).

You have given a function λ:R-> R with the following properties (x ∈ R, n∈ N) : Λ(n) =0, λ(x+1)= λ(x), λ(n+1/2)=1 Find two functions p,q:R-> Rwith q(x) not equal to 0 for all x such that λ(x)= q(x)(p(x)+1)

Let X = {0, 1, 2}. List the elements of each of the following sets: a. {z : z = 2x and x ∈ X} b. {z : z = x + y where x ∈ X and y ∈ X}

Let A = {n ∈ Z | n = 5r for some integer r} and B = {m ∈ Z | m = 20s for some integer s}. a. Is A ⊆ B? Explain. b. Is B ⊆ A? Explain

Let A = {a, b, c}, B = {x, y}, and C = {0, 1}. Find a. A × B × C. b. C × (B × A).

Which of the following are partitions of , the set of real numbers? Explain your answers. a. {In : n ∈ ℤ}, where In = {x ∈ ℝ : n ≤ x ≤ n + 1} b. {Jn : n ∈ ℤ }, where Jn = {x ∈ ℝ: n ≤ x < n + 1}

For each of the following sets, determine its power set. a. A = {a, b, c, d} b. A = {{1}, {1, 2}}

A professor in a discrete mathematics class passes out a form asking students to check all the mathematics and computer science courses they have recently taken. The finding is that out of a total of 50 students in the class, 30 took …

For the proposition(p ∨¬r)∧(¬p∨(q∨¬r) a. Draw the truth table b. Build the logic circuit which outputs the given compound proposition from input bits p, q, and r.

PDNF of p->((p->q)^~(~qv~p))

Obtain DNF for ~(p → (q ^ r)) and also obtain PCNF for (p → q) ^ (qr) without using truth tables.

in a class of 35 students, each student studies Chemistry or woodwork. Twice as many study chemistry as study woodwork and half as many study only chemistry as study both. illustrate the information on a venn diagram and hence find th…

write the relation on {a,b,c,d} in ordered pairs.

Write each statement in symbolic form, using the given symbols. Let p: I will study. Let q: I will pass the test. Let r: I am foolish. 1. I will study or I am foolish. 2. I will study or I will not pass the test. 3. I will study an…

There is an island with two mythical creatures, the Komos and the Dragos. Komos loves eating visitors to the island while Dragos hates to eat visitors. One fine day, you mysteriously end up on the island and encounter two creatures, B…

Write each statement in symbolic form, using the given symbols. Let p: I will study Let q: I will pass the test Let r: I am foolish 1. I will study or i am foolish 2. I will study or i will not pass the test. 3. I will study and I w…

Let us denote Sn = an + bn + cn for arbitrary numbers a, b, c. It is known that S1 = 8, S2 = 66, S3 = 536 for some values of a, b, c. What is the smallest possible value of S242 — S41 S43?

Let A=[top(1 1) bottom (0 1)] be a matrix consisting of real numbers (we are not interpreting this as a bit matrix). Find a formula for An, where n ϵ Z+, and use Mathematical Induction to prove that your formula is correct.

Let A be a square matrix, and AT denotes the transpose of A. Show that the following hold true. (a) (AT)T=A (b) (A+B)T=AT+BT (c) (AB)T=BT AT.

Show that the relation R=∅ on a nonempty set S is symmetric and transitive, but not reflexive.

Show that the relation R=∅ on the empty set S=∅ is reflexive, symmetric, and transitive.

(a) Find the number of relations on the set S={a, b, c, d, e}? (b) How many relations are there on the set S={a, b, c, d, e} that contain (a, a) and (b, b)?

Let S be a set with 6 elements and let a and b be distinct elements of S. How many relations R are there on S such that... (a) (a, b) ϵ R? b) (a; b) ∉ S? (c) no ordered pair in R has a as its first element? (d) at least one ordered pa…

Let R be a reflexive relation on a finite set A, and let MR be the bit matrix representing R. Specify the value of the entries on the main diagonal.

Let R be a symmetric relation on a finite set A, and let MR be the bit matrix representing R. Is MR necessarily a symmetric matrix? Why or why not?

Use Mathematical Induction to show that if MR is the bit matrix representing the relation R, then M^[n]R is the matrix representing R^n. (This was how the question was stated. If you're confused about the terms M^[n]R and R^n, they ar…

Let S be the set of bit strings of length no larger than 6, and define an equivalence relation R on S as follows: (x, y) ϵ R if and only if x and y are of the same length. Specify the partition P of S that arises from R.

Let S ={a, b, c, d, e}, and P={{a, b},{c, d},{e}}. (a) Verify that P really is a partiton of S. (b) Find the equivalence relation R on S induced by P.

Suppose S is a set, and P={S} is a partition of S. Find the equivalence relation R corresponding to P.

Let p and q be distinct positive primes. Define the partial ordering ⪯ of S={1, p, p^2, p^3, p^4, q, q^2, q^3, q^4} as follows: a⪯b if and only if a|b. Draw the Hasse diagram for this partial ordering of S.

Let S={1,2,3,4}, and define a partial ordering of P(S) (the power set of S), by: A⪯B if and only if A⊆B. Is this partial ordering in fact a total ordering (chain)? Why or why not?

Suppose S is a set containing 5 elements, and that ⪯ is a total ordering of S. Draw the Hasse diagram for ⪯ (no need to label the vertices in your diagram).

How many distinct permutations are there of the letters of the word "MARRIAGE"? a.30240 b.40320 c.20160 d.10080

How many 4-digit numbers can be formed from the digits 0, 1, 2, 3, 4, 5 if the first digit must not be 0 and repetition of digits is not allowed? a.300 b.320 c.360 d.280

There are two webcams, X and Y that can automatically switch On or Off at any given time to record a live video streaming session. To ensure the smooth recording session, the live feed input system is programmed with certain criteria.…

Find the Transitive closure by using Warshall’s Algorithm where A= {1, 2, 3, 4, 5, 6} and R= {(x,y)| (x-y)=2}

From a set of numbers 1-15, how many numbers should be picked to form pair of numbers that adds up to 16? Illustrate the solution.

Suppose S is a set containing 5 elements, and that ⪯ is a total ordering of S. Draw the Hasse diagram for ⪯ (no need to label the vertices in your diagram).

Model two contextualized problems using binary trees both quantitatively and qualitatively.

Show graphically that which of the following is one to one function (1)f(x)=ln(x) (2)g(x)=e^x (3) h(x)=x³

(i) Give a formal definition of a graph G and its complement G. (ii) Draw the graph with degree sequence 4, 4, 4, 4, 4, 4 and show that it is unique. (iii) Suppose a graph G has (0, 1) adjacency matrix A(G) = A. Write down the adjacen…

There are two webcams, X and Y that can automatically switch On or Off at any given time to record a live video streaming session. To ensure the smooth recording session, the live feed input system is programmed with certain criteria.…

Prove that log2 3 is irrational.

How many numbers are divisible by 2, 5, 9, and 13 between 100 and 100,000? How to implement this question in discrete math ?

a) Let p, q, and r be the propositions p : You study hard. q : You are on merit r : You do not get degree from Iqra University. Express each of these propositions as an English sentence. i) ¬q ↔ r ii) q →¬ r iii) p∨q ∨¬r iv) (p →¬r)∨(…

b) What is the value of x after each of these statements is encountered in a computer program, if x =3 before the statement is reached? i) if x +2=5 then x := 3*x +5 ii) if (x +1=4) OR (2x +2=3) then x := x +1 iii) if (2x +3=5) AND (3…

Suppose that the domain of the propositional function P(x) consists of the integers 1, 2, 3, 4, and 5. Express these statements without using quantiﬁers, instead using only negations, disjunctions, and conjunctions. a) ∃xP(x) b) ∀xP(x…

a) We have the following set of information about a computer program, find the mistake in the program using Rules of Inferences. i. Either a variable is not declared or there is a syntax error in the fifth line. ii. If there is a synt…

1.Determine whether ¬(p∨(¬p∧q)) and ¬p∧¬q are equivalent without using truth table. 2.Determine whether the compound proposition ~(p∨q)∨(~p∧q)∨p to tautology. 3.Determine whether (p → q)∧(p → r)≡p → (q ∧r) using a truth table

Solve the following recurrence relations i) Fn= Fn-1 +Fn-2 where a1=a2=1 ii) an=2an-1 - an-2 +2 where a1 = 1 and a2 = 5

Use mathimatical Induction to prove that 1²+2²+3²+.......n²= n(n+1)(2n+1) divided by 6

We have the following set of information about a computer program, find the mistake in the program using Rules of Inferences. i. Either a variable is not declared or there is a syntax error in the fifth line. ii. If there is a syntax …

Definition of Function, Domain, Codomain and Range, Well defined function, Types of functions(Injective ,Surjective, Bijective, Composite)

Suppose S is a set containing 5 elements, and that ⪯ is a total ordering of S. Draw the Hasse diagram for ⪯ (no need to label the vertices in your diagram).

Transform by making change of variable j = i-4.

Consider the scenario of Knights and Knaves. You visited that island and met five people there. Suppose those were A, B, C, D, E [10]  A: B is a knight.  B: E is a knight.  C: A is a knave.  D: There are at most two knights a…

Determine the truth value of each of the quantified statements below if the domain consists of R. (a)∃x(x^5 = -1) (b)∃x(x^6< x^4) (c)∀x((-x)4=x^4) (d)∀x(2x > x)

(a) Let S be a set, and define the set W as follows: Basis: ∅ ϵ W.Recursive Definition: If x ϵ S and A ϵ W, then {x} U A ϵ W. Provide an explicit description of W, and justify your answer.

Define r(n, m) : N x Z+ -> N be the remainder obtained when dividing m into n. Define a function fm: N x N -> N as follows: f(n, k) = k if r(n, m) = 0, and f(n, k) = f(n-m, k+ 1) otherwise. Describe in terms of a single well-known ari…

For all parts of this problem, let S be a finite set, with |S|=n. (a) If f:S -> S is onto, does it necessarily follow that f is invertible? Why or why not? (b) Compute the number of distinct functions g:S -> S that are onto. (c) Find …

(a) Define r(n, m) : N x Z+ ->N be the remainder obtained when dividing m into n. Define the function g: Z+ x Z+ ->Z+ as follows: g(a, b) = b if r(a, b) = 0, and g(a, b) = g(b, r(a,b)) otherwise. Describe what g is calculating, and ju…

(b) Find a concise, explicit description for the set A, which is defined by 1 ∈ A, and if a and B are bit strings in A, then aB ∈ A, 0aB ∈ A, a0B ∈ A, and aB0 ∈ A.

(a) We say that two positive integers a, b are relatively prime if the greatest common divisor of a and b is 1. Let p, q be distinct positive prime numbers such that n=pq. Calculate the number of positive integers not exceeding n that…

b) Read Section 2.3.6 (on page 161) of the 8'th edition of Rosen's book on partial functions. Let A and B be finite sets, with |A| = m and |B| = n. Calculate the number of partial functions f: A -> B.

How many ternary strings (i.e., the only allowable characters are 0, 1, and 2) of length 15 are there containing exactly four 0s, five 1s, and six 2s?

How many solutions are there to the inequality x1+x2+x3+x4≤15, where x1,x2,x3, and x4 are nonnegative integers? Hint: Introduce an extra variable x5 and consider x1+x2+x3+x4+x5 = 15.

Suppose a friend asks you to list out all relations on the set S = {n|n ∈ Z+ and n≤1000}. Find the number of number of relations on S. Is your friend making a reasonable request?

Let R be a relation from A to B. Both sets are finite, with |A|=n and |B|=m. Define the complementary relation "R bar" as follows: R bar={(a, b)|(a,b)∈R} Calculate |R bar|.

(a) If A={1,2,3,4}, calculate the number of reflexive relations on A. (b) If B={1,2,3,4,5}, calculate the number of symmetric relations on B.

Let S be a finite set, with |S|=n. If the bit matrix MR representing R contains exactly r entries that are 0, how many entries of MRbar are 0? Note: "MRbar" is supposed to be just like MR, which you should know has R as a s…

Let S be a finite non-empty set. How many relations on S are simultaneously an equivalence relation and a partial order? Justify your answer.

Define a function A: N x N -> N as follows: A(m, n) ={2n, if m= 0; 0, if m≥1 and n= 0; 2, if m≥1 and n= 1; A(m-1, A(m, n-1)), if m≥1 and n≥2 (a) Calculate the following: (i)A(1,0) (ii)A(0,1) (iii)A(1,1) (iv)A(2,2).

Define a function A: N x N -> N as follows: A(m, n) ={2n, if m= 0; 0, if m≥1 and n= 0; 2, if m≥1 and n= 1; A(m-1, A(m, n-1)), if m≥1 and n≥2 Show that A(m, 2) = 4 whenever m≥1. Hint: Induct on m.

Here's the Solution to this Question

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Question ID: mtid-5-stid-8-sqid-754-qpid-639