CS5002 Discrete Structures Prof. Rachlin Spring 2022 April 30, 2022
Instructions:
CS52002 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. The exam window opens on Saturday, April 30th at 12:00pm ET/Boston (Noon) and closes 12 hours later at 11:59pm ET/Boston. Once you begin your exam, you will have 4 hours to complete the exam AND submit your exam to gradescope. Therefore, be sure to START your exam before 8pm ET/Boston so that you have the full four hours to complete the exam.
3. Discussing the exam with others is strictly prohibited. Working together on the solutions 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. A solution is not enough. You must show how you derived your solution.
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 extra time solely for the purpose of uploading your exam. Exams emailed to instructors will be penalized 5 percent, so be sure to give yourself enough time to submit your exam! Exams received via email more than a few minutes beyond the 11:59pm will not be graded.
The following may be written out by hand if you are unable to print the coversheet.
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 [20 pts (5, 10, 5)]: Logic Circuits
1. Draw the circuit corresponding to the following expression. (Do not simplify your expression
or the corresponding circuit.) ¬(¬(p ∨ ¬q ∨ r) ∨ (q ∧ ¬r))
2. Now use the laws of logical equivalence to simplify your expression so that negations, where ever they occur, appear before single variables only. Show every step and state the Law of Logical Equivalence you are using at each step.
3. Draw the simplified circuit corresponding to your simplified expression. Any unneeded inputs can be ignored in your drawing.
Section 2 [20 pts (3, 7, 10)]: Counting
1. Given the set of nine letters ABCDEFGHI to choose from, how many sequences of length 4 are possible assuming that letters can be repeated? For example, some possible sequences are: BCDE, AAAA, FGFH, and BABB. A simple expression suffices for an answer.
2. Given the set of nine letters ABCDEFGHI to choose from, how many sequences of length 4 contain exactly THREE different letters? For example, some valid sequences are: ABBI, BEEF, and BAHA.
3. In a word-find puzzle your task is to find words along a straight line going forwards or backwards, up or down, or diagonally. If we arrange the 9 letters ABCDEFGHI into a 3 × 3 word-find puzzle, how many puzzles do NOT contain the word BAD? For this problem, rotations of the 3 × 3 word-find puzzle would constitute a different puzzle.
Section 3[20 pts (5 points each)]: Probability
1. Hui classifies 90 percent of the emails she receives as spam. One-half of those emails marked as spam contain word FREE. Only 20 percent of the emails that are not spam contain the word FREE. If a new email arrives containing the word FREE, what is the probabability that the email is actually spam? Reduce your answer to a simple fraction (xy where x and y are non-negative integers.)
2. A city consists of 9 intersections laid out in a 3×3 grid as shown below. If an intersection is selected at random, what is the expected number of adjacent intersections? Two intersections are adjacent if they are directly connected via a street.
3. If two distinct intersections are chosen at random from the city above, what is the probability that they would be adjacent?
4. If 7 distinct intersections are chosen at random from the city diagrammed above, how many of those interactions would we expect to be corner intersections? Reduce your answer to a simple fraction (xy where x and y are non-negative integers.)
Section 4 [20 pts (5 points each)]: Sequences and Recurrences Let Mn = Mn−1 + 3n − 1; M1 = 2. (This is our recursive definition.)
1. List the first five values in the sequence, M1 to M5
2. Derive a closed form formula for Mn using any method you like.
3. Is the sequence linear, quadratic, cubic, geometric, or something else? Justify your answer.
4. Prove that the closed-form formula follows from the recursive definition using Mathematical Induction. Clearly state your inductive hypothesis.
Section 5 [20 pts (10, 5, 5)] : Graphs
1. For the 9-vertex graph below, highlight the edges that would be traversed using Depth-First Search (left) and Breadth-First Search (right) starting at the corner vertex labeled S. Add a number, 1 to 9 next to each edge to show the order in which each edge is traversed. In cases of possible ambiguity, the vertices should be processed alphabetically.
2. Draw the adjacency-list representation of the above graph.
3. If a graph were laid out as an n × n array (extending the 3 × 3 grid layout in the above problem), how many edges would it have and what would be the total sum of the vertex degrees? State your answers as two closed-form formulas on n (one for the number of edges and one for the total sum of the vertex degrees.) Clearly explain how you derived the formulas and verify that your formulas are correct for the 3 × 3 grid layout in the above problem.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com