Advance Algorithm FAQ Solution

Short Questions

[Link] are some important NP-complete problems?

Some important NP-Complete problems are:

1. Travelling Salesman Problem (TSP)

Find the shortest route to visit all cities once and return back.
2. Knapsack Problem
Choose items with maximum value without exceeding bag capacity.
3. Vertex Cover Problem
Select minimum vertices in a graph so every edge is connected to at least one selected vertex.
4. Hamiltonian Cycle Problem
Find a cycle that visits every vertex exactly once.
5. Graph Coloring Problem
Color graph vertices using minimum colors so adjacent vertices have different colors.
6. Subset Sum Problem
Check if some numbers from a set add up to a target value.
7. 3-SAT Problem
Determine if a logical formula can be satisfied with true/false values.

These problems are important because no fast algorithm is known to solve them efficiently for large inputs.

[Link] is an augmenting path in matching?

An augmenting path is a path that helps increase the number of matched pairs in a graph.

 It starts from an unmatched node

 Ends at another unmatched node
 By changing the connections on this path, we get one more matching.

Example

If:

 A is connected to B
 B is connected to C

and only A-B is matched, then path A → B → C can help match more nodes.

[Link]: Asymptotic notation

Asymptotic notation is a method used to describe the performance or time complexity of an algorithm
when the input size becomes very large.

It shows:

 how fast an algorithm runs

 or how much memory it uses
1|Page
Common types:

 Big O (O) → Worst case

 Omega (Ω) → Best case
 Theta (Θ) → Average/Exact growth rate

Example

If an algorithm takes time n2n^2n2, we write it as:

O(n2)O(n^2)O(n2)

This means the running time grows proportional to the square of input size.

[Link] is the Fibonacci sequence and how can it be calculated using dynamic programming?

The Fibonacci sequence is a series of numbers where each number is the sum of the previous two numbers.

Sequence:
0, 1, 1, 2, 3, 5, 8, 13 ...

Formula:

F(n)=F(n−1)+F(n−2)F(n)=F(n-1)+F(n-2)F(n)=F(n−1)+F(n−2)

Using Dynamic Programming

Dynamic Programming stores previous answers to avoid repeated calculations.

Steps:

1. Store first two values: 0 and 1

2. Add previous two numbers to get next number
3. Repeat until required term

This method is faster and more efficient than normal recursion.

[Link] is Bubble sort and what is its time complexity?

Bubble Sort is a simple sorting algorithm that repeatedly compares two adjacent elements and swaps them
if they are in the wrong order.

Example

Array: 5, 3, 8, 1

After sorting: 1, 3, 5, 8

Time Complexity

2|Page
  Best Case: O(n)O(n)O(n)
 Worst Case: O(n2)O(n^2)O(n2)

It is easy to understand but not efficient for large data.

6 .Define: Cook-Levin Theorem

The Cook-Levin Theorem is an important theorem in Computer Science and complexity theory.

It states that the Boolean Satisfiability Problem (SAT) is NP-Complete.

Meaning of the Theorem

The theorem proves two things:

1. SAT belongs to NP
o A proposed solution can be checked quickly (in polynomial time).
2. Every NP problem can be converted into SAT
o Any problem in NP can be transformed into a SAT problem in polynomial time.

Because of this, SAT became the first NP-Complete problem.

What is SAT?

SAT asks whether a logical formula can be made true by assigning values:

 True (1)
 False (0)

Example:

(A∨B)∧(¬A∨C)(A \lor B) \land (\neg A \lor C)(A∨B)∧(¬A∨C)

We check if some values of A, B, and C make the formula true.

Importance

 Foundation of NP-Complete theory

 Helps prove other problems are NP-Complete
 Used in optimization, AI, circuit design, and algorithms

Conclusion

The Cook-Levin Theorem showed that SAT is NP-Complete, meaning it is one of the hardest problems in
NP and every NP problem can be reduced to it.

[Link] is inapproximability?

3|Page
Inapproximability means that for some difficult problems, it is hard to find even a near-optimal
(approximate) solution efficiently.

In simple words:

 Some problems cannot be solved exactly in reasonable time.

 For certain problems, even getting a close answer is also very difficult.

Example

