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
0answers
12 views

Setting up a recurrence for Odd-Even Mergesort

Given the below algorithm How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort? What I've tried For ...
0
votes
1answer
16 views

Explain instability in Numerics so that I can understand and answer this question that involves roots of a equation

I found this question in my math book: Instability. For small |a| the equation (x - k)^2 = a has nearly a double root. Why do these roots show instability? I read and belive I understood the ...
0
votes
0answers
8 views

similarity between two ranked sequence

How can I measure similarity/distance between two sequences of ranked numbers/letters. The two sequences are of different length, and only have some elements in common? For example, if I have three ...
3
votes
2answers
34 views

Selecting k distinct numbers from an array with increasing probability distribution

I have to select k distinct numbers from an array such that probability of a number getting selected is more if it is at the end of the array (probability increases linearly). I'm thinking of ...
0
votes
0answers
12 views

Determining accuracy of time using Cristian's Algorithm [on hold]

When determining the accuracy of a result, Cristian's Algorithm says that you do: $$ \pm \frac{T_1 - T_0}{2} - T_m $$ Why is this not $$-2T_m$$ to account for the min transmission time on both ...
2
votes
3answers
39 views

Fastest way to perform this multiplication expansion?

Consider a product chain: $$(a_1 + x)(a_2 + x)(a_3 + x)\cdots(a_n + x)$$ Where $x$ is an unknown variable and all $a_i$ terms are known positive integers. Is there an efficient way to expand this?
1
vote
0answers
37 views

Setting up and solving a recurrence relation

Assume we have two lists, $A$ and $B$; both are sorted lists each with $n$ elements (assume $n$ is a power of 2). We want to recursively merge the odd-indexed elements from each list: merge $a_1, ...
1
vote
2answers
41 views

How to approximate $x^y$ using a quadratic function

I need to build an algorithm that finds the approximately $x^y$ where $x = [0, 1]$ and $y = [0, 0.4)$. This is for a computer algorithm (the standard library is too slow). I thought about making a ...
0
votes
1answer
33 views

Finding all intersecting circles of one circle.

I have one circle $C_0(x_0,y_0,R_0)$ in a plane (which moves around here and there). There are many other circles on the same plane $C_1(x_1,y_1,R_1),C_2(x_2,y_2,R_2).....,C_n(x_n,y_n,R_n)$ where ...
1
vote
1answer
24 views

Show that there is such an algorithm

Let $L_P = \{+, \geq; 0, 1\} $. The first-order theory of $\mathbb{N}$ in the language $L = L_P \cup \{exp_2\}$, where $exp_2$ the function which sends a natural number $n$ to $2^n$, is decidable. ...
0
votes
1answer
20 views

how to determine maximum length of chain of tail-to-head connections in a given word list

Given a finite set of words, I wish to to write an algorithm which will create a chain of words, where the tail (last letter) of a word n will be the same as the ...
1
vote
2answers
30 views

What's theoretical maximum information compression rate?

Let's say I've got a random bit sequence s and a reversible function f(s), for which the following statement ...
2
votes
1answer
42 views

Find edge disjoint spanning tree subgraph between A and B

