# 演算法作業 1

###### tags: `演算法`

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, heap-sort.

| | Bubble Sort | Insertion Sort | Quick Sort | Merge Sort | Heap Sort |
| -------- | -------- | -------- | -------- | -------- | -------- |
| stable | Yes | Yes | No | Yes | No |
| in place | Yes | Yes | Yes/No | No | Yes |

------------
* Bubble Sort
`Input: A[n] ,n is the length of array A`

    BubbleSort(A[]){
        bool swap = false;
        for i = 1 : n
            swap = false;
            for j = 1 : n-i
                if(A[j]>A[j+1])
                    SWAP(A[j],A[j+1]);
                    swap=true;
            if(!swap)
                break;
    }

分析:
它是stable，在原本未排序的A當中值相同的元素，經過排序後相對位置不會被互換。
它是in-place，排序過程僅有一個布林變數swap被使用，這是唯一多使用的空間，大小是$O(n)$，因此是in-place。

* Insertion Sort

    InsertionSot(A[]){
        for i = 2 : n
            int key = A[i];
            int j=i-1;
            while(j>0 and A[j]>key)
                A[j+1] = A[j];
                j=j-1;
            A[j+1]=key;
    }

分析:
it's stable，A中任意兩相同大小的元素經過排序後相對位置不會改變。
it's in-place，整個排序過程只多開了一個變數key，大小是$O(n)。

* Quick Sort

    QuickSort(A[],start,end){
        if(start<end){
            pivot = Partition(A[],start,end);
            QuickSort(A[],start,pivot-1);
            QuickSort(A[],pivot+1,end);
        }
    }
    
    Partition(A[],start,end){
        int pivot = end;
        int i,j = start - 1;
        
        for i = start : end-1
            if(A[i]<=A[pivot])
                j=j+1;
                SWAP(A[j],A[i]);
        j=j+1;
        SWAP(A[j],A[pivot]);
        return j;
    }

分析:
it's not stable,假設A原本是{5,8(a),8(b)}，經過排序後會變成{5,8(b),8(a)}，原本相同大小的8(a),8(b)相對位置被改變了。
它可能是in-place也可能不是，如果排序過程每次挑到的pivot都是子陣列的最大或最小值，那加開的空間可能達到$O(n)$，這樣就不是in-place，如果大多數挑到的pivot都不是最大最小值，那加開的空間大約是$O(log(n))$，這樣是in-place。

* Merge Sort

    MergeSort(A[],start,end){
        if(start<end)
            int mid = floor((start+end)/2);
            MergeSort(A[],start,mid);
            MergeSort(A[],mid+1,end);
            Merge(A[],start,mid,end);
    }
    
    Merge(A[],start,mid,end){
        if(start==mid) or (mid+1==end)
            return;
        
        int L[mid-start+2],R[end-mid+1];
        L[mid-start+2]=inf;
        R[end-mid+1]=inf;
        
        int l=1,r=1;
        for i = start:end
            if(L[l]<=R[r])
                A[i]=L[l];
                l=l+1;
            else
                A[i]=R[r];
                r=r+1;
    }
    

分析:
it's stable,任意兩個相同大小的值在merge的時候，前面的那個一定會先被放進排好的陣列中。
it's not in-place，每次merge都需要加開L[]、R[]兩個陣列，空間是$O(n)$，因此並非in-place。

* Heap Sort

    HeapSort(A[]){
        //Build a Max Heap
        for i = floor(A.length/2) to 1
            Max-Heaplify(A[],i);
        
        n=A.size;
        for i = n to 2
            SWAP(A[1],A[i]);
            A.size=A.size-1;
            Max-Heaplify(A[],1);
    }
    
    Max-Heaplify(A[],root){
        int child = root*2;
        while(child<=A.size)
            if(child+1<=A.size && A[child]<A[child+1])
                child=child+1;
            if(A[root]>=A[child])
                break;
            SWAP(A[root],A[child]);
            root=child;
            child=root*2;
    }

分析:
it's not stable,假設有一陣列{8(a),8(b),5}，經過heap sort之後會變成{5,8(b),8(a)}，因此不是stable。
it's in-place，heap sort過程中只有加開$O(1)$大小的變數來幫助排序，因此為in-place。

2. Design a data structure to represent a set with elements being positive integers, and then design algorithms for the following operations:
Compute the union of two sets.
Compute the intersection of two sets.
Determine if a given element is in a given set.

