CS46B Lab - Pseudocode Bootcamp

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

A. Tracing Pseudocode

Consider this pseudocode.
```
i = 0
max = 0
imax = 0
while i < a.length
   j = i + 1
   while j < a.length and a[i] == a[j]
      j++
   if j - i > max
      max = j - i
      imax = i
   i = j
```
With the array a = [4, 4, 3, 2, 2, 2, 5, 5], trace this algorithm. That is, take out a sheet of paper, make a table with columns for all the variables, and update them as the algorithm proceeds. The driver marks the current line, and the scribe updates the table. Don't erase the old values, but write the new values below the old ones.
If you can't trace it, it's not pseudocode.
What does this algorithm do?
There is a funny thing about that pseudocode. Imagine j == a.length. In that case, we skip over the j++ but we don't skip over the if j - i > max part. Is that going to get us in trouble? Give an array of integers that would exhibit this behavior.
Trace through the algorithm with your choice of array. What happens when j == a.length?

B. From Pseudocode to Code

We want to compute the area of a polygon recursively, by cutting it in two polygons, each with half the number of vertices. (We assume that the polygon is convex. That means, that it has no corners with angle > 180 degrees, or, more technically, that, if any two points p and q are contained in the polygon, so is the line joining them.)

Assuming that the points are stored in an array list p, here is the pseudocode:
```
area(p)
n = p.size()
if n == 3
   return triangle area of p[0], p[1], p[2]
else
   k = n / 2
   p1 = new array list
   for i = 0 ... k
      add p[i] to p1
   p2 = new array list
   for i = k to p.size() - 1
      add p[i] to p2
   add p[0] to p2
   return area(p1) + area(p2)
```
Now complete this class. What is your code?
Run this tester. What is the result?
When you translated the pseudocode to code, what adaptations did you have to make?

C. Telling Good Pseudocode From Bad

One common problem with pseudocode is that it is too vague. Consider this example:
```
area(p)
n = p.size()
if n == 3
   return triangle area of p[0], p[1], p[2]
else
   Divide p into two polygons p1, p2, each of size n / 2
   return area(p1) + area(p2)
```
What mistakes can you make in the vague step Divide p into two polygons p1, p2, each of size n / 2? Describe at least two mistakes.
If there are multiple ways of coding it (with different behavior), it's not pseudocode.
An easy way of noting vagueness is to look at key phrases, such as "keep on going", "do it the same way", or simply "...". Look at Piazza for two examples of vague pseudocode. Paste them in your lab report. You don't have to fix them.
One way for improving pseudocode is to introduce variables. Stay away from “the array”, “the element”, “the index”, “the counter”, “the string”. Instead, use a, e, i, count, str. Nothing wrong with short variable names. Consider this example:
```
Initialize an index to loop over the array
While the index is not at the end of the array
   Check if the element at the index is the specific string
   If so, increment the counter
```
Reword this pseudocode so that it names all variables
Some students think that pseudocode should be like a story, with only words. That's not useful. You should change wordy pseudocode to assignments, the ++ operator, method calls, and so on. Rewrite the pseudocode from the preceding steps to do that. Also, use Java style if ... statements, and not “check if ... if so”.
When you have done the preceding step, you will end up with pseudocode that looks almost like Java. And you will be able to spot a couple of small errors in the pseudocode. What are they?
FInd another example of overly verbose pseudocode on Piazza. Copy it in your lab report and simplify it.
In pseudocode, one doesn't usually include types (int, int[], ArrayList<Integer>, etc.) That's another form of wordiness, and one should just drop them. If it's not clear from context that something is an array, you can always call the variable arr or array. Take this example:
```
minimumPositionAfter(a, r, c)
 int[] temp = elements r,c;
  int min = 21;
      for loop int row =0 row < a[r] length iterate row
    	  for loop int column = 0 column < a[c] length iterate column
    		  if a[r][c] < min 
    			  min=a[r][c];
    			  temp[0] = r;
    			  temp[1] = c;

     return temp; 
```
Rewrite it without the types. While you are at it, drop the semicolons. Also, change the for loops to the form
```
for variable in start...end
```
And do something about those variable names. r and c are used for two different purposes: The method parameters and the loop variables. Keep the meaning of the code intact--don't fix it.
This pseudocode was meant to find the position of the smallest element in a 2D array a, starting at a[r][c]. There are two obvious errors in the pseudocode. Fix them.

D. Translating Simple Actions

One of the reasons to write pseudocode is not to waste time with simple but tedious code. For example,
```
x = last element of a
```
is easier to write (and read) than
```
x = a.get(a.size() - 1)
```
Of course, the assumption is that a reasonably competent programmer can quickly and unambigously translate such simple actions into Java. For example, what is this in Java?
```
ch = last character of str
```
And this?
```
sum = sum of all elements in a
```

