CS1321 Spring 2002
Homework 10

New due date: before 6:00 pm Monday, April 1

Instructions:

• TURN IN THIS ASSIGNMENT USING WEBWORK!!!

• Do this homework using DrScheme. (Save the file as a ".scm" file--that is, with a .scm extension.)

• At the top of your file, include the student info portion of the HW Skeleton (Name, GT Number, HW, Course, Instructor, Lecture Time).

Note:

• 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 Scheme".

• For all problems, you should read the words program and function to mean "program or group of programs," or "function or group of functions."

• Failure to follow these instructions may result in harsh point deductions for this assignment.
  

Problem 1

You've been hired by a coffee company to help them figure out some interesting things about their coffee plantations. They want to find the average coffee yield of their plantations, and lucky for you, they already have a set of scheme structures setup to help you out with this. They give you the following memo:

After asking some of the people in Junior Management, you find out that the average yield of any plantation is the total amount of coffee produced by the farms and plantations that reaches Java Scheme Coffee House divided by the total number of farms. Knowing this, you decide you have enough information to write a function called average-coffee-yield. The function should take in a plantation and determine the average coffee yield for the given plantation.

An example of this function would be

(define FARM1 (make-farm 'SouthWest 128 'Robusta))
(define FARM2 (make-farm 'West 28 'Arabica))
(define FARM3 (make-farm 'Yeman 786 'Sananni))
(define FARM4 (make-farm 'North 128 'WildMild))
(define FARM5 (make-farm 'NorthEast 854 'Yukon))
(define FARM6 (make-farm 'Island3 2000 'Sidamo))
(define FARM7 (make-farm 'Island4 135 'Burbon))
(define FARM8 (make-farm 'Island5 9542 'BellaVista))
(define FARM9 (make-farm 'NewGuine 4000 'Peaberry))
(define FARM10 (make-farm 'Variety1 128 'GoldenLight))
(define FARM11 (make-farm 'Variety2 12 'Yergacheff))
(define FARM12 (make-farm 'Variety3 50000 'Valentine))

(define PLAN1 (make-plantation 'JavaEstates
   0.36 
   (list FARM1 FARM2 FARM3 FARM4 FARM5)))

(define PLAN2 (make-plantation 'ImpaNemma
   0.63 
   (list FARM6 FARM7)))

(define PLAN3 (make-plantation 'Append
   0.23
   (list PLAN1)))

(define PLAN4 (make-plantation 'Lambda
   0.786
   (list FARM8 FARM9)))

(define PLAN5 (make-plantation 'Condz
   0.0035
   (list PLAN4)))

(define PLAN6 (make-plantation 'Define
   0.04
   (list FARM10 PLAN2 PLAN3)))

(define PLAN7 (make-plantation 'JavaSchemeCoffeeHouse
   0.00
   (list FARM11 PLAN6 FARM12 PLAN5 PLAN6)))

(define ROOT PLAN7)

>(average-coffee-yield ROOT)
27345649177/6000000

A picture that represents the plantation above would be

In the picture, farms a denoted by RED squares. The annual amount of coffee yield is indicated by the number inside the square. Plantations are indicated by ORANGE squares. The free-base for each plantation is indicated by the number inside the square.

HINTS

• Remember that not all of the coffee produced by a plantation reaches Java Scheme Coffee House—you'll have to use the free-base field to help determine what percentage the company gets from a plantation.

• For the purposes of this problem, conceptually think of the graph as a N-ary tree of plantations and farms.

• Remember, the average coffee yield is how much coffee reaches the company divided by the number of farms—not the number of farms AND plantations.

Problem 2

A common tool used in math is called Pascal's Triangle. Pascal's Triangle shows provides a way to determine the coefficients of a binomial expression raised to a particular power. To find the coefficients, a mathematician only needs to look at the row number that corresponds to the given power (n) that the binomial is being raised to—remember that row numbers for Pascal's Triangle start at row numbers zero. For example, given (a + b)⁴ it can be expanded in the following manner by looking at the forth row of Pascal's Triangle:

