Programming with
Data Structures and Algorithms

Finger Exercises: Part 1

Bigfoot

For this lab we're going to use a language developed by two former cs019 students (including current cs019 TA jmiranda) that allows you to trace the evaluation of your program, or look at the big-step operational semantics of your program. To begin, change the language of your file to #lang planet tracer/tracer. Then, add (trace-all) as the next line of your file.

When you run your program, a browser will automatically open up and show you a pretty graphical representation of the evaluation of your code. The only difference between #lang planet cs019/cs019 and this language is that you get to see a trace of your program — the rest of the semantics will still be the same. This will become an invaluable debugging tool, so be sure to check out the documentation.

To set what browser DrRacket opens Bigfoot in, go to Edit, Preferences. Select the Browser tab, and choose Google Chrome.

Questions to Think About

What happened when you traced a check-expect that failed? One that passed? What happened when you traced code that generated an error? How can you find out where a function was defined? Or where it was used?

Exercises

Solve the following exercises. Don't forget to write check-expects.

  1. Tedeschi needs a way to compute the value of a bag of coins. Define the function sum-coins. It consumes five numbers: the number of pennies, nickels, dimes, quarters, and those annoying gold-dollar things that the MBTA gives you as change; it produces the amount of money in the bag.
  2. The Brown University Madrigal Singers (starring everyone's favorite CS19 TA / MTA) have a simple profit function for their concerts. Each customer pays $5 per ticket. Every performance costs the theater $20, plus $0.50 per attendee. Develop the function total-profit. It consumes the number of attendees (of a show) and produces how much income the attendees produce. (But really concerts are free and you should come!)
  3. You are playing a game of Settlers of Catan and you have created a new game-piece that is similar to the robber, but instead of only stealing one resource card whenever he moves, he steals a fraction of resource cards. For a player with 1-4 cards, he steals 1 card; for a player with 5-7 cards, he steals 2 cards; for a player with more than 7 cards, he steals half of their deck (rounding up to the nearest whole number). Define the function steal-cards, which takes the number of cards that a player has and returns the number of cards that are stolen from him when the new robber is moved.
  4. Since the CS students at Brown give Subway so much business, they want to create a discount program where students are given discounts based on what CS course they are in. Write the program discount, which takes the name of a course that someone belongs to and produces the discount (a percentage) that the person should receive on a purchase. Members of CS19 get 20%, members of CS15 or CS17 get 10%, and members of CS2 get 5%. All other CS courses get 15%. Sometimes a non-CS student will try to get a discount, but these students get 0% discount.

    Use discount to write purchase, which takes the price of an item and the name of a course that the student is in and produces the amount owed after the discount is applied.
  5. Define a type for a grade record, which contains a midterm exam grade (non-negative number), final exam grade (non-negative number), and course grade (symbol or false, using the latter if no grade has been assigned yet).
  6. Write a function assign-grade that takes a grade record and produces a grade record. The produced grade record has the same exam grades as the original, but has computed the course grade from the exam grades. The course grade is A for an average above 85, B for an average between 70 and 84, C for an average between 55 and 69, and NC otherwise.
  7. Define a type for a student record, which contains a student's name, class year, and a grade record (use whatever type you like for the class year).
  8. Write a function new-student which consumes a student name and class year and produces a student record with the given name and class year, both exam grades initialized to 0 and the course grade initialized to false.
  9. Write a function average that consumes a list of numbers and produces its average. Return an error message if the list is empty.
  10. Write a function suffixes that consumes a list L (containing anything) and produces a list of all the suffixes of L. For example, (suffixes (list a b c d)) should produce (list (list a b c d) (list b c d) (list c d) (list d) empty).

When you are done...

Call a TA over to get yourself checked off. Once you have been checked off you are free to go.