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)

0
votes
0answers
80 views

completely stuck on this question about decidability

A decision problem X is as follows: $X = f\langle M \rangle\mid M$ is a program that accepts the empty string. Now, we define another decision problem Y as follows: $Y = f\langle P \rangle ...
4
votes
4answers
259 views

Show the probability that the sum of these numbers is odd is 1/2

Setting Let $S$ be a set of integers where at least one of the integers is odd. Suppose we pick a random subset $T$ of $S$ by including each element of $S$ independently with probability $1/2$, Show ...
7
votes
1answer
157 views

Accelerating approximations for arccos

I have recently built a method to accelerate drastically the accuracy of the following approximation of $\arccos(x)$ : $f_n(x)=2^n\sqrt{2-2g^{n-1}(x)}$ where $g(x)=\frac{1}2\sqrt{2+2x}$ and ...
1
vote
1answer
30 views

Switching lights in a matrix

I'm interested in papers and articles on the following problems (not necessarily solutions). At least is there a name to these that I can lookup ? Say that $a_{ij} \in \{-1, +1\}$ for $1 \leq i, j ...
0
votes
2answers
30 views

Analysis of Algorithms - Big O Notation Equivalences - Limits

Please see below block question from review for test. True Or False? Justify Your answers A) is 2^(n+1) = O($2^n$) B) is 2^2n = O($2^n$) C) is log($n^2$) = O(logn) D) is ...
0
votes
1answer
29 views

Where does the root of this tree come from?

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 ...
1
vote
1answer
75 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 ...
2
votes
1answer
45 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 ...
1
vote
0answers
31 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
33 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 ...
2
votes
1answer
17 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] ...
4
votes
1answer
24 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
11 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
13 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
61 views

Efficient computation of matrix determinant in finite ring

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 ...
1
vote
0answers
20 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
29 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
32 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
31 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
83 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 ...
7
votes
1answer
165 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
30 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
25 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
37 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.
1
vote
2answers
39 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
44 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
33 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 ...
0
votes
0answers
33 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 ...
1
vote
1answer
48 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
19 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
10 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
17 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
37 views

Regular Subresultant PRS from Euclidean PRS?

Is there any way to compute regular subresultant polynomial remainder sequence if we know the Euclidean polynomial remainder sequence of two univariate polynomials and vice versa?
0
votes
0answers
40 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
32 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
10 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
56 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
59 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
27 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
16 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
15 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
13 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
53 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
33 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
30 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
44 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
17 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
30 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 ...