## Navigation

- 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`.- Show that $\log_b f(x) \in \Theta(\log_{10} f(x))$ for any constant $b>1$. (To demonstrate a statement like this, go to the definition. You must find $K$ and $M$ such that $|\log_b f(x)| < |K\log_{10} f(x)|$ for $x > M$.
- Suppose that $p(x)$ is any polynomial in $x$ with positive coefficients. Show that $\log p(x) \in O(\log x)$.
- Suppose that $f(n)$ is a positive, non-decreasing function.

Show that $\lceil f(n)\rceil \in O(f(n))$, where $\lceil x \rceil$ is defined as $x$ rounded up to the nearest integer.