Solved: Consider the function f(n) = 35n3+ 2n3log(n) − 2n2log(n2) which represents the complexity of some algorithm. (a) Find a tight big-O bound of the form g(n) = np for the given function f with some natural number p. What are the constants C and k from the big-O definition? (b) Find a tight big-Ω bound of the form g(n) = np for the given function f with some natural number p. What are the constants C and k from the big- Ω definition? (c) Can we conclude that f is big−Θ (np) for some natural number p?

At a college of 600 students there are (n+5) enrolled in physics, (n+20) in Mathematics who play sports and (n-15) in chemistry and play sports. Create a Venn diagram to illustrate this information. Where n is your arid number

At a college of 600 students there are (n+5) enrolled in physics, (n+20) in Mathematics who play sports and (n-15) in chemistry and play sports. Create a Venn diagram to illustrate this information. Where n=8

At a college of 600 students there are (n+5) enrolled in physics, (n+20) in Mathematics who play sports and (n-15) in chemistry and play sports. Create a Venn diagram to illustrate this information. Where n is your arid number.

At a college of 600 students there are (n+5) enrolled in physics, (n+20) in Mathematics who play sports and (n-15) in chemistry and play sports. Create a Venn diagram to illustrate this information. Where n=8

If P(k) = k2 (k + 2)(k – 1) is true, then what is P (k + 1)?

. A special type of password consists of six(6) different letters of the alphabet, where each letter is used only once. How many different possible passwords are there? (3 pts) A. 244, 140, 625 B. 308, 915, 776 C. 165,765,600 D. …

Let p: priya is tall and q:priya is beautiful write the following statement in symbolic form. i) Priya is tall and beautiful ii) Priya is tall but beautiful iii) It is false that priya is short or beautiful

The relation 'is the father of' is________. a) reflexive b) irreflexive c) transitive d) symmetric

In a market, 50 women sell only Apple, 25 sell Apple and Banana and 50 sell Banana. Each woman sells at least one the two fruits. How many women are there?

A. COUNTING METHODS 1. How many strings of length 4 can be formed using the letters ABCDE if it starts with letters AC and repetition is not allowed? 2. There are 10 multiple choice questions in an examination. Each of the question…

We want to make a 6 character password such that the password must start and end with a digit. Moreover, one digit must be even and other must be odd. There must be one capital letter. How many such password can we make? Note: Charact…

Let n be 26. Construct a map of a continent having n different countries in such a way that four colours are needed to colour bordering countries in different colours. Using blue for the ocean (and possibly for some of the countries),…

Translate these system specifications into English where the predicate S(x, y) is “x is in state y” and where the domain for x and y consists of all systems and all possible states, respectively. a) ∃xS(x, open) b) ∀x(S(x, malfunc…

Express the negations of these propositions using quantifiers, and in English. a) Every student in this class likes mathematics. b) There is a student in this class who has never seen a computer. c) There is a student in this class…

Let W(x, y) mean that student x has visited website y, where the domain for x consists of all students in your school and the domain for y consists of all websites. Express each of these statements by a simple English sentence. a) …

For each of these arguments, explain which rules of inference are used for each step. a) “Doug, a student in this class, knows how to write programs in JAVA. Everyone who knows how to write programs in JAVA can get a high-paying jo…

Identify the error or errors in this argument that supposedly shows that if ∃xP (x) ∧ ∃xQ(x) is true then ∃x(P (x) ∧ Q(x)) is true. a) ∃xP (x) ∨ ∃xQ(x) Premise b) ∃xP (x) Simplification from (1) c) P (c) Existential instantiation …

What is the Cartesian product A × B × C, where A is the set of all airlines and B and C are both set of allcities in USA? Give an example of how this Cartesian product can be used

A = Q, (a*b) = a + b

The set of all natural number whose square is more than 21.

A. COUNTING METHODS (5 pts each) 1. How many strings of length 4 can be formed using the letters ABCDE if it starts with letters AC and repetition is not allowed? 2. There are 10 multiple choice questions in an examination. Each of…

Determine whether the function f is a bijection from R to R ? Find fog and gof where f(x)=2x2+3 and g(x)=x=1

(A∪B) c (A∪B)c

