Shared Flashcard Set

Details

Counting (INCOMPLETE)
http://courses.ics.hawaii.edu/ReviewICS141/modules/counting/
11
Computer Science
Undergraduate 2
02/08/2019

Additional Computer Science Flashcards

 


 

Cards

Term
Topic: Counting

A multiple-choice test contains 10 questions. There are four possible answers for each question.

In how many ways can a student answer the questions on the test if the student answers every question?
Definition
Here, there are 4 choices per question, and 10 questions.
Choosing an answer for each question is a sequential task, so there are 4 × 4 × 4 × 4 × 4 × 4 × 4 × 4 × 4 × 4 = 4^10 ways to answer.
Term
Topic: Counting

A multiple-choice test contains 10 questions. There are four possible answers for each question.

In how many ways can a student answer the questions on the test if the student can leave answers blank?
Definition
Here, there are 5 choices per question (a, b, c, d and N/A), and 10 questions.
Choosing an answer for each question is a sequential task, so there are 5^10 ways to answer.
Term
Topic: Counting

How many strings of three decimal digits do not contain the same digit three times?
Definition
There are 103 = 1000 decimal strings with 3 digits, and there are 10 of them containing three equal digits: 000, 111, . . . , 999. Therefore, there are 1000 − 10 = 990 strings that do not contain the same digit three times.
Term
Topic: Counting

How many strings of three digits begin with an odd number?
Definition
There are 5 odd digits, therefore we have 5 × 10 × 10 = 500 strings of three decimal digits beginning with an odd digit.
Term
Topic: Counting

Show that among any group of five (not necessarily consecutive) integers, there are two with the same remainder when divided by 4.
Definition
There are four possible remainders when an integer is divided by 4: 0, 1, 2, or 3 (these are pigeonholes). Therefore, by the pigeonhole principle at least two (= ceiling(5/4)) of the five given remainders (these are pigeons) must be the same.
Term
Topic: Counting

There are 38 different time periods during which classes at a university can be scheduled. If there are 677 different classes, how many different rooms will be needed?
Definition
The 38 time periods are the pigeonholes, and the 677 classes are the pigeons. By the generalized pigeonhole principle there is at least one time period in which at least ceiling(677/38) = 18 classes are meeting. Since each class must meet in a different room, we need 18 rooms.
Term
Topic: Counting

List all the permutations of {a, b, c}.
Definition
This is a permutation and repeats are not allowed. Therefore, there are P(3, 3) = 3! 0! = 6 permutations, which are: (a, b, c) ; (a, c, b) ; (b, a, c) ; (b, c, a) ; (c, a, b) ; (c, b, a)
Term
Topic: Counting

Find the number of 5-permutations of a set with nine elements.
Definition
P(n, r) where n = 9 and r = 5. P(9, 5) = 9!/(9 − 5)! = 9!/4! = 15,120.
Term
Topic: Counting

How many bit strings of length 10 contain exactly four 1s?
Definition
This is just asking us to choose 4 out of 10 slots to place 1’s in. C(10, 4) = 10!/(4! × 6!) = (10 × 9 × 8 × 7)/4! = 210.
Term
Topic: Counting

How many 5 cards can be drawn from a deck of 52 cards?
Definition
C(52, 5) = 52!/[5!(52-5)!] = 52!/(5!*47!)
Term
Topic: Counting

How many ways can one draw 3 diamonds and 2 clubs from a deck of 52 cards?
Definition
# of ways to draw 3 diamonds: C(13, 3) = 13!/[3!(13-3)!] = 13!/(3!*10!) = 13*11*2 = 286

# of ways to draw 2 clubs: C(13, 2) = 13!/[2!(13-2)!] = 13!/(2!*11!) = 13*6 = 78

286*78 = 22308 total ways/combinations
Supporting users have an ad free experience!