How to compute algorithm complexity? Analysis the complexity of Binary Search Algorithm for the following input and search item 13. [5, 8, 11, 13, 29, 35, 36, 38]

"A patient goes to see a doctor. The doctor performs a test with 99 percent reliability--that is, 99 percent of people who are sick test positive and 99 percent of the healthy people test negative. The doctor knows that only 1 percent of the people in the country are sick. Now the question is: if the patient tests positive, what are the chances the patient is sick?"

How to compute algorithm complexity? Analysis the complexity of Binary Search Algorithm for the following input and search item 13. [5, 8, 11, 13, 29, 35, 36, 38]

 Define set with example. What is the power set of {a, b, c, 2} and Cartesian products of {1, 2, 3} and {x, y, z).

Suppose that there are eight runners in a race. The winner receives a gold medal, the second place finisher receives a silver medal, and the third-place finisher receives a bronze medal. How many different ways are there to award to these medals, if all possible outcomes of the race can occur and there no ties?

Suppose that there are eight runners in a race. The winner receives a gold medal, the second-place finisher receives a silver medal, and the third-place finisher receives a bronze medal. How many different ways are there to award to these medals, if all possible outcomes of the race can occur and there no ties?

In how many ways can we select three students from a group of five students to stand in line for a picture? In how many ways can we arrange all five of these students in a line for a picture?

A bag contains 10 red marbles, 10 white marbles, and 10 blue marbles. What is the minimum no. of marbles you have to choose randomly from the bag to ensure that we get 4 marbles of same color?

"A patient goes to see a doctor. The doctor performs a test with 99 percent reliability--that is, 99 percent of people who are sick test positive and 99 percent of the healthy people test negative. The doctor knows that only 1 percent of the people in the country are sick. Now the question is: if the patient tests positive, what are the chances the patient is sick?"

Define Handshaking Theorem/Lemma. Find the in-degree and out-degree of each vertex in the following graph with directed edges.

"A patient goes to see a doctor. The doctor performs a test with 99 percent reliability--that is, 99 percent of people who are sick test positive and 99 percent of the healthy people test negative. The doctor knows that only 1 percent of the people in the country are sick. Now the question is: if the patient tests positive, what are the chances the patient is sick?"

What is the probability that a positive integer selected at random from the set of positive integers not exceeding 100 is divisible by either 2 or 5?

Explain Eulerian and Hamiltonian graphs with examples, also draw the graphs of the following:

i) Eulerian but not Hamiltonian

ii) Hamiltonian but not Eulerian

What is planner graph? Draw the planner graph of the given graph.

Suppose that there are eight runners in a race. The winner receives a gold medal, the second place finisher receives a silver medal, and the third-place finisher receives a bronze medal. How many different ways are there to award to these medals, if all possible outcomes of the race can occur and there no ties?

Suppose that there are eight runners in a race. The winner receives a gold medal, the second-place finisher receives a silver medal, and the third-place finisher receives a bronze medal. How many different ways are there to award to these medals, if all possible outcomes of the race can occur and there no ties?

In how many ways can we select three students from a group of five students to stand in line for a picture? In how many ways can we arrange all five of these students in a line for a picture?

Define quantifier. Translate: For every person x, if x is a student in the class, then x has visited Dhaka and x has not visited USA.

Explain the difference between a relation and a function. Let f: ℝ -> ℝ be defined by f(x) = 2x + 3. Show that f is one-to-one (injective).

Explain Eulerian and Hamiltonian graphs with examples, also draw the graphs of the following:

i) Eulerian but not Hamiltonian

ii) Hamiltonian but not Eulerian

Define Handshaking Theorem/Lemma. Find the in-degree and out-degree of each vertex in the following graph with directed edges.

What is planner graph? Draw the planner graph of the given graph.

Explain Eulerian and Hamiltonian graphs with examples, also draw the graphs of the following:

i) Eulerian but not Hamiltonian

ii) Hamiltonian but not Eulerian

Define Handshaking Theorem/Lemma. Find the in-degree and out-degree of each vertex in the following graph with directed edges.

What is the probability that a positive integer selected at random from the set of positive integers not exceeding 100 is divisible by either 2 or 5?

Explain the difference between a relation and a function. Let f: ℝ -> ℝ be defined by f(x) = 2x + 3. Show that f is one-to-one (injective).

Represent with Venn diagram the relationship i) AUB = {x|x∈A V x∈B} ii) A∩B= {x|x∈A Ʌ x∈B)

Explain proof technique. Proof the following statement with contradiction and contrapositive technique. "The sum of any two consecutive numbers is odd"

