CS计算机代考程序代写 AI algorithm Oliver Braun

Oliver Braun
CSE 101 (Summer Session 2021)

Homework 1: Algorithms and Optimization Problems

Instructions

Homework questions will be similar to your future exam questions. The homework will not be graded,
however, you are highly recommended to practice using these questions for better preparations of the
exams.

Key Concepts Algorithms, Optimization Problems, Minimization: Assignment, Maximization: Knap-
sack, Greedy-Heuristics, Complete Enumeration, Branch-And-Bound, Lower and Upper Bounds.

We start with some questions about analyzing iterative and recursive algorithms in terms of proving
their correctness and performing time analysis. Then we have a look at algorithms for solving two basic
optimization problems:

The Assignment Problem is a minimization problem. In this problem, an Upper Bound is an actual
achievable sum (will accept nothing larger), whereas a Lower Bound is a smallest possible sum (will
accept nothing smaller, but may or may not be achievable). Our goal is to minimize the Best Upper
Bound.

The Knapsack Problem is a maximization problem. A Lower Bound is an actual achievable sum (will
accept nothing lower), whereas an Upper Bound is a largest possible sum (will accept nothing larger,
but might or might not be achievable). Our goal is to maximize the Best Lower Bound.

We start with Greedy-Heuristics, then do Complete Enumeration, Branch-And-Bound and Dynamic
Programming.

Complete Enumeration just completely enumerates all possible solutions. The main idea of Branch-And-
Bound is to use Lower and Upper Bounds to cut off a huge number of possible solutions and so be in
most cases significantly faster than doing Complete Enumeration.

Dynamic Programming is a powerful mathematical optimization technique that breaks the problem
into subproblems of smaller dimensions, solves these subproblems only once, memorizes the result for
each subproblem and then uses these results to get the answer for subproblems of larger dimensions.
Eventually, this leads to the solution of the initial problem. In order to get an optimal answer, each of
the problems must be solved optimally. There are two ways that a problem can be solved with the help
of Dynamic Programming.

Top-down approach. In this method, we break a problem into smaller subproblems, solve each subproblem
and then combine the results to get the answer for the initial problem. The relation between the problem
and its subproblems is represented by recurrent formulas.

Bottom-up approach. In this method, we find the answer for the current problem and then use its result
to get answers for problems of larger dimensions. Our initial problem will be their subproblem.

In this homework, we will consider a top-down approach, although many problems can be solved in both
ways.

Sources:
[1] Dasgupta, Sanjoy / Papadimitriou, Christos / Vazirani, Umesh (2008): Algorithms, McGrawHill.
[2] Kleinberg, Jon / Tardos, Eva (2014): Algorithm Design, Pearson.

Problem 1. In this problem, we are given a sequence a1, a2, . . . , an of integers and we want to return a list
of all terms in the sequence that are greater than the sum of all previous terms of the sequence.
For example, on an input sequence of 1, 4, 6, 3, 2, 20, the output should be the list 1, 4, 6, 20. The
following algorithm solves this problem.

procedure PartialSums(a1, a2, . . . , an: a sequence of integers with n ≥ 1)

1. total := 0

2. Initialize an empty list L.

3. for i := 1 to n

4. if ai > total

5. Append ai to list L.

6. total := total + ai

7. return L

(a) Prove the following loop invariant by induction on the number of loop iterations: Loop In-
variant: After the kth iteration of the for loop, total = a1 + a2 + · · ·+ ak and L contains all
elements from a1, a2, . . . , ak that are greater than the sum of all previous terms of the sequence.

(b) Use the loop invariant to prove that the algorithm is correct, i.e., prove that it returns a list of
all terms in the sequence that are greater than the sum of all previous terms of the sequence.

Solution:

(a) We will prove the loop invariant by induction on k, the number of for loop iterations.

Base case: Before we enter the for loop (k = 0) the total is 0 and L is an empty list.

Induction Hypothesis: Same as Loop Invariant for k − 1.
Induction Step: On the kth iteration of the for loop, either (a) ak > total, in which case we
add ak to L, or (b) ak ≤ total, so we leave L as is. By the Induction Hypothesis, L contains all
elements from a1, . . . , ak−1 that are greater than the sum of all previous terms in the sequence,
so then after the kth iteration, L contains all elements from a1, . . . , ak that are greater than
the sum of all previous terms in the sequence. Then the total is updated, and so the Loop
Invariant is true for k. By Mathematical Induction, the Loop Invariant is true.

(b) Since the Loop Invariant is true for all iterations, then letting the loop iterate n times, the loop
will terminate, total = a1 + a2 + · · ·+ an and L contains all elements from a1, a2, . . . , an that
are greater than the sum of all previous terms of the sequence. Thus, the algorithm is correct.

Problem 2. The following algorithm determines whether a word is a palindrome, that is, if the word is the
same read left to right as right to left. An example of a palindrome is racecar.

procedure Palindrome(s1s2s3 . . . sn)

1. if n = 0 or n = 1 then return true

2. if s1 = sn then return Palindrome(s2 . . . sn−1)

3. else return false

Note: Writing s1s2s3 . . . sn denotes a string of length n whose characters are s1, s2, s3, etc. These
characters are being concatenated (not multiplied) to form a string.

(a) Prove that this algorithm is correct, i.e., that it returns true if and only if s1s2s3 . . . sn is a
palindrome.