And this?

i = position of first negative element in a

And this?
```
i = position of first $ in str
```

And this?

salary = characters in str with commas removed, as a double

E. Find and Fix Semantic Errors

One reason to write pseudocode is to find and fix errors before implementing code. Consider this example for finding the starting index of the longest repeated sequence.
```
i = 0
max = 0
imax = 0
while i < a.length
   j = i + 1
   while a[i] == a[j]
      j++
   if j - i > max
      max = j - i
      imax = i
   i = j + 1
```
Simulate this code with the sequence
```
1 1 2 2 2 3
```
There are two errors in the pseudocode. Find and fix them.
Consider this pseudocode for cutting a polygon in two.
```
n = p.size()
k = n / 2
p1 = new array list
for i = 0 ... k
   add p[i] to p1
p2 = new array list
for i = k + 1 to p.size() - 1
   add p[i] to p2
```
Trace this with p = [c0, c1, c2, c3, c4, c5, c6, c7] from the picture at the top of this page. What are you getting for p1 and p2?
Is p1 the red polygon? Is p2 the green polygon?
How do you fix the pseudocode? (There are two errors.)

Here is the cleaned-up code for finding the position of the smallest element in a 2D array.

minimumPositionAfter(a, r, c)
result = [r, c]
min = a[r][c]
for row = r ... #rows in a - 1
   for col = c ... #cols in a - 1
      if a[row][col] < min 
         min = a[row][col]
         result = [row, rol]
return result

Simulate this pseudocode where a is the array

2 4 9
6 3 5
1 8 7

and r and c are both 2. What result do you get?

The expected result is [2, 0] since the smallest element is the 1 in the lower left corner. Change the pseudocode so that the method correctly traverses the entire remainder of the 2D array.

You can save many hours of debugging code by “wasting” a few minutes writing and debugging pseudocode.

F. Stepwise Refinement

One reason to write pseudocode is for “stepwise refinement”. As you have seen, you want to avoid all vagueness in pseudocode, but there is nothing wrong with making an outline first and then refining it. For example, suppose we need to compute the total of an invoice like this:
```
Description          Quantity    Unit Price
Microwave Oven             12         39.95
Toaster                     4         19.95
Stand Mixer                 1        109.95
```
We might start out with this high-level description:
```
discard first line of in
for l in lines of in
   Extract quantity and unit price from l...
   total += quantity * unit price
```
Note the ... behind the second line. That's an indication that this line needs further refinement—it is still too vague.

Demonstrate that the line is too vague. Describe two different strategies (with possibly different semantics) in which one can execute “Extract quantity and unit price from the line...”
Let's say we use the strategy of breaking the line into words and taking the two last words of the line l. Rewrite the pseudocode to indicate this strategy. Be sure to turn the words into numbers.
Conversely, let's assume that we extract substrings starting at the appropriate column indexes (21-29 for quantity, 33-43 for unit price, but don't hardwire that...). Now write that pseudocode.
In one of the scenarios, it is potentially beneficial to introduce a helper function. Write the pseudocode with the helper function. Clearly specify the parameters of the helper function. Everything that the helper function needs must be passed as a parameter (in particular, the line!). But don't specify types of the parameters. First write the pseudocode of the algorithm, then put the helper function below. Underline the helper function header, like we did elsewhere in this lab.

G. Practice Problems

In this section, write pseudocode for some common programming problems. Be sure to understand and follow these syntax rules.

Given an array a of integers, find the length of the ith “run”, i.e. the ith sequence of repeated elements. For example, in the array 1 1 2 2 2 3, the first run has length 2, the second run length 3, the third run length 1.
```
lengthOfRun(a, i)
...
```
Given a string containing quoted strings, produce an array list of all quoted substrings. For example, if the string is
```
"Toaster Oven", "4", "19.95"
```
or, technically,
```
"\"Toaster Oven\", \"4\", \"19.95\""
```
you should produce an array of three strings, "Toaster Oven", "4", and "19.95"
Given an array a of integers and an integer k, return an array of all positions of the kth-smallest element. For example, if a is [1, 4, 7, 5, 0, 5, 6, 4, 4, 5] and k is 3, then return the array [1, 7, 8] because the 3rd smallest element is 4, and it occurs at positions 2, 7, and 8.

H. Your Turn

Take a recent homework problem that uses an interesting algorithm. Write the pseudocode for the algorithm. Don't be vague. Don't be too wordy. Follow the syntax rules.
Trace your pseudocode for a typical input.