BTree Algorithms

If t is minimum degree  of B tree

For nodes other than root
Minimum number of keys
Every node other than root must have atleast t-1 keys 
so every internal node must have at  least t childrens



 Maximum number of keys
every node can contain at most 2t-1 keys
therefore internal node can have at most 2t children

For root

For Non empty tree root should have at least 1 children

Height of B Tree
Height of Btree is function of total number of keys in Btree

number of nodes at depth 1 has to be >=2 So we have atleast 2 nodes at depth 1
next level would have t nodes for each node in level 1 so t*2
depth 3 t^2*2
for depth h  it has at least t^h-1 * 2
Each node has t-1 number of keys 
so the tree has at least 1+ (t-1) * {sum i to h}2t^i-1    keys
n >= 1+ (t-1) * {sum i to h}2t^i-1
n>=2t^h -1
h <= log(t, (n+1)/2)

Operations on Btree
n(x)+1 way branching decision since there are n+1 different choices to follow
Searching
Search (x,k)
find the smallest index such that k < key[xi]  //from left find the position which is just greater than k
if its the key k then return the index and node
else
if its leaf then return NIL         //failed search
 else
        Disk-Read(ci[x])           // bring the new children in memory and 
      Search(ci[x],k)                  //search child

Performance
Children is brought in memory  if key not found in present node
number of disk pages accessed is height of tree  Th(h) = Th(log(t,n))
searching the index at each node takes O(t)
so total time = O(ht) =O(t log(t,n)) that is for each disk read we have to search that nodes keys

Create Empty Btree
Create Root
B-Tree -Create(T)
allocate a disk page  x //O(1)
set it as leaf and number of keys n[x]= 0
write it back to disk
assign it as root root(T)=x
O(1) disk operations and O(1) CPU time

Insert Key
New key has to be inserted such that it maintains the B tree property of min and max nodes

If leaf y is full then it contains all 2t-1 key, that is, maximum allowed and we
split the node y around its median key key[y] into two nodes having t-1 keys each
move y to parent to identify dividing point
If y's parent is full then it must be splited too

We can insert the key on pass from root to leaf node
Travel down the tree searching for the position where the new key belongs and split each full node we come along the way including the leaf 

Insert(T,k)
If root is full that is it has 2t-1 keys then
  s= allocate-node() //make new node s as root
  set r as child of s
  split child (s,1,r)    //
  Insert-Nonfull(s,k)  //insert key k in non full node s
else
 Insert Nonfull(r,k)

Performance : O(th) time and disk access =O(h)

B tree increases in height at top not at bottom unlike binary tree

Insert-Nonfull(x,k)
i =n[x]
If x is leaf node then  // that is we have only root and its not full

  while k < keyi[x]       //traversing  from right key
          key(i+1)=key(i)         // move the key to right
             i=i-1
   key(i+1)[x] =k           //store the key at position i+1
   Disk Write(x)
Else  //when not leaf
  loop to find right index in x to search which children
  Disk-Read(ci[x]) //read that children in memory
  If the children is full
   Split-Tree(x,i,c[x])
   if k > keyi[x]
     traverse i+1
Insert-Nonfull(ci[x],k)

Performance
There are O(1) disk read and write operations on each recursion so total O(h)
CPU time O(th)
tail recursion so can be converted into while loop and allowing number of block in memory O(1)




Split Node
inputs :   x non full node. child of x, y, is full
output : will split child y and adjusts x to have additional child

Height of tree increases by one on split of root

Its the only operation which increases the height

Split(x,i,y)
y is ith child of x
divides child y into y and z,

z = allocate-node()            // to have last t-1 keys that is,  larger t-1 keys
for index j to t-1
 change key position       // what was j+t key in y will be now jth key in z
if node y is not leaf then
 change child positions for z //what is j+t child in y is jth child of z
similarly move the index position and key for x to make space for
median[y]
key[xi] = key[yt]
and n[x] = n[x] + 1

Disk-Write(y,z,x)

Performance
O(t) time  to change the children and keys of x and z
and O(1) disk operation

Deletion
Deletion from an internal node requires that nodes be rearranged that is when  interal node has minimum number of keys

Btree-Delete deletes the key k from the subtree rooted at x.
guarantees that whenever procedure is called recursively on node x, the number of keys is at least t that is 1 more than required to satisfy B tree property
allows to delete a key from the tree in one pass without back up

Procedure
preceding child is the left child
predecessor of key is the largest key in its left child
1)If  key k is in node which is leaf then delete key k from x
2)If key k is in internal node x then
 i) if child y that precedes x has at least t keys then find the predecessor k' of k in the subtree rooted at y.
   Recursively delete k' and replace k by k' in x
 ii)If child z that follows k in the node x has atleast t keys then find successor k' of k in subtree rooted at z
iii)If both y and z have only t-1 keys then merge k and all of z in to y so that now


B+ tree
order of m : internal node can contain m-1 keys

Deletion
We always delete key from leaf
If key is in index also we delete from there also

Redistribution of leaf node:
middle key is copied up and sibling is borrowed
if sibling has atleast t/2 keys than we can redistribute the sibling (same parent as L)
Key is deleted from leaf and a key is borrowed from sibling inserted into L and a common parent is changed to middle key that is if
             k |  l  |  m |   
            /   \     \      \
          /       \     \      \
      a  b     c d e
delete a 
key a is in node L(a,b)
and if we delete a and t -1 = 2 that is fill factor is 2 then
1)we can borrow a key c from sibling
2) we have to replace k also with the middle key after sorting these two sibling that is d
so we move d to parent

             d |  l  |  m |   

            /   \     \      \

          /       \     \      \

      a  c      d e

Merging 
toss parent index entry and pull down index's parent if index deficient
If the sibling do not have sufficient node then we merge L with its sibling

          q
        /    \
   o  p    d |  l  |   

 /  |  |     /   \     \     
          /       \     \   
      a  c      d e

delete c
key c is in L (a,c)
since siblings do not have sufficient keys we merge L and sibling (d e)
and delete the parent d but that would make parent node l deficient so we need to merge index page also
we pull down  parent of l, q down that is
          q

        /    \

   o  p      l     

 /  |  |     /   \          
          /       \      
      a d e

               

   o  p q  l     

 /  |  |     /   \          
          /       \      
      a d e



Redistribution in Non leaf node

         q

        /    \

r  o  p      l     

 /  |  |     /   \          
       t   /       \      
      a d e


here we can move p to position of q and q with l
right child of  p will become left child of new position of q
          p

        /    \

r  o       q  l     

/  |        /   \          
          /       \      
         t        a d e



1)If index page and leaf page are not below fill factor
delete record from leaf page Arrange keys in ascending order to fill void
If key appears in the index page use next key to replace it
First check left then right for merging

2)If leaf page is below fill and index page not then
combine leaf page and its siblings
Change index page to reflect change
3)If both index and leaf are below fill then
Combine leaf and siblings
Adjust index page
Combine index with its siblings

Problem 

If we delete 60 in above  case from node 60 65 we will have less than 2(fill factor) in the node so we must merge this node with left node 50 55 and also we have to delete its index 75 But deleting index

Merging of leaf pages reduces the index entry by one

will result in less than fill factor for parent 85 so index pages need to be merged Since 60 is the only key and merging reduces the key so we need to delete the root

 Problem

 Deleting 25 from 25 28 30 leaves number of keys above fill factor so we delete 25 from leaf and we need to delete corresponding key also and fill that position in parent with key next to 25 that is 28

 If it had been 25 alone in that node we would have deleted that node and also 25 from parent and set left of parent 25 to left of 50

