Q.1 What is the order of growth of the solution to the Quicksort-like recurrence FN = 2N + 1 + 1/N + ∑ 1≤K≤N (Fk - 1 + FN - K) with F0 = 0?
1. 0 2. 1 3. 1/N 4. N 5. N log N 6. $ N^2$ 7. $ N^3$
Answer:- 5. N log N
Q.2 Which of the following is a drawback to analyzing algorithms by proving O- upper bounds on the worst case?
1. Generally cannot be used to predict performance. 2. Input model may be unrealistic. 3. Generally cannot be used to compare algorithms. 4. Likely to be too much detail in the analysis.
Answer:- Option 1 & 3
Q.3 What is the order of growth of the solution to the Quicksort-like recurrence FN = N2 + 1 + 1/N + ∑ 1≤K≤N (Fk - 1 + FN - K) with F0 = 0?
1. 0 2. 1 3. 1/N 4. N 5. N log N 6. $N^2$ 7. $N^3$
Answer:- 6. $N^2$
Week 2:- Recurrence Pop Quiz On Telescoping:-
Q.1 Solve the recurrence an = nan - 1 + n! for n > 0 with a0 = 1. Give a simple expression for an
Q.1 What is the tightest estimate you can prove on the memory consumption of a trie built off n non-empty patterns p1, p2,..., pn if all the patterns' lengths are bounded from above by L, and the sum of lengths of all patterns is no more than S?
Answer:- O(S)
Q.2 What is the time complexity of searching all occurrences of n patterns p1, p2,..., pn in text T of length |T| if all patterns have length at most L and the sum of their lengths is at most S?
Answer:- O(|T|L)
Q.3 What is the smallest possible number of nodes in a trie built off n patterns p1, p2,..., pn if all the patterns have the same length L > 0 ?
Answer:- L + 1
Q.4 If you take all the suffixes of a string S of length L and build a regular trie off those suffixes as patterns, what is the maximum possible number of nodes in such trie?
Answer:- L( L + 1 ) ⁄ 2 + 1
Q.5 What is the smallest possible number of nodes in a suffix tree of string S with length L?
Answer:- L + 1
Programming Assignment 1
Please go to the Algorithms on Strings folder then click on week 1 then click on programming assignmnet 1 there are some files download that and upload that files in the assignment exercise with their respective names.
Week 2:- Burrows-Wheeler Transform and Suffix Arrays
Q.1 What is the length of BWT(S) for a string S of length L?
Answer:- L
Q.2 What is the time complexity of the algorithm from the lectures used to build BWT(S) for a string S of length L?
Answer:- O(L)
Q.3 What is the time complexity of the algorithm from the lectures to build the inverse Burrows-Wheeler Transform of a string S of length L?
Answer:- O(L)
Q.4 What is the time complexity of the algorithm from the lectures to build a suffix array of a string S of length l?
Answer:- O(L2)
Programming Assignment 2
Please go to the Algorithms on Strings folder then click on week 2 then click on programming assignmnet 2 there are some files download that and upload that files in the assignment exercise with their respective names.
Q.1 For the Brute Force algorithm (from this lecture) matching some Pattern against the Text AAAAAAAAAT, which of the Patterns below will require the maximum number of comparisons throughout the whole algorithm?
Answer:- AAAA
Q.2 You've just tried to match the Pattern AACTAACAT against some Text starting from position 3 and you know that AACTAAC is the longest common prefix of the Pattern and the suffix of the Text starting in position 3:
???AACTAAC???????????????? AACTAACAT
What is the maximum amount by which you can shift the Pattern to the right without missing an occurrence of the Pattern in the Text?
Answer:- 4
Q.3 What are the values of the prefix function for the string AC AT AC AT AC AC A?
Q.4 What is the total number of times that the condition of the while loop will be checked in this pseudocode for ComputePrefixFunction if we call it for the string AC AT AC AT AC AC A?
Answer:- 15
Week 4:- Suffix Array Construction
Q.1 For the string S=AACGATAGCGGTAGA$, what will be the contents of array order after SortCharacters?
Q.4 For string S=AACGATAGCGGTAGA$, what will be the order of cyclic shifts of length 2 after SortDoubled with L = 1?
Answer:- [15,14,0,1,6,12,4,2,8,3,13,7,9,10,5,11]
Q.5 For string S=AACGATAGCGGTAGA$, what will be the contents of the array class for the cyclic shifts of length 2 after UpdateClasses?
Answer:- [2,3,6,7,5,11,4,8,6,9,10,11,4,7,1,0]
Q.6 For string S=AACGATAGCGGTAGA$, what will be the suffix array?
Answer:- [15,14,0,1,12,6,4,2,8,13,3,7,9,10,11,5]
Programming Assignment 3
Please go to the Algorithms on Strings folder then click on week 4 then click on programming assignmnet 3 there are some files download that and upload that files in the assignment exercise with their respective names.
Note:- We have to complete till Karatsuba's Multiplication Algorithm for week 5 according to our IP
Q.1 Consider the array with numbers that is input to the max subarray problem [1, 19, 5, -4, 7, 18, 15, -10 ] Select all true facts from the list below making sure that no incorrect choices are selected.
Answer:- 1. The output to the max subarray .problem should be 18-(-4) =22 2. The divide and conquer algorithm will compute the result of max subarray problem on the first half of the array, which in this instance yields the value 18 3. The divide and conquer algorithm will compute the result of max subarray problem on the second half of the array, which in this instance yields the value 11 4. The minimum element of the first half of the array is -4 and maximum element of the second half of the array is 18. These in turn form the result for the max subarray problem which is 22.
Q.2 Consider the recurrence that represents the running time for the max subarray problem: T(n) = { Θ(1) n ≤ 2 2T(n ⁄ 2) Otherwise
Answer:- 1. The case when n ≤ 2 represents the constant amount of work needed to find the max subarray for input arrays of size 1 or 2. 2. The recurrence assumes that n is a power of two, since repeated division by 2 can yield fractional results otherwise. 3. The θ (n) term in the recurrence for n> 2 represents the work to find minimum of first half and maximum of second half. 4. The recurrence and the running time are identical to that obtained for the mergesort algorithm covered earlier in course 1 of this specialization.
Week 1:- Karatsuba's Multiplication Algorithm
Q.1 The following questions concern the binary representation of numbers and addition. Note that we will write binary numbers as bn, ..., b0 where bn is the most significant bit whereas b0 is the least significant bit. However, represented as a list in the computer, the same number would be [b0, b1, ... , bn].
Answer:- 1. The number 6 in decimal is represented by the list [0, 1, 1] 2. Consider two lists [0, 1, 1] and [1, 1]. The sum of these two numbers is given by [1, 0, 0, 1] 3. The addition of a m bit number with a n bit number yields a number with as many as max (m, n) + 1 bits. 4. The algorithm for adding two n bit numbers runs in time θ (n).
Q.2 The following questions concern the grade school algorithm we studied in the lecture. Note that we will represent numbers as lists of bits. Select all the correct answers from the list below.
Answer:- 1. The grade school multiplication algorithms performs as many additions as the number of 1 bits in the second argument. 2. The shift operation performed at each step of the multiplication algorithm appends a 0 to the beginning of the list. 3. Consider the multiplication of two numbers represented by list a = [1, 0, 1] with b = [1, 1]. The grade school multiplication algorithm performs additions of the number [1, 0, 1,0] with the number [0, 1, 0, 11, yielding the result [1, 1, 1, 1]. Note the number an ... a0 is represented as a list [ a0, a1, ... , an ].
Q.3 The following question concerns the multiplication of two n bit numbers a and b represented by the lists using the divide and conquer scheme presented in the lecture. [ a0, ..., an - 1 ] and [ b0, ..., bn - 1 ] For any list of bits l, the number denoted by the list is denoted by [[l]]. Assume that n is a power of 2 and let m = n ⁄ 2.
Answer:- 1. The number denoted by the list [ a0, ..., an - 1 ] can be written as [[ [ a0, ..., am - 1 ] ]] + 2m [[ [ am, ..., an - 1 ] ]] 2. Karatsuba multiplication of two n bit numbers makes three recursive calls with two of the calls involving multiplication of m bit numbers and one call involving multiplication of at most m + 1 bit number. 3. Depending on the implementation details and the computer on which we run, there is a cutoff value of n such that for all inputs with greater than in bits, the worst case running time of Karatsuba's algorithm will outperform the worst case running time of grade school multiplication.
Week 1:- Master Method
Q.1 Consider a recurrence of the form : T(n) = { Θ(1) n ≤ 1 {3T(n/3) + Θ(n) otherwise Select all the correct options from the list below.
Answer:- 1) The recurrence above can be obtained from a divide and conquer scheme that divides inputs of size n into 3 subparts of size n/3 each. 2) Master method is applied with a = 6 = 3 and 1. Case-2 applies and the overall complexity is T(n) = Θ(nlog3(3) log(n)) = Θ(nlog(n)).
Q.2 Consider a recurrence of the form : T(n) = { Θ(1) n ≤ 1 {2T(n/3) + Θ(√n) otherwise Select all the correct options from the list below.
Answer:- 1) The recurrence denotes a divide and conquer scheme wherein the divide and combine steps take Θ(√n) time in total; 2) Master method is applied with a = 2 and b = 3. We have logb(a) = log3(2) which is a number between 0 and 1 but is greater than half. 3) Case-1 of the master method applies and the complexity of the algorithm is Θ(nlog3(2)).
Week 1:- Complex Numbers and Roots of Unity
Q.1 Select all the correct facts about complex numbers from the list below.
Answer:- 1. The complex number 3 + 4j has modulus 5. 2. The conjugate of the complex number rejΘ is given by re-jΘ 3. The complex number j is one of the fourth roots of unity. 4. For any complex number z, the numbers z + z̅ and z × z̅ are both real numbers. 5. The value of 1 ⁄ 1 + j is 1 ⁄ 2 (1 - j).
Q.2 Let wn denote the generator of the nth roots of unity for n ≥ 1. Select all the correct options from the list below.
Answer:- 1. wn = cos(2Π ⁄ n) + jsin(2Π ⁄ n) 2. wnn - 1 = w̅n = 1 ⁄ wn 3. If n is even and n ≥ 2 then w2n = wn / 2 4. For any 0 ≤ k < n we have wnk = w̅nn-k = 1 ⁄ w̅kn 5. 1 + wn + w2n + ... + wn-1n = for all n ≥ 2
Week 1:- FFT Algorithm and Applications
Q.1 Consider a sequence [ a0, a1, a2, a3 ]. Let [ A0, A1, A2, A3 ] be the discrete fourier transform of this sequence. Select all the correct options below.
Answer:- 1. The 4th roots of unity are {1, j, -1, -j}. 2. A0 = a0 + a1 + a2 + a3. 3. The DFT can be viewed as evaluating the polynomial a(x) = a0 + a1x + a2x2 + a3x3 for x = 1,j, -1 and - j respectively. 4. A2 = a(-1) = a0 - a1 + a2 - a3. 5. A1 andd A3 must be complex conjugates of each other as long as the sequence a0, a1, a2, a3 consist of real numbers. 6. A0 and A2 must always be real numbers as long as the sequence a0, a1, a2, a3 consist of real numbers.
Q.2 Let a0,...,a511 be a sequence of real numbers obtained from sampling wind velocity with 8 samples per minute over 64 minutes (roughly 1 hour). Suppose we compute the DFT and obtain the sequence [ A0,...,An-1 ]as the DFT coefficients.
Answer:- 1. A0 = ∑ $_{j=0}^{511} a_j$. 2. A256 = a0 - a1 + a2 - a3 + ... + a510 - a511 3. A128 corresponds to the frequency: 8 × 128 ⁄ = per minute = 2/minute. 4. The highest frequency component is A256 which corresponds to a frequency of 4/minute. 5. The reason we assign negative frequencies to components Aj for j > n ⁄ 2 is because they correspond to roots of unity $w_n^j$ which can be seen as "rotating" in clockwise direction (opposite direction to roots $w_n^j$ for j ≤ n ⁄ 2.
Week 1:- Problem Set 1
For the problem set 1 you need to go the Dynamic Programming, Greedy Algorithms Folder in that folder go to Week 1 Folder then there there is a file named "Problem Set 1.py". In that file there are question and the code blocks in which some code is written you can directly copy paste the code accordingly.
Dynamic Programming, Greedy Algorithms Folder -> Week 1 -> Open Problem Set 1.py -> Then in Problem Set 1 module click on Launch Lab -> Then Copy & Paste code accordingly -> Then Submit your assignment.
Week 2:- Rod Cutting Problem and Recurrence (Practice Quiz)
Q.1 Consider the rod cutting problem with the following price table:
Length
Price
2
1.9
3
2.2
5
4.2
Assume that "wasting" earns no revenue. We have a rod of length L = 11. Choose all the correct facts below.
Answer:- The optimal solution involves 1 cut of length 5 and 3 cuts of length 2.
Q.2 Consider the rod cutting problem with the following price table:
Length
Price
2
1.9
3
2.2
5
4.2
Assume that "wasting" earns a penalty that is −1 × waste length Let maxRev(L) denote the maximum revenue obtainable from a rod of length L with the price table fixed above. Fill in the missing portions of the recurrence below: maxRev(L) = { ?1 L < 0 { ?2 L = 0 { max (?3, maxRev(L - 2)+?4, maxRev(L - 3)+?5, maxRev(L - 5)+?6 otherwise
Answer:- 1. ?2 should be 0 2. ?4 should be 1.9 3. ?6 should equal the revenue of a cut of length 5.
Week 2:- Memoization
Q.1 Consider the rod cutting problem with the following price table:
Length
Price
2
1.9
3
2.2
5
4.2
Assume that "wasting" earns no revenue. We have a rod of length L = 9. Using the recurrence, we will fill out the memo table T below for the rod cutting problem for length L = 9
Q.1 Consider we wish to compute change for 48 cents given coins of denomination { 2, 5, 10, 20} cents. We design two tables
Tbl[j] that records the best solution in terms of number of coins for j cents. S[j] that records the "first" coin denomination that we need to use for obtaining the solution for Tbl[j] Select all the correct facts from the list below.
Answer:- 1. Tbl[j] = min(1 + Tbl[j - 2], 1 + Tbl[j - 5], 1 + Tbl[j - 10], 1 + Tbl[j - 20]) 2. Tbl[3] = ∞ denoting that we cannot make change for 3 cents using the given denominations. 3. Suppose we wish to recover the solution, let S[48] have the value 20 after we finish implementing the memoization. The solution recovery will add a 20 cent coin to our solution list and look up S[28]
Q.2 Consider the usual solution that people use to make change for target T.
-Take the largest denomination coin that is ≤ T let it be cj. -Give cj and recursively make change for T - cj. -Stop when the remaining change is 0. Consider the denominations {1,2,5,10,20,25} cents.
Answer:- 1. Suppose we wish to make change for 50 cents, our approach will provide two 25 cent coins as change, which is optimal. 2. The algorithm makes optimal decision for T = 49, using four coins: one 25 cent, one 20 cent and two 2 cent coins.
Week 2:- Knapsack Problem
Q.1 Throughout this quiz consider a knapsack problem with three items
Item
Value
Weight
I1
v1
w1
I2
v2
w2
I3
v3
w3
Once again we wish to maximize the total value of our steal while keeping weights under limit W. However, for each item we can steal arbitrarily many copies of that item. For instance, if we steal item I2 5 times, we have a value of 5v2 and weight 5w2. There is no limit on the number of times an item can be stolen.
Assume wj > 0 for each item: otherwise, we can take infinitely many copies of the items and the problem becomes undefined.
Answer:- This sort of situation can happen if Ij is a stock where we can invest in 0 or more units of the stock Ij.
Q.2 Refer to the problem introduced in the previous question.
Let maxValue(j, W) be the maximum value obtained for considering items Ij,...,I3 and weight limit W. Note that 1 ≤ j ≤ 4. In particular for j = 4, we obtain the empty list of items.
Select all the correct facts from the choices below.
Notation [a ⁄ b] is the value by computing a ⁄ b and rounding it down when a,b > 0.
Answer:- 1. The minimum number of times we can choose item Ij is 0 and maximum number of times is [ W ⁄ wj ] 2. maxValue(4, W) = 0 whenever W ≥ 0. 3. If the thief chose to steal item Ij, K ≥ 0 times, the remaining weight budget is W - kwj and value obtained is kvj.
Week 2:- Longest Common Subsequence
Q.1 Consider two strings:
s1 = "ATTCCGGAC" and s2 = "TTACGG"
We wish to find the longest common substring between these two strings.
Answer:- 1. The longest common substring is of length 5: "TTCGG" 2. Suppose we have committed to matching the second character "T" in s1 to the first character s2, the remaining decision is to optimally find the LCS for the suffix: TCCGGAC and TACGG
Q.2 Consider strings s1: ATCCG and s2: CACGC
We construct a memo table which for your convenience is labeled with the characters in strings s1 and s2
C
A
C
G
C
A
0
T
0
C
??7
??5
??6
0
C
??4
??3
0
G
??2
??1
0
0
0
0
0
0
0
Write down the values that will be filled in for the positions labeled with ??1 - ??7 in the memo table above and use those to select the correct answers below.
For the problem set 2 you need to go the Dynamic Programming, Greedy Algorithms Folder in that folder go to Week 2 Folder then there is a file named "Problem Set 2.py". In that file there are question and the code blocks in which some code is written you can directly copy paste the code accordingly.
Dynamic Programming, Greedy Algorithms Folder -> Week 2 -> Open Problem Set 2.py -> Then in Problem Set 2 module click on Launch Lab -> Then Copy & Paste code accordingly -> Then Submit your assignment.
Week 3:- Greedy Algorithms(Practice Quiz)
Q.1 Consider once again the coin changing problem with denominations: {1, 2, 5, 10} cents.
Answer:- 1. The greedy coin changing algorithm when applied to make change for 18 cents will utilize 4 coins. 2. If we added a 8 cent coin to our set of denominations, the greedy algorithm will not be an optimal algorithm for making change with the least number of coins.
Q.2 Consider a version of knapsack problem for a perfumer who has an empty perfume bottle with volume V = 10 ml and would like to mix ingredients in various proportions to maximize the total profit which is simply calculated by summing up the profit/unit volume of each ingredient times the volume of the ingredient used.
Liquid
Profit/Unit Volume
Available Amount
A
1.5 $/ml
10 ml
B
2.2 $/ml
4 ml
C
3.3 $/ml
3 ml
D
2.1$/ml
5 ml
E
1.7 $/ml
2 ml
Answer:- 1. The optimal solution would be to fill up 3 units of C, 4 units of B, and 3 units of D yielding a total profit of 3 x 3.3 + 4 x 2.2 + 3 x 2.1 = 25 dollars. 2. For solving problems like this, a greedy strategy would be to first take as many units of ingredient C as possible since that has the most profit per unit volume.
Week 3:- Greedy Interval Scheduling
Q.1 In this lecture, we saw how greedy algorithms were optimal for interval scheduling when our goal is to maximize the number of meetings held. Suppose we have the same problem setup of meetings with start/end times specified and our goal was to improve the overall room utilization : i.e, the amount of time the room is occupied in a meeting rather than the number of meetings.
Answer the following questions below by selecting the correct facts.
Answer:- 1. Suppose we design a greedy algorithm that first schedules the longest meeting, deletes all the conflicting meetings and recursively solves the remaining sub problem, this algorithm is not optimal in terms of total occupancy. 2. The greedy algorithm used to maximize the number of meetings held will not necessarily maximize the total time the room is occupied by a meeting. 3. Suppose all meetings are of the same duration then maximizing the number of meetings is equivalent to maximizing the total time utilized by the meetings.
