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
1answer
30 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
4answers
76 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
14 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
55 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
39 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
36 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
62 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
55 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
37 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
76 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
33 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
19 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
44 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
54 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
70 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
36 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
50 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 ?
0
votes
0answers
16 views

Quantization minimizing the quadratic error

I am working on a quantization problem which could be express in these terms : Given a set of positive reals $\{x_1, x_2,\dots,x_M\}$, I need to find another set $\{y_1,y_2,\dots,y_N\}$ of size $N ...
2
votes
2answers
51 views

Given four points, verify if they form a Tetrahedron

As per the title, I've been requested to build a program that -given 4 points in space- determine if they form a 3D shape and if this is case to present it's volume. For the volume part of the ...
7
votes
1answer
97 views

Fast algorithm for approximating Eigenvalue distribution of large sparse matrix

I am interested in the eigenvalue distribution of a huge $2^{16}$x$2^{16}$ Hermitian sparse matrix with spectrum contained in $[-1,1]$. That is I don't need to know all eigenvalues exactly, but rather ...
0
votes
1answer
33 views

Multi-Tape Turing Machines to find palindrome

Given an Alphabet {a,b,c} , produce a Turing Machine which recognize if a given input string X is a palindrome. means if X is a palindrome, TM is halting and accepting, else halting and rejecting. ...
2
votes
1answer
73 views

Logarithm of $\frac{a^k}{a^k-1}$

On a question on this site there is an explanation of the algorithm Knuth gives in The Art Of Computer Programming to compute an approximation of $y = \log_bx$. Now, I understand why it works; ...
0
votes
0answers
31 views

Finding the largest $3^k$ number less than the natural number

Given the natural number $N$ in binary representation (computer memory). How to obtain the representation of the $N\rightarrow\sum^{M}_{k=0}(a_k\cdot(3^k+1))$ form or, at least, how to find the $M$? ...
1
vote
1answer
32 views

Using rgb triplets in “scalar” math

So I'm reading a computer graphics research paper and I'm confused as to how to interpret certain formulas that are being used. In the paper, a value σ is defined as an RGB triplet. Later on, that ...
2
votes
0answers
12 views

Ordering binary matrices for reflection/rotation

I have a collection of $n\times n$ binary matrices and I would like to reduce it for symmetry ($D_4$ -- reflections and rotations). The naive method of testing each pair is very slow because the ...
1
vote
1answer
29 views

An algorithm to rate players in team?

I would like to design an algorithm to rate players in a team sport. One team of N players plays a match against another team of N players. The individual players will possibly change, from match to ...
1
vote
1answer
33 views

Computing eigenvalues of principal submatrices of Kronecker product of two PSD matrices

Given two PSD matrices $A \in R^{n \times n}$ and $B \in R^{m \times m}$ with eigenvalues $\lambda_i$ and $\mu_j$ respectively, the eigenvalues of the Kronecker product $A \otimes B$ are given by ...
1
vote
0answers
33 views

How to find the lengths of the shortest paths in a directed graph in $O(m)$ steps?

Let $G = (V,A)$ be a directed graph for which it is true that if $(v_i , v_j) \in A$, it is implied that $i < j$. Question: How does one construct an $\mathcal{O}(m)$ algorithm to find the ...
11
votes
3answers
158 views

Deducing correct answers from multiple choice exams

I am looking for an algorithmic way to solve the following problem. Problem Say we are given a multiple choice test with 100 questions, 4 answers per question (exactly one of those four being ...
2
votes
3answers
60 views

Why in formulas a return value of a function sometimes shown as an argument?

Sorry for a perhaps newbie question, I had a hard time in the school. Well, the title says the problem, let's look at example, which I stole from the coursera video-lectures about an algorithms: ...
1
vote
0answers
34 views

O(m) all-pairs shortest paths algorithm for directed acylical graph

An exercise I'm working on asks me to devise an $O(m)$ algorithm for the all-pairs shortest paths of the graph $G = (V, A)$, where $(v_i, v_j) \in A$ implies $i < j$. I'm wondering whether this is ...
0
votes
0answers
24 views

Computer program for decomposing a graph into subgraphs?

Obviously there are programs out there that can find perfect matchings. I am interested in finding out if there is a program that can, for instance, tell when graphs like the cube graph $Q_n$, has ...
2
votes
1answer
87 views

Questions about a computer science field

I would like to have some information about the computer science field, " Algorithmic and Systems Analysis ". Is this a field of theoretical computer science? What subjects are related with this ...
1
vote
1answer
30 views

Algorithm for checking Prime Power

Suppose we are given some arbitrary positive integer. How can we check whether the integer is a prime power? Brute force would be very inefficient in this case.
-1
votes
1answer
23 views

Reverse simple formula [closed]

I am needing to reverse this simple formula to get A a = variable b = float Formula a + a * b = c Example 100 + 100 * 1.5 = 250 How to get back 100
0
votes
0answers
19 views

Find a depending formula

I cant find a literature that can help me with this question. We have x1, x2, x3 and y (over 1000 examples). x1 x2 x3 y 1 2 3 10 1 10 0 2 etc y is ...
12
votes
1answer
123 views

When is a number in $\mathbb{Q}(\sqrt{a_1},\ldots,\sqrt{a_n})$?

Given an algebraic number $\alpha$ with minimal polynomial $P(x)$ of degree $2^n$, how can I decide if there are integers $a_1,\ldots,a_n$ such that ...
0
votes
1answer
28 views

Smoothing Spline Example

I am learning the smoothing spline method. I saw that smoothing spline is a penalty term to reduce overfitting in linear regression. Given dataset {$(x_1,y_1),(x_2,y_2)..(x_n,y_n)$}So the formular ...
2
votes
3answers
31 views

Performing matrix chain multiplication by hand

I'm trying to gain intuition for writing a matrix chain multiplication algorithm by working through a few problems by hand. I see plenty of worked-through solutions on sets of three or four solutions, ...
1
vote
0answers
20 views

Minimize the number of nonzero elements of a matrix through elementary row operations?

Is there a general method to minimize the number of nonzero elements of a real rectangular matrix through elementary row operations? I am looking for something analogous to Gaussian elimination, that ...
1
vote
1answer
85 views

How many regulars do the primorials 223092870 and 6469693230 have?

Regulars = Divisors + Semidivisors http://global.britannica.com/EBchecked/topic/496213/regular-number So for example: 6 has 5 regulars: 1, 2, 3, 4, 6. 8 has 4 regulars: 1, 2, 4, 8. 9 has 3 ...
0
votes
0answers
20 views

Mathematically safe, open TAN generation and verification

For an upcoming Arduino project I need to generate, distribute and verify TANs (transaction authentication numbers). Let me explain (and assume for a second this is happening on a bigger computer). I ...
0
votes
0answers
19 views

Proving function defined by algorithm is convex

I'm working on my bachelor thesis and I'm trying to prove a conjecture, but I seem to miss the hint that helps me. I have an algorithm that defines a function $f:\mathbb{R}_{\geq ...