CS35: Data Structures and Algorithms

Test 3 Study Guide

The tests in this course may contain any material covered in lecture up until this point, although much stronger emphasis will be placed on material for which you have received graded feedback. This page contains a collection of exercises that you may wish to complete to prepare yourself.

Inductive Proofs

You should be prepared to give inductive proofs for simple mathematical summations.

  1. Prove by induction that \(\sum\limits_{i=1}^{n} i \cdot 2^i = 2^{n+1}(n-1) + 2\).

  2. Prove by induction that \(\sum\limits_{i=1}^{n} \frac{3}{4^i} = 1 - (\frac{1}{4})^n\).

Dictionary ADT

  1. What does a Dictionary store?
  2. Which Dictionary operations do we want to run as efficiently as possible?
  3. Name all of the implementations of the Dictionary ADT that we discussed in this class.
  4. Compare and contrast the various Dictionary implementations. What run times do we expect on the key operations for each implementation? When would we prefer one implementation over another.

Trees

  1. Define the following terms with respect to tree data structures:
    • Node
    • Leaf
    • Height
    • Binary tree
    • Binary search tree
    • AVL tree
    • Max heap

Binary Search Trees

  1. Show the BST that would result from inserting the following keys into an initially empty tree: 12, 8, 5, 17, 1, 9, 22.
  2. Is this the only BST that could contain these keys? If not, give at least one example of another BST that holds these same keys.
  3. Is the following tree a BST? If not, why not?

  4. If we tried to find the key 22 in the following tree, where would it have to be?

AVL Trees

  1. Draw a diagram showing the “rotate left” operation on binary trees. When is it impossible to rotate a binary tree to the left?
  2. Write pseudocode for the AVL rebalancing algorithm.
  3. Consider the following tree:

Priority Queues and Heaps

  1. What is the difference between a queue and a priority queue?

  2. What does it mean for a binary tree to be complete?

  3. Consider the following lists of numbers. Write each as a complete binary tree using the representation we discussed in class.
    • [2, 3, 9, 3, 6, 2]
    • [11, 4, 4, 3, 4, 6, 9, 10, 2]
    • [9, 12, 3, 14, 2, 1, 6, 8, 8, 8, 9, 14, 7]
  4. Is the following statement true or false? If true, give a justification. If false, give a counterexample. “All BSTs are heaps.”

  5. Give pseudocode for the bubbleDown heap algorithm.

  6. Give pseudocode for the heapify heap algorithm to turn these complete binary trees into heaps. Briefly explain why this algorithm is \(O(n)\).