CS230 Data Structures, Wellesley College, Fall 1999

Problem Set 3

Due any time Thursday, September 30

[CS230 Home Page] [Assignments] [Documentation] [Software Installation] [FAQ] [CS Dept.] [CWIS]


Notes:


Problem 0

To begin this problem set, download the Lists folder from the CS230 download folder. The file IntListOps.java contains the integer list methods that we discussed in class this past Thursday. It also contains some methods that we did not discuss. You should study all of these methods before proceeding with the other problems.

Executing the applet IntListOpsTest.html gives a TextApplet window in which you can see the results of various test cases involving some of the methods in IntListOps.java. Pressing the Run button displays the test results. The printed representation of lists has the elements in square brackets separated by commas. For instance, the list of numbers 3, 2, and 5 is displayed as [3, 2, 5].

Unfortunately, you cannot cut and paste text from this TextApplet window. If you would like to save the results to a text file, do the following:

Select the apple pull-down menu in the upper left hand corner of the Screen. In this menu, select Java Runtime>Save Text Window. You will be prompted for an output file name.

The above assumes that the "Write to stdout?" checkbox is checked. This makes sure that any displayed text appears in both the applet window and the stdout window. This is helpful for debugging your programs, for the following reason. The Run button does not print anything in the applet window until all the tests are complete, but it prints output to the stdout window on a line by line basis. If your code contains an infinite recursion, the applet window won't give you a clue of where it is because it will just be blank. But the stdout window will show you how far the tests progressed before the infinite recursion was encountered.

Why this bizarre interface? Because if the program were an application (rather than an applet), you would have to quit out of the Applet Viewer and relaunch every time you made a modification. This is very inconvenient. In contrast, when the program is an applet, simply selecting Applet>Reload in the AppletViewer menu will make your applet consistent with your changes.

One more note about TextApplets: when use the mouse to click on the upper left corner in order to close them, they often take a long time to close after you click. Be patient. I do not know why this happens.

Speaking of infinite recursions, you are very likely to encounter them on this assignment if you are not careful. They typically arise from accidentally calling a recursive list method on the argument list rather than the tail of the argument list within the body of a method. An infinite recursion will typically manifest itself by crashing your machine, so it's best to be as vigilant as possible in detecting them before you test your code! Liberally inserting calls to System.out.println in your code is a good way to detect infinite recursions.


Problem 1: IntList Methods

In this problem, you will define three methods that manipulate integer lists. Skeletons for these methods appear in the file PS3IntListOps.java. This file is configured so that you can use head, tail, prepend, etc as abbreviations for IntList.head, IntList.tail, IntList.prepend, etc. You can test your methods by executing the PS3IntListOpsTest.html applet. Although it is not required, you may find it helpful in some cases to define auxiliary methods.

Here are contracts and test case results for the three methods:

public static boolean isSorted(IntList L)
Returns true if the integers in L are sorted from low to high, and false otherwise.

Examples:

isSorted([ ]) = true
isSorted([1]) = true
isSorted([1]) = true
isSorted([1, 1]) = true
isSorted([2, 1]) = false
isSorted([1, 2, 3, 4, 5]) = true
isSorted([1, 2, 3, 4, 0]) = false
isSorted([1, 5, 3, 4, 2]) = false

 

public static IntList remove(int i, IntList L)
Returns a new list that contains all of the elements of L in the same order except for occurrences of i, which are removed.

Examples:

remove(0, [4, 2, 3, 4, 1, 3, 4, 2, 4, 3]) = [4, 2, 3, 4, 1, 3, 4, 2, 4, 3]
remove(1, [4, 2, 3, 4, 1, 3, 4, 2, 4, 3]) = [4, 2, 3, 4, 3, 4, 2, 4, 3]
remove(2, [4, 2, 3, 4, 1, 3, 4, 2, 4, 3]) = [4, 3, 4, 1, 3, 4, 4, 3]
remove(3, [4, 2, 3, 4, 1, 3, 4, 2, 4, 3]) = [4, 2, 4, 1, 4, 2, 4]
remove(4, [4, 2, 3, 4, 1, 3, 4, 2, 4, 3]) = [2, 3, 1, 3, 2, 3]

 

public static IntList removeDuplicates(IntList L)
Returns a new list that contains exactly only one occurrence of each integer that occurs in L. The order of the integers in the resulting list does not matter.

Examples:

removeDuplicates([ ]) = [ ]
removeDuplicates([3, 5, 2, 1, 4]) = [3, 5, 2, 1, 4]
removeDuplicates([4, 2, 3, 4, 1, 3, 4, 2, 4, 3]) = [4, 2, 3, 1]

