Implement a template class queue from scratch; that is, don't use the C++ list other such data structure classes.

Implement queue as linked nodes, using an inner Node struct that is singly linked with a data member and next member that points to the next Node.

Node should have a constructor to initialze its members.

The queue class should have private members

• int size;
• Node *front;
• Node *rear;

and public members

• queue() /* constructor */
• void insert(const E& x)
• E peekfront() const;
• E remove();
• bool empty() const;
• int size() const;
• ~queue() /* destructor */

The destructor should delete all remaining nodes, if any.

Give the tilde (~) approximations for the following expressions:

1. a. N + 1
2. b. 1 + 1 / N
3. c. (1 + 1 / N)(1 + 2 / N)
4. d. 2N³ - 15N² + N
5. e. lg(2N) / lg(N)
6. f. lg(N² + 1) / lg(N)

Answers

1. a. N + 1 ~ N
2. b. 1 + 1 / N ~ 1
3. c. (1 + 1 / N)(1 + 2 / N) ~ 1
4. d. 2N³ - 15N² + N ~ 2N³
5. e. lg(2N) / lg(N) ~ 1
6. f. lg(N² + 1) / lg(N) ~ 2

Assume N is a power of 2: N = 2^k.

	int sum = 0;
	for(int n = N; n > 0; n /= 2) {
	   for(int i = 0; i < n; i++) {
	      sum++;
           }
        }
      

For N = 2^k

 N + N / 2 + N / 22 + ... + N / 2k =
	2k + 2k - 1 + ... + 1 =
        1 + 2 + 4 + 8 + ... + N
      

This sum is 2N - 1

So the growth is ~ 2N

For N = 2^k

	int sum = 0;
	for(int i = 1; i < N; i *= 2) {
	   for(int j = 0; j < i; j++) {
	      sum++;
           }
        }
      

For N = 2^k

	1 + 2 + 4 + ... + 2k - 1 = 
	2k - 1 =
	N - 1
      

So the growth is ~ N

For N = 2^k

	int sum = 0;
	for(int i = 1; i < N; i *= 2) {
	   for(int j = 0; j < N; j++) {
	      sum++;
           }
        }
      

For N = 2^k

	N + N + ... + N =   /* k terms */
        N * k =
        N * lg(N)
      

So the growth is ~ N * lg(N)

Sort a deck of cards with only these operations:

• look at the values of the top two cards
• exchange the top two cards
• move the top card to the bottom of the deck

For simplicity assume the cards are numbered 1 to N.

1. If the top card is N, move to the bottom
2. Else if the top card number is > second card, swap
3. Else move the top card to the bottom.

If N cards are moved to the bottom with no swaps and the top card is 1, the deck is sorted.

A clerk at a shipping company is charged with the task of rearranging a number of large crates in order of the time they are to be shipped out. So the cost of compares is very low (just look at the labels) relative to the cost of exchanges (move the crates). The warehouse is nearly full - there is extra space sufficien to hold any one of the crates, but not two. What sorting method sould the clerk use?

Insertion sort, but instead of exchanging elements in order to insert, move the item to insert to the extra space if it is smaller than the last item inserted. Then move the already inserted items over one place until the correct place is found. Finally move the item from the extra space to this location.

Here is insertion sort:

    1	
    2	  template<typename E>
    3	  static void sort(vector<E>& v)
    4	  {
    5	    for(unsigned int i = 1; i < v.size(); i++) {
    6	      // insert v[i] into v[0]...v[i - 1]
    7	      int pos = i - 1;
    8	      for(int j = i; j > 0 && v[j] < v[j-1]; j--) {
    9	        E tmp = v[j];
   10	        v[j] = v[j - 1];
   11	        v[j - 1] = tmp;
   12	      }
   13	    }
   14	  }

If we first find the smallest element and swap it with v[0], how can we simplify the inner loop?

Same except:

• Do one pass to find the minimum and put it in position 0.
• Then the code can just be:

    void sort(E[] a)
    {
      /* insert code here to find the minimum and swap it with a[0] */	    
      for(int i = 1; i < a.length; i++) {
         int j = i;
         while(v[j] < v[j - 1]) {
           swap(v, j, j - 1);
         }
      }
  	  

What's wrong with this idea for a max priority queue?

To implement find the maximum in constant time, why not use a stack or a queue, but keep track of the maximum value inserted so far, then return that value for find the maximum.

What has to happen if the maximum is removed?

The largest item in a heap must appear in position 1, and the second largest must be in position 2 or position 3.

Give the list of positions in a heap of size 31 where the kth largest (i) can appear, and (ii) cannot appear, for k = 2,3,4 (assuming the values are distinct).

1. 1st largest must be at position 0 (depth 0)
2. 2nd largest can be at positions 1 - 2 (depth 1)
3. 3rd largest can be at positions 1 - 6 (depth 1 or 2)
4. 4th largest can be at positions 1 - 14 (depth 1, 2, or 3)

Suppose that your application will have a huge number of insert operations, but only a few remove the maximum operations. Which priority-queue implementation do you think would be most effective: heap, unordered array, or ordered array, unordered linked list, ordered linked list?

Assume the number of remove the maximum operations is no more than 15.

The cost is the sum of insertions plus the deletions.

1. Unordered List

   	  N insertions costs N  (really some small constant times N)
   	  15 deletions costs about 15N (may have to search all items)
   	  Total = 16N
   	  

2. MaxHeap implementation

   	    N insertions costs Nlog(N)
   	    15 deletions costs about 15log(N)
               Total = Nlog(N) + 15log(N)
   	  

   If log(N) > 16 (that is, N > 2¹⁶ ~ 65000), max heap is more expensive.

Not the code, just the result