Yioop - PHP Search Engine

-- May 13 - Final Review

Problem 10: Give the TRIM(L,δ) algorithm we used as part of our fully p-time approximation algorithm for SUBSET-SUM. Give an example of applying it to a list of integers.

TRIM(L, δ)
We assume L = (y[1], ..., y[m])
1 let m be the length of L
2 L' = (y[1])
3 last = y[1]
4 for i = 2 to m
5     if y[i] > last * (1 + δ) // y[i] ≥ last because L is sorted
6         append y[i] to L'
7         last = y[i]
8 return L'

`\frac{y}{1 + δ} ≤ z ≤ y `

For Example if `δ = 0.1` and `L = ⟨12,13,23,25,26,40,45,60,77⟩`

`L^' = ⟨12, 23, 26, 40, 45, 60, 77⟩`(Edited: 2019-05-15)

'''Problem 10:''' Give the TRIM(L,δ) algorithm we used as part of our fully p-time approximation algorithm for SUBSET-SUM. Give an example of applying it to a list of integers. <pre> TRIM(L, δ) We assume L = (y[1], ..., y[m]) 1 let m be the length of L 2 L' = (y[1]) 3 last = y[1] 4 for i = 2 to m 5 if y[i] > last * (1 + δ) // y[i] ≥ last because L is sorted 6 append y[i] to L' 7 last = y[i] 8 return L' </pre> <math>\frac{y}{1 + δ} &leq; z &leq; y </math> For Example if <math>δ = 0.1</math> and <math>L = ⟨12,13,23,25,26,40,45,60,77⟩</math> <math>L^' = ⟨12, 23, 26, 40, 45, 60, 77⟩</math>

-- May 13 - Final Review

10) Give the TRIM(L,δ) algorithm we used as part of our fully p-time approximation algorithm for SUBSET-SUM. Give an example of applying it to a list of integers.

TRIM(L, δ)

We assume L = (y[1], ..., y[m])

let m be the length of L

L' = (y[1])

last = y[1]

for i = 2 to m

    if y[i] > last * (1 + δ) // y[i] ≥ last because L is sorted

        append y[i] to L'

        last = y[i]

return L'

An example : L=⟨50,51,55,70,71,82,83,84,99⟩

and δ=0.1.

Using the inequality from above,

L'=⟨50,55,70,82,99⟩

(Edited: 2019-05-15)

'''10) Give the TRIM(L,δ) algorithm we used as part of our fully p-time approximation algorithm for SUBSET-SUM. Give an example of applying it to a list of integers.''' TRIM(L, δ) We assume L = (y[1], ..., y[m]) let m be the length of L L' = (y[1]) last = y[1] for i = 2 to m if y[i] > last * (1 + δ) // y[i] ≥ last because L is sorted append y[i] to L' last = y[i] return L' An example : L=⟨50,51,55,70,71,82,83,84,99⟩ and δ=0.1. Using the inequality from above, L'=⟨50,55,70,82,99⟩

-- May 13 - Final Review

Problem 10

 TRIM(L, δ)
 We assume L = (y[1], ..., y[m])
 1 let m be the length of L
 2 L' = (y[1])
 3 last = y[1]
 4 for i = 2 to m
 5     if y[i] > last * (1 + δ)
 6         append y[i] to L'
 7         last = y[i]
 8 return L'

Example:

L = <18, 24, 33, 35, 40, 41, 52, 59, 68, 70>, δ = 0.5

L’ = (18) ----- 18 x 1.5 = 27

L’ = (18, 33) ----- 33 x 1.5 = 49.5

L’ = (18, 33, 52) ----- 52 x 1.5 = 78

Trimmed list: L’ = <18, 33, 52>

(Edited: 2019-05-15)

