NPTEL Design and analysis of algorithms Assignment 4 Answer

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

NPTEL Design and analysis of algorithms Assignment 4 Answer – 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 4 Answer? If Yes You are in Our Great Place to Getting Your Solution, This Post Should be help you with the Assignment answer to the National Programme on Technology Enhanced Learning (NPTEL) Course “NPTEL Design and analysis of algorithms Assignment 4 Answer”

Table of Contents

NPTEL Design and analysis of algorithms Assignment

ABOUT THE COURSE :

This course will cover basic concepts in the design and analysis of algorithms.

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

INTENDED AUDIENCE: Students in BE/BTech Computer Science, 2nd/3rd year.

PRE-REQUISITES: Exposure to introductory courses on programming and data structures.

INDUSTRY SUPPORT: This course should be of value to any company working in the area of software services and products.

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.

Final score = Assignment score + Unproctored programming exam score + Proctored Exam 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 4 Answer 2022? :

All questions carry equal weightage. You may submit as many times as you like within the deadline. Your final submission will be graded.

Answers will be Uploaded Shortly and it will be Notified on Telegram, So JOIN NOW

All questions carry equal weightage. You may submit as many times as you like within the deadline. Your final submission will be graded.

2 points

We are given a directed graph, represented as an adjacency list, in which each vertex has at least one incoming edge and one outgoing edge. We would like to print out for each vertex j the list of vertices pointing into j. What is the most accurate description of the complexity of computing these quantities in terms of n, the number of vertices, and m, the number of edges?

O(n²)

O(nm)

O(m)

O(n)

Ans – C

2 points

Consider the following strategy to convert an undirected graph with negative edge weights to one that does not have negative edge weights. Let the maximum magnitude negative edge weight in the graph be -k. Then, for each edge in the graph with weight w, update the weight to w+k+1. Consider the following claim:

To solve the shortest path problem in the original graph, we can run Dijkstra’s algorithm on the modified graph and subtract the added weights to get the original distances.

Which of the following is not correct.

The claim is not true in general.

The claim is not true in general for graphs with cycles.

The claim is true for connected acyclic graphs.

The claim is true for all graphs.

Ans – D

2 points

Consider the following algorithm on a graph with edge weights.

Sort the edges as [e₁,e₂,…,e_m] in decreasing order of cost.
Start with the original graph. Consider each edge e_j. If this edge is part of a cycle delete it.

Which of the following is not true.

At most n-1 edges will be deleted.

After processing all m edges, the resulting graph is connected.

What remains at the end is a minimum cost spanning tree.

Exactly m-n+1 edges will be deleted.

Ans – A

Answers will be Uploaded Shortly and it will be Notified on Telegram, So JOIN NOW

2 points

Consider the following strategy to solve the single source shortest path problem with edge weights from source s.

Replace each edge with weight w by w edges of weight 1 connected by new intermediate nodes
Run BFS(s) on the modified graph to find the shortest path to each of the original vertices in the graph.

Which of the following statements is correct?

This strategy will solve the problem correctly and is as efficient as Dijkstra’s algorithm.

This strategy will solve the problem correctly but is not as efficient as Dijkstra’s algorithm.

This strategy will only work if the graph is acyclic.

This strategy will not solve the problem correctly.

Ans – B

Answers will be Uploaded Shortly and it will be Notified on Telegram, So JOIN NOW

2 points

Suppose we have a graph with negative edge weights. We take the largest magnitude negative edge weight -k and reset each edge weight w to w+k+1. Which of the following is true?

Kruskal’s algorithm will identify the same spanning tree on the new graph as on the old graph.

Minimum cost spanning trees in the original graph will not correspond to minimum cost spanning trees in the new graph.

Prim’s algorithm will not work on the modified graph but will work on the original graph.

There are more minimum cost spanning trees in the modified graph than in the original graph.

Ans – A

Yhaa You have done it but next? if YOU Want to your Others NPTEL Design and analysis of algorithms Assignment 4 Answer Then Follow US HERE and Join Telegram.

NPTEL Design and analysis of algorithms Assignment 4 Answer

NPTEL Design and analysis of algorithms Assignment

CHECK HERE OTHERS NPTEL ASSIGNMENTS ANSWERS

BELOW YOU CAN GET YOUR NPTEL Design and analysis of algorithms Assignment 4 Answer 2022? :

Related Posts

NPTEL Design and analysis of algorithms Assignment 8 Answer

NPTEL Design and analysis of algorithms Assignment 7 Answer

Leave a Reply Cancel reply