CompSci 18S - Fall 2007 - Sorting (ginorst)

Classwork: Group Writeup (10 pts)

I. Algorithm: Making S'mores

You are given a box of graham crackers, a jar of nutella spread, a jar of Jet-Puffed Marshmellow Creme, two knifes and a plate. Write an algorithm, a set of precise instructions, for making a S'more, a sandwich of graham crackers with nutella and marshmellow creme.

II. Algorithm: Sorting words

• Sorting a list of approximately 100 words.
• Developing and writing down an algorithm that others can use to sort a list of words.
• Answering questions about the words.

Part 1. Sorting the Words

Your group will be given approximately 100 words. You are to sort them into alphabetical order. You should arrange the words in such a way that your group can answer questions such as

• What is the third word alphabetically?
• What is the third to last word alphabetically?
• How many words are there?
• Is a certain word in the list of words?

The success of your work will be judged on whether you can correctly answer most of these questions. There is nothing to writeup for this part.

Note: There is nothing to write down for this part.

Part 2. Specifying an Algorithm

Each group must prepare one write-up as described below Be sure that each group member's name (first and last name) is on the write-up.

You are to write an explanation of how to sort a list of words. Assume that the number of words isn't known in advance, but will be between 10 and 600. You are to write an algorithm in English that specifies precisely how to sort the words. Consider that another group might use your algorithm, and following the instructions literally. This means that you must convey exactly what steps to follow.

Saying "put in alphabetical order" is too vague. The end result is alphabetical order, but which "algorithm" or method should you use to put them in this order. There are lots of words. How do you organize them?

Part 3. Questions

1. You can refuse to answer one of the questions below. The questions refer to the "sorted" list of words.
   1. How many words begin with the letter 'm'?
   2. What is the last word with a double letter (e.g., ``jello'')?
   3. How many words are there?
   4. Is the word "preternatural" in the list of words?
   5. How many words end in the letter 's'?
   6. How many words begin with a vowel?
   7. What is the 66th word?
   8. What is the 13th word?
   9. How many words contain the word "her" in them?
   10. What is the group's favorite word?
   11. What is the 100th word?
2. Did you refuse to answer 1 of the above questions. Why?
3. Did you organize the words in any special order besides just sorted to answer the questions above? Explain.

Assignment 4 (10 pts)

If you have time in class you can discuss these in your group, but each of you should write this part up individually to turn in (the writeup should be your own).