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
1answer
29 views

search algorithm BFS?

So i have a recursive search algorithm here, ...
0
votes
2answers
17 views

Raised to the power and modulus

Task: $26^{61}(\pmod {851}$ And I stucked with the operation pow(26,61) because it's too hard for me. I read the article about this problem, but I don't quite understand how to solve it. I can ...
0
votes
0answers
10 views

Which is the greatest integer value of $a$, for which $A'$ is asymptotically faster than $A$?

The recurrence relation $T(n)=7T\left( \frac{n}{2}\right)+n^2$ describes the execution time of an algorithm $A$. A "competitor" algorithm, let $A'$, has execution time $T'(n)=aT'\left( \frac{n}{4} ...
0
votes
2answers
19 views

RSA and find 'd'

So, my task is to find d if $p=5, q=11, e=17$. Here I've tried: Find $n=p\cdot q = 5*11 = 55$ Find $\phi(n) = (p-1)(q-1)=(5-1)(11-1) = 40$ Euclidean algorithm: $$ 40=2\cdot 17+6 \\ 17 = 2\cdot 6 + 5 ...
0
votes
0answers
18 views

Application of divide-and-conquer

Good afternoon. Consider a two-position switch with two inputs and two outputs. In one position inputs 1 and 2 are connected to outputs 1 and 2 respectively. Using these switches, design a network ...
1
vote
0answers
28 views

Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case

Prove that the probability that an insertion into a cuckoo hash table probes $t$ array locations is $O(\frac{1}{2^{t/2}})$. Keep in mind that there are two tables, each with size $s \ge 2n$, ...
0
votes
1answer
11 views

Logic with increasing monte carlo possible output

I am working on Monte Carlo algorithm : Given that you have an experiment MC which has a p-correct of 75%, which means it gives you the right answer 75% of the time. You run MC3 which repeats MC 3 ...
0
votes
0answers
17 views

Show that this is the number of moves that have to be done to solve the problem [duplicate]

Prove that $2^n − 1$ moves are necessary and sufficient to solve the Towers of Hanoi problem. Could you give me some hints how I could do that??
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 ...
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
21 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
44 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
61 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
1answer
58 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
42 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
30 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 ...