CS5002 Discrete Structures Profs. Amor-Tijani and Rachlin Fall 2021 December 8, 2021
CS52002 Practice Problems
Instructions (for final 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. 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.
3. 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 this isn’t clear and obvious you won’t get full credit for your response.
4. The exam is worth 100 total points. The points for each problemn and sub-problem are provided.
5. 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.
6. 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.
7. The exam window starts at 1:35pm ET/Boston and all exams must be received by 9:15pm ET/Boston. Once started you will have 3 hours and 15 minutes to complete the exam AND submit your exam to gradescope.
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:
Problem 1 : Number Representations
1. Convert F 3A16 to binary (base 2).
2. Convert 1011101104 (base 4) to hexadecimal (base 16).
Problem 2 : Logic
Use rules of logical equivalence to show that (p ∧ q ∧ r) ∨ ¬(¬p ∨ ¬q ∨ r) ≡ (p ∧ q). Indicate when using the Distributive, Double Negative, or De Morgan’s Law.
Problem 3: Sets
Fifty (50) fans of the Star Wars movie franchise were asked which droids they liked. Specifically, they were asked if they liked C-3PO, R2-D2, and/or BB-8. (They could say they liked more than one.)
• 2 fans said they didn’t like any of these droids.
• Everyone who liked C-3PO also liked R2-D2.
• Everyone who liked R2-D2 also liked BB-8.
• Three times as many fans liked BB-8 as liked R2-D2. • 10 fans liked all three droids.
How many fans liked each droid? Explain your answer.
Problem 4: Counting
1. A grocery store has 5 apples, 4 bananas, and 3 pears on the shelf. Assume the apples are indistinguishable as are the bananas and pears. How many ways are there to purchase exactly 4 pieces of fruit? (For example, you might purchase 2 apples, 1 pear, and 1 banana, or 1 apple and 3 pears, etc.)
2. How many ways are there to arrange the six digits 012345 so that no two adjacent digits add up to 5?
Problem 5: Probability
1. A sock drawer contains 4 white socks and 4 black socks and 4 tan socks. What is the probability that if two socks are randomly drawn (without replacement) they will form a matching pair? Reduce your answer to a simple fraction.
2. What is the minimum number of socks that one would have to draw (without replacement) to be certain of having at least two matching pairs? Explain your answer and state the principle underlying your argument.
Problem 5b: More Probability
A jar contains 3 red balls and 7 blue balls.
i. If a ball is picked at random, what is the probability that this ball is blue?
ii. If two balls are taken out of the jar at random (without replacement), what is the probability that they are of different colors?
iii. If three balls are taken out at random (without replacement), what is the probability that they are all of the same color?
Problem 5c: More Probability
i. What is the probability, if a die is rolled five times, that only two different values appear?
ii. Which is more likely, rolling an 8 when two dice are rolled, or rolling an 8 when three dice are rolled?
Problem 5d: Conditional Probability
We are given 5 cards. 3 of the cards are black and they are numbered 1, 2, 3. The other two cards are red and they are numbered 1, 2.
We pick 2 random cards.
i. What is the probability that both cards are red?
ii. What is the probability that both cards are red, if we know that at least one of them is red?
iii. What is the probability that both cards are red, if we know that one of them is red card number 1?
Problem 5e: More Conditional Probability
Punxsutawney Phil is a weather predicting groundhog. On February 2nd, Phil makes a predic- tion about how soon spring comes (when weather warms up) by either observing his shadow or not each. Let’s make the following assumptions:
i. If flowers bloom in April, Phil observes his shadow 30% of the time.
ii. if flowers do not bloom in April, Phil observes his shadow 80% of the time.
iii. Flowers bloom in April only 15% of the time, whether or not Phil’s shadow is observed.
Given that Phil has not seen his Shadow this year, whats the probability that the flowers will bloom?
Problem 6: Expectation
A standard 52-card deck of cards contains 4 suits (Hearts, Diamonds, Clubs, and Spades). Each suit contains 13 ranks (Ace,2,3,4,5,6,7,8,9,10,Jack,Queen,King). The Jack, Queen, and King are face cards. Two such decks are combined and shuffled together forming a 104-card deck from which you are dealt exactly five cards. How many cards would you expect to receive that are Clubs, or face cards, or both?
Problem 7: Algorithms For the first two parts, your answer should be a single integer.
i. How many steps (compares) does it take, in the worst case, to search for a given element in
an unordered array of length 512?
ii. How many steps (compares) does Binary Search take, in the worst case, to search for a given
element in an ordered array of length 512?
iii. If algorithms A1, A2, A3, A4, A5, A6 run on a list of length n in times log2 n, n, (log2n)3, n3, 2n, and n!, miliseconds respectively, what is the length of the largest list that each of them could complete a run on in 1 second (1000 miliseconds)?
Your answers should be integers or integer powers of 2 or 10.
A1 A2 A3 A4 A5 A6
(log2 n)3 n3
Length of List
Problem 8: Mathematical Induction
Prove by mathematical induction:
n n·(n−1)·(n+1)
(i − 1) · i = 3
Problem 9: Sequences and Recurrences
i. Using the iterative, substitution method, find a closed-form formula for the recurrence:
T(n)=T(n2)+n;T(1)=1. Youmayassumethatnisapowerof2.
ii. Using the iterative / substitution method, find a closed form formula for the recurrence:
T (n) = 2T (n − 1) + 1; T (0) = 0.
iii. Prove your formula for the second recurrence by induction for all integers n ≥ 1.
iv. Use two methods to find a closed form formula for the sequence: an = −42, −39, −34, −27, −18, …. The first term is a1.
Problem 10: Graphs Consider the graph with vertex set {a, b, c, d, e, f, g} and adjacency lists:
a→g→d→e b→g→d→e→c c→f→b d→a→f→b e→a→g→f→b f→d→e→c g→a→e→b
1. Draw this graph in the plane so that no two edges intersect, except at common end vertices.
2. Starting at vertex a traverse the graph by depth-first-search, processing the neighbors of each vertex in the order they appear on the adjacency list of that vertex (thus not in the alphabetical order). In your drawing, color the tree edges in red and next to each vertex write its place in the order in which the vertices are first visited (with a as 1).
3. Starting at vertex a traverse the graph by breadth-first-search, processing the neighbors of each vertex in the order they appear on the adjacency list of that vertex (thus not in the alphabetical order). In a fresh copy of your drawing of the graph, color the tree edges in blue and next to each vertex write its place in the order in which the vertices are first visited (with a as 1).
4. Give a spanning tree of the graph.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com