Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: YSYY66

CS5002 Discrete Structures

Spring 2022

C S 52002 M i d t e r m E xa m

S ec t i on 1 [25 pts (5 each)] : N u m b e r R e p r ese n t a t i on s

1. Convert BB816 to octal. (Show your work.)

2. Convert D216 to binary. Now, treating the number as an 8-bit two’s-complement number, convert to decimal (base-10).

3. The droid C3PO from Star Wars knows 6 million forms of communication. We assign each form of communication a unique identiﬁer in the form of a ﬁxed-length unsigned binary number. (By ﬁxed-length we mean that the number of bits allocated to each identiﬁer is the same.) How many bits must be allocated for each identiﬁer? Give your answer in the form of an integer, and explain.

4. 215 = 32, 768. How many numbers between 0 and 215 are the sum of exactly three powers of 8? Each power must be a natural number. Natural numbers are the non-negative integers (0, 1, 2, 3, ...). The powers need not be distict. For example, 10 is one such number because 10 = 81 + 80 + 80 = 8 + 1 + 1 and 521 is another such number because 521 = 83 + 81 + 80 = 512 + 8 + 1. Reduce your answer to an integer and explain your answer.

5. Droids on the planet Tatooine perform calculations in base-6. What is the largest base-6 number that can be represented with three distinct digits? (Each digit in your base-6 number must be diﬀerent.) Convert your answer to decimal (base-10).

S ec t i on 2 [25 pts] : Log i c

Given the domains m e MOVIES and c e CHARACTERS and the following predicates:

● SW(m): m is a Star Wars movie.

● A(c, m): c is a character who appears in the movie m

● D(c): c is a Droid.

● L(m): I liked m.

● Q(c, q): c says q (c is quoted as saying q.)

● jarjar is the character Jar Jar Binks

● bad is the quote: ”I’ve got a bad feeling about this!”

1. Express the following English sentence with predicate logic using Existential and/or Universal quantiﬁers: I didn’t like any Star Wars movie if Jar Jar Binks was in it.

2. Express the following English sentence with predicate logic using Existential and/or Universal quantiﬁers: At least two droids appear in every Star Wars movie. You may use the notation x = y and x y as needed.

3. Express the following English sentence with predicate logic using Existential and/or Universal quantiﬁers: In every Star Wars movie, some character in the movie says ”I’ve got a bad feeling about this!”.

4. Negate your expression from sub-problem (3). Now simplify the logical expression using the laws of logical equivalence. To simplify, eliminate implications (if any) and negations in front of quantiﬁers. Negations should appear only in front of single predicates. Show each step. Cite the law of logical equivalence you are applying with each step.

5. Convert your ﬁnal simpliﬁed expression from the previous problem back into English.

Sec ti on 3 [25 pts (15,10)] : Se t s

1. In this problem A = {R2D2, C3PO, BB8} and B = {BB8, R5D4}. IAI denotes the cardinal- ity (number of members) of the set A. Answer each question with an integer or an expression involving exponents. You do not need to show each step.

i. IA × BI =?

ii. IA - BI =?

iii. I(A - B) n (B - A)I =?

i v . Ip(A△B)I =?

v . I{x : x e p(A u B) A IxI = 2}I =?

2. Some rebel pilots were surveyed to determine what they thought of diﬀerent star ﬁghters. The three kinds of star ﬁghters are the X-Wing, the Y-Wing, and Tie Fighters.

● Every pilot liked at least one kind of star ﬁghter

● 1 liked all three. (The force is strong with this pilot!)

● 1 liked X-Wings and Y-Wings

● 2 liked X-Wings and Tie Fighters

● 3 liked Y-Wings and Tie Fighters

● 5 liked X-Wings

● 8 liked Y-Wings

● 13 liked Tie Fighters.

Use the Principle of Inclusion and Exclusion to determine how many pilots answered the survey. Draw a Venn Diagram depicting the above data. Note: when we say, for example, that n pilots liked a particular kind of Star Fighter, it means they might have liked other types as well. For example, some of the 13 pilots that like Tie Fighters liked X-Wings, Y-Wings or maybe both.

Sec ti on 4 [25 pts (5 each)] : C oun ti ng

1. Suppose droids in the Star Wars universe follow the following naming conventions:

● Names must be 3-5 characters including uppercase letters and digits. (No dashes.)

● All names must start with a letter and contain at least 1 digit.

How many droid names are possible? You can leave your answer as an expression as long as you clearly explain each term in the expression. Some valid names include BB8, R2D2, C3PO, and H2SO4.

2. Seventeen Jedi are ﬁghting for their lives in an arena. Each Jedi uses a light saber with one of 4 colors.

(a) Explain why ﬁve or more Jedi must be using the same color light saber. What mathe-

matical principle are you invoking in your explanation?

(b) How many Jedi would there need to be in the arena in order to guarantee that seven or

more Jedi are using the same color light saber?

3. Nine Star Wars movies make up the three Star Wars trilogies:

(a) Episodes 1-3 (The prequels with Jar Jar Binks)

(b) Episodes 4-6 (The originals starring Mark Hamill as Luke Skywalker)

(c) Episodes 7-9 (The ones starring Daisy Ridley as Rey)

My weekend movie marathon consists of an ordered sequence of ﬁve distinct movies selected from these nine. How many movie marathons are possible? (The same ﬁve movies watched in a diﬀerence sequence constitute a diﬀerent marathon.)

4. What if each marathon consists of four to six movies and each marthon is distinguished by the particular movies I select and not the order in which I watch them. Furthermore, I’m allowed to pick the same movie more than once. Now how many movie marathons are possible?

5. What if my movie marathon consists of exactly ﬁve distinct movies: two movies from one of the trilogies, 2 movies from a 2nd trilogy, and 1 movie from a 3rd. The movies can be watched in whatever order I choose and the same ﬁve movies watched in a diﬀerent order constitute a diﬀerent marathon. Now how many movie marathons are possible?