(b) Let C(n) be the number of times this algorithm compares two letters si and sj for some i, j.
Write a recurrence relation that C(n) satisfies. Hint: C(0) = C(1) = 0.

Solution:

(a) We proceed by induction on n, the size of the input.

– Base Case: When n = 1 and n = 0, the string is a palindrome by definition and the
algorithm is correct.

– Induction Hypothesis: Assume the algorithm is correct on inputs of size 0, 1, . . . , k− 1.
– Inductive Step: Here we show the algorithm is correct on input of size k. If a1 6= ak then

the string is not a palindrome and we return false. Otherwise, we recurse on the string
a2 . . . ak−1 and the algorithm is correct by the Inductive Hypothesis.

Hence, the algorithm is correct for all words of length n.

Picture: word input = a1 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ak. If a1 = ak, we repeat on the substring ∗ ∗ ∗ ∗ ∗ ∗ ∗.
Otherwise, there is no way this string is a palindrome and we return false.

(b) With each recursive call, one comparison is done in line 2 (between the first and last letter of
the word), and then Palindrome is called again with an input having length two smaller than
before. No comparisons are done in the base cases in line 1. Therefore, the recurrence is

C(n) = C(n− 2) + 1, with C(0) = 0, C(1) = 0.

(c) To find an exact formula for C(n) we will have to consider whether n is even or odd, since
the recursion expresses C(n) in terms of C(n − 2). This means that when n is even, we will
eventually hit the base case for n = 0 and when n is odd, we will eventually hit the base case
for n = 1. Unraveling the recurrence gives

C(n) = C(n− 2) + 1
= C(n− 4) + 2
= C(n− 6) + 3
…

= C(n− 2k) + k
…

