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

Amortized Analysis Problem

I need to find the cost of the problem below but I cannot find a pattern to find the total cost. Problem: The cost of multiplication of n-bit binary number by 2. If a bit changes the cost of that ...
2
votes
0answers
36 views

Upper limit for adding N numbers in grid of N processors in parallel

We must show how N binary numbers, each consisting of N bits each, can be added in a linear grid of N+logN processors. Suppose that the binary digits can be inserted directly in each processor of the ...
0
votes
3answers
43 views

Algorithm - if known $x$ and $y$ value

I am new to this site, so please bear with my bad question-writing skills! I was given a puzzle, in which I have to work the algorithm being used to generate the $y$ value from the $x$ value. Here ...
0
votes
0answers
20 views

finding the least non-zero of a multivariable polynomial

Let $P(x_1,x_2,...,x_m)$ be a homogeneous polynomial of degree n, with integers coefficients. How can you find the least* $a=(a_1,a_2,...,a_m)$, where $a_i$ are positive integers and $P(a)!\neq 0$? ...
0
votes
0answers
44 views

Todd-Coxeter algorithm: coincidences

I'm trying to understand the Todd-Coxeter algorithm with the help of a multiplication and relator table, but there is one thing about coincidences that is not really clear. For some small groups (for ...
1
vote
0answers
16 views

Divisibility via Inclusion-Exclusion

Let $N$ be a large natural number, let $A$ be a subset of naturals, and ask: How many numbers $n\leq N$ are divisible by one or more numbers in $A$. This is a classical application of the ...
0
votes
0answers
43 views

How can nested for-loops be expressed in mathematical notation?

Apologies if this is an obvious question; I'm not very familiar with mathematical notation for algorithms. I was coding a solution for Project Euler #4, and I came up with an interesting way of ...
0
votes
0answers
19 views

How to test for a polygon witn n vertices if it's nonintersecting polygon or not?

How can you design an algorithm to know if an n-vertex polygon nonintersecting ? On what criteria is the test going to be
0
votes
0answers
49 views

Max-Flow Algorithm construction

I am trying to solve an algorithm that requires a reduction to max-flow by constructing the appropriate flow-network and finding the max-flow, but I am having trouble making the jump to the ...
0
votes
1answer
83 views

Find all subsets whose sum modulo a value is 0.

How can we find the count of number of subsets of a given set (e.g. {1,7,4,90,23} ) whose sum is a multiple of a given value A. One method which I know of is to store all subset sums modulo A and ...
0
votes
2answers
29 views

What can be observed by evaluating a polynomial at roots of order greater than the polynomial itself?

I have been reading through an algorithms book on the use of FFT for large number multiplication. An example it used to emphasize a point was: Evaluate the following polynomial at all roots of unity ...
1
vote
1answer
37 views

Minimum Cut algorithm on undirected graph with no source or sink

When dealing with Minimum Cuts, what do you do when you are given an undirected graph without edge weights and no source and sink node? How do you modify the graph so that it can be used with ...
1
vote
3answers
87 views

How to choose the starting point in Newton's method?

How to choose the starting point in Newton's method ? If $p(x)=x^3-11x^2+32x-22$ We only learnt that the algorithm $x_{n+1}:=x_n-\frac{f(x_n)}{f'(x_n)}$ converges only in some ...
0
votes
0answers
25 views

Euclidean algorithm to find GCD

I have to find GCD(975, 442) using Euclidean algorithm and write it in like: $ax + by$. Please tell me what do i do wrong. ...
0
votes
3answers
28 views

How do you solve a equation by converting to logarithm form for the problem$3e^{x-4} +2=83$?

$3e^{x-4} +2=83$ I understand converting logarithms but i dont understand how to convert e into log form and solve. help would be deeply appreciated.
1
vote
0answers
25 views

Decentralized Algorithm for a one dimensional ring

I'm working on a homework in which a graph of n nodes is arranged as a one-dimensional ring and every node has 3 out-going edges. I need some help in proving that any decentralized algorithm would ...
1
vote
1answer
20 views

Matlab create matrix without loops

