CS代考 COMP3711: Design and Analysis of Algorithms

DP Tutorial 8

COMP3711: Design and Analysis of Algorithms
A DP problem from an old exam Decoding Numbers to Letters

A Problem From an Old Exam
1)“A”→1, “B”→2, …, “Z”→26
Given an encoded message A containing n digits in 1-9, design a O(n) time dynamic programming algorithm to determine the total number of ways to decode A.
Let be the total number of ways to decode A[1..i].
Base Cases:
since there is only one way to decode the items
Working through the possibilities (checking whether A[1,2] can encode a single letter or not, shows

A Problem From an Old Exam
1)“A”→1, “B”→2, …, “Z”→26
Given an encoded message A containing n digits in 1-9, design a O(n) time dynamic programming algorithm to determine the total number of ways to decode A.
Let be the total number of ways to decode A[1..i]. General Case: If
If A[ can not encode a letter (because it is > 26) then
the decoding must have A[i] encoding a unique letter. Otherwise there are two possibilities: either A[i-1, i] encodes a single letter or encodes two different letters. This yields

A Problem From an Old Exam
1)“A”→1, “B”→2, …, “Z”→26
Given an encoded message A containing n digits in 1-9, design a O(n) time dynamic programming algorithm to determine the total number of ways to decode A.
Let be the total number of ways to decode A[1..i])
Base Case:
General Case: If
This can be implemented in time. time to calculate each
time to calculate all the

Version of 10/22/2021
The 0/1 Knapsack Problem

The 0/1 Knapsack Problem
(i) Give an dynamic programming algorithm for the 0-1 knapsack problem where is the number of items and W is the max weight that can fit into the knapsack.
Recall that the input is items with given weights
and associated values 􏰆 􏰈 􏰀 and the objective is to choose a set of items with weight with maximum value.
(2) Now suppose that you are given two knapsacks with the same max weight . Give an 2 dynamic programming algorithm for finding the maximum value of items that can be carried by the two knapsacks.

Problem implicitly assumes that and the 􏰌 are all integers.
This was not needed for the fractional knapsack case (and its greedy solution) but is required for “polynomial-time” solutions of the 0-1 knapsack problems
We first solve the one-knapsack case. The algorithm is based on defining a table
is the maximum value of objects
chosen from the set of the first objects
that can be placed in a knapsack that has maximum weight .
The optimal solution to the problem is .

is the maximum value of objects
chosen from the set of the first objects
that can be placed in a knapsack that has maximum weight .
The algorithm is based on the following recurrence relation:
with initial conditions:
Note: is being used to denote that something is impossible.

There are two possible cases for :
Either (i) the ’th item is not included or (ii) the ’th item is included.
(i) If ’th item is not included in knapsack
optimal solution is optimal solution using the first
(ii) If the i ’th item is included in knapsack, it adds value After inclusion, knapsack has weight capacity of
filled by the first items with additional value
𝑖 which is optimally
If 􏰎 ’th item can’t fit into knapsack; this is flagged by “initial condition”

Fill in the table by first filling in and then
calculate using (*)
Note: when evaluating
have already been evaluated.
There are table entries and each requires only time to evaluate the entire algorithm uses only time.
Alg calculates best Value. To find set of items achieving that value, maintain auxiliary Boolean matrix Included , set to be T or F depending upon whether max occurs at
or 𝑖 𝑖 . Using standard approach, can reconstruct optimal set from matrix by working backwards from Included

Alternatively, don’t use recurrence/code as:
𝑖 flag and write the

We now discuss the case of two knapsacks.
Algorithm for this case is a simple generalization of the previous one and is based on defining a table
is maximum value of objects chosen from the set of the first objects
that can be placed in two knapsacks,
with first knapsack having weight capacity 1, and second knapsack having weight capacity 2.
The optimal solution to the problem is .

