1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
# Assignment 1 – choose ONE exercise each from Chapters 2 and 3
## Chapter 2: Exercises
1. Write pseudocode instructions to carry out each of the following
computational operations:
* Determine the area of a triangle given values for the base `b` and the height `h`.
* Compute the interest earned in 1 year given the starting account balance B
and the annual interest rate / and assuming simple interest, that is, no
compounding. Also determine the final balance at the end of the year.
* Determine the flying time between two cities given the mileage M between
them and the average speed of the airplane.
2. Using only the sequential operations described in Section 2.2.2, write an
algorithm that gets values for the starting account balance B, annual
interest rate I, and annual service charge S. Your algorithm should output
the amount of interest earned during the year and the final account balance
at the end of the year. Assume that interest is compounded monthly and the
service charge is deducted once, at the end of the year.
3. Using only the sequential operations described in Section 2.2.2, write an
algorithm that gets four numbers corresponding to scores received on three
semester tests and a final examination. Your algorithm should compute and
display the average of all four tests, weighting the final exam twice as
heavily as a regular test.
4. Write an algorithm that gets the price for item A plus the quantity
purchased. The algorithm prints the total cost, including 6% sales tax.
5. Write an if/then/else primitive to do each of the following operations:
* a. Compute and display the value `x / y` if the value of `y` is not `0`. if
`y` does have the value `0`, then display the message `Unable to perform the
division.`
* b. Compute the area and circumference of a circle given the radius `r` if
the radius is greater than or equal to `1.0`; otherwise, you should compute
only the circumference.
6. Modify the algorithm of Exercise 2 to include the annual service charge only
if the starting account balance at the beginning of the year is less than
$1,000. If it is greater than or equal to $1,000, then there is no annual
service charge.
7. Write an algorithm that uses the `loop` (1) to input 10 pairs of numbers,
where each pair represents the score of a football game with the Computer
State University (CSU) score listed first, and (2) for each pair of numbers,
determine whether CSU won or lost. After reading in these 10 pairs of values,
print out the won/lost/tie record of CSU. In addition, if this record is
perfect 10-0, then print out the message `Congratulations on your undefeated
season.`
8. Modify the test-averaging algorithm of Exercise 3 so that it reads in 15 test
scores rather than 4. There are 14 regular tests and a final examination,
which counts twice as much as a regular test. Use a loop to input and sume
the scores.
9. Modify the sales computation algorithm of Exercise 4 so that after finishing
the computation for one item, it starts on the computation for the next. This
iterative process is repeated until the total cost exceeds $1,000.
10. Write an algorithm that is given your electric meter readings (in
kilowatt-hours) at the beginning and end of each month of the year. The
algorithm determines your annual cost of electricity on the basis of a
charge of 6 cents per kilowatt-hour for the first 1,000 kilowatt-hours of
each month and 8 cents per kilowatt-hour beyond 1,000. After printing out
your total annual charge, the algorithm also determines whether you used
less than 500 kilowatt-hours for the entire year and, if so, prints out a
message thank you for conserving electricity.
11. Develop an algorithm to compute gross pay. The inputs of your algorithm are
the hours worked per week and the hourly pay rate. The rule for determining
gross pay is to pay the regular pay rate for all hours worked up to 40,
time-and-a-half for all hours over 40 up to 54, and double time for all
hours over 54. Compute and display the value for gross pay using this rule.
After displaying one value, ask the user whether he or she wants to do
another computation. Repeat the entire set of operations until the user says
no.
12. Develop a formal argument that "proves" that the sequential search algorithm
shown in Figure 2.13 cannot have an infinite loop; that is, prove that it
will always stop after a finite number of operations.
13. Modify the sequential search algorithm of Figure 2.13 so that it works
correctively even if the names in the directory are not unique, that is, if
the desired name occurs more than once. Your modified algorithm should find
every occurrence of NAME in the directory and print out the telephone number
corresponding to every match. In addition, after all the numbers have been
displayed, your algorithm should print out how many occurrences of NAME were
located. For example, if NAME occurred three times, the output of the
algorithm might look something like this:
528-5638
922-7874
488-2020
14. Use the Find Largest algorithm of Figure 2.14 to help you develop an
algorithm to find the median value in a list containing `N` unique numbers.
The median of `N` numbers is defined as the value in the list in which
approximately half the values are larger than it and half the values are
smaller than it. For example, consider the following list of seven number:
25, 50, 83, 44, 91, 20, 55
The median value is 50 because three values (20, 26, 44) are smaller and
three values (55, 83, and 91) are larger. if `N` is an even value, then the
number of values larger than the median will be one greater than the number
of values smaller than the median.
15. With regard to the Find Largest algorithm of Figure 2.14, if the numbers in
our list were not unique and therefore the largest number could occur more
than once, would the algorithm find the first occurrence? The last
occurrence? Every occurrence? Explain precisely how this algorithm would
behave when presented with this new condition.
16. On the sixth line of the Find Largest algorithm of Figure 2.14, there is an
instruction that reads, `while(i<=n) do`. Explain exactly what would happen
if we changed that instruction to read as follows:
* a. `while(i>=n) do`
* b. `while(i<n) do`
* c. `while(i==n) do`
17. On the seventh line of the Find Largest algorithm of Figure 2.14, there is
an instruction that reads `if A > largest so far then ...`. Explain exactly
what would happen if we changed that instruction to rea as follows:
* a. `if A >= largest so far then...`
* b. `if A < largest so far then...`
Looking back at your answers in Exercises 16 and 17, what do they say about
the importance of using the correct relational operations (<,==,>,>=,<=,!=)
when writing out either an iterative or conditional algorithmic primitive?
18. Refer to the pattern-matching algorithm in Figure 2.16.
* a. What is the output of the algorithm as it currently stands if our text is
`We must band together and handle adversity` and we search for `and`?
* b. How could we modify the algorithm so that it finds only the complete word
`and` rather than the occurrence of the character sequance `a`, `n` and `d`
that is contained within another word, such as `band`?
19. Refer to the pattern-matching algorithm in Figure 2.16. Explain how the
algorithm would behave if we accidentally ommitted the statement on Line 16
that says `Increment k by 1`.
20. Design an algorithm that is given a positive integer `N` and determines
whether `N` is a prime number, that is, not evenly divisible by any value
other than 1 and itself. The output of your algorithm is either the message
`not prime` along with a factor of `N`, or the message 'prime'.
21. Write an algorithm that generates a Caesar cipher - a secret message in
which each letter is replaced by the one that is `k` letters ahead of it in
the alphabet, in a circular fashion. For example, if `k = 5`, then the
letter `a` would be replaced by the letter `f`, and the letter `x` would be
replaced by the letter `c`. (We'll talk more about the Caesar cipher and
other encryption algorithms in Chapter 8.) The input to your algorithm is
the text to be encoded, ending with the special symbol `$`, and the value
`k`. (You may assume that, except for the special ending character, the text
contains only the 26 letters `a...z`.) The output of your algorithm is the
encoded text.
22. Design and implement an algorithm that is given as input an integer value `k
>= 0` and a list of `k` numbers `N1,N2,...,Nk`. Your algorithm should
reverse the order of the numbers in the list. That is, if the original list
contained:
`N1 = 5, N2 = 13, N3 = 8, N4 = 27, N5 = 10 (k = 5)` then when your algorithm
has completed, the values stored in the list will be:
`N1 = 10, N2 = 27, N3 = 8, N4 = 13, N5 = 5`.
23. Design and implement an algorithm that gets as input a list of `k` integer
values `N1, N2,...,Nk` as well as a special value `SUM`. Your algorithm must
locate a pair of values in the list `N` that sum to the value `SUM`. For
example, if your list of values is 3, 8, 13, 2, 17, 18, 10 and the value of
`SUM` is 20, then your algorithm would output either the two values (2, 18)
or (3, 17). If your algorithm cannot find any pair of values that sum to the
value.`SUM`, then it should print out the message `Sorry, there is no such
pair of values`.
24. Instead of reading in an entire list `N1, N2, ...` all at once, some
algorithms (depending on the task to be done) can read in only one element
at a time and process that single element completely before inputting the
next one. This can be a useful technique when the list is very big (e.g.,
billions of elements) and there might not be enough memory in the computer
to store it in its entirety. Wire an algorithm that reads in a sequence of
values `V >= 0`, one at a time, and computes the average of all the numbers.
You should stop the computation when you input a value of `V = -1`. Do not
include this negative value in your computations; it is not a piece of data
but only a marker to identify the end of the list.
25. Write an algorithm to read in a sequence of values `V >= 0`, one at a time,
and determine if the list contains at least one adjacent pair of values that
are identical. The end of the entire list is marked by the special value `V
= -1`. For example, if you were given the following input:
`14, 3, 7, 7, 9, 1, 804, 22, -1`.
the output of your algorithm should be a `Yes` because there is at least one
pair of adjacent numbers that are equal (the 7s). However, given the
following input: `14, 3, 7, 77, 9, 1, 804, 22, -1` the output of your
algorithm should be a `No` because there are no adjacent pairs that are
equal. You may assume in your solution that there are at least two numbers
in the list.
26. Modify the algorithm that you developed in Exercise 25 so that if there is a
pair of identical adjacent values, your algorithm also outputs, in addition
to the phrase `Yes`, the value of the identical numbers. So, given the first
list of numbers shown in Exercise 25, the output of your algorithm would be
something like `Yes, the numbers 7 and 7 are adjacent to each other in the
list`.
## Chapter 3: Exercises
21. Use the binary search algorithm to decide whether 35 is in the following
list: `3, 6, 7, 9, 12, 14, 18, 21, 22, 31, 43`
```ruby
def search(target, items)
return false if items.empty?
mid = items.size / 2
return true if items[mid] == target
return items[mid] > target ? items[0..mid] : items[mid+1..-1]
end
```
The comparisons are:
|