For some NP-Complete problems, no efficient algorithm can guarantee a good approximation unless:

P=NPP = NPP=NP

Importance

Inapproximability helps researchers understand:

 which problems are very hard,

 and how close we can get to the best solution.

[Link]: Selection sort.

Selection Sort is a simple sorting algorithm that repeatedly finds the smallest element from the unsorted part
of the array and places it at the correct position.

Steps

1. Find the smallest element

2. Swap it with the first element
3. Repeat for remaining elements

Example

Array: 64, 25, 12, 22, 11

After sorting: 11, 12, 22, 25, 64

Time Complexity

O(n2)O(n^2)O(n2)

Selection sort is easy to understand but not efficient for large datasets.

9 .Solve the recurrence relation: T(n) = T(n/2) + n.

[Link] is the algorithm used to compute maximum matching in a graph and how is maximum
matching characterized?
4|Page
The algorithm commonly used to compute maximum matching in a graph is the Hungarian Algorithm
(for bipartite graphs) and augmenting path methods like Ford-Fulkerson or Hopcroft-Karp Algorithm.

Maximum Matching

A matching is a set of edges where no two edges share the same vertex.

A maximum matching is a matching with the largest possible number of matched pairs.

Characterization of Maximum Matching

A matching is maximum if there is no augmenting path in the graph.

Simple Meaning

 If we cannot increase the number of matched pairs further, then the matching is maximum.
 Augmenting paths are used to improve the matching until no more improvement is possible.

[Link] is Ford-Fulkerson method?

The Ford-Fulkerson Method is an algorithm used to find the maximum flow in a flow network (graph).

It works by repeatedly finding an augmenting path from source to sink and increasing the flow through that
path.

Steps

1. Start with flow = 0

2. Find a path from source to sink
3. Add possible flow through that path
4. Repeat until no more augmenting path exists

Formula

Maximum flow is increased as:

Max Flow=∑flow through augmenting paths\text{Max Flow} = \sum \text{flow through augmenting
paths}Max Flow=∑flow through augmenting paths

Uses

 Network routing
 Traffic systems
 Transportation problems
 Bipartite matching

The method stops when no more flow can be added.

[Link]: LUP decomposition.

LUP Decomposition is a method in mathematics used to solve systems of linear equations.

5|Page
It decomposes a matrix into three matrices:

A=LUPA = LUPA=LUP

Where:

 L = Lower triangular matrix

 U = Upper triangular matrix
 P = Permutation matrix (used for row swapping)

Simple Meaning

It breaks a difficult matrix into simpler parts so calculations become easier and faster.

Uses

 Solving linear equations

 Finding matrix inverse
 Determinant calculation

Example Formula

A=LUPA=LUPA=LUP

[Link]: Maxflow-mincut theorem.

The Maxflow-Mincut Theorem states that:

The maximum flow passing from the source to the sink in a network is equal to the minimum cut capacity of
the network.

Simple Meaning

 Maximum Flow → Largest amount of flow that can move through the network.
 Minimum Cut → Smallest set of edges whose removal disconnects source and sink.

The theorem says both values are equal.

Formula

Maximum Flow=Minimum Cut Capacity\text{Maximum Flow} = \text{Minimum Cut

Capacity}Maximum Flow=Minimum Cut Capacity

Uses

 Network design
 Traffic routing
 Internet flow
 Transportation systems

[Link] is Edmonds’ Blossom algorithm ?

6|Page
The Edmonds’ Blossom Algorithm is an algorithm used to find maximum matching in a general graph.

It was developed by Jack Edmonds.

Simple Idea

Sometimes graphs contain a special cycle called a blossom (an odd-length cycle).
This algorithm shrinks the blossom into a single node and continues finding augmenting paths.

Purpose

 Finds the largest possible matching in a graph

 Works for both bipartite and non-bipartite graphs

Importance

It was the first efficient algorithm for maximum matching in general graphs.

Long Questions

[Link] is Topological Sorting? Write an algorithm to find topological

sorting of a graph. Describe with example.

Topological Sorting
Topological Sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every
directed edge:

u→vu \rightarrow vu→v

vertex u comes before v in the ordering.

Simple Meaning

If one task must be completed before another task, then topological sorting gives the correct order of tasks.

