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

learn more… | top users | synonyms (1)

2
votes
0answers
36 views

How to load warehouse pallets efficiently?

Assume that we would wan't to develop a warehouse management system, which picks up plastick boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height ...
1
vote
1answer
35 views

Digit wise modulo for calculating power function for very very large positive integers

I am writing a code to calculate $P^Q$ where $P$, $Q$ are positive integers which can have number of digits up to $100000$. I want the result as $r = P^Q \pmod{10^9+7}$, where $10^9+7$ is a prime ...
0
votes
1answer
11 views

Converting between rates using a common base rate

If I have a base rate of USD = 1 and know that all conversion rates are in relation to that currency, how would I convert other currencies between each other using that commonality? For instance, I ...
0
votes
0answers
19 views

Is there an algorithm that, given a point cloud, infers an optimal wireframe (surface) structure?

I have a point cloud that I would like to convert to a surface, in the form of a wireframe lattice structure. This means, from a sequence of 3D points (x,y,z), obtaining three 2D matrices X,Y,Z of ...
-1
votes
0answers
98 views

Minimum penalty calculation

Their are N tables in a restaurant.Now customer visit the restaurant and they will be provided seats. Each customer has following properties : The customer don't leave the table unless they are ...
1
vote
2answers
53 views

Proving Hamiltonian Cycle is NP Complete

I'm trying to learn Complexity classes.I want to show Hamiltonian cycle is NP Complete. The text tells me that Inorder to prove NP-Completeness we first show it belongs to NP,by taking a ...
0
votes
2answers
21 views

Converting between exchange rates

Suppose I have a currency exchange rate of 1 USD = 102.642499 JPY. If I had 50 USD and wanted to get the value in JPY using that exchange rate, my equation would be 102.642499 * 50, correct? How ...
4
votes
1answer
54 views

How to check if $\text{position}\left(\frac{a + b} 2\right )$ is in range $\text{position}\left(a\right )$ and $\text{position}\left(b\right )$

Given a permutation of $n$ number $1, 2, 3,\dots,n$. How to check if it is exist $a,\ b$ with the same parity such that $\frac {a + b} 2$ is between $a, b$. How to solve this problem efficiently ? ...
0
votes
1answer
271 views

Select elements from N sets

N sets are given which can have any number of elements from 1-100 each.Now we need to count arrangements in which we select 1 element from each set under the condition that we can not choose same ...
0
votes
0answers
7 views

pick rx unique elements from set of x elements (percolation run time)

I have written a program to run experiments on percolation with a square grid of side $N$. The grid starts with all closed spaces, and spaces are open one at a time until there is an open path from ...
2
votes
1answer
38 views

Why is Doolittle Decomposition Algorithm failing and what should I try next?

I am trying to find the LU Decomposition of the following matrix: So far I have only tried the Doolittle Decomposition algorithm with partial pivoting (it's never failed me before!). As far as I can ...
0
votes
0answers
277 views

Cleaning minimum tables

Moderator Note: This question is part of the Ongoing August Challenge 2014 CodeChef (problem page). This contest ends on 11 August 2014, and this question will remain locked (with current answers ...
4
votes
0answers
305 views

Find if person go through given point

Moderator Note: This question is part of the Ongoing August Challenge 2014 CodeChef (problem page). This contest ends on 11 August 2014, and this question will remain locked (with current answers ...
0
votes
0answers
576 views

Count arrangment such that each person wear different tshirt

Few friends are going to a party. Each person has his own collection of T-Shirts. There are 100 different kind of T-Shirts. Each T-Shirt has a unique id between 1 and 100. No person has two T-Shirts ...
2
votes
1answer
73 views

How can I find the point (X, Y, Z) which minimizes this quantity?

I have a number of equally powerful light sources $L_i, 1 \le i \le N$ at points within a cube $(x_i, y_i, z_i), -1 \le x_i, y_i, z_i \le 1$. The intensity of each light falls off with distance ...
2
votes
1answer
68 views

Finding an $n$ such that $n^2 \equiv -1 \mod p$

What is an efficient algorithm to find the first number $n$ such that $n^2 \equiv -1 \mod p$ for a prime $p$, if such an $n$ exists? Is there anything better than the brute-force approach up to $p-1 ...
2
votes
1answer
44 views

How to measure trajectory regularity?

I have two animal running trajectories. A regular one with repeated back and forth running between point A and B, like the one on top in the figure. The other one is very irregular, animal paused and ...
1
vote
2answers
82 views

How can i find if a given number occurs in a custom Fibonacci sequence?

Its a recent interview question from Amazon. For e.g. let starting numbers be $a$ and $b$, then third number will be $a+b$ and so on: forming recursion like: $F(n)=F(n-1)+F(n-2) , n\ge 2$ $F(1)=a$ ...
1
vote
1answer
48 views
0
votes
0answers
33 views

Number of unique ways to edge-label a complete graph with $k$ distinct labels.

Given $k$ distinct labels, how many unique ways to label the edges of a complete graph with $n$ nodes (nodes are not labeled). For example, to label a complete graph with 3 nodes using 4 distinct ...
1
vote
2answers
35 views

Algorithm of order $O(n)$

Design an $O(n)$ algorithm, that given a real number $x$ and a sorted array $S$ of $n$ numbers, determine whether there exists any two elements in $S$ whose sum is exactly $x$. The solution I have ...
3
votes
2answers
89 views

Fibonaaci Recurrence

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities Given Data in question ...
0
votes
0answers
39 views

sorting young's tableau better than n^3

Young's tableau takes $O(n^3)$ to sort. By sorting I mean sort numbers in existing young's tableau. http://en.wikipedia.org/wiki/Young_tableau Simply it is a matrix sorted by rows and columns. ...
3
votes
2answers
46 views

Largest Equilateral Triangle in a Polygon

Is there an algorithm to determine the largest equilateral triangle in a convex polygon?
1
vote
0answers
58 views

Sparse matrix algorithms involving data-driven or random access / walk

I am looking for some well-known algorithms in which sparse matrix elements are accessed in a non-structured way, i.e. row/column depends on a value of another (sparse) matrix/vector element or some ...
0
votes
0answers
24 views

Solving a simple Recurrence in summation form(very special case)

I have a bit confusing recursion form $\sum_{n=2}^{\infty}\{f(n)\frac{n}{n-1}\}=C, \tag 1$ $f(0)=b,f(1)= a,f(2)=c$ and $C$ are constants. Could you help me to solve this recursion or help me to ...
1
vote
0answers
50 views

Solving the recursion $F(n)=K_0F(n-1)/(n-1)+K_1F(n-2)/(n-2)$

Please help me in solving the recursion $F(n)=K_0\frac{F(n-1)}{n-1}+K_1\frac{F(n-2)}{n-2}$, preferably using power series for the values of $F(n)$ in terms of $n$. Here $K_1$ and $K_2$ are ...
5
votes
3answers
364 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
2
votes
2answers
128 views

Fast way to find the sum of LCM of the given range of numbers?

I want to find the sum of LCM of a given range of integers. For example: Input: $5$ Output: \begin{align} \sum_{i=1}^5 \mathrm{LCM}(i,5) & = \mathrm{LCM}(1,5) +\mathrm{LCM}(2,5) ...
1
vote
0answers
35 views

Maximal flow in flow-networks

I want to do the task (b),(c) and (d)in the picture above. I have done (b) correctly. For (c) I only found one (s-t) augmenting path, namely (s,1),(1,3),(3,2),(2,4),(4,t) and I only can push one ...
0
votes
2answers
21 views

$O(n \log k)$ for merging of $k$ lists with total of $n$ elements

Is it possible to merge $K$ sorted list into one sorted list where n is the total number of elements in all the input lists in $O(n \log k)$ time? What I tried to do is, taking the list, and adding ...
0
votes
0answers
46 views

Miscellaneous questions about trees

I want to know which of the following claims are true: 1) Let T be a minimal spanning tree in G for a weight function w. Then T is also a minimal spanning tree for the weight function obtained from w ...
0
votes
1answer
20 views

Proof about spanning tress in graphs

Let $G=(V,E)$ be a graph and $T_i=(V,F_i),i=1,2$ two disjoint spanning trees in $G$. Let $f_1 \in F_1$. Prove that there is $f_2\in F_2 $ such that $T:=T_1-f_1+f_2$ is a spanning tree.
2
votes
1answer
20 views

How to efficiently compute the pareto front in a >2 dimensional multi-objective case?

I'm currently working on an optimization problem with 4 different objective functions and need an algorithm to compute the pareto frontier from several "solutions" to that problem. I already found ...
7
votes
3answers
227 views

Solving recurrence relation: Product form

Please help in finding the solution of this recursion. $$f(n)=\frac{f(n-1) \cdot f(n-2)}{n},$$ where $ f(1)=1$ and $f(2)=2$.
1
vote
1answer
134 views

Tree Traversal - Simple Puzzle type Issue.

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
0
votes
3answers
25 views

A property regarding intervals

While I was solving a problem on TopCoder I used the following assumption. I have n intervals: $ [a_1,b_1], [a_2,b_2],...,[a_n,b_n]$ and a number $T$ such that: $$ a_1 + a_2 + ... + a_n \leq T \leq ...
1
vote
1answer
38 views

How Jaccard similarity can be approximated with minhash similarity?

In Page 81 of this book, Mining of Massive Data Sets. It says the following: Now, consider the probability that h(S1) = h(S2). If we imagine the rows permuted randomly, and we proceed from the top, ...
0
votes
0answers
6 views

SPSA loss function

I need a simple implementation (in Matlab) of the most basic SPSA algorithm for a friend of mine. I have found this code from J.C. Spall but I don't know where to find an implementation of an ...
1
vote
1answer
70 views

Find the pair of values $a[i]$, $a[j]$ such that $a[i]\,\&\,a[j]$ is maximum

Given a list of positive integers, find the largest possible value of $a[i]$ $\&$ $a[j]$, where $i$, $j$ are indices of the list. $ i\ne j $, $a[i]\,\&\,a[j]$ is bitwise AND of $a[i]$ and ...
-1
votes
0answers
53 views

Maximise and operation [duplicate]

Given an array of $n$ non-negative integers $A_1, A_2, \dots, A_N$, find a pair of integers $A_u$, $A_v$, where $1 \leq u < v \leq N$, such that the bitwise-and ($A_u$ and $A_v$) is as large as ...
2
votes
1answer
51 views

Why is the sentence true?

I am looking at the algorithm of the insertion sort: ...
0
votes
1answer
43 views

Best approach or algorithm to solve equation with multiple variables?

I have an equation : $A^6x_1 + A^5x_2 + A^4x_3 + A^3x_4 + A^2x_5 + A^1x_6 + x_7 = B$ What can be the best algorithm/approach I can use to crack this? $A$ and $B$ are constants. $x_1,x_2...x_7$ are ...
0
votes
0answers
21 views

How does inserting N objects one at a time into an ordered AVL tree yield an efficient sorting algorithim

If we assume reblalancing an AVL tree of height n after an insertion or deletion takes O(n) operations. How does inserting N objects one at a time into an ordered AVL tree yield an efficient sorting ...
1
vote
0answers
29 views

Lowest sum of 2 sets of number pairs

I am given a set of unique integers $n$. I need to compute the smallest sum $s$ such that there are two different pairs of integers $(x1, x2)$ and $(y1, y2)$ where $x1 < x2$ and $y1 < y2$ and ...
1
vote
0answers
40 views

Finding whether a sum of numbers in a set generate another number

I have a set of numbers {a1....an} and another number k. I need to find whether sum of any combination of numbers in the set ...
2
votes
2answers
33 views

Flip cards to get maximum sum

Given N cards where if ith card has number x on its front side then it will have -x on back side and a single operation that can be done only once that is to flip any number of cards in consecutive ...
1
vote
1answer
41 views

Find extra work done by Bob

Alice has challenegd Bob game of N puzzle.N puzzle is played on N*N grid with each cell containing distinct numbered tile from 1 to N*N-1 Except one which is empty cell and represented as 0. Move ...
0
votes
0answers
24 views

Strassens Matrix Multiplication Algorithm to compute product of 2 4X4 Matrices

Im trying to learn starssens matrix multiplication Algorithm.So far i know that it uses 7 multiplications and replaces a multiplication by several additions and subtractions,to achieve better ...
0
votes
2answers
22 views

Algorithm to find all possible base26 numbers of a 32-bit cropped value

I have following formula: base26value = 26(26(26(26(26(26a + b) + c) + d) + e) + f) + g The variables a..g have a range ...