onur.cobanoglu.84
BAN USERTo the best of my knowledge, computers cannot bitwise OR unboundedly large integers in a single operation. They can bitwise OR two words in a constant time, though. If the range of numbers in two lists are k, then it will take O(k) two take bitwise OR of bit vectors of two lists. If none of the lists are supposed to have duplicate values, then k will be at least n, where n is the length of the larger list. Hence this solution is O(n), not O(1).
- onur.cobanoglu.84 July 11, 2010If no extra place is to be used, then matrix transposition must be done in-place. There's a paper named "In-Place Transposition of Rectangular Matrices" telling an algorithm on how to do it. You can find it easily on Google.
- onur.cobanoglu.84 July 11, 2010No, it does.
Proof: First element is chosen from the whole array uniformly at random, so the probability that itself will be chosen is 1/n. The probability that second element will be itself is the probability that the first element in the shuffled version is not the second element in the first array (and this probability is (n-1)/n) times the probability that the second element in the shuffled array will be the second element in the original array (which requires choosing itself, and that probability is 1/(n-1)). So the product makes 1/n. In general, the probability that kth element will remain in place is the probability that some (k-1) permutation of the array which does not include kth element will be chosen for the first (k-1) places in the shuffled array (which is P(n-1,k-1)/(n*...*(n-k+2))) times kth element will be chosen among the remaining elements (which is 1/(n-k+1)). This product is always 1/n.
It means that there is a dynamic (run-time) stack of scopes and binding of any variable is looked for from the top to the bottom of the stack.
- onur.cobanoglu.84 July 16, 2010In C++ there is no dynamic scoping for variables (at least in a straightforward manner, but if there is a really subtle way of doing it, I don't know).