Question

If given the equation bx+dy+a=0 of a line ? in the plane, with 3 coefficients b,d,a, are integers expressed with, n bits (at most). One must determine whether line L passes through any point with integer coordinates. This is a problem that can be solved efficiently in the worst case in Θ time. What is that worst case time? Or is it impossible to do so?

Answer #1

**Ans).** We have a Diophantine equation (an
equation of the form ax+by+c=0). Well, by using euclidean
algorithm, we have integer solution for bx+dy=gcd(b,d).

Doing some analysis, we can find out the in order for a
diophantine equation **bx+dy+a=0** to have integer
solution, we need only one condition : **a is a multiple of
gcd(b,d).**

Thus the whole problem boils down to finding gcd which can be done in O(log(min(b,d))).

Therefore, the overall worst case complexity is **O( Log(
min(b,d) ) ).**

**Hope it helped! Feel free to ask any dount in comments.
Don't forget to upvote if it helped :).**

1.Find an equation for the plane that is perpendicular to the
line l(t) = (8, 0, 4)t + (5, −1, 1) and passes through (6, −1,
0).
2.Find an equation for the plane that is perpendicular to the
line l(t) = (−3, −6, 9)t + (0, 7, 1)and passes
through (2, 2, −1).

Part I. Indicate whether true or false (T or F).
____ Storm water detention ponds typically are designed to
regulate the outflow peak rate at or below a single target value,
such as the pre-development (pre-land use change) peak runoff rate
for a specified return period event. Detention storage alters the
peak but not the volume of the outflow hydrograph.
_____ Typical rating curves for weirs are concave upward.
Typical rating curves for orifices are concave downward.
____ A sediment...

Please answer the following Case
analysis questions
1-How is New Balance performing compared to its primary rivals?
How will the acquisition of Reebok by Adidas impact the structure
of the athletic shoe industry? Is this likely to be favorable or
unfavorable for New Balance?
2- What issues does New Balance management need to address?
3-What recommendations would you make to New Balance Management?
What does New Balance need to do to continue to be successful?
Should management continue to invest...

Sign In
INNOVATION
Deep Change: How Operational Innovation Can Transform Your
Company
by
Michael Hammer
From the April 2004 Issue
Save
Share
8.95
In 1991, Progressive Insurance, an automobile insurer based in
Mayfield Village, Ohio, had approximately $1.3 billion in sales. By
2002, that figure had grown to $9.5 billion. What fashionable
strategies did Progressive employ to achieve sevenfold growth in
just over a decade? Was it positioned in a high-growth industry?
Hardly. Auto insurance is a mature, 100-year-old industry...

What tools could AA leaders have used to increase their
awareness of internal and external issues?
???ALASKA AIRLINES: NAVIGATING CHANGE
In the autumn of 2007, Alaska Airlines executives adjourned at
the end of a long and stressful day in the
midst of a multi-day strategic planning session. Most headed
outside to relax, unwind and enjoy a bonfire
on the shore of Semiahmoo Spit, outside the meeting venue in
Blaine, a seaport town in northwest
Washington state.
Meanwhile, several members of...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 26 minutes ago

asked 34 minutes ago

asked 44 minutes ago

asked 44 minutes ago

asked 45 minutes ago

asked 46 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago