Grades

are now in CUNYFirst

some answers for final

again, link to the final


 2 3 + 4 ×

string Visit(node, priorPrecedence) {
  if node is number
    return number.ToString()
  result = Visit(left, node.precedence) +
           node.Operator +
           Visit(right, node.precedence)
  if node.precedence < priorPrecedence
    result = '(' + result + ')'
  return result
}

// two parts.
//part 1: build the expression tree.

Node buildExpressionTree(string s)
{
Stack<Node> St = new Stack<Node>();
for (char c : s)
{
switch(c)
{
case '+':
case '-':
case 'x':
case '/':
Node rhs = St.pop();
Node lhs = St.pop();
Node n = new Node(c);
n.right = rhs;
n.left = lhs;
St.push(n);
break;
default: // a digit
Node n = new Node(Integer.parse(c.toString()));
St.push(n);
}
}
return St.pop();
}

// part 2
// printing out the expression tree InOrder
void InOrder(Node n)
{
if (n == null)
return;
System.out.print("(");
InOrder(n.left);
System.out.print(" " + n.element + " ");
InOrder(n.right);
System.out.print(")");

}

test time and room

SB-B137 at 8:30 PM

And the winner is...

Cumulative!

data structures in a database

create a table. first define the structure, then i'll put in the actual data.

field - column, cell
record - row

an example of indexes in a database, stored as a tree structure. why would updates take longer now? why would lookup based on an indexed field be faster?


skip list data structure
http://en.wikipedia.org/wiki/Skip_list

Survey for the final

1 2 + 4 * 5 + 3 −

stack: 14

plan for today:
*1) show how to use a stack to evaluate a RPN expression

*2) go over three ways of reversing a singly linked list

*3) discussion of final
// fix TreeNode class so that there is one less in each array
int print_in_order(TreeNode current)
{
if (current == NULL) return 0;
int i;
int sum = 0;
for (i = 0; i < current.num_elements; i++)
{
sum += print_in_order(current.links[i];
// System.out.println(current.key_values[i] + " ");
}
sum += print_in_order(current.links[i];
return current.num_elements +sum ;
}




4) skip list

5) DFS

2)
void iterative_reverse()
{
 Node p, q, r;

 if(head == NULL)
  return;

 p = head;
 q = p.next;

 p.next = NULL;

 while (q != NULL)
 {
  r = q.next;
  q.next = p;
  p = q;
  q = r;
 }

 head = p;
}


void iterative_reverse_2()
{
 Stack s = new Stack();
 Node cur, prev;
 for (cur = head; cur != NULL; cur=cur.next)
 {
  s.push(cur);
 }
 head = s.pop();
 cur = head;
 while (! s.empty())
 {
  prev = cur;
  cur = s.pop();
  prev.next = cur;
 }
 cur.next = NULL;
 tail = cur;
}

public void reverse()
{
 reverse2(NULL, head);
 Node temp = head;
 head = tail;
 tail = temp;
}

private void reverse2(Node prev, Node current)
{
 if (current == NULL) return;
 reverse2(current, current.next);
 current.next = prev;

}