×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

by: Lamont Block

15

0

4

# Design and Analysis of Algorithms COT 5405

Marketplace > University of Central Florida > Engineering and Tech > COT 5405 > Design and Analysis of Algorithms
Lamont Block
University of Central Florida
GPA 3.74

Staff

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
4
WORDS
KARMA
25 ?

## 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

×

×

### What is Karma?

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

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

×

×

### BOOM! Enjoy Your Free Notes!

×

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

Bentley McCaw University of Florida

#### "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!"

Allison Fischer University of Alabama

#### "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!"

Steve Martinelli UC Los Angeles

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### 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