Design Analysis of Algorithm

This article covers the Design Analysis of Algorithm for CS-6550 course. It includes solutions to exercises related to Bipartite Graph, Koenig’s Theorem, Hall's Theorem, Regular Bipartite Graph, and Matching Reductions.

Design Analysis of Algorithm
Design Analysis of Algorithm
CS – 6550
1

Design Analysis of Algorithm
Table of Contents
Solution Exercise 1 1
Solution Exercise 2 2
Solution Exercise 3 3
Solution Exercise 4 4
Solution Exercise 5 5
Solution Exercise 6 6
2

Design Analysis of Algorithm
Exercises
1. *Flows, Kings, Halls, and Colors. Recall that Koenig’s theorem says for a
bipartite graph G, the size of the maximum cardinality of a matching in G is
equal to the size of the minimum vertex cover.
(a) Use the max-flow/min-cut theorem to prove Koenig’s theorem. (Recall that the
max-flow/min-cut theorem says that in any flow network, the maximum s􀀀t flow
equals the minimum s􀀀t cut. Moreover if the arc capacities are integers, then there
is a max flow which is integral.)
Solution-
Bipartite Graph
A Bipartite Graph also known as Bi-graph is a graph having set of vertices decomposed into two
disjoint set of vertices such that no two vertices in the graph within the same set are adjacent. It
is considered as a special case of K-Partite graph. A Bipartite Graph G= {U, R, V} consists of
two disjoint sets Land R and a set of edge E such that it has one vertex in L and one in R.
Koenig’s Theorem
3

Design Analysis of Algorithm
According to Koenig’s Theorem the size of minimum vertex cover is equal to the size of minimum
vertex cover is equal to the size of the maximum matching. For a Bipartite graph G, the maximum
size of a matching equals the minimum size of a vertex cover.
Proof of Koenig’s Theorem through Max- Flow/Min-Cut Theorem
According to the Max-Flow /Min –Cut Theorem, a minimum cut is equal to the maximal flow.
Now using the definition of Bipartite Graph, for any finite Bipartite Graph g, the number of
edges in maximal equals to the number of vertices in the Minimal Vertex Cover.
In order to prove this we extend the Bipartite Graph G to a network by adding source and sink
in it. By doing this it is observed that in the new graph the maximal flow corresponds to the
maximal matching and the Minimum Cut corresponds to the minimum cover. Here Let X and Y
be the Bipartite separation for the graph G, now by this we draw a digraph G1 = {V1, E1}, where
V1 represents the set of vertices in V with source s and sink t, E1 represents the set of edges in E,
along with this their consists of the other new edges leading from s to every vertex in Set X and
leading from vertex Y to t. The Edges according to the assumption has infinite capacity, and to
each added new edge in E1 the capacity assigned is 1. It is assumed that the cardinality of
matching to be k, so the flow will also be k. The Flow 1 is pushed in the path s-x, x-y and y-t
where (x, y) is one of the matched observations with flow 1. Thus the maximal flow in G1
corresponds to the cardinality of G.
Let the M be the Cover of G with r vertices , let M(X) and M(Y) be the subsets of M having
vertices of M in X and Y. It is assumed that the X1 = X-M(X) and Y1 = Y-M(Y). The Cover M
implies that there is no edge from X1 to Y1. Further it is assumed that S be the Union of s, M(Y)
4

Design Analysis of Algorithm
and Y1. Similarly let T be Union of t, M(Y) and Y1. Further it is observed that the cardinality of
cut (S, T) of G1 is r which is also the cardinality of M, so the cover of vertex cut is same. Again
by the rule the edges from X to Y will have infinite capacity and edges from S to T will have
capacity 1. Since the cut had cardinality r so the number of arcs is also r.
Now we observe for Minimal value, here let M be the set of vertices x in X such that sx in
(S,T) , similarly set of vertices y in Y such that sy in ( S,T). As proved before that the number of
vertices in M are r . So it is observed that every cover in G corresponds to the G1. So minimum
cut corresponds to the minimal covering in G.
*(b) Use Konigs theorem to prove Hall's theorem:
In a bipartite graph G = (L;R;E), for any set S _ L, let N(S) = fr 2 Rj9` 2 S; (`; r) 2
E g be the neighbors of S. Then G has a matching of size jLj if and only if jN(S)j _
jSj for all S _ L
Proof
Hall’s Theorem
According to Hall ‘s Theorem , A Bipartite graph G with Bi-partition, Here Let L and R be the
Bipartite separation for the graph G . Then there is matching of size X if and only if every set S
is subset of L of vertices at least connected to |S| vertices in B.
Now using the Konig’s theorem - The size of minimum vertex cover is equal to the size of
minimum vertex cover is equal to the size of the maximum matching . For a Bipartite graph G,
the maximum size of a matching equals the minimum size of a vertex cover. So by using the
result of konig’s theorem the S will be subset of L as both have same capacity and flow with
maximal matching.
5