Applications

 Task scheduling
 Course prerequisite planning
 Project management
 Dependency resolution

7|Page
Example
Suppose we have these dependencies:

 A must be done before C

 B must be done before C
 C must be done before D

Graph:

A→C→D
B→C

One possible topological order is:

A, B, C, DA,\ B,\ C,\ DA, B, C, D

or

B, A, C, DB,\ A,\ C,\ DB, A, C, D

Both are correct.

Algorithm for Topological Sorting

(Using Indegree Method / Kahn’s Algorithm)

Steps

1. Find indegree of all vertices

(Indegree = number of incoming edges)
2. Put all vertices with indegree 0 into a queue
3. Remove a vertex from queue and add it to result
4. Reduce indegree of adjacent vertices by 1
5. If any vertex becomes indegree 0, add it to queue
6. Repeat until queue becomes empty

Pseudocode
TopologicalSort(G)

1. Calculate indegree of all vertices

2. Insert all vertices with indegree 0 into queue
3. While queue is not empty:
a. Remove vertex u
b. Print u
c. For each adjacent vertex v:
indegree[v]--
If indegree[v] == 0
insert v into queue

8|Page
Detailed Example
Consider graph:

A→CA \rightarrow CA→C B→CB \rightarrow CB→C C→DC \rightarrow DC→D

Step 1: Find Indegree

Vertex Indegree

A 0

B 0

C 2

D 1

Step 2: Insert indegree 0 vertices

Queue:

A, B

Step 3: Remove A

Result:

Reduce indegree of C:

C=1

Step 4: Remove B

Result:

A, B

Reduce indegree of C:

C=0

Add C to queue.

9|Page
Step 5: Remove C

Result:

A, B, C

Reduce indegree of D:

D=0

Add D to queue.

Step 6: Remove D

Result:

A, B, C, D

Final Topological Order

A, B, C, DA,\ B,\ C,\ DA, B, C, D

Important Points
 Topological sorting is possible only for DAG (Directed Acyclic Graph).
 If graph contains a cycle, topological sorting is not possible.

Time Complexity
Using queue and adjacency list:

O(V+E)O(V+E)O(V+E)

Where:

 VVV = number of vertices

 EEE = number of edges

[Link] selection sort algorithm to sort the characters of string 'advance

algorithms'.

10 | P a g e
Selection sort arranges characters by repeatedly selecting the smallest character and placing it at the correct
position.

Given string:

advance algorithms

Selection Sort Algorithm

SelectionSort(str)

1. Convert string into character array

2. For i = 0 to n-1
min = i

3. For j = i+1 to n
If str[j] < str[min]
min = j

4. Swap str[i] and str[min]

5. Repeat until all characters are sorted

Sorting the String

Original String:

advance algorithms

Sorted Characters:

aaacdeghilmnnoorrstv

(Spaces are also considered characters and come first in ASCII order.)

Time Complexity
O(n2)O(n^2)O(n2)

Selection sort is simple but slower for large strings or data.

[Link] and explain an algorithm to compute a maximum matching in a graph.

A matching in a graph is a set of edges where no two edges share the same vertex.

A maximum matching is the matching containing the largest possible number of edges.

Idea of the Algorithm

The algorithm repeatedly finds an augmenting path and increases the matching size.

An augmenting path:

11 | P a g e
  starts with an unmatched vertex
 ends with an unmatched vertex
 alternates between matched and unmatched edges

When such a path is found, we reverse the matched and unmatched edges to increase matching by 1.

Algorithm (Augmenting Path Method)

MaximumMatching(G)

1. Start with empty matching M

2. Find an augmenting path P in graph G

3. If no augmenting path exists

return M

4. Else
Reverse matched and unmatched edges along P
Update M

5. Repeat from Step 2

Step-by-Step Example
Consider graph:

A ----- 1
A ----- 2
B ----- 2
B ----- 3

Initially:

No edges matched.

Step 1

Choose edge:

A−1A - 1A−1

Matching:

M={(A,1)}M = \{(A,1)\}M={(A,1)}

Step 2

Find augmenting path:

12 | P a g e
B→2B \rightarrow 2B→2

Add it to matching.

Matching becomes:

