Questions

1.  Dynamic Progreamming: The maximum increasing subsequence problem is defined as follows:

Given a sequence of numbers, find an increasing subsequence of maximum length contains in it.  The subsequence does not have to be contiguous (which means – the numbers don’t have to follow con- secutively in the array).  We are looking for the sequence as the final answer, not just the size of the sequence. For example, if the input is:

0  8  4  12  2  10  6  14  1  9  5  13  3  11  7  15

A maximum contiguous subsequence is:

0  4  6  9  13  15

Notice that the solution is not necessarily unique, so other subsequences of size 6 may exist.  I will accept any valid sequence. In this example there are four possible solutions.

Write a dynamic programming program to solve the problem. The idea is as follows: given an input sequence a[0] . . . a[n · 1] each index j either extends a previous maximum length subsequence or starts a new one if a[j] is not larger than any previous element in the sequence.

Notice that since the sequence is not necessarily contiguous, it’s not sufficient to only check a[j · 1] for each a[j], but possibly all the elements left of a[j]. You can assume that no two elements in your input array are equal.

In addition to your input array keep also an array p[] where p[j] is the predecessor of a[j] in the maximum increasing subsequence ending in a[j], and an array s[] where s[j] is the size of the maximum subsequence ending in j.  These arrays will later be used to backtrack on the output and print the sequence.

Specs:

● Implement a class, DynamicSubsequence.

● The constructor should be:  public  DynamicSubsequence(ArrayList<Integer>  input) where the input is a list of numbers (as shown above). The input array should be a class variable (so the constructor copies the input parameter into a class variable).

● The class should have, in the minimum, the following function: public  ArrayList maxSubsequence(), which solves the Dynamic Programming problem and returns the output array containing the max-        imum subsequence.

● Any other methods or variables that you see fit.

● Notice: Please use the Java ArrayList for this question.

● The main program gives you a way to test your implementation.

2.  Sequence  alignment:  The question is loosely based on ”Creative Programming assignments” by Sedgewick and Wayne:

https://introcs.cs.princeton.edu/java/assignments/sequence.html

Important:  I adapted the question to match the sequence alignment process we saw in class.  For background see here: http://www.cs.umb.edu/cs310/homework/global seq.tex

The background in the question provides the recursive brute force process, but you should only imple- ment the dynamic programming part.  Test your program on the sequences suggested in the checklist (see bottom of the page here: https://www.cis.upenn.edu/ cis110/12su/hw/hw06/dynprog.shtml.

It is very important that you fully understand the dynamic programming sequence alignment algorithm before you start programming.   The algorithm,  once you understand it,  is very straightforward to implement, but the understanding part requires careful consideration. What helps is to run an example on paper. For example, for the two sequences in the question build the dynamic programming matrix and fill it manually, making sure you’re getting what you suppose to get.  Notice that unlike the links above (but like the process we showed in class), the matrix should be filled out from top to bottom and left to right.  Therefore, the final edit distance can be obtained from

opt[M][N] (bottom right).

Some guidelines:

● Implement two classes, Path and Match, in two separate files under the pa3 package.

● Your program should get a file as a command line parameter. Usage: java  pa3.Match  input.txt. where input.txt contains two DNA sequences separated by a newline. This is different from the description in both links above.

● Your program should consist of a class Match.java with one public method to compute the optimal match between a pair of objects.

● The optimal solution is returned as a linked list of Path nodes.  Each Path node stores the row and column of the element it represents, the total cost of the match from that point to the end, and a pointer to the next Path node.  So for opt matrix above, the Path nodes would follow the red numbers: the row and col variables of the first node would both be 8 and 10, respectively and cost would be 7. In the second node, row and col would be 7 and 9 respectively and the cost would be 6, and so on.  The reason for this is that the DP formula gives you the edit distance, but you also need to recover the alignment itself.

● You can take ideas for Match and Path from the API described here: http://www.cis.upenn.edu/ cis110/12su/hw/hw06/dynprog.shtml

BUT

–  The match function inside the Match class should be public and not static.

–  The Path class variables should be private.  The getters should be:  public  int  getRow(), public  int  getCol(),public  int  getCost() and public  Path  getNext().

– You will also need setters.

● The output should be in the same format as described in the link above (I won’t test it in the autograder but I’ll ask you to paste it in your memo.txt file).  BUT notice that the link above, and the S&W exercise it’s based on, do it all backwards.

● Therefore, to print the path in correct order you can store it in a stack or print it recursively.

● Use standard java and place all your files (from this and the other questions in a pa3 package, as per the instructions in the previous PAs.

3. Implement Move-To-Front. Loosely based on: http://coursera.cs.princeton.edu/algs4/assignments/burrows.html

In this assignment you only do the move-to-front part with some changes to prevent relying too much on the standard input and output. I copy the relevant parts here, with some edits:

Binary input and binary output: To enable your programs to work with binary data, you will use BinaryIn and BinaryOut, which are described in Algorithms, 4th edition and part of algs4.jar (as opposed to BinaryStdIn and BinaryStdOut. This means you have to work with files, and treat them like binary streams) To display the binary output when debugging, you can use HexDump, which takes a command-line argument n, reads bytes from standard input and writes them to standard output in hexadecimal, n per line.

> more  abra.txt

ABRACADABRA!

>  java  -cp  .:../lib/algs4.jar  edu.princeton.cs.algs4.HexDump  16  <  abra.txt

41  42  52  41  43  41  44  41  42  52  41  21

96  bits

Note that in ASCII, ’A’ is 41 (hex) and ’!’ is 21 (hex).

Move-to-front encoding and decoding: The main idea of move-to-front encoding is to maintain an ordered sequence of the characters in the alphabet, and repeatedly read in a character from the input message, print out the position in which that character appears, and move that character to the front of the sequence.  As a simple example, if the initial ordering over a 6-character alphabet is A B C D E F, and we want to encode the input CAAABCCCACCF, then we would update the move-to-front sequences as follows:

If the same character occurs next to each other many times in the input, then many of the output values will be small integers, such as 0, 1, and 2.  The extremely high frequency of certain characters makes an ideal scenario for Huffman coding (which you don’t have to implement).

Move-to-front encoding: Your task is to maintain an ordered sequence of the 256 extended ASCII characters. Initialize the sequence by making the ith character in the sequence equal to the ith extended ASCII character. Now, read in each 8-bit character c from the input file one at a time, output the 8-bit index in the sequence where c appears, and move c to the front.

>  java  -cp  .:../lib/algs4.jar  pa3.MoveToFront  -  abra.txt  |  java  -cp  .:../lib/algs4.jar

edu.princeton.cs.algs4.HexDump  16

41  42  52  02  44  01  45  01  04  04  02  26

96  bits

Move-to-front decoding:  Initialize an ordered sequence of 256 characters, where extended ASCII character i appears ith  in the sequence. Now, read in each 8-bit character i (but treat it as an integer between 0 and 255) from the input file one at a time, write the ith  character in the sequence, and move that character to the front. Check that the decoder recovers any encoded message.