COMP3121/9101
Algorithm Design
Copyright By PowCoder代写 加微信 powcoder
Problem Set 5 – Dynamic Programming
[K] – key questions [H] – harder questions [E] – extended questions [X] – beyond the scope of this course
1 SECTION ONE: OPTIMISATION 2
2 SECTION TWO: ENUMERATION 4
3 SECTION THREE: KNAPSACK AND RELATED PROBLEMS 5
4 SECTION FOUR: STRINGS 6
5 SECTION FIVE: SHORTEST PATHS 8
Problem Set 5 SECTION ONE: OPTIMISATION
§ SECTION ONE: OPTIMISATION
[K] Exercise 1. You are given n intervals on an axis. The ith interval [li, ri) has integer endpoints li < ri and has
a score of si. Your task is to select a set of disjoint intervals with maximum total score. Note that if intervals i and j
satisfy ri = lj then they are still disjoint. Design an algorithm which solves this problem and runs in O(n
[K] Exercise 2. Due to the recent droughts, n proposals have been made to dam the Murray river. The ith proposal
asks to place a dam xi meters from the head of the river (i.e., from the source of the river) and requires that there is
not another dam within ri metres (upstream or downstream). Design an algorithm that returns the maximal number
of dams that can be built, you may assume that xi < xi+1 for all i = 1, . . . , n− 1.
[K] Exercise 3. You are given a set of n types of rectangular boxes, where the ith box has height hi, width wi and
depth di. You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of
another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the
higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple
instances of the same type of box. Design an O(n2) algorithm that returns the maximum height of the stack of boxes.
Hint: How can we reduce this to a problem without rotations?
[K] Exercise 4. You have n1 items of size s1 and n2 items of size s2. You would like to pack all of these items into
bins, each of capacity C > s1, s2, using as few bins as possible. Design an algorithm that returns the minimal number
of bins required.
[K] Exercise 5. Consider a row of n coins of values v1, v2, …vn, where n is even. We play a game against an opponent
by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row
permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely
win if we move first.
[K] Exercise 6. Given a sequence of n positive or negative integersA1, A2, . . . , An, determine a contiguous subsequence
Ai to Aj for which the sum of elements in the subsequence is maximised.
[H] Exercise 7. Skiers go fastest with skis whose length is close to their height. Consider n skiers with heights
h1, h2, . . . , hn, gets a delivery of m ≥ n pairs of skis, with lengths l1, l2, . . . , lm. Design an algorithm to assign to each
skier one pair of skis to minimise the sum of the absolute differences between the height hi of the skier and the length
of the corresponding ski they got, i.e., to minimise
∣∣hi − ls(i)∣∣
where s(i) is the index of the skies assigned to the skier of height hi.
[H] Exercise 8. You have been handed responsibility for a business in Texas for the next n days. Initially, you have
K illegal workers. At the beginning of each day, you may hire an illegal worker, keep the number of illegal workers the
same or fire an illegal worker. At the end of each day, there will be an inspection. The inspector on the ith day will
check that you have between li and ri illegal workers (inclusive). If you do not, you will fail the inspection. Design an
COMP3121/9101 – Term 3, 2022 2
Problem Set 5 SECTION ONE: OPTIMISATION
algorithm that determines the fewest number of inspections you will fail if you hire and fire illegal employees optimally.
[H] Exercise 9. A company is organising a party for its employees. The organisers of the party want it to be a fun
party, and so have assigned a fun rating to every employee. The employees are organised into a strict hierarchy, i.e.
a tree rooted at the president. There is one restriction, though, on the guest list to the party: an employee and their
immediate supervisor (parent in the tree) cannot both attend the party (because that would be no fun at all). Give an
algorithm that makes a guest list for the party that maximises the sum of the fun ratings of the guests.
[H] Exercise 10. You have to cut a wood stick into several pieces. The most affordable company, Analog Cutting
Machinery (ACM), charges money according to the length of the stick being cut. Their cutting saw allows them to
make only one cut at a time. It is easy to see that different cutting orders can lead to different prices. For example,
consider a stick of length 10 m that has to be cut at 2, 4, and 7 m from one end. There are several choices. One can
cut first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 m, the
resulting stick of 8 m, and the last one of 6 m. Another choice could cut at 4, then at 2, then at 7. This would lead to
a price of 10 + 4 + 6 = 20, which is better for us. Your boss demands that you design an O(n2) algorithm to find the
minimum possible cutting cost for any given stick.
[H] Exercise 11. You are given an n×n chessboard with an integer in each of its n2 squares. You start from the top
left corner of the board; at each move you can go either to the square immediately below or to the square immediately
to the right of the square you are at the moment; you can never move diagonally. The goal is to reach the right bottom
corner so that the sum of integers at all squares visited is minimal.
(a) Describe a greedy algorithm which attempts to find such a minimal sum path and show by an example that such
a greedy algorithm might fail to find such a minimal sum path.
(b) Describe an algorithm which always correctly finds a minimal sum path and runs in time n2.
(c) Describe an algorithm which computes the number of such minimal paths.
(d) Assume now that such a chessboard is stored in a read only memory. Describe an algorithm which always correctly
finds a minimal sum path and runs in linear space (i.e., amount of read/write memory used is O(n)) and in time
Hint: For (d), combine divide and conquer with dynamic programming.
COMP3121/9101 – Term 3, 2022 3
Problem Set 5 SECTION TWO: ENUMERATION
§ SECTION TWO: ENUMERATION
[K] Exercise 12. Some people think that the bigger an elephant is, the smarter it is. To disprove this, you want
to analyse a collection of elephants and place as large a subset of elephants as possible into a sequence whose weights
are increasing but their IQ’s are decreasing. Design an O(n log n) algorithm which, given the weights and IQ’s of n
elephants, will find a longest sequence of elephants such that their weights are increasing but IQ’s are decreasing.
[K] Exercise 13. There are n levels to complete in a video game. Completing a level takes you to the next level,
however each level has a secret exit that lets you skip to another level later in the game. Determine if there is a path
through the game that plays exactly K levels.
[K] Exercise 14. A partition of a number n is a sequence ⟨p1, p2, . . . , pt⟩ (we call the pk parts) such that 1 ≤ p1 ≤
p2 ≤ . . . ≤ pt ≤ n and such that p1 + . . .+ pt = n. Define numpart(k, n) to be the number of partitions of n such that
every part is at most k.
(a) Explain why numpart(1, n) = 1 for each n.
(b) Devise a recursion to determine the number of partitions of n in which every part is smaller or equal than k,
where n, k are two given numbers such that 2 ≤ k ≤ n.
(c) Hence, find the total number of partitions of n.
[K] Exercise 15. Given an array of n positive integers, find the number of ways of splitting the array up into
contiguous blocks of sum at most k in O(n2) time.
[H] Exercise 16. You are given a boolean expression consisting of a string of the symbols true (T ) and false (F ) and
with exactly one operation of and (∧), or (∨) or xor (⊕) between any two consecutive symbols(truth values). Count
the number of ways to place brackets in the expression such that it will evaluate to true.
[H] Exercise 17. We are given a checkerboard which has 4 rows and n columns, and has an integer written in each
square. We are also given a set of 2n pebbles, and we want to place some or all of these on the checkerboard (each
pebble can be placed on exactly one square) so as to maximise the sum of the integers in the squares that are covered
by pebbles. There is one constraint: for a placement of pebbles to be legal, no two of them can be on horizontally or
vertically adjacent squares (diagonal adjacency is fine).
(a) Determine the number of legal patterns that can occur in any column (in isolation, ignoring the pebbles in adjacent
columns) and describe these patterns.
Call two patterns compatible if they can be placed on adjacent columns to form a legal placement. Let us consider
sub-problems consisting of the first k columns 1 ≤ k ≤ n. Each sub-problem can be assigned a type, which is the
pattern occurring in the last column.
(b) Using the notions of compatibility and type, give an O(n)-time algorithm for computing an optimal placement.
COMP3121/9101 – Term 3, 2022 4
https://en.wikipedia.org/wiki/Logical_conjunction
https://en.wikipedia.org/wiki/Logical_disjunction
https://en.wikipedia.org/wiki/XOR_gate
Problem Set 5 SECTION THREE: KNAPSACK AND RELATED PROBLEMS
§ SECTION THREE: KNAPSACK AND RELATED PROBLEMS
[K] Exercise 18. You have an amount of money M and you are in a candy store. There are n kinds of candies and
for each candy, you know how much pleasure you get by eating it, which is a number between 1 and K, as well as the
price of each candy. Your task is to choose which candies you are going to buy to maximise the total pleasure you will
get by gobbling them all.
[K] Exercise 19. Your shipping company has just received N shipping requests (jobs). For each request i, you know
it will require ti trucks to complete, paying you di dollars. You have T trucks in total. Out of these N jobs you can
take as many as you would like, as long as no more than T trucks are used total. Devise an efficient algorithm to select
jobs that will bring you the largest possible amount of money.
[K] Exercise 20. Again your shipping company has just received N shipping requests (jobs). This time, for each
request i, you know it will require ei employees and ti trucks to complete, paying you di dollars. You have E employees
and T trucks in total. Out of these N jobs you can take as many of them as you would like, as long as no more than E
employees and T trucks are used in total. Devise an efficient algorithm to select jobs which will bring you the largest
possible amount of money.
COMP3121/9101 – Term 3, 2022 5
Problem Set 5 SECTION FOUR: STRINGS
§ SECTION FOUR: STRINGS
[K] Exercise 21. We say that a string A occurs as a subsequence of another string B if we can obtain A by deleting
some of the letters of B. Design an algorithm that for two strings A and B gives the number of different occurrences
of A in B, i.e., the number of ways one can delete some of the symbols of B to get A.
[K] Exercise 22. For bit strings X = x1 . . . xn, Y = y1 . . . ym and Z = z1 . . . zn+m, we say that Z is an interleaving
of X and Y if it can be obtained by interleaving the bits in X and Y in a way that maintains the left-to-right order of
the bits in X and Y .
[K] Exercise 23. A palindrome is a sequence of at least two letters which reads equally from left to right and from
right to left. For example, the string S = ababa is a palindrome of length 5.
Given a sequence of letters (a string), find efficiently its longest subsequence (not necessarily contiguous) that is a
palindrome. In other words, we are looking for the longest palindrome which can be obtained by crossing out some of
the letters of the initial sequence without permuting the remaining letters.
[X] Exercise 24. A context-free grammar is a tuple ⟨V,Σ, R, S⟩, where:
• V is a set of variables;
• Σ is a finite set of symbols used to define characters of a word;
• R is a set of production rules that determines how the strings can be generated by the grammar;
• S is the start variable.
The rules of a grammar come in the form:
• A → α where A is a variable and α is a symbol,
• A → BC where A,B,C are variables and B,C are not the start variable,
• S → ϵ where ϵ is the empty character.
To generate a string, we use the production rules given above and keep performing substitutions until we get to a point
where there are no variables. That is, we repeatedly replace variables with the corresponding symbol or variable given
by the production rules.
(a) Consider the context-free grammar, G = ⟨V,Σ, R, S⟩, where
• V = {A,B,C},
• Σ = {0, 1},
• R is given by the production rules:
– A → ϵ or A → BC,
– B → 0 or B → BB,
– C → 1 or C → CC,
We can generate the string 01 because, starting with A → BC, we can replace B with 0 and C with 1. Thus, we
generate A → 01 and so, G generates 01. Using these production rules, find another string that can be generated
COMP3121/9101 – Term 3, 2022 6
Problem Set 5 SECTION FOUR: STRINGS
We now attempt to solve the membership problem; that is, given an arbitrary context-free grammar G and a
string w, does G generate w?
(b) Suppose that w is a symbol. Devise an O(1) algorithm to determine if G generates w.
(c) Now suppose that w is a string of length 2. Devise a recursion to determine if G generates w.
(d) Now suppose that w is a string of length n. Devise an O(n3) algorithm to determine if G generates w.
Note. This formally depends on the size of the grammar but the size of the grammar is independent of the length
of the string, so we treat the size of the grammar as a fixed constant.
COMP3121/9101 – Term 3, 2022 7
Problem Set 5 SECTION FIVE: SHORTEST PATHS
§ SECTION FIVE: SHORTEST PATHS
[K] Exercise 25. You are travelling by canoe down a river and there are n trading posts along the way. Before
starting your journey, you are given for each 1 ≤ i < j ≤ n the fee F (i, j) for renting a canoe from post i to post j.
These fees are arbitrary, for example it is possible that F (1, 3) = 10 and F (1, 4) = 5. You begin at trading post 1
and must end at trading post n (using rented canoes). Your goal is to design an efficient algorithm that produces the
sequence of trading posts where you change your canoe which minimizes the total rental cost.
COMP3121/9101 – Term 3, 2022 8
SECTION ONE: OPTIMISATION
SECTION TWO: ENUMERATION
SECTION THREE: KNAPSACK AND RELATED PROBLEMS
SECTION FOUR: STRINGS
SECTION FIVE: SHORTEST PATHS
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com