Q1.

Explain Tree Traversal techniques with algorithm and example

Ans). To traverse a binary tree means to visit each node of the tree exactly once in a
systematic fashion. Binary tree is non-linear data structure. Hence, we can’t traverse it like a
linked list is a sequential manner but it requires a different approach.
We mainly have three algorithms for traversing binary tree.
A. Pre-order Traversal
B. In-order Traversal
C. Post-order Traversal

Pre-order traversal:-To traverse a non-empty binary tree by pre-order method, the following
operations are performed recursively until all nodes are visited:
i. Visit the root node.
ii. Traverse the left sub-tree fully.
iii. Traverse the right sub-tree.
The pre-order traversal of above tree is A,Q,W,Z,C,H,G,D
In-order Traversal:- To traverse a non-empty binary tree by in-order method, the following
operations are performed recursively until all nodes are visited:
i. Traverse the left sub-tree.
ii. Now, visit the root node.
iii. Then, finally traverse the right sub-tree.
The in-order traversal of the tree is Q, Z, W, C, A, H, D, G
Post-Order traversal:- To traverse a non-empty binary tree by post-order method, the
following operations are performed recursively until all nodes are visited:
i. Traverse the left sub-tree.
ii. Now, move to the right sub tree
iii. Then, finally visit the root node.
The post-order traversal of the tree is Z, C, W, Q, D, G, H, A

Q2. Explain Dijkstra's algorithm with an example

Ans.) Dijkstra's algorithm is a way of traversal which uses the shortest possible path to cover
all the nodes. Dijkstra algorithm works only for connected graphs and only for those graphs
that do not contain any negative weight edge. Since Dijkstra’s Algorithm is a greedy
algorithm, we would consider all the paths but select only the ones with shortest possible
distances from the priority queue to complete the array. The time complexity of the same
would be (N log N) or O[(N+E) + N] and the space complexity of this algorithm would be
O(N) + O(N)
For the given image, the output would be 0;4;12;19;21;11;9;8;14
The explanation is as follows: -
The distance from 0 to 1 = 4
The minimum distance from 0 to 2 = 12 [0 → 1→ 2]
The minimum distance from 0 to 3 = 19 [0→ 1→ 2 → 3]
The minimum distance from 0 to 4 = 21[0 → 7 → 6 → 5 → 4]
The minimum distance from 0 to 5 = 11 [0 → 7→ 6 → 5]
The minimum distance from 0 to 6 = 9 [0 → 7 → 6]
The minimum distance from 0 to 7 = 8 [0 → 7]
The minimum distance from 0 to 8 = 14 [0 → 1→ 2 → 8]
Q3 Explain DFS and BFS algorithm with an example.
Ans)
Depth First Search
For implementation of DFS, we must know how to “stack” data structure
Follow these steps
1. Start from one of the graph node, it may be start from left to right
2. Visit the current node and push it to stack
3. Check the top of the stack having adjacent nodes
4. If yes, then push the adjacent nodes into stack
5. If no then print the top of the stack and pop it from stack
6. Repeat these steps until all nodes are visited
Breadth First Search
For BFS, we need to use “Queue” as a data structure
Follow algorithm for BFS
1. Start with one node of graph. It may be traversed from left to right.
2. So there are two factors which are important for traversing first that the node is visited
or not and second one is there any adjacent nodes for current node
3. If we are visiting current node, then add node into queue
4. If the current node has adjacent nodes, then add those nodes into queue
5. If there are no more adjacent are found, then print the current node and place the
pointer to first node of queue
6. Repeat until all nodes get traversed.
Q4. What is minimum spanning tree? Explain Prim’s and Kruskal’s algorithm
Ans.) A minimum spanning tree is the one that contains the least weight among all the other
spanning trees of a connected weighted graph. There can be more than one minimum
spanning tree for a graph. The two most common ways to find the minimum spanning tree in
a graph are Prim’s Algorithm and Kruskal’s Algorithm.
In Prim’s Algorithm, we take up the source node (for example: 0) and then we take the
minimal edges connected to it, i.e., those with lowest weight margins. Once that is done, we
stop. Prim’s Algorithm is also an example of a greedy algorithm. To implement Prim’s
Algorithm, we would require 3 arrays, i.e., “Key Array” ; “MST Array” (short for Minimum
Spanning Tree) and the “Parent Array”. Initially, the “Key Array” would have all the values
as ∞, the “MST Array” would have all the values as False or ‘F’ and “Parent Array” would
have all the values as -1. As we are solving the minimum spanning tree , we will
subsequently mark the values “Key Array” with minimum edge weights, subsequently we
will mark “MST Array” values as true as we move forward and also mark the values of the
“Parent Array” to the numbers where there is the minimum edge weight. We will do this until
the tree is spanned.
An example for the same is given below: -

2 3
0 1 2

8 5
6 7
3 4

Initial Input
Key Array 0 1 2 3 4
∞ ∞ ∞ ∞ ∞
MST Array F F F F F

Parent Array -1 -1 -1 -1 -1

Final Input
Key Array 0 1 2 3 4
∞ 2 3 6 5

MST Array T T T T T

Parent Array -1 0 1 0 1
In Kruskal’s Algorithm, we use the concepts of “ Minimum spanning tree” and “ Disjoint
Set”. Since it is a greedy algorithm, we try to span the entire tree without making a cycle (as
it would defeat the purpose of the minimum spanning tree) and according to the disjoint set,
we ensure that the same parent which has already been used is not used (again to prevent
from making a cycle). We again use 3 Arrays for this, i.e., “Weight” ; “Source” and
“Destination” (in my example, I will implement this format) and thorough this we ensure that
the whole tree is spanned.

An example for the same is given below: -

8 7
1 2 3
4 9
2
4 14
11
0 8 4
7
6
8 10

7 6 5
1 2

The following graph contains 9 vertices and 14 edges: -

⸫ Minimum spanning tree will be formed in N-1 edges, i.e, 9-1 = 8 edges

After sorting:
Weight Source Destination
1 7 6
2 8 2
2 6 5
4 0 1
4 2 5
6 8 6
7 2 3
7 7 8
8 0 7
8 1 2
9 3 4
10 5 4
11 1 7
14 3 5
Final Result
7
1 2 3
4 9
2
4
0 8 4

8
7 6 5
1 2

Q5.Explain Apriori algorithm for finding association rules.

Ans.) The Apriori Algorithm uses frequent itemsets to generate association rules, and it is
designed to work on the databases that contain transactions. With the help of these
association rule, it determines how strongly or how weakly two objects are connected. This
algorithm uses a Breadth First Search (explained in a previous question) and Hash Tree to
calculate the itemset associations efficiently. It is the iterative process for finding the frequent
itemsets from the large dataset.
Frequent itemsets are those items whose support is greater than the threshold value or user-
specified minimum support. It means if A & B are the frequent itemsets together, then
individually A and B should also be the frequent itemset.
Suppose there are the two transactions: A= {1,2,3,4,5}, and B= {2,3,7}, in these two
transactions, 2 and 3 are the frequent itemsets.
Below are the steps for the Apriori Algorithm:
Step-1: Determine the support of itemsets in the transactional database, and select the
minimum support and confidence.
Step-2: Take all supports in the transaction with higher support value than the minimum or
selected support value.
Step-3: Find all the rules of these subsets that have higher confidence value than the
threshold or minimum confidence.
Step-4: Sort the rules as the decreasing order of lift.

Q7. Explain K-means and Hierarchical clustering methods with an example.

Ans.) K-means uses a pre-specified number of clusters .This method assigns records to each
cluster to find the mutually exclusive cluster of spherical shape based on distance. It needs
advance knowledge of K, i.e., no. of clusters one wants to divide data into. One can use
median or mean as a cluster centre to represent each cluster. In K Means clustering, since one
start with random choice of clusters, the results produced by running the algorithm many
times may differ. K- means clustering a simply a division of the set of data objects into non-
overlapping subsets (clusters) such that each data object is in exactly one subset).

Example: -

Cluster 1 Cluster 2 Cluster 3

(4, 1) (1, 9) (8, 2)

(3, 7) (2, 8) (5, 8)

(4, 7) (2, 7) (6, 6)

(6, 9)

Hierarchical clustering is used to group the unlabelled datasets into a cluster and also
known as hierarchical cluster analysis or HCA. In this algorithm, we develop the hierarchy of
clusters in the form of a tree, and this tree-shaped structure is known as the dendrogram. The
hierarchical clustering technique has two approaches:

Agglomerative: Agglomerative is a bottom-up approach, in which the algorithm starts with

taking all data points as single clusters and merging them until one cluster is left.

Divisive: Divisive algorithm is the reverse of the agglomerative algorithm as it is a top-down

approach.

In the k-means clustering that there are some challenges with this algorithm, which are a
predetermined number of clusters, and it always tries to create the clusters of the same size.

To solve these two challenges, we can opt for the hierarchical clustering algorithm because,
in this algorithm, we don't need to have knowledge about the predefined number of clusters.

Example: - It is used to sort country data, below is an example of US States arrest data