Share
Explore BrainMass

Discrete Structures

Big O notation

I) Show that x^3 is O(x^4) but x^4 is not O(x^3) ii)Show that xlnx is O(x^2) but x^2 is not O(xlnx) iii)Show that a^x O(b^x) but b^x is not O(a^x) if 0 < a < b (0 = zero) iv)Show that 1^k + 2^k+...+n^k is O(n^(k+1)) for every positive integer k

Formula - Several Problems

(See attached file for full problem description with proper symbols) --- 2. Let f(x) = x2 +1 and g(x) = {x+1, x> =3; x-1, x<3 so both f and g map R into Find the formula for a. (f+g)(x) b. (f .g)(x) c. (f o g)(x) d. (g o f)(x) 3. Let A = {a,b,c,d} and B = {1,2,3} and let f : A &#61664; B be a function . Let g : Z

Discrete structures located

We worked on the attached problems today in class I am now trying to work through them again for understanding and I am not getting very far. My skills in discrete mathematics are not such that I can work through these on my own effectively. 3. Seven points are located in a plane. List the possible numbers of lines determi

Discrete Structures : Sequences, Subsequences and Remainders

1. How do I prove that in a group of n people there are two people with the same number of acquaintances within the group? 2. Prove that given a sequence of twelve integers, a1, a2, ...,a12, there is a subsequence aj, aj+1, ..., ak where 12 divides &#8721;kn= aa n. 3. A scrape of paper is found in an old desk that read:

Frequency

When a pair of dice is rolled, the total will range from 2 (1,1) to 12 (6,6). It is a fact that some numbers will occur more frequently than others as the dice are rolled over and over. Why will some numbers come up more frequently than others? Each die has six sides numbered from 1 to 6. How many possible ways can a numb

Suppose that only 25% of all drivers...

48. Suppose that only 25% of all drivers come to a complete stop at an intersection having flashing red lights in all directions when no other cars are visible... (see attachment for complete question)

Handshakes

On the first day of math class, 20 people are present in the room. To become acquainted with one another, each person shakes hands just once with everyone else. How many handshakes take place?

Multinomial experiment, Expected Frequency

1. True or False. In a multinomial experiment, all outcomes of each trial can have several categories. 2. In finding Expected Frequency you multiply what divided by what?

Discrete Structures : Congruences

Construct addition and multiplication tables for arithmetic modulo 11. For example, 7 + 8 mod 11 is 4 and 7*8 mod 11 is 1 so the entry in row 7, column 8 would be 4 for the addition table and 1 for the multiplication table. Use your tables to solve each of the following congruences: a. 3x+2&#8801;8 (mod11) b. 3x-5&#8801;2 (m

Subgraphs

Let G be a complete graph on n vertices. Please calculate how many spanning and induced subgroups G has... (see attachment)

Big-Oh: Context Free Grammars

Following is a big-oh relationship. Give witnesses n0 and c that can be used to prove the relationship. Choose your witnesses to be minimal, in the sense that n0 - 1 and c are not witnesses, and if d < c, then n0 and d are not witnesses. n¹º is O(3ⁿ)

Tree Traversal.

Find the: 1. preorder transversal 2. inorder transversal 3. postorder transversal Of the tree attached in the Word document.

Recursive relationship problem

Consider the recursive relationship for combinations: C(n,r) = C(n-1,r) + C(n-1,r-1) Prove this relationship algebraically using the mathematical definition of a combination, as well as that of the factorial function. Provide a logical explanation for this relationship (Hint: consider n objects as consisting of n-1 ex

Relations for Symmetric Transitive Closures

S = {0, 1, 2, 4, 6} Test the binary relations on S for reflexivity, symmetry ,antisymmetry, and transitivity. Also find the reflexive, symmetric and transitive closure of each relations. A) P = {(0,0), (1,1), (2,2), (4,4), (6,6), (0,1), (1,2), (2,4), (4,6) } B) P {(0,1), (1,0), (2,4), (4,2), (4,6), (6,4)} C) P ((0

Discrete structures

.Derive the statement as corollaries of other theorems from the text or of statement you have proved true in the exercise. Prove that if one solution to a quadratic equation of the form x^2+bx+c=0 is rational (where b and c are rational), then the other solutions is also rational. (Use the fact that if the solutions of the e

Equivalence Relations and Classes

Let L be a subset of {a,b}* Define a relation R (R sub L) on S* as follows: L for All of x, y is a member of S*, (x,y) are members of R if for all of z, xz are members of L iff yz are members of L A) Show that R is an equivalence relation B) Suppose L={a^i b^i where i >= 0} What can you say about the inde

Discrete Structures

11) Use generating functions to determine the number of different ways 12 identical action figures can be given to five children so that each child receives at most three action figures. 12) Use generating functions to find the number of ways to select 10 balls from an urn containing red, white and blue balls if: a. The

Discrete structures

6. A string that contains only 0s 1s and 2s is called a ternary string a) find a recurrence relation for the number of ternary strings that contain two consecutive 0s b) what are the initial conditions c) how many ternary strings of length six contain two consecutive 0s The next 3 problems deal with a variation of the

Calculating the standard deviation from a frequency table.

Find the standard deviation of the data in the given frequency table. A company had 80 employees whose salaries are summarized in the frequency table below. Find the standard deviation. Salary / Employees 5001-10000 / 17 10001-15000 / 16 15001-20000 / 20 20001-25000 /15 25001-30000 /12

Standard deviation calculation by frequency table

Find the standard deviation of the data in the given frequency table. A company had 80 employees whose salaries are summarized in the frequency table below. Find the standard deviation. Salary Employees 5001-10000 17 10001-15000 16 15001-20000 20 20001-25000 15 25001-30000 12