As a first step go to the last page and read the section: “Advice on how to do the assignment. ”

Problem 工. (10 points) You are given a game with the following rules: there are two players, Blue and Red, playing one after the other each for a total of n rounds and controlling a character, Charlie, to explore a board made of two types of tiles, blue and red. (So the game goes on for a total of 2n turns, alternating between the two players, and Blue plays first.) When Blue plays, she decides whether the character goes left or right; when Red plays, she chooses to go forward or backward. At the end of the 2n steps, Blue wins if Charlie is on a blue tile, and Red wins if Charlie is on a red tile.

You want to find the optimal strategy to win the game, and, in particular, if there is a way for Blue to win the game: we model the game as a binary tree T of height 2n, where the leaves correspond to the tiles Charlie reaches at the end, and a path from root to a leaf corresponds to a sequence of decisions by Blue and Red players. So the leaves of the tree are either red or blue; when we are at an internal node of even depth, it is Red’s turn to play; when we are at an internal node of odd depth, this is Blue’s turn to play.

You asked two of your friends, and they came up with the following two algo- rithms, CanRedWin1 and CanRedWin2, which are supposed to indicate if there is a strategy for Red to win the game no matter how well Blue plays: at every step, Red can select a winning move. But you suspect your friends’ algorithms might be wrong. . .

(In the above, mod is the modulo function, which returns the parity of an inte- ger; ^ is the Boolean AND operator, and _ is the Boolean OR.)

a) State (without justification) which one of the two algorithms, when called with

v = T.root and k = 0, always returns the correct answer.

b) Prove correctness of the algorithm you said was the correct one.

[2 points]

[4 points]

c) Establish the time complexity of that algorithm, as a function of n. [4 points]

Important: Throughout the rest of the assignment, we will assume that a real number takes O(1) space to represent and store.

Problem 2. (15 points)

A real (univariate) polynomial P of degree n is a function of the form

n

=0

where a0, a1, . . . , an  are real numbers, with an 0 (by convention, the “zero polyno- mial” P(x) = 0 has degree n = −•).

The goal of this exercise is to evaluate polynomials efficiently. That is, given an array A of n ≥ 1 numbers representing a polynomial P(x) = A[0]+ A[1]x + ·· · + A[n − 1]xn−1 and a real number x, we want to compute and output the value P(x).

Here are three different algorithms for this task.

a) Show that all three algorithms are correct. [5 points] (Hint: for the second, show that Power(x, k) computes xk, by induction on k.)

b) Show that evaluate1 runs in Q(n2 ) time.

c) Show that evaluate2 runs in Q(n log n) time.

(You can use without justification thefact that Power(x, i) runs in time Q(logi)for i ≥ 2.)

d) Show that evaluate3 runs in Q(n) time. [3 points]

Problem 3. (35 points)

We want to build a library to manipulate (univariate) polynomials, which allows us to support the following:

• Initialisation: given a non-negative integer n and a real number a 2 R, create the polynomial P(x) = axn .

• Addition:  given two polynomials P(x)  = Âk(n)=0 akxk  and Q(x)  = Â0 bkxk, return the polynomial R = P + Q (of degree r = max(n, m) given by

r

=0

(with the convention that ak = 0 if k > n, bk = 0 if k > m).

• Multiplication: given two polynomials P(x) = Âk(n)=0 akxk and Q(x) = Â0 bkxk, return the polynomial R = PQ (of degree r = m + n) given by

r  R(x) = P(x)Q(x) = Â

=0

aibk−i! xk

(with the convention that ak = 0 if k > n, bk = 0 if k > m).

• Degree: given a polynomial P, return its degree.

• Evaluation: given a polynomial P and a real value x 2 R, return the value P(x) (a real number).

Your task is to design a data structure, Polynomial, along with the following operations: