1. Write two methods to insert an element into a given position in a list of characters, one for a list implemented as an array and one for an implementation using a linked list. For example, insert(3, 'a') would insert the character 'a' into position 3 in the list. Throw an exception for any invalid operations.
2. Write two methods for searching an array of integers: (1) an iterative implementation of sequential search and (2) a recursive implementation of binary search. Trace each method when looking for element 12 in the sorted list 4, 5, 9, 11, 18.
3. Answer the following short-answer questions about binary and sequential search in an ordered list.
4. Write a method that returns a new two-dimensional array of doubles with n rows and m columns (n and m are parameters of the method). Set each element of the matrix to a random double value between 0 and 1. What is the worst-case complexity of your method, using big-oh notation?
5. Write a recursive method to compute a! (a factorial). Trace your code on the example of a = 4. scribe advantages and disadvantages of recursion vs. iteration in solving a problem, from the viewpoint of easiness to write, easiness to understand, and running time.
6. Rewrite the expression 4 / 2 + (3 - 1) using postfix notation. Show, step by step, how a stack can be used to compute the value of the resulting expression. Briefly describe why a stack is different from a list.
7. Show, step by step, the state of a queue implemented as a 4-element array as we execute the following operations: enqueue Z, dequeue, enqueue B, enqueue N, enqueue V, dequeue, dequeue, enqueue M. Write a method for dequeue when the queue is represented as an array.
8. Answer the following questions about sorting.
9. Suppose you start with an empty AVL-balanced binary search tree.
10. Suppose you have implemented a hash table as an array of linked lists, with an array of size 5. As the hash function, use modulo 5, so h(n) = n % 5. Show how this hash table will look after inserting the following elements: 1, 5, 37, 12, 41. What are the main advantages and disadvantages of hash tables?
11. For extra credit: Implement one of heapsort, mergesort, or quicksort.
12. For extra credit: Write a method to remove a given element from a binary search tree (you do not need to re-balance the tree).