Assignment: Due: Language level: Allowed recursion: Files to submit: Warmup exercises: Practice exercises:
CS 135 Fall 2018 Becker, Clarke, Hackman, Jung, Lanctot, Nijjar, Reetz
9
Monday, December 3rd, 9:00 pm
Intermediate Student with Lambda
Any and all, see below
directed.rkt, fib.rkt, sequences.rkt, bonus.rkt HtDP 28.1.6, 28.2.1, 30.1.1, 31.3.1, 31.3.3, 31.3.6, 32.3.1 HtDP 28.1.4, 28.2.2, 28.2.3, 28.2.4, 31.3.7, 32.3.2, 32.3.3
• Make sure you read the OFFICIAL A09 post on Piazza for the answers to frequently asked questions.
• For this assignment, you have full access to all forms of recursion, all techniques learned this term, and all built-in functions and special forms in Intermediate Student with Lambda that have been covered in the course.
• Purposes and contracts are not required for lambdas or for locally defined helper functions, but purposes and contracts are required for globally defined helper funtions. You can use any purposes and contracts we provide, when we provide them. Examples and test cases are not required for globally defined helper functions, but are encouraged.
• Your solutions must be entirely your own work.
CS 135 — Fall 2018 Assignment 9 1
1. In Module 12 we provide an defintion of directed graphs using adjacency lists:
;; A Node is a Sym
;; A Graph is a (listof (list Node (listof Node)))
We also develop a function find-route that finds a route from an origin node to a destination node in a given directed graph, if one exists. In this question, we solve the related problem of determining if a given route provides a valid path from a origin node to a destination node.
Write a predicate valid-route? that takes a route and a directed graph as arguments and indicates if that route represents a path though the directed graph. Remember that a route must contain every node between the origin and the destination. Place your solution in directed.rkt.
(define a-graph
’((A (C D E)) (B (E J)) (C ()) (D (F J))
(E (K)) (F (K H)) (H ()) (J (H)) (K ())))
(check-expect (valid-route? ’(A D J H) a-graph) true)
(check-expect (valid-route? ’(A B C) a-graph) false)
(check-expect (valid-route? ’(A B C) empty) false)
(check-expect (valid-route? empty a-graph) true)
(check-expect (valid-route? empty empty) true)
(check-expect (valid-route? ’(X Y Z) a-graph) false)
2. Fibonacci numbers are defined by the following recursive equations:
fibonacci(0) = 0,
fibonacci(1) = 1, and
fibonacci( i ) = fibonacci(i − 1) + fibonacci(i − 2), where i > 1.
It’s easy to translate this formula directly into Racket:
(define (fib i) (cond [(= i 0) 0] [(= i 1) 1]
[else (+ (fib (- i 1)) (fib (- i 2)))]))
Sadly, this function runs very very slowly; (fib 42) can take over a minute on a typical laptop. Write a function fast-fib that computes Fibonacci numbers for larger values; (fast-fib 10000)shouldtakenomorethanafewsecondsonatypicallaptop.Placeyour solution in fib.rkt.
Hint: Think about how you would compute Fibonacci numbers on a piece of paper. We suggest a helper function that counts up and takes the previous two values as arguments.
(check-expect (fast-fib 1) 1)
(check-expect (fast-fib 6) 8)
(check-expect (fast-fib 42) 267914296) (check-expect (fast-fib 101) 573147844013817084101)
CS 135 — Fall 2018 Assignment 9 2
3. Number sequence tests can provide a psychometric assessment of an individual’s numerical reasoning ability. For example, in the following sequences, what’s the next number?
• 2,4,6,8,10,12,? • 1,-2,3,-4,5,-6,? • 3,5,9,17,33,65,? • 1,1,2,3,5,8,?
But since this is CS135, we don’t want you to solve such problems yourself. We want you to write a Racket function to solve them.
For each of these problems, there will be a partially known integer sequence n0,n1,n2,…ni,…
where ni = f (i) for some unknown function f (i). Given the first few numbers in the sequence, typically 5 or 6 of them, we want you to guess the function f (i). Since there might be more than one function that generates the first few numbers, we will provide some guidance along the way. Place your solutions in sequences.rkt.
(a) Let’s start by checking if a proposed solution, assuming we have one, is actually correct. Write a predicate solution? as follows:
;; (solution? f lon) checks that f generates the values in
-
;; the list of integers lon, where f takes a
-
;; the list as an argument, starting at 0. ;; solution?: (Nat -> Int) (listof Int) -> Bool(check-expect
(solution? (lambda (i) (* 2 (+ i 1))) (list 2 true)(check-expect (solution? (lambda (i) i) (list 0 (check-expect (solution? (lambda (i) i) (list 1 (check-expect (solution? (lambda (i) i) empty) true)
We suggest you use build-list to answer this part, solely because we’ll be testing it on the final, and it’s good to get some practice.
(b) Now let’s guess that the solution for a given list might be a quadratic polynomial of the form f (i) = ai2 + bi + c and produce a function to generate this solution. For this type of guess, if you’re given a list with exactly three numbers there will be exactly one possible solution. If you’re given a list with more than three numbers, you can ignore all but the first three numbers for the purposes of generating the guess. We will check the guess in part c. If you’re given a list with less than three numbers, just generate any of the possible solutions; you won’t be wrong. If you’re given an empty list, guess
f (i) = 0. Write a function guess-quadratic, as follows:
CS 135 — Fall 2018 Assignment 9 3
position in
4 6 8 10 12))
1 2 3 4 5)) true) 2 3 4 5 6)) false)
;; (guess-quadratic lon) guesses that the number sequence lon has a ;; quadratic solution and produces the guess.
;; guess-quadratic: (listof Int) -> (Nat -> Int)
(define test-a (list 2 4 6 8 10 12))
(check-expect (solution? (guess-quadratic test-a) test-a) true) (define test-b (list 1 11 33 67 113))
(check-expect (solution? (guess-quadratic test-b) test-b) true) (define test-c (list 2 4 8 16 32 64))
(check-expect (solution? (guess-quadratic test-c) test-c) false)
(c) Using the function solution? from part a) and the function guess-quadratic from part b) as helpers, write a function try-quadratic, which guesses that the solution might be quadratic and if so returns the solution. If not, it should return the empty list, so that we know to try solutions based on other patterns.
;; (try-quadratic lon) tries solving the number sequence lon with
- ;; a quadratic. It produces the solution if it works and empty
- ;; if it doesn’t.
;; try-quadratic: (listof Int) -> (anyof (Nat -> Int) empty)(check-expect ((try-quadratic test-a) 6) 14) (check-expect ((try-quadratic test-a) 1000000) 2000002) (check-expect ((try-quadratic test-b) 5) 171) (check-expect (try-quadratic test-c) empty)
(d) Repeat step b) and c) above for a recursive pattern of the form
f(0)=n0, f(1)=n1, and
f(i) = ani−1 +bni−2,where i > 1.
Write functions called guess-recursive and try-recursive. Don’t forget to write purposes and contracts for these functions. While our test cases will generally use lists with length greater than 3, you still need to do something reasonable with shorter lists, like you did in part b). Like guess-quadratic, the function guess-recursive should always return a function, which will then be checked by try-recursive. Be very very careful to avoid division by zero.
(define test-d (list 1 1 2 3 5 8 13))
(check-expect ((try-recursive test-d) 7) 21)
(check-expect ((try-recursive test-d) 100) 573147844013817084101) (define test-e (list 0 1 1 2 3 5 8))
(check-expect ((try-recursive test-e) 7) 13)
(define test-f (list 1 1 3 5 11 21 43))
(check-expect ((try-recursive test-f) 7) 85)
(define test-g (list 2 0 0 0 0 0))
(check-expect ((try-recursive test-g) 0) 2)
(check-expect ((try-recursive test-g) 100) 0)
(check-expect (try-recursive test-b) empty)CS 135 — Fall 2018 Assignment 9 4
(e) Finally, write a function solve that tries both the quadratic and recursive patterns, in that order, and returns a solution, if one exists. Otherwise, return the empty list. Don’t forget to write a purpose and contract for this function. If you try the bonus, you’ll be adding more try- functions. Consider using a list to make adding them easy.
(check-expect ((solve test-a) 6) 14)
(check-expect ((solve test-a) 1000000) 2000002) (check-expect ((solve test-b) 5) 171)
(check-expect ((solve test-c) 8) 512)
(check-expect ((solve test-d) 7) 21)
(check-expect ((solve test-d) 100) 573147844013817084101) (check-expect ((solve test-e) 7) 13)
(check-expect ((solve test-f) 7) 85)
(check-expect ((solve test-g) 0) 2)
(check-expect ((solve test-g) 100) 0)
(check-expect (solve ’(1 1 2 1 2 3 1 2 3 4)) empty)
Of course we could try other patterns, but we’ll leave that for the bonus…
This concludes the list of questions for which you need to submit solutions. Do not forget to always check your email for the basic test results after making a submission.
4. Bonus of up to 100% or more: Extend your numerical sequence solver to solve sequences of integers with other patterns. Whatever you can think up. Have fun.
Call this function supersolve and submit it in the file bonus.rkt. You may reuse code from your submitted sequences.rkt file, but that code must be included in bonus.rkt.
We have hidden 10 test cases, which are similar to number sequence tests intended to test humans. For these test cases, you will get no feedback of any sort until after the submission deadline. For each test case solved by your function, you will receive a 10% bonus on your grade for this assignment.
Since these test cases are similar to those intended to be solved by humans, you can assume that any constants will be relatively small and that any mathematics will be at the first-year university level or below. For these hidden test cases, we will also not ask for values of f (i) where i is greater than 12, again because a human would not be expected to solve such problems. For each test case, we will give your function one minute to solve it. After one minute, we may stop your program at any time.
If your submission solves a test case that no other submission solves, across all sections, you will receive a further bonus of 10% on your overall course grade. Note that your final course grade cannot exceed 100% and that your weighted exam average must still be 50% or greater for you to pass the course.
We strongly recommend that you avoid this bonus question until you have completed the rest of the assignment. Your solver should handle the basic (non-bonus) patterns before you try new ones.
CS 135 — Fall 2018 Assignment 9 5