[go: up one dir, main page]

0% found this document useful (0 votes)
214 views2 pages

UNC401 MST Spring 2025

The document outlines a mid-semester test for the Department of Electronics & Communication Engineering at Thapar Institute, focusing on data structures and algorithms. It includes various questions on time complexity analysis, algorithm proofs, expression conversion, and linked list manipulation. The test is structured to assess students' understanding of algorithmic concepts and their practical applications.

Uploaded by

abhi.av57000
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
214 views2 pages

UNC401 MST Spring 2025

The document outlines a mid-semester test for the Department of Electronics & Communication Engineering at Thapar Institute, focusing on data structures and algorithms. It includes various questions on time complexity analysis, algorithm proofs, expression conversion, and linked list manipulation. The test is structured to assess students' understanding of algorithmic concepts and their practical applications.

Uploaded by

abhi.av57000
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Thapar Institute of Engineering & Technology, Patiala

(Deemed to be University)
Department of Electronics & Communication Engineering
Mid Semester Test

Roll Number: ​ ​ ​ Name:​ ​ ​ ​ ​


BE- ENC/ECE UNC401 Data structures and Algorithms
Date- 05/03/2025
Time: 120 Mins, 40 Marks Name of Faculty: _____________________
Group name: _______________

Note: Attempt all questions. Read each question carefully. Marks are indicated
against each question.

Q1 (a) Analyze the time complexity of the following function? 2,3


FUNCTION calculate_count(n)
FOR i FROM n/2 TO n DO
FOR j FROM 1 TO n - n/2 STEP j * 2 DO
FOR k FROM 1 TO n STEP k * 2 DO
INCREMENT count
END FOR
END FUNCTION
(b) Solve the following recurrence relation and provide the big O asymptotic complexity?
T(n) = 3T(n/3) + n/2, when n>1 and T(1) = 1.

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.

Column A (Algorithms/Operations) Column B (Time


Complexities)

1. QuickSort, MergeSort

2. Bubble Sort, Selection Sort, Insertion


Sort

3. Linear Search, Binary Search


Options for Column B:
(A) Θ(n), (B) Θ(n²), (C) Θ(n log n), (D) Θ(log n), (E) Θ(1)

You might also like