CSF211 2024 MidsemSolutions

Birla Institute of Technology & Science
CS F211 Data Structures & Algorithms

Mid-Semester Exam SOLUTIONS, II Semester 2023-2024
CLOSED BOOK, 90 marks, 90 minutes.
• Write your answers in the provided answer booklet. Be brief.

• Answer every question on a fresh page & in the order that they appear below.
1. (a) [7 marks] Prove that √n is O(n), where √n denotes the square root of n.
Suppose, √n <= n
⇔ n <= n2 (Squaring)
⇔ n >= 1 (Dividing both sides by n).
Therefore, for c=1, n0=1, we have √n <= c n, for all n>=n0, due to which √n is O(n).
(b) [8 marks] Prove that n is not O(√n).
Proof:
Suppose, by way of contradiction that n is O(√n).
Therefore, n <= c √n, for all n >=n0 , where c and n0 are positive constants.
⇔ n2 <= c2n, for all n >=n0 (Squaring)
⇔ n <= c2 , for all n >=n0 (Dividing both sides by n).
This is a contradiction and therefore n is not O(√n).
2. [5 marks] Prove that in a Binary Search tree, if a node z has a right child, then the successor
y of the node z cannot have two children. An example will not suffice.
Proof:
Suppose z has a right child. Then, the successor y of z is an element in the right subtree of z.
Now, suppose, by way of contradiction that y has two children and x is the left child of y.
Then x>=z and x<=y, due to which y cannot be the successor of z, which is a contradiction.
Therefore y cannot have two children.
3. [10 marks] Given a list of n unsorted elements, design an O(n log k) algorithm to find the k
smallest elements in the list. You may use any algorithms discussed in class as subroutines,
without expanding on them. Briefly argue about its asymptotic running time.
Create a max-heap with the first k elements. For the subsequent elements in the list, if the
element is smaller than the largest element in the max heap, remove the maximum element in
the max heap and replace it with said element. O(k) time for building the max heap initially,
and at most O((n-k) log k ) for the deletions and insertions, due to which we have an O(n log
k) algorithm.
4. Suppose you modified MergeSort so that instead of splitting the input array into two
parts, you split it into three (almost) equal parts, so that you merge the sorted lists via a
3-way Merge routine.
(a) [8 marks] Write down pseudocode for this variant of MergeSort.
(b) [3 marks] Write down the recurrence relation for the running time of your pseudocode.
(c) [4 marks] Solve the recurrence relation to obtain tight asymptotic estimates.
4-(a) PseudoCode for 3-way merge sort
3waymergesort(L)
If length(L) <= 1 then
return L
LA <- L[1,....,L/3]
LB <- L[L/3+1,....,2L/3]
LC <- L[2L/3+1,....,L]
LA<- 3waymergesort(LA)
LB<- 3waymergesort(LB)
LC<- 3waymergesort(LC)
LD<- Merge(LA,LB)
Return Merge(LC,LD)
4-(b) Recurrence relation:
T(n) = 3T(n/3) + O(n)
There are three recursive calls to 3waymergesort, each on a list of size n/3, followed by a call to
Merge, which takes O(n) time
4-(c) Solving above using recursion tree, tight asymptotic estimate: θ (n logn)
5. [15 marks] For the Bucket Sort algorithm discussed in class, with the same assumptions,
derive an expression for the expected number of elements per bucket.
6. (a) [7 marks] Prove that for a binary tree, in general, one cannot reconstruct the binary tree
given only its preorder traversal. You may prove this by demonstrating two distinct binary
trees, which have the same preorder traversal.
(b) [8 marks] For a Binary Search tree, however, it turns out that knowing its preorder
traversal is sufficient to exactly reconstruct the tree. Design a recursive algorithm to do so.
An English description of the algorithm is sufficient, as long as it contains all details.
7. In this problem, you will design a linear-time algorithm to find a weighted median, as
defined below. Given an unsorted array of n distinct elements x1, x2, …, xn with associated
positive weights w1, w2, …, wn, define the weighted median as an element xk for whom the
total weight of elements less than it, is at most w/2, where w is the sum of all weights and
also total weight of all elements greater than xk is at most w/2. If there are two such
medians, consider the smaller one.
(a) [7 marks] Recall the naïve algorithm that used Partition & an arbitrary pivot to create a
median-finding algorithm. Modify that algorithm to solve this problem and describe it in a
few sentences in English. Analyze the worst-case running time of this algorithm.
Solution:
Pick a pivot, and run Partition. Now, one needs to determine if the weighted median is on
the left of the pivot or to the right or is indeed the pivot. Compute the sum of weights of
elements less than the pivot and greater than the pivot respectively. If both sums are at
most w/2, then the pivot is the weighted median. Else, the side which has total weight
greater than w/2 contains the weighted median. Recursively call the algorithm on this side;
including the pivot whose weight is now updated to equal its current weight plus the net
weight of elements on the discarded side. If the pivot turns out to be the least/biggest
element, choose another element as pivot the next time around. Recurrence is
T(n)=T(n-1)+cn = θ(n2)
(b) [8 marks] Modify the Select algorithm to find the weighted median in linear time. Briefly
describe your algorithm in a few sentences and briefly argue why it is linear time. (You don’t
have to write down the complete asymptotic analysis.)
Solution:
Similar to Part (a) except always choose the pivot to be the median. Recurrence is
T(n)=T(n/2) + cn = θ(n).

CSF211 2024 MidsemSolutions

Uploaded by

Copyright:

Available Formats

CSF211 2024 MidsemSolutions

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CSF211 2024 MidsemSolutions

Uploaded by

Copyright:

Available Formats

Birla Institute of Technology & Science

CS F211 Data Structures & Algorithms

• Write your answers in the provided answer booklet. Be brief.

(b) [8 marks] Prove that n is not O(√n).

4-(a) PseudoCode for 3-way merge sort

4-(b) Recurrence relation:

T(n) = 3T(n/3) + O(n)

You might also like