Problem Set 5

due by 11:59 p.m. on Tuesday, March 20, 2018

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 cs112-staff@cs.bu.edu.

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

Part I

45 points total

Problem 1: Comparing two algorithms

9 points; individual-only

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

Suppose that you want to find the largest element in an unsorted array of n elements. Algorithm A searches the entire array sequentially and keeps track of the largest element seen thus far. Algorithm B sorts the array using mergesort, and then reports the last element as the largest.

1. What is the big-O time efficiency of Algorithm A in the best, average, and worst cases? Explain your answer briefly. (You do not need to implement either algorithm. We just want you to analyze them.)

2. What is the big-O time efficiency of Algorithm B in the best, average, and worst cases? Explain your answer briefly.

3. Which algorithm is faster? Explain briefly.

Problem 2: Mergesort

6 points; 2 points for each part; individual-only

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

Given the following array:

{24, 3, 27, 13, 34, 2, 50, 12}

1. If the array were sorted using the version of mergesort presented in lecture, what would the array look like after the completion of the second call to the merge() method—the method that merges two subarrays? Note: The merge method is the separate helper method; is not the recursive mSort method.

2. What would the array look like after the completion of the fourth call to the merge() method?

3. The initial call to the recursive mSort() method is made from within the mergeSort() “wrapper” method. This initial call to mSort() is not a recursive call, because the method is not calling itself. Rather, all recursive calls to mSort() are made from within mSort().

   Assuming that the array has at least two elements, the initial invocation of mSort() makes two recursive calls (which in turn lead to other recursive calls, and so on). Starting with the initial array above, what would the array look like after the completion of the first of these two recursive calls?

Problem 3: Practice with references

16 points total; individual-only

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

A doubly linked list consists of nodes that include two references: one called next to the next node in the linked list, and one called prev to the previous node in the linked list. The first node in such a list has a prev field whose value is null, and the last node has a next field whose value is null.

The top portion of the diagram below shows a doubly linked list of characters that could be used to represent the string "cat".

Each of the nodes shown is an instance of the following class:

public class DNode {
    private char ch;
    private DNode next;
    private DNode prev;
}

(In the diagram, we have labeled the individual fields of the DNode object that contains the character 'c'.)

In addition to the list representing "cat", the diagram shows an extra node containing the character 'h', and two reference variables: y, which holds a reference to the second node in the list (the 'a' node); and x, which holds a reference to the 'h' node. The diagram also shows memory addresses of the start of the variables and objects. For example, the 'c' node begins at address 0x400.

1. (6 points) Complete the table below, filling in the address and value of each expression from the left-hand column.

   You should assume the following:

   • the address of the ch field of a DNode is the same as the address of the DNode itself

   • the address of the next field of a DNode is 2 more than the address of the DNode itself

   • the address of the prev field of a DNode is 6 more than the address of the DNode itself, which means that it is also 4 more than the address of the next field.

   Here is the table:

   expression         address       value
   ------------------ ------------- -----------
   x                                
   x.ch                             
   y.prev                           
   y.next.prev                      
   y.prev.next                      
   y.prev.next.next
   

2. (4 points) Write a Java code fragment that inserts the 'h' node between the 'c' node and the 'a' node, producing a linked list that represents the string "chat".

   Your code fragment should consist of a series of assignment statements. You should not make any method calls, and you should not use any variables other than the ones provided in the diagram. You may assume that your code is part of the main method in the DNode class, and thus it has direct access to the private fields of the DNode objects.

   Make sure that the resulting doubly linked list has correct values for the next and prev fields in all nodes.

3. (6 points) We will cover the process of using a loop to traverse a linked list during the first lecture after break, so you may want to hold off on this question until then.

   Suppose you have a doubly linked list of DNode objects in which the prev references have the correct values but the next references have not yet been initialized.

   Write a static method called initNexts() that:

   • takes one parameter, a reference to the last node of the linked list

   • traverses the linked list from back to front, filling in the next references

   • returns a reference to the first node of the linked list.

   You may assume that there is at least one node in the list.

   You do not need to code up this method as part of a class; simply include it in the same file as your other problems for this question. You may assume that the method is part of the DNode class.

Problem 4: Representing polynomials

16 points total; 4 points each part; individual-only

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.

Part II

55 points total

Problem 5: A merge-like approach to finding the intersection of two arrays

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

In a file named MergeIntersect.java, implement a static method named intersect that takes two arrays of integers as parameters and uses an approach based on merging to find and return the intersection of the two arrays – i.e., all values that are found in both arrays.

More specifically, you should do the following:

1. Begin by creating a new array for the intersection, giving it the length of the smaller of the two arrays.

2. Use one of the more efficient sorting algorithms from Sort.java to sort both of the arrays.

3. Find the intersection of the two arrays by employing an approach that is similar to the one that we used to merge two sorted subarrays (i.e., the approach taken by the merge method in Sort.java). Your method should not actually merge the two arrays, but it should take a similar approach—using indices to “walk down” the two arrays, and making use of the fact that the arrays are sorted. As the elements of the intersection are found, put them in the array that you created at the start of the method.

   For full credit:

   • The intersection that you create should not have any duplicates.

   • Your algorithm should be as efficient as possible. In particular, you should perform at most one complete pass through each of the arrays.

4. At the end of the method, return a reference to the array containing the intersection.

5. Add test code for your method to the main method. Recall that that you can use the Arrays.toString() method to convert an array to a string; import the java.util. package to gain access to the Arrays class.

Here are some example calls from the Interactions Pane in DrJava:

> int[] a1 = {10, 5, 7, 5, 9, 4};
> int[] a2 = {7, 5, 15, 7, 7, 9, 10};
> int[] result = MergeIntersect.intersect(a1, a2);
> result
{ 5, 7, 9, 10, 0, 0 }
> int[] a3 = {0, 2, -4, 6, 10, 8};
> int[] a4 = {12, 0, -4, 8};
> int[] result = MergeIntersect.intersect(a3, a4);
> result
{-4, 0, 8, 0}

Notes:

• In both tests, the array containing the intersection has the same length as the shorter of the original arrays.

• When the number of values in the intersection (call it n) is smaller than the length of the shorter array, we end up with extra 0s at the end of the array containing the intersection. This happens because the array of integers that we create is initially filled with 0s, and we only use the first n positions of the array.

  If 0 is one of the values in the intersection, it will also show up earlier in the results, as it does in our second test above.

Problem 6: Rewriting linked-list methods

35 points; individual-only

We will cover the process of using a loop to traverse a linked list during the first lecture after break, so you may want to hold off on this question until then.

In lecture, we’ve been looking at linked lists of characters that are composed of objects from the StringNode.java class. The class includes a variety of methods for manipulating these linked lists, and many of these methods provide functionality that is comparable to the methods found in Java String objects.

Some of the existing StringNode methods use recursion, while others use iteration (i.e., a loop!). In this problem, you will rewrite several of the methods so that they use the alternative approach.

0. Before you get started, we recommend that you put a copy of the original StringNode class in a different folder, so that you can compare the behavior of the original methods to the behavior of your revised methods.

1. Rewrite the length() method. Remove the existing recursive implementation of the method, and replace it with one that uses iteration instead.

2. Rewrite the toUpperCase() method. Remove the existing iterative implementation of the method, and replace it with one that uses recursion instead. No loops are allowed.

3. Rewrite the printReverse() method so that it uses iteration. This method is easy to implement using recursion–as we have done in StringNode.java–but it’s more difficult to implement using iteration. Here are two possible iterative approaches, either of which will receive full credit:

   • reverse the linked list before printing it: This approach is the trickier of the two, but we recommend it because it uses less memory, and it will give you more practice with manipulating linked lists. Remember that you may not use the toString() method for this or any other method. In addition, you should not use the print() method. Finally, don’t forget to restore the linked list to its original form!

   • use an array: Create an array of type char that is large enough to hold all of the characters in the string and use it to help you with the problem.

4. Rewrite the removeFirst() method. Remove the existing iterative implementation of the method, and replace it with one that uses recursion instead. No loops are allowed.

5. Rewrite the copy() method. Remove the existing recursive implementation of the method, and replace it with one that uses iteration instead.

Remember: Drawing diagrams will be a great help as you design your revised methods!

Submitting Your Work

You should use Apollo to submit the following files:

• your ps5pr1.txt file containing your solution for Problem 1
• your ps5pr2.txt file containing your solutions for Problem 2
• your ps5pr3.txt file containing your solutions for Problem 3
• your ps5pr4.txt file containing your solutions for Problem 4
• your MergeIntersect.java file containing your solution 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 StringNode.java file containing your solutions for Problem 6

Here are the steps:

1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
3. Find the appropriate problem set section on the main page and click Upload files.
4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
5. Click the Upload button at the bottom of the page.
6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.