Question

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 duplicate

   public class Numbers
   {
      /**
         Computes the number of even and odd values in a given array
         @param values an array of integer values
         @return an array of length 2 whose 0 entry contains the count
         of even elements and whose 1 entry contains the count of odd
         values
      */
      public static int[] evenOdds(int[] values)
      {
         // your work here
   
   
   
      }
   }
   
   Code tester
   
   public class NumbersTester
   {
      public static void main(String[] args)
      {
         int[] a = { 1, 2, 3 };
         int[] r = Numbers.evenOdds(a);
         System.out.println(r[0] + " " + r[1]);
         System.out.println("Expected: 1 2");
         a[1] = 5;
         r = Numbers.evenOdds(a);
         System.out.println(r[0] + " " + r[1]);
         System.out.println("Expected: 0 3");
         a = new int[0];
         r = Numbers.evenOdds(a);
         System.out.println(r[0] + " " + r[1]);
         System.out.println("Expected: 0 0");
      }
   }

   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:

9. How do we know when a word is duplicated?
10. Should we first check for duplication, or should we proactively remove all duplicates of every word?
11. How can we be sure to leave one copy of the word in place?
12. How do we remove all those duplicates?
13. When removing a word and traversing an array at the same time, how does that affect the array index?

14. 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:

15. Which actions need to be carried out in each loop iteration?
16. How many iterations are there (for arbitrary even lengths, not necessarily 6)
17. Which actions need to be carried out in each loop iteration?
18. How do you know the positions of the elements to be swapped?
19. How many iterations are there (for arbitrary even lengths, not necessarily 6)

20. 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.

    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):

Answer 1

Working code implemented in Java and appropriate comments provided for better understanding.

Here I am attaching code for all files:

• Lab11D.java
• Swap.java
• Numbers.java
• NumbersTester.java
• TextTester1.java
• TextTester2.java
• VisualArrayList.java

Lab11D.java:

public class Lab11D
{
public static void main(String[] args)
{
VisualArrayList<Picture> list = new VisualArrayList<Picture>();   
list.add(new Picture("a.jpeg"));
list.add(new Picture("b.jpeg"));
list.add(new Picture("c.jpeg"));
list.add(new Picture("d.jpeg"));
list.add(new Picture("e.jpeg"));
list.add(new Picture("f.jpeg"));

VisualArrayList<Picture> list1 = new VisualArrayList<Picture>();

for (int i = list.size() / 2; i < list.size(); i++)
{
list1.add(list.get(i));
}

for (int j = 0; j <= list.size() / 2 - 1; j++)
{
list1.add(list.get(j));
}

for (int i = 0; i < list.size() / 2; i++)
{
list.add(list.remove(0));
}

for (int i = 0; i < list.size() / 2; i++)
{
Picture temp = list.get(i);
list.set(i, list.get(i + (list.size() / 2)));
list.set(i + (list.size() / 2), temp);

}

}
}

Swap.java:

import java.util.*;

public class Swap
{
public static void main(String[] args)
{
// Make a random array of even length between 10 and 20
// containing numbers between 0 and 99
Random generator = new Random();
int n = 10 + 2 * generator.nextInt(6);
int[] numbers = new int[n];
for (int i = 0; i < n; i++)
numbers[i] = generator.nextInt(100);

// Here is the array
System.out.println(Arrays.toString(numbers));

// Swap adjacent neighbors

for (int i = 0; i < n; i = i + 2)
{
int temp = numbers[i];
numbers[i] = numbers[i + 1];
numbers[i + 1] = temp;
}

// Here is the array after swapping
System.out.println(Arrays.toString(numbers));
}
}

Numbers.java:

public class Numbers
{
/**
Computes the number of even and odd values in a given array
@param values an array of integer values
@return an array of length 2 whose 0 entry contains the count
of even elements and whose 1 entry contains the count of odd
values
*/
public static int[] evenOdds(int[] values)
{
int[] countArray = new int[2];
int numEven = 0;

for (int element : values)
{
if (element % 2 == 0)
{
numEven = numEven + 1;
}
}

int numOdd = values.length - numEven;
  
countArray[0] = numEven;
countArray[1] = numOdd;

return countArray;
}
}

NumbersTester.java:

