CSC 233: Foundations of Computation, Fall 2011

Assignments

Friday, September 2:

Complete the following Scala exercises, which we will start in class. Upload a file (.scala or .kojo) to Moodle containing your solutions.

1. Complete the following skeleton to define a function that adds up a list of Ints:

   def total(nums: List[Int]): Int = nums match {
     case Nil =>
     case head :: tail =>
   }

2. Write a function doubleAll that takes a list of Ints and returns a list where each item has been doubled. For example, doubleAll(3 :: 1 :: 4 :: 1 :: Nil) should return 6 :: 2 :: 8 :: 2 :: Nil (which may also be written List(6, 2, 8, 2)).
3. Write a function named filterOdd that takes a list of Ints and returns a list of only the odd items from the list. For example, filterOdd(List(3, 1, 4, 1, 6)) should return List(3, 1, 1).
4. Write a function with signature isLowerBound(n: Int, nums: List[Int]): Bool that returns true if n is less than or equal to all of the numbers in nums. For example, isLowerBound(1, List(3, 1, 4)) should return true, while isLowerBound(2, List(3, 1, 4)) should return false.
5. Write a function with signature splitMin(nums: List[Int]): (Int, List[Int]) that returns a pair consisting of the smallest item from nums and a list of all of the remaining values from nums. For example, splitMin(List(3, 1, 4, 1, 6)) might return (1, List(3, 4, 1, 6)). You may assume that nums is non-empty; if splitMin is called on an empty list, you may call the error function to throw an exception: error("splitMin of an empty list").
6. Use the splitMin function to write a selection sort: selSort(List(3, 1, 4, 1, 6)) should return List(1, 1, 3, 4, 6).
7. Write a function with signature insert(n: Int, nums: List[Int]): List[Int] that returns the list nums with n inserted into the correct sorted position (assuming nums was sorted). For example, insert(3, List(1, 4, 6)) should return List(1, 3, 4, 6).
8. Use the insert function to write an insertion sort.
9. Write a "higher-order" function (that is, a function that takes another function as an argument) with signature applyAll(nums: List[Int], fun: Int => Int): List[Int] that returns a list where each of the items from nums has had fun applied to it. For example, given def double(n: Int): Int = 2 * n, the call applyAll(nums, double) should return the same as doubleAll(nums).
10. Write a higher-order function with signature filterPred(nums: List[Int], pred: Int => Bool): List[Int] that returns a list of only those items from nums for which pred (the "predicate") returns true. For example, given def odd(n: Int): Bool = n % 2 == 1, the call filterPred(nums, odd) should return the same as filterOdd(nums).

Wednesday, September 14:

Complete the five exercises at the end of Command2.kojo, then upload your resulting .kojo file. Be sure that the tests pass for the first two exercises (and consider writing additional tests yourself).

Friday, September 23:

Do the following exercises in class:

1. Consider the following Scala code:

   sealed trait Tree
   case object Leaf extends Tree
   case class Node(left: Tree, n: Int, right: Tree) extends Tree
   
   def insert(x: Int, t: Tree): Tree = t match {
     case Leaf => Node(Leaf, x, Leaf)
     case Node(left, n, right) =>
       if (x > n)
         Node(insert(x, left), n, right)
       else
         Node(left, n, insert(x, right))  
   }
   
   def buildTree(nums: List[Int]): Tree = nums match {
     case Nil => Leaf
     case head :: tail => insert(head, buildTree(tail))
   }
   

   1. Write a function size(t: Tree): Int that returns the number of nodes in a tree (do not count the leaves).
   2. Given a tree t such that size(t) is N, how many leaves does it have? Prove your answer by induction.
   3. What is the average Big-Oh running time of buildTree(nums), in terms of the length of nums
   ?
   4. State an invariant that holds between the values in each node of a tree returned by buildTree.
   5. Write a function inOrder(t: Tree): List[Int] that returns the values from t according to an inorder traversal.
   6. What is the Big-Oh running time of inOrder(t), in terms of the size of t?
   7. What is the result of inOrder(buildTree(nums)), and what is its average running time in terms of the length of nums?
2. [To be continued...]

Friday, November 4:

Turn in Exercises 9.6.1-4, 9.8.3, and 9.9.4 (which should already be done), plus 9.7.4, 9.8.2, and 9.9.2

Monday, November 21:

Do the following exercises from the text (to hand in):
10.2.6, 10.3.3, 10.4.1, 10.4.2, 10.5.2, 10.5.7, and 10.8.1-5

DePauw University, Computer Science Department, Fall 2011
Maintained by Brian Howard (bhoward@depauw.edu). Last updated