DS GTU Paper Solution Winter 2020 | 3130702

Step 1: Divide the unsorted list into n sub-lists, each containing 1 element. Here, the sub-lists would be [20], [10], [5], [15], [25], [30], [50], [35].

Step 2: Merge sub-lists to produce newly sorted sub-lists until there is only 1 sub-list remaining.

Step 3: Compare the first element of each sub-list and merge them in the order that results in a sorted list.

Sub-list 1: [20] Sub-list 2: [10] New sub-list: [10, 20]

Sub-list 1: [5] Sub-list 2: [15] New sub-list: [5, 15]

Sub-list 1: [25] Sub-list 2: [30] New sub-list: [25, 30]

Sub-list 1: [50] Sub-list 2: [35] New sub-list: [35, 50]

Sub-list 1: [10, 20] Sub-list 2: [5, 15] New sub-list: [5, 10, 15, 20]

Sub-list 1: [25, 30] Sub-list 2: [35, 50] New sub-list: [25, 30, 35, 50]

Sub-list 1: [5, 10, 15, 20] Sub-list 2: [25, 30, 35, 50] New sub-list: [5, 10, 15, 20, 25, 30, 35, 50]

Step 4: The final sub-list [5, 10, 15, 20, 25, 30, 35, 50] is the sorted list using merge sort.

#include <stdio.h>
int main()
{
  int array[100], n, c, d, swap;
  printf("Enter number of elements\n");
  scanf("%d", &n);
  printf("Enter %d integers\n", n);
  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);
  for (c = 0 ; c < n - 1; c++)
  {
    for (d = 0 ; d < n - c - 1; d++)
    {
      if (array[d] > array[d+1]) /* For decreasing order use '<' instead of '>' */
      {
        swap       = array[d];
        array[d]   = array[d+1];
        array[d+1] = swap;
      }
    }
  }
  printf("Sorted list in ascending order:\n");
  for (c = 0; c < n; c++)
     printf("%d\n", array[c]);
  return 0;
}

1. Infix expression: A*B+C/D

•    Prefix expression:

Start by converting the infix expression to postfix expression: AB * CD / +

Reverse the postfix expression: + / CD * AB

Result: + / CD * AB

•   Postfix expression:

Start by converting the infix expression to postfix expression using the standard postfix algorithm: AB * CD / +

Result: AB * CD / +

Note: The postfix expression is already in the required form and there is no need to reverse it.

2. Infix expression: (A*B)+(C/D)-(D+E)

•     Prefix expression:

Start by converting the infix expression to postfix expression: AB * CD / + DE + –

Reverse the postfix expression: – + DE + / CD * AB

Result: – + DE + / CD * AB

•   Postfix expression:

Start by converting the infix expression to postfix expression using the standard postfix algorithm: AB * CD / + DE + –

Result: AB * CD / + DE + –

A priority queue is a type of queue that arranges elements based on their priority values. Elements with higher priority values are typically retrieved before elements with lower priority values.

In a priority queue, each element has a priority value associated with it. When you add an element to the queue, it is inserted in a position based on its priority value. For example, if you add an element with a high priority value to a priority queue, it may be inserted near the front of the queue, while an element with a low priority value may be inserted near the back.

Applications of priority queue:

• Dijkstra’s Shortest Path Algorithm using priority queue: In this algorithm, priority queue can be used to extract the minimum when the graph is stored in the form of adjacency list or matrix.
• Prim’s Algorithm using priority queue: Priority queue is used to implement the Prim’s algorithm to store the keys of nodes and extract the minimum value node at every step.
• Data Compression: Priority queue is used for compressing the data in Huffman coding.
• Operating Systems: Priority queue is also used in operating systems for interrupt handling, load balancing (load balancing on server).
• Heap Sort: In Heap sort is basically implemented using Heap data structure which is implemented using priority queue.
• Artificial Intelligence
• *A Search Algorithm:** This algorithm is used to find the shortest path between two vertices of a weighted graph, trying out the most promising route first. It uses priority queue to keep track of unexplored routes, the one for which a lower bound on the total path length is smallest is given highest priority.

Implementation of Priority Queue

The priority queue can be implemented in four ways that include arrays, linked list, heap data structure and binary search tree. The heap data structure is the most efficient way of implementing the priority queue, so we will implement the priority queue using a heap data structure in this topic. Now, first we understand the reason why heap is the most efficient way among all the other data structures.

STEP 1 START

STEP 2 Store the element to insert in linear data structure

STEP 3 Check if (front == 0 && rear == MAX-1) || (front == rear+1) then queue Overflow else goto step 4

STEP 4 Check if (front == -1) then front = 0; rear= 0; else goto step 5 

STEP 5 Check if (rear == MAX -1) then rear=0; else rear= rear+1; and goto step 6

STEP 6 Insert element cqueue_arr[rear] = item;

STEP 7 STOP

Let LLOne and LLTwo be the head pointer of two sorted linked list and resultHead and resultTail are the head and tail pointer of merged linked list.

