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

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 ...
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/...
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 ...
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?
22 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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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, ...
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: ...
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 ...
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? ...
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 ...
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,...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
9 views

### Finding the lowest amount of edges in all minimum cuts in flow network

Given a network N, I want to find the minimum cut that has the lowest number of edges in it. I thought about: Find the maximum flow (with Dinitz algorithm for example) Increase the capacity function ...
23 views

49 views

### Intersection of two sets of rationals

I'm looking to see if anyone has any solutions or references for this problem. I'm not even sure of a proper category. It seems like it should be trivial, perhaps I'm missing something obvious. ...