CS46A Lab

Designing Algorithms

Copyright © Cay S. Horstmann 2010 Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.

The purpose of this lab is to practice designing algorithms. You will gain experience in

A. Getting only the vowels / Using physical objects

  1. Your goal is to write a method getVowels that returns all vowels of a string. For example, new Word("monopoly").getVowels() should return the string "oooy". Your method should be a part of this Word class.

    It is useful to think about “building blocks”, snippets of code that may help you attack this problem. Here are a few:

    1. Extracting the ith character of a string (or, more accurately, a string containing the ith character)
      String ch = str.substring(i, i + 1); 
    2. Looping over all characters in a string
      for (int i = 0; i < str.length(); i++)
      {
         ...
      }
    3. Adding a character to a string (you didn't see this in the previous lab)
      result = result + ch;
    4. Checking whether two strings are equal
      if (str1.equals(str2)) ...
    5. Checking whether a letter is a vowel
      if (isVowel(ch)) ...

      This method was given to you in the previous lab, and you will also want to use it in this lab.

    6. Checking whether a letter isn't a vowel
      if (!isVowel(ch)) ...

    Discuss with your lab partner which of these could be helpful for solving your task. Scribe: Record the  consensus--just list the building blocks that you think you'll be using (a, b, etc.), not your rationale.

  2. Now you need to come up with a plan, where you loop through the letters, look for vowels, and do something with them. The end goal is to come up with pseudocode, but how do you get there? You first need an idea.

    One way of developing ideas is to simulate the process with physical objects such as Scrabble tiles and paper clips (to indicate a current position).

    Try this with your partner. Get some tiles that spell a word with at least two vowels. Put a paper clip at the first letter to indicate the current loop index.

    Move the paper clip to the first letter, then the second letter, etc. Each time, decide what to do with the letter. If you decide to add it to another string, just move it.

    If anyone gets confused what is happening, start over.

  3. After you have a shared understanding how to simulate the algorithm with the tiles and paperclip, jointly develop the pseudocode (mixture of Java and English), just like in the previous lab.

    Caution: In the Word class, the string in question is stored in an instance variable text. You should use text, not str, when you write down your pseudocode.

    Scribe: Once the group agrees on the pseudocode, type a copy into the lab report.

  4. Now we'll use the tiles and paperclip one more time to test the pseudocode. The scribe directs the driver, reading one instruction at a time from the pseudocode. The driver moves the letters and paperclip as appropriate.
  5. When you do this simulation, the vowels move from the text string to the result string. In this regard, the simulation is not totally accurate (it doesn't reflect what goes on inside the computer). What is the difference between the phyiscal process and the process inside the computer? Discuss and put the answer in your report.

B. Vowels first / Adapting an algorithm

  1. Now consider a different goal, to develop a method getVowelsFirst that returns all vowels of a string, followed by all other letters. For example, new Word("monopoly").getVowelsFirst() should return the string "oooymnpl". You will want to adapt the algorithm that you discovered in the preceding steps. As a group, discuss how you can do that.

    Play out your adaptation with the tiles and paperclip.

    In your adaptation, does the paperclip traverse the text string once or twice? (There are two ways of solving this, both equally valid, that differ in this aspect. I want to know which one you came up with.)

  2. Now develop the pseudocode for your adaptation. What is it? (You can just scribble the changes on the same sheet that you used in step A3.
  3. In step B1, I asked whether the paperclip traverses the text string once or twice. If your answer was "twice", how can you improve your algorithm so that the string is only traversed once?

C. Stepwise Refinement

  1. Consider another way of developing the getVowelsFirst method.

    In part A, you developed a method getVowels.

    One way of solving a problem is to reduce it to a simpler problem, like this:

    public String getVowelsFirst()
    {
       String result = getVowels(); // get the vowels in the text
       // now what?
       return result;
    }

    What needs to be added to result to complete the method?

    First consider the concrete case in which text is "monopoly".

  2. In general, what needs to be added to result to complete the method?
  3. Let's write another method that produces the string that needs to be added after the vowels. Describe that method or simply give me a descriptive name for it.
  4. What is the pseudocode? Hint: It is very similar to the pseudocode of getVowels. Just tell me how the two differ.
  5. Now what is the code for getVowelsFirst that uses these two methods?

D. The longest vowel sequence / Combining algorithms

  1. In the previous lab, you discovered an algorithm for counting the number of vowel groups in a word. For example, the word
    outrageous

    has three vowel groups. Here is one algorithm for this purpose:

    count = 0
    i = 0
    while i < text.length()
       letter = the ith letter in text   
       i++
       if letter is a vowel
          count++
          while i < text.length() and the ith letter is a vowel
             i++ 

    Make a word with a couple of vowel groups and simulate this algorithm, using a paper clip to mark the position of i.

    Note how the inner while loop skips over the vowel group.

  2. Now let's say we want to find the longest of these sequences.

    In our example, that would be eou.

    First off, we need to assemble the vowel groups, not just count them. You know from part A how to assemble a sequence of letters in a string. Start with the empty string, then add letters as you encounter them.

    Look at the pseudocode above.

  3. Revise the pseudocode so that it assembles all vowel strings and prints them. What is your pseudocode?
  4. In class, we discussed an algorithm for finding the largest input value.
    while there are more inputs
       newValue = next input
       if newValue > largestValueSoFar
          largestValueSoFar = newValue

    Here, we remember the largest value. But in our situation, we want to remember the longest string.

    So, let's make a variable longestVowelGroupSoFar. In step 3, look where you printed the assembled vowel string. Replace the print statement with the code required to update the longest string. What is your pseudocode for that replacement?

  5. The count variable is no longer necessary. We no longer care how many vowel groups there are. Eliminate it from the pseudocode.

    What is the final pseudocode for the longestVowelGroup method?

  6. Trace your pseudocode with a word that has two vowel groups of equal maximal length, such as
    beauteous

    Which of them is reported as the longest one? The first or the second?