Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

1
vote
0answers
37 views

Efficient algorithm for calculating the tetration of two numbers mod n?

I'm trying to study the algebraic properties of the magma created by defining the binary operation $x*y$ to be: $ x*y = (x \uparrow y) \bmod n $ where $ \uparrow $ is the symbol for tetration. ...
1
vote
2answers
268 views

Optimization problem: Maximize the sum of minimum.

Given positive integers $L$ and a set of non-negative integers $N$. Find maximum of: $$\large \sum_{i = 1}^{4L}\ N_i\cdot(\min(\vert i - c\vert, 4L - \vert i - c\vert))$$ with $c \in \{1, 2,\dots ...
0
votes
0answers
22 views

Complexity of and an algorithm for finding ideals of a ring?

One of the problems that has been a roadblock in my understanding of ideals has been how one would find them. One way of finding an I of some ring R would be to say $ \forall x \in I, \forall r \in R ...
0
votes
1answer
71 views

How many 10-bit strings with more 0’s than 1’s?

I have to pick the answer from: a.512 b.386 c.256 d.252 e.none of these The number of bit strings of length 10 with n 0's (or n 1's in fact): is C(10,n) , where C(a,b) = a! / [(a-b)!b!] is the ...
4
votes
2answers
58 views

What is the value of the following? $3^{302} \mod 5.$

I have to choose from a. 0 b. 1 c. 2 d. 3 e. 4 I think its e. 4 because $$3^{302} = 3^{300} \cdot 3^2 = 3^{4\cdot 75} \cdot 3^2 = (3^4)^{75} \cdot 3^2.$$ Applying Fermat's Little Theorem to ...
3
votes
1answer
47 views

Find an algorithm to evaluate unknown polynomial of degree $n$ given its values for $x=0,x=1, x=2,\ldots,x=n$

Given $n+1$ values ($P(0),P(1), P(2),\ldots,P(n)$) of unknown polynomial $P(x)$ of degree $n$ find an algorithm that works in $O(n^2)$ for evaluating $P(n+1), P(n+2),\ldots,P(2n)$. Given $n+1$ values ...
0
votes
1answer
35 views

Working out a formula for a series of numbers which are NOT an X-Y set

I need to find a formula, which can calculate the value of M from the given value, O. The values are as follows: O0, 1, 2, 3, 4, 5, 6, 7, 8 … M1, 2, 4, 8, 16, 32, 64, 128, 256 … Note that the values ...
0
votes
0answers
42 views

An efficient algorithm to pair chess players in a team tournament

I found this question on a website. Your team is playing a chess tournament against a visiting team. Your opponents have arrived with a team of $M$ players, numbered $1,2,\dots,M$. You have $N$ ...
0
votes
2answers
66 views

$O(n^{\log(n)}) $ time algorithms

Is $O(n^{\log(n)}) $ time algorithm considered of exponential time ? Is it applicable ?
1
vote
1answer
38 views

What's a more optimal native C-language algorithm to set bit $k$? [closed]

Let $n$ be an integer (for example an unsigned int which is usually 32- or 64-bits), let the number of bits be $|n|$. Let $0 \leq k \lt|n|$. I usually do: ...
1
vote
0answers
20 views

Ideal shrinking of discrete randomness source

I have a discrete randomness source that emits random integer numbers in range [0..N) with uniform distribution. I need to reduce this distribution, limiting it to ...
1
vote
2answers
61 views

Given a Cayley table, is there an algorithm to determine if it is a dihedral group?

Showing that it is a group is simple enough, but is it possible to determine if it is a dihedral group or not just by looking at the Cayley table?
1
vote
1answer
35 views

find the polynomial if we know its output

$f$ is a polynomial of integral coefficient.Now suppose we have a computer program to find out its output taken in $\mathbb{Z}$.Is it possible for us to find out this polynomial in finitely many ...
0
votes
0answers
102 views

Find all the subsequences which are arithmetic progression

Given a sequence is there a linear or sub-linear algorithm to find all the sub-sequences that are arithmetic progressions with a given D, where D is the consecutive difference between the elements ?
1
vote
0answers
31 views

Mathematical formulation of Algorithms

Is there a way to formulate the definition of algorithms mathematically, so that the effectiveness and completeness of algorithms is justified.
0
votes
1answer
69 views

Properties of the relation R on the set of all real functions

So... I'm working on this and I'm supposed to figure out if each of these properties are pertinent. Can someone please help me? Thank you! Properties: Reflexive Symmetric Anti-Symmetric Transitive ...
1
vote
2answers
49 views

