Design and analysis of Algorithms – An algorithm is the best way to represent the solution of a particular problem in a very simple and efficient way. If we have an algorithm for a specific problem, then we can implement it in any programming language, meaning that the algorithm is independent of any programming languages.
Design and analysis of Algorithms is a MOOC based course that is 12 weeks in duration and can fulfill the criteria of 4 credits in a year. You can visit the NPTEL SWAYAM platform and register yourself for the course. This course is brought to you 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 Dean of Studies. His main research area is formal verification. He has active research collaborations within and outside India and serves on international conference programme committees and editorial boards of journals.
Who Can Join: Any discipline Students in BE/BTech Computer Science, 2nd/3rd year. PREREQUISITES: 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.
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.
Design And Analysis Assignment Week 8 Answers:-
Contents
Q1. Which of the following is a linear constraint?
Answer:- C – 7x ≤ 3xy + 14z – 12
Q2. A critical document has to be sent from Ougadougou to Timbuktu. To ensure that it reaches safely, three copies are made and entrusted to three different people to carry to the destination. They will each take a sequence of trains, buses and flights. To ensure that the document reaches safely, the three couriers are not allowed to take the same train, bus or flight at any stage along the route.
This can be modelled as a network flow problem where the source and target are the Ougadougou and Timbuktu, the cities along the way are nodes and each direct connection between two cities by train, bus or plane is an edge. The actual flow problem to be solved is to:
Answer:- D – Assign each edge capacity 1 and check that the maximum flow is at least 3.
Q3. A major political party’s main convention is currently in progress. The biggest 24 hour news channel in town wants full video coverage of all the major events. Unfortunately, some of these events overlap with each other. The channel’s programme managers are trying to compute the minimum number of camera teams needed to cover all the relevant events.
The programme managers decide to model this as a graph where the nodes are the major events to be covered and edges represent pairs of events with overlapping timings. In this setting, the graph theoretic question to be answered is:
Answer:- D – Find a minimum size vertex cover.
Q4. We wish to show that problem B is NP-complete. Which of the following facts is sufficient to establish this.
Answer:- D- There is a polynomial time reduction from SAT to B, and B has a checking algorithm.
Q5. We have constructed a polynomial time reduction from problem A to problem B. Which of the following is a valid inference?
Answer:- A – If the best algorithm for A takes exponential time, there is no polynomial time algorithm for B.
Design And Analysis Assignment Week 7 Answers:-
A greedy strategy is to buy when the price is low and sell when the price is high. The maximum money he can make in this case is 13: buy on day 2, sell on day 3 (+3), buy on day 4, sell on day 6 (+5), buy on day 7, sell on day 8 (+5).
To discourage speculation, the stock market has decided to charge a transaction fee. Each time 100 shares are bought or sold, Rs 1 has to be paid to the stock market.
Here is how we recursively compute Shambu’s best strategy now over a period of N days.
- On day i, Shambu can either buy or not buy 100 shares.
- If he does not buy on day i, it is as though he started his transactions directly on day i+1.
- If Shambu does buy on day i, the money he makes depends on when he sells the shares on days i+1,…,N.
Let Profit[i] be the money Shambu can make on days i,i+1,…,N, assuming he has no shares at the start of day i.
Q1. We want to write down a recursive expression for Profit[i].
- Profit[N] = 0
- For 1 ≤ i < N, Profit[i] = ??
Answer:- D – max(Profit[i+1], Profit[i+2] + Price[i+1] – Price[i] – 2, Profit[i+3] + Price[i+2] – Price[i] – 2, … Profit[N] + Price[N-1] – Price[i] – 2, Price[N] – Price[i] – 2)
Q2. What is the size of the memo table for this problem?
Answer:- B – N
Q3. What is a good order to compute the values of Profit[i] using dynamic programming?
Answer:- A – From Profit[N] to Profit[1]
Q4. How much time will dynamic programming take to compute Profit[1]?
Answer:- C- O(N2)
Q5. What is the value of Profit[1] in the example given in the problem statement?
Answer:- B – 8
Design And Analysis Assignment Week 6 Answers:-
Q1. Suppose we implement a binary search tree without a parent pointer in each node. So each node has a value and pointers to the left and right children. What would be the complexity of computing the successor for a node in such an implementation for a balanced search tree on n nodes?
Answer:- a) O(n) for all nodes
b) O(log n) for all nodes
c) O(log n) for a node with a right child, O(n) otherwise
d) O(log n) for a node with a right child, O(n log n) otherwise
Q2. We have n distinct values stored in a height balanced (AVL) binary search tree. Which of the following statements is always true?
Answer:- a) The value at each node is the median of the values in the subtree rooted at that node.
b) The shortest path between any pair of nodes is at most O(log n).
c) For any node, the difference between the size of the left subtree and the right subtree is at most 3.
d)The number of leaf nodes is greater than or equal to the number of internal nodes.
Q3. Postorder traversal lists out the nodes in a binary tree as follows.
- First do a postorder traversal of the left subtree of the root.
- Then do a postorder traversal of the right subtree of the root.
- Finally list out the value at the root.
The postorder traversal of a binary search tree with integer values produces the following sequence: 17, 28, 25, 51, 98, 55, 42, 37. What is the value of the left child of the root of the tree?
Answer:- a) 37
b) 28
c) 25
d)`17
Q4. Consider the following function to traverse a search tree t with integer values, where prime(m) returns True if m is an even number and False otherwise.
function strangeOrder(t) {
if (t != NIL) {
if (prime(t.value)){
strangeOrder(t.left);
print(t.value);
strangeOrder(t.right);
}else{
strangeOrder(t.right);
print(t.value);
strangeOrder(t.left);
}
}
}Answer:- a) O(n) whether the tree is balanced or unbalanced.
b) O(n log n) whether the tree is balanced or unbalanced.
c) O(log n) if the tree is balanced, O(n) otherwise.
d) O(n) if the tree is balanced, O(n log n) otherwise.
Q5.Suppose we build a Huffman code over the four letter alphabet {a,b,c,d}, where f(a), f(b), f(c) and f(d) denote the frequencies (probabilities) of the letters and f(a) > f(b) > f(c) > f(d). Which of the following conditions will result in a Huffman code assigning a 2 bit code for each letter?
Answer:- a) f(a) > f(c)+f(d)
b) f(b) > f(c)+f(d)
c) f(a) > f(b)+f(c)+f(d)
d) f(c)+f(d) > f(a)+f(b)
Design And Analysis Assignment Week 5 Answers:-
Q1. An image is represented as an N×N array A of pixels. There is a function that transforms the image as follows:
- The function scans each pixel A[i][j]. Depending on the current value of A[i][j], some values in row i and column j are updated. It is possible that all values in row i and column j are updated. It is also possible that no values are updated.
- Updating a pixel takes time O(log N).
- Each pixel in the image is updated at most once by the function.
What is the best upper bound you can estimate for the total time taken across all the updates made by the function?
Answer:- B – O(N2 log N)
Q2. In the Union-Find data structure, suppose we want to add an operation reassign(j,k) that moves item j to the same component as item k. What would be the complexity of this operation for a set with n elements?
Answer:- D – Not O(1) for either the array representation or the pointer representation.
Q3. In a min-heap, what is the most accurate description of the worst-case complexity of the operation find_max that reports the value of the largest element in the heap, without removing it?
Answer:- C – O(n)
Q4. After inserting 57 into a max-heap, the structure of the heap is [82,57,27,42,25,18,25,27,32]. What was the structure of the heap before inserting 57?
Answer:- D- [82,42,27,32,25,18,25,27]
Q5. Consider an alternative to binary search called ternary search that divides the input array into three equal parts and recursively searches one of these three segments. What can we say about the asymptotic worst case complexity of ternary search versus binary search?
Answer:- A- The complexity of ternary search is the same as that of binary search.
Design And Analysis Assignment Week 4 Answers:-
Q1. A regional airline serves 10 cities. It operates to-and-fro return flights between 9 pairs of cities in such a way that every city is reachable from every other city through a sequence of connecting flights. We know the fuel consumption for the direct flights between each pair of cities. We want to compute the minimum fuel consumption from a given city to every other city in the airline network. Which of the following is true for this specific situation?
Answer:- B – We can use BFS or Dijkstra’s algorithm to compute this, but not DFS.
Q2. An airline charges a fixed price for each direct flight. For each sequence of hopping flights, the ticket price is the sum of the fares of the individual sectors, TripGuru has precalculated the cheapest routes between all pairs of cities on this airline’s route network so that it can offer an optimum choice instantly to customers visiting its website. The government decides to impose a 3% luxury tax on each sector. Which of the following describes the impact of this surcharge on TripGuru’s computation?
Answer:- C – The surcharge favours hopping flights with fewer sectors. TripGuru should recompute any cheapest route where there is a shorter route in terms of number of flights.
DAA WEEK 4 ASSIGNMENT ANSWER
Q3. An airline charges a fixed price for each direct flight. For each sequence of hopping flights, the ticket price is the sum of the fares of the individual sectors. TripGuru has precalculated the cheapest routes between all pairs of cities on this airline’s route network. To simplify administrative processing, the IT company has selected a subset of the airline’s routes so that all of their office locations are reachable from each other, and the total cost of traveling across all the chosen routes is minimum. The airline has decided to become a full-service carrier and has included a meal in each sector. To account for this, the airline has added a flat “convenience fee” of Rs 300 on each sector. Which of the following describes the impact of this surcharge on the IT company’s computation of which subset of routes to use?
Answer:- A- There is no impact. The IT company can retain the same subset of routes.
Q4. Suppose we have a weighted undirected graph with negative edge weights. Which of the following is correct?
Answer:- D – Both Krusksl’s algorithm and Prim’s algorithm can be used to compute an MCST.
Q5. Suppose we run the Bellman-Ford algorithm on a weighted graph with n vertices and observe that some distances decrease in iteration n+1. Which of the following is not a valid conclusion.
Answer:- D – Some shortest path entry in iteration n+1 must be negative.
Design And Analysis Assignment Week 3 Answers:-
Q1. An undirected graph G on 37 vertices has 5 connected components. What is the minimum number of edges in G?
Answer:- B – 32
Q2. Suppose we have a directed graph G = (V,E) with V = {1,2,…,n} and E is presented as an adjacency list. For each vertex u in V, out(u) is a list [v1,v2,…,vk] such that (u,vi) in E for each i in {1,2,…,k. For each u in V, we wish to compute a corresponding list in(u) = [v1,v2,…,vk’] such that (vi,u) in E for each i in {1,2,…,k’. Let n be the number of vertices in V and m be the number of edges in E. How long would it take to construct the lists in(u), u in V, from the lists out(u), u in V?
Answer:- B-O(n + m)
Q3. Suppose we obtain the following DFS tree rooted at node F for an undirected graph Gr with vertices {A,B,C,D,E,F,G,H}. Which of the following cannot be an edge in the graph Gr?
Answer:- D- (A,H)
Q4. We are interested in topological orderings of the following DAG that satisfy one or both of the following constraints:
- 4 appears before 3
- 8 appears after 7
How many such orderings are there?
Answer:- B- 13
Q5. Assembling a laptop consists of several steps, such as fixing the motherboard, inserting the battery, putting in the keyboard, attaching the screen, etc. Suppose there are 10 steps, labelled A, B, C, D, E, F, G, H, I, J. Each step takes a day to complete and we have the following dependencies between steps.
Answer:- B- 8
Design And Analysis Assignment Week 2 Answers:-
Q1. Having collected Aadhaar information for each SIM card, a government agency wants to check that all the Aadhaar numbers entered in SIM card applications are actually valid, by comparing SIM card applications against the list of registered Aadhaar numbers. Which of the following is likely to be the best strategy for this?
Answer:- D
Q2. Suppose our aim is to sort an array in descending order. Which of the following statements is true?
Answer:- D
Q3. Suppose we want to sort an array in ascending order and we implement quicksort so that we always choose the last element in the array as the pivot element. Assume that the input is a permutation of {1, 2, …, n}. Which of the following would definitely be a worst case permutation of this input for this implementation of quicksort?
Answer:- C
Q4. Which of the following statements is not true?
Answer:– B
Q5. We have a list of pairs [(“Ashwin”,69),(“Sumati”,87),(“Tanuja”,69),(“Brinda”,87), (“Shabana”,72),(“Vijay”,60)], where each pair consists of a student’s name and his/her marks in a course. We sort these pairs in ascending order of marks. Which of the folllowing corresponds to a stable sort of this input?
Answer:- B
Design And Analysis Assignment Week 1 Answers:-
1. An algorithm has two phases. The first phase, initialization, takes time O(n3). The second phase, which is the main computation, takes time O(n2). What is the most accurate description of the complexity of the overall algorithm?
Ans:- B – O(n3)
2. We are using a computer that performs 108 basic operations per second. Also we are trying to determine the worst case time complexity of a library function that is 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 50 the function always returns well within one second, for inputs of size 500 it sometimes takes a couple of seconds and for inputs of size 5,000 it sometimes takes over 15 minutes. What is a reasonable conclusion we can draw about the worst case time complexity of the library function?
Ans:- A
3. Suppose f(n) is 2n4+4n+5 and g(n) is 7n3 + 5n2 + 12. Let h(n) be a third, unknown function. Which of the following is not possible.
Ans:- D
4. How many times is the comparison i <= n performed in the following program?
Ans:- C
Also Check:-
5. If T(n) is O(n4/3) which of the following is false?
Ans:- A
Also Check:- NPTEL » Art of C Programming Quiz Assigment Week 1 2021
[foobar id=”1315″]