### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Algorithm Design ECS 122A

UCD

GPA 3.75

### View Full Document

## 156

## 0

## Popular in Course

## Popular in Engineering Computer Science

This 2 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 122A at University of California - Davis taught by Zhaojun Bai in Fall. Since its upload, it has received 156 views. For similar materials see /class/187716/ecs-122a-university-of-california-davis in Engineering Computer Science at University of California - Davis.

## Reviews for Algorithm Design

### 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: 09/08/15

ECS122A Handout June 2 2009 How to prove a problem is NP complete Example 1 The directed Hamilton cycle HC problem is known to be NP complete In the following we show that the directed HC problem is reducible to the undirected Hamilton cycle problem Therefore we conclude that the undirected HC problem is also NP complete PROOF Let G V E be a directed graph with n vertices G is transformed into the undirected graph G V E by the transform function T de ned as the following 1 E V 111112113 E V and 111112 112113 6 E and 1111 6 E A 113111 6 E Clearly T is polynomial time computable We now show that G has aHC ltgt G has aHC o gt Suppose that G has a directed HC 121122 vnv1 Then 1 2 3 1 2 3 1 2 3 1 U17U17U17U27U27U277UmUmUmU1 is an undirected HC for G u lt Suppose that G has an undirected HC the three vertices say 121122123 that correspond to one vertex from G must be traversed consecutively in the order 121122123 or 123122121 since 122 cannot be reached from any other vertex in G Since the other edges in G connect vertices with superscripts 1 or 3 if for any one triple the order of the superscripts is 1 2 3 then the order is 1 2 3 for all triples Otherwise it is 3 2 1 for all triples Since G is undirected we may assume that its Hamilton cycle is 1 2 3 1 2 3 1 2 3 1 2 3 111171111711117012701270127 7Uinvvin7Uinvvilvvilvvil Then WNW2 12 12 is a directed Hamilton cycle for G D Example 2 The subset sum problem is known to be NP complete7 In the following7 we show that the subset sum problem is reducible to the job scheduling with penalties problem Therefore7 we conclude that the problem of job scheduling with penalties is also NP complete PROOF Let 31 32 73 and C be an input for the subset sum problem we may assume that 21 si 2 C Let the input be transformed into the following input for the job scheduling problem ti pi8i f0r1 i n7 di C forlgign7 n k Esra i1 Clearly the transformation takes polynomial time Now we shows that Yes instance of the subset sum ltgt Yes instance of the job scheduling o gt suppose that the subset sum input produces a YES answer ie7 there is a subset J of N 17 27 771 such that Zia si C Then let 7139 be any permutation of N that causes all jobs with indices in J to be done before any job with indices in N7 J The rst lJl jobs are completed by their deadline since Zia t Zia si C and C is the deadline for all jobs Then the total penalty M n n n n PW 2PM t 2 PW 0 2 PW Z 3W 87quot C k j1 jJi1 jlJl1 HJHI 11 Thus the jobs can be done with total penalty k c lt77 Let 7139 be any schedule for the jobs with total penalty k Let m be largest such that m i1 ie7 m is the number ofjobs completed by the deadline C The penalty7 then7 is Z p7ri k3i 0 2 i1 im1 Since 25 pi si for all 1 g i g n we must have m 7L m TI 7L 2 2 PW 23W Z 3W 2 i1 im1 i1 im1 i1 and this can happen only if the inequalities in 1 and 2 are equalities Thus m 2 07 i1 so the objects with indices 7r17 7r27 77rm are a solution to the subset sum problem D

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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

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

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

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