1. Consider the function f(n) defined as follows, where n is a nonnegative integer n is even,n>l (a) Draw a box trace diagram showing the evaluation of f(11). Give the value of the expression f(11). [5 points] (b) List the calls in the order made. How many calls are made to the function? [5 points (c) Give the multiplicities of the calls for each value of n. [5 points] (d) Suppose each call to the function is memoized as f(11) is evaluated. Draw the box trace diagram for the evaluation of this version of the expression(5 points (e) How many calls are made for this version? How many fewer calls are made using the memoized version? [5 points] 2. Assuming simple connected graphs, consider the definitions below. Definition 1. An Euler circuit, also called an Euler cycle, or Euler tour, is a trail which starts and ends at the same vertex in a graph. In other words, it is a cycle which traverses each graph edge exactly once Definition 2. An -regular graph is a graph whose vertices are r degree each Draw a 2-regular graph of order 5, labeling its vertices A, B, C, D, and E, and give an Euler circuit for the graph by listing the sequence of vertices, beginning and ending with the same vertex. [5 points (a) (b) Using the fact that 211 = deg(u), show that a simple connected graph cannot have an odd number of odd degree vertices. [5 points] If possible, draw an order 4 graph with at least one odd degree and an Euler cycle or explain why no such graph exists. [5 points) (c) (d) For what values of n3 will a K, a complete graph of order n, have an Eulerian Circuit? [5 points] (e) Draw an order 7 3-regular graph or explain why it is impossible to draw one. [5 points Assignment 2 Page 1