Home
Preface
Chapter Selection
Programming Examples
Homework Problems
Homework Solutions MEA's
Search Useful Links

Homework Solutions

Chapter 5 Homework Solutions

5.1 arr[9,2,5,4,3]
 
5.2 9
2
5
4
3
 
5.3 
i=0                   
while(i < arr.size)
	if(arr[i]>4)
		 puts arr[i];
	end
	i=i+1;
end
 
5.4 Three real-world applications for one-dimensional arrays: storing sensor data in regular time intervals, acting as set (store the set of users that have access to a certain file), and holding a list of tasks to that need to be schedules and completed.

Three real-world applications for multi-dimensional arrays: digital pictures can store pixels in a two-dimensional array, a spread sheet would have cells in a two dimensional array, the air pressure of a room can be modeled with a 3 dimensional array, where each cell in the 3 dimensional space is barometric pressure.
 
5.5 1
abc
nil
abc
b
c
 
5.6 85
14
90
9
 
5.7 Change lines 8 and 9 to: 
8.	temp=arr[i+1]
9.	arr[i+1]=arr[i]
10.	arr[i]=temp
 
5.8 Use a two dimensional array. Let the row number be the computer number, and the column index/key access the clock speed, memory and brand.
computers = [[3.2,2,"StarComp"],[4.0,4,"YPN"],[1.8,1,"CoolWare"]]
or, the information could be stored in a hash.
computers = [{"clock"=>3.2, "mem"=>2, "brand"=>"StarComp"},{"clock"=>4.0, "mem"=>4, "brand"=>"YPN"},{"clock"=>1.8, "mem"=>1, "brand"=>"CoolWare"}]
 
5.9 The variable a is the minimum integer in the arr array.
The variable b is the maximum integer in the arr array.
The programs prints the minimum and maximum numbers of the array
 
5.10 Actually, since Ruby uses completely associative arrays, either hash or array would cause no penalty. However, in many other programming languages, arrays are not associative and will have to allocate memory even if the array has no data in it. The following argument applies to these other programming languages.

For holding 1% of all the possible phone numbers, a hash should be used. This method saves space in comparison to the array because the array will store many nil entries between the few name entries. In hashes, there is no need to create keys in between other keys.

However, when the list contains 90% of all possible phone numbers, the array will save memory. The following is rough estimate for memory usage.

Assume phone numbers require 4 bytes Assume referencing a name object requires 4 bytes

array memory usage = 107 * 4 = 40 MB hashing 1% = 107 * (0.01) * 4 * 4 = 1.6 MB hashing 90% = 107 * (0.90) * 4 * 4 = 144 MB
 
5.11 
int_list = [[7,12,-6],[-5,6,-9],[3,8,15],[10,-8,0],[2,7,5],[-1,5,10]]
i=0
closest_distance= ((int_list[0][0]-int_list[1][0])**2+
                   (int_list[0][1]-int_list[1][1])**2+
                   (int_list[0][2]-int_list[1][2])**2)**0.5

point_a=0, point_b=1
while (i
 
5.12 arr = [ 0, 1, 1, 3, 2]
 
5.13 
input = [ 6, 45, 23, 65, 17, 48, 97, 32, 18, 9, 88 ]
i = 0
sum = 0
# use the mean to partion.  
# (median is obviously a better choice)
while(i < input.length)
    sum += input[i]
    i += 1
end
mean = sum/input.length
lower_half_array=[]
lower_half_index = 0
upper_half_array=[]
upper_half_index = 0
i = 0
while(i < input.length)
    if(input[i] < mean)
        lower_half_array[lower_half_index] = input[i]
        lower_half_index += 1
    else
        upper_half_array[upper_half_index] = input[i]
        upper_half_index += 1
    end
    i += 1
end
print "[ "
i = 0
while(i < lower_half_array.length)
    print lower_half_array[i]," "
    i +=1
end
print "]  <  [ "
i = 0
while(i < upper_half_array.length)
    print upper_half_array[i]," "
    i +=1
end
print "]\n"
 
5.14 
input=[]
# read in floats
i = 0
print "\nEnter a float: "
float = gets.to_f
while(float >= 0)
    input[i] = float
    i += 1
    print "\nEnter a float: "
    float = gets.to_f
end
#find median
input.sort()
median = -1
if(input.length%2 == 0)
    median = ((input[input.length/2].to_i+input[input.length/2-1].to_i)/2.0)
else
    median = input[input.length/2]
end
print "The median is : "
puts median
 
5.15 # indicates shows what the line was in the uncorrected code 
arr = [1,3,5,8,2,9,7,10,2]
i=0
    # i=1
sum=0
while (i
 
5.16 
Red=0
Green=1
Blue=2
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]]]
number_of_rows = sample.length
number_of_cols = sample[0].length
red_pixel_count=0
row=0
while(row 100 and
            sample[row][col][Red]/4 > sample[row][col][Green] and
            sample[row][col][Red]/4 > sample[row][col][Blue]  )
                red_pixel_count += 1
        end
        col += 1
    end
    row += 1
