# Full Binary Tree Theorem

#### The theorem

Let T be a nonempty, full binary tree.

The theorem claims that the number of nodes N, the number of leaves L, and the number of internal nodes I are related in such a way that if you know any one of them, you can determine the other two. Continue reading Full Binary Tree Theorem

# Generate random weighted variables

In this post I describe the common problem how to generate random weighted variables. For example you have a die with 6 faces that is fixed, so the probability of an 1 is not the same with the probability of a 2 etc.

The table below shows an example:

 Face Probability 1 25 2 25 3 20 4 20 5 5 6 5

One easy solution is to reduce the problem to another one with a die with 100 faces that is not fixed.

You generate a random value from 0-99 that follows the uniform distribution. Do not use the modulo function to do that. See this post instead.

Once you have that value you perform the following steps:

You check the space within which that value relies.

1. between 0 and 24, you generate 1 as the weighted variable
2. between 25 and 49, you generate 2 as the weighted variable
3. between 50 and 69, you generate 3 as the weighted variable
4. between 70 and 89, you generate 4 as the weighted variable
5. between 90 and 94, you generate 5 as the weighted variable
6. between 95 and 99, you generate 6 as the weighted variable

# Generate uniformly distributed random variables

Formulas shown below generate values that follow uniform distribution.

Using simple modulo methods is not considered as a good solution (although used a lot by students) as the module function does not generate all the variables with the same frequency.

### Random integer between [ 0, 1 ]

`int r = (int) (rand()/(RAND_MAX + 0.0));`

### Random integer between [ 0, 1 )

`int r = (int) (rand()/(RAND_MAX + 1.0));`

### Random integer between [ 0, N ]

`int r = (int) (N * (rand() / (RAND_MAX + 0.0)));`

### Random integer between [ 0, N )

`int r = (int) (N * (rand()/(RAND_MAX + 1.0)));`

### Random integer between [ M, N ]

`int r = (int) (Μ + (rand()/(RAND_MAX + 0.0))*(N-M+1));`

### Random integer between [ M, N )

`int r = (int) (Μ + (rand()/(RAND_MAX + 1.0))*(N-M+1));`

### Summary

The general formula is:

`int r = (int) (A + (rand()/(RAND_MAX + C))*B);`

Values of M, N, K are shown in the following table:

 Range A B C [ 0, 1 ] 0 1 0.0 [ 0, N ] 0 N 0.0 [ M, N ] M N – M + 1 0.0 [ 0, 1 ) 0 1 1.0 [ 0, N ) 0 N 1.0 [ M, N ) M N – M + 1 1.0

# Generating values of normal distribution – Marsaglia method

Assuming you can already produce variables of uniform distribution, you can produce variables of normal distribution using various formulas. Two of the most important are:

Most methods are based on Box-Muller method.

The Marsaglia method is my favorite since it does not require using sin() or cos() functions and the steps are very easy to implement.

Here is a sequence of the steps:

1. Generate a value that follows uniform distribution in any space you want (eg: [ 0 , 1 ))
2. Map that value to space (-1, +1) and assign it to variable U
3. Repeat steps 1 and 2 and assign the result to variable V
4. Calculate S = U*U + V*V
5. if S = 0 or S >= 1 then free all variables if needed and restart from the beginning
6. The following two variables will be independent and standard normally distributed (mean = 0, variance = 1):

Optionally you can add m to the quantities above to change the mean value of the distribution.

# Distance between point and rectangular box without case logic

Assuming you have a point (x,y) and a rectangle parallel to x and y axis defined by its upper left and lower right corner. How can we calculate its distance without using case logic?

P = (x,y)
A = { (x1,y1), (x2,y2) }

``````dx = max(A.x1 - p.x, 0, p.x - A.x2)
dy = max(A.y1 - p.y, 0, p.y - A.y2)
distance = sqrt(dx*dx + dy*dy)
``````

Its very tricky.

Here is a great analysis here by MultiRRomero:

http://stackoverflow.com/questions/5254838/calculating-distance-between-a-point-and-a-rectangular-box-nearest-point

# Determine if two rectangles intersect without case logic

Assuming you have two rectangles A and B that exist parallel to the x and y axis and are defined by their upper left (x1,x2) and lower right corners (x2,y2). How can you calculate if A and B intersect without using case logic?

A = { (x1,y1), (x2,y2) }
B = { (x1,y1), (x2,y2) }

``````if (A.x1 < B.x2 &&
A.x2 > B.x1 &&
A.y1 < B.y2 &&
A.y2 > B.y1) {
then A and B intersect
}
``````

There is a great analysis here:

http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other

And an awesome interactive visualization by Matthew Crumley here:

https://silentmatt.com/rectangle-intersection/

# Frequently used Unicode math operators

This is a selection of the operators i use frequently while taking notes. You can find a detailed table on wikipedia.

You can find ways to type the symbols here and a complete PDF for math operators here

##### Predicate logic
 existential quantification U+2203 ∃ U+2204 ∄ universal quantification U+2200 ∀ logical conjunction logical disjunction U+2227 U+2228 ∧ ∨ material implication implication U+21D2 U+2192 ⇒ → material equivalence U+21D4 ⇔ negation U+00AC ¬ entails provable from U+22A8 U+22A2 ⊨ ⊢

#### sets

 proper subset U+2282 U+2283 ⊂ ⊃ U+2284 U+2285 ⊄ ⊅ subset U+2286 U+2287 ⊆ ⊇ U+2288 U+2289 ⊈ ⊉ element of U+2208 U+220B ∈ ∋ U+2209 U+220C ∉ ∌ empty set U+2205 ∅ intersection union U+22C2 U+22C3 ⋂ ⋃ cross product U+2a2f ⨯

Here are some Copy-Q tabs to use:

1. With set operators here
2. With logic operators here