# 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 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$$anon1.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 Main$$anon1.display(hw3.scala:4) at Main$$anon$1.display(hw3.scala:5) at Main$$anon1.display(hw3.scala:5) at Main$$anon$1.display(hw3.scala:5)
at Main$$anon1.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$$.