end
print "Number of red pixels: ", red_pixel_count,"\n"
 
5.17 It inserts a number into a sorted list
 
5.18 
	
Create a hash mapping from number to binary
map = {0=>[0,0,0], 1=>[0,0,1], 2=>[0,1,0], 3=>[0,1,1],
        4=>[1,0,0], 5=>[1,0,1], 6=>[1,1,0], 7=>[1,1,1],}
#Four test cases
test_cases = [  [ 0,  0,  0,  1,  1,  0,  1,  0],
                [ 0,  0,  0,  1,  0,  0,  0,  0],
                 [ 0,  1,  1,  1,  0,  1,  0,  1],
                 [ 0,  0,  0,  0,  0,  0,  0,  1] ] 
# the first high bit seen from the left
#  determines the output
case_number=0
while(case_number [ ",
            map[7-i][0],", ",
            map[7-i][1],", ",
            map[7-i][2]," ]\n"
    case_number+=1end
 
5.19 
A)
#we need 100000 locations
y = Array(100000)
i=0
# calculate y(x) for each i
x=-50
while(i<100000)
    x=-50.0 +(i/100000.0)*100.0
    y[i]=(x**4 + 17*x**3 - 416*x**2 - 612*x+2500)/50
    i+=1
end	

B)
# we need 100000 locations
y = Array(100000)
i=0
# calculate y(x) for each i
x=-50
while(i<100000)
    x=-50.0 +(i/100000.0)*100.0
    y[i]=(x**4 + 17*x**3 - 416*x**2 - 612*x+2500)/50
    i+=1
end
# find the zero values in y array
# how to define a zero?
# a good way is to find out when
#  y changes sign
is_positive = y[0] > 0
previous_is_positive = is_positive
i=1
while(i<100000)
    is_positive = y[i] > 0
    if( is_positive != previous_is_positive )
         #print the x that gets closest to zero
        if( y[i-1].abs < y[i].abs )
            print "zero at x=", -50.0 +((i-1)/100000.0)*100.0,"\n"
        else
            print "zero at x=", -50.0 +((i)/100000.0)*100.0,"\n"
        end
    end
    previous_is_positive = is_positive
    i += 1
end
 
5.20 
A)
# we need 10000 locations
#  and 2 arrays
STEPS= 10000
y1 = Array(STEPS)
y2 = Array(STEPS)
i=0
# calculate difference(x) for each i
x=0
while(i < STEPS)
    # need to multiply by 1.0 in order to find a float
    x=( 1.0*i/STEPS )*5.0
    # store 2 functions at x
    y1[i] = (3*x**3)
     y2[i] = (7-x**2)
    i+=1
end

B)
# we need 10000 locations
#  and 2 arrays
STEPS= 10000
y1 = Array(STEPS)
y2 = Array(STEPS)
i=0
# calculate difference(x) for each i
x=0
while(i < STEPS)
    # need to multiply by 1.0 in order to find a float
    x=( 1.0*i/STEPS )*5.0
    # store 2 functions at x 
   y1[i] = (3*x**3)
     y2[i] = (7-x**2)
    i+=1
