Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [algorithms]

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).

0
votes
0answers
8 views

Is there an algorithm for breaking symmetries in polycube puzzles?

Does there exist a general algorithm for dividing a polyomino/polycube packing problem into a set of subproblems which if solved will produce in aggregate all solutions to the original problem, but ...
0
votes
4answers
46 views

How do you add, subtract, multiply, and divide infinite decimals?

In elementary school, we are taught how to add, subtract, multiply, and divide two terminating decimals. My question is, what are the corresponding algorithms in the case of non-terminating decimals, ...
0
votes
0answers
22 views

Find unknowns from xor equations [on hold]

I have equations of the following form for $n$ variables: $$ \left\{\begin{array}{l} a_1 \oplus a_2 \oplus a_3 = v_1 \\ a_2 \oplus a_3 \oplus a_4 = v_2 \\ \dots \\ a_{n-2} \oplus a_{n-1} \oplus a_n = ...
0
votes
0answers
15 views

decaying fractions and make them closer

My problem is actually algorithmic. I have two request queues, each holding its average wait time. For each queue I am holding x = total_wait_time, y = number_of_requests. ...
0
votes
1answer
39 views

faster than O(n^4) algorithm for solving the following problem

This question is quite similar to the previous one I asked here. I recommend taking a look at it and the solution given by @platty before continuing. Given a set of n inequalities each of the form ax+...
1
vote
0answers
25 views

What does the 8 stand for in the Cantor pairing function?

What does the "8" stand for in the Cantor pairing function (which assigns a natural number to each pair of natural numbers)? Can I change it, or is it constant? The other function for getting the ...
0
votes
1answer
15 views

How to show that the Nearest Neighbour Algorithm given an instance of the metric travelling salesman problem has a logarithmic approximation ratio?

I would like to understand why the Nearest Neighbour Algorithm has a logarithmic approximation ratio when given an instance of the metric travelling salesman problem. I have come across the paper of ...
0
votes
1answer
16 views

Expectation in spectral sparsification algorithms

I am new to random matrices. I am studying the (Sampling) sparsification algorithms done by Daniel Spielman, Teng, Srivastava. They used the concept of graph sampling to obtain a good spectral ...
0
votes
1answer
40 views

faster than O(n^3) algorithm for solving the following problem

Consider the following problem: Given a set of n inequalities each of the form ax+by≤c for some a,b,c in Q, determine if there exists x and y in Q that satisfy all the inequalities. Here is an O(n3) ...
0
votes
0answers
18 views

Algorithm to explain the minimum subset of n variables to explain a sum of non-negative functions in N variables

For a practical application, I have a set of $M$ real valued functions $f_i(\mathbf{x}_t) , \hspace{6pt} 1 \leq i \leq M$. $x_{j,t}$ can be either real or integer in a limited range. The functions ...
2
votes
1answer
39 views

Distance from eigenspace of matrix

In linear algebra, is there a separate name / concept for the notion of distance between linear vector subspaces? I'm asking this because I'm considering a problem in numerical linear algebra where ...
0
votes
3answers
29 views

All possible ways to split a number

I am trying to find a way to find (if it is possible) how many ways there are to split a number of n digits considering that the "splits" can occur everywhere and the subsets don't have to be the same ...
0
votes
0answers
14 views

How would I reduce the Minimum Vertex Cover problem to a Weighted MAX SAT problem?

I am currently trying to solve the Minimum Vertex Cover problem via a Weighted MAX SAT solver, but I am stuck with the model. The transformation to a simple SAT is straightforward since every node can ...
-1
votes
0answers
19 views

Evaluate the time complexity of following recurrence relation: T(x,y) = Θ(x+y) + T(x/2,y/2) T(x,c) = Θ(x) for c<=2 T(c,x) = Θ(y) for c<=2

This question has been asked repeatedly in my mid and final semester exams and I haven't found any solution of it online or in any books. ...
0
votes
2answers
47 views

Why Is This Algorithm Not In Polynomial Time?

so recently my professor went over this algorithm and stated that this is not a polynomial time algorithm due to n not being the length of the input. Can somebody explain why this is so? I didn't ...
1
vote
1answer
23 views

How to create sets of nodes on a colored graph while cutting as few edges as possible

I'm a programmer not a mathematician so my jargon is terrible and I apologize. My problem: I have a graph (relatively sparse) and I've colored all its nodes. There are no edges between nodes of ...
1
vote
0answers
15 views

How to find the location of negative cost dicircuit with Bellman-Ford algorithm?

I know that using Bellman-Ford algorithm, it is possible to know whether there is a cycle with negative cost or not. I want to know if it is possible to know which edges form that negative cycle? ...
0
votes
1answer
33 views

Recurrence proof by induction

I'm having a hard time to understand how am i supposed to solve this question: $T(n) = \sqrt{n}T(\sqrt{n})+n$. Prove by induction that $T(n) = \Theta (n \log{(\log{(n)})})$. These are all the data ...
2
votes
1answer
40 views

Large Carmichael number

I need to find or generate a very large Carmichael number (500 digits or longer). I've tried to find a database or just an example of such a number but failed. Is there any examples of really big ...
0
votes
0answers
25 views

Elo ranking system against Expected value [closed]

Why is the Elo necessary and how does it compare against just looking at something like the expectation of wins at measuring players true skill? An example of a correct Elo score would meant that it ...
1
vote
1answer
21 views

Explanation of summation equation

Could somebody please explain the following equation to me? I have no clue what H represents, nor how theta(ln(n)) - theta(ln(k)) results in theta(ln (n/k)) Any explanation would be appreciated. ...
1
vote
0answers
25 views

You're given a list of $n$ days. How many ways can you pick a pair of days such that the first comes before the second?

This is a problem that's introduced in Introduction to Algorithms on the maximum subarray problem. Very briefly, the main problem is something like this: You're given data on the price of a stock ...
0
votes
0answers
23 views

how to draw an undirected graph knowing only connections and weights

I need to draw a complex graph on computer, but all I know are nodes connections and their weights. The problem is how to draw it clearly. Because I don't know [x,y] coordinates for each node, and ...
0
votes
0answers
14 views

How many balls will be left at the end of this process?

Consider having $N$ colored balls. Each color has at least $N/2k$ and at most $N/k$ balls in the beginning, for some parameter $k\ll N$. At each iteration, we remove $k$ balls with different colors, ...
1
vote
1answer
23 views

Why is the average-case running time of quicksort $O(n \log_2 n)$?

What is a mathematically rigorous explanation of why quicksort's average-case running time is $O(n \log_2 n)$?
0
votes
0answers
35 views

Repeating random choice

Let's say I have 10 shirts (A to J) and I'd like to randomly wear a different one each day. So, the one I wore yesterday (let's say shirt J) has 0% chance of being chosen today; The one I wore the ...
1
vote
1answer
34 views

Activity Selection Algorithm

I have an activity selection problem where I am given a number of rides at an amusement park and their start and finish times. My goal is to create a program which maximize the amount of time spent on ...
0
votes
1answer
44 views

Outer product reformulation of LU decomposition

For my numerical analysis class, I wanted to implement the rather simple, in-place LU decomposition algorithm. I did this the naive way and found my code was very, very slow, because I was doing every ...
2
votes
0answers
32 views

Number of Sets of Points Containing a Given Point in its Convex Hull

Consider a lattice grid $[0,N]\times [0,N]$ and a given point $P$ inside the grid. Denote the set of lattice points as $S$ (of course, $|S|=(N+1)^2$). I'd like to ask how to count the number of ...
0
votes
0answers
45 views

Reducing a formula containing Sum and matrices.

M and T is a NxN Matrix, a and b are vectors with N length. g(x) is a function that takes a vector and returns a vector with the same length. g(x) inverse exists. The vector multiplication: t = u*v ...
0
votes
1answer
26 views

4 Points with 2 different colors and 2 Lines partitioning the plane - Combinatorial geometry algorithm problem

We have 4 different points on the x-y plane and we know NO three of them are collinear. The coordinates are $p_1 (x_1 ,y_1) , p_2 (x_2 , y_2) , p'_1 (x'_1 , y'_1) , p'_2 (x'_2, y'_2)$. The first two ...
2
votes
1answer
15 views

What is the maximum connectivity of a planar graph?

The Icosahedral Graph is a simple 5-connected planar graph. Is there a 6-connected planar graph? In general, is there a theoretical maximum on the vertex connectivity of planar graphs? This is ...
0
votes
0answers
13 views

Creating inputs that make a subtraction-based GCD algorithm slow

I have a GCD algorithm that is based on comparison and subtraction. The principle looks like this: ...
0
votes
0answers
15 views

Proof of correctness for rotation of matrix using Transpose and rotation?

I was solving this problem of algorithms where I had to rotate a matrix by 90 degrees (clockwise). The solution seems to be working in all the scenarios and I'm fascinated by the easiness of solution, ...
1
vote
0answers
11 views

Verification of the Cocke-Younger-Kasami (CYK) Algorithm

I've got to test if the string "abba" belongs to the following grammar in CNF: S → CD | CF | CG | CH A → DC | DE B → AC | BC | BE | DC | DE | a C → a D → b E → AC F → DB G → DA H → DI ...
0
votes
1answer
21 views

Most efficient set of characters for cracking passwords (Parallelized)?

For an assignment, we are required to crack a password from a hash given a salt. The password will always be 4 characters that are case sensitive (ex: CMPS, cmps, CAMP, LIST). We are to parallelize ...
1
vote
0answers
15 views

Fast modular composition and irreducibility testing

Given a polynomials $f\in F_q[t]$ we want an algorithm that says if $f$ is irreducible or not. In the book "Modern Computer Algebra" by von zur Gathen and Jürgen Gerhard, an algorithm for that is ...
1
vote
1answer
28 views

Does the TSP (traveling salesman problem) change in difficulty when the number of dimensions is greater than the number of cities?

The title pretty much says it all. I am curious if the TSP is dependent only upon the number of cities, $c$, involved, or if the dimensionality, $d$, matters to the problem. For example, if $d>&...
4
votes
2answers
78 views

A puzzle about the maximum number of favorable squares on a board of any given size.

I have come up with an interesting puzzle but I can't for the life of me figure out how to solve it. It follows like this: You have 2 types of squires that are congruent with one another. Let's call ...
1
vote
1answer
22 views

Adjacency matrix of subdivision graph.

Is there a way to get from an adjacency matrix of a simple graph to an arbitrary subdivision of the graph? I believe I found a way to get from $G$ to $G^{1/2}$ using the incidence matrix, but in ...
0
votes
1answer
11 views

comparing Asymptotic functions $ 3^{{2}^{n}}$ and $n! \times n^{3}$

$f(n)= 3^{{2}^{n}}$ $g(n)=n! \times n^{3}$ $\text{which is asymptotically greater} ?$ My Approach-: $$f(n)=e^{\log 4^{{3}^{n}} }$$ $$g(n)=e^{\log n! \times n^{3}}$$ i am comparing just the ...
0
votes
1answer
28 views

Solution to $x_i=a(1+\sum_{i\ne j}\frac{b_ix_j}{1+b_ix_j})$

I'm dealing with a set of variables $x_i$ and following equations: $\forall i$ $x_i=a(1+\sum_{i\ne j}\frac{b_ix_j}{1+b_ix_j})$ Wolfram mathematica's NSolve could help, but it's not very accurate and ...
0
votes
1answer
25 views

Finding $(x,y)$ closest to $N$ points

Given $N$ points where the coordinates of the $i$th point are $(x_i,y_i)$ find $(x,y)$ that minimizes the following sum. $$\sum_{i=1}^ N\max(|x-x_i|,|y-y_i|)$$ I've done a similar problem minimize $$\...
1
vote
1answer
70 views

Calculating $\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{m-1} |mi-nj|$

I'd like to calculate $f(n,m)=\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{m-1} |mi-nj|$ for all $1 \leq n \leq N,\ 1 \leq m \leq M$. Straightforward brute force method runs in $O(N^2M^2)$ which is too ...
0
votes
1answer
23 views

Convergence of Linear Neural Networks in the Easiest Framework

EDIT: Thanks to the first answer I'm lighting some assumptions: I'm trying to understand the basics of machine learning, and I have this theoretical question: I have a one layer linear neural ...
0
votes
2answers
29 views

Permutations without repeating myself

This may be a quite simple question, but there we go. Imagine that I've got a sequence $s = [s_1, s_2, \dots, s_n]$. I want to generate programatically a new random permutation $s'$ of $s$ so that $\...
0
votes
1answer
26 views

How to check subsets efficiently

Suppose we have a 5-bit 0-1 string "01001" and a set of 5-bit 0-1 strings {"01010","10111","01011"}. Define a relation on string a and b: $a \subseteq b$ if and only if all bits 1 in a exist in b in ...
1
vote
0answers
27 views

Why is the Frank-Wolfe algorithm projection-free while gradient descent isn't?

While reading this article about the Frank-Wolfe algorithm, I did not understand why the Frank-Wolfe algorithm is projection-free, while the gradient descent is not. I think the problem is, that I do ...
0
votes
1answer
19 views

Max flow min cut in matching reduced to max flow

I can not find the max flow, min cut in this graph where all edges have capacity 1. The graph: 1 The max flow in this graph from s to t is 2? But it is impossible to separate s and t without cutting ...
0
votes
0answers
14 views

The criterion of the number nullability

There are $n$ charged balls lying separately. It is known that the sum of the charges is zero. There is a natural numbers subset $M$. In one move it is allowed to choose the number $k$ from $M$, take ...