Advanced Search
All Posts : Education
I would like to see solutions to Exercise 7 at the end of Chapter 6 in the 2007 edition of the Maple 11 Introductory Programming Guide. It's on page 255. The exercise reads as follows: “Demonstrate that the BinarySearch procedure always terminates.” “Hint: Suppose the dictionary has n entries. How many words in the dictionary D does BinarySearch look at in the worst case?” My solution (I’m a Maple novice and I’m reading the book.) is: View 4937_Chapter6Exercise7.mw on MapleNet or Download 4937_Chapter6Exercise7.mw
View file details The lengths of most of the test dictionaries are powers of two. The dictionaries are utterly without diversity. The dictionaries are minimizing. Is there a better test set? The exercise says “demonstrate”. Would a proof solve the problem? Does anyone have a pointer to such a proof? Does such a proof have anything to do with the halting problem?

Please Wait...