Problem Set 6

due by 11:59 p.m. on Sunday, March 31, 2019

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email instructor.

Make sure to submit your work following the procedures found at the end of the assignment.

Part I

35 points total

Problem 1: Choosing an appropriate list implementation

12 pts. total; 4 pts. each part; individual-only

Put all of your work for this problem in a plain-text file named ps6pr1.txt.

As you learned in high-school algebra, a polynomial is an algebraic expression formed by adding together terms of the form ax^b, where x is a variable and a and b are constants. a is the coefficient of the term, and b is the exponent of the term. For the sake of this problem, we will assume that all exponents are all non-negative integers. If the exponent is 0, then the term is a constant, because x⁰ = 1.

For example, the following are all examples of polynomials of the variable x:

• 6 + 5x + 8x⁵
• -2x²
• 4x³ + (-2)x⁷ + x¹²

A polynomial can be evaluated for a specific value of x by plugging in the value and computing the result. For example, when x is 2, the first polynomial above has the value

6 + 5(2) + 8(2⁵) = 6 + 10 + 8(32) = 272

One way to represent a polynomial is to store its coefficients in an array. The exponent of a given term is used to determine the position of the corresponding coefficient in the array. For example:

• 6 + 5x + 8x⁵ would be represented by the array {6, 5, 0, 0, 0, 8}

• -2x² would be represented by the array {0, 0, -2}

• 4x³ + (-2)x⁷ + x¹² would be represented by the array {0, 0, 0, 4, 0, 0, 0, -2, 0, 0, 0, 0, 1}

An alternative representation of a polynomial involves using a linked list in which each node in the list represents a single term of the polynomial. Here is one example of class that could be used for the nodes:

public class PolyNode {
    private int coeff;       // the coefficient
    private int exp;         // the exponent
    private PolyNode next;
}

The nodes would be sorted by their exponents, and it would not be necessary to include nodes for non-existent terms (i.e., terms with a coefficient of 0). For example, the linked list for the third polynomial above would look like this:

For each of the following questions, your answers should make use of big-O expressions that are functions of t, the number of terms in the polynomial, and/or m, the maximum exponent in the polynomial. (The third polynomial above has t = 3 terms and a maximum exponent m of 12.) Explain each answer briefly.

1. What is the space efficiency of each implementation?

2. What is the time efficiency of changing the coefficient of a term (e.g., changing the coefficient of the x³ term in the third polynomial from 4 to 10) in each implementation in the best, average, and worst cases?

3. What is the time efficiency of evaluating a polynomial in each implementation in the best, average, and worst cases? Important: You should assume that both implementations use a helper method that takes O(n) steps to compute x to the nth power.

4. Describe a situation in which one of the two representations would clearly be more efficient than the other one.

Problem 2: Improving the efficiency of an algorithm

13 pts. total; individual-only

Put all of your work for this problem in a plain-text file named ps6pr2.txt.

Consider the following method, which takes two unsorted lists, list1 and list2 – both instances of our LLList class from lecture – and creates a third list containing the intersection of list1 and list2:

public static LLList intersect(LLList list1, LLList list2) {
    LLList inters = new LLList();

    for (int i = 0; i < list1.length(); i++) {
        Object item1 = list1.getItem(i);
        for (int j = 0; j < list2.length(); j++) {
            Object item2 = list2.getItem(j);
            if (item2.equals(item1)) {
                inters.addItem(item2, inters.length());
                break;   // move onto the next item from list1
            }
        }
    }

    return inters;
}

The lists are unsorted, so we take a nested-loop approach in which each item in list1 is compared to the items in list2; if a match is found in list2, the item is added to the intersection and we break out of the inner loop. (Note that this method will include duplicate values in the intersection when list1 itself has duplicates; doing so is acceptable for the purposes of this problem.)

1. (3 points) What is the worst-case running time of this algorithm as a function of the length m of list1 and the length n of list2? Don’t forget to take into account the time efficiency of the underlying list operations, getItem() and addItem(). Use big-O notation, and explain your answer briefly.

2. (7 points) Rewrite this method to improve its time efficiency. Your new method should not modify the existing lists in any way, and it should use no more than a constant (O(1)) amount of additional memory. Make the new method as efficient time-wise as possible, given the constraints on memory usage. You should assume this method is not part of the LLList class, and therefore it doesn’t have direct access to the private LLList members.

3. (3 points) What is the worst-case running time of the improved algorithm? Use big-O notation, and explain your answer briefly.

Problem 3: Working with stacks and queues

10 points; 5 points each part; individual-only

Put all of your work for this problem in a plain-text file named ps6pr3.txt.

1. Write a method remAllStack(Stack<Object> stack, Object item) that takes a stack and an item, and that removes all occurrences of that item from the stack. After the removals, the remaining items should still be in the same order with respect to each other. For example, if you have a stack that contains (from top to bottom) {5, 2, 7, 2, 10}, if you use the method to remove all occurrences of 2, the resulting stack should contain (from top to bottom) {5, 7, 10}.

   Important guidelines:

   • Your method may use either another stack or a queue to assist it. It may not use an array, linked list, or other data structure. When choosing between a stack or a queue, choose the one that leads to the more efficient implementation.

   • You should assume that the method does not have access to the internals of the collection objects, and thus you can only interact with them using the methods in the interfaces that we discussed in lecture.

   • Although you aren’t writing this method as part of a class, you should use appropriate Java syntax. The methods should be static and should not return a value.

2. Write a method remAllQueue(Queue<Object> queue, Object item) that takes a queue and an item, and that removes all occurrences of that item from the queue. After the removals, the remaining items should still be in the same order with respect to each other. For example, if you have a queue that contains (from front to rear) {5, 2, 7, 2, 10} and you use the method to remove all occurrences of 2, the resulting queue should contain (from front to rear) {5, 7, 10}. The same guidelines that we specified for remAllStack() also apply here.

Part II

65 points total

Preparing for Part II

Begin by downloading the following zip file: ps6.zip

Unzip this archive, and you should find a folder named ps6, and within it the files you will need for Part II. Make sure that you keep all of the files in the same folder.

Important: When you compile the code in this folder, you may see one or more warnings labeled “unchecked cast”. You can safely ignore them.

Problem 4: Removing all occurrences from a list

20 points; individual-only

If you haven’t already done so, complete the steps above to prepare for this and the remaining problems in Part II.

Assume that we want list objects to support the following method:

 boolean removeAll(Object item)

This method takes an item, and it should removes all occurrences of that item from the list. If one or more occurrences of the item are removed, the method should return true. If there were no occurrences of the item to begin with, it should return false.

Create two implementations of this method: one as part of the ArrayList class, and one as part of the LLList class. Both classes can be found in the ps6 folder.

Important: For full credit, both methods should:

• run in O(n) time, where n is the number of items in the list
• use no more than a constant (O(1)) amount of additional memory.

In addition, you should make sure that your ArrayList version of the method doesn’t leave any extraneous references to objects in the items array. For example, let’s say that you have 9 items in the ArrayList. If a call to removeAll() removes 3 of them, you should end up with an array in which the first 6 elements hold references to actual items, and all of the remaining elements are null.

To facilitate testing, we have added a constructor to both classes that takes an array of type Object containing the initial contents of the list. Given these constructors, you can test your methods using examples that look like this:

> String[] letters = {"a", "b", "c", "a", "c", "d", "e", "a"};
> ArrayList list1 = new ArrayList(letters);
> System.out.println(list1);
{a, b, c, a, c, d, e, a}
> System.out.println(list1.removeAll("a"));
true
> System.out.println(list1);
{b, c, c, d, e}
> System.out.println(list1.removeAll("c"));
true
> System.out.println(list1);
{b, d, e}
> System.out.println(list1.removeAll("x"));
false
> System.out.println(list1);
{b, d, e}
> LLList list2 = new LLList(letters);
> System.out.println(list2);
{a, b, c, a, c, d, e, a}
> System.out.println(list2.removeAll("a"));
true
> System.out.println(list2);
{b, c, c, d, e}
> System.out.println(list2.removeAll("x"));
false

Problem 5: Implementing the Bag ADT using a linked list

25 points; pair-optional

This is the only problem of the assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

Earlier in the course, we worked with the ArrayBag class. This class can be seen as an implementation of the Bag abstract data type, which we can specify in Java using the following interface:

public interface Bag {
    boolean add(Object item);
    boolean remove(Object item);
    boolean contains(Object item);
    int numItems();
    Object grab();
    Object[] toArray();
}

In the ps6 folder, we have included:

• the Bag interface (Bag.java)
• a version of the ArrayBag class that includes an implements clause in its header to specify that it implements this interface.

In a file named LLBag.java, write a class called LLBag that implements the Bag interface using a linked list instead of an array. You may use a linked list with or without a dummy head node.

In designing your implementation, you may find it helpful to compare the LLList class, our linked-list implementation of the List ADT, to the ArrayList class, our array-based implementation of that same ADT. In the same way that LLList uses a linked list instead of an array to implement a list, your LLBag class should use a linked list instead of an array to implement a bag.

Notes:

