Introduction
Two basic rules:
Rule of sum: if an action is performed making A choices or B choices, then it can be performed ways.
Rule of product: If an action can be performed by making A choices followed by B choices, then it can be performed ways.
Permutation: an ordered list where every object appears exactly once
combinations: When order is not important and the repetition is not allowed, the number of ways to choose k from the distinct n is as for :
in general, choosing k
out of n
is same as not choose nk
out of n
.
According to the Pascal’s Triangle:
Again from the pascal triangle:

ordered 
repeating 
sequence 

yes 
Permutation 

yes 
Multisubset 

no 
combination 
or 
no 
It is sufficent to implement .: the programming construct is recursion because .
12 fold way
Here D  distinct and I  identical. In the following table, if then all the values of the at most are zeros. if , then all the values of the at least are zeros.
A 
B 
any 
at most 
at least 
D 
D 



I 
D 



D 
I 

1 if else 0 

I 
I 

1 if else 0 

In the above table, Stirling numbers of the second kind count the number of ways to partition a set of a
elements into b
nonempty subsets. Stirling numbers of the first kind count permutations of a
objects with exactly b cycles.
In the above table, is the number of ways to partition the number a
as the sum of b
positive numbers since the order don’t matter. For :
Multichoosing is the number of ways to choose k
objects from a set of n
objects where order is not important but repetition is allowed.
Simplification,
Multinomial theorem where
Principle of InclusionExclusion
Formula for the sterling number:
Java
There are two choices for the intermediate represetiation
 portable machine language
 graph based
Initially Java was created only with byte code interpreter. But current Java has Just In Time (JIT) compiler.
There are two popular representations:
 Stack based  0 operand
 Register based  3 operand
Java uses Stack based representation.
If you consider the for single loop in Java
for (int i =0; i < N; i++){
...
}
The running time cost of the above loop is means linear. The running time cost of the double loop is quadratic. Triple loop running time is cubic.The worst running time can be something like exponential.
Order of the Growth
Fortunately there are limited models to consider. Here the growth from best running time to worst:
 (Knuth shuffle)
 (Mergesort, QuickSort)
 (selection =, insertion = 1/4 )
Each instance of the java.util.ArrayList has the capacity, when reach to the capacity, the array need to be increased. Assume, each time ArrayList is double when it reach to the capacity then the equation is
This is because ArrayList is using java array of Object as a implementation. Advantages are that every operation takes constant time of Amortised time( Average running time per operation over the worst case sequence of operations) and less wasted space compared to linked list implementation because linked list is based on object.
Sorting
There java.lang.Comparable<T>
and java.util.Comparator<T>
is based on the total order which is a binary relation that satisfy:
 Antisymmetry: if and , then
 Transitivity: if and , then
 Totality: either or or both
Quicksort is little bit faster than Mergesort because Quicksort doesn’t exchange the elements always. However, quick sort wort case running time is quadratic () and average case is . Quciksort random shuffle is the probabilistic guarantee to avoid worst case.
The java.utils.Arrays sort() method is using Quicksort for the primitives and Mergesort for the objects.
Dijkstart 3way partitioning is the way to compromise with the duplicate keys because lower bound is reduced linearithmic to linear for most of the applications as follows:
Algorithm 
Worst 
Average 
Best 
Remarks 
selection 



N exchanges 
insertions 



small N or partially 
shell 
? 
? 
N 
tight code 
merge 



guaranteed 
quick 



probabilistic guarantee 
3way quick 



support duplicate keys 
Heapsort 



Inplace algo. Inner loop is longer than quicksort. Poor use of cache memory. Not stable. 





Searching
Binary Search Tree (BST) is a binary tree(BT) in symmetric order. BT can be either empty or two disjoint binary trees at left and right(left/right nodes can be null).
In the BST every node has a key:
 Larger than all keys in its left subtree
 smaller than all keys in its right subtree
For the N number of distinct values in random order, the number of comparisons are .
RedBlack trees
The java.util.TreeMap
is based on the Redblack tree. Here some of the characteristics of the RedBlack tree:
 Represents 23 tree as
 use internal leftleaning link to glue three nodes which is red link
 no node has two red links
 every path from root to null link there are same number of black links.
Appendix
quadratic
logarithmic ( is called linearithmic)
cubic ( is called quadratic)