DAA-2020 Week 01 Assignment 01

02/07/2020 Design and analysis of algorithms - - Unit 4 - Week 1 Quiz
(https://swayam.gov.in) (https://swayam.gov.in/nc_details/NPTEL)
[email protected] 
NPTEL (https://swayam.gov.in/explorer?ncCode=NPTEL) » Design and analysis of algorithms (course)
Announcements (announcements) About the Course (https://swayam.gov.in/nd1_noc20_cs27/preview)
Ask a Question (forum) Progress (student/home) Mentor (student/mentor)
Unit 4 - Week 1 Quiz
Course
outline Week 1 Quiz
How does an The due date for submitting this assignment has passed. Due on 2020-02-12, 23:59 IST.
NPTEL online As per our records you have not submitted this assignment.
course work?
All questions carry equal weightage. You may submit as many times as you like within the deadline.
Week 1 : Your final submission will be graded.
Introduction
1) An image processing application begins with two n×n matrices A and B. The first phase of 2 points
2
preprocessing the inputs takes O(n ) steps for each of A and B. The second step involves a convolution of
Week 1 : Analysis
A and B to yield a new matrix C in time O(n3). This is followed by an edge detection phase that takes
of algorithms
times O(n2) for matrix C. What is the most accurate and concise description of the complexity of the
overall algorithm?
Week 1 Quiz
O(n2)
Quiz : Week 1
Quiz O(n3)
(assessment? O(n2+n3)
name=93)
O(n5)
Week 2 : No, the answer is incorrect.
Searching and Score: 0
sorting Feedback:
When there are multiple phases in sequence, the largest of the phases dominates the overall complexity.
Week 2 Quiz Here the second phase is O(n3) and the first and third phases are O(n2).
Accepted Answers:
O(n3)
Week 2
Programming 2) We are trying to determine the worst case time complexity of a library function that is 2 points
Assignment provided to us, whose code we cannot read. We test the function by feeding large numbers of random
inputs of different sizes. We find that for inputs of size 300 and 3.000, the function always returns well
Week 3 : Graphs within one second, but for inputs of size 30,000 it sometimes takes about 1 second and for inputs of size
300,000 it sometimes takes 1-2 minutes. What is a reasonable conclusion we can draw about the worst
Week 3 Quiz case time complexity of the library function? (You can assume, as usual, that a typical desktop PC
performs 109 basic operations per second.)
https://onlinecourses.nptel.ac.in/noc20_cs27/unit?unit=92&assessment=93 1/3
Week 3 O(n log n)

Programming O(n2)
Assignment O(n3)
O(n3 log n)
Week 4 :
Weighted graphs No, the answer is incorrect.
Score: 0
Feedback:
Week 4 Quiz
Assuming a CPU with 109 operations per second, 3002 and 30002 would be well under 109 whereas 30000
is 9×108 = 0.9×109 (about 1 second) and 3000002 is 90×109 (about 1.5 minutes).
Week 4
Accepted Answers:
Programming
O(n2)
Assignment
3) Suppose f(n) is 2n3+4n+5 and g(n) is 7n5 + 5n3 + 12. Let h(n) be a third, unknown function. 2 points
Week 5: Data Which of the following is not possible.
Structures:
Union-Find and h(n) is O(f(n)) and h(n) is also O(g(n))
Heaps h(n) is O(f(n)) but h(n) is not O(g(n))
h(n) is O(g(n)) but h(n) is not O(f(n))
Week 5 : Divide
h(n) is not O(f(n)) and h(n) is also not O(g(n))
and Conqure
No, the answer is incorrect.
Score: 0
Week 5 Quiz
Feedback:
Since f(n) is O(g(n)), if h(n) is O(f(n)) it must also be O(g(n)). All other combinations are possible.
Week 6: Data
Accepted Answers:
Structures:
h(n) is O(f(n)) but h(n) is not O(g(n))
Search Trees
4) How many times is the comparison i >= n performed in the following program? 2 points
Week 6: Greedy
Algorithms int i = 200, n = 80;
main(){
while (i >= n){
Week 6 Quiz
i = i-2;
n = n+1;
Week 6
}
Programming
Assignment }
Week 7: Dynamic 40
Programming 41
42
Week 7 Quiz
43
Week 7 No, the answer is incorrect.
Programming Score: 0
Assignment Feedback:
After 40 iterations, i is 200-80=120 and n is 80+40=120. At this point, i==n so the 41st iteration succeeds
Week 8: Linear The next test of the while condition fails and exits the loop. Hence, overall the while condition is checked
Programming 42 times.
and Network Accepted Answers:
Flows 42
5) If T(n) is O(n2 √ n) which of the following is false? 2 points

Week 8:
Intractability T(n) is O(n2 log n)
T(n) is O(n3)
Week 8 Quiz
T(n) is O(n3 log n)
Text Transcripts T(n) is O(n4)

N h i i
No, the answer is incorrect.

Books Score: 0
Feedback:
√ n is not O(log n)
Download Videos
Accepted Answers:
T(n) is O(n2 log n)

DAA-2020 Week 01 Assignment 01

Uploaded by

Copyright:

Available Formats

DAA-2020 Week 01 Assignment 01

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

DAA-2020 Week 01 Assignment 01

Uploaded by

Copyright:

Available Formats

02/07/2020 Design and analysis of algorithms - - Unit 4 - Week 1 Quiz

NPTEL (https://swayam.gov.in/explorer?ncCode=NPTEL) » Design and analysis of algorithms (course)

Announcements (announcements) About the Course (https://swayam.gov.in/nd1_noc20_cs27/preview)

Ask a Question (forum) Progress (student/home) Mentor (student/mentor)

Unit 4 - Week 1 Quiz

Week 3 O(n log n)

5) If T(n) is O(n2 √ n) which of the following is false? 2 points

Text Transcripts T(n) is O(n4)

No, the answer is incorrect.

You might also like