Problem

Delete 6 from above tree
Deleting 6 we need to delete from index also which would leave index below fill factor so we need to merge index pages


avid.cs.umass.edu/courses/445/f2008/17-tree-indexes-2.pdf

Graph Algorithms

Minimum Spanning Tree

Problem definition
In a weighted connected graph G(V,E,W) Find tree T that contains all the vertices in G and minimizes the sum of weight of all edges
Greedy approach to find minimum spanning tree,at each step one of the several possible choices is made that best choice

Safe edge is one that can be added to  subset of edges of minimum spanning tree A without violating the condition
A cut is any partition of V
If no edge in A crosses the cut then it respects the cut
An edge is light edge crossing the cut if its weight is minimum of any edge crossing the cut

Theorem In graph G if we partition set V into S and V-S and A is subset of edges of minimum spanning tree then a light edge {u,v} can be added to set A safely that is AU{u,v} is also subset of MST
If  edge u,v is not part of MST then there must be some other edge (xy) connecting the two partitions V  and V-S so if we add edge uv to it, it should create cycle but we have uv as light edge so
w(uv)<=w(xy)
so we have MST with uv also
But if all edges have distinct weights we cannot have this condition and only edge {u,v} can be part of MST

Generic- MST : Find a safe edge and add it to A to form MST

Kruskal algorithm
greedy algorithm because at each step adds the least possible weight edge to A.
set A in case of Kruskal algorithm is forest
It finds a safe edge to add to the growing forest by finding edge {u,v} of least weight that connects any two trees in forest

Kruskal algorithm
Kruskal(G,w)

For each vertex v in V(G)
  make-set(v)   //O(V)
sort the edges of G in nondecreasing order by weight   //greedy approach to take minimum weight
For each edge E{u,v} in the sorted list
if both endpoints do not belong to same tree then  //if belongs to same tree then we would have cycle
If Find-Set(u)  != Find-Set(v)          //O(E) for each edge
 then A =A U {u,v} // add edge E to set A
 Union(u,v)

we used disjoint set data structure to implement it

Running time
depends on the disjoint set operations
time to sort the edges takes (E log E)
creating a disjoint set of vertices that is that many number of distinct trees initially and the main loop to process each edge takes O(E+V)a(V), but since G is connected graph E >= V-1 and so it becomes O(E)a(V) (a takes into count the union at last when vertices are added to tree) where a(V) is (log V) = O(log E)
Total running time is O(E log E) also |e|<=|v|^2  so log E = O(log V) and we can also state running time as
O(E log V)


Prim Algorithm
also example greedy algorithm 
edges in the set A forms Tree that is it works by adding edges to a set A
operates like Dijkstra algorithm
It gradually creates a minimum tree that spans all the verties
At each step light edge is added to tree A that connects A to an isolated vertex
key concern is how to select
min priority queue is used to hold vertices not in tree A based on key field .For each vertex v, key[v] is the minimum weight of any edge connecting v to a vertex in the tree

Prim Algorithm
r is the starting vertex
At each step we update the adjacent veritces weight so that when we call extract-min on priority queue we get the light edge that is minimum weight edge
Prim(G,w,r)
for each vertex add set the key field to infinity and parent field to null except for the vertex r for which key field is set 0
set the min priority queue with this information
while queue is no empty
  u =  extract-min (Q)            // we process vertex in order on min key in Q
  for each edge v adjacent to u
   if v is in the priority queue and weight w(u,v) < key[v]  
    update the key and parent for vertex u

For every vertex v in Q, key[v] is the minimum weight of any edge connecting v to a vertex in the tree
Q will have non infinite key for those vertexes whose adjacent vertex has been processed or in other words we determine the cut of the graph and light edge is added to the set A.
set A and Q forms disjoint sets of cut.


Loop invariants
set A contains V-Q that is vertices processed and removed from queue
for all vertices in queue if parent is not null then key of vertie

Running time of prim algorithm
depends on how min priority queue is implemented
1)If binary min heap is used
we use build min heap to create vertex with key and parent fields it will takes O(V) time
 Extract min takes O(log V)  //when selecting the vertex in queue
and is called V times that is for each vertex  so extract min takes total of O(V logV)
Decrease key on binary heap = O(log V)  // when updating the key of adjacent vertices
and is called for all the adjacent vertices of v
sum of lenght of all adjacency list is 2|E| so decrease key is called O(E logV)
total time is O(V log V + E log V )
when graph is sparse we have e << v^2 and e = Th(v) so cost is O(V log V)
when graph is dense we have e ~= v^2, so cost is O(V^2 log V)
2)using fibonaci heap
extract min can be performed in O(log V)
and decrease key can be performed in O(1)
so total time is (VlogV+E)
for sparse we have e=Th(v) so  cost is O(VlogV)
for dense we have e ~= v^2 so cost is O(V^2)
3)using adjacency matrix
scans the list to find the smallest key   O(V)
 for each vertex update its adjacent vertex weight   //O(deg(u))
total cost is {sum over all vertices} O(V + deg[u])
so  total cost is O(V^2 + E) =O(V^2)

Negative edges in Kruskal and Prim algorithm
Negative edges does not affects the kruskal algorithm Both works correctly as should be
Light edge donot distinguish negative and positive edges

Shortest Path Problem

There is only one minimum spanning tree but in general there is different shortest path for each source

Optimal structure
each subpath of shortest path is shortest path

Cycle in graph
negative weight edges
there may be negative weight edges
If G contains no negative weight edges then shortest path weight remains well defined for all sources s
If there is negative weight cycle reachable from s then shortest path are not well defined
If there is negative weight cycle on some path from s to v then shortest path weight d(s,v) = -infinity

If vertex v is not reachable from s than d(s,v) = + infinity

Dijkstra algorithm requires no negative weight edge in the input
Bellman Ford algorithm allows negative  weight edge in input graph and produces correct answer as long as no negative weight cycles are reachable from source. It can detect the negative weight edge cycles and reprot there existence

Shortest path cannot contain negative edge cycles and also not positive weight edge cycles
zero weight edge cycle it can be on the shortest path but then we can also go via another path instead of zero cycle
So we will consider shortest path only for v-1 edges that is without any cycle

Relaxation step
Relax(u,v,w)  //relax edge {uv} having weight w
we update the distance on the vertex v like
if d(v) > d(u) +w(uv)
then update d(v) with d(u) + w(uv)

Each algorithm differs in how many times and in which order they relax edges.
Dijkstra algorithm relaxes each edge exactly once
In Bellman ford each edge is relaxed many times

Bellmand Ford Algorithm
solves single source shortest path in weighted directed graph G(V,E)
negative weight edges allowed
detects reachable negative weight edge cycles
algorithm returns boolean value indicating whether or not negative weight edge cycle exist If such cycle exists the algorithm indicates there is no solution If there is no cycle it  produces shortest path and weight

algorithm return TRUE if and only if the graph contains no negative weight cycle reachable from source s

Bellman-Ford(G,w,s)
Initialize(G,s )  //initializes the d(v) for each vertex to infinity and path s to zero
for i =1 to |V|-1  //remaining vertices other than source
  for each edge (u,v) in E(G)  //each pass relaxes each of the edge of the graph so |v-1|*|E| relaxation
    Relax(u,v,w)
for each edge (u,v) in E(G)   //check negative weight cycle
 check if d(v) > d(u) + w(u,v) 
    return FALSE              //if negative weight cycle exist
return TRUE