end
# find the zero values in y array
# how to define a zero?
#  a good way is to find out when
#  the difference between y1(x)
#  and y2(x) changes sign
is_positive = (y1[0] - y2[0]) > 0
previous_is_positive = is_positive
i=1
while(i 0
    if( is_positive != previous_is_positive )
         #print the x that gets closest to zero
        if( (y1[i-1]-y2[i-1]).abs < (y1[i]-y2[i]).abs )
            print "intersection at x=",
                   (1.0*(i-1)/STEPS)*5.0,"\n"
        else
            print "intersection at x=",
                   (1.0*(i)/STEPS)*5.0,"\n"
        end
    end
    previous_is_positive = is_positive
    i += 1
end
 
5.21 
	
codon_sequence = ["AUG","ACU","ACG","GGU","CUA","UGU","GUU",
                  "CAG","GGG","AGU","UGU","GGC","UAA"]

# most of the work is done with this large hash map
map = { "UUU"=>"Phe", "UUC"=>"Phe", "UUA"=>"Leu", "UUG"=>"Leu",
        "UCU"=>"Ser", "UCC"=>"Ser", "UCA"=>"Ser", "UCG"=>"Ser",
        "UAU"=>"Tyr", "UAC"=>"Tyr", "UAA"=>"Stop", "UAG"=>"Stop",
        "UGU"=>"Cys", "UGC"=>"Cys", "UGA"=>"Stop", "UGG"=>"Trp",
        "CUU"=>"Leu", "CUC"=>"Leu", "CUA"=>"Leu", "CUG"=>"Leu",
        "CCU"=>"Pro", "CCC"=>"Pro", "CCA"=>"Pro", "CCG"=>"Pro",
        "CAU"=>"His", "CAC"=>"His", "CAA"=>"Gin", "CAG"=>"Gin",
        "CGU"=>"Arg", "CGC"=>"Arg", "CGA"=>"Arg", "CGG"=>"Arg",
        "AUU"=>"Ile", "AUC"=>"Ile", "AUA"=>"Ile", "AUG"=>"Met",
        "ACU"=>"Thr", "ACC"=>"Thr", "ACA"=>"Thr", "ACG"=>"Thr",
        "AAU"=>"Asn", "AAC"=>"Asn", "AAA"=>"Lys", "AAG"=>"Lys",
        "AGU"=>"Ser", "AGC"=>"Ser", "AGA"=>"Arg", "AGG"=>"Arg",
        "GUU"=>"Val", "GUC"=>"Val", "GUA"=>"Val", "GUG"=>"Val",
        "GCU"=>"Ala", "GCC"=>"Ala", "GCA"=>"Ala", "GCG"=>"Ala",
        "GAU"=>"Asp", "GAC"=>"Asp", "GAA"=>"Glu", "GAG"=>"Glu",
        "GGU"=>"Gly", "GGC"=>"Gly", "GGA"=>"Gly", "GGG"=>"Gly",
      }
# Map each element in the codon_sequence array
mapped_sequence = Array(codon_sequence.length)
i=0
while(i < codon_sequence.length)
    mapped_sequence[i] = map[codon_sequence[i]]
    i+=1
end
# print out mapped_sequence
print "["
j = 0
while(j < mapped_sequence.length)
    print " ",mapped_sequence[j]
    if( j+1 != mapped_sequence.length )
        print ","
    end
    j += 1
end
puts " ]"
 
5.22 
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" ]
# most of the work is done with this large hash map
map = { "UUU"=>"Phe", "UUC"=>"Phe", "UUA"=>"Leu", "UUG"=>"Leu",
          "UCU"=>"Ser", "UCC"=>"Ser", "UCA"=>"Ser", "UCG"=>"Ser",
        "UAU"=>"Tyr", "UAC"=>"Tyr", "UAA"=>"Stop", "UAG"=>"Stop",
        "UGU"=>"Cys", "UGC"=>"Cys", "UGA"=>"Stop", "UGG"=>"Trp",
        "CUU"=>"Leu", "CUC"=>"Leu", "CUA"=>"Leu", "CUG"=>"Leu",
          "CCU"=>"Pro", "CCC"=>"Pro", "CCA"=>"Pro", "CCG"=>"Pro",
        "CAU"=>"His", "CAC"=>"His", "CAA"=>"Gin", "CAG"=>"Gin",
        "CGU"=>"Arg", "CGC"=>"Arg", "CGA"=>"Arg", "CGG"=>"Arg",
        "AUU"=>"Ile", "AUC"=>"Ile", "AUA"=>"Ile", "AUG"=>"Met",
          "ACU"=>"Thr", "ACC"=>"Thr", "ACA"=>"Thr", "ACG"=>"Thr",
        "AAU"=>"Asn", "AAC"=>"Asn", "AAA"=>"Lys", "AAG"=>"Lys",
        "AGU"=>"Ser", "AGC"=>"Ser", "AGA"=>"Arg", "AGG"=>"Arg",
        "GUU"=>"Val", "GUC"=>"Val", "GUA"=>"Val", "GUG"=>"Val",
          "GCU"=>"Ala", "GCC"=>"Ala", "GCA"=>"Ala", "GCG"=>"Ala",
        "GAU"=>"Asp", "GAC"=>"Asp", "GAA"=>"Glu", "GAG"=>"Glu",
        "GGU"=>"Gly", "GGC"=>"Gly", "GGA"=>"Gly", "GGG"=>"Gly",
      }

# Evaluate the nucleotide sequence
#   at 3 offsets
offset=0
while(offset<3)
    # Map each element in the codon_sequence array
    mapped_sequence = Array(nucleotide_sequence.length/3)
    i=0
    while(i<(nucleotide_sequence.length-offset)/3)
        codon=nucleotide_sequence[3*i+offset]+
                nucleotide_sequence[3*i+1+offset]+
                nucleotide_sequence[3*i+2+offset]
        mapped_sequence[i] = map[codon]
        i+=1
    end
    # look through mapped_sequence
    #   for a start and stop
    i=0
    start=-1
    stop=-1
    while(i=0)
        while(i= 1 and start>=0 and stop>start)
        print "["
        j = start
        while(j <= stop)
            print " ",mapped_sequence[j]
            if( j+1 != stop +1 )
                print ","
            end
            j += 1
        end
        puts " ]"
    end
    offset+=1
end
 
5.23 
	
EON=0
TOF=1
WOB=2
AF=3
TOW=4
# create a reaction table
reactions = [   [-4, 0,-2, 3, 4],
                [ 2,-1, 0, 0,-3],
                [ 0, 1,-1,-2, 0],
                [ 0,-4, 0,-2,-7]  ]

# a simple hueristic will work
#  1) make an potion if possible
#  2) if not, what ingredient is needed?
#  3) try to increase that ingredient with 
#       a reaction.
#  4) Go back to 1 if TOF, AF and TOW are present
ingredients = [34, 59, 20, 5, 20 ]
potions = 0
last_brew=0
while(last_brew<30)
    i=0
    while(i<5)
        ingredients[i]+=reactions[3][i]
        i+=1
    end
    # if an ingredient is negative, we must use another reaction
    # which ingredient are negative?
    missing_TOF=false
    missing_AF=false
    missing_TOW=false
    missing_EON=false
    i=0
    if(ingredients[TOF]<0)
        missing_TOF=true
    end
    if(ingredients[AF]<0)
        missing_AF=true
    end
    if(ingredients[TOW]<0)
        missing_TOW=true
    end
        if(missing_TOF or missing_AF or missing_TOW)
        last_brew+=1
        #reverse the potion reaction
        i=0
        while(i<5)
            ingredients[i]-=reactions[3][i] 
            i+=1
        end
        if( missing_AF or missing_TOW )
            i=0
            if(ingredients[EON]>=4 and ingredients[WOB]>=2)
                while(i<5)
                    ingredients[i]+=reactions[0][i]
                    i+=1
                end
            else
                if(ingredients[EON]<4)
                    missing_EON=true
                end
            end
        end
        if( missing_EON )
            i=0
            if(ingredients[TOF]>=1 and ingredients[TOW]>=3)
                while(i<5)
                    ingredients[i]+=reactions[1][i]
                    i+=1
                end
            end
        end
        if( missing_TOF )
            i=0
            if(ingredients[WOB]>=1 and ingredients[AF]>=2)
                while(i<5)
                    ingredients[i]+=reactions[2][i]
                    i+=1
                end
             end
         end
             
    else
        # if ingredients are left, potion is made
         potions+=1
        last_brew=0
    end
end
print "The witches can brew ",potions," health potions.\n"
 
5.24 
A)
data=[8.72,10.44,13.39,16.01,15.97,

        19.71,20.47,23.25,25.80,27.82]