Submission Details: Your hardcopy submission for this problem should be your final version of PS3IntListOps.java. Your softcopy submission for all three problems should be your final version of the Lists folder.


Problem 2: IntListList Methods

In this problem, you will define four methods that manipulate lists whose elements are integer lists. These are instances of the class IntListList, which supports the same methods as IntList except for a change in type. For instance, the head of an IntListList is an IntList, and the tail of an IntListList is an IntListList.

Skeletons for these methods appear in the file PS3IntListListOps.java. This file is configured so that you can use head, tail, prepend, etc as abbreviations for IntListList.head, IntListList.tail, IntListList.prepend, etc. However, some problems require class methods from other classes; for these, you will have to use an explicit prefix. E.g. IntList.head, IntListOps.length, PS3IntListOps.sorted, etc. You can test your methods by executing the PS3IntListListOpsTest.html applet. Although it is not required, you may find it helpful in some cases to define auxiliary methods.

Here are contracts and test case results for the four methods:

public static IntListList filterSorted(IntListList L)
Returns a list of all elements of L that are sorted lists.

Examples:

filterSorted([ ]) = [ ]
filterSorted([[ ]]) = [[ ]]
filterSorted([[ ], [1], [1, 2], [2, 1], [1, 2, 3], [1, 3, 2], 
             [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]) 
  = [[ ], [1], [1, 2], [1, 2, 3]]
filterSorted([[2, 1], [2, 3, 1], [3, 1, 4, 2], [ ], [1, 2, 3, 4], 
             [2, 1, 3], [1, 2, 3], [2, 1], [1]]) 
  = [[ ], [1, 2, 3, 4], [1, 2, 3], [1]]

 

public static IntListList mapPrepend(int i, IntListList L)
Returns a list the same length as L in which each element is the corresponding element of L with the integer i prepended in front.

Examples:

mapPrepend(5, [ ]) = [ ]
mapPrepend(6, [[ ]]) = [[6]]
mapPrepend(7, [[ ], [1], [1, 2], [2, 1], [1, 2, 3], [1, 3, 2], 
               [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]) 
  = [[7], [7, 1], [7, 1, 2], [7, 2, 1], [7, 1, 2, 3], [7, 1, 3, 2], 
     [7, 2, 1, 3], [7, 2, 3, 1], [7, 3, 1, 2], [7, 3, 2, 1]]
mapPrepend(8, [[2, 1], [2, 3, 1], [3, 1, 4, 2], [ ], [1, 2, 3, 4], 
               [2, 1, 3], [1, 2, 3], [2, 1], [1]]) 
  = [[8, 2, 1], [8, 2, 3, 1], [8, 3, 1, 4, 2], [8], [8, 1, 2, 3, 4], 
     [8, 2, 1, 3], [8, 1, 2, 3], [8, 2, 1], [8, 1]]

 

public static IntListList subsequences(IntList L)
Returns a list of all subsequences of L. A subsequence of L is a list that is obtained from L by deleting zero or more elements and maintaining the relative order of the undeleted elements. The order of components lists in the result returned by subsequences does not matter.

Examples:

subsequences([ ]) = [[ ]]
subsequences([1]) = [[ ], [1]]
subsequences([1, 2, 3]) 
  = [[ ], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
subsequences([3, 1, 4, 2]) 
  = [[ ], [2], [4], [4, 2], [1], [1, 2], [1, 4], [1, 4, 2], 
     [3], [3, 2], [3, 4], [3, 4, 2], [3, 1], [3, 1, 2], [3, 1, 4], [3, 1, 4, 2]]

 

public static IntListList longest(IntListList L)
Returns a list containing all the components that have the longest length in L

Examples:

longest([ ]) = [ ]
longest([[ ]]) = [[ ]]
longest([[ ], [1], [1, 2], [2, 1], [1, 2, 3], [1, 3, 2], 
         [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]) 
  = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
longest([[2, 1], [2, 3, 1], [3, 1, 4, 2], [ ], [1, 2, 3, 4], 
        [2, 1, 3], [1, 2, 3], [2, 1], [1]]) 
  = [[3, 1, 4, 2], [1, 2, 3, 4]]

Submission Details: Your hardcopy submission for this problem should be your final version of PS3IntListListOps.java. Your softcopy submission for all three problems should be your final version of the Lists folder.


Problem 3: Longest Sorted Subsequence

This problem nicely illustrates the power of expressing programs as the composition of mix-and-match parts that produce and consume aggregate data structures (in this case, lists).

A subsequence of a string of characters is a string that results by deleting zero or more characters, but maintaining the relative order of the undeleted characters. The longest sorted subsequences (LSS) of a string are the longest subsequences of the string whose characters appear in alphabetical order. For example, the longest sorted subsequences of "computer" are ["copu", "copt", "copr", "cmpu", "cmpt", "cmpr"], the longest sorted subsequences of "science" are ["cin", "cen", "cee", "cee"], and the longest sorted subsequences of "parameter" are ["aaeer"].

You can use the methods you developed in Problem 2 to define the LSS function. However, it is first necessary to establish a correspondence between strings integer lists. There is a standard encoding of characters as integers known as ASCII that maps the characters 'a' through 'z' to the integers 97 through 122, the characters 'A' through 'Z' to the integers 65 though 90, and other characters to other integers between 0 and 255. In Java, these encodings are performed as casts between the char type and the int type. For instance, (int) 'a' is 97 and (char) 65 is 'A'.

Based on the above encodings, it is easy to map a string into an integer list via the following method:

	public static IntList stringToIntList (String str) {
		IntList list = IntList.empty();
		for (int i = str.length() - 1; i >=0; i--) {
			// The (int) cast converts char to ASCII integer value.
			list = IntList.prepend((int) str.charAt(i), list);
		}
		return list;
	}

For example, stringToIntList("computer") yields [99, 111, 109, 112, 117, 116, 101, 114].

Similarly, we can convert from an integer list to string:

	public static String intListToString (IntList list) {
		if (IntList.isEmpty(list)) {
			return "";
		} else {
			// The (char) cast converts ASCII integer value to char.
			return ((char) IntList.head(list)) 
                         + intListToString(IntList.tail(list));
		}
	}
 

Finally, we can map intListToString over an IntListList to get a list of strings (represented as an element of the ObjectList class, in which each list head is an Object):

	
	public static ObjectList mapIntListToString (IntListList lists) {
		if (IntListList.isEmpty(lists)) {
			return ObjectList.empty();
		} else {
			return ObjectList.prepend(
                          intListToString(IntListList.head(lists)),
			        mapIntListToString(IntListList.tail(lists)));
		}
	}

Your goal in this problem is to define the following method:

public static ObjectList LSS (String s)
Returns a list of the longest common subsequences of the string s.

You should be able to define this method as a simple composition of methods from Problem 2 along with the stringToIntList method and mapIntListToString method from above. These latter two methods, along with a skeleton of LSS, can be found in the file LSS.java. You should flesh out the skeletons of the LSS method in this file to complete the problem. You can test your method by executing the LSS.html applet, which allows you to enter a string and compute its LSS.

Warning: this approach to computing the LSS of a string is very inefficient in both time and space. In particular, the subsequences method operating on a list of n integers produces a list of 2n integer lists; such a process is said to be exponential in time and space. 210 is about one thousand, 220 about one million, and 230 about one billion. Performing one million IntList.prepends on my laptop takes about two minutes; performing one billion would take two thousand minutes, which is over 33 hours. Since most integer lists produced by subsequences have multiple elements, two minutes greatly underestimates the time to perform subsequences on a list with 20 elements.

Even worse, each list node takes at least 3 bytes of memory, so storing the result of subsequences on a list with 20 elements would require tens of millions of bytes of storage. Since the Applet Viewer supplies less than one million bytes of storage by default, the result of subsequences won't even fit in memory for a list of 20 elements! (By the way, you can change the default amount of storage in the Applet Viewer by selecting the pull-down apple menu, selecting Java Runtime, and editing the Heap Min field.)

All this is just to say that you should test LSS on short strings (say, less than 10 characters), or your program may run out of memory. Unfortunately, the AppletViewer does not gracefully handle such situations. Instead, it crashes your machine, forcing you to reboot.

In just a few weeks, we will have much more to say about characterizing the time and space resources required by a computation.

Extra Credit: It is possible to redesign LSS so that input strings with 30 characters can be handled with modest time and space resources. The key idea is this: rather than producing all subsequences and then filtering them for the sorted ones and the longest ones, only generate sorted subsequences in the first place, and only keep those candidates that have a shot at being part of the longest. I will offer extra credit for a version of LSS that can handle an arbitrary string with 30 characters.

Submission Details: Your hardcopy submission for this problem should be your final version of LSS.java. Your softcopy submission for all three problems should be your final version of the Lists folder.