Math 210, Concepts from Discrete Mathematics Worksheet 10 1. (a) How many nonisomorphic, unrooted trees are there with 4 vertices. Draw all the possibilities. (b) How many nonisomorphic, rooted trees are there with 4 vertices. Draw all the possibilities. 2. How many edges does a tree with 19,463,229,837,262 vertices have? 3. How many leaves does a full 3-ary tree with 100 vertices have? 4. A chain letter starts when a person sends a letter to five others. Each person who receives the letter either sends it to five people who have never received it or does not send it to anyone. Suppose that 10000 people send out the letter before the chain ends and that no one receives more than one letter. How many people receive the letter, and how many do not send it out? 5. Build a binary search tree for the words: hair, pies, chemical, keen, silver, drum, crib, huge, periodic, and clover using alphabetical order. 6. Determine the least number of comparison needed to sort four elements and draw a binary tree that represents the algorithm that sorts these elements using this number of comparisons. 7. (a) Draw a game tree for Nim if the starting position consists of three piles with one, two, and three stones respectively. (b) Extra Credit. Who wins the game if both players follow an optimal strategy? ...