Practice problems 1

1. Consider the following function:

   scala> def test(m: Int, s: String) {
        |   val A = new Array[Int](3)
        |   val S = new Array[String](3)
        |   val m1 = m + 27
        |   A(0) = m - 1
        |   A(1) = m
        |   A(2) = m + 1
        |   for (i <- 0 until 3)
        |     S(i) = s + A(i)
        | }
   test: (m: Int,s: String)Unit
   

   Draw a picture of the heap and of the activation record (stack frame) of the method call test(13, "Hi ") at the time just before the function returns. Draw all objects on the heap referenced directly or indirectly from the activation record.

2. Consider the following code:

   scala> val A = Array(1, 2, 3, 4)
   A: Array[Int] = Array(1, 2, 3, 4)
   
   scala> val B = Array(1, 2, 3, 4)
   B: Array[Int] = Array(1, 2, 3, 4)
   
   scala> println(A == B)
   false
   
   scala> val C = A
   C: Array[Int] = Array(1, 2, 3, 4)
   
   scala> println(A == C)
   true
   

   Explain the output. What does the == operator do for two arrays?
3. Which of the following classes are immutable, and which are mutable? (Look carefully at their fields.)

   scala> class Class1(val x: Int, t: String) {
        |   val s: String = t
        | }
   defined class Class1
   
   scala> class Class2(val n: Int, m: Int) {
        |   val t = new Array[Int](m)
        | }
   defined class Class2
   
   scala> class Class3(var x: Int) {
        |   val y: Int = 17
        | }
   defined class Class3
   

4. Consider a chessboard of size \(2^{n} \times 2^{n}\). One piece of the chessboard has been removed. Prove that the rest of the chessboard can be tiled (covered without overlap) by L-shaped tiles consisting of three chessboard-squares.
5. Recall that a pure stack only supports the methods push, pop, top, and isEmpty.

   Write a function removeThird(A: Stack[Int]): Int that removes and returns the third-from-top element from the pure stack A. For example, if A contains

         23   <- top
         45
         56
         78
   

   then removeThird(A) returns 56 and leaves A in this state:

         23   <- top
         45
         78
   

6. Who is the Recursion Fairy?
7. Write a recursive Scala function reverse(s: String): String that returns the reverse of string s. For example, reverse("CS206") would return "602SC".
8. Write a recursive Scala function palindrome(s: String): Boolean that determines whether s is a palindrome (a string that is equal to its reverse). For example, palindrom("CS206") returns false, but palindrom("CS101SC") returns true.
9. The easy way to compute \(a^{n}\), where \(a\) is a Double and \(n\) is an integer, requires \(n-1\) multiplications. It is possible to compute powers with far fewer multiplications (and therefore runtime), using the following two formulas:
   If \(n\) is even, then
   \[ a^{n} = (a^{n/2})^{2} \]
   and if \(n\) is odd then
   \[ a^{n} = a (a^{(n-1)/2})^{2} \]
   Write a recursive Scala function exp(a: Double, n: Int): Double that computes \(a^{n}\) in this manner. Analyze the number of multiplications.
10. Consider the following Scala script recurse.scala:

    def display(L: List[Int]) {
      L match {
        case Nil => Thread.dumpStack()
        case x :: xs => print(x + " "); display(xs)
      }
    }
    
    val l = (1 to 5).toList
    display(l)
    

    When I run this script, an exception occurs, with the following error message:

    $ scala recurse.scala 
    1 2 3 4 5 java.lang.Exception: Stack trace
    	at java.lang.Thread.dumpStack(Thread.java:1266)
    	at Main$$anon$1.display(hw3.scala:4)
    	at Main$$anon$1.<init>(hw3.scala:10)
    	at Main$.main(hw3.scala:1)
    	at Main.main(hw3.scala)
    

    This surprised me, because it seems that the function display was called only once. I had expected it to look like this:

    $ scala recurse.scala 
    1 2 3 4 5 java.lang.Exception: Stack trace
    	at java.lang.Thread.dumpStack(Thread.java:1266)
    	at Main$$anon$1.display(hw3.scala:4)
    	at Main$$anon$1.display(hw3.scala:5)
    	at Main$$anon$1.display(hw3.scala:5)
    	at Main$$anon$1.display(hw3.scala:5)
    	at Main$$anon$1.display(hw3.scala:5)
    	at Main$$anon$1.display(hw3.scala:5)
    	at Main$$anon$1.<init>(hw3.scala:10)
    	at Main$.main(hw3.scala:1)
    	at Main.main(hw3.scala)
    

    Explain why I do not see this output, but the one above.
11. The following function find finds the first occurrence of x in a list L, and returns the suffix of the list starting with this element:

    def find(L: List[String], x: String): List[String] = {
      var p = L
      while (p != Nil && p.head != x)
        p = p.tail
      p
    }
    

    Write a new method findLast(L: List[String], x: String) that returns the list starting with the last occurrence of \(x\).