V2024 Algo Flashcards
Consider the Pattern Matching problem where we want to decide if a text of length contains a pattern of length .
What is the running time in the worst case for following algorithms?
We have the Huffman tree below (“o” is a node, not a letter)
o
/ \
o c
/ \
a b
Decode the following message: 00101001 [ ] write down just the letters without anything else
acbac
We have given two strings, Y and Z, and want to find the length their longest common subsequence. We use a dynamic programming approach using an array. We find the Z-string in the first row and the Y-string in the first column. We do not know the exact strings, but Z contains an ‘a’ at index j. We consider two alternative characters for Y at index i. The cells of the known entries are grey. See figure below.
The following is an instance of the Set cover problem. We have seen a greedy algorithm for the problem. What set is chosen first by this algorithm?
S = {1, 2, 3, 4, 5}
S1 = {1, 2, 5}, w1 = 1
S2 = {1, 3}, w2 = 2
S3 = {2, 3, 5}, w3 = 2
S4 = {3, 4}, w4 = 3
S5 = {4, 5}, w5 = 7
A = s1 is correct!
Steps:
Take the weight w and devide it with the amount of elements in each set.
S1 => 1/3 = 0.33
S2 => 2/2 ) = 1
S3 => 2 / 3 = 0.66
S4 => 3 / 2 = 1.5
S5 => 7 / 2 = 3.5
Below you find an adjacency matrix of a small graph which does NOT obey the triangle inequality.
Triangle Inequality Recap
The triangle inequality states that for any three nodes i, j, k:
d(i,j) ≤ d(i,k) + d(k,j)
d(a, d) = 7
via b:
d(a,d) <= d(ab) + d(b,d)
7 <= 4 + 2 => 7 <= 6 False!
via c:
d(a, d) <= (a, c) + (c, d)
7 <= 3 + 3 => 7 <= 6 False
C a & d do not obey the triangle inequality
We have a polynomial-time approximation scheme (PTAS) for a given minimization problem. That means we have a (1+ε)-approximation algorithm for the problem. What happens when we choose a larger ε with the running time and the quality of the solution.
We consider a maximization problem. What does it mean to have a randomized -approximation algorithm for the problem?
In the Knapsack Problem, we have a set of items I = {1, 2, . . . , n} where each item i has a value vi ≥ 0 and a size 0 ≤ si ≤ B where B is the size of the knapsack. In the dynamic programming algorithm a pair (t, w)
indicates that there exists a subset S of I where ∑iϵS si = t ≤ B and
∑iϵS vi = w
A pair 𝑡, 𝑤 dominates another pair (𝑡′, 𝑤′) if 𝑡 ≤ 𝑡′ and
𝑤 ≥ 𝑤′
That is why A dominates B on the last one!
3 <= 4 and 5 >= 4
We have a (very) small instance of the MAX SAT problem. Assign true/false to the variables x1, x2 x3 , and such
that the solution is optimal.
We have a MAX SAT problem where we have listed the first clauses. They include all clauses containing variables x1, x2 and x3. Assign true/false to the variables x1, x2 and x3 (in that order) using the derandomized algorithm we have seen in lectures / compulsory assignments.
Remember to go through the calculations putting
x1 = True and then x1 = False etc!
Example:
x1 = True
c1 = 1 * 1 = 1
c2 = 3(1-(1/2)^2) = 2.25
total = 3.25
x1 = False
c1 = 1(1 - (1/2)) = 1.5
c2 = 3 * 1 = 3
total = 4.5! WINNER!
Therefore x1 = False
What is the main idea behind Compressed tries?
Standard tries are space inefficient. This is solved by ensuring that each internal node has at least two children. We use substrings to label nodes in stead of single characters.
Give an example of a problem where tries are useful.
Dictionary and pattern matching (suffix trie)
i) What is a suffix trie?
ii) Construct a small example.
iii) Explain why and how it can be used in pattern matching.
i) A suffix trie is a trie containing all suffixes of a given string (except the empty string).
ii) in picture
iii) If a pattern is present in a string, it must be a start of a suffix of the string. Hence, if you find the pattern as a prefix of one of the strings in the suffixtrie you know the pattern is present in the string.
i) What is the preemtive version of the scheduling problem below?
ii) Give an algorithm to find an optimal solution on the preemptive version
iii) Show how the algorithm work on the instance in a)
i) In the preemptive version we do not need to complete a job before we start antother job.
ii) Can find an optimal solution to this problem via the shortest remaining processing time (SRPT) rule
while there are jobs left do
* If there are no released jobs, move time until next job is released
* Among released jobs that are not done, choose the one with shortest
remaining processing time
* Schedule it until it is completed or a new job is released
Job | 1 | 2 | 3 | 4 | 4 |
time| 0 - 2 | 2 - 3 | 3 - 4 | 4 - 5 | 5 - 8 |
i) Give an algorithm to find an approximate solution to the problem described in a)
ii) What order will this algorithm give for the instance in a?
Shortest
Remaining Processing Time (SRPT)
What is the approximation ratio of the algorithm in c)?
The algorithm is a 2-approximation algorithm
Formulate the corresponding Vertex Cover (nodedekke) problem as an integer linear program (ILP). You can write x1 and use <= and >=
Formulate the linear program (LP) relaxation of the ILP in
a)
Minimize
x1 + x2 + x3 + x4 + x5 + x6
x1 + x2 >= 1
x1 + x4 >= 1
x2 + x3 >= 1
x2 + x6 >= 1
x3 + x4 >= 1
x3 + x6 >= 1
x4 + x5 >= 1
x5 + x6 >= 1
xi in {0, 1}, for i in {1,2,3,4,5,6} (Alternatively: 1 <= i <= 6)
Answer: Replace “xi in {0, 1}” with “xi in [0,1]” in a)
Formulate the dual version of the LP problem below:
Minimize
x1 + x2 + x3 + x4 + x5 + x6
x1 + x2 >= 1
x1 + x4 >= 1
x2 + x3 >= 1
x2 + x6 >= 1
x3 + x4 >= 1
x3 + x6 >= 1
x4 + x5 >= 1
x5 + x6 >= 1
xi in [0,1], for i in {1,2,3,4,5,6}
