CS代考 CS 344 – Spring 2022 Exam 1

CS 344 – Spring 2022 Exam 1
100 points total + 10 points EC
Instructions
Academic Integrity Policy You must complete this exam entirely alone. You may not discuss the exam with any students in the class, or with anyone outside the class.

Copyright By PowCoder代写 加微信 powcoder

The exam is open notes, so you can look at any files/videos posted on canvas and your own notes. You may also use either of the two books recom- mended for this course. You are not allowed to use any other sources, and in particular you are not allowed to use any online source.
Academic Integrity Statement You should type the following text on the first page of your midterm.
I have not discussed this exam with anyone except the professor and the TAs of CS 344. I have not used any online resources during the exam except for those accessible from the Canvass website.
What to Write
• On the first page write your full name, netID, and the academic in- tegrity statement above. Do not write anything else.
• Start each problem on a new page.
• Typed assignments receive 2 extra points.
• If your assignment is hand-written please write very legibly.
• Assignment should be submitted as a single PDF in the same way as a HW problem.
Skipping Problems Remember that if you skip a problem you get 25% credit. If you give an answer that is on the right track you will get more than 25% in partial credit, so don’t be afraid to attempt problems if you think

you know how to approach them. But keep in mind that if you simply don’t know the answer, writing a very wrong answer may get 0%.
The only exception is the extra credit problem: you do not get any credit for leaving that blank and it’s harder to get partial credit on that problem.
Suggestion: Leave the extra credit problem for last, as it is harder than the rest and worth fewer points.
The 344 Library: Throughout the test, any algorithm you design may use any of the functions or data structures we covered in class without ex- planation. E.g. you can just say “Do Select(A,k) in O(n) time”. You can use heaps and dictionaries freely.
Also, if you are analyzing a recurrence formula and the recurrence formula is one we have seen before in class or HW, you don’t have to re-solve it. You can just state the answer and say which algorithm from class has the same recurrence formula. For example, if your solution to a problem has recurrence formula T (n) ≤ T (n/2) + O(1) you can then say: “we know that T(n) = O(log(n)) because this is the same recurrence formula as binary search.”

1 Problem 1 (20 points total)
For both problems below, you can assume a base case of T (1) = T (2) = 1.
Part 1 (10 points) Say you had an algorithm with recurrence formula T (n) ≤ 81T (n/3) + n3 . Use a recursion tree (or recursion table) to solve for T (n). No need for induction on this one.
(10 points) Say you had an algorithm with recurrence formula T (n) ≤ 3T (n/2) + 4T (n/3) + n3. Use induction to show that T (n) = O(n3). No need for a recursion on this one – only induction.
Problem 2 (20 points)
Recall the Select(A,k) from class where we broke the array into chunks of size 5, found the median of each chunk, recursively computed the median of the medians and so on.
Let us say that we use a different algorithm where we break the array into chunks of size 17 rather than size 5. Other than that the algorithm is the same. So the algorithm is:
1. Break A into chunks of size 17
2. Compute the median of each chunk
3. Recursively compute the median of the medians (call it m)
4. Partition around m
5. Recurse to one side
What is the recurrence formula for this algorithm? That is, with chunks of size 5 we had recurrence formula T (n) ≤ T (n/5) + T (7n/10) + O(n). So what is the recurrence formula if we use chunks of size 17 instead? Make sure to explain why your recurrence formula is the correct one. As in class, you can assume that all elements of the array A are distinct (no duplicates).
NOTE: you do NOT need to prove that the recurrence solves to O(n). You do NOT need to write pseudocode for the algorithm. All you need to do is state the recurrence formula and explain why that is the recurrence formula. The explanation should be at the level of what we did in class to show that for chunks of size 5 the reccurence formula is T (n) ≤ T (n/5) + T (7n/10) + O(n).

3 Problem 3 (25 points)
Consider the following problem. We are given an array A of numbers with len(A) = n, and a parameter k < n. Duplicates in A are allowed. We say that A[i] = x is k-isolated if x does not appear in the previous k entries of the array. That is, A[i] is isolated if A[i] ̸= A[j] for every index j ∈ [i − k, i − 1]. Note in particular that we only look at previous entries: so if k = 2 and A = 1,1,2,3,1,8,1 then A[0] is k-isolated but A[1] is not. In more detail: A[1] and A[6] are not k-isolated, but every other index in this array A is k-isolated. Consider the problem FindIsolated(A,k), where the goal is to determine, for each A[i], whether it is k-isolated. Formally: • Input: a positive integer k, and an unsorted A with n numbers, some of them repeating. • Output: an array B of length n, where B[i] = Y if A[i] is k-isolated and B[i] = N if A[i] is NOT k-isolated. Example: if k = 3 and A = [1,2,5,1,6,2,8,2,4] then the algorithm should output B = [Y,Y,Y,N,Y,Y,Y,N,Y]. The Problem Write pseudocode for algorithm FindIsolated(A,k) that has running time O(n) time. Note that the running time must be O(n) even if k is very large. So e.g. even if k = √n, the running time of your algorithm should be O(n). In particular, a running time of O(nk) is not good enough and will receive very little credit. 4 Problem 4 (35 points) For both parts of this problem, you can use the function sum(A), which just returns the sum of all elements in A. The running time of sum(A) time is O(n) for an array of length n. Using this function will make your pseudocode a bit simpler. You can also, as usual, use any functions from our library. 4.1 Part 1 (10 points) Consider the problem SumLargestSmallest(A, k) 4 • INPUT: an unsorted array A of length n, and a positive integer k ≤ n/2. You can assume for this problem that n is even, that all numbers in A are unique, and that all numbers in A are positive integers. • OUTPUT: the total sum of the k largest elements in A and the k smallest elements in A. For example, if A = [10,6,15,3,12,7,50,1,8] and k = 2, then the two smallest elements are 1, 3 and the two largest elements are 50, 15, so SumLargestSmallest(A, 2) = 1 + 3 + 50 + 15 = 68. The Problem Write pseudocode for SumLargestSmallest(A, k) that runs in time O(n). Note that the running time should be O(n) even if k is large. A running time of O(nk) will get very little credit. 4.2 Part 2 (25 points) Now consider the problem ThresholdLargestSmallest(A,T) • INPUT: an unsorted array A of length n, and a positive target integer T. Note that T might be much larger than n. You can assume for this problem that n is even, that all numbers in A are unique, and that all numbers in A are positive integers. • OUTPUT: the smallest number k ≤ n/2 such that SumLargestSmallest(A, k) ≥ T . Note in particular that k must satisfy SumLargestSmallest(A, k − 1) < T . If SumLargestSmallest(A,n/2) < T then output “No Solution” For example, if A = [10,6,15,3,12,7,50,1,8] and T = 80, then the out- put should be k = 3 because SumLargestSmallest(A, 2) = 1 + 3 + 50 + 15 = 68 < 80, while SumLargestSmallest(A, 3) = 1+3+6+50+15+12 = 86 > 80.
The Problem Write pseudocode for a recursive algorithm ThresholdLargestS- mallest(A,T) that runs in time O(n). All you need to write is psuedocode, and the recurrence formula of your algorithm.
NOTE: For this problem, ANY correct algorithm that runs in O(n) time will receive full credit. I said to use recursion because the only solution I know to this problem uses recursion. If you think you have a correct non- recursive solution then you are welcome to use that, though again, the only solution I know of uses recursion.

5 Extra Credit – 10 points
Consider the following problem. We are given an array A of length n where all the entries are either 3 or 5 or 7. We say that an interval A[i], A[i + 1], …, A[j ] is balanced if the interval contains the same number of 3’s, 5’s, and 7’s; note in particular that j − i + 1, which is the length of the interval, must be divisible by 3.
• INPUT: an array A of length n where all the entries are either 3 or 5 or 7.
• OUTPUT:thelengthofthelongestbalancedintervalA[i],A[i+1],…A[j].
EXAMPLE:saythatA=[5,5,7,3,5,3,5,5,3,7,7,7,7,7,7,3,3,5,7]. then the longest balanced interval is A[2…10] = [7, 3, 5, 3, 5, 5, 3, 7, 7]; this interval has 9 numbers, so the output should be 9.
EXAMPLE: if A = 5, 5, 7, 5, 5, 3 then there are no balanced intervals and the output should be 0.
The Problem: Write pseudocode for an algorithm that solves the above problem in time O(n).
NOTE: you only have to output the length of the longest balanced inter- val, not the interval itself. That might simplify your pseudocode a bit.

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com