Algorithms Notes

mobiprep (6).png

Algorithm Basics

mobiprep (6).png

Divide And Conquer

mobiprep (6).png

Greedy Algorithm

mobiprep (6).png

Dynamic Programming

mobiprep (6).png

Shortest Path

mobiprep (6).png

Backtracking

mobiprep (6).png

Minimum Spanning Tree

mobiprep (6).png

Maximum Flow

mobiprep (6).png

Complexity Classes

Heading

Q

1

Explain Network Flow Problems

LRM_EXPORT_207556595493866_20190724_1939

Ans

The most obvious flow network problem is the following:

Problem1: Given a flow network G = (V, E), the maximum flow problem is to find a flow with maximum value.

Problem 2: The multiple source and sink maximum flow problem is similar to the maximum flow problem, except there is a set {s1,s2,s3.......sn} of sources and a set {t1,t2,t3..........tn} of sinks.

Fortunately, this problem is no solid than regular maximum flow. Given multiple sources and sink flow network G, we define a new flow network G' by adding

A super source s,
A super sink t,
For each si, add edge (s, si) with capacity ∞, and
For each ti,add edge (ti,t) with capacity ∞

Figure shows a multiple sources and sinks flow network and an equivalent single source and sink flow network

LRM_EXPORT_207556595493866_20190724_1939

Q

2

Explain Maximum Bipartite Matching

LRM_EXPORT_207556595493866_20190724_1939

Ans

A Bipartite Graph is a graph whose vertices can be divided into two independent sets L and R such that every edge (u, v) either connect a vertex from L to R or a vertex from R to L. In other words, for every edge (u, v) either u ∈ L and v ∈ L. We can also say that no edge exists that connect vertices of the same set.
Maximum Bipartite Matching

Matching is a Bipartite Graph is a set of edges chosen in such a way that no two edges share an endpoint. Given an undirected Graph G = (V, E), a Matching is a subset of edge M ⊆ E such that for all vertices v ∈ V, at most one edge of M is incident on v.

A Maximum matching is a matching of maximum cardinality, that is, a matching M such that for any matching M', we have|M|>|M' |.

LRM_EXPORT_207556595493866_20190724_1939