EECS 376: Foundations of Computer Science Homework 5

EECS 376: Foundations of Computer Science Homework 5 We may grade a subset of the assigned questions, to be determined after the deadline, so that we can provide better feedback on the graded questions. Unless otherwise stated, each question requires sufficient justification to convince the reader of the correctness of your answer. For bonus questions, we will not provide any insight during office hours or Piazza, and we do not guarantee anything about the difficulty of these questions. We strongly encourage you to typeset your solutions in LATEX. If you collaborated with someone, you must state their name(s). You must write your own solution for all problems and may not look at any other student’s write-up. 0. If applicable, state the name(s) and uniqname(s) of your collaborator(s). Solution: 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 University of Michigan, Fall 2023 Homework 5 Due 8:00pm, Oct 4 (accepted until 9:59 pm, no credit after) (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 University of Michigan, Fall 2023 Homework 5 Due 8:00pm, Oct 4 (accepted until 9:59 pm, no credit after) 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