New User Special Price Expires in

Let's log you in.

Sign in with Facebook


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


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Algorithm Design

by: Ashleigh Dare

Algorithm Design ECS 122A

Ashleigh Dare
GPA 3.75

Zhaojun Bai

Almost Ready


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

Purchase these notes here, or revisit this page.

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

Preview These Notes for FREE

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

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Zhaojun Bai
Class Notes
25 ?




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.

Similar to ECS 122A at UCD

Popular in Engineering Computer Science


Reviews for Algorithm Design


Report this Material


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


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Steve Martinelli UC Los Angeles

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

Anthony Lee UC Santa Barbara

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

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


"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


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


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:

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

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.