Csc263 Assignment Definition

 

Computer Science CSC263H February 3, 2011St. George Campus University of TorontoSolutions for Homework Assignment #1

Answer to Question 1.

(20 marks)

a.

(6 marks) If the input array is 1

,

2

,

3 then

Build-Max-Heap

transforms it to 3

,

2

,

1 while

Build-by-Inserts

transforms it to 3

,

1

,

2.

b.

(14 marks) Let

(

n

) denote the worst-case running time of 

Build-by-Inserts

on an input array

A

of size

n

. We must show that

(

n

) is Θ(

n

log

2

n

). To do so, we must show that

(

n

) is both

O

(

n

log

2

n

)and Ω(

n

log

2

n

).

(

n

) is

O

(

n

log

2

n

). To show this upper bound on

(

n

), note that on every input array

A

of size

n

the loop of 

Build-by-Inserts

is executed exactly

n

1 times. Each time this loop is executed,it inserts an element into a heap that has

at most 

n

elements. Thus, there is a constant

c

suchthat every insertion takes

at most 

c

log

2

n

time, and so the

n

1 iterations of the loop take

at most 

cn

log

2

n

time. We conclude that

(

n

) is

O

(

n

log

2

n

).

(

n

) is Ω(

n

log

2

n

). To show this lower bound on

(

n

), consider the execution of 

Build-by-Inserts

on an input array

A

of 

n

elements such that the

n

elements of 

A

appear in increasing order. In thisexecution, for each

j

:1. The

j

th iteration of the loop inserts an element to a heap that already contains

j

elements.2. The

j

th iteration of the loop inserts an element that is larger than any other presently in theheap, and so this element must “percolate up” from the bottom level to the root of the heap.So there is a constant

c

such that for every

j

, the

j

th iteration takes

at least 

c

log

2

j

time. Thus,the

n

1 iterations take

at least 

c

n

1

j

=1

log

2

j

time. It turns out that, for all

n

2

8

= 256,

n

1

j

=1

log

2

j

 ≥

116

n

log

2

n

(we include the proof at the end of this solution set). We conclude that,for every

n

256, there is an input array

A

of length

n

for which

BuildNewHeap

takes

at least 

c

16

n

log

2

n

time. Thus,

(

n

) is Ω(

n

log

2

n

).

Answer to Question 2.

(20 marks)

a.

(8 marks) A binomial heap

with

n

vertices consists of 

α

(

n

) trees. Let

i

, 1

i

α

(

n

), denotethe trees of 

. A tree

i

with

n

i

vertices has

n

i

1 edges. So the total number of edges in

is

i

=

α

(

n

)

i

=1

(

n

i

1) = (

i

=

α

(

n

)

i

=1

n

i

)

α

(

n

) =

n

α

(

n

)

b.

(12 marks) Binomial heap

has

n

nodes before the insertions. By Part (a), it has

n

α

(

n

) edgesbefore the insertions. After

k

consecutive insertions,

has

n

+

k

nodes, hence it now has (

n

+

k

)

α

(

n

+

k

)edges. So the number of new edges created during the

k

consecutive insertions is:[(

n

+

k

)

α

(

n

+

k

)]

[

n

α

(

n

)] =

k

+

α

(

n

)

α

(

n

+

k

)

k

+

α

(

n

) edges.As we explained in class, the number of pairwise comparisons between the elements of 

needed toexecute

k

consecutive insertions is equal to the number of new edges created during these insertions (eachnew edge is the result of a pairwise comparison, and each pairwise comparison creates a new edge in

).So

k

consecutive insertions require at most

k

+

α

(

n

) comparisons. By definition

α

(

n

) is the number of 1’sin the binary representation of 

n

, therefore,

α

(

n

)

≤ 

log

2

n

+ 1. So

k

consecutive insertions require atmost

k

+

log

2

n

+ 1 comparisons. Note that if 

k >

log

2

n

,

k

is the dominant factor in

k

+

log

2

n

+ 1.So, when

k >

log

2

n

,

k

consecutive insertions require just

O

(

k

) pairwise comparisons (a constant numberof comparisons per insertion on the average).1

Unformatted text preview: CSC 263 H1 Assignment #1 Winter 2015 Worth: 12% Due: By 5:59pm on Tuesday 10 February Remember to write the full name and student number of every group member prominently on your submission. Please read and understand the policy on Collaboration given on the Course Information Sheet. Then, to protect yourself, list on the front of your submission every source of information you used to complete this homework (other than your own lecture and tutorial notes). For example, indicate clearly the name of every student from another group with whom you had discussions, the title and sections of every textbook you consulted (including the course textbook), the source of every web document you used (including documents from the course webpage), etc. For each question, please write up detailed answers carefully. Make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjusti±ed, ambiguous, or vague claims in your solutions. 1. Considering the follow algorithm which searches for the last appearance of value k in an array A of length n . The index of the array starts from 0. FindLast ( A,k ) : 1 for i ← n − 1 ,n − 2 ,..., 0 : 2 if A [ i ] = k : 3 return i 4 return − 1 The input array A is generated in the following speci±c way: for A [0] we pick an integer from { , 1 } uniformly at random; for A [1] we pick an integer from { , 1 , 2 } uniformly at random; for A [2] we pick an integer from { , 1 , 2 , 3 } uniformly at random, etc. That is, for A [ i ] we pick an integer from { ,...,i + 1 } uniformly at random. All choices are independent from each other. Now, let’s analyse the complexity of FindLast by answering the following questions. All your answers should be in exact form , i.e., not in asymptotic notations. Note : For simplicity, we assume that k is an integer whose values satis±es 1 l k l n . (a) In the best case , for input ( A,k ), how many times is Line #2 (“ if A [ i ] = k ”) executed? Justify your answer. (b) What is the probability that the best case occurs? Justify carefully: show your work and explain your calculation. (c) In the worst case , for input ( A,k ), how many times is Line #2 executed? Justify your answer. (d) What is the probability that the worst case occurs? Justify carefully: show your work and explain your calculation. (e) In the average case , for input ( A,k ), how many times is Line #2 expected to be executed? Justify your answer carefully: show your work and explain your calculation. Hint: Your answers should be in terms of both n and k . Thinking about the number of comparisons needed to ±nd a given k , which values are possible, which values are not?...
View Full Document

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *