CS 1102 (A05) Homework 3: Complex Data Definitions

Due: September 15 (Thursday) at 11:59pm.

Assignment Goals

The Assignment

Mutual Recursion

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.

In these exercises, a "filesystem" is a directory (the root directory). Functions over "filesystems" should therefore follow the template for dir (where dir is as defined in the HtDP model).

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 two examples of data created with the filesystem data definition.

  2. Write the template for programs over filesystems.

  3. Write a program large-files-named? that consumes a filesystem, a number, and a symbol and produces a boolean indicating whether any file in the filesystem has the given name and a size at least as large as the given number.

  4. Write a program count-cluttered-dirs that consumes a filesystem and produces a number indicating how many directories in the filesystem have more than 20 files.

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

    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).

  6. Write a program find-file-path that consumes a filesystem 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.

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

Including Functions in Data Structures

Return to the auction assignment from last week. Reuse your data definitions from that assignment (no need to reproduce templates here). If you didn't get the listed functions working on homework 2, come to office hours for help or just develop the programs from scratch.

  1. Rewrite winning-items using filter and/or map.

  2. Rewrite hour-passed using filter and/or map.

  3. Rewrite bid-cheap-cars using filter and/or map.

  4. Using filter and/or map, write a function stuff-won that consumes a person's name and an auction and produces the descriptions of all items that a person has won. A person has won an item if there are 0 hours left to bid and the named person is the high bidder.

What to Turn In

Turn in a single file hwk3.ss (or hwk3.scm) containing all code and documentation for this assignment. Make sure that both students' names are in a comment at the top of the file.

Hints and Guidelines

Back to the Assignments page