M={(A,1),(B,2)}M = \{(A,1), (B,2)\}M={(A,1),(B,2)}

Final Maximum Matching

{(A,1),(B,2)}\{(A,1), (B,2)\}{(A,1),(B,2)}

No more augmenting paths exist.

So this is the maximum matching.

Important Points
 If no augmenting path exists, matching is maximum.
 Used in:
o Job assignment
o Network connections
o Bipartite graphs
o Scheduling problems

Time Complexity
Depends on the algorithm used.

For Hopcroft-Karp Algorithm:

O(VE)O(\sqrt{V}E)O(VE)

Where:

 VVV = number of vertices

 EEE = number of edges

[Link] all pairs shortest path problem. Explain how it can be solved using
dynamic programming.

All Pairs Shortest Path Problem (APSP)

The All Pairs Shortest Path Problem finds the shortest path between every pair of vertices in a graph.
13 | P a g e
Simple Meaning

For every vertex:

 find shortest distance to all other vertices.

Example
Suppose graph has vertices:

A, B, C

Edges:

 A→B=3
 B→C=2
 A → C = 10

Shortest path from A to C is:

A→B→CA \rightarrow B \rightarrow CA→B→C

Distance:

3+2=53 + 2 = 53+2=5

instead of 10.

Dynamic Programming Solution

(Floyd–Warshall Algorithm)

The APSP problem is solved using dynamic programming by gradually improving shortest paths.

Main Idea
Check whether using an intermediate vertex gives a shorter path.

Formula:

D[i][j]=min⁡(D[i][j], D[i][k]+D[k][j])D[i][j]=\min(D[i][j],\
D[i][k]+D[k][j])D[i][j]=min(D[i][j], D[i][k]+D[k][j])

Where:

14 | P a g e
  D[i][j]D[i][j]D[i][j] = shortest distance from iii to jjj
 kkk = intermediate vertex

Floyd–Warshall Algorithm
FloydWarshall(G)

1. Initialize distance matrix D

2. For each vertex k

For each vertex i
For each vertex j

3. If D[i][k] + D[k][j] < D[i][j]

D[i][j] = D[i][k] + D[k][j]

4. Return D

Example Matrix
Initial matrix:

A B C

A 0 3 10

B∞0 2

C∞∞0

Using B as intermediate:

A→B→CA \rightarrow B \rightarrow CA→B→C

Distance:

3+2=53 + 2 = 53+2=5

Update:

A B C

A0 3 5

B∞0 2

C∞∞0

15 | P a g e
Time Complexity
O(n3)O(n^3)O(n3)

Where nnn is number of vertices.

Applications
 GPS navigation
 Network routing
 Airline route systems
 Social networks

[Link] how all pairs shortest path problem is solved by using Floyd Warshall
algorithm.
he Floyd–Warshall Algorithm is a dynamic programming algorithm used to find the shortest paths
between all pairs of vertices in a weighted graph.

It works for:

 directed graphs
 undirected graphs
 graphs with negative edge weights
(but no negative cycles)

Main Idea
The algorithm checks whether a shorter path exists through an intermediate vertex.

Formula:

D[i][j]=min⁡(D[i][j], D[i][k]+D[k][j])D[i][j]=\min(D[i][j],\
D[i][k]+D[k][j])D[i][j]=min(D[i][j], D[i][k]+D[k][j])

Where:

 D[i][j]D[i][j]D[i][j] = shortest distance from vertex iii to vertex jjj

 kkk = intermediate vertex

16 | P a g e
Steps of Floyd–Warshall Algorithm
1. Create distance matrix from graph
2. Put:
o 0 for same vertices
o edge weight if edge exists
o ∞ if no edge exists
3. Select each vertex one by one as intermediate vertex
4. Update shortest distances using formula
5. Final matrix gives shortest paths between all pairs

Algorithm
FloydWarshall(G)

1. Initialize distance matrix D

2. For k = 1 to n
For i = 1 to n
For j = 1 to n

3. If D[i][k] + D[k][j] < D[i][j]

D[i][j] = D[i][k] + D[k][j]

4. Return D

Example
Consider graph:

 A→B=3
 B→C=2
 A → C = 10

Initial Distance Matrix

A B C

