CIS 320
Homework Assignment 1
Due: June 2nd, 11:00 AM on Gradescope
计算机理论作业代写 For each of the following statements, either prove that the statement is true for all positive-valuedfunctions f and g, or provide a specific pair
Please see Piazza and Canvas for submission logistics and LATEXtemplate.
1.For each of the following statements, either prove that the statement is true for all positive-valued functions f and g, 计算机理论作业代写
or provide a specific pair of (positive-valued) functions that provide a counter- example to the statement.
(a)If f (n) exceeds g(n) for only a finite number of values of n, then f (n) =O(g(n)).
(b)Iff (n) = O(g(n)) then g(n) = Ω(f (n)).计算机理论作业代写
(c) f (n) = O(f (n/2)).
- A set of n sumo wrestlers are facing off in the annual tournament. Each wrestler i ∈ [1..n] hasan associated strength si and weight wi. We say that wrestler i can yeet wrestler j if si > sj and wi > wj;
that is, if i is both stronger and heavier than j. A wrestler j is unyeetable if no wrestler i can yeet j.计算机理论作业代写 Design an O(n lg n) algorithm to find all the unyeetable wrestlers. For simplicity, you may assume that n is a power of 2.
3.Kachik has found a new procedure to compute a × b, where a, b ∈ N. He keeps a running total T = 0,
andinitially sets A = a and B = b. Until A = 0, he repeatedly divides A by 2, throwing away any remainder, and then multiplies B by 2. Before each step, if A is odd, then he adds B to T . At the end of the procedure, she claims T = a × b.
(a)Recall that an invariant is a property that is true at the start of Alex’s procedure, remains true ateach step, and is true when the procedure Carefully state an invariant such that at the end of Alex’s procedure, the invariant implies T = a × b.计算机理论作业代写
(b)Proveyour invariant holds at each step of the procedure, showing that Alex’s procedure is correct.
- EpidemiologistAli has blood samples from n individuals, exactly one of whom has Hand-Foot-Mouth disease, for which he has developed an accurate but time-consuming and expensive test. Test results are only available 24 hours after initiating the test. One option available is to pool together portions of the samples from a subset of individuals and perform a single test on the pooled sample that reveals whether some individual in the subset has the disease. Use pooling to show that Peter can identify the positive individual in |lg n| tests, all performed in just one day.计算机理论作业代写
Hint: See if you can find a procedure that identifies the individual in |lg n| days, and then refine your procedure to only use a single day.
- Vian hears a rumor that some mischievous CIS 320 student has enrolled in the course twice in an attempt to receive 2 credits. He wants to check that the n integer PennIDs on the course roster are distinct.Prove tight asymptotic upper and lower bounds in the comparison-tree model for this problem.计算机理论作业代写
6.A permutation of the elements [n] = {1, 2, . . . , n} is a bijection σ from [n] to [n]. There are n!计算机理论作业代写
such permutations,and a random permutation is one chosen uniformly at random from these n! permutations. If we represent a permutation by a directed graph with n nodes, where (i, j) is an edge if and only if σ(i) = j. This graph is just a collection of cycles. (We allow edges from a node i to itself, if σ(i) = i. This is considered a cycle of length 1. We also allow ”anti-parallel” edges (i, j) and (j, i), if σ(i) = j and σ(j) = i. This would be a length 2 cycle.)
Let σ be a random permutation of [n].
(a)Focusing on one element i∈ [n] prove that for any k ∈ 1, 2, . . . , n, the probability that i is in a cycle of length k is exactly 1 .计算机理论作业代写
(b)Define a random variable Xifor each i, whose value is 1 , where k is the length of the cycle that i is in. Using these random variables, linearity of expectation. And the solution to the previous part, find the expected number of cycles in a random permutation of [n].
7.Let U be a large universe of elements and S be some fixed subset of n We want to find a wayof hashing S so that there are no collisions! 计算机理论作业代写
In other words, you are given the input S, and youwant to come up with an algorithm that outputs a hash function h such that ∀x, y ∈ S h(x) ƒ= h(y).
Of course if the range of h is as large as |U | this is trivial — the identity function, h(x) = x, would do. We want to find this collision-free h with as small a range as possible. Using universal hashing,
describe an efficient randomized algorithm that outputs a collision-free h. Analyze your algorithm to prove its correctness and expected running time. For full credit you should give a correct solution where the hash function has a range of size n2.计算机理论作业代写
- Given an array of n integers and a number k, design and analyze an efficient algorithm for findingthe k integers in the array that are ‘closest’ to the median of the array. The distance between two integers x and y is the absolute value of their difference |x − y|. And your algorithm should output the k integers with the smallest distance to the median among the given n elements.计算机理论作业代写
- Given an array of n distinct integers A, using a heap, show how to construct an array B such that for each i, B[i] contains the rank of A[i] in A. For example, if the array A is [5, 2, 7, 4, 38], then the array B you return should be [4, 1, 5, 3, 2, 6], since, for example, the rank of 5 in A is 4, the rank of 2 is 1, etc. While there are many ways to solve this problem, your algorithm should use a heap in a central way.
其他代写：代写CS C++代写 java代写 r代写 金融经济统计代写 matlab代写 web代写 app代写 代写CS作业 物理代写 数学代写 考试助攻 algorithm代写
