Q1. Define Stack. Explain push and pop operations performed on stack.

Stack
A stack is a linear data structure that follows a particular order in which operations are performed. The
order can be summarized by the acronym LIFO (Last In First Out), meaning the last element added to the
stack will be the first element to be removed from it. You can think of a stack like a stack of plates: you
add (or remove) plates from the top only.

Operations
Push:
This operation is used to insert an item into the stack. If the stack is full, then it is said to be at an
overflow condition. When an element is pushed onto the stack, it becomes the topmost element and all
other elements are shifted down.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

Pop:
This operation is used to remove the topmost item from the stack. If the stack is empty, then it is
said to be in an underflow condition. Popping a stack will remove the most recently added element that
was not yet removed.

Example:
Let's consider a stack with the following elements: [5, 3, 9]

• If we push the number 7 onto the stack, it becomes: [5, 3, 9, 7]

• If we then pop from the stack, the number 7 will be removed, and the stack goes back to: [5, 3,
9]

Q2. what is binary search writing its algorithm

Binary Search:
It is a technique to find or search a value in array. But array should be "sorted. This algorithm uses DAC
approach to find an array /or value in sorted array.

Key Points:
1 Sorted Array:-
Binary Search technique is used.if array is not sorted so first Sorted then binary search technique is used
or linear search is used.

2. Target Value:-
Target Value is any value X which we want to search in sorted array.

3. Mid Value:
(a) This algorithm works by dividing sorted array into two parts on the bases of Mid value i+j/2

(b) check weather mid value is target value. If it is target value searching is complete. else find target
value is less than or greater than mid value. If target value less than mid value we will search that value
in left half otherwise search in right half.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

Algorithm

Explain the term Algorithm with its Characteristics.

Algorithm:
An algorithm is a finite, well-defined sequence of steps or set of rules that provides a solution to a
specific problem. If a procedure has all the characteristics of an algorithm, then it is an algorithm.

Characteristics of an Algorithm:
Clear Steps:

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

Every step should be simple and clear. Anyone who looks at it should understand what to do.

Has an End:

It shouldn't go on forever. After following all the steps, you should finish.

Doable Steps:

Every step should be something you can actually do and finish.

Inputs:

Like ingredients in a recipe. Before starting, you might need some information or things.

Outputs:

The result you get after following all the steps. Like a finished dish in a recipe.

Works for All:

If you have a type of problem, the algorithm should work for all similar problems, not just one.

Language-Free:

Think of this like a recipe that can be understood no matter what language you speak. An algorithm
should make sense even if you change the "language" (or way) you use to follow it.

Draw and Explain Tree Terminology.

Terminology
In a tree data structure, we use the following terminology...

1. Root
In a tree data structure, the first node is called as Root Node. Every tree must have a root node. We can
say that the root node is the origin of the tree data structure. In any tree, there must be only one root
node. We never have multiple root nodes in a tree.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

2. Edge
In a tree data structure, the connecting link between any two nodes is called as EDGE. In a tree with 'N'
number of nodes there will be a maximum of 'N-1' number of edges.

3. Parent
In a tree data structure, the node which is a predecessor of any node is called as PARENT NODE. In
simple words, the node which has a branch from it to any other node is called a parent node. Parent
node can also be defined as "The node which has child / children".

4. Child
In a tree data structure, the node which is descendant of any node is called as CHILD Node. In simple
words, the node which has a link from its parent node is called as child node. In a tree, any parent node
can have any number of child nodes. In a tree, all the nodes except root are child nodes.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

5. Siblings
In a tree data structure, nodes which belong to same Parent are called as SIBLINGS. In simple words, the
nodes with the same parent are called Sibling nodes.

6. Leaf
In a tree data structure, the node which does not have a child is called as LEAF Node. In simple words, a
leaf is a node with no child.

In a tree data structure, the leaf nodes are also called as External Nodes. External node is also a node
with no child. In a tree, leaf node is also called as 'Terminal' node.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

7. Internal Nodes
In a tree data structure, the node which has atleast one child is called as INTERNAL Node. In simple
words, an internal node is a node with atleast one child.

In a tree data structure, nodes other than leaf nodes are called as Internal Nodes. The root node is also
said to be Internal Node if the tree has more than one node. Internal nodes are also called as 'Non-
Terminal' nodes.

8. Degree
In a tree data structure, the total number of children of a node is called as DEGREE of that Node. In
simple words, the Degree of a node is total number of children it has. The highest degree of a node
among all the nodes in a tree is called as 'Degree of Tree'

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

9. Level
In a tree data structure, the root node is said to be at Level 0 and the children of root node are at Level 1
and the children of the nodes which are at Level 1 will be at Level 2 and so on... In simple words, in a
tree each step from top to bottom is called as a Level and the Level count starts with '0' and incremented
by one at each level (Step).

10. Height
In a tree data structure, the total number of edges from leaf node to a particular node in the longest
path is called as HEIGHT of that Node. In a tree, height of the root node is said to be height of the tree. In
a tree, height of all leaf nodes is '0'.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

11. Depth
In a tree data structure, the total number of egdes from root node to a particular node is called
as DEPTH of that Node. In a tree, the total number of edges from root node to a leaf node in the longest
path is said to be Depth of the tree. In simple words, the highest depth of any leaf node in a tree is said
to be depth of that tree. In a tree, depth of the root node is '0'.

12. Path
In a tree data structure, the sequence of Nodes and Edges from one node to another node is called
as PATH between that two Nodes. Length of a Path is total number of nodes in that path. In below
example the path A - B - E - J has length 4.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

