Articles of algorithms

Find 3rd largest number out of 7 under at most 11 comparisons

I know similar problem like “sort 5 numbers in 7 comparisons”. I know no general algorithms exist. Do I just enlist all possible game trees?

Jacobian matrix

Please help me to determine the Jacobian matrix of $n$ functions with $n$ parameters with C++. I know MATLAB has the possibility to determine the Jacobian matrix by using jacobian(f,v), but I have to use C++. I will appreciate your help.

A problem on Number theory

You are given three non-negative integers $A$, $B$ and $C$, find a number $X$ (say) satisfy $X^A \equiv B\pmod{2C + 1}$ and $0 \le X \le 2C$. I am inquisitive about how to approach this one?

Neighborhood Complex Connectedness Algorithm

Is there an algorithm that can decide, wether the polyhedron of a neighborhood complex (as defined here) of a given finite graph is simply connected? There is no such algorithm for arbitrary simplicial complexes, see k-connectedness of simplicial complexes.

Finding an MST among all spanning trees with maximum of white edges

Let an undirected graph $G=(V,E)$ with the color property $c(e)$ for every edge (could be black or white) and a weight property $1 \le w(e) \le 100$. Find the MST from the set of all spanning trees with the maximum number of white edges. Do it in linear time ($O(|V|+|E|$). So basically I want to […]

Solving a recurrence by using characteristic equation method

How can I solve $$T(n) = aT(n-1) + bT(n-2)+ cn $$; where $a,b,c$ are constants. I could not figüre it out 🙁 There are T(0) = d and T(1) = e, Thanks in advance.

How to prove CYK algorithm has $O(n^3)$ running time

I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final. I’m trying to find out how to prove the algorithm has worst case running time of $n^3$. Thanks

How can we draw $14$ squares to obtain an $8 \times 8$ table divided into $64$ unit squares?

How can we draw $14$ squares to obtain an $8\times8$ table divided into $64$ unit squares? Notes: -The squares to be drawn can be of any size. -There will be no drawings outside the table.

How can we show that 3-dimensional matching $\le_p$ exact cover?

In exact cover, we’re given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise disjoint. I’m wondering how we can show 3-dimensional matching $\le_p$ exact cover. Given an instance of the 3-dimensional […]

Efficiently partition a set into all possible unique pair combinations

Apologies in advance as I’m a programmer, not a mathematician. I am working on organizing pair programming in teams. So I have a set of individuals, and I want to work out all the possible unique pairing combinations so that we can have a set of pairs each day that ensures that no one re-pairs […]