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)

0
votes
0answers
7 views

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

I found a hard problem in one of my books about graphs and i have been thinking on it for 2 weeks. The problem is: "Find an algorithm that finds a spanning tree inside a connected 3-regular graph ...
1
vote
1answer
455 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
0
votes
1answer
18 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 ...
0
votes
1answer
33 views

set notation, for indexed family

I'm having trouble to express formally, a trivial algorithm, which is something like this: parameters: a set of students $S$ that have taken a course $c_i$, where course belongs to a of set courses ...
0
votes
0answers
24 views

How do I detect if two polygons overlap each other or not?

I'm developing a game engine. Currently I'm writing the collision detection part. I have to write down an algorithm which detects if two given polygons are overlapping each other or they are separated ...
1
vote
1answer
27 views

Questions concerning assumptions to conclude that $\operatorname{P}=\operatorname{NP}$

Suppose you find a reduction from the $k$-vertex-cut problem to the hamiltonian-path problem. In particular, you find an algorithm $A$ that, given the graph $G$ and the number $k$, outputs a ...
1
vote
0answers
11 views

Heuristic & Approximation algorithms

I just came to know the definition of r-approximation algorithm. I just want to know whether infinite-approximation algorithm is a heuristic algorithm? Is heuristic algorithm is an ...
0
votes
0answers
8 views

Divide the segment into parts with gaussian length distribution

I want to divide the segment having length 2a into N parts with normally distributed lengths. Is there any simple algorithm to do so? i.e how to find the coordinate of i-th point ?
4
votes
5answers
2k views

Does this algorithm find prime numbers only?

I'm writing code to help find prime numbers within a certain range. Here's my general pseudo-code: Iterate through every single number in the range. If the number is 2, 3, 5, or 7; then mark it as a ...
2
votes
1answer
19 views

What's the meaning of “reuse space”?

I'm reading this. $\quad \;\;$ What's the meaning of reuse space in here?
2
votes
1answer
42 views
+50

Applying MCMC Metropolis algorithm

I'm interested in all possible paths (on the grid $\mathbb{N}^2 $) that goes from $ (0,0) $ to $ (n, n) $. At each step there are two possibilities: go right or go up. The path is a sequence $ ...
1
vote
1answer
38 views

Algorithm for risky investments in banks

I made the following programming question on stack overflow but the users said it was more of math question. Here it is. Situation You start with a fixed amount of money, take it as $\$1000$. You ...
0
votes
1answer
20 views

How to get the maximum and minimum number of length $m$ and the sum of the digits $s$

How to get the maximum and minimum of length $m$ and the sum of the digits $s$ By example: Length: 2 Sum of its digits: 15 Max: 96, Min: 69 Length: 2 Sum of its digits: 2 Max: 20, Min: 11
2
votes
0answers
34 views

How can we find the elements?

I want to describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set ...
1
vote
1answer
52 views

How does the function work? [on hold]

Could you explain me the function of the following two algorithms? ...
1
vote
1answer
40 views

Expected time of Quicksort

I am reading the proof of the theorem: The Algorithm Quicksort sorts a sequence of $n$ elements in $O(n \log n)$ expected time. The proof is this: For simplicity in the timing analysis assume ...
0
votes
1answer
30 views

Number pattern prediction algorithm [duplicate]

Since childhood we are all familiar with the task of predicting the next number in a sequence. From something simple like, $2,4,6,...$ and $4,9,25,...$ to something more complex like, ...
1
vote
1answer
22 views

Las Vegas Algorithms

In some notes i'm reading it says that the definition of a Las Vegas Algorithm is An algorithm which always outputs the correct answer but has unbounded running time, with the expected running time ...
4
votes
2answers
568 views

Card Shuffling [SPOJ]

The original question is posted on SPOJ, and included below: Here is an algorithm for shuffling N cards: 1) The cards are divided into K equal piles, where K is a factor of N. 2) The ...
2
votes
3answers
24 views
0
votes
1answer
19 views

