CS 1101 (A05) Homework 5: Trees

Due: September 27 (Tuesday) at 11:59pm via turnin (assignment name hwk5).

Assignment Goals

To make sure you can

The Assignment

Option 1: Basic Problems

An emergency response team requires a way to notify its rescue workers as quickly as possible. To this end, teams form a hierarchy in which one person calls a few people, each of whom call a few other people, and so on. Each person on the team has a name, phone number, emergency-related role (such as doctor or fireman), and a list of other people who they are supposed to call in event of an emergency.

  1. Develop a data definition and two examples of data for emergency response teams. The hierarchy for a team should start with a single person who is the team leader.

  2. Provide the template for functions over an emergency response team.

  3. Write a function any-nurses? that consumes an emergency team and produces a boolean indicating whether any person on the team as "nurse" as their role.

  4. Write a function names-with-role that consumes a role and an emergency response team and produces a list of names of all people with the given role.

  5. Write a function add-fireman that consumes the names of two people, a phone number and an emergency response team and produces an emergency response team. In the produced team, the first named person has a new (additional) person to call, with the second name, the phone number, and the role of fireman. The new person doesn't have to call anyone else. You may assume that the first name occurs somewhere in the team and that each name is in the team at most once.

  6. When an emergency happens, people need to be notified as quickly as possible. Write a program notify-time that consumes an emergency response team and produces a number indicating how many minutes it takes for everyone on the team to receive a phone call about the emergency. Assume that each phone call takes one minute and that each person calls the others in their list of contacts in the same order as they appear in the list.

    The key to getting this question is to work several examples on paper and to turn those into good test cases. Draw yourself some sample hierarchies of emergency teams. Annotate your drawing with the number of minutes that pass before each person gets called. Watch what you are doing to annotate the graph, then turn that into code.

    You will likely want to use the scheme function max which takes numbers (as many as you want, but as separate inputs, not in a list) as inputs and produces the largest of those numbers.

Option 2: Challenge Problems

For an operating systems class, you've been asked to implement a simple filesystem. The HTDP text provides three models for filesystems. Use Model 3, the one at the bottom of the page, for these exercises.

If you want to test your filesystems programs on a real filesystem (your own, for example), use the dir.ss library described in HTDP, exercise 16.3.1.

Warning: One common error on these problems is mixing up the positions of files and subdirectories when you make your examples of data and test cases. You then spend a lot of time "debugging" code that is correct around buggy examples. Double check your examples carefully to make sure you haven't done this. One indication that you are having this problem is an error about no matching cond clause in one of your programs -- that usually means that you put the wrong type of data somewhere in your data structure.

  1. Write the template for programs that use the data definitions given in model 3.

  2. Write a program all-small-files? that consumes a directory and a number (a file size) and returns a boolean indicating whether all files in the filesystem have size smaller than the given size.

  3. Write a function files-containing that consumes a directory and a value and returns a list of names of files with the given value as its contents ("value" means "any valid scheme data", like a string, number, etc). You can compare arbitrary Scheme values for equality using the operator equal?.

  4. Write a program clean-directory that consumes a directory and an existing directory name, and returns a directory. In the returned directory, any files of size 0 in or nested within the named directory should have been removed. All other files and directories should be the same between the input and output directories.

    You may assume that the given directory name is only in the system once. You do not need to use this assumption if you don't want to (ie, no loss of points for not optimizing your code around this assumption).

  5. Write a program find-file-path that consumes a directory and a filename and returns either the path (a list of directory names, in order from root to the one containing the file) to that filename or false if the filename is not in the filesystem starting from the given directory. You can put "list[string] or false" as the output in the contract.

    Assume that the given file name is only in the system once.

What to Turn In

Turn in a single file hwk5.ss (or hwk5.scm) containing all code and documentation for this assignment. Challenge problems for one student can go into hwk5-extras.scm (or .ss). Make sure that both students' names are in a comment at the top of the file.


Back to the Assignments page