Homework Solutions
Chapter 1 Homework Solutions
| 1.1 |
Multiple solutions, here is one example:
Making a peanut butter and jelly sandwich
1. Take out materials.
2. Lay out 2 slices of bread.
3. Spread jelly on 1 slice until surface is covered.
4. Spread peanut butter on the other slince until surface is covered.
5. Stick the two slices together.
An algorithm such as this one has several general statements. For example, how do
you spread jelly? or, What materials should be taken out?
Making a peanut butter and jelly sandwich
1. Take out materials:
a. Take out two slices of bread.
b. Take out a tub of jelly.
c. Take out a tub of peanut butter.
d. Take out a spoon.
e. Take out a knife.
f. Take out a plate.
2. Lay out 2 slices of bread on the plate, and choose 1 to be the jelly slice.
3. Is the surface of the jelly slice completely covered by jelly?
3a. If yes, go to 4.
3b. If no, scoop up jelly from the tub and apply to the jelly slice. Go
back to 3.
4. Is the surface of the peanut butter slice completely covered by peanut butter?
3a. If yes, go to 5.
3b. If no, scoop up peanut butter from the tub and apply to the peanut
butter slice. Go back to 3.
5. Stick the two slices together. (jelly end to peanut butter end)
| | 1.2 |
1. Gather car soap, wax, a sponge, a 4 gallon bucket, a hose and 2 dry rags.
2. Fill the bucket half-way with water and pour in the appropriate amount of soap.
3. Go to 4 when the car is completely washed.
3a. Dunk the sponge in the bucket.
3b. Wash unwashed parts of the car (from top to bottom).
3c. Hose off the washed parts of the car. Go back to 3.
4. Wait until the car is dry.
5. Go to 6 when the car is covered with a layer of wax.
5a. Pour a dab of wax onto the dry rag
5b. In circular motions, rub the wax on unwaxed portions of the car. Go
back to 5 when the rag is dry.
6. Use the second dry rag to rub off all of the wax.
Modification 2:
7. If no cars are present to be washed and waxed, terminate this algorithm. If
there are cars present, continue to 7a.
7a. Empty the buck of water. Fill it up again half-way with water and
pour in the appropriate amount of soap.
7b. Find 2 new dry rags.
7c. Go to 3.
| | 1.3 |
1. Calculate change due: C=(money paid) - cost.
2. If(C>=100), then give 1 dollar back and C=C-100. Then, go back to 2. If
false, continue to next step.
3. If(C>=0.25), then give 1 quarter back and C=C-0.25. Then, go back to 3. If
false, continue to next step.
4. If(C>=0.10), then give 1 dime back and C=C-0.10. Then, go back to 4. If
false, continue to next step.
5. If(C>=0.05), then give 1 nickel back and C=C-0.05. Then, go back to 5. If
false, continue to next step.
6. If(C>=0.01), then give 1 penny back and C=C-0.01. Then, go back to 6. If
false, continue to next step.
7. Say goodbye to customer.
| | 1.4 |
(assumes k is a positive, integer value)
answer := 1
power := 1
while (power <= k)
answer := answer * n
end
| | 1.5 |
The engineer's algorithm does not work. For this case, it will pick all cable
routes except the routes that cost above 7. Clearly, we can eliminate a route that
costs 1, and two routes that cost 6. It is possible to modify the algorithm so
that it does work. In step one, add a restriction on picking routes that fail to
connect new houses.
| | | | 1.6 |
start
n=4
c=1
n<1 is false
c=1*2=2
n=3
n<1 is false
c=2*2=4
n=2
n<1 is false
c=4*2=8
n=1
n<1 is false
c=8*2=16
n=0
n<1 is true
output 16
end
The algorithm finds 2 to the power of 4 by multiplying 2 n=4 times.
| | | | 1.7 |
n=4
c=20
( c/2<= n)
sum := sum + my_n
my_n := my_n + 1
end
This algorithm will have 2 initial steps, plus 2n executions of the loop and
2*(n+1) executions of the loop condition, making 4(n+1) steps total.
sum := (n*(n+1))/2
This algorithm takes 1 step, for any n.
| | | | 1.8 |
NOTE: Minimum start year should be past 1752, the year the Gregorian calender was
implemented in most countries. See http://blog.plover.com/calendar/1752-act.html
for an incredibly detailed explanation.
current_year := start_year
while current_year <= end_year
if (current_year % 4 == 0)
if (current_year % 100 == 0)
if (current_year % 400 == 0)
output current_year
end
else
output current_year
end
output current_year
end
current_year := current_year + 1
end
| | 1.10 |
This problem is open-ended and has many solutions. The following can be one
solution.
One algorithm for solving a maze is following the wall to one's right.
Another algorithm is to drop markers crumbs to mark which paths a person has
already traversed.
1. Inside the maze, one has blue and red markers.
2. From the start of the maze, drop red and blue markers up until the first
branch of maze paths.
3. Randomly choose a path that does not have both blue and red markers. Choose
paths without any markers before paths with blue markers.
3a. Follow the path, dropping blue markers. If the path has blue
markers already on it, drop red markers.
3b. Go back to 3 if one reaches a branch.
3c. If one reaches a dead end, then return to the last branch while you
drop red markers.
For maze 1, algorithm #1 should outperform algorithm #2 because algorithm #1 finds
the shortest path to the end. Certainly, algorithm #2 can find also
generate a shortest path solution. However, since algorithm #2 can only
randomly obtain this optimal solution, it can never outperform algorithm #1
For maze 2, algorithm #2 may tend to outperform algorithm #1. Algorithm #1 goes
through 3 costly dead ends before it is on track. Algorithm #2 has the
likelihood of avoiding one of these early dead ends. If algorithm #2 gets
past them, then the end is not far away.
For maze 3, algorithm #1 may perform better. Although algorithm #1 will always
hit that early dead end, it will completely avoid the long, costly dead
end at the top of the maze. Algorithm #2 is presented with too many
opportunities to randomly pick a costly path. Secondly, a cycle present
in the latter half of the maze may possibly crash algorithm #2
| | | | 1.11 |
This is another open-ended question designed to spur thinking. Below are some
ideas
1. Copy each written character into an xy-coordinate plane.
2. Draw 10 different lines on the graph and determine how many times each line
intersects the letter.
3. Let each line predict the likelihood of a letter using weights and a function
of intersections. (For example, the letter D will have almost every line
intersect twice. The letter B will have 3 vertical intersections, and the
letter A will have 2 or 1 vertical intersections).
4. Output the most likely letter based on our 10 predictions.
Here is another algorithm.
1. Pretend the letter is a maze, and that you are starting at the bottom-right
corner of the letter. Travel around the maze, if any of the following occur,
we know we have found a letter.
case A: we find 1 loop with 1 branch
case B. We find 3 loops, the two small loops that make up the two humps
in the letter in addition to the loop around both.
case C. No loops. 1 dead end.
case D. 1 loop. No branches
case E. No loops, 3 branches.
2. Once the case is determined, output the letter.
| | | | 1.12 |
Input and output to algorithms are data. Often, algorithms will need to input or
output a lot of data, thus lending an advantage to data structures that make data
handling intuitive and fast. Secondly, data structures can assist in processing
data; when data is organized in some way, an algorithm may perform steps to reach
an output faster.
| | | | 1.13 |
To determine if the point configuration forms a square, we can first draw lines
between every point pair. Four of the outer lines are either parallel or
perpendicular with each other. There also exists two diagonals that are
perpendicular to each other.
Another and perhaps easier way is to use distances.
Between 4 pairs, the distance will be some constant, and between the other 2 pairs,
the distance will be a constant times the square root of 2. There are various ways
to count these pairs, below is a very simple method of determining squares by
distances.
Determine Square by distances.
1. Let C=0 be the number of pairs with distance X
2. Let D=0 be the number of pairs with distance X*(square root of 2)
3. X=minimum of [(distance(p1,p2), distance(p2,p3), distance (p3,p4)].
4. if( distance(p1,p2) = X ) then C=C+1
5. if( distance(p1,p3) = X ) then C=C+1
6. if( distance(p1,p4) = X ) then C=C+1
7. if( distance(p2,p3) = X ) then C=C+1
8. if( distance(p2,p4) = X ) then C=C+1
9. if( distance(p3,p4) = X ) then C=C+1
10. if( distance(p1,p2) = X*(square root of 2) ) then D=D+1
11. if( distance(p1,p3) = X*(square root of 2) ) then D=D+1
12. if( distance(p1,p4) = X*(square root of 2) ) then D=D+1
13. if( distance(p2,p3) = X*(square root of 2) ) then D=D+1
14. if( distance(p2,p4) = X*(square root of 2) ) then D=D+1
15. if( distance(p3,p4) = X*(square root of 2) ) then D=D+1
16. if( C=4 and D=2 ) then the four points do form a square.
| | | | 1.14 |
The algorithm relies on the user to pick reasonable minimum and maximum x values.
If the user does not pick a range that includes the minimum value, the algorithm
will fail. It also may not be able to deal with equations in which the minimum y
value is infinite. The algorithm also assumes the function is defined for every x
value within the range given. It returns only an approximation of the minimum
value.
| | | | 1.15 |
1. If the word is 1 character long, it is a palindrome
2. Check if 1st character is the same as the 1st to last (last) character.
3. Repeat step #2, incrementing”1st” until it is equal to the (length of the
word in characters) / 2 + 1. If the word has an odd number of characters, this
will be the middle character of the word, because the division used is integer
division.
4. If “1st” is equal to (length of the word in characters) / 2 + 1, word is a
palindrome.
| | | | 1.16 |
IMove can incorporate various strategies to meet customer demand. One such
strategy is to predict how many trucks will be rented in each depot and how many
trucks are likely to be returned to each depot.
Expected trucks returning - Expected trucks leaving = expected net truck gain/loss
For example, suppose that for Depot A 10 trucks usually are checked out and 5
trucks usually return. Then during the course of the month, IMove should find
truck surpluses in other depots, and drive them to Depot A.
Suppose Depot B is closest to Depot A, and expects 3 trucks to leave and 6 to be
checked-in. Then Depot B would send its surplus of 3 trucks to Depot A.
The rudimentary algorithm to solve this problem would be:
1. Given an array of 150 vector. Each vector contains the location, number of
expected truck, expected number of trucks to be check-in, the expected net truck
gain/loss, and an ordering of all the depots sorted by distance.
For the below algorithm, let expNet be the expected net truck gain/loss.
Loop though each vector V
if( V.expNet is negative )
Loop through V's closest depots D until V.expNet=0
if ( D.expNet is positive )
Send D's surplus to V (but do not send so many
as to make V.expNet positive)
More information could greatly improve the effectiveness of the algorithm. For
example, if we knew how each expected number changed from one month to the other,
our program would better predict demand. Secondly, the algorithm could calculate
the rate of net truck gain/loss in addition to the rate at which more trucks can be
replenished. If a depot, is losing trucks at a quick rate, then perhaps we can
send trucks from various depots to zero out the loss. The rate predictions will
ensure that that the trucks get there on time. More tweaks can be added if for
each depot, there is a critical minimum of trucks that must be met. If the truck
number falls below this minimum (or if the rate of loss predicts this fall), then
trucks should immediately be reassigned to this depot. Information about the speed
of the trucks and how the speed is affected by weather are also useful pieces of
information.
| | | | 1.17 |
The algorithm will not calculate the best fit. Consider the following item list and
truck:
Item Value Volume Value/Volume
1 17 8 2.125
2 6 3 2
3 6 3 2
4 6 3 2
Maximum truck capacity: 9 volume.
The customer's algorithm will choose the first item with volume 8 and stop.
The optimal solution would be to choose the 3 items that have a volume of 3, but a
lower ratio than the 8 volume item. This would end up with 18 value in the truck
instead of 17.
| | | | 1.18 |
1 Loop i from 1 to n
2 # Find out if i is a prime number
3 Set primeFlag = true
4 Loop from j = 2 to ((i-1)/2)
5 If i / j has no remainder then
6 # i is NOT PRIME
7 Set primeFlag = false
8 End
9 End
10 If primeFlag then OUTPUT i is PRIME
11 End
| | 1.19 |
With our initial pool of 200 birds, we can collect statistics on the average beak
length and wing span for each group of birds. Now for each generation of offsprings
produced in each group, we can again measure the average beak length and wing span
for each group of birds and use our program to see how it compares to the last
generation of their respective group (find the difference between the values of
each generation). The program should also note the amount of difference in these
attributes between the two groups for each passing generation.
Another factor to keep track of is to see is there any difference in food
preferences between the two groups. For each generation, data can be gathered to
see what is the most common food of choice for each group and see whether the food
type differs greatly between the two groups as months go by.
Different food choices can play a factor in speciation. Look at
http://upload.wikimedia.org/wikipedia/commons/c/c1/Drosophila_speciation_experiment.svg
To ultimately determine whether speciation has occurred, we will have to check
whether the two groups can interbreed. After the program determines there has been
significant differences between the groups in beak size, wing span, and/or food
choices and traits such as beak length have seen significant changes in a group
with each passing generation, we can take say 50 birds from each group and put them
in the same area. Scientists will be able see whether the two seperate groups will
breed or not.
| | | | 1.20 |
Set match_count to 0
Loop though each vector base pair
if base pairs are the same
add one to match_count
otherwise add pairs to list of umatched pairs
Output number of matched pairs, and list of umatched portions.
| | | | 1.21 |
The difficult portion is determining significant peaks. This data is very noisy,
and thus reporting Flux increases will inevitably fail. Additionally, reporting
high rates of change will fail as well because much of the noise appears to have
high slopes.
The easiest way to solve this problem is to say solar flares occur when the ratio
between a peak (local maximum) and a valley (local minimum) is at least 10.
As the new data point y is collected, after the previous reading x. We also know
the last peak/valley as p.
if( y-x>0 ) # there is a positive slope.
if( y/p>10 )
output solar flare warning.
A better way to predict flares is to use statistics. Log the data as a series of
peaks and valleys. Calculate the mean change between these points, as well as the
standard deviation. Now, consider the last observation as a peak or valley. If
this data point falls within s standard deviations from the mean, then there is
little evidence for a solar flare. One will have to find what s, the standard
deviation limit, should be in order to accurately assert that a solar flare is
present.
Let s be a list of peaks and valleys.
Calculate the mean change between points in s. Store then in c.
c[i]=s[i]-s[i-1] from i=1 to i=length of s
Calculate the mean and standard deviation of c
Take the next reading t
if( (t-s[last entry]) is greater than 0 and an outlier to the mean and standard
deviation for a normal curve )
output solar flare warning.
| | | | 1.22 |
a) Selection based on value alone is certainly a solution. However, this would
prioritize sector (d=7,v=50). Simply by analyzing the sample chart, we see a
long string of hazardous sectors, 11 total with a cumulative value of 239.
Should any one sector in this string catch on fire, then the fire may spread
easily throughout these sectors, and then affect sectors that have low dryness
indexes. Therefore, the idea is to reduce the connectivity of hazardous sectors.
b)For each sector, we find a variable m.
To get m, find the net value of adjacent flammable networks if this sector is
made inflammable. Then multiply these net values together , and then multiply
with v. We want to maximize m.
Algorithm:
1. Ignore inflammable sectors if there are flammable ones.
2. Find m for each sector
3. Make inflammable the sector with highest m, and add it to the end of the
list of "best sectors". Ignore this sector for the rest of the algorithm.
4. Go back to 2 if flammable sectors remain.
This algorithm is simple. It ignore the dryness index except for classifying
sectors as flammable or inflammable. Certainly, dryness can be used to make
decisions, but our approach to isolating sector networks is based on dividing
networks with large net value. Really, this problem is extremely rich and
open-ended. So, any solution that identifies a reasonable strategy and implements
it with a reasonable algorithm is acceptable.
To illustrate this algorithm, let us go through two iterations.
First iteration. The sector with (d=25, v=22) is chosen first because it will have
the highest m. For this sector, m=42*175*22, where 42 is the net value of the
hazardous network on its left, 175 is the net value of the hazardous network on its
right, and 22 is the value of itself. The sector immediately left of it is (d=33,
v=17). This results in an m=17*25*197, which is less than the previous. The m's
of every other sector are significantly lower because they do not divide the
network, and thus are only able to multiply 2 values instead of 3.
Now, (d=25, v=22) has been added first to our list and is inflammable.
A network exists to the left and right of this sector.
For the left network, there are 3 sectors with associated m values
(d=4, v=20)=> m=440
(d=23, v=5)=> m= 185
(d=33, v=17) => m=425
Obviously, these are pretty low, and we suspect the right network will be reduced
first. However, notice we would pick the sector with the highest value. This is
logical since if any of these sectors catch on fire, they would light each other
up. Therefore, preference to the sector with the highest value should be paramount.
For the right network, we see a long chain of hazardous zones. The follow is a
list of these sectors going clockwise.
(d=46, v=9)=> m=1494
(d=31, v=34)=> m= 40392
(d=4, v=20) => m=96320
(d=28, v=17)=> m=2686 (m is low since this sector does not split the
network)
(d=7, v=50)=> m= 180000
(d=25, v=36) => m=42120
(d=30, v=9)=> m=1494
| | 1.23 |
This solution involves simple geometry. If d is larger than 7*x, then the rover
will always find the communication device. Otherwise, the probability of the rover
finding the device is a the ratio of two circles.
PI=3.1415926535897
if(7*x<=d)
return 1.00
else
return (PI*d*d)/(PI*49*x*x)
| | 1.25 |
This is an open ended problem. Most solutions, however, should address key
questions:
1. Gather Requirements:
a. Who are the users?
b. Is Encryption necessary?
c. How much lag/latency is acceptable?
d. What hardware is required?
2. Algorithm:
a. Designs need to go through a revision process
3. Coding:
a. Completed code should be tested thoroughly, and fixed if it does not
meet the requirements.
|
|