Running Time
Initialization takes O(V)
we relax each edge for each vertex that is O(VE)
check for negative cycle takes O(E)
total running time is O(VE)

For proving the correctness of the bellman ford we need to prove that each vertex v has shortest distance from s that is for each vertex v d[v]=shortest distance from s

Observations
does not always returns shortest path from s to t in all the graphs, when graph have negative weight cycle
If graph has all distinct vertices then shortest path between two vertices may not be unique, same weight path possible


Dijkstra algorithm
single source shortest path on directed weighted graph
no negative edges allowed
example of greedy algorithm
greedy algorithms doesnot always yields optimal result but in case of Dijkstra it return optimal weight path 
maintains set S of vertices whose final shortest path weight from source have already been determined
select vertex u whith minimum path estimate from remaining vertices and adds it to S and relaxes all edges leaving u

Dijkstra (G,w,s)
Initialize all vertices to infinity distance
build a min priority queue from vertex set V[G] //Q would always contain V-S
while priority queue is not empty    //runs for |V| times
 u = extract-min(Q)
 add u to S
 for each vertex v adjacent to u
  relax(u,v,w)

Running Time of Dijkstra
maintains min prioity queue by calling three operations
Insert(build heap) ,Extract-min(G) and Decrease-Key(Relax)
1)we take advantage of the vertices being numbered 1 to |V|-1
we can perform Insert and Decrease-key in O(1) and extract min in O(V) time
total running time O(V^2+E) = O(V^2)
2)If graph is sparse that is E =o(V^2/log V) we implement it using binary min heap
build heap O(V)
extract min O(log V) and there are V such extract so O(V log V)
Decrease key O(log V) , number of decrease key is of O(E) so total  O(ElogV)
Total running time = O((V+E)log V) = O(E log V)
3)with fibonacci heap we can achieve (V logV+E)

Observations
Dijkstra algorithm relaxes each edges only once
example when Dijkstra algorithm does not works
here we start from A relax edge AB and AC
B gets labeled (5,A) and C(10,A) So we choose B and relax edge BD, D gets new label (6,B)
D is processed then C is chosen and edge CB is relaxed and B gets new label (3,C)
D has label (6,B) while D should have been (4,B)

All pair Shortest Path

Breadth First Search
for searching graph
given graph G and source s BFS explores the edges of G to discover every vertex that is reachable from s
It computes the smallest number of edges from s
explores all vertices at distnace k from s before moving to k+1 vertices

To keep track of progress, colors each vertex white gray or black.
not processed white
when first encountered it becomes non white
three color for vertices
white -- not discovered yet
gray discovered but not processed
black all the adjacent vertices discovered and grayed


all vertices adjacent to black are discovered vertices
vertices adjacent to gray may not be discovered

constructs a breadth first tree initially containing only its root

FIFO queue used to process vertices in order in which they are discovered

BFS(G,s)
color each vertex white initially , their distance infinity
color sources s as gray that is processing starts with s
enqueue s
for each vertex in queue
u = dequeue(Q)
for each adjacent vertex v of u
if its not discovered yet that is color ==white
color it gray
increase weight by one d(v) = d(u)+1
enqueue(Q, u)
color v black that is all its adj have been discovered

Queue Q always consists of gray vertices


Running time
aggregate analysis
Enqueue and Dequeue O(1) time
each vertex is enqueued and dequeued once giving O(V)
since sum of lenght of all adjacency list is Th(E)
total time scanning adjacency list is O(E)

total running time of BFS is O(V+E)

breadth first search shortest path, that is, minimum number of edges or weight of 1 on each edge, for each vertex
if it is reachable else infinity

DFS
edges are explored out of most recently discovered vertex
when all edge o v has been discovered search backtracks to explore edges leaving the vertex from which v was discovered
predecessor graph of DFS may be composed of several trees unlike that or BFS

like BFS vertices are colored to indicate their state
white initially grayed when discovered and black when finished

DFS(G)
initialize each vertex color to white
time =0
for each vertex in V[G]
if we have white colored vertex call DFS-VISIT(u)

DFS-VISIT(u)
set color of u to gray indicating its discovered
time = time+1
d[u] =time // time when vertex u is discovered
for each vertex v adjacent to u
if it is white colored
then call DFS-VISIT(v)
set color of u to black indicating all adjacent discovered
f[u] = time+1 //when the search or u adjacent vertices finished


Running time
since DFSVISIT is called exactly once for each vertex it takes O(V) time
scanning adjacency list O(E)
total O(V+E)

properties of DFS
vertex v is a decendant of vertex u in the depth first forest if and only if v is discovered during the time in which u is gray

discovery and finishing time have discovery structure
parenthesis theorem
that either interval [d[u],[u]] and [d[v],f[v]] are entirely disjoint or one is completely contained in other


vertex v is proper decendant of vertex u in the depth first forest for a graph G if and only if
d[u] <> j & not edge of graph








 Problem Remove cycles from graph O(k) cycles 
Solution When traversing the graph check whether edge trying to relax goes to node that has been seen but not finished that is gray colored vertex then this is back edge and we can save all such edges and at last remove them It will take time of DFS algo that is O(V+E)


 Observation
DFS-VISIT if runs on BST it would return the smallest element as its first node and root as its last
Only in case of DFS does absence of back edges ensures acyclic graph not in case of BFS
BFS finds path using fewest number of edges the BFS depth of any vertex is at least as small as DFS depth of the same vertex Thus DFS tree has greater or equal depth that is if maximum distance between two vertices is T edges then in BFS depth is at most T but depth of DFS might be larger,DFS may have depth up to V-1 like in case of complete graph
If adjacency matrix is used instead of adjacency list in BFS it would run in O(V^2) instead of O(V+E)



dynamic programming solution
characterize structure of optimal solutiom
recursively define value of optimal soluion
computer in bottom up


Optimal sub structure
subpath of shotest path are also shortest paths
that is if p is shortest path from i to j then
d(i,j) = d(i,k)+w(i,k)

Recursive solution
let l^m(i,j) be minimum weight of any path from i to j with at most m edges
when m =0
l^m(i,j) = 0 if i=j
= infinity if i<>j
for m >= 1
we compute l

Sorting

Quicksort

Divide and Conquer algorithm for sorting A[p .. r]
practically runs on average case Th(n lg n) and very small hidden constant factor
in place sorting algorithm
not stable
widely used and considered best for use

Divide: choose middle element such that all elements to right are greater and to left are smaller
Conquer sort the left and right subarray recursively
Combine once subarrays are sorted in place the list is in sorted order.

Divide
main job in divide step is to get the pivot element to right of which elements are greater and left elements smaller
Partition(A,p,r)
Pivot choice: we choose last element as pivot x=A[r]
we maintain 4 partitions
first partition keeps elements no greater than x
second keeps elements greater than x
third partition is for unprocessed elements
fourth partition is the x, pivot

j is used to process each element from p to r-1
we are interested in this three conditions
first partition(index p to i) will have all the elements <= x
second partition (index i+1 to j) will have all elements > x
and third will have x

Partition(A,p,r) Algorithm
get the last element as pivot x
set i to p-1
for each element j from  p to r-1
if current elment A[j] <= pivot x
  //then it belongs to first partition replace first element in partition 2 with this element
  i=i+1     //points to first element in second partition
  exchange A[i] to A[j]  // exchange with this current element
  // for first element is less than x than we exchange it with itself because of conditions above
At last we replace the  first index in second partition with pivot to get pivot in middle of two subarray

Running time of partition algorithm is O(n) because we parse all n-1  elements and perform some constant time operations

Performance of Quicksort

