Homework 5 | CS 61B Fall 2017

Homework 5: HW5: Bit Operations, BSTs, and Asymptotic Analysis

A Bit-Twiddling Puzzle
Implementing a Packed Array: Nybbles.java
Linked Lists via Arrays (With a Twist)
Set of Strings
Asymptotic Analysis

A. A Bit-Twiddling Puzzle

Fill in the definition of lastBit(n) with a single return statement so that it returns the value of n with all but its last (least significant) 1-bit set to 0. For example, 100 in binary is 1100100, so lastBit(100) should return 4, which is 100 in binary. Your solution should only use the Java arithmetic operators and bitwise operations (&, |, ^, etc.).

public static int lastBit(int n) {
     return _____________;
}

B. Implementing a Packed Array: Nybbles.java

Let's suppose we have an application that strains our computer's primary memory capacity and need to fit large arrays of small integers into as little space as possible. We want a data type that provides an array of integers that are limited in range to $-8$ to $7$. Such integers are representable in 4 bits (half a byte, also known as a nybble). So in principle, it ought to be possible to store $N$ integers in an $N/8$-integer array (packing 8 4-bit integers into each int). Fill in the template below to provide a suitable small-int array type. Do not perform any additional new operations in the implementation (you may include as many as you want for testing, if you put them in a different file).

/** Represents an array of integers each in the range -8..7. */
public class Nybbles {
    /** An array of size N. */
    public Nybbles(int N) {
        /* DON'T CHANGE THIS. */
        data = new int[(N+7) / 8];
        this.N = N;
    }

    /** Return the number of nybbles in me. */
    public int size () { return N; }

    /** Return my Kth integer, numbering from 0.  Assumes 0 <= K < N. */
    public int get(int k) {
        if (k < 0 || k >= N)
            throw new IndexOutOfBoundsException();
        else 
            return /* REPLACE WITH ANSWER */ 0;
    }

    /** Set my Kth integer to VAL.  Assumes 0 <= K < N and -8 <= VAL < 8. */
    public void set (int k, int val) {
        if (k < 0 || k >= N)
            throw new IndexOutOfBoundsException();
        else if (val < -8 || val >= 8)
            throw new IllegalArgumentException();
        else 
            data[ /* REPLACE WITH ANSWER */ 0 ] =
                /* REPLACE WITH ANSWER */ 0;
    }

    // DON'T CHANGE OR ADD TO THESE.
    private private int N;
    private private int[] data;
}

C. Linked Lists via Arrays (With a Twist)

In the old days, programmers used array indices in place of pointers.
Pointed-to objects would be elements of an array, and pointers to those objects would be integer array indices. For example, one could implement a doubly linked list containing the three strings "dog", "cat", "pony" with three arrays and one integer variable (pointing to the start of the list). One way to do so is this:

String[] data = { "cat", "pony", "dog", null, null };
int[] next = { 1, -1, 0, -1, -1 };
int[] prev = { 2, 0, -1, -1, -1 };
int L = 2;

Here,

data contains the three strings in some order (not necessarily the intended order of the list), plus possibly some leftover space for later additions;
L contains the index of the first string ("dog") and represents a pointer to the start of the list; `
next[i] is the index of the list item that comes after the item stored at data[i];
prev[i] is the index of the list item that comes before the item stored at data[i];
-1 is used to represent the null pointer.

By means of a clever hack, we don't need two arrays prev and next. We can actually get away with one array whose elements represent pointers going both ways! Doing this relies on the properties of the exclusive-or operation: x^y, or, as it is often written in technical literature, $x \oplus y$ Specifically, since x^x==0 for all values of x, and since exclusive-or is associative and commutative, it's always true that x^y^y == x and x^y^x == y.

Suppose therefore that in place of arrays prev and next, we have one array, link, where link[i] = next[i]^prev[i]. Suppose I want to sequence through the list forward, starting at item L. We know that prev[L] is -1, so we can compute next[L] as n = link[L]^(-1). Now we have n == next[L] and L. Since L is prev[n], we can also compute next[n] (that is, next[next[L]]): it's just L^link[n]. In this way, we can proceed forward down the list. By symmetry, we can also proceed backwards from the end of the list, starting from a pointer to the end of the list (whose next value is -1). Thus, from the single array of integers, link, and the index of either end of the list, we can traverse the entire list.

In class, we saw the AbstractList class, which allows one to get a complete concrete implementation of a subtype of List just from implementing the methods size, get, add, set, and remove (or just the first two for a read-only list). There is another abstract class, java.util.AbstractSequentialList, which is better suited to implementing lists (such as linked lists) where random access (get) is slow, but where there is a fast way to iterate through the list sequentially. You can get a full-blown List implementation from AbstractSequentialList by implementing just size and listIterator. To implement listIterator, one generally has to also implement a subtype of java.util.ListIterator.

Fill in the skeleton class CompactLinkedList to implement a List class that uses the exclusive-or hack to represent a List with just one pointer per item.

D. Set of Strings

Complete the implementation of the type BSTStringSet, which implements the interface StringSet. As the class name suggests, the intended implementation uses a binary search tree. Don't use any of the Java Collection classes in your BST implementation (you may still use a List implementation to collect items for the asList method).

E. Asymptotic Analysis

For these problems, you should give a brief explanation as hw5.txt. You should not use any fancy typesetting tools (like LaTeX, Word, etc.). Just submit a text file called hw5.txt. You are not required to explain your solutions, but you are encouraged to do so.

Provide simple and tight asymptotic bounds for each of the following. Here, "simple" means roughly "no unnecessary terms or constants" and "tight" means "either the largest $\Omega(\cdot)$ and smallest $O(\cdot)$ bounds you can find, or if possible, a $\Theta(\cdot)$ bound."

$9x^2 + 3x + 14 \log x$
$\log(4x^3 + 2x^2)$
$\sum_{i=0}^{N}\sum_{j=0}^{i} j$.
The worst case running time of the following code fragment:
```
int j;
j = 0;
for (int i = 0; i < N; i += 1) {
   for ( ; j < M; j += 1) {
      if (bump (i, j)) 
         break;
   }
}
```
Assume that M and N are integers, and bump is a constant-time ($O(1)$) method that returns a boolean result. We're looking for a $\Theta$ result that uses M and N.

The worst case running time of the function f5 for the code below.

public static int f1 (int n) {
  int x = 0;
  for (int i = 0; i < n; i++) {
      x++;
  }
  return x;
}

public static int f5 (int n) {
  if (n <= 1) {
    return 1; 
  }
  return f1(n) + f5(n/2) + f5(n/2);
}

Give your answer as $\Theta$ result that uses n.