Read chapters 3-6 of the textbook Explorations in Computing.
def search(list, key)
index = 0
while index != list.length do
if list[index] == key then
return index
end
index = index + 1
end
return nil
end
Suppose that we know the additional fact that the list is sorted in decreasing order (this means that list[i] > list[i+1], for 0 ≤ i < list.length-1). For example, if our list has the values:
[94, 82, 79, 73, 61, 45, 37, 25]
then if we want to search for the key 70 using linear search, we can stop when we reach 61 and return nil (assuming that the list is sorted).
def sorted?(list) end
HINT: Set up a for loop to compare list[i] with list[i+1]. If you ever get two neighboring elements that are not in decreasing order, then the whole list cannot be sorted. Be careful with the range you use for i.
Here is an implementation of binary search in Ruby using iteration:
def bsearch(list, key)
min = 0
max = list.length-1
while min <= max do
mid = (min+max)/2
return mid if list[mid] == key
if key > list[mid] then
min = mid + 1
else
max = mid - 1
end
end
return nil
end
Let list = [4, 10, 12, 16, 21, 24, 30, 33, 46, 58, 60, 72, 73, 85, 96].
min max -------------- 0 14
min max -------------- 0 14
min max -------------- 0 14
For example, if we call sum_positive(5), then the function should return the value 15 since 1 + 2 + 3 + 4 + 5 = 15.
HINT: The solution is similar to the factorial function we did in class.
def f(n) if n == 0 or n == 1 or n == 2 then return n else return f(n-3) + f(n/3) end end
Trace the computation of f(9) by drawing a recursion tree (like the one we drew for Fibonacci numbers), showing all of the recursive computations that need to be computed to find the value for f(9). Then using your recursion tree, compute the value of f(9).
In Ruby, in addition to non-negative indices, you can use negative index values when accessing array elements. These count backwards from the end of an array with -1 being an index for the last element in an array. The range notation for obtaining sub-arrays can also use negative elements or a mix of positive and negative elements. For example:
>> a = ["v", "w", "x", "y", "z"] => ["v", "w", "x", "y", "z"] >> a[-1] => "z" >> a[-2] => "y" >> a[-3] => "x" >> a[-3..-1] => ["x", "y", "z"] >> a[1..-3] => ["w", "x"]
If we refer to integers whose 1's digit is 3 (3, 13, 23, 33, etc.) as "3-ending", then a recursive algorithm that takes a list of positive integers and counts the number of "3-ending" integers in that list can be described as follows:
If the list is empty, then the number of "3-ending" integers is 0. Otherwise, if the last element of the list is not "3-ending", then the number of "3-ending" integers in the list is the number of "3-ending" integers in the list without the last element. Otherwise (the last element of the list must be "3-ending"), the number of "3-ending" integers in the list is 1 plus the number of "3-ending" integers in the list without the last element.
Complete the Ruby function below to perform this computation recursively using the algorithm above:
def count3ending(list) if ________________________ then return 0 end if ____________________________________ then return ___________________________________ else return 1 + ____________________________________ end end
[Added 2/22] Hint: you may want to use negative indices to obtain an array with all of the elements of list except the last element.
Merge Sort Algorithm:
1. Sort the first half of the array using merge sort.
2. Sort the second half of the array using merge sort.
3. Merge the two sorted halves to get a sorted array.
Algorithm 1: Songs are stored in the computer's memory in arbitrary order. Each song has a code that indicates the location in memory of the song that plays next. The player keeps track of the location of the first song in the playback sequence only.Algorithm 2: Songs are stored in the computer's memory in the order of playback starting at a specific fixed location in computer memory which cannot be changed.
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.
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 = [7, 3, "+", 4, 2, "-", "*", 8, 2, "/", 1, "+", "/"]
(Draw a new stack whenever a number is pushed or popped to show how the stack progresses throughout the computation.)
Suppose we represent a queue using an array named q such that the first element in the array (at index 0) is the front of the queue and the last element in the array (at index q.length-1) is the rear of the queue.
def h(string, table_size)
k = 0
for i in 0..string.length-1 do
k = string[i] + k * 256
end
return k % table_size
end
In the function above, string[i] returns the ASCII code of the ith character of string. Here are the ASCII codes for the lowercase letters:
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
59 24 35 78 61 42 90 88 15 57
66 22 81 23 50 73 39 33 42
NOTE: For this problem, you will probably need to show the max-heap after each individual element is inserted so you don't get lost.