running time depends on whether partitioning is balanced or unbalanced
If balanced partition it behaves like merge sort
If unbalanced partition them as slow as insertion sort (O(n^2))

Worst case partitioning
when sub problem is divided in to size n-1 and 0
assuming same unbalanced partition at each level
T(n) = T(n-1) + T(0) + Th(n)  //Th(n) for partition
Tn =Th(n^2)

This case occurs when list is already sorted, in which insertion gives time of O(n).

Best-case Partitioning
when partition divides list even size, that is, floor(n/2) and n/2-1
T(n) <= 2T(n/2) + Th(n)
T(n) =O(nlogn)

Average case
whenever partition yields constant proportionality we get the running time of O(nlogn)

Space complexity (O(lg n) in the worst case can be achieved)
Partitioning is in place O(1)
After partition element are sorted requiring recursive call taking most O(lg n) space

Selection based pivoting

selection algorithms can be used to choose best pivot to partition list
selection algorithm worst case is O(n) so we can use it to find best pivot at each stage and get worst case of O(nlogn) but this variant is slower compared to normal in average case

Problem Show that minimum depth of a leaf in recursion tree of quicksort split of 1-a and a (0<=1/2) is
-lg n/log a and max is -lg n/lg 1-a
Solution we have to look for path which is largest or has maximum depth
splits of larger size takes more number of further splits to reduce to base case so 1- a side split should have more depth because a < 1-a
at each level number of elements n is reduced by a that is (1-a)^i*n at i level
for leaf (1-a)^i*n =1
(1-a)^i =1/n
i lg (1-a) = -lg n
i = -lg n /lg(1-a)

similarly for the minimum depth we look for a splits
a^i*n=1
i=-lg n/lg a

Problem What happens in case of all duplicates in list for above algorithm
Solution we look at the partition algorithm, what happens in case of same values of pivot and current element j

if A[j] <=x then we swap that with first element in second partition i+1 index
this happens for all the elements giving at last, same list as original with pivot at original position only and i and j pointing to index before r.
so it divides the list in n-1 and 0, worst case scenario of quicksort

Problem Show that running time of quicksort can be improved by taking advantage of insertion sort fast running time for nearly sorted list, running time O(nk + nlg(n/k)) when  insertion sort is called when subarray size is<=k
Solution
recursion stops when n/2^i =k  that is i=lg n/k
recursion takes in total O(n log n/k)
n is cost of each level and log n/k is depth of level
The resulting array is composed of k subarray of size n/k elements in each subarray are less than elements in the following subarray Insertion sort call on sublist of size k take Th(k^2) for worst case to sort n/k such list would take  n/k*Th(k^2) = Th(nk)
O(nk + nlog n/k)
k should be chosen such that no bigger than lg n

Expected Running time

Merge Sort
also example of divide and conquer algorithms
Divide: list of elements is divided equally in two sublists of size n/2
Conquer: Sort the two sub list recursively
Combine: Merge the two sorted sublist to get the final sorted list

In case of quicksort we did actual work in Divide step to find the pivot with partition procedure here we do most of work in combine step to merge two sorted lists

Merge(A,p,q,r)
merge sorted subarray A[p ..q] and A[q+1 ..r] and give single list of sorted sequence
In merge procedure we compare the first elements of each list and check for smallest between two then place that in new list similarly we check until one of the list goes empty at that point we just add the remaining elements in other list to final list
we can see the number of comparison when list1 is of length L1 and list2 of length L2 can be at most L1+L2-1
so we can say for merge procedure time complexity should be Th(n) where L1=L2~=n/2

In case of Merge procedure we include sentinel element at end which makes the comparisons uniform without need to check for empty list separately
The number of comparisons in this case would be equal to L1+L2, that is n in case of Merge procedure


Merge(A,p,q,r) Algorithm
create two arrays from element of A like L[p ...q-p+1] and L[r-q+1]

//with size one greater to include sentinel element(very large number in this case,say infinity)

//we merge the two list L and R in our original list A

 //parse the two list L and R with index i and j respectively

for each position k in list A[p ...r] 

// we know that in total we have to place r-p+1 elements and at each step we would insert one element in list //A, not necessarily in its correct position as in sorted sequence

if L[i] <= R[j]  //compare current element in each list
  A[k] = L[i]  // at each step A gets the small of the two lists
  i=i+1  //compare the next element in list L with current in R
else
A[k] = R[j]
j=j+1


At start iteration k of the loop Array A contains elements from index p to k-1 as smallest of the two list L and R that is k-p elements

Running time of Merge Procedure
populating the list L and R takes time Th(n1+n2) =Th(n)
looping for each index in A takes time Th(n)
so total running time is Th(n)

Merge sort Algorithm
Merge-sort(A,p,r)
if p < r // when p>=r there is single element and its already sorted
find middle index q = floor(p+r/2)
Merge-sort(A,p,q)
Merge-sort(A,q+1,r)
Merge(A,p,q,r)

Running time of Merge sort
Divide step takes Th(1) time, finding the middle index
Conquer step if T(n) be time for complete sorting of n elements than conquer step would take 2T(n/2)
Combine step is Merge procedure which takes Th(n)
T(n) = 2T(n/2) + Th(n)
T(1) = Th(1)

T(n)= Th(n lg n)

Insertion sort

in place sorting algorithm
stable sorting
efficient algorithm for sorting small number of elements
Insertion-sort(A)
take each element in array A and find its correct position in elements before it
two partitions of the set
first partition contains sorted list of elements processed so far
second partition is elements not processed yet

At each step first partition contains sorted list of elements processed so far

Algorithm
for each elements from index 2 to length[A]
k=A[j]  //call current element key
//no insert this element in to its correct position in A[1] to A[j-1]
i = j-1
while i>0 and A[i] >key  // for each element greater than key shift it one position to right
  A[i+1] = A[i]
  i=i-1
when we find i such that  A[i] < key
we insert out key in position after that
A[i+1] = key

Running time of Insertion Sort
Worst case when we need to shift all elements at left by one position this case occurs when A[j] is less than all the elements in the first partition, this is case of list in decreasing order
O(n^2)

Average case
Average case time is also O(n^2)
but fastest algorithm for sorting small arrays

Best Case
array that is already sorted
during each iteration A[j] is compared with only its left element which is smaller than key so inner loop only runs once for each j
Th(n)

Selection sort

Selection-sort(A, p, r) // p: starting index; r: ending index
if p < r       
  then largest =  p  // call first element largest
  for i  =  p+1 to r   // linear search to find largest
 do if A[i] >= A[largest]
       then largest  = i

Exchange A[r] and A[largest]
selection-sort(A, p, r-1);

Divide: Select the largest element in the array, and then swap the largest element
and the last element. The selection process uses a linear search. Thus, the divide step
takes linear time.

Conquer: Sort the the first n − 1 elements recursively. This step takes T (n − 1) time.

Combine: Do nothing.

 Recurrence: T (n) = T (n − 1) + n

Median and order statistics

Heap Datastructure and Algorithms

 Heap Sort

•  running time is o(nlogn)
•  in place sorting algorithm unlike merge sort
•  not stable sort
•  uses max heap, largest element is first element in array and smallest element is in one of leaf nodes

Heap datastructure

•  nearly complete binary tree, completely filled on all level except possibly lowest which is filled from left to right
• Number of elements in heap of height should be between 2^h and 2^(h+1)-1  or 
• height of n element heap = ceil[logn] from above equation
•  since its almost complete binary tree parent child relation can be found in array with simple calculations like parent(i) = floor(i/2) , left(i) = 2i and right(i) = 2i+1

Type of binary heap

max heap, every node i has A[parent(i)] >= A[i]
and min heap, every node i has A[parent(i)] <= A[i]

Operations on heap data structure

Max-Heapify(A,i)-----log(n)

also called percolate down
Given a tree that is heap except for node i, arranges node i and its subtree
assumes that binary tree rooted at left(i) and right(i) are max heap
 A[i] is placed at its right position
Algorithm
at each step find largest of A[i] A[left(i)] A[right(i)] and store it in largest
If A[i] is largest no need to go further
Else swap the A[larger] with A[i] and call max heapify on (A,larger)

Analysis
The worst case of max heapify occurs when last level is half full
Find relation between level and total number of nodes n for worst case scenario
elements up to i-1 level = 2^0 + 2^1 + ....2^i-1 = 2ⁱ -1
elements at last level = 2^i /2
Total number of nodes = (2^0 + 2^1 + ....2^i-1) + 2^i/2
2ⁱ + 2^i-1 = n+1
2^i-1(2+1)=n+1;
2^i-1=(n+1)/3

Max subtree size = (half of all elements up to level i-1) + (elements at the last level)  – (1 root element) =
Max subtree size = (2^i - 1)/2 + 2^(i-1) - 1
substituting value from above equation
we get  total number of nodes  ~( 2n/3)


Recurrence relation 
Time to run max heapify = time to fix immediate child heap property and to call max heapify on subtree
worst case when subtree is of size 2n/3 Therefore
T(n) <= T(2n/3) +Th(1)
solution to this recurrence is O(logn)
When max heapify is called on node of height h its running time is O(h)

Build Heap -----O(n)

already have all the elements in array, build heap from that
In the array representation for storing n element heap leaves are indexed by
floor(n/2)+1, floor(n/2)+2 ....n that is there are ceil(n/2) leaves
we call max heapify for each node starting from last parent element

Algorithm 

Build Max Heap (A, n)
     for each element from floor(n/2) down to first
           Max-Heapify(A,i)

Analysis
Relaxed Upper bound  Each max heapify takes time log n and there are almost n calls so O(nlogn)
Tight upper bound Since max heapify takes time proportional to height of node on which its called and that varies for each call to it in above loo.
total cost = sum over all height(0 to h){ (number of nodes at height x) O(x)}
which comes out to be O(n)
when root node contains smallest value it will be swapped with every node at each iteration

number of nodes at height < =  ceil(n/2^(h+1))
we know that node at height h takes log h time for maxheapify
total cost = sum over all height(0 to h){ (number of nodes at height x) O(x)}
Cost of heapifying all = {sum o to log n}(n/2^(h+1)* O(h)) ~= O(n)

height and level of tree difference 

level of tree is calculated as distance from root
height of tree is calculated as distance from leaf
height of tree might not be same for node at some level or depth this could be the case in case of not complete binary tree.
max height of heap is floor(log n)


Heap Sort 
first we build the max heap using previous algorithm
since first element is the largest element we can place in its proper position at end of array

Heapsort (A,n)
Build-Max-Heap(A,n)  //first build heap
for i = n to 2
     exchange A[1] and A[i]  //at each iteration we get the largest element at first index and replace with last
     heap-size[A] = heap-size[A]-1 //no need to count the already sorted elements placed at end of array
     Max-Heapify(A,1) // after exchange it might not be heap anymore

Analysis
Since building max heap takes O(n) time and
there are n-1 call to max-heapify procedure that is O(nlogn)
so total cost is O(nlogn)

Insert(A,a)
Inserts an element in already established heap
put the new element at last position and percolate up that is find the right position by comparing with parent
and sibling
worst case time of O(log n)


Min Max Heap
It is possible to get both min and max in time O(logn)

Heap Implementation
1)binary tree
finding adjacents in last level is problem while adding
2)array
no space required for pointers
allows heapsort to be inplace
requires allocating array before using it so cannot be used for priority queue where number of task are not known before

Problem 

Is the sequence <23, 17, 14, 6, 13, 10, 1, 5, 7, 12> a max-heap?
Solution Not a max heap

Problem Time cost for Heap - Delete, which deletes a root element
Solution
We delete the element i and swap it with last element and call max heapify for this exchanged node
so it run in time of max heapify that is O(lg n)

Problem Merge k sorted list with heap sort.
Solution:
Assume total number of elements as n
1) build a min heap with first elements of each list, heap would contain k elements// cost O(k)
2) while heap not empty  // there are k element in heap
        Extract min from heap and append to output
        If successor of output element != nil, call min heapify for this element //cost O(lg k)
At a time there are max k elements in heap, successor of element is next element in its sorted list.
since we have total of n elements its O(nlogk)
and space will be O(k)

Problem Analyze the heapsort on already sorted array i)acending ii)decending
Solution
Heapsort Algorithm includes two things
1)build max heap // called n/2 times
2)exchange first element in array with last and call max heapify // called n-1 times

Consider Heapsort algorithm called on list already sorted in
i) descending order
Build Max heap is called on n/2 non leaf elements of the list and it need to go thru each even though they are sorted so it takes O(n).
max heapify is called n-1 times for list of n items But since max heapify replaces the last item with the first it changes the order of the list and it needs to be heapified each time which cost Th(log n)
so total cost becomes Th(n logn)
ii) ascending order
Build max heap will take time more than previous case but still O(n)
max heapify will still take Omega(logn) for each element
So total cost is Omega(nlogn)

Problem Insertion into Max heap with binary search
Consider max heap is stored as an array we insert the new element in the last position and then call heapify for nodes on its path to root which will take O(logn) time but what if we find the position of new element by binary search on its path to root, the number of nodes to compare would be O(lgn) and binary search will make Th(lg(lg n)) comparisons but then after finding the right position we need to shift the elements on its path downwards which will be of O(lgn) so again it becomes O(lg(lgn)+lgn ) = O(lgn)

Problem Given an array of n elements find i largest elements
Solution Build max heap of n elements // cost O(n)
Extract maximum element of heap i times // each extract takes O(lg n) time
Total cost = O(n+i lgn)
for i < n this cost is asymtotically less than O(nlogn)

Binary Search Tree(BST)

Different types of search tree includes Binary search tree, B tree, B+ tree,Red-black tree.
Basic operation takes time proportional to height of the tree in case of balanced tree.
  for complete binary tree with n nodes has worst case of Th(log n)
  for  linear chain of n nodes it behaves like linked list and has worst case of Th(n)
Can be used as dictionary and priority queue

Properties of Binary Search Tree

All nodes in the left subtree of parent must be no greater than parent that is key[left] <= key[parent]
All nodes in right subtree of parent must be no smaller than parent that is key[right] >= key[parent]

This property of binary search tree allows us to find sorted ordering in simple way by using inorder traversal

Tree Traversals

Process of visiting each node once.
Traversals are classified by the order in which root node is visited

1) Depth first traversal explores as far as along each node before backtracking
preorder (root left right)
inorder(left  root right) gives ascending sorted order
postorder (left right root)

2)Breadth first traversal
examining nodes at each level before moving to next level

Binary tree traversal implementation with Recursive procedure and auxiliary data structure require stack space proportional to the height of the tree. In a poorly balanced tree, this can be quite considerable.
Stack requirement can be removed by threading the tree, which will improve the inorder traversal alone.

Preorder traversal------------Th(n)

PREORDER-TRAVERSE(tree)
if (tree not empty)
  visit root of tree
  PREORDER-TRAVERSE(left subtree)
  PREORDER-TRAVERSE(right subtree)



