Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

0
votes
0answers
50 views

Subset Sum problem computational complexity

Is it feasible from computational complexity point of view to solve subset sum problems with thousand of variables (like 2000 or 10000 variables) efficiently in shorts period of time ...
1
vote
0answers
30 views

Performance estimation of shellSort

I'm trying to make a performance estimation for shell-sort algorithm. And I fail in it. My formula: equals to where dz is outer while-loop, dy is middle for-loop, and dx is inner for-loop ...
5
votes
0answers
76 views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N ...
1
vote
0answers
32 views

Josephus problem extended

Suppose there are $2n$ people in a circle; the first n are good guys and the last n are bad guys. If we go around the circle executing every $m$-th person, all the bad guys are first to go. How to ...
0
votes
0answers
10 views

how to make a graph of number of comparisons vs number of elements of a sorting algorithms?

can someone suggest me a tool/software which i can use to make a (number of comparisons) vs (number of elements) GRAPH of a sorting algorithm ? like you see similar type of graph in the research ...
0
votes
0answers
30 views

Maximum Number of vertices not sharing edge

Given a N*N adjacency matrix of graph I need to find the size of maximum set of vertices that do not share any common edge between any two vertices of the graph. Like : Say we have 3*3 matrix as 0 1 ...
0
votes
0answers
24 views

Explanation of LexBFS

I trying to understand the LexBFS algorithm, which is an algorithm for ordering the vertices in an undirected graph. Because I am not a computer science student, I am not able to understand the ...
0
votes
3answers
38 views

Place 1s and 0s

Given N 1's and M 0's i need to put them in a row in such a way that their are no two 0's together and no 3 1's together.How to do this question Please help If it is not possible than tell that its ...
1
vote
3answers
82 views

Finding set of non recurring non terminating decimals

I need to find a set of two Integers P and Q such that ...
13
votes
2answers
203 views

$e$ popping up in topic I'm unfamiliar with

I programmed up a little algorithm that goes like this: Fix two positive, real numbers, call them $\alpha$ and $\beta$. Generate a new, random, real number, $x \in [0,1]$ Set $\alpha$ = ...
1
vote
1answer
37 views

How many majority elements can there be in a sequence?

You are given a sequence $S$ of $n$ numbers. An element $x$ in $S$ is called a majority element if it occurs more than $n$/2 times in $S$. This question asks you to describe two algorithms that decide ...
1
vote
1answer
113 views

Which greedy algorithm is optimal?

The following question is a homework problem for a course called Design and Analysis of Algorithms. In the problem, there is a minimized cost function and two greedy algorithms. I am asked to show ...
0
votes
0answers
32 views

Algorithmically constructing graphs with specified degrees

In graph theory books there are lots of problems similar to these: Construct a graph of 7 vertices with exactly 5, 2, 1, 1, 1, 1, 1 degrees Prove or disprove that there is graph of 4 vertices with ...
0
votes
2answers
70 views

Longest Contiguous sequence Problem

Given 2 strings each of length upto $10^5$ Where String 1 is smaller or equal to length of String 2.Now i need to find longest contiguous sequence common in both the strings. If their are multiple ...
0
votes
1answer
25 views

reverse (left) arrow in an algorithm?

There is a algorithm, in which author has written steps of algorithm like this, 1.initialization:set up the threshold (th) and maximum iteration number, $I$. $i\leftarrow 0$ 2.calculate x while ...
0
votes
1answer
24 views

Does anyone know an algorthim to generate the following matrix?

Hi all I have the follow array: \begin{equation} \begin{matrix} L(1)\\ L(2)\\ \vdots\\ L(N)\\ \end{matrix} \end{equation} And I need the following matrix: \begin{equation} \begin{matrix} L(1) & ...
0
votes
0answers
25 views

Master Theorem Exercise

Could you please help me with a master theorem equation i have? for master theorem we have T(n) = aT(n/b)+f(n) where a>=1, b>1 here i have: T(n) = 5T(n/4)+12 a = 5; b = 4 and f(n) = 12; Now is c = 0 ...
1
vote
2answers
42 views

Calculate a recursive equation in terms of theta

