CS46A Lab

Designing Algorithms

Copyright © Cay S. Horstmann, Kathleen O’Brien 2009-2014
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

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

Generating ideas
Identifying “building blocks” for your algorithms
Simulating algorithms with physical objects
Reusing and adapting algorithms
Using “stepwise refinement” to break tasks into easier tasks

A. Getting only the vowels / Using physical objects

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". You will add your method to this Word class.
It is useful to think about “building blocks:" snippets of code that may help you attack this problem. These are things you already know how to do and you may be able to put various ideas together to solve the current problem. Here are a few things you know how to do:
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
```
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)) ...
```
  The isVowel 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. No code to be written in this step.
Now you need to come up with a plan, where you loop through the letters, look for vowels, and do something with them. Eventually you will write the code, but first you need 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. The lab instructor has a supply of Scrabble tiles and paper clips. Get some tiles that spell a word with at least two vowels. Use a paper clip to indicate the current loop index.

Put the paper clip at the first letter, then move it to the second letter, etc. Each time, decide what to do with the letter. (Is it a vowel? Do you want to add it to your vowel string?) If you decide to add it to another string, just move it.

If anyone gets confused about what is happening, start over. Just indicate in the report that you did step 2)
After you have a shared understanding of how to simulate the algorithm with the tiles and paperclip, jointly develop the pseudocode (mixture of Java and English) to describe what needs to be done to get all the vowels.
Caution: In the Word class, the string in question is stored in an instance variable text. It will make your life easier to also use text when you write down your pseudocode.

Scribe: Once the group agrees on the pseudocode, type a copy into the lab report. (no code yet, just pseudocode)
Now we'll use the tiles and paper clip 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 paper clip as appropriate. Does your pseudocode work? If not, fix it and try again.
Once you think the algorithm described in the pseudocode is correct, show it to your lab instructor.
Now add the code for the getVowels method to the Word class from Step 1. Driver: Paste the code for your getVowels method into your lab report. (Now you will turn your psedocode into code.)
Test using the Bluej workbench. Or if you are ambitious, you can write a tester.
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 physical process and the process inside the computer? Discuss. Scribe: Put the answer in your report.

B. Vowels first / Adapting an algorithm

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 paper clip.

Scribe: In your adaptation, does the paperclip traverse the text string once or twice? (There are two ways of solving this, both valid. I want to know which one you came up with.)
Now develop the pseudocode for your adaptation. What is it? (You can just modify what you created in step A3.) (no code yet)
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?
Show the pseudocode to your lab instructor
Add the getVowelsFirst method to the Word class. Driver: Paste the code for your method into your lab report (Now add the code to the Word class)

C. Stepwise Refinement

Programmers often use "stepwise refinement" in which they first increment a smaller problem that gets them closer to the solution.

Consider this 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".
- What does getVowels() return?
- What should getVowelsFirst() return?
- What needs to be added to result to complete the solution? Scribe: record your thoughts.
In general, what needs to be added to result to complete the method?
Let's write another method that produces the string that needs to be added after the vowels. Scribe: Describe that method or simply give a descriptive name for it. (no code yet)
Scribe: What is the pseudocode for this method? Hint: It is very similar to the pseudocode of getVowels. Just tell how the two differ.
Add the code for this new method.
Driver: Now what is the code for getVowelsFirst method using these two methods?

D. The longest vowel sequence / Combining algorithms

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 the Scrabble tiles and a paper clip to mark the position of i.

Note how the inner while loop skips over the vowel group.
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.
- Scribe: Where do you start assembling a vowel group?
- Scribe: Where do you add more vowels?
- Scribe: Where are you done with assembling the sequence?
Revise the pseudocode so that it assembles all vowel groups and prints them. Scribe: What is your pseudocode?
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
```
In that case, 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 group. Replace the print statement with the code required to update the longest group. Scribe: What is your pseudocode for that replacement? (No code yet)
The count variable is no longer necessary. We no longer care how many vowel groups there are. Eliminate it from the pseudocode.
Scribe: What is the final pseudocode for the longestVowelGroup method? (No code yet)
Trace your pseudocode with a word that has two vowel groups of equal maximal length, such as
```
beauteous
```
Scribe: Which of them is reported as the longest one? The first or the second?
Now add the code for longestVowelGroup method to the Word class. Driver: Paste the code for your method into your lab report (Now write the code.)

E. Homework08, Par16, and Quiz17

Discuss Homework08, Par16, and Quiz17 with your partner and ask your lab instructor for help when needed.