Read sections 6.1-6.6 in chapter 6 of the textbook Explorations in Computing.
def print_sum(matrix)
sum = 0
for row in 0..matrix.length-1 do
for col in 0..matrix[row].length-1 do
sum = sum + matrix[row][col]
end
end
print sum, "\n"
end
Using this function as a guide, write a generalized function find_sub_sum(matrix,row_start,row_end, col_start, col_end) to return the sum of a sub matrix that is bounded by (row_start, col_start) and (row_end, col_end). Your function will return nil, if given arguments (row_begin, row_end, col_begin, col_end) are out of bounds. Assume that all rows in the matrix are of the same length. That is matrix[row].length is the same for all rows.
Here is an example of how find_sub_sum is called.
A = [[1,2,3,4],[5,6,7,8],[9,0,1,2]] find_sub_sum(A,0,1,0,1) returns 14 find_sub_sum(A,3,3,3,3) returns nil find_sub_sum(A,0,2,0,2) returns 34 find_sub_sum(A,1,2,1,2) returns 14
rpn = [23, 3, "-", 4, 6, "+", "/"]
Recall the algorithm to compute the value of a RPN expression using a stack:
1. Set i equal to 0.
2. Set x equal to rpn[i].
3. Set s equal to an empty stack.
4. While i is not equal to the length of the rpn array, do the following:
a. If x is a number, then push x on stack s.
b. If x is a string (i.e. operator), then do the following:
i. Pop stack s and store number in b.
ii. Pop stack s and store number in a.
iii. If operator is "+", push a+b on stack s.
iv. If operator is "-", push a-b on stack s.
v. If operator is "*", push a*b on stack s.
vi. If operator is "/", push a/b on stack s.
c. Add 1 to i and continue looping.
5. Pop stack s and return this number.
Trace how this algorithm computes the value of the following RPN expression stored as an array:
rpn = [2, 3, "*", 5, 4, "/", "-", 6, 9, "+", 7, "*", "+"]
(Draw a new stack whenever a number is pushed or popped, to show how the stack progresses throughout the computation. You can find an example in the lecture slides.)
Suppose we represent a queue using an array named q such that the first element in the array (at the index front) is the front of the queue and the last element in the array (at the index back) is at the rear of the queue. We also implement this queue using a bounded array. That is, the operator << cannot be used with this array to append elements to the end. We call this a circular array since when back reaches the last index of the array q.length-1, then back loops to index 0 element of the array. Here are some examples of enqueue and dequeue operations a sample queue q.
operation queue front back
[nil, nil, nil, nil, nil] -1 -1
enqueue(q,"me") ["me", nil, nil, nil, nil] 0 0
enqueue(q,"you") ["me", "you", nil, nil, nil] 0 1
dequeue(q) [nil, "you", nil, nil, nil] 1 1
enqueue(q,"him") [nil, "you","him", nil, nil] 1 2
enqueue(q,"her") [nil, "you","him", "her", nil] 1 3
dequeue(q) [nil, nil,"him", "her", nil] 2 3
enqueue(q,"me") [nil, nil,"him", "her", "me"] 2 4
enqueue(q,"dad") ["dad", nil ,"him", "her", "me"] 2 0
def h(string, table_size) k = ((string[0].ord)*26) + string[1] return k%table_size end
In the function above, string[i] returns the ASCII code of the ith character of string and the ord method gives its order in the alphabet. For lowercase letters, char.ord gives the relative position of the character in the ASCII table. For example "a".ord=0, "b".ord=1 etc. This is computed based on the ASCII codes for the lowercase letters given below and by subtracting 97 from each value. That is "a".ord = 97-97=0 and "b".ord=98-97=1 etc:
a b c d e f g h i j k l m 97 98 99 100 101 102 103 104 105 106 107 108 109 n o p q r s t u v w x y z 110 111 112 113 114 115 116 117 118 119 120 121 122