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.

Inductive Proofs

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

  1. Prove by induction that \(\sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1}\).

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

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.\ cf(n) \leq g(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. Describe the difference between an ArrayList and a CircularArrayList.
    1. Which fields does each class have?
    2. What invariants do we keep between the fields of ArrayList? What additional invariants hold on CircularArrayList?
  2. For each of LinkedList (assume singly-linked with no tail pointer), ArrayList, and CircularArrayList, what are the big-\(O\) complexities of the following operations? Briefly explain your 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 front of the list.

Algorithmic Complexity and Pseudocode

You should be prepared to discuss the algorithmic complexity of pseudocode examples.

What is the algorithmic complexity of the following pseudocode? Justify your answer.

Sorting

You should be familiar with the sorting algorithms we discussed in class. You should be prepared to reproduce parts of those algorithms or diagnose errors in implementations of them. You should also be prepared to execute those algorithms on paper.