SOLVED EECS 376 Homework 5

  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}. 1 EECS 376: Foundations of Computer Science   (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: 2 EECS 376: Foundations of Computer Science   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: 3