I am struggling with the following equation for one week! Please help me solve it. $$T(n)=T(\frac{n}{2})+\frac{n}{logn}$$ So far, I have come to the equation $T(n)=\Sigma \frac{2^x}{x}$
3
votes
5answers
56 views

Round a set to the nearest values in another set (2D), faster algorithm with Matlab

Given a set of numbers, like A={{1,2.5,3}, {4.2,7,10}}; and another set of numbers, like B={1,2,3,4,5}; Is there a fast ...
0
votes
2answers
109 views

Maximise the happiness among children

Given N different candies and M childrens. Each ith children demands for K[i] different candies and will ONLY BE HAPPY IFF HE GET ALL THOSE DIFFERENT CANDIES WHICH HE DEMANDED. Now i want that ...
1
vote
1answer
15 views

comparing the orders of complexity

Suppose we have $f(n)=O(g(n))$. Can we claim $f^2(n)=O(g^2(n))$ ? I need to use it in a proof and I think it is correct.
0
votes
0answers
45 views

Solving the recurrence $F(0) = X$ and $F(i)=A \cdot (F(i-1))^2 + B \cdot F(i-1) + C$

Moderator Note: This is a current contest question on codechef.com. I am given $F(0)=X$ and $F(i)=A \cdot (F(i-1))^2 + B \cdot F(i-1) + C$ for $1 \leq i \leq N$. Now given $N,A,B,C$ and $X$, how ...
0
votes
1answer
45 views

Catastrophic Cancellation

I need some informations about algorithms to solve the problem of Catastrophic Cancellation, or in general to calculate mean and variance of a data stream. For example about Donald Knuth's algorithm ...
4
votes
1answer
44 views

Randomly generate an matrix $A$ s.t. $A^m = I$

Fixed $n$, I want to randomly generate a $n \times n$ real matrix $A$ from the set: $\{A \in \mathcal{M}_{n \times n}(\mathbb{R}): \exists m \in \mathbb{N} \mbox{ s.t. } A^m = I\}$ I think I should ...
0
votes
1answer
23 views

asymptotic analysis

For each of the following sentences involving functions f and/or g, find a counterexample to show that it is false: What is meant by counterexamples?
0
votes
3answers
52 views

How to find a set of ascending natural numbers which when added to another set of ascending natural numbers sums to a certain number