Verify that validating of the following inference. If one person is more successful than another, then he has worked harder to deserve success. X has not worked harder than Y. Therefore, X is not more successful than Y.

Suppose that there are eight runners in a race. The winner receives a gold medal, the second place finisher receives a silver medal, and the third-place finisher receives a bronze medal. How many different ways are there to award to these medals, if all possible outcomes of the race can occur and there no ties?

Suppose that there are eight runners in a race. The winner receives a gold medal, the second-place finisher receives a silver medal, and the third-place finisher receives a bronze medal. How many different ways are there to award to these medals, if all possible outcomes of the race can occur and there no ties?

In how many ways can we select three students from a group of five students to stand in line for a picture? In how many ways can we arrange all five of these students in a line for a picture?

 Prove that, if k + 1 or more pigeons are distributed among k pigeonholes, then at least one pigeonhole contains two or more pigeons.

A bag contains 10 red marbles, 10 white marbles, and 10 blue marbles. What is the minimum no. of marbles you have to choose randomly from the bag to ensure that we get 4 marbles of same color?

 Define set with example. What is the power set of {a, b, c, 2} and Cartesian products of {1, 2, 3} and {x, y, z).

Define quantifier. Translate: For every person x, if x is a student in the class, then x has visited Dhaka and x has not visited USA.

Show that ∀x (P(x)^Q(x)) and ∀x P(x)^∀x Q(x) are logically equivalent.

Explain proof technique. Proof the following statement with contradiction and contrapositive technique. "The sum of any two consecutive numbers is odd"

Explain proof technique. Proof the following statement with contradiction and contrapositive technique. "The sum of any two consecutive numbers is odd"

Suppose that Smartphone A has 256 MB RAM and 32 GB ROM, and the resolution of its camera is 8 MP; Smartphone B has 288 MB RAM and 64 GB ROM, and the resolution of its camera is 4 MP; and Smartphone C has 128 MB RAM and 32 GB ROM, and the resolution of its camera is 5 MP.
Determine the truth value of each of these propositions.

i) Smartphone B has the most RAM of these three smartphones.
ii) Smartphone C has more ROM or a higher resolution camera than Smartphone B.
iii) Smartphone B has more RAM, more ROM, and a higher resolution camera than Smartphone A.
iv) If Smartphone B has more RAM and more ROM than Smartphone C, then it also has a higher resolution camera.

Define proposition with example. Consider the following sentences and determine which of the following is a proposition or not. (i) Dhaka is the capital of Bangladesh. (ii) 2+3=5 (iii) x+2=11 x+y=y+x, for every pair of real numbers x and y.

Verify that validating of the following inference. If one person is more successful than another, then he has worked harder to deserve success. X has not worked harder than Y. Therefore, X is not more successful than Y.

Define logically Equivalences of compound proposition. Show that this implication is a tautology by using truth table. [(p → q) ∩ (q → r)] → (p → r)

Define quantifier. Translate: For every person x, if x is a student in the class, then x has visited Dhaka and x has not visited USA.

Show that ∀x (P(x)^Q(x)) and ∀x P(x)^∀x Q(x) are logically equivalent.

Analysis the complexity of Quick Sort Algorithm for the following input. 

 Define set with example. What is the power set of {a, b, c, 2} and Cartesian products of {1, 2, 3} and {x, y, z).

How to compute algorithm complexity? Analysis the complexity of Binary Search Algorithm for the following input and search item 13. [5, 8, 11, 13, 29, 35, 36, 38]

Analysis the complexity of Quick Sort Algorithm for the following input. 

Define logically Equivalences of compound proposition. Show that this implication is a tautology by using truth table. [(p → q) ∩ (q → r)] → (p → r)

How to compute algorithm complexity? Analysis the complexity of Binary Search Algorithm for the following input and search item 13. [5, 8, 11, 13, 29, 35, 36, 38]

What do you know about algorithm complexity? Analyze the time complexity of the following algorithm:

Analysis the complexity of Quick Sort Algorithm for the following input. 

Define logically Equivalences of compound proposition. Show that this implication is a tautology by using truth table. [(p → q) ∩ (q → r)] → (p → r)

Represent with Venn diagram the relationship i) AUB = {x|x∈A V x∈B} ii) A∩B= {x|x∈A Ʌ x∈B)

Show that ∀x (P(x)^Q(x)) and ∀x P(x)^∀x Q(x) are logically equivalent.

