INT102 Algorithmic Foundations
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
INT102 Algorithmic Foundations
Problem Session 1, Week 2
1. Give the trace table and the output of the following algorithm for m = 16.
input m
count = 0
x = 1
while x < m do
begin
x = x ∗ 2
count = count + 1
end
output count
What is the output for general m that is a positive power of 2 (i.e., m = 2, 4, 8, 16, 32, . . .)?
2. Rewrite the following for-loop into a while loop. input m
x = 0
for i = 1 to m do
begin
x = x + i
end
output x
3. Rewrite the above for-loop into a repeat loop.
4. List the following functions from lowest order to highest order of magnitude:
O(1), O(n2), O(n3), O(n), O(log n), O(log2 n), O(n log n), O(√
), O(n2 log4 n),
O(n3/2), O(n10/3), O(n4).
5. Prove that the functionf(n) = 3n2logn + 2n3 + 3n2 + 4n is O(n3).
(That is, show that there exists constants c and n0 such that f (n) ≤ cn3
for all n > n0 .)
6. Consider a string T of n characters T[0..(n- 1)]. Design and write a pseudo code of an algorithm to determine if a given character, denoted by C, appears uniquely in T [0..(n- 1)], i.e., whether the character C appears exactly once in T.
For example, if T [ ] is “Hello, how are you?" and C is `H', then the algorithm should report “Yes, the character appears uniquely.". However, if C is `e', then the algorithm should report “No, the character does not appear uniquely.
Problems for Fun (Optional):
1. [Puzzle] A farmer is standing on the left side of the river and with him are a wolf, a goat and a box of cabbages. In the river there is a small boat. The farmer wants to cross the river with all the three items that are with him. There are no bridges and in the boat there is only room for the farmer and one item. If he leaves the goat with the cabbages alone on one side of the river the goat will eat the cabbages. If he leaves the wolf and the goat on one side the wolf will eat the goat. How can the farmer cross the river with all three items, without one eating the other?
2. [Puzzle] Four people are going to cross a bridge from the same side. It is
night and they have only one flashlight. At each time there can be at most two people crossing the bridge. Any party that crosses the bridge, either one or two people, must have a flashlight to walk with them. The flashlight must be walked back and forth and cannot be thrown, for example. Each person walks at a different speed: person A takes 1 minute to cross the bridge, person B 2 minutes, person C 5 minutes and person D 10 minutes. A pair must walk together at the rate of the slower person’s pace. For example, if person A and person D walk together, it takes 10 minutes to get to the other side of the bridge.
How can they arrive the other side of the bridge in the shortest time? How
many minutes does this take?
3. [Puzzle] Twelve eggs look identical except one is of different weight (can be heavier or lighter). How can you weigh only four times on a balance scale to find out which one is different and whether it is heavier and lighter?
2022-05-27