# NPTEL Design and analysis of algorithms Assignment 2 Answer 2023

We Discuss About That NPTEL Design and analysis of algorithms Assignment 2 Answer 2023

NPTEL Design and analysis of algorithms Assignment 2 Answer 2023– Here All The Questions and Answers Provided to Help All The Students and NPTEL Candidate as a Reference Purpose, It is Mandetory to Submit Your Weekly Assignment By Your Own Understand Level.

Are you looking for the Assignment Answers to **NPTEL Design and analysis of algorithms Assignment 2 Answer 2023? **If Yes You are in Our Great Place to Getting Your Solution, This Post Should be help you with the Assignment answer to the **Nation**** al Programme on Technology Enhanced Learning (NPTEL)** Course

**“NPTEL Design and analysis of algorithms Assignment 2 Answer 2023”**

Table of Contents

## NPTEL Design and analysis of algorithms Assignment

- Asymptotic complexity, O() notation
- Sorting and search
- Algorithms on graphs: exploration, connectivity, shortest paths, directed acyclic graphs, spanning trees
- Design techniques: divide and conquer, greedy, dynamic programming
- Data structures: heaps, union of disjoint sets, search trees
- Intractability

**Next Week Assignment Answers**

This course can have Associate in Nursing unproctored programming communication conjointly excluding the Proctored communication, please check announcement section for date and time. The programming communication can have a weightage of twenty fifth towards the ultimate score.

- Assignment score = 25% of average of best 8 assignments out of the total 12 assignments given in the course.
**( All assignments in a particular week will be counted towards final scoring – quizzes and programming assignments).**- Unproctored programming exam score = 25% of the average scores obtained as part of Unproctored programming exam – out of 100
- Proctored Exam score =50% of the proctored certification exam score out of 100

**YOU WILL BE ELIGIBLE FOR A CERTIFICATE ONLY IF ASSIGNMENT SCORE >=10/25 AND**

**UNPROCTORED PROGRAMMING EXAM SCORE >=10/25 AND PROCTORED EXAM SCORE >= 20/50.**

**If any one of the 3 criteria is not met, you will not be eligible for the certificate even if the Final score >= 40/100.**

**CHECK HERE OTHERS NPTEL ASSIGNMENTS ANSWERS **

*BELOW YOU CAN GET YOUR NPTEL Design and analysis of algorithms Assignment 2 Answer 2023***?** :

**?**:

- Consider the following variation of the merge function, where the input lists A and B are assumed to be sorted, with no duplicated elements, and C is the output list.
python
`function StrangeMerge(A,m,B,n,C) {`

// A has m elements, B has n elements

i = 0; j = 0; k = 0;while (i+j < m+n) {

if (i == m) {C[k] = B[j]; j++; k++;}

if (j == n) {C[k] = A[i]; i++; k++;}`if (i < m and j < n) {`

if (A[i] < B[j]) {C[k] = A[i]; i++; k++;}

if (A[i] == B[j]) {i++; j++;}

if (A[i] > B[j]) {C[k] = B[j]; j++; k++;}

}

}

}

What does C contain after executing StrangeMerge(A,m,B,n,C)?

**Answer: C contains all values that occur in either A or B, but not in both input lists.**

- Suppose we modify mergesort as follows. We split the input into three equal segments, recursively sort each segment and then do a three way merge of the three sorted segments to obtain a fully sorted output.
If we work out the recurrence for this variant, we find that the worst case complexity is O(n log3 n), as opposed to O(n log2 n) for the usual divide and conquer that splits the input into two equal segments.

Let us call the new version 3-way mergesort. What can we say about the asymptotic worst case complexity of 3-way-mergesort with the usual mergesort?

**Answer: The asymptotic worst case complexity of 3-way mergesort is worse than that of usual mergesort.**

- Suppose a new generation CPU can process 10^10 operations per second. You have to sort an array with 10^8 elements. Which of the following is true?
**Answer: Quicksort will always take several hours while merge sort will always take less than 1 second.**

- Which of the following statements is not true about quicksort?
**Answer: If we randomly choose a pivot element each time, quicksort will always terminate in time O(n log n).**

- We have a list of three-dimensional points [(7,8,1),(3,7,5),(6,4,1),(6,9,5),(0,5,2),(9,9,0)]. We sort these in ascending order by the third coordinate. Which of the following corresponds to a stable sort of this input?
**Answer: [(0,5,2),(3,7,5),(6,4,1),(6,9,5),(7,8,1),(9,9,0)]**