Practice Problems For Fun

[mrnutty]

Just for Fun, and for reference to the web searchers, lets start a series of problems in computer science thats ranges in difficulty from [1,10], where 1 is easy, and 10 is harder. Maybe I and others will learn something useful from this. The following exercise is meant as an mental exercise relative to computer science subject. So without further ado, here are 3 problems for fun. Anyone is welcome to post their solution. It would be interesting to see different way of approaching to solve the same problem.

Questions:

Difficulty level = 2
1) What is the runtime of the following algorithm? Prove it!

for(int i = 0; i < N; ++i){
 for(int j = 0; j < i; ++j){
   for(int k = 0; k < j; ++k){
      print( sqrt( i*i + j*j + k*k) ); //assume this takes O(1)
   }
 }
}

Difficulty level = 3
2) Prove by induction that the series 1 + 2 + 3 + 4 + ... + n = n(n-1)/2

Difficulty level = 3
3) Prove that max{ f(n) , g(n) } = THETA( f(n) + g(n) ), where max function returns the max value of f(n) or g(n) for some natural number n. Assume that f(n) and g(n) are time complexities, therefore postive.

[csurfer]

Problem 1:

Legend :
Summation where z ranges from low to high( ) :: S-z-[low]-[high]( )

Above stated problem is as follows...

S-i-[0]-[n-1]( S-j-[0]-[i-1]( S-k-[0]-[j-1]( 1 ) ) )

S-i-[0]-[n-1]( S-j-[0]-[i-1]( j ) )

S-i-[0]-[n-1]( (i-1)*i/2 )

S-i-[0]-[n-1]( (i^2-i)/2 )

1/2 * { S-i-[0]-[n-1]( i^2 ) - S-i-[0]-[n-1]( i ) }

1/2 * { (n-1)(n)(2n-1)/6 - (n-1)(n)/2 }

On solving...

(n)(n-1)(2n-4)/12

Neglecting the co-efficients its O(n^3).
Or can be said to be of cubic complexity.

Problem 2:

==> 1+2+3+4+5+....+n
==> Pairing the 1st elements form both end 2nd elements form both end and so on...
==> (n + 1)+(n-1 + 2)+(n-2 + 3)+.....
==> (n + 1)+(n + 1)+..... n/2 times
==> (n+1)n/2

Assuming it to be true for n as n(n+1)/2
Summation upto n+1 should be n+1 added to this sum ie,

n(n+1)/2 + n+1
Solving
(n+1)(n+2)/2
Which is actually (n+1)((n+1)+1)/2
hence it proves that the formula is applicable for any n.