University of Texas at : Techniques and Theory
Department of Computer Science Professor Vijaya Ramachandran
CS388G (Online), Spring 2023
Problem Set 5
Copyright By PowCoder代写 加微信 powcoder
• Answer all four questions.
• Please turn in your solutions electronically, typeset in LATEX.
1. [15 POINTS]
(a) (6 pts) Consider Union-Find implemented with union by rank and path compression. Using only the results in Lemma 0 in Lecture 17, establish the following amortized bounds for this implementation using the Accounting method for amortized analysis:
Make-set: 1; Find-set: 1; and Link: ρ.
In the lecture we defined ρ as the number of different ranks assigned to nodes during the execution of the Union-Find operations. Here, we let ρ be the maximum rank assigned to any node during the execution. (The result can be established with either definition.)
(b) Balanced Tree-path Minimum Problem: In this problem you are given a completely balanced binary tree T on n leaves with a key (i.e., value) at each node, so there are 2n − 1 keys. This is not a binary search tree but simply a completely balanced binary tree with a key at each node. You can assume that all keys are distinct.
You need to be able to answer queries of the form:
Min(x,y), where x is a leaf and y is an ancestor of x in the tree. Here, x,y are pointers to elements in the tree.
A query Min(x,y) needs to return the minimum value of any key in the tree path between x and y.
You are allowed to pre-process the given tree to compute and store the answer for some (or all) of the paths in the tree. The goal is to achieve very small query time (close to constant) while also keeping the preprocessing time and space used small (close to linear in n).
In the following, we will measure the query time in terms of the number of ‘probes’ made, where each probe is an access to either a node in the input tree or to a location that stores a value computed by the preprocessing algorithm. If k probes are made, we also allow k − 1 min/max operations using values returned by the probes.
Note that you need not count the time to determine a particular node’s position in the tree nor do you need to specify the method you use to store the precomputed values. In this problem the only quantity of interest is the trade-off between preprocessing time and query time for any given Min query.
(i) (1 pts) Give a simple method that answers any query in O(log n) time with no prepro- cessing.
(ii) (2 pts) Give a preprocessing method that runs in O(n · log n) time and space, after which it computes the answer to any query with one probe.
(iii) (6 pts) Give a preprocessing method that runs in O(n · log log n) time and space, after which it computes the answer to any query with at most 2 probes.
Hint: Use a strategy inspired by the loglogn analysis that you saw in the lecture for Union-Find.
(The analysis in part (iii) can be further refined to obtain a preprocessing method that runs in O(n) time and space, and then computes the answer to any query with at most O(α(n, n)) probes. This further refinement is not needed here.)
2. [15 POINTS] Consider the following two page replacement strategies:
FIFO (First-In, First-Out) is a page replacement strategy in which the page that is evicted
is the one that has been currently in the cache for the longest duration.
LIFO (Last-in, First-Out) is a page replacement strategy in which the page that is evicted is the one that was brought into cache most recently in time.
(a) (4 pts) Show that neither FIFO nor LIFO is a marking algorithm.
The following definition applies to parts (b) and (c):
Subsequence Property: A cache replacement policy P has the subsequence property if it satisfies the following: Let k be the size of the cache. Let σ be a sequence of memory accesses and let σ′ be any contiguous subsequence of σ that accesses at most k distinct memory locations. Then, P performs at most k evictions on σ′.
(b) (5 pts) Determine whether or not each of FIFO and LIFO has the subsequence policy. (c) (6 pts) Prove that any cache replacement policy that has the subsequence property has
competitive ratio k , where k is the size of the cache, and h ≤ k is the size of the cache k−h+1
for OPT, the optimal offline cache replacement policy.
3. [15 POINTS] Parts (a), (b), and (c) are unrelated.
(a) (5 pts) Prove that any language in NP can be solved by an algorithm running in exponential time, i.e., in time 2poly(n) time, where n is the size of the input and poly(n) = O(nk) for some constant k > 0.
(b) (5 pts) The complement Q ̄ of a decision problem Q is defined as Q ̄ = {0, 1}∗ − Q. Inotherwords,aninputx∈{0,1}∗ isinQ ̄ifandonlyifxisnotinQ. Notethatthe complement of Q ̄ is Q.
We define co-NP to be the class of decision problems whose complements are in NP.
Show that if P=NP then NP=co-NP.
(c) (5 pts) Establish that if the decision problem Ham-cycle ∈ P, then the problem of listing the set of edges in a Hamiltonian cycle in an undirected graph G with a Hamiltonian cycle is polynomial time solvable.
4. [15 POINTS] Given an integer m × n matrix A and an integer m-vector b, the feasible 0-1 integer-programming problem (feasible 0-1-IP or simply just 0-1-IP) asks whether there exists an n-vector x with elements in the set {0, 1} such that Ax ≤ b.
(a) (5 pts) Show that 0-1-IP is in NP. Be sure to clearly specify a set of certificates, along with a polynomial time verification algorithm for 0-1-IP. You must establish the correctness and polynomial time bound of your verification algorithm.
(b) (9 pts) Show that 3-CNF-SAT ≤P 0-1-IP. Be sure to clearly specify your reduction, and to establish its correctness.
(c) (1 pt) Show that 0-1-IP is NP-complete.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com