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)

0
votes
1answer
378 views

Algorithm to find Frobenius number

I realize that such a question may have already been asked, and having looked at a few, I didn't really understand how to calculate a frobenius number. So, is there a general equation that can be ...
3
votes
1answer
42 views

Best strategy for the first player in a game for two on a large checkered paper

Here's a puzzle that's been seating in the back of my head for quite a long time. The game is played on a grid of infinite dimensions; sufficiently large checkered paper. First player specifies ...
0
votes
1answer
8 views

Codility - NumberOfDiscIntersections 100%

I've been practicing some algorithm writing on the website codility.com. Specifically the task NumberOfDiscIntersections located here https://codility.com/...
0
votes
0answers
21 views

Different Representation Matrices from same Generating Set

Motivation: This post. $K \subset S_n, \langle K \rangle =G \leq S_n$. We can create a Representation Matrix $M$ from $K$ that represnts $G$ (Furst. Hopcroft, Luks). Question: Is $M$ unique for a ...
0
votes
0answers
34 views

Optimal assignment for an unsatisfiable formula

Given an unsatisfiable formula $F$ in CNF, are there any methods to find an assignment that can satisfy as many clauses as possible?
0
votes
1answer
294 views

Method for finding bridges and articulation points using DFS

How can we find all bridges and articulation points using DFS? Suppose we have the following DFS psuedocode (from Wikipedia): ...
2
votes
0answers
22 views

probabilistic method for random algorithm that decide language membership

$A$ is an random algorithm that decide membership to language $L$. It outputs on input $x \in \{0,1\}^n$ and a string of random bits $r \in \{0,1\}^n$ in the following way: $if \{x \in L\} \Rightarrow ...
2
votes
0answers
29 views

Is there a method that determines an unknown permutation better than $\sum_{k=1}^n (k+1)/2$ steps on average?

Suppose I have a random permutation $s \in S_n$ that is unknown to me. However, suppose I can make a query where when I ask if $i$ is in the $j$th position in the permutation, I receive a yes or no ...
1
vote
1answer
382 views

is there are specific way to solve coupled first-order differential equations with coefficients varying?

suppose I have "n" coupled differential equation represented by the matrix, Y• = A Y , where Y• is the column matrix containing first derivatives, namely, y1•(t), y2•(t), ... yn&...
0
votes
1answer
453 views

How do I prove an algorithm has $n^3$ time complexity?

Take the CYK algorithm outlined here: How to prove CYK algorithm has $O(n^3)$ running time In the top answer, how did that person go from the three summations to $t=(n^3−n)/6$ ? What's the method ...
3
votes
0answers
19 views

Closed form asymptotically

The bound for $$\sum_{i=1}^n\binom{n}{i}2^i$$ is $O\left(3^n\right)$ but what will be the bound for $$\sum_{i=1}^{\frac{n}{2}}\binom{n}{i}2^i$$ Any idea how should I proceed?
3
votes
1answer
547 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 ...
0
votes
2answers
31 views

Linear equation in n variables with non negative solution

The problem is that given a positive integer y and n positive integers x1 , x2 , ... , xn does there exist non negative integers ...
0
votes
1answer
13 views

Divide items with integer ID-s into N equal groups, based on ID-s

I have unknown number of items, each having ID (consecutive integer numbers), ie. 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15... I want to split above items into as ...
0
votes
1answer
41 views

Gradient descent with linear perturbation

Given a convex, differentiable function $f$ (from a Hilbert space to $\mathbb{R}$) with a minimum (say $x^*$), I know you can find $x^*$ using gradient descent. Suppose now that you apply gradient ...
2
votes
0answers
63 views

Accelerated gradient descent versus nonlinear conjugate gradient descent

Let's consider smooth and convex minimization problem, i.e. $min f(x)$, where $f$ is not necessarily a quadratic function. If measured by iterations, Accelerated Gradient Descend (AGD) has $O(1/T^2)...
0
votes
0answers
32 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: https://www.wikiwand.com/en/Gradient_descent#/...
1
vote
1answer
411 views

Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n)

Given recurrence $$T(n) = 3T(n/2) + O(n)$$ $$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$ so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \ k = 1 \ call$$ So I ...
-1
votes
0answers
26 views

Bound on binomial summation