A language $L$ is polynomially transformable to $L_0$

Could someone explain to me the following definition?? A language $L$ is polynomially transformable to $L_0$ if there is a deterministic polynomial-time-bounded Turing machine $M$ which will convert ...
5
votes
1answer
48 views

Special case of Minimum Spanning Tree

I have been bashing my head trying to solve the following problem for the past two days, it is a review question in preparation for my exam and I assume something similar will be on it. The problem ...
0
votes
0answers
27 views

Two convex polygon intersection from set of m convex polygons with total n vertices

I have a set of m convex polygons $(p_1,p_2, \ldots p_m)$. $n_i$ is the number of vertices in $p_i$. $\sum_{i=1}^{m} n_i = n$. Each polygon has vertices listed in anti-clockwise direction, starting ...
1
vote
1answer
26 views

Find every possible distribution of the x elements considering a constraint on one of them

Considering a number r of triplets { a, c, i } I'd like to know which procedure / math field should I use to calculate every ...
0
votes
1answer
11 views

wondering about the greedy algorithm to the set cover problem

i'm currently learning about the Set-Cover problem and i have a question about it. Using the greedy algorithm to solve this, some proof says: Since the optimal solution uses k sets, there must some ...
2
votes
1answer
25 views

best possible algorithm for finding out an ordering $i_1i_2..i_n$ such that $b_{i_k}=a_{i_k+1}$ for $k=1$ to $n-1$

Suppose that I have a given set of items $S$. Now I have been given $n$ sequences made using the items in $S$ like $$a_1(...)b_1, a_2(...)b_2,...a_n(...)b_n$$ The sequences have lengths ...
0
votes
3answers
52 views

How to find upper and lower bound without using formula?

