Advanced Data Structure MCA

Subject Code: - PGCA 952
Subject Name: - Advanced Data Structure
Date of Examination: - December 2020
Class: - MCA 1st

Instructions to Candidates

Section A is Compulsory consisting of TEN questions carrying TWO marks each.
Section B & C have FOUR questions each.
Attempt any FIVE questions from SECTION B & C carrying TEN marks each.
Select at least TWO questions from SECTION B & C

SECTION-A

Sorting
Complexity
Algorithms
Underflow
Recursion
Garbage Collection
Prefix
Out Degree
Hash Function
KMP

SECTION-B

Explain Data Structures and their types in detail.
What are a Heap and its types? How to insert and delete the nodes from the heap?
Write an algorithm to perform QuickSort for example.
What is Hashing and Hash table? How it is implemented?

SECTION-C

Explain the Dijkstra’s and Kruskal Algorithms.
What is a String? Write an algorithm to check whether the string is a palindrome.
Discuss with example Boyer-Moore Algorithm.
What is MST? How it is found? Explain.

Answers:

Section A

Q1. Sorting

Ans: - Sorting is the process of arranging the elements of an array so that they can be placed either in ascending or descending order. For example, consider an array A = {A1, A2, A3, A4,?? An}, the array is called to be in ascending order if element of A are arranged like A1 > A2 > A3 > A4 > A5 > ? > An.

Consider an array;

int A [10] = {5, 4, 10, 2, 30, 45, 34, 14, 18, 9)

The Array sorted in ascending order will be given as;

A [] = {2, 4, 5, 9, 10, 14, 18, 30, 34, 45}

Sorting Algorithms:

Bubble Sort
Insertion Sort
Quick Sort
Selection Sort
Bucket Sort
Counting Sort

Q2. Complexity

Ans: - The complexity of an algorithm is a function describing the efficiency of the algorithm in terms of the amount of data the algorithm must process. In general, the amount of resources (or cost) that an algorithm requires in order to return the expected result is called computational complexity or just complexity. The complexity of an algorithm can be measured in terms of time complexity and/or space complexity.

Space Complexity: The space complexity of an algorithm refers to the amount of memory that this algorithm requires to execute and get the result. This can be for inputs, temporary operations, or outputs.
Time Complexity: The time complexity of an algorithm refers to the amount of time that this algorithm requires to execute and get the result. This can be for normal operations, conditional if-else statements, loop statements, etc.

Q3. Algorithms

Ans: - Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

An algorithm should have the following characteristics −

Clear and Unambiguous: The algorithm should be clear and unambiguous. Each of its steps should be clear in all aspects and must lead to only one meaning.
Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined inputs.
Well-Defined Outputs: The algorithm must clearly define what output will be yielded and it should be well-defined as well.
Finite-ness: The algorithm must be finite, i.e. it should not end up in infinite loops or similar.
Feasible: The algorithm must be simple, generic, and practical, such that it can be executed upon with the available resources. It must not contain some future technology or anything.
Language Independent: The Algorithm designed must be language-independent, i.e. it must be just plain instructions that can be implemented in any language, and yet the output will be the same, as expected.

Q4. Underflow

Ans: - Underflow is a condition that arises when we want to delete some data from an array data structure but there are no data available in that data structure.

It means that the given data structure is empty so if empty then there is no element is available to delete, this situation is called underflow.

Q5. Recursion

Ans:- Recursion is a common mathematical and programming concept. It means that a function calls itself. This has the benefit of meaning that you can loop through data to reach a result. The developer should be very careful with recursion as it can be quite easy to slip into writing a function that never terminates, or one that uses excess amounts of memory or processor power. However, when written correctly recursion can be a very efficient and mathematically-elegant approach to programming.

Example: -

Output: -

Q6. Garbage Collection

Ans: - In computer science, garbage collection is a type of memory management. It automatically cleans up unused objects and pointers in memory, allowing the resources to be used again. Some programming languages have built-in garbage collection, while others require custom functions to manage unused memory. A common method of garbage collection is called reference counting. This strategy simply counts how many references there are to each object stored in memory.

Garbage collection may also be done at compile-time when a program's source code is compiled into an executable program. In this method, the compiler determines which resources in memory will never be accessed after a certain time.

Q7. Prefix

Ans: - An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2).

Example:

*+AB-CD (Infix: (A+B) * (C-D))

Prefix

+AB
-+ABC
-*+ABCD

Q8. Out Degree

Ans: - The number of nodes that point to the node in consideration is called in-degree of the node. Similarly, the number of nodes the node in consideration points to is called out-degree of the node.

Out-degree of vertex 0 = 3
Out-degree of vertex 1 = 2
Out-degree of vertex 2 = 1
Out-degree of vertex 3 = 1
Out-degree of vertex 4 = 0

Q9. Hash Function

