Objects and Strings - A Concise and Practical Introduction to Programming Algorithms in Java - page 125

Implement the Horner evaluation scheme in function static long
HornerScheme(Polynomial source, long x);

- A function static Polynomial multiply(Polynomial P, Polynomial
Q); for multiplying 4 two polynomials. What is the time complexity of
that polynomial multiplication?

Exercise 5.5 (Chevalier de Mere's probability games)

During the 17th century, gambler de Mere asked Blaise Pascal an
explanation for his game losses. His question was solved by Pascal
and Fermat, and yielded the foundations of the theory of probability.
Gamblers used to bet on the event of getting at least one ace in four
rolls of a dice. As a game variation, De Mere proposed to use two die
and roll them 24 times with a bet on having at least one double ace. De
Mere thought the games were equivalent but he lost consistently. Explain
why? Write a simulation program to empirically determine which one
dice/two die game is more likely to win.

Use the following classes:

import java.util.Random;

class Dice
Random rand ;

Dice ()
{ rand= new Random ( ) ; }

// Return the elementary outcome of tossing a dice: A
face between 1 and 6
int Toss ()
{

return 1+rand . n e x t I n t ( 6 ) ; }

}

// One dice, four rolls
class DeMereGame1
{ Dice dice ;

DeMereGame1 ( )
{ dice= new Dice () ; }

// Return true if the gamer win and false otherwise
boolean Experiment ()
{ int i;

4 Note that we can perform faster multiplication of polynomials using the Karatsuba
algorithm ( O ( n 1 . 585 ) time complexity) or the FFT algorithm ( O ( n log n )-time).