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)

0
votes
1answer
19 views

Rigorously prove while loop executes $\lceil \log_{2}(\log_{2}(n)) \rceil$ times

Problem Suppose we have the following code k := 2 while k < n do k := k * k end while How many times will the loop execute? Current Work My intuitive ...
1
vote
1answer
33 views

Why does my induction proof of an algorithm's running time always seems tautological?

I'm having some trouble proving algorithm's running times. The problem is not so much that I can't define the recurrence in open form nor that I cannot come to the conclusion that I know to be true. ...
0
votes
0answers
14 views

Proof of optimal substructure for the “plus sign game”

First of all, I think there's no "plus sign game", I have just invented the name to describe the problem faster. Another thing: I thought to ask the question in these stack exchange's website because ...
1
vote
1answer
20 views

Tool for the partition problem with planar rectangles

The classical "partition problem" asks how many ways one can write a given natural number as a sum of smaller numbers. One variant of this would be to ask if a positive real number can be expressed ...
0
votes
2answers
43 views

How many ways are there to solve a Rubiks cube?

Friends have been arguing that a rubiks cube could never be mastered cause there are too many different ways to solve it cause there are 43,252,003,274,489,856,000 positions the Cube could have, so ...
1
vote
1answer
59 views

How to calculate distance from the International Space Station given coordinates?

How would one calculate how far away a point is (latitude/longitude) from the international space station given its latitude/longitude/altitude? The distance would be direct as if drawing a straight ...
0
votes
0answers
11 views

Fill valleys of waveform (flatten them, level them out)

I have waveform data and want to fill the valleys with a given maximum width. That is, I have sample values with a constant distance. The parameter "maximum width" determines the y-position of the ...
0
votes
0answers
25 views

Pseudo-arclength continuation scheme

I have implemented a simple parameter continuation scheme to find the stationary solutions of a nonlinear problem at different parameter values. However, my scheme cannot handle bifurcations - it ...
0
votes
1answer
30 views

What exactly does this inequality do?

I this paper which is titled "KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation", in the section about "kmeans algorithm for vector quantization", there is the ...
0
votes
1answer
22 views

The complete bipartite graph K2,5 is planar [on hold]

I wonder why The complete bipartite graph K2,5 is planar?
3
votes
1answer
30 views

the least $m$ such that $a^m\equiv 1 \mod n $ for fixed $a,n$.

Is there any known method for calculating $\lambda_a(n)$ which returns the smallest integer $m$ such that $a^m\equiv 1 \pmod n$ where $\gcd(a,n)=1$ ? I searched but I found nothing, is there at ...
0
votes
0answers
19 views

Asymptotic notations (Big Omega) [on hold]

Use the definition of big- $\Omega$ to prove that $n + n(\log n)^2 = \Omega(5n + 9n(\log n)^5)$. Provide the appropriate $c$ and $k$ constants ? I am new to the topic : Advanced Analysis of ...
0
votes
2answers
80 views

prerequisit for BigO notation

I have been trying to learn algorithms for a long time now and I am really struggling with the math part and don't know what to do. I only know very basic math, so my question is what do I have to ...
2
votes
3answers
83 views

Evaluate the summation $\sum_{k=1}^{n}{\frac{1}{2k-1}}$

I need to find this sum $$\sum_{k=1}^{n}{\frac{1}{2k-1}}$$ by manipulating the harmonic series. I have been given that $$\sum_{k=1}^{n}{\frac{1}{k}} = \ln(n) + C$$ where $C$ is a constant. I have ...
1
vote
0answers
14 views

Select a random edge [on hold]

Given a source of random bits and a multigraph G(V, E), provide an algorithm for selecting an edge e ∈ E uniformly at random in O(n) time.
6
votes
0answers
37 views

Generating a Random Connected Graph

Given a graph G(V, E), with |V | = n and |E| = 0 (that is, the graph is empty), and a static set F containing all the possible edges. Consider the following algorithm for generating a random graph. ...
1
vote
0answers
13 views

Signal recovery using Majorization-Minimization with Quadratic Upper Bound

I am trying to formulate a majorization-minimization (MM) (via quadratic upper bound) approach to total variation denoising (TVD). The total variation denoisng objective function is defined as an ...
1
vote
1answer
26 views

