xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

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

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

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

扫码添加客服微信

扫描添加客服微信

python代写-FIT3155-Assignment 2

时间：2021-04-19

FIT3155 S1/2021: Assignment 2

(Due midnight 11:59pm on Fri 30th April 2021)

[Weight: 20 = 3 + 8 + 3 + 6 marks.]

Your assignment will be marked on the performance/efficiency of your program. You must

write all the code yourself, and should not use any external library routines, except those

that are considered standard. The usual input/output and other unavoidable routines are

exempted.

Follow these procedures while submitting this assignment:

The assignment should be submitted online via moodle strictly as follows:

• All your scripts MUST contain your name and student ID.

• Use gzip or Winzip to bundle your work into an archive which uses your student ID

as the file name. (STRICTLY AVOID UPLOADING .rar ARCHIVES!)

– Your archive should extract to a directory which is your student ID.

– This directory should contain a subdirectory for each of the four questions, named

as: q1/, q2/, q3/ and q4/.

– Your corresponding scripts and work should be tucked within those subdirectories.

Note: If you have scripts that are common to multiple questions, such as your

suffix tree construction, you may include the script in the parent directory, or

copy it into the relevant subdirectories.

• Submit your zipped file electronically via Moodle.

Academic integrity, plagiarism and collusion

Monash University is committed to upholding high standards of honesty and academic

integrity. As a Monash student your responsibilities include developing the knowl-

edge and skills to avoid plagiarism and collusion. Read carefully the material available

at https://www.monash.edu/students/academic/policies/academic-integrity to understand

your responsibilities. As per FIT policy, all submissions will be scanned via MOSS.

1

Assignment Questions

1. (3 marks) Recall that a spanning tree of a graph G(V,E) is a subgraph T consisting of

all the vertices in V and some subset of edges E ′ ⊂ E such that T is a tree. That is, a

spanning tree is a collection of edges that form a tree and connect all the vertices in V .

A spanning tree in a weighted graph is called a weighted spanning tree and a weighted

spanning tree of minimum total possible weight is called a minimum spanning tree.

Given a weighted undirected graph G(V,E), your task is to write a program that uses

Kruskal’s algorithm (see notes from FIT2004) to find a minimum weight spanning tree in

G. You may assume that G is connected.

Strictly follow the following specification to address this task:

Program name: kruskals.py

Arguments to your program: The total number of vertices |V | (the size of G’s vertex

set) as a positive integer, and a plain text file. Every line in the text file contains

single edge with weight w connecting vertex u to vertex v in G represented by 3

integers in the following format:

u v w

The integers u and v are integers in the range [0 . . . |V | − 1]. Each of the integers in

the line are separated by a single space.

Command line usage of your script:

kruskals.py <|V|>

Do not hard-code the filename in your program.

Output file name: output kruskals.txt

Output format: The output file should contain:

• The total weight (as an integer) of a minimum spanning tree in G on the first

line.

• The edges of the minimum weight spanning found by your program. There

should be one edge per line, (starting from the second line) in the same format

as the input edge file.

Example: In the example below the minimum weight spanning tree (shown in red) has

weight 1 + 4 + 6 + 2 + 1 + 2 = 16. In this case the usage of your program would be:

python kruskals.py 7 G.txt

2

Where G.txt would contain:

0 1 5

1 2 4

2 3 2

3 4 10

4 5 6

5 0 1

0 6 8

1 6 2

2 6 1

3 6 3

4 6 7

5 6 4

Finally, the output of your program in this case would be a file output kruskals.txt

containing the weight of the minimum spanning tree (16) on the first line, followed

by the edges contained in the tree:

16

0 5 1

2 6 1

2 3 2

1 6 2

5 6 4

4 5 6

3

Questions 2 and 3 must be addressed using a suffix tree. There are 6 marks assigned

to suffix tree construction and these are included in the 8 marks available for question

2. That is for question 2, 6/8 marks are dedicated to suffix tree construction while the

remaining 2 are allocated to your use of the suffix tree and the output of your program.

As always, marking will be based on the efficiency of your suffix tree construction, and

those of the tasks below.

2. (8 marks) Given a string str[0 . . . n− 1], write a program that constructs its suffix tree,

and using that suffix tree, outputs the suffix array of the string. Note suffix arrays were

covered in FIT2004.

Strictly follow the following specification to address this task:

Program name: suffix array.py

Argument to your program: An input file containing str[0 . . . n − 1]. It is safe to

assume that:

• str consists of lower case English characters, i.e. ASCII characters with values

in the range [97 . . . 122].

• There are no line breaks in the input file, and that all characters str[0 . . . n− 1]

are lexicographically larger than the terminal character, $, which you will need

to append to str[0 . . . n− 1] after reading it from the file.

Command line usage of your script:

suffix array.py

Do not hard-code the filename in your program.

Output file name: output suffix array.txt

• Output format: The output file should contain the start indices of all the suffixes

in str[0 . . . n−1]$ in the order that they appear in the corresponding suffix array.

Each line of the file should contain a single suffix index as shown in the example

below.

Example: If str[0 . . . 10]$ = mississippi$ then the output would be:

11

10

7

4

1

0

9

8

6

3

5

2

4

3. (3 marks) For strings S1[0 . . . n− 1] and S2[0 . . .m− 1], define the values L(i, j) for any

