HOMEWORK #2 LinkedListMethods solution

Write the class LinkedListMethods that contains only static methods.
Write only the 5 methods that are next to your name.


Follow the same procedure that you did for Homework #1, i.e use good
programming style, write an author block and email them to me.
You do not have to turn the hard copy and the java file for the Pair class.



Method 1:

A multiset is similar to a set except that the duplications count.
We want to represent multisets as linked lists. The first representation
that comes to mind uses a LinkedList<T where the same item can occur at
several indices.
For example, the multiset { "Ali Baba" , "Papa Bill", "Marcus",
"Ali Baba", "Marcus", "Ali Baba" } can be represented as a linked list
of strings with "Ali Baba" at index 0, "Papa Bill" at index 1,
"Marcus" at index 2, "Ali Baba" at index 3, and so on, for a total of
6 strings.

We want a representation of the multiset as pair <item,integer where the integer,
called the multiplication of item,
tells us how many times item occurs in the multiset.
This way the above multiset is represented as the linked list with
Pair("Ali Baba" ,3) at index 0, Pair("Papa Bill", 1) at index 1, and
Pair("Marcus",2) at index 2.

Write the method

public static <T LinkedList<Pair<T,Integer
convert(LinkedList<T in)


that transforms the first representation into the Pair representation.
If in is null, convert returns null. Also feel free to modify the input list.

Below is the class Pair.

public class Pair<T,S
{

// the fields

private T first;

private S second;


// the constructor
public Pair(T f, S s)
{

first = f;
second = s;
}

// the get methods
public T getFirst()
{
return first;
}

public S getSecond()
{
return second;
}

// the set methods
// set first to v
public void setFirst(T v)
{
first = v;
}

// set second to v
public void setSecond(S v)
{
second = v;
}

}


Method 2:

Write the method


public static void reduceList( java.util.LinkedList<String list,
char ch)

that deletes from list all names that start with the letter ch.

Method 3:

We define the balanced parentheses strings as follows:

1. {} is a balanced parentheses string

2. [] is a balanced parentheses string

3. () is a balanced parentheses string

4. If S is a balanced parentheses string, so is {S}

5. If S is a balanced parentheses string, so is [S]

6. If S is a balanced parentheses string, so is (S)

7. If S and T are balanced parentheses strings, so is ST .
where S and T can be the same string or different ones.



For example, the strings () , [()] , {{}(){}} , ()() are 4 balanced strings.

Write the method

public static boolean isBalanced(String in)

that returns true if in is a string of balanced parentheses and
false if it is not. You may write a recursive or a non-recursive program,
but try to make your program as short as possible.

Method 4:

Write the method

public static <T void eliminateDuplicates(LinkedList<T list)

that deletes all duplicate items from list. Use the equals method to
check for duplications.


Method 5:

Write the method

public static <T extends Comparable<? super T void
sort(LinkedList<T list)

that sorts list in the increasing order of compareTo.
Do not use the Collections class.

Method 6:

We define the Grandpa strings as follows:

1. ab is a Grandpa string.

2. bca is a Grandpa string.

3. If S is a Grandpa string, so is SaS.

4. If U and V are Grandpa strings, so is UbV.

Here a, b, c are constants and S,U,V are variables. In these rules,
the same letter represents the same string. So, if S = ab,
rule 3 tells us that abaab is a Grandpa string.
In rule 4, U and V represent Grandpa strings, but they may be different.

Write the method

public static boolean isGrandpa(String in)
returns true if S is a Grandpa string and false otherwise.

Method 7:

Write the method

public static <T extends Comparable< ? super T
int find(T [] a, T x, int low, int high)

returns an index where x occurs in the array a, or -1 if
x is not in a. Assume that a is sorted in increasing order.
Use the binary search method.

Method 8:

Write the method sort.

public static <T extends Comparable< ? super T
void sort(T [] a)

sorts the array a in increasing order. The method must be
a short recursive program. Do not use the methods quicksort,
merge sort, or the Arrays class.

Method 9:

Write the method getLargest.

public static <T extends Comparable< ? super T
T getLargest(T [] a, int low, int high)

returns the largest item in the array slice a[low:high].
Throw an illegal argument exception if low high.