CS46A Lab

Arrays

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

In this lab, you will switch between groups of four and groups of two. When you design a solution, you will work in groups of four. When you implement and test your solution, you will split up into two groups of two.

Part A. Array Practice

Group of four: Go to JavaBat, then Arrays1, then midThree. Discuss how you will solve this problem. How do you make the new array? How do you figure out the index values that you need to look up in the given array? Write the Java code that you intend to use on a sheet of paper. Stop when each group of two is confident that you are ready to implement the solution.
Groups of two: In JavaBat, type in your solution and test it. Fix any mistakes.
In your lab report, paste in both solutions.
Repeat with lucky13 in Arrays2. Discuss as a group of four how you will solve the problem. How will you loop through the array? What will you return? When do you know the answer? Then test your solution as groups of two, and paste both solutions into your report.
Extra time? Do withoutTen.

Part B. Removing duplicates

A common typo is to accidentally duplicate a word, which can be be rather embarrassing. Your task is to design and implement a program that removes adjacent duplicates. This class reads a file and puts all words into an ArrayList<String> called words. Your task is to add a method removeAdjacentDuplicates that removes all adjacent duplicates in words. As a group of four, develop a plan and write pseudocode for this task. How will you find duplicates? What will you do when you find them? Pay special attention to what happens at the beginning or end of the array list.
As groups of two, implement your solution. To test, put all files in this zip file into the same directory that contains your BlueJ project. (You must unzip the zip file. Don't simply move the zip into your BlueJ directory.)
Make a Text object on the BlueJ workbench. Right-click and call pick. Pick the file typo.txt. Right-click and call removeAdjacentDuplicates (i.e. your method). Right-click and call explore. Is the duplicate “be” removed?
Run this tester. Did you pass all tests? If not, what did you do to fix your code?
In your lab report, paste in both solutions.
Now suppose you want to remove all duplicates, whether adjacent or not. The result will be a list of unique words. For example, if the array list contains these immortal words
```
Mary had a little lamb little lamb little lamb
Mary had a little lamb whose fleece was white as snow
And everywhere that Mary went Mary went Mary went
And everywhere that Mary went the lamb was sure to go
```
you should produce the array list
```
Mary had a little lamb
whose fleece was white as snow
And everywhere that went
the was sure to go
```
As a group of four, decide upon an algorithm and write down the pseudocode.

Ask yourselves:
- How do we know when a word is duplicated?
- Should we first check for duplication, or should we proactively remove all duplicates of every word?
- How can we be sure to leave one copy of the word in place?
- How do we remove all those duplicates?
- When removing a word and traversing an array at the same time, how does that affect the array index?
When both groups of two are satisfied that you can implement it, add a method removeAllDuplicates to the Text class. Provide your implementation and test it as described above.
Run this tester. Did you pass all tests? If not, what did you do to fix your code?
In your lab report, paste in both solutions.

Part C. Swapping

Start out in groups of two. Each group runs this program. The swapNeighborsmethod is intended to swap neighboring elements. For example,
```
1 4 9 16 25 36
```
is supposed to turn int
```
4 1 16 9 36 25
```
But as you can see, it doesn't work. Now launch the BlueJ debugger (still working in groups of two). Step into the swapNeighbors method. Then keep clicking Step and observe the program behavior until you can tell why it fails to swap the values.

Tip: To see the contents of the array, double-click on it in the Local Variables pane.
As a group of four, discuss what you learned from observing the program, and how you can fix your program so that the swapping actually works.
Back as groups of two, implement your fix and test it. Put the fixed code in your lab report.

Part D. More Swapping with Alice

Start out in groups of two. Each group unzips this file and opens the project in Netbeans. Run the program. Look at the run method in the ArrayScene class. Note that a VisualArrayList is exactly like an ArrayList, except it shows you in slow motion what goes on inside.
As a group of four, come up with an algorithm for the following task. We want to swap the first half and the second half of the array list.
For example, A B C D E F should turn into D E F A B C.

You should assume that the array list has an even number of elements (not necessarily 6).

One solution is to keep removing the element at index 0 and adding it to the back.
```
A B C D E F
B C D E F A
C D E F A B
D E F A B C
```
Write pseudocode for this algorithm.

Ask yourselves:
- Which actions need to be carried out in each loop iteration?
- How many iterations are there (for arbitrary even lengths, not necessarily 6)
As groups of two, implement this pseudocode and run it. Paste the run method into your lab report.
When you run the code, you will find that there is a lot of movement in the array. Each call to remove(0) causes n - 1 elements to move, where n is the length of the array. If n is 100, then you move 99 elements 50 times, (almost 5000 move operations). That's an inefficient way of swapping the first and second halves.
Come up with a better way in which you swap the elements directly.
```
A B C D E F
D B C A E F
D E C A B F
D E F A B C
```
Write pseudocode for this algorithm.

Ask yourselves:
- Which actions need to be carried out in each loop iteration?
- How do you know the positions of the elements to be swapped?
- How many iterations are there (for arbitrary even lengths, not necessarily 6)
As groups of two, implement this pseudocode and run it. Paste the run method into your lab report. Watch how much faster it runs. (In Alice, this is pretty obvious since the movement of the array elements takes time.)
Set NCARS to 10 and run the program again to double-check that it works with any even number of cars.

Part E. 2D arrays

As groups of two, run the code in this class. Note how the makePattern method fills a two-dimensional array colors[15][10] with colors.
As a group of four, provide pseudocode for creating this pattern:

Ask yourselves:
- How do you make a row of squares of the same color, with a given arbitrary row index?
- How do you make all the blue rows? (Assuming that you know how to make one row anywhere)
- At what index values do you make all the red rows?
Each group of two implements the code and executes it. Put the code of the makePattern method in your lab report.
Each group of two comes up with a pattern that it wants the other group to implement. Sketch the pattern on a sheet of paper. Be creative, but keep in mind that the pattern should be regular enough that it can be done with a couple of loops.
Discuss the pattern that you got from the other group and be sure you know what they want. Ask them to clarify if necessary.
If either group feels that the pattern they got from the other is too hard to code, they can refuse it. In that case, each team implements the pattern that they designed.
Implement the pattern. Attach a screen capture and the code to your lab report.