Solved: 1. A. (20p) Give a Big-O estimate that is as good as possible for each of the following functions. i. (n^3 + n)(logn + n) ii. (n + 1000)(logn + 1) B. (15p) If these are complexities of algorithms that solve the same problem, which one would you prefer? Why? C. (15p) Considering the Big-O complexity, how many times is your choice faster with respect to the other solution for an input size of 2^16? Note: The base of logarithm is 2

Show that whether x5 + 10x3 + x + 1 is O(x4) or not?

Obtain the sum – of – products and product - of - sum canonical form for 𝑥1⨁(𝑥2 ⋆ 𝑥3 ′ )

Determine the cardinality of each of the sets, A, B, and C defined below, and prove the cardinality of any set that you claim is countably infinite. A is the set of negative odd integers B is the set of positive integers less th…

3. Let P(x), Q(x), and R(x) be the statements “x is a professor,” “x is ignorant,” and “x is vain,” respectively. Express each of these statements using quantifiers; logical connectives; and P(x), Q(x), and R(x), where the domain cons…

Write the forpseudocode an algorithm that determines if a function is injective, assuming that you can iterate through all the elements in the domain and the co-domain in a finite number of steps. Recall the insertion sort algorithm …

Determine the cardinality of each of the sets, A, B, and C defined below, and prove the cardinality of any set that you claim is countably infinite. A is the set of negative odd integers B is the set of positive integers less th…

Show that whether x5 + 10x3 + x + 1 is O(x4) or not?

Using a truth table, prove or disprove the following: ~[(~p∧q)↔ r]≡ ~(p∨~q)↔ ~r

Show that the hexadecimal expansion of a positive integer can be obtained from its binary expansion by grouping together blocks of four binary digits, adding initial zeros if necessary, and translating each block of four binary digits…

Use properties of Boolean algebra to simplify the following Boolean expression (showing all the steps): (x + y′)(x′ + y′)′

Find the inverse of 35 modulo 11 by using extended Euclidean Algorithm

Construct a truth tabal for each of these compound proposition

Give the truth value. P-~q,if q-~p is false

Define a relation T from R to R as follows: For all real numbers x and y (X,y) E T means that y^2- x^2= 1. Is T a function? Explain

Determine whether each of these pairs of sets are equal. (1 pt each) a) {1,3,3,3,5,5,5,5,5}, {5,3,1} b) {{1}}, {1,{1}} c) ∅, {∅}

Let A = { 0,2,4,6,8,10 }, B = { 0,1,2,3,4,5,6 }, and C = { 4,5,6,7,8,9,10 }. (2 pts each) Find a) A ∩ B ∩ C b) A ∪ B ∪ C c) ( A ∪ B) ∩ C d) ( A ∩ B) ∪ C

Using a truth table, prove or disprove the following: ~[(~p∧q)↔ r]≡ ~(p∨~q)↔ ~r

