[CS202]-Algorithms I Fall 2020-21
Homework: 5
Name: Aastha Asthana RollNo:11840020 email:[email protected]
Collaborators Names: Kumar Shivendu
Solution of problem 1. I am using bottom-up DP approach:
Algorithm: We have 2 options:
a) Include the current number(i)
b) Don’t include the current number
If option ”a” is selected it means that the previous(i-1) number can’t be selected but the one before previous(i-2) can
be selected.
If option ”b” is selected, it means that we have got the maximum sum till (i − 1)th number.
So now it comes down to what is maximum:
• Current number + sum before the previous
• Previous number and the sum before that
More can be understood from the pseudocode:
Pseudo-code:
SPACESUM(n, A[n]):
if n == 0: return 0
if n == 1: return A[0]
if n == 2: return max(A[0], A[1])
int memo[n]
memo[0]=A[0]
memo[1]=max(A[0], A[1])
for i in range(2, n):
memo[i] = max(memo[i-1], A[i]+memo[i-2])
return max(memo)
For A = [3, 5, 8, 4, 9, 16, 14, 6, 13], n=9. A memo[n] array will be created.According to the code:
memo[0]= 3
memo[1]= max(3,5)=5
For memo[2], we enter the for loop and get max(5, 8+3)=11.
1-1
Lecture 1 1-2
Similarly we calculate memo[3]= max(11, 4+5)=11 ... and so on
Our final memo array is [3,5,11,11,20,27,34,34,47].
Max of this array is 47 which is the largest possible value that can be obtained by summing a subset of the entries of
A such that the subset contains at most one of any two consecutive entries.
Proof of Correctness:
Loop invariant: At the end of the iteration i of the for loop, memo[i] will contain the maximum sum till the ith
element.
Initialization: For n=1 or i=0 i.e. if the array has only 1 element, memo[0]=A[0] which is the maximum as there is
only 1 number.
Maintainence:For j ≥ 1; let LI(j) be true. So memo[j] will contain the maximum sum till the j th element. Now for
LI(j+1), memo[j+1]= max(memo[j], A[j+1]+memo[j-1]). From LI(j), we know that memo[j] contains the maximum
sum till the j th element. We just have to compare which is maximum, memo[j] or A[j+1]+memo[j-1]. Thus, we will
have the maximum sum till the (j + 1)th in memo[j+1].
Termination: Loop terminates at i=n-1 and memo[n-1] will contain our result, which is the maximum sub of subset
of A such that the subset contains at most one of any two consecutive entries.
Hence, our algorithm is correct.
Time Complexity: O(n)
Solution of problem 2.
Algorithm :
We first sort the jobs according to the finish time and then maintain an array(DP) to store solutions for the subproblems.
Now DP[i] stores the score for interviews till arr[i](inclusive). Then we will take entries in DP by taking maximum
score if we include the current job, and if we don’t. We find the score while including current job by maintaining in-
clScore variable. Basically we have to find the latest job before the current job in the sorted array that doesn’t conflict
with the current job. Once we find such a job, we use recursion for all jobs till that job and add score of current job to
inclScore variable. At the end we return the result of our main problem.
More can be understood by the Pseudocode:
comparejobs(job1,job2):
return (job1.finish < job2.finish)
binarySearch(jobs[], index):
int l = 0, r = index - 1
while( l ≤ r )
Lecture 1 1-3
mid = (l + r) / 2
if(jobs[mid].finish ≤ jobs[index].start ):
if(jobs[mid + 1].finish ≤ jobs[index].start ):
l = mid + 1
else:
return mid
else:
r = mid - 1
return -1
findMaxScore(arr, n):
sort(arr, arr + n, comparejobs)
DP[n] = 0
DP[0] = arr[0].Score
for i in range(n):
inclScore = arr[i].Score
l = binarySearch(arr, i)
if( l 6= 1 ):
inclScore += DP[l]
DP[i] = max(inclScore, DP[i-1])
result = DP[n-1]
return result
Proof of correctness :
Loop invariant :
At the end of iteration j of the for loop, DP[j] will contain the maximum profit till the j th job interview.
Initialization : For n = 1, i.e. for i=0, DP[0] will store the arr[i].profit for this sub problem as there is only one job
offered. Hence L1(1) is true.
Maintainace : For j ≥ 1, let us assume LI(j) be True which implies that DP[j] contains the maximum profit till j th
job interview. Now for LI(j + 1), DP[j + 1] = max(inclScore, DP[j]). From LI(j) we know DP[j] contains the correct
solution for the sub-problem n = j (from initialization step) and inclScore has the latest job’s profit before the current
job(in sorted array) that doesn’t clash with the job arr[j - 1] in addition to the profit of current job. As former is the
case when we choose that job’s interview and the latter is the case when we exclude the current job’s interview, we
pick the maximum of both. Hence LI(j + 1) is also correct
Termination : Loop will terminate at i = n, and DP[n - 1] will contain the result of our weighted scheduling problem
and it is stored in the result variable and returns result variable that contains the maximum profit made till the nth job
interview. Hence algorithm is correct.
Time complexity : The time complexity for binary search algorithm is O(log n) and our for loop runs from 0 to n-1
which is n times. Hence the time complexity of our algorithm is O(nlogn).
Solution of problem 3. Algorithm: To solve this problem using Dynamic Programming,we create an array that
counts all the way up to the nth value. With this array, we can calculate the number of ways the coins make up the
values at the index of array of ways. Basically we are using the index value as the amount of coins(i.e. n) of which
we have to select the change from coins of various denominations. If we can determine that a coin is larger than the
amount at the index then we can’t use that coin to calculate the combinations of the coins because that coin is larger
than that amount. We will keep the first value of the ways array with 0 as there is only 1 way to make 0 with 0 coins.
Then we will compare each index value with the coin value and update the array and then we will have our final answer
which will be the nth value at that array.
Lecture 1 1-4
For more clarity, refer to the Pseudocode below:
CoinChange(n,a[])
int ways[n+1]=[0,0....,0]
ways[0]=1
for i in range(len(a)):
for j in range(len(ways)):
if (a[i]≤j):
ways[j] += ways[j - a[i]]
return ways[n]
Proof of Correctness:
Loop invariant: After completion of j th iteration, ways[i] will contain all ways of making change exactly once.
Initialization: The loop works for n=1(Let’s assume a[0]=1). For j=0, we have ways[0]=1 as there is only 1 way to
make 0 with 0 coins. For j=1, ways[1]=ways[0]+ways[1]=1, which is correct. So our LI is correct.
Maintenance: For k ≥ 1 let’s assume LI(k) to be true which implies that our array ways[k] will contain all
ways of making change for n=k. We know that if the value of the coin is smaller than the value of the index
at the ways array then ways[k-coins[i]]+ways[k] is the new value of ways[k]. Similary it will work for LI(k+1),
ways[k+1]=ways[k+1]+ways[k+1-a[i]] as ways[k+1-a[i]] will contain our previously calculated answer for k+1-a[i]
and here we are determining that a[i]th goes into all the values leading upto (k + 1)th coin. We are checking our
previous result dynamically and updating our answer instead of recalculating all over again.
Termination :
The for loop will terminate when j reaches n and ways[n] will have our final answer.
Thus, our required number of ways will be found by ways[n] and hence our algorithm is correct.
Time Complexity: O(n*len(a)) [As there are two nested for loops one goes from 0 till n-1 and another from 0 till
(len(a)-1)].
Solution of problem 4. (a)Counter example:
Let us assume the input array be [0.0,0.6,1.0,1.2,1.4,2.0] then the proposed algorithm fails as it will give the output as
3 because it will select {0.6,1.0,1.2,1.4} and then {0.0} and {2.0} which is wrong as the correct answer for is 2 when
we select {0.0,0.6,1.0} and {1.2, 1.4, 2.0}. Hence the given greedy algorithm is wrong.
(b)Algorthm:Our main approach is to put a unit interval block starting at the point whenever we tackle a point which
is greater than the right end of our current interval block and then we will increment the counter. Initially our current
interval block left end is at -1 and right end is at -1
Pseudocode:
1. int INTERVALCOVER (points [],n )
2. float leftsegment {-1}
3. float rightsegment {-1}
4. int count {0}
Lecture 1 1-5
5. for ( int i {}; i < n; + + i):
6. if ( points[i] > rightsegment ):
7. leftsegment = points[i]
8. rightsegment = leftsegment +1
9 count++
10. return count
Proof of Correctness:
Loop Invariant : At the end of jth iteration, count will contain the count of minimum intervals required to cover the
points till jth index.
Initialisation :First, we have initialized leftsegment and rightsegment as - 1. Now, for i = 0, let point at 0 th index be
p0 then it is greater than -1 and our current interval will become [p0, p0 + 1]. Then count will increment to 1 and this
is the minimum interval to cover 1 single point. Hence LI(1) is true.
Maintenance : There would be two cases here. First, let us assume LI(j) is true. It means that, count will contain the
count of minimum intervals required to cover the points till jth index at the end of jth iteration. So the first case is
The new undiscovered point at (j + 1) th index is less than or equal to the right segment of the current interval block.
LI(j) ensures the positive chances of our answer and no new interval is created which means that the count remains
same. Hence LI(j + 1) is true for this case. Now, the second case is the new undiscovered point at (j + 1) th index
is strictly greater than the right segment of the current interval block. Here , the algorithm generates new interval for
the point [pnew , pnew + 1].If we want to take this, we need to right segment of any interval block at the pnew .Due to
this, it will uncover at least one previously covered points.Hence, LI(j + 1) is true for this case.Hence, LI(j + 1) is true.
Termination : The loop terminates when i reaches to n and return count which contains the minimum number of
intervals required to cover the given points.
Time Complexity: Loop runs n-1 times. Therefore, time complexity will be O (n).
