Here are sample problems for the final.
The radix and crossProduct problems on the midterm sample problems are also appropriate for the final.
Write a function middle :: Ord a => [a] -> a that takes a list of ordered types, and returns "middle" element: the one that has an equal number of larger and smaller elements. If there is no precisely middle element (because the list is of even length), you may return either of the two elements closest to the middle. You may use built-in functions. For instance:
middle [7,3,1,9,5] = 5
middle "flamingo" = 'l'
middle [1,2,3,4] = 2 //3 is also acceptable.
Note: this would not be a a good question for the final, because it is very easy using built-in functions and very hard using recursion.
Write an IO action getPassword :: IO (Maybe String) that prompts a user to enter a password, asks them to confirm the password, and returns that string if the two entries are equal. If they are not equal return Nothing.
Using either do blocks or case expressions, write a function
quadruple :: (Maybe a) -> (Maybe b) -> (Maybe c) -> (Maybe d) -> Maybe (a,b,c,d)
that takes 4 Maybe values. If any of them are Nothing, return nothing. Otherwise make a quadruple (4-tuple) of the values.
Note: this would not be a good question for the final, because it uses "do" blocks for Maybes.
Write a higher-order function myPartition :: Ord a => (a -> Bool) -> [a] -> ([a], [a]) that takes a Boolean predicate, a list of elements, and returns the tuple of two lists: the first containing all elements that make the predicate True, and the second all the elements that make the predicate False. For example:
myPartition isDigit "h3110, 1 @m l337 h4ck3r" = ("31101133743", "h, @m hckr")
A node-valued binary search tree is a tree where nodes carry values, that obeys the invariant that for a node with value x, all values in the left child are less than x, and all values in the right child are greater than x.
data BST a = Node (BST a) a (BST a) | Leaf deriving Show
We say a binary search tree is balanced when, for every node, the number of left children is within 1 of the number of right children. Using middle, myPartition, delete, null, and non-structural recursion, write
buildBalancedTree :: Ord a => [a] -> BST a that creates a balanced binary search tree from a (finite) list of elements. You may assume there are no duplicate elements. You may not pattern match on lists for this problem.
Recall that null :: [a] -> Bool takes a list and returns True if the list is empty.
Recall that delete :: Eq a => a -> [a] -> [a] takes an element and a list, and removes the first occurrence of the element from the list.
Note: This is also an bad question for the final, as it incorporates BST's (which we didn't cover) and has awkward restrictions on recursion.
Decompose this problem into logically coherent subproblems, and describe how to solve the problem using the subproblems.
The problem is to write kMeans, which takes an integer k, a list of points, and returns a list of k clusters. A cluster is a center, which may not be an original point, and a list of points associated with the center. The list of clusters must: (a) contain all original points, (b) associate each point with the nearest center, and (c) have the center be in the middle of it's associated points.
You are given these type signatures
type Point = (Int, Int)
type Cluster = (Point, [Point])
And a distance function
dist :: Point -> Point -> Double
The algorithm to implement is:
Start with n points.
Take k points as starting centers.
Assign each point to its nearest center, forming the initial clusters.
Repeatedly improve the clusters by:
Update each center to be the mean of its cluster.
Assign each point to the nearest updated center
The algorithm terminates when the clusters stop changing.
(a) Write a function to solve this problem, using at least 4 helper functions that solve logical sub-problems. You do not need to define the helper functions.
kMeans:: Int -> [Point] -> [Cluster]
(b) For each helper function, provide it’s type and a brief (1-2 sentence) description of what it does. Do not describe how the function works, but rather what the output is. Think of the comments above each function in the project.