Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (comptutational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

0
votes
0answers
18 views

Proving regular languages over an alphabet

Language L over alphabet Σ THREE(L) = {abc | a,b,c ∈ Σ and ∃x ∈ Σ∗ s.t. abcx ∈ L} and every String in THREE(L) is exactly 3 characters long I am not sure how to prove that L whenever L is a regular ...
2
votes
1answer
25 views

confudes with Dijkstra's algorithm.

I have tried to understand the question but I got really confused. So starting from node 3, the distance to other nodes are 3 to 1 = 3 3 to 2 = 1 3 to 4 = 4 3 to 5 = 2 3 to 6 = 3 3 to 7 = 2 ...
0
votes
0answers
25 views

How to solve recurrence relation $T(n)=2T(n/2)+4^n$ using characteristic equation method?

With change of variables $n = 2^k$ We get $$T(2^k) = 2T(2^{k-1}) + 4^{2^k}$$ which yields $$S(k) = 2S(k-1) + 4^{2^k}$$ I cannot go further. Here: ...
1
vote
1answer
51 views

Tower of Hanoi Algorithm

I read many articles about the "Towers of Hanoi" algorithm, but i couldn't see any relation to computer science or something else? Is it used somewhere to describe a special problem?
0
votes
0answers
39 views

Finding value of given function with mod M

I want to calculate value of $F(N) = (F(N-1) * (N-R+1)^{(N-R+1)}/R^R)$ % M for given values of N,R and M. Here M need not to be prime. How to approach this question? Please help because if M was ...
0
votes
0answers
61 views

Finding the initial permutation

Assume a permutation P[1], P[2], ..., P[n]. Now we have made N permutations Q[1], Q[2], ..., Q[N], Q[i] is permutation P without element i (we subtract 1 from all elements bigger than i). For ...
1
vote
3answers
16 views

running time of an algorithm

I am trying to prove an algorithm with input size $n$ satisties the recurence relation (for $n>=1$) $T(n) = T(n-1)+n$ and an initial condition of $T(1)=1$ has running time in $Θ(n^2$). By using ...
1
vote
1answer
50 views

Analyzing runtime of a nested for loop

// assume n is a power of 5 for (int i=1; i<n; i=i*5) for (j=i; j<n; j++) sum = i+j; I am supposed to find out how many times each line of code ...
1
vote
0answers
7 views

How to calculate the maximal error of a solution of a physical problem found numerically?

Assume we throw a body from a height h with the velocity v0 in some arbitrary direction. Beside the weight ...
2
votes
3answers
31 views

Time spent to sort $10^7$ records with insertion sort

I am stuck with my revision for the upcoming test. The question asks" An implementation of insertion sort spent 1 second to sort a list of ${10^6}$ records. How many seconds it will spend to sort ...
0
votes
3answers
61 views

Is there any simple algorithm which can tell if a string is a repeat of its substring?

Is there any simple algorithm which can tell if a string is a repeat of its substring? For example, $1212121212$ is a repeat of $12$, $135746135746$ is a repeat of $135746$.
0
votes
0answers
28 views

Show that this algorithm provides a matching of at least this size?

Consider the 'greedy' algorithm for finding a matching on a graph G. First pick an edge xy, add this edge to the matching then delete both x and y from the graph and continue. Suppose that $e(g)\geq ...
0
votes
0answers
76 views

Prove that whenever L is a regular language so is HasPrefix(L)

For a language $L$ over an alphabet $\Sigma$, define the language $\operatorname{HasPrefix}(L)$ as follows: $$\operatorname{HasPrefix}(L) = \{xy\mid x,y \in\Sigma^*, x \in L, xy \in L, |y|> 0\}$$ ...
1
vote
1answer
37 views

Minimum number of steps to reach a position

I am on a infinite length number line, Currently at position zero. Each step I can only take R units to right and L units to ...
0
votes
0answers
24 views

How to find a legal flow in a network with upper and lower bounds?

I am trying to understand Ford-Fulkerson algorithm. How can I use Ford-Fulkerson algorithm to find legal flow and NOT MAX flow.
0
votes
0answers
12 views

Bluestein algorithm for 2-D implementation

I wished to know that while finding the DFT using Bluestein algo for 1-D array we express it as a convolution of two series, so can we analogously say that for the DFT of a 2-D array, the Bluestein ...
0
votes
1answer
24 views

How to determine if a vector belongs to the conical hull of a set of vectors?

Let $\mathbf{p}_i$ be a finite set of finite-dimensional real vectors with non-negative components with the property that, for any $k$, $\mathbf{p}_k$ cannot be expressed as a linear combination with ...
1
vote
1answer
33 views

dijkstra's algorithm in time O(k|V|+|E|)

Can somebody can help me with this problem: I have to calculate the minimum distance from a source node $s$ for undirected and connected graphs $G = ( V, E)$ with weights on the arcs belonging to the ...
0
votes
1answer
26 views

What algorithm to solve this integral similar to a normal CDF numerically?

I'm looking to solve this integral numerically. It is a bit similar to a normal CDF. z and tau are deterministic. What kind of algorithm may do the job, ideally to be coded in C/C++? I'm ...
1
vote
1answer
79 views

Three dynamic programming techniques

I've noticed three terms that come up when I look at dynamic programming exercises. Binary choice - seen it in a weighted interval scheduling problem. Multiway choice - seen in a segmented least ...
4
votes
1answer
68 views

Checking whether a line segment is above another in $\mathbb{R}^3$

There are two non parallel line segments $U$ and $V$ in $\mathbb{R}^3$, each given by their two end points $u_0, u_1$ and $v_0, v_1$, such that if they are projected into $\mathbb{R}^2$ by their $x$ ...
6
votes
2answers
196 views

Number of sudokus with no consecutive arithmetic progression of length 3 in any row or column.

How many such Sudokus are there? Any reference to papers, books, articles or any insight into the problem will be greatly appreciated. I've tried several search engines, scholarly and not, with no ...
2
votes
0answers
62 views

A Strange Algorithm on Processor [closed]

We have n processes, each with a predetermined start and end time. We want to use the ...
0
votes
1answer
25 views

Randomized algorithm for coloring with monochromatic copies

Consider the complete graph $K_n$. Give a randomized algorithm for finding a coloring by two colors with at most $\binom{n}{4}2^{-5}$ monochromatic copies of $K_4$ that runs in expected time ...
0
votes
0answers
31 views

Can every optimization problem that can be solved by a greedy algorithm be solved using dynamic programming? Why, why not?

In other terms, is the set of optimization problems solvable using greedy algorithms contained fully within the set of optimization problems solvable by dynamic programming?
0
votes
0answers
27 views

Simplify iterative logarithm

This is a homework question for my algorithms class and I have no clue how to start simplifying this function. I know log* is the iterative log function. It will equal the number of times you have to ...
0
votes
2answers
34 views

Using Master Theorem to prove a recurrence with f(n) = Θ(n/logn)

I'm trying to use the master theorem to solve the recurrence: $$T(n) = 4T\left(\frac{n}{5}\right) + \Theta\left(\frac{n}{\log n}\right)$$ I'm having trouble understanding how the ...
1
vote
1answer
50 views

Counting the number of complete bipartite subgraphs

I am stuck with problem and not getting much ideas. I have a graph with $N$ vertices and $M$ edges. I have to count number of ways I can choose a pair of set of vertices say $(p,q)$, such that every ...
0
votes
1answer
31 views

finding two most distant 3d points

I'm trying to write an algorithm. There are 9 points 3 of x ,3 of y,3 of z. How can I find the two most distant? Mathematically, I need explanation. Thank you for all appreciated answers. coordinates ...
0
votes
1answer
30 views

Available in 6-packs, 9-packs, 20-packs

Started with an algorithms problem which says item is sold in 3 different sizes of boxes. These 3 boxes have 6, 9, 20 items each. Input is n, figure out if you can ...
-1
votes
0answers
29 views

Linear Programming question involving a data set of consumer purchases

I am from Netherlands and preparing for an interview with Two Sigma Capital, which for the position I am applying for is notorious for asking linear programming questions. I was trying to solve this ...
0
votes
2answers
32 views

Sigma notation, changing limits

I'm trying to understand the proof for a nested loop algorithm and there is only one step that has me scratching my head. The algorithm is represented by: $$ ...
6
votes
0answers
43 views

Is there a numeral system that makes both addition and multiplication easy?

Decimal positional notation, the system for writing numbers we all use every single day, makes addition very easy by transforming it from a computation to a repeated operation on individual digits ...
0
votes
2answers
37 views

Show whether this algorithm produces a uniform random permutation

I am trying to solve this question from CLRS. Professor Armstrong suggests the following procedure for generating a uniform random permutation: ...
1
vote
1answer
25 views

Extended Euclidean Question

The question is as follows: $3157x + 656y = 2173$. I found so far $3157 = 4 \cdot 656 + 533$ $656 = 1 \cdot 533 + 123$ $533 = 4 \cdot 123 + 41$ $123 = 3 \cdot 41 + 0$. Now we do the reverse ...
1
vote
2answers
66 views

Solving $T(n)= 2T(n/2) + \sqrt{n}$ without master theorem (algebraically & recurrence tree)

$$T(n)= 2T(n/2) + \sqrt{n}$$ This recurrence was in a stackoverflow question, and I want to solve it without relying on the master method. The solution was given, but wolframAlpha gives a slightly ...
0
votes
1answer
29 views

A problem related to linear assignment with constraints.

Suppose I have two sets of numbers $\{a_1,\ldots,a_n\}$ and $\{b_1,\ldots,b_n\}$, an integer $m < n$, and a number $r\ge0$. I wish to choose a subset $C$ of $\{1,2,\ldots,n\}$ with $|C|=m$ that ...
0
votes
0answers
15 views

Techniques & Algorithms used to solve Shorted Hamilton Path, Hamilton Circuit Questions

I'm interested in knowing different techniques in approaching the following: Shortest Hamilton Path, Hamilton Circuit (when weights have been given for each edge) Hamilton Circuit - Current method ...
0
votes
0answers
21 views

Probabilistic Method in language membership decision

$F(x,r)$ is a random algorithm to decide membership of input $x \in \{0,1\}^n$ to a language $L$. $r \in \{0,1\}^n$ is randomly selected bits. We know the if indeed $x \in L$, then the probability ...
2
votes
0answers
40 views

Algorithm to find smallest difference in array

We want an algorithm that, given an array of length $n$ of integers, find the minimum difference between two integers in the array. One such algorithm is to sort the array and check adjacent pairs of ...
0
votes
1answer
29 views

Sum of the series of numbers in an array

You are given a number $x$ and an array A[1,2....n] storing $n$ positive numbers such that $$A[1]+A[2]+....+A[i]≤A[i+1], \space \forall i<1.$$ Design a polynomial time algorithm to determine if ...
3
votes
4answers
556 views

Help with mathematical side of programming?

I am a student trying to learn programming on my own, getting help from online sources and people like you. I found an exercise online to create a small program The program should read the numbers a ...
0
votes
1answer
18 views

What is the complexity of halving the size of an $n$-bit number every time.

I was discussing this question with my fiend the other day and was hoping to get some confirmation from someone if the logic I used is correct. Suppose that we have a number $N$ in base 2 ie ...
0
votes
0answers
15 views

Check if an axis aligned bounding box intercepts with a triangle

As the questions says I am trying to check if an AABB intersect with a triangle. I've divided the problem in 3 parts: check if any of the triangle edges intersect any of the AABB faces check if the ...
0
votes
1answer
22 views

How to calculate a line vector from a bunch of points.

I get a bunch of not really random points, which should be abled to formed a single line, the example looks like the following: In this sample, we could easily imagine there is a line formed by the ...
1
vote
1answer
18 views

Algorithm Running Time

Given an algorithm with a running time $$T(n)=5T(n/2)+n^2$$ So the number of nodes at a depth $i$ would be: $5^i$ The input size for each node at $i$ would be: $n/2^i$ Agreed. Then it states that ...
3
votes
1answer
50 views

How to find an expression for a number via a given set of math operators and constants?

Consider one gives you $n$ digits of a (possibly irrational) number and a finite set of math operators and constants, like $\{\sin(x), \ln(x),+,\times, \pi,e,7\}$. Then he asks you to build a ...
0
votes
0answers
22 views

Variation of Bin-packing with classes of bins and objects

I'm working on a problem that is a variation of bin-packing, but a bit more general form with extra constraints. The problem definition is as follows- We have objects of varying sizes, which can be ...
1
vote
2answers
45 views

An algorithm which takes long time to halt

I want to find an algorithm such that takes 10 inputs as natural number returns 1 output as natural number between 1 and 10. (including 1 and 10) It means it should be a function f($x_0$, $x_1$, ...
2
votes
1answer
46 views

Best score in this puzzle

I want to maximise the score of the following table, choosing one item from each column/row, so no two items are on the same row or column. Score to maximise is just adding all the choices together. ...