A 0 3 10

B∞0 2

C∞∞0

Using B as Intermediate Vertex

Check path:

A→B→CA \rightarrow B \rightarrow CA→B→C

17 | P a g e
Distance:

3+2=53 + 2 = 53+2=5

Since:

5<105 < 105<10

Update:

A B C

A0 3 5

B∞0 2

C∞∞0

Now shortest path from A to C is 5.

Final Shortest Paths

 A→B=3
 B→C=2
 A→C=5

Time Complexity
O(n3)O(n^3)O(n3)

Where:

 nnn = number of vertices

Advantages
 Simple and easy to implement
 Finds shortest paths between all vertices
 Handles negative edge weights

18 | P a g e
Applications
 Network routing
 GPS systems
 Airline route optimization
 Communication networks

6 .Sort the following data with Insertion Sort Method: 67, 75, 5, 50, 25, 20,
90, 45, and 90.
Insertion sort inserts each element into its correct position in the sorted part.

Step-by-Step Sorting
Pass 1

Insert 75 into sorted list [67]

67, 75, 5, 50, 25, 20, 90, 45, 90

Pass 2

Insert 5 into sorted list [67, 75]

5, 67, 75, 50, 25, 20, 90, 45, 90

Pass 3

Insert 50 into sorted list [5, 67, 75]

5, 50, 67, 75, 25, 20, 90, 45, 90

Pass 4

Insert 25 into sorted list [5, 50, 67, 75]

5, 25, 50, 67, 75, 20, 90, 45, 90

Pass 5

Insert 20 into sorted list [5, 25, 50, 67, 75]

5, 20, 25, 50, 67, 75, 90, 45, 90

19 | P a g e
Pass 6

Insert 90 into sorted list

5, 20, 25, 50, 67, 75, 90, 45, 90

Pass 7

Insert 45 into sorted list

5, 20, 25, 45, 50, 67, 75, 90, 90

Pass 8

Insert last 90 into sorted list

5, 20, 25, 45, 50, 67, 75, 90, 90

Final Sorted Data

5, 20, 25, 45, 50, 67, 75, 90, 90

Time Complexity

[Link] the applications of linear programming.

Linear Programming (LP) is a mathematical technique used to find the best solution (maximum profit or
minimum cost) under given constraints.

It is widely used in business, industry, engineering, and management.

Major Applications of Linear Programming

1. Production Planning

Helps industries decide:

 how much product to produce

 how to use raw materials efficiently

Example

A factory decides the number of chairs and tables to maximize profit.

20 | P a g e
2. Transportation Problems

Used to minimize transportation cost from factories to warehouses or customers.

Example

Finding the cheapest shipping routes.

3. Assignment Problems

Assigns jobs to workers or machines efficiently.

Example

Assigning employees to tasks with minimum cost or time.

4. Diet Problems

Used to prepare a balanced diet at minimum cost.

Example

Selecting food items containing required nutrients.

5. Business and Finance

Helps in:

 investment planning
 budget allocation
 profit maximization

Example

Choosing best investment options.

6. Network Flow Problems

Used in:

 internet routing
 traffic systems
 communication networks

21 | P a g e
7. Scheduling

Used for:

 employee scheduling
 machine scheduling
 project planning

8. Agriculture

Helps farmers decide:

 crop selection
 fertilizer usage
 land allocation

9. Military Applications

Used in:

 resource allocation
 transportation planning
 strategy optimization

Advantages of Linear Programming

 Maximizes profit
 Minimizes cost
 Efficient use of resources
 Improves decision making

Conclusion
Linear Programming is an important optimization technique used in many real-life problems to achieve the
best possible result under given conditions.

[Link] vertex cover and set cover problems. Explain with example how
vertex cover problem can be reduced to set cover problem.

22 | P a g e
[Link] vertex cover and set cover problems. Explain with example how
vertex cover problem can be reduced to set cover problem.

[Link] linear programming in brief?

Linear Programming is a mathematical method used to find the best possible solution for a problem under
given conditions or constraints.

It helps in:

 maximizing profit
 minimizing cost
 efficient use of resources

Main Components of Linear Programming

1. Objective Function

The function that needs to be maximized or minimized.

Example:

