Knuth shuffle

from wikipedia

In a computer, shuffling is equivalent to generating a random permutation of the cards. There are two basic algorithms for doing this, both popularized by Donald Knuth. The first is simply to assign a random number to each card, and then to sort the cards in order of their random numbers. This will generate a random permutation, unless two of the random numbers generated are the same. This can be eliminated either by retrying these cases, or reduced to an arbitrarily low probability by choosing a sufficiently wide range of random number choices.

The second, generally known as the Knuth shuffle or Fisher-Yates shuffle, is a linear-time algorithm (as opposed to the previous O(n log n) algorithm if using efficient sorting such as mergesort or heapsort) which involves moving through the pack from top to bottom, swapping each card in turn with another card from a random position in the part of the pack that has not yet been passed through (including itself). Providing that the random numbers are unbiased, this will always generate a random permutation.

programming pearls

1. the use of bitmap for counting when memory is unlimited
2. the find of substrings with maximum sum with recursive and O(N) complexity
3. rotate a string with reversal function

c++ abstract

1. system function

2. the use of namespace to distinguish

3. the order of linking; linker links object module (corresponding to file) and the order may be fixed

4. extern (declaration rather than definition)

5. oct hex used for output with different numeric formats

6. the C++ Standard does not “include” the STL (HP and then SGI)

7. The boundary between compilers and interpreters can with Python, which has many of the features and power of a compiled language but the quick of an interpreted language.

8. volatile versus const; volatile means “You never know when this will change,” and prevents the compiler from performing any optimizations based on the stability of that variable.

excerpt of effective c++

1. rules for effective c++ programming vary, depending on the part of c++ you are using (c, c++, template, STL)

2. For simple constants prefer const objcts or enums to $defines (enum hack)

3. For function-like macros, prefer inline functions to #defines (which has side-effect)

4. Declaring soemthing const helps compilers detect usage erros. const can be applied to objects at any scope, to function parameters and return types, and to member functions as a whole

5. Compilers enforce bitwise constness, but you should program using conceptual constness (e.g., use of mutable)

6. When const and non-const member functions have essentially identical implementations, code duplication can be avoided by having the non-const version call the const version

7. Manually initialize objects of built-in type, because C++ only sometimes initializes them itself

8. In a constructor, prefer use of the member initialization list to assignment inside the body of constructor. List data members in the initialization list in the same order they are declared in the class.

9. Avoid initilization order problems across translation units by replacing non-local static objects with local static objects

1. count odd num (xor) , exchange x and y
2. count bit num x&x-1
3. reverse the nth element double pointer
4. large number addition
5. max sum substring, sufficient and necessary condition
6. db group by
7. garbage collection: reference count and mark and sweep
8. newton-raphson
9. knuth-morris-pratt

A warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.

"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the 'On' or the 'Off' position. I am not telling you their present positions. The switches are not connected to anything.

"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none, either. Then he'll be led back to his cell.

"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.'

"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."

another prison puzzle

John and Dianne, two journalists (and experienced bridge players), are captured by some foreign government. The guardian says that he can free them, if they win the following game. First, Dianne must choose five random cards from a standard 52 card pack. Then, she must send one card at a time (through the guardian) to John. When John receives the fourth card, it must correctly guess the fifth card that Dianne still has. If he guesses correctly, they are both free. Otherwise, they will both stay in prison forever.

Can John and Dianne exit the prison in these conditions?

Assumptions:
- Before the actual game, John and Dianne can talk together for one day and decide their playing strategy. But, after that, they cannot communicate in any way - they are now completely isolated forever (or, at least, until they get out from the prison). Also, they are completely isolated from the outer world (no cell phones) etc. The only method to communicate between them will be through the cards that Dianne sends to John.
- The time interval between delivering the cards cannot be used as a method to communicate information. In fact, the guardian might randomly delay delivering the cards to John just to make sure that they are not using this trick to send additional information.
- Dianne cannot alter the cards the she sends in any way to send additional information. In fact, after receiving a card from Dianne, the guardian might send to John another (almost identical) card of the same type, to make sure that she didn't use the card to send additional clues to John.

back-of-envelope-calculation

The average number of customers in a stable system (over some time interval), N, is equal to their average arrival rate, λ, multiplied by their average time in the system, T, or:

Although it looks intuitively reasonable, it's a quite remarkable result, as it implies that this behavior is entirely independent of any of the detailed probability distributions involved, and hence requires no assumptions about the schedule according to which customers arrive or are serviced. The only assumption is that the system operates in a first-come-first-served manner (FCFS).

regarding binary search: watch the condition

find an O(n) complexity algorithm to find the kth big(or small) element; Hoare's algorithm based on quicksort

Newton iteration: simulate function by straight line: x(i+1) = x(i)-f(i)/f(i)'

basic principles of graph theory

1. The number I of loops in an arbitrary undirected connected graph is related to the number of its edges L and vertices N: I = L + 1-N

2. the clustering coefficient C of a vertex is the ratio between the total number y of the edges connecting its nearest neighbors and the total number of all possible edges between all these nearest neighbors, C = 2y/(z(z-1)). Thus, the clustering coefficient for tree is zero.

cisco p2p

from http://www.computerbusinessreview.com/article_news.asp?guid=65882650-14FB-49D0-B9DB-5E5FC1AC6AAE

Cisco has taken part in an $8m second round of funding for Oversi, an Israeli developer of peer-to-peer caching and content delivery technology for ISPs.