Items tagged with algorithm algorithm Tagged Items Feed

Not homework (from the telly): A gallery takes a concave polygon shape with a square pillar in the centre. security cameras can do a 360 degree sweep but they can't see around corners. The cameras have to be attached to the walls. What is the fewest number of cameras such that they can see everywhere in the gallery?

I got as far as drawing it in Maple.

there is an algorithm -which supposedly finds the optimal solutuion- breaking the object into triangular shapes. that gets an answer:  4 cameras.

EDIT 11/10

this is based on Fisk's short proof. See Markiyan's wiki ref below.

1.first stand on on a corner and scan clockwise around the room. Any two corners passed creates one triangle.

Repeat for every corner


2. Pick three colours and allocate each color to each corner of each triangle.

sometimes you will end up with a triangle which has 2 corners of the same colour. This one has two blue corners


This triangle must be broken in two and add a green dot

3.finally the algorithm places cameras on the colour which occurs least.

But by experimenting with more complex shapes (convex polygons) you can cover the gallery with 3.


In Maple anyone?


Hello everyone, 


I'm currently taking a Chaos and Fractal Geometry class that did not have a pre-req of computer programming or knowledge of Maple, but I am apparently the only person in the class who has not taken a class/does not have this knowledge so my professor really flew by teaching the material. My sob story aside, I was hoping you great people would be able to help me out with (what are apparently) really basic procedures and plots while I try to read up on how to actaully do it myself (if anyone has a good supplement to recommend, I'm all ears!). Anyway, here are the one's that I'm stumped on:

  • "Write a Maple proc L that takes as input two lists and returns as output a set containing the terms they have in common (not necessarily in the same position). For example, L([1, 3, x, 5],[2, x, 5, 2, 1, 8]) should return [1, x, 5]."
    I'm thinking this is going to use some form of the intersection command, but I cannot for the life of me figure out how to set up the syntax
  • "Write a Maple program that implements the Euclidean algorithm to compute the gcd(x, y) for any natural numbers x, y (except x = y = 0). Your program should not just compute the gcd, but should do so by implementing the Euclidean algorithm directly (i.e. proc(x,y) RETURN(gcd(x,y)) end; is not what I am looking for here! :) )."
    If only he would've let me do the easy one :(
  • "Write a Maple program to plot the Pythagorean spiral. The program should take a single positive integer n as an argument and plot the spiral until the side of length n is reached"
    Not even a clue on how to approach this one. 


Thanks again to any and all help/recommendations you can make. I really appreciate it!

Bubble := proc (X::list)

local n, i, j, t;

n := nops(X);

if n = 0 then ERROR("empty list") end if;

for i to n-1 do

   for j to n-i do

      if X[j+1] < X[j] then

          t := X[j];

          X[j] := X[j+1];

          X[j+1] := t;

      end if;

   end do;

end do;


end proc


I make bubble sort algorithm. but i can't find 'illegal use of a formal parameter'.

I want to test linearly dependence of a polynomial f on a list of polynomials F by additional condition on parametric coefficients of linear parametric polynomial (linear for variables not parameters). Please note that:

  1. The polynomialand the members of are always homogenous in the variables.
  2. The coefficients of f, the coefficients of the members of F are all always polynomials in the parameters or contant and the members of N and W are all always polynomials in the parameters.


For example let


(a,b,c,d,e,h are parameters and A1,A2,A3 are variables).