Design Analysis of Algorithm
Now through another result of Hall’s Theorem if L and R are both countable and every vertex
has finite number of neighbors then for every S that is subset of L , has at least |S| neighbors,
then there is matching touching every vertex of L, now it is given-
According to above given specification there are finite number of neighbors, in order to check
we assume to take arbitrary x ϵ L and yϵ R such that both have at least one neighbor in both.
We match the neighbors of both the sets and observe that the flow or cardinality of both the cut
set are equal. L-x and R-y, so there are vertices that match to S1 to the L.
*(c) Use Koenig’s or Halls theorems to show that in a bipartite graph where every
vertex has the same degree d (also called a d-regular bipartite graph), there is a
perfect matching.
Proof
D-regular Bipartite Graph
A Bipartite Graph is called regular –d bipartite graph if and only if every vertex of G has degree
d. As it is evident the degree of a vertex implies the number of edges incident on the vertex. By
Koenig’s Theorem- the Edges according to the assumption has infinite capacity, and to each
added new edge in E1 the capacity assigned is 1. It is assumed that the cardinality of matching to
be k, so the flow will also be k. The Flow 1 is pushed in the path s-x, x-y and y-t where ( x,y) is
one of the matched observation with flow 1. Thus the maximal flow in G1 corresponds to the
cardinality of G. Since the graph is regular and the edges go from X to Y then for generality we
assume that the A be subset of X .Let A⊆X be an arbitrary subset, and denote by the set of
6

Design Analysis of Algorithm
neighbors N of elements of A .Every edge in the Bipartite graph has endpoint in A has an
endpoint in N(A) (N(A) is the set of neighbours of A) , so letting EA and EN(A) denote the
respective edge sets, . Then since G is regular (d is the degree of each vertex), |EA|=d|A| and |
EN(A)|=d|N(A)| , hence |A|≤|N(A)| . By Hall’s theorem there is a complete matching. But |X|=|Y|,
so every vertex in is matched to a vertex in , which together match every vertex in the graph.
Thus the complete matching is a perfect matching
*(d) Use the above part to show that the edges of a d-regular bipartite graph can be
colored using d colors so that all edges incident on each vertex have different
colors.
Color of Edges in Graph
The coloring of edges in a graph defines the way in which no vertex is incident on two edges
having the same color, a graph is Bipartite if the graph is 2 colorable otherwise not.
Cloring of Edges in Regular Bipartite graph with degree d
A Bipartite Graph is called regular –d Bipartite graph if and only if every vertex of G has degree
d. For coloring the graph two set of possible path from graph is required to create from subsets
X,Y such that their vertices are not repeated and one color to one set of path and another color to
another set of path is drawn. As it is evident the degree of a vertex implies the number of edges
incident on the vertex. By Konig’s Theorem- The Edges according to the assumption has infinite
capacity , and to each added new edge in E1 the capacity assigned is 1. It is assumed that the
cardinality of matching to be k, so the flow will also be k. The Flow 1 is pushed in the path s-x,
x-y and y-t where ( x,y) is one of the matched observation with flow 1. Thus the maximal flow
in G1 corresponds to the cardinality of G. Since the graph is regular and the edges go from X to
7