0 ≤ i ≤ n − 1 and 0 ≤ j ≤ m − 1, as the longest prefix common to the suffixes starting

at position i in S1 and position j in S2.

For a given pair of input strings S1[0 . . . n− 1] and S2[0 . . .m− 1] and a list of (i, j) pairs

your task is to use a suffix tree to compute the L(i, j) value for each (i, j) pair in the list.

Strictly follow the following specification to address this task:

Program name: lcp.py

Arguments to your program:

(a) An input file containing S1[0 . . . n− 1].

(b) An input file containing S2[0 . . .m− 1].

(c) An input file containing a list of (i, j) pairs, one per line in the format:

i j

where 0 ≤ i ≤ n− 1 and 0 ≤ j ≤ m− 1.

It is safe to assume that:

• S1 and S2 consist of lower case English characters, i.e. ASCII characters with

values in the range [97 . . . 122].

• There are no line breaks in the files containing S1 and S2.

• Each line of the (i, j) pairs file contains a single pair where each index is sepa-

rated by a single whitespace (see example below).

Command line usage of your script:

lcp.py

Do not hard-code the filename in your program.

Output file name: output lcp.txt

• Each line should contain of a single pair of i and j indices followed by the corre-

sponding L(i, j) value, with each value being separated by a single whitespace

e.g. in the following format:

i j L(i,j)

Example: If S1[0 . . . 9] = abcdacbdab, S2[0 . . . 7] = dacbdabc and the input (i, j) pairs

file contained:

3 0

4 2

0 5

then the output should be:

3 0 7

4 2 0

0 5 3

5

4. (6 marks)

To give your fingers a break from coding this question will focus on the amortised analysis

of a Fibonacci heap.

Strictly follow the following specification to address this task:

File name: fibonacci.pdf

Submission instrcutions:

Your pdf file should contain your solutions to parts a-j below. Clearly indicate

which question each section in your solution refers to and be careful to include all

the necessary working. You may type your solutions or write them by hand and scan

them into a pdf file. Please note that if you choose to submit hand written solutions

it is your responsibility to ensure that your hand writing is legible. If your marker

cannot read your work you will not receive marks for it!

Once you have collected your solutions into a pdf file (named appropriately) simply

place it inside of your q4 subdirectory.

6

Preliminaries

Recall that the goal of any amortised analysis is to provide an upper bound on the cost

of any sequence of operations that might be performed on a given data structure. That

is, if we denote the true, or actual cost of some sequence of operations {op1, op2, . . . , opn}

as TC({op1, op2, . . . , opn}) then we desire some costing scheme that always ensures that

the amortised cost of this sequence (AC({op1, op2, . . . , opn})) is such that,

AC({op1, op2, . . . , opn}) ≥ TC({op1, op2, . . . , opn}). (1)

It is important to stress that this must be true for any sequence of operations not just

one specific sequence!

At this point you are likely already familiar with one costing scheme known as the ag-

gregate method where we simply assign AC({op1, op2, . . . , opn}) to be the cost (or some

upper bound on it) of the worst case sequence. We then distribute this work evenly

amongst the constituent operations to define the amortised cost of each operation oi -

denoted aci - as,

aci =

AC({op1, op2, . . . , opn})

n

. (2)

However, the amortised cost of the sequence need not be distributed evenly amongst the

operations in the sequence.

In the potential method we instead define the amortised cost of an operation oi to be,

aci = tci + Φ(Di)− Φ(Di−1), (3)

where tci is the true, or the actual cost of operation oi, Di is the state of the data

structure after operation oi has been completed, and Φ is known as a potential function.

The potential function simply maps the state of the data structure Di to a real number

Φ(Di), which is referred to as the potential associated with Di.

Using our newly defined notation and noting that the amortised cost of a sequence of

operations is simply the sum of the amortised cost of each individual operation in the

sequence we obtain,

AC({op1, op2, . . . , opn}) =

n∑

i=1

aci =

n∑

i=1

tci + Φ(Dn)− Φ(D0) (4)

(a) (0.5 marks) Use equation 3 to derive the right-hand-side of equation 4.

Since TC({op1, op2, . . . , opn}) =

∑n

i=1 tci we require Φ(Dn) ≥ Φ(D0) in equation 4 so

that the amortised cost of the sequence always upper bounds its true cost. Moreover, it is

common to define a potential function such that Φ(D0) = 0 and since in practice we don’t

always know how many operations will be in our sequence we also require Φ(Di) ≥ Φ(D0)

for all i. Thus, if we can show that Φ(Di) ≥ 0 for all i, we guarantee that the amortised

cost will always upper bound the true cost of any sequence.

7

Fibonacci heaps

To this point everything has been a little abstract, so let’s try to intuit what we have so

far and begin applying it to a Fibonacci heap. Examining equation 3,

aci = tci + Φ(Di)− Φ(Di−1),

we can see that the amortised cost for operation oi can be more or less than the true

cost. This means that the potential function Φ acts as a kind of credit and debit account

for our data structure. If the change in potential ∆Φ = Φ(Di)− Φ(Di−1) is positive this

amounts to overestimating the cost of the operation, which increases the potential and

corresponds to making a credit to our account. Conversely if ∆Φ < 0 then our potential

decreases as we have underestimated the cost of the operation, which corresponds to

making a debit to our account. Since initially Φ(D0) = 0 and we want Φ(Di) ≥ 0 for

