CS 540 Fall 2005Homework 2Instructor: Louis OliphantDue Date: October 18, 2005There are 6 pages in this portion of the assignment. This assignment has twoparts. Part A is given to you now and consists of short answer type questions. Part Bconsists of a programming problem, and a related short answer part. You will receive partB shortly. Please turn in all written parts together (we prefer typed answer scripts), andthe programming part using the handin program.Part A: Short-answer questionsQuestion 1In this question you will explore the role of sex in evolution. Consider a hypotheticalorganism with 100 genes. Each gene either fits the environment (1, representing fit) or not(0, representing unfit), thus each gene can be encoded with one bit. All genes of anindividual are therefore coded as a 100-bit string.Assume the fitness of an individual, X, is measured by the number of fit genes it possesses,thus,fitness(X) = sum of X's gene bitsConsider two separate scenarios:1. Asexual reproduction (mutation only)(A) The population consists of N organisms, and each of them splits in two, with the copyhaving an identical gene pattern as the original parent. The population thus grows to size2N. It then follows that each gene in an individual is mutated (flip the bit, 1 to 0 or 0 to 1)independently with a small probability p. (B) Finally, after the mutation only the top N most-fit organisms survive (as measured bytheir fitness(X)). The population is again N.2. Sexual reproduction (crossover only)(A) The population consists of N organisms. They form couples of two at random. Eachcouple first produces 2 children by a crossover, and then produces 2 more children byanother crossover. Each crossover happens at some random position. The parent generationall die out after the reproduction. There are 2N individuals in the new generation, same asin scenario 1.1(B) Finally only the top N most-fit children survive. The population is again N.Assumption: At time (A), all individuals have the same fitness value f, and f > 50. Notice their bitstrings are random and might all be different, they just all sum to f.(a) What is the average fitness of the population in scenario 1 at the beginning of (A)? (b): What is the average fitness of the population in scenario 2 at the beginning of (A)?(c) What is the average fitness of the population right before (B) in scenario 1? (d) What is the average fitness of the population right before (B) in scenario 2?(e) After 1(B) and 2(B), which population do you think will have a higher average fitness?(f) Does this example prove the importance of sex? Justify your answer.Question 2Explain what type of search would result with each of the following special cases:(a) Local Beam Search with k = 1(b) Local Beam Search with k = ∞ (infinity)(c) Simulated Annealing with T = 0 (or VERY close) at all times(d) Simulated Annealing with T = ∞ (infinity) (or VERY large) at all times(e) Genetic algorithm with population size N = 12Question 3Perform each of the following crossover operations between the two parents in thetraveling salesperson problem. Cut-points (crossover) are indicated by a |.(3241|596|78)(6458|713|92)(a) OX -- order crossover(b) PMX -- partially mapped crossoverQuestion 4Use minimax alpha-beta algorithm to complete the tree below. Write the alpha-beta valuesin the nodes of the tree and cross out the nodes that are pruned.3MAX MINMIN MAXMAXMAXMAX2-3 8 10 -8 0 5 2Question 5Using Newton-Raphson, find the minimum off  x=ex−20 x3Figure 3. The shape of f(x)You may use a calculator. Let's say that Newton-Raphson converges if the four most-significant digits of x no longer change. Reminder: the derivative of ex is still ex.Answer the following questions:(a) Starting from x=7, how many steps does it take to converge and what is the value for xand f(x)?(b) Starting from x=4, same as above.(c) Starting from x=0, same as above.(d) Try some other starting values. How many optima (minima/maxima) do you think fhas?4Question 6In two-finger Morra we know the optimal mixed strategy for both E and O is(7/12 play 1, 5/12 play 2), and the expected value for E is -1/12.E and O are going to play the game tomorrow. However they all missed the class and hadto derive the optimal strategy on their own separately. E did the correct calculation and wasdistressed that he would expect to lose money. Desperate, E hacked into O's computer andto his surprise, E found that O made a math mistake! O wrote in a memo "(1/2, 1/2) is theoptimal strategy and I will play according to that tomorrow".(a) Should E change his strategy? If yes, what strategy should E use now?What's the expected value for E now?(b) What E didn't know was that O corrected the math mistake later that night. Owill play using the optimal strategy (7/12, 5/12) tomorrow. If E uses the strategy in (a),what's the expected value for E now?(c) Furthermore, O in fact discovered the computer intrusion. O knew that Ethought O is going to use (1/2, 1/2). O knew that E will use the strategy in (a). Should Ouse (7/12, 5/12)? If no, what strategy should O use now? What's the expected value for Enow?5Question 7This is a 2-color graph optimization problem. Consider the graph below. The objective isto color the nodes in the graph with Red or White (write the color R(Red) or W(White) ineach node) so that no adjacent nodes have the same color (lines indicate adjacency). The score of a state is defined as the number of conflicting pairs. A move from a givenstate is defined as changing the color of a single node. A local minimum is achieved whenno neighbor of a given state has a lower score than the current state (they can have thesame score). Label the nodes below so that it is a local minimum but not the