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
35 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
50 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
72 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
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
109 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
74 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
33 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
13 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
35 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
34 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
167 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
35 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
32 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
24 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
124 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 ...
1
vote
1answer
51 views

Dijkstra's Algorithm- Two equal weights, one leads to a shorter path. What to do?

I am confused about this situation that happened to me as I was trying to solve a shortest path problem using Dijkstra's Algorithm. '$s$' is the starting point and '$t$' is finish. When I reach to ...
2
votes
1answer
30 views

Limit at Infinity of Rational Function

I'm following the Algorithm Design book by Eva Trados. In the 'Basics of Algorithm Analysis' chapter, I've come across a proof that I'm having difficulty understanding and can't find any proper ...
0
votes
1answer
21 views

Point scoring algorithm for users based on article submission.

There is a website where users contribute articles. User will score points based on the number of articles contributed. The point awarde should not be linear. The point score for each article ...
0
votes
1answer
81 views

How can I prove the correctness of this multiplication algorithm?

I want to know how I can prove that this algorithm is correct: ...
0
votes
0answers
11 views

If I have sets of 5 steps each, and a number that iterates trough them, how do I convert this number to set and set element?

Let's say I have $6$ sets each having $5$ elements. Each element has a number from $0$ to $29$. So set $1$ has $5$ elements ${0, 1, 2, 3, 4}$, set $2$ has ${5, 6, 7, 8, 9}$ I go trough them linearly, ...
0
votes
0answers
28 views

Slot size bound for chaining

This is a question from CLRS Q) Suppose that we have a hash table with n slots, with collisions resolved by chain-ing, and suppose that $n$ keys are inserted into the table. Each key is equally ...
0
votes
1answer
32 views

Assigning workers to tasks such that difference of the number of workers for each task to a given optimum is minimized

Im trying to find an algorithm to solve the following problem: We have a set of workers and some tasks, with not every worker being able to do any kind of task (but at least one). Theres is ...
0
votes
1answer
39 views

Which algorithm do I use to find the line center of a gaussian curve?

Which algorithm do I use to find the line center on the image below?
3
votes
1answer
36 views

Number of ways to color such that one color always leads

There are n boxes drawn out in a line. We have two colors, blue and red. We start coloring boxes from left to right. At any instant we want to color the boxes in such a way that number of boxes ...
1
vote
2answers
24 views

Finding the number of solutions satisfying an equation?

Given one condition $x_1+x_2+x_3=n$ where n is known number. Given a set of data X={$a_1,a_2....a_n$}. Can you help me find all possible cases satisfying the above condition $x_1+x_2+x_3=n$ ???
1
vote
2answers
36 views

Could anyone explain how is this Matlab code for log likelihood of Gaussian distribution implemented?

I was implementing Expectation-maximization algorithm for gaussian mixture module. However I realized my implementation has very bad accuracy. Then I found some code on internet. It seems this ...
2
votes
0answers
35 views

Dynamic Programming: Stock Exercise

I'm having a trouble dealing with this problem: Since future market prices, and the effect of large sales on these prices, are very hard to predict, brokerage firms use models of the market to ...
0
votes
0answers
25 views

Independent Sets that are Odd Covers

I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd ...
-2
votes
1answer
47 views

Prove that $\log n = O(\log^2 n)$

Trying to solve this, but I can't seem to figure it out. Its fairly straight forward.