H2023 Algo Flashcards
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)
A
They are always equal
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
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): [ ]
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.
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
suffixTrieMatch algorithm
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.
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.
No codeword can be a preix of another.
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
A
Optimal solution
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
B
Convert the values by making them smaller
Check the picture for how it was done in the assignment :O
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.
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!
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!
What is the main idea used by the algorithm compared to other algorithms we have seen (short answer).for the Pattern Matching problem.
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.
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.
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
Christofidesβ algorithm is another approximation algorithm for the TSP-problem. Give the main steps in this algorithm.
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
Formulate the linear program (LP) relaxation of the ILP in a)
Replace: Xi Ξ΅ {0,1} with 0 β€ π₯π β€ 1 in the ILP formulation
How is the optimal solution to the LP problem related to the optimal solution to the ILP problem. Give a short explanation
Formulate the dual version of the LP problem above.
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
