nonevent99 Posted November 6, 2003 Share Posted November 6, 2003 Q1) Express in prefix and postfix: 3-5*7/5+2*(3+4*6) Q2) Solve this recurrence: f(n f(n > 1) = f(n/2) + n^p for some p >= 0 Q3) Solve this recurrence: f(n f(n > 1) = f(n-c) + n^p for some p >= 0 Q4) Consider the expression f(x,y) = (x->y)+(y->x)*y Is f a tautology? Is it satisfiable? Q5) Let R be a binary relation defined such that xRy iff f(x,y) = true. Is R reflexive, symmetric, transitive, antisymmetric, or any combination of these adjectives? Q6) On the average, a certain piece of software X fails every 1 year. The time to repair it is approximately one day. What is the probability that, at any moment in time, X will be available / functioning properly? Q7) In connection with Q6, suppose that a second piece of software Y is also installed on the same system. It fails once every 2 years and takes 7 days to fix. If the system X+Y as a whole is considered "available" only if both X and Y are functioning properly, what is the probabilty that, at any moment in time, X+Y will be available? Q8) Is there a number n such that (7*n) = 1 (mod 10)? Is there a number n such that (q*n) = 1 (mod x) for all positive integers q and x? Q9) Consider the following program: function paint(node n) { if (n->ispainted) return; n->ispainted = true; foreach neighbor of n paint(n); } Suppose that each call to the paint() function costs 10ns (regardless whether or not it's called on an unpainted or painted node). If paint(G.nodes) is called on a graph G such that G is a complete graph Kn, what is the smallest n such that the runtime exceeds 100ns? How would your answer change if calling paint() cost 20ns on an unpainted node (and 10ns on a painted node)? Q10) What is your favorite classical numerical algorithm? How does it work? Why is it your favorite? Q11) Suppose that we represent numbers using IEEE-754 (which sets aside 23 bits for the mantissa, 8 for the excess-127 exponent, and 1 for the sign bit). What is the largest relative error that can occur when a number is represented in this format? Q12) How would you represent 45.25 in IEEE-754? Q13) Suppose we have 16 bits to represent an integer. What are the biggest and smallest numbers that can be represented in 2's complement, 1's complement, and sign-magnitude? Q14) Approximately how many hexadecimal characters are required to represent a positive N-digit base-10 number? Q15) Demonstrate the simplex method on x + 4y y + 5z P(x,y,z) = 3*x+4*y+5*z Quote Link to comment Share on other sites More sharing options...
wood Posted November 6, 2003 Share Posted November 6, 2003 Q1) Express in prefix and postfix: 3-5*7/5+2*(3+4*6) prefix: + - 3 * 5 7 / 5 * 2 + * 4 6 postfix[/b]: 3 5 7 * 5 / - 2 3 4 6 * + * + Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 6, 2003 Share Posted November 6, 2003 Q1) Express in prefix and postfix: 3-5*7/5+2*(3+4*6) prefix: + - 3 * 5 7 / 5 * 2 + * 4 6 postfix: 3 5 7 * 5 / - 2 3 4 6 * + * + Prefix + - 3 / * 5 7 5 * 2 + 3 * 4 6 Postfix 3 5 7 * 5 / - 2 3 4 6 * + * + your prefix is different Quote Link to comment Share on other sites More sharing options...
wood Posted November 6, 2003 Share Posted November 6, 2003 You're right... I always try to do it without a tree and get a wrong answer... damn it. Wood Quote Link to comment Share on other sites More sharing options...
wood Posted November 6, 2003 Share Posted November 6, 2003 Q2) Solve this recurrence: f(n f(n > 1) = f(n/2) + n^p for some p >= 0 I'm getting: n^p+(n/2)^p+(n/2^2)^p+...+(n/2^k)^p n^p*[1+(1/2^p)+(1/2^2p)+...+(1/2^kp)] How do I solve this summation?! Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 6, 2003 Share Posted November 6, 2003 Originally posted by wood Q2) Solve this recurrence: f(n f(n > 1) = f(n/2) + n^p for some p >= 0 I'm getting: n^p+(n/2)^p+(n/2^2)^p+...+(n/2^k)^p n^p*[1+(1/2^p)+(1/2^2p)+...+(1/2^kp)] How do I solve this summation?! p = 0 => f(n) = lg(n) p = 1 => 2n - 1 I am getting same summation i.e f(n) = n^p * sum(k=0 to k = lg(n)-1)[ (1/2)^(kp) ] [color=Blue]+ 1[/color] I don't know about that summation, but I am sure it is not more than 2. Why? 1 + 1/2^p + 1/4^p + 1/8^p ....... the terms decrease by a factor > 2, doing 1+ 1/2 + 1/4 + 1/8 ......... converges towards 2. So assuming summation = 2, we get f(n) = 2n^p +1, assuming the above summation we can get a nice Big OH of the function f(n) = O(n^p) for p > 0 Quote Link to comment Share on other sites More sharing options...
wood Posted November 6, 2003 Share Posted November 6, 2003 Thanks AlbaLed. Good solution. What about this one? Q3) Solve this recurrence: f(n f(n > 1) = f(n-c) + n^p for some p >= 0 [blue] f(n) = f(n-c) + n^p f(n) = f(n-2c) + (n-c)^p + n^p ... Let k=ceiling(n/c) ... f(n) = 1 + (n-kc)^p + ... + (n-2c)^p + (n-c)^p + n^p We can either expand it and get a really nasty PowerSum ... or, we can simply say all the powers of (n-c)^p ... (n-kc)^p will be bounded each by n^p. So, f(n) = O(1 + n^p + n^p + n^p + n^p + ... + n^p) (k+1 times) f(n) = O(1 + (k+1)n^p) Substituting k back f(n) = O(1 + (ceiling(n/c)+1) n^p) O(n) = O(1 + n^(p+1)) = O(n^(p+1)) Is it right? Am I missing something? Wood Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 6, 2003 Author Share Posted November 6, 2003 Originally posted by wood You're right... I always try to do it without a tree and get a wrong answer... damn it. Wood Me, too. I am getting this expression: +-3/*575*2+3*46 357*5/-2346*+*+ Am I making a mistake somewhere? I redid it w/ a tree. Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 6, 2003 Author Share Posted November 6, 2003 Originally posted by AlbaLed Originally posted by wood Q2) Solve this recurrence: f(n f(n > 1) = f(n/2) + n^p for some p >= 0 I'm getting: n^p+(n/2)^p+(n/2^2)^p+...+(n/2^k)^p n^p*[1+(1/2^p)+(1/2^2p)+...+(1/2^kp)] How do I solve this summation?! p = 0 => f(n) = lg(n) p = 1 => 2n - 1 I am getting same summation i.e f(n) = n^p * sum(k=0 to k = lg(n)-1)[ (1/2)^(kp) ] [color=Blue]+ 1[/color] I don't know about that summation, but I am sure it is not more than 2. Why? 1 + 1/2^p + 1/4^p + 1/8^p ....... the terms decrease by a factor > 2, doing 1+ 1/2 + 1/4 + 1/8 ......... converges towards 2. So assuming summation = 2, we get f(n) = 2n^p +1, assuming the above summation we can get a nice Big OH of the function f(n) = O(n^p) for p > 0 I designed this one with the Master Theorem in mind. If you use it, O(n^p) pops out immediately for p > 0. However, the question asked for cases where p >= 0, so the other valid answer is O(lgn) Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 6, 2003 Author Share Posted November 6, 2003 Originally posted by wood Thanks AlbaLed. Good solution. What about this one? Q3) Solve this recurrence: f(n f(n > 1) = f(n-c) + n^p for some p >= 0 [blue] f(n) = f(n-c) + n^p f(n) = f(n-2c) + (n-c)^p + n^p ... Let k=ceiling(n/c) ... f(n) = 1 + (n-kc)^p + ... + (n-2c)^p + (n-c)^p + n^p We can either expand it and get a really nasty PowerSum ... or, we can simply say all the powers of (n-c)^p ... (n-kc)^p will be bounded each by n^p. So, f(n) = O(1 + n^p + n^p + n^p + n^p + ... + n^p) (k+1 times) f(n) = O(1 + (k+1)n^p) Substituting k back f(n) = O(1 + (ceiling(n/c)+1) n^p) O(n) = O(1 + n^(p+1)) = O(n^(p+1)) Is it right? Am I missing something? Wood Totally right. Good job! It's probably worth memorizing the fact that f(n) = f(n-constant) + n^p is O(n^(p+1)) Quote Link to comment Share on other sites More sharing options...
wood Posted November 6, 2003 Share Posted November 6, 2003 Q4) Consider the expression f(x,y) = (x->y)+(y->x)*y Is f a tautology? Is it satisfiable? f(x,y) = x'+y + (y'+x)*y f(x,y) = x'+y + y'y + xy f(x,y) = x'+y + y'y + xy So, f(x,y) is not a tautology, but is satisfiable. Q9) Consider the following program: function paint(node n) { if (n->ispainted) return; n->ispainted = true; foreach neighbor of n paint(n); }Suppose that each call to the paint() function costs 10ns (regardless whether or not it's called on an unpainted or painted node). If paint(G.nodes) is called on a graph G such that G is a complete graph Kn, what is the smallest n such that the runtime exceeds 100ns? How would your answer change if calling paint() cost 20ns on an unpainted node (and 10ns on a painted node)? 10ns = K4 ? 20ns/10ns = if by exceeds you mean >100 and not >=100, then the answer is still K4. If you mean >=, then the answer is K3. Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 6, 2003 Share Posted November 6, 2003 Originally posted by nonevent99 Me, too. I am getting this expression: +-3/*575*2+3*46 357*5/-2346*+*+ Am I making a mistake somewhere? I redid it w/ a tree. Nonevent I think yours is fine, you're getting same thing as I am !! Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 6, 2003 Share Posted November 6, 2003 Wood, A+++++++++++++=-+ I think you're right on Q4, can you elaborate so that others can get it !!!! Quote Link to comment Share on other sites More sharing options...
samlai Posted November 6, 2003 Share Posted November 6, 2003 Q4) Consider the expression f(x,y) = (x->y)+(y->x)*y Is f a tautology? Is it satisfiable? I find it easier to do this: x | y | (x->y)+(y->x)*y ================== T | T | T T | F | F F | T | T F | F | T Thus, not a tautology (results are not all T) and satisfiable (at least one result is T). This method only works well for small inputs. Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 6, 2003 Author Share Posted November 6, 2003 Q4) Consider the expression f(x,y) = (x->y)+(y->x)*y Is f a tautology? Is it satisfiable? f(x,y) = x'+y + (y'+x)*y f(x,y) = x'+y + y'y + xy f(x,y) = x'+y + y'y + xy So, f(x,y) is not a tautology, but is satisfiable. Good, Wood. How about Q5? Q9) Consider the following program: function paint(node n) { if (n->ispainted) return; n->ispainted = true; foreach neighbor of n paint(n); }Suppose that each call to the paint() function costs 10ns (regardless whether or not it's called on an unpainted or painted node). If paint(G.nodes) is called on a graph G such that G is a complete graph Kn, what is the smallest n such that the runtime exceeds 100ns? How would your answer change if calling paint() cost 20ns on an unpainted node (and 10ns on a painted node)? 10ns = K4 ? 20ns/10ns = if by exceeds you mean >100 and not >=100, then the answer is still K4. If you mean >=, then the answer is K3. When paint is called on the first node, it fires off a call to all other nodes. So paint() gets called at least once for each node. It's called on a node, it will then call paint() on all other nodes in Kn. So each node is eventually called once from each other node, for a total of n-1 calls onto each node. There are n such nodes, so the total number of calls is n(n-1). At 10ns per call, this means we want n(n-1) to exceed 100ns/10ns, ie 10. n=4 is the smallest such n such that n(n-1) > 10, so K4 works. Good job, Wood! [banana] I didn't get this on my first try, so I'm especially impressed. Now, a node is painted the first time that paint is called on it. It therefore can only be unpainted the first time paint is called on it. Thus, you must pay a 20ns-10ns = 10ns penalty n times, once for each node. Now the equation to satisfy becomes n(n-1)*10ns + n*10ns > 100ns. That is, n^2 > 10. n = 4 is the first such integer, as you successfully discovered, Wood. (I'm puzzled by how you got K3 on >= 100ns, though). Quote Link to comment Share on other sites More sharing options...
wood Posted November 6, 2003 Share Posted November 6, 2003 Humm, let see. Think of it as a (K-1)-ary tree. For K3, you pay 20ns for the first node (root in our tree). For its 2 children (2 neighbors), you pay also 20ns for each. So far, the total is 60ns. Now, for these two children, you have 2 more children for each to visit, totalling 4 nodes. Each one of them will cost you 10ns = 40ns. That's 60+40 and you get 100ns. Does it make sense? Wood Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 6, 2003 Author Share Posted November 6, 2003 Originally posted by wood Humm, let see. Think of it as a (K-1)-ary tree. For K3, you pay 20ns for the first node (root in our tree). For its 2 children (2 neighbors), you pay also 20ns for each. So far, the total is 60ns. Now, for these two children, you have 2 more children for each to visit, totalling 4 nodes. Each one of them will cost you 10ns = 40ns. That's 60+40 and you get 100ns. Does it make sense? Wood yup. I just plain got it wrong! Thanks for your help. Quote Link to comment Share on other sites More sharing options...
CalmLogic Posted January 16, 2007 Share Posted January 16, 2007 *** bump Quote Link to comment Share on other sites More sharing options...
omaradib Posted September 13, 2007 Share Posted September 13, 2007 Seems the forum was very active during 2003. But, not every questions are answered. Q5, my answers: It is closed under reflexive and transitive. But not symmetric or antisymmetric. Just the nature of implication operator. Quote Link to comment Share on other sites More sharing options...
CalmLogic Posted September 14, 2007 Share Posted September 14, 2007 A similar but apparently different set of questions with solutions: Q1) Consider the 2-variable boolean function f(x,y) = (x->y)*(y->x) Is this expression a tautology? Is it satisfiable? (x->y)*(y->x) = (y + x’)(x + y’) = xy + x’y’ = (x==y) Not a tautology (consider x=0, y = 1), but satisfiable (consider x=y=0) Q2)Now consider the boolean expression in Q1 as a binary relation R from x to y in the sense that xRy iff f(x,y) = true. Is R reflexive? Is it symmetric? Is it transitive? The relation is defined on the space {0, 1}. Trying all the combinations of 0’s and 1’s, it’s apparent that R = {, } Since aRa for any a in {0,1}, R must be reflexive. Since aRb implies bRa, R must be symmetric. Since aRb and bRc implies aRc, R must be transitive. BTW, this means R is an equivalence relation. http://www.www.urch.com/forums/gre-computer-science/7751-driller-mathematics-2.html Quote Link to comment Share on other sites More sharing options...
night Posted September 27, 2007 Share Posted September 27, 2007 I also noticed that this forum was very active in 2003. I constantly browse back to old threads looking for interesting questions. Why is the forum almost dead nowadays? (with the notable exception of a few who post) Quote Link to comment Share on other sites More sharing options...
CalmLogic Posted September 27, 2007 Share Posted September 27, 2007 Maybe the GRE CS exam is becoming less popular? On the other hand, even in 1998 the GRE CS was suffering from a popularity crisis: I don't know about other departments, but we don't pay a lot of attention to the GRE subject in our graduate admissions. The generals are much more important...(not to mention transcripts and letters). This sort of question might explain why. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppst...@ics.uci.edu http://www.ics.uci.edu/~eppstein/ which sort is more independent of its input - comp.theory | Google Groups Quote Link to comment Share on other sites More sharing options...
super mutant Posted October 2, 2007 Share Posted October 2, 2007 Q5) I'm getting that R is reflexive, transitive and antisymmetric, but not symmetric. I included antisymmetric because any time xRy^yRx then x=y. I was also assuming that the f(x,y) in Q5 is the f(x,y) from Q4. Quote Link to comment Share on other sites More sharing options...
brianhead Posted October 3, 2007 Share Posted October 3, 2007 Q2) Solve this recurrence: f(n f(n > 1) = f(n/2) + n^p for some p >= 0 what if p equals to 0? then it should be O(log(n)) Quote Link to comment Share on other sites More sharing options...
dhruvbird Posted October 6, 2010 Share Posted October 6, 2010 Q2) Solve this recurrence: f(n f(n > 1) = f(n/2) + n^p for some p >= 0 what if p equals to 0? then it should be O(log(n)) The answer to this would be O(n^p log n) using the formula for the Master method as given on wikipedia Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.