Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

0
votes
0answers
12 views

Modifying U=mxn SVD Algorithm to U=mxm Algorithm

I have painstakingly ported this Python source "svd.py" to C++. I confirm it works for the example it comes with. While testing another example (this one, from Wikipedia), the assert statement trips ...
2
votes
1answer
18 views

Need an Algorithm Such that $\sum_{k-i}^{j}{A[k]}$

I need an algorithm for real application. Suppose we have array A (positive & negative ) numbers. we want to find index i, j such that $\sum_{k-i}^{j}{A[k]}$ has the lowest difference to zero. ...
2
votes
0answers
28 views

Can we sort 6 numbers with at most 9 comparison? [duplicate]

i know there is an algorithm to sort 5 numbers with 7 comparison. Can we sort 6 numbers with at most 9 comparison? thanks to all.
8
votes
1answer
66 views

SQRTSORT from Vazirani's book on algorithms

I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
6
votes
1answer
105 views
+50

Intuition behind accelerated first-order methods

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ Suppose that we want to solve the following convex optimization problem: $\min_{x \in \mathbb{R}^n} g(x) + ...
2
votes
0answers
28 views

Minimise total cost and count ways

A country has a + b cities located in a row, which are uniformely placed. There are two large telecommunication operators in this country. The first operator will install BTSs in a cities and the ...
-1
votes
0answers
45 views

Paper pen algorithms [on hold]

I want all paper and pen algorithms from addition to fields medal problems. Where do I go? I've searched the web, I've even bought a book, but without any luck.
1
vote
1answer
35 views

Finding Kth string by applying given operations

Given is a matrix of dimension 4*4 in which we are given the result when value along row is computed with value along column. ...
0
votes
1answer
15 views

algorithm to see if some sign(s) of terms will sum to zero

I was trying to develop an algorithm so see if a given set of terms $a,b,c,d$ can sum to zero given any possible combination of signs $+/-$ on those terms. How does one compute how many distinct ...
4
votes
3answers
89 views

2000 Olympiad in Informatics Question on Box

I have an old Olympiad question on informatics. There are 31 boxes. In each box there is one number. We know the number if and only if we open the box. We want to calculate the minimum number of ...
0
votes
0answers
22 views

Algorithm of matching points between two point sets

I have two point sets $A=\{a_1,a_2,...,a_m\}$ and $B=\{b_1,b_2,...,b_n\}$ $(m\ge n)$, and want to find a injection map $\phi$ from $B$ to $A$ such that it minimizes $\sum{||b_i-\phi(b_i)||}$. There ...
3
votes
1answer
80 views
+50

Base of logarithm decrease when variable count increase

I run a large online platform where users submit articles and earn points. I am working on an algorithm where the more comments they submit, the higher score they will receive. In its simplest ...
0
votes
0answers
9 views

Perlin noise seems to be distributed like on a bell curve