Z=5x+3yZ = 5x + 3yZ=5x+3y

where ZZZ is profit.

2. Constraints

Restrictions or limitations on resources.

Example:

x+y≤10x + y \leq 10x+y≤10

3. Decision Variables

Unknown quantities to be determined.

Example:

 xxx = number of tables

 yyy = number of chairs
23 | P a g e
Example
A factory produces tables and chairs.

Goal:

 maximize profit
 limited wood and labor available

Linear programming helps decide how many tables and chairs should be produced.

Applications
 Production planning
 Transportation
 Assignment problems
 Business optimization
 Scheduling
 Agriculture

Advantages
 Better decision making
 Efficient resource utilization
 Cost reduction
 Profit maximization

Conclusion
Linear Programming is an important optimization technique used to solve real-life business and engineering
problems efficiently.

[Link] is triangular matrix with example?

Triangular Matrix
A triangular matrix is a square matrix in which all elements either above or below the main diagonal are
zero.

There are two types:

24 | P a g e
1. Upper Triangular Matrix
In an upper triangular matrix, all elements below the main diagonal are zero.

Example:

[123045006]\begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix}100240356

Here, all elements below the diagonal are 0.

2. Lower Triangular Matrix

In a lower triangular matrix, all elements above the main diagonal are zero.

Example:

[100230456]\begin{bmatrix} 1 & 0 & 0 \\ 2 & 3 & 0 \\ 4 & 5 & 6 \end{bmatrix}124035006

Here, all elements above the diagonal are 0.

Important Point
The main diagonal contains elements from top-left to bottom-right.

Uses
 Solving linear equations
 Matrix decomposition
 Numerical computations
 Computer algorithms

[Link] is residual network and how it is constructed? Explain with

example.
A Residual Network is a graph used in the Graph Theory maximum flow problems to show how much
additional flow can still pass through the network.

It is mainly used in the Computer Science Ford–Fulkerson method.

25 | P a g e
Simple Meaning
Residual network tells:

 how much capacity is left in each edge

 where more flow can still be sent

Residual Capacity
Residual capacity is calculated as:

Residual Capacity=Capacity−FlowResidual\ Capacity = Capacity - FlowResidual Capacity=Capacity−Flow

Construction of Residual Network

For every edge (u,v)(u,v)(u,v):

1. Add a forward edge with remaining capacity:

c(u,v)−f(u,v)c(u,v)-f(u,v)c(u,v)−f(u,v)

2. Add a backward edge with capacity:

f(u,v)f(u,v)f(u,v)

where:

 c(u,v)c(u,v)c(u,v) = capacity
 f(u,v)f(u,v)f(u,v) = current flow

Example
Suppose we have edge:

S→AS \rightarrow AS→A

Capacity:

101010

Current flow:

666

26 | P a g e
Step 1: Forward Edge
Remaining capacity:

10−6=410 - 6 = 410−6=4

Residual edge:

S→A=4S \rightarrow A = 4S→A=4

Step 2: Backward Edge

Backward residual edge:

A→S=6A \rightarrow S = 6A→S=6

Residual Network
S ----4----> A
A ----6----> S

Purpose of Backward Edge

Backward edge helps:

 reduce previous flow if needed

 reroute flow through better paths

Applications
 Maximum flow problems
 Network routing
 Transportation systems
 Internet traffic management

Conclusion
Residual network represents the remaining flow capacity in a graph and helps algorithms find augmenting
paths to increase maximum flow.

27 | P a g e
[Link] with example the process of LU decomposition of a given
matrix.

LU Decomposition
LU Decomposition is a method of decomposing a matrix into:

A=LUA = LUA=LU

Where:

 LLL = Lower triangular matrix

 UUU = Upper triangular matrix

It is used to solve systems of linear equations easily.

Example
Given matrix:

A=[2347]A= \begin{bmatrix} 2 & 3 \\ 4 & 7 \end{bmatrix}A=[2437]

We want to find:

A=LUA = LUA=LU

Step 1: Assume Forms of L and U

Lower triangular matrix:

L=[10l211]L= \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix}L=[1l2101]

Upper triangular matrix:

U=[u11u120u22]U= \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}U=[u110u12u22]

Step 2: Multiply L and U