• Make sure that your class explicitly indicates that it implements the Bag interface. To allow your new class to compile, you will need to put it in the ps6 folder with Bag.java.

• Like the LLList class, your LLBag class should use a private inner class called Node for the nodes in the linked list.

• In addition to the methods in the Bag interface, your LLBag class should also have a toString() method that overrides the default toString() method inherited from the Object class. Consult the ArrayBag toString() method to see what the string returned by this method should look like.

• One of the benefits of using a linked list is that there is no need to specify a maximum size—the bag can effectively grow without limit. Therefore, you will not need to provide a constructor that specifies a maximum size, and your add() method can always return true.

• Because the order of the items in a bag doesn’t matter, you can add items to either end of the linked list; however, make sure that your method adds items in O(1) time.

• In general, you should make your methods as efficient as possible. For example, when implementing the remove() method, you should make sure that you don’t traverse the list more than once.

• Copy over the main() method from the ArrayBag class, and make whatever modifications are necessary to allow it to test your LLBag class.

  Important: If you compare the results that you obtain from testing the two classes, you may see that the items are not in the same order in both sets of tests. That is to be expected, and it’s not a problem because items in a bag do not have a position!

Problem 6: Palindrome tester

20 points; individual-only

1. (15 points) As you know a palindrome is a string like "radar", "racecar", and "abba" that reads the same in either direction. To enable longer palindromes, we can ignore spaces, punctuation, and the cases of the letters. For example:

   "A man, a plan, a canal, Panama!"
   

   is a palindrome, because if we ignore spaces and punctuation and convert everything to lowercase we get

   "amanaplanacanalpanama"
   

   which is a palindrome.

   In the file Palindrome.java that we’ve included in the ps6 folder, add a static method called isPal() that takes a String object as a parameter and determines if it is a palindrome, returning true if it is and false if it is not.

   A string of length 1 and an empty string should both be considered palindromes. Throw an exception for null values.

   Although we can implement solutions to this problem using recursion or an appropriately constructed loop that manipulates the String object directly, your method must use an instance of one or more of the following collection classes from the ps6 folder:

   • ArrayStack
   • LLStack
   • ArrayQueue
   • LLQueue

   You must not use any other data structure, including arrays or linked lists other than the ones that are “inside” instances of the above collections. Rather, you should put individual characters from the original string into an instance of one or more of the above collections, and use those collection object(s) to determine if the string is a palindrome.

   For full credit, you should:

   • Write your method so that spaces, punctuation, and the cases of the letters don’t prevent a string from being a palindrome. To put it another way, make sure that your method only considers characters in the string that are letters of the alphabet and that it ignores the cases of the letters. See our example above.

   • Make your method as efficient as possible. In particular:

     • You should perform only one iteration over the original String object. After that one iteration, any additional manipulations of the characters should be done using the collection object(s) that you have chosen to use.

     • Because we want to avoid unnecessary scanning, you may not use any of the built-in String methods except charAt() and length().

   Hints:

   • When constructing the collection object(s) that you decide to use, you will need to specify the appropriate data type for the items in the collection. Because char values are primitives, you should use the corresponding “wrapper” class, which is called Character.

   • You may also find it helpful to use the Character.toLowerCase() or Character.toUpperCase() method.

   • Remember that char values are essentially integers, so you can compare them just as you would compare integers.

2. (5 points) For professional programmers, writing well-formatted units tests is an extremely important part of their work. In the main() method of Palindrome.java, we’ve given you an example of what such a unit test should look like.

   Add five additional unit tests for your isPal() method to the main() method. Your unit tests must follow the same format as our example test. In particular, the output of each of your unit tests should include:

   • a header that specifies the test number and a description of what is being tested
   • the actual return value that you get from that test
   • the expected return value
   • whether the actual return value matches the expected return value.

   Put each test in the context of a try-catch block so that you can handle any exceptions that are thrown. Leave a blank line between tests.

Submitting Your Work

• You have read the Java Style Guide (linked on Course page)and followed all guidelines regarding format, layout, spaces, blank lines, and comments;
• You have removed or changed all comments inherited from my templates which do not relate to your solution;
• ensured that the signature of the methods specified in the assignment have not been changed.
• You have verified that your programs satisfy all the performance tests in the templates;

Follow the instructions and submit the following files:

• your ps6pr1.txt file for Problem 1
• your ps6pr2.txt file for Problem 2
• your ps6pr3.txt file for Problem 3
• your modified ArrayList.java and LLList.java files for Problem 4
• your LLBag.java file for Problem 5; if you worked with a partner, make sure that you each submit a copy of your joint work, and that you include comments at the top of each file specifying the name and email of your partner
• your modified Palindrome.java file for Problem 6