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

learn more… | top users | synonyms (1)

1
vote
1answer
39 views

Measuring Sets Intersection

I need a fitness function saying how well Interval B fits inside Interval A. Both intervals are ordered continuous numbers going from Interval_Start to Interval_End, for example [1..100] or [1..55]. ...
0
votes
0answers
19 views

What is the difference between these two coin changing problems? (Greedy and Dynamic Programming way)

I have been reading about Dynamic Programming, and I found out about the change making problem. When there is a given set of coins with different denominations but unlimited amount of each and we want ...
2
votes
1answer
52 views

How can I get better at algorithmic thinking?

I have been practising for a an upcoming algorithmic thinking competition but have always found that when doing the past papers, I have never had enough time left to finish. I can do basically all of ...
0
votes
1answer
41 views

Problem with summations for sorting algorithm?

According to this lecture http://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/10/Small10.pdf, slide 26, the expected number of comparisons done by quicksort is smaller or equal to ...
0
votes
0answers
22 views

Parallel finding maximum matching in bipartite graph

I try to research the following theme - finding maximum matching in bipartite graph. Now I researched some algorithms for finding maximum matching in bipartite graph, but all of algorithms which I ...
-1
votes
1answer
35 views

Prime checking algorithm [closed]

What should the algorithm for checking prime numbers be? I have one: Read a number Initialize division Check for divisibility by 2 and 3 If true, declare prime, otherwise not a prime Please tell ...
0
votes
1answer
50 views

In a box there are $R$ red pens and $B$ blue pens. What is the probability that you need to pick up a pen $3$ times?

In a box there are $R$ red pens and $B$ blue pens. Pens are randomly selected, one at a time, until a red one is obtained. Assume that each selected pen is replaced before the next one is drawn. (a) ...
1
vote
1answer
6 views

Encoding Bipartite Matching as a special case of Independent Set

Given a bipartite graph $G' = (V', E')$, the objects being chosen are edges, and the conflicts arise between two edges that share an end. (These, indeed, are the pairs of edges that cannot belong ...
1
vote
2answers
28 views

Big-O proof of inclusion

I'm working on this proof of inclusion:$$\log_2(8^n)\in{\mathcal O(n)}$$ $$\log_28^n-cn\leq0$$ for all $n>n_0$. Is there a log rule that I can use to further simplify before I plug random values to ...
2
votes
1answer
46 views

Alice and bob xor nim game

Alice and Bob are playing a game. The rules of this game are as follows: Initially, there are $N$ piles of stones, numbered $1$ through $N$. The i-th pile contains $A[i]$ stones. The players take ...
1
vote
1answer
21 views

Smallest number of groups to sniff

The question given: The sniffer dog at the airport stops beside a trolley piled high with 60 suitcases. One of the suitcases contains contraband peanuts. The dog can tell whether peanuts are hidden in ...
6
votes
3answers
124 views

How do Gap generate the elements in permutation groups?

I understand that permutationgroups in Gap are represented by generators, which seems to be far more efficient than groups represented by all it's elements, but how could then for example ...
2
votes
3answers
39 views

Mapping all numbers in a set to a particular number

This is not homework, I am a programmer and I encountered this problem in the implementation of an algorithm of mine. I was wondering if the following can be done without the use of any auxiliary ...
0
votes
1answer
50 views

Recursive approach for computing $(a,b) \mapsto a^b$

As a programming exercise I was asked to implement a recursive approach for computing $a^b$ given two real $a,b \in \mathbb R, a>0$. I assume this task has a typo, as a recursive approach makes ...
2
votes
1answer
40 views

Constructing every spanning tree from addition and deletion of edges

Let $G = (V,E)$ be given (note that this is not necessarily simple), and consider the set of every spanning tree of $G$, $S$. Choose any $G_a, G_b \in S$. Is it possible to construct $G_b$ from $G_a$ ...
0
votes
0answers
28 views

Division by power of 3.

Is there any fast division algorithm to divide a binary number by power of $3$. I want to find the $q,r$ for $a=q*3^b+r$, $b$ is constant.
2
votes
0answers
20 views

How to construct a polyhedron from given planes

This seems to be a basic questions, but I really don't know a good computer algorithm to do this. I have a set of planes (parameterized by normal direction and distance from a given point), and I want ...
3
votes
2answers
97 views

Why is the Leibniz method for approximating pi so inefficient

I've been playing around with algorithms for computing pi. One that I noticed is the leibniz algorithm. It states that pi can be approximated like this $n = 1$ ...
1
vote
1answer
20 views

Couple of questions about a proof of an algorithm

$M$ is a set of men and $W$ is a set of women. ...
-1
votes
0answers
23 views

To find order of an element in group of large size

G be multiplicative group of positive integers less than prime p. a be any arbitrary element of G .Is there any efficient algorithm to find order of a in G?
0
votes
0answers
17 views

Algorithm for dtecting negative edge cycle and then remove cycle which have odd number of negative edges

can anyone suggest me that how to remove negative edge which are involve into create a negative cycle? for exam ...
0
votes
0answers
11 views

Magnetic dipole - sensing from 3 locations

The problem is to estimate the position $\vec{r}_0$ and direction $\widehat{𝑚}$ of a magnetic dipole (e.g. current loop) using electromagnetic field measurements by three sensors. A magnetic dipole ...
0
votes
1answer
29 views

Number of fragments into which a fixed triangle is cut in the 3d version of the binary space partitioning algorithm

You can scroll down the question, if you're familiar with the construction of a 3d binary space partition as presented in the book Computational Geometry: Algorithms and Applications by Mark de Berg ...
1
vote
1answer
22 views

Why is no analysis possible for the 3d version of the random binary space partioning algorithm?

Let $S$ be a set of $n$ non-overlapping line segments in the plane $\ell(s)$ be the line which contains $s\in S$ $\ell^+$ and $\ell^-$ be the half-plane above and below of a line $\ell$, ...
2
votes
3answers
62 views

Intersection point of two functions - one linear, the other with logarithmic and sqrt terms

I would like first to appreciate everything that is being done on this forum and to greet you all! I have namely two functions and the goal is to find the intersection point of them. $y_1 = a + ...
2
votes
1answer
52 views

Cracking a combination lock

I was thinking, how long would it take to crack a combination lock by bruteforcing it? Assuming a combination lock has $40^3$ different combinations, and it takes about ten seconds for each try. In ...
0
votes
3answers
50 views

How to design the max function for integers using only additions and multiplications?

I want to design a function which outputs the maximum value between two integers, something like this $f(x,y) = \begin{cases} 1, & \text{if } x > y, \\ 0, & \text{otherwise}. ...
1
vote
1answer
55 views

Conway's Game of Life borders rules

I'm taking a look at the Conway's Game of Life rules, and I'm not sure how to deal when the cell reach the corner of the field... let's take an example: ...
0
votes
1answer
39 views

Finding log base 2 of a number .

I generally visualize $\log_{2}$ of a number as an inverted binary tree, for example to know how many times 8 needs to be divided to become one I image a inverted tree of 8 leaves then, the level ...
0
votes
1answer
52 views

Packing three increasing integers into one

I have three integers representing positions on a board. Because all pieces are equal, the order does not matter, so it suffices to only consider increasing lists of three integers. However I am ...
2
votes
2answers
79 views

Efficient way to check if prime factors are the same

Given two positive integers $m$ and $n$ such that $1<m<n$, what is an efficient way to check if the prime factors of $m$ and $n$ are exactly the same, i.e, if $\mathcal{P}_m=\mathcal{P}_n$, ...
0
votes
0answers
26 views

Gradient Descent Algorithm

Hello I'm trying to understand how the Gradient Descent Algorithm works. There is a formula that I found on wikipedia and that I cannot justify: ...
0
votes
0answers
12 views

Uniform cost search algorithm on given graph

I am having an issue understanding this problem and how to apply the uniform cost search on a given graph (the London metro) which is given here: http://tubephotos.dannycox.me.uk/stationsbyline.html ...
0
votes
0answers
21 views

Alphabetical Listing Algorithm

Do you know any Alphabetical Ordering non-repetitious algorithms or functions? I need a bijection from Natural numbers to alphabetically ordered list of $n$-tuples of a finite set. Maybe a recursive ...
0
votes
0answers
11 views

