A.1.1 worst-case

f1 is n^2 or E
f2 is n^2 or E
f3 is n log n or D
f4 is 2^n or G
f5 is 1 or A

A.1.2 best-case
f1 is n or C
f2 is 1 or A
f3 is n or C
f4 is 2^n or G
f5 is 1 or A

---------------------

A.2 Hashing

A.2.3. The sequence <A H E B C D F I G> (using any format that captures a sequence)

A.2.4. no

A.2.5. yes

A.2.6. yes


-------------------

A.3 Sorting

A.3.7. yes. 

A.3.8. 
<12 13 15 17 14 16>
<13 14 15 17 16>
<14 16 15 17>
<15 16 17>
<16 17>
<17>

---------------------

A.4 Binary search trees

A.4.9. 
Any complete sequence that does not put a descendant before an ascendant.
For exempel <12 4 2 10 20 14 22 18 16 6 8>

A.4.10.
10 4 2// 6/ 8// 20 14/ 18 16// / 22//
or
14 4 2// 10 6/ 8// / 20 18 16// / 22//

A.4.11.
10 4 2// 6/ 8 7// / 20 14/ 18 16// / 22//
or
14 4 2// 10 6/ 8 7// / / 20 18 16// / 22//

A.4.12.
10 4 2// 6/ 8// 12/ 20 14/ 18 16// / 22//

------------------------

A.5 Graphs

A.5.13. 

<F E A C D B>

A.5.14.

{A, B, C, D}

------------------------

B.1 AVL trees:

Observe the problem recalls the height of a tree to be the length of a
longest path to a leaf (i.e., largest depth), and it gives as example
that the height of a tree containing a single node is 0.

15. Answer: minNodes(3)=7.

16.

Suppose minNodes(k) gives the minimum number of nodes in
an AVL tree of height k for any 0 <= k < h.

The root of an AVL tree of height h > 3 has to have two children as
the AVL property requires the absolute value of the difference between
left and right heights is at most one. So an AVL tree of height > 3 has
to have two children.

One of the two children has to have height h-1 (otherwise the root
would not be of height h).

By the AVL property, the other child can have height h-1 or h-2.

Since we would like to deduce the minimum number of nodes for height
h, and since the higher the tree the more nodes it has to have, then
the minimum number of nodes for height h is obtained with a root child
of height h-1 and another of height h-2.

The recurrence relation is:

minNodes(h) = 1 + minNodes(h-1) + minNodes(h-2)

with :
*  1 for the root
* minNodes(h-1) for a root child of height h-1
* minNodes(h-2) for a root child of height h-2

17. Assume h > 3.

Observe minNodes(0)=1, minNodes(1)=2, minNodes(2)=4, minNodes(3)=7.

Recall minNodes(k) = 1 + minNodes(k-1) + minNodes(k-2) for all k > 3

Since larger heights yield larger minNodes, we get:

minNodes(h) >= 1 + 2 minNodes(h-2)
	    >= 1 + 2 (1 + 2 minNodes(h-4))
	    >= 1 + 2 (1 + 2 (1 + 2 minNodes(h-6)))
	    >= 1 + 2^1 + ... + 2^(k-1) + 2^k minNodes(h-2k)

by unrolling the inequality until height h=4 or h=5 depending on whether h is odd or even, we get

* h is even, we unroll until height h=4 (since we assumed the recurrence for h >= 4) and k = (h-2)/2 to get h-2k=2:

minNodes(h) >= 1 + 2^1 + ... + 2^((h-4)/2) + 2^((h-2)/2) minNodes(2)
             = (2^((h-2)/2)-1) + 4*2^((h-2)/2)
	     = 5*2^((h-2)/2)-1 = (5/2) 2^(h/2) - 1

* h is odd, we unroll until height h=5 (since we assumed the recurrence for h >= 4) and k = (h-3)/2 to get h-2k = 3:

minNodes(h) >= 1 + 2^1 + ... + 2^((h-5)/2) + 2^((h-3)/2) minNodes(3)
             = (2^((h-3)/2)-1) + 7*2^((h-3)/2)
	     = 8*2^((h-3)/2)-1 = (8/2^(3/2)) 2^(h/2) - 1

So regardless of whether h is odd or even, as long as it is larger
than 3, we get:

minNodes(h) >= 2^(h/2) - 1

Given an AVL tree t with height(t) and nodes(t) nodes, if height(t) > 3, we get:

nodes(t) >= 2^(height(t)/2) - 1,

Hence, log2(nodes(t) + 1) >= height(t)/2

and hence, height(t) <= 2 log2(nodes(t) + 1)

So c1= 2, c2=1 and c3 = 0 would do.

------------------------------------------

B.2 Asymptotic claims:

18. no: the family of inputs just says it is possible to get
executions times in Omega(n). This does not contradict a worst
execution time in Theta(n²). For instance, the family could be in
Theta(n) and represent a best case.

19. yes: the family takes at least as much as n^2 log(n), strictly
more than the worst case (which cannot take more than n²).

20. yes: the best case takes at least n^2. Yet the algorithm always
takes Theta(n log n) steps, strictly less than the best case.


------------------------------------------

21.
int brute(const std::vector<int>& p, int& bp, int& sp){
  int max_profit  = 0;
  bp = sp = 0;
  for(int i=0; i < p.size(); i++){
    for(int j=i; j < p.size(); j++){
      int profit = (p[j] - p[i]);
      if(profit > max_profit){
	max_profit = profit;
	bp = i;
	sp = j;
      }      
    }
  }
  return max_profit;
}

