Question 1.
In pseudo code, describe a recursive algorithm that reverses the elements in a singly linked list.
Describe the running time of your algorithm in a) as recurrence equation. Justify your answer.
Determine big-oh of your algorithm in a) by determining the closed form of your recurrence equation in b). Show your work using the repeated substitution method.
Question 2.
In pseudo code, describe an iterative algorithm that reverses the elements in a singly linked list.
Describe, in general, how to convert a given recursive algorithm into an iterative algorithm.
Question 3.
Let array be an array that contains − 1 unique integers in the range [0, − 1]. That is, there is one number in range [0, − 1] that is not stored in . Describe in pseudo-code an ( )-time algorithm for finding that number. You are only allowed to use ( ) bits of additional space besides the array itself.
Question 4.
Consider the following so called Master Theorem for recurrence equations. It applies to recurrence equations of the following form T(n) = aT(n/b) + c nd, where:
T(n) is an increasing function,
a ≥ 1 is a constant,
b 1 is an integer constant,
c 0 is a constant, and
d ≥ 0 is a constant.
Then T(n) is
O(nd) if a < bd,
O(nd log n) if a = bd, and
O(nlogb a) if a bd.
Consider the following algorithm.
Algorithm FindMin(A, front, last)
if last-front ≤ 1 then return A[front]
else
midpoint ← ⌊(front+last)/2⌋
minf ← FindMin(A, front, midpoint)
minl ← FindMin(A, midpoint+1, last)
return min{minf, minl}
end
What is the recurrence equation describing the running time of Algorithm FindMin?
Does this recurrence equation fit the Master Theorem? If so, what are a, b, c and d?
What is the Big-Oh running time of Algorithm FindMin?
Question 5.
Consider the sorting algorithms insertion sort and merge sort. How many comparisons will each of the two algorithms execute for the following instances (assume that you are to sort the elements in increasing order):
a) 1 2 3 4 5
b) 5 4 3 2 1
For insertion sort, determine the big-Oh of the worst-case number of comparisons for a sequence of n elements. Justify your answer.
