======================================================
Review Questions
======================================================
1.

Write a function to delete the nth node of a linked list.

By deletion, we mean a relinking of three nodes such that deleted node is
orphaned andthe node pointing to the deleted node now refers to the deleted
node's next 
node.



2) You are designing a base Shape class intended to be the superclass
for Rectangle, Oval, and Triangle, and are trying to decide how to
handle computing the area. Each shape subclass will have its own
definition of the area method. For Shape itself you have three options:
create an area method that returns 0, declare area as an abstract
method, or leave area out of the Shape class and have each subclass
declare area themselves. Which of the three is the better design
decision? Explain what makes that choice better than each of the other
two options.

3. For this problem, you will design C++ classes suitable for managing
information about stores. Stores come in many variants, in addition to
your garden variety general store, there are Bargain stores, Gouge
stores, and HighBrow stores.

Every store keeps track of its inventory using Item objects. An Item
object tracks the item name, current quantity in stock, and cost the
store paid for the item. Stores will need to search for items by name
and track a list of competitors (which are other stores).

We're interested in what happens when you try to purchase some items by
sending a purchase(tvector<string> shoppingList) message to the Store
object. The shoppingList is the names of the items we want to buy. The
stores inventory should be depleted by one for each item we purchase,
and the return value from purchase is the total bill after buying all
items.

In general, stores mark up items with a 50% profit. So if the store paid 
$10 for an item, they charge $15 to their customers. However, Bargain
stoees are a bit different in this regard. They set their price by
checking with all of the competitors and matching the lowest price of
any competitor. If no competitor sells the item, a Bargain store sticks
with the usual 50% markup over supplier cost. Gouge stores also check
with their competitors, but only to see if any of them have the item in
stock, if all competitors are out of an item, they double the usual
marked-up price to make an extra profit. All HighBrow stores tack on the 
same the same luxury tax on mroe expensive items. Currently, they add
$10 to the retail price of an any item marked up to $100 or more, but
both the threshold and the additional amount are expected to change in
the future, so you must plan for  this.

When you try to purchase an item that the store does not sell or has
run out of, most stores just skip over it and add nothing to the
bill. In order to avoid inconveniencing you, HighBrow stores try to buy
the item for you from one of its competitors and directly pass the cost
on to you as part of your bill.

In order to show customers are valued, HighBrow stores automatically
deducts 5% from the total of any purchase of $200 or more. Bargain
stores run a promotion where every 1000th customers gets their purchase
entirely for free.

Assume the Item class is provided to you and responds to these messages:

class Item {
  public:
  string getName();                // name of item
  double getSupplierCost();        // price the store paid for the item
  int getQuantity();               // quantity of item in store's stock
  void changeQuantity(int delta);  // add/subtract from inventory
}

a) Design a class hierarchy to model stores. Draw a tree of your
hierarchy. List the instance variable and methods (including their
types/prototypes) for each class. You will need not metion or define
constructors or other setup code at all - just assume that a miracle
occurs and you objects are set up at run time. You do not need to deal
with access specifiers.

b) Give the code to implement the double purchase(tvector<string> shoppingList) 
method for all stores and all its necessary helper methods.

============================================================
Big-Oh
============================================================
1. Describe what it means for a function to be O(N).

A function is O(N) if it's rate of growth is less than or equal to the
function f(n) = N for sufficiently large N.

2. 

What is the Big-oh for the following algorithm:

bool  mystery (int n) {
if (n == 2) return true;
else if (n % 2 == 0)
   return mystery (n/2);
else 
   return false;
}

O(logn)

3.
What is the Big-oh for the following algorithm:

bool mystery (int n) {
   while ( n != 2) {
      if (n % 2 == 0) 
         n /= 2;
      else 
         return false;
   }
   return true;
}

O(logn)

4.
What is the Big-oh for the following algorithm:

bool mystery (int n) {
   tvector<bool> v(100);

   int i = 2;
   
   while (i < 100) {
      v[i] = true;
      i *= 2;
   }

   if (n < 100) return v[n];
   else return -1;
}

O(1)


============================================================
Linked Lists
============================================================

a)
Node circle(int n) 
{
  Node* first, last;
  first = 0;
  first = last = new Node(n, 0);
  for (int i = n - 1; i > = 1; i--)
    first = new Node(i, first);
  last->next = first;
  return first;
}

b)
Pair josephusSurvivors(int numPeople)
{
  Node* victim = 0;
  Node* survivor =  circle(numPeople);
  int last, nextTo;

  last = nextTo = 0;
  while (true) {
    victim = survivor->next;
    nextTo = last;
    last = victim->position;
    /* remove victim from list of survivors */
    survivor->next = victim->next;

    if (victim == survivor) break;
    survivor = survivor.next;
  }
  p.lastKilled = last;
  p.nextToLastKilled = nextto;
  return p;
}



Stacks
============================================================
1.
A fully parenthesized infix expression is:

   (exA op exB)

where exA and exB can be either another fully parenthesized infix
expression, or a number.  Write a method that converts a String of fully
parenthesized infix expression to postfix notation.  Consider only
operations +, -, *, and /.  Also assume that there are no spaces in the
input String, and each number is preceded by the character '#'.  Assume
correct input (meaning don't check for bad input).

string InToPost(string infixExp) {
  
  
}

   A sample input String:

(#21-(((#252*(#87-#4))+#113)*#50))

and the correct output String would be:

#21#252#87#4-*#113+#50*-

-------------------
Binary Search Trees
-------------------

1.  Manually provide the inorder, preorder, and postorder traversals of
    the binary search tree:


                       49
                      /  \
                    /      \
                  /          \
                28            83
              /    \        /    \
            18     40      71     97
           /  \   /  \    /  \   /  \
          11  19 32  44  69  72 92  99


Inorder:
11 18 19 28 32 40 44 49 69 71 72 83 92 97 99

Preorder:
49 28 18 11 19 40 32 44 83 71 69 72 97 92 99

Postorder:  (sort of trickier!)
11 19 18 32 44 40 28 69 72 71 92 99 97 83 49

2.  Level-order traversal of a binary tree -- in which the node values
    are printed level by level starting at the root node level.  The
    nodes on each level are printed from left to right.  The
    level-order traversal is not a recursive algorithm.  It uses a
    queue object to control the output of the nodes.  Fill in the
    following algorithm:

    1.  Insert the root node in the queue
    2.  While there are nodes left in the queue
	      Get the next node in the queue
              (soln I)
	      -----------------------------
                Print the node value, or put it in your return string.
  	      -----------------------------
	      If the pointer to the left child of the node is not
	      null,
	      (soln IIa)
	      -----------------------------
                Insert the left child node in the queue
	      -----------------------------
	      If the pointer to the right child of the node is not
	      null,
	      (soln IIb)
	      -----------------------------
               Insert the right child node in the queue
	      -----------------------------

   Furthermore, write the function levelOrder that implements the
   algorithm.

   string levelOrder (TreeNode *t) {


   }


3.  One problem with the binary tree sort is that the order in which
    the data is inserted affects the shape of the tree - for the same
    collection of data, different orderings can yield binary trees of
    dramatically different shapes.  The performace of the binary tree
    sorting and searching algorithms is sensitive to the shape of the
    binary tree.  What shape would a binary tree have if its data were
    inserted in increasing order?  In decreasing order?  (very simple)


Like a linked list for both types of data.



    Suppose my job is to assign student IDs to 100 students.  Given that SID
    is 8 digits, how can I make my search tree better?  (give at least
    2 suggestions) 


       I.   Not to assign SID consecutively -- jump back and forth
            within a subset of numbers, say, within 1399XXXX.
       II.  Stay away from tree all-together.  Use table entries,
            perhaps some sort of hashing table.
       III. Balance the tree -- Make sure the tree is stored as a
            AVL, Red-Black, etc.
       IV.  Store the students in groups in separate trees.  Lookup
            can be done by first determining which group the student
            belongs to (eg. Hash Table), and then search through the
            particular tree.

-----
Heaps
-----
1. 

Give a good logarithmic time bound for finding the Nth largest element in
a set of M elements which is stored in a

1. Heap 
N log M
2. Binary Search Tree
N
3. Sorrted Vector
1
4. Sorted Linked List
N

2. A treap is a data structure which combines elements of a heap and a
binary search tree. In it, for every node we create a priority, using a
hashing function. When we are later inserting the new node into a treap we
make sure of two things: 1) any left children of the final position of the
node are smaller then or equal to the current node, and any right children
are greater than it, and 2) the priority of all children of this node will
always be smaller than the priority of the node.

Given the definition

struct TreapNode {
  int label;
  int priority;

  TreapNode *left, *right;

  ....


}

write the function 
TreapNode insert (TreapNode *P) {
   if (p->label > label) {
      if (right == null)
        right = P;
      else 
      	right = right->insert(P);
      if (right->priority > priority)
        rotateLeft();
   }
   else {
      if (left == null)
        left = P;
      else 
      	left = left->insert(P);
      if (left->priority > priority)
        rotateRight();
   }
}



-----------
Hash Tables
-----------


1.


