Homework 2

The purpose of this homework is to practice recursion. You cannot use any mutation—no var, no arrays, no Java collections, no mutable Scala collections. That makes while loops pretty useless, so don't even try that. Also, no use of any library function other than String.length, String.contains, String.substring, String.replace, except in the third problem, where you are allowed one call to List.map.

Again, the one and only point is to practice recursion. We don't care about implementing these functions any other way, and there will be no partial credit for any submission that uses any forbidden construct.

1. Write a Scala function

   def subs(s: String) : String

   that yields all “subset strings” of a given string, obtained by a subset of the letters in the same order. For example, the subset strings of "Amy" are:

   ""
   "A"
   "m"
   "y"
   "Am"
   "Ay"
   "my"
   "Amy"
   

   Note that "Ay" is a subset string but not a substring. The order matters—"ym" is not a subset string. If the original string has length n, there are 2ⁿ subset strings. Return a string that concatenates all of the subset strings, separated by |. You can produce them in any order. One acceptable answer for subs("Amy") is

   "|A|m|Am|y|Ay|my|Amy"

2. Write a Scala function

   lcs(a: String, b: String) : String
   

   that produces the longest substring (in the normal meaning, not that of the preceding exercise) that is common to both a and b. For example, lcs("permission", "cruise missile") is "missi". If there are multiple common substrings of the same maximal length, you can produce any one of them. Don't use dynamic programming. Simply call the contains method with suitable substrings of decreasing length. However, don't be too wasteful—your implementation must run in O(n³) time, where n is max(a.length(), b.length()). Hint: If b.contains(a), you have the answer. If not, you can try shorter substrings of a. Either the substring contains the initial letter of a—there are O(n) such substrings that you can handle with a helper function. Or you can solve the original problem with simpler inputs.
3. Write a scala function

   onebits(n: Int) : List[Int]

   that returns a list of positions where the binary representation of n has a bit of 1. For example, onebits(13) is List(0, 2, 3) because in binary, 13 is 1101, and the powers 2⁰, 2², and 2³ have coefficients of 1. Don't use a library function that converts n to a binary/octal/hex string. Hint: How can you compute onebits(n) from onebits(n / 2)? Use map!

You turn in three files in the hw2 subdirectory of your repo:

• hw2.scala:

  object hw2 {
    def subs(s: String) : String = 
      ...  
    def lcs(a: String, b: String) : String = 
      ...
    def onebits(n: Int) : List[Int] =
      ...
  }

• hw2test.scala:

  object hw2test extends App {
    println(hw2.lcs("Mary had a little lamb", "Its fleece was white as snow"))
    // your other test cases
  }
  

• hw2.txt: Explain in plain English for each of your solutions how/why the recursion works. Why does it terminate? Why does it give the right answer?

If you want to test what the grader will do (always a good idea), you need to first install sbt. Then run

cd /tmp
echo hw2 | sbt new sbt/scala-seed.g8
cd hw2
cp ~/cs152/hw2/*.scala src/main/scala # (substitute your git repo root for ~/cs152)
sbt run

You should see the print statements from your hw2test object. The grader will add his own test objects.