算法问题集代做 CSCI 3104代写

CSCI 3104 Problem Set 13

1 Instructions 算法问题集代做

The solutions must be typed, using proper mathematical notation. We cannot accept hand-written solutions. Here’s a short intro to LATEX.
You should submit your work through the class Canvas page only. Please submit one PDF file, compiled using this LATEX template.
You may not need a full page for your solutions; pagebreaks are there to help Gradescope automatically find where each problem is. Even if you do not attempt every problem, please submit this document with no fewer pages than the blank template (or Gradescope has issues with it).
You are welcome and encouraged to collaborate with your classmates, as well as consult outside resources.

You must cite your sources in this document. Copying from any source is an Honor Code violation. Furthermore, all submissions must be in your own words and reflect your understanding of the material. If there is any confusion about this policy, it is your responsibility to clarify before the due date.

Posting to any service including, but not limited to Chegg, Reddit, StackExchange, etc., for help on an assignment is a violation of the Honor Code.
You must virtually sign the Honor Code (see Section 2). Failure to do so will result in your assignment not being graded.

2 Honor Code (Make Sure to Virtually Sign the Honor Pledge) 算法问题集代做

Problem 1. On my honor, my submission reflects the following:

My submission is in my own words and reflects my understanding of the material.
Any collaborations and external sources have been clearly cited in this document.
I have not posted to external services including, but not limited to Chegg, Reddit, StackExchange, etc.
I have neither copied nor provided others solutions they can copy.

In the specified region below, clearly indicate that you have upheld the Honor Code. Then type your name.

3 Standard 27- Computational Complexity: Formulating Decision Problems

4 Standard 28- Computational Complexity: Problems in P

Problem 3. Consider the decision variant of the Interval Scheduling problem.

Instance: Let I = {[s₁, f₁], . . . , [s_n, f_n]} be our set of intervals, and let k ∈ N.
Decision: Does there exist a set S ⊆ I of at least k pairwise-disjoint intervals?

Show that the decision variant of the Interval Scheduling problem belongs to P. You are welcome and encouraged to cite algorithms we have previously covered in class, including known facts about their runtime. [Note: To gauge the level of detail, I expect your solutions to this problem will be 2-4 sentences. I am not asking you to analyze an algorithm in great detail.]

5 Standard 29- Computational Complexity: Problems in NP 算法问题集代做

Problem 4. We consider an algebraic structure Q = (S, ★), where S is our set of elements and ★ : S × S → S is our multiplication operation. That is, for any i, j ∈ S, the product i ★ j ∈ S. When S is finite, we say that (S, ★) is a quasigroup if the multiplication table is a Latin square; that is, if each element of S appears exactly once in each row and exactly once in each column.

The Latin Square Isotopy problem is defined as follows.

Decision: Let Q₁= (S₁, ★) and Q₂= (S₂, ◇ ) be quasigroups, where S₁, S₂ are n-element sets. Suppose that (S₁, ★) and (S₂, ◇ ) are given by their multiplication tables.
Decision: Do there exist one-to-one functions α, β, γ : S1 → S2 such that for all x, y ∈ S:

α(x) ◇ β(y) = γ(x ★ y).

Here, α(x) β(y) is a product being considered in Q₂, while x ★ y is a product being considered in Q₁.

Show that the Latin Square Isotopy problem belongs to NP. ^∗

6 Standard 31- Hashing 算法问题集代做

6.1 Problem 5

Problem 5. Let H be a hash table with the underlying array A[1, . . . , m] and hash function h(x) satisfying the Simple Uniform Hashing Assumptions. Suppose that H resolves collisions with chaining. Now suppose that k ∉ H. Prove that the lookup and deletion operations have expected runtime Θ(1 + α). [Hint: Assume the hash function takes 1 step. Now once we have applied the hash function, how do we determine if k ∈ H?]

Proof. The hash function on k will take one step.

Now once we apply the hash function, we will have to check a list whose expected length is α. The lookup operation will have to loop through the whole list to see if k ∈ H, which will be Θ(α) steps. Therefore, the total time complexity for lookup is Θ(1 + α).

For the deletion, the argument is similar, we will still have to loop through a link list whose expected length is α. Therefore the time complexity for both lookup and deletion are both Θ(1 + α).

6.2 Problem 6 算法问题集代做

Problem 6. Let H be a hash table with the underlying array A[1, . . . , 9] and hash function h(x) satisfying the Simple Uniform Hashing Assumptions. Suppose that H resolves collisions with chaining, and that H begins with n = 0 elements. For our complexity goals, we want α ≤ 1/3. The array is doubled whenever the load factor is strictly greater than 1/3. What is the size of the array when H contains n = 15 elements? Show all work.

6.3 Problem 7

Problem 7. Hash tables and balanced binary trees can be both be used to implement a dictionary data structure, which supports insertion, deletion, and lookup operations. In balanced binary trees containing n elements, the runtime of all operations is Θ(log n).

For each of the following three scenarios, compare the average-case performance of a dictionary implemented with a hash table (which resolves collisions with chaining using doubly-linked lists) to a dictionary implemented with a balanced binary tree.

(a) A hash table with hash function h₁(x) = 1 for all keys x.

(b) A hash table with a hash function h₂ that satisfies the Simple Uniform Hashing Assumption, and where the number m of buckets is Θ(n).

(c) A hash table with a hash function h₃ that satisfies the Simple Uniform Hashing Assumption, and where the number m of buckets is Θ(√n)

合作平台：essay代写论文代写写手招聘英国留学生代写