Time complexity (in Θ-notation) in terms of n?

Can someone please help me with this problem? Any help would be much appreciated? Thanks in advance!! ...
2
votes
1answer
52 views

What's the Lucas version of the Möbius test for Fibonacci numbers?

I recently came across the following, attributed to Möbius: $$(a\in\mathbb N)=F_n\iff\left[\varphi a-\tfrac{1}{a},\varphi a+\tfrac{1}{a}\right]\ni(b\in\mathbb N)$$ It is the lesser-known test used to ...
0
votes
1answer
33 views

The maximum length of a line contained inside a convex polygon

I have a convex polygon. What algorithm do you suggest to find the maximum length of a line with a specific slope that is contained inside the polygon. The direction of the line is shown with blue ...
0
votes
1answer
25 views

Intersect and Trim lines with a polygon

I have defined a Polygon. I want to intersect and trim a list of other Lines with the Edges ...
2
votes
1answer
51 views

What is the time complexity (in Θ-notation) in terms of n?

Consider the following algorithm, where $n$ is a parameter. ...
0
votes
1answer
19 views

Scale position on weighted vector

I have a logic problem in a software I'm writing that I can't identify a way to resolve. Maybe it's just simple math and I'm overthinking. In this software, the user select several colours in a ...
2
votes
2answers
87 views

How do I apply the $\pm4$ part of the equation $5F_n^2\pm~4=L_n^2$ without knowing $n$?

I'm trying to test a great many numbers $a^3+b^3$ to see if any of them are Fibonacci using the formula $$a^3+b^3=F_n \iff 5(a^3+b^3)^2\pm~4=L_n^2$$ I want to make my search more efficient by having ...
2
votes
0answers
17 views

Flow reduction by removing a set of k edges

I am trying to find an algorithm which recieves as input: 1) a Flow network N(G,c,s,t) in which the capacity of an edge is either 0 or 1 (i.e. Exists or not). 2) a positive integer k The output ...
0
votes
0answers
19 views

Is there a algorithm to extract the minimum number of Cartesian products from a set of formulas?

For example, we have a set of formulas as below: B*2*j B*3*i B*3*j C*2*j C*3*i C*3*j D*2*i D*2*j D*3*i D*3*j And we could have three Cartesian products to ...
0
votes
0answers
23 views

Reaching a proof

I'm trying to solve this problem: Link. After reading the problem, I realized that to start off, we can imagine the problem only in the positive axis, working only with $|x|$. Then, we want the ...
1
vote
1answer
32 views

Generalization of Jacobi symbol for higher powers?

Let $n$ be an odd positive integer of unknown factorization, and let $x$ be relatively prime to $n$. The Jacobi symbol $\left(\frac{x}{n}\right)$ gives me partial information on whether $x$ is a ...
0
votes
3answers
84 views

Algorithm for Fundamental theorem of arithmetic

What is a good algorithm for decomposing a number into a product of primes? What would be its time complexity?
0
votes
0answers
17 views

Algorithm to draw a 2D graph of bounds connecting points

I have a list of triangles, facets of a 3D convex hull, and I'd like to represent the relations between those facets on a 2D diagram, a bit like a puzzle, where each face is (for matter of simplicity) ...
1
vote
1answer
71 views

Solve non-linear equations of 3 variables using Newton-Raphson Method iterms of c,s and q.

The three non-linear equations are given by \begin{equation} c[(6.7 * 10^8) + (1.2 * 10^8)s+(1-q)(2.6*10^8)]-0.00114532=0 \end{equation} \begin{equation} s[2.001 *c + 835(1-q)]-2.001*c =0 ...
2
votes
1answer
43 views

Time complexity of random algorithm

I was wondering how to perform the complexity analysis of the following random algorithm. The answer are: $\Omega(n)$, $O(n²)$, and $\Theta(n)$. At first I thought to perform the analysis by saying ...
0
votes
1answer
40 views

Concrete Example of Maximum Likelihood Estimator

I was reading this article, about how seatgeek creates its algorithm for choosing the optimal seat: http://chairnerd.seatgeek.com/the-math-behind-ticket-bargains Most of it is straightforward up ...
0
votes
2answers
45 views

Improving an algorithm for defining a matrix

I am making a program of combinatorics. There is a step where I give an integer n and I want n positive or zero integers $a_i$ so that $\sum \limits_{i=0}^{n-1} a_i=\frac{n(n-1)}{2}$. I would like ...
2
votes
1answer
63 views

Algorithm - iterative method

