Question

1. Describe a recursive algorithm for finding the maximum element in an array A of n elements. What
is the running time of your algorithm?

2. Draw the recursion trace for the execution of reverseArray(data, 0, 4), on the array data = 4, 3, 6, 2, 6.

3. Give an algorithm for finding the second-to-last node in a singly-linked list ub which the last node is
indicated by a null next reference.

4. Suppose we are maintaining a collection C of elements such that, each time we add a new element
to the collection, we copy the contents of C into a new array list of just the right size. What is the
running time of adding n elements to an initially empty collection C in this case?

Answer 1

Answer on Question # 44894, Programming, Other

Task:

1. Describe a recursive algorithm for finding the maximum element in an array A of n elements. What is the running time of your algorithm?

Answer:

Algorithm Max (A, m, n)
    if A[n-1] > m
        m ← A[n-1]
    if n=1
        return m
    else
        return Max(A, m, n-1)

Task:

2. Draw the recursion trace for the execution of ReverseArray(data, 0, 4), on the array data = 4, 3, 6, 2, 6.

Answer:

Algorithm ReverseArray(A, i, j):
    Input: An array A and nonnegative integer indices i and j
    Output: The reversal of the elements in A starting at index i and ending at j
    if i < j then
        Swap A[i] and A[j]
        ReverseArray(A, i+1, j-1)
    return

1) i=0, j=4, A= {4, 3, 6, 2, 6}

i < j → 0 < 4 (yes)

swap(A[0], A[4])

A= {6, 3, 6, 2, 4}

2) i=1, j=3, A= {6, 3, 6, 2, 4}

i < j → 1 < 3 (yes)

swap(A[1], A[3])

A= {6, 2, 6, 3, 4}

3) i=2, j=2, A= {6, 2, 6, 3, 4}

i < j → 2 < 2 (no)

return

Task:

3. Give an algorithm for finding the second-to-last node in a singly-linked list which the last node is indicated by a null next reference.

Answer:

Algorithm findPenultimate(S):
    Node n←head
    while (n.getNext() != tail) do
        N  $\leftarrow$  n.getNext()
    return n

Task:

4. Suppose we are maintaining a collection $C$ of elements such that, each time we add a new element to the collection, we copy the contents of $C$ into a new array list of just the right size. What is the running time of adding $n$ elements to an initially empty collection $C$ in this case?

Answer:

The total running time for adding n elements in this way is $O(n^{2})$

http://www.AssignmentExpert.com/