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.

- What is the best, worst, and average number of elements that sequential and binary search will look at? Do NOT use big-oh notation, give exact values for a list with n elements.
- Briefly describe the advantages and disadvantages of the two search algorithms.
- Suppose you have an unsorted list and you want to find a single element in the list. Would it be faster to do a sequential search, or to first sort the list and then use binary search to find the element? Justify your answer.

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 a

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.

- Show, step by step, how mergesort, quicksort, and heapsort will sort the following list of elements: 6, 3, 15, 9, 12, 1. For quicksort, use the first element of the array as the pivot.
- Write code for either selection sort or bubble sort.
- Draw a table showing the worst and average-case complexity for bubble, insertion, selection, merge, quick, and heap sort using big-oh notation.

9. Suppose you start with an empty AVL-balanced binary search tree.

- Show, step by step, what will happen if we add the following elements to an AVL-balanced binary search tree: 4, 2, 1, 8, 6. Don't forget to balance at each step when necessary.
- Show how the resulting tree will look in both a reference-based and an array-based implementation of trees.
- Why is balancing necessary in a 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.

12.