`

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.