Represent with Venn diagram the relationship i) AUB = {x|x∈A V x∈B} ii) A∩B= {x|x∈A Ʌ x∈B)

Let P(x) be the statement "x=x²". If the domain consists of integers, what are these truth values?
i) P(0)   ii) ƎxP(x)     iii) ∀xP(x)

 Use set builder notation to give a description of each of these sets:
     i) {-3, -2, -1, 0, 1, 2, 3}      ii) {m, n, o, p}

 Let p(n) = a₀ + a_₁n + a₂ n² +.... + a_mn^m; that is, suppose degree p(n) = m, prove that p(n) = O (n^m).

 Show that if n is an integer greater than 1, then n can be written as a prime or product primes.

Suppose that A and B are events from a sample space S such that P(A) ≠ 0 and P(B)≠ 0. Then proof the following:

What is planner graph? Draw the planner graph of the given simple graph.

 Suppose the pre-order and in-order traversals of a binary tree T yield the following sequence of nodes: 
Pre-order: G, B, Q, A, C, K, F, P, D, E, R, H
In-order: Q, B, K, C, F, A, G, P, E, D, H, R

i) Draw the diagram of T         ii) Find the depth d of T
iii) Find the descendants of B   iv) List the terminal nodes of T

Define set with example. What is the power set of {x, y, z, 5} and Cartesian products of {x, y, z} and {a, b, c}.

Let p(n) = a₀ + a₁n + a₂ n² + ... + a_mn^m; that is, suppose degree p(n) = m, prove that p(n) = O (n^m).

Discuss generalized pigeonhole principle and proof this theorem using proof by contradiction.

Suppose that A and B are events from a sample space S such that P(A) ≠ 0 and P(B) ≠0. Then proof the following:

Define Isomorphic graph, Complete graph and Bipartite graph with example.

Illustrate how Kruskal's algorithm and Prim's algorithm are used to find a minimum spanning tree, using a weighted graph with at least eight vertices and 15 edges.

Show that if A, B and C are sets, then (A ∩B ∩C)'=A'∪ B'∪ C'.

Use rules of inference to show that the hypotheses "If it does not rain or if it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on," "If the sailing race is held, then the trophy will be awarded," and "The trophy was not awarded" imply the conclusion "It rained."

Discuss generalized pigeonhole principle and proof this theorem using proof by contradiction.

"A patient goes to see a doctor. The doctor performs a test with 99 percent reliability--that is, 99 percent of people who are sick test positive and 99 percent of the healthy people test negative. The doctor knows that only 1 percent of the people in the country are sick. Now the question is: if the patient tests positive, what are the chances the patient is sick?"

A computer company receives 350 applications from college graduates for a job planning a line of new web servers. Suppose that 220 of these applicants majored in CSE, 147 majored in Math, and 51 majored both in CSE and Math. How many of these applicants majored neither in CSE nor in Math.

Find all the spanning tree of graph G and find which is the minimal spanning tree of G shown in fig:

Suppose here, r> k and the degree of q(n) is r. Prove that q(n) = O(n^r).

A university offers the following courses: 38 courses in Mathematics and 42 courses in Computer Science. If a student can choose either a Mathematics course or a Computer Science course, how many choices does the student have in total? Explain your reasoning using the Sum Rule.

Consider the following undirected graph G: It has 6 vertices, with degrees 2, 3, 3, 2, 4, and 4, respectively. i) Determine whether the graph G has an Eulerian circuit. Justify your answer using the necessary and sufficient condition for Eulerian circuits. ii) If G does not have an Eulerian circuit, explain whether it has an Eulerian path, and if so, identify the starting and ending vertices.

Illustrate how Kruskal's algorithm and Prim's algorithm are used to find a minimum spanning tree, using a weighted graph with at least eight vertices and 15 edges.

Define propositional logic. Write down the difference between implication and biconditional with example.

Let fl and f2 be functions from R to R such that f1(x) = x2 and f2(x) = x - x2. What are the functions f1 + f2 and f1f2?

Show that A × A ≠ B × A, when A and B are nonempty, unless A = B. 

 Use mathematical induction to prove that 2ⁿ < n! for every integer n with n ≥ 4. (Note that this inequality is false for n = 1, 2, and 3.)

Each user on a computer system has a password, which is six to eight characters long, where each character is an uppercase letter or a digit. Each password must contain at least one digit. How many possible passwords are there?

Explain Eulerian and Hamiitonian graphs with examples, also draw the graphs of the following:

i) Eulerian but not Hamiltonian     ii) Hamiltonian but not Eulerian