The algorithm is based on the following recurrence relation:
with initial conditions: 􏰆􏰈􏰆􏰈
Basic idea behind the equation is that the three terms on the right hand
side correspond to the 3 cases in which optimal solution for (i) does not use item at all or
(ii) puts item in the first knapsack or
(iii) puts item in the second knapsack.
We do not go into more details because this is similar to the derivation of 1 knapsack case.

The algorithm is based on the following recurrence relation:
with initial conditions: 􏰆􏰈􏰆􏰈
If all of the items on right hand side of recurrence were already known, left hand side could be calculated in time.
It’s not hard to find an ordering that satisfies this property the algorithm runs in 􏰈 time.
As before, algorithm only finds the best value.
To find actual items in two knapsacks you need to keep an auxiliary matrix that associates with each entry in the matrix, how the optimal value for that entry was achieved.

The longest arithmetic progression problem

The Longest Arithmetic Progression
An arithmetic progression is such that the n-th term is
For example: 4, 7, 10, 13,… is an arithmetic progression
Describe and analyze an efficient algorithm to find the length of the longest arithmetic progression in a sequence of integers.
For example, if the input sequence is 9, 4, 7, 2, 10, your algorithm should output 3, corresponding to the subsequence 4,7,10.
For full credit, your algorithm should run in 􏰈 time.

An arithmetic progression is such that the n-th term is
For example: 4, 7, 10, 13,… is an arithmetic progression
Describe and analyze an efficient algorithm to find the length of the longest arithmetic progression in a sequence of integers.
We use a memoization strategy, to store arithmetic sequences we have found so farthatendwithindex .
In the hash map , we remember the longest possible arithmetic sequence that ends at index and its .
If we find a longer sequence, we update the last index and delete the previous entry from the hash map

Describe and analyze an efficient algorithm to find the length of the longest arithmetic progression in a sequence
of integers.
Let be the longest arithmetic progression that ends and includes the element at
Base Case:
General Case: If and
This can be implemented in 􏰈 time.

Base Case:
General Case: If and
Stored values in hash map

Base Case:
General Case: If and
Finally, we find the largest value in the hash map
Stored values in hash map
and return

Number of contiguous subarrays with average k

Number of contiguous subarrays with average k
Describe and analyze an efficient algorithm to find the number of contiguous subarrays from an array that have an average equal to .
For example, if the input array is 1, 3, 1, 5, 7 and , your algorithm should output 3, corresponding to the subarrays {3}, {1,5}, {3,1,5}.
For full credit, your algorithm should run in time.

