Data Structures and Algorithms Design Week 3 Answers

Are you looking for Data Structures and Algorithms Design Week 3 Answers ? All weeks solutions of this Swayam course are available here.

---

---

Data Structures and Algorithms Design Week 3 Answers (July-Dec 2025)

Course link: Click here to visit course on Nptel Website

---

Question 1. Which of the following is always true for an unsorted array with distinct elements?
a) There exists at least one local minimum
b) The first element is always a local minimum
c) There can be no local minima
d) The middle element is always a local minimum

View Answer

---

Question 2. In Euclid’s algorithm for computing gcd(a,b), what operation is repeatedly applied?
a) Replace (a,b) with (b, a mod b)
b) Replace (a,b) with (a − b, b)
c) Replace (a,b) with (a + b, a)
d) Replace (a,b) with (a, a mod b)

View Answer

---

Question 3. Analyze the time complexity of the following algorithm called Euclid’s algorithm for GCD of two numbers:

javaCopyEditGCD(a,b) // a ≥ b
{
   while b <> 0
   {
         t = b
         b = a mod b
         a = t
   }
   return a
}

a) O(a)
b) O(a log b)
c) O(log a + log b)
d) O(log a + 1)

View Answer

---

Question 4. What is the time complexity of finding a local minimum in a 1D array using divide and conquer?
a) O(log n)
b) O(n)
c) O(n log n)
d) O(√n)

View Answer

---

Question 5. Given the recurrence T(n) = 2T(n/2) + n, what is the asymptotic time complexity?
a) O(n log n)
b) O(n²)
c) O(n)
d) O(log n)

View Answer

---

Question 6. Consider the recurrence T(n) = 2T(n/2) + √n. What is the time complexity?
a) O(n)
b) O(n log n)
c) O(n¹·⁵)
d) O(√n log n)

View Answer

---

Question 7. A matrix algorithm divides an n × n matrix into 4 equal submatrices and processes each recursively. It performs O(n²) additional work. What is the recurrence?
a) T(n) = 4T(n/2) + O(n²)
b) T(n) = 2T(n/2) + O(n log n)
c) T(n) = T(n/2) + O(n²)
d) T(n) = 4T(n/2) + O(n)

View Answer

These are Data Structures and Algorithms Design Week 3 Answers

---

Question 8. In the divide-and-conquer algorithm for finding a local minimum in an n × n matrix, the algorithm scans the middle column to find its minimum and then recurses on one half of the matrix. What is the recurrence relation for its time complexity?
a) T(n) = T(n/2) + O(n)
b) T(n) = 2T(n/2) + O(n)
c) T(n) = T(n − 1) + O(1)
d) T(n) = T(n/2) + O(log n)

View Answer

---

Question 9. The divide-and-conquer algorithm for finding a local minimum in an n × n matrix runs in O(n) time. Which of the following best explains this?
a) The total number of elements processed across all levels shrinks geometrically and sums to O(n)
b) The algorithm reduces both dimensions simultaneously at each step, which leads to O(n) time by halving both rows and columns
c) Even though each level takes O(n) time and there are O(log n) levels, the matrix structure forces the total to be linear
d) Since only one column and one row are scanned at each step, total cost is just O(log n)

View Answer

---

Question 10. Which of the following problems is most naturally solved using divide-and-conquer?
a) Finding the closest pair of points in a plane
b) Finding the shortest path in a graph
c) Selecting activities to maximize profit
d) Computing the nth Fibonacci number with memoization

View Answer

---

These are Data Structures and Algorithms Design Week 3 Answers

Click here for all nptel assignment answers