I coded a perlin noise function, (gradient noise, not value noise). Weirdly, (or maybe it's normal?) my values seem to be distributed pretty much like on a bell curve. I guess I should fix my ...
1
vote
1answer
21 views

Omega Notation and Average Running Time Problem

if we have an algorithm that average running time of randomized algorithm A for input of size n is equal to $\theta(n^2)$. why there would be an input data such that A solve it in $\Omega(n^{3n})$?
-1
votes
1answer
64 views

Chess Game with N knights [on hold]

Given an infinite chess board containing N knights. The bottom left corner of the board is labelled as (0,0). Two geeks decide to play the following game on the board : In one turn, a player may move ...
0
votes
1answer
21 views

Maximal-size set of disjoint edges

Inspired by a "real-world" puzzle (actually, an unimportant aspect of a free-to-play game someone I know is playing)... Given an arbitrary (finite) undirected graph, I want to compute a ...
-3
votes
0answers
45 views

“How to Easily Memorize the Multiplication Table I The Great Courses” [on hold]

https://www.youtube.com/watch?v=v1Ih3-mDPUk How can I find tips like these throughout the whole subject of mathematics? Is there an tag I am looking for or something along the lines? Any ideas how to ...
0
votes
0answers
7 views

Estimate time it takes the minimum mean cycle cancelling algorithm to converge

This particular algorithm solves the circulation problem, equivalent to the minimum-capacitated flow. My question rather than only from this particular algorithm, but for combinatorial solutions in ...
5
votes
1answer
99 views

$X^A \equiv B \pmod{2K + 1}$

I recently found this problem which asks you to find an algorithm to find all $X$ such that $X^A \equiv B \pmod{2K + 1}$. Is there something special about the modulus being odd that allows us to ...
11
votes
3answers
209 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 ...
0
votes
2answers
24 views

Fastest way to find the top points in a rectangle

Given a rectangle X1,Y1 and X2,Y2 such that X1,Y1----------------- | | | | ----------------------X2, Y2 And given a ...
0
votes
3answers
69 views

Wolf cabbage and goat using dijkstra.

A farmer has to cross a river with a wolf, a goat and a cabbage. He has a boat, but in the boat he can take just one thing. He cannot let the goat alone with the wolf or the goat with the cabbage. ...
6
votes
2answers
5k views

Continuous coloring of a Mandelbrot fractal

I've recently started making a small fractal app in Javascript using the famous Mandelbrot bulb $(z = z^2 + c)$. I've been trying to find the best method of coloring the points on the complex plane, ...
5
votes
1answer
195 views

Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded

Given an undirected graph $G=(V,E)$, two distinct vertices $s,t\in V$, a weight function $f:E \to \mathbb{N}$, and a constant $M\in \mathbb{N}$, does there exist a pair of edge disjoint paths ...
3
votes
2answers
39 views

Smallest value taken by a quadratic polynomial in two variables.

Let $p$ be a degree $2$ polynomial with integer coefficients, say $$p(x,y) = Ax^2 + By^2 + Cxy + Dx + Ey + F.$$ I would like to find an algorithm which solves the following: Problem 1: Given ...
1
vote
1answer
33 views

How to generate a point cloud with known symmetry?

So I would like to know if there are any published algorithms to generate point clouds with known symmetry groups, such as $D_{3h}$ or $O_h$ and stuff like that. I know lots and lots of point clouds ...
1
vote
1answer
30 views

Algorithm for retrieving all the permutations (randomized) for a vector sequence 1…N with only unique values

Here is the problem: I have a vector of $N$ elements long (containing only unique values from $1...N$). I am searching for an algorithm to obtain all the (randomized) combinations possible, where ...
2
votes
1answer
187 views

Algorithm to find the total resistance between 2 vertices of a graph

Assume we have a graph, and resistors are placed on the edges. I want to know if there is an algorithm that find the total resistance between any 2 vertex. i have a hard time finding any description ...
0
votes
0answers
51 views

Probability of producing a finer balance in quicksort

So this question is a starred one in CLRS Q) Argue that for any constant 0< $\alpha$ $\leq$1/2, the probability is approximately 1-2$\alpha$˛that on a random input array, PARTITION produces a ...
0
votes
0answers
7 views

what is a non parametric iterative algorithm?

I am trying to uderstand mean shift algorithm.Mean Shift is a non parametric iterative algorith.What does it mean?
1
vote
1answer
25 views

Algorithm to multiply nimbers

Let $a,b$ be nimbers. Is there an efficient algorithm to calculate $a*b$, the nim-product of $a$ and $b$? The following rule seems like it could be helpful: $$ 2^{2^m} * 2^{2^n} = \begin{cases} ...
10
votes
6answers
4k views

Fastest way to calculate $e^x$ up to arbitrary number of decimals?

What are other faster methods of calculating $e^x$ up to any number of decimals other than using the Taylor series formula?
1
vote
3answers
41 views

Big-O, Omega, Theta and Orders of common functions

