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

How many arithematic operations(flops) are to $n×(n+1)$ matrix of system?

Source: Linear Algebra and Its Applications David C. Lay A system of n equations in n unknows correspond to $n×(n+1)$ augmented matrix. One book says the reduction(elimination) to echelon form ...
1
vote
1answer
28 views

Generate all N-bit numbers in such an order that the number of 1s increases monotonically

For a given positive integer $N$, is there an efficient algorithm to generate all $N$-bit numbers in such an order that the number of 1s in the binary representation increases monotonically?
0
votes
0answers
119 views

Binary counting problems

Recall that counting from 1 to n in binary takes $\Theta$(n) steps; i.e., the increment operation has constant amortized cost as opposed to $\Theta$(logn) in the worst-case. a) Analyze the amortized ...
0
votes
0answers
46 views

Good books on Algorithms for a math major without any programming experience?

I couldn't find this question anywhere else so it may not be apt. I am an undergraduate mathematics major and during my discrete math class I really enjoyed the study of algorithms and recursive ...
4
votes
3answers
60 views

Minimum number of steps required to visit every corner of a rectangular grid

I am stucked at this problem: Suppose we have the following grid configuration (or matrix) $G\in \Bbb{M}^{\{0,x,y\}}_{m\times n}$ (I.e $G$ is a matrix that have $m$ rows and $n$ colums over the ...
0
votes
1answer
17 views

Branching/layered optimisation - how?

Imagine you had a collection of systems each with their own constraints and objective functions to optimise (likely similar in form to each other), these then collectively aggregated into a ...
3
votes
0answers
33 views

Is math recursive or iterative?

Is the process of solving a mathematical problem (algebraic equations, limits, derivatives, integrals, EDOs, trigonometric identities proof) recursive or iterative? For example, for solving $x=1+2+3$ ...
1
vote
0answers
37 views

Is there any online Huffman code/decoder?

I need to see and work with Huffman code and see how does it compress data. Anyone has any link of online Huffman coder and decoder (compressor)?
0
votes
0answers
15 views

Exact line Search in Steepest descent

I wanted to clarify the idea of the exact line search in steepest descent method. An exact line search involves starting with a relatively large step size ($\alpha$) for movement along the search ...
0
votes
0answers
34 views

Is there any two way algorithm for compressing numbers?

I have this question that is there any way we can convert a number to another number with less character in the new number? For example, Imagine we have 811008 and if we divide this 13 times by 2, we ...
3
votes
2answers
25 views

Minimal Subset that sums up to

Let $X \subsetneq \mathbb{N}$ be a finite set, and $c \in \mathbb{N}$ we are looking for a subset $$ Y \subseteq X $$ such that $\sum_{y \in Y} y \geq c$. Assuming a subset that satisfies the ...
0
votes
0answers
13 views

3SUM problem solution on the basis of cubic function and a line?

The 3SUM problem formulation: in a given set of n real numbers find 3 elements that sum to specified value S. I am trying to understand mathematical solution of the 3SUM problem based on a polynomial ...
1
vote
1answer
22 views

Time Complexity of DFS

My understanding is that: 1) given a graph G with n vertices and m edges, DFS is O(n + m) 2) DFS can be used to produce a list of all simple paths between 2 vertices u and v This would mean that ...
0
votes
0answers
11 views

Does ray tracing have any speed ups in algorithm running time in the frequency domain?

Could ray tracing be Fourier-transformed so that all calculations are done in the frequency domain? I think ray-tracing a set of rays $S$ from the eye into the view frustum might be more efficient ...
3
votes
1answer
28 views

Re-Balancing Bins with Capacity Limit Problem

Let $\hat n = \{1, \dots, n\}$. Assume that we have a sequence of bins $$ B_1, B_2 ..., B_n $$ which all have the same capacity limit $c \in \mathbb{Q}$. Now, there is a finite set of items $I ...
2
votes
1answer
55 views

A smart algorithm to decide whether a simple graph is 2-regular

Given a simple graph $(V,E)$, is there a smart algorithm to decide if the graph is 2-regular? Is it really necessary to check that all nodes in the graph appears exactly twice? I have implemented ...
3
votes
5answers
79 views

Tricky Nested Summation

I am trying to analyze a programming algorithm that has three nested loops. The algorithm looks like this: $$\sum_{i=0}^{n} \sum_{j=i}^{n}\sum_{k=i}^{j} 1$$. I am trying to simplify it. These are the ...
1
vote
1answer
49 views

Subsequence occurring exactly twice in pattern

Given a string $S$, consisting of letters from the set $\{0, 1\}$. We need to find a string $T$ that appears in $S$ as a subsequence exactly twice. How to tackle this problem, without enumerating all ...
10
votes
3answers
205 views

What is the most efficient algorithm for factorisation when an approximate value of one factor is known

If I am given the following number: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350 692006139 And am told that one of ...
2
votes
1answer
57 views

From currency conversions to graph modeling

The problem I am trying to solve the following programming problem (in C++). I have tried to solve it thoughtlessly just typing code and observing what happens, but, as expected, I have reached ...
0
votes
0answers
14 views

Why does knuth mastermind algorithm favour guesses in S?

From wikipedia : Mastermind > algorithms: From the set of guesses with the maximum score select one as the next guess, choosing a member of S whenever possible. I understand that the hidden ...
1
vote
1answer
24 views

How to prove $2^{\sqrt{f(n)}} \in O\ (2^{f(n)})$ if $f:\Bbb{N}\rightarrow \Bbb{R^+}$?