Initilaize resultHead and resultTail to NULL. resultHead = resultTail = NULL;
If first linked list is empty, then attach whole of second list at the tail of merged linked list. if(LLOne == NULL) then resultTail->next = LLTwo;
If second linked list is empty, then attach whole of first list at the tail of merged linked list. if(LLTwo == NULL) then resultTail->next = LLOne;
Check which of the current nodes of both linked list is smaller and then remove it from linked list.
Add the smalled node at the tail of merged linked list.
Repeat above process, until one of the linked list or both becomes empty.
Return head pointer of merged linked list. return resultHead.

1. A+B/C*D-E

2. ((A+B)-(C*D))%((E^F)/(G-H))

There are several ways to represent a graph in a computer’s memory. Some of the most common methods are:

1. Adjacency matrix: In this representation, the graph is stored as a 2D array where each row and column represents a vertex in the graph. If there is an edge between two vertices, the corresponding entry in the matrix is set to 1, otherwise it is set to 0. This method is easy to implement and allows constant time access to edge information, but can be inefficient for sparse graphs.
2. Adjacency list: In this representation, the graph is stored as a list of vertices, where each vertex contains a list of its neighboring vertices. This method is efficient for sparse graphs, as it only stores information about the edges that exist in the graph. However, it can be slower for dense graphs.
3. Edge list: In this representation, the graph is stored as a list of edges, where each edge is represented as a tuple of the form (u, v), where u and v are the endpoints of the edge. This method is simple and efficient for sparse graphs, but can be less efficient for dense graphs.

The choice of graph representation method depends on various factors, such as the size and density of the graph, the operations that need to be performed on the graph, and the available memory. In general, adjacency lists are often preferred for sparse graphs, while adjacency matrices are preferred for dense graphs. Edge lists are a good choice when the focus is on the edges of the graph rather than the vertices.

Depth First Search (DFS) and Breadth First Search (BFS) are two common algorithms used to traverse and search graphs and trees. Here are the main differences between DFS and BFS:

1. Order of traversal: DFS traverses a graph or tree by exploring as far as possible along each branch before backtracking, while BFS traverses a graph or tree level by level, exploring all nodes at each level before moving to the next level.
2. Memory usage: DFS uses a stack to keep track of the nodes to visit next, while BFS uses a queue to keep track of the nodes to visit next. This means that DFS can be implemented with lower memory usage than BFS, especially for deep graphs or trees.
3. Completeness: BFS is guaranteed to find the shortest path between two nodes in an unweighted graph, while DFS is not. This is because BFS explores all nodes at a given level before moving to the next level, ensuring that the shortest path is found first.
4. Applications: DFS is commonly used in backtracking, topological sorting, and cycle detection, while BFS is commonly used in pathfinding, shortest path algorithms, and maze solving.

To summarize, DFS and BFS are two different algorithms used to traverse and search graphs and trees. DFS explores as far as possible along each branch before backtracking, while BFS explores all nodes at a given level before moving to the next level. DFS is memory-efficient and useful for certain applications, while BFS is guaranteed to find the shortest path in an unweighted graph and useful for other applications.

Insert function is used to add a new element in a binary search tree at appropriate location. Insert function is to be designed in such a way that, it must node violate the property of binary search tree at each value. 

1. Allocate the memory for tree. 
2. Set the data part to the value and set the left and right pointer of tree, point to NULL. 
3. If the item to be inserted, will be the first element of the tree, then the left and right of this node will point to NULL.
4. Else, check if the item is less than the root element of the tree, if this is true, then recursively perform this operation with the left of the root.
5. If this is false, then perform this operation recursively with the right sub-tree of the root.

Insert (TREE, ITEM)

• Step 1: IF TREE = NULL
      Allocate memory for TREE
     SET TREE -> DATA = ITEM 
    SET TREE -> LEFT = TREE -> RIGHT = NULL
    ELSE
     IF ITEM < TREE -> DATA
      Insert(TREE -> LEFT, ITEM)
    ELSE
     Insert(TREE -> RIGHT, ITEM)
    [END OF IF]
    [END OF IF]
• Step 2: END

Message Digest: 

This is an application of cryptographic Hash Functions. Cryptographic hash functions are the functions which produce an output from which reaching the input is close to impossible. This property of hash functions is called irreversibility. 

Password Verification: 

Cryptographic hash functions are very commonly used in password verification

Data Structures(Programming Languages): 

Various programming languages have hash table based Data Structures. The basic idea is to create a key-value pair where key is supposed to be a unique value, whereas value can be same for different keys. This implementation is seen in unordered_set & unordered_map in C++, HashSet & HashMap in java, dict in python etc. 

Compiler Operation: 

The keywords of a programming language are processed differently than other identifiers. To differentiate between the keywords of a programming language(if, else, for, return etc.) and other identifiers and to successfully compile the program, the compiler stores all these keywords in a set which is implemented using a hash table. 

Rabin-Karp Algorithm: 