ODE systems of particles - reduce computational load due to distances evaluation

This question both relate to ode numerical solution and algorithmic approach. I'm going to ask it here hoping that I'm not violating the rules of this forum. I have a system of $N$ particles in the ...
0
votes
1answer
51 views

Find the Theta class for the recursion $T(n) = T(3n/4) + T(n/6) + 5n$

$\displaystyle T(n) = T\left(3n\over4\right) + T\left(n\over6\right) + 5n$ is not in the proper form for the Master theorem so I can't really apply it. The only idea I had was changing the ...
0
votes
2answers
45 views

Can I prove that 2n+1 = O(2n)?

Is 2n+1 = O(2n)? In other words, 2n+1 <= c * 2n for any c and all n > n0? I have plugged in numbers but none that worked. Obviously It is also (n) but I am trying to prove the above. Much ...
3
votes
0answers
50 views

Count number of m-subsets with xor = 0 [closed]

Given positive integers $n$ and $m$, count the $m$-subsets $S\subseteq[2^n - 1]$ such that the bitwise XOR of the members of $S$ is $0$, where as usual for any positive integer $k$ we let ...
1
vote
1answer
50 views

Formula for simulating radioactive decay for a large number of isotopes

Currently I'm working on a project where I need to simulate the decay of a number of isotopes after each second. One way to do so is each second do a uniform random roll for each particle, and if it ...
2
votes
1answer
118 views

What is the maximum sum of these numbers?

Consider $n$ circles with intersection by any two of them. Any area is all the common part between $m$ circles(a $m$-area): We have $2^n - 1$ areas, $m$ varies between $1$ and $m$. A $1$-area is an ...
1
vote
1answer
16 views

Cannot create algorithm for decidable language

L2 = {<M> : M is a TM and there exists an input string w such that M halts within 10 steps on input w} Hi. I am creating an algorithm to show above L2 is ...
0
votes
1answer
19 views

iterate algorithm/program correctness proof by induction

Suppose I have a function where it calculates which bit is larger called LargerBinary. Let's say I have an input 110111;101001, the output will be 110111 and if the input is 110110:110110, the output ...
0
votes
0answers
11 views

Effective algorithmic calculation of gcd determinant

This is a contest problem taken from here: http://www.e-olymp.com/en/problems/3243 I need to calculate the following determinant: $$ D(1,\dots,n)=\begin{vmatrix} (1,1) & \cdots & (1,k) & ...
0
votes
1answer
49 views

Trailing zeroes in product of numbers with factorial power

I need to find the number of trailing zeroes in $1^{1!} \cdot 2^{2!} \cdot 3^{3!} \cdots N^{N!}$, where $N$ is natural number. Assuming $N$ is very large, say $500$, where you cannot find factorial ...
4
votes
1answer
52 views

Running through all permutations of a Rubik's cube

According to Wikipedia a $3 \times3\times3$ Rubik's cube has $43252003274489856000$ permutations. I never tried solving one myself (too tedious), however I wondered, if one could miraculously ...
0
votes
0answers
16 views

Fitting in a combination of numbers

I have stumbled across a problem In a conference I need to fit in n presentations of respective durations for an instance 60 mins, 45 mins, 15 mins, 5 mins. I ...
1
vote
3answers
96 views

How is this possible to convert a long string to a number with less characters?

I'm going to write a program (function) that can convert a long string to a number. For this, first I convert each character (letter) to a number; like ...
0
votes
1answer
37 views

Cannot understand solution (Turing Machine & Reduction)

Photo of my problem that I don't understand About question above in photo, I just can't understand its solution provided. We know the complement of Atm = {...
1
vote
1answer
66 views

An algorithm for creating a circle on a discrete plane and a limit for $\pi$

I know there is a well known algorithm which uses the circle equation to approximate it with pixels. However, I wanted to approach this problem from the most basic principles. So we start with a ...
0
votes
2answers
65 views

Define algorithm using divide and conquer paradigm [closed]

Q:Describe a Θ(n lg n)-time algorithm that, given a set S of n integers, determines which two elements in S have the smallest difference. (From what i understand, we first apply merge sort to our ...