Randomized and Graph-Theoretic Method

Assignment Help Data Structure & Algorithms

Reference no: EM132681919

Programming Assignment

Topic: Randomized & Graph-Theoretic Method

Consider a collection of M lightbulbs and N switches. The switches can be placed either in a down or up position. Each lightbulb is connected to two of the switches and it can only be turned off if the two switches connected to it assume a specific configuration.

We ask if there is a configuration of the switches (down or up for each) so that all of the lightbulbs are on simultaneously.

Suppose we represent the N switches as integers 1 through N. We represent each lightbulb as a pair of integers which encodes the configuration which avoids the lightbulb to be turned off. We will encode the up and down positions by using positive and negative integers. So, if a lightbulb is represented by the pair (i, -j), then this means the lightbulb is connected to switches i and j. If switch i is in the down position and switch j is in the up position, then the lightbulb is off, otherwise the lightbulb will be on.

PROBLEM
Given an instance of this lightbulb problem, determine if there is a configuration of the switches so that all lightbulbs are simultaneously on. If the answer is YES, then provide the sequence of up/down for each switch. If the answer is NO, provide a "proof" of this fact.

Attachment:- Programming Assignment.rar

Reference no: EM132681919

Questions Cloud

Discussion is online education efficient for students : Is online education efficient for students in Hong Kong and Explain whether the argument agrees or disagrees

Describe acceptable types of education and training : You are the HR Manager for the Pleasantville School District. Although it hadn't done so before, the district recently implemented a person-focused pay program.

Explain proposed capital structure of the firm : FCOJ, Inc., a prominent consumer products firm, is debating whether or not to convert its all-equity capital structure to one that is 30 percent debt.

What is the interest tax shield-tatum co : Tatum Co. has a 25 percent tax rate. Its total interest payment for the year just ended was $30.3 million. What is the interest tax shield?

Randomized and Graph-Theoretic Method : Randomized and Graph-Theoretic Method - determine if there is a configuration of the switches so that all lightbulbs are simultaneously on

Business valuations - contemporary studies : Business valuations - Contemporary Studies in Economic and Financial Analysis Mergers and Acquisitions

Evaluate fairness of company current compensation system : You have recently been hired as the HR manager of a small furniture manufacturing company that has 63 employees. These employees include everyone from line work

Describe the civil right rights act : The Civil Right Rights Act of 1964. Please discuss the chosen topic. You should tell (1) why it is important, (2) how it has impacted the workforce.

What concrete situations in your workplace might give rise : What concrete situations in your workplace might give rise to ethical dilemmas? Does the professional code of conduct provide any relevant guidance for these.

User Account

All Pages