Ans: - The hash function is a function that is applied on a key by which it produces an integer, which can be used as an address of the hash table. Hence one can use the same hash function for accessing the data from the hash table. In this, the integer returned by the hash function is called the hash key. A hash function is a function or algorithm that is used to generate the encrypted or shortened value to any given key.

Example: -

Q10. KMP

Ans: - Knuth-Morris and Pratt introduce a linear time algorithm for the string matching problem. A matching time of O(n) is achieved by avoiding comparison with an element of 'S' that have previously been involved in comparison with some element of the pattern 'p' to be matched. i.e. backtracking on the string 'S' never occurs

Components of KMP Algorithm:

The Prefix Function (Π): The Prefix Function, Π for a pattern encapsulates knowledge about how the pattern matches against the shift of itself. This information can be used to avoid a useless shift of the pattern 'p.' In other words, this enables avoiding backtracking of the string 'S.'
The KMP Matcher: With string 'S,' pattern 'p' and prefix function 'Π' as inputs, find the occurrence of 'p' in 'S' and returns the number of shifts of 'p' after which occurrences are found.

Section B

Q1. Explain Data Structures and their types in detail.

Ans: - The data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently.

Types of Data Structure

Linear data structures

Array Data Structure
Stack Data Structure
Queue Data Structure
Linked List Data Structure

Non-linear data structures

Graph Data Structure
Trees Data Structure

Solution in detail ⟶

Q2. What are a Heap and its types? How to insert and delete the nodes from the heap?

Ans: - Heap data structure is a complete binary tree that satisfies the heap property, where any given node is

always greater than its child node/s and the key of the root node is the largest among all other nodes. This property is also called max heap property.
always smaller than the child node/s and the key of the root node is the smallest among all other nodes. This property is also called min-heap property.

Solution in detail ⟶

Q3. Write an algorithm to perform QuickSort for example.

Ans: - Quicksort is a sorting algorithm based on the divide and conquer approach where

Solution in detail ⟶

Q4. What is Hashing and Hash table? How it is implemented?

Ans: - Hashing is used to index and retrieve items in a database because it is faster to find the item using the shortest hashed key than to find it using the original value. It is also used in many encryption algorithms.

Solution in detail ⟶

Section C

Q1. Explain the Dijkstra’s and Kruskal Algorithms.

Ans: - Dijkstra algorithm is one of the prominent algorithms to find the shortest path from the source node to a destination node. It uses the greedy approach to find the shortest path. The concept of the Dijkstra algorithm is to find the shortest distance (path) starting from the source point and to ignore the longer distances while doing an update.

Dijkstra Algorithm Steps:

Step1: All nodes should be marked as unvisited.
Step2: All the nodes must be initialized with the "infinite" (a big number) distance. The starting node must be initialized with zero.
Step3: Mark starting node as the current node.
Step4: From the current node, analyze all of its neighbors that are not visited yet, and compute their distances by adding the weight of the edge, which establishes the connection between the current node and neighbor node to the current distance of the current node.
Step5: Now, compare the recently computed distance with the distance allotted to the neighboring node, and treat it as the current distance of the neighboring node,
Step6: After that, the surrounding neighbors of the current node, which has not been visited, are considered, and the current nodes are marked as visited.
Step7: When the ending node is marked as visited, then the algorithm has done its job; otherwise,
Step8: Pick the unvisited node which has been allotted the minimum distance and treat it as the new current node. After that, start again from step4.

Limitations of Dijkstra Algorithm:

The Dijkstra algorithm does not work when an edge has negative values.
For cyclic graphs, the algorithm does not evaluate the shortest path. Hence, for the cyclic graphs, it is not recommended to use the Dijkstra Algorithm.

Usages of Dijkstra Algorithm:

The algorithm is used by Google maps.
The algorithm is used to find the distance between two locations.
In IP routing also, this algorithm is used to discover the shortest path.

Kruskal Algorithm - Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. The main target of the algorithm is to find the subset of edges by using which we can traverse every vertex of the graph. It follows the greedy approach that finds an optimum solution at every stage instead of focusing on a global optimum.

How does Kruskal's algorithm work?

First, sort all the edges from low weight to high.
Now, take the edge with the lowest weight and add it to the spanning tree. If the edge to be added creates a cycle, then reject the edge.
Continue to add the edges until we reach all vertices, and a minimum spanning tree is created.

The applications of Kruskal's algorithm are -

Kruskal's algorithm can be used to layout electrical wiring among cities.
It can be used to lay down LAN connections.

Algorithm:

Create a forest F in such a way that every vertex of the graph is a separate tree.
Create a set E that contains all the edges of the graph.
Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning
Remove an edge from E with minimum weight
IF the edge obtained in Step 4 connects two different trees, then add it to the forest F

(for combining two trees into one tree).

ELSE
Discard the edge
END

Q2. What is a String? Write an algorithm to check whether the string is a palindrome.

