# 算法代写 | 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