Homework Problems
Chapter 5 Homework Problems
| 5.1 | An a array is created with the six lines below. Fill
in the blanks in line 8 to create the same array.
1 arr = Array(5)
2 arr[0]=9
3 arr[1]=2
4 arr[2]=5
5
6 arr[3]=4
7 arr[4]=3
8 arr = [__,__,__,__,__]
| | 5.2 | Using the array arr in problem 5.1, determine the output of
the following code:
1 i=0
2
3 while(i < arr.size)
4 puts arr[i];
5 i=i+1;
6 end
| | 5.3 | Modify the code in 5.2 to print only array elements that are
greater than 4.
| |
| | 5.4 | Name three real-world applications where one-dimensional
arrays can be useful. Name three real-world applications
where multi-dimensional arrays can be useful.
| |
| | 5.5 | What does the following program output?
1 arr = [1, 2, "ruby", 3.14159, ["a","b","c"]]
2 print arr[0],"\n"
3 print arr[4],"\n"
4 print arr[5],"\n"
5 print arr[-1],"\n"
6 print arr[4][1],"\n"
7 print arr[-1][-1],"\n"
| | 5.6 | What does the following program output?
1 arr1 = [1,2,4,9,16]
2 arr2 = [1,3,9,27,81]
3
4 puts arr1[2]+arr2[4]
5 puts arr1[0]+arr1[3]+arr[1]*2
6 puts arr1[arr2[1]]+arr2[arr1[arr1[1]]]
7 arr1[5]=arr2
8 puts arr1[5][2]
| | 5.7 | This code looks for the first two elements that are out of order
and swaps them. However, it is not producing the correct results. Fix the code so it works correctly.
1 arr = [5, 22, 29, 39, 19, 51, 78, 96, 84]
2 i = 0
3 while i
| |
| | 5.8 | Suppose you have 100 computers. You want to store the clock
speed (GHz), memory (GB) and brand for each computer.
How can you do this with a two dimensional array. Use Ruby
code to express 3 example entries.
| |
| | 5.9 | What does the following code do?
1 arr = [54,12,66,19,46,84,18,73,65,51,78,4,46,87,26]
2 i=1;
3 a=arr[0]
4 b=arr[0]
5
6 while(i<arr.size)
7 if(a>arr[i])
8 a=arr[i]
9 end
10 if(b<arr[i])
11 b=arr[i]
12 end
13 i=i+1
14 end
15
16 print "a: ",a,"\n"
17 print "b: ",b,"\n"
| | 5.10 | Suppose we want to create a list where seven digit phone
numbers serve as the index/key into an array/hash that holds
names. We are concerned about saving memory. Should we
use an array or a hash to store this data if the list contains
only 1% of all possible phone numbers? Does this answer
change if the list contains 90% of all possible phone numbers?
| |
| | 5.11 | Given six points in 3 dimensional space, write a program that
determines which two points are closest. The distance
formula is ((x1-x2)**2+(y1-y2)**2+(z1-z2)**2)**0.5, where
point 1 is [x1,y1,z1] and point 2 is [x2,y2,z2].
point_list = [[7,12,-6],[-5,6,-9],[3,8,15],[10,-8,0],[2,7,5],[-1,5,10]]
| | 5.12 | Determine the contents of the arr array after the first while
loop
1 arr = [0,12,25,76,35,17]
2
3 i=1
4 while(i0)
6 arr[i]=arr[i]-i
7 end
8 i+=1
9 end
| | 5.13 | Write a program that splits an array into two arrays where any
element in one array is smaller than any element in the other
array. Solutions are not unique, but equally sized splits are
desirable. The input can be any size array less than 100.
example input: [ 6, 45, 23, 65, 17, 48, 97, 32, 18, 9, 88 ]
example output: [ 6, 23, 17, 18 , 9 ] < [ 45, 65, 48, 97, 32, 88]
| | 5.14 | Create a program that that continually prompts for floats from
the user until float that is less than zero is entered. Store the
floats in an array, and find the median. (Remember, if there is
an even number of floats, the median is the average of the two
middle numbers).
| |
| | 5.15 | The following program tries to sum the numbers in the array,
and add the sum to end of the array, increasing the array's
length by one. However, there are several errors in the code.
Fix the code so that it is correct.
1 arr = [1,3,5,8,2,9,7,10,2]
2
3 i=1
4 sum=0
5
6 while (i<=arr.size)
7 sum=sum+arr[i]
8 end
9 arr[arr.size+1]=sum
| | 5.16 | There are many ways to store image data. One way is to store
pixel data in a two dimensional array. The pixel data is itself a
3 element array containing a number 0 to 255. This number
describes how much red, green, and blue is in the pixel. Here
are a few example RGB values:
[255,0,0] = red
[0,255,0] = green
[0,0,255] = blue
[0,0,0] = black
[255,255,255]=white
[255,255,0] = yellow
Suppose you have a picture and need to count red pixels. For
a pixel to be red, it must be within the following RGB
constraints:
1. The R value must be greater than 100
2. The G and B values must each be less than than the R value
divided by 4
sample = [[[ 65, 67, 23],[234,176, 0],[143, 0, 0]],
[[255, 30, 51],[156, 41, 38],[ 3,243,176]],
[[255,255,255],[ 0, 0, 0],[133, 28, 13]],
[[ 26, 43,255],[ 48, 2, 2],[ 57, 89,202]] ]
This sample has 3 red pixels.
| |
| | 5.17 | What will this code do?
1 arr = [-43, -5, 1, 6, 7, 13, 49, 51]
2
3 new_number = 8
4 i = arr.size
5 arr[i] = arr[i-1]
6
7 while ( new_number
| |
| | 5.18 | In the 1980s a motherboard could have used a chip called the
8:3 priority encoder to send signals to the processor from
peripheral devices. Basically, there are eight input lines and 3
output lines. The mapping from input to output is shown
below:
8 Inputs 3 Outputs
i7 i6 i5 i4 i3 i2 i1 i0 y2 y1 y0
1 X X X X X X X 1 1 1
0 1 X X X X X X 1 1 0
0 0 1 X X X X X 1 0 1
0 0 0 1 X X X X 1 0 0
0 0 0 0 1 X X X 0 1 1
0 0 0 0 0 1 X X 0 1 0
0 0 0 0 0 0 1 X 0 0 1
0 0 0 0 0 0 0 X 0 0 0
Each input and output can be binary 0 or 1. An 'X' under an
input means that the input can be 0 or 1 but still result in the
same output. For example, 00001000 and 00001011 both map
to 011 because 00001XXXX maps to 011. This chip is called
the priority encoder because it looks at the highest input to
determine the output. For instance, since i7 is the the highest
input, no other input can affect the output.
Write a program to simulate the above 8:3 priority encoder.
The program should analyze a 8 input bits and determine what
output they map to. Below are some example test cases, and
an example of what your code should output:
[i7, i6, i5, i4, i3, i2, i1, i0] => [y2, y1, y0]
[ 0, 0, 0, 1, 1, 0, 1, 0] => [ 1, 0, 0]
[ 0, 0, 0, 1, 0, 0, 0, 0] => [ 1, 0, 0]
[ 0, 1, 1, 1, 0, 1, 0, 1] => [ 1, 1, 0]
[ 0, 0, 0, 0, 0, 0, 0, 1] => [ 0, 0, 0]
| |
| | 5.19 | Function plotting software must calculate a function at many
points in order to plot it. Given the function:
f(x) = (x**4 + 17*x**3 - 416*x**2 - 612*x+2500)/500
a) Write a program that calculates and stores 100000 values for
f(x) between x=-50 and x=50
b) Add to the program code that searches for values for x that
are very close to, or are, zero. How many x values between
-50 and 50 make f(x) zero? What are they?
| |
| | 5.20 | Suppose we have two equations, y=3*x**3 and y=7-x**2
We know these two equations intersect somewhere between
x=0 and x=8.
a) Write a program that calculates and stores 10000 y values
for each equation between x=0 and x=5
b) Use the arrays found in part a to estimate where the
equations would intersect. What is the x and y value at the
point of intersection?
| |
| | 5.21 | To create a protein, nucleotide sequences in DNA or RNA are
translated into a sequence of amino acids. Triplets of
nucleotides, called codons, translate into one amino acid.
Below is the table that maps codons to amino acids. The
codon “CAG” is translated with the table below to the amino
acid “Gin.”
There are some simple rules to translation. The codon each
sequence starts with is AUG. There are three codons that the
sequence end with: UAG, UGA, or UAA. Write a computer
program that takes an array of nucleotides and translates it
into a sequence of amino acids. Use sample input and output
below to test you program.
codon_sequence = ["AUG", "ACU", "ACG", "GGU", "CUA",
"UGU", "GUU", "CAG", "GGG", "AGU", "UGU", "GGC", "UAA"]
amino_sequence = ["Met", "Thr", "Thr", "Gly", "Leu", "Cys",
"Val", "Gin", "Gly", "Ser", "Cys", "Gly", "Stop"]
| |
| | 5.22 | Do exercise 5.17 to prepare for this exercise. Suppose one is
not given a sequence of codons but is given a sequence of
nucleotides. Write a program that finds and outputs of all
possible protein sequences that could be translated from the
nucleotide sequence. Hint: Look for start and stop codons.
nucleotide_sequence = ["G", "C","A", "U", "G", "A", "C", "U",
"A", "C", "G", "G", "G", "U" ,"C" ,"U" ,"A" ,"U", "G", "U","G",
"U", "U", "C", "A", "G", "G", "G", "G","A", "G", "U", "A", "G",
"U", "G", "G", "C", "U", "A", "A"]
In the sample nucleotide sequence, two proteins should be
found.
| |
| | 5.23 | The three witches in Hamlet can brew any potion provided they
have the right ingredients. Suppose that there are five
ingredients necessary in making a health potion: eye of newt
(eon), toe of frog (tof), wool of bat (wob), adder's fork (af), and
tooth of wolf (tow). There are 4 reactions that can occur
between these incredients:
1. 4 eon + 2 wob = 3 af + 4 tow
2. 3 tow + 1 tof = 2 eon
3. 1 wob + 2 af = 1 tof
4. 4 tof + 7 tow + 2 af = 1 health potion
Assuming you can control the order of reactions, write a
program that can calculate the maximum number of health
potions one can brew with a given amount of ingredients.
Here is example output:
If I have 34 eon, 59 tof, 20 wob, 5 af and 20 tow, I can make 7
health potions.
| |
| | 5.24 | A scientist named Betty has been taking measurements of a
strange bacterial culture. For every hour, Betty has recorded
the area of the bacterial culture, and has stored these areas in
an array called data.
data=[8.72,10.44,13.39,16.01,15.97,19.71,20.47,23.25,25.80,27.82]
where the first reading of 8.72 was taken at t=0
and the last reading was at t=9
She predicts that the growth rate of the strange bacterial
culture is linear. Betty wishes to find an accurate linear
equation to model the growth. The linear equation is a
function of the hour and will define an array of modeled points
which will be stored in the model array:
model[t]=m*t+b
where model[] is the array in which the modeled points go
t is the hour
m and b are constants
The two constants, m and b, change the slope and intercept of
the line, respectively. Betty wishes find the values for m and b
that best predict the data. In order to test pairs of values for
m and b, Betty uses a least squares test. To find this, she
must perform the following algorithm:
Let sum=0
For each hour t
add the square of (model[t]-data[t]) to sum\
a) Given the data array, write a program that calculates the
least squares for these pairs of m and b: (m=2, b=8.72),
(m=1.5,9), and (m=1.75,b=8.75)
b) Of the three pairs, which pair best predicts the data? (which
pair yields the minimum result for the least squares
calculation?)
c) Modify the program to find and display the optimal linear
equation. Let the program find values for m and b that are
accurate to the hundredths place.
| |
| | 5.25 | Code a program that multiplies two matrices or any valid size
together. In case you are unfamiliar with matrix
multiplication, read the following explanation. Matrices are
two dimensional structures with i rows, and j columns (see
Figure 5.5 for an illustration). The matrix has i*j integer
elements. To access an element in the ith row and jth column
of matrix a, the standard notation would look like ai,j. In
Ruby, this would probably be coded as a[i][j].
To multiply two matrices, ai,j x bj,k = ci,k, matrix a must have i
rows, and j column while matrix b must have j rows and k
columns, where i, j, and k are any positive integer. The
resulting matrix c has i rows and k columns.
ci,k = ai,1*b1,k + ai,2*b2,k + ai,3*b3,k + . . . + ai,j*bj,k
Take the following
c1,2 = 4*1 +2*(-5) = -6
c3,1 = 7*7 + 3*9 = 76
| |
| | 5.26 | Consider a maze created with a 2-dimensional array. Write
code that walks from "s" to "f" inside this maze.
maze = [[ 1 , 1 , 1 , 1 , 1 , 1 , 1 ],
[ 1 , 0 , 1 , 0 , 0 , 0 ,"e"],
[ 1 , 0 , 1 , 1 , 0 , 1 , 1 ],
[ 1 , 0 , 0 , 0 , 0 , 0 , 1 ],
["s", 0 , 1 , 1 , 1 , 0 , 1 ],
[ 1 , 0 , 1 , 0 , 0 , 0 , 1 ],
[ 1 , 1 , 1 , 1 , 1 , 1 , 1 ]]
where: 1 indicates a wall
0 is a walkway
"s" is the start
"e" is the exit
| |
|
|