(a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴

As great of a tool that this might be, the problem that Pascal's Triangle has is that it gets rather cumbersome as the power (n) that you raise the binomial to gets really really big. So, mathematicians decided to devise a different way to derive the coefficient of a term in a binomial expansion. The formula needs to know the power the binomial is being raised to, and the term number in the expansion you want to find. In the above example where (a+b) is raised by the power 4, the term 6a²b² was in the 2 term spot—remember that term numbers for this problem start at zero. The formula for calculating the coefficient given a power (n) and term number (t) is

coefficient = n! / (t! * (n - t)!)

This formula provides a much faster way of calculating a given coefficient. Your job now is to write a function called pascal-list. The function should take in a power that a binomial is being raised to. pascal-list should return a list of all the coefficients in the correct order for the given binomial expansion. A few examples of this are

> (pascal-list 6)
(list 1 6 15 20 15 6 1)

> (pascal-list 4)
(list 1 4 6 4 1)

> (pascal-list 5)
(list 1 5 10 10 5 1)

> (pascal-list 0)
(list 1)

> (pascal-list 14)
(list 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1)

NOTES

• To view Pascal's Triangle click here

• You MUST use tail-recursion to solve this problem—any use of augmenting/head recursion will result in no credit for this problem.

Hint

You will more than likely want to create a function for the formula that determines what the coefficient should be. You are welcome to use the factorial code provided to you in the lecture slides—remember it must be tail-recursive though.

Problem 3

Suppose you are given the following graph

You are to start off at node A and proceed to node F using a DFS.

1. In what order would each node be visited? Assume that when you are presented with multiple choices, you take the choice that comes first alphabetically—if you are at node D you can go to node I or C, the algorithm would visit node C first because it is alphabitically before I. If a particular node is visited more than once, thus resulting in a cycle while you are using the DFS, list the first time that the node is visited with a * following it in your final answer. For example, lets assume that the following nodes were visited in the order ABADCDEFGABCBI, your final answer would look like A*B*D*C*EFGI.

2. How many times were each of the nodes that caused a cycle visited during the DFS from A to F?

3. What order would the nodes be visited in if you were to use a DFS to go from node A to H? Be sure to format your answer the same way as part a.

NOTE

Be sure to comment out your answers to this problem.

Problem 4

Now suppose you are given the same graph from problem 3.

1. In what order would each node be visited using a BFS going from node I to node G. Be sure to format your answer in the same fashion as you did in problem 3. Assume that when multiple choices are provided, the BFS picks the first one alphabetically. If a node is visited twice, but does not result in a cycle, you should not place a * after it in your final solution.

2. What is the final path that the BFS found?

3. In the process of finding the path from I to G, how many cycles were encountered by the BFS.

NOTE

Be sure to comment out your answers to this problem.

Problem 5

You're given the following weighted graph

1. Using Prim's Algorithm, describe the order that nodes would be picked in while creating the Minimal Spanning Tree starting at node H. Format your answer in terms of a list of symbols. For example, if the order the nodes were picked in was AJIFBC you should format your answer by saying

   (define p5 '(A J I F B C))

2. What is the total weight of the MST that was returned by Prim's Algorithm? Format your answer by defining it to be p5total. Use the define function to do this. For example, if your total weight was 35 then you should have

   (define p5total 35)

   in your scheme file that you turn in.

NOTE

Do NOT comment out your answer—format it in the exact same way as shown in the problem.

Problem 6

1. Using the same graph from problem 5, outline what order the nodes would be picked to create a "Minimal Spanning Tree" using a greedy algorithm start at node H. The greedy algorithm you should use operates in the following manner

   1. Start at the given node
   2. Pick the lowest adjacent weight and connect the new node only if it doesn't create a cycle
   3. Mark the newly connected node as the current node.
   4. If you exhaust the possibilities that can be taken from the given node, backtrack untill you are at a node that allows for a new node to be connected.
   5. If all the nodes are connected in the graph, stop.

   6. Restart the whole processes at step 1 using the current node as the given node.

   Be sure to format your answer the same way you did in p5, only define your answer to be p6.

2. What is the total weight of the tree found by the greedy algorithm? Format your answer the same was as you did in p5, only define your answer to be p6total.

Last Modified: Wednesday, March 27, 2002 4:43 PM by CS1321WWW