$24
Homework #3 Solution
Sharing this PDF file in any way, e.g., via email, uploading to a web site (personal, public, commercial) is
unauthorized.
This file is copyrighted material. Copyright held by Professor Dimitris Achlioptas and UC Santa Cruz.
Each problem is worth 25 points. You must define the function OPT, give an identity for it, explain the identity, show how to use it to compute OPT, show how to derive the actual solution, and state the running time.
Reminder: For each of the four problems you receive 6 of the 25 points if you write nothing about the problem. If you feel that you have a partial answer worth more than 6 points, e.g., you have an algorithm but can’t prove it correct, or your algorithm can be proven correct but is too slow, you can still write this information as long as you begin your answer by assessing your work. If we find your work as assessed, you will receive at least 6 points.
On The Run
You’ve gotten into some trouble with the Santa Cruz locals and decided to make a run for it. You are on your hog (slang for motorcycle) trying to get from Santa Cruz to Achliopolis as fast as possible. Santa Cruz and Achliopolis are connected by two parallel roads, Highway A and Highway B. Along your way, A and B are connected at n junctions. At each junction you can exit from your current road and switch to the other. A may be a faster road between some junctions and B may be faster between others, but you will have to weight the gained speed against the time it takes to switch roads. Let ai denote the time it takes to get from the i-th junction to the (i + 1)-st junction on road A, and let bi denote the same for road B. Let k be the time it takes to switch roads at any junction. Come up with a dynamic programming algorithm that finds the fastest route from Santa Cruz to Achliopolis.
Engine Trouble
You’ve made it to Achliopolis, but your hog is in bad shape. A sequence of L repairs need to be made to it, i.e., the L repairs must be performed in a specific order. Repair i will take any mechanic ti hours, for some integer ti. There are two mechanics you can go to, Maggie and Mikey and each repair must be done entirely by one mechanic. Maggy charges r dollars an hour for her work, but Mikey takes a flat rate of b bucks for five repairs. Once you give Mikey your motorcycle, you can’t get it back until either he has finished the next five repairs or runs out of repairs to do. Given L, r, and b, come up with a polynomial-time algorithm that determines the cheapest way to get the repairs done.
Achliopolis Vegan Hot Dog Eating Champion
You’ve made it to the safe haven of Achliopolis, but you blew most of your cash on those motorcycle repairs. Lucky for you, the Achliopolis vegan hot dog eating festival is about to start. The festival lasts n days, and each day there is a vegan hot dog eating contest with cash prizes. By looking at who has entered the contest on each day, you figure that if you enter the contest on the i-th day, you will make exactly ci dollars. But you need to fast for two days before and after each contest, i.e., if you enter the contest on day i you cannot enter the contest on day i 2, i 1, i + 1, or i + 2. Given the values ci, come up with a vegan hot dog eating schedule that maximizes the money you will make during this festival.
The Rest of Your Life
You made a considerable fortune from eating vegan hot dogs and have decided to settle down in an a lovely Achliopolis townhouse. You figure you have about y years of life remaining, and you want to dedicate those years to learning. There are n topics you are interested in studying, but you don’t necessarily have time to investigate, much less master, each of them. You can only study one topic at a time, and once you set a topic aside you will never study it again. Let fi(t) be a function denoting the wisdom you attain from studying topic i for t years. No single topic can give you more than w units of wisdom (i.e. fi(t) w) and no additional wisdom can be attained by studying for a fraction of a year (i.e. fi(t) = fi(btc)). Come up with an algorithm that maximizes your wisdom at the time of your death in O(naybwc) time for some constants a; b; c.
2