For each proposition below, decide whether it is true or false and give a brief explanation. Assume the universe (domain of variables) to be Z, the set of integers. (1) ((x = 5) ∧ (y = 1)) → ((x > 10) ∨ (y > 0)) (2) ∀x((x < 0) ∨ (x^…

Rahul left his cycle in a parking lot that is filled with bikes and cycles, parked neatly in several rows. When he returns, he notices someone push all the vehicles on the left end of each row, causing them to fall. Rahul knows that…

In the game of poker, five cards are drawn from a deck of 52 cards. A set of 5 cards is said to be a hand. [A standard 52-card deck contains four suits of 13 cards each. The suits are spades (♠), clubs (♣), hearts (♥) and diamonds(♦…

Let R ⊆ S × S be an equivalence relation on a set S. For an element x ∈ S, let S(x) = {y ∈ S : (x, y) ∈ R}. Show that for every pair of elements x, y ∈ S, either S(x) = S(y) or S(x) ∩ S(y) = ∅.

Let A={a, b, c}, B={d, e}, C={a, d}. Find (i) A × B (ii) B × A (iii) A × (B C) (iv) (A C) x B (v) A ∆ (B – C) (vi) Complement of (A ∆ B) (vii) P(B C)

Find the singleton sets and the pair of disjoint sets from the following 1. A = {x |x and x4 − 4 =0} and B = {y | y and x4 − 16 =0 =0}.

Determine for which positive integer values of n, 3n^3+2≤n^4 and prove your claim by mathematical induction. I was able to determine n must be greater or equal to 4. But I can't seem to get through the inductive step.

Using the definition of "Big-O" determine if each of the following functions, f(x) = (xlogx)^2 - 4 and g(x) = 5x^5 are O(x^4) and prove your claims.

In how many ways can a set of five letters be selected from alphabets

For each proposition below, decide whether it is true or false and give a brief explanation. Assume the universe (domain of variables) to be Z, the set of integers. (1) ((x = 5) ∧ (y = 1)) → ((x > 10) ∨ (y > 0)) (2) ∀x((x < 0) ∨ (x^…

Let R ⊆ S × S be an equivalence relation on a set S. For an element x ∈ S, let S(x) = {y ∈ S : (x, y) ∈ R}. Show that for every pair of elements x, y ∈ S, either S(x) = S(y) or S(x) ∩ S(y) = ∅.

Let A = {l, m, m, m, n, n, n, p, p, p} and B = {l, l, m, n, n, n, p, r, r}, find the operations of the following multisets: A. A + B B. A - B C. A U B D. A ∩ B

Using a truth table, prove or disprove the following: ~[(~p∧q)↔ r]≡ ~(p∨~q)↔ ~r

Consider the functions from the set of students in a discrete mathematics class. Under what conditions is the function one-to-one if it assigns to a student his or her a) mobile phone …

Suppose that p and q are any statements. By constructing the truth tables, show that the statement ¬ (p V q) & (¬ p) ∧ (¬ q) are logically equivalent.

Define the following terms using mathematical notations. Also provide example for each term- Subset Universal set Power set

Show the following operations on set(s)- Complement of a set Symmetric difference of two sets

Use mathematical induction to prove the following: An = (1 3n − 1 0 3n) for all integers n ≥ 1, where A = (1 2 0 3) After you have proved the above statement using mathematical induction, write a MATLAB program to veri…

Which is the most suitable graph representation scheme for a dense graph? Draw its representation with the help of an example. What is the space complexity of a such graph representation scheme?

Suppose T(n) and f(n) and two functions. Write asymptotic notations (Ο, Ω, Θ) using these two functions and explain the growth rate of these functions in each notation.

20. Give an example of a function from N to N that is a) one-to-one but not onto. b) onto but not one-to-one. c) both onto and one-to-one (but different from the iden- tity function). d) neither one-to-one nor onto.

Identify whether the given path in the graph is (a) A simple path (b) A cycle (c) A simple cycle (i) (b, b) (ii) (a, d, c, d, e) (iii) (e, d, c, b) (iv) (d, c, b, e, d) (v) (a, d, c, b, e)

Draw a graph having the given properties (a) Four vertices each of degree 1 (b) Six vertices each of degree 3

Determine the truth value of each of these statements if the domain for all variables consists of all integers. a) ∀n(n2 ≥ 0) b) ∃n(n2 = 2) c) ∀n(n2 ≥ n) d) ∃n(n2 < 0)

Given three sets A, B, and C. Suppose we know that the union of the three sets has cardinality 182. Further, |A| = 92, |B| = 41, |C| = 118. Also, |A ∩ B| = 15, |A ∩ C| = 42, and |A ∩ B ∩ C| = 10. Find |B ∩ C|.

Show that (p → q) → (r → s) and (p → r) → (q → s) are not logically equivalent. The dual of a compound proposition that contains only the logical operators ∨, ∧, and ¬ is the compound proposition obtained by replacing each ∨ by ∧,…

Given three sets A, B, and C. Suppose we know that the union of the three sets has cardinality 182. Further, |A| = 92, |B| = 41, |C| = 118. Also, |A ∩ B| = 15, |A ∩ C| = 42, and |A ∩ B ∩ C| = 10. Find |B ∩ C|.

Given three sets A, B, and C. Suppose the the union of the three sets has cardnality 280. Suppose also that |A| = 100, |B| = 200, and |C| = 150. And suppose we also know |A∩B| = 50, |A∩C| = 80, and |B∩C| = 90. Find the cardinality of …

Out of 300 students taking discrete mathematics 60 take coffee , 27 take coco, 36 take tea, 17 take tea only, 47 take chocolate only, 7 take chocolate and coco, 3 take chocolate tea and coco, 20 take coco only, 2 take tea, chocolate a…

