CS35: Data Structures and Algorithms

Test 2 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. We also encourage you to review the lecture notes from topics presented since the previous test.

Sorting

You should make sure to review the sorting algorithms we covered in class and be ready to discuss them.

  1. What is the worst-case time complexity of bubble sort? QuickSort? MergeSort?

  2. Although QuickSort’s worst-case time complexity is worse than MergeSort’s, we use QuickSort as a default in practice. Why?

  3. What is an in-place sorting algorithm?

  4. What is wrong with the following QuickSort pseudocode? What would happen if we used this pseudocode to sort an array? How could we fix it?

    Function brokenQuickSort(array, left, right)
        pivot <- partition(array, left, right)
        brokenQuickSort(array, left, pivot-1)
        brokenQuickSort(array, pivot+1, right)
    EndFunction
    
  5. Write pseudocode for a partition function which can be used in the QuickSort algorithm.

  6. Write pseudocode for the merge function of the MergeSort algorithm.

Big-O Proofs

Recall the definition of big-\(O\) notation we used in class: \(f(x)\) is \(O(g(x))\) if \(\exists c>0, k\geq 1.\ \forall n \geq k.\ f(n) \leq cg(n)\). You should be prepared, given this definition, to prove complexity bounds on functions.

  1. Prove that \(f(n) = \frac{n^2+1}{n}\) is \(O(n)\).

  2. Prove that \(f(n) = 3n^3 + 5n^2 + 8\) is \(O(n^3)\).

  3. Prove that \(f(n) = (n+1)(n-1)\) is \(O(n^2)\).

Data Structures and Invariants

You should be prepared to discuss the data structures we have created in class, the fields in their implementations, and the invariants we rely upon in order to write algorithms for those data structures.

  1. What is an ADT? What is the difference between an ADT and a data structure? Give two examples of each.
  2. What is the difference between a List and a Stack? When might we use a Stack instead of a List?
  3. What are the big-\(O\) complexities of the following operations? Answer for each of (a) LinkedList with a tail pointer, (b) LinkedList without a tail pointer, and (c) ArrayList. Briefly explain each answer.
    1. Insert to the front of the list.
    2. Insert to the back of the list.
    3. Retrieve the first element of the list.
    4. Retrieve the middle element of the list.
    5. Remove an element from the back of the list.
  4. What is amortized complexity?
  5. Draw a stack diagram of a stack frame in which the following code has been run:
    Stack<int>* stack = new LinkedStack<int>();
    stack->push(4);
    stack->push(5);