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 charater '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 6 in the sorted list 1, 4, 8, 13, 25.
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 the power ab. Trace your code on the example of a = 5 and b = 3. Describe 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 2 * 5 - (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 R, enqueue B, dequeue, enqueue N, enqueue V, dequeue, enqueue Y. Write a method for enqueuing 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: 4, 2, 12, 7, 18. 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).