---
# System prepended metadata

title: HW5
tags: [algorithm]

---

## HW5

1. Heap Sort
    1. 下圖為Max Heap。Heap Sort的每一回合，會將Heap的最大值刪除後，又恢復為Heap。請畫出第一回合恢復的過程。
    ```graphviz
    digraph dg{
        44 -> 42;
        44 -> 35;
        42 -> 33;
        42 -> 31;
        35 -> 19;
        35 -> 27;
        33 -> 10;
        33 -> 26;
        31 -> 14;
    }
    ```

    - Ans:
        1. 去掉最大元素 
            ```graphviz
            digraph dg{
                14 [style=filled, fillcolor= "#FFCF76"]
                14 -> 42;
                14 -> 35;
                42 -> 33;
                42 -> 31;
                35 -> 19;
                35 -> 27;
                33 -> 10;
                33 -> 26;
            }
            ```
        2. 找 14/42/35 之間最大的元素後交換
            ```graphviz
            digraph dg{
                14 [style=filled, weight=0.5, fillcolor= "#FFCF76"];
                42 [style=filled, weight=0.5, fillcolor= "#FFCF76"];
                42 -> 14;
                42 -> 35;
                14 -> 33;
                14 -> 31;
                35 -> 19;
                35 -> 27;
                33 -> 10[weight=0.5];
                33 -> 26[weight=0.5];
            }
            ```
        3. 找 14/33/33 之間最大的元素後交換
            ```graphviz
            digraph dg{
                14 [style=filled, weight=0.5, fillcolor= "#FFCF76"];
                33 [style=filled, weight=0.5, fillcolor= "#FFCF76"];
                42 -> 33;
                42 -> 35;
                33 -> 14;
                33 -> 31;
                35 -> 19;
                35 -> 27;
                14 -> 10[weight=0.5];
                14 -> 26[weight=0.5];
            }
            ```
        4. 找 14/10/26 之間最大的元素後交換
            ```graphviz
            digraph dg{

                26 [style=filled, weight=0.5, fillcolor= "#FFCF76"];
                42 -> 33;
                42 -> 35;
                33 -> 26;
                33 -> 31;
                35 -> 19;
                35 -> 27;
                26 -> 10[weight=0.5];
                26 -> 14[weight=0.5];
                14 [style=filled, weight=0.5, fillcolor= "#FFCF76"];
            }
            ```
    2. 投影片69頁的公式如下，請解釋此公式的含意。
        ![image](https://hackmd.io/_uploads/H1cS6LzeR.png)


2. Problem平均的Lower Bound
    ![image](https://hackmd.io/_uploads/Sk9upUGgC.png)
    - 從0開始的結果:
        ![image](https://hackmd.io/_uploads/r1rSD2MgR.png)

3.  Problem Transformation
    - Sorting problem reduces to Convex Hull Problem
    - 請說明，若要排序五個數字：4,1,3,2,5，如何轉為Convex Hull Problem後，完成排序。
  ![image](https://hackmd.io/_uploads/BkP3TUGlC.png)



reference:

1. [Graphviz note](https://hackmd.io/9yNZus8GTFaeHjjwcv_CBQ?both)
2. [Attributes Color](https://hackmd.io/@eric88525/graphviz-note) 
3. [Attributes Color](https://hackmd.io/@lilybon/graphviz)