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
0answers
12 views

Efficient approximation of nth term without losing accuracy

Probelem Given a recurrence relation for gn as g0 = c where is a contant double. gn = a* gn-1 + b* gn-2 then find the value of another recurrence given by hn = gn/exp(n) constraints: 1 ...
1
vote
1answer
32 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 ...
6
votes
5answers
310 views

pandigital rational approximations to the golden ratio and the base of the natural logarithm

Steven Stadnicki suggested in a comment that I post the following as a question. The golden ration $\phi$ is given by $$\phi = \frac{1+\sqrt{5}}{2} \approx 1.618033988.$$ A rational approximation is ...
1
vote
1answer
26 views

How can we measure the accuracy of prediction algorithm?

We have created a prediction algorithm, which predicts the chances of confirmation of ticket based on some parameters, and gives the prediction in percent. Now, how do I measure how close the ...
3
votes
0answers
43 views

Can every mathematical proof be seen as the verification of some algorithm's action?

Put another way: Can every mathematical proof be reformulated to be about some class of Turing Machines? Example Any proof of the existence of infinite prime numbers is equivalent to the statement: ...
1
vote
1answer
14 views

Use the limit rule to find Big Oh characterization of for loop

Find Big Oh characterization in terms of n, the professor says to use the limit rule for big Oh which says f(n) = O(g(n)) means f(n) "≤" g(n) => lim n->inf f(n)/g(n) = c where c is 0< c < inf ...
0
votes
0answers
28 views

Is there an algorithm for computing pushouts in finite sets?

Does anyone know of an algorithm for computing pushouts in finite set? That is, given finite sets $X$, $Y$ and $Z$ with maps (of sets) from $X$ to $Z$ and $Y$ to $Z$, is there an algorithm for ...
0
votes
1answer
38 views

Given number n. Find the n digit numbers.

For eg; if n = 2, Then the output should be 10,11,...99 // (i.e) 10 to 99 if n = 3, Output: 100,101...999 //note the 3 digit numbers are returned. The range would be 100 to 999. How can i achieve ...
1
vote
1answer
34 views

Algorithm and top-points.

Problem: For an array $A[1],\dots,A[n]$, with $n\geq 3$, it holds that $$A[i+1]>\frac{A[i]+A[i+2]}{2},\qquad i\in \{1,2,\dots, n-2\}$$ That is, it holds that $$A[2]>\frac{A[1]+A[3]}{2},\dots, ...
3
votes
1answer
385 views

How to get numbers with distinct digits within some range?

I have a little program I'm working on for my project (a simple practice in school), part of the program is that it should receive input composed of an array of 7 digit (or less) numbers which should ...
1
vote
3answers
2k views

Nested Summation

I have the following nested sum : $$\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{j}x = x+1$$ I don't have a clue how to solve this one, can somebody help me? Thanks in advance. ${}{}$
0
votes
0answers
24 views

Implementing FizzBuzz game

I need to build an electrical-circuit for the FizzBuzz game. There's a signal, called next which increment the current number by one. The rules are simple - You ...
8
votes
1answer
575 views

Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?

I have been reading Introduction to Algorithms by Cormen. Before explaining Strassen algorithm the book says this: Strassen’s algorithm is not at all obvious. (This might be the biggest ...
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
2answers
45 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 ...
0
votes
1answer
24 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 ...
0
votes
1answer
298 views

Work out an algorithm

I'm wanting to work out the algorithm what gives these results It's always a $6$ digit code that is turned into a $4$ digit code $000000$ is $1558$ $000001$ is $9617$ $000002$ is $8633$ $000010$ ...
1
vote
1answer
38 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 ...
1
vote
1answer
60 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
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 ...
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 ...
2
votes
2answers
1k views

Convex hull has the smallest perimeter

How do you show that the convex hull of a given set of points S, always has the minimum perimeter ? By perimeter i mean the length of the boundary of the hull
0
votes
1answer
31 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
23 views
0
votes
0answers
19 views

Asymptotic notations (Big Omega) [closed]

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 ...
3
votes
1answer
31 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 ...
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 ...
3
votes
3answers
413 views

For Maths Major, advice for perfect book to learn Algorithms and Date Structures

Purpose: Self-Learning, NOT for course or exam Prerequisite: Done a course in basic data structures and algorithms, but too basic, not many things. Major: Bachelor, Mathematics My Opinion: Prefer ...
0
votes
1answer
30 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 ...
1
vote
0answers
14 views

Select a random edge [closed]

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.
0
votes
2answers
675 views

number of ways to divide an array into m sets of equal sum

I recently came across this question: Find the number of ways to divide and array into m subarrays of equal sum? Ex: given a[]= {1, 1, 2, 3, 4, 5}, m= 2 ...
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 ...
13
votes
0answers
199 views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
2
votes
0answers
24 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
25 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
18 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
30 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 ...
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?
3
votes
2answers
39 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
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 ...
0
votes
0answers
14 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 ...
1
vote
0answers
46 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
1answer
154 views

Can a method related to “Weisfeiler-Lehman Method” provide better time complexity for Graph Isomorphism than existing result?

Cai-Furer-Immerman showed that the W-L(Weisfeiler-Lehman ) hierarchy cannot distinguish general graphs except at linear dimension. Even besides CFI's result, there is good reason to believe that ...
7
votes
1answer
591 views

The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence $T(m,n) = T(n, m ...
1
vote
2answers
42 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 ...