---
title: Algorithm V
description: 第五次作業
---
# Group 2
組員:王承隆、賴文宏、施宗佑、王昱翔、王柏喬、莊淳方、傅文宗

# [Homework](https://drive.google.com/file/d/1Zk2Hq2HguyY2rwKiFT5iJ-a4R_0w6tcQ/view?usp=sharing)
# Problem 1
[CLRS 3 rd ] Exercise 6.1-4
## Topic
Where in a max-heap might the smallest element reside, assuming that all elements are distinct?

## Solution
Leaves($\lfloor n/2\rfloor$ + 1 to n), because the childs must be smaller than their parent,as a result, the smallest element will reside at the bottom

# Problem 2

## Topic
投影片unit03 p.6, priority queue 基本implementation。
如何分別用(a) unsorted list (b) sorted list (c) heap (d) binary search tree
四種不同結構做priority queue, 並回答用在sort ≅ ?sort

## Solution
假設所有新的key都比原本的key大
1. Unsorted List
- Construct：O(n)
將所有元素塞進list
- Push：O(1)
插入一個元素進list
- Pop largest：O(n)
搜尋list，取出並刪除最大值
- Pick largest：O(n)
搜尋list，取出最大值
- Increase-Key:O(1)
找到指定的元素, 更新它的key
- sort$\approx$selection sort
全部看過一遍選最大的。
2. Sorted List
- Construct：O(nlgn)
排序O(nlgn)
- Push：O(n)
在正確位置上插入至已排好的陣列
- Pop largest：O(1)
取出並刪除最後一個值
- Pick largest：O(1)
取出最後一個值
- Increase-Key:O(n)
找到指定的元素, 更新它的key, 再做insertion sort
- Sort$\approx$insertion sort
將新增的值插入已排好的陣列
3. Heap
- Construct：O(nlgn)
將值輸入進priority queue中，進行heapify(bottom-up)，需要花O(lgn)的時間
- Push：O(lgn)
放到最後，再heapify(bottom-up)
- Pop largest：O(lgn)
移除root，再heapify(bottom-up)
- Pick largest：O(1)
移除root
- Increase-Key:O(lgn)
找到指定的元素, 更新它的key, 再從root做heapify
- Sort $\approx$ heap sort
4. Binary Search Tree (implement array)
- Construct：Worst: O($n^2$), Average: O(nlgn)
實踐方法如同quick sort，先隨機取一個值當pivot，大於小於pivot個別遞迴，小的放左邊，大的放右邊
因此複雜度和quick sort一樣
- Push：Worst: O(n), Average: O(lgn)
Binary search，樹高為n，因此最差解為n
- Pop largest：Worst: O(n), Average: O(lgn)
同上
- Pick largest：Worst: O(n), Average: O(lgn)
同上上
- Increase-Key:Worst: O($n^2$), Average: O(nlgn)
找到指定的元素, 更新它的key, 再sort一次
- Sort $\approx$ quick sort

# Problem 3
[CLRS 3 rd ] Exercise 15.1-1
## Topic
Show that equation (15.4) follows from equation (15.3)
and the initial condition
T(0)=1.
T(n) = 1+ $\sum_{j=0}^{n-1}$ T(j). (15.3)
T(n) = $2^n$. (15.4)

## Solution
T(0) = 1
T(1) = 1 + T(0) = 2T(0) = 2
T(2) = 1 + T(0) + T(1) = 2T(1) = 4
...
Suppose T(k - 1) = $2^{k-1}$ when k ≧ 1
T(k) = (1 + T(0) + T(1) + .. T(k - 2))+ T(k - 1) = 2T(k - 1) = 2 x $2^{k-1}$ = $2^k$
∴T(n) = $2^n$

# Problem 4
[CLRS 3 rd ] Exercise 15.1-2
## Topic
Show, by means of a counterexample, that the following "greedy" strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be $p_i/i$, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1 ≤ i ≤ n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n−i.
## Solution
Given n = 9

we got 14(7, 2) by greedy strategy, but there is a higher price 15(3, 3, 3)
| length | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ------- | --- |:---:|:----:| --- |:---:| --- | ---- | --- |:---:|
| price | 1 | 2 | 5 | 4 | 5 | 6 | 12 | 8 | 9 |
| density | 1 | 1 | 1.67 | 1 | 1 | 1 | 1.71 | 1 | 1 |

# Problem 5(看第七題)
[CLRS 3 rd ] Exercise 15.1-3
## Topic
Consider a modification of the rod-cutting problem in which, in addition to a price $p_i$ for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem.
# Solution

Psuedocode
rodCutting(length,prices[], cutCost){
	//profit[i] record the maximal profit of a rod of length i 
	profit ia an array of size (length + 1)
	i and j are integers
	cut[0] = 0
	for i in (1 to length) do
		profit[i] = prices[i]
		for j in (1 to i-1)
			if profit[i] < prices[j] + profit[i - j] - cutCost do
				profit[i] = prices[j] + profit[i - j] - cutCost;
			end if
	end for
	return profit[length]//max profit;
}