Write notes on how to find cartesian products of sets and in you concluding page, site examples on the applications of set theory to solving real world business problems

(a) How many code words over a, b, c, d of length 20 contain exactly 10 a’s? (b) How many contain exactly 10 a’s and 5b’s.

4 What is the probability that an arrangement of a, b, c, e, f, g begins and ends with a vowel? 5 Helen wants to buy a bunch of flowers. There are five types of flowers available, namely roses, chrysanthemums, lilies, carnations and …

6 a) Show, using the pigeonhole principle, that in any set of 5 integers, at least two have the same remainder when divided by 4. (b) Use the extended pigeonhole principle to show that there are at least 3 ways of choosing 2 differen…

1 Let a relation R be represented by the following matrix MR = 1000001 1111000  1 0 1 1 0 1 0  MR=1 0 0 1 0 0 0  1 1 0 1 0 0 0  0 1 0 1 1 0 1 0111100   Determine whether R is (a) reflexive (b) irreflexive (c)…

Using Boolean algebra simplify the statement ¬(𝑟 → 𝑠) → (¬𝑟)

Use generating function to prove the identity n ∑ k=o r k s n−k = r +s n

Helen wants to buy a bunch of flowers. There are five types of flowers available, namely roses, chrysanthemums, lilies, carnations and tulips. How many possible bunches of 16 flowers can she choose if the bunch must contain no more th…

an = a 0.5n + n, a1 = 0, where n is a power of 2, is a linear recurrence relation. ( true / falsa ).

Consider the following relation R on A where A = {1, 2, 3, 4, 5} aRb ⇔ a b < min(a, b) For example, 2R4 since 2 4 = 1 2 and min(2, 4) = 2 and 1 2 < 2. (a) Draw the digraph of R (4) (b) Give a path of length 2 from 3, if…

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. {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}

Let S = {a1,a2,a3,...an}be a set of test scores. Prove using the the indirect method of proof that if the average of this set of test scores is greater than 90, then at least one of the scores is greater than 90.

Apply your knowledge gaining from this course in describing how you convert a function into a relation and a relation into a function?

COUNTING METHODS (15 pts) 1. How many 5-digit number can be formed from digits 0 – 6 if: a. If repetition is allowed? (3 pts) b. If repetition is not allowed? (3 pts) c. If one (1) is not to be used as the 1st digit and rep…

PERMUTATIONS (21 pts) 1. There are 6 people to be arranged in a line for a concert. How many arrangements are possible? (3 pts) 2. How many strings of length 5 can be formed using the letters QUALITY if a. Repetitions ar…

COMBINATIONS (24 pts) 1. Patrick has assignments in 5 subjects. He can only do two assignments. In how many ways can he do two assignments? (3 pts) 2. In how many ways can a group of 5 men and 3 women be made out of a total…

BINOMIAL COEFFICIENTS (20 pts) 1. Expand the (2𝑚 − 2𝑏)3 using binomial coefficient. (14 pts) 2. Find for the coefficient of a5b5; (a - 4b )10 (3 pts) 3. Find the 5th term after expanding the expression (3x – 4y)15 (3 pts) …

Solve the following. (35 pts) 1. How many 3-digit number can be formed from digits 1 – 5 if: a. If repetition is allowed? (3 pts) b. If repetition is not allowed? (3 pts) 2. How many strings of length 4 can be formed …

Determine the truth-values of the followings “ 1+1=4 if and only if earth is round” “ Milk is white if and only if birds lay eggs” “ Sky is white if and only if 1=0” “ 33 is divisible by 5 if and only if hours has four legs” “ …

translate to propositional logic “To get tenure as a professor, it is sufficient to be world-famous.”

Decide for each of the following relations whether or not it is an equivalence relation. Give full reasons if it is an equivalence relation, give the equivalence classes. A. Let a,b E Z. Define aRb if and only if (a/b)E Z. B. Let a …

The complete m-partite graph 𝑲𝒏𝟏,𝒏𝟐,……,𝒏𝒎 has vertices partitioned into m subsets of 𝒏𝟏, 𝒏𝟐, … … , 𝒏𝒎 elements each, and vertices are adjacent if and only if they are in different subsets in the partition. For example, if m=2, it is o…