Time complexity of recursive traversal 
consider n-node tree

T(n) = T(left)+ T(right) + d
T(n)=T(k)+T(n-k+1)+d
T(n) = Th(n)

Example Consider tree

       j         <-- level 0
     /   \
    f      k     <-- level 1
  /   \      \
 a     h      z  <-- level 2
  \
   d

inorder traversal   a d f h j k z
preorder traversal  j f a d h k z
postorder traversal d a h f z k j
breadth traversal   j f k a h z d

Reconstruction Property of Binary Search Tree
A unique binary search tree is possible from its its inorder, preorder and inorder, postorder but not from preorder and postorder. All the three a possible in case of full binary tree.


Example For 4 nodes draw a tree that gives same preorder and inorder traversal
It will have no left childrens

a
 \
  b
   \
    c
     \
      d
is the same possible with postorder and inorder traversal ?

Traversal with explicit Stack  
Every recursive call is Push operation and visit is print operation
The state of stack before first pop for
1) inorder
|_a _|
|_f__|
|_j__|
as in recursive call we call inorder(j) then on its left  inorder(f) and then inorder(a) then print(a) ...
2)  post order
|_a _|
|_f__|
|_j__|

3)preorder
|_   _|
|_ __|
|_j__|
before first pop


|_   _|
|_k _|
|_f__|
after first pop

Tree - Successor (x)       ----- O(log n)

successor in sorted order determined by inorder traversal
we need to find successor of node x

case1 : If the right subtree of  x is not null then need to traverse down and find
  Tree-Minimum(right(x))

case2 : right subtree of x is null then successor of x is
lowest ancestor of x whose left child is also an ancestor of x i.e

y = parent(x)

while(y!=null and x=right(y))

 x = y

 y = parent(y)

return y

Example Consider tree below and we want to find successor of node 13

                     15
                   /     
                 6
                   \
                    7  <-------y
                      \
                      13  <-------x
since right(y) == x so we move into loop

After first loop
                  15
                   /     
                 6 <-------y
                   \
                    7  <-------x

                      \
                      13
here also right(y) == x

After second loop

                  15 <-------y
                   /     
                 6 <-------x
                   \
                    7

                      \
                      13


right(y) which is null != x so we get 15 as ancestor of x


Time Complexity of Tree-Successor(x)
big O(h)


Inorder Traversal without using stacks 
If each node stores reference to parent then traversal implementation is possible without stack

or visited flag. When we don't have parent pointer we need to use Threaded binary tree.

Right threaded binary 

We need to know if a pointer is an actual link or a thread, so we keep a boolean for each pointer.
Traversal
1) We start at the leftmost node in the tree, print it, and follow its right pointer
2) case 1  If its thread to the right, we output the node and continue to its right
    case 2  If we follow a link to the right, we go to the leftmost node, print it, and continue
Example
consider below right threaded tree

1)we start at leftmost node i.e 1, print it and follow right pointer
2)right pointer is  thread so we output 3 and move to its right
3)right pointer is link now to node 5 so we follow the leftmost node of 5 which is none so we print 5 and follow its right pointer and so..

Algorithm 

x  = leftmost(n);
while (x != null)
  print x
  If (right(x) = thread)
    x = x.right;
  else
     x = leftmost(x.right);

Advantages
Binary trees have a lot of wasted space: the leaf nodes each have 2 null pointers.We can use these pointers to help us in inorder traversals

Insertion and Deletion

Deletion----  O(logn)

Tree-Delete( T,z)
z is pointer to node of Tree T to be deleted
There are 3 possibilities

• deleting leaf node we modify the parent of z to replace z will null
• deleting a node with single child, splice z by making anew link between its child and its parent
• deleting a node with two children we splice out z, do not delete z instead choose either its inorder successor or predecessor and replace z with this and then delete successor 
• or for two children we can say delete smallest key in the right subtree or largest one in the left subtree

the successor of z,y will have no left child because if it has left child then it contradict that its successor of z.

Running time of deletion
running time of deletion procedure depends on Tree-successor which takes O(h) time
So running time of deletion is O(log n)


Insertion ------------ O(log n)
Tree-Insert(T,z)
point y to parent of each node
x to current node
while x!=null    // traverses tree downwards  takes O(h)
if key[z] < key[x]
 x=left[x]
else x=right[x]

at end y will hold the node where to insert z
p[z] = y

If y=null //means tree is null then create root
root[T]= z
else
set z as appropiate left or right child of y


Running Time
takes O(h) time

Build BST---------worst O(n^2)
In the worst case it takes O(n^2) when we have sorted list so all goes one after other in tree
making height of tree n
if we use self balanced tree it can be performed in O(nlogn)

Sorting ------worst O(n^2)
Build BST
perform Inorder traversal
worst case that of build procedure O(n^2)
poor cache performance and overhead of space
most efficient for incremental sorting



Range(a,b)
returns range of values a<=n<=b
find a and b in the tree
Let Pa and Pb be the search path from root to a and b resp.
Let x be the node where pa and pb split
for every node  v in the path a tox
if v > a
 print v
 inorder(right.v)

for every node  v in the path b to x
if v < b
 print v

 inorder(left.v)



Total time
finding the paths Pa and Pb takes at most O(h)
each inorder takes O(n) for n node tree
here we have k elements so O(k)
O(h+k)


Check the sequence if possible on searching
build the bst by placing larger on right and smaller on left
now check for each node every node in right subtree should be greater and in left should be small
Example
935, 278, 347, 621, 299, 392, 358, 363
isn't a possible sequence because 299 can't be in the right sub-tree of 347.

Problem Two binary search tree T1 and T2 with distinct nodes, each node in T1 is small than node in T2
Time complexity to merge T1 and T2 and height of new BST
Solution
If height of T1, h1, is greater than h2 then
find the largest element v of T1 and make it root
v= Find-Max(T1) //O(h1)
v.right =T2
v.left=T1
since maximum of T1 is less than T2 and will be greater than remaining T1
similarly when h2>h1 we can
Find-Min(T2) and make it root in time O(h2)

In both cases running time is O(min(h1,h2)) height of tree would be O(max(h1,h2)+1)

Tree Rotation
changes the structure without interfering with the order of the elements.
node node moves up(smaller subtree) other down(larger subtree)
Right rotation
                        a                right rotation                                 b
                      /    \              --------------                            /     \
                    b      c                                                           d        a
                  /   \                                                                         /    \
                d     e                                                                      e      c

AVL Tree
self balancing binary search tree
height of two child subnodes of any node differ by at most 1 or balance factor 1 0 -1
balance factor = height of left sunode - height of right
After each basic operation we perform rotations to keep tree balanced


Height of AVL tree
g(h)  number of nodes in the worst case the minimum number of nodes a AVL tree can have
g(h) = 1+ g(h-1)+g(h-2)
where g(0) = 1 and g(1)=2
interms of fibonacci sequence its
g(n) = f(n+2) -1
height of AVL tree is < 1.44 * log (n+2) - 1
Height of Red black tree is at most 2log(n+1)

Problem what is minimum number of nodes in AVL tree of height 10
Solution we know g(0) =1 and g(1) =2 and g(h) = g(h-1)+g(h-2) +1
so g(2) = 1+2+1 =4, g(3) = 7,g(4) = 12,g(5)=20,g(6)=33,g(7)=54,g(8)=88,g(9)=143,g(10)=232

Look up
look up is similar to unbalanced BST
since here its balanced in the worst also it takes O(log n)

