HtDP Problem Set

Section 14

Problem 1:
An ft-node is one of:
  - empty
  - (make-child ft-node ft-node symbol number symbol)

Develop the function get-mothers. The function consumes an ft-node and produces a list of all mother's names present in the tree.

Hint: Use the Scheme operation append, which consumes any number of lists and produces their concatenation.


Problem 2:
Develop the function born-after. The function consumes an ft-node and a year and produces a list of names of family members who were born after that year.


Problem 3:
A Web-page (short: WP) is one of:
  1. empty;
  2. (cons symbol WP); or
  3. (cons WP WP)

Develop the function remove-wp. The function consumes a Web-page and creates a new Web-page in which any pages that start with the special symbol '%remove are replaced with the empty Web-page.


Problem 4:
A peer-to-peer network (like GNUtella) consists of individual nodes that are connected to the rest of the network through one or more neighboring nodes. In a simplified model, each node has only one neighbor and a list of files that it can serve. Every node has a unique number representing its address.

(define-struct file (name contents))
(define-struct node (address files neighbor))

A P2P-Network is one of:
 - empty
 - (make-node number list-of-File P2P-Network)

A list-of-file is one of
 - empty 
 - (cons File list-of-file)

A File is a structure: (make-file symbol string)

Develop the function P2P-search. The function consumes the name of file and a P2P-network and returns the address of the first node that is discovered to have the file or false if the file does not exist anywhere within the network.

Optional: A copyright enforcement group wants to collect the addresses of all nodes on a P2P-Network that are hosting a particular file. Develop the function P2P-search-all, which is like P2P-search except that it returns the list of addresses of all nodes having a copy of the file being searched for.


Problem 5:

See previous problem for data definitions.

Develop the function P2P-get. The function consumes the name of file, the address of a node, and a P2P-network and returns the contents of the file. Assume that both the node and file exist.


Jamie Raymond
Matthias Felleisen

01 december 2003