{
C(0) + n

2
if n is even (letting k = n/2)

C(1) + n−1
2

if n is odd (letting k = (n− 1)/2)

{
n
2

if n is even
n−1
2

if n is odd

=
⌊n

⌋
In Θ notation, this is Θ(n), or linear time in the number of letters in the input word.

Problem 3. Design your own algorithm. You are given a list of integers where some integers might occur more
than once. Design an algorithm that returns a list of integers where all of the integers that appear
in the original list are present without any duplicates (i.e. exactly once).

(a) Develop an algorithm that solves this problem.

(b) Prove the correctness.

Note: This can be done in O(n) using hashing, providing an O(n log(n)) solution is sufficient.

Solution:

(a) Algorithm: We can solve this by using sorting. First we sort the original list using e.g.
Mergesort. Now the original list is sorted and we can traverse through it using a pointer. Let’s
define a pointer i at the start of the list. We now traverse the list and keep pushing all the
elements in a new list, we don’t push an element if the previous element is equal to the current
element. We then return is new list.

(b) Correctness: We have two parts of this problem, first is sorting the list and the second one
is traversing the list while pushing elements into a new list. Since we use a sorting without
any modification we can say that sorting will be done successfully. Now, for the second part.
Prove by induction on n, the total input size.

Base case: n = 0. The list is empty and we return an empty list as nothing is pushed into
the list which is correct.

Induction hypothesis: Same as claim for n− 1.
Induction step: Assume this algorithm works for list with n − 1 elements, now we need to
prove that this also works for n elements.

Case 1: nth element is equal to (n − 1)th element If the nth element is equal to previous
element, it means we must have either pushed (n − 1)th element in the new list, in that case
we don’t have to push nth element. It might be possible the (n− 2)th element is also same as
nth but even in that case we must have pushed it to the new list. So, we don’t have to push
the nth element.

Case 2: nth element is not equal to (n− 1)th element If the nth element is equal to (n− 1)th
element, we can safely say that nth element has not occurred before in the original list, as the
list is sorted. In this case, (n − 1)th element will be smaller than nth element which means,
every other element before that will also be smaller than nth element. Hence, this is the first
occurrence of the element and can be pushed into the new list.

(c) Time complexity: Time complexity of the algorithm is Θ(n log n). Since we are sorting the
entire list it will take O(n log n) time, and for the next iteration it will be just O(n). We use
O(n) space since we are creating an additional array.

Problem 4. Design your own algorithm. You are given a sequence of n positive integers a1, a2, . . . , an. Find a
continuous subsequence al, al+1, . . . , ar, such that the sum of all numbers in it is less than K and
its length is as large as possible.

(a) Develop an algorithm that solves this problem.

(b) Prove the correctness.

Solution:

(a) Algorithm: We will solve this problem with a popular technique called two pointers. Let’s
have two variables l = 0 and r = 0. Let’s scan our sequence from left to right. Variables l and
r will denote the beginning and the end of the current subsequence respectively and let S(l, r)
be its sum. At each step, if S(l, r) is less than K, we have found the subsequence of the length
r − l + 1. Otherwise, while S(l, r) ≥ K and l ≤ r, we will increase the value of variable l.
At the end of each step, we increase the value of r. During the process, we also have variable
ans = 0 which we will update every time we find a new valid sequence: ans = max(ans, r−l+1).
The algorithm stops when r = n.

(b) Correctness: Let’s prove that the algorithm finds the largest possible subsequence. Let
al′ , al′+1, . . . , ar′ be the optimal answer for the problem. At some time of our algorithm, r will
be more than or equal to l′. We will have l ≤ l′ and r ≤ r′ and l′ ≤ r. At any time while
l′ ≤ r ≤ r′, l will not exceed l′. Indeed, if at some point l were bigger than l′, it would mean
that there was r ≤ r′, such that S(l′, r) ≥ K. However, this is not possible as all numbers
are positive. Therefore, S(l′, r) ≤ S(l′, r′) < K. Consequently, there will be a moment during our algorithm, when l ≤ l′ and r = r′. As sequence al′ , al′+1, . . . , ar′ is optimal, it means that l = l′. So our algorithm finds the optimal answer for this problem. (c) Time complexity: Time complexity of the algorithm is θ(n). Indeed, at each step, we increase either l (in a loop) or r. Both l and r can not exceed n. Each step works in θ(1) time. There are no more than 2n steps. Therefore, the complexity is θ(n). 5 Problem 5. Design your own algorithm. You have n packs of candy and each pack has a different number of candy inside. Luckily, the number of candies in a pack is written outside. You have m ≤ n friends, and you want to give every one of your friends exactly one pack of candy. You want to give out these packs such that the difference between the pack with the maximum number of candy and the pack with the minimum number of candy is as small as possible. (a) Develop an algorithm that solves this problem. (b) Prove the correctness. (c) Prove the time complexity. Solution: (a) Algorithm: Our input is a list of integers representing the number of candies inside each of the n packs. We can sort this list in ascending order and denote the sorted list as a1, ..., an. Now, let’s have two pointers, i and j. We initialize the pointer i at index 1, and j at i+m− 1 (index m). We calculate the difference between the values at these indices, i.e. aj − ai, and initialize a variable storing minimum difference to this value. Next, we increment both pointers by 1, and calculate the difference aj − ai again. Update the minimum difference variable if current difference is smaller. Keep track of the pointer values associated with the minimum difference as well. Repeat this process. Terminate after pointer j hits the end of the list and return the packs between (and including) pointer indices associated with minimum difference. (b) Correctness: Let’s prove that the algorithm finds the minimum difference in number of candies when distributing n packs. Let S = ak1 , ..., akm be the optimal selection, sorted in ascending order. We first want to prove S must be able to take form of a consecutive subsequence of length m in the sorted input a1, ..., an. Assume by contradiction the index of S can’t be consecutive. Then we know km > k1 + (m − 1). Construct another selection S′ =
ak1 , ak1+1, …, ak1+m−1. Since a1, …, an is sorted, MAX(S) = akm ≥ ak1+m−1 = MAX(S′).
Thus, MAX(S)−MIN(S) = akm−ak1 ≥ ak1+m−1−ak1 = MAX(S′)−MIN(S′), which means
S′ is a selection no worse than S, contradicting our assumption that the optimal selection can’t
be consecutive. Therefore, at least one optimal selection takes form of S = al, al+1, …, al+m−1
for some l. Our two pointers scan through the sorted input list and compute the differences
for each consecutive subsequence of length m, so our algorithm will find this at some point.

(c) Time complexity: Time complexity of the algorithm is Θ(n log n). Since, we are sorting the
entire list it will take O(n log n) time, and since we traverse the list just once using two pointers
it will be O(n). The overall complexity would be O(n log n)

Problem 6. Quicksort, Partitioning. Quicksort is a very famous and simple sorting algorithm that is used in
many applications. The problem is the following – we have an array of n elements: A0, A1, . . . , An−1
that we need to rearrange in a way that it becomes sorted in an increasing order, i.e. A0 ≤ A1 ≤
. . . ≤ An−1. To accomplish this, we will do the following: let’s choose a random element from the
array. We will call this element a pivot. Now, let’s break, or partition, the remainder of the array
into two groups (maybe empty): the first part contains all elements that are less than or equal to
the pivot, the second part contains all elements that are strictly larger than the pivot. We will call
this process partitioning. Let’s look at the example:

10 3 5 0 12 17 7 4 5 19

The array contains 10 elements. Let’s choose a random element. Let it be the third element of the
array. Its value equals 5.

Now let’s break the array into two parts as was described above:

3 5 0 4 5 10 12 17 7 19

Red-color elements belong to the first group, while blue-color ones belong to the second group.
The pivot element’s color is green.

The elements in both groups can be arranged in any way inside their group. As long as the
conditions that all elements in the left group are less than or equal to the pivot and that all
elements in the group are strictly larger that the pivot are satisfied, any partition will be valid.
For example, another valid partition is:

0 3 4 5 5 7 10 12 17 19

As we can see, if all the elements in both groups were sorted in an increasing order, the resulting
array after the partitioning would be sorted too. We will use this observation to sort the array.
We will call the sorting method quicksort. First, we choose a random element in the array and
perform partioning. Then, we apply the quicksort recursively to each of the resulting groups. The
recursion stops when there is only one element in the array.

Apparently, as a result, we will get a sorted array.

(a) Develop an algorithm that performs partitioning. Try to make it as efficient as possible.

(b) Prove the correctness of the partitioning.

(d) Prove the correctness of the quicksort.

(e) Show (prove) the worst case running time of the quicksort.

(f) Show (prove) the average running time of the quicksort. (the average running time of an
algorithm is the number of operations averaged over all possible inputs)

Solution:

(a) Algorithm: Let’s describe how partitioning works. Let’s look at the same example with the
same pivot element:

10 3 5 0 12 17 7 4 5 19

First let’s swap the first element of the array and the pivot element. We will get:

5 3 10 0 12 17 7 4 5 19

Now, let’s have two pointers l and r, which will initially point to the beginning and to the end
of the array respectively (l = 0, r = n− 1). And let’s denote the pivot element as p.

5
l

3 10 0 12 1 7 4 5 19
r

First, we try to increase l as much as possible. We increment pointer l, if A[l] ≤ p.

5 3 10
l

0 12 17 7 4 5 19
r

Then, we try to decrease r as much as we can. We decrement pointer r, if p < A[r]. 5 3 10 l 0 12 17 7 4 5 r 19 Then, if l < r, we swap elements A[l] and A[r]. 5 3 5 l 0 12 17 7 4 10 r 19 If l < r, we also repeat all these three operations again (increasing l, decreasing r and swapping l and r again, if l < r). As soon as l > r, we swap elements A[r] and p and stop partitioning.

5 3 5 0 12
l

17 7 4
r

10 19

5 3 5 0 4
l

17 7 12
r

10 19

5 3 5 0 4 17
l

7 12
r

10 19

5 3 5 0 4
r

17
l

7 12 10 19

4 3 5 0 5
r

17
l

7 12 10 19

(b) Correctness (partitioning): Let’s prove that partitioning is correct. Indeed, after we in-
crease l and decrease r, all elements to the left of A[l] are less than or equal to p, and all
elements to the right of A[r] are strictly larger than p. After this process, we get that A[l] > p
and A[r] ≤ p. If l < r, we swap A[l] and A[r] and get that A[l] ≤ p, A[r] > p. If l > r, we swap
A[r] and p, which are both less than or equal to p and stop partitioning. As a result, we get
that all elements to the left of p are less than or equal to p, and all the elements to the right
of p are strictly larger than p.

(c) Time complexity (partitioning): The time complexity for partitioning will be Θ(n). In-
deed, at each step we increase l or decrease r. Each step takes O(1) time. Both l and r can’t
be increased/decreased more than n times, so there are not more than 2n steps. On the other
hand, the number of iterations will be at least equal to n, as we continue partitioning till l > r

(d) Correctness (quicksort): Now, let’s prove that the quicksort is correct.

The base case is when we have only one element. One element is an ordered array, so the base
case is correct.

The hypothesis is that the quicksort sorts correctly all arrays of the size less than n.

Now, there is the inductive step. For an array of size n, we, first, choose a pivot element p.
Then, we perform partitioning bases on this element. As a result, the array will be divided
into two groups: the left group in which all elements are less than or equal to p, and the right
group in which all elements are strictly larger than p. The sizes of these groups are less than
n (because they at least do not contain the pivot element). Then, we use the quicksort on
them recursively. According to the hypothesis, both these groups of elements will be sorted
correctly. As a result, the initial array will consist of the left part which is sorted correclty, the
pivot element and the right part which is also sorted correctly. Therefore, the whole array will
be sorted correctly.

(e) Time complexity (quicksort): Let T (n) be the number of operations the quicksort makes
for the array of size n. Then,

T (0) = Θ(1)

T (n) = T (i) + T (n− i− 1) + Θ(n)

where A[i] is a pivot element.

Let’s say, that at each iteration, the pivot element is the smallest element in the array. Then,
we have:

T (n) = T (0) + T (n− 1) + Θ(n)

T (n) ≥ T (n− 1) + n− 1

T (n) ≥ T (n− 2) + n− 2 + n− 1

. . .

T (n) ≥ 1 + 2 + . . .+ n− 2 + n− 1

T (n) ≥
(n− 1)n

Therefore, T (n) ∈ Ω(n2)
So in the worst case, the quicksort will take quadratic time to sort the array. But this case
happens rarely. Let’s see how fast the quicksort works on average (the expected time complex-
ity).

(f) Time complexity (quicksort): Let partitioning take cn operations and T (n) be the average
running time. Then, we will have the following recurrent equation:

T (n) =
1

n−1∑
i=0

(T (i) + T (n− i− 1) + cn)

T (n) =
2

n−1∑
i=0

T (i) + cn

nT (n) = 2

n−1∑
i=0

T (i) + cn2

(n− 1)T (n− 1) = 2
n−2∑
i=0

T (i) + c(n− 1)2

nT (n)− (n− 1)T (n− 1) ≈ 2T (n− 1) + 2cn
T (n)

n+ 1
≈
T (n− 1)

n
+

n+ 1

n∑
i=1

T (i)

i+ 1
≈

n∑
i=1

(
T (i− 1)

i
+

i+ 1
)

T (n)

n+ 1
≈
T0
1

+ 2c(

n∑
i=1

i
− 1)

T (n)

n+ 1
≈ 2c(lnn− 1)

T (n) ≈ c′n lnn

T (n) ∈ Θ(n log n)

Problem 7. Consider the following table:

T1 T2 T3 T4
A 6 4 2 5
B 2 1 5 4
C 4 2 1 3
D 5 3 3 2

(a) Compute a feasible solution with the Smallest-Number-Heuristic.

(b) Solve the problem with Branch-and-Bound : Use the solution value of the Smallest-Number-
Heuristic as the first Best Upper Bound, UB1.

i. Branch: Level = Agent, and continue always at that vertex with the smallest Lower
Bound.

ii. Lower Bound: Use the Row-Min-Strategy. If this is ≥ the current Best Upper Bound,
cross out this vertex; otherwise, proceed.

iii. Upper Bound: Use the Smallest-Number-Heuristic. If this is ≤ to the Best Upper Bound,
set this as the newest Best Upper Bound and immediately cross out any open vertices with
a Lower Bound ≥ this new Best Upper Bound.

iv. Crossing out a vertex: all assignments are done or its Upper Bound is ≤ its Lower
Bound.

v. Number each vertex in the order they are constructed.

The vertex with the Best Upper Bound is an optimal solution.

(c) How many vertices do you not have when you use Branch-and-Bound instead of Complete
Enumeration (for this problem instance)?

Solution:

(a) SNH = 10

(b) We take UB1 = SNH = 10

start

LB:
A6 + B1 + C1 + D2 = 10
LB(10) ≥ UB1(10)

LB:
A4 + B2 + C1 + D2 = 9
UB:
A4 + B2 + C1 + D2 = 9
new UB2(9)
LB(9) ≥ UB2(9)

LB:
A2 + B1 + C2 + D2 = 7
UB:
A2 + B1 + C4 + D2 = 9

LB:
A5 + B1 + C1 + D3 = 10
LB(10) ≥ UB2(9)

A← T1 A← T2 A← T3 A← T4

LB:
A2 + B2 + C2 + D2 = 8
UB:
A2 + B2 + C2 + D2 = 8
new UB3(8)
LB(8) ≥ UB3(8)

LB:
A2 + B1 + C3 + D2 = 8
LB(8) ≥ UB3(8)

LB:
A2 + B4 + C2 + D3 = 11
LB(11) ≥ UB3(8)

B ← T1 B ← T2 B ← T4

4 + 4 · 3 + 4 · 3 · 2 = 40 vertices.

So in this instance, we calculated 33 fewer vertices.

Problem 8. A set of 5 items each with a value and a weight is given in the following table. The capacity of the
knapsack is 13.

A B C D E
Values 3 4 5 8 10
Weights 2 3 4 5 9

(a) Apply the largest-relative-value heuristic to this instance to find a feasible solution.

(b) Solve the problem with Branch-and-Bound.

Use the solution value of the Largest-Relative-Value-Heuristic as the first Best Lower Bound,
LB1.

i. Branch: Level = Largest Value, and continue always at that vertex with the largest
Upper Bound.

ii. Upper Bound: Use the Largest-Relative-Values-Strategy. If this is ≤ the current Best
Lower Bound, cross out this vertex; otherwise, proceed.

iii. Lower Bound: Use the Largest-Relative-Value-Heuristic. If this is ≥ to the Best Lower
Bound, set this as the newest Best Lower Bound and immediately cross out any open
vertices with an Upper Bound ≤ this new Best Lower Bound.

iv. Crossing out a vertex: all assignments are done or its Lower Bound is ≥ its Upper
Bound.

v. Number each vertex in the order they are constructed.

The vertex with the Best Lower Bound is an optimal solution.

(c) How many vertices do you not have when you use Branch-and-Bound instead of Complete
Enumeration (for this problem instance)?

Solution:

(a) LRVH = 15

(b) LB2 = 17 (take objects D, C, B with total value v = 17 and total weight w = 12).

2 + 4 + 8 + 16 + 32 = 62 = 26 − 2 vertices.

So in this instance, we calculated 52 fewer vertices.

E D A
UB: v: 10 6.4 = 16

w: 9 4 = 13
LB: v: 10 3 = 13

w: 9 2 = 2

D A B C
UB: v: 8 3 4 3.75 = 18

w: 5 2 3 3 = 13
LB: v: 8 3 4 = 15

w: 5 2 3 = 10

D A B C
UB: v: 8 3 4 3.75 = 18

w: 5 2 3 3 = 13
LB: v: 8 3 4 = 15

w: 5 2 3 = 10

A B C
UB: v: 3 4 5 = 12

w: 2 3 4 = 9
UB(12) ≤ LB1(15)

D C A B
UB: v: 8 5 3 2.6̄ = 18

w: 5 4 2 2 = 13
LB: v: 8 5 3 = 16

w: 5 4 2 = 11
New LB2(16)

D A B
UB: v: 8 3 4 = 15

w: 5 2 3 = 13
UB(15) ≤ LB2(16)

D C B A
UB: v: 8 5 4 1.5 = 18

w: 5 4 3 1 = 13
LB: v: 8 5 4 = 17

w: 5 4 3 = 12
New LB3(17)

UB(16) ≤ LB2(16)

D C A
UB: v: 8 5 3 = 16

w: 5 4 2 = 13
UB(16) ≤ LB3(17)

Insufficient capacity D C B
UB: v: 8 5 4 = 17

w: 5 4 3 = 12
UB(17) ≤ LB3(17)

E in E out

D in D out

C in C out

B in B out

A in A out

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

Problem 9. Design your own algorithm. Dynamic Programming. You are given a knapsack of weight W and n
items of weights w1, w2, . . . , wn. You need to fill the knapsack in a such way that the total weight
of all items in the knapsack is maximized and doesn’t exceed the capacity of the knapsack.

Solution:

Let fi,k be the optimal weight of all items in the knapsack of weight k, when we can use frost i
items. Here, we have defined the problem of the dimension (i, k). These two parameters help us
to define a problem (note that function f may also depend on variables, that have no connection
with the dimension of the problem).

Let’s assume that we know optimal answers for all subproblems of smaller sizes, i.e. for all problems
(i′, k′), such that i′ ≤ i and k′ ≤ k and (i, k) 6= (i′, k′). Now we want to find an answer for problem
(i, k). Let’s look at item number i. There are two possible actions that we can take: we can either
include item i in the knapsack, if there is enough capacity for it, or we can ignore it. If we ignore
item i, this means that we have to fill the knapsack of the weight k optimally without using this
item. Thus, we can only include items from 1 to i− 1. Therefore the subproblem where we don’t
include item i will be (i − 1, k). The answer for this subproblem is fi−1,k. Now let’s consider
the case where we try to put item i into the knapsack. It is only possible, if the capacity of the
knapsack is not less than the weight of the item i, i.e. k ≥ wi. If this condition is true, then we put
the item in the knapsack. As regards the rest of space in the knapsack, we will try to fill it with
items 1, 2, . . . , i− 1 in the most optimal way. This subproblem will have dimension (i− 1, k−wi),
where k − wi is available capacity left in the knapsack after we put item i in it. So, all smaller
subproblems of problem (i, k) can be divided into two sets: when we include item i in the knapsack
and when we don’t. Using all these observations we can calculate the value fi,k:

For i > 0:

fi,k =

{
max(fi−1,k−wi + wi, fi−1,k) if k − wi ≥ 0
fi−1,k otherwise

This is a recurrent formula for dynamic programming. We can use recursion in order to compute
it. An important thing to remember here is that we should calculate values for problems fi,k only
once. We can do this by memorizing all the computed values and just use them, if they are needed.
This will improve time complexity dramatically.

Similar to mathematical induction, dynamic programming technique requires base.

As we can see the recurrent formula above makes sense only when i > 0. So the base case will be
f0,k = 0, where k ∈ [0,W ].
The correctness of such recurrent equations are proven in two steps: first we prove the base case,
then we prove the formula. When we prove the formula, we use the assumption that all subproblems
are solved optimally. For example, in this problem all possible valid combinations of first i items
can be divided into sets: when we include item i into the knapsack and when we don’t. We have
optimal answers for both of these case in our subproblems (i − 1, k) and (i − 1, k − wi), thus the
answer for (i, k) also will be optimal.

As each value fi,k is calculated only once, then the time complexity for this problem is Θ(nW ).

Problem 10. Design your own algorithm. You are given a sequence of n integers a1, a2, . . . , an. Find the
length of the longest increasing subsequence ak1 , ak2 , . . . , akm , such that ki ∈ {1, 2, . . . , n} for
i ∈ {1, 2, . . . ,m}, k1 < k2 < . . . < km and ak1 ≤ ak2 ≤ . . . ≤ akm . (a) Find a dynamic programming formula to solve the problem. (b) Prove its correctness. (c) Show and prove its time complexity. Solution: (a) Let fi be the length of the longest increasing subsequence, that ends with element on position i. Then: Base case: f0 = 0 For i > 0:

fi = max(fj + 1) for all j: 0 ≤ j < i and aj ≤ ai The answer to the initial problem: fn (b) When there are no elements in the array, then the length of the longest increasing subsequence (LIS) is zero. The base case is correct. Now, let’s assume that values for f1, f2, ..., fi−1 are calculated correctly. We need to prove that fi is also correct. If the LIS that ends with element ai has the length one, then this means that ai is the smallest element in a1, a2, ..., ai. In this case, our solution will give fi = 1, which is correct. If the LIS that ends with ai consists of more than one element, then some element aj , j < i and aj < ai will come right before ai in the optimal answer. As we iterate through all valid aj , and fj is the longest increasing subsequence that ends with aj , then fi will also be optimal. (c) We need O(n) to calculate fi. The overall time complexity will be On2. 15 Problem 11. Design your own algorithm. Find the number of binary sequences of the length n, such that no sequence has two consecutive zeros. (a) Find a dynamic programming formula to solve the problem. (b) Prove its correctness. (c) Show and prove its time complexity. Solution: (a) Let fi be the number of all binary sequences of the length i with no consecutive zeroes. Base case: f0 = 1, f1 = 2 For i > 1:

fi = fi−1 + fi−2

The answer to the initial problem: fn

(b) The number of empty sequences is zero. Valid sequences of length 1: ”0”, ”1”. The base case
is correct. Now, let’s assume that values f2, f3, …, fi−1 are calculated correctly. Let’s show
that fi is also correct.
Let’s consider all valid sequences of the length i. They can be divided into two groups: those
that end with 1 and those that end with 0. The number of sequences of the length i that
end with 1 equals fi−1. Indeed, if the last element is 1, then it doesn’t affect the previous
elements anyhow, they only need to be valid. If the last element in the sequence is zero, then
the previous element can be only 1. This means, that all sequences of length i that end with
0 will end with 10. The number of such sequences is fi−2 (we have just shown this).

Problem 12. You are given a knapsack of weight W and n items with integer weights w1, w2, . . . , wn. Items have
their cost c1, c2, . . . , cn. You can take each item only once. Your goal is to fill the knapsack
with items, such that their cost is maximized.

(a) Find a dynamic programming formula to solve the problem.

(b) Prove its correctness.

Solution:

(a) Let fi,k be the optimal cost of the items in the knapsack of the weight k, when we have only
the first i items. Then:

Base case:

f0,k = 0 for all k ∈ [0,W ]

For other values:

fi,k =

{
max(fi−1,k−wi + ci, fi−1,k) if k − wi ≥ 0
fi−1,k otherwise

The answer to the initial problem: fn,W

(b) If there are no items, then the total cost is always zero. The base case is correct. Now let’s
assume that all fi′,k′ , where (i

′, k′) ∈ (i, k) are calculated correctly. Let’s show that fi,k is
also correct.
Let’s consider two possibilities: when item i is included in the knapsack and when it is not.
If item i is not in the knapsack, then we need to fill the knapsack of capacity k with items
1, 2, …, i − 1, such that their cost is maximized. But we already know the answer to this
problem. It is fi−1,k. Now, let’s assume we include item i in the knapsack. This means that
there is now only k−wi space left. Let’s fill this space with items 1, 2, …, i−1, such that their
total cost is maximized. The optimal value for this problem is fi−1,k−wi . At the end, we just
need to take the one which has the larger value. As both problems are solved optimally (give
the largest total cost), fi,k will also be optimal.

Problem 13. Design your own algorithm. You are given a knapsack of the weight W and n items with integer
weights w1, w2, . . . , wn. Each item has its cost c1, c2, . . . , cn. You can take each item as many
times as you want. Your goal is to fill the knapsack with items, such that their cost is maximized.

(a) Find a dynamic programming formula to solve the problem.

(b) Prove its correctness.

Solution:

(a) Let fi,k be the optimal cost of items in the knapsack of the weight k, when we have only first
i items. Then:

Base case:

f0,k = 0 for all k ∈ [0,W ]

For other values:

fi,k =

{
max(fi,k−wi + ci, fi−1,k) if k − wi ≥ 0
fi−1,k otherwise

The answer to the initial problem: fn,W

(b) The proof is similar to the previous one with just one exception. Now we can take each item
as many times as we want. So in the case, when we include item i in the knapsack, we now
need to fill the knapsack of the weight k with all items 1, 2, …, i. In the previous problem, we
couldn’t include item i, as it was already taken. But now we can. So the optimal answer to
this subproblem will be fi,k−wi .

Problem 14. Design your own algorithm. You are given a knapsack of the weight W and n items with integer
weights w1, w2, . . . , wn. Each item has its cost c1, c2, . . . , cn. You can take item i only bi times,
where bi is a positive integer number for i ∈ {1, 2, . . . , n}. Your goal is to fill the knapsack
with items, such that their cost is maximized.

(a) Find a dynamic programming formula to solve the problem.

(b) Prove its correctness.

Solution:

(a) Let fi,k be the optimal cost of the items in the knapsack of the weight k, when we have only
first i items. Then:

Base case:

f0,k = 0 for all k ∈ [0,W ]

For other values:

fi,k =

{
max(fi−1,k−l∗wi + l ∗ ci, fi−1,k) for all l: k − l ∗ wi ≥ 0 and 1 ≤ l ≤ bi
fi−1,k otherwise

The answer to the initial problem: fn,W

(b) The proof for this problem is similar to proofs for the previous two. In this case, we do not
consider the two possibilities of whether we put item i in the knapsack or not. Instead, we
explore how many times we take item i. For example, 0, 1, 2, …, bi times. We look through each
case separately. The optimal substructure of subproblems will lead to the optimal structure
of the initial problem.

(c) It takes O(W ) time to find fi,k. Because in the worst case, the weight of the item will be one,
and bi will be no less than W . The overall complexity will be O(nW 2).

Problem 15. Design your own algorithm. You are given two strings s = s1s2 . . . sn and t = t1t2 . . . tm. You may
perform three type of operations on a string: delete a symbol, insert a symbol or replace existing
symbol with any other possible symbol. Assume that all symbols are lowercase English letters.
What is the minimum number of operations you need to transform string s to string t?

(a) Find a dynamic programming formula to solve the problem.

(b) Prove its correctness.

Solution:

(a) Let fi,k be the minimum number of operations needed to transform string s1s2 . . . si to string
t1t2 . . . tk. Base case:

f0,k = k for all k : 1 ≤ k ≤ m

fi,0 = i for all i : 1 ≤ i ≤ n

For other values:

fi,k =

{
min(fi−1,k + 1, fi,k−1 + 1, fi−1,k−1 + 1) if si 6= tk
min(fi−1,k + 1, fi,k−1 + 1, fi−1,k−1) otherwise

The answer to the initial problem: fn,m

(b) We need to add k symbols to turn an empty string to string t1t2…tk and we need i deletions
to turn string s1s2…si to an empty string. The base case is correct. Now, let’s assume that
all values fi′,k′ for (i

′, k′) ∈ (i, k) are calculated correctly. Let’s show that fi,k is also correct.
Consider a sequence of operations that transforms s1s2 . . . si to string t1t2 . . . tk with fi,k
operations (i.e. it’s optimal) and operates from left to right. There could be three possibilities
for the last operation:

• The last operation is a deletion – we deleted symbol si. Then, after deleting si, we need
to find a way to turn s1s2…si−1 into t1t2…tk. The minimum number of operations to do
so equals fi−1,k + 1.

• The last operation is an insertion – we added symbol tk. So before adding tk, we need to
turn s1s2…si into t1t2…tk−1. Then, we add tk. The minimum number of operations to
do so equals fi,k−1 + 1.

• Now, let’s look at all other possibilities. If the last operation is neither a deletion or an
insertion, it must be either 1. a substitution of si to tk, fi−1,k−1 + 1 minimum operations
or 2. keeping the original symbol – this is not counted as an operation and requires
si == tk, and takes fi−1,k−1 operations minimum in total.

• fi,k would be the minimum of these three possibilities.

Problem 16. Design your own algorithm. You have a board of a dimension 1×n. There is a robot on cell 1. The
robot can make moves from cell i to cells i+ 1, i+ 2, . . . , i+ k. Moving to cell i costs ci resources
(c1 = 0). Find the path from cell 1 to cell n for a robot, that requires the minimum amount of
resources.

(a) Find a dynamic programming formula to solve the problem.

(b) Prove its correctness.

Solution:

(a) Let fi be a minimum amount of resources required for a robot to get to cell i.

Base case:

f0 = 0

For i > 0:

fi = min(fi−j) + ci for all j : i− j ≥ 0 and 1 ≤ j ≤ k

The answer to the initial problem: fn

(b) If the board is empty, then the amount of resources gained is zero. The base case is correct.
Let’s assume that subproblems f1, f2, …, fi−1 are solved optimally. Let’s show that fi is also
correct.
We can get to cell i from cells i− 1, i− 2, i− k (as long as these cells are on the board). We
know the value of the optimal way to get to each of these cells and that all paths to cell i
from 1 go through them. As all subproblems are solved optimally, the answer to fi also will
be optimal.

Problem 17. Design your own algorithm. You are given a board of a dimension N ×M . There is a robot on
cell (x0, y0) on the board. At each step robot may go from cell (x, y) to cells (x− 1, y), (x, y − 1),
(x + 1, y) and (x, y + 1) (all cells must be in table). Find the number of ways in which the robot
may get from initial cell to final cell (x1, y1) in k steps.

(a) Find a dynamic programming formula to solve the problem.

(b) Prove its correctness.

Solution:

(a) Let fx,y,k be the number of ways for the robot to get to cell (x, y) in k steps from cell (x0, y0).
And let:

gi,j,k =

{
fi,j,k if 1 ≤ i ≤ N and 1 ≤ j ≤M
0 otherwise

Base case:

fx,y,0 = 0 for all (x, y) : 1 ≤ x ≤ N and 1 ≤ y ≤M

For k > 1:

fi,j,k = gi−1,j,k−1 + gi,j−1,k−1 + gi+1,j,k−1 + gi,j+1,k−1

The answer to the initial problem: fx1,y1,k

(b) The proof is similar to the proof for the previous problem. We can get to cell (x, y) on step k
from cells (x− 1, y), (x, y− 1), (x+ 1, y) and (x, y+ 1) on step k− 1. As all the subproblems
are solved optimally, it leads to the optimality of the initial problem.

Problem 18. Design your own algorithm. You are given a sequence of n binary digits a1, a2, . . . , an (ai ∈ {0, 1} for
i ∈ {1, 2, . . . , n}). Find the number of subsequences ak1 , ak2 , . . . , akm , such that ki ∈ {1, 2, . . . , n}
for i ∈ {1, 2, . . . ,m}, k1 < k2 < . . . < km and the sum of all digits in the subsequence is even. (a) Find a dynamic programming formula to solve the problem. (b) Prove its correctness. (c) Show and prove its time complexity. Solution: (a) Let fi and gi be numbers of subsequences of a sequence a1, a2, . . . , ai with even and odd sums respectively. Then we have, Base case: f0 = g0 = 0 For i > 0:

fi =

{
2fi−1 + 1 if ai = 0

fi−1 + gi−1 otherwise

gi =

{
2gi−1 if ai = 0

fi−1 + gi−1 + 1 otherwise

The answer to the initial problem: fn

(b) The correctness of the base case is obvious. Now let’s assume that all sub-problems f0, g0,
. . . , fi−1, gi−1 are computed correctly. We will show that fi and gi are also correct.
Let’s consider sequence a1, a2, . . . , ai. We know the number of subsequence with even and
odd sums of the sequence a1, a2, . . . , ai−1, which are also part of a1, a2, . . . , ai. To compute
the total numbers of subsequence of a1, a2, . . . , ai, we would need to consider ai.

First we consider the case where ai = 0. To calculate fi, the number of subsequence of
a1, a2, . . . , ai with an even sum, we perform case analysis on whether ai is in the subsequence.
If ai = 0 is in the subsequence, consider the rest of the subsequence, excluding ai. It could
either be 1. a subsequence of a1, a2, . . . , ai−1 with even sum, since adding ai to the subse-
quence will not affect the total sum, and there are fi−1 of those, or 2. empty, which means
the original subsequence is ai itself which is even. So the total number of even subsequence
including ai would be fi−1 + 1. If the subsequence does not include ai, then it must be an
even sum subsequence of a1, a2, . . . , ai−1, and there are fi−1 of those. Thus, if we add the 2
sets, then we have fi = fi−1 + 1 + fi−1 = 2fi−1 + 1. Similarly for gi, we can also discuss 2
cases: include ai and not include ai. If we include ai, then it doesn’t affect the total sum and
we would have gi−1 subsequence. In this case, we don’t add one because ai = 0 is not an odd
number. If we don’t include ai, then the number of subsequence is the same. Thus, gi = 2gi−1.

Then we consider the case where ai = 1 and perform similar case analysis. For fi, if we
include ai, the size of included set would be gi−1 since odd number plus ai = 1 would be even.
For the non-include set, the size would be fi−1 since we don’t change the subsequence. Thus,
we can say fi = gi−1+fi−1. Likewise, for gi, the size of the included set would be fi−1+1 since
even number plus 1 is odd and ai itself is an odd number. The size of the non-included set
would be gi−1 because we don’t change the subsequence. Then, we have gi = gi−1 + fi−1 + 1.
Since all previous sub-problems are computed correctly, the answer to the initial problem will
also be correct.

Related Posts