Assignment 04 Solution

Description

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 R_L denote the revenue for a low capacity job and R_H 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 R​ and R​ will maximize the total

H L

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
​

1. 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 R​ and the third line has n

H ​

positive numbers for R​. See input format below.

L​

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

1. 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:12

1:03

2:04

3:15678

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​.

1. 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.

1. 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: q​x​.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.

10. We will use automated code testing so pay close attention to the input and output formats.

11. 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.

10. 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.

10. 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.