'''Problem 10''' TRIM(L, δ) We assume L = (y[1], ..., y[m]) 1 let m be the length of L 2 L' = (y[1]) 3 last = y[1] 4 for i = 2 to m 5 if y[i] > last * (1 + δ) 6 append y[i] to L' 7 last = y[i] 8 return L' Example: L = <18, 24, 33, 35, 40, 41, 52, 59, 68, 70>, δ = 0.5 L’ = (18) ----- 18 x 1.5 = 27 L’ = (18, 33) ----- 33 x 1.5 = 49.5 L’ = (18, 33, 52) ----- 52 x 1.5 = 78 Trimmed list: L’ = <18, 33, 52>

-- May 13 - Final Review

A list L' is a trimmed list of L by δ if it contains only elements from L and if for every y∈L there is a z∈L' such that 1/(1+δ>≤z≤y.

L=⟨50,51,55,70,71,82,83,84,99⟩， δ=0.1

  50 -> 45.45<=z<=50 -> 50
  51 -> 46.36<=z<=51 -> 50,51
  55 -> 50<=z<=55 -> 50, 51, 55
  70 -> 63.63<=z<=70 -> 70
  71 -> 64.54<=z<=71 -> 70, 71
  82 -> 74.54<=z<=82 -> 82
  83 -> 75.45<=z<=83 -> 82, 83
  84 -> 76.36<=z<=84 -> 82, 83, 84
  99 -> 90<=z<=99 -> 99
 
  L' = ⟨50,55,70,82,99⟩

A list L' is a trimmed list of L by δ if it contains only elements from L and if for every y∈L there is a z∈L' such that 1/(1+δ>≤z≤y. L=⟨50,51,55,70,71,82,83,84,99⟩， δ=0.1 50 -> 45.45<=z<=50 -> 50 51 -> 46.36<=z<=51 -> 50,51 55 -> 50<=z<=55 -> 50, 51, 55 70 -> 63.63<=z<=70 -> 70 71 -> 64.54<=z<=71 -> 70, 71 82 -> 74.54<=z<=82 -> 82 83 -> 75.45<=z<=83 -> 82, 83 84 -> 76.36<=z<=84 -> 82, 83, 84 99 -> 90<=z<=99 -> 99 L' = ⟨50,55,70,82,99⟩

-- May 13 - Final Review

10. TRIM(L, δ) We assume L = (y[1], ..., y[m])

1 let m be the length of L

2 L' = (y[1])

3 last = y[1]

4 for i = 2 to m

5 if y[i] > last * (1 + δ) // y[i] ≥ last because L is sorted

6 append y[i] to L'

7 last = y[I]

8 return L'

`y/(1+δ)≤z≤y`

Example: <50,51,55,70,71,82,83,84,99> Let `δ=0.1`. Using `TRIM(L,δ)` L'=⟨50,55,70,82,99⟩

(Edited: 2019-05-16)

10. TRIM(L, δ) We assume L = (y[1], ..., y[m]) 1 let m be the length of L 2 L' = (y[1]) 3 last = y[1] 4 for i = 2 to m 5 if y[i] > last * (1 + δ) // y[i] ≥ last because L is sorted 6 append y[i] to L' 7 last = y[I] 8 return L' @BT@y/(1+δ)≤z≤y@BT@ Example: <50,51,55,70,71,82,83,84,99> Let @BT@δ=0.1@BT@. Using @BT@TRIM(L,δ)@BT@ L'=⟨50,55,70,82,99⟩

-- May 13 - Final Review

TRIM(L, δ)

 We assume L = (y[1], ..., y[m])
 1 let m be the length of L
 2 L' = (y[1])
 3 last = y[1]
 4 for i = 2 to m
 5     if y[i] > last * (1 + δ)
 6         append y[i] to L'
 7         last = y[i]
 8 return L'

<50,51,55,70,71,82,83,84,99>

δ=0.1

TRIM(L,δ) L'=⟨50,55,70,82,99⟩

TRIM(L, δ) We assume L = (y[1], ..., y[m]) 1 let m be the length of L 2 L' = (y[1]) 3 last = y[1] 4 for i = 2 to m 5 if y[i] > last * (1 + δ) 6 append y[i] to L' 7 last = y[i] 8 return L' <50,51,55,70,71,82,83,84,99> δ=0.1 TRIM(L,δ) L'=⟨50,55,70,82,99⟩