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
1answer
18 views

How to find worst case in chain matrix multiplication

The question we got was Determine a worst-case parenthesization of the matrix-chain product whose sequence of dimensions is (5, 2, 3, 10, 4, 6, 7, 8). what i dont understand is how do we determine ...
1
vote
1answer
25 views

Wouldn't this Greedy Algorithm achieve the highest possible of money in this situation?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
0
votes
0answers
10 views

people passing a bridge (a proof for a greedy algorithm)

the problem some people are passing a bridge . each one takes a different time to pass . assume the people are sorted by their passing time increasingly . these are the conditions of passing the ...
0
votes
1answer
17 views

Looking for algorithms capable of modifying graph structure

I realize this is a quite a general request. I'm just looking for examples of path searching algorithms for directed graphs which are capable of utilizing simple modifications (adding vertices, adding ...
0
votes
0answers
8 views

Generating Random Derangements in R

Does someone know how I can easily generate random derangements of a vector in R ? Do I have to do it manually or is there some existing package ? I have not found anything so far. Thank you ! Anas ...
2
votes
0answers
9 views

Finding regular expressions for which a given Turing machine halts and accepts, halts and rejects, and diverges.

Consider the Turing machine M = (Q,Σ,Γ,δ,q,F) F = {t} Q = {q,r,s,t,v,x} Σ = {a,b,c} Γ = {B,a,b,c} δ = [q,a,q,a,R] [q,b,q,b,R] [q,c,v,b,R] [q,B,r,B,L] [r,a,s,B,L] [r,b,s,B,L] [r,c,s,B,L] ...
3
votes
1answer
18 views

Find the “surface vertices” of a collection of points.

I am currently doing some experiments in order to simulate liquids. I have a collection of 3D points that interact with each other to form a body of water. I would like to form a mesh from these ...
0
votes
0answers
7 views

recurrence tree final step - binary search

Starting with the base case and recursive case run times as follows: 􏰀 t(N) = 1 , if N = 1 t(N)= 1+t(N/2) ,ifN > 1 At the end of my tree I have ...
0
votes
0answers
8 views

Examples of Algorithms capable of modifying graph structure?

I'm currently working on a problem where one is presented with 2 connected digraphs (call them G1 and G2), each with an associated set of logical constraints. Each vertex of each graph represents a ...
2
votes
0answers
18 views

Efficient computation of matrix determinant in finite field

I am trying to implement generalization of Hill cipher. My idea is very simple: the size of key matrix should be arbitrary number not only three. All steps of this cipher is trivial except computation ...
0
votes
0answers
13 views

Learning Booth's Algorithm, I Can't Find the Issue on Final Result

I am practicing using Booth's Algorithm to multiply a positive number and a negative number (specifically the problem is $-12 \times 4$). I have included my attempt, but I can't find the issue. If ...
1
vote
2answers
27 views

Simple Adding and Subtracting algorithm to get a current amount

So this is my first post and its probably a really dumb question but I cannot get my head around a proper algorithm to handle the following situation. I have a dataset that contains employees who ...
1
vote
1answer
16 views

0/1 knapsack upper bound

I'm new to the 0/1 knapsack problem and I've ordered my nodes into profit/weight as: Knapsack max weight: 12 ...
0
votes
1answer
29 views

Find all nearest points

I have two sets: $$P = \{p_1, p_2, ..., p_n\}$$ $$Q = \{q_1, q_2, ..., q_m\}$$ For each $p_i$ point I need to find all nearest points in $Q$. I.e., $$p_i \rightarrow \{ q_{i_1}, q_{i_2}, ..., ...
0
votes
2answers
59 views

Minimum number of operations to make all of the strings (objects) the same

Let $A$ be an alphabet, $K$ and $N$ be natural numbers and $X$ be a list of $N$ strings over $A$, each one consisting of $K$ letters. You have one operation ($@f$): convert a string from $X$ to ...
3
votes
1answer
59 views

Algorithm to solve gridlock (traffic jam)

Is there an algorithm for solving a gridlock (traffic jam)? Given a gridlock situation, this algorithm should tell which moves each car should make, and in which order the cars should move, so that ...
0
votes
0answers
22 views

How to approximate a trigonometric to make less computation complexity

I having a trigonometric function such as $$ p_2(s) = \begin{cases} \frac {1}{(2 \pi)^2}(1-\cos (2 \pi s)), & \text{if $s \le1$ } \\ \frac {1}{2 }(s-1)^2, & \text{if $s >1$ } ...
1
vote
1answer
19 views

Origin of divergence in a divergent field (2D)

I have a field of measured vectors, see example of four vectors in image below. If there was no noise they would all point outward exactly from one "central point". i.e. there would be a circle whose ...
0
votes
3answers
33 views

Efficient algorithm for taking powers of binary numbers?

Is there any efficient algorithm for taking powers of binary numbers? Or even just squaring one? Thanks ahead of time.
-4
votes
0answers
32 views

does anyone know how to generate those red shape in pictures? [on hold]

I'm trying to make red shape through some kind of algorithm,suppose we know the font consist of Bézier points and lines.any good ideas?
1
vote
2answers
35 views

Problem implementing a QR factorization

I'm trying to write a Fortran subroutine to compute a QR factorization using the Householder method. To test my routine, I compute the factorization of the following matrix: $$ A = \begin{pmatrix} ...
0
votes
2answers
39 views

Writing a GCD of three numbers as a linear combination

i know how to find the $\gcd(5,11,2^{2015}-1)$. but i can't seem to find the linear combination. do you find it the same way we find the linear combination of two integers.
1
vote
1answer
26 views

How to set up this algorithm?

I'm doing a simple budget app, to make some calculations to improve private economy. I've made an option where you can enter the value of the money that are in the bank right now, and how many days ...
-1
votes
0answers
9 views

Get a given string by concatenation of the minimal number of given words [on hold]

Suppose you have an input string, say $s$, and a set of words $W$. The task is to find the minimal $N$ such that: $s = w_1 \cup w_2 \cup ... w_N$, where $w_i \in W$. Could you please name a handy ...
0
votes
0answers
22 views

How to use mobius-inversion to solve this problem?

Currently, I'm trying to solve this problem using mobius-inversion. the function f(d) means the number of (i, j, k) equals d, and function g(d) means the numbers that satisfying: d | (i, j, k). Then ...
0
votes
1answer
28 views

Given that Minimum Spanning Tree is NP-complete show that Hamiltonian Cycle is NP complete

So first of all I know finding MST is in P and is not NP complete. But I checked last year exams from my University and there is a problem: Given that Minimum Spanning Tree is NP-complete show that ...
0
votes
0answers
15 views

Implementing specific SVD algorithms

My goal is to learn to implement the two-sided Jacobi SVD, a method of SVD for bidiagonal matrices, and a method of SVD for tridiagonal matrices. Can anyone recommend a place to learn about these, or ...
1
vote
1answer
23 views

How to efficiently list prime with a very specific property

I noticed that my phone number 06 xx xx xx xx is a prime number. Ok that cool ... But if you had the country code (+33 for france), ...
1
vote
0answers
6 views

Is the mapping achieved by the discrete Frechet Distance the best achievable pair decomposition?

I have the following proble: There are 2 sequences $P$ and $Q$ composed by $M$ and $N$ points respectively. I want to calculate the discrete Frechet distance between them. This operation outputs also ...
0
votes
0answers
15 views

A suitable algorithm to change strings to zero strings

I found a programming exercise I couldn't solve. Namely, I have been given a long binary string and a fixed set of operations. Here, an operation means that it takes a substring and transforms its ...
0
votes
0answers
35 views

How many counts the square number?

For example I have a number is $55$. Can I check this for how many counts number's square create this number. For example I have $55$ So, I know this number total from 5 number, which are $$55 = ...
0
votes
1answer
22 views

Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

This problem is from Algorithms, problem 2 The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($\log n$) time algorithm to find the median of the 2$n$ ...
0
votes
0answers
18 views

Help understanding Jacobi SVD

I found this link, and I want to complete this implementation of the Jacobi SVD method, but it isn't clear to me how to implement alpha, beta, and gamma. I think it's very clear that ...
0
votes
0answers
9 views

Code that Creates a Monotonic Array

I'm not sure whether this belongs on StackOverflow or here. Suppose I have an infinite (indexed from $-\infty$ to $\infty$) array of random doubles x[]. They are ...
1
vote
0answers
47 views

Squaring a matrix using a linear memory

I have a N x N matrix (let's denote it with A). I want to calculate $A ^ 2$, using $\theta(N)$ memory (speed does not matter as long as it's a polynomial) on one processor. I believe that this can ...
0
votes
1answer
43 views

What algorithm can sort the first sqrt(n) elements of an array in O(n) time?

I want to partially sort an array of $n$ elements to get the first $\sqrt{n}$ elements sorted, and it has to be done in $O(n)$ time. The complexity $O(n)$ seems to imply that it is necessary to go ...
0
votes
1answer
19 views

Finding algorithm to design combinatorics formulae per input data

Problem: calculate how many unique "words" can be made using the letters of your a) name (Kateryna - 8 letters, letter 'a' used twice) b) lastname (Atamanchuk - 10 letters, letter 'a' used 3 times) ...
0
votes
0answers
15 views

Computing efficiently a small base to the power a large number

Is there a fast algorithm to compute an exponential with a small base, (namely , close to 1) For example, computing 1.01 to the power 100?
0
votes
0answers
12 views

Depths of top-level multiplication algorithms

I've seen that the depth of the Cantor/Kaltofen algorithm is in $O(\log n)$. Are the operations for this complexity undifferentiated ? Or this complexity is in terms of multiplications only ?
0
votes
0answers
7 views

BFS Modification For Total Shortest Paths

I was given the following problem as an assignment but it is really confusing me: Consider the BFS algorithm. Given a digraph G = (V, E) and a starting vertex s ∈ V, this algorithm computes for ...
2
votes
1answer
33 views

The output spanning tree of Kruskal's algorithm is a minimum spanning tree

I want to show that the output spanning tree $S$ of Kruskal's algorithm is a minimum spanning tree, so it is of minimum weight, by contradiction. We suppose that $S$ is not a minimum spanning tree. ...
0
votes
1answer
30 views

Have you seen these integer factorization algorithms before?

I have two algorithms for finding two factors, $p$ & $q$, of a number $N$. The algorithms are (hopefully) obviously related. The pseudo-code for them follows: Algorithm 1 ...
1
vote
1answer
21 views

Summation to Closed Form conversion

I am struggling to understand basics as it related to forming a closed form expression from a summation. I understand the goal at hand, but do not understand the process for which to follow in order ...
0
votes
0answers
35 views

proof that some expected value equal to $\theta (\log n - \log k)$

So here is the problem - Given the following equation: $(c_2\cdot \log n) - (c_1\cdot \log k)\le E(X)\le 1+ (c_1\cdot \log n) - (c_2\cdot \log k)$ When $c_2,c_1\gt0$ and also $c_1\gt c_2$ In ...
0
votes
0answers
16 views

how to create sets which has one common value for intersection

There is a algorithm called Maekawa, to send message to a particular request set (http://courses.cs.vt.edu/cs5204/fall99/Supplemental/ProblemSet8.html) I am interested in the ALgorithm to generate ...
4
votes
0answers
27 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has n different elements [A1 .. A2 .... An](random order). We have a comparator C, but it has a probability p to return correct ...
0
votes
0answers
20 views

expectation approximation

Note: You don't have to understand Approximation Algorithms to answer this Hello. I need to prove an algorithm approximation by using expectation. The algorithm takes $x_i \in {0,1,2}$ such that ...
2
votes
1answer
57 views

The output of Kruskal's algorithm is a spanning tree

I want to show that the output of Kruskal's algorithm is a spanning tree. Let $G$ be a connected, weighted graph and let $S$ be the subgraph of $G$ which is the output of the algorithm. $S$ cannot ...
1
vote
0answers
20 views

Coloring chordal graphs

It is well known that the graph coloring problem --- given a graph $G$ and a number $k\in\mathbb{N}$ decide whether $\chi(X)\le k$ --- is NP-complete. However, certain classes of graphs can be colored ...
1
vote
1answer
65 views

Is there a fast divisibility check for a fixed divisor?

Is there a fast algorithm to check if $d \mid n$ is true for varying $n$, if divisor $d$ is fixed? Variable $n$ is a $w$-bit binary integer, $d$ is an integer constant.