Algorithms’ Assignment-4 DYNAMIC PROGRAMMING

`
CS 310 ‘Algorithms’ Assignment-4

DYNAMIC PROGRAMMING
Q1. [15 marks]
A factory produces solar panels for large businesses. The volume of panels produced
depends on the orders placed by its customers. The machines at the factory can be run at
low production capacity or high production capacity. If the machines are to be run at high
capacity in some week (say week X), then they must be stopped and specially primed in
week X-1 and can’t produce any panels during that time. The machines, however, can be run
at low capacity for weeks without stopping. A high capacity week can also be immediately
followed by a low capacity week. A high capacity job can be selected in Week 1 as it is
assumed that the machines are already primed.
The factory manager maintains a record of high and low capacity orders for each week and
must decide which one to pick each week or stop for priming. The goal is to select a
combination of low and high orders so that the overall revenue for the factory is maximized.
Let RL denote the revenue for a low capacity job and RH denote the revenue for a high
capacity job.
Example: Suppose the factory manager maintains the following table. The revenue for
week-1 would be 22 if the manager picks a high capacity order and 20 if a low capacity order
is selected. Similarly for other weeks. Assume that the factory manager has this information
for ‘n’ weeks, you have to find which combination of RH and RL will maximize the total
revenue for n weeks.
Week 1 Week 2 Week 3 Week 4 Week 5
RH 22 4 100 200 100
RL 20 15 65 100 60
A) Write an efficient dynamic-programming algorithm in C/C++ that determines what
should be done in each of the n weeks (low job, high job or priming) to maximize the
overall revenue. Print the selection for each week and the value of the revenue at the
end of n
th week. Clearly write the base case and recurrence relation of the problem
in the comments of your code. You must clearly specify what your recurrence
relation defines and what are the parameters that it takes. [14]
B) What is the time complexity of your algorithm? Describe how many subproblems
you’ve computed and how much time it takes to compute each subproblem. [1]
`
Your program will read the input from a text file. The first line of the file contains one positive
integer value for n. The second line has n positive numbers for RH and the third line has n
positive numbers for RL
. See input format below.
Input format:
n 5
RH 22 4 100 200 100
RL 20 15 65 100 60
Output format:
Week 1: High 22
Week 2: Low 15
Week 3: Priming
Week 4: High 200
Week 5: Low 60
Total Revenue: 297
Q2. [15 marks]
Suppose you are standing in a building that contains a set of connected corridors. We are
going to model the corridors as edges in an undirected graph and the junctions of the
corridors as nodes of the graph. Note there are no cycles in the graph. You can go from one
corridor to another through the junctions. We want to install lights at the junctions such that
all the corridors are illuminated, however, we want to install as few lights as possible. A
light at a junction will illuminate all of the corridors (i.e. edges) that it is connected to.
For example, in Figure 1, there are nine junctions, labelled A to I and eight corridors
connecting those junctions.
Figure 1
The minimum number of lights required for Figure 1 is three. E.g. If we install lights at
junctions B, C and D then we can illuminate all eight corridors with just three lights.
Note that other answers are also possible, which give the optimal minimum.
For example:
- install lights at A, E and D, or
- install lights at A, C and D
A) Write an efficient dynamic-programming algorithm in C/C++ that determines the
minimum number of lights required. Clearly write the base case and recurrence
relation of the problem in the comments of your code. You must clearly specify
`
what your recurrence relation defines and what are the parameters that it takes.
[14]
B) What is the time complexity of your algorithm? Describe how many subproblems
you’ve computed and how much time it takes to compute each subproblem. [1]
You will read the input from a text file where the first line contains the value of ‘n’, which is
the number of nodes in your graph. The graph nodes are numbered from 0 to n-1. The graph
format is similar to the one in the previous assignments.
Figure 2
Input Format (for Figure 2):
n 9
0 : 1 2
1 : 0 3
2 : 0 4
3 : 1 5 6 7 8
4 : 2
5 : 3
6 : 3
7 : 3
8 : 3
Output Format:
Minimum Lights 3
{0, 3, 4} /* This indicates the nodes where lights are installed */
Q3. [15 marks]
You are given a ruler of length ‘n’, which has markings at unit length distances labeled 1 to n
from left to right. This ruler is to be cut at ‘m’ positions. You are given the ‘m’ cut
positions/labels on the ruler. Each cut has a different cost which depends on the order in
which the cuts are made, as described in the following example.
Example:
Suppose you are given a ruler of length n=15, which is to be cut at m=3 positions. The
cuts should be made at labels {3, 5, 10}. The cost of a cut is equal to the length of the
ruler segment on which the cut is applied.
`
● One way of cutting the ruler is that you decide to make the first cut at label 5. The
ruler segment on which this first cut is made is the whole ruler, so the cost of the first
cut is its length, i.e., 15. Now the ruler is in two pieces of lengths 5 and 10, let’s call
them piece 1 and piece 2, respectively. You decide to make the second cut at label 3,
which lies on piece 1. The length of piece 1 is 5 so cost of this second cut is 5. The
third and last cut is made at label 10 which lies on piece 2 and its cost is equal to
length of piece 2 i.e., 10. Total cost of cutting the ruler in this order is 15+5+10 = 30.
● Another way of cutting the ruler is that you decide to make the first cut at label 3. The
ruler segment on which this first cut is made is the whole ruler, so the cost of the first
cut is its length, i.e., 15. Now the ruler is in two pieces of lengths 3 and 12, let’s call
them piece 1 and piece 2, respectively. You decide to make the second cut at label 5
which lies on piece 2. The length of piece 2 is 12 so cost of this second cut is 12.
Now piece 2 is further divided into two pieces, let’s call them piece 2A of length 2 and
piece 2B of length 10. The third and last cut is made at label 10 on piece 2B and its
cost is equal to length of piece 2B i.e., 10. Total cost of cutting the ruler in this order
is 15+12+10 = 37.
● Yet another way of cutting the ruler is that you decide to make the first cut at label 10.
The ruler segment on which this first cut is made is the whole ruler, so the cost of the
first cut is its length, i.e., 15. Now the ruler is in two pieces of lengths 10 and 5, let’s
call them piece 1 and piece 2, respectively. You decide to make the second cut at
label 3 which lies on piece 1. The length of piece 1 is 10 so cost of this second cut is
10. Now piece 1 is further divided into two pieces, let’s call them piece 1A of length 3
and piece 1B of length 7. The third and last cut is made at label 5 on piece 1B and its
cost is equal to length of piece 1B i.e., 7. Total cost of cutting the ruler in this order is
15+10+7 = 32.
As you can see, there are other possible orderings as well. You have to find an ordering of
cuts that has the least cost.
A) Write an efficient dynamic-programming algorithm in C/C++ that solves the above
problem. The input to your program is the value of ‘n’ and ‘m’ cut positions, where
m<n. You have to specify the optimal ordering of the cuts and its cost. Clearly write
the base case and recurrence relation of the problem in the comments of your
code. You must clearly specify what your recurrence relation defines and what
are the parameters that it takes. Remember: Think about overlapping subproblems
in this question before starting to code. [14]
B) What is the time complexity of your algorithm? Describe how many subproblems
you’ve computed and how much time it takes to compute each subproblem. [1]
You will read the input from a text file that contains the value of ‘n’ and the ‘m’ labels where
the ruler is to be cut (see input format below).
Example 1
Input Format:
n 15
m 3 5 10
`
Output Format:
Optimal cut ordering: 5 3 10
Least cost: 30
Example 2
Input Format:
n 100
m 2 3 15 88 89 93 95
Output Format:
Optimal cut ordering: 15 3 2 88 93 89 95
Least cost: 227
Note: More than one optimal cost orderings are possible.
Q4. [15 marks]
Let S1, S2 and S3 be three strings. String S1 is ‘n’ characters long, S2 is ‘m’ characters long
and S3 is n+m characters in length. You have to find if S3 can be formed by some
interleaving of all the characters in S1 and S2 such that the left to right ordering of the
characters in each string is preserved.
Example: Let S1 = “merges” and S2 = “mired”
S3 = “mmiergreeds” is a valid interleaving.
S3 = “msergemired” is an invalid interleaving, because left to right ordering is violated and
similarly S3 = “mirgesmered” is an invalid interleaving.
A) Write an efficient dynamic-programming algorithm in C/C++ that determines whether
S3 is a valid interleaving of S1 and S2. Your code should output VALID or INVALID.
If VALID, then mention the interleaving order (see output below). Clearly write the
base case and recurrence relation of the problem in the comments of your code.
You must clearly specify what your recurrence relation defines and what are
the parameters that it takes. [14]
B) What is the time complexity of your algorithm? Describe how many subproblems
you’ve computed and how much time it takes to compute each subproblem. [1]
Your program will read the three strings from an input text file. String S1 will be on the first
line of the file, S2 on the second and S3 on the third line. See input format below.
Input format:
merges
mired
mmiergreeds
`
Output format:
VALID
1:m
2:mi
1:erg
2:re
1:e
2:d
1:s
/* 1:m means the character m is selected from string S1. 2:mi means that two characters mi
are selected from string S2. The rows in the output format represent the order of the
selection to form the valid interleaving, i.e. in this example, one character is selected from
S1, followed by two characters from S2, followed by three characters from S1 and so on. */
Note: More than one valid interleavings are possible.
Instructions and policies
1. When submitting, please rename the folder according to your roll number.
2. Do delete all executables and test files before submitting your assignment on LMS.
3. Folder convention should not be changed. If you make any changes, the auto
grader will grade your assignment 0.
4. You are allowed to discuss strategies to solve assignment questions with your
classmates. Group learning is encouraged, however, the code must be your own.
You are not allowed to copy code from each other or from other sources. Remember
to acknowledge other classmates if discussions with them has helped you.
5. You should name your code files using the following convention: qx.cpp
6. If the assignment includes any theoretical questions, then type your answer to those
questions and submit a separate pdf file for each using the naming convention above.
7. Upload all your files in the corresponding assignment folder on LMS. There will be a
20% deduction for assignments submitted up to one day late (the late
deduction is only applicable to the questions submitted late, not on the whole
assignment). Assignments submitted 24 hours after the deadline will not be
marked.
8. There will be vivas during grading of the assignment. The TAs will announce a
schedule and ask you to sign up for viva time slots. Failure to show up for vivas will
result in a 70% marks reduction in the assignment.
9. In the questions where you are asked to create test cases. Think carefully about good
test cases that check different conditions and corner cases. The examples given in
the assignment are for clarity and illustration purposes. You should not assume that
those are the only test cases your code should work for. Your code should be able to
scale up to larger input sizes and more complex scenarios.
`
10. Do not make arbitrary assumptions about the input or the structure of the problem
without clarifying them first with the Instructor or the TAs.
11. We will use automated code testing so pay close attention to the input and
output formats.
12. Make sure that your code compiles and runs on Ubuntu. You may choose to
develop your code in your favourite OS environment, however, the code must
be properly tested on Linux before submission. During vivas, your code should
not have any compatibility issues. It's a good idea to use gcc -Wall option flag
to generate the compiler's warnings. Pay attention to those warnings as fixing
them will lead to a much better and robust code.
13. For full credit, comment your code clearly and state any assumptions that you have
made. There are marks for writing well-structured and efficient code.
14. Familiarize yourself with LUMS policy on plagiarism and the penalties associated with
it. We will use a tool to check for plagiarism in the submissions.