Key Concepts in Computer Science -Assignment 8

1) [8 marks] Describe an algorithm that uses only assignment statements that replaces the triple (x; y; z) with (y; z; x).
t := z
x := y
y := z
z := t
(where t is a temporary variable)
2) [10 marks] List all the steps used to search for 9 in the sequence 1, 3, 4, 5, 6, 8, 9, 11 using
a) a linear search
we check whether 9 is equal to these numbers: 1, 3, 4, 5, 6, 8, 9. As soon as we hit 9, we find the answer and the search is stopped.
b) a binary search
First, we search the entire list and compare 9 with 5.
Since 9 > 5, we search list 6, 8, 9, 11 and compare 9 with 8.
Since 9 > 8, we search list 9, 11 and compare 9 with 9.
Since 9 ≯ 9, we search list 9 and then i ≮ j and we finish the search.
3) [12 marks] Describe an algorithm that takes as input a list of n integers and produces as output the largest difference obtained by subtracting an integer in the list from the one following it.
Example: input: L = [1, 4, 2, 20, 24] output = 18 (20 – 2)
procedure largestDiff(a1…an: integers)
answer   -∞
for i   1 to n-1
if (ai+1 – ai answer then
answer   ai+1 – ai
return answer
4) [10 marks] Apply greedy algorithm to make change using quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent) for:
a) 24 cents
2 dimes, 4 pennies
b) 261 cents
10 quarters, 1 dime, 1 penny
5) [10 marks] Apply greedy algorithm to make change using quarters (25 cents), dimes (10 cents), and pennies (1 cent) for:
a) 32 cents
1 quarter, 7 pennies
b) 148 cents
5 quarter, 2 dimes, 3 pennies
6) Bonus Question [25 marks]
A checkerboard has a certain number of coins on it.
A robot starts in the upper-left corner, and walks to the bottom left-hand corner.
The robot can only move in two directions: right and down.
The robot collects coins as it goes.
You want to collect all the coins using the minimum number of robots.
Do you see a greedy algorithm for doing this?
Does the algorithm guarantee an optimal solution?
Can you prove it or find a counterexample?
Solution: See https://pdfs.semanticscholar.org/34ea/88796979721646982545a2e2dc72100a1b8e.pdf
Let’s Solve… Gold Collection (by Eugene Wallingford)
You are taken to a room with an nxm-square foot floor. Gold coins are spread throughout the room, with at most one per square foot. For example:
You want those coins! Serendipitously, you have a set of robots that can pick up a gold coin in any cells they visit. Unfortunately:
 Each robot can move in only two directions, down and to the right.
 Robots are are expensive to operate.
Design an algorithm to determine the smallest number of robots you will need to retrieve all of the coins. Your algorithm should take as input
 the room dimensions, n and m, and
 a list of the locations of the cells that contain gold coins.
For our example layout above, the inputs would be:
7 8 # a 7×8 room
2 6 #
3 2 #
3 8 #
4 3 # a list of x y coordinates
4 5 # for the ten gold coins,
5 2 # with 1 1 being
5 5 # the upper left corner
6 8 #
7 5 #
7 6 #
Quick Question: What is the correct output for this example board? (3).
It may be difficult to code your algorithm in full detail at this point. It’s okay if you can only describe it at a high level. Just be sure that someone else in the class can understand your idea.
Hint: Try your algorithm on some simple cases first. What are some problematic layouts, given our robots limits? How well does your algorithm handle them? Look for disconfirmatory evidence — evidence that shows your idea doesn’t work!
Gold Collection: Debrief
Quick Question: What sort of real-world problems does this puzzle model?
( A current example: fixing the Hubble space telescope. )
What did you discover? Does generalizing the problem to allow multiple coins per cell affect your solution?
How might we represent this problem?
 We could use a two-dimensional array. An algorithm might then walks rows and columns, incrementing indices, and clearing non-zero cells.
 We could use as a graph. The algorithm then might walk paths from source to sink, removing nodes and links.
Are there any regularities in the problem that we can use to find an optimal solution? What design techniques, such as dynamic programming, can we use to solve the problem?
One intuition: greed. We could try to maximize the number of coins collected by each robot. Let the first robot grab as many coins as possible, then let a second do the same, and so on, until all of the coins are taken.
Unfortunately, no. An especially strong harvest by one robot can divide the remaining gold-containing cells into disjoint regions. Consider this example:
A maximal first robot will garner seven coins, from row 3 and then column eight. The remaining four coins require two robots, for a total of three. However, two robots are enough in this case. (Do you see it?)
Can we salvage the greedy approach by handling this as a special case? Maybe, but are there other special cases to consider? Maybe greed doesn’t pay here…
Let’s try a new idea, based on the second example. Have each robot peel off the leftmost strip of coin-containing cells, like peeling the layers of an onion.
In the second example, the optimal solution is to grab the first three coins from row 3, the two coins from row 5, and (optionally) the coin in row 7. Notice the decision point at (3,4). Both simplicity (“Don’t change directions with gold ahead!”) and greed (“Grab as many coins you can!”) would send the robot further down row 3, but both result in a bad split of the remaining coins.
This new approach is optimal. How can we justify the claim? The underlying regularity involves disjoint cells.
 Two occupied cells are disjoint if one is below and to the left of the other. In our first example, the coins in (4, 3) and (5, 2) are disjoint.
 Given our restriction on robot moves, disjoint cells require separate robots.
 By peeling the leftmost layers of cells from the grid with a single robot, we never leave disjoint cells!
 We can find the optimal number of robots by computing the length of the longest chain of disjoint cells.
In the first example above, the longest such chain is (2, 6) → (4, 3) or (4, 5) → (5,2), so we need three robots.
In the second example, the longest such chain is of size 2; there are several. But even with many chains of size 2, we need only 2 robots!
Greed doesn’t always pay. The problem is that, in general, there is no good way to know in advance. So we we shouldn’t settle for our first solution if we prefer better results than it provides.
Don’t let your intuitions lead you astray. Don’t settle for the first idea you come up with. That doesn’t mean that you cannot be creative… Make analogies. Operate as if they are correct. Tinker to improve. But work with lots of examples. And, most important, try to prove your theory wrong. Algorithm design works a lot like science