Date: Tuesday, December 7, 2010.
- Write a recursive method for transforming a decimal number into a binary number.
- Trace your method on the example of n = 10.
- Describe advantages and disadvantages of
recursion vs. iteration in solving a problem, from the
viewpoint of easiness to write, easiness to understand, and
3. Multi-D Arrays:
- Write a method that, given a general square matrix A,
returns the sum of the diagonal elements from the upper-left to lower-right; this sum is called
a trace of the matrix. For example, for
1 2 3
4 5 6
7 8 9
your method should return the value 1 + 5 + 9 = 15.
- Trace your method on the example of this matrix.
- Using big-oh notation, what is the wost-case running time for your algorithm?
- Rewrite the expresion 12 * 7 - (20 + 10) in postfix form.
- Show, step by step, how a stack can be used to compute the value of the resulting
Show, step by step, the state of a queue -- implemented as an
3-element array - when we first add 12 and 7, then dequeue,
then add 20 and 1, dequeue again and add 0.
- Write a method for dequeuing a queue
represented as an array.
- Using big-oh notation, what is the worst-case running time for your dequeuing 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, 7, 20, 1, and 0.
- Write a code for one of these sorting algorithms.
- 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 Search Trees:
No code is needed.
- Show, step by step, what will happen if we add elements 12, 7, 20,
1, and 0
to an initially empty AVL binary search tree; do not forget to balance at every step at which
balancing 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, 7, 12, and 20.
- What is the
worst-case and average 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 the hash table with four "buckets" will looks like if we
sequentially add to it elements 7, 12, 20, 1, and 0. Assume that
as a hash function, we take remainder modulo 4:
h(n) = n % 4.
- What are advantages and disadvantages of hash tables?
- List two properties of a good hash function.