Programming with
Data Structures and Algorithms

Lab 2


One of the most important steps toward writing good code is writing good test cases. In DrScheme, you should use check-expect for testing. check-expect takes two expressions as input and verifies that their values are the same. (check-expect (+ 1 1) 2) would result in a successful test, while (check-expect (+ 1 1) 0) would not. If all your tests pass, DrScheme will happily tell you so. When a test fails, a window will appear describing the result.

For example, if you wrote the following function to calculate the absolute value of a number,

(define (absolute x)
   (if (< x 0)
       (* x -1)
it would be important to verify that it works correct on both positive and negative numbers. It's also important to test the "edge cases" (like 0 for this function). These are where errors are most likely to be made.
(check-expect (absolute 2) 2)
(check-expect (absolute -5) 5)
(check-expect (absolute 0) 0)

You must completely test every function you write for CS19. We will grade you on the quality of your test cases.

List operators

There are three basic operators for building lists: cons, list, and append (concatenation). Their contracts are as follows:

For each of the following expressions, try to predict (a) what they will return and (b) what the length of the resulting list is, then check your answers in DrScheme:

  1. (cons empty empty)
  2. (list empty empty)
  3. (append empty empty)
  4. (cons (list 1 2 3) (list 4 5))
  5. (list (list 1 2 3) (list 4 5))
  6. (append (list 1 2 3) (list 4 5))

Lists of structures

Computer scientists and computer engineers frequently describe systems as finite-state machines (also called finite-state automata). The best way to understand a finite-state machine is through an example.

Imagine that you want to show how a soda/vending machine behaves. To keep the example small, we'll assume that a soda costs 25 cents and that the machine accepts nickels and dimes. The machine will not give change. The following figure shows the state machine:

The soda machine is a trivial example. In reality, state machines are used to capture all sorts of systems, many with more than 2 to the power of 500 states.

If we give a name to each state, we can represent a state machine as a list of transition structures. A transition structure consists of three pieces of information: the name of the states on either end of the arrow and the label on the arrow.

    ; transition : string string string
    (define-struct transition (source label target))

    ; We create transitions with the make-transition function
    ; For example,
    (make-transition "5-cents" "nickel" "10-cents")

You are going to write a series of programs to work with state machines. Copy the definition of the transition struct into the DrScheme definitions window before you start. Make sure to have a TA check your work when you're done.

  1. Write the list of transitions for the soda machine example showed above. Define it as a constant called soda-machine.

  2. Write a function get-next-state that consumes the name of a state, an action, and a list of transitions and produces the name of a state. The produced state should be the target state of a transition with the input source state name and action. For example,

      (get-next-state "10-cents" "dime" soda-machine)

    should produce "20-cents".

  3. Write a function get-state-sequence that consumes the name of a state, a list of actions, and a list of transitions and produces a list of state names. The produced list should show the sequence of states visited while processing the list of actions (in order), starting from the given state. For example,

      (get-state-sequence "0-cents" (list "nickel" "dime" "nickel") soda-machine)

    should produce (list "0-cents" "5-cents" "15-cents" "20-cents")

  4. Write a function gets-soda? that consumes a list of actions and produces a boolean indicating whether that sequence of actions visits the "soda" state.

  5. If our state machine definition includes multiple transitions with the same source state and action but different target states, it will be unclear which state to enter next. To check for these ambiguities, write a function ambiguous-states that consumes a list of transitions and produces a list of names of source states that have multiple target states for the same action. State machines with ambiguity, or nondeterministic finite-state machines, are a central part of the theory of computation; if you're curious, you can read more online.

  6. This definition of state machines relies on matching state names to hook up the transitions. If you made a typo when entering a state name (say "5-cts" instead of "5-cents"), you would create a machine in which there is no transition out of some state. Programs can help check whether such errors exist in a list of transitions. Write a function dead-end-states that consumes a list of transitions and produces a list of names of target states out of which there are no other transitions.

  7. It would seem that the problems with typos in the previous problem would go away if we made a structure for each state (containing its name and outgoing transitions), then put the state structure instead of the state name as the "target" of each transition. Why didn't we set the problem up this way? Consider what you would need to do this that you haven't learned in Scheme yet and argue why it is technically necessary.