---
title: homework VIII
---
# P1
## topic
[CLRS 3 rd ] Exercise 16.2-5
## Solution
從最小的點開始,因為沒有點在它的左側,所以我們以該點作為第一個closed interval的左端點,並檢查右方一單位內是否有其他點,有的話,因為它已經被涵蓋在這個interval裡面了,所以我們可以忽視它,接著我們只須對這個interval之後的點重複作同樣的事即可,因為每個步驟都沒有浪費任何長度,因此最後得到的應是最佳解

# P2
## Topic
[CLRS 3 rd ] Exercise 16.3-3
What is an optimal Huffman code for the following set of frequencies, based on the first 8 Fibonacci numbers?

$a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21$

Can you generalize your answer to find the optimal code when the frequencies are the first nnn Fibonacci numbers?
## Solution

Huffman(C)
n=|C|;
Q=C;
for i=1 to n-1
	allocate a new node z;
	z.left=x=EXTRACT-MIN(Q);
	z.right=y=EXTRACT-MIN(Q);
	z.freq=x.freq+y.freq;
	Insert(Q,z);
Return EXTRACT-MIN(Q); //return the root of the tree





# P3
## topic
[CLRS 3 rd ] Exercise 16.3-7
## Solution
在建立一般的Huffman Tree時，我們會先抓2個lowest frequecy的點，這件事情就算到要以teranry來表達也沒有變，只是改從一個排序過的抓3個lowest的點，合併產生的新節點仍會跟尚未使用的節點們做排序，再抓出lowest的3個點，故仍會是最佳化。
# P4
## topic
[CLRS 3 rd ] Exercise 16.3-9
## Solution
The reason Huffman code can be used compress data lies in the differences between each characters' frequency. By building a complete binary tree according to each characters' frequency, we get shorter codes for those have higher frequency and longer codes(still shorter than original) for those have lower frequency. However, if every characters' frequency are equal, the size of the code we get will be equal to the original.
# P5
## topic
Solve the instance of the scheduling problem given in Figure 16.7, but with each penalty w~i~ replaced by 80 - w~i~.
| a~i~ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| ----- | --- | --- | --- | --- | --- | --- |:---:|
| d~i~ | 4 | 2 | 4 | 3 | 1 | 4 | 6 |
| w~i~ | 70 | 60 | 50 | 40 | 30 | 20 | 10 |
## Solution
To find the independent set A with minial penalties, we sort {a~i~} into monotonically decreasing order by w~i~'

| a~i~ | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| ----- | --- | --- | --- | --- | --- | --- |:---:|
| d~i~ | 6 | 4 | 1 | 3 | 4 | 2 | 4 |
| w~i~' | 70 | 60 | 50 | 40 | 30 | 20 | 10 |

selecting the largest weight and keeping N~t~ ≦ t, we select a~7~, a~6~, a~5~, a~4~ and a~3~, and reject a~1~ and a~2~(since N~4~({a~5~, a~4~, a~3~, a~6~}) = 4)

The optimal schedule is
- <a~5~, a~4~, a~3~, a~6~, a~7~, a~1~, a~2~>

and the total penalty is
- 10 + 20 = 30

# P6
## topic
Show how to use property 2 of Lemma 16.12 to determine in time O(|A|) whether or not a given set A of tasks is independent.

## Solution

Count how many tasks sharing the same deadline.
Then accumulate the numbers from low to high, checking whether the load has exceeded the time we can use.

check(A){
    // A is an array of deadline
    let arr be an integer array of size A.size() initialized with 0
    //accounting deadline
    for i = 1 to deadline.size()
        arr[deadline[i]] += 1
    end for
    //accumulating
    for i = 1 to deadline.size()
        acc +=arr[i]
        if acc>i
            return false
        end if
    end for
    return true
}


# P7
## topic

## Solution
### a
#### Pseudo

minimizeAverageC(S){ //O(nlogn)
    Sort S into S' by processing time //O(nlogn)
	count = 0
	for i =1 to S.size()
		count += ho[i]*(ho.size()-i+1)
	return count/ho.size()
}

#### Greedy choice

#### Optimal substructure
With the greedy choice, we select a~i~ that has the least p~i~, the sum of the completion time would be C = p[i] + [(n-1)p[i] + C'] where C'
is the optimal solution to S - a[i]

### b

minimizeAverageC(S){ //O(n^2)
    q is a empty priority queue (min heap)
    Sort S into S' by release time //O(nlogn)
    last_time = 1
    count = 0
    gap = 0
    q.push(S'[1])
    for t = 2 to S'.size() //O(n)
        gap = S'[t].release - S'[t-1] //time passed
        while !q.empty() //O(n)
            if gap >= q.top().remain // remove top
                gap -= q.top().remain
                count += q.top().time*(S'.size()-t+1)
                q.pop()
            else
                q.top().remain -= gap
                gap = 0
                break
        count += q.top().time*(S'.size()-t+1) //gap cost
        q.push(S'[t])//O(logn)
    //remaining task
    while !q.empty() //O(n)
        count += q.top().remain * q.size()
    return count / S'.size()

Sort the tasks by their release time.
Once a task is released, insert it to a priority queue.
Then subtract the time had passed during the release times between these 2 tasks from tasks, remove the top task if the it's remaining time is 0.

Similar to part a, we choose to cope with the task can be finished the most quickly. Doing so, we can make sure the time other tasks finished get least delay caused by the task we choose.