►Fundamentals I
▼Problem Sets
    ← prev  up  next → 

Problem Set 11h

This is the honors version of Problem Set 11.

image

home work!

Programming Language ISL+

Purpose This problem set (primarily) concerns the design of accumulator-style functions.

image

Problem 1
; posn-sum : [Listof Posn] -> Posn
; Compute a posn whose x coordinate is the sum of the x coordinates in ps
; and whose y coordinates is the sum of the y coordinates in ps
(define (posn-sum ps) ...)

Problem 2
; A Digit is a Number in the range [0-9]
; digits->num : [Listof Digit] -> Number
; Compute the number represented by the list of digits
(define (digits->num ds) ...)
 
; Examples:
(digits->num (list 1 2 3))  -->  123
(digits->num empty) ---> 0

Problem 3 A palindrome is a word, number or phrase that reads the same forward and backward.

  1. Design the function make-palindrome, which consumes a non-empty String and constructs a palindrome by mirroring the String around the last letter. For example, (make-palindrome "fundies") should produce "fundieseidnuf".

  2. Design the function is-palindrome?, which consumes a non-empty String and determines whether the String is a palindrome or not.

Problem 4 A number, n>1, is prime if it is not divisible by any numbers besides 1 and itself, such as 2, 3, 5 and 7.

  1. Design the function prime? which consumes a Natural Number, n and returns true if it is prime and false otherwise. Use the fact that if n is not prime, one if its factors must be less than or equal to the square root of n.

  2. Design the function list-primes which consumes a Natural Number, n, and produces the list of prime numbers up to n.

Problem 5 The Fibonacci numbers, which are the numbers in the following sequence: 0 ,1 ,1 ,2 ,3 ,5 ,8 ,13 ,21 ,34 ,55 ,89 ,144 ,... are defined by the recurrence relation: Fn = Fn-1 + Fn-2, with seed values F0 = 0 and F1 = 1.

  1. Design the function fibonacci, (without accumulators) which consumes a Natural Number and produces its Fibonacci number. For example, (fibonacci 11) should produce 89.

  2. Use accumulators to design a more efficient version of fibonacci.

  3.  Design a function, list-fibonacci, that consumes a Natural Number and produces the list of Fibonacci numbers from F0 to Fn.

Problem 6 Many card games are structured around the taking of tricks, a set of four cards where one card is contributed from each player. Examples of trick-taking games include hearts, bridge and whist.

  1. Define a function that takes a trick and returns the winning player according to the following rules:

    • High card wins

    • In the case of a tie i.e. two or more cards of the same value are played the trick goes to the player with the better suit. (Clubs < Diamonds < Hearts < Spades)

    Note that the problem is purposely left ambiguous in terms of data definitions and requirements. It is up to you to decide how to implement this problem. There is not one right answer, but some answers are better and simpler than others. Make sure to follow the design recipe.

  2. A game is a series of tricks. Design a function that takes a game and returns a winner. The winner is the person who won the most tricks overall.

Problem 7 Twitter is a social networking service that allows users to write messages called tweets that are up to 140 characters.

  1. Design a data definition for a network of Twitter users. A Twitter user should have a handle (or name) and tweeps (or followers).

    Create an example of a network of five or more users.

  2. Design a function, list-handles, that consumes a network and produces a list of all of the handles in the network. You must use an accumulator.

  3. Design a function, most-followers, that consumes a network and produces the handle in the network that has the most followers. You must use an accumulator.

  4. Design a function, friends?, that consumes a network and two handles and determines whether it contains two users who follow each other.

    ← prev  up  next →