Sample Midterm Problems

Date: Tuesday 10/22

Time: 6pm-8pm

Location: Northrup Hall (NH) 214 and 216

These problems are not the distribution of what will be on the midterm, but should give you a good idea of what kinds of questions are on the exam, and good sample for the more difficult problems.

You can also look at the in-class activities for sample problems.

• 1. Define subList :: Eq a => [a] -> [a] -> Bool, which checks if one list is a sublist of another. subList lst’ lst should return True if every element of lst’ occurs in lst. Order and duplicates do not matter: [3,2,2] is a sublist of [1,2,3] even though the order is different and 2 appears twice in the first list.

(a) Define subList using recursion.

(b) Define subList using higher-order functions.

• 2. The following function uses an auxiliary function to test if a number is prime. The aux function takes a list of possible divisors and checks each one in turn. If none of the divisors are valid, it returns true.

isPrime :: Integer -> Bool
isPrime n =
      let aux [] = True
          aux (x:xs) = (n `mod` x /= 0) && (aux xs)
      in aux [2..(n-1)]

Write a version of isPrime that uses higher-order functions instead of recursion. You do not have to use a helper function, but if you do make sure your helper function is not recursive. You may use multiple higher-order functions.

• 3. Write splitOnParity :: [Int] -> ([Int], [Int]) that takes a list  and returns a tuple of two lists, the first containing all even numbers, and the second all odd numbers.

(a) Define splitOnParity using recursion.

(b) Define splitOnParity using two filters.

(c) Define splitOnParity using one fold.

• 4. Define sumValues :: [(a, Int)] -> Int that takes an association list where the values are integers, and returns the sum of the values. 

(a) Define sumValues using a list comprehension.

(b) Define sumValues using higher-order functions.

• 5. Define bestKey :: [(a, Int)] -> a that takes an association list where the values are integers, and returns the key with the maximum value. 

(a) Define bestKey using recursion.

(b) Define bestKey using higher-order functions.

• 6. Write a function mostCommonElement :: Eq a => [a] -> a that takes a list and returns the most common element.
     
     

  7. (a) Define a higher-order function exists :: (a -> Bool) -> [a] -> Bool that takes a predicate, a list, and returns True if the predicate is true for anything in the list.

(b) Using exists, define zeroDetector :: [Int] -> Bool to check if there is a zero in a list.

(c) Using exists, define isPrime :: Int -> Bool that takes an integer and returns True if it is prime (i.e. not evenly divisible by any number other than 1 and itself).

• 8. (a) Write a higher order function bucket :: Eq b => (a -> b) -> [b] -> [a] -> [[a]]
     Where bucket f labels xs groups the elements of xs based on which elements of buckets they map to.
     For instance: buckets (`mod` 3) [0,1,2] [6..10] = [[6,9],[7,10],[8]]
     Groups the numbers for 6 to 10 based on their remainder when divided by 3. The first list  ([6,9]) contains those with remainder 0, the list [7,10] remainder 1, and [8] remainder 2. 

(b) The function radix :: Int -> Int -> Int takes an exponent a number, and returns the digit of that number in that exponent's place. For instance, radix 3 1972 returns 9, while radix 1 1972 returns 2.

radix 1 n = n `mod` 10
radix k n = radix (k-1) (n `div` 10)

Using radix and buckets write the following three functions

• 8. • • radixHundreds :: [Int] -> [[Int]] that takes a list of integers and groups them by their hundreds digit.

       • radixTens :: [Int] -> [[Int]] that takes a list of integers and groups them by their tens digit.

       • radixOnes :: [Int] -> [[Int]] that takes a list of integers and groups them by their ones digit.

(c) Using the above functions, concat, and map, write a linear-time sorting algorithm for integers of 3 digits or less.

radixSort :: [Int] -> [Int]

• 9. Without using list comprehensions with multiple generators, write crossProduct :: [a] -> [b] -> [(a,b)] that takes two lists and returns their cross product.
     For instance, crossProduct [1,2] "ABC" = [(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C')]
     
     

  10. For this problem, we consider lists that represent sets. Thus order does not matter, and you may assume there are no repeated elements. You may not use the powerset function, even if you implement it yourself. We use the subset relation from Problem 1: a list lst’ is a subset of lst if every element of lst’ occurs in lst. Thus [2,3] is a subset of [9,3,2], even though the elements are out of order. The subset sum problem is, given a list of unique integers lst and a target value n, does there exist a subset of lst whose elements sum to value.
      
      Define a function subsetSum:: Integer -> [Integer] -> Bool that checks if a subset of the list exists that sums to the integer. For example,
      subsetSum 4 [1,5,-6,10] is True, while subsetSum 8 [1,5,-6,10] is False.