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)

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
23 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 ...
-1
votes
1answer
19 views
0
votes
0answers
17 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 ...
3
votes
1answer
25 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
2answers
57 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
79 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
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 ...
1
vote
0answers
13 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.
0
votes
2answers
641 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 ...
5
votes
0answers
29 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
11 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
198 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
22 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
27 views

Minimize a convex function over a convex cone

I want to minimize a strictly convex function over a convex cone, where the number of parameter is the same as the sample size. Does the Newton-type algorithm have a global (or local) convergence ...
0
votes
0answers
19 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
26 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
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
11 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
12 views

Determining accuracy of time using Cristian's Algorithm [on hold]

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
44 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
150 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
590 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
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
41 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
331 views

Maximum subarray problem

Given a 2d array N*M made of only 1's and 0's . I need to find a maximum subarray(square or rectangle) between two rows of the given 2d array which has all ones inside it. I need to find count of ones ...
5
votes
2answers
356 views

Algorithm for tetration to work with floating point numbers

So far, I've figured out an algorithm for tetration that works. However, although the variable a can be floating or integer, unfortunately, the variable ...
9
votes
5answers
2k views

General McNugget problem

The classic McNugget problem states: Chicken McNuggets can be purchased in quantities of 6, 9, and 20 pieces. You can buy exactly 15 pieces by purchasing a 6 and a 9, but you can't buy exactly 10 ...
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 ...
4
votes
1answer
54 views

Polynomial algorithm for problem in graphs which can also be solved as a linear programming problem.

I have an (undirected) graph $G = (V, E)$. For each vertex $i \in V$ we have a cost associated $v_i$ and for each edge $e \in E$ we have a prize associated $x_e$. My problem is to find $W \subseteq ...
0
votes
2answers
498 views

Greedy Algorithm, Fewest overlaps

Hi I need help doing this problem. I've been working on it for like 2 hours now and I'm no where. I'm literally about to throw my computer. I've watched youtube videos, reread my notes. The homework ...
0
votes
3answers
103 views

Solve the recurrence $T(n) = 2T(n-1)+n^2$

Solve the recurrence $$T(1) = 1, T(2) = 1, T(3) = 1,T(n) = 2T(n-1)+n^2, n > 3$$ I have now, $$T(n) = 2T(n-1)+^2 $$ $$= 2(2T(n-2)+(n-1)^2+n^2$$ $$=4T(n-2)+2(n-1)^2+n^2$$ $$....$$ ...
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 ...
2
votes
1answer
379 views

Fast generation of Pareto-distributed randoms.

I'm developing a library of routines for generating random numbers for simulations (it's on GitHub). I've included fast routines for normally distributed and exponentially distributed randoms, using ...
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 ...
0
votes
1answer
290 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
7
votes
3answers
80 views

Infinite sequence of $3$ numbers with nonrepeated parts.

I am thinking about this problem. Can we construct infinite sequence with $3$ numbers so that no repeated parts exist in it? There should not be subsequence with $2k$ numbers so that its left and ...
2
votes
1answer
27 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. ...
1
vote
2answers
30 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
401 views

In context of graph search,what is mini-max principle

after doing some Google search i am not able to find an effective and understandable explanation of mini-max principle,anyone please explain it to me.
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 ...
0
votes
1answer
72 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 ...
1
vote
2answers
289 views

Give an algorithm that computes a fair driving schedule for all people in a carpool over $d$ days

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none ...
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 ...
1
vote
2answers
52 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 ...
-1
votes
1answer
100 views

How to make this cubic root (C++) algorithm faster?

Okay, so this is the algorithm. It works but takes too much time. ...