Lab 4 Recursion
Purpose: The purpose of this lab is to give you some hands-on experience with self-referential data, and also to get some practice using the exam server.
Textbook references: Chapter 9: Designing with Self-Referential Data Definitions
Relay Race
Goals: Practice processing self-referential data.
Coach Matt is the coach of a very successful relay race team. Each member of the team takes turns completing parts of the race before passing the baton to the next member. Each runner has a name and a fastest time. "Rebecca" is the fastest member of the team, so she is in the last position, known as the anchor.
Starter Code: The following data definition encapsulates Coach Matt’s team.
; A RRT (RelayRaceTeam) is one of: ; - "Rebecca" ; - (make-runner String Number RRT) (define-struct runner [name time team]) ; and represents the fastest runner ; or a team containing her (and possibly other runners) with a name and fastest time in seconds.
Exercise (Reviewed) 1 Define examples and design a template for a RRT.
Exercise (Reviewed) 2 Design a function which gives a RRT’s total race time, assuming all the members run their fastest time (where "Rebecca" has a fastest time of 0).
Exercise 3 Design a function which determines if a runner with a particular name is in a RRT.
Exercise 4 Design a function which takes a RRT and decreases all of its runner’s times sizes by 1 second.
Exercise 5 Design a function which takes a RRT and a number and removes all runners slower than the given time.
Exercise 6 Design the function in-order? which ensures a RRT has its runners in order of slowest, second-slowest, third-slowest, and so on, ending with "Rebecca". Hint: break the problem down into English. Doing so shall hopefully show that a previously defined function will help.
Testing, Testing, 1, 2, 3
Goals: To practice using the exam server for next week’s exam.
On Wednesday, October 14th, you will be taking Exam 1. The exam will take place on the exam server. To prepare for this exam, there is a tutorial of the process of taking the test in the exam server.
Exercise 7 When the TA instructs you, go to the exam server, sign in using your Khoury account, and perform the tutorial. When you are done, please wait for the entire lab to finish, as we will regroup and continue with lab.
Before You Go...
If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.
Expanding Conciousness
Goals: Learn to look at numbers and recursion in a new way.
Starter Code: Below is a data definition which shows how natural numbers can be built up recursively.
; A Nat is one of: ; - 0 ; - (add1 Nat) (define NAT-0 0) (define NAT-1 (add1 NAT-0)) (define NAT-2 (add1 NAT-1))
Exercise 8 Design the template for Nats. In these problems, we’re not quite using structured data, but we’re going to treat numbers as if they were structured. Specifically, we’ll use zero? and positive? to distinguish our two cases, and we’ll treat positive numbers as if they were made from a smaller number using add1. Zero is still atomic data, and to take apart a positive number into its smaller part, we use sub1.
Exercise 9 Design the function double which doubles a Nat. As we are following our Nat template, you may only use the functions mentioned above, cond, and double (no + or *).
Exercise 10 Design the function even?/nat which deterimes if a Nat is even. You may only use the functions mentioned above, as well as cond, not, and even?/nat. Your code must follow the template exactly, and therefore two successive calls to sub1 is forbidden.
Exercise 11 Design the function nat+ which sums two Nats. You may only use the functions mentioned above, as well as cond and nat+ (no +).