# Recent questions tagged discrete-mathematics

1 vote
1
The number of positive integers not exceeding $100$ that are either odd or the square of an integer is _______ $63$ $59$ $55$ $50$
2
How many ways are there to pack six copies of the same book into four identical boxes, where a box can contain as many as six books? $4$ $6$ $7$ $9$
3
Which of the following pairs of propositions are not logically equivalent? $((p \rightarrow r) \wedge (q \rightarrow r))$ and $((p \vee q) \rightarrow r)$ $p \leftrightarrow q$ and $(\neg p \leftrightarrow \neg q)$ $((p \wedge q) \vee (\neg p \wedge \neg q))$ and $p \leftrightarrow q$ $((p \wedge q) \rightarrow r)$ and $((p \rightarrow r) \wedge (q \rightarrow r))$
4
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ if and only if either $j=i+1$ or $j=3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is ______ $23$ $99$ $4$ $7$
5
If $f(x)=x$ is my friend, and $p(x) =x$ is perfect, then correct logical translation of the statement “some of my friends are not perfect” is ______ $\forall _x (f(x) \wedge \neg p(x))$ $\exists _x (f(x) \wedge \neg p(x))$ $\neg (f(x) \wedge \neg p(x))$ $\exists _x (\neg f(x) \wedge \neg p(x))$
6
What kind of clauses are available in conjunctive normal form? Disjunction of literals Disjunction of variables Conjunction of literals Conjunction of variables
7
Consider the following properties: Reflexive Antisymmetric Symmetric Let $A=\{a,b,c,d,e,f,g\}$ and $R=\{(a,a), (b,b), (c,d), (c,g), (d,g), (e,e), (f,f), (g,g)\}$ be a relation on $A$. Which of the following property (properties) is (are) satisfied by the relation $R$? Only $a$ Only $c$ Both $a$ and $b$ $b$ and not $a$
8
Consider the following argument with premise $\forall _x (P(x) \vee Q(x))$ and conclusion $(\forall _x P(x)) \wedge (\forall _x Q(x))$ ... valid argument Steps $(C)$ and $(E)$ are not correct inferences Steps $(D)$ and $(F)$ are not correct inferences Step $(G)$ is not a correct inference
9
Consider the following statements: Any tree is $2$-colorable A graph $G$ has no cycles of even length if it is bipartite A graph $G$ is $2$-colorable if is bipartite A graph $G$ can be colored with $d+1$ colors if $d$ is the maximum degree of any vertex in the graph $G$ ... and $(e)$ are incorrect $(b)$ and $(c)$ are incorrect $(b)$ and $(e)$ are incorrect $(a)$ and $(d)$ are incorrect
10
Consider the statement below. A person who is radical $(R)$ is electable $(E)$ if he/she is conservative $(C)$, but otherwise not electable. Few probable logical assertions of the above sentence are given below. $(R \wedge E) \Leftrightarrow C$ $R \rightarrow (E \leftrightarrow C)$ ... answer from the options given below: $(B)$ only $(C)$ only $(A)$ and $(C)$ only $(B)$ and $(D)$ only
11
Let $G$ be a simple undirected graph, $T_D$ be a DFS tree on $G$, and $T_B$ be the BFS tree on $G$. Consider the following statements. Statement $I$: No edge of $G$ is a cross with respect to $T_D$ Statement $II$: For every edge $(u,v)$ of $G$ ... Statement $I$ and Statement $II$ are false Statement $I$ is correct but Statement $II$ is false Statement $I$ is incorrect but Statement $II$ is true
12
Solve the recurrence relation for the number of rounds in the tournament described in question $14.$
13
How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?
14
Suppose that there are $n = 2^{k}$ teams in an elimination tournament, where there are $\frac{n}{2}$ games in the first round, with the $\frac{n}{2} = 2^{k-1}$ winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.
15
Give a big-O estimate for the function $f$ given below if $f$ is an increasing function. $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
1 vote
16
Find $f (n)$ when $n = 3k,$ where $f$ satisfies the recurrence relation $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
17
Give a big-O estimate for the function $f$ in question $10$ if $f$ is an increasing function.
18
Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$
19
Suppose that $f (n) = f (n/5) + 3n^{2}$ when $n$ is a positive integer divisible by $5, \:\text{and}\: f (1) = 4.$ Find $f (5)$ $f (125)$ $f (3125)$
20
Suppose that $f (n) = 2f (n/2) + 3$ when $n$ is an even positive integer, and $f (1) = 5.$ Find $f (2)$ $f (8)$ $f (64)$ $(1024)$
21
Suppose that $f (n) = f (n/3) + 1$ when $n$ is a positive integer divisible by $3,$ and $f (1) = 1.$ Find $f (3)$ $f (27)$ $f (729)$
22
How many operations are needed to multiply two $32 \times 32$ matrices using the algorithm referred to in Example $5?$
23
Determine a value for the constant C in Example $4$ and use it to estimate the number of bit operations needed to multiply two $64$-bit integers using the fast multiplication algorithm.
24
Express the fast multiplication algorithm in pseudocode.
25
Multiply $(1110)_{2} \:\text{and}\: (1010)_{2}$ using the fast multiplication algorithm.
26
How many comparisons are needed to locate the maximum and minimum elements in a sequence with $128$ elements using the algorithm in Example $2$?
How many comparisons are needed for a binary search in a set of $64$ elements?
Prove Theorem $6:$Suppose that $\{a_{n}\}$ satisfies the liner nonhomogeneous recurrence relation $a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k} + F(n),$ where $c_{1}.c_{2},\dots,c_{k}$ ... is $m,$ there is a particular solution of the form $n^{m}(p_{t}n^{t} + p_{t-1}n^{t-1} + \dots + p_{1}n + p_{0})s^{n}.$
Prove Theorem $4:$ Let $c_{1},c_{2},\dots,c_{k}$ be real numbers. Suppose that the characteristic equation $r^{k}-c_{1}r^{k-1}-\dots c_{k} = 0$ has $t$ distinct roots $r_{1},r_{2},\dots,r_{t}$ with multiplicities $m_{1},m_{2},\dots,m_{t},$ ... $\alpha_{i,j}$ are constants for $1 \leq i \leq t\:\text{and}\: 0 \leq j \leq m_{i} - 1.$