The bound for $\sum_{i=1}^n\binom{n}{i}2^i$ is $O(3^n)$ but what will be the bound for $\sum_{i=1}^{\frac{n}{2}}\binom{n}{i}2^i$. Any idea how should I proceed.
1
vote
0answers
10 views

Similar distance pairs

There are two lists of 2D coordinates with the same length. Now I want each element of list 1 to form a pair with an element of list 2, in such a way that the distance between both elements are ...
1
vote
0answers
27 views

37 percent rule with second-chance-allowed

What is the math behind this? fragment from book Algorithms to Live By: The Computer Science of Human Decisions For example, assume an immediate proposal is a sure thing but belated proposals are ...
0
votes
1answer
392 views

optimization of a non-differentiable, component-wise step function

I would like to estimate the (local) minimum of a function $c:R^N \mapsto R^+$ where: $c$ is only differentiable almost everywhere, there exists a component $j$, such that $\frac{\partial c}{\...
1
vote
0answers
15 views

CLRS substitution method “subtracting constant” technique

I'm reading CLRS, and in Chapter 4 it states that if you guess the asymptotic complexity of a recurrence correctly but cannot quite get the mathematical induction work out, a common method to employ ...
-4
votes
0answers
27 views

Desperate For Help- How To Create An Multi Variable Algorithm? [on hold]

I am new to the workforce and need to create an algorithm that takes into account 15 - 20 different sets of data for a project. Is this possible and what web-based tutorials are available? Thanks so ...
0
votes
0answers
20 views

Which of the statements are true for travelling sales man problem of a greedy algorithm [on hold]

Which of the statements are true for travelling sales man problem of a greedy algorithm work’s for in complete graph also Krushkal’s algorithm gives a sub-optional solution in general Both $(1)$ and ...
0
votes
0answers
22 views

A graph is said to be in Hamiltonian cycle. Then the travelling salesman problem is? [on hold]

The graph ‘g’ with vertices {A, B, C, D, E } is said to be in Hamiltonian cycle. Then the travelling salesman problem is Heuristic NP-complete minimal spanning tree triangle inequality My ...
0
votes
0answers
17 views

Coin Denomination like problem except with negatives

So my problem is similar to the coin denomination problem, but also different, let me explain how: Suppose that your "coin" can have the following values: -5,-4,-3,-2,-1,0,1,2,3,4,5 0 means the ...
0
votes
1answer
28 views

What is difference between $O(|V|+|E|)$ and $O(|V+E|)$?

Perform DFS over the entire graph. The linear time taken by a size of graph as visiting each node finished is put it on the head of initially empty list is $O(|V|+|E|)$ $O(|V+E|)$ $O(|V|^k)$ $O(\...
0
votes
1answer
35 views

Algorithm to convert binary fraction to decimal fraction

There's an algorithm to convert binary integer into decimal integer that is based on the expanded form of a number: $$ 12 = 2\cdot(2\cdot(2\cdot(2\cdot 0 + 1)+1)+0)+0 $$ \begin{aligned} & 2\cdot0+...
2
votes
1answer
36 views

Algorithm for partitioning works to workers

I'm writing a computer program to do work but there's a partitioning problem. In this program, there're workers and works. The main objectif is to give a balanced partition plan, so that works can be ...
2
votes
1answer
80 views

Discrete logarithm modulo powers of a small prime

Is there an efficient way to compute $x$ in $2^x \equiv b \pmod {p^m}$, where $p$ is a small odd prime and $m$ could be a large integer? I know the solution is of the form $x=\phi(p^m) k + y$ for ...
0
votes
0answers
30 views

Transforming generating functions into algorithms that generate combinatorial objects

I've stumbled upon this paper where they write about random sampling of combinatorial objects. For sampling to be proper one has to know some core numbers (probabilities). However, I'm not interested ...
0
votes
2answers
32 views

What is the computational complexity of Newton Raphson method to find square root.

I am not a math student, so I don’t fully understand the complexity as mentioned on Wiki for Newton Raphson method for finding square root. But I wrote a computer program for Newton-Raphson’s method ...
2
votes
3answers
66 views

$p\in\mathbb P\iff\Big(2\leq k<\sqrt p\implies\gcd(k^2,p-k^2)=1\Big ),\;p>3$

This is sharper variant of A condition for being a prime: $\;\forall m,n\in\mathbb Z^+\!:\,p=m+n\implies \gcd(m,n)=1$ It seems enough to test that for some sums: $p=m+n\implies\gcd(m,n)=1$, namely ...
-1
votes
0answers
43 views

How does the induction proof work in this solution?

Refer to answer 1.1 of this file: http://www.dei.unipd.it/~geppo/AA/DOCS/NPC.pdf From my understanding and this thread, http://math.stackexchange.com/a/928412, we need 3 steps for that proof. ...
2
votes
1answer
491 views

Pack rectangular objects of different sizes in a fixed size rectangle

If this has been asked before, please help me find it, I have scoured Math.stackexchange and have found quite similar questions but not exactly what I am looking for. I have a rectangular space. I ...
0
votes
4answers
44 views

Sum solution unclear

I have started studying algorithms and currently am reading Skiena's Algorithm Design book. While doing the tasks, I encountered with question that I could not find solution for. I took a look in ...
0
votes
0answers
18 views

Obtain the biggest circle which has all inner points close to given regions

In $\mathbb{R}^2$, I've got various spots, which may either be points, lines or polygons (there will always be one point in $(0,0)$): Illustration of the spots How can I find the biggest circle/disk ...
1
vote
0answers
15 views

Extension of Planar Algorithms to Higher-Dimensional Voronoi Diagrams

Voronoi diagrams are not new, and there are many established algorithms (Fortune's, Lloyd's) for generating them (or their duals, the Delaunay triangulation). There are many recent-ish papers too, ...
2
votes
2answers
808 views

Does $Ax + By = C$ pass through any lattice point?

Given an equation of a straight line of form $Ax + By = C$. where $A,B,C$ are integers. How could we check if this passes through any lattice point or not? Please suggest me a suitable algorithm.
2
votes
2answers
47 views

Find least number of radial-subgraph of a graph

Background: Here is a group G of a people, one maybe another's friend. How to select least number of people to be a leader of a subgroup, so that everyone in the group G has a friend as a leader? ...
0
votes
2answers
57 views

In AB + BC + AC = N, how can I find all possibilities for A, B and C in less than n³ computational time?

The problem is the one on the title. Given a N, find all possibilies for A, B and C that make this true: $AB+BC+AC = N$when $A \ge B \ge C$. This code in C do the job: ...
2
votes
1answer
54 views

Show that there's no such algorithm

Show that there's no such algorithm, $A$ which gets a sentence, $\varphi$ (a formula without free-variables) and returns $\varphi'$ such that: $\varphi$ is satisfiable iff $\varphi'$ is valid (meaning,...
0
votes
1answer
18 views

Bin packing approximation algorithm

I know that bin packing cannot be solved in $\mathrm P$ unless $\mathrm P=\mathrm{NP}$, because we could solve partition problem. However, I do not see why this theorem is a collorary. There is ...
0
votes
2answers
27 views

How to deduce the simplified equation for angle between clock hands?

I'm trying to understand how wikipedia simplifies the equation for the angle between clock hands. https://en.wikipedia.org/wiki/Clock_angle_problem The angle between clock hands can be found by H ...
-1
votes
0answers
33 views

Is it ever possible to publish results about special cases of already published more general results? [closed]

Suppose there is existing published work on some general mathematical result, for example some computational algorithm. If I study the special case of that algorithm (e.g. low-dimensional case with ...
1
vote
1answer
15 views

Advantage of multi-objective optimization over single objective

What are the advantages of multi-objective optimization over single objective? I am specifically thinking about MO and SO in Genetic Algorithm. I have surfed the net and found many articles talking ...
0
votes
0answers
9 views

Gradient descent algorithm not converging for large $x$, small $y$

My data set includes three points: $(115, 20), (118, 20), (127, 20)$. When I attempt my gradient descent algorithm on this method, I get $\theta_0 = 0.216$ and $\theta_1 = 0.165$. After normalizing my ...
1
vote
3answers
1k views

Running time (Big O) of counting in binary

What is the total running time of counting from 1 to $n$ in binary if the time needed to add 1 to the current number $i$ is proportional to the number of bits in the binary expansion of $i$ that must ...
0
votes
0answers
22 views

How to make check matrix H when you have generator matrix (algorithm)

It's all built on top of python numpy lib. So we have a class finite field and get access to elements of field like Finite_field[index_of_element]. Elements of field are numpy matrices(ndarray). For a ...