Describe and analyze an efficient algorithm to find the number of contiguous subarrays from an array that have an average equal to .
Note: Given an array with elements, if the average is avg , then
avg avg avg
If we subtract from every element of and the sum is equal to 0
If we split and ∀􏰌
, then the average of all the elements is (avg
to two subarrays at a random index then

Describe and analyze an efficient algorithm to find the number of contiguous subarrays from an array that have an average equal to .
, then avg . (1)
to two subarrays at a random index then
If we split
and ∀􏰌 We name
The suffix
as the prefix and
always includes at least the last element, i.e., .
as the suffix.
To find all the suffixes that end with and have an average of
we count all the prefixes such that 􏰙􏰌􏰍􏰆 (by equation 1 & 2). Thus, we sum and count the contiguous subarrays that end at

Naïve Solution
Describe and analyze an efficient algorithm to find the number of contiguous
subarrays from an array that have an average equal to
To find all the suffixes that end with and have an average of prefixes such that 􏰙􏰌􏰍􏰆 (by equation 1 & 2).
Thus, we sum and count the contiguous subarrays that end at Let 􏰙 􏰙􏰌􏰍􏰇 for ,westore 􏰙inatable .
For any and 􏰙 , we find all prefixes such that 􏰌 and allsuchoccurrencesandaddthemto 􏰙.
, we find all the .
. We count
􏰙storesthecountofthecontiguoussubarraysthatsatisfytheconditionupto . The base cases are 􏰇 and 􏰇 .

Base Case: and
General Case: If
Naïve Solution
we set up our base base cases:

Naïve Solution
Base Case: and
General Case: If

Naïve Solution
Base Case: and
General Case: If
This implies that we remove the prefix

Naïve Solution
Base Case: and
General Case: If

Naïve Solution
Base Case:
General Case: If
This implies that we remove the prefixes and

General Case: If
Naïve Solution
Base Case: and
Finally, we return

Describe and analyze an efficient algorithm to find the number of contiguous
subarrays from an array
Instead of using a table occurrences of each 􏰌.
Base Case:
General Case: If
that have an average equal to .
, we use a hash map to store the number of

Base Case:
General Case: If
, we set up our base cases:
Stored values on hash map

Base Case: , and
General Case: If
Stored values on hash map We update

Base Case: , and
General Case: If
This implies that we remove the prefix
Stored values on hash map We update

Base Case: , and
General Case: If
Stored values on hash map We update

Base Case: , and
General Case: If
This implies that we remove the prefixes and
Stored values on hash map We update

Base Case: , and
General Case: If
Stored values on hash map We update
Finally, we return

The longest oscillating subsequence problem

A Problem From an Old Exam
A sequence of numbers
􏰆 􏰈 􏰀 is oscillating if 􏰌􏰑􏰆 for every odd index i
􏰌􏰑􏰆 for even index i
For example, the sequence below is oscillating. 2, 7, 1, 8, 2, 6, 1, 8, 3
Describe and analyze an efficient algorithm to find a longest oscillating subsequence in a sequence of n integers.
Your algorithm only needs to output the length of the oscillating subsequence.
For example if the input sequence is 2, 4, 5, 1, 4, 2, 1, your algorithm should output 5, corresponding to the subsequence 2, 4, 1, 4, 1, or 2, 4, 1, 4, 2, or any other such subsequence.
For full credit, your algorithm should run in 􏰈 time.

Recall “Longest Increasing Subsequence Problem”
Give an 􏰈 time dynamic programming algorithm to find the length of the longest monotonically increasing subsequence of a sequence of numbers, i.e, each successive number in the subsequence is greater than or equal to its predecessor.
For example, if the input sequence is
the output should be either

Solution to Longest Increasing Subsequence Problem
Let 􏰌 􏰆 􏰌 denote the prefix of consisting of the first items. Define to be the length of the longest increasing subsequence that
endswith 􏰌.
Length of the longest increasing subsequence in is given by
𝟏􏰜𝒓􏰝𝒊 𝒙𝒓 􏰜𝒙𝒊
For every it takes time to calculate 􏰌. =>therunningtimeis 􏰀􏰌􏰍􏰆 􏰈 .
We can modify this idea to solve the oscillating subsequence problem

Solution to Oscillating Subsequence Problem
Uses similar idea.
Let ends at
Let e ends at
be the length of the longest oscillating subsequence that and has an odd length;
be the length of the longest oscillating subsequence that and has an even length;
Base Case:
Main New Observation:
In order to be able to add a new item to the end of an oscillating sequence that ended at a previous we need to know if that sequence was odd size (went down) or even size (went up).
That requires maintaining TWO different tables.
One for odd size oscillating subseqs and one for even ones.

Solution to Oscillating Subsequence Problem
Uses similar idea.
Let ends at
Let e ends at
be the length of the longest oscillating subsequence that and has an odd length;
be the length of the longest oscillating subsequence that and has an even length;
General Case: For e
If for all
=> no even oscillating subsequence ending at 􏰌 exists.
Otherwise, longest even oscillating sequence ending with
􏰌 where is an odd oscillating sequence ending at
where 􏰙 􏰌and ==>

Let ends at Let e ends at
be the length of the longest oscillating subsequence that and has an odd length;
be the length of the longest oscillating subsequence that and has an even length;
Solution to Oscillating Subsequence Problem
Base Case: General Case
Final solution is maximum of all the
Since each and can be calculated in entire algorithm requires time.
􏰙􏰝􏰌 & 􏰠􏰞􏰝􏰠􏰟
􏰙􏰝􏰌 & 􏰠􏰞􏰡􏰠􏰟

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts