xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-CS326

时间：2021-03-14

Homework Set 4: Selection, Amortization, and Greed

CS326

1. The Oil of Olay Problem [25 points]

Exercise 9.3-9 in CLRS (Page 193). Before beginning this problem, argue why placing the

pipeline at the mean value of y might not necessarily give an optimal answer (i.e. provide

a counter example in which this strategy will break). “Showing an optimal location can be

determined in linear time” requires describing an algorithm that: i) runs in linear time; and

ii) is actually correct.

While you don’t need to show a formal proof of correctness, you should provide a clear

explanation for why your approach correctly returns an optimal answer.

2. Dynamic Arrays Revisited [40 points] A dynamically re-sizing array is an array that is

initially allocated at size 1, and every time you need to insert past the end of the array you

double its size and copy elements from the old array to the new array.

In class, we showed that n inserts into a dynamic array can be accomplished in O(n) using an

accounting argument where we pre-paid $3 for each insert, thus pre-paying for its doubling

and the doubling of one older element.

(a) Formally write the proof for this accounting

(b) Show the same bound using the potential method

(c) Does this O(n) bound on n operations hold if you include deletions? Why or why not?

(Credit will be given for solutions that prove that a bound does work with particular

array assumptions).

3. Amortizing Red-Black Trees [50 points]

CLRS Problem 17-4, parts a, c, d, e, f (In the back of the chapter)

4. Block Uh Oh [20 points] Dr. I Lai has a son in preschool, and she wants to spell out words

to him with alphabet blocks by picking up one block at a time to show to him. However,

somehow every block is covered in BabySlime, so they are very hard to pick up unless they

are in the ACME Block Washer. Unfortunately, the washer has only 5 spots. Picking up a

block from the washer costs one Happiness Point every time. Picking up a block from the

washer is free!

Dr. Lai would to spell out her favorite song, ”ALGORITHMS ARE THE BESTEST BEST

BEST YEAH”, with a minimal number of BabySlime interactions (so as many letters pulled

out of the block washer as possible). Note: Letters can be swapped into the block washer,

but putting a new block into the washer requires getting it from the table, which costs a

happiness point.

1

(a) Design an optimal Greedy Algorithm for placing blocks in the block holder. What is the

cost in happiness points?

(b) Generalize your algorithm to k blocks in the holder and a string of size k.

(c) Can you use a greedy algorithm if you don’t know the entire sequence ahead of time?

2

学霸联盟

CS326

1. The Oil of Olay Problem [25 points]

Exercise 9.3-9 in CLRS (Page 193). Before beginning this problem, argue why placing the

pipeline at the mean value of y might not necessarily give an optimal answer (i.e. provide

a counter example in which this strategy will break). “Showing an optimal location can be

determined in linear time” requires describing an algorithm that: i) runs in linear time; and

ii) is actually correct.

While you don’t need to show a formal proof of correctness, you should provide a clear

explanation for why your approach correctly returns an optimal answer.

2. Dynamic Arrays Revisited [40 points] A dynamically re-sizing array is an array that is

initially allocated at size 1, and every time you need to insert past the end of the array you

double its size and copy elements from the old array to the new array.

In class, we showed that n inserts into a dynamic array can be accomplished in O(n) using an

accounting argument where we pre-paid $3 for each insert, thus pre-paying for its doubling

and the doubling of one older element.

(a) Formally write the proof for this accounting

(b) Show the same bound using the potential method

(c) Does this O(n) bound on n operations hold if you include deletions? Why or why not?

(Credit will be given for solutions that prove that a bound does work with particular

array assumptions).

3. Amortizing Red-Black Trees [50 points]

CLRS Problem 17-4, parts a, c, d, e, f (In the back of the chapter)

4. Block Uh Oh [20 points] Dr. I Lai has a son in preschool, and she wants to spell out words

to him with alphabet blocks by picking up one block at a time to show to him. However,

somehow every block is covered in BabySlime, so they are very hard to pick up unless they

are in the ACME Block Washer. Unfortunately, the washer has only 5 spots. Picking up a

block from the washer costs one Happiness Point every time. Picking up a block from the

washer is free!

Dr. Lai would to spell out her favorite song, ”ALGORITHMS ARE THE BESTEST BEST

BEST YEAH”, with a minimal number of BabySlime interactions (so as many letters pulled

out of the block washer as possible). Note: Letters can be swapped into the block washer,

but putting a new block into the washer requires getting it from the table, which costs a

happiness point.

1

(a) Design an optimal Greedy Algorithm for placing blocks in the block holder. What is the

cost in happiness points?

(b) Generalize your algorithm to k blocks in the holder and a string of size k.

(c) Can you use a greedy algorithm if you don’t know the entire sequence ahead of time?

2

学霸联盟