How to calculate optimal sizes of rectangles for this type of array visualization?

Given array of positive numbers, I would like to draw this diagram and be able to put descriptions inside: There should be no empty space left, consider that these numbers represent % of total. Do ...
0
votes
1answer
29 views

01-integer programming

can someone please explain to me what is meant by easily converting negative objective function coefficients? This may seem like a restrictive set of conditions, but many problems are easy to ...
2
votes
0answers
23 views

Border rank of tensors

Can anyone help me find the rank and border rank of the following tensor: \begin{align} T=a_{11}\otimes b_{11}\otimes c_{11}+a_{12}\otimes b_{21}\otimes c_{11}+a_{11}\otimes b_{12}\otimes c_{12}\\ ...
0
votes
0answers
22 views

Strassen's Laser Method Technique AND Tensors in matrix multiplication algorithms

I understand the first algorithm presented by Strassen in 1968, for fast matrix multiplication. This was the first improvement to the naive approach of multiplying matrices. Thereafter, he went on to ...
1
vote
0answers
17 views

condition number with component-wise norm for the sample variance any help is appreciated! :)

I'm looking through some notes and came across the following two statements in the notes where the author states it can be shown that one leads to the next. I've tried to show this using the ...
2
votes
0answers
17 views

Setting up a recurrence for Odd-Even Mergesort

Given the below algorithm How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort? What I've tried For ...
0
votes
1answer
29 views

Explain instability in Numerics so that I can understand and answer this question that involves roots of a equation

I found this question in my math book: Instability. For small |a| the equation (x - k)^2 = a has nearly a double root. Why do these roots show instability? I read and belive I understood the ...
0
votes
0answers
12 views

similarity between two ranked sequence

How can I measure similarity/distance between two sequences of ranked numbers/letters. The two sequences are of different length, and only have some elements in common? For example, if I have three ...
3
votes
2answers
38 views

Selecting k distinct numbers from an array with increasing probability distribution

I have to select k distinct numbers from an array such that probability of a number getting selected is more if it is at the end of the array (probability increases linearly). I'm thinking of ...
0
votes
0answers
13 views

Determining accuracy of time using Cristian's Algorithm [closed]

When determining the accuracy of a result, Cristian's Algorithm says that you do: $$ \pm \frac{T_1 - T_0}{2} - T_m $$ Why is this not $$-2T_m$$ to account for the min transmission time on both ...
2
votes
3answers
46 views

Fastest way to perform this multiplication expansion?

Consider a product chain: $$(a_1 + x)(a_2 + x)(a_3 + x)\cdots(a_n + x)$$ Where $x$ is an unknown variable and all $a_i$ terms are known positive integers. Is there an efficient way to expand this?
1
vote
0answers
45 views

Setting up and solving a recurrence relation

Assume we have two lists, $A$ and $B$; both are sorted lists each with $n$ elements (assume $n$ is a power of 2). We want to recursively merge the odd-indexed elements from each list: merge $a_1, ...
1
vote
2answers
41 views

How to approximate $x^y$ using a quadratic function

I need to build an algorithm that finds the approximately $x^y$ where $x = [0, 1]$ and $y = [0, 0.4)$. This is for a computer algorithm (the standard library is too slow). I thought about making a ...
0
votes
1answer
44 views

Finding all intersecting circles of one circle.

I have one circle $C_0(x_0,y_0,R_0)$ in a plane (which moves around here and there). There are many other circles on the same plane $C_1(x_1,y_1,R_1),C_2(x_2,y_2,R_2).....,C_n(x_n,y_n,R_n)$ where ...
2
votes
1answer
28 views

Show that there is such an algorithm

Let $L_P = \{+, \geq; 0, 1\} $. The first-order theory of $\mathbb{N}$ in the language $L = L_P \cup \{exp_2\}$, where $exp_2$ the function which sends a natural number $n$ to $2^n$, is decidable. ...
0
votes
1answer
20 views

how to determine maximum length of chain of tail-to-head connections in a given word list

Given a finite set of words, I wish to to write an algorithm which will create a chain of words, where the tail (last letter) of a word n will be the same as the ...
1
vote
2answers
31 views

What's theoretical maximum information compression rate?

Let's say I've got a random bit sequence s and a reversible function f(s), for which the following statement ...
2
votes
1answer
43 views

Find edge disjoint spanning tree subgraph between A and B

Given an undirected graph G(V,E). A and B are elements of V. Identify a subgraph of G containing A & B with 2 edge disjoint spanning trees (or prove one doesn't exist). I have found several ...
0
votes
1answer
73 views

Is an algorithm to find all primes up to $n$ that runs in $O(n)$ time fast?

I kindly ask you if it is useful or fast for a prime number generator to run in $O(n/3)$ time? I believe I have a way to generate all $P$ primes up to $n$, quickly and neatly, in $P$ comparisons and ...
2
votes
1answer
31 views

Tensors in matrix multiplication algorithms

Fast matrix multiplication algorithms, be it the Winograd and Coppersmith algorithm or any further improvement of it, extensively use tensors. In fact, the entire construction is based on tensor ...
3
votes
0answers
34 views

How to create a new formula for a fractal-type image?

(If this is the wrong place to ask, then PLEASE tell me where to take the question instead of chewing me out over this.) I have been learning how to write out SVG by hand, and in the process made a ...
1
vote
2answers
53 views

Manual generation of all permutations of N non-repeating elements

I am looking to find if there is a way to manually (meaning, not using a machine that has high memory capacity) generate all the permutations of a set of N non-repeating (unique) elements by the way ...
0
votes
0answers
23 views

How can I modify this simple code to include the pressure term? (1-D Navier Stokes)

I have a mathematical model that involves a cylindrical container that is being modeled with a one dimensional simplification as the system is isotropic with respect to the z-axis. As part of the ...
0
votes
0answers
15 views

How to get accuracy of prediction?

I am working on a project where there is a part, which is based on the confidence level (between 0 and 1). The confidence level here is for various situations finally going Yes or No. So, 0.9 ...
0
votes
1answer
24 views

Making all row sums and column sums non-negative by a sequence of moves

Real numbers are written on an $m\times n$ board. At each step, you are allowed to change the sign of every number of a row or of a column. Prove that by a sequence of such steps, you can always ...
0
votes
0answers
12 views

Distributing resource based on Efficiency

I am trying to form an optimization problem where I have $k$ nodes who transmits packets with rate $x_k$. The objective is to maximize the rate. $\hspace{28mm} \text{ Maximize } \sum_k \log x_k$ ...
0
votes
0answers
27 views

Algorithm for finding the value of determinant

Okay I am writing to write a program which computes the determinant of a matrix. So is there an algorithm that allows you to do that ? Are there any other ways of finding the determinant value other ...
0
votes
1answer
17 views

How to combine not disjoint sets in all possible ways?

Let's say that I have a set of sets. Each of them composed by two or more subsets. For example: S = {S1, S2, S3} S1 = [0,1,2,3] = {S11 = [0,1], S12 = [2,3]} S2 = [2,3,4,5] = {S21 = [2,3], S22 = ...
0
votes
1answer
61 views

Bresenham's Line Algorithm

This is a page from the book Schaum's Outline of Computer Graphics. The text says, Selecting T means $d_i>=0$, and, selecting S means $d_i<0$. I didn't understand why. Can you please ...
1
vote
0answers
21 views

Process Transition Algorithm

I have a process with 100 possible states and independent entities going through the process. All the Entities have been observed through a span of 5 years at the end of each month. When the ...
2
votes
2answers
30 views

Proof of completeness and soundness of a proof system

As stated here, https://en.wikipedia.org/wiki/List_of_rules_of_inference, "a set of rules can be used to infer any valid conclusion if it is complete, while never inferring an invalid conclusion, if ...
0
votes
1answer
35 views

Program languages recommended for complexity theory

I am an undergraduate studying mathematics and one of my interests include complexity and computability theory. I have no experience in programming. The computability theory books I looked into didn't ...
0
votes
0answers
8 views

Shrink wrapping algorithms to make a mesh watertight for 3d printing

I'm investigating algorithms to make a mesh watertight for 3d printing. I'd be very excited to implement such algorithms. The initial input is a mesh which is not watertight and I want to understand ...