# Tagged Questions

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).

1k views

### Are there dictionaries in math?

Consider the following dictionary in the programming language Python: D = {'A': 1, 'B': 2, 'C': 3} It is saying that the value of A is 1, the value of B is 2, ...
14 views

### Simplify non-linear but simple expression with max and min

I have this code: max(n+1,min(numPages+n-4,currentPage+n-2)) which is equivalent to the expression $\max\{n+1, \min\{N+n-4, m+n-2\}\}$ $0<m<N, 0\le n\le5$...
24 views

### How to exactly determine whether a sum of n-th roots of unity is zero

Define the set $R = \{e^{2\pi i k/n} | k=0,1,\ldots,n-1\}$ of $n$-th roots of unity. Let $S \subseteq R$ be a subset. How can I (algorithmically?) determine whether $\sum_{s\in S} s = 0$? I'm ...
94 views

### What is the optimal route for visiting Pokéstops in Pokémon Go?

Okay, I've got a fun problem for you, which was not suited for the gaming stackexchange: Pokéstops are GPS locations with a certain radius. When you are in the radius, you can get certain ingame ...
380 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 ...
46 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 ...
9 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/...
22 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 ...
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?
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): ...
23 views

$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 ... 0answers 31 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 ... 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&... 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 ... 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? 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 ... 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 ... 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 ... 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 ... 0answers 64 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)...
32 views

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#/...
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 ...
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.
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 ...
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 ...
392 views

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+...
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 ...
81 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 ...
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 ...
34 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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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, ...
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.
48 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? ...
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: ...
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,...
19 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 ...