TURN IN THIS ASSIGNMENT USING WEBWORK!!!
Do this homework using DrScheme. (Save the file as a ".scm" file--that is, with a .scm extension.)
Your parameters must be in the same order as they are shown here. If you are unsure, ask your TA. You will lose credit otherwise.
Your functions should be named exactly as they are shown in each problem.
Follow the HW Skeleton, these homeworks will be autograded and must be in the specified format. You will lose credit otherwise.
Any submissions which don't execute cleanly (i.e. no errors when you click Execute) may receive a grade of zero.
If you do not submit a .scm file, you may receive a grade of zero.
Remember that you must be in "Advanced Student Mode ".
For all problems, you should read the words program and function to mean "program or group of programs," or "function or group of functions."
1. Define the function add-digits which accepts a non-negative number
and returns the sum of the digits of the non-negative number.
Name your function add-digits. Use tail recursion to solve this
problem. You will not get credit for this problem if you use
regular (known as head or also augmenting) recursion.
Example calls:
(add-digits 98254) produces 28
(add-digits 12345) produces 15
(add-digits 0) produces 0
2. Do 26.1.1 from the book. Find the divisors of a non-negative
number > zero. Name your function tabulate-div as the problem
states in the book. Your function is to accepts a non-negative
number n as a parameter and returns a list of the divisors of that
number. Order the list of divisors such that the first divisor in
the resultant list is 1 and the last divisor in your resultant
list is n itself. In other words, the list must be in ascending
order.
Use tail recursion to solve this problem. You will not receive
credit if you use head or augmenting recursion.
Example calls:
(tabulate-div 20) produces (list 1 2 4 5 10 20)
(tabulate-div 13) produces (list 1 13)
(tabulate-div 32) produces (list 1 2 4 8 16 32)
(tabulate-div 6) produces (list 1 2 3 6)
3. Define the function gather-evens. The function is to accept a
list of numbers and return a list of numbers having only the even
numbers from the original list. The relative ordering of the
numbers must remain unchanged. See example calls and expected
output for clarification.
You are required to use tail recursion to solve this problem. You
will not receive credit if you use head or augmenting recursion.
(gather-evens '(1 2 4 88 200 81 18)) produces (list 2 4 88 200 18)
(gather-evens '()) produces empty
(gather-evens '(0 2 0 -6 -5 8 0 2 -22)) produces (list 0 2 0 -6 8 0 2 -22)
(gather-evens '(1 21 9 5 11 33 99)) produces empty
4. Perform the following dfs yourself. No coding is involved. Place
your answer in the form of a list of nodes within your scm file and
comment it out. Use the form
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; <4>
;; (list this that theother)
Assume that you are a freshman and you live in the Towers Dorm.
You want to get a snack from The Varsity and get back to your dorm.
You are a freshman and don't know your way around. Using the
graph below.
perform a depth-first search starting at the node labeled "T
Towers Dorm" and search for the node named V for the Varsity.
Then perform a depth-first search from The Varsity back to the
Towers Dorm.
Assume that you must abide by the rules of one-way roads, so you
cannot go backwards on a one-way road.
Assume that when faced with multiple adjacent nodes you follow
alphabetic ordering - that is, you would explore the link to the
node that is alphabetically first among the current adjacent nodes
being considered.
List the labels of all the nodes that you visit when carrying out
this search. Make sure you list them in the order in which you
visit them. See the following example for clarification on
exactly what we want.
Example. If the problem had been to perform the dfs from H to I
we would expect the following list as the result:
(list H F K E V I)
5. Perform the following bfs yourself. No coding is involved. Place
your answer in the form of a list of nodes within your scm file and
comment it out. Use the form
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; <5>
;; (list this that theother)
Given the graph at
that represents the interconnections of rooms within a house,
perform a breadth-first search from the "foyer" to the "master
bathroom". Assume that you visit adjacent nodes in alphabetic
order. (That is, when at the "foyer" node you see "West hall",
"East hall", and "living room" as the nodes adjacent to the foyer,
explore the "East hall" first since it is alphabetically first.)
Note that all edges of this graph are indeed bi-directional.
List the labels of all the nodes as you visit them in carrying out
the bfs search. See the following example for clarification on
exactly what we want.
Example. If the problem had been to perform the bfs from the
"guest bathroom" to the "home theatre", we would expect the following
list as the result:
(list guestbathroom guestbedroom Westhall foyer halfbath
Easthall livingroom diningroom hometheatre)
For your answer please run the words of a single label together as
we have on this example to help make the list readable.
6. Perform the following bfs yourself. No coding is involved. Place
your answer in the form of a list of nodes within your scm file and
comment it out. Use the form
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; <6>
;; (list this that theother)
Given the same graph representation of the house from problem 5,
perform a breadth-first search from "foyer" to "sauna". Note
"sauna" is not in the graph, so you will end up exhaustively
searching the entire graph.
List the labels of the nodes as you visit them in carrying out
this search.
See the example above (problem 5) for clarification on what your
list should look like.