driller for mathematics

[nonevent99]

One more lengthy drill from me, guys. Enjoy.

 

Q1) Consider the 2-variable boolean function f(x,y) = (x->y)*(y->x)

Is this expression a tautology? Is it satisfiable?

 

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?

 

Q3) How do you know whether an undirected graph has an Eulerian circuit?

 

Q4) A certain network of n computers, represented as a graph, is complete. How many distinct routes are there from computer X to computer Y (X is different than Y), if it is assumed that a route can visit a computer no more than once?

 

Q5) What is A(2,y) as a function of y, given the following?

A(0,y) = y+1            {for y >= 0}
A(x,0) = A(x-1,1)      {for x > 0}
A(x,y) = A(x-1,A(x,y-1)) {otherwise}

If you cannot get an exact answer, then express your answer in Big-O notation.

 

Q6) How many distinct numbers can be represented in 8-bit 2's complement (and how many are positive numbers)? How about sign-magnitude? How about 1's complement?

 

Q7) What is the difference between a rotation matrix and a permutation matrix?

 

Q8) If you multiply a row in an n-by-n matrix by 15, how does that affect the determinant? What if you swap the position of two rows?

 

Q9) Suppose we use Newton's method to find the zero of x^4 - 16, and our first guess is 5. What is the error after two iterations?

 

Q10) Let x = 10 and y = 110. Are these numbers relatively prime? Are they congruent mod 9? What is their GCD and LCM?

 

 

 

 

 

[AlbaLed]

Q3) How do you know whether an undirected graph has an Eulerian circuit?

Degree of all edges should be even

 

Q4) A certain network of n computers, represented as a graph, is complete. How many distinct routes are there from computer X to computer Y (X is different than Y), if it is assumed that a route can visit a computer no more than once?

(n-2)! + 1

X can send it to Y directly this is the "+ 1" above or

X can send it to n-2 other nodes which, which in turn can send it to (n-3 ) nodes and so on untill it arrives ar Y therefore (n-2)!

 

Q5) What is A(2,y) as a function of y, given the following?

 

A(0,y) = y+1            {for y >= 0}
A(x,0) = A(x-1,1)      {for x > 0}
A(x,y) = A(x-1,A(x,y-1)) {otherwise}

If you cannot get an exact answer, then express your answer in Big-O notation.

Ackerman's function, a pain in the butt function, grows faster than poly and exponential, try writting a program that computes A(6, 6) and you'll see what I mean.

 

Q6) How many distinct numbers can be represented in 8-bit 2's complement (and how many are positive numbers)? How about sign-magnitude? How about 1's complement?

2's complement 2^8 different numbers -2^7 to 2^7 -1

1's complement 2^8 - 1 different numbers -2^7 -1 to 2^7 -1 and 2 zeors

sign magnitude, = same as 1's complement

Q7) What is the difference between a rotation matrix and a permutation matrix?

No idea

Q8) If you multiply a row in an n-by-n matrix by 15, how does that affect the determinant? What if you swap the position of two rows?

if you multiply a row by 15 than the determinant is multiplied by 15,

if you swap two rows then the sign of determinant changes

 

Q9) Suppose we use Newton's method to find the zero of x^4 - 16, and our first guess is 5. What is the error after two iterations?

No clue, need some help on this topic. Can someone explain this in detail, including any tricks there might be??????

Q10) Let x = 10 and y = 110. Are these numbers relatively prime? Are they relatively prime mod 9? What is their GCD and LCD?

Assuming x, y are decimal

Nope they are not relatively prime

Don;t know about relatively prime mod 9, but I don't think so because 10 mod 9 = 1

GCD = 10

Should LCD be LCM (least common multiple ??)

LCM = 110

If it is LCD (least common divisor, eventhough I've never heard of such thing)then

LCD = 2

[wood]

Q1) Consider the 2-variable boolean function f(x,y) = (x->y)*(y->x)

Is this expression a tautology? Is it satisfiable?

