Miscellaneous Problems, HWK 11

IST 230

Frank Ritter

2 points total, 15 subpoints total

31/X/00

(1 points) p. 262 # 2, 4

(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. That is,

217 333 2000 (my mom)

814 865 4453 (me)

So sort:

217

333

2000

814

865

4453

and my partners.....

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

(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.

(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.

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

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

(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?