Interesting Problems

Interesting Problem 5 : Trees

noreply@blogger.com (Sarcastic Bastard) — Sun, 04 Jul 2010 08:26:00 +0000

Q.5 Consider the following sequence of keys

(5,16,22,45,2,10,18,30,50,12,1)

Consider the insertion of items with this set of keys, in the order given, into :

a. An initially empty (2,4) tree T’

b. An initially empty red black tree T’’

My solution :

Interesting Problem 4 : Writing VB Scripts

noreply@blogger.com (Sarcastic Bastard) — Sun, 04 Jul 2010 06:54:00 +0000

Write a script to simulate the rolling of two dice. The script should use Math.random to roll the first die and again to roll the second die. The sum of the two values should then be calculated. [note: Since each die can show an integer value from 1 to 6, the sum of the values will vary from 2 to 12, with 7 being the most frequent sum, and 2 and 12 the least frequent sums. Your program should roll the dice 36,000 times. Use a one-dimensional array to tally the numbers of times each possible sum appears. Display the results in an XHTML table. Also determine whether the totals are reasonable.(e.g., there are six ways to roll a 7, so approximately 1/6 of all the rolls should be 7)]

My Solution: Writing in a file named as scripts.vbs .

Dim dice1
Dim dice2
Dim total(10)
total(0)=0
total(1)=0
total(2)=0
total(3)=0
total(4)=0
total(5)=0
total(6)=0
total(7)=0
total(8)=0
total(9)=0
total(10)=0

Dim max,min
max=6
min=1
Dim sum

for count =0 to 35999
dice1 = Int((max-min+1)*Rnd+min)
dice2 = Int((max-min+1)*Rnd+min)
sum = dice1 + dice2

Select Case sum
Case 2
total(0) = total(0) + 1
Case 3
total(1) = total(1) + 1
Case 4
total(2) = total(2) + 1
Case 5
total(3) = total(3) + 1
Case 6
total(4) = total(4) + 1
Case 7
total(5) = total(5) + 1
Case 8
total(6) = total(6) + 1
Case 9
total(7) = total(7) + 1
Case 10
total(8) = total(8) + 1
Case 11
total(9) = total(9) + 1
Case 12
total(10) = total(10) + 1
End Select

Next

Now we can import these values in html table using document.write property and using html tags .

Interesting Problem 3 : Decimal to Floating Point Conversion

noreply@blogger.com (Sarcastic Bastard) — Fri, 18 Jun 2010 04:55:00 +0000

1. Assuming your not restricted to using normalized form, list all the bit patterns that could be used to represent the value 3/8 using the floating- point format described in Figure contains an 8 bit floating point format "a 1 bit sign bit, b. 3 bit exponent, and c. 4 bit mantissa" A= Sign bit, B= Exponent, C=Mantissa. A B B B C C C C. One of the answers is: 01000110,

My solution:

As stated in the question one of the solutions is 01000110.

So assuming this is the first representation of 3/8 in floating –point format.

3/8 can be written as 0.011 in binary having decimal and integer part.

01000110 is 0110.0 × 2^-4

So other solutions will be

01000011 is 0011.0 × 2^-3

01100001

01110000

The last two solutions are not precise due to fewer bits in Mantissa. This is the limitation of floating point numbers. Preciseness can be improve by having representation in more bits .

Interesting Problem 2 : Pumping Lemma

noreply@blogger.com (Sarcastic Bastard) — Wed, 16 Jun 2010 20:20:00 +0000

1. Show that the language {an bcba2n : n ≥ 0} is not regular using the pumping lemma.

Ans. If the Language L = an bcba2n is regular than it can be converted into string w where w = xyz . so we have that xyz = an bcba2n . Now since y ≠ € , there can be three cases .

Case 1 : Now assume y is having an instance of a and z will have the rest of bcba2n . Now according to pumping lemma we will have xyⁱz where i ≥ 0 , will also lies in L but if i = k , then we can increase the instances of a without increasing the instance of a present in substring z . So it can’t be a regular language .

Case 2: Now assume that y = bcb , in that case . xyⁱz when i = 0 will not have any instance of bcb . so the resulting language would be falling in L . Hence L can’t be a regular language.

Case 3: Now assume that y is having an instance of a present after bcb . in that case x = aⁿbcb , y = a^k , z = a^2n-k. Now according to pumping lemma xyⁱz where i≥0 , should lie in L . Now if we increase the value of i , we can have more instances of a in the later part which violates the property of L having exactly double number of instances of a present in the substring x . Hence L can’t be a regular language.

As none of the case is able to provide valid proof of pumping lemma L can’t be a regular language.

Interesting Problem 1 : State Transition Diagram

noreply@blogger.com (Sarcastic Bastard) — Wed, 16 Jun 2010 20:09:00 +0000

Give a transition diagram for a pushdown automaton that accepts the language {a^i b^j c^k | i + k = j}.

My Solution :