- Prove that each of the following sorting algorithms is stable or show that it is unstable by giving a counter example; moreover, determine whether it is in place: bubble sort, insertion sort, quick sort, merge sort and heap-sort.
- Given a positive integer
, design an algorithm for computing
.
- How to implement merge-sort such that the extra space used is about
where
is the number of input elements?
- Given two sorted arrays
and
, design an algorithm to compute
.
- Solve the recurrence
where
is assumed; assume that
is constant if
.
- Given a sorted array
of
distinct integers, you want to find out the index
for which
if it exists. Please design a Divide-and-Conquer algorithm that runs in time
. (Analyze your algorithm and show it is correct.)
- Analyze best-case, average-case, and worst-case performance of the following pseudocode which describes a sorting algorithm. Append your analyzing process or reasons.
i = 2
while i <= size
if i == 1 or array[i] >= array[i - 1]
i += 1
else
swap array[i], array[i - 1]
i -= 1