0/32 Questions Answered
Q1 Greedy Algorithms
This question is about greedy algorithms.
Q1.1 Number of Minimum Spanning Trees (1)
Calculate and provide the number of (distinct) minimum spanning
trees for the weighted undirected graph illustrated below.
Enter your answer here
Save Answer
Q1.2 Number of Minimum Spanning Trees (2)
Calculate and provide the number of (distinct) minimum spanning trees for the weighted undirected graph illustrated below.
Enter your answer here
Save Answer
Q1.3 Number of Minimum Spanning Trees (3) Calculate and provide the number of (distinct) minimum spanning
trees for the weighted undirected graph illustrated below.
Enter your answer here
Save Answer
Q1.4 k-Minimum Spanning Tree (1)
Consider the so-called k-Minimum Spanning Tree (k-MST)
problem, which is defined as follows.
An instance of the k-MST problem is given by a connected undirected graph G = (V , E) with edge weights w : E → Q and a natural number k > 2. The question is to find a tree with exactly k nodes that is a subgraph of G and minimises the weight among all such trees. Informally, k-MST is the variant of the minimum spanning tree problem, where instead of a spanning tree one wants to find a tree with exactly k nodes.
What would be the result if we apply Prim’s, respectively Kruskal’s, algorithm to the problem by stopping both algorithms after k − 1 edges have been added? In the following we refer to these versions of Prim’s and Kruskal’s algorithm as the modified algorithm of Prime or Kruskal, respectively.
Consider the following graph.
For which of the following edge weights, assigned to the graph above, does the modified algorithm of Kruskal provide a wrong result assuming that k = 4. Tick all correct answers.
w(1,2)=w(2,3)=w(3,4)=1 and w(4,5)=2
w(1,2)=1, w(2,3)=1, w(3,4)=2, w(4,5)=1
w(1,2)=1, w(2,3)=2, w(3,4)=3, w(4,5)=4
w(1,2)=1, w(2,3)=3, w(3,4)=2, w(4,5)=4
w(1,2)=1, w(2,3)=2, w(3,4)=4, w(4,5)=3
Here, w(a, b) = d means that the edge between vertices a and b has weight d.
Save Answer
Q1.5 k-Minimum Spanning Tree (2)
Consider now the modified algorithm of Prim as defined in Question 1.4 and the following graph.
For which of the following edge weights, assigned to the graph above, and starting vertex s does the modified algorithm of Prime provide a wrong result assuming that k = 4. Tick all correct answers.
s=1, w(1,2)=1, w(2,3)=2, w(3,4)=4, w(4,5)=3, w(1,5)=8
s=5, w(1,2)=1, w(2,3)=2, w(3,4)=4, w(4,5)=3, w(1,5)=8
s=1, w(1,2)=3, w(2,3)=4, w(3,4)=2, w(4,5)=1, w(1,5)=10
s=1, w(1,2)=1, w(2,3)=2, w(3,4)=3, w(4,5)=4, w(1,5)=5
s=1, w(1,2)=3, w(2,3)=3, w(3,4)=1, w(4,5)=1, w(1,5)=4
Here, w(a, b) = d means that the edge between vertices a and b has weight d and s = a means that the start vertex for the modified algorithm of Prim is set to the vertex a.
Save Answer
Q2 CYK algorithm
The CYK algorithm recognises strings in the language generated by a fixed context-free grammar G = (Σ, V , P , S) in Chomsky normal form (CNF). That is, a given string s = x1 x2 ⋯ xn , where xi ∈ Σ for i = 1, 2, … , n, is accepted if it can be generated by G and rejected otherwise. In this question you consider context- free grammars of other forms. Similar to the CNF these other forms are defined by the type of productions allowed. Your task is to modify the CYK algorithm such that it recognises the languages generated by a fixed grammar of such a form. That is, you should not transform the grammar into one in CNF. Instead you should modify the way certain subsets of V are computed.
For each of the three forms state
which subsets of V are computed,
how these subsets are computed (give the recurrence), how the algorithm accepts or rejects its input string, and the asymptotic running time of the algorithm.
Q2.1 CYK variant
The productions are of the form
A→aforA∈V anda∈Σ
A → BC for A, B, C ∈ V
A → BCD for A, B, C, D ∈ V
Save Answer
Q2.2 CYK variant
The productions are of the form
A→aforA∈V anda∈Σ A→aBforA,B∈V anda∈Σ
Save Answer
Q2.3 CYK variant
The productions are of the form
A→aforA∈V anda∈Σ A→aBforA,B∈V anda∈Σ A → Ba for A, B ∈ V and a ∈ Σ
Enter your answer here
Enter your answer here
Save Answer
Q2.4 original CYK: k=i+1
Execute the original CYK algorithm on aababb to decide whether this string can be generated by the grammar G = (V ,T,P,S) with variables V = {A, B, S}, terminals T = {a, b} start symbol S and productions P as follows
S → AB
A → AS ∣ a B → SB ∣ b
Note that if a and b are considered as opening and closing bracket, respectively, then G generates all nonempty strings in T ∗ that are correct bracketings.
Work out a table. Give the values V (i, k) as plain text for the diagonals as specified. The set {S, A, B} should be given as {S,A,B}, the empty set as {}. Separate the sets by a single blank symbol only.
k=i+1
Enter your answer here
Save Answer
Q2.5 original CYK: k=i+2
k=i+2
Enter your answer here
Enter your answer here
Q2.6 original CYK: k=i +3
k=i+3
Enter your answer here
Save Answer
Q2.7 original CYK: k=i+4 k=i+4
Enter your answer here
Save Answer
Q2.8 original CYK: k=i+5 k=i+5
Enter your answer here
Can the string aababb be generated by G? yes
no
Save Answer
Q2.9 first parse tree
Save Answer
Give all parse trees of the string aababb by inserted brackets. Sort the strings encoding the parse trees into ascending order, where
a < b < (<). The first parse tree is (leave empty if there is no parse tree):
Enter your answer here
Save Answer
Q2.10 second parse tree
The first parse tree is (leave empty if there is no second parse tree):
Enter your answer here
Save Answer
Q2.11 remaining parse trees
The third, fourth and fifth parse trees are (leave empty if no more
parse trees exist):
Enter your answer here
Enter your answer here
Enter your answer here
Save Answer
Q3 Hash tables
This question is about hash tables.
Q3.1 Double Hashing without Brent's improvement
Insert the key 26 in the hash table given below. Use double hashing without Brent's improvement to avoid collisions and the following two hash functions:
h1(k) = k mod 11 h2(k) = (k mod 8) + 1 Hash table:
Fill the following fields with all the probing positions for 26 in the order in which the probing is applied. For instance, if the first probing position is 2, the second probing position is 5, and the third probing position is 7, then fill the first field with 2, the second field with 5, the third field with 7 and leave the remaining fields empty.
Enter your answer here Enter your answer here Enter your answer here Enter your answer here
Enter your answer here
Save Answer
Q3.2 Double Hashing with Brent's improvement
Insert the key 26 in the hash table given below. Use double hashing wit Brent's improvement to avoid collisions and the following two hash functions:
h1(k) = k mod 11 h2(k) = (k mod 5) + 1 Hash table:
Fill the following fields with all the probing positions for 26 in order in which the probing is applied. For instance, if the first probing position is 2, the second probing position is 5, and the third probing position is 7, then fill the first field with 2, the second field with 5, the third field with 7 and leave the remaining fields empty.
Enter your answer here
Enter your answer here
Enter your answer here
Enter your answer here
Enter your answer here
Is there another key apart from 26 that is moved to a different position? If so provide the key; if not leave the following field empty:
If you put a key above, to which position is the key moved to? If you did not put a key above leave the following field empty:
Enter your answer here
Save Answer
Q3.3 Hash strategies I Consider the following hash strategy.
multiplication method
table size m = 210
factor A = π 2
Which of the following statements is correct? A should be a power of 2.
m should be prime.
The strategy has no problems.
m should be a power of 2. Save Answer
Q3.4 Hash strategies II Consider the following hash strategy.
multiplication method table size m = 13 factor A = 2
Which of the following statements is correct?
Enter your answer here
A should be prime number.
m should be a power of 2.
The strategy has no problems. A should be an irrational number.
Save Answer
Q3.5 Hash strategies III Consider the following hash strategy.
division method
table size m = 25 h(k)=(k+1) modm
Which of the following statements is correct? The strategy has no problems.
A should be a prime number.
The hash function is not correct.
A should be a power of 7. Save Answer
Q3.6 Hash strategies IV Consider the following hash strategy.
division method with double hashing table size m = 27
h1(k) = k mod 23
h2(k) = (k mod 6) + 1
Which of the following statements is correct?
m should be a power of 5.
h2(k) does not always cycle through all available places. The strategy has no problems.
h1(k) does not use all available spaces.
Save Answer
Q4 AVL trees
Consider the following AVL-tree:
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.
For each such interval you need to specify: (1) The interval, e.g., 0-6.
(2) The position in the AVL-tree, where every number in the interval is inserted. For instance, if all numbers in the interval are inserted to the left of 7, write L7, if they are inserted to the right of 7, write R7.
(3) The type of reorganization that has to be applied after one (any) number in the interval would be inserted in the AVL-tree. There are three possible types of reorganization:
(A) For no reorganization write N. (B) For a simple rotation write SR. (C) For a double rotation write DR.
You should consider the intervals in their natural order. Use each of the following sub-questions to specify all of the above information for one interval (starting from the second interval because the first
interval is given as an example). For instance, the first interval contains all numbers between 0 and 6, and those will be inserted to the left of 7 using a simple rotation. Therefore, you would need to write: 0-6 L7 SR for the first interval.
Q4.1 2nd interval: Enter your answer here
Save Answer
Q4.2 3rd interval: Enter your answer here
Save Answer
Q4.3 4th interval: Enter your answer here
Save Answer
Q4.4 5th interval Enter your answer here
Save Answer
Q4.5 6th interval
Enter your answer here
Save Answer
Q4.6 7th interval Enter your answer here
Save Answer
Q4.7 8th interval: Enter your answer here
Save Answer
Q4.8 9th interval: Enter your answer here
Save Answer
Q4.9 10th interval:
Enter your answer here
Save Answer
Q4.10 11th interval:
Enter your answer here
Save Answer
Save All Answers Submit & View Submission