13. Sub Tree
In a tree data structure, each child from a node forms a subtree recursively. Every child node will form a
subtree on its parent node.

Explain Depth first search and Breath first search methods with example.

S.
No. Parameters BFS DFS

BFS stands for Breadth DFS stands for Depth

1. Stands for First Search. First Search.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

 S.
No. Parameters BFS DFS

BFS(Breadth First
DFS(Depth First Search)
Search) uses Queue data
uses Stack data
Data structure for finding the
structure.
2. Structure shortest path.

DFS is also a traversal

BFS is a traversal approach in which the
approach in which we traverse begins at the
first walk through all root node and proceeds
nodes on the same level through the nodes as far
before moving on to the as possible until we
next level. reach the node with no
3. Definition unvisited nearby nodes.

BFS can be used to find a

single source shortest
In DFS, we might
path in an unweighted
traverse through more
graph because, in BFS,
edges to reach a
we reach a vertex with a
destination vertex from
minimum number of
a source.
edges from a source
4. Technique vertex.

Conceptual BFS builds the tree level DFS builds the tree sub-
5. Difference by level. tree by sub-tree.

It works on the concept It works on the concept

Approach of FIFO (First In First of LIFO (Last In First
6. used Out). Out).

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

 S.
No. Parameters BFS DFS

BFS is more suitable for DFS is more suitable

searching vertices closer when there are solutions
7. Suitable for to the given source. away from source.

DFS is more suitable for

game or puzzle
BFS considers all problems. We make a
neighbors first and decision, and the then
therefore not suitable for explore all paths
decision-making trees through this decision.
Suitability used in games or puzzles. And if this decision
for Decision- leads to win situation,
8. Trees we stop.

The Time complexity of The Time complexity of

BFS is O(V + E) when DFS is also O(V + E)
Adjacency List is used when Adjacency List is
and O(V^2) when used and O(V^2) when
Adjacency Matrix is used, Adjacency Matrix is
where V stands for used, where V stands
Time vertices and E stands for for vertices and E stands
9. Complexity edges. for edges.

Visiting of
Here, siblings are visited Here, children are visited
Siblings/
before the children. before the siblings.
10. Children

The visited nodes are

Nodes that are traversed added to the stack and
Removal of several times are deleted then removed when
Traversed from the queue. there are no more nodes
11. Nodes to visit.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

 S.
No. Parameters BFS DFS

DFS algorithm is a
In BFS there is no recursive algorithm that
concept of backtracking. uses the idea of
12. Backtracking backtracking

BFS is used in various DFS is used in various

applications such as applications such as
bipartite graphs, shortest acyclic graphs and
13. Applications paths, etc. topological order etc.

BFS requires more DFS requires less

14. Memory memory. memory.

DFS is not optimal for

BFS is optimal for finding
finding the shortest
the shortest path.
15. Optimality path.

DFS has lesser space

In BFS, the space
complexity because at a
complexity is more
time it needs to store
critical as compared to
Space only a single path from
time complexity.
16. complexity the root to the leaf node.

BFS is slow as compared DFS is fast as compared

17. Speed to DFS. to BFS.

In BFS, there is no
In DFS, we may be
Tapping in problem of trapping into
trapped in infinite loops.
18, loops infinite loops.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

 S.
No. Parameters BFS DFS

When the target is close When the target is far

When to to the source, BFS from the source, DFS is
19. use? performs better. preferable.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

Q1 Implement the Insertion sort of give Array.
14 33 27 10 35 19 42 43

insertion sort on the given array step by step.

14 33 27 10 35 19 42 43
Starting with the second element (33), compare it to the first element (14) and insert it in the correct
position within the sorted subarray.

14 33 27 10 35 19 42 43
Move to the third element (27) and insert it into the sorted subarray (14, 33).

14 33 27 10 35 19 42 43
Move to the fourth element (10) and insert it into the sorted subarray (14, 27, 33).

10 14 27 33 35 19 42 43
Move to the fifth element (35) and insert it into the sorted subarray (10, 14, 27, 33).

10 14 27 33 35 19 42 43
Move to the sixth element (19) and insert it into the sorted subarray (10, 14, 27, 33, 35).

10 14 19 27 33 35 42 43
Move to the seventh element (42) and insert it into the sorted subarray (10, 14, 19, 27, 33, 35).

10 14 19 27 33 35 42 43
Finally, move to the last element (43) and insert it into the sorted subarray (10, 14, 19, 27, 33, 35, 42).

10 14 19 27 33 35 42 43

Q2 Find Shorts path Using Dijkstra Algorithm

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

Sol

So , Shortest path is Starting from S to C then to D via C and then to A via C and then to B via A.

Note Dow Path Not Only Write

Q.3 0/1 knapsack problem

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

Q.5: Solve the Travel salesman Problem on (a) and Kruskal Algorithm on
(b)

salesman Problem

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

Kruskal Algorithm on

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )
MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )
Q1. Draw the Directed graph for given Adjacency Matrix. Also write
down the Adjacency List of this Graph.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

Q.2 Apply DFS

Kruskal's Algorithm to find the Minimum Spanning Tree.

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )

Q.4 Apply Dijkstra's Algorithm and find the shortest path for given graph
(start from Vertex S)

MR.NOMAN.TARIQ@OUTLOOK.COM 0309-6054532. (IF FIND ANY MISTAKE CONTACT ME )