# Tagged Questions

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

19 views

### Enumerating (some) combinations of elements subject to a constraint

Consider this variant of the knapsack problem: I own an outdoor goods store, and hikers come from miles around because of my amazing variety of products for sale. There are 4 popular hikes in the ...
35 views

### algorithm problem: MxN matrix such that each element is from {0,1}

the question is the following: let $A$ be a matrix $m \times n$ such that each element is either $0$ or $1$ and each row has exactly $5x$ "$1$"s in it and each column has $5y$ $1$'s in it ...
55 views

### $L\in P$ prove that $L^*\in P$

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$ prove that $L^*\in P$ (L is a language and P is the class of all problems which can be decided by a ...
30 views

### calculating max n so that a has nth root over $\mathbb{Z}$

is there a nice (fast) way to find the maximal n so that for $a \in \mathbb{Z_+}$, $a^{1/n} \in \mathbb{Z}$ ? The only algorithmn which i know is brute Force. Greetings
16 views

### Maximizing the total viewership of the posters using Dynamic Programming

You must advertise your sorority’s big party along an M foot-long corridor. There are bulletin boards at positions x1,x2, . . . ,xn along this corridor (in sorted order from north ...
51 views

### Prove there's no such algorithm

Prove there's no algorithm which gets $\varphi$, a formula without free-variables as in input and returns a formula of the form $\varphi ' =\exists x_1,\ldots,\exists x_n \psi$ where $\psi$ is a ...
47 views

### What is the required group theory knowledge needed to understand Verhoeff's algorithm?

The Wikipedia page tells me I need to understand permutation groups and dihedral groups. Can someone clearly outline what exactly the perquisites of understanding this is and how much time I'll take ...
44 views

### self teach algorithms [closed]

What are some good resources to self teach the subject of Algorithms for someone with background in mathematics? That is, does there exists a more theoretical and abstract approach versus practical ...
21 views

### First Intersection Of Periodically Repeating Intervals

I have a set of coupled tasks, let's say $M$ of them. The $ith$ coupled task is represented as the following 3-tuple $\{A_i,D_i,B_i\}$ where $A_i$ represents the time it takes to perform the first ...
44 views

26 views

### What would be the formula to get the position of a combination, instead of a permutation ,given an index in this example

Let be an array A = {a,b,c,d,e,f} of six elements and we want three elements at the time, so the total number of permutations with repetitions will be: 6^3. Now to get the position of those ...
41 views

### Number of integer solutions of an equation $x^3 + y^2 = k$ [closed]

Given equation $$x^3 + y^2 = k$$ How can one count efficiently a number of integer solutions?
19 views

### Is there a minimum spanning tree including $e$ after removing at most $k$ edges?

Let an undirected, connected graph $G=(V,E)$ with the weight funciton $w:E\to \mathbb{R}$, an edge $e$, and $0<k\in\mathbb{N}$. Describe an algorithm determines if there are at most $k$ edges could ...
55 views

### Maximum number of non-intersecting lines

Given a polygon with $n$ vertices as $P_1,P_2,\ldots,P_n$ and a point $A$ in 2D space, what algorithm can I use to determine how many of the segments $\overline{AP_i}$ do not intersect an edge of the ...
21 views

21 views

### Red-black tree insert

I'm currently trying to figure out this exercise (sorry for link to image, it's for the red-black trees): http://i.imgur.com/IKMCkVf.png And I do know that the correct one is number three from the ...
37 views

### Algorithm to order and partition a set of of (n,m) pairs with constraints.

I ran into this problem while looking at Google API distance matrix service. Say you have a collection of a few million (origins, destinations) unique pairs/2 column table like (address, zip) for ...
23 views

### Max Flow Min Cut - Prove that $e$ crosses some minimal cut

I already asked about the opposite direction but I'm really confused about it, so I'd like to get some help please: Let's assume we have a flow network $G$ and some edge $e$. Now, Let's assume ...
14 views

26 views

### Computing unknown matrix norm

Suppose that we have a unknown vector norm but there is a machine that get a vector and correctly tell us the norm of the vector. Is there any algorithm to compute the matrix norm corresponding to ...
35 views

### Variation of TSP - Revisit Nodes

I have a problem where I have an symmetric graph and I want to find that shortest path that visits every node at least once (not exactly once). In order to solve this problem, I have found that we ...