Design Analysis of Algorithm
Y then for generality we assume that the A be subset of X .Let A⊆X be an arbitrary subset, and
denote by the set of neighbors N of elements of A .Every edge in the Bipartite graph has
endpoint in A has an endpoint in N(A) (N(A) is the set of neighbours of A) , so letting EA and
EN(A) denote the respective edge sets,
In order to perform coloring the Subsets of vertices X , Y are done and path , s-x , s-y is drawn,
t-x, t-y is drawn using the result of konig’s Theorem Again by the rule the edges from X to Y
will have infinite capacity and edges from S to T will have capacity 1. Since the cut had
cardinality r so the number of arcs is also r , the flow of all the path is 1 . According to rule each
bigraph should be divided in two parts so by using the halls result matching is performed . In
order to check we assume to take arbitrary x ϵ X and yϵ Ysuch that both have at least one
neighbor in both. We match the neighbours of both the sets and observe that the flow or
cardinality of both the cut set are equal. X-x and Y-y , so there are vertices that matches to S1 to
the L. only coloring is done to unmatched set of edges.
2. *Some Matching Reductions. Suppose you have an algorithm that solves max-
weight perfect matchings (MaxWPM) for all non-negative weight functions. Give
reductions that allow you to solve (a) min-weight perfect matchings (MinWPM)
and (b) min-weight max cardinality matchings (MinWMaxM)i.e., among all
matchings of size equal to MM(G), _nd the one with least weight. If the MinWPM
and MinWMaxM instances are bipartite, ensure that the reductions give you
MaxWPM instances that are bipartite too
8

Design Analysis of Algorithm
Proof-
According to Maximum weighted matching algorithm , a non negative weight wi ,j is assigned to
each edge in the xi and yi in the set in Knn. Here we have to find the perfect matching M for
maximizing the total weight w(M) = ∑ e ∈ M W(e) .
In order to perform this a weighted cover , let u1, u2, u3---------un and v1, v2, v3------vn is selected
such that ui + vj ≥ w i.j for all i and j. Along with above the cost of c(u,v) is ∑ ui+¿ ∑ vj¿. Here
we have to find the cover with minimum cost.
For a perfect matching M in the Bipartite graph G with cover C (u,v) is that in any case the
C(u,v) ≥ w(M) . For matching this is possible only if M (matching ) consists of edges such that
ui+ vj = w ij. Here (u,v) is considered to be optimal. In the cover excess for i, j is ui+ vj – wi,j. we
are applying the Hingerian Algorithm for min-weight perfect matchings (MinWPM) .
Input : A matrix Wi,j of weights on edges on Kn,n with partite sets X and Y.
Concept : Adjusting the cover (u,v) iteratively until subgraph Gu,v has a perfect matching.
Initialization: Let ui = max { Wi,j : j=1,2…..n} and vj = 0.
Iteration: In order to perform the iteration first the two sets GU,V are designed and perfect
matching M is applied. The iteration will be stopped when the M has maximum matching and
(u,v) has minimal cost cover. Else the update of (u,v) will be done and same iterative operation is
applied until M has maximum matching and (u,v) has minimal cost cover.
B) Now to find the min-weight max cardinality matchings (MinWMaxM) i.e., among all
matching of size equal to MM(G), _nd the one with least weight. If the MinWPM and
MinWMaxM instances are bipartite, ensure that the reductions give you MaxWPM instances that
are bipartite too. We apply the result of Konig’s Theorem in it it is observed that the cardinality
9

Design Analysis of Algorithm
of cut (S,T) of G1 is r which is also the cardinality of M, so the cover of vertex cut is same. Again
by the rule the edges from X to Y will have infinite capacity and edges from S to T will have
capacity 1. Since the cut had cardinality r so the number of arcs is also r. so by applying this the
required criteria is fulfilled.
*3. Min-weight Perfect Matching’s. Suppose G = (L;R;E) is a undirected bipartite
graph with (possibly negative) integer edge weights we, suppose M is some perfect
matching. Let HM be the digraph obtained by directing edges in E n M from left-
to-right and putting weights we on them, and directing all edges in M from right-
to-left and putting weights 􀀀we on them.
(a) Show that HM has a negative-weight cycle if and only if M is not a min-
weight perfect matching.
Prove
Here it is given that there is unidirected Bipartite Graph G= (L;R;E) , means that the graph G
can be divided into two sub graphs X having set of vertices L and Sub graph Y with set of
vertices R, and the set of edges E. It has edge weights Wi,j inclined in it. For perfect Bipartite
graph to check the Maximum matching M , for any non-existing edge we add a edge with zero
weight .As we have shown how to find the min-weight max cardinality matchings
(MinWMaxM)i.e., among all matching of size equal to MM(G), _nd the one with least weight in
previous prove , we will continue with the same result. Now in order to prove that HM has a
negative-weight cycle if and only if M is not a min-weight perfect matching we will first check
10