22.

int dAc(const std::vector<int>& p, int& bp, int& sp){
    return divide(p, 0, p.size()-1, bp, sp);
}


int conquer(const std::vector<int>& p, int lo, int mid, int hi, int& mlo, int& mhi){  
  mlo= mid; 
  int smallest_left=p[mid]; 
  for(int i= mid-1; i >= lo; i--){
    if(p[i] < smallest_left){
      mlo = i;
      smallest_left = p[i];
    } 
  }
  mhi= mid; 
  int largest_right = p[mid];
  for(int i= mid+1; i <= hi; i++){
    if(p[i] > largest_right){
      mhi = i;
      largest_right = p[i];
    } 
  }
  return largest_right - smallest_left;
}


int divide(const std::vector<int>& p, int lo, int hi, int& bp, int& sp){
  if(lo == hi){
    bp = sp = lo;
    return 0;
  }
  int mid = lo + (hi-lo)/2;
  int left_lo, left_hi;
  int left_sum = divide(p, lo, mid, left_lo, left_hi);

  int right_lo, right_hi;
  int right_sum = divide(p, mid+1, hi, right_lo, right_hi);

  int mid_lo, mid_hi;
  int mid_sum = conquer(p, lo, mid, hi, mid_lo, mid_hi);

  if(mid_sum >= left_sum && mid_sum >= right_sum){
    bp = mid_lo;
    sp = mid_hi;
  if(mid_sum >= left_sum && mid_sum >= right_sum){
    bp = mid_lo;
    sp = mid_hi;
    return mid_sum;
  }
  if(left_sum >= mid_sum && left_sum >= right_sum){
    bp = left_lo;
    sp = left_hi;
    return left_sum;
  }

  bp = right_lo;
  sp = right_hi;
  return right_sum;

}

23.

dAc uses two help functions: A recursive divide function, and a conquer
function.

The divide function is given a range where to look for a maximal
profit interval. If the range is empty, it returns
directly. Otherwise, it computes a middles point in the range and uses
it to define three problems: identify a maximal range to the left of
the midpoint, one to the right of it, and one that starts on the left
and finished to the right.

For the left and right cases, it calls itself with the corresponding
ranges.

However, the maximal profit interval might start to the left of the
middlepoint and finish to the right of it. This is covered by the
"conquer" function which looks for the cheapest prices to the left of
the middlepoint to the most expensive price to the right.

The three intervals are then compared to choose one with highest profit,
which is returned with the corresponding ranges.

24.

divide does divide the range in two, so there can be at most log2(n) levels.

At each level, divide performs a constant amount of work (finding midllepoint,
calling itself twice and conquer ones, and combining the results and returning
a best one).

However, conquer goes through the whole range each time to find cheapest buying
price to the left and cheapest one to the right. This is a linear amount of work
in the size of the range.

Hence, log2(n) levels with a linear amount of work at each level, which gives
Theta(n log2(n)).

25.

int simpler(const std::vector<int>& p, int & bp, int & sp){

  int min = 0;
  bp = sp = 0;

  for(int i=0; i < p.size(); i++){

    if(p[i] < p[min]){
      min = i;
    return mid_sum;
  }
  if(left_sum >= mid_sum && left_sum >= right_sum){
    bp = left_lo;
    sp = left_hi;
    return left_sum;
  }

  bp = right_lo;
  sp = right_hi;
  return right_sum;

}

23.

dAc uses two help functions: A recursive divide function, and a conquer
function.

The divide function is given a range where to look for a maximal
profit interval. If the range is empty, it returns
directly. Otherwise, it computes a middles point in the range and uses
it to define three problems: identify a maximal range to the left of
the midpoint, one to the right of it, and one that starts on the left
and finished to the right.

For the left and right cases, it calls itself with the corresponding
ranges.

However, the maximal profit interval might start to the left of the
middlepoint and finish to the right of it. This is covered by the
"conquer" function which looks for the cheapest prices to the left of
the middlepoint to the most expensive price to the right.

The three intervals are then compared to choose one with highest profit,
which is returned with the corresponding ranges.

24.

divide does divide the range in two, so there can be at most log2(n) levels.

At each level, divide performs a constant amount of work (finding midllepoint,
calling itself twice and conquer ones, and combining the results and returning
a best one).

However, conquer goes through the whole range each time to find cheapest buying
price to the left and cheapest one to the right. This is a linear amount of work
in the size of the range.

Hence, log2(n) levels with a linear amount of work at each level, which gives
Theta(n log2(n)).

25.

int simpler(const std::vector<int>& p, int & bp, int & sp){

  int min = 0;
  bp = sp = 0;

  for(int i=0; i < p.size(); i++){

    if(p[i] < p[min]){
      min = i;
    }
    if((p[i] - p[min]) > (p[sp] - p[bp])){
      bp = min;
      sp = i;
    }
  }

  return p[sp] - p[bp];
}


At the beginning (when i=0), the profixt is 0 as buying and selling
occur on the same day.

The loop always keeps track of the index of the cheapest buying price
encountered so far as this would be the best buying price if we are to
sell in the future.

As the loop progresses to i, either the selling price at i will give a
better margin compared to the current one (in which case we use the
chea+est buying price encouterd so far), or it does not improve the
margin.