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.
Week 3:- Huffman Codes
Q.1 Consider a large document with 5 letters {A, B, C, D, E} and the following percentages of occurrence for each of the five letters:
Letters
fraction of occurrence
A
35%
B
25%
C
20%
D
15%
E
5%
Consider how many bits each character gets allocated by a Huffman code:
Letters
# bits
A
bA
B
bB
C
bC
D
bD
E
bE
Select all the correct answers from the list below about the Huffman code generated for this example.
Answer:- 1. The construction of Huffman code will first merge D and E into a subtree. 2. bA = bB = 2 3. bC = 2 4. The average number of bits per character for the Huffman code is 2.2 bits/character
Q.2 Select all the correct facts about the behavior of the Huffman coding algorithm given a set of characters A1 ,..., An and their frequencies f1 ,..., fn.
Answer:- 1. The character with lowest frequency will always have the highest number of bits assigned. 2. The character with second lowest frequency will also have the highest number of bits assigned. 3. Supposen = 32 and we assign 5 bits to each character. A Huffman code will always assign 5 or fewer bits per character, on average.
Week 3:- Problem Set 3
For the problem set 3 you need to go the Dynamic Programming, Greedy Algorithms Folder in that folder go to Week 3 Folder then there is a file named "Problem Set 3.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 3 -> Open Problem Set 3.py -> Then in Problem Set 3 module click on Launch Lab -> Then Copy & Paste code accordingly -> Then Submit your assignment.
Note:- A video Tutorial has also been added to the same Dynamic Programming, Greedy Algorithms folder.
Named as "Tutorial for Problem Set 3.MOV" In week 3 for problem set 3. If anyone is facing any issue related
to do how to do week 3 problem set, then they can refer to that video. Or you can see it below.
Step-By-Step Guide for problem set 3
Tutorial.for.Problem.Set.3.mov
Week 4:- Decision Problems and Languages
Q.1 Select all the correct facts from the list be low.
Answer:- 1. Consider the language L = { 0, 10, 100, 110, ... } of binary encodings of all even numbers. An algorithm that recognizes L is also an algorithm that given a number returns true if even and false if odd. 2. Consider the problem of finding if a graph G is strongly connected (i.e, entire graph is a single SCC). The corresponding language is L = { < G > | G is a graph that is strongly connected } 3. It is possible to encode graphs as binary strings of 0s and 1s such that every graph G corresponds to a unique binary string.
Week 4:- Polynomial Time and Certificates
Q.1 Select all the problems for which we know of an efficient polynomial time algorithm through techniques studied thus far in this specialization.
Answer:- 1. Given a weighted graph G, does there exist a negative weight cycle? 2. Given a graph is there a spanning tree whose weight is less than K? 3. Given an array a of size n and a number k, are there more than n/4 elements which are >= k?
Q.2 Select all the correct answers regarding certificates from the list below.
Answer:- 1. Given a number n that is known to be a product of two large prime numbers (such numbers are used extensively in cryptography), we wish to find out the kth bit of its smallest prime factor. The certificate is the prime factor p itself. 2. Let G be a weighted directed graph and s,t be two vertices of G. We wish to know if there a path from s to t of length ≤ W. The empty string can be a certificate for this problem that can be checked in polynomial time. 3. Let G be an undirected graph. We wish to know if there is a cycle that visits all vertices of G exactly once. The certificate for a yes answer is given by the cycle itself
Week 4:- NP Completeness Reductions
Q.1 Suppose problem A reduces in polynomial time to problem B. Let us suppose that problem B cannot be solved in polynomial time. Does it mean that A cannot also be solved in polynomial time?
Answer:- No, it is possible that there is some other "more ingenious" way of solving A in polynomial time that does not involve a reduction to B.
Q.2 True of False: Every problem in P can be reduced in polynomial time to the k-clique problem of checking if a given graph G has a clique of size at least k.
Answer:- True: every problem P is trivially in NP and by Cook-Levin theorem all problems in NP can be reduced to 3-SAT and we saw in the lecture that 3-SAT was reduced in polynomial time to the k-clique problem.
Q.3 Suppose we have a polynomial time reduction from problem A to problem B, select all the true facts from the list below.
Answer:- 1. If there is no algorithm that can solve A in polynomial time, then there is no algorithm that can solve B in polynomial time. 2. If A is NP complete and B is in NP, then B is also NP complete.
Q.4 Suppose we wish to prove the travelling salesperson problem (TSP) discussed in the lecture is NP complete. Which of the following steps will be needed to do so?
Answer:- 1. We will need to show that TSP is in NP by showing that the yes answer comes with a certificate that can be checked in polynomial time. 2. We need to reduce 3-SAT or a previously known NP complete problem to the TSP in polynomial time. 3. A reduction from 3-SAT to TSP, will take a boolean 3-CNF-SAT formula and create a weighted graph G that is an instance of TSP.
Week 4:- NP Completeness Problems
Q.1 Consider a 3-CNF-SAT problem with n variables denoted x1,...,xm and m clauses. We wish to reduce it to a 0-1 ILP problem: Find z1 ∈ {0, 1} ,..., zn ∈ {0, 1} such that a set of m linear inequality constraints c1z1 + c2z2 + ... + cnzn ≥ c0 are all satisfied. Select all the true facts about the reduction.
Answer:- 1. We use a 0-1 variable zi corresponding to each variable xi in the original 3-CNF-SAT problem. 2. A clause of the form xi ∨ xj ∨ xk translates into an inequality zi + zj + zk ≥ 1. 3. The logical negation of a variable xi can be modeled as the arithmetic operation 1 - zi 4. The clause x̄ī ∨ xj ∨ x̄ī is translated to the inequality -zi + zj -zk ≥ -1 5. The reduction yields as many inequalities as the number of clauses in the 3-SAT formula
Q.2 An independent set in a graph is a subset of vertices such that no two vertices in the independent set have an edge between them. k-Indpendent-Set Problem Given a graph G and a number k, we wish to know if there is an independent set of size at least k in G.
Answer:- 1. The k Independent-Set problem is in NP since the certificate can involve just the set of k vertices that we claim to belong to an independent set. 2. A graph G has an independent set of size k if and only if its complement has a clique of size k. 3. We can reduce the problem of finding k-clique in a graph G to that of finding a k-independent-set in its complement Ḡ.
Week 4:- Problem Set 4
For the problem set 4 you need to go the Dynamic Programming, Greedy Algorithms Folder in that folder go to Week 4 Folder then there is a file named "Problem Set 4.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 4 -> Open Problem Set 4.py -> Then in Problem Set 4 module click on Launch Lab -> Then Copy & Paste code accordingly -> Then Submit your assignment.
For this lab just launch lab and then cut the tab and refresh your course you will find it is already completed.
Week 1:- Basics of Linear Programs
Q.1 Consider the following linear program:
max 3x + 4y x + y ≤ 4 x ≥ 0 y ≥ 0
Check all options that are correct.
Answer:- 1. The optimal solution for the above LP is 16. 2. If we remove the constraint x + y ≤ 4 it is still a feasible LP problem. 3. If we changed the problem's objective function to min - 3x - 4y then the optimal solution for (x,y) remains unchanged.
Q.2 Consider the following scenario.
Green Energy Solutions is a company specializing in solar panel installations. They have a limited workforce and want to maximize their profit while adhering to certain constraints. The company has two types of solar panel installations: Type A and Type B.
Each Type A installation:
Requires 12 hours of labor
Costs $500 in materials
Generates $800 profit per installation.
Each Type B installation:
Requires 8 hours of labor
Costs $300 in materials
Generates $600 profit per installation.
The company has a total of 1000 labor hours available.
The company has $400,000 in cash at hand.
Due to supply constraints, the company can only install a maximum of 300 Type A panels.
Formulate a linear program to maximize the profits while adhering to the constraints above. Let decision variable A denote the number of type A installation and decision variable B denote the number of type B installations. Choose the correct answers from the choices given below.
Answer:- max 800A+600B 12A+8B≤1000 500A+300B≤400000 A≤300 A,B≥0
Q.3 Select all options that are linear programs.
Answer:- 1. min 5x+7y 3x+2y≤12 4x+5y≤15 x,y≥0
2. max 5x+3y 2x+y≤10 3x+2y≤15 x,y≥0
Q.4 max 2x+y x+y≥5 x,y≥0 The given linear program is:
Answer:- Feasible but not bounded
Q.5 Select all the options that are correct.
Answer:- An LP problem can have more than one optimal solution
Lab: Formulate and Solve LPs using PULP
For this lab just launch lab and then cut the tab and refresh your course you will find it is already completed.
Week 1:- Solving LPs using PULP
Q.1 What does the statement x_var = pulp.LpVariable('x', lowBound=0, upBound=10, cat='Continuous') achieve? Select all the correct answers. See documentation here: https://www.coin-or.org/PuLP/pulp.html
Answer:- 1. Setting cat=Continuous is optional since the category is set to Continuous by default. 2. In a linear programming problem, every decision variable should have cat = Continuous 3. It adds a decision variable 'x' to the problem.
Q.2 Consider the following code sinppet:
from pulp import *
mdl = LpProblem('my_problem', LpMaximize)
x = LpVariable('x', lowBound = 0)
y = LpVariable('y', lowBound = 0, upBound = 4)
mdl += (x + 2 * y)
mdl += x <= y + 3
mdl += x >= y - 1
mdl += x - 2 * y <= 5
status= mdl.solve()
print(x.value())
print(y.value())
print(mdl.objective.value())
Select all the correct facts about the code snippet above. Make sure that no incorrect facts are selected.
Answer:- 1. The LP problem as entered in the code snippet is feasible 2. The LP problem as entered in the code snippet is bounded. 3. The linear programming problem seeks to maximize the objective x + 2 * y 4. The constraint x − 2 y≤ 5 is part of the linear program.
Q.3 Consider again the code snippet from the previous problem
from pulp import *
mdl = LpProblem('my_problem', LpMaximize)
x = LpVariable('x', lowBound = 0)
y = LpVariable('y', lowBound = 0, upBound = 4)
mdl += (x + 2 * y)
mdl += x <= y + 3
mdl += x >= y - 1
mdl += x - 2 * y <= 5
status= mdl.solve()
assert status == LpStatusOptimal
print(x.value())
print(y.value())
print(mdl.objective.value())
Select all the correct choices from the list below
Answer:- All options are correct
Q.4 Consider the code snippet below:
from pulp import *
mdl = LpProblem('n_problem', LpMaximize)
n = 15
vars = [ LpVariable(f'x{i}', lowBound = 0.0) for i in range(n)]
mdl += lpSum(vars)
for i in range(14):
mdl += vars[i] - vars[i+1] <= i
mdl += vars[i] - vars[i+1] >= -i
status = mdl.solve()
if status == LpStatusOptimal:
print('Optimal solution found!')
print([vi.value() for vi in vars])
print(mdl.objective.value())
elif status == LpStatusInfeasible:
print('Infeasible problem')
elif status == LpStatusUnbounded:
print('Unbounded problem')
else:
print('Unknown status')
Answer:- 1. The objective for this problem is the sum of all the variables in the list vars 2. Line 4 of the problem declares n=15 variables and stores them in the list vars 3. The problem is unbounded.
Interactive Notes: Diet Problem and Network Flow Problems
For this lab just launch lab and then cut the tab and refresh your course you will find it is already completed.
Week 1:- Network Flow Problems as LPs
Q.1 Select all the options that are true for network flow problems. Assume all edge capacities are finite and non-negative.
Answer:- 1. At each vertex , the incoming flow equals the outgoing flow. 2. Network flow problems are always feasible as long as the graph is connected. 3. Flow capacity can be less than or equal to the capacity of the edge.
Q.2 For the given network , what is the maximum flow that can be transported from source to sink ?
Answer:- 15
Q.3
Select all the correct flow conservation constraints from the list below.
Q.1 If a LP has an optimal solution, then at least one solution can always be found at:
Answer:- the vertices of the feasible region.
Q.2 Consider the following objective function min 4x + 2y + 3z The feasible region is a convex polyhedron with the following vertices A(2, 3, 1), B(4, 1, 2), C(5, 4, 1), D(3, 5, 3), and E(1, 2, 1). we have provided a name for each vertex and its coordinates The optimal value for this LP is:
Answer:- 9
Q.3 Select all that apply for a convex polyhedron in the context of linear programming.
Answer:- 1. The optimal solution always lies at one of the vertices of the convex polyhedron. 2. Every point within the convex polyhedron , forms a feasible solution. 3. For any 2 points within the convex polyhedron , the line segment joining the 2 points also lies completely within the polyhedron. 4. Convex polyhedron is formed by the intersection of half spaces defined by constraints.
Q.4 Which of the following graphs correctly depicts the feasible region for the given LP : max 4x + 3 2x + y ≤ 8 x + 2y ≤ 6 x ≥ 0 y ≥ 0
Answer:-
Interactive Notes on Geometry of Linear Programs and Simplex Algorithm
For this lab just launch lab and then cut the tab and refresh your course you will find it is already completed.
Week 1:- LP Algorithms
Q.1 Select all options that are true about vertices of a polyhedron.
Answer:- 1. A vertex of a polyhedron satisfies all the constraints. 2. Vertex lies on at least n faces of the polyhedron , where n is the number of decision variables.
Q.2 Which of the following statements are true about the simplex algorithm in LP ?
Answer:- 1. At every iteration , the algorithm moves to an adjacent vertex to improve the value of the objective function. 2. The average case time complexity for simplex algorithm is polynomial time.
Problem Set # 1 :- Programming Assignment: Linear Programming
Q.1 Consider the integer linear programming problem: max 2x1 + 3x2 s.t. x1 ≥ 0 x1 ≤ 9.8 x2 ≥ 0 x2 ≤ 10.5 x1, x2 ∈ Z Select all true facts about this problem below, ensure no wrong facts are selected.
Answer:- 1. The LP relaxation achieves an optimal objective value of 51.1 whereas the ILP optimal solution is 48. 2. The integrality gap for this problem is 51.1/48 3. The problem has an optimal solution and it is given by x1 = 9, x2 = 10.
Q.2 Select all the true facts about integer linear programming problems in relation to their LP relaxations. Make sure that no incorrect fact is selected.
Answer:- 1. If the ILP is unbounded, the LP relaxation is unbounded too. 2. If the problem involves maximizing an objective, the optimal ILP objective is always less than or equal to that of the LP relaxation.
Q.3 The following questions concern the NP-completeness of integer linear programming. Please select all correct facts.
Answer:- All are correct.
Q.4 Suppose we are given an ILP which seeks to minimize an objective functions subject to constraints. We solve the LP relaxation and find an optimal solution with the objective evaluating to 54.3
What can you say about the original ILP.
Answer:- 1. If the ILP is feasible, its optimal solution must be greater than or equal to 54.3 2. It is possible that the ILP's optimal solution (if it exists) will be 76.5 X 102331 3. If the ILP is feasible, it is guaranteed to be bounded. 4. If the integrality gap of the ILP problem was known to be 3, then the ILP optimal solution will be in the range [ 54.3,3 X 54.3]
Week 2:- Formulating/Solving ILPs
Important Note
The problems below ask you to setup and solve ILPs using Pulp. It helps to have python3 installed in your computer. If you have a package manager such as pip/conda, you can directly use them to install pulp library. This will allow you to program in python either through your REPL, or through an IDE such as Atom, VSCode, IntelliJ PyCharm and so on.
Alternatively, if you are not setup to program on your local machine, we suggest using google colab to have a python3 jupyter notebook. In the very first cell of the notebook type !pip3 install pulp to install the pulp library. In the next cell please type from pulp import * to check if it got installed.
You can type python programs to solve the ILPs and find out the answers for the problems below.
Write down the optimal value of the objective function correct to two decimal places.
Answer:- 40.00
Q.2 Solve the LP relaxation of the ILP from the previous problem using PuLP. What is the answer obtained?
Answer:- 40.00
Q.3 What can you conclude from solving the LP relaxation and original ILP for the previous problem.
Answer:- 1. They have the same solution. 2. The LP relaxation yields an integral solution for all the decision variables and we know from just that information that the ILP will also have the same optimal solution. 3. The integrality gap is 1.
The questions below pertains to the following ILP max 2x1 - 3x2 + x3 s.t. x1 - x2 ≥ 5 x1 - x2 ≤ 0.75 x2 - x3 ≤ 1.25 x2 - x3 ≥ 0.95 x1, x2, x3 ∈ [-1, 1] x1, x2, x3 ∈ Z
Q.4 What is the status obtained when solving the ILP?
Answer:- Infeasible
Q.5 What is the status of the LP relaxation?
Answer:- Optimal solution obtained
Interactive Notes: Vertex Cover as an ILP
For this lab just launch lab and then cut the tab and refresh your course you will find it is already completed.
Week 2:- Vertex Cover Problem ILP formulation
Q.1 Which of the following statements is true about an optimal solution to the vertex cover problem?
Answer:- It includes the minimum number of vertices that cover all edges
Q.2 If you add a constraint 'xi + xj <= 1 for some edge (i, i)' to the vertex cover problem, what will be the effect?
Answer:- Some valid vertex covers will be excluded
Q.3 Which of the following is a correct integer linear programming formulation for the vertex cover problem?
Answer:- Minimize ∑ xi subject to xi + xj >= 1 for every edge (i, j) and xi in {0, 1} for every vertex i
Q.4 Given a graph with vertices (1, 2, 3, 4} and edges (1, 2), (2, 3), (3, 4), which of the following is a feasible solution for the vertex cover problem?
Answer:- 1. {2,4} 2. {1,3}
Q.5 In an integer linear programming formulation, why is the condition 'xi in (0, 1} for every vertex i' necessary for the vertex cover problem?
Answer:- It ensures that the solution is a vertex cover
Interactive Notes: Integrality Gap for Vertex Cover
For this lab just launch lab and then cut the tab and refresh your course you will find it is already completed.
Week 2:- Vertex Cover ILP, LP Relaxation and Integrality Gap.
Q.1 We wish to find the optimal vertex cover for a graph G. Solving the LP relaxation of the vertex cover problem yields an optimal solution with value 442. What can we say about the size of the optimal vertex cover of the graph G? Choose all the options that are correct.
Answer:- 1. The optimal vertex cover size lies in the range [442, 884]. 2. Using the rounding procedure on fractional solutions of the LP relaxation would yield a vertex cover of size between 442 and 884.
Q.2 Calculate the optimal vertex cover for the graph below. Feel free to use the code/notes provided as part of the ungraded lab. Hopefully you have a python setup either on your computer with the pulp library installed or you are using google colab as indicated in the previous quiz on solving ILPs.
Answer:- 5
Q.3 Solve the LP relaxation for the graph in the previous problem and write down its optimal objective value below.
Answer:- 3.5
Q.4 If we rounded the LP relaxation for the problem above, what is the vertex cover we obtain?
Answer:- All the vertices of the graph are part of this cover.
Interactive Notes: Branch and Bound Solvers for ILPs
For this lab just launch lab and then cut the tab and refresh your course you will find it is already completed.
Week 2:- Branch and Bound Solvers
Q.1 Suppose we are solving an ILP using branch and bound algorithm. Select all the facts below about the algorithm that are true.
Answer:- 1. Each step of branch and bound solves the LP relaxation of some ILP problem that is either the original problem or obtained by branching. 2. If the LP relaxation at the "root" of the branch and bound is infeasible, the whole ILP must be infeasible. 3. If the original ILP is unbounded, then the LP relaxation at the root of branch and bound (the very first LP we will solve) will be unbounded.
Q.2 We are solving a branch and bound problem and at some stage, we solve a LP relaxation that yields the solution x1 = 2.5, x2 = 1.3, x3 = 5, x4 = 6.9.
Select all the valid options for the branch and bound algorithm.
Answer:- 1. We recursively solve two subproblems with the constraints x4 ≤ 6 and x4 ≥ 7, respectively. 2. We may recursively solve two subproblems with the constraints x1 ≤ 2 and x1 ≥ 3, respectively.
Q.3 We are solving an ILP whose objective function is max x1 + x2 - x3. At some point in the branch and bound algorithm, we have seen integer solutions shown below:
x1
x2
x3
objective
1
2
-1
4
4
1
2
3
5
2
-2
9
1
1
1
2
Select all true facts from the list below.
Answer:- 1. Suppose we solve an LP relaxation and find that the objective value is 9.8 , we can prune this branch from further consideration. 2. Suppose we solve an LP relaxation and find that the objective value is 8.5, we can prune this branch from further consideration. 3. The optimal solution of the ILP will have objective value greater than or equal to 9.
Problem Set # 2 :- Programming Assignment: Integer Linear Programs
Q.1 We have designed an efficient 2-factor approximation algorithm for a minimization problem. Running the approximation algorithm on an instance yields a solution with objective value 12. What can we say about the optimum?
Answer:- The optimal solution is in the range 6 ≤ OPT ≤ 12.
Q,2 We have designed an efficient 3-factor approximation algorithm for a maximization problem. Running the approximation algorithm on an instance yields a solution with objective value 12. What can we say about the optimum?
Answer:- 1. The optimal solution may be the same as that of the approximation algorithm. 2. The optimal solution is in the range 12 ≤ OPT ≤ 36
Interactive Notes: Jobshop Scheduling
For this lab just launch lab and then cut the tab and refresh your course you will find it is already completed.
Week 3:- Job Shop Scheduling Questions
The questions below concern the following instance of the jobshop scheduling problem.
Job ID
Time
1
5
2
6
3
2
4
5
5
2
6
1
7
3
8
4
Q.1 Consider an instance of the minimum makespan scheduling above. Suppose we have three processors. What is the makespan achieved if we ran the greedy algorithm. You can simply use a pencil and paper to run the greedy algorithm to work out the answer. Assume that the algorithm processes the jobs in the increasing order of Job ID.
Answer:- 11
Q.2 What is the makespan of the solution
Processor
Job IDs
1
2, 3, 5
2
1, 6, 7
3
4, 8
Answer:- 10
Q.3 Suppose we sorted the jobs in decreasing order of their times instead and ran the greedy algorithm. What is the makespan of the optimal solution obtained?
Answer:- 10
Q.4 Without solving the optimal problem, we wish to find bounds on the optimal solution anyways. Which of the following options are valid arguments that serve to place bounds on the optimal solution.
Answer:- 1. The total times for all jobs is 28. No matter how we distribute it among three processors, at least one processor must have finish time more than $\frac{28}{3}$ or 9.3333.... Therefore, the optimal answer cannot be smaller than 10. 2. The algorithm is known to have an approximation ratio of 2 - $\frac{1}{3}$ = $\frac{5}{3}$. Therefore, the optimal solution has to be at least 11 × $\frac{3}{5}$ ≈ 6.6 3. The following assignment:
Processor
Job IDs
1
2, 3, 5
2
1, 6, 7
3
4, 8
has a makespan of 10. And therefore, the optimal solution must have value $\leq 10$. 4. By pigeon hole principle, if we consider the first four job IDs 1, 2, 3, 4; at least two of the jobs must share the same processor in any assignment. This yields a lower bound of 7 on the optimal solution.
Interactive Notes on Vertex Cover Approximation Algorithms
For this lab just launch lab and then cut the tab and refresh your course you will find it is already completed.
Week 3:- Vertex Cover
The questions below concern the following graph with 7 nodes.
Q.1 Suppose we apply the greedy algorithm that repeatedly chooses the maximum degree node in the graph, adds it to the cover and then deletes it from the graph. Note that we break ties between multiple vertices that have the same degree by choosing the vertex with lowest number/ID.
Answer:- 1. Node 4 is the second node added to the cover. 2. Node 3 is the very first node added to the cover. 3. Node 6 is the third node added to the cover. 4. The greedy algorithm produces a vertex cover of size 5 that involves nodes 1, 3, 4, 5, 6
Q.2 Suppose we ran the greedy algorithm based on maximal matching and processed the edges in the following order:
What is the size of the vertex cover that we obtain?
Answer:-6
Interactive Notes on Maximum Satisfiability Approximation
For this lab just launch lab and then cut the tab and refresh your course you will find it is already completed.
Week 3:- Max-SAT Approximation
The problems below concern the following instance for the MAX-SAT problem involving propositional variables ${x_1}$, ${x_2}$, ${x_3}$, ${x_4}$. Note that ∨ stands for Or, $\overline{x_j}$ epresents the negation of ${x_j}$
Consider the MAXSAT instance involving the following clauses. ${x_1}$ ∨ ${x_2}$ ∨ $\overline{x_4}$ $\overline{x_2}$ ∨ ${x_3}$ ∨ ${x_4}$ ${x_1}$ ∨ $\overline{x_2}$ ∨ ${x_3}$ ${x_2}$ ∨ $\overline{x_3}$ ∨ $\overline{x_4}$
Q.1 What is the expected number of clauses that a randomly chosen truth assignment where each variable is independently assigned true/false with probability $\frac{1}{2}$ .
Answer:- 3.5
Q.2 Using just the information from the previous problem select which fact you can conclude.
Answer:- There is a truth assignment that satisfies all the clauses.
Q.3 Suppose we set ${x_1}$ = true, what is the expected number of clauses we can satisfy in the resulting formula?
Answer:- 3.75
Q.4 Suppose we set ${x_1}$ - false, what is the expected number of clauses we can satisfy in the resulting formula?
Answer:- 3.25
Q.5 What truth value will our approximation algorithm for MAXSAT assign to ${x_1}$ ?
Answer:- True
Problem Set # 3 :- Programming Assignment: Approximation Algorithms
Interactive Notes on TSP Basics, NP-Hardness and Inapproximability
For this lab just launch lab and then cut the tab and refresh your course you will find it is already completed.
Week 4:- TSP Basics
Q.1 The questions below concern the following TSP instance involving 5 nodes:
Edges shown in black are assigned a weight of 1 whereas edges shown in red are assigned a weight of 2.
Q1. Select all the correct answers from the list below.
Answer:- 1. The sequence of vertices 1,2,3,4,5, 1 (1 is the start/end point) is a valid TSP tour of cost 6 2. There is a TSP tour whose cost is 5, i.e, it involves only the black edges in the graph.
Q.2 The TSP above is an instance of a Metric TSP. It is symmetric and satisfies the triangle inequality.
Answer:- True
Q.3 This question concerns the following instance of the Hamiltonian Cycle Problem:
We wish to find out if there is a Hamiltonian cycle problem using a reduction to the TSP problem. Select all the correct answers about this reduction.
Answer:- 1. The reduction will need to assign a weight of 1 to each edge in the original graph and add the missing edges (4,5), (1,3) and (2,4) with some weight ${W > 1}$. 2. Let ${W > 1}$ be the weight given to the missing edges that we will need to add back for the reduction to TSP. The optimal TSP tour cost will be at least ${5 + W}$ if there is no Hamiltonian cycle. 3. Once we reduce to the TSP, we conclude the presence of a Hamiltonian cycle if the optimal TSP tour has weight 6.
Interactive Notes on Exact Approaches to TSP
For this lab just launch lab and then cut the tab and refresh your course you will find it is already completed.
Week 4:- Held-Karp Algorithm
The problem below concerns the following TSP instance. Edges shown in black have a weight of 1 1 whereas red edges have a weight of 3.
Assume vertex 1 is the designated start/end point of the tour. Let $C_{ij}$ represent the cost of the edge from vertex i to vertex j.
Q.1 Which of the following expressions is the appropriate equation for the value of $minCostPath(\{2,3\},4)$?<br Answer:- $\min(\text{{minCostPath}}(\{2\},3) + C_{3,4}, \text{{minCostPath}}(\{3\},2) + C_{2,4})$
Q.2 Calculate the value of $minCostPath(\{2,3\},4)$?<br Answer:- 3
Q.3 What vertex in the graph would you associate with the memo table corresponding to $minCostPath(\{2,3\},4)$ to recover the minimum cost path?<br Answer:- 3
Q.4 Consider the recurrence for the minimum cost TSP tour:
Select appropriate choices for the missing portions.
The following problems concern the TSP instance below. Black colored edges have weight 1 1 whereas red edges have weight 2.
We consider both the encodings MTZ and subtour elimination as presented in our interactive notes. Note that they are more general than the ones in the video which did not go into the details for non-symmetric cases. Please read through these notes and look at the provided code before attempting the problems below.
Q.1 Select all the correct facts about the ILP encoding/decision variables $x_{i,j}$ .
Answer:- 1. Setting the variable $x_{i,j} = 1$ denotes that we go from vertex i to j using the edge (i,j) in our tour. 2. The constraint $x_{2,1} + x_{3,1} + x_{4,1} + x_{5,1} = 1$ expresses that we have exactly one edge entering the vertex 1 in our tour.
Q.2 Select all the correct facts about the MTZ encoding as it pertains to the problem above.
Answer:- 1. Time stamp variables $t_2,t_3,t,_4,t_5$ are added to eliminate possible subtours by assigning increasing time stamps to nodes visited along a tour. 2. The constraint t3 ≥ t2 + x2,3 - M(1 - x2,3) for a large number M is equivalent to if x2,3 = 1 then $t_3 \geq t_2 + 1$ else $t_3 \geq t_2 - M$
Q.3 Suppose we solve the degree ILP relaxation and obtain a subtour {2,3,5}, which of the following inequalities will eliminate the subtour. Once again, please refer to the detailed notes which present the general case for non-symmetric TSPs rather than the video lecture which is restricted to the symmetric case.
Suppose we have a TSP instance for which the minimum spanning tree (MST) is shown below.
The edges not in the MST have not been shown. We perform a depth first traversal of the TSP and it yields the following sequence of visits that form a TSP tour:
[1,2,5,6,3,4]
Note that we take vertex 1 to be the start/end point.
Q.1 Which of the following are the shorcut edges in the TSP tour constructed?
Answer:- 1. (6,3) 2. (5,6) 3. (4,1)
Q.2 What can we say for sure about the cost of the edge (6,5) denoted $C_{6,5}$ in the original TSP?
Answer:- 1. $C_{6,5} ≤ 2$ 2. $C_{6,5} = C_{5,6}$
Q.3 What can we say for sure about the cost of the TSP tour [1,2,5,6,3,4] obtained computed by shorcutting the MST as above? Select all choices that apply
Answer:- 1. The cost of the tour must be less than or equal to twice the cost of the MST. 2. The cost of the TSP tour must be ≤ 10
Q.4 Which of the following statements about the cost of the optimal TSP tour for the instance above can be concluded.
Answer:- 1. The optimal tour cost has to be ≥ 5. 2. The optimal tour cost has to be ≤ 10.
Proceeding with the previous example, the odd degree vertices in the MST are {1,4,5,6} each of which is a leaf and has degree 1. Suppose we construct a minimum weight matching over these odd degree vertices to obtain the following graph which shows the original MST edges in black and the matching edges and weights in blue.
An Eulerian tour of this graph is obtained as
[1,2,5,4,3,2,6,1]
You can verify that this tour visits all edges in the graph formed by MST and matching edges.
Q.5 Which of the following is the TSP tour that will be obtained by shortcutting the Eulerian tour?
Answer:- [1,2,5,4,3,6]
Q.6 Which of the following is a valid observation about the cost of the TSP tour obtained by shortcutting the Eulerian tour?
Answer:- 1. Cost of TSP tour is less than or equal to 8.7 2. The cost of the tour must be less than or equal to the cost of all the edges in the matching + cost of all edges in the MST 3. Cost of TSP tour is less than or equal to 10 (the bound we placed on the cost of the previous tour using DFS).
Week 4:- Fully Polynomial Time Approximation Scheme
Q.1 A fully polynomial time approximation scheme for a maximization problem guarantees a solution within ( 1 - ∊ ) OPT where OPT is the optimal solution value in time $n^2 × \left(\frac{1}{\epsilon}\right)^2$. . We wish to compute an approximation that is guaranteed to be no worst than 0.9OPT What is the time cost for the algorithm?
Answer:- $100n^2$
The questions below concern a Knapsack problem instance with 4 items and the following data about weights and value.
a1
a2
a3
a4
Weight
2
4
3
1
Value
1
2
1
1
The total weight budget is $ 6 $.
Recall that $W_{i,v}$ is defined as the minimum weight of items needed to achieve value exactly v while choosing the subset of items { a1,...,ai }
Also recall the recurrence/base cases for $W$
$W (0,0) = 0, W (0,v) = ∞$$if$$v > 0, W (i,0) = 0$ $W (i,v) = min( W (i - 1,v), W (i - 1, v - v_i) + w_i )$ where $w_i, v_i$ are the weight and value, respectively of item $a_i$.
Q.2 Which of the following expressions in terms of $W$ yield the optimal value for the original Knapsack problem?
Answer:- $\max {v \mid 0 \leq v \leq 5 \text{ and } W(4,v) \leq 6}$
Q.3 Select all the correct choices from the list below.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent