In addition to all concepts from Quiz 1,

You should be able to define or explain the following terms:

• Asymptotic analysis and Big-O notation
• Constant, logarithmic, linear, quasilinear, quadratic, and exponential functions
• Induction
• Correctness of an algorithm
• Loop invariant
• Abstract data types, interface, implementation
• Lists, array lists, linked lists
• Segmentation fault (after this week's lab assignment you probably don't need to study this one)

You should be familiar with the following C++-related concepts:

• new and delete for basic types and arrays
• Pointer/array equivalence
• Exceptions (how to throw, but not necessarily how to catch, exceptions)
• Abstract (or pure virtual) classes
• Templates
• this
• Basic uses of gdb

Practice problems

1. Prove that 41*n^2 + 12n - 1 is O(n^2).
2. Using induction, prove that 0^2 + 1^2 + 2^2 + ... + n^2 is less than or equal to n^3 for all non-negative integers n.
3. Declare and implement a templated ArrayList removeItem(int i) function that, given a position i (indexed from 0), removes the ith item from an ArrayList.
4. Declare and implement a templated LinkedList removeItem(int i) function that, given a position i (indexed from 0), removes the ith item from a LinkedList.
5. Write a program that prompts the user for an integer n, then reads n strings into an array of strings stored on the heap, prints true if the array is sorted and false otherwise, and then frees the memory on the heap. As part of this program declare and implement a templated boolean isSorted(T* a, int n) function that, given a pointer to an array a and the length of that array n, returns true if the array is sorted and false otherwise.

Home Page