I'm stuck on an exercise on algorithms, can you help me with this exercise? Solve this recursion using iterative method. $$T(n) = \begin{cases}1 & n=1;\\ 2, & n=2;\\ T(n-2) + n/2,& ...
1
vote
0answers
59 views

3-pass counting triangles algorithm

Hei guys, I need some hints on Counting subgraphs in data streams. Consider this 3-pass counting triangles algorithm: 1st Pass: count the number of edges |E| in the stream 2nd Pass: sample ...
4
votes
1answer
112 views

Bipartite graph matching like problem.

Let $A=\{a_1,a_2, ..., a_n \}$ and $B=\{b_1,...,b_m\}$ be finite sets. Also $A_1,...,A_k\subset A$ are covering of $A$ and $B_1,...,B_t\subset B$ are covering of $B$. Let $V$ be a set of pairs of ...
-4
votes
2answers
54 views

Which algorithm is faster for large values of n?

Algorithm A running time satisfies the relation $$A(n) = A \left(\left\lfloor\frac n2\right\rfloor\right) + n, A(1) = 2$$ and algorithm B running time can be expressed as $$B(n) = 2B\left ...
0
votes
2answers
31 views

Algorithm to find shortest time span for fixed ascent.

I have discrete dataset of values for $f(t)$. I now want to find the shortest amount of time $(dt)$ where the data "ascends" a certain amount $(x)$. So I want to find the minimal $dt$, where $f(t+dt) ...
2
votes
1answer
39 views

Is there a general algorithm to solve computable integral equation?

Hilbert's tenth problem ask for the general algorithm(finite number of operation) to solve of all Diophantine problems.Today, it is known that no such algorithm exists in the general case. What ...
3
votes
2answers
77 views

How to extend an existing orthogonal set of vectors?

Suppose I have $k$ vectors in $\mathbb R^n$ that are orthogonal to each other ($k \ll n$). Is there an efficient way to find another vector that is orthogonal to all these given vectors? If we put ...
1
vote
0answers
36 views

How do I use the digit-by-digit square root algorithm in a base-n context, e.g. $2^{16}$?

I have to take the square root of a number so large that there is no way to compute it directly. I thought if I divided it up into smaller pieces, I might be able to get this done in as few steps as ...
1
vote
0answers
20 views

Factorisation algorithm for polynomials in several variables over $\mathbb{Z}$.

What algorithm is used by a CAS to decide how to factor a polynomial in several variables over $\mathbb Z$?
0
votes
0answers
53 views

Calculating time complexity of algorithms written in pseudocode.

Nowadays we are interested to find some algorithms with a prescribed running time. For example if for certain decisional problem $X$ there is an algorithm with running time $O(n^3)$ we try to break ...
0
votes
0answers
56 views

Comparison of Pi with rational numbers

Is there a way to compare (i.e. to know if it is greater or less) Pi with any given rational number (given by a/b, where a and b are integers), and to know beforehand the maximum of steps (development ...
2
votes
1answer
31 views

Maximum number of induced $P_3$ in a $P_4$-free graph

Say I have a graph $G$ on $n$ vertices that is $P_4$-free (it has no induced paths of length 4). These are known as cographs. Note that $G$ might not be connected. I'd like to list the induced $P_3$ ...
1
vote
1answer
74 views

Mixed Q horn SAT

I am familiar with Horn formula: Formula whose clauses have atmost one positive literal. I am also familiar with Mixed Horn formula: Formula whose clauses are either 2 CNF or Horn. Question 1: But, ...
0
votes
0answers
38 views

Computational Streaming Model - longest decreasing subsequence

Question: Given a sequence of numbers from a stream of length $n$ (Streaming Model) for example: $(2, 6, 4, 7, 2, 8, 3, 1)$ Determine the longest decreasing subsequence (LDS) of length $k$ in that ...
0
votes
0answers
6 views

General question about algorithm convergence or well posedness

This is a rather general question. Say I am proposing a new optimization algorithm that yields a solution $x$ given some observations $y,z$. (Specifically, I solve some Euler-Lagrange equations to ...
0
votes
0answers
15 views

Fitting by an ellipsoid with a known center?

Consider a set of $N$ points in 3D of coordinates : $$p_{i} = \left\{x_{i}, y_{i}, z_{i} \right\}$$ The very general question I ask is : how to fit these points by the surface of an ellipsoid ...
0
votes
1answer
51 views

What is the meaning of nCk X nPk?

I am trying to understand the bulls and cows document, Page 6 , equivalences . Can someone please tell me what author means when he says nCk x nPk like 4P0 X 4C0 , 4P1 X 4C1 ?