CS46A Lab

Arrays

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

Part A: Simple array algorithms

  1. With your buddy, read through this problem statement. Be sure to read the Javadoc comments for the evenOdd method.
  2. Scribe: What is the return type of the evenOdd method?
  3. Scribe: How do you create an int array that can hold two numbers?
  4. The problem of coding the evenOdd method decomposes into three simpler problems. Scribe: What are they?
  5. Scribe: Which algorithm in section 7.3 of your textbook will be helpful?
  6. Scribe: Assuming that you have the counts for the odds and evens (say in oddCount and evenCount), what is the Java code for creating an array of length 2 and returning both counts in the array?
  7. Scribe: You really do not have to compute two counts. How can you calculate one given the other?
  8. Solve the problem in BlueJ. Make sure your code passes the test cases in this tester. Driver: Paste your code into the lab report.

Part B: Removing duplicates

Step1
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 complete the method removeAdjacentDuplicates to remove all adjacent duplicates in words. Develop a plan and write pseudocode for this task. Questions to think about. Scribe: How do you plan to find duplicates? Scribe: What will you do when you find them? Pay special attention to what happens at the beginning or end of the array list. Show your lab instructor your pseudocode before doing the next step.

Step 2
Implement your solution. To test, download and unzip this zip file. Copy each file into the same directory that contains your BlueJ project. Do not copy the folder.

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. . Scribe: Is the duplicate “be” removed?

Step 3
Run this tester. Scribe: Did you pass all tests? If not, what did you do to fix your code?

Driver: In your lab report, paste the correct solution.

Step 4
 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 sure to go

Decide upon an algorithm and write down the pseudocode.

Scribe: Ask yourselves:


Step 5
When you are satisfied that you can implement it, add a method removeAllDuplicates to the Text class.

Implement the method and test it as described above.

Step 6
Run this tester.

Scribe: Did you pass all tests? If not, what did you do to fix your code

Step 7
Driver: In your lab report, paste the correct solution.

Part C: Swapping

Step 1
Run this program.

The code on lines 20 to 24 is intended to swap neighboring elements. For example, 

1 4 9 16 25 36

is supposed to turn into

4 1 16 9 36 25

But as you can see, it doesn't work. Now launch the BlueJ debugger. Put a breakpoint at line 20. Click Step. And 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.

Step 2
Discuss what you learned from observing the program

How you can fix your program so that the swapping actually works? Scribe: What did you decide?

Step 3
Implement your fix and test it.

Driver: Put the fixed code in your lab report.

Part D: More Swapping with Pictures

Step 1
Unzip this file and open the project in BlueJ. Run the program.
Look at the main method in the Lab11D class. Note that a VisualArrayList is exactly like an ArrayList, except it shows you in slow motion what goes on inside.

Step 2
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:

Step 3
Implement your pseudocode and run it.

Driver: Paste the main method into your lab report.

Step 4
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. Hint: How do you swap elements at index1 and index2?

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 (Scribe: record the answers):


Step 5
Implement your pseudocode and run it.

Driver: Paste the main method into your lab report. Watch how much faster it runs. (This should be pretty obvious since the movement of the array elements takes time.)

Add four more letters and run the program again to double-check that it works with any even number of letters.