# NPTEL Design and analysis of algorithms ASSIGNMENT 2021

NPTEL Design and analysis of algorithms This course will cover basic concepts in the design and analysis of algorithms. Like Asymptotic complexity, O() notation, Sorting and search,Algorithms on graphs: exploration, connectivity, shortest paths, directed acyclic graphs, spanning trees

Design and analysis of algorithms is a MOOC course offered by Chennai Mathematical Institute on the NPTEL platform. The course is developed by Madhavan Mukund studied at IIT Bombay (BTech) and Aarhus University (PhD). He has been a faculty member at Chennai Mathematical Institute since 1992, where he is presently Professor and Director. His main research area is formal verification.

1. INTENDED AUDIENCE: Students in BE/BTech Computer Science, 2nd/3rd year.
2. Requirements/Prerequisites: Nil
3. INDUSTRY SUPPORT:This course should be of value to any company working in the area of software services and products.ams.

CRITERIA TO GET A CERTIFICATE

Average assignment score = 25% of the average of the best 6 assignments out of the total 8 assignments given in the course.
Exam score = 75% of the proctored certification exam score out of 100

Final score = Average assignment score + Exam score

Students will be eligible for CERTIFICATE ONLY IF AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75. If any of the 2 criteria are not met, the student will not get the certificate even if the Final score >= 40/100.

## NPTEL Design and analysis of algorithms ASSIGNMENT WEEK 3 ANSWERS:-

Q1. A connected undirected graph G has 1225 edges. What can we say about n, the number of vertices in G?

Q2. An airline serves 1000 cities and runs 5500 direct flights each day between these cities. Which of the following is a good data structure to represent the collection of flights?

FOR DESIGN AND ANALYSIS PROGRAMMING ASSIGNMENT:- DESIGN AND ANALYSIS OF ALGORITHMS

Q3. Suppose we obtain the following BFS tree rooted at node J for an undirected graph with vertices {A,B,C,D,E,F,G,H,I,J,K}.