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
16 views

Algorithm or program to verify packaging results

Is there an open source program or algorithm to try to repeat the optimal packaging results listed in http://www2.stetson.edu/~efriedma/squinsqu/ ? I tried to make my own program but it was hopelessly ...
-1
votes
2answers
33 views

How may occupied positions are there?

Consider an array, that can have a huge ( or infinite ) number of positions, but only the first $n$ positions are occupied(only $n$ of them contain valid elements), and the remaining are empty. ...
0
votes
1answer
31 views

Merge two sets, list and tree

We are given two sets $S_1$ and $S_2$. We consider that $S_1$ is implemented, using a sorted list, and $S_2$ is implemented, using a pre-order sorted tree. I have to write a pseudocode, that ...
2
votes
1answer
69 views

Checking two graphs to be homeomorphic

How can I check that two simple connected graphs are homeomorphic? I know the defenition of homeomorfism, but I can't figure out when to stop subdividing, algoritmically. I need here some stopping ...
2
votes
3answers
24 views

Number of layers in nested convex hull

Find the maximum number of nested convex hull
1
vote
0answers
20 views

Help with proof about merge two heaps to one heap…

We have two heaps: $H_1,H_2$ that have $n_1,n_2$ elements ($H_1$ have $n_1$ elements and $H_2$ have $n_2$ elements). We know that the smallest element at $H_1$ is bigger the root (the biggest element) ...
3
votes
2answers
43 views

Help with understanding the polynomial long division algorithm

I saw this algorithm at Wikipedia: ...
6
votes
3answers
712 views

Finding prime factors by taking the square root

I'm trying to solve the third Project Euler problem and I'd like a little help understanding a mathematical concept underlying my tentative solution. The question reads: The prime factors of ...
0
votes
1answer
57 views

Zig-Zag traversal of list

Suppose that each node of the list has the following structs: string num next It is given a string $w$. Suppose that $w$ is in the list at a node $p$, of which the struct num has the value n. We ...
1
vote
1answer
23 views

Algorithm to find string

