This is an open book, open notes, and open computer test. You may not use any books other than your textbook, and you may not use Internet resources from off campus. If you get stuck, talk to Jeff Ondich. Don't talk to anyone else.

1. (10 points) Write a recursive procedure that will print out the integers between 1 and N in reverse order. N should be passed as a parameter to your procedure.
   
   
2. (10 points) I have N numbers stored in an array a[], and I want to know the distance between the pair of these numbers that are furthest apart. Elmo suggests the following code, which does the job:

   
   	max := 0;
   	for i := 1 to N do
   	begin
   		for j := 1 to N do
   		begin
   			if a[i] - a[j] > max then
   				max := a[i] - a[j]
   		end
   	end
   

   • When I used Elmo's code on N = 5000 numbers, the program took 1.4 seconds (I tried it several times--1.4 seconds every time). Approximately how long will Elmo's code take to run if N = 25000 (assuming I use the same computer)? Justify your answer.
   • Zoe says she thinks Elmo's code is stupid. For 6 points extra credit, write some code that is significantly faster than Elmo's, and explain why it's faster.
   
   
   
3. (10 points) One day in class, I showed you a program that computed N! ("N factorial") for given values of N. (Recall that N! = N*(N-1)*...*2*1). I tried several values of N, and the program showed us 3! = 6, 4! = 24, etc. Then I tried 50!, and the answer was 0. As I recall, I said something to the effect of "I know why it did that, but I don't want to tell you right now." Well, now I feel like telling you. Or, rather, I feel like asking you to figure it out.

   Below is a program that prints out N! for all values of N between 1 and 50. Run it, and then answer the questions that follow.

   
   program factorials(input,output);
   const	top = 50;
   var		k : integer;
   
   function factorial( n : integer ) : integer;
   begin
   	if n <= 1 then
   		factorial := 1
   	else
   		factorial := factorial( n - 1 ) * n
   end;
   
   begin
   	for k := 1 to top do
   		writeln( k, '! = ', factorial( k ) )
   end.
   

   • For what integer J is J! first reported as a negative number?
   • For what integer K is K! first reported as 0?
   • In base ten, what are the correct values of J! and K!?
   • What are the base two expressions of the correct values of J! and K!?
   • Use your binary expressions of J! and K! to explain why the computer seems to think J! is negative and K! is 0.
   
   
   
4. (10 points) Suppose I told you the following routines were built into Pascal:

   
   {==================================================
       Returns true if the given word is an English
       word, and false otherwise.
    ==================================================}
   function IsInDictionary( word : string ) : boolean;
   
   
   {==================================================
       Returns the next word from standard input
       in the variable parameter "word".
    ==================================================}
   procedure ReadWord( var word : string );
   

   Using these routines, write a main program that takes input from a file in our usual way (using "<" on the command line), and prints out all the words in the file that are misspelled--that is, all the words that do not appear in the dictionary.

   Note that you should NOT try to write IsInDictionary or ReadWord.
   
   

5. (15 points) On my office door you can find a list of several rearrangements of my name (Jeffrey Robert Ondich), including my favorite, "Fjord Conifer Thereby." The search for such "anagrams" has been an obsession of word-lovers for centuries. Since early in the computer age, this search has been a popular computer application.

   One approach to the search for anagrams is to list all possible rearrangements (also known as "permutations") of the word or words in question, after which the permutations can be looked up in the dictionary. For example, the six permutations of the letters in "TEA" are "AET," "ATE," "EAT," "ETA," "TAE," and "TEA," five of which appear in the Official Scrabble Players' Dictionary.

   Suppose you wanted to generate all the permutations of the word "BREAD". You could approach the task like so:

   	Generate all permutations that start with B
   	Generate all permutations that start with R
   	Generate all permutations that start with E
   	Generate all permutations that start with A
   	Generate all permutations that start with D
   

   How would you go about doing that first step? Well, you might do the following:

   	B followed by all permutations of READ starting with R
   	B followed by all permutations of READ starting with E
   	B followed by all permutations of READ starting with A
   	B followed by all permutations of READ starting with D
   

   If this looks recursive to you, good.

   Here are your tasks.

   • Write a procedure that will take a string parameter and print out all the permutations of the characters in the string. I recommend the following interface:

     {==================================================
         Permute prints out all the permutations of the
         character string s in which s[1],...,s[index] are
         fixed.
      ==================================================}
     procedure Permute( s : string; index : integer );
     

     You can, of course, use the built-in function length that returns the length of a string. Also, if you use the above interface, you'll want to call it initially with index = 0, like this: Permute('BREAD',0).
   • How many permutations does an N-letter word have?
   • If my computer can print out 10,000 lines per second, how long would it take to print out all the permutations of JEFFREYROBERTONDICH?