Department of Advanced Computer Science & Engineering
Data Structures(22TP201)
Question-1 (Sorting)
Design an algorithm using Quick Sort in separate recursive (QR) and iterative (QI) versions.
(a) Implement pivot selection techniques and other performance enhancements as applicable
for each.
(b) Compare the performance of QR and QI on a significant-sized collection of randomly
generated inputs. Choose based on this comparison, the better of QR and QI say QS.
(c) Implement Selection Sort iteratively (SS).
(d) Plot performance of QS versus SS for various sizes (lengths) of input data (lists). Find the
cut off size, say N, below which SS outperforms QS. Repeat the measurements at different
system loads to remove spurious variations.
(e) Rewrite QS such that when the size of sublist becomes less than N, SS is invoked. Call
this version QI.
(f) Add the performance plot of QI to the one obtained in (d) and measure the performance
improvement (as compared to QS).
(g) Find a system implementation of Quick Sort and add this to the plot obtained in QI.
Question-3 (Queue & Sorting)
b) Suppose you are given an m sorted list, each containing n elements. Write an efficient
algorithm based on priority queue to sort them in increasing order
Example: Input: 5 sorted lists of fixed size 4
[11, 21, 31, 41], [16, 26, 36, 46], [28, 30, 38, 49], [33, 34, 40, 51], [17, 19, 23, 29]
Output: [11, 16, 17, 19, 21, 23, 26, 28, 29, 30, 31, 33, 34, 36, 38, 40, 41, 46, 49, 51]
Question-14 (Sorting)
Without taking input n from user, read list of integers from input provided by user and
store them in an Array. Design an algorithm by using Quick sort in following ways.
Take first element as pivot and sort the elements, print the number of operations
performed.
Take Last element as pivot and sort the elements, print the number of operations
performed.
Take random element as pivot and sort the elements, print the number of
operations performed.
Input :3
87282 5621 2179 26717 2830
243 038 2297 456
548479 7728292 0290232
Output:
0238 1279 1256 12677 22788
038 234 456 2297
0022239 445789 2227789
Question-24 (Searching)
Design an Algorithm that generate a sequenced array of numbers starting with 1
and alternately add 1 and then add 2 to create the next numbers in the series, as
shown below.
1 3 4 6 7 9 10 12 13 15 16 ... 145 147 148 150
Then, using the ordered list search, searches the array 100 times. For the search arguments,
generate the 100 numbers in the range of 1 to 150.
At the end of the program, display the following statistics:
a) The number of searches completed
b) The number of successful searches
c) The percentage of successful searches
d) The average number of tests per search
To determine the average number of tests per search, you need to count the number of
tests for each search. After you run your program, write a paragraph on the similarities or
differences between the expected efficiency (big-O) and your calculated results.
Question-2 (Linked List)
Suppose you are given two linked lists, and you have to insert elements of the second list into
the first list. E.g., if the given first list is 6, 9, 11, 16, 18 and the second list is 13, 19, 21, 25,
8. The output list should be 6, 13, 9, 19, 11, 21, 16, 25, 18, 8, and the second list should
become empty. You have to insert the element of the second list only when the position in the
first list is available.
E.g., if the first list is 4, 7, 9, and the second list is 11, 12, 13, 14, 15, then the output list
should be 4, 11, 7, 12, 9, 13, and the second list is 14, 15.
Design an efficient algorithm to implement the above output list.
Note: You are not allowed to use extra space or create additional nodes, i.e., insertion of
elements must be in place.
Question-25 (Linked List)
Design an Algorithm to take an integer K and K number of sorted linked lists of various
lengths. implement the following functions:
● Store all K linked list heads in an array of pointers.
● Write a function which takes an array of linked lists and merges all sorted linked
lists into a single linked list and returns the linked list.
● For the above sorted single linked list delete the duplicate nodes in the list a
● Print the resultant linked list.
Sample Input (Optional):
K=3
List1 = 1->1->4->7-
>NULL List2 = 2-
>4->NULL
List3 = 3->5->7->NULL
Sample Output (Optional):
List = 1->2->3->4->5->7->NULL
Hints If any:
Use a new linked list for merging the array of linked lists.
Question-22 (Searching)
Given an array of size N and a target value. Design an Algorithm to implement
the following:(Array is not sorted initially).
a) Insert the target value such that you must return the index of the element where it is
inserted for the first time because there might be duplicates.
b) Now find the starting and ending position of a given target value.
c) Now from the resultant array count the no of pairs can be formed with given target value.
d) Find whether there are duplicate elements in the array or not if yes then remove those
duplicate elements and print the elements that appear only once in the array.
e) Now you are given with value K such that the array must be divided into K sub arrays.
f) Find the sum of differences of the maximum and the minimum of each subarray is
minimized.
Sample Input:
N = 7, Target = 8
Array = [2,4,5,7,9,10,8]
Sample Output:
a.) 4 // [2,4,5,7,8,9,10,8]
b.) [4,7]
c.) 0 Because no pair can be formed with the given
target value d.) [2,4,5,7,9,10]
e.) [2,4,5] [7,9,10] (5-2) + (10-7) = 6
Final o/p: 6
Question-30 (Linked List)
Design an algorithm to Reverse Nodes in k-Group
Given the head of a linked list, reverse the nodes of the list k at a time, and return the
modified list. k is a positive integer and is less than or equal to the length of the linked
list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should
remain as it is. You may not alter the values in the list's nodes, only nodes themselves
may be changed.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Example 2:
Input: head = [1,2,3,4,5],
k = 3 Output: [3,2,1,4,5]
Constraints:
The number of nodes in the
list is n. 1 <= k <= n <=
5000
0 <= [Link] <= 1000
Question-31 (Stack)
Design an algorithm to determine the Maximal Rectangle using arrays or stack
Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle
containing only 1's and return its area.
Example 1:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],
["1","0","0","1","0 "]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.
Example 2:
Input: matrix = [["0"]]
Output: 0
Example 3:
Input: matrix = [["1"]]
Output: 1
Constraints:
• rows == [Link]
• cols == matrix[i].length
• 1 <= row, cols <= 200
• matrix[i][j] is '0' or '1'
Question-33 (Stack)
Design an algorithm for the basic Calculator using Stack
Given a string s representing a valid expression, implement a basic calculator to evaluate
it, and return the result of the evaluation.
Note: You are not allowed to use any built-in function which evaluates strings as
mathematical expressions, such as eval().
Example 1:
Input: s = "1 + 1"
Output: 2
Example 2:
Input: s = " 2-1
+ 2 " Output: 3
Example 3:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output
: 23
Constr
aints:
• 1 <= [Link] <= 3 * 105
• s consists of digits, '+', '-', '(', ')', and ' '.
• s represents a valid expression.
• '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
• '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
• There will be no two consecutive operators in the input.
Every number and running calculation will fit in a signed 32-bit integer