Assignment 1: Programming in Racket

Parameters:

Due date: Wednesday 9/11, 11:59PM EST
Use the following code template here
Upload a code.rkt solution to Gradescope. It will give you a score, but this is not your final score; some of the test cases will be kept private. You should test all your code thoroughly.
Ask questions on Piazza or during office hours.
Perform all the work for this project by yourself. You may discuss with your classmates, but you must write your own code.
On all problems submit at least 3 of your own test cases.

Resources:

Problem 1 [10 Points]: all-greater?

Implement the function all-greater? l k that takes as input a list of numbers l and number k and returns true if every element in l is greater than k and false otherwise. The empty list trivially satisfies the requirement, so (all-greater? '() k) should return #t for any k.

See this section of the guide on lists.

Example:

> (all-greater? '(2 3 4) 2)
#f

Problem 2 [10 Points]: sorted?

Implement the function sorted? l that takes as input a list of numbers l and returns true if the list is sorted from least to greatest and false otherwise. Your solution should use a helper function.

Example:

> (sorted? '(2 3 4))
#t

Problem 3 [10 Points]: sum-tree

The following problems use a binary tree datatype whose leaves are numbers:

; type tree =
;   | node of tree * tree
;   | leaf of number
(struct node (l r) #:transparent)
(struct leaf (x) #:transparent)

If you’re unfamiliar with structures in Racket, see this section of the guide. Implement the function sum-tree t that takes a binary tree t as an argument and returns the result of summing all the leaves in the tree.

Example:

> (sum-tree (node (leaf 10) (leaf 20)))
30

Your solution must make use of the match construct.

Problem 4 [10 Points]: right-linear?

A binary tree is right-linear if, for every node in the tree, the left child is a leaf. For example, the following tree is right-linear:

  /\
 /  \
 1  /\
   2  3

Implement a function right-linear? t that returns true if the tree is right-linear and false otherwise.

Example:

> (right-linear? (node (leaf 10) (leaf 20)))
#t

Problem 5 [10 Points]: dfs-list

A depth-first left-first traversal of a tree traverses the tree in depth-first order starting with the left child of each node. Consider this tree:

  /\
 / 3
/\
1 2

For the above tree, a depth-first left-first traversal explores leaf 1, then 2, then 3.

Implement a function dfs-list t that takes a tree as an argument and returns a list of all the leaf values traversed according to depth-first left-first order.

Example:

> (dfs-list (node (node (leaf 1) (leaf 2)) (leaf 3)))
'(1 2 3)

Problem 6 [10 Points]: subst

Implement a function subst t old n that takes a tree t and two numbers old and n as arguments and returns a tree that results from substituting all leaves of value old with n. This is like a “find and replace” for trees: we want to find all values equal to old and replace them with n, leaving everything else about the tree unchanged.

Example:

> (subst (node (leaf 10) (leaf 20)) 20 30)
(node (leaf 10) (leaf 30))

Problem 7 [10 Points]: multi-subst

Now we want to perform multiple substitutions at once. We will keep track of all the substitutions in a hash table. A hash table in Racket can be defined and used as follows:

; declare a hash-table that maps 1 to 3 and 2 to 4
> (define my-tbl (hash 1 3 2 4))

; look up key 1 in my-tbl
> (hash-ref my-tbl 1)
3

; check if hash table contains key
> (hash-has-key? my-tbl 1)
#t

Implement the function multi-subst t tbl that takes a tree t and a hash table tbl as input and returns a new tree that results from performing all the substitutions specified by tbl.

Example:

; define a substitution that maps 1 to 3 and 2 to 4
> (define test-tbl (hash 1 3 2 4))
> (multi-subst (node (leaf 1) (leaf 20)) test-tbl)
(node (leaf 3) (leaf 20))

Problem 8 [10 Points]: filter

Implement a function my-filter l f that takes a list of numbers and a function of type number -> bool as input that removes all elements of l for which f evaluates to #f.

Example:

> (my-filter '(1 2 3) (lambda (x) (< x 3)))
'(1 2)