Insertion
need to check ancestors for balance, if it becomes +- 2 we need to balance it
i)right-right case : when balance factor p for node is -2 that is right child outweighs
 check balance factor of right subchild (R )
   if p(R) <= 0 then left rotation with P as root
   if p(R)= +1 then double rotation wrt to P is needed first with R as root and next with P as root
ii) left-left case when balance factor for node P is +2 that is left outweighs

Dynamic Programming - LCS, Matrix Chain, Optimal BST, Knapsack

Dynamic Programming

• DP is general approach to solving problems much like Divide and Conquer, except that subproblems will typically overlap.
• Break the problem into reasonable number of subproblems in such a way that we can give optimal solution to subproblem to achieve optimal solution to large ones.
• The dynamic programming idea doesn't tells us how to find solution, it just gives us a way of making the solution more efficient once we have.

Top down solution and Bottom up solution
Bottom up solution involves recursive solution this is also usually done in tabular form
calculates smaller values first and then
build larger values from them
moves from f(0) to f(1) f(2) so on
Top down memoization store the result of caculation which are later used
first break the problem then
calculate and store its result
move from f(n) to f(n-1) f(n-2) ...

Difference from Divide and Conquer
Subproblem size is of additive order in dynamic programming that is little smaller than original problem but in  case of divide and conquer subproblem size is of multiplicative order that is its n times small than original problem


Types of DP problems

Dijkstra shortest path problem, Bellman Ford shortest path problem, Fibonacci sequence, balance 0-1 matrix,Tower of Hanoi,Flyod all pair shortest path

Longest Common Subsequence Problem

Given two strings: string S of length n, and string T of length m. Our goal is to produce their longest common subsequence, the longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.

S = ABAZDC

T = BACBAD

LCS of length four ABAD

It is like finding  a 1-1 matching between some of the letters in S and some of the letters in T such that none of the edges in the matching cross each other.

Problem definition
consider two sequences
X =(x1,x2,...xm)
Y=(y1,y2,... yn)
Find longest common subsequence  Z=(z1,z2...zk)  of X and Y


Optimal substructure
1. If xm = yn that is last element is same then LCS also should have that last element

• zk = xm = yn because if it is not in Z then there exist some other sequence with xm that is longest
• remaining LCS will be of Xm-1 and Yn-1 
• LCS(X,Y) =(LCS(Xm-1,Yn-1),xm)

2. If xm != yn then either Z is common sequence which ends in 

•   yn i.e LCS(X,Y) = LCS(Xm-1,Y) or
•   xm i.e LCS(X,Y) = LCS(X,Yn-1)

Overlapping Substructure 
Finding solution now includes solving case 1 when x=yn or solving two possibilities for case 2
Solving both the possibility of case 2 needs to solve case 1 as their subproblems.

Recurrence Solution
c[i,j] be length of LCS of Xi and Xj which is
1) 0 when i=0 j=0
2)  c[i-1,j-1]+1  when i,j>0 and xi=yj
3)  max(c[i,j-1], c[i-1,j])  when i,j>0 and xi != yj

Using simple recursive solution will give exponential time, since there are Th(mn) distinct problems we use Dynamic programming to find solution bottom up.


Time Complexity
takes time O(mn)
space O(mn) if we want to retrace the path also
but if we need only the length we need to keep only two rows current and previous
The problem can be solved in polynomial time if number of sequences are constant but otherwise ........

Problem 

For X= 010110110 Y=10010101 Find LCS with matrix table

tracking back the LCS we get 010101

Matrix Chain Multiplication

Problem definition
Given A1, A2, …,An  compute the product: A1xA2x…xAn , find the fastest way (i.e., minimum number of multiplications) to compute it.

two matrices A(p,q) and B(q,r), compute their product C(p,r) in pqr multiplications

Different parenthesization will have different number of multiplications for product of multiple matrices.

There are an exponential number of different possible parenthesizations, in fact 2(n−1)C(n-1) /n or
P(n)   = 1 if n=1
         = sum(k=1 to n-1)P(k)P(n-k) if n>=2
catalan number, so we don’t want to search through all of them. Dynamic Programming gives us a better way.

Example: A(10,100), B(100,5), C(5,50)
– If ((AB) C), 10 *100*  5 +10 *5 * 50 =7500
– If (A(BC)), 10 *100* 50+100*5*50=75000
 The first way is ten times faster than the second

Denote matrices with their row columns as
A1(p0,p1), A2(p1,p2), …, Ai(pi-1,pi),… An(pn-1,pn)

so multiplying Ai..Ak Ak+1...Aj takes  pi-1 pk pj multiplications
that is multiplying A[2,2] and A[3,5] takes p1*p3*p5

Optimal Substructure
optimal parenthization of Ai,Ai+1...Aj splits the product between Ak and Ak+1  The parenthization of prefix subchain Ai...Ak must be optimal within Ai...Aj

Recursive Solution
Let m[i,j] be the minimum number of multiplications for Ai x Ai+1,…,x Aj where 1<=i<=j<=n
and thus for complete problem it would be m[1,n]
m[i,j]    = 0  if i = j
            = min(over i <= k< j) {m[i,k] + m[k+1,j] +pi-1pkpj } if i

Optimal Cost  and Overlapping Structure
Recursive solution will encounter the same subproblems  many time and hence running time becomes exponential but actual number of subproblems are Th(n^2), since one subproblem for each choice of i and j
that is C(n 2) + n
Tabling the answers for subproblems, each subproblem is only solved once. exploring the Overlapping structure

Running Time
O(n^3)
space Th(n^2)

Observations
we can fill the nodes A[i,j] where i=j and where j = i+1 initially
For solving each m[i j] we only use all the splits between i and j for calculation along with the cost to calculate
For A1A2A3A4 the nodes splits are like

Fig showing the split for A1A2A3A4

1-4 gets split into: 1-1,2-4;  1-2, 3-4;  1-3,4-4. similar for 1-2, 3-4; 1-3,4-4.
From the diagram we can find the order in which nodes are evaluated that is m[i,j]

Optimal Binary search Trees 

we are given n distinct keys and propabbility pi for each key that a search will be for ki
we also have dummy keys for key not in tree
Number of leaf nodes for  n keys = n+1

Probability of finding some search key key(success)  + probability of finding some dummy(unsuccessful) = 1

Assume that actual  cost of search is number of nodes examined i.e the depth of node found by search in T plus 1

Expected cost of search Tree  T is
E[search cost in T] = sum{0 to n} ((depth(ki + 1) * (pi) ) +sum{i=0 to n}((depth(di) + 1) * (qi))
1+ sum{0 to n} ((depth(ki ) * (pi) ) +sum{i=0 to n}((depth(di) ) * (qi))
because {sum 1 to n} pi + {sum 0 to n}qj = 1

expected cost of subtree when it becomes subtree of node
the depth of each node in subtree increases by 1
expected search cost increases by sum of all probabilities in tree that is  increase of
w(i,j)= {sum l= i to j} pi + {sum l= i-1 to j}qj  for nodes i to j in subtree 

Recurrence Relation
e[i,j] expected cost of searching an OBST containing keys ki ... kj.

e[i,j] =  qi-1 when j=i-1
        =  min{ e[i,r-1] + e[r+1,j] + w(i,j) }  when i≦j,i≦r≦j

Observations 
consider nodes  a, b, c, d in increasing order
with probability P(a) = .1, P(b) = .2, P(c) = .3, P(d) = .4


1) Possible BST

Fig. possible BST

search cost of node = (depth of node + 1) * probability of node
Average Cost = 1*0.4 + 2*0.3 + 3*0.2 + 4*0.1 = 2.0

2)OBST

   Average Cost = 1*.3+.2*2+.4*2+.1*3 = 1.8

