Show that to maximize the expected reward

Reference no: EM131121860

The Quiz Problem) Consider a quiz contest where a person is given a list of N questions and can answer these questions in any order he chooses. Question i will be answered correctly with probability pi, independently of earlier answers, and the person will then receive a reward Ri. At the first incorrect answer, the quiz terminates and the person is allowed to keep his previous rewards. The problem is to maximize the expected reward by choosing optimally the ordering of the questions.

(a) Show that to maximize the expected reward, questions should be answered in decreasing order of piRi/(1 - pi

(b) Consider the variant of the problem where there is a maximum number of questions that can be answered, which is smaller than the number of questions that are available. Show that it is not necessarily optimal to answer the questions in order of decreasing

(c) Give a 2-OPT algorithm to solve the problem where the number of available questions is one more than the maximum number of questions that can be answered.

Reference no: EM131121860

Questions Cloud

Trade secrets are protectable : Each of the following is considered trade dress except: Trade secrets are protectable:

Comprehensive depreciation computations kohl beck : Comprehensive Depreciation Computations Kohl beck Corporation, a manufacturer of steel products, began operations on October 1, 2009. The accounting department of Kohl beck has started the fixed-asset and depreciation schedule presented on page 581.

Recording statutes for real property : Recording statutes for real property: A former employee may not

As a base heuristic in a rollout algorithm : Rollout Algorithm for the Quiz Problem) Consider the quiz problem of Exercise 10.28 for the case where the maximum number of questions that can be answered is less or equal to the number of questions that are available.

Show that to maximize the expected reward : The Quiz Problem) Consider a quiz contest where a person is given a list of N questions and can answer these questions in any order he chooses. Question i will be answered correctly with probability pi, independently of earlier answers, and the pe..

What is the optimal product mix for problem : The objective of a linear programming problem is to maximize 1.50A + 1.50B, subject to 3A + 2B ≤ 600, 2A + 4B ≤ 600, and 1A + 3B ≤ 420. a. Plot the constraints on the grid below b. Identify the feasible region and its corner points. Show your work. c..

Monotonically nondecreasing sequences of numbers : (Hardy's Theorem) be monotonically nondecreasing sequences of numbers. Let us associate with each i = 1,...,n a distinct index ji, and consider Use an interchange argument

What is the optimal solution and max profit : A craftsman builds two kinds of birdhouses, one for wrens (X1), and one for bluebirds (X2). Each wren birdhouse takes four hours of labor and four units of lumber. Each bluebird house requires two hours of labor and twelve units of lumber. What is th..

The projects so as to minimize the maximum tardiness : A busy professor has to complete N projects. Each project i has a deadline di and the time it takes the professor to complete it is Ti. The professor can work on only one project at a time and must complete it before moving on to a new project. F..

User Account

All Pages