Design Analysis of Algorithm
for any negative cycle in HM, if there exists a negative cycle then matching cannot be
Maximum. We assume that there is no negative Cycle in HM and M is not a maximum
matching. Let there exists a maximum matching M1, we take sub graph D1 of Graph D. Therefore
there exists a maximum matching M′. This contains the edges in MM ′. This graph is made up of
single disjoint edges (e∈ M∩M′) and alternating cycles (C⊂(M∪M′)−(M∩M′)). We assume
W(M′)> W(M)and W(e) fore ∈ M∩M ′is equal for both matching’s, then we have W(M′−M)>
W(M−M), which means there exists the negative cycle C⊂(M∪M′)−(M∩M′) = (M−M′)∪(M′
−M) in D′, and therefore in D, with a weight at most W(M−M)−W(M′−M). This method is not
very efficient because there is no scope in of improvement in each iteration and when w max=
max i,j{wi,j }, it is large compared to w min= min i,j{wi,j} so the time complexity becomes
O(m n×n (w max−w min), which is not polynomial in the inputs . According to Goldberg and
Tarjan , that if one finds negative cycles with minimum average weight W(C)/|C|,the time
complexity will be strongly polynomial.
(b) Consider the algorithm: Start with any perfect matching M. While there exists a
negative-weight cycle C in HM, set M M_C. Show that you will eventually get a
MwPM. If T(n) is the time to _nd a negative-weight cycle in an n-node graph, and
W := maxe2Ejwej, a naïve bound on the runtime of the above algorithm would be
O(nW)_T(n), plus the time to _nd the _rst perfect matching.
Proof
Here in the Bipartite Graph G , we assume with Weight W i,j , there exists the negative cycle C in
HM as proved in previous solution. We set the M ← M ∆C. In order to find the shortest
11

Design Analysis of Algorithm
augmenting time for matching in the negative cycle we use the result of Bellman –Ford
algorithm, which runs on O(mn) time. According to previous discussion we will get the
M←{ maxi , j, Wi.j}
Now directing the edges from left to right , putting weight we on it, here T(n) is the time to find
the negative weight cycle , as through Bellman result the maximum matching is at n/2 in
Bipartite graph.
So by above rule we get the Mw PM. Now it is given that W := maxe2 Ejwej, so according to
the above specification the naïve bound on the runtime of the above algorithm would be
O(nW) . T. Here the time for calculating the first perfect matching be let T1 (n). So the timing run
time of above algorithm will be – T = O(nW)+ T1(n).
(c) For matching M, denote w(M) := P e2M we. Show that if w(M) > w(M) then
there exists a cycle in HM with weight-ratio1 at most w(M)􀀀w(M)
n , where M_ is a min-weight perfect matching.
Proof
Here now using the above specification
Let for matching M the Weight w(M):= P e2M we , where P is the perfect path for perfect
matching. A matching in graph G is the set M is a subset of E such that no two edge in M share
12

Design Analysis of Algorithm
the common vertex . Here we assume that the W(M) = ∑ ❑e ∈ MWe , so according to the rule
for the perfect matching in G the parameter
For a cycle in the Bipartite Graph the , the cycle has alternatively path in X and Y , the cycle
contains no odd edges in cycle. Then their exists a cycle with the weight W(e ) , according to the
konig’s rule the capacity at edges is infinite bit for the subsets the cost or weight is 1. We
consider is non-negative edge weighting as for rw (M*(G)) ≤∑
i=1
k
w (Pi)
We, without loosing the generality we assume that the w(P1) ≥w(P2) ≥w(p3)……….≥ W ( Pk ) .
Then rw (M*(G)) ≤ kw ( p 1 ) ≤ P∗G,
So from above specification there exists the cycle in Hm , with having ratio 1 at most
W(M)-W(m)/n. As by measuring the cardinality the ratio will be above only.
(d) Suppose we change the algorithm in (b) to use the minimum weight-ratio cycle
C at each step. Bound the runtime of this algorithm by O(n log(nW)) _ T0(n), plus
the time to _nd the _rst perfect matching. Here T0(n) is the time to _nd a minimum
weight-ratio cycle
Sol
Here in the Bipartite Graph G , we assume with Weight W i,j , there exists the negative cycle C in
HM as proved in previous solution. We set the M ← M ∆C. In order to find the shortest
13

Design Analysis of Algorithm
augmenting time for matching in the negative cycle we use the result of Bellman –Ford
algorithm, which runs on O(mn) time. According to previous discussion we will get the
M←{ maxi , j, Wi.j}
Now directing the edges from left to right , putting weight we on it, here T(n) is the time to find
the negative weight cycle , as through Bellman result the maximum matching is at n/2 in
Bipartite graph.
So by above rule we get the Mw PM. Now it is given that the minimum matching in the
above , Here we bound the run time to O n(Log (nW)) .T(n)1. So by above the time for
calculating the first perfect matching be let T1 (n). So the timing run time of above algorithm will
be – T = On(Log (nW)).T(n)1, where the T(n)1, represents the Run time required to calculate the
minimum weight ratio. The total run time will be-
On(Log (nW)).T(n)1+ T11.
Where T11represents the run time for first perfect matching .
4. A Degree of Smoothness.. In the Max-Cut problem, we are given a graph G =
(V;E) with edge weights we, and want to _nd a subset S _ V such that the weight
of the edges crossing the cut (denoted as @S := f(u; v) 2 E : u 2 S; v 2 V n Sg) is
maximized. In the smoothed analysis setting, the edge weights are random
variables We supported on [0; 1], whose density function is bounded by 1=_, as in
lecture. Suppose the maximum degree in G is _.
14

Design Analysis of Algorithm
One algorithm for max-cut is the simple local-search algorithm: start with any
subset S. Now if there is a vertex v which can be moved from S to V n S (or vice
versa) to improve the weight w(_S), make the change.
Show that the expected number of improving steps in such an algorithm is bounded
by O(n32_=_). (Hint:recall the argument we used for the 2OPT local search
heuristic for TSP.)
Prove
Max Cut Problem
A cut in the weighted uni directed graph Gw = ( V,E) is defined as the partition of the vertices in
the two sets , and the weight of the cut in this graph is summation of the edges that has an end
points in each of the set formed through this graph, The Max Cut problem is also defined as the
problem of finding the cut in G having maximum weight .
Now given in the Specification in Graph G = (V;E) with edge weights we, here the aim is to find
the subset S of V such that the weight of edges crossing the cut. Defined as
In the smoothed analysis the edge weights are random variable We, supported on[0,1], and the
density function is bounded by 1/σ. According to the definition, in Smooth analysis the
maximum expected run time is measured where the maximum is taken over the random
15

Design Analysis of Algorithm
perturbation of the input , it is controlled through some parameter. The perturbation parameter is
defined through standard deviation σ, and is upper bounded , here the bounded parameter is
defined as the 1/σ. The Local search algorithms are used for computing the near optimal
solutions for the hard combinatorial problems such as Max cut smooth problem. Smooth
Analysis helps to bridge the theoretical explanation of performance to the practical performance
observation.
By using the result of the Etscheid and Roglin that showed the smoothed number of iterations
that utilize the heuristics bounded by polynomial in nlog n, where the perturbation parameter σ,
here n represents the number of vertices in the graph , through integer programming it is evident
that the problems that can be solved through Pseudo polynomial can be solved through smoothed
analysis method.
Formulation
Let us assign the variable xi to each of the vertex of Gw = (U,V)
We define the variable through
Using above formulation we define the max cut problem as
Max ½ ∑ ❑i< jwij ( 1−xixj )
16

Design Analysis of Algorithm
Here the the subset S of V such that the weight of edges crossing the cut. Defined as
Is used according to the above specification the subset having cut satisfying the above criteria
can be defined. We achieve the feasible region by applying the bounded condition 1/σ. Dividing
the above result by 2 gives the cut of the feasible solution. It also shows that if a vertex v
is ,moved to the S/V , then the improvement in the value will also show the max cut in the
formulation similarly.
Now we bound the above result to the O (n32∆/σ).
By utilizing the above result of work done by Michel Etscheid , the above bound can be applied.
5. Blocking Experts (due to Avrim Blum). Here is a variation on the deterministic
Weighted Majority algorithm, designed to make it more adaptive.
_ Each expert begins with weight 1 (as before).
17

Design Analysis of Algorithm
_ We predict the result of a weighted-majority vote of the experts (as before).
_ If an expert makes a mistake, we penalize it by dividing its weight by 2, but only
if its weight was at least 1 of the average weight of experts.
Prove that in any contiguous block of trials (e.g., the 51st day through the 77th
day), the number of mistakes made by the algorithm is at most O(m + logN), where
m is the number of mistakes made by the best expert in that block, and N is the
total number of experts.
Prove
Blocking Expert( due to Avrim Blum)
Here is a variation on the deterministic Weighted Majority algorithm, designed to make it more
adaptive.
_ Each expert begins with weight 1 (as before).
_ We predict the result of a weighted-majority vote of the experts (as before).
_ If an expert makes a mistake, we penalize it by dividing its weight by 2, but only if its weight
was at least 1 of the average weight of experts.
Blocking
Blocking is a technique that is used mathematically to remove the variation caused by some of
the identifiable change in the experiment. Various design Block provide various methods for
bringing the change in experiments, it helps to normalize the data. By default the Blocking is
assigned 1 which means there is no Blocking. So according to first specification with each expert
begins with weight 1 means there is no blocking. An expert is a skilled agent that can perform
18

Design Analysis of Algorithm
the actions with defined output as trial which a non expert cannot perform. A trial is predefined
value.
Here we assume that Avrim algorithm has N available actions, where X= {1…..N} , at every
step t the algorithm selects the steps . Now the algorithm receives the unlabeled example x,
According to the definition the mistake is the incorrect prediction. The goal is to make bound
number of mistakes. According to the condition given if an expert makes a mistake, we penalize
it by dividing its weight by 2, but only if its weight was at least14 of the average weight of
experts. Now using this condition that the trial in the expert system is bound O(Tn Log N) , so
using this rule for Avrim algorithm the Trial mistake will be O(M+Log N).
6. Expertise in Experts.. Here are some problems to help you internalize the
experts proof.
(a) Show that if we change the basic weighted majority algorithm to reduce the
weight by (1_) instead of 1=2,
we getour total loss _ 2(1 + _) _ (total loss of expert i) + O(logN_):
Prove
As given in the specification if we bring change in the basic weighted majority algorithm by
reducing the 1ε instead of ½ ε, then the according to rule at each time t the action it with the
lowest probability Pt gets the loss of 0, and all the other actions get the loss of 1. Since Min{ Pit}
= I/N. this gives that the total loss of H in T time steps will be at least T(1- 1/N) , so the it is
considered to be loss of O(Log N/ε) , now considering the total loss for all the actions the total
loss will be
Total loss ≤ (2+ε). (total loss of expert i ) + O(Log N/ε).
19

Design Analysis of Algorithm
Solution
Here for given equation the loss vectors are given, by default the value of blocking expert is
negative infinity and the highest value of loss will be by 1, then for any expert iϵ [N] can be
defined as
Now (u,v) is given the usual inner product , the value is well defined, the result is bounded to the
limit. The possibility of mistake will be reduced in this factor. For any Xi ϵ(u,v) will be
bounded .c)
20