Answer:
我設計的Set當中的元素在陣列當中是以升序排列的方式儲存。

    class Set{
        Element[];//元素陣列，已升序排列好
        Union(Set A,Set B);
        Intersection(Set A,Set B);
        Exist(int num);
    }

    Intersection(Set A,Set B){
        I[]={};//建立一個新的空陣列，用來儲存Union Set
        i=1;
        j=1;
        k=1;
        while(i<=A.size and j<=B.size){
            if A[i]==B[j]
                I[k]=A[i];
                k=k+1;
                while(A[i]==B[j])
                    i=i+1;
            while(A[i]>B[j])
                j=j+1;
            while(A[i]<B[j])
                i=i+1;
        }
        return I[];
    }
    
    Union(Set A,Set B){
        U[]={};//建立一個空陣列，用來儲存Intersection
        i=1;
        j=1;
        k=1;
        while(i<=A.size and j<=B.size){
            if(A[i]==B[j])
                U[k]=A[i];
                k=k+1;
                while(A[i]==B[j])
                    i=i+1;
            while(A[i]>B[j])
                U[k]=B[j];
                j=j+1;
                k=k+1;
            while(A[i]<B[j])
                U[k]=A[i];
                i=i+1;
                k=k+1;
        }
        while(i<=A.size)
            U[k]=A[i];
            k=k+1;
            i=i+1;
        while(j<=B.size)
            U[k]=B[j];
            k=k+1;
            j=j+1;
        
        return U[];
    }

    Exist(int num){
        for i = 1 to Element.size
            if num==Element[i]
                return true;
        return false;
    }

3. Given two sorted arrays $x[1]…x[m]$, $y[1]…y[n]$, design an algorithm to compute $min_{i, j} | x[i] − y[j]|$.

Answer:
Time complexity: $O(m+n)$

    funct(x[],y[]){
        if x[1]>=y[n]
            return abs(x[1]-y[n]);
        if y[1]>=x[n]
            return abs(y[1]-x[n]);
        i=1;j=1;
        min=abs(x[1]-y[1]);
        while(i<=m and j<=n){
            dis=abs(x[i]-y[j]);
            if dis==0
                return 0;
            if dis<min
                min=dis
            if x[i]>y[j]
                j=j+1;
            else
                i=i+1;
        }        
        return min;
    }
    

4. Solve the recurrence $T(n) = 2T(n/2) + n – 1$ where $n = 2^𝑘$ is assumed. $T(1) = 0$

Answer:

5. Given a set S of n integers, and another number M, we want to determine whether or not there exist 2 numbers in S whose sum is exactly M. The algorithm of testing all possible 2 numbers in S will take $O(𝑛^2)$ time and it is unacceptable.
a) Design a more efficient algorithm for solving this problem. Analyze the time complexity of your algorithm.
b) Extend your algorithm for the following case: determine whether or not there exist 3 numbers in S whose sum is exactly M.
c) What about the case: determine whether or not there exist k ( > 3) numbers in S whose sum is exactly M.

Answer:
(a)
dp版本
**初始值:** $Able_{i00}=true、Able_{i1(S_i)}=true、Able_{0jk}=false$
**遞迴式:** $Able_{ijk}=\begin{cases}
Able_{(i-1)(j-1)(k-S_i)} \ or \ Able_{(i-1)jk} \ if \ k>=S_i\\
Able_{(i-1)jk} \ if \ k<S_i\\
\end{cases}$
**解答:** $Able_{n2M}$
**Time complexity:** $O(n*M)$ M可能大於等於n

    input:S[],n,2,M
    
    funct(S[],2,M){
        Able[n][2][M]={false};//將陣列元素全部設為false
        //Able[i][j][k]代表從s[]的前i個元素中找j個組成k
        for i= 1:n
            Able[i][0][0]=true;
            Able[i][1][S[i]]=true;
        
        for i = 1:n
            for j = 1:i and j<=2
                for k=1:M
                    if(k>=S[i])
                        Able[i][j][k]=Able[i-1][j-1][k-S[i]] or Able[i-1][j][k];
                    else
                        Able[i][j][k]=Able[i-1][j][k];
        
        return Able[n][2][M];
    }

第二版本
時間複雜度$O(n*lg(n))$

    funct2(S[],2,M){
        left=1,right=n
        sum=0
        sort(S[])
        while left<=n and S[left]<=M/2
            sum=S[left]+S[right]
            if sum==M
                return true
            else if sum>M
                right-=1
            else
                left+=1
        return false
    }
    

(b)
**初始值:** $Able_{i00}=true、Able_{i1(S_i)}=true、Able_{0jk}=false$
**遞迴式:** $Able_{ijk}=\begin{cases}
Able_{(i-1)(j-1)(k-S_i)} \ or \ Able_{(i-1)jk} \ if \ k>=S_i\\
Able_{(i-1)jk} \ if \ k<S_i\\
\end{cases}$
**解答:** $Able_{n3M}$

    input:S[],n,3,M
    
    funct(S[],3,M){
        Able[n][3][M]={false};//將陣列元素全部設為false
        //Able[i][j][k]代表從s[]的前i個元素中找j個組成k
        for i= 1:n
            Able[i][0][0]=true;
            Able[i][1][S[i]]=true;
        
        for i = 1:n
            for j = 1:i and j<=3
                for k=1:M
                    if(k>=S[i])
                        Able[i][j][k]=Able[i-1][j-1][k-S[i]] or Able[i-1][j][k];
                    else
                        Able[i][j][k]=Able[i-1][j][k];
        
        return Able[n][3][M];
    }

(c)
**初始值:** $Able_{i00}=true、Able_{i1(S_i)}=true、Able_{0jm}=false$
**遞迴式:** $Able_{ijm}=\begin{cases}
Able_{(i-1)(j-1)(m-S_i)} \ or \ Able_{(i-1)jm} \ if \ m>=S_i\\
Able_{(i-1)jm} \ if \ m<S_i\\
\end{cases}$
**解答:** $Able_{nkM}$

    input:S[],n,k,M
    
    funct(S[],k,M){
        Able[n][k][M]={false};//將陣列元素全部設為false
        //Able[i][j][m]代表從s[]的前i個元素中找j個組成k
        for i= 1:n
            Able[i][0][0]=true;
            Able[i][1][S[i]]=true;
        
        for i = 1:n
            for j = 1:i and j<=k
                for m=1:M
                    if(m>=S[i])
                        Able[i][j][m]=Able[i-1][j-1][m-S[i]] or Able[i-1][j][m];
                    else
                        Able[i][j][m]=Able[i-1][j][m];
        
        return Able[n][k][M];
    }

6. How to merge k sorted lists with total length N efficiently. What is the execution time of your algorithm.

Answer:
use Merge technique to sort k sorted lists
將k個sorted lists視為k個leaf node，那整個merge的樹高會是log(k)+1，而每次merge需要的時間是log(n)，n是lists的長度，而每個lists的長度又小於N，因此整體時間複雜度會是$O(N*log(k))$

    input:L[1]...L[k]
    Merge(L[],R[]){
        A[L.length+R.length]={};//創建一個空陣列
        i=1;j=1;k=1;
        while(i<=L.length and j<=R.length)
            if L[i]<=R[j]
                A[k]=L[i];
                k=k+1;
                i=i+1;
            else
                A[k]=R[j];
                k=k+1;
                j=j+1;
        while(i<=L.length)
            A[k]=L[i];
            k=k+1;
            i=i+1;
        while(j<=R.length)
            A[k]=R[j];
            k=k+1;
            j=j+1;
        
        return A[];
    }
    
    MergeK(){
        total=k;
        while total !=1
            j=1;
            if total%2==0
                for i = 1:total/2
                    L[j]=Merge(L[j],L[j+1]);
                    j=j+2;
                total=total/2;
            else
                for i=1:(total-1)/2
                    L[j]=Merge(L[j],L[j+1]);
                    j=j+2;
                total=(total+1)/2;
        return L[1];
    }

7. The input is a sequence of n integers with many duplications, such that the number of distinct integers in the sequence is $O(logn)$.
(a) Design a sorting algorithm to sort such sequences using at most $O(nloglogn)$ comparisons in the worst case.
(b) Why is the lower bound of sorting $𝛺(nlogn)$ not satisfied in this case?

Answer:
(a)
假設這n個數字的最大值不是太大，那我們可以用bucket sort排序它，時間複雜度會是 $O(n)$，而且只進行n次比較，因為只需要找出這序列的最大值。
如果最大值很大，或離均差很大，那我們可以用AVL tree去排序它，只要進行n次AVL tree的插入，我們知道每次AVL tree的insert time都是O(log(m))，這同時也是進行比較的次數，這邊的m是AVL tree的節點數量，在此序列當中只有log(n)個不同的數字，所以AVL tree的節點數量就會是log(n)，每次插入時間都是$O(log(log(n)))$，而總共進行n次插入，所以總共的比較次數是$O(nlog(log(n)))$。

    input:Num[],n;
    BucketSort(Num[],n){
        M=max(Num[]);//找到Num[]當中的最大值
        A[M]={0};//創建一個空陣列
        
        for i = 1:n
            A[Num[i]]=A[Num[i]]+1;
        return A[];
    }

    AVLsort(Num[],n){
        AVLTree={};//建立一個空的AVL tree
        for i = 1:n
            AVLTree.insert(Num[i]);
        return AVLTree
    }

(b)
正常的comparison sort的過程可以比擬為一顆二元樹，假設有n個不同的樹要排序，這棵樹的樹高會是log(n)，也是每個數要進行comparison的次數，總共有n個不同數字，所以總共的比較次數會是$O(n*log(n))$，但在這題當中不同的數字不是n個，而是log(n)個，所以不需要進行log(n)次比較，只需要log(log(n))次，對於n個數字來說，總共就會是 $O(log(log(n)))$。