LU=[10l211][u11u120u22]LU= \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} \\ 0
& u_{22} \end{bmatrix}LU=[1l2101][u110u12u22]

Result:

=[u11u12l21u11l21u12+u22]= \begin{bmatrix} u_{11} & u_{12} \\ l_{21}u_{11} & l_{21}u_{12}+u_{22}

\end{bmatrix}=[u11l21u11u12l21u12+u22]
28 | P a g e
Compare with original matrix:

[2347]\begin{bmatrix} 2 & 3 \\ 4 & 7 \end{bmatrix}[2437]

Step 3: Find Values

From comparison:

u11=2u_{11}=2u11=2 u12=3u_{12}=3u12=3 l21u11=4l_{21}u_{11}=4l21u11=4 l21(2)=4l_{21}(2)=4l21(2)=4

l21=2l_{21}=2l21=2

Now:

l21u12+u22=7l_{21}u_{12}+u_{22}=7l21u12+u22=7 2(3)+u22=72(3)+u_{22}=72(3)+u22=7 6+u22=76+u_{22}=76+u22

=7 u22=1u_{22}=1u22=1

Final Matrices
Lower triangular matrix:

L=[1021]L= \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}L=[1201]

Upper triangular matrix:

U=[2301]U= \begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}U=[2031]

Verification
LU=[1021][2301]=[2347]LU= \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} 2 & 3 \\ 0 & 1
\end{bmatrix} = \begin{bmatrix} 2 & 3 \\ 4 & 7 \end{bmatrix}LU=[1201][2031]=[2437]

which is equal to matrix AAA.

Applications
 Solving linear equations
 Matrix inversion
 Numerical analysis
 Engineering computations

[Link] flow and flow network.

29 | P a g e
Flow
A flow is the amount of material, data, or quantity passing through edges of a network from a source to a
sink.

Examples:

 Water flowing through pipes

 Data flowing through computer networks
 Traffic moving through roads

The flow on an edge cannot exceed its capacity.

Flow Network
A Flow Network is a directed graph where:

 each edge has a capacity

 flow moves from a source node to a sink node

It is represented as:

G=(V,E)G = (V,E)G=(V,E)

Where:

 VVV = set of vertices

 EEE = set of edges

Important Components
1. Source (S)

Starting point of flow.

2. Sink (T)

Ending point of flow.

3. Capacity

Maximum flow allowed through an edge.

Example
S ----10----> A ----5----> T

30 | P a g e
  Source = S
 Sink = T
 Capacity of edge S→A = 10
 Capacity of edge A→T = 5

Maximum possible flow to T is 5.

Applications
 Internet routing
 Transportation systems
 Water supply networks
 Maximum flow problems

[Link] divide and conquer paradigm with any one of algorithm.

Divide and Conquer Paradigm

Divide and Conquer is an algorithm design technique in which a problem is divided into smaller
subproblems, solved separately, and then combined to get the final solution.

Steps of Divide and Conquer

1. Divide

Break the problem into smaller subproblems.

2. Conquer

Solve the subproblems recursively.

3. Combine

Combine the solutions of subproblems to get the final answer.

Example Algorithm: Merge Sort

Merge Sort uses divide and conquer to sort elements.

Working of Merge Sort

Given array:

31 | P a g e
38, 27, 43, 3, 9, 82, 10

Step 1: Divide

Split array into smaller parts:

[38,27,43,3] [9,82,10]

Again divide until single elements remain.

Step 2: Conquer

Sort smaller arrays recursively.

Step 3: Combine

Merge sorted arrays:

3, 9, 10, 27, 38, 43, 82

Merge Sort Algorithm

MergeSort(A)

1. If array size is 1
return

2. Divide array into two halves

3. Recursively sort left half

4. Recursively sort right half

5. Merge both sorted halves

Time Complexity
O(nlog⁡n)O(n\log n)O(nlogn)

Advantages
 Efficient for large data
 Faster than simple sorting methods
 Easy to understand

32 | P a g e
Applications
 Sorting large files
 Searching
 Parallel processing
 Data analysis

Conclusion
Divide and Conquer solves complex problems efficiently by dividing them into smaller manageable parts
and combining their solutions.

33 | P a g e