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
19 views

Details of the Goldberg-Radzik algorithm for computing shortest paths

I'm trying to implement the Goldberg-Radzik algorithm, which is described in the 1993 paper "A heuristic improvement of the Bellman-Ford algorithm" by Andrew Goldberg and Tomasz Radzik (link: ...
-1
votes
0answers
80 views

Making Y chocolates from X chocolates [on hold]

**Moderator's Note: This is a live contest problem from CodeChef. Per usual protocol this question is locked until end of contest period. A mall has N chocolate multiplier machine numbered as 1, ...
-1
votes
0answers
86 views

Check if questions can be assigned to students [on hold]

Moderator Note: This is a current contest question on codechef.com. An exam is to be conducted. N students will give the exam. Students are numbered as 1, 2, 3 . . N. There are M questions and ...
4
votes
1answer
43 views

Hashing With Chaining Collision

We have $1000$ elements with key=1 to 1000, and a hashing function $$ h(i)=i^3 \mbox{ mod } 10 $$ for an array with length $10$ (array index from $0$ to $9$) with chaining method. What is the ...
2
votes
1answer
107 views

Water Box with n Liter

I ran into a basic challenging problem. I see an high school local math Olympiad question. we have a box that keep n Liter water. each time we extract 1/k Water from box. how many times (minimum) we ...
-1
votes
0answers
34 views

Total ways to complete the ladder game [on hold]

In a game, we have to climb up the ladder of height h, using only odd number of steps. But we don't progress to the next level unless you climb down as well..!!! For example: If we have a ladder of ...
2
votes
1answer
50 views

Count ways to make total coin value [on hold]

For any non-negative integer K, suppose we have exactly two coins of value 2^K (i.e., two to the power of K). Now we are given a long N. We need to find the number of different ways we can represent ...
2
votes
1answer
48 views

decomposition into three squares

Doing a coding assignment. And it's basically having a user enter $n$. Then I need to provide (If it exists) $$n = x^2 + y^2 + z^2.$$ Not really sure how to approach this. Any ideas?
-2
votes
1answer
32 views

Finding if it is possible to protect all suburbs [on hold]

Bob lives in a city that is circular in shape on a 2D plane. The city center is located at origin (0,0) and it has suburbs lying on the lattice points (points with integer coordinates). The city ...
1
vote
0answers
21 views

How to Prove an Algorithm is $O(n \log n)$ Using Substitution Method and a Change of Variable?

Consider the following: Show that $T(n) = 2T(\left \lfloor n/2 \right \rfloor + 17) + n$ is $O(n\log n)$. Here is what I have come up with: Restrict the domain of $n$ to $n \geq 1$ and define ...
-2
votes
0answers
73 views

Place two Bishops on chessboard [on hold]

Given a $ n \times n $ chessboard. Each cell of the chessboard has a number written on it. Bob wants to place two bishops on the chessboard in such a way that there is no cell that is attacked by both ...
0
votes
0answers
17 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
22 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
33 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
81 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 ...
2
votes
0answers
46 views

Minimise total cost and count ways [on hold]

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 ...
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 ...
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 ...
4
votes
3answers
92 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
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
22 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})$?
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 ...
0
votes
1answer
22 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 ...
1
vote
1answer
48 views

Finding Kth string by applying given operations [on hold]

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
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 ...
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 ...
3
votes
1answer
87 views

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 ...
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 ...
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
27 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} ...
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
58 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
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 ...
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
1answer
78 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
12 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
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: ...
-1
votes
0answers
57 views

Maximise destruction of states [on hold]

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
164 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 ...
1
vote
1answer
31 views

can dijkstra's algorithm be applied as it is for undirected graph

I am wondering why can't Dijkstra's algorithm be applied as it is for undirected graphs. I mean instead of adding 2 directed edges to make it equivalent to a directed graph , why wouldn't it work if ...
0
votes
1answer
74 views

Subtraction game between alice and bob

Alice and Bob decide to play a number game. Both play alternately, Alice playing the first move. In each of their moves, they can subtract a maximum of k and a minimun of 1 from n ( ie.each of them ...
0
votes
1answer
27 views

Algorithms to increase or decrease the contrast of an image

While tinkering with image editing, I thought I might implement a contrast algorithm; something that would take a range of values and, based on the value that the user provides (from 0 to 255; the ...
0
votes
0answers
31 views

What would be the way to learn algorithms?

I want to know the mathematical theory associated algorithms. Story with a base of calculation, analytical geometry and linear algebra. What would be the previous topics to begin the study of ...
1
vote
2answers
45 views

Solving a recurrence relation with square root

I ran into a bad recurrence relation. Anyone would calculate T(n) or add some hint? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 }\\ \sqrt{1/2[T^2(n-1)+T^2(n-2)]+}n ,\quad ...
2
votes
1answer
47 views

Height of Recursion Tree for $T(n, k) = T(n/2, k) + T(n, k/4) + kn$

If we use a recursion tree for solving $$\begin{cases} T(*,1)=T(1,*)=a \\ T(n,k)=T(n/2,k)+T(n,k/4)+kn \end{cases}$$ What is the height of the recursion tree? Any idea or solution highly ...
1
vote
0answers
17 views

Math Algorithm Help Needed with Aggregated Percentages (Business Metaphor)

I'm trying to figure out a math algorithm, but I'm having a hard time wrapping my head around the best way. Instead of defining a complex industry-specific process, I'll use a crazy metaphor here ...
-2
votes
0answers
10 views

Exchanging numerical data to percentages

I have a large amount of data that are all positive numbers that i am plotting, however, as apposed to using numbers, which lack relative significance, I was looking to find an algorithm that would ...
0
votes
1answer
18 views

Approximate non-Lipschitz (but continuous) functions by Lipschitz functions

Is there any algorithm to approximate non-Lipschitz (but continuous) functions by Lipschitz functions ?