Discrete Mathematics Answers

State TRUE or FALSE justifying your answer with proper reason.

a. 2𝑛^2 + 1 = 𝑂(𝑛^2 )

b. 𝑛^2 (1 + √𝑛) = 𝑂(𝑛^2 )

c. 𝑛^2 (1 + √𝑛) = 𝑂(𝑛^2 log 𝑛)

d. 3𝑛^2 + √𝑛 = 𝑂(𝑛 + 𝑛√𝑛 + √𝑛)

e. √𝑛 log 𝑛 = 𝑂(𝑛)

Assume that the function y(x) = f (x) + g(x) has a single local minimum in the

interval 0 <= x <= 1, at x = xm. Write

(i) a function M-file (called funct.m) and

(ii) a MATLAB statement (using the fminbnd command)

that together will compute xm and the value of y at xm.

Suppose you want to encode messages containing only the following characters with their given respective frequencies: B: 55 D: 15 E: 80 G: 5 U: 45

(a) What is the minimum length bit string required to encode each character with a distinct, fixed-length code?

(b) Construct the Huffman Tree for the characters with the given frequencies. (Use the convention that when merging two vertices, the vertex with the largest count goes on the left.)

(c) Use your Huffman Tree to decode the message M = 00101010000011

(d) How many bits are required to encode the characters with the given frequencies using the Huffman Encoding and the fixed-length encoding you found in part (a)? How much storage savings does this represent?

Use rules of inference to show that the hypothesis "All lions are fierce","Some Lions do not drink coffee" imply the conclusion "Some fierce creatures do not drink coffee".

prove a --> ( b V c ) using contradiction method and combination of inference rules and equivalence laws from these premises : 1. a --> ( d V b ) 2. d --> c

Construct the call graph for a set of seven telephone numbers 555-0011, 555-1221,

555-1333, 555-8888, 555-2222, 555-0091, and 555-1200 if there were three calls from 555-0011 to

555-8888 and two calls from 555-8888 to 555-0011, two calls from 555-2222 to 555-0091, two calls

from 555-1221 to each of the other numbers, and one call from 555-1333 to each of 555-0011, 555-

1221, and 555-1200.

What is the image (range) of the function that assigns the square of an integer to this integer

For all integers a, b and c, if 𝑎|𝑏 and 𝑏|𝑐, then prove that 𝑎𝑏 2 |𝑐 3 .

is 6x+1 < (2x+4) + (4x-2) proposition?

Construct a relation on the set {a, b, c, d} that is

a. reflexive, symmetric, but not transitive.

b. irreflexive, symmetric, and transitive.

c. irreflexive, antisymmetric, and not transitive.

d. reflexive, neither symmetric nor antisymmetric, and transitive.