{(1,2), (3,5)} is a partition of {1,2,3,4,5}?

1.) {(1,2), (3,5)} is a partition of {1,2,3,4,5}? let s={1,2,3}. in each case give an example of relation r on s that has the stated properties 2.) r is not symmentric, not reflexive and not transitive. 3.) r is transitive and re…

1. Show that in any set of six classes, each meeting regularly once a week on a particular day of the week, there must be two that meet on the same day, assuming that no classes are held on weekends. 2. Show that if there are 30 …

C. Given A= {d}, B= {c, d}, C= {a, b, c}, D = {a, b}, E= {a, b, d}. Determine whether the following statements are True or False. 10. 𝐴 ⊂ 𝐵 11. 𝐶~𝐷 12. 𝐷 ⊈ 𝐸 13. n(C) =3 14. C and D are joint sets 15. E has 16 subsets D…

6-7. A = {the set of the first 5 positive integers divisible by 10} 8-9 C = {Cavite, Laguna, Batangas, Rizal, Quezon}

B.Write the following sets using rule method: 6-7. Write A= {10, 20, 30, 40, 50} using rule method. 8-9. Write C={𝑥|𝑥 𝑖𝑠 𝑎 province in the region of CALABARZON} using roster method

Suppose T(n) and f(n) and two functions. Write asymptotic notations (Ο, Ω, Θ) using these two functions and explain the growth rate of these functions in each notation.

Using a truth table, prove or disprove the following: ~[(~p∧q)↔ r]≡ ~(p∨~q)↔ ~r

List all strings over X = {0,1} of length 2 or less.

Show that A = B where A = {x│x² - 4x +4 =1}, B = {1,3}

Let 𝑄(𝑥, 𝑦) denote "𝑥 + 𝑦 = 𝑦“. What are the truth values of the quantifications ∃𝑦∀𝑥𝑄(𝑥, 𝑦) and ∀𝑥∃𝑦𝑄(𝑥, 𝑦) where the domain for all variables consists of all real numbers?

On each square of a 5 × 5 board, there is a spider. Due to a sudden tremor each spider jumps to an adjacent square (two squares are adjacent if they share an edge). After this happens, is it possible that there is still one spider i…

Each point on a straight line is colored either red or blue. Prove that we can find three points of the same color such that one is the midpoint of the other two.

You have two machines A and B that, each, generate binary digits. On each machine, when the “run” button is pressed, it will generate a single binary digit. Machine A generates a 0 - 52% of the times and a 1 - 48% of the times. Machin…

In Monopoly, your token is allowed to leave the ”jail” cell if you roll doubles: you roll two 6 -sided dice and each shows the same face. Zach hates being in jail, So he invents a couple of weighted dice that are not independent. In p…

Prove or disprove that if R and S are antisymmetric, then so is: (a) (R ∪ S) (b) (R ∩ S)

Refer to a group of 191 students, of which 10 are taking math, business, and language; 36 are taking math and business; 20 are taking math and language; 18 are taking business and language; 65 are taking math; 76 are taking business a…

Consider all strings of length 12, consisting of all uppercase letters. Letters may be repeated. Please do not simplify your answers. (a) How many such strings are there? (b) How many such strings contain the word ”SCOOBY”? (c) How…

Let D=(3,5,7,9) E=( 0, 4, 6, 9) F=0,3,6,7 . Universal set U = 0,1,2,3,4,5,6,7,8,9. Draw venn diagram for. (I) DnEnF (II) (DUE) Uf

Prove by mathematical induction that n^2 +n < 2^n whenever n is an integer greater than 4.

Model the following situations as weighted graphs. Draw each graph, and complete the table below by filling in its direct neighbour. Leave the indirect neighbours as 0. It is well-known that in the Netherlands, there is a 2-lane highw…

What rule of inference is used in each of these argu- ments? a) Alice is a mathematics major. Therefore, Alice is ei- ther a mathematics major or a computer science major. b) Jerry is a mathematics major and a comp…

Write the negation of the following statement: ∀𝑥∃𝑦(𝑥 + 𝑦 = 2 ∧ 2𝑥 − 𝑦 = 1

Let D = {-5, -3, -1, 1, 3, 5}. Write the following statements using only negations, conjunctions and disjunctions: a) ∃𝑥𝑃(𝑥) b) ∀𝑥𝑃(𝑥) c) ∀𝑥((𝑥 ≠ 1) → 𝑃(𝑥)) d) ∃𝑥((𝑥 ≥ 0) ∧ 𝑃(𝑥)) e) ∃𝑥(￢𝑃(𝑥)) ∧ ∀𝑥((𝑥 < 0) → 𝑃(𝑥))