mb_pairs = [ [2, 8.72], [1.5, 9],

             [1.75, 8.75] ]

model = Array.new(mb_pairs.length)

i=0

while(i0.0000000000000001)

    # calculate model values

    #  for every m,b pair    

    pair = 0

    while(pair
 
5.25 
matrix_A=[[ 8, 4, 6],

          [10, 1,-1],

          [-6,-5, 3],

          [ 7, 7 ,99]]



matrix_B=[[ 2, 5,34, 1, 0],

          [19, 2, 7,-1,15],

          [ 6,-8, 7,-3, 1]]

# we have an i x j matrix and

#  j x k matrix, let's define 

#  these dimensions

i = matrix_A.length

j = matrix_A[0].length

if(j != matrix_B.length)

    puts "Cannot multiply these matrices."

    Process.exit
 # exits the program
end



k = matrix_B[0].length



# create an array to store

#  the result

result=Array(i)

row=0

while(row
 
5.26 The following algorithm uses bread crumbs to mark path we have already been on. Every time we move, we drop a bread crumb. We never move to places that have two bread crumbs. We prioritize moving the exit over moving to a walkway. We prefer moving to a walkway over moving to a walkway with a bread crumb.

The solution also animates the maze solving algorithm, by printing the maze. A "c" represents 1 crumb, an "X" represents 2 crumbs, and a "p" represents the current position in the maze. For fun, replace the exit with a wall to watch the algorithm traverse every path. 
#!/usr/bin/ruby

Wall=1

Path=0

Start="s"

End="e"

One_Crumb="c"

Two_Crumbs="X"



x = -1

y = -1



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 ]]

