Date: Friday, December 10, 2010.
- Write a recursive method (code) for computing the sum of all the elements
of a linked list.
- Trace your method on the example of a list consisting of elements
12, 10, and 20.
- 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.
3. Multi-Dimensional Arrays:
- Write a method for checking whether all the elements of a matrix
are positive. For example, for the matrix
1 2 3
4 5 6
7 8 9
the answer should be "true", while for the matrix
1 -2 3
4 5 6
7 8 9
the answer should be "false".
Trace your method on the example of the second matrix.
- Using big-oh notation, give the worst-case running time for your algorithm.
- Rewrite the expression 12 - 10 * (20 - 1) in postfix form.
- Show, step by step, how a stack can be used to compute the
value of the resulting postfix expression.
- Show, step by step, the state of a queue -- implemented as an
3-element array - when we first add 12, 10, and 20, then dequeue twice and after
that add 1 and 0.
Write a method for enqueuing an element in a queue represented as an array.
- Using big-oh notation, what is the worst-case running time for your enqueue method?
- Show, step by step, how bubble sort, selection sort, insertion sort, mergesort, quicksort, and
heapsort will sort a list consisting of the elements
12, 10, 20, 1, 0.
- Write code for one of these sorting algorithms (clearly specify which one).
- Draw a table listing the worst-case and average-case complexity for each of the six sorting algorithms.
- True or False: It is possible to implement a sorting algorithm that is much faster than heapsort. Justify your answer.
8. Binary Trees:
No code is needed.
- Suppose you start with an empty AVL binary search tree. Show step by step what will happen if you add elements 12, 10, 20, 1, and 0
to the binary search tree in that order. Balance at each step where it is necessary.
- Show how the resulting tree will look like in an array-based implementation of trees (leave blank spaces for any nodes that do not exist in the tree).
- In 1-2 sentences, what is the purpose of balancing?
- State the condition that every node in a binary search tree must satisfy.
- Show, step by step, how sequential search and binary search will
look for an element 9 in the sorted list 0, 1, 10, 11, and 20.
- What is the worst-case and average-case number complexity of each search?
- What are relative advantages and disadvantages of these two search algorithms?
- Write down a method
implementing sequential search and another implementing binary
search. Assume that the list is implemented as an array.
10. Hash Tables:
- Show, step by step, how a hash table with six "buckets" will look if we
sequentially add to it elements 12, 10, 20, 0, and 1. Assume that
as a hash function, we take remainder modulo 6:
h(n) = n % 6.
- What are advantages and disadvantages of hash tables?
- List two properties of a good hash function.