Page 2: How Many Five-Letter Words Are There?

Unit 5, Lab 1, Page 2

TG and solutions need to be checked. –MF, 12/19/18

On this page, you will see how long it takes to run a linear search algorithm.

On Unit 2 Lab 3 Page 6: Solving a Word Puzzle, you built a does () have () letters? block and used it with keep to find words of a specific length in a word list. How long does a process like that take?

  1. Click here to load this file. Then save it to your Snap! account.

    This project provides the variables 1,000 words, 10,000 words, and 100,000 words (each containing a list of words) and a copy of the does () have () letters? predicate.

  2. How many five-letter words are in the 10,000 words list?
  3. Use the computation time of 'grey ring input slot' block provided in this project to determine how long it takes for the computer to answer that question.

The computation time block takes any reporter (with its inputs filled in), computes the result but ignores it, and instead reports how long it took to do the computation (in milliseconds).
computation time of (numbers from (1) to (1000)) reporting 27

In this example, it took 27 milliseconds to compute the list of integers from 1 to 1000. (The report you see will depend on how fast your computer is and what other programs are running on it.)

You can look inside computation time to see how it works: Right-click (or control-click on a mac) the block and select “edit…” from the menu that appears.

  1. Click on the computation time expression you just used to answer the previous question three more times and note the range of answers. They’re not exactly the same because of other things that your computer is doing at the same time, so you should always take whatever result it gives you as approximate.
  2. Talk with Your Partner How long do you think it would take to count five-letter words if the list had 100,000 words?
  3. Use computation time to check using the 100,000 words list.

Searching for all the five-letter words in a specific word list is an instance of a more general problem: searching for all the words of any particular length.

: Problem and Instance of a Problem

AAP-4.A.1

  • A problem is a general description of a task that may (or may not) be solved algorithmically.
  • An instance of a problem is one case of a problem, with specific inputs.

  1. Suppose instead, we count the seven-letter words. Will this take… Write Out Your Thoughts

    1. More time because seven letters is more than five letters?
    2. Less time because there are fewer seven-letter words than five-letter words?
    3. The same time because it’s not the word length that matters; it’s the size of the dictionary?

    I was thrown off by the format of this exercise and rephrased it as a question. –MF, 5/31/20

    Should this maybe be a quizlet? Not sure… –MF, 7/13/20

  2. Experiment to find out for sure.

The only way to answer a “How many words…” problem is to check every single word in the dictionary. So if you have ten times as many words in the dictionary, it takes ten times as long to check them all.

: Linear Search or Sequential Search

  • An algorithm takes linear time if multiplying the input size by ten multiplies the time required by ten.
    graph of size vs. time showing a straight line through the origin and up to the right with the points for x=10,000 and x=100,000 marked

    • AAP-2.O.5

  • A linear search (or sequential search) algorithm checks each element of a list in order, a process which takes linear time.