Using mathematical induction prove the following: Σn k=1 k+4/k(k + 1)(k+2) = n(3n + 7)/2(n+1)(n+2)

Let A, B, and C be sets. Show that (B − A) ∪ (C − A) = (B ∪ C) – A by using Venn diagram?

If the statement ∧ r is true, determine all combinations of truth values for p and s such that the statement (q→[¬p∨s])∧[¬s→r] is true.

A∩(B−C)

Determine the truth value of the following statement, if the domain consists of all real numbers. Explain your answer in one sentence only. ∃x(x2=2)

How many 3-digit numbers greater than 300 can be formed using the digits 1, 2, 3, 4, and 5, when (a) repetition is not allowed and (b) repetition is allowed. Briefly explain the calculation process.

Find the solution of the recurrence relation: xn=3xn-1 + 1, where, x0=4

a) Suppose p, q and r mean “Kelly is at home, Hannah is at home and Sunny is at home then interpret the meaning of the statement p ∧∼q and (p ∧ q) ∧ r (b) You should pay the fares for tickets only if you plan to visit northern Pak…

Determine whether ( 𝑝∨𝑞)∧(𝑝→𝑟)∧( 𝑞→𝑠)→𝑟∨𝑠 is a Tautology or a contradiction

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

What are the two types of indirect proofs? Explain through an example for each type.

The sum of the values of the degree 𝜎(V) taken over all the vertices v of a graph .G= (V, E), is equal to twice the number of edges i.e. ∑ 𝜎(𝑣) = 2|E| v∈V. Write a proof to validate the equation.

Fourty (40) students go to a party wearing red, white and blue. Of these students, 17 wear red, 22 wear white, 25 wear blue. (Students do not necessarily wear only one colour.) Furthermore, 7 wear red and white, 12 wear blue and white…

Let T be a relation from A = {0, 1, 2, 3} to B = {0, 1, 2, 3, 4} such that (a, b) T iff b2 – a2 is an odd number. (A, B  U = Z.) (Hint: Write down all the elements of T. For example, if 4  B and 1  A then 42 – 12 = 16 – 1 = 15 whi…

Consider the following relation on set B = {a, b, {a}, {b}, {a, b}}: P = {(a, b), (b, {a, b}), ({a, b}, a), ({b}, a), (a, {a})}. Which one of the following alternatives represents the range of P (ran(P))? 1. {a, b, {a}, {a, b}} 2. …

Which one of the following relations represents the composition relation P ○ P (ie P; P)? 1. {(a, {a, b}), (b, a), ({a, b}, a), ({b}, {a}), (a, {a})} 2. {(a, {a, b}), (b, a), ({a, b}, a), ({b}, {a})} 3. {(a, {a, b}), (b, a), ({a, b}, …

The relation P does not satisfy trichotomy. Which ordered pairs should be included in P so that an extended relation P1 (say) would satisfy trichotomy? (For trichotomy, each element of B must be paired with each other different elemen…

Consider the following relation on set B = {a, b, {a}, {b}, {a, b}}: P = {(a, b), (b, {a, b}), ({a, b}, a), ({b}, a), (a, {a})}. Which one of the following sets is a partition S of B = {a, b, {a}, {b}, {a, b}}? 1. {{a, b, {a}, {b}}, …

Suppose U = {1, 2, 3, a, b, c} is a universal set with the subset A = {a, c, 2, 3}. Let R = { (a, a), (a, c), (3, c), (3, a), (2, 3), (2, a), (2, c), (c, 2) } be a relation on A. Answer questions 11 & 12 by using the given sets A, U a…

A class of 40 students were each to required three text book of Physics, Mathematics and chemistry however 20 students had physics books, 24 had Mathematics books and 22 had chemistry books. 10 students had Physics and mathematics boo…

Use the factor tree to determine the prime factors of 135

Consider the following relation on set B = {a, b, {a}, {b}, {a, b}}: P = {(a, b), (b, {a, b}), ({a, b}, a), ({b}, a), (a, {a})}. Which one of the following alternatives represents the range of P (ran(P))? 1. {a, b, {a}, {a, b}} 2.…

Using a Truth table, determine the value of the compound proposition (𝑝 ∨ 𝑞) ∧ (￢𝑝 ∨ 𝑟)) → (𝑞 ∨ 𝑟)

What is partial ordering?

Solve the recurrence relation of an+4 + 2an+2 + an=0, n greater than or equal to zero .

Determine if 1781 is divisible by 3, 6, 7, 8, and 9

Using letters L, W, C for the component statements, translate the following compound statements into symbolic notation. L(x): x is a lawyer W(x): x is a woman C(x): x is a chemist i)There are some women lawyers who are chemists. …

Let p, q and r be the propositions. p: You are a student of Govt. College of science. q: You get first position in the college. r: You get first position in University of the Punjab. i) You are a student of Govt. College of science,…

Define a binary relation P from R to R as follows: for all real numbers x and y, (𝑥, 𝑦) ∈ 𝑃 ⇔ 𝑥 = 𝑦 2 . Is P a function? Explain.

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}. Find a) A ∩ B ∩ C. b) A ∪ B ∪ C. c) (A ∪ B) ∩ C. d) (A ∩ B) ∪ C.

