H2023 Algo

Question 1

What is the relation between the number of prefixes and the number of suffixes in a textstring?

A
They are always equal

B
The number of prefixes may be smaller, but never larger than the number of suffixes

C
The number of prefixes may be larger, but never smaller than the number of suffixes

D
There is no relation (none of the ohters)

Answer 1

A
They are always equal

Question 2

Answer 2

G: n

Example:
The string is: “ABCD”

To create subsequences of length 𝑛 − 1 = 3, we remove exactly one character from the string:

Remove ‘A’: “BCD”
Remove ‘B’: “ACD”
Remove ‘C’: “ABD”
Remove ‘D’: “ABC”

Total subsequences of length 3:
4, which is equal to n = 4.

This demonstrates that there are 𝑛 subsequences of length 𝑛 - 1

Question 3

How many comparisons of characters will the Boyer-Moore algorithm do before it decides that the pattern P = “abb” is not in the text
T = “abcaccabc”?

Number of comparisons (integer): [ ]

Answer 3

The Boyer-Moore algorithm, comparisons are done right-to-left within the pattern P

3 comparisons

T = a(0) b(1) c(2) a(3) c(4) c(5) a(6) b(7) c(8)
P = a(0) b(1) b(2)

first comparison:
P[2] = ‘b’
T[2] = ‘c’
Mismatch, and we don’t have any c’s in our pattern, move P past c(2)

Second comparsion:
P[2] = ‘b’
T[5] = ‘c’
Mismatch, and we don’t have any c’s in our pattern, move P past c(5)

Third comparison:
P[2] = ‘b’
T[8] = ‘c’
Mismatch, and we don’t have any c’s in our pattern and we’re at the end of T.

Question 4

We want to support very many pattern matching queries on the same text. What is the most efficient algorithm?

suffixTrieMatch algorithm

Brute Force algorithm

Boyer Moore algorithm

Knuth-Morris-Pratt algorithm

Answer 4

suffixTrieMatch algorithm

Question 5

We use the Huffman algorithm to find an encoding for set of characters occurring in a string of length n. Example of an encoding of a character may be: “0110”. Decide if the following assertions are true or false.

Answer 5

The first is False.
We create a frequency table for each letter.
Combine the lowest frequent numbers first until you reach the end.
Example:
(a, 3), (b, 2), (c, 2), (d, 2), (e, 2).

Combine (b, 2) and (c, 2) -> (bc, 4).
Combine (d, 2) and (e, 2) -> (de, 4).
Combine (a, 3) and (bc, 4) -> (abc, 7)
Combine (abc, 7) and (de, 4) (abcde, 11)
Te most frequent character, a, is combined with (bc, 4) instead of being directly connected to the root. This means the code length depends on its position in the three, which may not be 1.

Second is true since we will combine (q, 1) and (s, 1) into (qs, 2), so they will always have the same lenght in their encoding.

Third is true since a frequency of 1 will always be at the bottom of the huffman tree.

Question 6

Answer 6

No codeword can be a preix of another.

Question 7

Answer 7

Question 8

When we have an optimization problem, ideally, we want to find the optimal solution in polynomial time and for any instance. An approximation algorithm relaxes on one of these requirements. Which?

A
Optimal solution

B
Polynomial time

C
For any instance

Answer 8

A
Optimal solution

Question 9

Answer 9

Question 10

How do we design a fully polynomial time approximation scheme (FPTAS) for the Knapsackproblem?

A
Convert the values by making them larger

B
Convert the values by making them smaller

C
Convert the sizes by making them larger

D
Convert the sizes by making them smaller

Answer 10

B
Convert the values by making them smaller

Check the picture for how it was done in the assignment :O

Question 11

Answer 11

If the best possible solution is worth 10 points, then a 1/2-approximation algorithm will guarantee finding a solution with an expected value of at least 5 points.

Question 12

Answer 12

First-fit = 5
Bin 1 = 0.5 + 0.4 = 0.9
Bin 2 = 0.2 + 0.3 + 0.2 = 0.7
Bin 3 = 0.4 + 0.4 = 0.8
Bin 4 = 0.5 = 0.5
Bin 5 = 0.8 = 0.8

First-Fit-Decreasing = 4
First reorder the numbers by max -> min
{0.8, 0.5, 0.5, 0.4, 0.4, 0.4, 0.3, 0.2, 0.2}

Bin 1 = 0.8 | 0.2 remaining | add 0.2 to bin 1 at the end!
Bin 2 = 0.5 + 0.5 = 1.0 | Full!
Bin 3 = 0.4 + 0.4 = 0.8 | 0.2 remaining
Bin 4 = 0.4 + 0.3 + 0.2 = 0.9 | 0.1 remaining

We are now left with only 0.2 which we can add to bin 1!

Question 13

Answer 13

Question 14

