To argue that if heuristic H does not know the access sequence in advance then the worse-case cost of H on an access sequence σ is C H ( σ ) = Ω ( m n ) .

Question

Want to see the full answer?

Answer 1

Question

Chapter 17, Problem 5P

(a)

Program Plan Intro

To argue that if heuristic H does not know the access sequence in advance then the worse-case cost of H on an access sequence σ is CH(σ)=Ω(mn) .

(b)

Program Plan Intro

To show that if σi accesses element x in list L using the move-to-front heuristic the ci=2.rankL(x)−1.

(c)

Program Plan Intro

To explain that equation ci=rankLi−1(x)+ti.

(d)

Program Plan Intro

To argue the transposition either increases the potential by 2 or decrease the potential by 2.

(e)

Program Plan Intro

To argue that rankLi−1(x)=|A|+|B|+1 and rankL*i−1(x)=|A|+|C|+1 .

(f)

Program Plan Intro

To show that access σi causes a change in potential of Φ(Li)=Φ(Li−1)≤2(|A|−|B|+ti) .

(g)

Program Plan Intro

To show that the amortized cost of access is bound by 4ci .

(h)

Program Plan Intro

To show the cost CMTF(σ) of access σ sequence with move-to-front is at most 4 times the cost CH(σ) of σ with any other heuristic H .

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Students have asked these similar questions

Can you find the least amount of different numbers to pick from positive numbers (integers) that are at most 100 to confirm two numbers that add up to 101 when each number can be picked at most two times?

Can you find the formula for an that satisfies the provided recursive definition? Please show all steps and justification

What is the number of injective functions f from set {1,2,....,2n} to set {1,2,....,2n} so that f(x) >= x for all the 1<= x <= n?

Answer 2

Question

Chapter 17, Problem 5P

(a)

Program Plan Intro

To argue that if heuristic H does not know the access sequence in advance then the worse-case cost of H on an access sequence σ is CH(σ)=Ω(mn) .

(b)

Program Plan Intro

To show that if σi accesses element x in list L using the move-to-front heuristic the ci=2.rankL(x)−1.

(c)

Program Plan Intro

To explain that equation ci=rankLi−1(x)+ti.

(d)

Program Plan Intro

To argue the transposition either increases the potential by 2 or decrease the potential by 2.

(e)

Program Plan Intro

To argue that rankLi−1(x)=|A|+|B|+1 and rankL*i−1(x)=|A|+|C|+1 .

(f)

Program Plan Intro

To show that access σi causes a change in potential of Φ(Li)=Φ(Li−1)≤2(|A|−|B|+ti) .

(g)

Program Plan Intro

To show that the amortized cost of access is bound by 4ci .

(h)

Program Plan Intro

To show the cost CMTF(σ) of access σ sequence with move-to-front is at most 4 times the cost CH(σ) of σ with any other heuristic H .

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 3

Question

Chapter 17, Problem 5P

(a)

Program Plan Intro

To argue that if heuristic H does not know the access sequence in advance then the worse-case cost of H on an access sequence σ is CH(σ)=Ω(mn) .

(b)

Program Plan Intro

To show that if σi accesses element x in list L using the move-to-front heuristic the ci=2.rankL(x)−1.

(c)

Program Plan Intro

To explain that equation ci=rankLi−1(x)+ti.

(d)

Program Plan Intro

To argue the transposition either increases the potential by 2 or decrease the potential by 2.

(e)

Program Plan Intro

To argue that rankLi−1(x)=|A|+|B|+1 and rankL*i−1(x)=|A|+|C|+1 .

(f)

Program Plan Intro

To show that access σi causes a change in potential of Φ(Li)=Φ(Li−1)≤2(|A|−|B|+ti) .

(g)

Program Plan Intro

To show that the amortized cost of access is bound by 4ci .

(h)

Program Plan Intro

To show the cost CMTF(σ) of access σ sequence with move-to-front is at most 4 times the cost CH(σ) of σ with any other heuristic H .

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 4

Question

Chapter 17, Problem 5P

(a)

Program Plan Intro

To argue that if heuristic H does not know the access sequence in advance then the worse-case cost of H on an access sequence σ is CH(σ)=Ω(mn) .

(b)

Program Plan Intro

To show that if σi accesses element x in list L using the move-to-front heuristic the ci=2.rankL(x)−1.

(c)

Program Plan Intro

To explain that equation ci=rankLi−1(x)+ti.

(d)

Program Plan Intro

To argue the transposition either increases the potential by 2 or decrease the potential by 2.

(e)

Program Plan Intro

To argue that rankLi−1(x)=|A|+|B|+1 and rankL*i−1(x)=|A|+|C|+1 .

(f)

Program Plan Intro

To show that access σi causes a change in potential of Φ(Li)=Φ(Li−1)≤2(|A|−|B|+ti) .

(g)

Program Plan Intro

To show that the amortized cost of access is bound by 4ci .

(h)

Program Plan Intro

To show the cost CMTF(σ) of access σ sequence with move-to-front is at most 4 times the cost CH(σ) of σ with any other heuristic H .

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 5

Chapter 17, Problem 5P

(a)

Program Plan Intro

