CompSci 18S - Sorting - Fall 2009

CompSci 18S - Fall 2009 - Sorting (ginorst)


September 7, 2009
Classwork 3: 10 points, Assignment 3: 10 points


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

There are three parts to this activity:

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

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

The answers to these questions should also be on your group writeup.

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

  • This assignment should be turned in the next class period.

    1. Now that you have your words sorted, suppose you are handed another envelope of different words that are not sorted. Describe an algorithm for creating a new list of words in sorted order using your sorted words and this new envelope of words.

    2. Now that you have your words sorted, suppose you are handed another envelope of different words that are already in sorted order. Describe an algorithm for creating a new list of words in sorted order using your sorted words and this new envelope of sorted words.

    3. Consider that you are given a large number of 8-digit numbers and you want to put them in sorted order (from smallest to largest). Will the algorithm you came up with in class for sorting words work also with 8-digit numbers?