Consider the following addresses which are in random order:
1, 2.2.1, 3.2, 2.2.1.1, 1.1.1, 0, 2.1, 3.2.1.1, 3, 3.1, 2.2, 2.1.1, 3.2.1, 1.1, 3.2.1.2, 2, 1.1.2

i) Place the addresses in lexicographic order   ii) Draw the corresponding ordered rooted tree

What is bi-implication? Develop truth table of (pΛq)v(⅂qΛr) and ⅂qv (⅂pΛq).

What do you mean by "((p→q)Λ⅂p)→⅂q is not a tautology"? For each of these arguments, explain with rules of inference are used for each step.

Show that ∀x (P(x)ΛQ(x)) and ∀x P(x)Λ ∀x Q(x) are logically equivalent.

Show that if n is an integer greater than 1, then n can be written as a prime or product primes.

Let E1 and E2 be events in the sample space S. Then proof the following: P(E1 U E2) = P(E1) + P(E2) - P(E1 ∩ E2)

How can the final exams at a university be scheduled (using graph coloring) so that no student has two exams at the same time?

Construct a truth table for the following compound propositions, (pVq) → (pɅq), where p and q represent arbitrary propositions. Determine whether this compound proposition is tautology, contradiction, or contingency. Justify your answer.

What is free variable? Let Q(x) denotes the statement "x=x+1". What is the truth value of the qualification ∃xQ(x), where domain consists of all real numbers?

Show that ∀x.(P(x)ΛQ(x)) and ∀xP(x) Λ ∀xQ(x) are logically equivalent.

Prove that, if n is an integer and 3n + 2 is odd, then n is odd?

Let E1 and E2 be events in the sample space S. Then proof the following: P(E1 U E2)=P(E1) + P(E2) - P(E1 ∩ E2)

Explain Eulerian and Hamiltonian graphs with examples, also draw the graphs of the following: i) Eulerian but not Hamiltonian ii) Hamiltonian but not Eulerian

Define Directed Graph. A drawing of the directed graph with vertices a, b, c, d, and e, and edges (a, a), (a, b), (b, c), (b, d), (a, d), (a, e), (e, d), (e, e), (e, a), (d, d), (c, e), (c, a) and (b, e).

How can this English sentence be translated into logical expression? "You can't ride the roller coaster if you're under 4 feet tall, unless you're over 16."

A library has two sections: i) Fiction Section: 8 books ii) Non-fiction Section: 10 books If a person wants to borrow one book from either section and one magazine (there are 6 magazines available), how many total choices does the person have?

Let G be a 4-regular connected planar graph having 16 edges. Find the number of regions of G.

Construct the truth table of the compound proposition: (p v ⅂q)  → (p Λ q)

Mention some methods of proving theorems. Prove that if m + n and n + p are even integers, where m, n, and p are integers, then m + p is even. What kind of proof did you use?

Analysis the complexity of the following binary search tree.

What do you mean by a complete graph? Draw a K₈ graph. What is the degree of a vertex of the K₈ graph you have drawn?

 Define graph coloring and chromatic number of a graph and find the chromatic number of
i) K_3,3
ii) cycle with even number of vertices

Find the in-degree and out-degree of each vertex in the following graph with directed edges.

How can this English sentence be translated into logical expression? "You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old."

Explain why (A × B) x (CxD) and A × (BxC) × D are not the same

How many bit strings of length 10 contain at least three 1s and at least three 0s?

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 with explanation. i) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} ii) {(2, 4), (4, 2)} iii) {(1, 1), (2, 2), (3, 3), (4, 4)}

Show that K_n has a Hamilton circuit whenever n ≥ 3.

In which order an in-order and post-order traversal visit the vertices of the given ordered rooted tree.

Translate each of these statements into logical expressions using predicates, quantifiers, and logical connectives. Let the domain consist of all people. (i) Someone in your class can speak Japanese. (ii) Everyone in your class is friendly. (iii) There is a person in your class who was not born in Jashore. (iv) No student in your class has taken a course in logic programming.

Let A = {0, 1, 2, 3} and define relations R, S and T on A as follows: R= {(0,0), (0,1), (0,3), (1,0), (1, 1), (2,2), (3,0), (3,3)}, S= {(0,0), (0,2), (0,3), (2,3)}, T= {(0, 1), (2, 3)}. i) Is R reflexive? Symmetric? Transitive? ii) Is S reflexive? Symmetric? Transitive?

Define Argument. Express the statements "Some student in this class has visited Mexico" and "Every student in this class has visited either Canada or Mexico" using predicates and quantifiers.