Homework answers / question archive / Assignment 4 CS-GY 6003 INET Spring 2021 Due date: In order to give you the most time possible for this assignment, you can hand it in anytime before the last day of classes, which is May 10th

Assignment 4 CS-GY 6003 INET Spring 2021 Due date: In order to give you the most time possible for this assignment, you can hand it in anytime before the last day of classes, which is May 10th

Math

Share With

Assignment 4 CS-GY 6003 INET Spring 2021 Due date: In order to give you the most time possible for this assignment, you can hand it in anytime before the last day of classes, which is May 10th. The submissions on gradescope are open until 11:55pm on May 10th. No assignments are accepted after that time. Instructions: Below you will find the questions which make up the written part of your homework. They are to be written out (or typed!) and handed in on Gradescope before the deadline. Question 1: Graph theory . (a)Let G be a planar graph with at least three vertices. Suppose the drawing is made up of triangles (faces with 3 boundary edges) and faces with 4 boundary edges. There are 10 edges in total. How many triangles do you have and why? Draw such a graph. (You may if you wish provide a solution to the original problem of ”10 faces” total, but you will have more than one answer). (b) A connected graph has n vertices. How many edges will guarantee that a vertex exists with degree at least 3? How many edges will guarantee that all vertices have degree at least 3? (c) How many non-isomorphic graphs are there on 5 vertices such that the graph contains a cycle of length 4? Draw them. (d) A set of n children is such that every child has either 2 friends or 4 friends in the set. A child cannot be friends with him/herself. At recess, the children try to organize themselves into exactly two teams so that each child has all their friends on their team. Explain why no matter how the children divide into two teams, there are always at least 2 pairs of friends that are separated or no children have a friend on the opposite team. (e) A graph consists of 3 connected components, one is C5 , and one is K3,4 and one is K4 . Explain how many edges you need to add over the whole graph to create an Euler tour. Give an example of a graph for which there is no way to create an Euler tour by adding edges. (f ) A binary tree has 27 vertices. What is the maximum number of leaves? What is the minimum number? Draw the tree in each case. Suppose now that the tree is such that every node has exactly 0 or 2 children. Explain why the maximum number of leaves is the same as the minimum number of leaves in this case. Determine the maximum and minimum height. (g)A complete binary tree has height h. Show by induction that the number of leaves in the tree is at most 2h . Probability Theory . (a) One rather dismal afternoon with very little to do, you decide to play a game with your roommate, Celia. Celia rolls a die, and you flip a coin the number of times showing on the die. Your other roommate, Ruth is in the kitchen studying for her math exam. When she comes out you tell her the exciting new that you have flipped a total of 3 heads. Ruth tells you the most likely number that was on Celia’s die. Explain Ruth’s answer. 1 (b) A wedding reception has exactly 2n guests. There are n children and n adults. Each guest writes the name of their preferred dance partners on a piece of paper (allowed more than one!). A couple will dance together if and only if they each chose the other person as their preferred dance partner. For example, if Carol wants to dance with Bob and Bob wants to dance with Carol, then they will dance. Suppose children like to chance with children, so the chance that any child selects another child as a dance parter is 1/2. A child selects any adult as a dance partner with probability 1/10. On the other hand, adults like to dance with adults. The chance that any adult selects another adult as a dance partner is 1/4. The chance that an adult selects a child as a dance parter is only 1/20. Determine the expected number of dances that take place at the reception. Next, repeat the process assuming each guest is only allowed to select exactly one partner. Children will select among all guests equally, and adults will select an adult twice as often as they select a child. (c) Consider a standard suffled deck of 52 cards. Suppose we draw one card at a time. What is the probability that the second card drawn has the same value as the first? (ex. both are 10s or both are Js). What is the probability that the third card drawn has the same value as the 2nd? What is the expected number of times that we draw two identical cards in a row? (d) Guests arrive at a birthday party one by one. At the entrance, each guest provides their birth day. A guest will receive a $100 prize if his or her birthday is the same as the previous guest. What is the expected number of guests that arrive until the first prize is awarded? What is the expected number of guests that arrive until the second prize is awarded? (e) A country has exactly 10 major cities. The government is adding flights between pairs of cities. Suppose the funding allows for exactly 18 bidirectional flights to be added. What is the probability that city A and city B are connected by a flight? What is the probability that one can flight city A to city B to city C? (each a direct flight). What is the expected number of flights out of city A? Suppose now that exactly 5 of those cities apply a tax at their airport. What is the probability that there are exactly 6 flights for which the tax is applied? 2