Based on this table, is it generally going to be true that for two functions whose most "significant" terms are of the same order that they will be big-Theta each other? And a function of order ...
1
vote
1answer
34 views

For an alphabet of size $N$, how many strings have all of its substrings of length $\geq 2$ unique?

For an alphabet of $N$ characters, how many strings can be formed (including the empty string) so that no substring of length $\geq 2$ appears more than once in the string? The maximum length of such ...
3
votes
3answers
57 views

How to generate $\log$ function that intersects at $(0,1)$ and $(1,0)$?

I apologize for any incorrect or missing formatting, first time posting in the math stack exchange. It's been a few years since I've done any kind of calculus, so I remember nothing at all, which is ...
0
votes
0answers
17 views

How to perform parallel cholesky factorisation

I am a student trying to understand and implement a parallel cholesky factorisation algorithm for sparse matrices in software. Can anyone give an example of a parallel cholesky factorisation ...
0
votes
0answers
26 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
1
vote
1answer
297 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
1
vote
1answer
646 views

Formal Proof of Counting Sort and Bucket Sort Algorithms

I'm new to this forum so please be patient. I'm studying two sort algorithms: counting sort and bucket sort. In numerous books I found examples, as a 'proof' that these algorithms work, but those ...
0
votes
1answer
74 views

Find if permutation is possible

Given a permutation of natural integers from 1 to N, inclusive. Initially, the permutation is 1, 2, 3, ..., N. We are also given M pairs of integers, where the i-th is (Li,Ri). In a single turn we ...
2
votes
0answers
79 views

Finding optimal velocity profile using Dynamic Programming

This question has been asked on scicomp but I thought maybe it's more a mathematical problem of how Bellman's idea is to be applied here. The main problem for me is: How to introduce the time ...
2
votes
0answers
11 views

Plot implicit equation in sub-quadratic time complexity

It is fairly straightforward to plot an explicit equation such as $y=x^3+3x^2+2x+5$ in linear time, because you can just iterate through all $x$ in your graphing space and use the equation to ...
2
votes
1answer
81 views

Find maximum height of smallest flower

Little beaver planted n flowers in a row on his windowsill and started waiting for them to grow. However, after some time the beaver noticed that the flowers stopped growing.So he decided to come up ...
2
votes
1answer
29 views

Recurrence relation from code

My Friends, Hi, I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code: ...
-2
votes
0answers
47 views

Count Triangular Triplets [on hold]

Given a range [L,R] we need to calculate numbers of such triplets [A,B,K] which follows A+B=K where A,B are any two triangular numbers and K must be in an ...
0
votes
1answer
49 views

Find solutions to given equation

Find all integer solutions $x$ for $0 < x < 10^9$ of the equation: $$x=b\cdot s(x)^a+c,$$ where $a$, $b$, $c$ are some predetermined constant values and function $s(x)$ determines the sum of ...
7
votes
1answer
3k views

When does a Square Matrix have an LU Decomposition?

When can we split a square matrix (rows = columns) into it’s LU decomposition? The LUP (LU Decomposition with pivoting) always exists; however, a true LU decomposition does not always exist. How do ...
0
votes
0answers
49 views

Maximise destruction of states

Given a map of 10 states : Every state has a missile launcher and a single missile. The missiles are designed such that they can travel only on a straight line path and can target only a state at ...
8
votes
2answers
157 views

Numbering edges of a cube from 1 to 12 such that sum of edges on any face is equal

Assign one number from 1 to 12 to each edge of a cube (without repetition) such that the sum of the numbers assigned to the edges of any face of the cube is the same. I tried a bunch of equations but ...
0
votes
1answer
240 views

Working algorithm for testing two rectangles for overlapping in Earth GPS coordinates plain

Here is a seemingly simple, but actually quite tricky problem: I am trying to figure out the correct algorithm to test intersection/overlapping of two rectangles, which are plotted on the Earth's ...