# find the start of the maze 



row=0

while(row < maze.length)

    col = 0

    while(col < maze[0].length)

        if(maze[row][col] == Start)

            x=row

            y=col

        end        

        col += 1

    end

    row += 1    

end



# enter the maze

if( maze[x-1][y] == Path ) # North

    x-=1

elsif( maze[x][y+1] == Path ) # East

    y+=1

elsif( maze[x+1][y] == Path ) # South

    x+=1

elsif( maze[x][y-1] == Path ) # West

    y-=1

end



while(maze[x][y] != End)

       if( maze[x-1][y] == End ) # North

        maze[x][y]=One_Crumb

        x-=1

    elsif( maze[x][y+1] == End ) # East

        maze[x][y]=One_Crumb

        y+=1

    elsif( maze[x+1][y] == End ) # South

        maze[x][y]=One_Crumb

        x+=1

    elsif( maze[x][y-1] == End ) # West

        maze[x][y]=One_Crumb

        y-=1





    elsif( maze[x-1][y] == Path ) # North

        maze[x][y]=One_Crumb

        x-=1

    elsif( maze[x][y+1] == Path ) # East

        maze[x][y]=One_Crumb

        y+=1

    elsif( maze[x+1][y] == Path ) # South

        maze[x][y]=One_Crumb

        x+=1

    elsif( maze[x][y-1] == Path ) # West

        maze[x][y]=One_Crumb

        y-=1





    elsif( maze[x-1][y] == One_Crumb ) # North

        maze[x][y]=Two_Crumbs

        x-=1        

    elsif( maze[x][y+1] == One_Crumb ) # East

        maze[x][y]=Two_Crumbs        

        y+=1        

    elsif( maze[x+1][y] == One_Crumb ) # South        

        maze[x][y]=Two_Crumbs

        x+=1

    elsif( maze[x][y-1] == One_Crumb ) # West

        maze[x][y]=Two_Crumbs

        y-=1

    end



row=0

while(row < maze.length)

    print "["

    col = 0

    while(col < maze[row].length)

        if (col==y and row==x)        

            print " p"

        else

            print " ",maze[row][col]

        end

        if( col+1 != maze[row].length )

            print ","

        end

        col += 1

    end

    row+=1

    puts " ]"

end

puts "------------------------"

sleep(0.5)



end



puts "maze complete"