all i, we essentially start with an empty account that we want to keep out of debit by

ensuring that we overestimate at least as much as we underestimate. This ensures that

our amortised cost always upper bounds the true cost of the sequence. With this you

should now have the necessary background knowledge required to analyse a Fibonacci

heap which will be the focus of the remainder of the assignment.

Let’s begin by considering a restricted version of a Fibonacci heap that only supports the

operations:

• Merge1

• Insert

• Find min

• Extract min

The reason for the omission of decrease key and delete from this list will become clear

later. To analyse the amortised complexity of these operations let’s define the potential

of a restricted Fibonacci heap H to be,

Φ(H) = T (H), (5)

where T (H) is the number of nodes in the root list of H. If we were to use this potential

to derive the amortised cost of find min we’d proceed as follows.

First we need to find the true cost of the operation, which is clearly O(1) since the

minimum element in the heap can be accessed directly via Hmin. In addition, since this

operation does not alter the number of nodes in the root list of H we have,

Φ(Di)− Φ(Di−1) = T (H)− T (H) = 0,

and so by equation 3 the amortised cost of find min is given by,

aci = tci + Φ(Di)− Φ(Di−1)

= O(1) + 0

= O(1).

In this case we see that the amortised cost for find min is actually equal to the true cost

of the operation.

1To analyse merge using our potential method we’d need to consider the potential of two separate heaps

H1 and H2 initially. To do so we simply define the potential of a collection of heaps to be the sum of their

individual potentials.

8

(b) (0.5 marks) Use the potential function given in equation 5 to derive the amortised

cost of insert.

Now that we’ve seen some examples of the potential method let’s quickly revisit equation

3,

aci = tci + Φ(Di)− Φ(Di−1).

If we were to overestimate the cost of operation oi by 3 units of potential then our

current interpretation would imply that those 3 units of potential are worth 3 units of

work. We can then use this potential to compensate for 3 units of work the next time

we underestimate the cost of an operation. However, we are free to scale the units of

the potential so that a single unit corresponds to any constant amount of work. In other

words, equation 3 should really be written as,

aci = tci +m [Φ(Di)− Φ(Di−1)] , (6)

where m is a positive real constant that we’ve implicitly assumed to be equal to 1 up

until this point.

(c) (1 mark) Show that the amortised cost of extract min is O(Dmax(N)), where N is

the number of nodes in H and Dmax(N) denotes the maximum degree of a node in

H.

Hint: Start by showing the true cost is O(T (H) +Dmax(N)) and then show that you

can scale the units of potential to leave O(Dmax(N)) for the amortised cost.

(d) (0.5 marks) Argue that for our restricted heap Dmax(N) ≤ blog2(N)c.

Now that we’ve analysed the operations of our restricted heap (you can convince yourself

that the amortised cost of merge is O(1)) let’s reintroduce decrease key.

The reason we initially omitted this operation from our list was that it complicates the

analysis slightly. For instance, the bound derived in part (f) is no longer valid, but we can

still show that the amortised cost of extract min is O(log(N)) even when decrease keys

are allowed.

To do so we need to show that Dmax(N) is still O(log(N)). This amounts to showing

that in the worst case the size of a given tree in H is still given by a function that is

exponential in the degree of the tree, so let’s determine how small our trees can get. Let’s

define a maximally decreased tree of degree k to be a tree - of degree k - in a Fibonacci

heap that has lost the maximum number of nodes from its subtrees due to decrease key

operations. Put another way, a maximally decreased tree is one from which we can’t

remove any more nodes via decrease keys without also decreasing the degree of the root.

For instance, the maximally decreased trees of degree 0, 1, 2 and 3 contain 1, 2, 3 and 5

nodes respectively, as shown in figure 1.

Figure 1: Maximally decreased trees of degree 0, 1, 2 and 3. The marked - denoted by the

shading - nodes have lost one child and the numbers represent the degree of each node rather

than the key of the node.

9

(e) (0.5 marks) How many nodes are in a maximally decreased tree of degree k?

Hint: Begin by simply drawing out maximally decreased trees of increasing degree

(you might find the representation used in figure 1 helpful). Now count the number

of nodes in each of these trees, can you spot a pattern? It may help to recall that the

Fibonacci sequence is defined as,

F0 = 0, F1 = 1 and Fn = Fn−1 + Fn−2 for n > 1,

and the start of the sequence is shown below.

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10

0 1 1 2 3 5 8 13 21 34 55

(f) (1.25 mark) Prove - using the principle of mathematical induction - that the expres-

sion you derived for the size of a maximally decreased tree in the previous part is

correct.

Hint: Think about how you can construct a maximally decreased tree of degree k

from maximally decreased trees of smaller degree.

At this point you should have an expression for the number of nodes in a maximally

decreased tree of degree k. By definition we know that this tree contains the fewest nodes

of any tree of degree k in our heap. Therefore, in general a tree of degree k rooted at r

in our heap must contain at least this many nodes i.e.,

size(r) ≥ g(k), (7)

where size(r) is the number of nodes in the tree and g(k) is the number nodes in a

maximally decreased tree of degree k that you found in part (e).

(g) (0.5 marks) Using equation 7 and the fact that,

Fk+2 ≥ φk, (8)

for all integers k ≥ 0, where φ = 1+

√

5

2

is the golden ratio, show that Dmax(N) =

