Data structure | Algorithm作业 – Module Title:Algorithms and Data Structures II c UNIVERSITY OF LEEDS

Module Title:Algorithms and Data Structures II c UNIVERSITY OF LEEDS

Data structure | Algorithm作业 – 该题目是一个常规的Algorithm的练习题目代写, 涵盖了Data structure/Algorithm等方面

School of Computing Semester 2 mock exam 2021/

Assessment Information

• There are2 hoursto complete the examination.
• There are 7 pages to this examination.
• Answerall 6questions.
• The number in brackets[ ]indicates the marks available for each question or part question.
• You are reminded of the need for clear presentation in your answers.
• The total number of marks for this examination paper is 96.
• You are allowed to use annotated materials.

Question 1

This question deals with minimum spanning trees in connected edge-weighted graphs.

(a) Consider the four weighted undirected graphs illustrated below. Calculate and provide the number of (distinct)
minimum spanning trees for each of the following weighted graphs.
c

b d

a e

1

2 3

4

5

6

7

8

Number:

c

b d

a e

1

1 1

1

1

2

2

2

Number:

c

b d

a e

2

1 1

2

1

2

1

2

Number:

c

b d

a e

1

1 1

1

1

1

1

1

Number:

[8 marks]

(b) Find a minimum spanning tree in the graph below and state the total weight of its edges.

1

2 3 4 5

6 7 1 2 3 4 5 6

7 1 2 3

4 5 6 7 1 2 3 4 5

6 7 8 9

[8 marks]

[Question 1 Total: 16 marks]

Question 2

This question is about the CYK parsing Algorithm for context-free grammars, named after its inventors, John Cocke, Daniel Younger and Tadao Kasami. The pseudocode is given below.

begin
fori 1 tondo
V(i, i){AV|(Axi)P}
forb 1 ton 1 do
fori 1 tonbdo
ki+b;V(i, k);
forjitok 1 do
V(i, k);
for(ABC)Pdo
ifBV(i, j)andCV(j+ 1, k)then V(i, k)V(i, k){A};

ifSV(1, n)thenacceptx 1 x 2... xnelserejectx 1 x 2... xn;

(a) Answer the following questions about the variant of the CYK algorithm that only decides whether a string
can be generated by a grammar.

(i) What are the input and the output?
(ii) Which sets are computed and how?
(iii) What is the asymptotic running time?
[4 marks]

(b) Execute your algorithm onababbato decide whether this string can be generated by the grammarG =
V, T, P, Swith variablesV ={A, B, S}, terminals T = {a,b}start symbolS and productions P as
follows:

SAB|BA AAS|a BBS|b

Show your work in a table. [8 marks]

(c) Give all parse trees of the stringababba. [8 marks]

[Question 2 Total: 20 marks]

Question 3

Analyse the running time of the following divide and conquer algorithms. For each algorithm, establish a recurrence for the running time and derive a tight asymptotic bound. In each case the input is an integern 0 and the function returns a non-negative integer.

(a) Fibonacci-numbers via the definition.

functionfibonacci(n)
ifn 1 then
returnn
else
return(fibonacci(n1) +fibonacci(n2))
[5 marks]

(b) Fibonacci-numbers via pairs.

functionfibonacci(n)
(x, y)pair(n);
returnx;
functionpair(n)
ifn= 0then
return(0,1)
else
(x, y)pair(n1);
return(y, x+y)
[5 marks]

(c) Powers of 2 via the definition.

functionpower(n)
ifn= 0then return 1 else return(2power(n1));
[5 marks]

(d) Powers of 2 via halving.

functionpower(n)
ifn= 0then
return 1
else
ppower(bn/ 2 c);
ifnis oddthen return(2pp)else return(pp);
[5 marks]

[Question 3 Total: 20 marks]

Question 4

This question deals with binomial trees and binomial heaps.

(a) Define binomial trees recursively. [4 marks]

(b) How many nodes does a binomial tree contain? Prove this using your definition above. [6 marks]

(c) Define a binomial heap. [4 marks]

(d) Give an example of an abstract data type that can be implemented using binomial heaps. Which functions
does this abstract data type support? What are their asymptotic worst case running times if implemented by
binomial heaps? [6 marks]

[Question 4 Total: 20 marks]

Question 5

This question is about one of the data structures for dictionaries introduced in the lecture, namely, hash tables.

In the items (a) and (b), you are asked to insert the following numbers into the given hash tables using the provided hash functions and strategies for avoiding collisions.

(a) Insert: 37
collision strategy: double hashingwithoutBrents improvement
Hash functions:
h 1 (k) =kmod 11
h 2 (k) = (kmod 5) + 1

Hash table:

0 123 4 5 6 7 8 910

(^4426611830) [3 marks] (b) Insert: 81 collision strategy: double hashingwith Brents improvement If an already present element is moved, then clearly mark its new position. Hash functions: h 1 (k) =kmod 11 h 2 (k) = (kmod 5) + 1 Hash table: 0 123 4 5 6 7 8 910 (^4426171830) [3 marks] (c) Consider the following hash strategies. Say whether you think the strategy is good or whether it could lead to problems. Argue why you think this is the case. I) multiplication method table sizem= 2^8 factorA= 1/ 3 II) multiplication method table sizem= 2^10 factorA=

2 / 2

III) division method
table sizem= 8^5
h(k) = (k+ 3) modm
IV) division method with double hashing
table sizem= 31
h 1 (k) =kmod 31
h 2 (k) =kmod 6
[4 marks]

[Question 5 Total: 10 marks]

Question 6

This question is about another Data structure for dictionaries introduced in the lecture, namely, AVL trees.

(a) Consider the following AVL-tree:

50

25

11

7

34

75

60 91

85 99

Partition all number between 0 and 100 that are not yet in the above AVL-tree into intervals such that two
numbers in the same interval would be added to the same position in the AVL-tree. Fill the following table by
providing for each such interval: (1) the position in the above tree where those numbers would be inserted,
(2) the type of reorganisation that has to be applied after a number in such an interval would be inserted.
The first row in the table is already correctly filled to provide an example.

intervalposition type of reorganisation

nonesimple rotationdouble rotation

06 left of 7 X

[10 marks]

[Question 6 Total: 10 marks]

[Grand Total: 96 marks]

Page 7 of 7 End