Design Analysis of Algorithm
Prove
Here for given equation the loss vectors are given, by default the value of blocking expert is
negative infinity and the highest value of loss will be by 1, then for any expert iϵ [N] can be
defined as
Now (u,v) is given the usual inner product , the value is well defined, the result is bounded to the
limit. The possibility of mistake will be reduced in this factor. For any Xi ϵ(u,v) will be bounded.
Here loss are bounded to x2≤ x bounded ¿
[0,1]n. and ϵ ≤½ ,
By generality for xi in the equation
then the according to rule at each time t the action it with the lowest probability Pt gets the loss of
0, and all the other actions get the loss of 1. Since Min{ Pit} = I/N. this gives that the total loss of
H in T time steps will be at least T(1- 1/N) , it is also formulated that the considering the total
loss for all the actions the total loss will be
21

Design Analysis of Algorithm
(ii) similarly if in the same given equation the we have only gains then at every action there will
be high probability of correct values. Here loss are bounded to x2
≤ x bounded ¿
[0,1]n. and ϵ ≤½ ,
By generality for xi in the equation
Text tour gain ≥ (1-2ε) (gain of best expert) by given specification , so the total gain will be-
Total Gain= Text tour gain ≥ (1-2ε) (gain of best expert)- 2ln N/ε.
As minimum possibility of loss is required to deduct.
Prove
By analogy , the l(t) ϵ[-ρ,ρ], so in the every possible action the loss will be reduced in this factor.
So the learning rate will be-
The learning will be according to this function.
Since by rule the function loss is according to -
22