Draw a binary search tree by inserting the values 50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 2, 3 and 70.

I. Write what is asked on the following item. Write your answer before the item. 1. Set of points in a graph 2. Set of lines in a graph. 3. A node with no children. 4. Children with the same parent. 5. Tree with n vertices cons…

Discuss Karnaugh map with one, two, three and four variables

Use Dijkstra’s algorithm to find the shortest path spanning tree for the following weighted directed graph with vertices A, B, C, D, and E given. Consider the starting vertex as E.

1. Assess whether the following undirected graphs have an Eulerian and/or a Hamiltonian cycle.

1. Simplify the following Boolean expressions using algebraic methods. 1. A(A+B)+B(B+C)+C(C+A) 2. (A+B ̅)(B+C)+(A+B)(C+A ̅) 3. (A+B)(AC+AC ̅)+AB+B 4. A ̅(A+B)+(B+A)(A+B ̅)

1. Consider the K-Maps given below. For each K- Map i. Write the appropriate standard form (SOP/POS) of Boolean expression. ii. Design the circuit using AND, NOT and OR gates. iii. Design the circuit only by using • NAND gates i…

We have 5 distinct jobs to be finished in the first 22 days of June but no two of the jobs will be finished on consecutive days. In how many ways can we plan the finishing days for these 5 distinct jobs? Write your answer: the number …

Define a binary relation P from R to R as follows: for all real numbers x and y, (x,y)∈P⇔x=y^2. Is P a function? Explain.

given that the function f(x) = 4x + 1 , find a formula for f-1(x)

Q1: 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 day. c) a has the sam…

Q2: Let R be the parent relation on the set of all people (see Example 21 in section 9.1 of the book). When is an ordered pair in the relation R^3? SUGGESTED TEXT: · Keneth H. Rosen. Discrete Mathematics and its Applications…

Q3: List the 16 different relations on the set {0,1}. Note: No partial credit would be admissible in this question.

(i) Use Karnaugh map to minimize the following SOP expression and also implement the simplified expression. Y = A’BC + A’B’C’ + ABC’ + AB’C’

A class contains 10 students with 6 boys and 4 girls. Find the number of ways: i. A 4 member committee can be selected from the students. ii. A 4 member committee with 2 boys and 2 girls can be selected from the students. iii. A 4 mem…

draw a binary search tree by inserting the values 50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 2, 3 and 70.

There were 100 students in the library who responded to how they completed their research paper. • 18 students only used the periodicals. • 29 students used the web and books. • 15 students used books, the web, and periodicals. • 40 s…

There are 70 women in class. Each play at least one game of the following games; volleyball, basketball, table tennis. 20 play volleyball only,10 play basketball only and 6 play table tennis. 4 play all the games and an equal number…

Give an example of a function which represents all types of a function. Find the composite function (f o g) (x) given that f = {(1,6), (4,7), (5,0)} and g = {(6,1), (7,4), (0,5)}

There were 100 students in the library who responded to how they completed their research papers. • 18 students only used the periodicals. • 29 students used the web and books. • 15 students used books, the web, and periodicals. •…

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

a) thesetofpeoplewhospeakEnglish,thesetofpeople who speak English with an Australian accent

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-1435-qpid-1173