x y x->y y->x f(x,y)
0 0   1    1    1 
0 1   1    0    0
1 0   0    1    0
1 1   1    1    1

f(x,y) is not a tautology and it is satisfiable.

 

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?

 

R is reflexive and symmetric. Not transitive.

 

Q4) A certain network of n computers, represented as a graph, is complete. How many distinct routes are there from computer X to computer Y (X is different than Y), if it is assumed that a route can visit a computer no more than once?

(n-2)! + 1

X can send it to Y directly this is the "+ 1" above or

X can send it to n-2 other nodes which, which in turn can send it to (n-3 ) nodes and so on untill it arrives ar Y therefore (n-2)!

 

Humm, I don't think so. For a K5, you have much more routes than (n-2)! + 1. For example:

 

You can visit it directly (no hops). 1 combination.

You can visit it using 1 hop. 3 combinations.

You can visit it using 2 hops. 6 combinations.

You can visit it using 3 hops. 6 combinations.

 

That's 16 combinations.

 

So, generically,

 

You can visit it directly (no hops). 1 combination.

You can visit it using 1 hop. n-2 combinations.

You can visit it using 2 hops. (n-2)(n-3) combinations.

You can visit it using 3 hops. (n-2)(n-3)(n-4) combinations.

...

You can visit it using n-2 hops. (n-2)!

 

What's the formula for that?

[wood]

Q5) What is A(2,y) as a function of y, given the following?

A(0,y) = y+1            {for y >= 0}
A(x,0) = A(x-1,1)      {for x > 0}
A(x,y) = A(x-1,A(x,y-1)) {otherwise}

If you cannot get an exact answer, then express your answer in Big-O notation.

 

O(2^y -1) ???

 

Please, confirm.

 

Wood

[wood]

Q7) What is the difference between a rotation matrix and a permutation matrix?

 

Rotation matrix:

http://mathworld.wolfram.com/RotationMatrix.html

 

Permutation matrix:

http://mathworld.wolfram.com/PermutationMatrix.html

[AlbaLed]

wood, I think the out put for 2 will be 2(y + 1) +1. I have my little ackerman function running on my machine, tried to compute A(5, 5). Wana try it wood, try A(4, 4) and see how you're machine does. Here is the code, it outputs the number of calls made to A(x, y) in tenthousands. Here is the code, it will strech the limits on your machine. give it a shot. Forget about java, this code will die real fast in java

 

#include 
#include 
  long calls = 0, tenThouCalls = 0;
  long A(long x, long y)
   { 
     calls ++;
if(calls%10000 == 0)
     {
	tenThouCalls++;
	calls = 0;
	cout";;
     }
     if(x == 0) return y+1;
     if(y == 0) return A(x-1, 1);
     return A(x-1, A(x, y-1));
   }
   void main()
   {
     int x, y;
     cout";
     cout      cin>>x;
     cout      cin>>y;

     cout";;
   }

[AlbaLed]

My machine gave up trying to compute A(4, 4) at about 2,760,760,000 calls to A(x, y), now I know how many calls the runtime stack of my machine can hold (2 params each call). Pretty neat huh ?

[AlbaLed]

Wood said

What's the formula for that?

 

2^(n - 1) ???

[wood]

For K5 = 16 comb., for K6 = 65 comb... weird. I must be missing something.

 

Wood

[AlbaLed]

wood maybe you made a mistake in calculating K5

K3 = 2

K4 = 5

K5 = 17

K6 = 65

 

Therefore 2^(n-2) + 1

[wood]

Maybe... but I can't seem to find 17 comb for K5. I must be getting tired or dumb.

[AlbaLed]

I counted K3, K4 you supplied K6, therefore I assumed K5, I am not getting 17 either. I've got to move on, you take over from here :D

[AlbaLed]

But the problem is I will not go to sleep by leaving one problem unsolved, so here is what I think

 

for even n > 2 there is 2^(n-2) +1 paths

