CS/ECE 374: Algorithms & Models of Computation, Spring 2019
Final Monday, May 6, 13:30–16:30
⇐ Please print
Which exam room to go to based on your discussion section.
Copyright By PowCoder代写 加微信 powcoder
AYA 9am Yipu AYB 10am Xilin AYC 11am Xilin AYD noon YE 1pm YJ 1pm Shant
AYF 2pm Konstantinos AYG 3pm YE 3pm Jiaming
AYH 4pm YK 2pm Shant BYA 9am Zhongyi BYC 1pm YB 10am Zhongyi BYF 4pm Jiaming BYD 2pm Shu
• Don’t panic!
• Please print your name, print your NetID, and circle your discussion section in the boxes above.
• There are seven questions – you should answer all of them.
• If you brought anything except your writing implements, your double-sided handwritten (in the
original) 81⁄2″ × 11″ cheat sheet, and your university ID, please put it away for the duration of the exam. In particular, please turn off and put away all medically unnecessary electronic devices.
– Submit your cheat sheet together with your exam. We will not return or scan the cheat sheets, so photocopy them before the exam if you want a copy.
– If you are NOT using a cheat sheet, please indicate so in large friendly letters on this page.
• Please read all the questions before starting to answer them. Please ask for clarification if any question is unclear.
• This exam lasts 175 minutes. The clock started when you got the exam.
• If you run out of space for an answer, feel free to use the blank pages at the back of this booklet,
but please tell us where to look.
• As usual, answering any (sub)problem with “I don’t know” (and nothing else) is worth 25% partial
credit. Correct, complete, but slightly sub-optimal solutions are always worth more than 25%. Solutions that are exponentially (or dramatically) slower than the expected solution would get no points at all. A blank answer is not the same as “I don’t know”.
• Total IDK points for the whole exam would not exceed 10.
• Give complete solutions, not examples. Declare all your variables. If you don’t know the answer
admit it and use IDK. Write short concise answers.
• Style counts. Please use the backs of the pages or the blank pages at the end for scratch work,
so that your actual answers are clear.
• Please return all paper with your answer booklet: your question sheet, your cheat sheet, and all
scratch paper.
• Good luck!
NETID: NAME:
(10 pts.) Short questions and hopefully short answers. No justification is required for your answers.
1.A. (5 pts.) Give an asymptotically tight bound for the following recurrence.
T (n) = T (ni) + O(n) for n > 200, and T (n) = 1 for 1 ≤ n ≤ 200, i=1
wheren1 +n2 +···n10 =n,andn/20≤ni ≤(9/10)nforalli.
1.B. (5 pts.) Describe (in detail) a DFA for the language below. Label the states and/or briefly
explain their meaning.
{w ∈ {0, 1}∗ | w has at least three 1’s and has odd length} .
(15 pts.) I have a question about NFAs.
2.A. (5 pts.) Recall that an NFA N is specified as (Q, δ, Σ, s, F ) where Q is a finite set of states, Σ is a finite alphabet, s ∈ Q is the start state, F ⊆ Q is the set of accepting states, and δ : Q × (Σ ∪ {ε}) → 2Q is the transition function. Recall that δ∗ extends δ to strings: δ∗(q, w) is the set of states reachable in N from state q on input string w.
In the NFA shown in the figure below what is δ∗(S,0)?
ε B 1ε G 1 0
2.B. (10 pts.) Given an arbitrary NFA N = (Q,Σ,δ,s,F) and an arbitrary state q ∈ Q and an arbitrary string w ∈ Σ∗ of length t, describe an efficient algorithm, as fast as possible, that computes δ∗(q,w). Express the running time of your algorithm in terms of n,m,t, where n = |Q|, m = p∈Q b∈Σ∪{ε} |δ(p, b)|, and t = |w|. Note that faster solutions can earn more points. You can assume that |Σ| = O(1).
You do not need to prove the correctness of your algorithm (no credit for incorrect algorithm). (Hint: Construct the appropriate graph, and do the appropriate things to it.)
(15 pts.) MST when there are few weights.
Let G = (V,E) be a connected undirected graph with n vertices and m edges, and with pos-
itive edge weights. Here, the edge weights are taken from a small set of k possible weights 2
NETID: NAME:
{w1, w2, . . . , wk} (for simplicity, assume that w1 < w2 < . . . < wk). Describe a linear time algorithm to compute the MST of G for the case that k is a constant. (For partial credit, you can solve the case k = 2.)
Provide a short explanation of why your algorithm is correct (no need for a formal proof).
4 (15 pts.) Shuffle it.
Let w ∈ Σ∗ be a string. A sequence of strings u1,u2,...,uh, where each ui ∈ Σ∗, is a valid split of w ⇐⇒ w = u1u2 ...uh (i.e., w is the concatenation of u1,u2,...,uh). Given a valid split u1, u2, . . . , uh of w, its price is p(w) = hi=1 |ui|2. For example, for the string INTRODUCTION, thesplitINT·RODUC·TIONhasprice32 +52 +42 =50.
Given two languages T1,T2 ⊆ Σ∗ a string w is a shuffle iff there is a valid split u1,u2,...,uh of w such that u2i−1 ∈ T1 and u2i ∈ T2, for all i (for simplicity, assume that ε ∈/ T1 and ε ∈/ T2). You are given a subroutine isInT(x, i) which outputs whether the input string x is in Ti or not, for i ∈ {1, 2}. To evaluate the running time of your solution you can assume that each call to isInT takes constant time.
Describe an efficient algorithm, as fast as possible, that given a string w = w1w2 . . . wn, of length n, and access to T1 and T2 via isInT, outputs the minimum l2 price of a shuffle if one exists. Your algorithm should output ∞ if there is no valid shuffle.
You will get partial credit for a correct, but slow (but still efficient), algorithm. An exponential time or incorrect algorithm would get no points at all.
What is the running time of your algorithm?
5 (15 pts.) Dumb and dumbbell.
For k > 1, a (k, k)-dumbbell is a graph formed by two disjoint complete graphs (cliques), each one on k vertices, plus an edge connecting the two (i.e., its a graph with 2k vertices). See figure for a (7, 7)-dumbbell. The DUMB problem is the following: given an undirected graph G = (V, E) and an integer k, does G contain a (k, k)-dumbbell as a subgraph? Prove that DUMB is NP-Complete.
6 (15 pts.) You are the decider.
Prove (via reduction) that the following language is undecidable.
L = {⟨M⟩ | M is a Turing machine that accepts at least 374 strings}. (You can not use Rice’s Theorem in solving this problem.)
7 (15 pts.) Yellow street needs bits.
There are n customers living on yellow street in Shampoo-banana. Yellow street is perfectly
straight, going from south by southeast to north by northwest. The ith customers lives in distance 3
NETID: NAME:
si meters from the beginning of the street (i.e., you are given n numbers: 0 ≤ s1 < s2 < · · · < sn). A new internet provider Bits4You is planning to connect all of these customers together using wireless network. A base station, which can be placed anywhere along yellow street, can serve all the customers in distance r from it.
The input is s1,s2,...,sn,r. Describe an efficient algorithm, as fast as possible, that computes the smallest number of base stations that can serve all the n customers. Namely, every one of the n customers must be in distance ≤ r from some base station that your algorithm decided to build. Incorrect algorithms will earn few, if any points. (Your algorithm output is just the number of base stations – there is no need to output their locations.)
Prove the correctness of your algorithm. What is the running time of your algorithm?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com