March 9, 2022
CS52002 Midterm Exam
Instructions (for midterm exam):
1. The exam is open book and open notes. You may use a calculator but it should not be necessary.
Copyright By PowCoder代写 加微信 powcoder
2. The exam window starts at 12:00pm ET/Boston (Noon) and all exams must be received by 11:59pm ET/Boston. Once started you will have 3 hours and 15 minutes to complete the exam AND submit your exam to gradescope.
3. Discussing the exam with others is strictly prohibited. Giving or receiving help from fellow students earns all parties involved an automatic F for the class. Do not test us on this.
4. Unless otherwise specified, you may leave your answer in the form of a fraction or mathematical expression that clearly shows your thought process. For credit you must show your scratch work and clearly explain how you got to your final answer. If your expression isn’t clear or obvious you won’t earn full credit.
5. If you have a question, post a PRIVATE question on Piazza. An instructor will respond as soon as possible.
6. When submitting your exam you must specify, for each problem, the page or pages where the solution to that problem is to be found. If we can’t see your solution you will not receive credit for the problem.
7. You have been granted an extra 15 minutes solely for the purpose of uploading your exam. Exams emailed to instructors will receive a 5 percent penalty, so be sure to give yourself enough time to submit your exam! Exams received via email more than a few minutes beyond the deadline will not be graded.
8. May the force be with you!
PRINT FULL NAME: STUDENT ID: I have
read the instructions above and understand that I may not discuss the exam with other students at any time. SIGN HERE:
Section 1 [25 pts (5 each)]: Number Representations 1. Convert BB816 to octal. (Show your work.)
BB816 =11×162 +11×161 +8×160 = 11 × 256 + 11 × 16 + 8 × 1
= 2816 + 176 + 8
3000/8 → Remainder = 0 = 375/8 → Remainder = 7 = 46/8 → Remainder = 6 = 5/8 → Remainder = 5
Therefore,BB816 =300010 =56708
2. Convert D216 to binary. Now, treating the number as an 8-bit two’s-complement number, convert to decimal (base-10).
Solution: D216 = 1101 00102
Conversion of negative 8-bit two’s complement number:
i) Flip the bits: 11010010 → 00101101
ii) Add 1: 00101101 + 1 = 00101110
iii) Convert to decimal and add negative sign: 00101110 = 46 → −46
3. The droid C3PO from Star Wars knows 6 million forms of communication. We assign each form of communication a unique identifier in the form of a fixed-length unsigned binary number. (By fixed-length we mean that the number of bits allocated to each identifier is the same.) How many bits must be allocated for each identifier? Give your answer in the form of an integer, and explain.
Assume each form of communication is represented by a unique number. The biggest number that can be represented by n-bits is given by 2n − 1. So the largest value that can be represented by 22 bits is 222 − 1 = 4, 194, 303, and the largest one for 23 bits is 223 − 1 = 8, 388, 607. We can estimate this by observing that 222 = 220 ∗ 22, which is approximately 4 million, and 223 = 220 ∗ 23, which is approximately 8 million.
Since 222 − 1 < 6 million < 223 − 1, 23 bits would be needed to have a unique representation i.e, a unique identifier for each of the 6 million forms of communication.
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+1and521isanothersuchnumberbecause521=83+81+80 = 512 + 8 + 1. Reduce your answer to an integer and explain your answer.
Since we need to count numbers between 0 and 215 that are a sum of three powers of 8, the maximum power of 8 we can have is 84. This is because 215 = (23)5 = 85, and having 85 as one of the powers of 8 would result in a sum that is greater that 215.
Now there are five powers of 8 to choose from, which are 84, 83, 82, 81, 80. Three of them are to be selected and each of them can be selected multiple times (the problem says 81+80+80 =8+1+1=10isvalid).
This can be framed as a typical bins and balls problem where repetition is allowed.
The powers of 8 are assumed to be the bins and balls would be their selection. Thus, the
number of possibilities is given by n+k−1 where n = number of bins = 5, and k = number k
of balls = 3.
Therefore the number of numbers between 0 and 215 which are a sum of exactly
three powers of 8 are 5+3−1 = 7 = 35. 33
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 different.) Convert your answer to decimal (base-10).
The largest base-6 that can be represented with three distinct digits is 5436. 5436 = 5×62 +4×61 +3×60
= 5 × 36 + 4 × 6 + 3 × 1 = 180 + 24 + 3
Section 2 [25 pts]: Logic Given the domains m ∈ MOV IES and c ∈ 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 quantifiers: I didn’t like any Star Wars movie if Jar Jar Binks was in it.
Solution: ∀m : (SW (m) ∧ A(jarjar, m)) → ¬L(m)
2. Express the following English sentence with predicate logic using Existential and/or Universal quantifiers: At least two droids appear in every Star Wars movie. You may use the notation x = y and x ̸= y as needed.
Solution: ∀m∃x,y:D(x)∧D(y)∧x̸=y∧(SW(m)→(A(x,m)∧A(y,m)))
3. Express the following English sentence with predicate logic using Existential and/or Universal quantifiers: In every Star Wars movie, some character in the movie says ”I’ve got a bad feeling about this!”.
Solution: ∀m∃x : SW (m) → (A(x, m) ∧ Q(x, bad))
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 quantifiers. Negations should appear only in front of single predicates. Show each step. Cite the law of logical equivalence you are applying with each step.
¬∀m∃x : SW (m) → (A(x, m) ∧ Q(x, bad)) ∃m¬∃x : SW (m) → (A(x, m) ∧ Q(x, bad)) ∃m∀x : ¬[SW (m) → (A(x, m) ∧ Q(x, bad))] ∃m∀x : ¬[¬SW (m) ∨ (A(x, m) ∧ Q(x, bad)) ∃m∀x : ¬¬SW (m) ∧ ¬(A(x, m) ∧ Q(x, bad)) ∃m∀x : SW (m) ∧ ¬(A(x, m) ∧ Q(x, bad)) ∃m∀x : SW (m) ∧ (¬A(x, m) ∨ ¬Q(x, bad))
negate universal negate existential implication def.
DeMorgan’s double negative
DeMorgan’s
5. Convert your final simplified expression from the previous problem back into English.
”There exists a movie m such that, for all characters x, m is a Star Wars movie and either x is not in the movie m or x does not say ’I’ve got a bad feeling about this!’”.
Another valid translation is:
”No character in a Star Wars movie says ’I’ve got a bad feeling about this!’”
Section 3 [25 pts (15,10)]: Sets
1. In this problem A = {R2D2, C3P O, BB8} and B = {BB8, R5D4}. |A| 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. |A×B|=? Solution: 6
ii. |A−B|=? Solution: 2
iii. |(A−B)∩(B−A)|=? Solution: 0
iv. |P(A△B)| =? Solution: 8.
The power set of A△B is:
{∅, {R2D2}, {C3P O}, {R5D4}, {R2D2, C3P O}, {C3P O, R5D4}, {R2D2, R5D4}, ... ...{R2D2, C3P O, R5D4}}
v. |{x:x∈P(A∪B)∧|x|=2}|=? Solution: 6.
{x : x ∈ P(A ∪ B) ∧ |x| = 2} is equal to:
{{R2D2, BB8}, {C3P O, BB8}, {R5D4, BB8}, {R2D2, C3P O}, ... ...{C3P O, R5D4}, {R2D2, R5D4}}
2. Some rebel pilots were surveyed to determine what they thought of different star fighters. The three kinds of star fighters are the X-Wing, the Y-Wing, and Tie Fighters.
• Every pilot liked at least one kind of star fighter
• 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 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.
|XY T|=|X|+|Y|+|T|−|XY|−|XT|−|Y T|+|XY T|=5+8+13− 1 − 2 − 3 + 1 = 21
Section 4 [25 pts (5 each)]: Counting
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.
• 3 characters:
= first character is letter and other characters are letters or digits - all characters are letters
= 26×(26+10)2 −263
• 4 characters:
= first character is letter and other characters are letters or digits - all characters are letters
= 26×(26+10)3 −264
• 5 characters:
= first character is letter and other characters are letters or digits - all characters are letters
= 26×(26+10)4 −265
Total = 26 × (362 − 262) + 26 × (363 − 263) + 26 × (364 − 264)
2. Seventeen Jedi are fighting for their lives in an arena. Each Jedi uses a light saber with one of 4 colors.
(a) Explain why five 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?
(a) Pigeonhole Principle states that if N objects are placed in k boxes, then there must exist a box that contains ⌈N/k⌉ or more objects. Thus, given 17 Jedi and 4 colors, there exists a light saber of one color that is used by at least ⌈17/4⌉ = 5 Jedi.
(b) 6×4+1=25Jedi
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 as )
(c) Episodes 7-9 (The ones starring as Rey)
My weekend movie marathon consists of an ordered sequence of five distinct movies selected from these nine. How many movie marathons are possible? (The same five movies watched in a difference sequence constitute a different marathon.)
Solution: P (9, 5) = 15120
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?
Solution: The9moviechoicesarethebinsandtheselectedmovies(4or5or6)aretheballs. 9+4−1 + 9+5−1 + 9+6−1 = 4785
5. What if my movie marathon consists of exactly five 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 five movies watched in a different order constitute a different marathon. Now how many movie marathons are possible?
• choose the trilogy that one movie will be selected from: 3 1
• choose one movie from that trilogy: 3 1
• choose 2 movies from the other two trilogies: 3 × 3 22
• permute the five chosen movies: P (5, 5) = 5!
3 × 3 × 3 × 3 × 5! = 9720 1122
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com