算法代写 | CPTS516 Take-home Final Exam

本次美国代写主要为算法修改的take home exam

CPTS516 Take-home Final Exam

You may use Python, C, C++, or Java (or any other programming language that you are familiar
with) to do the implementation. All the work must be your own; collaboration is prohibited.
You can search on the Internet but mostly, you will waste your time. I design the exam so that it
is googling-proof.
As we have learned this semester, NP is the class of problems that can be solved by nondeter-
ministic algorithms in polynomial time. In particular, NP-complete problems are the hardest ones
in NP. Currently, it is open whether we have ecient solutions to those problems. That is, many
researchers are still trying to nd (deterministic) polynomial time algorithms to solve those NP-
complete problems, or at least to nd practically ecient algorithms for them. Such eorts would
lead to successfully cracking RSA, which is known in NP (but we do not know whether cracking
RSA, i.e., factorizing a large number, is NP-complete). There is a well-known NP-complete prob-
lem, called linear Diophantine (written LD), which seeks nonnegative integer solutions to a linear
constraint system Q over multiple variables x1;


; xk, for some k; e.g.,
8
> > > <
> > > :
2×1 + x2 + 15 = 0
3×1 4×2 > 18
x1 + 3×2 < 27
x1 > 15
(1)
The example LD instance shown in (1) has two nonnegative integer variables x1 and x2 and four
constraints. Notice that the range of the variables is unbounded; hence, you can not assume
that they are in 32-bits unsigned ! Please stare at the example for 10 minutes and see how you
would design an algorithm to nd whether it has solutions and if it has, how you would come up
with a solution. There is a brilliant idea which we learned this semester in solving LD: using the
automata-based algorithm for Presburger arithmetic, where a linear constraint is represented as
an NFA (hence a labeled graph). (Do not even try to solve LD using equation-solving skills (called
Newton elimination) you learned in high school; variables in those high school equations are of real
values and do not apply here.)
Formally, an LD-instance Q is given as, for some k and m,
8
> > <
> > :
C11x1 +


+ C1kxk + C1 #1 0
.
.
.
Cm1x1 +


+ Cmkxk + Cm #m 0
(2)

where all the xj ‘s are nonnegative integer variables (called unknowns), and the following are all
the parameters:
ˆ all the coecients Cij ‘s, which are integers (positive, negative, zero), and
ˆ all the numbers Ci’s, which are nonnegative integers, and, nally,
ˆ all the #i’s, each of which is in f>;<;=g.

Excercise: What are the the values of the m, the k and the parameters for the example LD instance
shown in (1) ?
Any algorithm that solves the LD problem is to take an instance Q in (2) as the algorithm’s
input, and to return yes (along with a solution) if the instance has a nonnegative integer solution in
the unknowns x1;


; xk, and to return no if otherwise. Notice that the time complexity function
of the algorithm measures on the size of the input. (Hint: the size of number 4.6 billions is roughly
32. )
The remaining of the exam asks you to implement the brilliant idea in solving the LD problem:
representing each linear constraint (such as 2×1 3×2 + 4 = 0) in an instance Q using a labeled
graph (i.e., a nite automaton). Hence, since there are m constraints in the instance Q, you need
then implement a graph composition algorithm to convert the m graphs into one nal graph. Then,
you perform basic graph search on the nal graph to nally solve the LD problem.
1. (70pts) Watch the class videos on Presburger arithmetic, where I presented the aforementioned
brilliant ideas (which were invented decades ago by some of our brightest ancestors in algorithms)
and you take notes while watching. Make sure that you fully understand the ideas. In this
project, you are going to implement those ideas to solve an instance Q in three variables and with
2 equations. Being Diophantine, the variables are of nonnegative integers. I do not ask you to
design the algorithm, instead, I present the algorithm’s design, and you need only implement the
algorithm. You need turn-in working code and prepare for a demo.
Preparation 1.
Herein, an equation is in the form of
C1x1 + C2x2 + C3x3 + C = 0 (3)
where constants C1;C2;C3 are integers (positive,negative, zero), and constant C is nonnegative.
Hence, for instance, 3×1 + 0x2 4×3 17 = 0 is not an equation in the above form. However,
equivalently, 3×1 0x2 + 4×3 + 17 = 0 is in the above form.
For the equation in (3), we de ne
Cmax = max
d;d1;d2;d32f0;1g
jC1d1 + C2d2 + C3d3 + dj: (4)
(Exercise: For the aforementioned equation 3×1 0x2 +4×3 +17 = 0, what is the value of Cmax?)
Implement a function that returns Cmax from the description of an equation in (3), and use the
above Exercise to test your function.
Preparation 2.
For a constant C  0, we use binary representation for C. For instance, if C = 34, then in
binary, C = 100010. In this case, we use
b6b5b4b3b2b1