Design and Analysis of Algorithms
Design and Analysis of Algorithms COT 5405
University of Central Florida
Popular in Course
Popular in Engineering and Tech
This 4 page Class Notes was uploaded by Lamont Block on Thursday October 22, 2015. The Class Notes belongs to COT 5405 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 15 views. For similar materials see /class/227693/cot-5405-university-of-central-florida in Engineering and Tech at University of Central Florida.
Reviews for Design and Analysis of Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/22/15
Design amp Analysis of Algorithms COT 5405 Instructor Dr Arup Guha NoteTakers Zeeshan Furqan Amit Kejriwal Date 091603 Three different levels 21 1 High level description eg ofO steps labeled 1 7 u provides a general outline 2 Detailed but not formal intermediate e g pseudo code with some details 3 Formal specifying input alphabets tape alphabets states etc deals with implementation Subset sum problem is there a subset that adds up to sum A solution can be given if there is one by enumerating all possible subsets Non decidable Problems These are the problems that have no solution 1 Halting Problem input TM M input X for M 2 Acceptance Problem input TM M input X for M The goal of halting problem is to decide whether M halts when run on M The goal of Acceptance problem is to decide whether M accepts X Both the problems are Turing recognizable Non Deterministic Turing Machine NDTM Class NP set of problems that can be solved on a NDTM in polynomial time They can also be defined as the class who verify the acceptance of the machine with certi cate in polynomial time Class P problems that can be solved in polynomial time by a standard Turing machine Halting Problem Given a TMM and a string w is we L lI In other words is input string w which is feed to the Turing machine M is recognizable by the machine or not This problem is unsolvable problem and known as halting problem The halting problem can be proved as follows A M w M is a TM and M accepts w Proof We will prove halting problem using the principle of contradiction Assume A is decidable Suppose that H is a decider for A On input Mw H halts and accepts if M accepts w H halts and rejects if M fails to accept w HMw accepts if M accepts w rejects ifM does not accept w Let s construct a Turing machine D with H as a subroutine D calls H to determine what M does when the input to M is its own description Once D has determined this information it does the opposite The following is the description of D D on Input M 1 Run H on input MM 2 Output the opposite of what H outputs DM accepts if M does not accept M rejects ifM accepts M And if D is run with its own descriptor D as input then DD accepts if D does not accept D rejects ifD accepts D No matter what D does it is forced to do the opposite thus neither TM D nor TM H can exist 1 H accepts Mw exactly when M accepts w 2 D rejects M exactly when M accepts M 3 D rejects D exactly when D accepts D Diagonalization proof In the tables shown below all the TM s are listed down the row M1 M2 and all their description across the columns M1 M2 The entries tell whether the machine in a given row accepts the input in a given column The entry is accept if the machine accepts the input but is blank if it rejects or loops on that input Entry accept accepts In the following table the entries are result of running H on inputs corresponding to the above tables So if M3 does not accept input M2 the entry for row M3 and column M2 is reject because H rejects input M3 M2 The table below is obtained by adding D to the above table By our assumptions H and D both are TM Therefore it much occur on the list M1 M2 of all TMs D computes the opposite of diagonal entries The contradiction occurs at the point of 2 where the entry must be opposite of itself M1 M2 M3 M4 D M1 accept reject accept reject accept M2 accept accept accept accept accept M3 reject reject reject reject reject M4 accept accept reject reject accept D reject reject accept accept 2 Contradiction occurs at 2 The above proof can be related to the program distributed in the class A is the program and function machined symbolizes the D TM in the proof shown above Functions machinel and machine2 symbolize M1 and M2 respectively Function machined returns false if halting function returns true and returns true if halting function returns false Function halting is equivalent to the decider H