b"
The efficiency analysis of many divide-and-conquer algorithms is greatly simplified by the use of Master
theorem.
10. What is the general divide-and-conquer recurrence relation?
An instance of size ‘n’ can be divided into several instances of size n/b, with ‘a’ of them needing to be
solved. Assuming that size ‘n’ is a power of ‘b’, to simplify the analysis, the following recurrence for the
running time is obtained:
T(n) = aT (w/b) +4(n)
Where fn) is a function that accounts for the time spent on dividing the problem into smaller ones and on
combining their solutions.
11. Define mergesort.
Mergesort sorts a given array A[0..n-1] by dividing it into two halves a[0..(n/2)-1] and A[n/2..n-1] sorting
each of them recursively and then merging the two smaller sorted arrays into a single sorted one.
12. List the Steps in Merge Sort
1. Divide Step: If given array A has zero or one element, return S; it is already sorted. Otherwise,
divide A into two arrays, Al and A2, each containing about half of the elements of A.
2. Recursion Step: Recursively sort array A1 and A2.
3. Conquer Step: Combine the elements back in A by merging the sorted arrays Al and A2 into a
sorted sequence
13. List out Disadvantages of Divide and Conquer Algorithm:
* Conceptual difficulty
* Recursion overhead
+ Repeated subproblems
14, Define Quick Sort
Quick sort is an algorithm of choice in many situations because it is not difficult to implement, it is a good
" general purpose\" sort and it consumes relatively fewer resources during execution.
15. List out the Advantages in Quick Sort
Itis in-place since it uses only a small auxiliary stack.
It requires only n log(n) time to sort n items.
Ithas an extremely short inner loop
This algorithm has been subjected to a thorough mathematical analysis, a very precise statement
can be made about performance issues.
16. List out the Disadvantages in Quick Sort
+ Itis recursive. Especially if recursion is not available, the implementation is extremely complicated
+ Itrequires quadratic (i., n2) time in the worst-case.
+ It is fragile ic., a simple mistake in the implementation can go unnoticed and cause it to perform
badly.
17. What is the difference between quicksort and mergesort?
Both quicksort and mergesort use the divide-and-conquer technique in which the given array is partitioned
into subarrays and solved. The difference lies in the technique that the arrays are partitioned. For mergesort
the arrays are partitioned according to their position and in quicksort they are partitioned according to the
element values. 18. What is binary search?
Binary search is a remarkably efficient algorithm for searching in a sorted array. It works by comparing a
search key K with the arrays middle element A{m]. If they match the algorithm stops; otherwise the same
operation is repeated recursively for the first half of the array if K < A{m] and the second half if K >
Alm],
K
AO]... ‘AnahntaeeAl, ALN]
‘soarch bow i Kem] atch hore #KSAtm]
19. List out the 4 steps in Strassen’s Method?
1. Divide the input matrices A and B into n/2 * n/2 submatrices, as in equation (1).
2, Using @(n2) scalar additions and subtractions, compute 14 n/2 * n/2 matrices Al, BI, A2, B2, ..., A7, B7.
3. Recursively compute the seven matrix products Pi =AiBi for i =1, 2,7
4, Compute the desired submatrices 1, s, t, u of the result matrix C by adding and/or subtracting various
combinations of the Pi matrices, using only @(n2) scalar additions and subtractions.
16 marks
1. Explain Divide And Conquer Method
Y The most well known algorithm design strategy is Divide and Conquer Method. It
* Divide the problem into two or more smaller subproblems.
* Conquer the subproblems by solving them recursively.
* Combine the solutions to the subproblems into the solutions for the original problem.
Sey
STN ere)
Bey Bere)
Sra Cy Pn)
ST STL
Perm)
Ca
Y Divide and Conquer Examples
© Sorting: mergesort and quicksort
# Tree traversals © Binary search
* Matrix multiplication-Strassen’s algorithm
Explain Merge Sort with suitable example.
Merge sort definition,
Mergesort sorts a given array A[0..n-1] by dividing it into two halves a[0..(n/2)-1] and A[n/2..n-1]
sorting each of them recursively and then merging the two smaller sorted arrays into a single sorted
on
Steps in Merge Sort
1. Divide Step
If given array A has zeto or one clement, return §; it is already sorted. Otherwise, divide A
into two arrays, Al and A2, each containing about half of the elements of A.
2. Recursion Step
Recursively sort array Al and A2.
3. Conquer Step
Combine the elements back in A by merging the sorted arrays Al and A2 into a sorted
sequence
Algorithm for merge sort.
ALGORITHM Mergesort(A[0..0-1))
//Sorts an array A[0..n-1] by recursive mergesort
/input: An array A[0..n-1] of orderable elements
(Output: Array A[0..n-1] sorted in nondecreasing order
ifn>1
copy A(0..(n/2)-1] to B[0..(n/2)-1]
copy Af(a/2)..0-1] to C[0.(n/2)-1]
Mergesort(B[0..(n/2)-1])
Mergesort(C[0..n/2)-1})
Merge(B,C,A)
Algorithm to merge two sorted arrays into one.
ALGORITHM Merge (B [0..p-1], C[0..¢-1], A[0..p+q-1])
!/Merges two sorted arrays into one sorted array
/MInput: arrays B[0..p-1] and C[0..q-1] both sorted
Output: sorted array A [0..p+q-1] of the elements of B & C
1 0;j O;k 0
while I A[s]. (Computing the index of s is
part of partition.)
«Implication: A[s] will be in its final position in the sorted array.
* Conquer: Sort the two subarrays A(]..s-1] and A[s+1.1] by recursive calls to quicksort
* Combine: No work is needed, because A[s] is already in its correct place after the partition is
done, and the two subarrays have been sorted.
Steps in Quicksort
# Select a pivot w.r-. whose value we are going to divide the sublist. (e.g., p = A[I)
Rearrange the list so that it starts with the pivot followed by a < sublist (a sublist whose elements
are all smaller than or equal to the pivot) and a > sublist (a sublist whose elements are all greater than
‘or equal to the pivot ) Exchange the pivot with the last element in the first sublist(i.e., < sublist) — the
pivot is now in its final position
# Sort the two sublists recursively using quicksort.
ALL
=p //left-right scan
repeat j €j—1 until A{j] <= p//right-left scan
if(i=j {ino need to scan
swap(A[l], Afi)
retum j
Y Advantages in Quick Sort
+ It is in-place since it uses only a small auxiliary stack.
+ It requires only n log(n) time to sort n items
+ Ithas an extremely short inner loop + This algorithm has been subjected to a thorough mathematical analysis, a very precise statement can be
made about performance issues.
Y Disadvantages in Quick Sort
+ IL is recursive. Especially if recursion is not available, the implementation is extremely complicated.
+ It requires quadratic (i.e., n2) time in the worst-case.
+ It is fragile i.e., a simple mistake in the implementation can go unnoticed and cause it to perform badly.
Y Efficiency of Quicksort
Based on whether the partitioning is balanced.
Best case: split in the middle — @( n log 7)
Cin) = 2C(n/2) + O(n) 1/2 subproblems of size n/2 each
Worst case: sorted array! — @( n’)
C(n) = C(n-1) + n+1 2 subproblems of size 0 and n-1 respectively
Average case: random arrays — @( n log n)
4, Explain Binary Search.
Y Binary Search Iterative Algorithm
ALGORITHM BinarySearch(A(0..n-1], K)
Implements nonrecursive binary search
//Input: An array A[0..n-1] sorted in ascending order and
i a search key K
(Output: An index of the array’s element that is equal to K
u or-I if there is no such element
1€0,r€n-1
while 1 r base case 1:1 and r cross over> can’t find K
return —1
else
m€ (49/2,
if = A[m] ase case 2: K is found
return m
else general case: divide the problem.
ifK m) can be
modeled as the multiplication of 2 n-digit integers (by padding n — m Os before the
first digit of the m-digit integer)
© Brute-force algorithm
oo Cor oo Agr
co en ayo an
qo * boo + aor * Bro agg * bor + aor * bir
a10* boo + an * bro ayo * bor + an * bir
8 multiplications
© 4additions
© Efficiency class: @ (n3)
¥ Strassen’s Algorithm (two 2x2 matrices)
C00 Cor 0 or 00 bor
cio Jaro a bio bi
mf my -tps+ my,
m+ my
my = (@o0 + an) * (boo + bin)
m2 = (ajo + a11) * boo
m3 = ago * (bor - bui)
my= a1 * (bio boo)
ms = (ayo + ag)) * Bat
rmg= (ayo - ago) * (boo * bos)
my = (@} + a11) * (byo + bir)
+ Efficiency of Strassen’s Algorithm
©. Ifn isnot a power of 2, matrices can be padded with rows and columns with zeros
© Number of multiplications
© Number of additions
© Other algorithms have improved this result, but are even more complex
6. Explain in detail about Travelling Salesman Problem using exhaustive search.
Given » cities with known distances between each pair, find the shortest tour that passes through all
the cities exactly once before returning to the starting city Alternatively: Find shortest Hamiltonian circuit in a weighted connected graph
Example :
Tour
aoboeodoa 2434745 = 17
ahdoea 2444748 = 21
aceobodoa 8431445 = 20
aed boa 21
acdsboea 20
asdsesboa 17
Efficiency: @((n-1)!)
7. Explain in detail about knapsack problem.
Given n items:
weights: wy Wy. Wh
values: V2 Vy
a knapsack of capacity 7
Find most valuable subset of the items that fit into the knapsack
Example: Knapsack capa
item _weight value
2 $20
5 $30
10 $50
5 $10
Subset_Total weight _ Total value
{1} 2 $20
2} 5 $30
8} 10 $50
{4} 5 $10
{12} 7 $50
413} 12 $70
{1,4} 7 $30
42,3) 15 $80
42.4} 10 $40
3.4} $60
{1,23} 17 not feasible
{1.2.4} 12 $60 {13,4} 17 not feasible
{2.3.4} 20 not feasible
41,2,3,4} 22 not feasible
Efficiency: @2*n)
8. Explain in detail about closest pair problem.
Find the two closest points in a set of n points (in the two-dimensional Cartesian plane).
Brute-force algorithm
mmpute the distance between every pair of distinet points and retum the indexes of the points for which
the distance is the smallest.
ALGORITHM = BruteForceClosestPoinis(P)
/Anput: A list P of n (n > 2) points Py =
//Output: Indices index and index? of the closest pair of points
dmin —o
fori —lteon-1do
for j -i+1tondo
d < sqrt ((x; — x)? + 0; — ¥,)) sqrt is the square root function
ifd
/Output: Er, the set of edges composing a minimum spanning tree of G.
Sort F in nondecreasing order of the edge weights
En ondecresing oe
Er €@ ecounter €0 initialize the set of tree edges and its size
ke
while encounter < |V|- 1 do
kEek+1
if Er U feu} is acyclic
Er € EU {ex} ; counter ecounter + 1
return Ey
3. Discuss Prim's Algorithm
¥ Minimum Spanning Tree (MST)
© Spanning tree of a connected graph G: a connected acyclic subgraph (tree) of G that includes
all of G’s vertices.
Minimum Spanning Tree of a weighted, connected graph G: a spanning tree of G of
minimum total weight.
Example:
Prim’s MST algorithm
Y Start with a tree , To ,consisting of one vertex
Y “Grow” tree one vertex/edge at a time
© Construct a series of expanding su trees Ty, Tz, ... Tp, At each stage construct Tie; from T;
y = adding the minimum weight edge connecting a vertex in tree (T;) to one not yet in tree
+ choose from “fringe” edges
(this is the “greedy” step!) Or (another way to understand it)
expanding each tree (Ti) in a greedy manner by attaching to it the nearest vertex not in that tree. (a
vertex not in the tree connected to a vertex in the tree by an edge of the smallest weight)
Algorithm stops when all vertices are included
Algorithm:
ALGORITHM Prim(G)
//Prim’s algorithm for constructing a minimum spanning tree
Input A weighted connected graph G= V, E
Output Er, the set of edges composing a minimum spanning tree of G
Vr {v0}
EF
for i€1 to [V|-1 do
(v*,u*) among all the edges (v,u) such that v is in Vy and wis in
return Ep
Write short note on Greedy Method
A greedy algorithm makes a locally optimal choice in the hope that this choice will lead to a globally
optimal solution.
© The choice made at each step must be:
> Feasible
= Satisfy the problem’s constraints
© locally optimal
= Be the best local choice among all feasible choices
0 Imevocable
= Once made, the choice can’t be changed on subsequent steps.
Y Applications of the Greedy Strategy
‘© Optimal solutions
= change making
= Minimum Spanning Tree (MST)
= Single-source shortest paths
= Huffman codes
© Approximations
= Traveling Salesman Problem (TSP)
= Knapsack problem
= other optimization problems
5. What does dynamic programming has in common with divide-and-Conquer?
¥ Dynamic Programming
Dynamic Programming is a general algorithm design technique. “Programming” here means
“planning”.
Invented by American mathematician Richard Bellman in the 1950s to solve optimization
problems
© Main idea:
a. solve several smaller (overlapping) subproblems
b. record solutions in a table so that each subproblem is only solved once ¢. final state of the table will be (or contain) solution
* Dynamic programming vs. divide-and-conquer
a. partition a problem into overlapping subproblems and independent ones
b. store and not store solutions to subproblems
¥ Example: Fibonacci numbers
Recall definition of Fibonacci numbers:
f0) = 0
fuy=1
fa) = lal) + fr-2)
co Computing the n" Fibonacci number recursively (top-down):
fin)
An-2)
A
re ——
fn-3) + fwd)
Computing the n™ fibonacci number using bottom-up iteration:
AO) = 0
fly =1
f2)=0+1=1
fi3) = 141 =2
fla) = 142-3
AS) = 243 =5
fin-2) =
Aan-l)=
Aan) = fln-l) + fln-2)
ALGORITHM Fib(n)
F(0] € 0, F[I] € 1
for i€2 ton do
Fi) € F[i-l] + F[i-2]
return F[n]
6. Disuss Warshall’s Algorithm with suitable diagrams?
* Main idea: Use a bottom-up method to construct the transitive closure of a given digraph with n
vertices through a series of nxn boolean matrices:
RO RED) RD Re
RY rr = 1 in R , iff
there is an edge from i to j; or
there is a path from i to j going through vertex 1; or
there is a path from i to j going through vertex 1 and/or 2; or
there is a path from i to j going through 1, 2, ... and/or k R®
2
0010 R
0010
1001
1011 1011
foo0 0000 0000
e100 0100 1iit
Does not allow an| row 1 to be an [Allow 1,2 to be an
an
intermediate node intermediate node intermediate node
R®
0010 0010
lou a4
0000 0000
1idd lidd
Allow 1,2,3 to be an intermediate
Allow 1,2,3,4 to be an
node intermediate node
In the k" stage: to determine R™ is to determine if a path exists between two vertices i, j using
just vertices among 1,....k
| (path using just 1 ,...,k-1)
r= or
(ru? = 1 and ry?) =1 (path from ito k
and from k toi
using just 1 ,....A-1)
7. Explain how to Floyd’s Algorithm works.
+ All pairs shortest paths problem: In a weighted graph, find shortest paths between every pair of
vertices.
+ Applicable to: undirected and directed weighted graphs; no negative weight.
+ Same idea as the Warshall’s algorithm : construct solution through series of matrices D(0) , D(1), ...,
4
063
0” n
10 65
Weight matrix "distance matrix
+ D(k) : allow 1, 2, ..., k to be intermediate vertices,
+ In the kth stage, determine whether the introduction of k as a new eligible intermediate vertex will
bring about a shorter path from i to j.
+ dij(k) = min {dij(k-1) , dik(k-l) + dkj(k-1} fork > 1, dij(0) = wij aye) @
8. Explain Knapsack problem
¥ The problem
+ Find the most valuable subset of the given n items that fit into a knapsack of capacity W.
¥ Consider the following sub problem P(, j)
Find the most valuable subset of the first i items that fit into a knapsack of capacity j,
where 1 $i¢n,and 1s j m) is obtained by setting n — m
variables to 0 and solving the resulting system to get the values of the other m variables. The variables
set to 0 are called nonbasic; the variables obtained by solving the system are called basic.
A basic solution is called feasible if all its (basic) variables are nonnegative
3. Define flow and flow conservation requirement.
A flow is an assignment of real numbers x; to edges (i) of a given network that satisfy the following:
* flow-conservation requirements: The total amount of material entering an intermediate vertex
must be equal to the total amount of the material leaving the vertex
Dy = L xy fori=2,3,..., 0-1
EGINCE fGjeE
© capacity constraints
O m) is obtained by setting » — m
variables to 0 and solving the resulting system to get the values of the other m variables. The variables
set to 0 are called nonbasic; the variables obtained by solving the system are called basic.
A basic solution is called feasible if all its (basic) variables are nonnegative
Example x+ y+u 4
xt3y ty =6
(0, 0, 4, 6)is basic feasible solution
(x,y are nonbasic; 1, » are basic)
There is a 1-1 correspondence between extreme points of LP’s feasible region and its basic feasible
solutions.
maximize z= 3x + Sy +0u+0v
subject to xtytu
xt3y +
220, y20, u20, 20 Simplex method:
Step 0 [Initialization] Present a given LP problem in standard form and set up initial tableau.
Step 1 [Optimality test] If all entries in the objective row are nonnegative — stop: the tableau represents
an optimal solution.
Step 2 [Find entering variable] Select (the most) negative entry in the objective row. Mark its column to
indicate the entering variable and the pivot column,
Step 3 [Find departing variable] For each positive entry in the pivot column, calculate the @-ratio by
dividing that row's entry in the rightmost column by its entry in the pivot column. (If there are no
positive entries in the pivot column — stop: the problem is unbounded.) Find the row with the smallest
@-ratio, mark this row to indicate the departing variable and the pivot row.
Step 4 [Form the next tableau] Divide all the entries in the pivot row by its entry in the pivot column.
Subtract from each of the other rows, including the objective row, the new pivot row multiplied by the
entry in the pivot column of the row in question, Replace the label of the pivot row by the variable's
name of the pivot column and go back to Step 1
maximize z= 3x+5y+0u+0v
subject to xt ytu
xtay +
x20, y20, u20, v20
busie feusible sol.
(3,1, 9, 0)
2. Explain in detail about maximum flow problem.
Maximum Flow Problem
Problem of maximizing the flow of a material through a transportation network (c.g., pipeline system,
‘communications or transportation networks) Formally represented by a connected weighted digraph with n vertices numbered from 1 ton with the
following properties:
+ contains exactly one vertex with no entering edges, called the source (numbered 1)
+ contains exactly one vertex with no leaving edges, called the sink (numbered n)
+ has positive integer weight uy on each directed edge (i,/), called the edge capacity,
indicating the upper bound on the amount of the material that can be sent from
this edge
Source
(a
Definition of flow:
A flow is an assignment of real numbers xy to edges (ij) of a given network that satisfy the following:
* flow-conservation requirements: The total amount of material entering an intermediate vertex
must be equal to the total amount of the material leaving the vertex
Lx = L xy fori=2,3,..., 0-1
FEGINCE jz: Geek
* capacity constraints
0 SxjSuj for every edge (i,) E
Flow value and Maximum Flow Problem
Since no material can be lost or added to by going through intermediate vertices of the network, the total
amount of the material leaving the source must end up at the sink:
Lexy = L yn
Ree jGunyek
The value of the flow is defined as the total outflow from the source (= the total inflow into the sink).
Maximum-Flow Problem as LP problem
Maximize v = 5 xj
jj) © subject to
Tx - Uxy =O for i=2, 3,...,.n-1
EGIEE fGjel£
OSx,;Suy for every edge (ij) ¢ E
Augmenting Path (Ford-Fulkerson) Method
Start with the zero flow (xj = 0 for every edge)
On each iteration, try to find a flow-augmenting path from source to sink, which a path along
which some additional flow can be sent
If a flow-augmenting path is found, adjust the flow along the edges of this path to get a flow of
increased value and try again
If no flow-augmenting path is found, the current flow is maximum,
ia
Augmenting path: 1-2 3 6 max flow value = 3 Finding a flow-augmenting path
To find a flow-augmenting path for a flow x, consider paths from source to sink in the underlying undi
graph in which any two consecutive vertices i, are either:
+ connected by a directed edge (i to /) with some positive unused capacity r= uy — xy
— known as forward edge (>)
OR
+ connected by a directed edge (j to i) with positive flow x:
— known as backward edge (—)
If a flow-augmenting path is found, the current flow can be increased by r units by increasing x, by r on
each forward edge and decreasing x» by r on each backward edge, _ where
r = min {ry on all forward edges, x, on all backward edges}
Assuming the edge capacities are integers, r is a positive integer
‘On each iteration, the flow value increases by at least 1
Maximum value is bounded by the sum of the capacities of the edges leaving the soure
the augmenting-path method has to stop after a finite number of iterations
The final flow is always maximum, its value doesn’t depend on a sequence of augmenting paths
used
The augmenting-path method doesn’t prescribe a specific way for generating flow-augmenting
paths
* Selecting a bad sequence of augmenting paths could impact the method’s efficiency
Example:
o/U
@
U = large positive integer Example 2 (cont.)
uA uu
a
"Aa
Cy
~~ Requires 2U iterations to reach
maximum flow of value 2U
Shortest-Augmenting-Path Algorithm
Generate augmenting path with the least number of edges by BFS as follows
Starting at the source, perform BFS traversal by marking new (unlabeled) vertices with two labels:
+ first label — indicates the amount of additional flow that can be brought from the source to the
vertex being labeled
second label — indicates the vertex from which the vertex being labeled was reached, with “+” or “” added
to the second label to indicate whether the vertex was reached via a forward or backward cee
* The source is always labeled with 0,-
* All other vertices are labeled as follow:
© If unlabeled vertex j is connected to the front vertex i of the traversal queue by a directed
edge fiom to / with positive unused capacity ry = uy —xy (forward edge), vertex j is labeled
with J,i°, where J) = min{/, ry}
If unlabeled vertex j is connected to the front vertex i of the traversal queue by a directed
edge from j to i with positive flow xj; (backward edge), vertex j is labeled /j,°, where lj =
min{l, x)
* If the sink ends up being labeled, the current flow can be augmented by the amount indicated by the
sink’s first label The augmentation of the current flow is performed along the augmenting path traced by following
the vertex second labels from sink to source; the current flow quantities are increased on the forward
edges and decreased on the backward edges of this path
If the sink remains unlabeled after the traversal queue becomes empty, the algorithm retums the
current flow as maximum and stops
Queue: 143256 Queue: 14
Definition of a Cut:
Let X be a set of vertices in a network that includes its source but does not include its sink, and let X, the
complement of X, be the rest of the vertices including the sink, The cut induced by this partition of the
vertices is the set of all the edges with a tail in X and a head in X.
Capacity of a cut is defined as the sum of capacities of the edges that compose the cut.
We'll denote a cut and its capacity by C(X,X) and e(X,X)
Note that if all the edges of +a cut’ were deleted from the
network, there would be no directed path from source to sink
Minimum cut is a cut of the smallest capacity in a given network
Examples of network cuts
y
S/
4,
IX = {1} and X = {2,3,4,5,6}, CO%X) = {(1,2), 4}, 0= 5
