CSC373 – Problem Set 3
To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources (people, print, electronic) outside of your group, the course notes, and the course staff, that you consulted.
Problem Set: due October 28, 2016 22:00
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity.
Answers that are technically correct that are hard to understand will not receive full marks. Mark values for each question are contained in the [square brackets].
You may work in groups of up to THREE to complete these questions.
1 How Many Ways?
The input to this problem is a text T, a pattern P, and a nonnegative integer N.
Consider picking N nonempty, nonoverlapping substrings from T ; call them s1 , s2 , . . . , sN . If s1 s2 . . . sN
= P
The problem is to determine the number of ways that N substrings can be chosen from T so that we have a match with P.
concatenating the substrings together forms the same string as P ), then we have a match.
[5 marks] Follow the first four steps to design a dynamic-programming algorithm to solve this problem. Include and clearly
label each step in your submission. (Any guesses as to why I’m not asking for step 5?)
You must also provide a bottom-up dynamic programming Python program that we can run to test your work. We should be able to call function ways like this:
ways(T, P, N)
with the T string, P string, and N integer of our choice. The function should return the number of ways as an integer.
OK, an example. Suppose T is aababc, P is aabc, and N = 2. Then the answer is 4. Each line below shows one way to get P from T by choosing 2 appropriate substrings. The (1) and (2) indicate the two chosen substrings.
(1)aab ab (2)c (1)aa ba (2)bc (1)a ab (2)abc a (1)a b (2)abc
2 Robot Knapsack
A robot is in an n by n room and is allowed to start at any column in row 1. The robot has a knapsack with a weight capacity W , and, if programmed correctly, will maximize the value of the items that it puts in the knapsack.
Each cell (i,j) has zero or one item stored there. If an item is there, then vi,j gives its value and wi,j gives its weight. If there is no item there, then both wi,j = 0 and vi,j = 0.
The robot makes a sequence of moves. The robot picks up any item at its starting location, and then picks up any item on its cell after it completes a move. The allowable moves are to move down one row, diagonally down one row and to the left one column, or diagonally down one row and to the right one column.
Your goal is to write an algorithm to maximize the value of the items stored in the knapsack. Step 4 should give the optimal value, and step 5 should give the actual path that the robot should take to realize that value.
[5 marks] Follow the steps to design a dynamic-programming algorithm to solve this problem. Include and clearly label each step in your submission.
(that is,