Homework 1

1. 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.
   • 第十四組
2. Given a positive integer , design an algorithm for computing .
   • 第十六組
3. How to implement merge-sort such that the extra space used is about where is the number of input elements?
   • 第十三組
4. Given two sorted arrays and , design an algorithm to compute .
   • 第九組
5. Solve the recurrence where is assumed; assume that is constant if .
   • 第一組
6. 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.)
   • 第三組
7. 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