public class NumbersTester
{
public static void main(String[] args)
{
int[] a = { 1, 2, 3 };
int[] r = Numbers.evenOdds(a);
System.out.println(r[0] + " " + r[1]);
System.out.println("Expected: 1 2");
a[1] = 5;
r = Numbers.evenOdds(a);
System.out.println(r[0] + " " + r[1]);
System.out.println("Expected: 0 3");
a = new int[0];
r = Numbers.evenOdds(a);
System.out.println(r[0] + " " + r[1]);
System.out.println("Expected: 0 0");
}
}

TextTester1.java:

public class TextTester1
{
public static void main(String[] args)
{
Text text1 = new Text();
text1.load("typo.txt");
text1.removeAdjacentDuplicates();
System.out.println("Actual: " + text1.getWords());
System.out.println("Expected: [A, common, typo, is, to, accidentally, duplicate, a, word, which, can, be, rather, embarrassing]");

text1.load("test.txt");
text1.removeAdjacentDuplicates();
System.out.println("Actual: " + text1.getWords());
System.out.println("Expected: [a, b, a, c, a, d, a]");

text1.load("alice30.txt");
int before = text1.getWords().size();
text1.removeAdjacentDuplicates();
int after = text1.getWords().size();
System.out.println("Size before and after: " + before + " " + after);
System.out.println("Expected: 29074 29045");
}
}

TextTester2.java:

public class TextTester2
{
public static void main(String[] args)
{
Text text2 = new Text();
text2.load("mary.txt");
text2.removeAllDuplicates();
System.out.println("Actual: " + text2.getWords());
System.out.println("Expected: [Mary, had, a, little, lamb, whose, fleece, was, white, as, snow, And, everywhere, that, went, and, the, sure, to, go]");

text2.load("test.txt");
text2.removeAllDuplicates();
System.out.println("Actual: " + text2.getWords());
System.out.println("Expected: [a, b, c, d]");

text2.load("alice30.txt");
int before = text2.getWords().size();
text2.removeAllDuplicates();
int after = text2.getWords().size();
System.out.println("Size before and after: " + before + " " + after);
System.out.println("Expected: 29074 3385");
}
}

VisualArrayList.java:

import java.util.ArrayList;

public class VisualArrayList<E extends Picture> extends ArrayList<E>
{
private static final int GAP = 10;

private void visualTranslate(final int dx, final int dy, final Picture p)
{
final int x = p.getX();
final int y = p.getY();

Thread t = new Thread()
{
public void run()
{
final int STEPS = 100;
final int DELAY = 10;
for (int i = 1; i <= STEPS; i++)
{
try
{
p.translate(x + i * dx / STEPS - p.getX(), y + i * dy / STEPS - p.getY());   
Thread.sleep(DELAY);
}
catch (InterruptedException ex) {}
}
}
};
t.start();
try
{
t.join();
}
catch (InterruptedException ex) {}
}

public boolean add(E e)
{
add(size(), e);
return true;
}

public void add(int index, final E element)
{
for (int i = size() - 1; i >= index; i--)
{
Picture p = get(i);   
visualTranslate(element.getWidth() + GAP, 0, p);
}
super.add(index, element);
int x = index == 0 ? 0 : get(index - 1).getX() + get(index - 1).getWidth() + GAP;
element.translate(x - element.getX(), element.getHeight() -element.getY());
element.draw();
visualTranslate(0, -element.getHeight(), element);
}

public E remove(int index)
{
E element = super.remove(index);
visualTranslate(0, -element.getHeight(), element);
for (int i = index; i < size(); i++)
{
Picture p = get(i);
visualTranslate(-element.getWidth() - GAP, 0, p);
}
return element;
}

public E set(int index, E element)
{
E oldElement = get(index);
super.set(index, null);
if (!contains(oldElement)) Canvas.getInstance().remove(oldElement);
int dx = element.getWidth() - oldElement.getWidth();
for (int i = index + 1; i < size(); i++)
get(i).translate(dx, 0);
int x = index == 0 ? 0 : get(index - 1).getX() + get(index - 1).getWidth() + GAP;
element.translate(x - element.getX(), element.getHeight() -element.getY());
element.draw();
visualTranslate(0, -element.getHeight(), element);
super.set(index, element);
return oldElement;
}
}