Use It or Lose It

Here are some problems to practice the “Use It or Lose It” strategy.

subset-sum

Given a target sum and a list of integers, write a function subset-sum that returns true if some subset of the numbers can be summed up to the target. Otherwise, the function should return false. Note that each number in the list can be used at most once.

Here are some example test cases for subset-sum:

(check-true (subset-sum 0 '(1 2 3)))

(check-true (subset-sum 0 '()))

(check-true (subset-sum 1 '(1 2 3)))

(check-true (subset-sum 2 '(1 2 3)))

(check-true (subset-sum 3 '(1 2 3)))

(check-true (subset-sum 4 '(1 2 3)))

(check-true (subset-sum 5 '(1 2 3)))

(check-true (subset-sum 6 '(1 2 3)))

(check-false (subset-sum 7 '(1 2 3)))

(check-true (subset-sum 0 '(1 2 3)))

(check-true (subset-sum 0 '(1 2 3 0)))

Maximal, nonconsecutive values

Given a list of positive integers, write a function mnv that computes the maximum number that can be reached by adding up numbers that are non-adjacent in the list.

Here are some example test cases for mnv:

(check-equal? (mnv '()) 0)

(check-equal? (mnv '(1)) 1)

(check-equal? (mnv '(1 10)) 10)

(check-equal? (mnv '(10 1)) 10)

(check-equal? (mnv '(10 3 5 15 4)) 25)

(check-equal? (mnv '(10 15 3 5 8)) 23)

(check-equal? (mnv '(10 15 3 5 11)) 26)

The built-in Racket function max may be helpful. It may also be useful to write a helper function that can safely get the second element of a list, even if the list has fewer than two elements (in which case, it should return the empty list).

Solutions

Here are sample solutions to these two problems.

Trees

To work on this part, first take a look at the assignment, read the portion about “Interface vs Implementation”, then download the tree library.

height

Write a function

(define (height tree) … )

which takes an argument that is a tree and returns the height of that tree. Remember that the height of an empty tree is -1.

find-min

Write a function

(define (find-min bst) … )

that takes a non-empty binary search tree (bst) as an argument and returns the smallest value in the tree.

Solutions

Here are sample solutions to these two problems.

Analysis

filter

Here is an implementation of filter, using recursion:

(define (filter f L)

(cond [(empty? L) '()]

[(f (first L)) (cons (first L) (filter f (rest L)))]

[else (filter f (rest L))]))

If we define the input size to be the length of the list L and the cost metric to be the number of calls to filter, what is the recurrence relation for filter? Unroll the recurrence relation, find a pattern to the unrolling and use it to construct a closed-form version of the cost. Give the Big-O version of the cost.

Sample solution

Here is a sample solution, using a format that you can follow for the assignment.