1.
define multi stage graph and its applications
A Multi-Stage Graph is a directed graph for which
The vertices are divided into multiple stages (or levels).
All edges are directed from a vertex in one stage to a vertex in the next stage only (no backward or
same-stage edges).
It is usually acyclic (DAG – Directed Acyclic Graph).
The problem is often to find the minimum cost or maximum cost path from a starting vertex (in stage 1) to
an ending vertex (in the last stage).
Stage 1 Stage 2 Stage 3 Stage 4
(S) ----> (A, B) ----> (C, D) ----> (T)
APPLICATIONS>>>
Shortest / Minimum Cost Path Problems
Dynamic Programming Problems
Network Routing
Resource Allocation Paths
2.what is an optimal binary search tree ?
An optimal binary search tree is a binary search tree.
where as the tree nodes arranged in a way such that the tree cost is minimum .
eg.draw any tree with ABCD nodes
3.Define P and NP classes !!
class P :
The class P problems are the decisions problems that can be solved within a polynomial time by using a
deterministic algorithm
(option (write if u want)>>
deterministic algorithm:
we know that an algorithm is a step by step procedure of solving a problem and each step (instruction) is
an operation
If each and every step is defined uniquely then the algorithm is know as deterministic algorithm
,otherwise its a Non Deterministic Algorithm
class NP :
The class NP problems are the decision problems that can be solved within a polynomial time by using a
NON DETERMINISTIC ALGORTHMS
eg: travelling salesman and graph coloring
4.FLYODS Algorithm
Floyd’s Algorithm (also called Floyd-Warshall Algorithm) is a dynamic programming algorithm used to find
the shortest paths between all pairs of vertices in a weighted graph (both directed or undirected).
Applications
All-Pairs Shortest Path problems in road networks.
Network routing protocols (finding least-cost paths).
5. What is FIFO branch and bound search?
(1) FIFO branch and bound stands for First In First Out branch and bound.
(2) In this search method the children of E node (Expanded node) are inserted in queue.
(3) This method makes use of breadth First Search.
6.Job assignment problem
The Job Assignment Problem is a type of optimization problem where:
There are n jobs and n persons (or machines).
Each person can do exactly one job, and each job must be assigned to exactly one person.
There is a given cost matrix where cost[i][j] represents the cost of assigning job j to person i.
Goal: Assign all jobs to persons such that the total cost is minimized (or sometimes maximized for profit
problems).
7.Challenges of solving numerical analysis problems
Round-Off Errors
Truncation Errors
Stability of Algorithms
Convergence Issues
Computational Cost
Choice of Method
Human and Programming Errors
8.Nearest Neighbour Approximation Algorithm for TSP
The Travelling Salesman Problem (TSP) asks for the shortest possible route that visits every city exactly
once and returns to the starting city.
The Nearest Neighbour (NN) Approximation Algorithm is a simple greedy approach to solve it.
Steps of the Algorithm
Start from any arbitrary city (starting point).
Choose the nearest unvisited city (the city with the smallest distance from the current city).
Move to that city and mark it as visited.
Repeat Steps 2–3 until all cities are visited.
Return to the starting city to complete the tour.