separate chaining because it won't cause the clustering associated with
the other schemes and you don't need to allocate a specific amount of
memory in advance that may or may not be used.


Sorting
------------------------------------------------------------

1. 
in ascending order
2. 

in descending order

3. 

The minimum number each time as a pivot is the worst, so...

5 7 12 14 15 43 54 56 78 87


4. 
The time for Merge sort doesn't depend on the data sequence.
We just divide the list in half each time. We merge for all sizes
greater than 1, so we know smallest merge will be when we have
2 elements

There were 15 elements, so we round up to the nearest power of 2 (16)

        1           1
    1       1       2
  1   1   1   1     4
 1 1 1 1 1 1 1 1    8
                    --
                    15 (or n - 1)

The number of calls to merge is generally equal to the number of
interior nodes of balanced binary tree with n leaves.

5.
We can just divide the set into those which are less than or equal to
the pivot and those which are greater than or EQUAL to the pivot. The
reason is that we'd otherwise be moving elements from one side of the
partition to another for no goof reason.

6.  
Median of three helps when the middle value is the smallest or the
biggest.  That follows from earlier part that the algorithm is only
O(n^2) when the pivot is at the end of the values to be sorted.


7. 
We further reduce the probability of drawing a pivot which is close to
minimum of the array and getting a "bad split." It actually turns out
that median of 5, 7, and so on do not do much better in general that
median of three, especially considering the average overhead of
computing the median of 5 or more numbers.

8.
Merge sort always recurses all the way through the list. We want to use
insertion sort when the number of inversions is low (i.e. when the list 
is close to being sorted).

9 
If the pivot is always the smallest of all the values to be sorted, then
we will sort one value at a time, and thus costing O(n^2).

10.

Make one sorted list by ai (O(nlogn))
ai: (0.0, 0.2), (0.1, 0.25),  (0.35, 0.65), (0.4, 0.6), (0.8, 0.9)

Let:
  (ai, bi) be the ith element in the array sorted by ai

if (a0 != 0)                // border case
  add the interval (0,a0)

maxb = b0 
for (i=1; i < n; i++)
  if (maxb < ai)
    add the interval (maxb, ai)
    maxb = bi
  else if (maxb < bi)
    maxb = bi

if (maxb < 1)
  add the interval (maxb, 1)


Graphs
------------------------------------------------------------

1. 

Since the graph is acyclic, we don't have to store all visited nodes. 
Breadth first search has to maintain the whole frontier that it currently 
searching. We refer to b as the branching factor. Every step we get
deeper in the graph, the number of nodes we in our queue is multiplied
by a factor up to b.

BFS: O(b^d)

Depth first search only has to maintain the current path in the
stack. The longest path can never be longer than d and there were max b
choices at step along the way.

DFS: O(bd) 

2. Give a simple example of a directed graph with negative-weight edges
for which Dijkstra's algorithm produces incorrect answers.

3. 
Sort of like topological sort/depth first search:

Keep looking until we find a marked node. We only look through nodes
with degrees of 1. 

for (int v=0; v < G.numVertices(); v++)
  count[v] = G.Degree(v);

Stack fringe;
for (int v=0; v < G.numVertices(); v++)
  if (count[v] == 1)
    fringe.push(v);

while (!fringe.isEmpty()) {
  Vertex v = fringe.pop();
  v.mark
  for each edge (v,w) {
    if (w.getMark())
      return false; // found our cycle
    
    count[w]--;
    if (count[w] == 1)
      fringe.push(w)


C++
------------------------------------------------------------
1)what does the following code print out:

void swap1(int a, int b) {int t = a; a = b; b = t;}
void swap2(int &a, int &b) {int t = a; a = b; b = t;}
main() {
  int a = 3; int b = 3;
  int d = 4; int e = 4;
  swap1(a, d); swap2(b, e);
  cout<<a<" "<<d<<endl;
  cout<<b<" "<<e<<endl;
}


  4 3
  3 4

--------------------------------------------------
2)what is wrong with the following code for the file test.cc, and how
would you fix it?:
main(){
  int x = 5;
  fun(x);
  cout << x << endl;
}
int fun(int x) {x++;}

the function fun is defined after it is called by another function,
which will result in compilation errors.
reasoning:
unlike java, for compiler reasons you cannot call a function before it
is defined because the compiler can't be sure that when you call it you
are passing the correct variable types, etc.. to remedy this you have 3
options:
1.put the definition of fun before main.
2.put the function prototype before main (ie; int fun(int);)
3.put the function prototype in a file called test.h and have the first
line of test.cc be:#include <test.h>
  
draw that memory looks like after each block is executed: