hellohomeworkassignment2.pdfHomework Assignment 2
Answer each of the questions below and submit your answers as a PDF document through
Canvas by the due date.
1. Suppose that you have the Boolean function f ( x , y )=¬(x∧ y)∨ y . Simplify this
expression.
2. Suppose that you had a set of 25 items. How many different subsets with exactly 7
items are there? How many different subsets with less than 3 items are there?
3. Suppose that you have 9 people in a line waiting for ice cream. In how many different
orders could the seven people be served?
4. Suppose that a bowl has six blue balls, five red balls, and four green balls.
a. What is the probability of selecting a green ball?
b. What is the probability of selecting a green or red ball?
c. What is the probability of selecting a green ball, then a red ball, assuming
that you do not put the balls back in the bowl?
5. Let S and T be outcomes. The probability P(S) is .3, the probability P(T) is .5, the
probability P(S∩T) is .35. How do you know that outcomes S and T are not
independent? What is the conditional probability P(S|T)? What is the conditional
probability P(T|S)?
6. Suppose that S and T are two mutually exclusive outcomes. What is P(S|T)? What is
P(T|S)? Give a numeric answer, not symobolic. How do you know this numeric result?
7. Suppose that S and T are independent outcomes and that P(S) = .4. What is P(S|T)
as a numeric result? How do you know this?
8. Prove that a complete binary tree of height h has 2h+1−1 nodes.
9. Prove that a complete binary tree with n nodes has height lg⌈n+ 1⌉−1 .
10. Prove that while f (n)=2 n2 +n+30∈O( g( n)) , where g(n)=n2 , f (n)∉ o( g(n)) . (Hint,
use the limit approach).
11. Another definition for little-o is that
1) f (n)∈o(g(n)) if ∀ c >0, ∃n0 such that f (n)≤cg(n), ∀ n>n0 .
The constant n0 may depend on the choice of c. In the definition of big-O, there only
need be at least one constant c for which the inequality holds. Show that n n∉o (n) ,
but that n∈O(n) . (In the first case, find a constant c for which 1) does not hold).
12. Consider the function f (n)=lg lg n=lg(lg ( n)) . Assume the each lg is log base 2. For
what value of n will lglg produce a value greater than 10? Where does this function
fall in the big-O ordering of functions presented in the textbook?
Purchase answer to see full
attachment
Why Choose Us
- 100% non-plagiarized Papers
- 24/7 /365 Service Available
- Affordable Prices
- Any Paper, Urgency, and Subject
- Will complete your papers in 6 hours
- On-time Delivery
- Money-back and Privacy guarantees
- Unlimited Amendments upon request
- Satisfaction guarantee
How it Works
- Click on the “Place Order” tab at the top menu or “Order Now” icon at the bottom and a new page will appear with an order form to be filled.
- Fill in your paper’s requirements in the "PAPER DETAILS" section.
- Fill in your paper’s academic level, deadline, and the required number of pages from the drop-down menus.
- Click “CREATE ACCOUNT & SIGN IN” to enter your registration details and get an account with us for record-keeping and then, click on “PROCEED TO CHECKOUT” at the bottom of the page.
- From there, the payment sections will show, follow the guided payment process and your order will be available for our writing team to work on it.