Given a string $w$, we want to find the last string in the list, that precedes alphabetically $w$ and ends with the same letter as $w$. Example: $\text{ w=crabapple }$ $L=\langle \text{canary, cat, ...
0
votes
1answer
23 views

Visible objects from a point in a polygon with holes in 2d

The problem is the following: Given a polygon P with h holes/objects and a point c inside P but outside the holes/objects. P has n given vertices and each hole/object h has 4 vertices (the ...
0
votes
0answers
7 views

Algorithm for creating a directed scale free network with a fixed amount of nodes

I'm trying to figure out an algorithm that produces a scale free, directed network, for which I can give the final amount of nodes as an input. Now, this is a little bit tricky for a few reasons, so ...
0
votes
1answer
24 views

Algorithmic question regarding permutations

An algorithm i'm reading has the first step saying. The algorithm is a path enumeration algorithm which puts all permutations into lexicographic order. The algorithm works as follows Input: A ...
1
vote
1answer
29 views

Power set ordered by sum and Dijkstra shortest path

I've needed to enumerate the power set ordered by the sum of elements in each subset. Luckily I've found a nice solution here: Algorithm wanted: Enumerate all subsets of a set in order of increasing ...
0
votes
0answers
15 views

Plot of an increasing computable function is a solvable subset of $\mathbb{N^{2}}$

I got stuck at one of the steps of the problem's solution. The problem is to prove that the plot of $f: \mathbb{N} \rightarrow \mathbb{N}$ (computable increasing function) is a decidable subset of ...
2
votes
4answers
60 views

What does it mean to say breaking RSA generically is equivalent to factoring?

I am giving a one hour presentation on the RSA crypto-system as one of the requirements for Masters degree. I just want to get some facts straight here. I was told casually by a professor that RSA is ...
1
vote
0answers
53 views

Determine sign of sum of square roots

Problem Given positive square-free integers $r_i$ and non-zero integers $a_i$, is there an algorithm for determining the sign of $\sum_{i=1}^n a_i\sqrt{r_i}$ without calculating approximations for ...
3
votes
2answers
38 views

Algorithm to solve the system $\sum_{i=1}^nx_i^k = k!c_k$, $k=1,2,\ldots,n$ efficiently

$$ x_1 + x_2 + \cdots +x_n = c_1 $$ $$ \frac{x_1^2}{2} + \frac{x_2^2}{2} + \cdots +\frac{x_n^2}{2} = c_2 $$ $$ \vdots $$ $$ \frac{x_1^n}{n!} + \frac{x_2^n}{n!} + \cdots +\frac{x_n^n}{n!} = c_n $$ ...
0
votes
1answer
56 views

Proving number of edges in F = n - k

So if we let F = (V,E) be a forest with n vertices and k connected components (trees), how can I prove that the number of edges in F = n - k ? I was thinking of using induction, but I'm super lost. ...
1
vote
1answer
25 views

Proving n is not divisble by m using Division Algorithm

When $n$ and $m$ are integers, how could I write a statement equivalent to the statement "$n$ is not divisible by $m$" using ideas from the Division Algorithm?
0
votes
0answers
17 views

Is the string in $L(G)$?

I have to write an $O(n^3)$ algorithm to determine whether a given string $w=a_1 a_2 \dots a_n $is in $L(G)$, where $G=(N, \Sigma ,P, S)$ is a context-free grammar in Chomsky normal form. Could you ...
0
votes
1answer
11 views

Finding nodes with a particular weight in a graph

Given a weighted graph $G=(V,E)$ and given two integers $n$ and $k$, I want to find (if they exist) $n$ nodes such that the sum $S$ of all the edges incident to such $n$ nodes is smaller than $k$. Of ...
1
vote
1answer
65 views

True or False Time complexity questions

Here is my go at them and any help is appreciated: If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f - g)(n) = \Theta(n^2)$ where we define $(f-g)(n) = f(n) - g(n) \forall n$ TRUE? If $f(n) ...
1
vote
1answer
45 views

Time complexity of algorithms

I am having some trouble figuring out the time complexity in big theta notation of the following algorithms. Any help is appreciated. ...
0
votes
1answer
28 views

Resolve $Ay=b$ with fast method

I am looking for method that resolve equation $$Ay=b$$ I read the paper "Wiedemann's algorithm" that is one solution for fast way to find the solution instead of Gauss-Elimination. Could you suggest ...
0
votes
1answer
33 views

complex root finding

I have a problem of root finding. Format of the function can be arbitrary whereas I want to solve the following one: $$f(x)= a+e^{-x^2}(b+cx+dx^2)$$ where a,b,c and d are given parameters, not ...
1
vote
1answer
29 views

Find the sum of all the multiples of 3 or 5 below 1000 (Break down)

I know that this has been posted before but I can't grasp how it actually works. I'm a 16 year old in the 10th grade and am interested in algorithms. I've looked in multiple places on the web but am ...
1
vote
2answers
30 views

Split cab fare proportional to saving made across the board

Interesting dilemma. I've figured out how to split a cab fare 3 ways (proportional to time, mileage and equally) but I've found that when the cab fare is split proportional to time and mileage, the ...
0
votes
1answer
25 views

Split a cab fare proportional to the time everyone has spent in taxi

How would you split a cab fare proportional to the time everyone has spent in the taxi? Total journey time = 19 min Fare = $17.25 ...
0
votes
0answers
16 views

How to approximate the formual of combination function with large number element in set

I am implement the function to get the value of W with input are $k, \epsilon,\Omega$. The function W is defined as Please don't worry about the complex of equation. It is very easy with three known ...
1
vote
1answer
33 views

Find all Combinations of 1 and 2 which sums up to k.

I have two numbers $1$ and $2$. I have to print all ordered combinations which sums up to $k$. For example: $k=1$ Its only $1$. $k=2$ It's ${1,1},{2}$. $k=3$ Its ${1,1,1},{1,2},{2,1}$ What ...
0
votes
0answers
25 views

Evaluation a function of degree of vertices in a graph

I have a function $f(d)$ which takes in the degree of a vertex of a node in a graph $G$ and outputs a number between 0 and 1. The function is specified as follows. ...
0
votes
0answers
8 views

looking for an algorithm for nonuniform timing series

If we have a nonuniform timing series t1,t2,t3.... and every timing point means an event. A time interval T is given. Then n events can happen in T. Once T is given, how to calculate the maximum ...
0
votes
1answer
22 views

Select K numbers from N numbers fairly

I want to fairly select K numbers out of an array of N number. I know that this problem can be solved using Reservoir Sampling but I want to know if this approach is correct too? ...
1
vote
0answers
24 views

Formula for number of tiles needed to fill up predefined space?

I've been bashing my head all day with this problem, there is no way I could figure it out by myself. Here's a detailed explanation, any help will be much appreciated: We want to fill up the room ...
0
votes
1answer
19 views

Running time for algorithms

Suppose i have a set $\{1,2,...,n\}$ and i know that the solution to my problem is a subset $S \subseteq \{1,2,...,n\}$. Clearly trying out all subsets in an exhaustive approach is far too time ...
0
votes
0answers
31 views

Algorithm Generate all labeled graphs

I'm trying to find an algorithm which will generate all labeled graphs with $n$ nodes and $n-1$ edges. It must cover trees and graphs with cycles with one unconnected node, but without multigraphs. ...
0
votes
1answer
41 views

Maximum flow problem with both minimum and maximum capacities

I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum ...
0
votes
0answers
15 views

HMM - forward algorithm (Part-of-Speech Tagging)

In order to understand the Forward algorithm for Hidden Markov Models, I created a Little example of Part-of-Speech Tagging. Consider the Hidden Markov Model with states $N$ (Noun), $V$ ...
2
votes
0answers
42 views

A list of numbers and

I have a real life problem that math may be able to solve. I am no mathematician so if you have any insight please use the simplified version. This problem is way beyond me. My gut tells me there is ...
1
vote
0answers
29 views

Some doubts regarding decidable sets

I've been working at one of the problems, related to the decidability. Let's denote $ f: \mathbb{N} \rightarrow \mathbb{N}$ as a computable increasing function, $A \subset \mathbb{N}$ is a ...
0
votes
1answer
18 views

Interpolation in quadtrees/octrees

I'm looking for an interpolation algorithm for quadtrees and octrees that is derived from bi(tri)linear or bi(tri)cubic interpolation. I'm mostly interested in the case where: the interpolant is ...
0
votes
2answers
25 views

Directed acyclic graph problem

Love some guidance on this problem: G is a directed acyclic graph. You want to move from vertex c to vertex z. Some edges reduce your profit and some increase your profit. How do you get from c to z ...
0
votes
0answers
38 views

Grover's algorithm

Any help is appreciated! I've read over a bunch of sources but still I don't get the question. Consider a function $f \colon \{0,1\}^n\to\{0,1\}$ such that the number of $x\in\{0,1\}^n$ such that ...
0
votes
1answer
15 views

Explanation of division/reduction in a binary Galois Field using bit-shifts

I've seen a lot of algorithms reducing the result of a multiplication in a Binary Field by using only bit-shifts and XOR. The number of positions to shift seems to be derived from the polynomial, but ...
0
votes
1answer
24 views

What is the formal name of this problem?

I'm doing an assignment and I'm having trouble with this question, could anyone give me the formal name of the problem described so I can research it better? The task is to move a player along a path ...
0
votes
2answers
21 views

Help with algorithm

How can I prove that is true/false $$ f(n)+g(n)=O(f(n)\cdot g(n)) Where f(n),g(n) > 0 $$ I think that if $f(n)=\frac{1}{n}$ and $g(n)=n$ it can't be true but I don't know how to prove it.
0
votes
0answers
13 views

Find an algorithim for parallel time sharing

I am trying to come up with an algorithm to calculate the time spent on multiple tasks, where there is the potential that they can run in parallel. The problem can be summarized as follows: A CPU is ...
1
vote
1answer
24 views

Combinatorics problem

I am trying to solve this question, my solution involves solving a combinatorial problem as follows : Number of arrangements of exactly k distinct elements in n slots such that each one of the ...
0
votes
0answers
40 views

Approximation for fewest incompatibilities in a task scheduling selection algorithm

Suppose you have a task selection algorithm to select the largest subset of tasks that do no overlap. The greedy algorithm that selects tasks based on their finish time will always produce an optimal ...