Given: $$ X = \left\{ x_1, x_2, \ldots , x_n \right\}\text{ with }x_i \in \mathbb N\text{ and }1 \le x_i \le x_{i+1} $$ $$ z \in \mathbb N $$ Wanted result: $$ Y = \left\{ y_1, y_2, \ldots , y_n ...
0
votes
0answers
45 views

Creating rounds for a tournament with varying pools, teams and fields

I asked a similar question here: Effcient Box packing algorithm but have been unable to implement it for what I actually need it for. I also tried this method: ...
0
votes
0answers
36 views

Map Subgraph Ismorphism Problem to SAT Problem

The Subgraph Isomorphism (SI) problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H. I want to ...
0
votes
1answer
69 views

Working algorithm for testing two rectangles for overlapping in Earth GPS coordinates plain

Here is a seemingly simple, but actually quite tricky problem: I am trying to figure out the correct algorithm to test intersection/overlapping of two rectangles, which are plotted on the Earth's ...
1
vote
1answer
35 views

Checksum of a set of real numbers

I have a set of real numbers $a_i \in (-r, r)$ which can be represented as the tuple $(a_1, a_2, ..., a_n)$ where $n \in (5,10)$. I am searching for an algorithm to generate a checksum so that I can ...
4
votes
0answers
61 views

Binary Palindrome

Let an integer n be given. Write the integers from 1 to n in binary notation successively from left to right. In the resulting string consisting of zeros and ones, choose a palindrome substring of ...
0
votes
1answer
45 views

Calculating run times of programs with asymptotic notation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. Sorry if this is a dumb ...
0
votes
0answers
16 views

find a formula to find best approximation to a number using a collection of numbers

I am trying to find a formula to find best approximation to a number using a collection of numbers. for example i have a collection of numbers like:2,5,2,25,4,50 ...
0
votes
0answers
10 views

parallelizing $k$-means

I'm having trouble thinking about the following. If we have two machines 1 and 2 that evenly split a set of data points, does $k$-means separately, then averages the result, does this agree with just ...
1
vote
2answers
33 views

Approximating 'big' ratio with 'small' ratio

Given a ratio $ \frac{m}{n}, p \in N, q \in N $ where either $m$ or $n$ (or both) is a very big number, how can we find a ratio $ \frac{p}{q}, p \in N, q \in N $ which estimates $ \frac{m}{n} $ up to ...
0
votes
1answer
25 views

How to come up with formula for this number growth

I have difficulties to come up with a formula to achieve this in my programming challenge : The input number ranges between 100 to 10.000 (all integers), then the output would be 0.1 - 10, so the ...
13
votes
4answers
178 views

perfect play in 1-dimensional Minesweeper

In 1-dimensional Minesweeper with a known number of mines (that are distributed uniformly), is there a known somewhat-simple strategy for perfect play? When there are n cells and [0 or n-1 ...
0
votes
2answers
25 views

What is his algorithm of taking square of a 5 digit number?

I was watching this TED talk: Mathemagics and the performer, as his final trick, attempts to square a 5 digit number in a fairly short amount of time by as well thinking out loud (starting at 11:00, ...
0
votes
1answer
38 views

How to extract all the points from a noisy surface?

I have points representing a bridge like in this picture: My goal is to get all the points that are in the red box. These points all share a common surface that is not necessarily planar. The ...
0
votes
0answers
12 views

Algorithm for Emulating Change of Currency Exchange Rates over Time

I am trying to identify a mathematical that I could use to emulate a normal change in currency exchange rates between two currencies, for example U.S. Dollars and German Euros. My goal is to emulate ...
1
vote
1answer
15 views

How to recognize if an algorithm working on ordinal data will also work if the ordering is reversed?

Inspired by a comment on this question. Assume that I have an algorithm which uses ordinally scaled data. The algorithm in the original question was the solution of the Secretary Problem. It uses ...
8
votes
2answers
101 views

Mathematicly Untangeling Untangle.

I have a new addiction, I play Untangle to often, and i am wondering what is the mathematics behind it. some free games: (but be warned highly addictive) Javascript: ...
0
votes
0answers
36 views

Maximum independent set problem

I need to study about the maximum independent set problem in graph theory. I need to study the $P_t$ free graphs and many other such variants and look up their maximum independent set characteristics. ...
0
votes
0answers
15 views

chained max notation

I'm confused on how to implement a quality indicator for multi-objective optimization. I don't understand the following notation. $$I_{\epsilon} (A,B)=\max_{z^2 \in B} \min_{z^1 \in A} \max_{1 \le i ...
2
votes
1answer
112 views

How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c?

This recurrence relation was inferred from the function $f(n, m) = f(n - 1, m) + f(n, m-1) + c$. After expanding the latter, I ended up with the following: $$f(n,m)=\begin{cases} 0,&\text{if ...
0
votes
0answers
19 views

Notation help: “linearizing” multidimensional indices

I have an algorithm that makes use of a multidimensional data structure, e.g. $A(i,j,k)$, $1\le i,j,k\le n$. I am looking for a simple notation that enables me to refer to the $\ell$'th elements of ...
1
vote
2answers
100 views

How to check if two given line segments intersect

I was trying to understand convex hull problem..i came across a method to check intersection of line segment. Suppose the points are $p_1, q_1$ and $p_2, q_2$. One case says that the line segments ...
2
votes
1answer
22 views

Number that is a certain percent between two other numbers, without subtraction

The formula I'm trying to write is relatively simple. I'm looking for a number that is a certain percent between two numbers, i.e: 6 is 50% between 2 and 10. 8 is 75% between 2 and 10. Subtracting ...
0
votes
0answers
23 views

Calculate the fraction of volume of a rectilinear grid cell within some radius of the origin

I have a sphere (radius $R$) on a rectilinear grid. Some cells intersect the edge of that sphere, call them 'edge cells'. Designate a given cell by indices $[i,j,k]$ which refer to the lowest-index ...
1
vote
0answers
14 views

Encoder based on large similar data

Let us say you (Alice) and another agent (Bob) share a large piece of data (say, the Gutenberg project collection of books, or the Linux kernel. You want to send a smaller but still large piece of ...