If I use PolyLinearCombo(F,f,{A1,A2,A3}) (see its output is false,[].

Now we let to condition sets for parameters as the following:



The elements of N must be zero means that ebc+ahd=0

and the elements of W are non-zero that is a<>0 and c <>0.

Let a=b=c=d=h=1 and e=-1. This specialization satisfy in the above condition sets N and W. By this specialization we have:


Now if I use PolyLinearCombo(F,f,{A1,A2,A3}) then its output is true,[-1,1].

By this additional two condition sets I have to check that whether f is linearly independent of F or not. How can I do this without specialization? In fact I want an algorithm that its input is (null condition N, not-null condition W, list of polynomials F, a polynomial f, the set of variables) and its output is true and coefficients if f is linearly dependent of F w.r.t. null and not-null conditions N and W, else its output is false.

If the name of new procedure is ExtPolyLinearCombo and 



I want the output of

ExtPolyLinearCombo(N,W,F,f,{A1,A2,A3}) be true,[coefficients]

Thank you very much in advance.



Hi all,

Please help in writing finite difference algorithm for a nonlinear PDE using Maple.

for a[j], b[j] known at time n, I want to compute A[j]  for a[j] at time n+1 according to the equation below

EQs:=A[j]-theta*tau*(A[j-1]-2*A[j]+A[j+1])=a[j]+sqrt(a[j])*b[j]*h^2/tau+(1-theta)*tau*(a[j-1]-2*a[j]+a[j+1]) ;

Thanks in advance.

I am trying to understand how maple "isprime" algorithm works. But I can't find anywhere what special_primes means.



isprime := proc(n)
local btor, nr, p, r;
   1   if not type(n,'integer') then
   2     if type(n,('complex')('numeric')) then
   3       error "argument must be an integer"
   4       return 'isprime(n)'
         end if
       end if;
   5   if n < 2 then
   6     return false
       elif member(n,isprime:-special_primes) then
   7     return true
       elif igcd(2305567963945518424753102147331756070,n) <> 1 then
   8     return false
       elif n < 10201 then
   9     return true
       elif igcd(8496969489233418110532339909187349965926062586648932736611545426342203893270769390909069477309509137509786917118668028861499333825097682386722983737962963066757674131126736578936440788157186969893730633113066478620448624949257324022627395437363639038752608166758661255956834630697220447512298848222228550062683786342519960225996301315945644470064720696621750477244528915927867113,n) <> 1 then
  10     return false
       elif n < 1018081 then
  11     return true
  12     r := gmp_isprime(n);
  13     if not r or n <= 5000000000 then
  14       return r
         end if;
  15     nr := igcd(408410100000,n-1);
  16     nr := igcd(nr^5,n-1);
  17     r := iquo(n-1,nr);
  18     btor := modp(('power')(2,r),n);
  19     if cyclotest(n,btor,2,r) = false or irem(nr,3) = 0 and cyclotest(n,btor,3,r) = false or irem(nr,5) = 0 and cyclotest(n,btor,5,r) = false or irem(nr,7) = 0 and cyclotest(n,btor,7,r) = false then
  20       return false
         end if;
  21     if isqrt(n)^2 = n then
  22       return false
         end if;
  23     for p from 3 while numtheory:-jacobi(p^2-4,n) <> -1 do
  24       NULL
         end do;
  25     return evalb(TraceModQF(p,n+1,n) = [2, p])
       end if
end proc

I would like to pay attention to an article by David Austin "The Stable Marriage Problem and School Choice"

Here is its inroduction:

" Every year, 75,000 New York City eighth graders apply for admission to one of the city's 426 public high schools. Until recently, this process asked students to list five schools in order of preference. These lists were sent to the schools, who decided which applicants to accept, wait-list, or reject. The students were then notified of their status and allowed to accept only one offer and one position on a waiting list. After the students had responded to any offers received, schools with unfilled positions made a second round of offers, and this process continued through a concluding third round.

This process had several serious problems. At the end of the third round of offers, nearly half of the students, usually lower-performing students from poor families, had not been accepted into a school. Many of these students waited through the summer only to learn they had been matched with a school that was not on their list of five schools.

This process also encouraged students and their parents to think strategically about the list of schools they submitted. Students that were rejected by the school at the top of their list might find that their second-choice school had no vacancies in the second round of offers. This made it risky for many students to faithfully state their true preferences, a view encouraged by the Education Department's advice that students "determine what your competition is" before creating their lists of preferred schools.

Lastly, schools would often underrepresent their capacity hoping to save positions for students who were unhappy with their initial offerings.

In the end, the process couldn't place many students while it encouraged all parties, both students and schools, to strategically misrepresent themselves in an effort to obtain more desirable outcomes not possible otherwise. Widespread mistrust in the placement process was a natural consequence.

Using ideas described in this column, economists Atila Abdulkadiroglu, Parag Pathak, and Alvin Roth designed a clearinghouse for matching students with high schools, which was first implemented in 2004. This new computerized algorithm places all but about 3000 students each year and results in more students receiving offers from their first-choice schools. As a result, students now submit lists that reflect their true preferences, which provides school officials with public input into the determination of which schools to close or reform. For their part, schools have found that there is no longer an advantage to underrepresenting their capacity.

The key to this new algorithm is the notion of stability, first introduced in a 1962 paper by Gale and Shapley. We say that a matching of students to schools is stable if there is not a student and a school who would prefer to be matched with each other more than their current matches. Gale and Shapley introduced an algorithm, sometimes called deferred acceptance, which is guaranteed to produced a stable matching. Later, Roth showed that when the deferred acceptance algorithm is applied, a student can not gain admittance into a more preferred school by strategically misrepresenting his or her preferences.

This column will present the game-theoretic results contained in the original Gale-Shapley paper along with Roth's subsequent analysis. Pathak calls the deferred acceptance algorithm "one of the great ideas in economics," and Roth and Shapley were awarded the 2012 Nobel Prize in economics for this work"

It would be nice to realize that in Maple.




I have a question. I have to compare the times and steps taken by an algorithmus (which contents a loop).

So for time there is the time()-function, right? And is there any similar function for the steps taken?

So far i use a variable increasing by 1 each time, but i think there is an more elegant way to do it, which I just don't know.. :D


Thanks for any help!


I need to write a procedure that does the following :

Write a procedure quadsum whose input is an integer n and whose output is a list of pairs of solutions [x,y] to the above formula.

Your procedure should implement the following algorithm.

1 Initialization
"mylist = []."

Start at
x = 0
y = 0.

2 Phase A
Increment both
"x^2+y^2 >=n."

Phase B
Repeat the following until

If you are above the circle
x^2 + y^2 = n
then go down in unit steps until you are on or below the circle.

If you are on the circle, add the point to the list
"mylist. "

If you are on or below the circle
x^2 + y^2 = n
then go one step to the right. My procedure is as follows: but it runs into an infinite loop(most probably because of the while loop defined inside the while loop). What am I doing incorrectly?

I have atta


Hi there,

I'm trying to simulate an stochastic SIR model following the Gillespie algorithm, as described here [1].


When trying to update each process' probabilities, it looks like Maple is not updating their values. Although each element of the lists S, I and R is updated the ai lists are not updated.

For example, for a given index i

a2[i]:= m*S[i]:

takes the same value for every i, regardless of the value of S[i].

Can anybody tell why this is happening or what's wrong with the worksheet? This is the attempt:


On the other hand, I tried making things more clear through a couple of procedures. However, when it comes to the point where a random number with an exponential distirbution is computed:

Rexp := RandomVariable(Exponential(mu)):

it looks like Maple is unable to evaluate mu. But having a look at the Variables explorer, it has a defined value, indeed.

So what's wrong in the worksheet? Thi is the attempt:





Currently calculations: equations, regression analysis, differential equations, etc; to mention a few of them; are developed using traditional methods ie even are proposed and solved by hand and on paper. In teaching our scientists and engineers use the chalkboard as a way to reach students and enable them to solve their calculation. To what extent Maple contributes to research on new mathematical models applied science and engineering ?. Maplesoft appears as a proposal to resolve problems with our traditional proposed intelligent algorithms, development process, embedded components, and not only them but also generates type applications for Apple ipad tablets signature. Based on the computer algebra system Maple Maplesoft gives us the package which works exactly like we were on our work. I will show how mathematics is developed from a purely basic to reach modeling differential equations applied to education and engineering. Also visualizare current techniques for developing applications for mobile devices.





Lenin Araujo Castillo

Physics Pure

Computer Science

Dear Maple Experts,

i am new to maple and I am trying to write a maple algorithm in order to calculate the GCD of two functions. 

I have defined the two functions and written the algorithm, but I get an error "Unable to Parse".

Here is my code:

restart; with(Algebraic); with(LinearAlgebra[Generic]); with(RegularChains); with(FastArithmeticTools); with(ChainTools); interface(rtablesize = 15);

f := (y^2-1)*((y+1)*x^4+(y^2-1)*x^3+(y^3-1)*x^2+(y^4-1)*x+y^5-1);

g := (y-1)*x^5+(y^2-1)*x^4+(y^3-1)*x^3+(y^4-1)*x^2+(y^5-1)*x+y^6-1;

SubRes:=proc(f,g,var): local  i,a, delta, beta, psi: if degree(f,var)<degree(g,var) then a[0]:=Algebraic:-PrimitivePart(g,var): a[1]:=Algebraic:-PrimitivePart(f,var): else a[0]=Algebraic:-PrimitivePart(f,var): a[1]:=Algebraic:-PrimitivePart(g,var): fi: delta[0]:=degree(a[0],var)-degree(a[1],var): beta[2]:=(-1)^((delta[0]+1)): psi[2]:=-1: i:=1: while a[i]<>0 do a[i+1]:=(prem(a[i-1], a[i], var))/(beta[i+1]): delta[i]:=degree(a[i],var)-degree(a[i+1], var): i:=i+1: psi[i+1]:=((-lcoeff(a[i-1],var))^((delta[i-2])))*((psi[i])^((1-delta[i-2]))): beta[i+1]:=-lcoeff(a[i-1],var)*(psi[i+1])^((delta[i-1])): od: print("Last Non-Zero Subresultant: ", sort(simplify(a[i-1])),y): return (Algebraic:-PrimitivePart(a[i-1],var)): end proc

and I get this error:

Error, unable to parse

Would you kindly help me to fix this issue?

Kind Regards,



So the pseudocode I'm trying to translate into maple is for the greedy vertex coloring algorithm.

The pseudo code is:

1. for i = 1 to n do
2. f[i] := 0 (: no color assigned yet to vertex i :)
3. end(for)
Main loop:
4. for i = 1 to n do
5. let f[i] be the smallest positive integer
which is not in the set {f(j) : j ∈ adj[i]}
6. end(for)
7 return f


The closest I've gotten though is:

greedy := proc (G)

local i, j, n, k, L::list;

description "Take simple graph G and return a coloring of the vertices with at most Delta(G)+1 colors";

n := nops(Vertices(G));
L := [seq(x, i = 1 .. n)];
L := subsop(1 = c(1), L);
j := 1;
for i from 2 to n do
L[Vertices(G)[i]] := c(0)
end do;

for i from 2 to n do
   for k to i do
        if member(Vertices(G)[i], Neighbors(G, Vertices(G)[k])) then j := j+1
       end if; 
   end do;
L[Vertices(G)[i]] := c(j)
end do;
return L;
end proc;

Basically my procedure is returning more than delta+1 colors for most graphs, how can I edit it to fix this? I'm guessing the problem is somewhere in my nested loops. Also, I cannot use commands like greedycolor or isvertexcolorable. Thanks.


Having solution of an inequations system, is there a way/function/algorithm to find a particular numeric solution (as simplex[minimize] can do) ?


Q := {1 < x - y, x + y < 1};

R := solve(Q);

      { x < 1 - y, y < 0, y + 1 < x }

manually it's easy to find some numeric solutions:

      y = -1, x = 1
      y = -2, x = 0

but I need an automatic way.

Thank you for your help


Hi all

Can anybody suggest an algorithm allowing to detect, that two matrices of the same size can be obtained each from other by permutations of rows and columns? Maybe, such an algorithm there exists in LinearAlgebra package?

1 2 3 4 5 Page 1 of 5