for odd n > 1 there is 2^(n-2) paths

 

Anyone ???

[rafi_dery]

Q4:

First I explain 2^(n-2), but I think it's wrong.

wlg the route is between computer-1 and computer-n

represent a route as a word of n bits in which a bit I is "on" if the route is going through computer-I.

 

the 1st and nth bit are always on.

1 0 0 ..   0 0 1
1 0 0 ..   0 1 1
1 0 0 ..   1 0 1

 

a total of 2^(n-2) words to describe the routes.

 

Why I think it's wrong?

because it doesnt account for the inner order of the traversal.

the route 1-a-b-c-N is different than 1-b-a-c-N, but they have the same bitmap.

 

A general route between 1---N can have 0 to (n-2) tandem vertices.

for 0: 1 (direct)

for 1: there are (n-2) possiblities

for 2: P(2,n-2) = (n-2)(n-3)

for 3: P(3,n-2) = (n-2)(n-3)(n-4)

...

 

No idea how to sum all these

[rafi_dery]

Q5: Ackerman

According to this link

http://www.nyx.net/~fbrosson/ack/

ackerman is linear for x3

[wood]

AlbaLed... I calculated K7 (1+(n-2)+(n-2)(n-3)+...+(n-2)(n-3)(n-4)(n-5)(n-6)), and it gives you 326 combinations, much higher than 2^5 = 32.

 

The summation I posted and that rafi confirmed is correct. However, to get a formula is a little harder.

 

It looks like a sum of permutations:

 

1 + E[k=1..n-2, (n-2)Pk, (n-2)P1 + (n-2)P2 + (n-2)P3 + (n-2)P4 + ... + (n-2)Pk ]

 

I couldn't find the formula for the sum of permutations, just for the sum of combinations (binomial coefficient sum).

 

Anyone?

 

 

[nonevent99]

Here is an answer key, compiled from all your answers, and my own. (In some cases, your answers were so much better than anything I could come up with that I just plagiarized your work. Good job, guys!)

 

Items that could really use more discussion will be highlighted in orange. I will update this entry until no orange items remain.

 

 

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.

 

Q3) How do you know whether an undirected graph has an Eulerian circuit?

 

Degree of all edges should be even

 

Q4) A certain network of n computers, represented as a graph, is complete. How many distinct routes are there from computer X to computer Y (X is different than Y), if it is assumed that a route can visit a computer no more than once?

Well, you could go directly there. That’s 1 such route.

You could go via 1 other computer. There’s n-2 such routes.

You could go via 2 other computers. There’s (n-2 P 2) such routes.

 

In general, the answer is the sum of (n-2 P k) from k = 0 thru n-2. For convenience, let m = n-2.

 

Then the sum is E(k=0,k=m of (m!)/(m-k)!) = m! * E(k=0,k=m of 1/(m-k)!) = m! * E(r=0,r=m of 1/r!)

 

In case you didn’t know, E(r=0, r=infinity of 1/r!) is e, the special transcendental number. So the answer to this problem is pretty close to e*m! = e*(n-2)! for very large n.

 

Q5) What is A(2,y) as a function of y, given the following?

A(0,y) = y+1            {for y >= 0}
A(x,0) = A(x-1,1)      {for x > 0}
A(x,y) = A(x-1,A(x,y-1)) {otherwise}

If you cannot get an exact answer, then express your answer in Big-O notation.

 

The exact answer is 2y+3. There are lots of places to look this up, one of which is http://pw1.netcom.com/~hjsmith/Ackerman/Acker1L.html. The ETS practice problems have asked about A(1,y) in the past, and it wouldn’t surprise me if it’s good to memorize A(2,y) = 2y+3.

 

Q6) How many distinct numbers can be represented in 8-bit 2's complement (and how many are positive numbers)? How about sign-magnitude? How about 1's complement?

 

2's complement 2^8 different numbers -2^7 to 2^7 -1