O(log(N)) even when decrease key operations are allowed.

The result in part (g) proves that even when decrease key operations are allowed the

amortised complexity of extract min is still O(Dmax(N)) = O(log(N)).

Finally let’s conclude by deriving the amortised cost of decrease key.

(h) (0.5 marks) Using the potential given in equation 5, derive the amortised cost of a

decrease key operation. Is this what you’d expect?

Hint: Assume that you perform c ≥ 0 cascading cuts during the operation and

consider the true and amortised cost in this case.

Currently our potential is simply storing credits during decrease key that are used during

the extract min to offset the fact that we are adding more nodes to our root list. However,

we aren’t using any of our potential to compensate for the fact that marking nodes also

produces extra work in the form of cascading cuts in future decrease keys. To resolve this

let’s ‘back charge’ this work to the decrease keys that marked the nodes in the first place.

10

That is, we want to modify our potential so that we account for this work (make a credit)

every time we mark a node.

Let’s consider the potential,

Φ = T (H) + αM(H), (9)

where α is a positive constant and M(H) denotes the number of marked nodes in H. Now

every time we mark a node our potential increases by α units, but what value should we

choose for α?

(i) (0.5 marks) Determine the smallest integral value of α for which the potential in

equation 9 yields an O(1) amortised cost for decrease key.

(j) (0.25 marks) Explain why this value of α intuitively makes sense.

-=o0o=-

END

-=o0o=-

11

(Due midnight 11:59pm on Fri 30th April 2021)

[Weight: 20 = 3 + 8 + 3 + 6 marks.]

Your assignment will be marked on the performance/efficiency of your program. You must

write all the code yourself, and should not use any external library routines, except those

that are considered standard. The usual input/output and other unavoidable routines are

exempted.

Follow these procedures while submitting this assignment:

The assignment should be submitted online via moodle strictly as follows:

• All your scripts MUST contain your name and student ID.

• Use gzip or Winzip to bundle your work into an archive which uses your student ID

as the file name. (STRICTLY AVOID UPLOADING .rar ARCHIVES!)

– Your archive should extract to a directory which is your student ID.

– This directory should contain a subdirectory for each of the four questions, named

as: q1/, q2/, q3/ and q4/.

– Your corresponding scripts and work should be tucked within those subdirectories.

Note: If you have scripts that are common to multiple questions, such as your

suffix tree construction, you may include the script in the parent directory, or

copy it into the relevant subdirectories.

• Submit your zipped file electronically via Moodle.

Academic integrity, plagiarism and collusion

Monash University is committed to upholding high standards of honesty and academic

integrity. As a Monash student your responsibilities include developing the knowl-

edge and skills to avoid plagiarism and collusion. Read carefully the material available

at https://www.monash.edu/students/academic/policies/academic-integrity to understand

your responsibilities. As per FIT policy, all submissions will be scanned via MOSS.

1

Assignment Questions

1. (3 marks) Recall that a spanning tree of a graph G(V,E) is a subgraph T consisting of

all the vertices in V and some subset of edges E ′ ⊂ E such that T is a tree. That is, a

spanning tree is a collection of edges that form a tree and connect all the vertices in V .

A spanning tree in a weighted graph is called a weighted spanning tree and a weighted

spanning tree of minimum total possible weight is called a minimum spanning tree.

Given a weighted undirected graph G(V,E), your task is to write a program that uses

Kruskal’s algorithm (see notes from FIT2004) to find a minimum weight spanning tree in

G. You may assume that G is connected.

Strictly follow the following specification to address this task:

Program name: kruskals.py

Arguments to your program: The total number of vertices |V | (the size of G’s vertex

set) as a positive integer, and a plain text file. Every line in the text file contains

single edge with weight w connecting vertex u to vertex v in G represented by 3

integers in the following format:

u v w

The integers u and v are integers in the range [0 . . . |V | − 1]. Each of the integers in

the line are separated by a single space.

Command line usage of your script:

kruskals.py <|V|>

Do not hard-code the filename in your program.

Output file name: output kruskals.txt

Output format: The output file should contain:

• The total weight (as an integer) of a minimum spanning tree in G on the first

line.

• The edges of the minimum weight spanning found by your program. There

should be one edge per line, (starting from the second line) in the same format

as the input edge file.

Example: In the example below the minimum weight spanning tree (shown in red) has

weight 1 + 4 + 6 + 2 + 1 + 2 = 16. In this case the usage of your program would be:

python kruskals.py 7 G.txt

2

Where G.txt would contain:

0 1 5

1 2 4

2 3 2

3 4 10

4 5 6

5 0 1

0 6 8

1 6 2

2 6 1

3 6 3

4 6 7

5 6 4

Finally, the output of your program in this case would be a file output kruskals.txt

containing the weight of the minimum spanning tree (16) on the first line, followed

by the edges contained in the tree:

16

0 5 1

2 6 1

2 3 2

1 6 2

5 6 4

4 5 6

3

Questions 2 and 3 must be addressed using a suffix tree. There are 6 marks assigned

to suffix tree construction and these are included in the 8 marks available for question

2. That is for question 2, 6/8 marks are dedicated to suffix tree construction while the

remaining 2 are allocated to your use of the suffix tree and the output of your program.

As always, marking will be based on the efficiency of your suffix tree construction, and

those of the tasks below.

