DSA
IMPORTANT instructions:
Read carefully the question first, and then ask for the queries.
Student are required to Submit/turn in their Assessments on Google classroom
only, Assessment submitted through any other Mode will not be considered
submitted and will not be marked.
Student are Required to attempt the assessment in a word file.
The name of file must include student registration No and Name.
Copy pasted Answers may result in zero marks for the question.
_____________________________________________________________________________
__________________
‘Attempt all questions’
Q1: Solve the following short questions (2.5+ 2.5
Marks)
a. Convert the following infix notation into postfix notation:
( ( ( m +n ) * o ) - ( ( p + q ) / r ) )
Postfix notation:
mn+o*pq+r/-
b. Consider the following matrix and draw the graph (G)
G= [0 1 1 0 0, 1 0 0 1 1, 0 0 1 0 1, 0 1 0 0 1, 0 1 0 1 0]
Q2: How would you differentiate between code and an algorithm? What are the two
main measures that contribute towards the efficiency of an algorithm? Moreover,
search the element “4” in the given array A, using Binary search:
(2.5+ 2.5 Marks)
A= [3, 42, 5, 7, 14, 4, 23, 17, 25, 8].
Algorithm
An algorithm is a series of steps for solving a problem, completing a task or performing a
calculation. Algorithms are usually executed by computer programs, but the term can also apply
to steps in domains such as mathematics for human problem solving.
Code
Code is a series of steps that machines can execute.
Coding is the process of designing and building an executable computer program to accomplish a
specific computing result.
Efficiency of an algorithm
Time complexity: it is a function describing the amount of time an algorithm takes in
terms of the amount of input to the algorithm. "Time" can mean the number of memory accesses
performed, the number of comparisons between integers, the number of times some inner loop is
executed, or some other natural unit related to the amount of real time the algorithm will take.
We try to keep this idea of time separate from "wall clock" time, since many factors unrelated to
the algorithm itself can affect the real time (like the language used, type of computing hardware,
proficiency of the programmer, optimization in the compiler, etc.). It turns out that, if we chose
the units wisely, all of the other stuff doesn't matter and we can get an independent measure of
the efficiency of the algorithm.
Space complexity: it is a function describing the amount of memory (space) an algorithm takes in terms
of the amount of input to the algorithm. We often speak of "extra" memory needed, not counting the
memory needed to store the input itself. Again, we use natural (but fixed-length) units to measure this.
We can use bytes, but it's easier to use, say, number of integers used, number of fixed-sized structures,
etc. In the end, the function we come up with will be independent of the actual number of bytes needed
to represent the unit. Space complexity is sometimes ignored because the space used is minimal and/or
obvious, but sometimes it becomes as important an issue as time.
Algorithm
Step 1: First divide the list of elements in half.
Step 2: In the second step we compare the target value with the middle element of the array. If it
matches the middle element, then search ends here and doesn’t proceed further.
Step 3: Else if the element less than the middle element then we begin the search in lower half of the
array.
Step 4: Else if the element is greater than the middle element then we begin the search in greater half of
the array.
Step 5: We will repeat the steps 3 ,4 and 5 until our target element is found.
Code:
#include <iostream>
using namespace std;
int binarySearch(int[], int, int, int);
int main()
{
int num[10] = {3,42 , 5, 7, 14, 4,23,17,25,8};
int search_num, loc=-1;
cout<<"Enter the number that you want to search: ";
cin>>search_num;
loc = binarySearch(num, 0, 6, search_num);
if(loc != -1)
{
cout<<search_num<<" found in the array at the location: "<<loc;
}
else
{
cout<<"Element not found";
}
return 0;
}
int binarySearch(int a[], int first, int last, int search_num)
{
int middle;
if(last >= first)
{
middle = (first + last)/2;
if(a[middle] == search_num)
{
return middle+1;
}
else if(a[middle] < search_num)
{
return binarySearch(a,middle+1,last,search_num);
}
else
{
return binarySearch(a,first,middle-1,search_num);
}
}
return -1;
}
Q3: Differentiate between the characteristics of BT, BST, AVL Tree and Heap. Also
narrate in which applications shortest path first algorithms are required.
(Give any practical example with illustrations.) (2 + 3
Marks)
Binary Tree
1: BINARY TREE is a non linear data structure where each node can have almost two child
nodes.
2: BINARY TREE is unordered hence slower in process of insertion, deletion and searching.
3: IN BINARY TREE there is no ordering in terms of how the nodes are arranged.
Binary search Tree
1: BINARY SEARCH TREE is a node based binary tree which further has right and left subtree
that too are binary search tree.
2: Insertion, deletion, searching of an element is faster in BINARY SEARCH TREE than
BINARY TREE due to the ordered characteristics.
3: IN BINARY SEARCH TREE the left subtree has elements less than the nodes element and the right
subtree has elements greater than the nodes element.
AVL Tree
1: VL trees are balanced binary trees that are mostly used in database indexing.
2: All the operations performed on AVL trees are similar to those of binary search trees but the only
difference in the case of AVL trees is that we need to maintain the balance factor i.e. the data structure
should remain a balanced tree as a result of various operations. This is achieved by using the AVL Tree
Rotation operation.
Heap
1: Heaps are complete binary tree structures that are classified into min-heap or max-heap. Min-heap has
the minimum element as its root and the subsequent nodes are greater than or equal to their parent node.
2: The Heap differs from a Binary Search Tree. The BST is an ordered data structure, however,
the Heap is not. In computer memory, the heap is usually represented as an array of numbers.
The heap can be either Min-Heap or Max-Heap.
3: The main rule of the Max-Heap is that the subtree under each node contains values less or equal than
its root node.
Q4: Solve the following routing problems. (2.5
+5Marks)
a. Using Djkstra Algorithm find the forwarding table in U. Also explain how
Dijkstra algorithm deals with positive and negative weights.
b. Construct an AVL Tree by inserting numbers from { 10, 5, 3, 15, 17, 19, 21}.
Q5: Please find the below graph representing the road maps of 7 cities named A, B,
C, D, E, F and G. Find the adjacency matrix (in degree and out degree). Also
explain if you can tell which roads are one way and which offer two way facilities.
(7.5 marks)