How to prove $2^{\sqrt{f(n)}} \in O\ (2^{f(n)})$ if $f:\Bbb{N}\rightarrow \Bbb{R^+}$? So we want to prove $\exists c\in\Bbb{R^+}:\ [\exists B\in\Bbb{N}:[\ \forall n\in\Bbb{N}:\ n\ge B\rightarrow ...
0
votes
0answers
6 views

Non-monotone Submodular Maximization with Cardinality Constraints

Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or unbounded below? Fact 1: For monotone submodular functions, Nemhauser, ...
0
votes
0answers
16 views

Contour and perimeter recognition in binary image

I need to detect contour (object) and find the perimeter of a detected object. For example, I have the following image: http://i.stack.imgur.com/40TTX.png All images are binary, so they consist of ...
0
votes
2answers
34 views

How to prove $\frac15 n^2-42n-8\in Ω(n^2)$?

Here is my procedure: So we want to prove $\exists c\in\Bbb{R^+}:\ [\exists B\in\Bbb{N}:[\ \forall n\in\Bbb{N}:\ n\ge B\rightarrow \frac15 n^2-42n-8\ge cn^2]]$ Taking $B=1$. We have $\frac15 ...
0
votes
1answer
26 views

Replacing inequality with equality.

Rate of Convergence: Definition Let $\{x_n\}_{n\ge 0}$ is a sequence that converges to a number $x*$. Suppose that $\{a_n\}_{n\ge 0}$ is another sequence known to converge to $0$. We say ...
0
votes
1answer
23 views

Bipartite graph G(U,V,E) with directed edges from U to V only

I wonder if in the graph theory community or in any other subfield there is a name for a bipartite graph $G(U,V,E)$ with the property of having all edges $(i,j)\in E$ such that $i\in U$ and $j\in V$. ...
1
vote
1answer
31 views

A DE shaw interview question on calculating previous k-average

Given a number flow $a_1, a_2, ... a_N$, $N$ is a large number for example $N = 1000$, the goal is to calculate the average value of previous $n$. For example, now we are at state $k$, then if $n = ...
1
vote
0answers
32 views

Can Levenberg-Marquardt be used to find a local minimum of a function?

I've already implement an algorithm using Gradient Descent (GD) for converging to a local minimum of a function. For example the function is (using MATLAB - a=3 b=3 at this example): ...
0
votes
1answer
15 views

lower bound for an integer inequality in randomized 3SAT proof

I'm having trouble seeing why an inequality holds in a section of a proof for solving MAX-3SAT by a randomized algorithm. So given non-negative integer $k$, we define non negative integer $k'$ to be ...
1
vote
1answer
39 views

Measuring Sets Intersection

I need a fitness function saying how well Interval B fits inside Interval A. Both intervals are ordered continuous numbers going from Interval_Start to Interval_End, for example [1..100] or [1..55]. ...
0
votes
0answers
17 views

What is the difference between these two coin changing problems? (Greedy and Dynamic Programming way)

I have been reading about Dynamic Programming, and I found out about the change making problem. When there is a given set of coins with different denominations but unlimited amount of each and we want ...
2
votes
1answer
52 views

How can I get better at algorithmic thinking?

I have been practising for a an upcoming algorithmic thinking competition but have always found that when doing the past papers, I have never had enough time left to finish. I can do basically all of ...
0
votes
1answer
41 views

Problem with summations for sorting algorithm?

According to this lecture http://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/10/Small10.pdf, slide 26, the expected number of comparisons done by quicksort is smaller or equal to ...
0
votes
0answers
22 views

Parallel finding maximum matching in bipartite graph

I try to research the following theme - finding maximum matching in bipartite graph. Now I researched some algorithms for finding maximum matching in bipartite graph, but all of algorithms which I ...
-1
votes
1answer
34 views

Prime checking algorithm [closed]

What should the algorithm for checking prime numbers be? I have one: Read a number Initialize division Check for divisibility by 2 and 3 If true, declare prime, otherwise not a prime Please tell ...
0
votes
1answer
50 views

In a box there are $R$ red pens and $B$ blue pens. What is the probability that you need to pick up a pen $3$ times?

In a box there are $R$ red pens and $B$ blue pens. Pens are randomly selected, one at a time, until a red one is obtained. Assume that each selected pen is replaced before the next one is drawn. (a) ...
1
vote
1answer
6 views

Encoding Bipartite Matching as a special case of Independent Set

Given a bipartite graph $G' = (V', E')$, the objects being chosen are edges, and the conflicts arise between two edges that share an end. (These, indeed, are the pairs of edges that cannot belong ...
1
vote
2answers
28 views

Big-O proof of inclusion

I'm working on this proof of inclusion:$$\log_2(8^n)\in{\mathcal O(n)}$$ $$\log_28^n-cn\leq0$$ for all $n>n_0$. Is there a log rule that I can use to further simplify before I plug random values to ...
2
votes
1answer
46 views

Alice and bob xor nim game

Alice and Bob are playing a game. The rules of this game are as follows: Initially, there are $N$ piles of stones, numbered $1$ through $N$. The i-th pile contains $A[i]$ stones. The players take ...
1
vote
1answer
21 views

Smallest number of groups to sniff

The question given: The sniffer dog at the airport stops beside a trolley piled high with 60 suitcases. One of the suitcases contains contraband peanuts. The dog can tell whether peanuts are hidden in ...
6
votes
3answers
123 views

How do Gap generate the elements in permutation groups?

I understand that permutationgroups in Gap are represented by generators, which seems to be far more efficient than groups represented by all it's elements, but how could then for example ...
2
votes
3answers
39 views

Mapping all numbers in a set to a particular number

This is not homework, I am a programmer and I encountered this problem in the implementation of an algorithm of mine. I was wondering if the following can be done without the use of any auxiliary ...
0
votes
1answer
50 views

Recursive approach for computing $(a,b) \mapsto a^b$

As a programming exercise I was asked to implement a recursive approach for computing $a^b$ given two real $a,b \in \mathbb R, a>0$. I assume this task has a typo, as a recursive approach makes ...
2
votes
1answer
40 views

Constructing every spanning tree from addition and deletion of edges

Let $G = (V,E)$ be given (note that this is not necessarily simple), and consider the set of every spanning tree of $G$, $S$. Choose any $G_a, G_b \in S$. Is it possible to construct $G_b$ from $G_a$ ...
0
votes
0answers
28 views

Division by power of 3.

Is there any fast division algorithm to divide a binary number by power of $3$. I want to find the $q,r$ for $a=q*3^b+r$, $b$ is constant.
2
votes
0answers
20 views

How to construct a polyhedron from given planes

This seems to be a basic questions, but I really don't know a good computer algorithm to do this. I have a set of planes (parameterized by normal direction and distance from a given point), and I want ...
3
votes
2answers
97 views

Why is the Leibniz method for approximating pi so inefficient

I've been playing around with algorithms for computing pi. One that I noticed is the leibniz algorithm. It states that pi can be approximated like this $n = 1$ ...
1
vote
1answer
20 views

Couple of questions about a proof of an algorithm

$M$ is a set of men and $W$ is a set of women. ...
-1
votes
0answers
23 views

To find order of an element in group of large size

G be multiplicative group of positive integers less than prime p. a be any arbitrary element of G .Is there any efficient algorithm to find order of a in G?