2. (8 marks) Given a string str[0 . . . n− 1], write a program that constructs its suffix tree,

and using that suffix tree, outputs the suffix array of the string. Note suffix arrays were

covered in FIT2004.

Strictly follow the following specification to address this task:

Program name: suffix array.py

Argument to your program: An input file containing str[0 . . . n − 1]. It is safe to

assume that:

• str consists of lower case English characters, i.e. ASCII characters with values

in the range [97 . . . 122].

• There are no line breaks in the input file, and that all characters str[0 . . . n− 1]

are lexicographically larger than the terminal character, $, which you will need

to append to str[0 . . . n− 1] after reading it from the file.

Command line usage of your script:

suffix array.py

Do not hard-code the filename in your program.

Output file name: output suffix array.txt

• Output format: The output file should contain the start indices of all the suffixes

in str[0 . . . n−1]$ in the order that they appear in the corresponding suffix array.

Each line of the file should contain a single suffix index as shown in the example

below.

Example: If str[0 . . . 10]$ = mississippi$ then the output would be:

11

10

7

4

1

0

9

8

6

3

5

2

4

3. (3 marks) For strings S1[0 . . . n− 1] and S2[0 . . .m− 1], define the values L(i, j) for any

0 ≤ i ≤ n − 1 and 0 ≤ j ≤ m − 1, as the longest prefix common to the suffixes starting

at position i in S1 and position j in S2.

For a given pair of input strings S1[0 . . . n− 1] and S2[0 . . .m− 1] and a list of (i, j) pairs

your task is to use a suffix tree to compute the L(i, j) value for each (i, j) pair in the list.

Strictly follow the following specification to address this task:

Program name: lcp.py

Arguments to your program:

(a) An input file containing S1[0 . . . n− 1].

(b) An input file containing S2[0 . . .m− 1].

(c) An input file containing a list of (i, j) pairs, one per line in the format:

i j

where 0 ≤ i ≤ n− 1 and 0 ≤ j ≤ m− 1.

It is safe to assume that:

• S1 and S2 consist of lower case English characters, i.e. ASCII characters with

values in the range [97 . . . 122].

• There are no line breaks in the files containing S1 and S2.

• Each line of the (i, j) pairs file contains a single pair where each index is sepa-

rated by a single whitespace (see example below).

Command line usage of your script:

lcp.py

Do not hard-code the filename in your program.

Output file name: output lcp.txt

• Each line should contain of a single pair of i and j indices followed by the corre-

sponding L(i, j) value, with each value being separated by a single whitespace

e.g. in the following format:

i j L(i,j)

Example: If S1[0 . . . 9] = abcdacbdab, S2[0 . . . 7] = dacbdabc and the input (i, j) pairs

file contained:

3 0

4 2

0 5

then the output should be:

3 0 7

4 2 0

0 5 3

5

4. (6 marks)

To give your fingers a break from coding this question will focus on the amortised analysis

of a Fibonacci heap.

Strictly follow the following specification to address this task:

File name: fibonacci.pdf

Submission instrcutions:

Your pdf file should contain your solutions to parts a-j below. Clearly indicate

which question each section in your solution refers to and be careful to include all

the necessary working. You may type your solutions or write them by hand and scan

them into a pdf file. Please note that if you choose to submit hand written solutions

it is your responsibility to ensure that your hand writing is legible. If your marker

cannot read your work you will not receive marks for it!

Once you have collected your solutions into a pdf file (named appropriately) simply

place it inside of your q4 subdirectory.

6

Preliminaries

Recall that the goal of any amortised analysis is to provide an upper bound on the cost

of any sequence of operations that might be performed on a given data structure. That

is, if we denote the true, or actual cost of some sequence of operations {op1, op2, . . . , opn}

as TC({op1, op2, . . . , opn}) then we desire some costing scheme that always ensures that

the amortised cost of this sequence (AC({op1, op2, . . . , opn})) is such that,

AC({op1, op2, . . . , opn}) ≥ TC({op1, op2, . . . , opn}). (1)

It is important to stress that this must be true for any sequence of operations not just

one specific sequence!

At this point you are likely already familiar with one costing scheme known as the ag-

gregate method where we simply assign AC({op1, op2, . . . , opn}) to be the cost (or some

upper bound on it) of the worst case sequence. We then distribute this work evenly

amongst the constituent operations to define the amortised cost of each operation oi -

denoted aci - as,

aci =

AC({op1, op2, . . . , opn})

n

. (2)

However, the amortised cost of the sequence need not be distributed evenly amongst the

operations in the sequence.

In the potential method we instead define the amortised cost of an operation oi to be,

aci = tci + Φ(Di)− Φ(Di−1), (3)

where tci is the true, or the actual cost of operation oi, Di is the state of the data

structure after operation oi has been completed, and Φ is known as a potential function.

The potential function simply maps the state of the data structure Di to a real number

Φ(Di), which is referred to as the potential associated with Di.

Using our newly defined notation and noting that the amortised cost of a sequence of

operations is simply the sum of the amortised cost of each individual operation in the

sequence we obtain,

AC({op1, op2, . . . , opn}) =

n∑

i=1

aci =

n∑

i=1

tci + Φ(Dn)− Φ(D0) (4)

(a) (0.5 marks) Use equation 3 to derive the right-hand-side of equation 4.

Since TC({op1, op2, . . . , opn}) =

∑n

