PolyListItr for use in
polyCompare:
public boolean isPastEnd()
{
return current == null;
}
public double getCoefficient()
{
return current.coefficient;
}
public int getExponent()
{
return current.exponent;
}
public void advance()
{
if ( !isPastEnd() )
current = current.next;
}
Then the function polyCompare is as follows:
// returns -1 if p1 < p2, 0 if p1 == p2, else 1 if p1 > p2
int polyCompare( PolyListItr p1, PolyListItr p2 )
{
while ( !p1.isPastEnd() && !p2.isPastEnd() )
{
if (p1.getExponent() > p2.getExponent()) // p1 greater than p2
return 1;
else if (p1.getExponent() < p2.getExponent()) // p1 is less than p2
return -1;
else if (p1.getExponent() == p2.getExponent()) // exponents equal check
if (p1.getCoefficient() > p2.getCoefficient()) // coefficients
return 1;
else if (p1.getCoefficient() < p2.getCoefficient())
return -1;
else
// exponents and coefficients equal, recurse on rest of the
// two polynomials
return (polyCompare(p1.advance(), p2.advance());
}
}
Note: the above code does not properly handle the case where the first n terms
of p1 are equal to the first n terms of the other polynomial, but the other
polynomial has m > n terms. How would you modify the code to handle this?
int sameStack(StackLi s1, StackLi s2)
{
private int s, t;
if (s1.isEmpty() && s2.isEmpty()) // both empty, return 1
return 1;
else if (s1.isEmpty() || s2.isEmpty) // not equal, one empty, not the
return 0; // the other, return 0
else {
s = s1.topAndPop();
t = s2.topAndPop();
if (s == t) // if equal, recurse on rest of
sameStack(s1, s2); // stacks
else
return 0; // elements not equal, return 0
}
}
Induction: Assume that it is true that a full binary tree of height k is 2^(k+1) - 1 nodes. We need to show that a full binary tree of height k+1 has 2^(k+2) - 1 nodes.
A full binary tree of height k+1 has a root node, and 2 subtrees, each of height k. Since we know that the number of nodes in a subtree of height k is 2^(k+2) - 1, this new tree of height k+1 has the following number of nodes:
= 2 * 2^(k+1) - 1 + 1 - 1
= 2^(k+2) - 1
This is called a recurrence relation, in which work is defined in
terms of
itself. At each step we do some constant amount of work
(signified by the 1 term) and then work on a problem of half size.
Eventually, the problem size will be small enough where we can
analyze it. This usually occurs when T(N) =
T(1) = O(1) - an input size
of 1 is solved in a constant time. In binary search, that just means
we can find the element in an array of size 1 in constant time.
To compute the running time for an input of size N =
2^k (N is a power of 2, which simplifies the analysis),
we can do the following:
T(4) = T(2) + 1
= T(1) + 1 + 1
= 1 + 1 + 1 = 3
T(8) = T(4) + 1
= T(2) + 1 + 1
= T(1) + 1 + 1 + 1
= 1 + 1 + 1 + 1 = 4
T(16) = T(8) + 1
= T(4) + 1 + 1
= T(2) + 1 + 1 + 1
= T(1) + 1 + 1 + 1 +1
= 1 + 1 + 1 + 1 + 1 = 5
Its clear that for an input of N =
2^k, the running time is a function of
k: T(N) = k + 1. And since
k = Log N, we can see that
T(N) = k + 1 = Log N + 1 = O(Log N)
-
/ \
/ \
* 6
/ \
/ \
* 4
/ \
/ \
5 +
/ \
/ \
4 ^
/ \
/ \
3 2
(c) postfix: 5 4 3 2 ^ + * 4 * 6 -
LinkedListItr for use in
evenList:
public boolean isPastEnd()
{
return current == null;
}
public int retrieve()
{
return current.data;
}
public void advance()
{
if ( !isPastEnd() )
current = current.next;
}
Here is the code for the evenList function:
LinkedListItr evenList(LinkedListItr L)
{
LinkedListItr Even, Lcur, Ecur, newItr;
ListNode n;
if (L.current.next != null)
Lcur = new LinkedListItr(L.current.next); // Lcur points to second node
else // in list
return null; // no even nodes is list, return null
// instantiate a ListNode object, with data of first even ListNode in list
n = new ListNode(Lcur.retrieve());
// instantiate a LinkedListItr object Even to reference the head of
// the new list
Even = new LinkedListItr(n);
// Ecur will point to the last node of the new list
Ecur = new LinkedListItr(Even.current);
while(Lcur.current.next != null)
{
Lcur.advance(); // advance to next odd node in original list
// if there is another even node in list
if (Lcur.current.next != null)
Lcur.advance(); // move to even node
// instantiate a new ListNode for the even list
n = new ListNode(Lcur.retrieve());
Ecur.current.next = n; // append new to end of Even list, move
Ecur.advance(); // Ecur to end of Even list
}
return Even; // return header of Even list
}
void delete(LinkListItr p)
{
LinkedListItr prev;
// instantiate a new LinkedListItr object that points to the previous
// node in the list
prev = new LinkedListItr(p.current.left);
prev.current.right = p.current.right; // prev points to node to the right
// of p in list
p.current.right.left = prev; // update the left pointer of node
// to the right of p
}
LinkedListItr for use in
reverse:
public boolean isPastEnd()
{
return current == null;
}
Here is the code for reverse:
LinkedListItr reverse(LinkedList tail)
{
LinkedListItr succ, prev, cur, newtail;
if (tail.isPastEnd()) // empty queue
return null;
if (tail.current.next == tail.current) // single node in queue
return tail;
// cur points to old head of queue
cur = new LinkedListItr(tail.current.next);
// new tail is the old head
newtail = new LinkedListItr(cur.current);
// prev points to old tail
prev = new LinkedListItr(tail.current);
// succ points to old head's next node
succ = new LinkedListItr(cur.current.next);
if (succ.current == tail.current) // only two nodes in queue, return
return newtail; // new tail
while (!succ.current == tail.current)
{
cur.current.next = prev.current; // point cur to its old predecessor
prev.current = cur.current; // advance prev one node
cur.current = succ.current; // advance cur one node
succ.current = succ.current.next; // advance succ one node
}
cur.current.next = prev.current;
succ.current.next = cur.current; // points old tail to its old
// predecessor
return newtail;
}
A
/ \
/ \
B C
/ / \
D E F
\ / \
G H I
void childSwap(BinaryNode t)
{
BinaryNode tmp;
if (t != NULL)
{
childSwap(t.left); // traverse left
childSwap(t.right); // traverse right
// swap child pointers
tmp = t.left;
t.left = t.right;
t.right = tmp;
}
}
static AvlNode doubleRotateWithLeft( AvlNode k3 )
{
AvlNode k1, k2;
k1 = k3.left;
k2 = k1.right;
k1.right = k2.left;
k3.left = k2.right;
k2.left = k1;
k2.right = k3;
k1.height = Math.max( height(k1.left), height(k1.right)) + 1;
k3.height = Math.max( height(k3.left), height(k3.right)) + 1;
k2.height = Math.max( k1.height, k3.height ) + 1;
return k3;
}
3
/ \
/ \
1 4
\ \
2 6
/ \
5 9
/
7
(b)
4
/ \
/ \
1 6
\ / \
2 5 9
/
7