HW3 Solutions Credit given where due for solutions. 1. //by Irana Sheykh-Zade class Quatenary { /** A string consisting of integer n in base 4 notation * E.g.: quatenary(5) = "11", quatenary(-12)="-30" * No using +,-,*,/,% or java mathematical classes such * as BigInteger. */ public static String quatenary(int n) { String result = ""; char minus = 45; int sign = n & (1<<31); int temp = n; if (n == 0) { result = "0"; } if (sign == 0) { while (temp != 0) { int digit = temp & 3; result = String.valueOf(digit).concat(result); temp = temp>>>2; } return result; } else { result = String.valueOf(minus).concat (quatenary (Math.abs(n))); return result; } } } 2. // by Irana Sheykh-Zade class Adder { /** returns the sum of a & b without using +, -, *, /, % * or any java or other classes/ */ static int add(int a, int b) { int xor = a ^ b; int and = a & b; int result = xor; if (and != 0) { result = add (xor, (and<<1)); } return result; } } 3. by Chris Shaw Assume towards contradiction that (~x)+1 is not equal to -x. Therefore, x + (~x)+1 = c, where c does not equal 0. Let x be any arbitrary 32 bit number. Note that for any binary digit b, that b + (~b) yields 1. Therefore x + (~x) = d, where d is a 32 bit integer containing all 1's. But if we add 1 to d, we will end up with the 33rd bit being a 1, but the remaining 32 bits are zero which is a result of the rules of binary addition. As a 32 bit number (c), this is zero, which contradicts the original assumption. Therefore (~x)+1 = -x. 4. by Ryan Said The most efficient base is e (where ln(e) = 1). Proof: Given n dollars, we wish to find the base b that yields the largest number. Each digit in base b costs b dollars, so the number of digits that may be allocated given n dollars is n/b. With n/b digits, the largest number that can be represented is b^(n/b). Let f(b) = b^(n/b), so that f(b) represents the largest number that may be represented using base b (where n is constant). To maximize f, we simply set f'(b) ( = df/db) = 0 and solve for b. This calculation follows: First rewrite f(b): f(b) = b^(n/b) = e^(ln(b^(n/b))) = e^((n/b)*ln(b)). Now we solve f'(b) = 0 for b using the chain rule: d(e^((n/b)*ln(b))/db = (e^((n/b)*ln(b))*[-n*b^(-2) + n*b^(-1)/b] = (n/b^2)*(1-ln(b))*(e^((n/b)*ln(b))) = 0. Since b != 0 (base 0 has no meaning), n != 0 (with no money, we can't represent any number), and e^a != 0, where a is any real number, the above expression is equivalent to 1 - ln(b) = 0. Therefore, ln(b) = 1. So we have e^(ln(b)) = e^1 = e. In general, for all x > 0, e^(ln(x)) = x, so we have e^(ln(b)) = b = e. Thus the most cost efficient base is e. 5. Question postponed to the next homework. 6. /** A Priority Queue represented using a List */ // by Jeff Schoner, 7/15 public class ListPriorityQueue { /** True iff this is empty. */ public boolean empty() { // O(1) // if data list has no items, then the queue is empty return (data == null); } /** The element of the sequence with the highest priority. Requires * that !empty(). */ public Prioritized peek() { // O(1) return (Prioritized)data.head; } /** Return the element of the sequence with the highest priority * and remove it from the sequence. Requires that !empty(). */ public Prioritized remove() { // O(1) Prioritized result = (Prioritized)data.head; // save value for return data = data.tail; // front is always highest priority, so just remove it return result; } /** Put ITEM into the sequence. O(n) */ public void insert(Prioritized item) { if (empty()) { // if empty, it's simply the first item in the list data = new List(item, null); } else { if (((Prioritized)data.head).getPriority() < item.getPriority()) { // must be the higher than any other existing priority, so // it goes at the front of data data = new List(item, data); } else { // else search for it List pointer = data.tail; List previous = data; while (pointer != null) { // find the first item in data that has a smaller priority than item if (((Prioritized)pointer.head).getPriority() < item.getPriority()) { break; } previous = pointer; // advance the pointers pointer = pointer.tail; } /* insert right before the first priority smaller than item, or at the very end of the list if one has not been found */ previous.tail = new List(item, pointer); } } } List data; } /** A Priority Queue represented using an array */ // by Jeff Schoner, 7/15/00 public class ArrayPriorityQueue { /** True iff this is empty. */ public boolean empty() { // O(1) return (itemCount == 0); } /** The element of the sequence with the highest priority. Requires * that !empty(). */ public Prioritized peek() { // O(n) Prioritized highestSoFar = data[0]; for (int i = 1 ; i < itemCount ; i++) { if (data[i].getPriority() > data[0].getPriority()) { highestSoFar = data[i]; } } return highestSoFar; } /** Return the element of the sequence with the highest priority * and remove it from the sequence. Requires that !empty(). */ public Prioritized remove() { // O(n) Prioritized highestSoFar = data[0]; int highestIndex = 0; for (int i = 1 ; i < itemCount ; i++) { if (data[i].getPriority() > data[0].getPriority()) { highestSoFar = data[i]; highestIndex = i; } } itemCount -= 1; // shrink the sucker by one data[highestIndex] = data[itemCount]; // move last item into the hole return highestSoFar; } /** Put ITEM into the sequence. */ public void insert(Prioritized item) { // O(1) if (allocatedSize < itemCount + 1) { allocatedSize = allocatedSize * 2 + 1; // some arbitrary growth Prioritized[] newData = new Prioritized[allocatedSize]; // make new bigger array for (int i = 0 ; i < itemCount ; i++) { // copy everything over the to new one newData[i] = data[i]; } data = newData; // replace old with new } data[itemCount] = item; itemCount += 1; } int allocatedSize; int itemCount; Prioritized[] data; } 7. // by Jeff Schoner, 7/19/00 // this goes fairly quickly although I've heard there are faster solutions // using ints instead of longs makes things almost twice as fast, but // 2^31 - 1 < 75^5, so you really can't do that although the solution // is within the range of int. public class SevenEquation { public static void main(String args[]) { for (int i = 1 ; i <= 75 ; i += 1) { // only compute them once this way iFifth[i] = i * i * i * i * i; } long leftHandSum = 0; for (int a = 1 ; a <= 75 ; a += 1) { leftHandSum += iFifth[a]; for (int b = a ; b <= 75 ; b += 1) { leftHandSum += iFifth[b]; for (int c = b ; c <= 75 ; c += 1) { leftHandSum += iFifth[c]; for (int d = c ; d <= 75 ; d += 1) { leftHandSum += iFifth[d]; for (int e = d ; e <= 75 ; e += 1) { leftHandSum += iFifth[e]; for (int f = e ; f <= 75 ; f += 1) { if (leftHandSum == iFifth[f]) { System.out.println("[" + a + " " + b + " " + c + " " + d + " " + e + " " + f + "] = " + leftHandSum + ", " + iFifth[f]); System.exit(0); } /* if lhs is already less than f to the 5th, don't bother trying larger f values */ else if (leftHandSum < iFifth[f]) break; } leftHandSum -= iFifth[e]; } leftHandSum -= iFifth[d]; } leftHandSum -= iFifth[c]; } leftHandSum -= iFifth[b]; } leftHandSum -= iFifth[a]; } } static long[] iFifth = new long[76]; // one for each possible value } 8. // List2 class. // C.Shaw, 7/14/00 class List2 { public Object head; public List2 tail; /** The empty List. */ public List2() { tail = null; } /** Insert item X at the beginning of this list. That is, after * L.insert(X), L.tail points to a list containing the same items * that L originally pointed to and L.head is X. */ public void insert(Object X) { // Create a list object. List2 NewList = new List2 (); // Insert the object as the second object in this list. NewList.tail = tail; tail = NewList; // Reassign the object references so X is at the front of the list. NewList.head = head; head = X; } /** Remove the first item in this list. Assumes !isEmpty(). That * is, after L.delete(), L points to a list containing the same * items that L.tail originally pointed to. */ public void delete() { // Check to see if it's empty. if (isEmpty ()) throw new IllegalStateException ("List is already empty!"); // Make the first list object refer to the second data object. head = tail.head; // Reassign the reference pointer of the first list object to // skip the second list object. tail = tail.tail; } /** True iff there are no items in this list. */ public boolean isEmpty() { return tail == null; } } }