Description
1. Define a language L which corresponds to each decision problem stated in parts (a) through
(c).
Example: Given integers x, y, determine if x is divisible by y.
L = {hx, yi : x, y ∈ Z and x mod y ≡ 0}
The language L consists of all encodings of pairs of integers hx, yi such that x mod y ≡ 0, i.e.,
y divides x. (You do not need to explain how the encoding works. In this case, we could say
it is a string in {−, 0, 1, #}
∗ where x, y are written in binary, negated with ‘−’, and separated
by a #, e.g., h−5, 3i = −101#11.)
(a) Given an integer x, is x a perfect cube?
Solution:
(b) Given an integer m, is m odd?
Solution:
(c) Given natural numbers p and q, do p and q share a common prime factor?
Solution:
2. Draw a DFA which decides the following languages:
(a) {x ∈ {0, 1}
∗
| x has an even number of 0s and the last character of x is 1}.
(b) b(aaa)
∗
b.
Reminder: the alphabet is {a, b}.
(c) Let x ∈ {0, 1}
∗
. In this problem, we will consider the reversal of x as defined in lecture
slides, where we read least significant digits first.
Formally, if we have read n bits so far, let x = x0x1 . . . xn. The unsigned numeric value
of x is notated as hxi∗, where hx0x1 . . . xni∗ := Pn
i=0 2
ixi
. (Note the reversed binary
representation, where the leftmost bit x0 corresponds to 2
0
, x1 corresponds to 2
1
, etc.)
We would read this bitstring from left to right.
Devise a DFA that decides
L = {x ∈ {0, 1}
∗
| hxi∗ mod 3 = 0}.
Note:
• The empty string has value zero. hεi∗ = 0.
• There may be extra zeros. For example, h11010000i∗ = h1101i∗ = 11.
• You may represent your DFA as a table of state transitions or as a diagram,
whichever is easier.
Hint: Try to characterize hx0x1 . . . xki∗ in terms of the previously read value hx0x1 . . . xk−1i∗.
Consider the value of (2
k mod 3) for even and odd k.
Solution:
3. What language does the following DFA decide? Give your answer as a regular expression.
Solution:
4. A robot is walking on a 2D-grid. It receives instructions from the set Σ = {N, W, S, E}, which
indicate a move 1 step to the north, west, south and east, respectively. The robot starts at
the origin, and receives an instruction string x ∈ Σ
∗
.
The robot wants to know whether it
is at the origin after executing x. Prove that if the robot uses a DFA, it cannot answer this
question.
Solution:
5. Define the “fractional knapsack problem” as a variant of the original knapsack problem which
allows one to take any partial amount of an item (that is, for an item of value v and weight
w, one may select some t ∈ [0, 1] and add t· v and t· w as weight and value to the knapsack.)
(a) For this fractional variant, describe a greedy algorithm which returns the maximum
value given the capacity of the knapsack. Explain (1-2 sentences should be sufficient)
why your algorithm gives the optimal value.
(b) Prove that the optimal value for the fractional knapsack is at least as large as that for
the original 0-1 knapsack problem (for the same weights, values, and knapsack capacity).
(c) Prove that the greedy approach you proposed in part (a) may not find an optimal solution
to the original 0-1 knapsack problem.
Solution:
