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.

Part A: Simple array algorithms

With your buddy, read through this problem statement. The problem decomposes into three simpler problems. What are they?
Which algorithm in section 7.6 will be helpful?
Assuming that you have the counts for the odds and evens (say in oddCount and evenCount), what is the Java code for returning them together in an array?
Do you really have to compute two counts? Or can you figure out one from the other?
Solve the problem in BlueJ. Make sure the test cases pass. Paste your code into the lab report.

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. 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.
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
```
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 you 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

Run this program. The swapNeighbors method 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. 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.
Discuss what you learned from observing the program, and how you can fix your program so that the swapping actually works.
Implement your fix and test it. Put the fixed code in your lab report.

Part D. More Swapping with Alice

Unzip this file and open the project in Netbeans. Run the program. Look at the myFirstMethod method in the Scene class. Note that a VisualArrayList is exactly like an ArrayList, except it shows you in slow motion what goes on inside.
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)
Implement your 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)
Implement your 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

Run the code in this class. Note how the makePattern method fills a two-dimensional array colors[15][10] with colors.
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?
Implement the code and execute it. Put the code of the makePattern method in your lab report.
Each of you comes up with a pattern that you want your partner 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 your partner and be sure you know what your partner wants. Ask for clarification if necessary.
If either of you feels that the pattern they got from the other is too hard to code, you can refuse it. In that case, each of you implements the pattern that you designed.
Implement the pattern. Attach a screen capture and the code to your lab report.