Given an undirected graph G(V,E). A and B are elements of V. Identify a subgraph of G containing A & B with 2 edge disjoint spanning trees (or prove one doesn't exist). I have found several ...
0
votes
1answer
68 views

Is an algorithm to find all primes up to $n$ that runs in $O(n)$ time fast?

I kindly ask you if it is useful or fast for a prime number generator to run in $O(n/3)$ time? I believe I have a way to generate all $P$ primes up to $n$, quickly and neatly, in $P$ comparisons and ...
2
votes
1answer
29 views

Tensors in matrix multiplication algorithms

Fast matrix multiplication algorithms, be it the Winograd and Coppersmith algorithm or any further improvement of it, extensively use tensors. In fact, the entire construction is based on tensor ...
3
votes
0answers
34 views

How to create a new formula for a fractal-type image?

(If this is the wrong place to ask, then PLEASE tell me where to take the question instead of chewing me out over this.) I have been learning how to write out SVG by hand, and in the process made a ...
1
vote
2answers
49 views

Manual generation of all permutations of N non-repeating elements

I am looking to find if there is a way to manually (meaning, not using a machine that has high memory capacity) generate all the permutations of a set of N non-repeating (unique) elements by the way ...
0
votes
0answers
23 views

How can I modify this simple code to include the pressure term? (1-D Navier Stokes)

I have a mathematical model that involves a cylindrical container that is being modeled with a one dimensional simplification as the system is isotropic with respect to the z-axis. As part of the ...
0
votes
0answers
15 views

How to get accuracy of prediction?

I am working on a project where there is a part, which is based on the confidence level (between 0 and 1). The confidence level here is for various situations finally going Yes or No. So, 0.9 ...
0
votes
1answer
20 views

Making all row sums and column sums non-negative by a sequence of moves

Real numbers are written on an $m\times n$ board. At each step, you are allowed to change the sign of every number of a row or of a column. Prove that by a sequence of such steps, you can always ...
0
votes
0answers
11 views

Distributing resource based on Efficiency

I am trying to form an optimization problem where I have $k$ nodes who transmits packets with rate $x_k$. The objective is to maximize the rate. $\hspace{28mm} \text{ Maximize } \sum_k \log x_k$ ...
0
votes
1answer
27 views

How to find the find the Optimal Time Schedule? [closed]

You have N = 2 processors to process M independent tasks with processing times 1, 2, 3, …, M. Find the optimal schedule, and give the optimal completion time Opt in terms of M. (Hint: Consider ...
0
votes
0answers
26 views

Algorithm for finding the value of determinant

Okay I am writing to write a program which computes the determinant of a matrix. So is there an algorithm that allows you to do that ? Are there any other ways of finding the determinant value other ...
0
votes
1answer
17 views

How to combine not disjoint sets in all possible ways?

Let's say that I have a set of sets. Each of them composed by two or more subsets. For example: S = {S1, S2, S3} S1 = [0,1,2,3] = {S11 = [0,1], S12 = [2,3]} S2 = [2,3,4,5] = {S21 = [2,3], S22 = ...
0
votes
1answer
60 views

Bresenham's Line Algorithm

This is a page from the book Schaum's Outline of Computer Graphics. The text says, Selecting T means $d_i>=0$, and, selecting S means $d_i<0$. I didn't understand why. Can you please ...
1
vote
0answers
20 views

Process Transition Algorithm

I have a process with 100 possible states and independent entities going through the process. All the Entities have been observed through a span of 5 years at the end of each month. When the ...
2
votes
2answers
28 views

Proof of completeness and soundness of a proof system

As stated here, https://en.wikipedia.org/wiki/List_of_rules_of_inference, "a set of rules can be used to infer any valid conclusion if it is complete, while never inferring an invalid conclusion, if ...
0
votes
1answer
33 views

Program languages recommended for complexity theory

I am an undergraduate studying mathematics and one of my interests include complexity and computability theory. I have no experience in programming. The computability theory books I looked into didn't ...
0
votes
0answers
8 views

Shrink wrapping algorithms to make a mesh watertight for 3d printing

I'm investigating algorithms to make a mesh watertight for 3d printing. I'd be very excited to implement such algorithms. The initial input is a mesh which is not watertight and I want to understand ...
0
votes
1answer
29 views

Lower bound on circuit size of a Boolean function

I'm currently reading a proof of the following claim from the notes http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf which can be found on the bottom of page 6. I'd like to point out i'm interested ...
0
votes
1answer
45 views

Bilinear maps and Bilinear algorithms

How can one intuitively understand the definition of a bilinear map? Is there some way of looking at it geometrically? I found the following definition: Let $\mathit{A}$,$\mathit{B}$,$\mathit{C}$ ...
0
votes
0answers
18 views

Algorithms for finding maximum matching in a graph

I need to learn as much as possible algorithms for finding maximum matching in a graph (directed and undirected, bipartite and non-bipartite). At the moment, I have the following algorithms: ...
0
votes
1answer
19 views

Proof that the fractional knapsack problem exhibits the greedy-choice property

I have the following problem: Prove that the fractional knapsack problem has the greedy-choice property. The greedy choice property should be the following: An optimal solution to a problem ...
3
votes
1answer
58 views

Finite difference method works for $\frac{\partial u}{\partial t} = \frac{du}{dz}$ but not for $\frac{\partial u}{\partial t} = - \frac{du}{dz}$?

I am using the method of lines with forward differences to solve the transport equation $$\frac{\partial u}{\partial t} = \frac{du}{dz}$$ with initial condition $u(z, 0) = z$ and boundary condition ...
0
votes
0answers
28 views

Is it true that Ackermann's function cannot be implemented without recursion? [duplicate]

Yesterday I got sucked into a bingewatch of Computerphile's and Numberphile's videos on youtube. In particular I ended up watching some on Ackermann's function. While I knew already this function (and ...
0
votes
1answer
27 views

Algorithm for grouping users by their quiz answers

Let's say I have a cluster of users that I want to group to N groups by the similarities of their quiz answers. Questions have predefined answers with value of a letter (a, b, c, etc.). My criteria ...
0
votes
1answer
35 views

Coin Change Problem with Fixed Coins

Problem: Given $n$ coin denominations, with $c_1<c_2<c_3<\cdots<c_{n}$ being positive integer numbers, and a number $X$, we want to know whether the number $X$ can be changed by $N$ coins. ...
0
votes
1answer
36 views

Find number in Young tableau in $O(n+m)$

Give an $O(n+m)$-time algorithm to determine whether a given number is stored in a given $m\times n$ Young tableau. An $m\times n$ Young tableau is an $m\times n$ matrix such that the entries of each ...
1
vote
1answer
37 views

Strassen's Algorithm for matrix multiplication

Can someone demonstrate the multiplication of two $4\times 4$ matrices using Strassen's algorithm? I don't understand when to stop partitioning the matrices. We first partition the two $4\times 4$ ...
0
votes
1answer
20 views

Algorithmic solultion for eigenproblem over finite field

i am looking for the standard algorithms for solving eigenvalue problems over finite fields. (For example the algorithm implemented in GAP). I googled a lot but did not come to a conclusion. I saw ...
3
votes
1answer
52 views

Cutting a paper with the smallest number of cuts

You want to cut a piece of paper of length $N$ to $N$ pieces of length 1. It is not allowed to fold the paper, but if two or more previously-cut pieces of paper have the same length, it is allowed to ...
2
votes
0answers
45 views

packing problem of semicircles into rectangle

I have problem. How can I get the maximum amount of semicircles (for example radius $35\;mm$) into rectangle $(485\times 185\:mm)$. I found many articles about packing of circles but nothing about ...
1
vote
1answer
142 views

Can a method related to “Weisfeiler-Lehman Method” provide better time complexity for Graph Isomorphism than existing result?

Cai-Furer-Immerman showed that the W-L(Weisfeiler-Lehman ) hierarchy cannot distinguish general graphs except at linear dimension. Even besides CFI's result, there is good reason to believe that ...
2
votes
0answers
48 views

Intersecting convex figures

Take in the real plane a finitely long horizontal line segment and connect the two endpoints by a convex path, above the segment, with the property that the only extreme points of the convex hull of ...
0
votes
2answers
25 views

Proving guess wrong used for substitution method

Following is my recurrence relation : $T(n) = 2T(n−1) + c_1$. Complexity: $O(2^N)$. I want to prove it by substitution method/ mathematical induction (You can get insight of it from : ...
4
votes
1answer
54 views

Polynomial algorithm for problem in graphs which can also be solved as a linear programming problem.

I have an (undirected) graph $G = (V, E)$. For each vertex $i \in V$ we have a cost associated $v_i$ and for each edge $e \in E$ we have a prize associated $x_e$. My problem is to find $W \subseteq ...
1
vote
2answers
29 views

expected value of final x using the following algorithm

It has a bit of pseudo code so i'll try to explain x = 0 for i from 1 to n: if random() > 1/4: x = x + 5 else: x = x - 1 the probability ...
-1
votes
1answer
100 views

How to make this cubic root (C++) algorithm faster?

Okay, so this is the algorithm. It works but takes too much time. ...
0
votes
0answers
18 views

to that prove for an adjacency matrix A 1/3*(trace(A^3) equals to the number of sub graphs that are isomorphic graphs to k3 [duplicate]

i am kinda new to the graph theory, i've got an assignment to prove that: For an adjacency matrix A (1/3)*(trace(A^3)) equals to the number of sub graphs that are isomorphic graphs to k3. i am ...
1
vote
0answers
8 views

How do you determine the number of errors in the Welch-Berlekamp method for decoding Reed-Solomon codes?

I asked this question on cs.stackexchange, but the community appears to be very small and I got no response. In the Welch-Berlekamp algorithm for decoding Reed-Solomon codes, one is given a list of ...