Now we explore the tree structure of the problem and bring in the Branch and Bound idea. Notice that while 3 is invertible modulo 212 , 2 of course is not. In fact, what is happening as you go through the stages 9' > y- (2/3) > y- (2/3)2 > ... > 23*1 is that each stage is a 2to1 map. For instance, in the rst step, the odd numbers 3; and (2\"1 + 3;) mod 22 both map to 29/ 3 mod 23, a number which is divisible by 2 but not by 4. In the very last stage, the two numbers 29\"2 and 2f1 + 2'92 map to 2E_1. Now you should \"turn this around\" and imagine a binary tree whose vertices are labeled with certain rational numbers. The root is labeled with 1 / 2. I11 general, if a. vertex is labeled with 2, its children are labeled, one each, with the two values of 2' mod 1 satisfying the equation 22' = 32 mod 1. (\"Mod 1\" gives the fractional part of a number. Note there are indeed two distinct z' satisfying the equation 22' = 37; mod 1, offset by 1/2, since 2 - (1/2) = 0 mod 1.) For example, the children of the root are labeled with 1 / 4 and 3 / 4. The children of the vertex labeled 1/4 are labeled with 3/8 and 7/8; while the children of the vertex labeled 3/4 are labeled with 1/8 and 5/8. You will notice that at level if of the tree (with the root being level 1), the labels have denominators = 2'? and odd numerators. Let Lg denote the set of vertices at level 3 of the tree; for vertex 1) let 14(1)) denote the ancestors of v (the vertices on the simple path from v to the root, inclusive); and let 2(0) denote the rational number labeling vertex 17. You can now verify that if vertex 1) is such that 25(2)) = y/2f, y odd, then fe(y) = $39 Z exp(27riz(u)) uEA('u) Let us denote this value also f(v) = fg(y). This means that if 11) is some vertex in the tree at depth 16, then all vertices U which are at depth 3 and are descendants of w, satisfy f(v)=E kf(w)+re Z exam-2(a)) uA(U)A(w) Use this observation to design a branch and bound algorithm to compute F(1?). Describe it and justify correctness. Then program it. For full credit, use it to compute FOE\") up to at least E = 40. Hand in your code and a CSV le of results with each row containing the value of E, the value of F(E), and the time it took to compute this value. For additional credit, run your program for larger values of 6. One additional point of credit for each 20 additional values of 1?, up to three additional points. (So through I = 100) First, some preliminaries. For any integer N 2 2, Z/N is the ring of integers modulo N, namely, the set {0, ..., N -1} with addition, subtraction and multiplication modulo N. Division is not always possible; you can perform the division x/y only if y is invertible modulo N, namely, there exists another element of Z/N, called y , such that y .y = 1 mod N. In that case, x/y is defined to be x . y . The criterion for whether or not y is invertible is quite simple: it is that y and N should be relatively prime, namely, god(y, N) = 1. As we saw earlier in the course, an equivalent condition is that there exist integers a, b such that aN + by = 1; and then b = y mod N. In this exercise we need only the case that N = 2. So the invertible elements are precisely the odd integers modulo 2. For x E C, let R(x) be the real part of x. And define ex : Z/N - C by en(y) = exp(2miy/N). For a given ( 2 1, let fely) = E eze (y (2/3 ) m) m=0 Notice that the division by 3 is not in R; this is multiplication by 3-1 in Z/2. Conjecture 1 There is a c