CS5002 Discrete Structures Prof. Rachlin Spring 2022 April 13, 2022
Homework #10
Assigned: Wednesday April 13, 2022
Due: Tuesday April 19, 2022 @ 11:59pm ET/Boston −5%: Wednesday April 20, 2022 @ 11:59pm ET/Boston −10%: Thursday April 21, 2022 @ 11:59pm ET/Boston
Copyright By PowCoder代写 加微信 powcoder
Instructions:
• Homework is due on Tuesday at 11:59pm ET/Boston. Homeworks received up to 24 hours late (11:59pm ET on Wednesday) will be penalized 5 percent. Homeworks received up to 48 hours late (11:59pm ET on Thursday) will be penalized 10 percent. NO assignment will be accepted after 48 hours.
• We expect that you will study with friends and fellow students and you are welcome to verbally discuss the problems openly. However, your solution writeup should be the product of your own mind and expressed in your own words. The TAs and I will be available to answer specific questions or address speific points of confusion but we will not verify your answers prior to submission.
• Assignments should be typed using Word or LateX, or hand-written neatly. When submitting to gradescope be sure to indicate the page containing your answer to each problem, so that the TAs don’t have to search for your solution.
• To get full credit, explain your solution and show each step of the solution process! Simply writing down a correct answer will receive little or no credit. We don’t need your scratch work or draft solutions, only your final solution explaining your step-by-step reasoning. Recommendation: try to imagine you need to explain your solution to someone not in this class.
• If you think the TA made a clerical error in grading your assignment, you may submit a regrade request on Gradescope within 1 week of the publication of the grades. After 1 week of publication, ALL GRADES ARE FINAL.
Problem 1 [40 points (10 points each)] Branching Patterns
Consider the following figure where an denotes the number of matches in a growing pattern and n ≥ 1.
1. What are the first five values of the sequence?
a2 =3+3·2=9
a3 =3+3·2+3·2·2=21
Continuing the pattern of doubling the end points: a4 =3+3·2+3·22 +3·23 =45
a5 =3+3·2+3·22 +3·23 +3·24 =93
2. Give the recursive definition for the value of an, that is, a formula for an in terms of an−1. Don’t forget to also state the base case!
Solution: an =an−1+3·2n−1;a1 =3 3. Find a closed-form formula for an.
Solution: Full credit for immediately recognizing that this is a multiple of a geometric series: n−1
an =3(20 +21 +22 +…)=3(1+2+4+8+…)=3· 2k =3·(2n −1) k=0
Note that the sum goes from k = 0 to k = n−1 because we are summing n terms. This could be derived by iteration:
an =an−1 +3·2n−1
an−1 = an−2 + 3 · 2n−2, So
an =an−2 +3·2n−2 +3·2n−1
an−2 = an−3 + 3 · 2n−3, So
an =an−3 +3·2n−3 +3·2n−2 +3·2n−1
an =an−k +3·2n−k +3·2n−k+1 +…+3·2n−1 n−k=1whenk=n−1anda1 =3givingus an =3+3·2+3·22 +…+3·2n−1
an =3(20+21+22+…+2n−1)=3·(2n−1)asbefore.
4. Using your recursive definition from sub-problem (2), prove that your closed-form formula is
correct (∀n ≥ 1) using a proof by induction.
Solution: We want to prove (by induction): ∀n ≥ 1 : an = 3 · (2n − 1). Basecase(n=1): a1 =3·(21−1)=3·1=3.
Inductive case:
a) Assume ak = 3 · (2k − 1) for some k > 1. (inductive hypothesis.)
b) We want to show: ak+1 = 3 · (2k+1 − 1). From our recurrence formula, ak+1 = ak + 3 · 2k and by our inductive hypothesis: ak+1 = 3·(2k −1)+3·2k = 3·2k +3·2k −3 = 3·(2k+1 −1). Therefore by the principle of mathematical induction, our closed-form formula is proven (∀n ≥ 1).
Problem 2 [40 points]: Sorting
An array contains the following sequence: 8, 14, 99, 0, 1, 7, 19, 4. We wish to sort the array in DESCENDING order from LARGEST to SMALLEST value. For both (a) INSERTION sort and (b) SELECTION sort, indicate for each iteration:
1. The state of the array (after a number is moved into its correct position) 2. The number of comparisons performed for that iteration
3. The number of swaps performed for that iteration
Insertion sort:
Selection sort:
A 8,14,99,0,1,7,19,4 14,8,99,0,1,7,19,4 99,14,8,0,1,7,19,4 99,14,8,0,1,7,19,4 99,14,8,1,0,7,19,4 99,14,8,7,1,0,19,4 99,19,14,8,7,1,0,4 99,19,14,8,7,4,1,0 A
comparisons swaps – –
comparisons swaps 8,14,99,0,1,7,19,4 – – 99,14,8,0,1,7,19,4 7 1 99,19,8,0,1,7,14,4 6 1 99,19,14,0,1,7,8,4 5 1 99,19,14,8,1,7,0,4 4 1 99,19,14,8,7,1,0,4 3 1 99,19,14,8,7,4,0,1 2 1 99,19,14,8,7,4,1,0 1 1
Problem 3 [20 pts]: MergeSort
Show me that you understand how MergeSort works by filling in all the boxes and drawing all
the remaining arrows in the figure below. Again, we are sorting in DESCENDING order using the same starting sequence from problem 3.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com