i=1 tci we require Φ(Dn) ≥ Φ(D0) in equation 4 so

that the amortised cost of the sequence always upper bounds its true cost. Moreover, it is

common to define a potential function such that Φ(D0) = 0 and since in practice we don’t

always know how many operations will be in our sequence we also require Φ(Di) ≥ Φ(D0)

for all i. Thus, if we can show that Φ(Di) ≥ 0 for all i, we guarantee that the amortised

cost will always upper bound the true cost of any sequence.

7

Fibonacci heaps

To this point everything has been a little abstract, so let’s try to intuit what we have so

far and begin applying it to a Fibonacci heap. Examining equation 3,

aci = tci + Φ(Di)− Φ(Di−1),

we can see that the amortised cost for operation oi can be more or less than the true

cost. This means that the potential function Φ acts as a kind of credit and debit account

for our data structure. If the change in potential ∆Φ = Φ(Di)− Φ(Di−1) is positive this

amounts to overestimating the cost of the operation, which increases the potential and

corresponds to making a credit to our account. Conversely if ∆Φ < 0 then our potential

decreases as we have underestimated the cost of the operation, which corresponds to

making a debit to our account. Since initially Φ(D0) = 0 and we want Φ(Di) ≥ 0 for

all i, we essentially start with an empty account that we want to keep out of debit by

ensuring that we overestimate at least as much as we underestimate. This ensures that

our amortised cost always upper bounds the true cost of the sequence. With this you

should now have the necessary background knowledge required to analyse a Fibonacci

heap which will be the focus of the remainder of the assignment.

Let’s begin by considering a restricted version of a Fibonacci heap that only supports the

operations:

• Merge1

• Insert

• Find min

• Extract min

The reason for the omission of decrease key and delete from this list will become clear

later. To analyse the amortised complexity of these operations let’s define the potential

of a restricted Fibonacci heap H to be,

Φ(H) = T (H), (5)

where T (H) is the number of nodes in the root list of H. If we were to use this potential

to derive the amortised cost of find min we’d proceed as follows.

First we need to find the true cost of the operation, which is clearly O(1) since the

minimum element in the heap can be accessed directly via Hmin. In addition, since this

operation does not alter the number of nodes in the root list of H we have,

Φ(Di)− Φ(Di−1) = T (H)− T (H) = 0,

and so by equation 3 the amortised cost of find min is given by,

aci = tci + Φ(Di)− Φ(Di−1)

= O(1) + 0

= O(1).

In this case we see that the amortised cost for find min is actually equal to the true cost

of the operation.

1To analyse merge using our potential method we’d need to consider the potential of two separate heaps

H1 and H2 initially. To do so we simply define the potential of a collection of heaps to be the sum of their

individual potentials.

8

(b) (0.5 marks) Use the potential function given in equation 5 to derive the amortised

cost of insert.

Now that we’ve seen some examples of the potential method let’s quickly revisit equation

3,

aci = tci + Φ(Di)− Φ(Di−1).

If we were to overestimate the cost of operation oi by 3 units of potential then our

current interpretation would imply that those 3 units of potential are worth 3 units of

work. We can then use this potential to compensate for 3 units of work the next time

we underestimate the cost of an operation. However, we are free to scale the units of

the potential so that a single unit corresponds to any constant amount of work. In other

words, equation 3 should really be written as,

aci = tci +m [Φ(Di)− Φ(Di−1)] , (6)

where m is a positive real constant that we’ve implicitly assumed to be equal to 1 up

until this point.

(c) (1 mark) Show that the amortised cost of extract min is O(Dmax(N)), where N is

the number of nodes in H and Dmax(N) denotes the maximum degree of a node in

H.

Hint: Start by showing the true cost is O(T (H) +Dmax(N)) and then show that you

can scale the units of potential to leave O(Dmax(N)) for the amortised cost.

(d) (0.5 marks) Argue that for our restricted heap Dmax(N) ≤ blog2(N)c.

Now that we’ve analysed the operations of our restricted heap (you can convince yourself

that the amortised cost of merge is O(1)) let’s reintroduce decrease key.

The reason we initially omitted this operation from our list was that it complicates the

analysis slightly. For instance, the bound derived in part (f) is no longer valid, but we can

still show that the amortised cost of extract min is O(log(N)) even when decrease keys

are allowed.

To do so we need to show that Dmax(N) is still O(log(N)). This amounts to showing

that in the worst case the size of a given tree in H is still given by a function that is

exponential in the degree of the tree, so let’s determine how small our trees can get. Let’s

define a maximally decreased tree of degree k to be a tree - of degree k - in a Fibonacci

heap that has lost the maximum number of nodes from its subtrees due to decrease key

operations. Put another way, a maximally decreased tree is one from which we can’t

remove any more nodes via decrease keys without also decreasing the degree of the root.

For instance, the maximally decreased trees of degree 0, 1, 2 and 3 contain 1, 2, 3 and 5

nodes respectively, as shown in figure 1.

Figure 1: Maximally decreased trees of degree 0, 1, 2 and 3. The marked - denoted by the

shading - nodes have lost one child and the numbers represent the degree of each node rather

than the key of the node.

9

(e) (0.5 marks) How many nodes are in a maximally decreased tree of degree k?

Hint: Begin by simply drawing out maximally decreased trees of increasing degree

(you might find the representation used in figure 1 helpful). Now count the number

