Scribd
Upload
30 views

DSA Tutorial Question

Dsa tutorial questions

Uploaded by

kmor
Copyright
© © All Rights Reserved
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
30 views

DSA Tutorial Question

Dsa tutorial questions

Uploaded by

kmor
Copyright
© © All Rights Reserved
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

School of Computer Science Engineering and Technology

Course- B. Tech Type- Core Course


Code- CSET243 Course Name-DSA using C++
Year- 2024 Semester- Odd
Date-04-08-2024 Batch- 5th Sem
Tutorial: 01

COURSE-SPECIFIC LEARNING OUTCOMES (CO)

CO1: Articulate the design, use and associated algorithms of fundamental and abstract data structures

CO2: Examine various searching and sorting techniques based on complexity analysis for applicative
solutions.

CO3: Demonstrate hands-on experience on implementing different data structures

CO4: Build optimized solutions for real-word programming problems using efficient data structures.

Objective 1: Finding time complexities using backward substitution method.


Objective 2: Finding time complexities using recursion tree method.

Tut No. Name CO 1 CO 2 CO 3 CO4


1 Tutorial:2.1 √

Section 1 Easy (3 Questions)

Question 1. Which of the following sorting algorithms in its typical implementation gives best
performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are
misplaced).

(a) Quick Sort


(b) Heap sort
(c) Merge sort
(d) Insertion sort
Question 2 The number of swaps required to arrange the numbers 8, 22, 7, 9, 31, 5, 13 in ascending
order using the bubble sort algorithm is (5 Mins)
(a) 11
(b) 12
(c) 13
(d) 10

Question 3. What is the time complexity of the following code: (5 Mins)


int a = 0;
for (i = 0; i < N; i++) {
for (j = N; j > i; j--) {
a = a + i + j;
}
}

(a) O(N)
(b) O(N*log(N))
(c) O(N * Sqrt(N))
(d) O(N*N)

Section 2 Medium (3 Questions)

Question 1. A teacher needs to arrange the scores of students in her class in ascending order to
identify the students with the lowest scores who may need extra help. Due to the simplicity of the task,
she wants to use the Bubble Sort algorithm to sort the scores.
You are given a list of student scores. Your task is to write a C++ program that uses the Bubble Sort
algorithm to sort these scores in ascending order. Additionally, after each complete pass of the Bubble
Sort algorithm, the program should output the current state of the list to show how the sorting progresses.

(5 Mins)

Question 2: You are given an array of 0s and 1s in random order. Segregate 0s on left side and 1s on
right side of the array [Basically you have to sort the array]. Traverse array only once.
Example
Input array = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]
Output array = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] (15 Mins)

Question 3: Given an array of integers (both odd and even), sort them in such a way that the first part of
the array contains odd numbers sorted in descending order, rest portion contains even numbers sorted in
ascending order. (15 Mins)
Input: arr[] = {1, 2, 3, 5, 4, 7, 10}
Output: arr[] = {7, 5, 3, 1, 2, 4, 10}
Section 3 Hard (3 Questions)

Question 1: In quick sort, for sorting n elements, we choose the n/4th smallest element as a pivot
with an O(n) time algorithm. Calculate the worst-case time complexity for the quick sort?
[15 Min]

Question 2: Given an unsorted array of integers in the range from 0 to n-1. We are allowed to swap
adjacent elements in array many number of times but only if the absolute difference between these
element is 1. Check if it is possible to sort the array. If yes then print “yes” else “no”.
(Microsoft) [15 Mins]

Example: Input : arr[] = {1, 0, 3, 2}


Output : yes

Input : arr[] = {2, 1, 0}


Output : no

Question 3: Given an array A[] consisting of only 0s, 1s, and 2s. The task is to sort the array, i.e., put all
0s first, then all 1s and all 2s in last. This problem is also known as Dutch National Flag problem.

[Paytm, Flipkart] [15 Mins]


Example
Input: {0, 1, 2, 0, 1, 2}
Output: {0, 0, 1, 1, 2, 2}

You might also like