Prove that 2 − 2 · 7 + 2 · 72 −· · ·+2(−7)n = (1 – ((−7)n+1)/4 whenever n is a nonnegative integer

Find a recurrence relation, with initial condition, that uniquely determines each of the following geometric progressions. a) 2, 10, 50, 250, . . . b) 7, 14/5, 28/25, 56/125, . . .

Suppose T(n) and f(n) and two functions. Write asymptotic notations (Ο, Ω, Θ) using these two functions and explain the growth rate of these functions in each notation.

10. 𝐴 ⊂ 𝐵

U= {1, 2, 3, 4, 5, 6, 7, 8, }, A= {1, 2, 3, 4, 5, 7}, B= {1, 5, 6, 7}, C= {1, 2, 3, 6} 16-20. Illustrate the Venn Diagram for the sets A, B, and C.

x is a member of A

Ac - Cc

Show that p ↔ q and (p ∧ q) ∨ (¬p ∧ ¬q) are logically equivalent.

Draw a simple, undirected graph yourself, the vertices are connected with each other including 8 vertices and 14 edges. Find the shortest path from two arbitrary vertices: a) The weight of each edge is 1. b) Self-weighting for…

1. For the following functions, provide the domain and range a) f: . For each x ∈ domain f(x) = cx. b) g: . For each x,y ∈ domain, g(x,y) = yxd.

Are the following functions from R to R? If not, explain why a) f(x) = 1/x b) f(x) = 2x + 7

2. For each function below (from Z to Z), indicate whether the function is onto, one-to-one, neither or both. If the function is not onto or not one-to-one, give an example showing why. If the function is bijective, find and show …

2. Consider three functions f, g, and h (from R to R+). Let f (x) = x2, g(x) = 2x and h(x) = log2(x) a) Evaluate f ◦ g(0) b) Evaluate h ◦ g(5) c) Evaluate h ◦ f(0) d) Give a mathematical expression for h ◦ g e) Give a ma…

2. Indicate if the following statements are possible. Justify your answer. If the answer is “yes”, give a specific example of the functions. Let f: and g: Z be two functions. Use a diagram if that helps explain the function. a)…

2. Provide the first 5 terms of the following sequence, excluding any initially provided terms. Also, indicate which sequences are increasing, decreasing, non-increasing, and/or non-decreasing. a) The nth term is ⌈⌉. b) The nt…

2. Let S = { :(a1a2a3a4∈ N and 0 ≤ ≤ 9 for each i = 1, 2, 3, 4}. In other words, S is the set of all 4-digit strings with each digit between 0 an 9. (a) Show that the function f : S → S deﬁned by f(a1a2a3a4) =a4a3a2a1 is a bij…

State whether or not the following functions have a well-deﬁned inverse. If the inverse is well-deﬁned, deﬁne it. If it is not well-deﬁned, provide justiﬁcation. a) f : Z → Z. f(x) = 7x – 7 b) f : R → R. f(x) = 7x – 7 c) A…

For each list of integers, provide a simple formula or rule that generates the terms of an integer sequence that begins with the given list. Assume the sequence starts with . Do not forget initial conditions if required. a) 7, 11…

List the ordered pairs in the relation R from A = {0, 1, 2, 3, 4} to B = {0, 1, 2, 3}, where (a, b) ∈ R if and only if a) a = b. b) a + b = 4. c) a > b. d) a ∣ b. e) gcd(a, b) = 1. f ) lcm(a, b) = 2.

Show that A ⊕ B = (A ∪ B) - (A ∩ B).

For each of these relations on the set {1, 2, 3, 4}, decide whether it is reflexive, whether it is symmetric, whether it is antisymmetric, and whether it is transitive. a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)…

Determine whether the relation R on the set of all people is reflexive, symmetric, antisymmetric, and/or transitive, where (a, b) ∈ R if and only if a) a is taller than b. b) a and b were born on the same d…

Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a, b) ∈ R if and only if a) everyone who has visited Web page a has also visited Web pa…

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-3391-qpid-2090