of nodes in each of these trees, can you spot a pattern? It may help to recall that the

Fibonacci sequence is defined as,

F0 = 0, F1 = 1 and Fn = Fn−1 + Fn−2 for n > 1,

and the start of the sequence is shown below.

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10

0 1 1 2 3 5 8 13 21 34 55

(f) (1.25 mark) Prove - using the principle of mathematical induction - that the expres-

sion you derived for the size of a maximally decreased tree in the previous part is

correct.

Hint: Think about how you can construct a maximally decreased tree of degree k

from maximally decreased trees of smaller degree.

At this point you should have an expression for the number of nodes in a maximally

decreased tree of degree k. By definition we know that this tree contains the fewest nodes

of any tree of degree k in our heap. Therefore, in general a tree of degree k rooted at r

in our heap must contain at least this many nodes i.e.,

size(r) ≥ g(k), (7)

where size(r) is the number of nodes in the tree and g(k) is the number nodes in a

maximally decreased tree of degree k that you found in part (e).

(g) (0.5 marks) Using equation 7 and the fact that,

Fk+2 ≥ φk, (8)

for all integers k ≥ 0, where φ = 1+

√

5

2

is the golden ratio, show that Dmax(N) =

O(log(N)) even when decrease key operations are allowed.

The result in part (g) proves that even when decrease key operations are allowed the

amortised complexity of extract min is still O(Dmax(N)) = O(log(N)).

Finally let’s conclude by deriving the amortised cost of decrease key.

(h) (0.5 marks) Using the potential given in equation 5, derive the amortised cost of a

decrease key operation. Is this what you’d expect?

Hint: Assume that you perform c ≥ 0 cascading cuts during the operation and

consider the true and amortised cost in this case.

Currently our potential is simply storing credits during decrease key that are used during

the extract min to offset the fact that we are adding more nodes to our root list. However,

we aren’t using any of our potential to compensate for the fact that marking nodes also

produces extra work in the form of cascading cuts in future decrease keys. To resolve this

let’s ‘back charge’ this work to the decrease keys that marked the nodes in the first place.

10

That is, we want to modify our potential so that we account for this work (make a credit)

every time we mark a node.

Let’s consider the potential,

Φ = T (H) + αM(H), (9)

where α is a positive constant and M(H) denotes the number of marked nodes in H. Now

every time we mark a node our potential increases by α units, but what value should we

choose for α?

(i) (0.5 marks) Determine the smallest integral value of α for which the potential in

equation 9 yields an O(1) amortised cost for decrease key.

(j) (0.25 marks) Explain why this value of α intuitively makes sense.

-=o0o=-

END

-=o0o=-

11

