In this module we introduce the notions of abstraction and accumulators. First we show how recursive functions can be rewritten to maintain information during each recursive call using accumulators. Second we upgrade to the Intermediate Student Language which allows functions as values. We then show how functions can consume/produce other functions allowing for more abstract, and more elegant, designs.

  1. Given a function that uses mutual recursion, convert it to use accumulators.
  2. Document accumulator arguments by writing an invariant.
  3. Write a function definition that is local in scope to another function.
  4. Given a set of Scheme functions that contain duplicative code, write the abstracted function.
  5. Given a data definition for tree structured data, write a template.
  6. Given a specification for information represented as a tree, write a data definition that maps the information into Scheme data.
  7. Recognize patterns for built-in abstract functions.
  8. Write the contracts for the built-in abstract functions.
  9. Given abstract functions, use Higher Order Function Composition to define a new function.
  10. Given a function that uses structural decomposition, convert it into a function that uses Higher Order Function Composition.
  11. Given a signature that takes other functions as arguments, write down valid inputs for the signature.
  12. Given a recursive data definition, write a fold function.
  13. Recognize patterns for built-in abstract functions.
  14. Write the contracts for the built-in abstract functions.
  15. Given abstract functions, use Higher Order Function Composition to define a new function.
  16. Given a signature that takes other functions as arguments, write down valid inputs for the signature.
  17. Given a function that uses structural decomposition, convert it into a function that uses Higher Order Function Composition.
  18. Given a recursive data definition, write a fold function.
  19. Write an anonymous function using the keyword lambda.
  20. Write a call to an anonymous function with the appropriate number of inputs.
  21. Given a Scheme expression, write down the sequence of steps taken during evaluation.
  22. Use the syntactical conventions for function definitions.
  23. Given a Scheme function, identify the strategy used.
  • DUE DATE: Tuesday March 22nd at 12:00pm (NOON)

Missile Defence

We are going to develop a version of the game called "Missile Defence". Visually the game consists of:

  • A set of missiles.
  • A set of bullets.
  • A defender.
  • A numerical value that represents the defender's health.
  • A numerical value that represents the defender's score.

The game starts with

  • the defender's current score displayed in the top left corner of the scene,
  • the defender's current health in the top right corner of the scene,
  • a random number of missiles falling from the top of our scene in a straight line downwards to the bottom at a steady speed,
  • the defender at the bottom, center, of the scene starting to move towards the left of the scene.
A defender starts the game with health equal to 5 units and a score equal to 0. As the game progresses we have missiles appearing at the top of the scene at random locations moving at a steady speed downwards. The number of missiles that appear at each tick on the scene is left up to you. Make sure you select a comfortable number of missiles to appear on each tick to make the game interesting to play.

The defender is controlled by the user and can move in all four directions, i.e,

  • up
  • down
  • left
  • right

The defender's speed is constant. The user can change the defender's direction by

  • pressing the right arrow key will change the defender's direction to right,
  • pressing the left arrow key will change the defender's direction to left,
  • pressing the up arrow key will change the defender's direction to up,
  • pressing the down arrow key will change the defender's direction to down.

The defender can move all the way to the edges of the scene. Once the defender reaches an edge of the scene it stays at the edge of the scene unless it's direction is altered. For example if the defender is moving to the right and it reaches the right edge it should remain at the edge until its direction is changed to go left.

The user can press the space bar in order to fire a bullet. Bullets are created from the location of the defender at the time when the user pressed the space bar. Bullets travel upwards towards the top of the scene at a steady speed and in a straight line. Once a bullet hits a missile

  • the bullet is removed and is no longer visible,
  • the missile is removed and is not longer visible,
  • the defender's score increases by 2 points.

The defender can lose health points in the following cases.

  • When a missile reaches the bottom of the scene the defender loses 1 point of health. The missile should be removed when it is no longer visible on the screen.
  • the defender hits (overlaps in some part or as a whole) with a missile, the defender loses 1 point of health and gains 2 score points. The missile should be removed from the scene when this happens.

The game ends when the defender has 0 or less health points. When the game ends the scene should freeze, i.e.,

  • no missiles are moving,
  • no new missiles are generated,
  • the defender does not move,
  • the defender cannot be controlled by the user,
  • the defender's score is displayed in the top left corner of the scene and the defender's health is displayed at the top right corner of the scene.
  • DUE DATE: Wednesday March 30nd at 12:00pm (NOON)

Binary Search Trees

A classmate of yours is starting a small startup company and is asking for your help to evaluate the code that the startup already has. There is a lot of discussion around the implementation of an Integer Binary Search Tree (IBST). Your classmate is asking you to design an IBST with the following operations so that he can have another design from someone outside the company for a comparison.

Provide your date definitions, any invariants, signatures, purpose statements and tests.

  • ibst-contains? should consume an IBST and a number and return true if the number provided is in the IBST and false otherwise.
  • ibst-add should consume an IBST and a number and return a new IBST with the number provided added to the original IBST
  • ibst-inorder should consume an IBST and return a list of numbers by traversing the IBST inorder.
  • ibst-postorder should consume an IBST and return a list of numbers by traversing the IBST postorder.
  • ibst-preorder should consume an IBST and return a list of numbers by traversing the IBST preorder.
  • ibst-depth should consume an IBST return the maximum depth of the tree, i.e., the longest path from the root to a leaf node.
  • is-ibst? should consume any Racket value and return true if and only if the input is a valid IBST and false otherwise.
  • ibst-remove should consume an IBST and a number and return a new IBST with the number provided removed from the original IBST. This function should return a valid IBST.

Sets

A friend of yours is taking his intro class on mathematical sets and wants to see if you can design and implement mathematical sets and their operations.

A Set is a collection of items. Your sets should be able to hold any Racket value. There elements are not sorted and there is no order. However every element in a set is unique, i.e., there are no duplicates.

For this problem only you are allowed to use equal? to check for equality between two Racket values.

Provide your date definitions, any invariants, signatures, purpose statements and tests.

  • set-add should consume an Set and a Racket value of the same kind as the elements of Set and return a new Set with the Racket value added. If the Racket value is already in the Set, then the Set is unchanged.
  • set-remove should consume an Set and a Racket value of the same kind as the elements of Set and remove the Racket value provided if it is in the Set. If the Racket value is not in the Set then the Set is unchanged.
  • set-contains? should consume an Set and a Racket value of the same kind as the elements of Set and return true if the Racket value is in the Set and false otherwise.
  • set-equals? should consume two Sets that contains elements of the same kind and return true if the Sets contain the same elements. The order of the elements does not matter, e.g., if we have a Set of numbers then {1,2,3,4} is equal to {2,3,4,1} or any other set with the same numbers in any permutation.
  • set-union should consume two Sets and return the Set union of the two sets.
  • set-intersection should consume two Sets and return the Set intersection of the two sets.
  • set-symmetric-diff should consume two Sets and return the Set symmetric difference of the two sets.
  • is-set? should consume any Racket value and return true if the value is a Set, and false otherwise.