Miscellaneous Problems, HWK 11

IST 230

Frank Ritter

2 points total, 10 subpoints total

31/X/00, revised 19/XI/00

(1 points) p. 262 # 2, 4

doing #2 as a full example for sorting 97239485

Merge sort

97239485
(79)(23)(49)(58) (commas might appear as well)
(2379)(4589)
(23457899)

Quicksort

97239485
(7234859)(9)
((23457)(89))(9)
(((2)(3457))((8)(9)))(9)
(((2)((3)(547)))((8)(9)))(9)
(((2)((3)(45)(7)))((8)(9)))(9)
(((2)((3)((4)(5))(7)))((8)(9)))(9)

Note that nesting is necessary for keeping things really clear, but we did not require it.

(1 point) Apply bubblesort, quicksort and mergesort to you and your partners telephone number parts. This will give you a longer and more interesting list.

The answer will vary.

(1 point) Comment on how you think sorting feels for each algorithm, how they are the same and how they are different.

You might notice that quick sort has some setup time, that merge sort seems easy to do. That quick sort does poorly if the pivot does not work well. Bubblesort is fast if the list is nearly sorted and the algorithm is smart about checking it is done.

(1 subpoints) Banks will typically not tell you how much money is in someone's account, but will tell you if a check could be paid. Describe an algorithm for finding out how much money I have in the bank.

See the book p.257 for information on binary search. Use binary search starting at some reasonable number.

(2 subpoints) With your partner, play the guess the number game 10 times, each. (a) How long does it take, on average? (b) What was the worst case? (c) What are good numbers to choose if your partner is using a good strategy? (d) give a formula if you can for how long you might expect in the average case and in the best case and in the worst case.

It should take about log n time (worst case, slightly higher perhaps due to rounding) or better if you are lucky, lucky because you might get it on your first or second choice.

(1 subpoints) Do p. 270 # 2 & 4.

In order of addition of links, #2 (#4 is similar)

Kruskal's: 4,6,8,8,10

Prim's: (order varies on start) 8,4,10,6,8

(1 subpoints) When would Prim's and when would Kruskal's be easier to apply?

from p. 279. O(V lg V + E lg V) is Prim's complexity, and O(E lg E) is Kruskal's.

If there are a lot of nodes and not a lot of edges, then Kruskal's is faster (number of nodes don't figure in its calculations). If lots of edges, then Prim's.

(2 subpoints) (a) Apply Dijkstra's algorithm to the figure in problem 15, p. 271. (b) When would Dijkstra's algorithm work best? When would it work worst? (c) How could it be improved?

(a) The optimal answer is 27 (with links of 10,5,2,10). Some work must be shown for full credit.

(b) Works best when graph is simple, without paths that go to local minima and good paths that start out good compared to other paths. Negative links can cause troubles.

(c) If there are some directions that are known to be good (heuristics, or knowledge), this helps. If the best is answer is not needed but just a good one, then other algorithms can be used.