CS35: Test 3 Study Guide

We have \(P(n) \equiv \sum\limits_{i=1}^{n} i \cdot 2^i = 2^{n+1}(n-1) + 2\).

The base case, \(P(1)\), is to say \(\sum\limits_{i=1}^{1} i \cdot 2^i = 2^{1+1}(1-1) + 2\). We reduce this as follows:

\begin{align*} \sum_{i=1}^{1} i \cdot 2^i &= 2^{1+1}(1-1) + 2 \\\\ 1 \cdot 2^1 &= 2^{2}(0) + 2 \\\\ 2 &= 0 + 2 \end{align*}

For the inductive case, we show that \(P(k)\) implies \(P(k+1)\) for positive \(k\).

\begin{align*} \sum_{i=1}^{k} i \cdot 2^i &= 2^{k+1}(k-1) + 2 \\ \left(\sum_{i=1}^{k} i \cdot 2^i\right) + (k+1)\cdot 2^{k+1} &= 2^{k+1}(k-1) + 2 + (k+1)\cdot 2^{k+1} \\ \sum_{i=1}^{k+1} i \cdot 2^i &= 2^{k+1}(k-1) + 2^{k+1}(k+1) + 2 \\ \sum_{i=1}^{k+1} i \cdot 2^i &= 2^{k+1}(k-1+k+1) + 2 \\ \sum_{i=1}^{k+1} i \cdot 2^i &= 2^{k+1}(2k) + 2 \\ \sum_{i=1}^{k+1} i \cdot 2^i &= 2^{k+2}(k) + 2 \\ \sum_{i=1}^{k+1} i \cdot 2^i &= 2^{(k+1)+1}((k+1)-1) + 2 \\ \end{align*}

As we have shown both the base case and the inductive case, \(P(n)\) must be true for all integer \(n>1\).

We have \(P(n) \equiv \sum\limits_{i=1}^{n} \frac{3}{4^i} = 1 - (\frac{1}{4})^n\).

The base case, \(P(1)\), is to say \(\sum\limits_{i=1}^{1} \frac{3}{4^i} = 1 - (\frac{1}{4})^1\). We reduce this as follows:

\begin{align*} \sum_{i=1}^{1} \frac{3}{4^i} &= 1 - (\frac{1}{4})^1 \\ \frac{3}{4^1} &= 1 - (\frac{1}{4})^1 \\ \frac{3}{4} &= 1 - \frac{1}{4} \\ \frac{3}{4} &= \frac{3}{4} \\ \end{align*}

For the inductive case, we show that \(P(k)\) implies \(P(k+1)\) for positive \(k\).

\begin{align*} \sum_{i=1}^{k} \frac{3}{4^i} &= 1 - (\frac{1}{4})^k \\ \left(\sum_{i=1}^{k} \frac{3}{4^i}\right) + \frac{3}{4^{k+1}} &= 1 - (\frac{1}{4})^k + \frac{3}{4^{k+1}} \\ \sum_{i=1}^{k+1} \frac{3}{4^i} &= 1 - \frac{1^k}{4^k} + \frac{3}{4^{k+1}} \\ \sum_{i=1}^{k+1} \frac{3}{4^i} &= 1 - \frac{4}{4^{k+1}} + \frac{3}{4^{k+1}} \\ \sum_{i=1}^{k+1} \frac{3}{4^i} &= 1 + \frac{3-4}{4^{k+1}} \\ \sum_{i=1}^{k+1} \frac{3}{4^i} &= 1 - \frac{1}{4^{k+1}} \\ \end{align*}

As we have shown both the base case and the inductive case, \(P(n)\) must be true for all integer \(n>1\).

A Dictionary stores keys and their associated values.

The operations contains(key), get(key), insert(key, value), and remove(key) must run efficiently.

The implementations that we considered were Binary Search Trees, AVL Trees, Hash Tables, and Linear (using vectors).

Binary Search Trees

Run time: \(O(h)\) where h is the height of the tree, which in the worst case could be \(O(n)\)

Because BSTs do not have any height guarantees, and AVL Trees do, we would typically prefer the AVL Tree over a BST.
AVL Trees

Run time: \(O(\log n)\)

This implementation is preferred when knowing some information about the ordering of the keys is important. For instance we can easily find the min or max key within this implementation.
Hash Tables

Run time: \(O(1)\), on average

This implementation is the fastest on average, and is thus preferred in most cases. However, it trades space for time, so there might be situtations where you are not willing to make this tradeoff. It also requires the use of a hash function, which for some domains may be non-trivial to create.
Linear (using vectors)

Run time: \(O(n)\)

This implementation is preferred when the size of the dictionary is known to be small and this simpler approach will have less overhead.

A node is an object that holds the key, value, and pointers to the left and right children of a particular location within a tree data structure.
A leaf is a node in a tree that has no children.
The height of a tree is the number of levels below the root; or the number of edges in the longest path from the root to a leaf; or one less than the number of levels in the tree.
A binary tree is a tree for which each node has at most one left child and at most one right child.
A binary search tree is a binary tree in which, for each node, all keys in the left subtree are less than the node’s key and all keys in the right subtree are greater than the node’s key.
An AVL tree is a binary search tree in which, for every node, the height of the left subtree and the height of the right subtree differ by no more than one.
A max heap is a complete binary tree in which every node’s prioiry is greater than or equal to the priorities of its children.

No, this is not the only BST that could hold these keys. If the keys were inserted in sorted order from 1 through 22, then the tree would be a long line of right branches with 1 at the root and 22 as the only leaf.

This is not a BST. The key 29 is to the right of the key 30, which violates the Binary Search Tree Property.

If the key 22 where inserted into this BST, it would have to be to the right of the key 17.

It is only possible to perform left rotation if the root has a right child; a binary tree with no right child of the root cannot be left-rotated.

Method rebalance()
  d <- rightChild.height - leftChild.height
  If d < -1 Then
    If leftChild.leftChild.height < leftChild.rightChild.height Then
      leftChild.rotateLeft()
    EndIf
    this.rotateRight()
  Else If d > 1 Then
    If rightChild.leftChild.height > rightChild.rightChild.height Then
      rightChild.rotateRight()
    EndIf
    this.rotateLeft()
  EndIf
End Function

Showing the heights above each node:

Showing the insertion of 1 into the tree and the changed heights as bold.

Inserting 15 into the original tree. Note that a rebalancing is necessary because 17 was out of balance after the 15 was added.

Removing 5 from the original tree. No rebalancing is necessary.

Removing 9 from the original tree.

Removing 6 from the original tree.

A priority queue has a priority type as well as an element type. When elements are enqueued into a priority queue, they are paired with a priority (in contrast to a queue, which simply requires the element). In a queue, elements are dequeued in the order that they are enqueued; in a priority queue, they are dequeued in an order based upon their associated priorities.

A binary tree is complete when all levels but the last level are full and when the nodes in the last level are left-aligned.

The statement that “all BSTs are heaps” is false. The following BST shows this:

This binary tree is a BST because 3 < 4 (left subtree data are smaller) and 5 > 4 (right subtree data are larger). But it is not a max heap because 4 < 5 and, in a max heap, all parents must have a priority greater than or equal to the priority of their children.

Method bubbleDown(index)
  left <- leftChild(index)
  right <- rightChild(index)
  If right >= size Then
    If left < size Then
      If contents[left].priority > contents[index].priority Then
        swap(contents[left], contents[index])
      EndIf
    EndIf
  Else
    If contents[left].priority > contents[right.priority] Then
      biggest <- left
    Else
      biggest <- right
    EndIf
    If contents[biggest].priority > contents[index].priority Then
      swap(contents[biggest], contents[index])
      bubbleDown(biggest)
    EndIf
  EndIf
End Function

Method heapify()
  For index <- contents.size-1 Down To 0 Do
    bubbleDown(index)
  EndFor
End Function

This algorithm is \(O(n)\) because, although the loop runs \(O(n)\) times and bubbleDown takes \(O(\log n)\) worst-case time, most bubbleDown operations are small – that is, most nodes are closer to the leaves of the tree rather than the root. As a result, the overall number of actual swaps that occurs is \(O(n)\).

Test 3 Study Guide

Inductive Proofs

Dictionary ADT

Trees

Binary Search Trees

AVL Trees

Priority Queues and Heaps