1's complement 2^8 - 1 different numbers -2^7 -1 to 2^7 -1 and 2 zeors

sign magnitude, = same as 1's complement

 

Q7) What is the difference between a rotation matrix and a permutation matrix?

Multiplying a matrix by a permutation matrix is equivalent to swapping rows. It has one 1 per row and per column, with all other entries being 0.

 

If a vector is viewed as being a pointer to a location in space W, a rotation matrix can be used to transform the pointer to a different space W’ with the same number of dimensions as W but a different orientation. (e.g.: you could rotate “around” the z-axis by 45 degrees so that the point in W lies on the x-axis of W’). Rotation matrices are very similar to permutation matrices, except that you can have entries which are neither 0 nor 1, as long as the quadratic sum of the entries in a row or column is 1.

 

http://mathworld.wolfram.com/PermutationMatrix.html

http://mathworld.wolfram.com/RotationMatrix.html

 

 

Q8) If you multiply a row in an n-by-n matrix by 15, how does that affect the determinant? What if you swap the position of two rows?

 

If you multiply a row by 15, then the determinant is multiplied by 15.

If you swap two rows, then the determinant is multiplied by -1.

 

Q9) Suppose we use Newton's method to find the zero of x^4 - 16, and our first guess is 5. What is the error after two iterations?

 

Letting f(x) = x^4 – 16, f’(x) = 4*x^3.

 

f(5) = 25*25-16 = 625-16 = 609

f’(5) = 4*25*5 = 500

 

The first iteration produces 5 – 609/500 = approx 5-600/500 = 5-1.2 = 3.8

 

f(3.8) = 192.5 or so

f’(3.8) = 4*3.8^3 = 220 or so

 

The next iteration produces 3.8 – 192.5/220 = 2.9 or so.

 

any mistakes there?

 

Q10) Let x = 10 and y = 110. Are these numbers relatively prime? Are they congruent mod 9? What is their GCD and LCM?

 

 

 

10 and 110 share many factors, so they are not relatively prime

 

10 % 9 = 1, 110 % 9 = 2, so they are not congruent mod 9

 

To compute the GCD, you can factor 10 = 2*5 and 110 = 11*2*5 and take the largest common subset of factors, 2*5 = 10.

 

To compute the LCM, you can multiply 10 * 110 = 1100 and then divide by the GCD = 10 to get 110.

 

 

[AlbaLed]

Wood, that was my mistake. I was doing binomial coeficient summation, yesterday seemed like a really bad performance day. I hope it does not happen on the test day

[wood]

Hey dude.. don't worry. You'll be the only one acing this test... We'll all be behind you with 98%! I hope! :D

[AlbaLed]

Nonevent what is LCD (least common ...........)?

[nonevent99]

Originally posted by AlbaLed

 

Nonevent what is LCD (least common ...........)?

 

Lowest common dumb-schmuck. :p That's me.

 

I meant Least Common Multiple, and will update my posts accordingly.

[nonevent99]

Did anybody see an error in this?

 

Q4) A certain network of n computers, represented as a graph, is complete. How many distinct routes are there from computer X to computer Y (X is different than Y), if it is assumed that a route can visit a computer no more than once?

 

Well, you could go directly there. That’s 1 such route.

You could go via 1 other computer. There’s n-2 such routes.

You could go via 2 other computers. There’s (n-2 P 2) such routes.

 

In general, the answer is the sum of (n-2 P k) from k = 0 thru n-2. For convenience, let m = n-2.

 

Then the sum is E(k=0,k=m of (m!)/(m-k)!) = m! * E(k=0,k=m of 1/(m-k)!) = m! * E(r=0,r=m of 1/r!)

 

In case you didn’t know, E(r=0, r=infinity of 1/r!) is e, the special transcendental number. So the answer to this problem is pretty close to e*m! = e*(n-2)! for very large n.

 

 

[dhruvbird]

+1

Taylor series - Wikipedia, the free encyclopedia