confidence booster 103

[nonevent99]

 

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

 

 

[wood]

 

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 * + * +

 

 

[AlbaLed]

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

[wood]

You're right... I always try to do it without a tree and get a wrong answer... damn it.

 

Wood

[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?!

[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 

[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

 

[nonevent99]

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.

[nonevent99]

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)

[nonevent99]

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))

 

[wood]

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.

 

[AlbaLed]

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 !!

[AlbaLed]

Wood, A+++++++++++++=-+

 

I think you're right on Q4, can you elaborate so that others can get it !!!!

[samlai]

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.

[nonevent99]

 

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).

[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

[nonevent99]

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.

[CalmLogic]

*** bump

[omaradib]

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.

[CalmLogic]

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

[night]

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)

[CalmLogic]

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

[super mutant]

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.

[brianhead]

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))

[dhruvbird]

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