Design Analysis of Algorithm
Using the above specification-
The average regret or loss will be-
E
Prove
By updating the step according to given equation the loss will be
As by rule the loss will be according to this form only as specified above cases.
Problems
23

Design Analysis of Algorithm
Solution
a) Matching of Matroid-
A Matroid M=(U,I)
For Xϵ I , defines a Bipartite Graph HM(X) =(X,U\X,E) , where (x,y) ϵ E if x ϵX , y ϵU\X
And (X+y –x) ϵI
Here X,Y ϵI be two independent sets with |X| = |Y|
In order to be X,Y be in Matroid M, the
Then I is a subset of U ,
Here given X,Y ϵ I where X,Y are independent sets
Here the Bipartite Graph HM(X)
So there will be two graphs X, U\X
Now since it is a Matroid then U\X is a subset of X, in this case all the vertices of U\X are also
in X.
Now for perfect Matching the HM(X) should have cover having all vertices in the M, here since
according to the specifications maximal cover is there for HM(X) for M . So it has perfect
matching.
b) For Xϵ Y , there exists Y subset of U having h- |m(X) | contains a unique matching on
x∆y ,
Since according to the definition of Bipartite graph HM(X)
where (x,y) ϵ E if x ϵX , y ϵU\X
24

Design Analysis of Algorithm
And (X+y –x) ϵI
According to above specifications since (x,y) ϵ E if satisfying above conditions,
If h- |m(X) | contains a unique matching on x∆y , then it means all the vertices except m(X) or
cut of M(X) are matched, then since yϵU\X , and U is a subset of I , then YϵI.
Proof
Here it is given-
Set of points S subset of Rd
For each x ϵ S, weight w(x) ≥ 1 , label l(x) ϵ{0,1}
In order to remove the weakness of the hypothesis S in algorithm
We start with w(x) =1, for all S if w(x) =1 then there is no blocking and all the predictions are
correct
Now here labeling l( ) runs A for T= O( 1/η2log1/ε)
Outputs the Function
F(x) = majority (f1(x); f2(x); : : : ; fT (x)
fiϵ G, such that err s,l ,w (F) ≤ε
so by flowing the hedge analysis
L T –min (1..N) 1/η2log1/ε
25

Design Analysis of Algorithm
Solution
According to the Sherman –Morrison
Formula=
It is observed that the inverse of one rank updates the rank one to matrix inverse .
According to the above given specification
a) By the above specifications it is observed that the i≥1,
Since GO has perfect matching ,
Since G is Bipartite Graph , then its all the vertices are maximal covered as proved in previous
solutions .
Now according to this the addition of edge and removing the edge at each instant will be at each
Gi.
Now according to the rule-
26

