UNC401 MST Spring 2025
UNC401 MST Spring 2025
(Deemed to be University)
Department of Electronics & Communication Engineering
Mid Semester Test
Note: Attempt all questions. Read each question carefully. Marks are indicated
against each question.
Q2 1,2,2
(a)Prove that the function f(n) = 3n2 + 8n + 2 is not O(n).
(b)Prove that the function f(n) = 3n2 + 8n + 2 is O(n2) by finding positive constants c and
n0 such that the definition of Big O notation is satisfied.
(c)Prove that 22n is not O(2n).
Q3 (a)Given the infix expression ((a/(b-c+d))*(e-a)*c), analyze the expression and 2.5,2.
demonstrate how to convert it into a postfix expression. Additionally, create a 5
pseudocode to evaluate the resulting postfix expression and then apply this
pseudocode using the values a=6, b=3, c=1, d=2, and e=4. Trace the evaluation
step-by-step to show the result of the computation.
(b)Given a stack with basic operations such as push, pop, isEmpty, and peek, devise a
pseudocode that removes the middle element of the stack. Implement this algorithm
and demonstrate its application by applying it to a stack with the values [11, 22, 33,
44, 55].
Example: Input stack = [11, 22, 33, 44, 55] Output: stack = [11, 22, 44, 55]
Q4 Implement a function which will traverse a 1-D array from beginning to end and reverse all 5
the increasing and decreasing sequence of components present in the array. Component is
the collection of continuous elements either in increasing or decreasing order. Example: Let
an array contains 1,2,3,7,4,2,9,7,8.Here the components are “1,2,3,7”, “4,2”, “9,7” and “8”.
The function should produce the array with elements 7,3,2,1,2,4,7,9,8.
Q5 Given a singly linked list and an integer K, write an algorithm to rotate the list to the right by 5
K positions. A right rotation moves each node K steps forward, and the last node wraps
around to the beginning.
Example:
Input Linked List: 1 -> 2 -> 3 -> 4 -> 5, K = 2
Output Linked List: 4 -> 5 -> 1 -> 2 -> 3
Q6 Given an unsorted doubly linked list containing n nodes, each containing an integer. Write 5
an algorithm to remove the maximum element from the given list.
Q7 Although merge sort runs in Θ(nlgn) worst-case time and insertion sort runs in Θ(n2) 1,2,2
worst-case time, the constant factors in insertion sort can make it faster in practice for small
problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the
recursion by using insertion sort within merge sort when subproblems become sufficiently
small. Consider a modification to merge sort in which
n/k sublists of length k are sorted using insertion sort and then merged using the standard
merging mechanism, where k is a value to be determined.
(a)What is the worst-case time complexity of using insertion sort to sort n/k sublists,
each of length k?
(b)Find the worst-case time complexity for merging n/k sorted sublists, each of length k.
(c)Find the worst-case time complexity of the modified algorithm and determine the
largest value of k as a function of n such that the modified algorithm has the same
running time as the standard merge sort in terms of Θ-notation.
Q8 Each algorithm or operation in Column A may have multiple applicable time complexities 2,2,1
from Column B. Consider all possible cases (best, worst, and average) when selecting your
answers. Some options in Column B may be used multiple times. For each algorithm or
operation in Column A, match all applicable time complexities from Column B based on the
best, worst, and average cases.
1. QuickSort, MergeSort