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;

}

A sample final

https://docs.google.com/Doc?id=ajbqhgmq9qdz_356c8wv4tc6

Here are three reverse methods I came up with

Three methods:
1) simple iteration
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;
}

2) Using a stack data structure
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;
}

3) using the call stack
void reverse()
{
reverse2(NULL, head);
Node temp = head;
head = tail;
tail = temp;
}

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

class Node
{
    char element;
    int next;
}

class SinglyLinkedList
{
    Node []space = new Node[100];
    int head = -1;
    int tail = -1;
    int size = 0;

    InsertBeginning(char val)
    {
        index = mymalloc(space);
        space[index].element = val;
        space[index].next = -1; // in general

        space[index].next = head;
        head = index;
    }
    etc., etc.
}

how do we allocate this memory from the array?

i gave an example, using a linked list, where each node had a start position and a length property.

but however you do it, malloc


summary of data structure: using xor, we can use a single link field to navigate a linked list in either direction. we need a history of the previous element, xor it with link field, that yields address of 'next' / 'prev' element.

Related to a midterm question. *Print* a singly linked list in reverse order.

main()
{
    print_reverse(head);
}
void print_reverse(Node *current)
{
    if (current == NULL)
        return;
    else
        print_reverse(current->next);
    cout << current->value << " ";
}

note to self: still need to see recursive reverse


"unrolled linked list"
http://en.wikipedia.org/wiki/Unrolled_linked_list

class Node
{
Node next;
int element;
}

class SinglyLinkedList
{
Node head, tail;
int size;
// methods go here
}

Node remove(int value)
{
Node cur = head;
while (cur != null && cur.next != null &&  cur.next.value != value)
cur = cur.next;

cur.next = cur.next.next;
}

void swap(Node x, Node y)
{
int temp;
temp = x.value;
x.value = y.value;
y.value = temp;
}

Date and Time for the Final

Monday, May 23, 8:30 PM- 10:30 PM

they had messed up AM and PM.

All the midterms are graded

However, there is a pile of graded midterms I still need to locate. So check BlackBoard, and you may see your grade there. If not, sorry -- I'll post them just as soon as I have opportunity to search.

The grades are out of 5. Multiply that by 20 to get your score. This is uncurved. Any curve, assuming there is one, will be applied at the end of the semester.