Design Analysis of Algorithm
 A rank one update may change all the entries in the matrix by adding another matrix of
rank1.
 A rank K matrix (here G i) will also change in this manner.
 Operations on matrix will work accordingly.
Now since the graph is bipartite all the vertices will be fully covered with weight wi. So all the
set are completely matched.
Solution
A square matrix M K=0 for some positive integer K .
Then 0= det (M)k= det (M----M) (k times) = det (M)----det(M)= det (M)k
Mk . (MI) K= (M----M) (k times)=I
So by computing and putting the value for-
(1-M)-1= 1- (M----M) (k times)
So |(1-M)|-1= 1- (M----M) (k times)
So by computation
27

Design Analysis of Algorithm
Solution
For a directed Graph G , the number of directed walks from node i to j of length in arc.
Aij=1 if and only oif (I,j) is an arc in G
The adjacency matrix have at least one common vertices
So by above
Let graph G =(v1, v2-------vn)
Path = v1-v2, v2-v3, --------
So the no of (I,j) th entry = (v1-v2, v2-v3, --------)the entry
It will be O(nw).
By following the rule of calculating the run time. As the most general run time is 0( n+e) so here
as path is considered so the run time will be O(nw).
Where wi is path of graph..
(d) Show how to maintain these path counts under edge additions and deletions to the
graph, as long as
it remains a DAG. (Make sure you argue that you dont perform any operations that cause
matrices to
become singular, etc.) The time for each update should be O(n2).
Solution
As discussed above, the number of
Now according to the rule-
 A rank one update may change all the entries in the matrix by adding another matrix of
