Homework 11

Due Date Friday, November 22 at 6pm

Purpose To practice working with graphs.

Exercise 1 Consider the following data definition:

(define-struct branch [in])

(define-struct fork [left right])

; A FT (FunkyTree) is one of:

; - "end"

; - (make-branch FT)

; - (make-fork FT FT)

Finish the data design recipe for the supplied definition (you do not need to provide an interpretation). Then, design the function ft-same? which determines if two FTs are equal.

Before starting the following exercise, reread section 19.5 of the textbook to remind yourself of the idea of a Binary Search Tree (BST), which is a binary tree in which everything in the left child is less than or equal to the value at the node, and everything in the right is greater. Your task will be to apply this idea to a file of strings.

Exercise 2 Consider the following data definition and function:

(define-struct bstnode [data left right])

; A StringBST is one of:

; - "leaf"

; - (make-bstnode String StringBST StringBST)

; representing a binary search tree of strings, wherein any nodes

; to the left of a node have a smaller string (according to string<=?)

; and any strings to the right are greater.

(define SBST-LEAF "leaf")

(define SBST-A (make-bstnode "a" SBST-LEAF SBST-LEAF))

(define SBST-R (make-bstnode "r" SBST-LEAF SBST-LEAF))

(define SBST-S (make-bstnode "s" SBST-LEAF SBST-LEAF))

(define SBST-SS (make-bstnode "s" SBST-S SBST-LEAF))

(define SBST-RS (make-bstnode "r" SBST-LEAF SBST-S))

(define SBST-RSS (make-bstnode "r" SBST-LEAF SBST-SS))

(define SBST-MRS (make-bstnode "m" SBST-LEAF SBST-RS))

(define SBST-MAR (make-bstnode "m" SBST-A SBST-R))

(define SBST-MARS (make-bstnode "m" SBST-A SBST-RS))

(define SBST-MARSS (make-bstnode "m" SBST-A SBST-RSS))

(define (sbst-temp sbst)

(...

(cond

[(string? sbst) ...]

[(bstnode? sbst)

(...

(bstnode-data sbst) ...

(sbst-temp (bstnode-left sbst)) ...

(sbst-temp (bstnode-right sbst)) ...)])))

; add-to-sbst : String SBST -> SBST

; Adds a string to an SBST

(check-expect (add-to-sbst "a" SBST-LEAF) SBST-A)

(check-expect (add-to-sbst "s" SBST-R) SBST-RS)

(check-expect (add-to-sbst "s" SBST-MAR) SBST-MARS)

(check-expect (add-to-sbst "a" SBST-MRS) SBST-MARS)

(check-expect (add-to-sbst "s" SBST-MARS) SBST-MARSS)

(define (add-to-sbst str sbst)

(cond

[(string? sbst) (make-bstnode str SBST-LEAF SBST-LEAF)]

[(bstnode? sbst)

(if (string<=? str (bstnode-data sbst))

(make-bstnode

(bstnode-data sbst)

(add-to-sbst str (bstnode-left sbst))

(bstnode-right sbst))

(make-bstnode

(bstnode-data sbst)

(bstnode-left sbst)

(add-to-sbst str (bstnode-right sbst))))]))

Design the function count-words-in-file which accepts a file path and a list of words to search for. The function should read the file, if it exists, as a list of all the words (the pre-defined function read-words will be quite useful) and create a BST of these words. Then, using the BST, the function should produce a list of counts of how many times each search term appears as a word in the file.

Importantly, the function should be case-insensitive: that is, the words "Term", "TERM", and "term" should all be considered equal. We have provided three example text files (alpha.txt, peter.txt, and wood.txt) and the following tests should all pass:

(check-expect

(count-words-in-file (list "A" "a" "f" "F" "n" "N" "z" "Z" "foo") "alpha.txt")

(list 1 1 6 6 14 14 26 26 0))

(check-expect

(count-words-in-file (list "peter") "peter.txt")

(list 4))

(check-expect

(count-words-in-file (list "wood" "would") "wood.txt")

(list 2 1))

For the remaining questions, use the following definition of a graph:

(define-struct graph [nodes neighbors])

; A Graph is a (make-graph [List-of Nat] [Nat -> [List-of Nat]])

; and represents the nodes and edges in a graph, where each node

; is identified by a unique natural number.

; All of the numbers in nodes are assumed to be unique, as are the numbers in

; any list returned by neighbors, and all of the numbers returned by neighbors

; are assumed to be in nodes.

(define G1

(make-graph (build-list 7 add1)

(λ (n)

(cond [(= n 1) (list 2 5)]

[(= n 2) (list 5 6)]

[(= n 3) (list 4)]

[(= n 4) empty]

[(= n 5) (list 3 6 1)]

[(= n 6) (list 4 7)]

[(= n 7) empty]))))

(define G2

(make-graph (build-list 3 add1)

(λ (n)

(cond [(= n 1) (list 2)]

[(= n 2) (list 1)]

[(= n 3) empty]))))

(define G3

(make-graph (build-list 3 add1)

(λ (n)

(cond [(= n 1) (list 2 3)]

[(= n 2) (list 1 3)]

[(= n 3) (list 1 2)]))))

(define (graph-temp g)

(... (list-template (graph-nodes g))

(graph-neighbors g) ...))

Exercise 3 Design the function neighbor-of? that takes a graph and two natural numbers and determines if the second Nat is a neighbor of the first one or vice-versa. Assume both nodes are in the given graph.

Exercise 4 Design the function undirected? which determines if each edge in a given graph has a matching edge going in the opposite direction.

Exercise 5 Design the function fully-connected? which determines if every node is directly connected to every other node.

Exercise 6 Design the function reverse-edges, which takes a graph and reverses the edges. For testing purposes, you might find the following function useful:

; same-set? : (X) [List-of X] [List-of X] -> Boolean

; Does the second list contain all the items in the

; first (assumed to be distinct) and nothing else?

(check-expect (same-set? (list 1 2) (list 2 1)) true)

(check-expect (same-set? (list 1 2) (list 2 1 3)) false)

(check-expect (same-set? (list 1 2) (list 1)) false)

(define (same-set? l1 l2)

(and

(= (length l1) (length l2))

(andmap (λ (x) (member? x l2)) l1)))

Exercise 7 Design the function collapse, which takes in three nodes and a graph. The first two nodes are assumed to be in the graph, and the third is assumed not to be.

The function collapses the first two nodes into one new node, which is named by the third node. All nodes in the graph that were pointing to either of the first two given nodes should now point to this new one, and the new node should point to all nodes either of the first two nodes were pointing to.