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

23 views

24 views

### For What Families of Subgraphs, the Subgraph Isomorphism Problem Can be Solved in Polynomial Time?

Are there families of subgraphs that are arbitrarily large and are still easy to match in a larger graph ? By a "family" I mean a graph sequence $\mathcal{G}=\{G_1,G_2,\ldots,G_n,\ldots\}$ which is ...
44 views

### Infinite sums and squaring the plane, or sort of

This question is regarding two algorithms for squaring/almost squaring the plane. the Henles' method of squaring the plane. pdf here my method of tiling $n^2$ squares. I worked out* a simple gap-...
19 views

### Pseudocode and loop invariant of the searching problem

I hope it's apt to ask questions about algorithms here in MSE. Prelude: I am absolutely new to formal understanding of algorithms, though I had been overusing the word "algorithms" in programming ...
25 views

### Existence of a fixed point for a linear stationary iterative method

Suppose you are attempting to solve $Ax = b$ using linear stationary iteration method defined by $$x_k = G x_{k-1} + f$$ that is consistent with $Ax = b$, i.e., for which $f = (I - G)A^{-1}b$. Suppose ...
30 views

### What does 2n + 1 in long multiplication mean?

Having got some basics down in regard to addition and explaining it in terms of primitive operations, I am now again stuck on understanding the more complicated long multiplication. I have read in ...
39 views

### Mills Test Running Time

Can Miller's Test be replaced with the bound below in hopes that it would make a faster general-purpose primality test (compared to ECPP). If $n$ is an $a$-SPRP for all primes $a$ $<$ ($\log_2 n$)...
12 views

### For each of the functions, how to calculate a subgradient of the function at a given $x$.

We have $$f(x)=1/2||Ax-b||_2+||x||_2$$ where $A\in \mathbb{R}^{m\times n}$ and $x\in \mathbb R^n$ and $$f(x)=\inf_y||Ay-x||_\infty$$ where $A\in \mathbb R^{m\times n}$ and $x\in \mathbb R^n$
45 views

### Find a path from $s$ to $t$ with smallest “bottleneck”

Let an undirected graph, $G=(V,E)$ with weights defined by the function $w:E\to\mathbb{N}$ and for each edge: $1\le w(e) \le |V|$. You are given two vertices: $s,t\in V$. Find a path from $s$ to $t$ ...
28 views

### Recurrence: Theta of t(n) = 4t(n-1) -15

First let me start off by saying that I am using the substitution method to solve this equation.Although any other methods will be welcomed, this is just the particular method I feel comfortable with. ...
22 views

### Finding an MST among all spanning trees with maximum of white edges

Let an undirected graph $G=(V,E)$ with the color property $c(e)$ for every edge (could be black or white) and a weight property $1 \le w(e) \le 100$. Find the MST from the set of all spanning trees ...
33 views

47 views

### Is there a known fast algorithm to find the $k^\text{th}$ root modulo a prime?

I was trying to write an algorithm, but I got stuck at a point. Is there a known computationally fast algorithm to find kth root of an integer modulo a prime n, with k being odd and coprime to n. I ...
20 views

### Find a set of vertices $U\subseteq V$ included in some simple cycle

Let $G=(V,E)$, an un-directed graph. Find an efficient algorithm to return a $U\subseteq V$, where $u\in U$ is in some simple cycle of $G$. So basically we've learned in class about the $low$ ...
56 views

### Is Frank Wolfe a descent algorithm?

A colleague was explaining to me that the Frank-Wolfe algorithm is a descent algorithm (i.e. its objective value decreases monotonically at each iteration). However, when I tried simulating it, my ...
21 views

### For every $v\in V$, determine if it belongs to some negative cycle in $G$

Let $G=(V,E)$ a directed graph with a weight function $w:E\to\mathbb{R}$. For every $v\in V$, determine if $v$ belongs to some negative cycle. Obviously we need to utilize Bellman-Ford algorithm for ...
10 views

### Estimate the complexity for number times the function n/ lgn will be called recursively such that the result is a constant c = 2?

Cormen exercise $3.6$ which defines recursive function $f(i)$ such that $i$, $i \ge 0$ and the function is recursively called on itself $f(….f(i))$ such that it reaches a constant $c= 2$. Please help....
76 views

### I am looking for a mathematical equation to warp an image [closed]

Theoretically, I know that to warp an image, each pixel $(x,y)$ in the source image is transformed to $(x', y')$ using a function f (i.e. $x'=f(x,y)$ & $y'=f(x,y)$ ). But what mathematical ...
15 views

### 2D Bin Packing with Ordering Along One Dimension

This is my second attempt at solving this particular problem (original is here: Topological sort into a limited number of bins, each with limited capacity). For clarity, I have reproduced the relevant ...
29 views

### Growth function and one misunderstanding point?!

I have a question about Growth and Asymptotic notation topic. My question is as follows: $2^n$ > $n^{log_2{(n)}}$ is True. anyone could say how we can deduce that this fact is true?
28 views

### Monte Carlo Search Tree iterations

I have had this example in my exam last week and I can not figure out how to solve it. I have watched lots of tutorials on Monte Carlo Search Tree but I can't still understand this algorithm properly. ...
34 views

### Construct a weighted graph under the following conditions:

I need to construct a weighted graph of which neither of the Greedy Algorithms produces a correct answer to the Traveling Salesman Problem. Greedy Algorithms 1) Nearest Neighbor Works as ...
Problem There is a $N$ by $1$ long card consisting of $N$ square cards, each having the number $1, 2, \cdots, N$ regardless of the sequence of cards. Find whether or not the long card could be in ...