Ans: - The string can be defined as the one-dimensional array of characters terminated by a null ('\0'). The character array or the string is used to manipulate text such as words or sentences. Each character in the array occupies one byte of memory, and the last character must always be 0. The termination character ('\0') is important in a string since it is the only way to identify where the string ends. When we define a string as char s[10], the character s[10] is implicitly initialized with the null in the memory.

Algorithm to check whether a string is palindrome or not:

Start
Read the string from the user
Calculate the length of the string
Initialize rev = “ ” [empty string]
Initialize i = length - 1
Repeat until i>=0:

rev = rev + Character at position ‘i’ of the string
i = i – 1

If string = rev:

Print “Given string is palindrome”

Else:

Print “Given string is not palindrome”

Stop

Q3. Discuss with example Boyer-Moore Algorithm.

Ans: - The B-M algorithm takes a 'backward' approach: the pattern string (P) is aligned with the start of the text string (T), and then compares the characters of a pattern from right to left, beginning with rightmost character.

If a character is compared that is not within the pattern, no match can be found by analyzing any further aspects at this position so the pattern can be changed entirely past the mismatching character.

For deciding the possible shifts, B-M algorithm uses two preprocessing strategies simultaneously. Whenever a mismatch occurs, the algorithm calculates a variation using both approaches and selects the more significant shift thus, if make use of the most effective strategy for each case. The two strategies are called heuristics of B - M as they are used to reduce the search. They are:

Bad Character Heuristics
Good Suffix Heuristics

Bad Character Heuristics:

Suppose there is a character in a text in which does not occur in a pattern at all. When a mismatch happens at this character (called as bad character), the whole pattern can be changed, begin matching form substring next to this 'bad character.'
On the other hand, it might be that a bad character is present in the pattern, in this case, align the nature of the pattern with a bad character in the text.
Thus in any case shift may be higher than one.
Example: Let Text T = <nyoo nyoo> and pattern P = <noyo>

Problem in Bad-Character Heuristics:

In some cases, Bad-Character Heuristics produces some negative shifts.
For Example:

This means that we need some extra information to produce a shift on encountering a bad character. This information is about the last position of every aspect in the pattern and also the set of characters used in a pattern (often called the alphabet ∑of a pattern).

Good Suffix Heuristics:

A good suffix is a suffix that has matched successfully. After a mismatch which has a negative shift in bad character heuristics, look if a substring of pattern matched till bad character has a good suffix in it, if it is so then we have an onward jump equal to the length of suffix found.
Example:

Q4. What is MST? How it is found? Explain.

Ans: - The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.

Minimum spanning tree has direct application in the design of networks. It is used in algorithms approximating the travelling salesman problem, multi-terminal minimum cut problem and minimum-cost weighted perfect matching. Other practical applications are:

Cluster Analysis
Handwriting recognition
Image segmentation

There are two famous algorithms for finding the Minimum Spanning Tree:

Kruskal’s Algorithm: - Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing spanning tree. Kruskal's algorithm follows greedy approach as in each iteration it finds an edge which has least weight and add it to the growing spanning tree.

Algorithm Steps:

Sort the graph edges with respect to their weights.
Start adding edges to the MST from the edge with the smallest weight until the edge of the largest weight.
Only add edges which doesn't form a cycle , edges which connect only disconnected components.

Prim’s Algorithm: - Prim’s Algorithm also use Greedy approach to find the minimum spanning tree. In Prim’s Algorithm we grow the spanning tree from a starting position. Unlike an edge in Kruskal's, we add vertex to the growing spanning tree in Prim's.

Algorithm Steps:

Maintain two disjoint sets of vertices. One containing vertices that are in the growing spanning tree and other that are not in the growing spanning tree.
Select the cheapest vertex that is connected to the growing spanning tree and is not in the growing spanning tree and add it into the growing spanning tree. This can be done using Priority Queues. Insert the vertices, that are connected to growing spanning tree, into the Priority Queue.
Check for cycles. To do that, mark the nodes which have been already selected and insert only those nodes in the Priority Queue that are not marked.

The following are the spanning trees that we can make from the graph.

The first spanning tree is a tree in which we have removed the edge between the vertices 1 and 5 shown as: The sum of the edges of the above tree is (1 + 4 + 5 + 2): 12

The second spanning tree is a tree in which we have removed the edge between the vertices 1 and 2 shown as: The sum of the edges of the above tree is (3 + 2 + 5 + 4) : 14

The third spanning tree is a tree in which we have removed the edge between the vertices 2 and 3 shown as: The sum of the edges of the above tree is (1 + 3 + 2 + 5) : 11

The fourth spanning tree is a tree in which we have removed the edge between the vertices 3 and 4 shown as: The sum of the edges of the above tree is (1 + 3 + 2 + 4) : 10. The edge cost 10 is minimum so it is a minimum spanning tree.

Top

Search This Blog

mk7 question paper