I am studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything usefull. Prove the following sum is theta(n^2) (we have to find ...
2
votes
1answer
27 views

NP Solvable in Polynomial Time

I just took an exam and am a little curious about this question (it may not be verbatim, but the idea is clear): TRUE/FALSE: If an NP complete problem can be solved in polynomial time, then P = NP. ...
3
votes
2answers
575 views

maximum flow ford-fulkerson analysis

I am reading about maximum flows in Introduction to algorithms by Cormen etc. Ford-Fulkerson algorithm is given below. FORD-FULKERSON(G, s, t) ...
5
votes
3answers
971 views

Calculate Runge-Kutta order 4's order of error experimentally

The Problem Use the order 4 Runge-Kutta method to solve the differential equation $ \frac{\partial^2 y}{\partial t^2} = -g + \beta e^{-y/\alpha }*\left | \frac{\partial y}{\partial t} \right |^{2} $ ...
10
votes
2answers
817 views

Algorithm(s) for computing an elementary symmetric polynomial

I've run into an application where I need to compute a bunch of elementary symmetric polynomials. It is trivial to compute a sum or product of quantities, of course, so my concern is with computing ...
0
votes
0answers
29 views

Show that it is NP-complete [on hold]

Show that the problem of determining whether a regular expression over the alphabet $\{0\}$ does not denote $0^*$ is NP-complete. Could you give me some hints how I could do that??
3
votes
1answer
99 views

What kind of edge do we have?

In order to find the kind of the edges of a graph, at which we applied the Depth-first search algorithm, we could use this: $$\begin{bmatrix} \text{ tree edges: } x \to y & [d[y],f[y]] \subset ...
1
vote
1answer
270 views

How to get numbers with distinct digits within some range?

I have a little program I'm working on for my project (a simple practice in school), part of the program is that it should receive input composed of an array of 7 digit (or less) numbers which should ...
1
vote
0answers
10 views

Asymptotic Notations Iterative Method for Solving Recurrences

Recurrence T(n)= T(n^1\2) + O(lg(lg(n))) The solution suggests substituting m = lg(n) So the recurrence becomes S(m)= S(m\2) + O(lg(lg(m))) Then solving using iterative method for solvng ...
0
votes
1answer
45 views

Find smallest $x$ such that $a^x \equiv b \bmod p$

Problem: How do we find smallest $x$ such that $a^x \equiv b \bmod p$, where $p$ is a prime and $1 \le b,a \le p$ and $a$, $b$, and $p$ are given and fixed. If there is no such $x$, how do we check ...
0
votes
1answer
10 views

Efficient algorithm for slightly generalized attribution problem

I have what I believe is an attribution problem: Given an $m \times n$ matrix, I need to select $p = \min\{m,n\}$ elements maximizing their sum such that they do not share a row or column. More ...
1
vote
2answers
46 views

Avoiding extraneous solutions

When solving quadratic equations like $\sqrt{x+1} + \sqrt{x-1} = \sqrt{2x + 1}$ we are told to solve naively, for example we would get $x \in \{\frac{-\sqrt{5}}{2},\frac{\sqrt{5}}{2}\}$, even though ...
0
votes
1answer
29 views

Shifting Nth Root Algorithm

Does anyone have a very simple dumbed-down explanation of the shifting nth root algorithm on paper (finding an nth root with a method similar to long division)? I know very basic addition, ...
4
votes
2answers
90 views

Number of solutions of a simple equation

Problem How to count the number of distinct integer solutions $(x_1,x_2,\dots,x_n)$ of the equations like : $$|x_1| + |x_2| + \cdots + |x_n| = d $$ the count gives the number of coordinate points ...
4
votes
1answer
81 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
2
votes
2answers
354 views

Largest submatrix problem

Given a $N*M$ grid I want to find biggest submatrix not necessarily a square one that has all the value in it same. Like If $N=4$ and $M=5$ and matrix is $$ ...
4
votes
1answer
164 views

Will this algorithm stop before time?

For every $n \in \mathbb N$, let's define $a_0 = 0$, $$\begin{cases} a_{i+1} = 2a_i + 1 \pmod {2^n}, &\text{if it never appeared before} \\ a_{i+1} = 2a_i \pmod {2^n},& ...
6
votes
2answers
677 views

Lights Out Variant: Flipping the whole row and column.

So I found this puzzle similar to Lights Out, if any of you have ever played that. Basically the puzzle works in a grid of lights like so: 1 0 0 00 0 0 00 1 0 0 0 0 1 0 When you selected a ...
3
votes
1answer
47 views

Knuth's algorithm for Mastermind question

I'm reading about Knuth's algorithm to solve the mastermind game, so I've looked in wikipedia and read the pseudo-code (http://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm). I ...
3
votes
2answers
48 views

Objects into two bags puzzle

I found a maths puzzle somewhere and a part of it as below: Kelly wants to place n objects $a_1,a_2,⋅⋅⋅,a_n$ into two bags. For each $i=1,2,⋅⋅⋅,n$, the weight of $a_i$ is $w_i$ kilograms. The ...
0
votes
0answers
64 views

Maximum XOR of a set with an integer [closed]

I have to find XOR of a number say $K$ with all the subsets of set $P$ such that $P$ contains all non zero integers (can contain at most 1000 integers), so that my result of XOR should be the maximum. ...
2
votes
1answer
45 views

Weights - Objects into bags puzzle

I found a maths puzzle somewhere and a part of it as below: Kelly wants to place n objects $a_1 , a_2 , ··· , a_n$ into $k > 1$ bags. For each $i = 1 , 2 , ··· , n $, the weight of $a_i$ is $w_i$ ...
0
votes
2answers
46 views

Hexagonal Tessellation on a sphere

I want to detect collision of a sphere with another object and to find out(show) the deformation of the sphere. I have come to know that hexagon(regular)tessellation of a sphere is the most ...
0
votes
0answers
20 views

How quickly can we multiply hypercomplexes?

If we start with a hypercomplex number with $2^n$ entries, how quickly can we multiply it by another hypercomplex number, modulo a prime? EXAMPLE For example, with $n=1$, we get the complex numbers. ...