- 留学生代写
- Python代写
- Java代写
- c/c++代写
- 数据库代写
- 算法代写
- 机器学习代写
- 数据挖掘代写
- 数据分析代写
- Android代写
- html代写
- 计算机网络代写
- 操作系统代写
- 计算机体系结构代写
- R代写
- 数学代写
- 金融作业代写
- 微观经济学代写
- 会计代写
- 统计代写
- 生物代写
- 物理代写
- 机械代写
- Assignment代写
- sql数据库代写
- analysis代写
- Haskell代写
- Linux代写
- Shell代写
- Diode Ideality Factor代写
- 宏观经济学代写
- 经济代写
- 计量经济代写
- math代写
- 金融统计代写
- 经济统计代写
- 概率论代写
- 代数代写
- 工程作业代写
- Databases代写
- 逻辑代写
- JavaScript代写
- Matlab代写
- Unity代写
- BigDate大数据代写
- 汇编代写
- stat代写
- scala代写
- OpenGL代写
- CS代写
- 程序代写
- 简答代写
- Excel代写
- Logisim代写
- 代码代写
- 手写题代写
- 电子工程代写
- 判断代写
- 论文代写
- stata代写
- witness代写
- statscloud代写
- 证明代写
- 非欧几何代写
- 理论代写
- http代写
- MySQL代写
- PHP代写
- 计算代写
- 考试代写
- 博弈论代写
- 英语代写
- essay代写
- 不限代写
- lingo代写
- 线性代数代写
- 文本处理代写
- 商科代写
- visual studio代写
- 光谱分析代写
- report代写
- GCP代写
- 无代写
- 电力系统代写
- refinitiv eikon代写
- 运筹学代写
- simulink代写
- 单片机代写
- GAMS代写
- 人力资源代写
- 报告代写
- SQLAlchemy代写
- Stufio代写
- sklearn代写
- 计算机架构代写
- 贝叶斯代写
- 以太坊代写
- 计算证明代写
- prolog代写
- 交互设计代写
- mips代写
- css代写
- 云计算代写
- dafny代写
- quiz考试代写
- js代写
- 密码学代写
- ml代写
- 水利工程基础代写
- 经济管理代写
- Rmarkdown代写
- 电路代写
- 质量管理画图代写
- sas代写
- 金融数学代写
- processing代写
- 预测分析代写
- 机械力学代写
- vhdl代写
- solidworks代写
- 不涉及代写
- 计算分析代写
- Netlogo代写
- openbugs代写
- 土木代写
- 国际金融专题代写
- 离散数学代写
- openssl代写
- 化学材料代写
- eview代写
- nlp代写
- Assembly language代写
- gproms代写
- studio代写
- robot analyse代写
- pytorch代写
- 证明题代写
- latex代写
- coq代写
- 市场营销论文代写
- 人力资论文代写
- weka代写
- 英文代写
- Minitab代写
- 航空代写
- webots代写
- Advanced Management Accounting代写
- Lunix代写
- 云基础代写
- 有限状态过程代写
- aws代写
- AI代写
- 图灵机代写
- Sociology代写
- 分析代写
- 经济开发代写
- Data代写
- jupyter代写
- 通信考试代写
- 网络安全代写
- 固体力学代写
- spss代写
- 无编程代写
- react代写
- Ocaml代写
- 期货期权代写
- Scheme代写
- 数学统计代写
- 信息安全代写
- Bloomberg代写
- 残疾与创新设计代写
- 历史代写
- 理论题代写
- cpu代写
- 计量代写
- Xpress-IVE代写
- 微积分代写
- 材料学代写
- 代写
- 会计信息系统代写
- 凸优化代写
- 投资代写
- F#代写
- C#代写
- arm代写
- 伪代码代写
- 白话代写
- IC集成电路代写
- reasoning代写
- agents代写
- 精算代写
- opencl代写
- Perl代写
- 图像处理代写
- 工程电磁场代写
- 时间序列代写
- 数据结构算法代写
- 网络基础代写
- 画图代写
- Marie代写
- ASP代写
- EViews代写
- Interval Temporal Logic代写
- ccgarch代写
- rmgarch代写
- jmp代写
- 选择填空代写
- mathematics代写
- winbugs代写
- maya代写
- Directx代写
- PPT代写
- 可视化代写
- 工程材料代写
- 环境代写
- abaqus代写
- 投资组合代写
- 选择题代写
- openmp.c代写
- cuda.cu代写
- 传感器基础代写
- 区块链比特币代写
- 土壤固结代写
- 电气代写
- 电子设计代写
- 主观题代写
- 金融微积代写
- ajax代写
- Risk theory代写
- tcp代写
- tableau代写
- mylab代写
- research paper代写
- 手写代写
- 管理代写
- paper代写
- 毕设代写
- 衍生品代写
- 学术论文代写
- 计算画图代写
- SPIM汇编代写
- 演讲稿代写
- 金融实证代写
- 环境化学代写
- 通信代写
- 股权市场代写
- 计算机逻辑代写
- Microsoft Visio代写
- 业务流程管理代写
- Spark代写
- USYD代写
- 数值分析代写
- 有限元代写
- 抽代代写
- 不限定代写
- IOS代写
- scikit-learn代写
- ts angular代写
- sml代写
- 管理决策分析代写
- vba代写
- 墨大代写
- erlang代写
- Azure代写
- 粒子物理代写
- 编译器代写
- socket代写
- 商业分析代写
- 财务报表分析代写
- Machine Learning代写
- 国际贸易代写
- code代写
- 流体力学代写
- 辅导代写
- 设计代写
- marketing代写
- web代写
- 计算机代写
- verilog代写
- 心理学代写
- 线性回归代写
- 高级数据分析代写
- clingo代写
- Mplab代写
- coventorware代写
- creo代写
- nosql代写
- 供应链代写
- uml代写
- 数字业务技术代写
- 数字业务管理代写
- 结构分析代写
- tf-idf代写
- 地理代写
- financial modeling代写
- quantlib代写
- 电力电子元件代写
- atenda 2D代写
- 宏观代写
- 媒体代写
- 政治代写
- 化学代写
- 随机过程代写
- self attension算法代写
- arm assembly代写
- wireshark代写
- openCV代写
- Uncertainty Quantificatio代写
- prolong代写
- IPYthon代写
- Digital system design 代写
- julia代写
- Advanced Geotechnical Engineering代写
- 回答问题代写
- junit代写
- solidty代写
- maple代写
- 光电技术代写
- 网页代写
- 网络分析代写
- ENVI代写
- gimp代写
- sfml代写
- 社会学代写
- simulationX solidwork代写
- unity 3D代写
- ansys代写
- react native代写
- Alloy代写
- Applied Matrix代写
- JMP PRO代写
- 微观代写
- 人类健康代写
- 市场代写
- proposal代写
- 软件代写
- 信息检索代写
- 商法代写
- 信号代写
- pycharm代写
- 金融风险管理代写
- 数据可视化代写
- fashion代写
- 加拿大代写
- 经济学代写
- Behavioural Finance代写
- cytoscape代写
- 推荐代写
- 金融经济代写
- optimization代写
- alteryxy代写
- tabluea代写
- sas viya代写
- ads代写
- 实时系统代写
- 药剂学代写
- os代写
- Mathematica代写
- Xcode代写
- Swift代写
- rattle代写
- 人工智能代写
- 流体代写
- 结构力学代写
- Communications代写
- 动物学代写
- 问答代写
- MiKTEX代写
- 图论代写
- 数据科学代写
- 计算机安全代写
- 日本历史代写
- gis代写
- rs代写
- 语言代写
- 电学代写
- flutter代写
- drat代写
- 澳洲代写
- 医药代写
- ox代写
- 营销代写
- pddl代写
- 工程项目代写
- archi代写
- Propositional Logic代写
- 国际财务管理代写
- 高宏代写
- 模型代写
- 润色代写
- 营养学论文代写
- 热力学代写
- Acct代写
- Data Synthesis代写