1. Binary Trees

A friend missed class this past Monday and is completely clueless when it comes to binary trees. They managed to start the data definitions but got frustrated and gave up. Help them out!

;;  A SBT (String Binary Tree) is one of
;; - (make-leaf)
;; - (make-node String SBT SBT)

(define-struct leaf ())
;; A Leaf is a (make-leaf)
;; INTERP: represents a leaf in a binary Tree

(define-struct node (val left right))
;; A Node is (make-node String SBT SBT)
;; INTERP: Represents a node in a SBT that has exactly 2 children.
Practise Exercises

  • 1) Write a deconstructor template for String Binary Tree (SBT)

  • 2) Create some data examples of SBTs

  • 3) Design a function called sbt-count that given a string binary tree returns the number of nodes in the tree

  • 4) Design a function called sbt-append that given a SBT returns one string that is the result of appending each node in the SBT (any order of appending nodes is ok)

  • 5) Design a function called sbt-contains? that given an SBT and a string returns true if the string exists within the binary tree and false otherwise

2. List of List of Strings

You have another friend who actually attended class on Monday but spent the entire time on Facebook looking at their crush’s profile pictures from 2010. They need help with Lists of Strings. Use the following data definitions:

;; A List of Strings (LoS) is one
;; - empty
;; - (cons String LoS)
;; INTERP: represents a list of strings

;; Template
;; los-fn: LoS -> ???
#;(define (los-fn los)
    (cond
      [(empty? los) ...]
      [(cons? los) ... (first los) ...
                   ... (los-fn (rest los)) ...]))
Practise Exercises

  • 6) Create a data definition for a List of List of Strings (LLoS)

  • 7) Design a function called llos-sizes that given an LLoS returns a list that contains the number of all characters in each LoS ex. (sizes (list (list "a" "aa") (list "a") empty)) returns (list 3 1 0)

  • 8) Design a function called llos-contains? that given an LLoS and a string returns true if the string exists within any of the lists in the LLoS and false otherwise

3. Playing with Big Bang

You are now at your 3rd job in 1 year (how fickle you are!). And once again, you are working on developing a game. Because you have so much work experience, your superiors have decided to put you in charge of moving a square around a screen! How exciting! You are given the following data definitions:

(require 2htdp/image)
(require 2htdp/universe)

(define-struct world (pin square-side))
;; A World is (make-world Posn NonNegInteger)
;; INTERP: represents the pin (location) of the center of the square and
;;         the side of the square to draw

(define BACKGROUND (empty-scene 500 500))
(define INIT-WORLD (make-world (make-posn 250 250) 50))
Practise Exercises

  • 9) Design a function called draw-world that given a world, will draw the square at the pin on the canvas. It is up to you to decide what the color and mode of the square will be

  • 10) Design a function called move-left that given a world, will return a new world were the pin has shifted to the left by 10

  • 11) Design the functions move-right, move-up, and move-down that moves the pin to the right, up, and down by 10 units respectively

Now, your team shares with you that they are very indecisive and the speed at which the square moves is probably going to change a couple times.

Practise Exercises

  • 12) Create a constant for speed and use it in your functions so that the square move these many units

You are given the following code to test out your functions:

(big-bang INIT-WORLD
          (on-tick move-left 0.1)
          (to-draw draw-world))
Practise Exercises

  • 13) Using the code above, run your program. Switch the move- function in big-bang for on-tick and observe the effects.

  • 14) Extend your program to allow for any number of squares on the screen that all move in the same direction and by the same amount.