Order Description

Question 1

You have in front of you a set of AA batteries and a flashlight. The flashlight will only light up if two functioning AA batteries are inside. Among all the batteries, there is a number n of batteries which are not functional and and a number m of batteries which are functional. You need to find an algorithm that finds two good stacks among the n + m stacks in front of you. This algorithm should make as few worst-case comparisons as possible. So you should assume that you found the two correct stacks on your last comparison. If m> 2, an algorithm testing in worst case ( n + m ) × (n + m − 1) / 2 pairs of batteries will be awarded a maximum of 15 points. You have to find a trick so as not to compare all the pairs. As a guide, if n = 30 and m = 10, you can find two functional stacks in 100 tries or less.

Steps: 1. Download the programming code for this question.

2. Implement the find function in the find_stack.cpp file. No other file should be modified. Your implementation should have the lowest possible worst-case complexity .

4. count the number of times you call the conjunction method as a function of n and m, in worst case.

Question 2

A company is developing a new video game based on the world of Harry Potter. In this game, you become a student of Hogwarts and you have to complete several levels throughout the year. The final level is the final exam. It's a practical exam of all the spells you've learned during your year at Hogwarts. Each spell cast is evaluated by its accuracy. Your mandate is to calculate the penalty associated with a lack of precision. The designers want this level to be really tough. The goal is to shoot all the spells in the target worth the most points. Each time the desired target is not reached, a penalty is calculated. The farther the spell is from the target, the greater the penalty. We also want to penalize the disparity of spells. For example, if your four casts are on targets 5, 10, 15, 20, you will be heavily penalized since no spells are on the same target. The designers have already figured out how to calculate the penalty. Let v be the vector of the pointing of the targets reached by the spells. The vector v is sorted in ascending order. The penalty for each vi spell is the sum of the distance between vi and all spells with a greater score. It is therefore the sum of the distance between vi and vj for all j such that j> i. This makes it possible to measure the disparity of spells. We must also add to the penalty the distance between the pointing of vi and the pointing of the desired target for each spell. This makes it possible to penalize the fact that the largest target has not been reached.

Suppose the disparity penalty for spell i is Ai and the penalty for not hitting the larger target is Bi. Suppose also that the targets hit from 5 throws are 5, 5, 10, 10, 15 and the max target is 20.

The first throw disparity penalty is: A1 = (5− 5) + ( 10−5) + (10−5) + (15−5) = 20. The penalty for not hitting the target of the first throw is : B1 = (20 - 5) = 15. The total penalty for the first throw is: A1 + B1 = 35

The second throw disparity penalty is: (10 - 5) + (10 - 5) + (15 - 5) = 20. The penalty for not hitting the target for the second throw is: B2 = (20 - 5) = 15. The total penalty for the second throw is: A2 + B2 = 35

The third throw disparity penalty is: (10 - 10) + (15 - 10) = 5. The penalty for not hitting the target of the third throw is: B1 = (20 - 10) = 10. The total penalty of the third throw is: A3 + B3 = 15

The fourth throw disparity penalty is: (15 - 10) = 5. The penalty for not hitting the target of the fourth throw is: B1 = (20 - 10) = 10. The total penalty for the fourth throw is: A4 + B4 = 15

There is no disparity penalty for the fifth throw, so A5 = 0. The penalty for not

not having hit the target of the fifth throw is: B1 = (20 - 15) = 5. The total penalty of the fifth throw is: A5 + B5 = 5

The total penalty for accuracy is the sum of the penalties for all spells cast. In the previous example, the total penalty would be 35 + 35 + 15 + 15 + 5 = 105. You therefore have, as input to your program, the sorted vector of targets reached and the value of the maximum target. You must return the full penalty for accuracy.

The company tells you that they found a way to solve this problem at Θ ( n 2) where n is the number of spells cast. Unfortunately, as this game is being developed on a server, the time to return the accuracy penalty is too great. We therefore ask you to design an algorithm faster than Θ ( n 2).

Steps: 1. Download the programming code for this question.

2. Implement the calculate_penalite function in the penalite.cpp file. No other file should be modified. Your implementation should have the lowest possible worst-case complexity .