To argue that if heuristic H does not know the access sequence in advance then the worse-case cost of H on an access sequence σ is CH(σ)=Ω(mn) .

(b)

Program Plan Intro

To show that if σi accesses element x in list L using the move-to-front heuristic the ci=2.rankL(x)−1.

(c)

Program Plan Intro

To explain that equation ci=rankLi−1(x)+ti.

(d)

Program Plan Intro

To argue the transposition either increases the potential by 2 or decrease the potential by 2.

(e)

Program Plan Intro

To argue that rankLi−1(x)=|A|+|B|+1 and rankL*i−1(x)=|A|+|C|+1 .

(f)

Program Plan Intro

To show that access σi causes a change in potential of Φ(Li)=Φ(Li−1)≤2(|A|−|B|+ti) .

(g)

Program Plan Intro

To show that the amortized cost of access is bound by 4ci .

(h)

Program Plan Intro

To show the cost CMTF(σ) of access σ sequence with move-to-front is at most 4 times the cost CH(σ) of σ with any other heuristic H .

Answer 6

Chapter 17, Problem 5P

(a)

Program Plan Intro

To argue that if heuristic H does not know the access sequence in advance then the worse-case cost of H on an access sequence σ is CH(σ)=Ω(mn) .

Answer 7

Chapter 17, Problem 5P

(a)

Program Plan Intro

To argue that if heuristic H does not know the access sequence in advance then the worse-case cost of H on an access sequence σ is CH(σ)=Ω(mn) .

Answer 8

(b)

Program Plan Intro

To show that if σi accesses element x in list L using the move-to-front heuristic the ci=2.rankL(x)−1.

Answer 9

(b)

Program Plan Intro

To show that if σi accesses element x in list L using the move-to-front heuristic the ci=2.rankL(x)−1.

Answer 10

(c)

Program Plan Intro

To explain that equation ci=rankLi−1(x)+ti.

Answer 11

(c)

Program Plan Intro

To explain that equation ci=rankLi−1(x)+ti.

Answer 12

(d)

Program Plan Intro

To argue the transposition either increases the potential by 2 or decrease the potential by 2.

Answer 13

(d)

Program Plan Intro

To argue the transposition either increases the potential by 2 or decrease the potential by 2.

Answer 14

(e)

Program Plan Intro

To argue that rankLi−1(x)=|A|+|B|+1 and rankL*i−1(x)=|A|+|C|+1 .

Answer 15

(e)

Program Plan Intro

To argue that rankLi−1(x)=|A|+|B|+1 and rankL*i−1(x)=|A|+|C|+1 .

Answer 16

(f)

Program Plan Intro

To show that access σi causes a change in potential of Φ(Li)=Φ(Li−1)≤2(|A|−|B|+ti) .

Answer 17

(f)

Program Plan Intro

To show that access σi causes a change in potential of Φ(Li)=Φ(Li−1)≤2(|A|−|B|+ti) .

Answer 18

(g)

Program Plan Intro

To show that the amortized cost of access is bound by 4ci .

Answer 19

(g)

Program Plan Intro

To show that the amortized cost of access is bound by 4ci .

Answer 20

(h)

Program Plan Intro

To show the cost CMTF(σ) of access σ sequence with move-to-front is at most 4 times the cost CH(σ) of σ with any other heuristic H .

Answer 21

(h)

Program Plan Intro

To show the cost CMTF(σ) of access σ sequence with move-to-front is at most 4 times the cost CH(σ) of σ with any other heuristic H .

Answer 22

Expert Solution & Answer

Answer 23

Expert Solution & Answer

Answer 24

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 25

Ch. 17.1 - Prob. 1E Ch. 17.1 - Prob. 2E Ch. 17.1 - Prob. 3E Ch. 17.2 - Prob. 1E Ch. 17.2 - Prob. 2E Ch. 17.2 - Prob. 3E Ch. 17.3 - Prob. 1E Ch. 17.3 - Prob. 2E Ch. 17.3 - Prob. 3E Ch. 17.3 - Prob. 4E

To argue that if heuristic H does not know the access sequence in advance then the worse-case cost of H on an access sequence σ is C H ( σ ) = Ω ( m n ) .

Solution Summary: The author argues that if heuristic H does not know the access sequence in advance, the worse-case cost of H is CH(sigma )=Omega (mn).

Concept explainers

To argue that if heuristic H does not know the access sequence in advance then the worse-case cost of H on an access sequence σ is CH(σ)=Ω(mn) .

To show that if σi accesses element x in list L using the move-to-front heuristic the ci=2.rankL(x)−1.

To explain that equation ci=rankLi−1(x)+ti.

To argue the transposition either increases the potential by 2 or decrease the potential by 2.

To argue that rankLi−1(x)=|A|+|B|+1 and rankL*i−1(x)=|A|+|C|+1 .

To show that access σi causes a change in potential of Φ(Li)=Φ(Li−1)≤2(|A|−|B|+ti) .

To show that the amortized cost of access is bound by 4ci .

To show the cost CMTF(σ) of access σ sequence with move-to-front is at most 4 times the cost CH(σ) of σ with any other heuristic H .

Want to see the full answer?

Chapter 17 Solutions