Example 2

i   |   1     2    3     4    5
P  | .24 .22  .23  .3   .01

we find values of table e[i,j]
for i= j its
www.cs.wpi.edu/~songwang/ta/recitation6.ppt

 Knapsack Problem

Problem definition
we are given a set of n items, where each item i is specified by a size si and a value vi . We are also given a size bound S (the size of our knapsack). The goal is to find the subset of items of maximum total value such that sum of their sizes is at most S (they all fit into the knapsack).

Input:
Capacity of knapsack k
n items with weight wi and value vi
Output:
set S of items such that
sum of weight of items in S <= k
and sum of values of items in S is maximized

c[i,w] be solution for items 1,2..i for maximum weight w
When we are considering ith item either we include it or exclude it
If we include the ith item then value of that item will be added and remaining problem should give optimal soution for remaining weight that is c[i-1,w-wi ]
If we exclude the ith item then value then still we have weight w to fill and remaining i-1 items to check
that is c[i-1,w]

Recurrence Relation
c[i,w]         =     0     if i = 0 or w = 0
                  =    c[i-1, w]     if wi  ≥  w
                  =  max [vi + c[i-1, w-wi], c[i-1, w]}     if i>0 and w ≥  wi

Computing the maximum value in weight
 c[i, j] is table, that is, a two dimensional array,  c[0 . . n, 0 . . w]

for w = 0 to W
 c[0,w] = 0
for i = 1 to n

 c[i,0] = 0

for i = 1 to n
  for w = 0 to W
   if wi <= w // item i can be part of the solution
     if bi + c[i-1,w-wi] > c[i-1,w]

       c[i,w] = bi + c[i-1,w- wi]
    else

     c[i,w] = c[i-1,w]
   else c[i,w] = c[i-1,w] // wi > w

Example
consider  n =4 W=5 and following
weight and values (2,3), (3,4), (4,5), (5,6)

consider evaluation
for 1st row v1= 3, w1=2,

for c[1,1] w=1
since w1 > w 
   c[1,1]= c[0,1] = 0
for c[1,2] w=2
 c[1,2] = max(3+c[0,0] ,c[0,2]) = 3

 for c[2,1]  v2=4 w2=3 w=1

since w2>w, we have c[2,1] = [1,1] =0

for c[3,5] v3=5 w3=4 w=5

c[3,5] = max(5+c[2,1] , c[2,5])

similarly filling all we have

//incomplete
//travelling salesman problem
//all pair shortest path

Recurrence Relations

Recurrence	Algorithm	Big-Oh Solution
T(n) = T(n/2) + O(1)	Binary Search	O(log n)
T(n) = T(n-1) + O(1)	Sequential Search	O(n)
T(n) = 2 T(n/2) + O(1)	tree traversal	O(n)
T(n) = T(n-1) + O(n)	Selection Sort (other n2 sorts)	O(n2)
T(n) = 2 T(n/2) + O(n)	Mergesort (average case Quicksort)	O(n log n)

Recurrence of form
1.T(n)= T(k) + T(n-k+1)+C
2.T(n) =T(k)+T(n-k+1)+O(n)
3.T(n)=2T(n/2) +O(n)

solution
1. O(n) , relation T(..) on right contributing also Th(n)

2. O(nlogn) ,O(n) contributing to the time complexity

3.same as 2,O(n) contributing to the time complexity

solver recurrence
1) T_n=3T_n/2       
   Tn = 3(3T_n/2²) = (3ⁱ )Tn/2ⁱ =
   3^log₂n =n^log₂3
2) Tn = 3Tn−1+2.
   3ⁿ − 1.
3) Tn = 2T(n−1) + 2.
   2ⁿ⁺¹ − 2.

Lame’s theorem (Complexity of the Euclidean algorithm). Let a and b be positive integers with a ? b, n be the number of divisions used by the Euclidean algorithm to find gcd(a, b) and k is the number of decimal digits in b. Then n <= 5k.Note that k <= log10 b?+1. Therefore, n = O(log b) divisions are used by the Euclidean algorithm.

Couting problems with Recurrence Relations

Problem Find number of bit string s with no two consecutive 0's
lets call an be number of  bit strings of lenght n where we do not  have 2 consecutive zeros
1) number of bitstrings ending with 0 that should have 1 with them, that is of the form
----|10 and the first part can be occupied by any valid bit string that itsself donot have consecutive zero that is an-2
2) number bit strings ending in 1, ----|1 which is an-1
so an = an-1 + an-2 where initial conditions should be specified for a0 a1 and a2
a0 = 0
a1=2 {0,1}
a2 = 3{01,10,11}
the recurrence seems to be like Fibonacci sequence where a1 corresponds to f3, a2 to f4  i.e  an = Fn+2
This is also relation for subsets of n numbers which do not contain consecutive number
{1,2,3} subsets are F(5) i.e {empty,{1},{2},{3},{1,3}} 5 subsets

Problem Count all number of n digit where number of zero is even
1)any number of for 9,57 which has no zero is valid, and such numbers in form of recurrence is
n-1|9 , n-1|8 , n-1|7... that is all strings ending in some non zero digit and having first n-1 as valid string
i.e 9*an-1
2)we have not counted any number which has zero digit in it ...(we use little to much recursive thinking here)
numbers with zero digit can be formed by adding a zero to number with even number of zeros
number with even number of zeros = total numbers - number with odd zeros(which we have named an)
 10^n-1 - an-1
we get final reccurence as an = 8an-1 + 10^n-1

Solving Recurrence Relations


www.cs.duke.edu/courses/cps130/.../Homeworks/Solutions/H2-solution.pdf   //order of growth problem
www.cse.psu.edu/~berman/sol_565_1.pdf

1) If f(n) = Th(g(n))  { 0<=c1g(n) <= f(n) <= c2g(n) } for some n>= n0 and c1,c2,n0 >=0 
then f(n) = O(g(n)) because it implies 0<= f(n) <= c2g(n)

2)For polynomials p(n) = Th(n^d)

3)o notation
if f(n) = o(g(n))
f(n) becomes insignificant relative to  g(n) for large values of n


4) if
f(n) = w(g(n))



Comparing various functions time complexity
5) exponential and polynomial function
exponential functions with base greater than 1 grows faster than polynomial functions that is
n^b = o(a^n) for a > 1
lim{n->infty} ( n^b / a^n)  = 0

6)exponential e^x
e = 2.71828e^x = {sum o to inty}  x^i / i!
i.e e^x  >= 1+ x
when x = 0 its equality
if |x| <=1
e^x <= 1+x+x^2
so e^x = 1+x+Th(x^2)

7)logarithm functions
polylogatithmic functions grow more slowly than polynomial in the similar manner like polynomial grows slowly than exponential
we use substitution to prove that
substitute log n for n and 2^a for a


a^(log_bc) = c^(log_ba)
 abc converts to reverse, cba


8)
Transitivity is true for all five operators like
f(n) = O(g(n)) and g(n) = O(h(n)) then
f(n) =O(h(n))

Reflexivity is also true for O,Th and Omega that is for all asymptotic tight bounds
f(n) = O((n))

Symmetry is true for Th only that is
f(n) = Th(g(n)) if and only if  gn = Th(f(n))

Case when we might not be able to compare function like in case of
trignometric functions which oscillates n^(1+sin n) and n here 1+sin n oscillates between 0 and 2