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
1answer
35 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
46 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
22 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
59 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
40 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
40 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
53 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
50 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
151 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
49 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
26 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
56 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
30 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 ...
0
votes
0answers
27 views

Square root in a general field

In $\mathbb{Q}$, $\mathbb{R}$ and $\mathbb{C}$ there are obvious ways to calculate the square root of a quadratic residue. For finite fields of order $p$ we can use the Tonelli–Shanks algorithm. How ...
2
votes
0answers
68 views

Compute sum of large powers [closed]

I have the following problem. There is an array that contains values that are to be powers of $-2$. I need to calculate the sum of these powers. For example, if the array is $\{3,4,5\}$ I need to ...
0
votes
1answer
30 views

NP-complete proof of subset with sum zero

I'm trying to proof that a problem of subset from a group has a sum of zero. I know that i can use the partition problem that is known to be NP-complete, but i can't seems to find what i need to ...
2
votes
0answers
35 views

Riemann Zeta continued fraction approximants

In the paper Continued-Fraction Expansions for the Riemann Zeta Function and Polylogarithms by Djurdje Cvijovic and Jacek Klinowski, there is a claim that I cannot reproduce. In the abstract they ...
1
vote
0answers
24 views

Chaining integer division operations

In an assembler program I am writing, I need to (quickly) calculate $a\text{ mod }n$. Now, in the language I am using there is a division instruction that takes two numbers $x$ and $y$ and returns ...
0
votes
0answers
42 views

Find the shortest cycle in a directed weighted graph using Dijkstra's algorithm

I was studying Dijkstra's algorithm to find the shortest path from a node to other nodes, and it came out a problem: find the shortest cycle in a directed weighted graph containing a node. I have ...
-1
votes
0answers
18 views

Anaerobic treshold computation from lactate test.

I would like to know how to calculate the anaerobic threshold of a lactate test. This is used for better planning of training for athletes. Input data is as follows: $$\begin{array}{c|c|c|c|c} & ...
1
vote
1answer
24 views

What is the name of the transform which finds the number of ways to make partitions of the given sizes?

I'm looking for the name of a transform which takes a sequence giving the number of 'prime' elements of a given size to the number of ways to make a number out of a sum of 'prime' elements, up to ...
0
votes
1answer
25 views

Dijkstra’s algorithm / path is this done correctly?

im doing this assignment and it seems as if my teacher has made a mistake. according to me in order to find the minimum spanning treee from a-z , you start from a and then go to : a,f,d,c,b,e,z,g ...
1
vote
1answer
40 views

On counting and generating all $k$-permutations of a multiset

Let $A$ be a finite set, and $\mu:A \to \mathbb{N}_{>0}$. Let $M$ be the multiset having $A$ as its "underlying set of elements" and $\mu$ as its "multiplicity function". (Hence $M$ is finite.) ...
0
votes
1answer
49 views

Dijkstra's algorithm, am I or the teacher mistaken?

Imagine that Dijkstra’s algorithm has been used to show the length of the shortest path from $a$ to $g$ in the graph in figure 1. Which of the following vertices is added first to the set $S$? It's ...
4
votes
0answers
34 views

Can I go from the LU factorization of a symmetric matrix to its Cholesky factorization, without starting over?

I mistakenly computed the LU factorization and then realized that the question is asking for a Cholesky factorization, i.e., finding a lower triangular matrix L such that the symmetric matrix A has ...
0
votes
1answer
28 views

Map one graph to another graph

consider we have a flow network $G = \{V_g, E_g\}$ and an undirected graph $T = \{V_t, E_t\}$. Nodes of the network G have weights $w(v): v \in V_g$ and edges G have weights $w(u,v): u,v \in E$. Nodes ...
0
votes
0answers
42 views

Minimum movements to arrange fruits in boxes

I have $3$ boxes - $B_1, B_2, B_3$. Each box initially contains a mixture of $3$ different kind of fruits say - Apple, Orange, Mango. Our goal is to arrange the fruits in the boxes in such a manner ...
3
votes
1answer
47 views

Finding the n-th arrangement of items with repetitions [duplicate]

I'm new to Stackexchange and maybe I do not have the correct mathematical terms for the question I'm about to ask. I'm given a multiset of given size $N$ which consists of zeros and ones. Example: ...
0
votes
0answers
6 views

Example of weighted max cut taking exponential time iwth local search

In the Coursera algorithms course, the instructor mentions some graphs with weighted edges take exponential time to solve in the worst case with local search the max cut problem. The search algorithm ...
0
votes
1answer
96 views

Finding number of subarrays not including certain pairs

How many contiguous subarrays of an array exist such that they do not contain certain pairs of positions of the array? For eg. if array ={11,22,33,45} and if we do not want to include say position ...
0
votes
1answer
22 views

Maths Algorithm need help

Hi I'm stuck on this maths question don't really know how to about it. I've tried simultaneous equation to solve for k and c with no success. Hope you can help. I got part 1 but can't get part 2. A ...
1
vote
1answer
51 views
0
votes
1answer
43 views

Proof that there isn't a graph search algorithm that is complete with finite memory

Is there a proof that any graph-search algorithm capable of exploring any graph (where there is a upper bound on the degree of each node and there is an ordering of the edges at each node-i.e left to ...
0
votes
2answers
40 views

Proving that this algorithm distributes a quantity as expected

Background (non-essential) Let $Q$ be an integer quantity (of say, marbles) to be distributed into $n$ buckets ($B_1$ ... $B_n$) according to weights. Let $w_1$ ... $w_n$ be the non-negative weights, ...
0
votes
1answer
10 views

Raymarching (fixed steps, increasing step size)

I have two points, "near" and "far", on a line (e.g. near = 0.5 and far = 1000.0). I wish to step along the line from near to far in a certain number of steps (e.g. 256). I would like the step size ...
4
votes
1answer
33 views

LU decomposition for cyclic tridiagonal matrices

It is known that a tridiagonal matrix $$ A = \begin{pmatrix} b_1 & c_1 & 0 & 0 & \dots & 0\\ a_2 & b_2 & c_2 & 0 & \dots & 0\\ 0 & a_3 & b_3 & c_3 ...
2
votes
1answer
126 views

The largest tile in 2048, groups of 3 variant?

Question closed on SO for being too mathematical, I've re-asked it here. Following the rules of the, as http://arxiv.org/pdf/1501.03837v1.pdf puts it, "slide and merge" game 2048, canonically ...
0
votes
0answers
17 views

Extension of Isovist concept for a point - to Isovist for a polygon

There is the concept of Isovist/Visibility polygon. They both talking about volume of space visible from a given point in space. My question: What is the algorithamic solution of this problem for a ...
0
votes
1answer
31 views

Complexity of subset-generation algorithm

I'm trying to calculate the computational complexity of an algorithm which generates the power set of a set of items. The algorithm works using the recursive formula of the binomial coefficient ...
0
votes
1answer
193 views

How are these equations equal?

I am reading CLRS 3rd edition(Wikipedia page) on page 26, author deduced a formula for the running time of ...