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)

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/...
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 ...
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?
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 ...
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 ...
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?
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
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
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 ...
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
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
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
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
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 ...
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 ...
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 ...
-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. ...
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 ...
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 ...
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, ...
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
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 ...
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
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 ...
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
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 ...
-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 ...
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
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 ...
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 ...
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 ...
-1
votes
0answers
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 ...
1
vote
0answers
23 views

When is $\frac{2 n f(n)}{n !}$ in the order of some fixed power of $n$?

I would like to know when $\frac{2 n f(n)}{n !}$ is $O (n^b)$ where $b$ is a constant. Here, $n$ is a positive integer. My attempt: $$ \frac{2 n f(n)}{n !} = \frac{2 n f(n)}{\sqrt{2 \pi n} (\frac{n}{...
0
votes
1answer
47 views

Analysis of bisection search

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-1/lecture-3-problem-solving/ In the following video i'm ...
2
votes
2answers
51 views

Why does $\sum_{i=0}^{n-1} \frac{1}{n-i} = \sum_{i=1}^{n }\frac{1}{i}$?

From CLRS Problem 4.3, part 5 . Why does the following holds? $$\sum_{i=0}^{n-1} \frac{1}{n-i} = \sum_{i=1}^{n }\frac{1}{i}. $$
1
vote
0answers
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. ...
1
vote
0answers
35 views

Sifting algorithm for group generated by a set. [closed]

On page 38 of "Lecture Notes in Computer Science" by Christoph M. Hoffmann, there is an algorithm (ALGORITHM 2). I have some confusions. The algorithm needs to go to all column element indexed by ...
0
votes
0answers
14 views

Is there a simple way to describe all $O(n)$ algorithms given simple assumptions about the machine?

For example, can all $O(n)$ algorithms (where $n$ is strictly an integer) be described as: for k in 0..f(n): O(1)(k) where $f$ is a linear polynomial in $\Bbb{...
1
vote
1answer
29 views

Properties on proximal term

If the equation $x_i$-subproblem showed below is not strictly convex $\arg \min_{x_i}=f_i(x_i)+\frac{\rho}{2}\|A_ix_i+\sum_{j\neq i}A_jx_j^k-c-\frac{\lambda^k}{\rho}\|_2^2$ Why adding the proximal ...
0
votes
0answers
7 views

Knuth X exact cover

The famous algorithm for exact cover is given by Donald Knuth called Knuth X algorithm. https://en.wikipedia.org/wiki/Exact_cover) ...
0
votes
1answer
37 views

Finding the overlap between direction of distance in position space and direction of distance in velocity space

There are two objects A and B that can be described in position space and velocity space. The position space describes the instantaneous positions of the objects while the velocity space describes ...
1
vote
1answer
32 views

how to find closely related values from a set?

I have a set of values, for eg. {20, 1, 1, 21, 8, 22, 11, 40, 5, 21} and will need to find n closely related values. If n is 4 in the given example, the result should be {20, 21, 21, 22} because these ...
1
vote
1answer
21 views

translating algorithm to preserve validity?

Let two languages $\Sigma_1 = \{R^2, P^1, =^2\}$ and $\Sigma_2 = \{c, f^1, =^2\}$. Prove or disprove: There's an algorithm (procedure that halts) which gets as an input a formula $A$ above $\Sigma_2$ ...
0
votes
0answers
17 views

Graph theory decision tree

I have a graph G in $\R^4. |V(G)| = 15, vertices are 15 points in R^4. I am trying to build the largest graph possible without significantly changing it's independence number. I have a set of ...