Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (comptutational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

1
vote
2answers
40 views

Big-O Notation (How to calculate C and k)

I have a fair idea of what Big-O Notation is, but I'd like to know if there's a sure fire way to calculate the values of C and k for which Example question: Via trial and error, I have found ...
-1
votes
3answers
61 views

Find algorithm for equation [closed]

I need algorithm for this problem: Find $x,y$ from the equation: $c=ax+by$, where a,b,c are given natural numbers and $(a,b)=1$ (the greatest common factor of $a$ and $b$ is $1$).
1
vote
1answer
34 views

Can number of constraints be less than number of variables in Linear Programming?

In standard form of LP we have $n$ variable and $m$ constraint. In simplex algorithm we set all non-basic variable to zero and at most $m$ basic variable have positive value. if $m < n$, then at ...
8
votes
1answer
363 views

Puzzle: Give an algorithm for finding a frog that jumps along the number line

You are playing a game, your goal in this game is to catch a frog that's leaping between natural numbers. At first, the frog is found at the number $a \in \mathbb N$ which is not known to you. Each ...
1
vote
1answer
32 views

Efficient method for finding the number of combinations of values so that the sum is a certain number

I know one can make a sample space for this problem, but are there any other ways of solving a problem like this: Each letter has a number value. Find all possible combinations of the letters that ...
0
votes
2answers
31 views

Scan line algorithm for intersecting polygons

Given two sets of polygons $P_1 = \{s_1,...,s_m\}$ and $P_2=\{s_m+1,...,s_n\}$ with total number of $n$ segments, the previous and next segment on it's polygon can be determined in $O(1)$. Describe a ...
6
votes
1answer
219 views

Prime Number Sieve using LCM Function

How to prove following conjecture ? Definition : Let $b_n=b_{n-2}+\operatorname{lcm}(n-1 , b_{n-2})$ with $b_1=2$ , $b_2=2$ and $n>2$ . Let $a_n=b_{n+2}/b_n-1$ Conjecture : Every term of ...
7
votes
2answers
64 views

Infinite sequence of $3$ numbres with nonrepeated parts.

I am thinking about this problem. Can we construct infinite sequence with $3$ numbers so that no repeated parts exist in it? There should not be subsequence with $2k$ numbers so that its left and ...
3
votes
0answers
36 views

Add vectors from a set to reach the goal vector, using the minimum possible cost

I am trying to solve a problem in an optimal way. The problem is as follows: We have an n-dimensional space In this space, we have a "finish" point with n coordinates, all non-negative We have a set ...
3
votes
0answers
78 views

subtract a number from its digits until it reaches 0 [closed]

Can anyone help me with some algorithm for this problem? We have a big number (19 digits) and, in a loop, we subtract one of the digits of that number from the number itself. We continue to do this ...
0
votes
0answers
56 views

Big Oh Complexity of the algorithm “for $i=1$ to $z$, for $j = 1-X(i)$ to $Y(i)-n^2$ set $k=0$”

I've got a past paper algorithm question I'm trying to complete. I was hoping you could helped me, if so great if not then it's fine :P if you can keep in mind ironically (yep cs student) I'm not ...
0
votes
0answers
54 views

Implementation of disjoint sets with union

I am looking at disjoint sets that support the function of the Union. The technique of height reduction of a tree: We always merge the smaller tree to the greater one, i.e. we make the root of the ...
6
votes
1answer
87 views

How to eliminate some edges of a lattice to get exactly k paths?

We have an $n$ by $n$ lattice. We want to find a way to eliminate some edges, so that there are exactly $k$ paths from $(1,1)$ to $(n,n)$ of length $2n-2$. (this means our paths should be NE). I don't ...
2
votes
0answers
56 views

Show that matrices multiplication and LUP decompositions have the same difficulty

Let $M(n)$ be the time to multiply two $n\times n$ matrices, and let $L(n)$ be the time to compute the LUP decomposition of an $n\times n$ matrix. How to show that multiplying matrices and ...
1
vote
0answers
40 views

partitions of finite set in same-size parts having at most one element in common

Given g ≥ 2, k ≥ 1 and a population of p = kg workers, I'm trying to figure out the longest series of work shifts such that: during each shift, all workers work in k teams of g people; any two ...
1
vote
1answer
59 views

general formula for permutations with some ordering

Assume I want all permutations of a set of numbers with certain numbers must go before others. Similar to this question but I'm looking for a more general formula. For example the set ...
0
votes
1answer
13 views

A question about importance sample and Metropolis Algorithm

I am reading this paper by Beichl, I., & Sullivan, F. (2000) on Metropolis algorithm. I understand rejection sample. In the section "The Rejection Sample", I can understand the equation: ...
1
vote
1answer
73 views

Differential problem solving with Euler and Heun methods

I have to write application which solves task presented below. I only know some c# so I will stick to it. It is some kind of homework but I am asking for help with understanding this and advice for ...
3
votes
1answer
44 views

Find an assignment of courses to days so that no student has more than one exam on the same day is NP-complete?

Given a list of $N$ courses, $M$ students, the list of courses each student is taking and an integer $K$ representing the duration of the exam phase, is there an exam schedule consisting of $K$ dates ...
11
votes
4answers
234 views

How to compare products of prime factors efficiently?

Let's say that $n$ and $m$ are two very large natural numbers, both expressed as product of prime factors, for example: $n = 3×5×43×367×4931×629281$ $m = 8219×138107×647099$ Now I'd like to know ...
0
votes
1answer
48 views

Why won't my conjugate gradient algorithm work?

I made this simple Conjugate Algorithm on Matlab n = length(b); r0 = b - A*x0; p0=r0; k=1; n0=(r0')*r0; while n0 >= eps && k <= n ...
0
votes
1answer
33 views

Discrete Math number of multiplications it takes to calculate $x^{15}$

This is in the topic of time complexity and algorithms in my list of problems and I really wanted to figure it out how to take a grip. Here's the problem: Find the number of multiplications needed ...
1
vote
0answers
19 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than 2 I should choose a special partitioning hyperplane for the divide and conquer algorithm to get O(n log n). I am confused because to choose this ...
1
vote
1answer
50 views

Detection of self intersection point of curve

What numerical procedure is be adopted to detect self-intersecting parametrized points $ [x(t), y(t) ] $ in $ \mathbb R^2 $ ? Observation : @ roots ( t= 2, t=-1 ) parabola has double value with ...
7
votes
2answers
96 views

Transform polygons into one another?

I am aware that there must be no standard way to achieve this, but I don't know what has been done so far. I feel like I'm missing keywords to investigate further. I have any two 2D polygons $a$ and ...
2
votes
0answers
27 views

What is the most “unbalanced” vector between two given vectors?

Let $\mathbb{R}_+$ be the set of non-negative real numbers. Let $m$ be a positive integer and $\leq_m$ be the product order on $\mathbb{R}_+^m$. Lastly, given a vector $V = (v_1, \dots, v_m) \in ...
1
vote
1answer
79 views

Is there a mathematic expression for this sequence

I want to arrange a sequence from $1$ to $n$, so that every time I (i) remove 1 number and add it to the list; (ii) move the next number to the bottom of the sequence. finally I can get a sequence ...
0
votes
1answer
99 views

sudoku algorithm explanation formula

I'm implementing a sudoku solver using human way algorithm. Which have 3 constraint, different number ini row, cell and box. I googled and I got ...
5
votes
1answer
81 views

Can all math operations be reduced to a sufficiently complex algorithm?

Say I could only perform one operation (addition) from addition I could derive subtraction by adding a negative number. Also, from addition I could derive multiplication, like $ a n $, just add $ a $ ...
0
votes
0answers
41 views

Algorithm-generating algorithm

Is there an algorithm that can create other algorithms based on any number of arguments? For example, a way to determine a function $ f (x) $ from a given input and a given output? I.e. if $ f (2)=4 $ ...
1
vote
1answer
36 views

Give tight asymptotic bounds for the following recurrence. T(n) = 3T(n/3)+log n

Give tight asymptotic bounds for the following recurrence. Justify your answers by working out the details or by appealing to a case of the master theorem $$T(n) = 3T\left(\frac n3\right)+\log(n)$$ ...
1
vote
3answers
53 views

On finding the $n$-th term of an arithmetic progression

Given the common difference $d$, and first term $a$ (say). It is very easy to find the $n$th term of an arithmetic progression. My question is if we are given two common differences say $d_1$ and ...
2
votes
0answers
73 views

Checking if a relation is complete

I have a transitive relation $\subset$ on a (finite and small) set S and a list of pairs $x_i\subset y_i.$ I would like to check if my list is complete in the sense that if $x\subset y$ then there are ...
0
votes
1answer
74 views

Given a set of integers and operators, find if number is obtainable

Let's say I have a set of sequential integers $(x_1,x_2,x_3,x_4,\ldots,x_n)$ and operators $(+,-,\times,/,(,))$ (arithmetic operators and parenthesis). Now say we can have any $t$ numbers from the ...
0
votes
1answer
41 views

How many primes can be represented in JavaScript?

In JavaScript, the largest odd positive number representable is $2^{53}-1$. All integers between 1 and $2^{53}-1$ can be represented without loss of precision. How many prime numbers can be ...
2
votes
1answer
25 views

Max-Cut not optimal solution example?

I currently learning about the Max-Cut problem, but i'm little bit confused about how the 2-approximation algorithm works. The algorithm is as follows: Start with an arbitrary partition Find a ...
4
votes
5answers
733 views

Lottery odds calculated in your head, or pen and paper.

So I am working out the odds for a lottery, picking 4 numbers between 1-35. The equation is: $$\mbox{odds}=\frac{35\cdot 34\cdot 33\cdot 32}{1\cdot 2\cdot 3\cdot 4}=52360$$ Yes, I can work this out ...
2
votes
0answers
22 views

Coefficients of Lagrange resolvent

I'm trying to make sense of some things I read about Galois theory. Let $p$ be a monic polynomial of degree $n$ with known coefficients $a_i$ and unknown roots $x_i$: \begin{alignat*}{2} p(X) &= ...
1
vote
1answer
50 views

The traveling salesman problem is NP-complete Reduction

The traveling salesman problem is NP-complete. Proof: First, we have to prove that TSP belongs to NP. If we want to check a tour for credibility, we check that the tour contains each vertex once. Then ...
3
votes
1answer
31 views

Finding all local $k$-maximums in sequence $a_1, a_2, \ldots a_n$.

For given sequence of numbers $a_1, a_2, \ldots, a_n$ we say that $a_i$ is $k$-local maximum, if $i > k$ and $a_i$ is largest of numbers $a_{i - k}, a_{i-k+1}, \ldots, a_i$. How can we find all ...
0
votes
2answers
50 views

Calculating interaction beween 100 objects with each other.

The other day I was thinking about how many interactions 100 objects would have with each other. By that I mean if we are using a computer to draw the scene with 100 point lights, the total result ...
2
votes
1answer
34 views

Predicting the increase/decrease of number

I have these entries in my database that looks like this: ...
3
votes
1answer
42 views

Finding $m$ largest numbers from union of $k$ sorted lists $A_1, A_2, \ldots, A_k$

We are given $k$ sorted lists $A_1, A_2, \ldots A_k$ with corresponding sizes $n_1, n_2, \ldots n_k$. How can one find $m$ largest elements (numbers) from union of lists $A_1, A_2, \ldots, A_k$? We ...
1
vote
2answers
31 views

Finding median of union of two sorted (ordered) lists

We are given two sorted list of numbers $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$. Question is, how to find a median for list $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$. Algorithm should ...
0
votes
1answer
41 views

Quicksort-How did we get the relation?

At the proof of the theorem that the expected time of Quicksort is $O(n \log n)$, there is the following sentence: We suppose that the partitions are equally likely, so the possibility that the sizes ...
2
votes
0answers
87 views

Traveling salesman neighborhood

I am solving some TSP problems and i got this one and i am not pretty sure about my answer. By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined ...
9
votes
2answers
260 views

Proving that $T$:$(x_1,…,x_n) \rightarrow (\frac {x_1+x_2}{2},\frac {x_2+x_3}{2},…,\frac {x_n+x_1}{2})$ leads to nonintegral components

Start with $n$ paiwise different integers $x_1,x_2,...,x_n,(n>2)$ and repeat the following step: $T$:$(x_1,...,x_n) \rightarrow (\frac {x_1+x_2}{2},\frac {x_2+x_3}{2},...,\frac {x_n+x_1}{2})$ ...
2
votes
2answers
124 views

Knapsack problem NP-complete

Show that the knapsack problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete. Hint:Use the exact ...
3
votes
0answers
93 views

a problem about finding an algorithm for a spanning tree in a 3-regular graph

"Consider the connected 3-regular graph G. Find an algorithm that produces a subgraph S of G which is a spanning tree and if you remove S from G then G is divided into some components that each of ...
0
votes
1answer
27 views

Create a map of connected nodes from a list of edges in $O(n^2)$

I have a directed graph. It may or may not be a DAG. I would like to create a map in $O(n^2)$ time to find all nodes that are accessible from a node on a directed path, where $n$ is number of ...