# Problem 6(看第七題）
[CLRS 3 rd ] Exercise 15.1-4
## Topic
Modify $MEMOIZED-CUT-ROD$ to return not only the value but the actual solution, too.
# Solution

Psuedocode
rodCutting(length,prices[]){
	//profit[i] record the maximal profit of a rod of length i 
	//pieces[i] is the length of the first piece of a rod of length i
	profit and pieces are arrays of size length + 1
	i and j are integers
	profit[0] = 0
	for i in (1 to length) do
		profit[i] = prices[i]
		pieces[i] = i
		for j in (1 to i-1)
			if profit[i] < prices[j] + profit[i - j] do
				profit[i] = prices[j] + profit[i - j]
				pieces[i] = j
			end if
	end for
	return profit[length], pieces[1:] //max profit and the actual solution
}

# Problem 7

## Topic
Rod Cutting Problem(要寫Code)
Suppose you have a rod of length M, and you want to cut up the rod and sell the
pieces in a way. A piece of length i is worth p i dollars, when i ≤ n. Now M is
greater than n . Assume the length of a rod is always an integer. Design an
algorithm to maximize the total profit you get.

## Solution

Psuedocode
rodCutting(length,prices[]){ //O(length^2)
	//profit[i] record the maximal profit of a rod of length i 
	profit ia an array of size (length + 1)
	i and j are integers
	cut[0] = 0
	for i in (1 to length) do//O(length)
		profit[i] = prices[i]
		for j in (1 to i-1)//O(length)
			if profit[i] < prices[j] + profit[i - j] do
				profit[i] = prices[j] + profit[i - j];
			end if
	end for
	return profit[length]//max profit;
}

單純第7題code
#include <iostream>
using namespace std;

const int MIN_INT = -999999;

int rod_sol(int n, int p[], int r[]){
  if(r[n]>=0){
    return r[n];
  }
  
  int q = MIN_INT;
  if(n==0){
    q = 0;
  }else{
    for(int i=1;i<=n;i++)
      q = max( q, p[i] + rod_sol(n-i, p, r) );
    r[n] = q;
  }
  return q;
}

int rod_sol(int p[], int len){
  int r[len];
  for(int i=0;i<=len;i++)
    r[i] = MIN_INT;
  return rod_sol(len, p, r);
}

int max(int a, int b){return a>b?a:b;}

int main(){
  int len;
  cin>>len;
  int price[len+1];
  price[0] = MIN_INT;
  for(int i=1;i<=len;i++)
    cin>>price[i];
  cout<<"result: "<<rod_sol(price, len);
}

#### Price and method and cost

第5 6 7題code
#include <iostream>

using namespace std;

float rodCutting(int length, float *prices, int cutCost){
	//cut[0][i] record the maximal profit of a rod of length i 
	//cut[1][i] is the length of the first piece of a rod of length i
	float cut[2][length + 1];
	int i, j;
	cut[0][0] = 0;
	for(i = 1;i <= length;i++){
		cut[0][i] = prices[i];
		cut[1][i] = i;
		for(j = 1;j < i;j++){
			if(cut[0][i] < prices[j] + cut[0][i - j] - cutCost){
				cut[0][i] = prices[j] + cut[0][i - j] - cutCost;
				cut[1][i] = j;
			}
		}
	}
	cout << "rods:";
	for(i = length;i > 0;i -= cut[1][i])
		cout << cut[1][i] << ' ';
	cout << endl << "maximal profit:";
	return cut[0][length];
}

int main(){
	int length, i, cutCost;
	cout << "The total length: ";
	cin >> length;
	cout << "The cost of cutting: ";
	cin >> cutCost;
	float prices[length + 1];
	for(i = 1;i <= length;i++){
		cout << "price of length " << i << ": ";
		cin >> prices[i];
	}
	cout << rodCutting(length, prices, cutCost) << endl;
}

# program's homework

#include <iostream>
#include <vector>
using namespace std;

int mul(vector<int> A, vector<int>B){
  vector<int> C;
  for(int a=0;a<A.size();a++){
    for(int b=0;b<b.size();b++){
      int tmp = A[a]*B[b],
          quo = tmp/10;
      if(C.size()<a*b){
        C.push_back(tmp%10);
      }else{
        C[a*b]+=(tmp%10);
      }
      if(C.size()<a*b+1){
        C.push_back(quo);
      }else{
        C[a*b+1]+=quo;
      }
    }
  }
  return C;
}

int main(){
  vector<int> A, B;
  read_big_number(A);
  read_big_number(B);
  print_big_number(mul(A, B));
}