In a class of 120 students numbered 1 to 120, all even numbered students opt for Physics, whose numbers are divisible by 5 opt for Chemistry and those whose numbers are divisible by 7 opt for Math. How many opt for none of the three subjects?
We need to find out the number of students who took at least one of the three subjects and subtract that number from the overall 120 to get the number of students who did not opt for any of the three subjects. Number of students who took at least one of the three subjects can be found by finding out P U C U M, where P is the set of those who took Physics, C the set of those who took Chemistry and M the set of those who opted for Math. Now, P U C U M = P + C + M - (P n C + C n M + M n P) + (P n C n M) P is the set of those who opted for Physics = 120/2 = 60 students C is the set of those who opted for Chemistry = 120/5 = 24 M is the set of those who opted for Math = 120/7 = 17. The 10th, 20th, 30th..... numbered students would have opted for both Physics and Chemistry. Therefore, P n C = 120/10 = 12 The 14th, 28th, 42nd..... Numbered students would have opted for Physics and Math. Therefore, M n P = 120/14 = 8 The 35th, 70th.... numbered students would have opted for Chemistry and Math. Therefore, C n M = 120/35 = 3 And the 70th numbered student would have opted for all three subjects. Therefore, P U C U M = 60 + 24 + 17 - (12 + 8 + 3) + 1 = 79. Number of students who opted for none of the three subjects = 120 - 79 = 41.
Consider the quick-union algorithm for disjoint sets. We know that a sequence of n operations (unions and finds) can take asymptotically slightly more than linear time in the worst case. Explain why if all the unions are done before all the finds, a sequence of n operations is guaranteed to take O(n) time.
This question requires amortized analysis. Find operations can be expensive, but an expensive find operation is balanced out by lots of cheap union operations. The accounting is as follows: Union operations always take O(1) time, so let's say they have an actual cost of $1. Assign each union operation an amortized cost of $2, so every union operation puts $1 in the bank. Each union operation creates a new child. (Some node that was not a child of any other node before is a child now.) When all the union operations are done, there is $1 in the bank for every child, or in other words, for every node with a depth of one or greater. Let's say that a find(u) operation costs $1 if u is a root. For any other node, the find operation costs an additional $1 for each parent pointer the find operation traverses. So the actual cost is $(1 + d), where d is the depth of u. Assign each find operation an amortized cost of $2. This covers the case where u is a root or a child of a root. For each additional parent pointer traversed, $1 is withdrawn from the bank to pay for it. Fortunately, path compression changes the parent pointers of all the nodes we pay $1 to traverse, so these nodes become children of the root. All of the traversed nodes whose depths are 2 or greater move up, so their depths are now 1. We will never have to pay to traverse these nodes again. Say that a node is a grandchild if its depth is 2 or greater. Every time find(u) visits a grandchild, $1 is withdrawn from the bank, but the grandchild is no longer a grandchild. So the maximum number of dollars that can ever be withdrawn from the bank is the number of grandchildren. But we initially put $1 in the bank for every child, and every grandchild is a child, so the bank balance will never drop below zero. Therefore, the amortization works out. Union and find operations both have amortized costs of $2, so any sequence of n operations where all the unions are done first takes O(n) time.
A rope rests on two platforms which are both inclined at an angle θ. The rope has uniform mass density, and its coefficient of friction with the platforms is 1. The system has left-right symmetry. What is the largest possible fraction of the rope that does not touch the platforms? What angle θ allows this maximum value?
Let the total mass of the rope be m, and let a fraction f of it hang in the air. Consider the right half of this section. Its weight, (f /2)mg, must be balanced by the vertical component, T sin θ, of the tension at the point where it joins the part of the rope touching the right platform. The tension at this point therefore equals T = (f /2)mg/ sin θ. Now consider the part of the rope touching the right platform. This part has mass (1 − f)m/2. The normal force from the platform is N = (1 − f)(mg/2) cos θ, so the maximal friction force equals (1 − f)(mg/2) cos θ, because µ = 1. This fiction force must balance the sum of the gravitational force component along the plane, which is (1 − f)(mg/2) sin θ, plus the tension at the lower end, which is the (f /2)mg/ sin θ we found above. Therefore, 1/2(1 − f)mg cos θ = 1/2(1 − f)mg sin θ + (f mg)/2sin θ (1) which gives f = F(θ)/[1 + F(θ)] where F(θ) ≡ cos θ sin θ − sin^2θ (2) This expression for f is a monotonically increasing function of F(θ), as we can check. The maximal f is therefore obtained when F(θ) is as large as possible. Using the double-angle formulas, we can rewrite F(θ) as F(θ) = 1/2 (sin 2θ + cos 2θ − 1) (3) The derivative of this is cos 2θ−sin 2θ, which equals zero when tan 2θ = 1. Therefore, θmax = 22.5◦ (4) Eq. (3) then yields F(θmax) = (√2 − 1)/2, and so eq. (2) gives fmax = (√2 − 1)/(√2 + 1) = (√2 − 1)^2 = 3 − 2√2 ≈ 0.172