Friday, December 1, 2006
- The digits in the number are sorted(ascending order, left to right)
- The digits in the square of the number are also sorted
(Ex: N=12 N^2 = 144 fits the bill, but N=11, N^2 = 121 - does not. )
Prove that the number of numbers that satisfy this criteria is infinite.
(Got it from Knuth's lectures on the Stanford site.)
Thursday, November 30, 2006
Here is an interesting problem:
Given two n-bit numbers A and B, represented as two single-bit-arrays An-1...A0 and Bn-1...B0,
Write a program that generates a CNF (Conjunctive Normal Form) expression that checks if A is less than B.
Hint - The CNF expression for checking if a single-bit number A0 is less than another single-bit number B0 is = !A0.B0 = !(A0 + !BO) in CNF
I'll post the answer to this soon.
Sunday, November 26, 2006
We'll it's certainly possible, but it can be expensive. Consider random numbers with maximum value say 100, let's say we have the sequence
92 51 11 69 24 35 17 36 26 98The program to sort this sequence in O(n) is time is given at code for O(n) sorting
The output of the program is
11 17 24 26 35 36 51 69 92 98
Question 1: What are the disadvantages of such sorting methods - give at-least two
Question 2: Can you write code, given a sequence of numbers as input, it can verify if the array is in sorted order
PS: The curious and smart will notice that O(n) is not the correct analysis of the algorithm, so whats the correct complexity then?
Saturday, November 25, 2006
The problem is taken from Sheldon M Ross's Introduction to Probability Models (seventh Edition). Problem number 32, page 19 is stated as
Suppose all 'n' men at a party throw their hats in the center of the room. Each man randomly selects a hat. Show that the probability that none of the n men, selects his own hat isI've written a computer program to actually calculate the probability from the given sample space. The source code is at "The Hat Throwing Problem Code"
I have the analytical solution, but I want to hide it, till you solve it for yourself.
Monday, November 20, 2006
The blog will over a period of time evolve in a self aligned and organized group of topics. We hope the pattern will become clearer as the topics progress.
So, welcome and please keep us updated. The success of this blog will largely depend on regular feedback and help from all of you.