### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Computability&Algorithms CS 6505

GPA 3.81

### View Full Document

## 166

## 0

## Popular in Course

## Popular in ComputerScienence

This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 6505 at Georgia Institute of Technology - Main Campus taught by H. Venkateswaran in Fall. Since its upload, it has received 166 views. For similar materials see /class/234043/cs-6505-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.

## Reviews for Computability&Algorithms

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/02/15

H to DJ Computability Algorithms and Complexity Fall 2010Test 2 practice questions You can bring one sheet with notes on both sides to the test You can citeuse without re proving a Theorems Lemmas and Examples either covered in the class or covered in chapters 1 through 5 of the text b Problems and exercises from Chapters 1 and 2 of the text and b Home work problems from this course You may not use any other source Please state your assumptions Please write neat legible precise and succinct answers Do not use Rice s theorem for showing undecidability results unless explicitly stated The ATM language is the following ATM M w l M is a Turing machine that accepts w For a language L the notation L denotes the complement of L Thus the complement of ATM is denoted by ATM The language ALLCFG is the following ALLCFG 7 LG 7 2 Let M 622 P6q9 qa qr be a DTM and w be an input to M Let A Q U P A string of the form Cl02 Cm is an accepting computation history of M on w if a C is a valid con guration of M on w b 01 is the start con guration of M on w c Cm is an accepting con guration of M on w and d for all 1 g i 77171 M moves on w from Ci to CH1 Let NOT 7 ACHMM be the set of all strings over A that are not accepting computation histories of M on w In class we showed that NOT 7 ACHMM is a context free language and there is an algorithm to construct a context free grammar G for NOT 7 ACHMM The PCP problem is the following t1 t2 tk 3 2122 2m such that tiltiz H751 bilbi2 him where 251752 tkb1 b2 bk are strings over some alphabet E Exercises 55 57 from the Sipser text Problem 530 a from the Sipser text Answer if the following statement is TRUEFALSE proving your claim If A Sm B and B is a regular language then A is also a regular language Solution False Give a reduction from a non regular language such as 0 1 n 2 0 to a regular language 4 U a 1 Show that a language L is Turing decidable if and only if L is mapping reducible to wwR l w E 2 Solution For one direction if L is mapping reducible to a context free language then L must be decidable because of the following two facts a if a language L is mapping reducible to a decidable language L then L is decidable and b every context free language is decidable For the other direction let L be Turing decidable and let M be a decider that accepts L Let B wwR l w E 2 The language B is decidable On input w the reduction machine computes fw as follows run M on w and output the following a If M rejects w output fw 011 E F b If M accepts w output fw 1001 E B That is w E LM iff fw E B Let HTM Mw M halts on w and HTM Mw M does not halt on w Let finite M l LM is nite Give a reduction from HTM to finite Hint The empty set 0 is nite Solution On input M w a reduction machine constructs the following TM M M on input z a Run M on w and accept z iff M halts on w LM is 0 that is nite if M does not halt on w and it is 2 if M halts on w Show that there is a reduction from ATM to the language below G l G is a context 7 free grammar and G is NOT empty Solution ALLCFG LG 2 Therefore ALchG 7 We gave a reduction in class from ATM to ALLCFG from which the conclusion follows Consider the following two problems about Turing machines a P1 LM has at least 100 strings b P2 LM is accepted by a Turing machine that does not halt in an even number of steps a Show that one of the above two properties is non trivial and the other is trivial A problem P is nontrivial if it holds for some but not all Turing machines Solution The language P2 is trivial and the language P1 is non trivial Clearly the language L1 2 a Turing machine which always accepts has more than 100 strings and the language L2 j a Turing machine which always rejects has less than 100 strings Hence L1 6 P1 whereas L2 P1 We show that P2 is trivial that is it contains all possible Turing machines Let M be a Turing machine Make a new Turing machine M as follows M makes an initial dummy step and after that works as M At each step of M M executes an additional dummy step in addition to Ms step And M accepts iff M accepts Thus M takes 2k 1 steps for k steps of machine M Since M recognizes the same language as M but always halts in an odd number of steps the Turing machine lt M gt also belongs to property P2 00 to O H b For the nontrivial problem show that the membership of a Turing machine M in it depends only on the language of M That is for any Turing machines M1 M2 where LM1 LM2 we have M1 is in the problem iff M2 is in the problem Therefore we can conclude from Rice s theorem that the nontrivial problem is undecidable Solution If LM1 LM2 then lLM1l lLM2l less than 100 strings and both will either contain 2 100 strings or Use Rice s theorem to prove the undecidability of the following language NOTALLTM l M is a deterministic Turing machine and LM 7 2 Solution In order to apply Rice s Theorem we need to prove two things about NOTALLTM o NOTALLTM is non trivial There is a machine M with LM 2 and there is a machine M with LM 7 2 o NOTALLTM is a property of the language recognized by the machine That is if LM1 LM2 then either both M1 and M2 are in NOTALLTM or both of them are not This follows since if LM1 2 then LM2 2 so both of them are not in NOTALLTM and vice versa Now we can apply Rice s Theorem which says that any property that satisfying the above two properties is undecidable The Constrained PCP problem is the PCP problem in which each tile can be used in a match at most once That is the Constrained PCP problem is the following If t t l 3 DISTINCT indices 1122 Wm such that 25125 25 12112 mm where t1 t2 tkb1 b2 bk are strings over some alphabet 2 Is the Constrained PCP problem decidable Prove your answer Solution Let m denote the number of tiles used to get a match Clearly 1 S m g k since you cannot use a tile more than once For 1 g m S k for all m subsets S of 12 if the permutations correspond to a match There are Cn k here 001 k is the binomial coef cient 7 choose k subsets of size k and for each such subset there are kl permutations hence the total number of possibilities is 220 kl Cn Clearly all these possibilities can be enumerated and checked by a Turing machine in a nite amount of time k for all permutations of the elements of S check to see Problem 521 page 212 of the Sipser text Let M 622 P 6q9 qmqr be a DTM Let A Q U P A string ofthe form 01C392 Cm is an accepting computation history of M if a C is a valid con guration of M b Cl is a valid start con guration of M for input over 2 that is Cl qsw and w E 2 c Cm is an accepting con guration of M and d for all 1 g i g m 71 M moves from C to 011 In class we considered ACHMM and NOT7 ACHMM for a speci c input w In the following we con sider ACHM accepting computation histories of M on all input strings and NOT 7 ACHM non accepting computation histories of M on all input strings Computability Algorithms and Complexity Fall 2010 Test 4 practice questions NOTES o If necessary make reasonable assumptions But please make sure that you state your assumptions Please write neat legible precise and succinct answers 0 You can bring one sheet with notes on both sides to the test You can use without reproving a theorems lemmas and examples covered in class and b home work problems from this course You may not use any other source 1 Show that 4 is a principal 4 th root of unity modulo 17 2 We used a property called the optimal substructure property in deriving dynamic programming algorithms the compo nents of an optimal solution are optimal solutions to the corresponding subproblems For example consider the shortest path problem Given a directed graph G E with positive edge weights and two nodes 8 and t nd a shortest path from s to t Let P be a shortest path from node I to node y Then for any two nodes uv on P the subpath from u to v on P is a shortest path from u to 1 Show that the optimal substructure property does not hold for the following problem Given a directed graph G V E and two nodes 8 and t nd a simple directed path from s to t consisting of the most edges Solution See CLRS section 153 CA3 Let a and b be two nite length bit strings The concatenation of a and b is the string obtained by placing the string 12 after the string a Example The concatenation of 011 with 1011 is 0111011 Let L1 and L2 be a collection of nite length bit strings The concatenation of L1 and L2 is the collection obtained by concatenating every string in L1 with every string in L2 Example Let L1 10001 and L2 001101 The concatenation L1 L2 1000 101 10101 00100 0011 001101 Let the cost of concatenating L1 and L2 to produce the set L1 L2 be Ll gtlt Lg The resulting language has Ll gtlt Lg strings allowing duplicate strings Consider the problem of computing the optimum cost C1 n of concatenating n nite sets of bit strings L1 L2 Ln using the concatenation of two nite languages as the primitive a Derive a recurrence for the optimum cost Cij of forming the concatenation L L1 L for the languages Li Li1 Lj b Use this to describe a dynamic programming algorithm to compute the optimum cost Cij for 1 S ij S n Solution Let Cij be the cost of concatenating the languages Li Li1 Lj ThenCli 0 for all 1 S i S n In general in an optimum sequence for the languages Li L if the split for the nal concatenation is at k the total cost of concatenating the j 7 i 1 languages is 0quot minis k CZk CHM 1L1 391Lklyj1there Lik is the length of the languages obtained by concatenating Li Lk Similarly Lkl is the length of the languages obtained by concatenating Lk1 Lj 4 Let X 1112 an be a sequence of symbols from a nite alphabet E A subsequence Z of length 10 of X is string zilziznzik for1 S i1 lt 239 lt lt ik S n Derive an 0n2 dynamic programming algorithm to nd the length of the longest palindromic subsequence of X A subsequence is palindromic if it reads the same from left to right and right to left Computability Algorithms and Complexity Fall 2010 Test 5 practice questions NOTES o If necessary make reasonable assumptions But please make sure that you state your assumptions Please write neat legible precise and succinct answers 0 You can bring one sheet with notes on both sides to the test You can use without re proving a theorems lemmas and examples covered in class and b home work problems from this course You may not use any other source H Let E s t c be a network in which there is also a positive capacity dv for each vertex The max ow problem for such networks is to nd a ow from s to t that satis es the additional constraint that the ow through a vertex does not exceed its capacity Show how to transform this problem into a standard max ow problem What is the running time of your transformation algorithm Solution Construct a network G as follows For each vertex u in G create in 6quot two vertices ul and ug with an edge between them with capacity For every edge vw in G create an edge 112101 in G with capacity cvw 7 Suppose the capacities in a network are multiplied by a constant d How does the value of the maximum ow change 9 Suppose all edges in a network have equal capacities Show how to compute the maximum ow in the network in time F Let a network G V E s t c and an integer valued maximum ow in G Suppose we increase by l the capacity of a speci c edge e E E Let G be the resulting network a Using the Max ow Mincut theorem show that the maximum ow value in G can increase at most by 1 Solution Use the max ow mincut theorem The cost of any cut 5 V 7 S can only increase by at most 1 Therefore the minimum cut can at most increase by 1 and hence the maximum ow can also increase by at most 1 b Based on this describe an On m algorithm to nd a maximum ow in G given as input a a network G b an integer valued maximum ow f in G and c an edge 6 whose capacity is increased by 1 Solution Use the given ow f to construct the residual graph Cf Let 6 uv In the residual network increase the residual capacity of u v by 1 Cf u v Cf u v 1 Check whether there is an augmenting path p in the new residual network If there is no such path then f itself is the maximum ow If there is such a p augment ow along p by l the minimum capacity on p must be 1 to get a maximum ow f 1 This takes On m time 5 Given as input a network G Ecs t with all capacities l and a cut 5 T describe a 0m2logn algorithm to decide if S T is a minimum 8 7 tcut in G Why does your algorithm run in the claimed time bound Find a maximum ow Takes 0m210gn using the scaling algorithm Find a minimum 8 7 tcut AB If the capacity of the cut A B is the same as the capacity of S T then S T is a minimum 8 7 tcut 533 Let A be a unittime algorithm that decides if an input bipartite graph has a perfect matching or not Using A give an Om n algorithm to construct a perfect matching in an input bipartite graph G V1 V2 E with V n and m if G has a perfect matching Solution Note that A answers the decision version it only tells us whether G has a perfect matching or not We are to use this as a subroutine to nd the perfect matching in G The following algorithm returns a perfect matching in G FINDPMG 0 pick an edge e u v in G 0 run AG u v to see if G with vertices u v removed has a perfect matching Computability Algorithms and Complexity Fall 2010 Test 3 practice questions NOTES o If necessary make reasonable assumptions But please make sure that you state your assumptions Please write neat legible precise and succinct answers 0 You can bring one sheet with notes on both sides to the test You can use without re proving a Theorems Lemmas and Examples either covered in the class or covered in chapters 1 to 5 and chapter 7 of the Sipser text and b Home work problems from this course You may not use any other source You can assume the following o The clique problem is the following Given an undirected graph G V E and a natural number k is there a subset V g V such that a lV l k and b for any uv E V uv E E The clique problem is ANDComplete o The vertex cover problem is the following Given an undirected graph G V E with n vertices and an integer l lt k g n is there a vertex cover a subset V g V such that every edge in E is incident on at least one vertex in V of size S k The vertexcover problem is ANDComplete o The 16 coloiing problem is the following Given an undirected graph G V E and an integer k 2 3 is there a way to label the vertices from 1 k such that adjacent vertices do not get the same value The 16 coloring problem is ANDComplete o A Hamiltonian cycle in an undirected graph G V E is a cycle that goes through all the vertices exactly once The Hamiltonian Cycle problem is to decide if an input graph has a Hamiltonian cycle The Hamiltonian cycle problem is ANDComplete The subset sum problem is the following Given a collection of n1 positive integers a1 a2 an M is there a subset I C 12n such that e Iai M The subset sum problem is NpComplete o The unary subset sum problem is de ned as the subset problem except that the input numbers are in unary The unary subset sum problem is in 73 The cnfsat problem is the following Given a Boolean formula in conjunctive normal form is there a truth assignment to its variables that make the formula evaluate to true The cnfsat problem is ANDComplete o The 3cnfsat problem is the following Given a Boolean formula in conjunctive normal form in which each clause has exactly three literals in it is there a truth assignment to its variables that make the formula evaluate to true The 3cnfsat problem is ANDComplete 0 Evaluating a Boolean formula given a truth assignment to its variables is in 73 1 E0 3 u 01 The class CON is the complement of the languages in N73 The class N73 CON is the class of languages L such that L 6 N73 and L E COMP Is the following statement TRUE or FALSE Justify your answer 73 Q N73 COMP Show that 73 N73 if there is a polynomial time algorithm to transform an input formula in conjunctive normal form into an equivalent formula in disjunctive normal form Solution 0 Suppose there is a polytime algorithm M to convert a CNF formula 45 into an equivalent DNF formula Since the machine itself takes polynomial time the new formula 1 must be of size at most where c gt 0 is the exponent in the running time of M If there is a polytime algorithm for deciding whether a DNF formula is satis able then we can apply it on 1 to decide whether it is satis able Since 45 and 1 are equivalent this will constitute a polytime algorithm for CNFSAT Since CNFSAT is an Npcomplete problem by the argument below we have that 73 N73 0 By a property of polytime mapping reducibility if a language A is reducible to a language B and B E 73 then A E 73 Therefore if an Npcomplete problem A E 73 then N73 73 since every language in N73 is reducible to A Finally we descibe a polytime algorithm for deciding DNF satis ability A DNF formula 1 consists of an or of and clauses and hence is satis able iff at least one of the clauses c is satis able Since each clause is an and7 of literals it can be satis ed iff all literals are assigned value true This is possible iff both I and x do not occur in the same clause Thus to check for satis ability we go through all the clauses c E 1 and output nol iff we nd a clause with complementary literals z and x Clearly this algorithm runs in polynomial time Show that 73 N73 if and only if unary subset sum problem is ANDComplete Let 73 N73 Here is a reduction from cnfsat CNFSAT to unary subset sum Since 73 N73 there is a polynomial time algorithm A for cnfsat Given a CNF Boolean formula F run the algorithm A on F If F is satis able then output unary numbers a1 a1 and if F is not satis able output two distinct unary numbers a1 a2 Also unary subset sum is in 73 and hence in N73 this shows that unary subset sum is ANDComplete Let unary subsetsum be NpComplete Then all problems in N73 are polynomial time mapping reducible to unary subset sum Since unary subset sum is in 73 all problems in N are in 73 The partition problem is the following Given a collection of n positive integers a1a2an is there a subset I C 12n such that e Iai Q Iai Give a polynomial time reduction from the subset sum problem to the partition problem Why is your reduction correct We give a reduction from the subset sum to the partition problem that operates in polynomial time Given an instance b1 b2 bn2 where bi 2 21 lt i lt n ai 7 M of the partition problem a1a2 anM of the subset sum problem we construct an instance B ai for 1 S i S nbn1 ElSiSnaiMandbn2 Problem 721 page 296 of the text Reduction from cnfsat Given a CNFSAT formula F output F 2 V 2 for some new variable 2 The set cover problem is the following INPUT A set U of n elements a collection 51 52 PROBLEM Is there a collection of at most k of these subsets whose union is equal to the set U Sm of subsets of U and an integer 1 g k lt m Give a polynomial time reduction from the vertex cover problem to the set cover problem Argue why your reduction is correct Let CV E be an instance of the vertex cover problem on n vertices We construct an instance of the set cover problem as follows a The universal set U E ie the edges e E E form the elements of U 7 9 b For each vertex 11 E V we make a set SD which consists of all edges incident on V 51 6 6 6 E and 6 1111 for some u 6 V 1 Thus lUl and we have n subsets Svlv E V Now we show the correctness of the reduction Let V E V be a vertex cover of size S k Then we show that the sets Svlv E V form a set cover of the same size Take any edge 6 E E Let 116 6 V be a vertex on which it is incident since V is a vertex cover such a vertex must exist Then 6 E Sve and hence UveV SD U lt Now let 511 512 19le S l S k be a set cover of size S k Then we show that the vertices V form a vertex cover of the same size 111112 11 For any edge 6 E V let 116 be the index of the set that contains 6 such a set must exist since it is a set cover Then by the de nition of these sets 6 is incident of 116 6 V and hence V forms a vertex cover The Hitting Set problem is the following INPUT A set A of n elements a collection C of subsets of A and an integer 1 S k S n PROBLEM Is there a subset A of A with lA l S k such that A contains at least one element from each subset in C Give a polynomial time reduction from the vertex cover problem to the Hitting Set problem Let A Solution Reduction from vertex cover V For each edge u 11 E E let C contain the subset 1111 consisting of the two endpoints of u 11 A Boolean formula over the variables X1 Xn is a tautology if it evaluates to true for all truth assignments for the variables a Given a conjunctivenormal form Boolean formula F give a polynomial time algorithm to decide if F is NOT a tautology b Given a conjunctive normal form Boolean formula F is there a polynomial time algorithm to decide if F is a tautology Why or Why not Solution a If F is a tautology each clause 5 E F should evaluate to true irrespective of the truth assignment This is possible only if at least one pair of complementary literals z and x appear together in each clause 0 For otherwise we could make all literals in this clause to be false and then c and hence F will not be true for the corresponding assignment For example 11 V 12 V 13 could be false if we assign all the 111213 to false while for 11 V zl V 12 would evaluate to true irrespective of the value of 11 Hence whether F is tautology could be formulated as the following problem in each clause 5 check whether a complementary pair I x appears The algorithm works as follows For each clause c in F if there is no pair x not x return FALSE there exists an assignment which makes c false return TRUE F is a tautology Note Compare this algorithm with that for deciding the satis ability of DNF formulas b The answer is yes since 73 is closed under complement

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.