One of the most famous applications of hashing is the Rabin-Karp algorithm. This is basically a string-searching algorithm which uses hashing to find any one set of patterns in a string. A practical application of this algorithm is detecting plagiarism.

Linking File name and path together: 

When moving through files on our local system, we observe two very crucial components of a file i.e. file_name and file_path. In order to store the correspondence between file_name and file_path the system uses a map(file_name, file_path)which is implemented using a hash table. 

Game Boards: 

In a game like Tic-Tac-Toe or chess the position of the game may be stored using hash table.

File Organization

File organization ensures that records are available for processing. It is used to determine an efficient file organization for each base relation. 

For example, if we want to retrieve employee records in alphabetical order of name. Sorting the file by employee name is a good file organization. However, if we want to retrieve all employees whose marks are in a certain range, a file is ordered by employee name would not be a good file organization.

Types of File Organization

1. Sequential access file organization

• Storing and sorting in contiguous block within files on tape or disk is called as sequential access file organization.
• In sequential access file organization, all records are stored in a sequential order. The records are arranged in the ascending or descending order of a key field.
• Sequential file search starts from the beginning of the file and the records can be added at the end of the file.
• In sequential file, it is not possible to add a record in the middle of the file without rewriting the file.

2. Direct access file organization

• Direct access file is also known as random access or relative file organization.
• In direct access file, all records are stored in direct access storage device (DASD), such as hard disk. The records are randomly placed throughout the file.
• The records does not need to be in sequence because they are updated directly and rewritten back in the same location.
• This file organization is useful for immediate access to large amount of information. It is used in accessing large databases.
• It is also called as hashing.

3. Indexed sequential access file organization

• Indexed sequential access file combines both sequential file and direct access file organization.
• In indexed sequential access file, records are stored randomly on a direct access device such as magnetic disk by a primary key.
• This file have multiple keys. These keys can be alphanumeric in which the records are ordered is called primary key.
• The data can be access either sequentially or randomly using the index. The index is stored in a file and read into memory when the file is opened.

Calculate the hash value for key 131 using the formula h(k) = k mod m where m=10. The hash value is 1.

Create a linked list at memory location 1 and insert key 131 into the linked list.

Calculate the hash value for key 3 using the formula h(k) = k mod m where m=10. The hash value is 3.

Create a linked list at memory location 3 and insert key 3 into the linked list.

Calculate the hash value for key 4 using the formula h(k) = k mod m where m=10. The hash value is 4.

Insert key 4 into the linked list at memory location 4.

Calculate the hash value for key 21 using the formula h(k) = k mod m where m=10. The hash value is 1.

Insert key 21 into the linked list at memory location 1.

Calculate the hash value for key 61 using the formula h(k) = k mod m where m=10. The hash value is 1.

Insert key 61 into the linked list at memory location 1.

Calculate the hash value for key 24 using the formula h(k) = k mod m where m=10. The hash value is 4.

Insert key 24 into the linked list at memory location 4.

Calculate the hash value for key 7 using the formula h(k) = k mod m where m=10. The hash value is 7.

Create a linked list at memory location 7 and insert key 7 into the linked list.

Calculate the hash value for key 97 using the formula h(k) = k mod m where m=10. The hash value is 7.

Insert key 97 into the linked list at memory location 7.

Calculate the hash value for key 8 using the formula h(k) = k mod m where m=10. The hash value is 8.

Create a linked list at memory location 8 and insert key 8 into the linked list.

Calculate the hash value for key 9 using the formula h(k) = k mod m where m=10. The hash value is 9.

Create a linked list at memory location 9 and insert key 9 into the linked list.

So, the final hash table would look like: [131 -> 21 -> 61, null, 3, 4 -> 24, 7 -> 97, 8, 9].

1. Calculate the hash value for key 72 using the formula: h(x) = (h1(x) + c1 * i + c2 * i^2) mod m where m=10.
2. Place key 72 at position 2.
3. Calculate the hash value for key 27 using the formula: h(x) = (h1(x) + c1 * i + c2 * i^2) mod m where m=10.
4. Place key 27 at position 1.
5. Calculate the hash value for key 36 using the formula: h(x) = (h1(x) + c1 * i + c2 * i^2) mod m where m=10.
6. Place key 36 at position 5.
7. Calculate the hash value for key 24 using the formula: h(x) = (h1(x) + c1 * i + c2 * i^2) mod m where m=10.
8. Place key 24 at position 0.
9. Calculate the hash value for key 63 using the formula: h(x) = (h1(x) + c1 * i + c2 * i^2) mod m where m=10.
10. Place key 63 at position 8.
11. Calculate the hash value for key 81 using the formula: h(x) = (h1(x) + c1 * i + c2 * i^2) mod m where m=10.
12. Place key 81 at position 9.
13. Calculate the hash value for key 101 using the formula: h(x) = (h1(x) + c1 * i + c2 * i^2) mod m where m=10.
14. Key 101 cannot be placed, as all positions have been filled.

So, the final hash table would look like: [24, 27, 72, null, 36, null, null, null, 63, 81].