I'm trying to create a Matrix in Matlab, which is dependent on 2 control variables $i$ and $n$. They are defined like this: $i=1:10$, $n=0:N-1$. Now I'm trying to define a matrix, where an entry is: ...
0
votes
1answer
35 views

Reversing $\sum_0^kx\cdot2^i$

I'm trying to write an algorithm, and the easiest way I found for explaining the mathematical problem I'm facing is the following: Assume you have $x$ US dollars and you're gambling on a roulette. ...
0
votes
0answers
37 views

How to solve Flowchart logical reasoning questions?

I came across these crazy flow chart questions : You are given a table with 13 values, followed by a series of steps (say 8), some steps have yes or no branches as conditions, some just say go to ...
2
votes
2answers
160 views

number of solutions of x*y<N [closed]

How many solutions (unique pairs (x,y) ) exist for equation $xy < N$ ? constraints : $x >1 , y>1 , N<=50000$ I tried following method , but it fails for say N=24 , in which i calculate ...
1
vote
1answer
25 views

Reverse engineering the objective function

If there is a finite iteration algorithm can we find a function that this algorithm optimizes, in hindsight? Edit: Suppose there is a set of functions $f_i(x)$, where $x\in \mathbb R^n$, ...
0
votes
1answer
69 views

Count Integers satisfying the conditions

Given some constraints ,I need to find possible ways that these conditions are satisfied. I need to find four POSITIVE integers a,b,c,d such that ad-bc > 0 and also a+d=N for a given value of N. How ...
1
vote
0answers
25 views

Given a set of generators of a group G, is there a method to find a presentation for G using those generators?

Suppose I have a group $G$, which I know is finitely presentable and infinite. (In particular, I have a presentation for it, though not the one I want). Suppose I have a small list of generators ...
0
votes
1answer
20 views

Tight bound of worst case performance of algorithm

I am trying to find the "tight bound of an algorithm for the worst case run time. I have found that the upper bound of the worst case is O(n), I have also found that the lower bound for the worst case ...
0
votes
1answer
61 views

efficient algorithm to place people in a specific order

You are preparing a banquet where the guests are government officials from many different countries. In order to avoid unnecessary troubles, you are asked to check the list of international conflicts in ...
0
votes
1answer
11 views

Mathematical algorithm to alter values to specific range

I have a scroll bar in a computer program that scrolls from is -1 to 1.Its initial value is 0 .I need it to scroll from 0 to 1 and the initial value to be 0.5 What is the mathematical way to ...
0
votes
0answers
23 views

`x` increases by 10 everytime`y` occurs`i` times. How do I calculate the sum of `i`?

Can anyone tell me how to calculate this? x increases by 10 everytime y occurs i times. How ...
0
votes
0answers
23 views

Can You Figure Out This Spreadsheet Function?

https://docs.google.com/spreadsheet/ccc?key=0AmZYpC5sO3RtdF85UWY0c3J2SE1OQzlRMlNETGs1Mnc&usp=sharing This is a calculator for a game where you can increase your stats by spending your XP points. ...
1
vote
3answers
31 views

How multiple of number is determined?

Problem 5 Project Euler 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. It is suggested in above example that, 2520 is divisible by ...
1
vote
0answers
16 views

Composing permutations in factorial notation

Given two permutations $p_1$ and $p_2$ in factorial notation, is there a direct algorithm which computes their composition directly, i.e. without translating to a different notation or via computing ...
0
votes
0answers
13 views

Matrix Partial Derivative?? NMF Multiplicative update rules

Recently, I read Lee & Seung's work on Nonnegative Matrix Factorization. But I have problem with the update rule: The object function is minimize: $\|V - MH \|$ with respect to M and H, subject ...
-1
votes
0answers
19 views

Google Doc Algorithm To Calculate Incrementing Sum?

Ok I'm trying to calculate the total XP used for each stat but can't seem to figure out the algorithm. Stat Value is editable and changes to calcs in the Next Cost and XP Used. CostX is how much a ...
0
votes
2answers
26 views

Relating number of iterations to n

n = length of list with more than n > 0. index = 0 step = 1 while index < n: index = index + step step = step + 1 return How many times will the loop ...
1
vote
1answer
100 views