rank1.
 A rank K matrix (here G i) will also change in this manner.
 Operations on matrix will work accordingly.
 Follow directed graph rule
So by above rule the addition or deletions will be done by following above rule. As discussed
above for a directed graph , in order to maintain the these path counts under edge addition and
deletion and it remain a directed graph we have to perform following steps-
 Create the adjacency matrix in graph
 Maintain the counter to maintain the same number of edges so that directed graph cycle
be ,maintained.
28

Design Analysis of Algorithm
 Maintain an array of Boolean for true and false for transverse path
 By doing above operation we get the operation done in O(n2) time by the simple run
time .
Solution
Now it is given that the G is a Bipartite Graph , Where U is a subset of V , since all the vertices
in U are in V , they are fully covered so there is perfect matching.
Weight on Edge wE→R>0
W is isolating if the minimum-weight perfect in G is unique
For given cycle C
The U is subset of V , then the weight is same
Since here the cycle is given the starting and ending node will be same .
Independent size from the set is ≥2m
Then by the above specification the isolation exists and is according to above rule.
(b) Let h be a graph with n nodes and no cycles of length _ r and let r0 = 4 _ br=2c. Then
show that H has
at most n4 cycles of length _ r0
Here it is given that the Graph H has no of nodes = n
29

Design Analysis of Algorithm
Cycle = null ≤ r
r1= 4{r/4]
So by using this
Using rule for Bipartite graph
A Bipartite Graph does not contain odd no of cycles as it is a combination of two graphs ,
If the number of nodes(vertices)= n and given that there will be no cycle less than equal to r
Given-
r1= 4{r/4]
using the formula for calculating the no cycles in Graph
No cycle= k[r/2n]
No of cycles =n4
As by rule of cycle the number of vertices must be n4
Now as given it can be stated that H has at most n4 cycles of length ≤ r’. As it is minimum
required condition given for a cycle in H.
(c) Let C be a cycle in G such that imbw(G) 6= 0. Let E1 be the union of all minimum-weight
perfect
matchings in G. Show then that G1 = (U [ V;E1) does not contain a cycle in C.
Solution
We assume p be perfect matching polytype with
let x denote the point which is the average of all the
min-weight perfect matching’s in G.
if imbw© ≠0
then using the above specifications the new point weight will be less then associated node weight
so it will be cheaper. As the cost on the nodes are lesser now.
30

Design Analysis of Algorithm
Solution
Here it is given that the Graph H has no of nodes = n
Cycle = null ≤ r
Let r1= 4{r/4]
So by using this
Using rule
No cycle= k[r/2n]
No of cycles =n4
By using the same justification for cheaper cost,
The isolating weight will be of O(Log n2) by the rule of run time. So the probability of
randomness in it will be
1- O(log n)/n.
Using above the weight for run time will be of O(Log n2) , as given in the condition that for the
given Oracle O it uses the log( ns) random bits with no negative weights w for any set of cycles
{C1, C2, C3 ,--------Cs}
With
31

Design Analysis of Algorithm
Using above formulation the given condition is satisfied.
References
Bela .B, (2013), Modern Graph Theory, Springer Publication
V.K Balkrishnan, (2012), Introductory Discrete Mathematics, Dover Publication
Jean .G , (2011), Discrete Mathematics, Springer Publication
Jonathan.L, Jay . G, (2013), Graph Theory, CRC Publication
Richard.J , (2013), Introduction to Graph Theory, Kent University Press
32