Question
1. Consider the code below to test H = W,where H and W are binary arrays of length n. for (int i = 0; i
1. Consider the code below to test H = W,where H and W are binary arrays of length n. for (int i = 0; i < n; i++) if (H[i] != W[i]) return(false); return(true); Complete the following sentences and give a justications for your answer:
(a) #((H, W)-pairs that give false-return value in mth iteration, 1 m n)=.................
(b) #((H, W)-pairs giving false-return) = ................... (c) #((H, W)-pairs giving true-return) = ................... (d) For n = 4, the average #(iterations for all (H, W)-pairs) = ......... (e) For n = 5, the average #(iterations for all (H, W)-pairs) = ......... (f) For n = 6, the average #(iterations for all (H, W)-pairs) = .........
(g) For general n 1, the average #(iterations for all (H, W)-pairs) = .........
2. Give an alternate if-condition for the code in Problem 1 that would also correctly test H = W.
3. Express the set theoretic relationship between H and W,when we think of Hand W representing subsets of an n-set, that is tested by the following code.
for (int i = 0; i < n; i++) if (H[i] != W[i]) return(false); else return(true);
4. Complete the following sentences.
(a) For a given H of size m,0 m n,# (W disjoint from H)=........
(b) #((H, W)-pairs such that HW = and |H|=m)=.......
(c) #((H, W)-pairs such that HW = )=.......
(d) A matching of (H, W)-pairs with HW = and (H, W)-pairs with HW can be obtained as follows .................................................. For example, the pair ({a, b}, {c}) of 1st kind can be matched with the pair ........................ of 2nd kind. (e) How many(H, W)-pairs would give true return-value for the code in Problem 3?
5. What is wrong in the following way of counting (H, W)pairs with HW non-empty? (Here, H and W are subsets of an nset.)
(a) For a given m-subset X,1 m n,#((H, W)-pairs with HW = X)=3^nm.
(b) #((H, W)-pairs with |HW|=m)=C(n, m)3^nm. (c) #((H, W)-pairs with |HW| 1) = n m=1 C(n, m)3^nm =4^n 3^n.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started