Solving the recurrence relation $T(n) = T(n-\sqrt n) + 1$

I have an algorithm that at each step can discard $\lceil\sqrt(n)\rceil$ possibilities at a cost $1$. The solution to the recurrence relation below is related to the question of complexity of such ...
0
votes
1answer
21 views

return a number between 3 to 5 by get a number between 1 until 10000! [closed]

I want to have a math math formulas to do this operation: A:get a number between 1 to 10000 B:reteun a number between 3.00 until 5 for example 3.89 for greater number return greater number too! ...
0
votes
0answers
37 views

Find cardinality of set

I have faced the following problem recently: We have a sequence A of M consecutive integers, beginning at $A_{1} = 1$: $1,2,...M$ (example: $M = 8$ , $A = 1,2,3,4,5,6,7,8$ ) We have the set $T$ ...
0
votes
0answers
21 views

How do I measure the goodness of cosine similarity scores across different vector spaces?

I am a computer scientist working on a problem that requires some statistical measures, though (not being very well versed in statistics) I am not quite sure what statistics to use. Overview: I ...
2
votes
1answer
70 views

Soft Question: Algorithms: Will We (One Day) No Longer Need to Study Algorithms? [closed]

I'm just now getting into the study of algorithms and it seems like as computers get faster and faster the need to study algorithms may begin to diminish. How likely is it that in 50 years there ...
0
votes
0answers
14 views

algorithm for traversing a fractal in a “maximally ordered” way

consider a multidimensional fractal that can be "traversed" in an arbitrary order. is there an algorithm for traversing a fractal in a "maximally ordered" way? in other words the algorithm has ...
1
vote
0answers
33 views

Conjugate Gradient Method Near Exact Line Search

Unlike Newton-type methods, there is no natural step-length value $\alpha _k$ in conjugate gradient methods. Because of this, why do we need to use a near exact line search if we are to expect rapid ...
0
votes
0answers
15 views

NAESAT (Not all equal sat) problem

Given the following NAESAT problem: c3 = {x1,x2}, {x2,x3},{x3,x1} where cn = {x1,x2}, {x2,x3}..{xi,xi+1} What is c4? Well ...
0
votes
1answer
37 views

Checking convergence of an iteration

How to check if an algorithm converges in an interval, for example $x_{k+1}:=\frac{1}{11}(1-\cos(x_k))$ does it converge for any startpoint $x_0\in (-\pi/2,\pi/2)\setminus\{0\}$ ? (as hint: ...
4
votes
1answer
37 views

A game problem- double or increment by 1

Its a two player game. Initially $P=1$, and there is some fixed integer $Q>1$. A valid move consists of either increasing $P$ by $1$ or doubling it iff on doing so $P$ does NOT exceed $Q$.The ...
0
votes
0answers
8 views

Interpolating on the borders of differently-resolved images

I'm creating a three-dimensional model of the earth based on SRTM height data. The data set is pretty huge, so only a small fraction of the data is available at any given time. The height data is ...
0
votes
1answer
26 views

Repetitive Multiplication/Division

I have a number x = 10000 (for example), I want to divide it by a number y = 1.2 (for example) continuously until the result is equal or less than 1. for example: ...
0
votes
0answers
12 views

Writing a proof that a certain algorithm generates the correct transition matrix for a quantum walk?

Regarding quantum walks, I have a transition matrix $M$ and a particle vector $P$ and I have determined that the elements of $M$ have to be positioned in a certain way so that the position of the ...
0
votes
1answer
26 views

Is there a formula for finding the lowest common factor

Us there an formula/algorithm for finding the lowest/least common factor/denominator (other than one) of two numbers? Thanks!
0
votes
1answer
27 views

Is there a formula for finding the lowest factor of a number

Is there a simple formula/algorithm to find the lowest factor of a number other than one? Thanks!
1
vote
0answers
42 views

Secant method in Matlab

I have done following, but I don't know how to put that function into this: ...
3
votes
1answer
108 views

Minimizing Height of a Table

This optimization question popped into my mind while working with latex tables: Suppose we have a table with $m$ rows and $n$ columns, and for each $1\le i\le m,1\le j\le n$ we are given $T(i,j)$ ...