### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Discrete Mathematical Structures CSCI 2427

ECU

GPA 3.99

### View Full Document

## 47

## 0

## Popular in Course

## Popular in ComputerScienence

This 44 page Class Notes was uploaded by Else Dooley on Sunday October 11, 2015. The Class Notes belongs to CSCI 2427 at East Carolina University taught by Robert Hochberg in Fall. Since its upload, it has received 47 views. For similar materials see /class/221319/csci-2427-east-carolina-university in ComputerScienence at East Carolina University.

## Popular in ComputerScienence

## Reviews for Discrete Mathematical Structures

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/11/15

The Standing Bosses Game Line up some players in Chairs facing the Class 0 The rightmost sitting player from the class s point of View is the boss 0 The boss s job is to stand up and to tell all standing players to his right from the class s point of View to sit down The game is repeated for as long as possible What happens Will this game ever end What will the end look like Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 1 The Game with 3 People Mi Mi MM MW How long would the game last with 4 people gtALOgtALltgtgtALOgtALltgt gtALogtALltgt o 0 gt49 gtAIPO How long would the game last with 5 people Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 2 Symbolic Representation of the Game 000 100 001 101 010 110 011 111 Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 3 The Game with 3 People 000 001 010 011 100 101 110 111 Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 4 The Game with 4 People 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 5 The Game with 5 People 00000 10000 00001 10001 00010 10010 00011 10011 00100 10100 00101 10101 00110 10110 00111 10111 01000 11000 01001 11001 01010 11010 01011 11011 01100 11100 01101 11101 01110 11110 01111 11111 Okay What patterns do you see Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 6 Interesting Observation Number One 8 4 2 1 Total 0 O O O O O O 1 O O 1 O O O 1 1 O 1 O O O 1 O 1 O 1 1 O O 1 1 1 1 O O O 1 O O 1 1 O 1 O 1 O 1 1 1 1 O O 1 1 O 1 1 1 1 O 1 1 1 1 The Game secretly encodes the counting numbers Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 7 The Game with 5 People 01010101010101010101010101010101 00110011001100110011001100110011 00001111000011110000111100001111 00000000111111110000000011111111 00000000000000001111111111111111 Introduction to Counting TSP 8 Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Interesting Observation Number Two or Who s the Boss You ve seen this pattern before Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 9 Interesting Observation Number Three The Tower of Hanoi Puzzle A set of different sized discs are stacked on one of three poles The stack must be moved to another pole according to the following rules 0 You may move only one disc at a time 0 During the transfer you may never put a disc on top of a smaller disc How can one move all the discs from the start pole to another pole and how many moves will it take Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 10 Moving the Blocks small medium small large small medium small EDIE Db gt The blocks move in the direction in which the tab is pointing Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 11 Ema NEH Emaau m BEL Generation of the Sierpinski Triangle Can you give an iterative rule that generates this sequence of figures Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 13 Counting Subsets How many ways are there to select a committee from among 5 people A1 Bob Cate Deb Edith Fact The Standing Bosses game With n players gives all possible O l strings of length n We ll prove this shortly But for now go ahead give me a 0 1 string of length 5 Observation We can encode a selection of a committee by using the code 1 selected 0 unselected Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 14 Bijection There exists a natural bijection between 0 1 strings of length n and subsets of a set of size n suitably ordered Al Bob Cate Deb Edith 00000 lt gt e 00001 lt gt E 00010 lt gt D 0001 1 lt gt DE 10101 lt gt ACE 11111 lt gt ABCDE So the number of subsets of A B C D E is the same as the number of 5 bit strings Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 15 Proof that we Get All Strings The standing bosses game is a cheesy coding of the binary increment The game is exactly how we add 1 to an integer in binary 11010010110 11010010111 1 1 We started with everyone sitting 0 We ended with everyone standing Zl ip iople 1 Those are respectively the smallest and largest binary values that a bit string can represent So all other bit strings must fall somewhere between them Since our operation counted by ones we must hit all other bit strings along the way from 0 to 21mm16 l Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 16 Another Proof that we Get All Strings We can check by hand that for 3 players we get all strings Now suppose there are 4 players What does the leftmost player do 0 Watches a full game with 3 players 0 Stands up 0 Watches another full game with 3 players We therefore get all 4 bit O l strings 000 001 010 011 100 101 110 111 How about 5 The rest of the proof proceeds by induction on n the length of the strings 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 1 7 How Long do the Boss Games Last Assuming that every possible 0 1 string really does appear the question becomes How many 01 strings are there Okay I know you already know the answer Let s answer this for strings of length 3 by means of a skill that way too many undergraduate students undervalue Make a Systematic List Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 18 Tree Diagram for 3 Players Start Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 19 Tree Diagram for 4 Players Start In General We can find the number of binary strings of length n by doubling repeatedly 2x2xmx2 Where there are n 2s in that expression So the number of strings of n bits is 2 Another Way to Think of it Picture n slots each of which may be filled with either a O or 1 Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 21 The Multiplication Rule 0 If a task consists of several parts 0 And each part must be performed to complete the task 0 Then the number of ways the task can be accomplished is the product of the number of ways to do each part Task The number of ways to complete this task is aXchXdXeXf Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 22 Shirts and Pants Barry Wishes to select an outfit for each day of a 10 day program He has 3 shirts and 4 pairs of slacks available How many outfits are possible Will he have to repeat himself Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 23 Code Words The Dempsey Club assigns each of its members a 3 letter password which it uses for identification when a member puts it on the tab The letters are selected from the word AMB IDEXTROUSLY How many 3 letter code quotwordsquot are possible Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 24 39anasmm A pet store has for sale 5 dogs 3 cats 4 fish How many ways are there for little Suzy to select a pet to bring home The multiplication rule does not apply We do not have a task With many parts that all need to be performed Can you think of a question Where the answer is 5x3x4 How many ways are therefor little Suzy to select one of each type of animal Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 25 Add or Multiply All parts must be performed Multiply Do whatever you can to help your students keep this straight Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 26 Arrangements In how many ways can the letters of the word S P O T be arranged OPST POST SOPT TOPS OPTS POTS SOTP TOSP OSPT PSOT SPOT TPOS OSTP PSTO SPTO TPSO OTPS PTOS STOP TSOP OTSP PTSO STPO TSPO Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 27 Class Of cers Amy Brenda Clement and Darron have been selected as class officers Now they need to be assigned to the positions of President Vice President Secretary and Treasurer In how many ways can this be done I Amy I lBrendal lClementl lDarronl Pres VP Secy Treas Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 28 How Many Ways to arrange your Ferrari BMW and Mercedes in your 3 car garage assign siX beds to your siX children select the order in which you will surf parasail collect shells and sunbathe during your day at the beach arrange your ten favorite novels on a bookshelf select the order in which to remove seven illegal animals from the beach decide which of your five employees will sweep wash cook serve and bus respectively Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 29 Factorial The number of ways to arrange n distinct objects is given by the expression ngtltn 1gtltn 2gtltgtlt2gtlt1 This quantity arises often enough that it has been given its own notation n which is pronounced n factorial Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 30 Factorial Here is a chart showing the first few factorials n n O 1 2 3 4 5 6 7 8 9 yi O Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 31 Some Counting Practice 1 A classroom has 12 boys and 14 girls and the teacher wants to select one boy and one girl to be class representatives to the Spring Fling committee In how many ways can the teacher make her selection 2 A multiple choice quiz has 5 questions and 4 choices for each question How many ways are there for a student to answer the questions on this quiz 3 Dagwood is exercising great restraint in making a sandwich He is going to use only one kind of meat one kind of cheese one topping and one kind of bread The meat choices are ham salami bologna chicken roll or turkey the cheese he selects from American Swiss or provolone the topping he selects from mustard mayonnaise butter pickles or pepper the bread is either rye or pumpernickel How many sandwiches are possible Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 32 Some More Counting Practice 4 A preacher gave 33 sermons in 2000 41 sermons in 2001 and 37 sermons in 2002 He wants to reuse a sermon from a previous year this Sunday In how many ways can he do this 5 How many different ways are there to stack the blocks shown to the right Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 33 Some More Counting Practice 6 How many ways are there to build a stack of blocks from those shown in problem 5 where the stack can have any size 7 In the game of Canaps a gambler rolls either two or three dice of different colors and wins or loses depending on the outcome How many outcomes are possible Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 34 Some More Counting Practice 8 The host of a new game show is explaining the rules The contestant can select either star or year If she selects star then she has to name the star of a certain sitcom and the host has 20 sitcoms to select from If she selects year then she has to name the year in which a certain movie won an academy award the host has 8 to choose from and then select either sitcom soap or drama and name the year in which a show from that category started airing the host has 9 l7 and 5 respectively of each to choose from In how many ways can this game be played Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 35 Counting Anagrams For us an anagram of a word is any rearrangement of the letters whether it makes sense in English or not For example the following are anagrams of STAR ARTS RATS TARS But so are STRA SART SATR SRAT SRTA etc We are interested in the question of how many anagrams there are of any given word Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 36 How Many Anagrams TO TOE TOES TONES TONERS ATONERS Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting TSP 37 Handout 1 What Patterns do you See The Game with 3 People The Game with 4 People The Game with 5 People 000 0000 00000 001 0001 00001 010 0010 00010 011 0011 00011 100 0100 00100 101 0101 00101 110 0110 00110 111 0111 00111 1000 01000 1001 01001 1010 01010 1011 01011 1100 01100 1101 01101 1110 01110 1111 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting H0 1 Handout 2 Some Counting Problems 1 A classroom has 12 boys and 14 girls and the teacher wants to select one boy and one girl to be class representatives to the Spring Fling committee ln how many ways can the teacher make her selection 2 A multiple choice quiz has 5 questions and 4 choices for each question How many ways are there for a student to answer the questions on this quiz 3 Dagwood is exercising great restraint in making a sandwich He is going to use only one kind of meat one kind of cheese one topping and one kind of bread The meat choices are ham salami bologna chicken roll or turkey the cheese he selects from American Swiss or provolone the topping he selects from mustard mayonnaise butter pickles or pepper the bread is either rye or pumpernickel How many sandwiches are possible 4 A preacher gave 33 sermons in 2000 41 sermons in 2001 and 37 sermons in 2002 He wants to reuse a sermon from a previous year this Sunday In how many ways can he do this 5 How many different ways are there to stack the blocks shown to the right 6 How many ways are there to build a stack of blocks from those shown in problem 5 where the stack can have any size 7 In the game of Canaps a gambler rolls either two or three dice of different colors and wins or loses depending on the outcome How many outcomes are possible 8 The host of a new game show is explaining the rules The contestant can select either star or year If she selects star then she has to name the star of a certain sitcom and the host has 20 sitcoms to select from If she selects year then she has to name the year in which a certain movie won an academy award the host has 8 to choose from and then select either sitcom soap or drama and name the year in which a show from that category started airing the host has 9 17 and 5 respectively of each to choose from In how many ways can this game be played Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting H0 2 Exercises Introduction to Counting Warmup Problems 1 How many ways are there to arrange the letters of the word quotLOVEquot 2 How many ways are there to make a 3 letter codeword from the letters of the word quotAEGILOPSquot quotAegilopsquot is the longest word in the English language with all letters in alphabetical order 3 How many ways are there to select three letters from the letters of the word A quotAEGILOPSquot I I 4 How many ways are there to walk from A to B on the grid to the right without I I B backtracking that is moving only south and east Presentation Problems 5 How many 10 digit numbers are there which don t use any digit more than once where no odd digit ever follows an even digit and where the quot4 and the quot5 are next to each other 6 Pappy s Pizza offers seven different toppings for their pizzas How many different ways are there to make a pizza including plain and the works 7 Consider the following variation on the quotStanding Bosses game Line up some players sitting in chairs facing the class then iterate The boss is the second to rightmost sitting player The boss s job is to stand up and to tell all standing players to his right to sit down The game is repeated for as long as possible For example with 3 players the game goes like 000 gt 010 gt 100 gt 110 and game over a The game with 3 players had 4 positions altogether How many positions does the game with 4 players have altogether b How many positions do the games with 1 2 and 5 players have c How many positions does the game with n players have 8 Consider the following variation on the quotStanding Bosses game Line up some players sitting in chairs facing the class then iterate The boss is the rightmost sitting player who does not have a person standing to his immediate left The boss s job is to stand up and to tell all standing players to his right to sit down The game is repeated for as long as possible For example with 3 players the game goes like 000 gt 001 gt 010 gt 100 gt 101 and game over a The game with 3 players had 5 positions altogether How many positions does the game with 4 players have altogether b How many positions do the games with 1 2 and 5 players have c How many positions does the game with 15 players have Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting EX 1 9 For each of the following words make a tree diagram showing all of that words anagrams a b BOX c BOO d BOON e NOON f NOONE g NOOSE For each of these words give the number of anagrams 10 In the game of Spiroletto a single die is tossed and then a coin is tossed that number of times shown by the die The player wins a dollar for each Heads that appears a How many game plays are possible including the outcome for the die and coin tosses b What if it were an 8 sided die with the numbers 1 8 on its faces c What if it were an n sided die with the numbers 1 n on its faces 11 Bob is a subset lister and Sam is an arrangement selecter Bob is given a set of size n and has to make a list in some order of all subsets of that set Sam is given a word with n distinct letters and has to give some selection of anagrams of that word a In how many ways can Bill and Sam do their jobs for n 0 1 2 3 and 4 b For large values of n whose job can be done in more ways For this problem you may wish to use logs and consider Stirling s approximation n z n e 2739E n Extension Problems 12 How many ways are there to walk from A to B on the figure below without backtracking 13 Consider the following variation on the quotStanding Bosses game Line up some players sitting in chairs facing the class then iterate The boss is the person to the left of the leftmost sitting player unless the leftmost sitting player is the leftmost player in which case the boss is the rightmost player The boss s job is to stand up and to tell all standing players to sit down The game is repeated for as long as possible How many positions does the game with n players have 14 Suppose we have some variant of the standing bosses game with the following properties a There is some unique start position b A position consists of a row of players fixed in number each either sitting or standing c There is a rule which at each step determines the next position from the current position alone without using any randomness or any outside input Prove that such a game on n players must either continue indefinitely or stop within 2quot Steps Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting EX 2 Discrete Math Resource Book on Introduction to Counting Workshop Outline Introduction to Counting I Opener 7 Standing Bosses A Start with 8 players 1 See what happens 2 Taking too long B Try 3 players Count steps C Try 4 players Count steps D Discussion of some patterns E There is a bijection between the set of 0 1 strings of length n and the subsets of a set with n elements F Two proofs that the standing boss sequence encodes all 0 1 strings of length n 1 They encode the numbers from 0 to 2 7 1 each exactly once in binary 2 By induction 3 Since there are 2 0 1 strings of length n we know there are that many steps in the standing bosses game and that many subsets of a set of size n H Introduction to Counting A First of all there may be many different degrees of prior skill present Please be understanding of this and adjust your participation accordingly B Multiplication rule 1 Counting all the binary strings of length n a Tree Diagram as motivation b Using the multiplication rule 2 Practice with other examples a Distribute handout C Addition rule 1 Contrast with multiplication rule 2 Distribute handout with mixed examples of when to add andor multiply D Number of arrangements of n distinct objects 1 Factorial Copyright 2004 7 Discrete Teaching by Hochberg and DeBellis Introduction to Counting RES 1 Complexity of Binary Search start 1 end n while start lt end middle start end 2 if s gt amxd then start middle 1 else end middle 71 k Each pass through the body of the while loop takes constant unit time ifs astart location start else location The question is How many times will this while loop be executed C onstant time Complexity of Binary Search P Calculate the number of times the while loop will be execute PEach pass through the while loop decreases the size of the range by at least half P So the question is gt Given an integer n how many times does it need to be cut in half before it reaches or goes below 1 P That is which of the following will rst be lt l gt n2 n4 n8 n16 n2k Complexity of Binary Search Logarithmic Time Complexity is Fast PThat is which of the following will rst be lt l gt n2 n4 n8 n16 n2k PWe solve the equation nZk lt l and get k gt logzn P So if we set k floan l then we know that after that many iterations of the while loop we will have found our item or concluded that it was not in the list POur analysis shows that n 1 3909 binary search can be done in 2 n 0 1 4 5 3 25 time proportionalto the log m 4 m 100 1 ofthe number ofitems 1n the 20 5 0 400 1048576 list 50 0 5 2500 1 1E 100 7 100 10000 13930 PThlS IS considered very fast 200 8 2 0 40000 1 6960 500 9 500 250000 err when compared to linear or 1000 m 1000 Ems err polynomial algorithms 2000 M 2000 4E06 err 5000 13 5000 3E07 err PThe table to the right compares the number of operations that need to be performed for algorithms of various time complexities An Algorithm to Test onetooneness P TESTPAIRS PSupposef A H B is a function andA and B are finite sets PFor each element a ofA compute b a and then check for each element a EA a a whether fa b gt In nite time we will check all pairs gt Each checking is a straightforward comparison gt If the answer is ever yes then the function is not 11 gt Otherwise the function is 11 P Aren t you wondering what the time complexity of this algorithm is Time Complexity of TESTPAIRS PWe have to consider A elements PFor each of those we need to compare its function value with that of lA 7 1 other elements PFor a total time of lAKlA 7 1 steps PWhich is 00A gt This is considered a quadratic algorithm in the size of A gt Note that the size ofB does not affect the speed of the algorithm PCan we do better Can you suggest another algorithm Another Algorithm to Test 11 Complexity of COLORRAN GE P COLORRAN GE PFor each element a of A color a blue to show that we ve been there already PIf during this process we try to color an element blue which is already blue then the function is not ll PBut if that never happens then the function is 11 P Again I can see that you are wondering what the time complexity of this algorithm is PWe do something once for each element ofA and that something takes constant time PIn the worst case that is the case that makes our algorithm run the longest we have to scan through all of A which will take lA steps PSO our algorithm will run in QUAD steps gt So our algorithm is linear in the size ofA gt Note again that B does not affect the running time gt Is this faster or slower than TESTPAIRS

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.