CS 3230 Design and Analysis of Algorithms Assignment

- Start each of the problem on a separate page.
- Make sure your name and matric number is on each sheet.
- Write legibly. If we cannot read what you write, we cannot give points. In case you CANNOT write legibly, please type out your answers and print out hard copy.
- To hand the homework in, please submit a .pdf file of your typed/scanned version of your assignment to the submissions box on Luminus. It may be handwritten and scanned but please make sure your handwriting is legible and the copy has sufficiently high resolution.

IMPORTANT: You are advised to start on the homework early. For some problems, you need to let it incubate in your head before the solution will come to you. Also, start early so that there is time to consult the teaching staff during office hours. Some students might need some pointers regarding writing the proofs, others may need pointers on writing out the algorithm (idea, example, pseudo-code), while others will need to understand more deeply the material covered in class before they apply them to solving the homework problems. Use the office hours for these purposes!

It is always a good idea to email the teaching staff before going for office hours or if you need to schedule other timings to meet. Do it in advance. CS 3230 Design and Analysis of Algorithms Assignment

Background Story

Good news everyone! The Swedish robot from πKEA is here with the supercollider that Professor Farnsworth ordered. He’s pretty excited to plug it in and power it up so that he can run new experiments. But, his lab in a mess (he doesn’t clean up very often) and basically he need to reroute power from sources to sinks. He’s hired Mr. Nodle, a research assistant, to help him out here.

Unfortunately, after a few months of running around the labyrinth that is Professor Farnsworth’s lab, it’s probably safe to say that Nodle is not going to be able to solve this by himself. While he’s busy crying in a corner about how he’s misplaced the trust of the Professor, you could really do him a favor by trying to show him that in fact, this problem is in fact, very difficult, so he doesn’t have to feel so bad after all1.

Problem Statement

We will call the problem you’re trying to solve PLUGIT. The input is given as an m × n grid of tiles, where each tile can be one of the following:

- An empty tile
- A socket (powered)
- A socket (unpowered)
- A broadcast node
- Wall(s)

(Note: Wires are not part of the input.) Now the goal is to be able to power all sockets (broadcast nodes need not be powered). The section below details the physics of Professor Farnsworth’s lab. CS 3230 Design and Analysis of Algorithms Assignment

Definition 0.1 PLUGIT Given such a grid with tilings, the problem is to output yes if there exists a routing by using the directed wires (that follows the rules) to power all sockets, and no otherwise.

Goal of assignment: Show that PLUGIT is NP-complete.

Question 1: Proving NP-hardness

Show that PLUGIT is NP-hard. You may do this by performing a reduction from any of the NP-Hard problems presented during the lectures or tutorials.

To be precise, the list of problems you may use includes:

Question 2: Proving in NP

All is not lost, however. It turns out that Mr. Nodle has a good friend Mr. Govond, who just so happens to propose that it is indeed possible to power every socket. However, Mr. Nodle is usually quite skeptical about Mr. Govond’s propositions. Mr. Govond should be able to provide a polynomial-sized certificate that it is indeed possible, and Mr. Nodle should be able to verify that certificate, in polynomial time (with respect to the size of the input).

Question 3

Say there are n + m friends, as it turns out, the first n people owe money to the other m people, where the set of people who owe and the people who are owed are disjoint. Now, they wish to settle the matter with as few transactions as possible. In other words: Given a set of values A = [a1,a2,…,an], and B = [b1,b2,…,bm], and an integer k, where A is the set of the amount of money that the first n people owe, and B the set of the amount of people the next m people are owed, decide if the first n people can pay at most whatever they owe, the other m people can recieve whatever they are owed, within k transactions. You are guaranteed the total amounts in A and B are the same.

Question 4

Consider the optimization version of the problem stated in Question 3, i.e., to find the minimum number of transactions. Design a polynomial time approximation algorithm with approximation ratio at most 2. (Clearly mention the running time of your algorithm and calculate the approximation ratio.). CS 3230 Design and Analysis of Algorithms Assignment

##### Need Help with a similar Assignment?

The post CS 3230 Design and Analysis of Algorithms Assignment appeared first on EssayPanthers.

- Confidentiality & Authenticity Guaranteed
- Plagiarism Free answers Guarantee
- We Guarantee Timely Delivery of All essays
- Quality & Reliability
- Papers Written from Scratch and to Your exact Instructions
- Qualified Writers Only
- We offer Direct Contact With Your Writer
- 24/7 Customer Support