Answer 14

Algorithm for coloring a 3-colorable graph with 𝑂( 𝑛) colors
* While there exists a vertex in the graph with degree at least 𝑛
* Chose a vertex in the graph with degree at least 𝑛
* Pick 3 new colors.
* Color the vertex with one
* Use the 2-coloring algorithm to color its neighbors with the other two colors (possible since
the graph is 3-colorable)
* Remove these vertices from the graph
* Use algorithm that that colors a graph with (Δ + 1) colors to color the remaining vertices

10 vertices gives us sqr(10) = 3.16

Which means we only have 2 candiates
The rest only have 2 or 3 lines between them!

Question 15

What is the main idea used by the algorithm compared to other algorithms we have seen (short answer).for the Pattern Matching problem.

Answer 15

Preprocess the pattern P to compute a failure function f that indicates the proper shift of P. Based on the failure function the algorithm can reuse previously performed comparisons. Example: The yellow a in the example above.

Boyer-Moore always starts again at the back of the pattern when comparing.

Question 16

What is the running time of the Knuth-Morris-Pratt algorithm in O-notation. You can assume that the length of the string is n and the length of the pattern is m.

Explain / describe the idea.

Answer 16

Our textbook says 𝑂(𝑚 + 𝑛), but accept also 𝑂(𝑛) since it easy to modify the algorithm such the it answers “no” if P is longer than T (without computing the failure function).

Excluding the computation of the failure function, the running time is proportional to the number of iterations through the while-loop.
Let 𝑘 = 𝑖 − 𝑗. We have 𝑘 ≤ 𝑛. There are 3 cases in each iteration.
* If 𝑇[𝑖] = 𝑃[𝑗], both i and j increases by 1, so k remains unchanged.
* If 𝑇[𝑖] ≠ 𝑃[𝑗], and j > 0, then i does not change and k increases by at least 1 (since j decreases by at least 1).
* If 𝑇[𝑖] ≠ 𝑃[𝑗], and j = 0, both i and k increase by 1 (since j does not change).

In each iteration of the loop, either i or k increases by at least 1. This can happen at most 2n times. Hence KMP is 𝑂(𝑛).

Question 17

Formulate the Travelling Salesperson Problem (TSP). You can assume you have a graph with n vertices.

Answer 17

Want to find a tour of minimum cost that visits every vertex exactly once. A tour ends in in the same vertex that it starts.

Question 18

The Double Tree algorithm is an approximation algorithm for the TSP-problem. Give the main steps in this algorithm.

Answer 18

Double-tree algorithm
* Find MST
* Double all the edges in the tree (then all nodes will have even degree)
* Find Eulerian tour (exist when all nodes have even degree. Easy to find)
* Consider tour. Skip nodes that are already visited.
* Has 2 approximation and Triangle inequality holds!

Question 19

Run the Double Tree algorithm on a graph with the following minimum spanning tree. You can assume that distances between the vertices are the distances on the paper/screen. Show/explain intermediate steps.

Answer 19

After doubling the edges, we find an Eulerian tour. It is possible to start in any vertex, so let us start in 1. There are several Eulerian starting in 1.
An example:
1 3 4 2 4 5 4 6 4 3 1
To find an TSP tour vi skip already visited vertices and get:
1 3 4 2, 5, 6,1

Question 20

Christofides’ algorithm is another approximation algorithm for the TSP-problem. Give the main steps in this algorithm.

Answer 20

Vertices with odd degree are 1, 2, 5 and 6. There are 3 possible perfect matchings (1 can be matced with one of the three others and then the remaining is a pair). We see from the figure that the best matching is 1 & 2 and 5 & 6. Adding the edges (1, 2) and (5, 6) to the MST, all nodes have even degree and we can find an Eulerian tour.
For example:
1 3 4 6 5 4 2 1
TSP tour: 1 3 4 6 5 skip 2 1

• Triangle inequality holds!
• Has 1.5 approximation

Question 21

Answer 21

Question 22

Formulate the linear program (LP) relaxation of the ILP in a)

Answer 22

Replace: Xi ε {0,1} with 0 ≤ 𝑥𝑖 ≤ 1 in the ILP formulation

Question 23

How is the optimal solution to the LP problem related to the optimal solution to the ILP problem. Give a short explanation

Answer 23

Question 24

Formulate the dual version of the LP problem above.

Answer 24

LP
* n variables
* m constraints

Dual
* m variables
* n constraints

• Right hand sides in the LP’s constraints becomes coefficients in the Dual’s objective function
• Coefficients in the LP’s objective function becomes right hand sides in the Dual’s constraints

Question 25

How is a feasible (mulig) solution to the dual formulation related to the optimal solution to the LP problem.

Answer 25

A feasible solution to the dual formulation is at less or than equal to the optimal solution of the LP problem.