texts: Does a reduction from sorting imply an $\Omega(n \log n)$ time bound?

texts:
I have come across a proof where a certain function ("compute a straight skeleton") is shown to take $\Omega(n \log n)$ time by reducing the problem of sorting to it. The overhead for the reduction itself is linear, thus negligible.

Now my question is: is this a valid argument?

The original proof appears in: Huber - Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice, page 19, last paragraph.

In summary:

Given a list of $n$ natural numbers, the author constructs a "Polygon with holes" $P$ of structural size $O(n)$ in linear time. The algorithm then computes a straight skeleton $S(P)$, which can be traversed to enumerate the original numbers in sorted order (with constant overhead per number). Thus, the problem of sorting is reduced to computing $S(P)$. The author claims that this implies computing $S(P)$ is in $\Omega(n \log n)$ due to the bound for sorting.

It is well know that comparison-based sorting algorithms have $\Omega(n \log n)$ worst-case bounds. However, there are $O(n)$ sorting algorithms such as radix sort or bucket sort which aren't based on comparisons and for which this restriction doesn't apply. As far as I can tell, these are all restricted to certain domains, such as fixed-length integers or strings.

I assume generalizing these algorithms to unrestricted domains would reveal hidden costs. If we consider arbitrary integers, some operations which are assumed to be constant cost would actually be logarithmic in the size of the integer. I don't know, however, if this necessarily has to be the case for all possible sorting algorithms.

I think the author's construction could be used for sorting real numbers (possibly requiring a variable-length encoding), if this strengthens the requirement on the sorting enough to rule out any $O(n)$ (or $o(n \log n)$) sorting algorithms.

Are there any information theoretic arguments showing that, for fully general inputs and all operations strictly accounted for, at least $\Omega(n \log n)$ basic units of work (whether they be comparison or something else) are always needed? If not, does that mean the argument of "by reduction from sorting" doesn't strictly prove a lower bound stronger than $\Omega(n)$?


texts: How to prove {a^(n^2) | n>0} is not context-free?

texts:
So I have a language:
$$
L = \{a^{n^2} \mid n > 0\}
$$
I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'm sort of doubting its validity.

So I take a pumping length $p$ such that a word $a^{p^2}$ can be split into 5 parts $uvxyz$. I need to assume that $L$ is context-free and run through some cases and check if the word violates the pumping lemma or if it doesn't violate the pumping lemma but isn't in the language definition.

I know the concept of proving languages aren't context free and the pumping lemma but I'm very stuck applying it to this particular language.

What do I do?


texts: A Myhill-Nerode type characterization of the regular languages using fooling sets?

texts:
Ultimately, my question is whether it's possible to exactly characterize the regular languages in terms of fooling sets. To help explain my motivation for asking this, here's a quick exposition.

Let $L$ be a language. A set of strings $S$ is called pairwise distinguishable relative to $L$ if for any two distinct strings $x, y \in S$, there is a string $w \in \Sigma^*$ such that exactly one of $xw$ and $yw$ belongs to $L$.

Assuming the axiom of choice, the Myhill-Nerode theorem can be framed in terms of pairwise distinguishable sets:

  Theorem: let $L$ be a language. Then $L$ is nonregular if and only if there is an infinite set $S$ that is pairwise distinguishable relative to $L$.

Now, let's consider a related definition. If $L$ is a language, a set $S \subseteq \Sigma^* \times \Sigma^*$ is called a fooling set for $L$ if for any distinct pairs $(x_i, y_i), (x_j, y_j) \in S$, then $x_i y_i \in S, x_j y_j \in S$, and at least one of $x_i y_j$ and $x_j y_i$ isn't in $L$.

I'm curious whether the following statement is true:

  Conjecture: let $L$ be a language. Then $L$ is nonregular if and only if there is an infinite set $S$ that is a fooling set for $L$.

I can prove one direction of this using the Myhill-Nerode theorem: if there is an infinite fooling set $S$ for a language $L$, then we can take the first halves of each pair in $S$, gather them into a set $S'$, and we'll have an infinite set $S$ that is pairwise distinguishable relative to $L$, so $L$ is nonregular.

However, I keep getting stuck trying to go the other way. I'm not sure how to show that if $L$ is nonregular, then there must be an infinite fooling set for $L$. The equivalent direction of the Myhill-Nerode theorem follows by the contrapositive and the fact that the binary relation "is indistinguishable relative to $L$" is an equivalence relation. We don't - I believe - have a similar equivalence relation when it comes to fooling sets.

Does the other direction of implication hold here? Or is this a strictly weaker criterion than the Myhill-Nerode theorem?

Thanks!


texts:
On one hand, it seems to make no sense, because of the following:

When expanded, the claim $f(n,a) \in O(n/a)$ would be

  There exist $C > 0$, $n_0$, and $a_0$ such that if $n \geq n_0$ and $a \geq a_0$, then $f(n,a) \leq C \cdot n/a$.

Now, given any $\epsilon > 0$, we can find an $a_\epsilon \geq a_0$ such that
$C \cdot n_0/a_\epsilon < \epsilon$, and thus $f(n_0, a_\epsilon) < \epsilon$.

So for any $\epsilon$, there is an input, with $n = n_0$ and $a = a_\epsilon$, at which the algorithm takes less than $\epsilon$ time to run.
But any nontrivial algorithm performs at least one operation, regardless of the input. So this seems nonsensical.

On the other hand, you can imagine someone saying that some approximation algorithm runs in time "$O(n/a)$", where $n$ is the size of the input and $a$ is the maximum multiplicative error.

And in fact, there is a paper in which an algorithm is claimed to run in "$\tilde{O}(\frac{n}{A^3 \epsilon})$" time. (Yes, I know $\tilde{O}$ is different from $O$). I asked a longer question about that
here. This question is an attempt to isolate the core confusion there.


texts: Difference between substitution, morphism, and homomorphism

texts:
In closure properties, I got confused between substitution and morphism.

1) According to Wikipedia, string substitution means to map letters in a set of alphabets to languages (possibly in a different alphabet), that is, $f(a) = L_a$.  Does that means to replace a letter with a language? Or replace 1 letter from a set of alphabets with 1 letter another set of alphabets?

2) According to Wikipedia, string homomorphism means to replace each letter with a single string, that is, $f(a) = s$, where $s$ is a string. What does 'a single string' mean? Does this mean the letter 'a' may be replaced by a string such as 'owl'? A webpage says that homomorphism is a group maps, which make me even more confused. What's the difference with substitution?

3) I thought that if $\left| f(a) \right|=1$, it's called morphism. Then this is not a string but only a letter. Are morphism and homomorphism the same thing?

I am a beginner and really confused. Hope somebody can help me clear this confusion, as well as the difference in proving the closure properties of substitution, homomorphism, and morphism. Your knowledge and help are very appreciated.


texts: Minimize the maximum Hamming weight of basis vectors spanning a binary subspace

texts:
In the course of my research, I stumbled upon a problem which can be recast as the following decision problem:

First some notation:

Let $\mathbb{F}=\{0,1\}$ be the binary field. For $x\in\mathbb{F}^N$, $N\in\mathbb{N}$ arbitrary, let $w(x)$ denote the Hamming weight of $x$, i.e., the number of non-zero components.

Let $B\subset \mathbb{F}^N$ be an arbitrary set of binary vectors. Define the Hamming weight of $B$ as $w(B)\equiv \max_{b\in B}w(b)$.

Now the problem:

  Given a linear subspace $V\leq \mathbb{F}^N$ and a positive integer $C\leq N$.

  Is there a basis $B$ of $V$ such that $w(B)\leq C$ ?

The "size" of a particular instance is the dimension $\rm{dim} V=K\leq N$, as the brute-force solution requires the computation of $w$ for all possible bases of $V$.

Clearly, the evaluation of $w(B)$ requires $\mathcal{O}(KN)$ steps; therefore the problem is in NP.

As an example: If $V=\mathbb{F}^N$ and $C\geq 1$, the answer is positive as the standard basis ($e_i=(0,\dots,1,\dots,0$) has hamming weight 1. Obviously this is not the case for generic, non-trivial subspaces $V$.

I think the problem is closely related to the theory of linear binary codes (in fact, $V$ is one). In this context, however, people seem to be more interested in the minimum Hamming weights as these relate to the Hamming distance of the code.

As my understanding of and experience in complexity theory is rather sparse (my background is condensed matter physics), I do not know wheter this problem is known in complexity theory. If so, what is its complexity class (time complexity) ? Are there any relevant publications for this particular problem?
Maybe it's even a simple textbook problem?

Any hint is welcome. Thanks in advance.


texts: Is a set system an independence system, if and only if it is an accessible system, and has the Interval Property without Lower Bounds

texts:
From Wikipedia,
a finite matroid $M$ is defined to be $(E,F)$, where $E$ is a finite set  and $F$ is a family of subsets of $E$, so that it satisfies

either nonempty, the hereditary property, and the augmentation property:
or an accessible system, the augmentation property, and the interval property without lower bounds.

The two definitions should be equivalent. Do we need the augmentation property, for the following to be true:

  a set system $(E,F)$ is nonempty and has the hereditary property, if and only if it is an accessible system, and has the Interval Property without Lower Bounds?

Without assuming the augmentation property, it is simple to see that the "only if" part is true, but I wonder if the "if"part is also true?
Thanks and regards!

Note:

A set system $(E,F)$ that is nonempty and has the hereditary property is also called an independence system.

The aforementioned properties are defined as follows:

The empty set is in $F$. (nonempty property)
if $X \in F$, then every subset of $X$ is also in $F$. (The hereditary property)
for all $X,Y ∈ F$ with $|X| > |Y|$, there is some $x ∈ X-Y$ such that $Y∪{x} ∈ F$. (The augmentation property)
Every nonempty  $X  \in F$ contains an element $x$ such that $X-\{x\} \in F$. (I.e. $(E,F)$ is an accessible system)
If $B, C ∈ F$ with $B ⊆ C$, then, for all $x ∈ E-C$, $C∪\{x\} ∈ F$ implies $B∪\{x\} ∈ F$. (the Interval Property without Lower Bounds)


texts: From connected voxels to polyhedron in linear time?

texts:
I have a polyhedron defined as a set of connected voxels (from a 3D array). I'd like to get a representation of this polyhedron by its polyhedral surface (since it's going to be much sparser). Can I get that in quasilinear time? Do I need my set of voxels to be represented in a particular form?

I don't even know the answer for the same question in 2D (getting the contour from a set of connected pixels) and if the results are identical.

Bonus points: If you happen to know if such a quasilinear algorithm is implemented in CGAL feel free to tell me ;)


texts: I am reading the following paper https://pdfs.semanticscholar.org/5e86/db52119d2d691af0365cdba7bb27dc0dc303.pdf and trying to implement the tabu search algorithm they describe for image segmentation. In page 2 of the paper, in step 4 and 6 of the algorithm HTS, they say that if certain conditions are met "then $z_{ij}(t+1)$ with probability" or for example "accept $z(t+1)$ as Tabu image with probability". What exactly does this phrase of "with probability" mean? Can anyone give me some reference to read about this? Where can I find more information about this and how can I implement it in my code? Thanks!


texts: How to find diffrenet ways to implement merge and delete_min operation in binomial heap?

texts:
I have searched on the internet to find different ways to learn binomial heap operations. What I have found is not quite helpful for me.For example, for delete min operation the algorithm says:

Search through the roots of binomial trees and find the smallest key and call it x.Remove the x from the tree.
Create a new empty heap H'.
Reverse the order of x's children and set the head of H' to point to the head of the resulting list.
Merge H' with H.

On paper everthing seems logical and understandable. I also use some visualization websites-like this- to see how things work yet when it comes to coding -especially with C- things start to be seen harder. I could find some codes written in C and I also used them in my projects but I am not satisfied since I couldn't understand them fully.Writing and using these algorithms makes me feel inadequate for my future job.
Also for other algorithms I don't know how to understand algorithms and put them in code-I don't even know how these things will help me in 21st century's corporate world-.
My questions is how should I approach these powerful algorithms and use them?


texts: Increased rounding relative error when subtracting

texts:
I'm reading the book "Lessons in Scientific Computing" by Schoerghofer and it says:

  If x and y are real numbers of the same sign,
  their sum x + y has an absolute error that adds the two individual absolute
  errors, and the relative error is at most as large as the relative error of x or y. Hence, adding them is insensitive to roundoff. On the other hand, x−y has increased relative error.

I am not sure how to obtain the result for subtraction, i.e. how to show for
$$
x(1+\epsilon_x)-y(1+\epsilon_y) = (x-y)(1+\epsilon)
$$
that $\epsilon\ge\max(\epsilon_x,\epsilon_y)$.


texts: Can you form a group with assembly instructions under the MIPS-32 architecture?

texts: Would it be possible to form such a group using the ADD instruction and the NOT instruction?


texts: Algorithm for intersection point between two vectors

texts:
I'm trying to learn Computational Geometry and this formula isn't obvious to me.
Hint: cross is related to the cross product of two vectors.
# Returns intersection of infinite lines ab and pq (or undefined)
point intersect(point a, point b, point p, point q):
    d1 = cross(p - a, b - a)
    d2 = cross(q - a, b - a)
    return (d1 * q - d2 * p) / (d1 - d2)


texts: Algorithm for blindly navigating a physical labyrinth

texts:
I was recently in Maastricht and visited the caves and tunnels that lie under the city. (http://www.atlasobscura.com/places/fort-saint-pieter) While on a tour we were told that on numerous occaisions people have lost their light sources and have been unable to make their way out.

https://nltimes.nl/2015/08/05/21-hour-ordeal-lost-maastricht-students-rescued-cave

This made me wonder: is there an algorithm that you would be able to physically execute in real life, having found yourself in a similar situation.


texts: Is there an algorithm for getting the boundary of a non-planar graph?

texts:
This is my first question here!
If I have a non-planar graph where every vertex connects to 3 other vertices, and where the edges are allowed to intersect, how do I find the boundary of the graph?
For example in the below graph, the pink line shows the boundary of the graph which needs to be found. The boundary should also not intersect, with it self.

Is there anything in graph theory which would help with this?


texts: Difference between "data dependence graph", "data dependency graph", and "data flow graph"

texts:
Is there a difference between a "data dependence graph" and a "data dependency graph"? I have seen both terms - sometimes used interchangeably sometimes not.

To make things even more complicated, a "data dependency graph" is sometimes also called a "data flow graph" (see e.g. here).

The term "data dependence graph" is, for example, used on the second slide here.

If there is a difference, could someone give an example of each graph type?
If there is no difference, why the two different terms?


texts:
Consider two 2D-Array $B_{ij} $ (the buy array) and $S_{ij}$ (the sell array) where each $i^{th}$ element is associated with an array of floating-point values and each of the floating point value, in turn, is associated with an array of integers.

For example

B = [
  0001 => [ 32.5 => {10, 15, 20},
            45.2 => {48, 16, 19},
            ...,
            k1
          ],
  0002 => [ 35.6 => {17, 35, 89},
            68.7 => {18, 43, 74},
            ...,
            k2
          ]
]

and similiarly for the sell array.

This is akin to an order association system of a stock/commodity exchange

BuyOrderBook = [
                 CompanyName => [
                                 Price1 => [Qty1, Qty2...],
                                 Price2 => [Qty1, Qty2...]
                                ]
                 SecondCompany = [...]
               ]

What is the fastest way known to solve the following problem:

  Input: Buy array $B$, Sell array $S$
  Problem: Decide wether there are $(c_1 \Rightarrow p_1 \Rightarrow q_1) \in B$ and $(c_2 \Rightarrow p_2 \Rightarrow q_2) \in S$ with $q_1, q_2 > 0$ and $p_2 \geq p_1$.

In short, what is the fatest way of matching orders for an exchange?

Update in response to comments

Lets say, MSFT has 25 shares @ \$60 to be sold and there is buyer who is willing to offer \$61 for 10 shares of MSFT. Then the buyer gets 10 shares @ \$60 and the buy order book becomes empty while the sell order book now is updated with new quantity - 15 shares @ \$60.

Now take the reverse case, MSFT has 25 shares @ \$60 to be bought and there is seller who is willing to receive \$61 for 10 shares of MSFT. Then the trade will not be executed because seller is demanding a minimum of \$61 and the buyer is offering a maximum of \$60. The orders are now stored and await until new orders are received.

(This is the limit order principle, where the seller specifies minimum price at which he is willing to sell at and buyer specifies maximum price at which he is willing to buy).

Post execution, the sell order book will be (25-10)=15@86.5 while buy order book will be empty (10-10)=0.


texts: Counting $k$-Colorings $\mathcal{O}(\phi^{n + m})$ Solution

texts:
Given an undirected graph $G = (V, E)$ with $n$ vertices and $m$ edges, how many $k$-colorings of $G$ exist? A $k$-coloring is a function $c: V \to \{ 1, 2, \dots, k \}$ such that $c(u) \neq c(v)$ for all edges $\{ u, v \} \in E$. Let $f(G, k)$ denote the number of $k$-colorings of $G$.

There is a well-known formula, sometimes called Fundamental Reduction Theorem:

$\displaystyle f(G, k) = f(G - e, k) - f(G\,/\, e, k)$ for all $e \in E$.

Note that $G - e$ is $G$ without edge $e$ and $G\,/\,e$ is $G$ with edge $e$ contracted.

Using this formula, it is easy to figure out a recursive algorithm. We just need to choose an arbitrary edge and recurse on $G - e$ and $G\,/\, e$. The base case is a graph without edges. If $T(n + m)$ denotes the time complexity, we have $T(n + m) \le T(n + m - 1) + T(n + m - 2)$ which is just fibonacci recurrence and establishes a time complexity of $\mathcal{O}(\phi^{n + m})$ where $\displaystyle \phi = \frac{1 + \sqrt{5}}{2}$ denotes the golden ratio. So far, so good.

But we made an assumption: Can $G - e$ and $G\,/\,e$ really be obtained from $G$ in $\mathcal{O}(1)$ time? It seems like we cannot avoid a polynomial factor:

If $G$ is represented by an adjacency matrix, vertex removal (needed for contraction) does not shrink the matrix and we always need $\mathcal{O}(n)$ time to access the edges of a single vertex. And another problem: How to select an arbitrary edge fast?
If $G$ is represented by adjacency lists, edge removal is fast. But edge contraction requires moving/copying neighbour vertices to another adjacency lists which is expensive.
If $G$ is represented by an edge list, edge selecting is fast. Edge removal is also fast, because the edge is arbitrary and we can always take the first edge in the list. But again, edge contraction causes many edges to be updated (i.e. assigned another endpoint)...

Is there a way to really achieve $\mathcal{O}(\phi^{n + m})$ without a factor of $n$, $m$ or $n + m$ using an appropiate data structure or modification of the algorithm?


texts: Is there a name for a graph whose vertices consist of edges of an existing graph connected by an edge if they shared a common vertex?

texts:
I was wondering if there is a name for this construction:
Take a graph $G$ and construct a new graph $G'$ in which the edges of $G$ now become vertices, and "vertices become edges" in the sense that vertices are joined by edge in $G'$ if they as edges in $G$ shared a common vertex.

More precisely:
Given a graph $G=(V=\{v_1,v_2,\dots,v_n\},E=\{e_1,e_2,\dots,e_k\})$ where each $e_i=\{u,v\}\subset V$ we define the graph $G'=(V'=\{e_1,e_2,\dots,e_k\},E')$ so that $\{e_i,e_j\}\in E' \iff e_i\cap e_j\neq\emptyset$.

I don't know if this can be used for anything (my guess would be it can't) it just came to my mind and thought that perhaps this has a name.


texts: What would remain of Quantum Computing if quantum states were real numbers?

texts:
This question is motivated by my attempt to understand quantum computing and the source of its computational power.

Quantum statest are described by complex numbers. That is, 1 qubit is described by 2 complex numbers, one for each state (actually 1 complex number, due to the constraint and the invariance).

Quantum phenomena are  explained by the fact that quantum states consists of probability amplitutes (complex numbers) rather than actual probabilities (real numbers).

My question is, what if we would consider an alternative "pseudo-quantum" system, the states of which, unlike classical physics, still consist of a distribution over classical states, only it is now real-valued rather than complex-valued. What would remain of quantum computing (or "pseudo-quantum computing")?

One thing that would remain is that the number of dimensions in the system would still exponentially increase w.r.t. the number of pqubits (pseudo-qbits), which as far as I understand is one source of the power of quantum computing. That is, it would allow correlations/entanglement, contrary to classical computing, but I am not sure if this actually matters for comoutational power.


texts: BFS implementation: queue vs storing previous and next frontier

texts:
The most trivial implementation of BFS would simply store the last frontier (open list), build the new frontier, and then replace the last frontier with the new (like in the example python code below). But almost universally, the first algorithm shown for BFS in textbooks is the queue-based implementation.

What's the disadvantage of the simple frontier-storing approach? I can see it might use slightly more memory (effectively storing the new frontier while the old is still in memory), but usually textbooks only care about big-O complexity. Is there any other problem with it?

# example of a graph
g = {1: [2, 3], 2: [1, 3], 3: [1, 2, 4], 4: []}

def bfs(g, root):
    yield root
    boundary = [root]
    visited = {root}
    while boundary:
        new_boundary = []
        for v in boundary:
            for w in g[v]:
                if w not in visited:
                    yield w
                    visited.add(w)
                    new_boundary.append(w)
        boundary = new_boundary


texts: $Sat(EG^2\alpha)$ as a fixpoint of an operator

texts:
Currently I am studying CTL model checking. I found this exercise:
Consider the CTL formula $EG^2(\alpha)$ which means that there exists a path that satisfies $\alpha$ at every even position. Define $Sat(EG^2(\alpha))$ as a fixpoint of an operator and describe how to extend the CTL model checking algorithm for formulas that contain the operator $EG^2(\alpha)$.


texts: Copy on write is an interesting idea used on server systems. Does it make any sense on a smartphone?

texts:
The data pages that are actually modified need to be copied. This approach, called copy on write, improves performance by reducing copying.

According to me it is unnecessary as every process has its own data. (not sure) A third process working with that data is really not possible.

Please tell me if it's possible, if possible then why? Also an example where this will be helpful would help.
Thank you.


texts: I built a mechanical computer powered by marbles. What are its theoretical limitations?

texts:
Over the last couple years, I built a mechanical computer powered by marbles and made a game out of it. It's similar to the old Digi-Comp II, except for two key differences:

Parts are repositionable on the board.
You can connect multiple 'bits' together using gears. When one of these bits is flipped, it flips the other bits connected to it.

The above link describes how it works. My question is, what are its theoretical limitations? My theoretical computing background is weak, so please ELI5.

edit: I'm not interested in the obvious limitations: speed (not going to win any races there...), board size, or # of marbles. I'm more interested in its theoretical limitations. Maybe it would help to split it into two questions:

How can it be proven (or disproven) to be Turing-complete?
If more than 3 gear bits are connected together, the friction becomes too great for a marble to turn all of them at once. Does that create additional limitations?

Thanks - I'm really excited to read your answers! I've been thinking about this for a long time.


texts: Prove that $TQBF \notin SPACE(n^{\frac{1}{3}})$

texts: I would like some hints on how to approach this problem, I know for instance that $TQBF$ is $PSPACE$-$Complete$, so it can solved in poly space and any other $PSPACE$-$Complete$ problems can be log spaced reduced to $TQBF$. I believe that I need to employ the space hierarchy theorem in some way but I am not sure how, this is a homework question so I just want a hints. Thank you!


texts: Can I say θ(g(n)) is the intersection of Ω(g(n)) and O(g(n))?

texts:
Let's say Ω(g(n)) be a set representing the lower bound and O(g(n)) be another set representing the upper bound for some function f(n).

Can I say that θ(g(n)) is the intersection of these two sets?

The only reasoning I could give for it is that:

Ω(g(n)) is set of all the functions whose running time is at least cg(n) for some c>0.
O(g(n)) is set of all the functions whose running time is at most cg(n) for some c>0.
θ(g(n)) is the set of all the functions whose running time is in between c1g(n) and c2g(n) for some c1,c2>0.

which kind of looks like it is the intersection of both the sets.


texts:
I am reading about B-Tree through CLRS. One of the exercise problem is to express maximum number of keys in a BTree of height $h$ and minimum degree $t$.

Properties of BTree of $t$:

$t\ge 2$
Min. no of keys in a node is $t-1$ and max. number of keys in a node is $2t-1$
Max number of children a node can have is $2t$

To solve it the formula I came up with is $$\sum_0^h (2t)^h(2t-1) $$

Does it have any convergence?


texts: Average number of collisions before successful insertion into hash table

texts:
I want to compute the average number of collisions before sucessfully adding an item into a hash table. Let $m$ be the size of a hash table $H$.

I was thinking that since it is a linear probing and we do not know where the free slots in the hash table are, the probability that first slot is free is $(m-n)/m$ where $n$ denotes the amount of 'bad' slots, i.e. there are $n$ items stored in our hash table.
If the second slot is free then $(m-n)/(m-1) > (m-n)/n$ and so on.

So the expected number of collisions is $1/p = 1/ (1-\alpha)$ where $\alpha := n/m$ is our load factor.

But my friends got totally different numbers. Am I going into the right direction?


texts: Finding the rectangle with maximum perimeter weight in a 2D array

texts:
[Problem Description]:

Given an array of size $N \times N$, the task is to find the rectangle with maximum perimeter weight in the array. The perimeter is defined as the number of cells on the sides. The perimeter weight of a rectangle is defined as the sum of all the values lying on the sides of the rectangle.
For example, the above image shows an array of size 5*5. Each cell has a value. The pink cells form the perimeter of the rectangle with upper left cell (0,0) and lower right cell (2,3). The perimeter is 10. The perimeter weight is (1-1+0+4+2+1+0+2-5-1) = 3
I am asked to give:
(1): an $O(N^3)$ algorithm to find a rectangle with the maximum weight.
(2): an $O(N^3)$ algorithm to find a rectangle with the maximum weight with perimeter no greater than a given constant L.
I really have no idea about how to do. Could anyone give me some idea about these 2 problems?
Thanks a lot in advance!


texts: Lectures and books for beginner to approach learning simulations

texts:
I'm an incoming undergrad with a math background up to single-variable calculus, but reasonably strong programming background through algorithms, data structures, web and mobile app development. Broadly, I'm really interested in learning to simulate molecular systems and game physics, etc, but have never simulated anything before. I'd also like what I learn to be transferrable to financial markets, climate models, etc--so really focusing on principles of simulation, analysis and motivation behind simulation algorithms, limits of simulations, and more.

I've gone through MIT OCW 6.0002, and spent some time learning about random walks and Monte Carlo methods, as well as frequenting a smattering of random pages on molecular dynamics, but I'd really appreciate some structured, motivated resources for an absolute beginner with a programming background to learn about using programming to simulate things.


texts: Pumping lemma for regular languages vs. Pumping lemma for context-free languages

texts:
How can I prove the next claim:
If a language $L$ meets the pumping lemma for regular languages then $L$ meets the pumping lemma for context-free languages?
(Without any pre-condition about the regularity of $L$)


texts:
This is the first time that I'm looking in depth into the topic, although I've always been curious.
Could someone let me know about online resources (courses, tutorials, etc) and books that cover the basics of the topic?
I'd like to explore both the theoretical part and the more practical part of Data Mining.


texts:
I have a simple context free grammar $(\{A\}, \{(,)\}, R, A)$, which consists of this one production rule:

$A \rightarrow AA\, \vert\, (A)\, \vert\, \epsilon$

I believe this is ambiguous! For example, I can represent "()" like this:

I'm sure there are an infinite number of these. I've attempted to make the grammar unambiguous whilst ensuring that the same language is accepted:

$A \rightarrow AA\, \vert\, B$
$B \rightarrow (C)$
$C \rightarrow \epsilon$

How can I be sure that this captures the same language and is no longer ambiguous?


texts: Does the term "continuity" have a different meaning in maths and in CS?

texts:
I ask this question because of some statements in the question "What is the 'continuity' as a term in computable analysis?" making me suspicious.
I'm engineer, not computer scientist, so I don't have the Turing machine but logic gates in mind when I'm thinking about algebraic operations performed with devices.
I read the answer to the question "Why are computable functions continuous?" and understood it the following way:

Because the device's input is of infinite length (a decimal number with an infinite number of digits after the decimal point), the device (e.g. Turing machine or computer) cannot read the entire number before writing the $n$-th digit of output.
Instead, the device can only have read $m(n)$ digits of the input when it writes the $n$-th digit of output.
If the first $n$ digits of the output of some function only depend on the first $m(n)$ digits of the input, the function is continuous.

However, if I understand this argumentation correctly, the word "continuous" in computation theory is not identical to the word "continuous" in mathematics:
Rounding towards zero would only require reading the input until the decimal point (so $m(n)=\text{const.}$); however, the mathematical function being calculated is not "continuous" according to the mathematical definition of that term.
We could also perform a digit-wise operation ($m(n)=n$) and exchange certain digits after the decimal point; for example replace all 4s by 9s and all 9s by 4s. As far as I understand, the function being calculated is not continuous on any interval of $\mathbb{R}$ (however, it would be right-continuous on $[0,\infty)$ and left-continuous on $(-\infty,0]$).
And if I didn't make a conceptual mistake and we use a balanced numeral system (like a Russian computer in the 1960s) instead of the decimal system, a similar algorithm (exchanging 0s and 1s instead of 4s and 9s) would even represent a mathematical function which is not even directional continuous on any interval of $\mathbb{R}$.
Questions:
Does the computability depend on the numeral system being used (as the example with the balanced numeral system suggests) or is the term "computable" even assuming a certain numeral system being used?
Is the observation correct that the term "continuous" does not have the same meaning in maths and CS?


texts:
hope it's possible for this question to be answered in an objective manner.

I'm not studying in a liberal arts college so basically I only get to study one subject. Which would be the better preparation for future research (probably grad school) into theoretical CS? The standard undergraduate math course with analysis and algebra, or the standard undergraduate CS course with algos and concurrency and the like.


texts: How many bits would be needed for the byte?

texts:
The Problem: A high speed workstation has 64 bit words and 64 bit addresses with address resolution at the byte level.  Assuming a direct mapped cache with 8192 64 byte lines, how many bits are in each of the following address fields for the cache?  1) byte 2) Index 3) Tag?

I know that an address for specifying data within a cache is 64 bits.
I know that an address  for a cache has to have the byte, index, and tag field so byte + index + tag = 64
The index field should take up 13 bits to account for the 8192 byte lines

How many bits would be in the byte field though? I know that a processor processes one word at a time and each word consists of 8 bytes. A 64 byte cache line would contain 8 words. Would this byte field need to identify each word or each byte itself. If it was byte itself, it be 6 bits but if it was word it be 3 bits.

If I had to take a stab, I would say the byte field needs to be 3 bits to identify each word because it doesn't make sense for the processor to just process one byte. Can anyone confirm my suspicisions?


texts: How many clauses are required for SAT to be NP-hard in CNF formulas?

texts:
It is not hard to see that SAT for a CNF formula with $n$ variables and a constant number of clauses can be solved in polynomial time. On the other hand, it is not hard to see that a CNF formula with $n$ variables and $O(n)$ clauses is enough for NP-hardness (consider for example the instances of SAT associated with the natural formula for 3-colorability, applied to planar graphs).
We could define this formally as $\text{CNFSAT}-f-\text{Clauses}$, a family of problems parameterized by a function $f$, in which instances are formulas in CNF such that if they have $n$ variables, then they have at most $f(n)$ clauses. Based on this, what I'd like to know is what is the smallest function $g$ such that we know there exists $f \in O(g)$ such that $\text{CNFSAT}-f-\text{Clauses}$ is already NP-hard. We know that g = 1 (constant # of clauses) does not work, and $g = n$ (linear number of clauses) works.
What about $g = \log n$? Is there a simple algorithm for CNFSAT over formulas that have $O(\lg \lg n)$ clauses?


texts: Substituting a term for a variable in a context

texts:
At this link you can read Nicola Gambino's slides on one way to approach the formal syntax of Martin-Löf dependent type theory. (They are concise and very readable.)
On slide 10, he gives a standard definition of a context as a list of the form
$$x_1:A_1, \ldots, x_n:A_n   $$ where the $x_i$ denote pairwise distinct variables.
Now, on slide 17, he gives a standard example of a structural rule for the type theory, often called the substitution rule:
$$ \frac{x : A, \Gamma \vdash J \quad a : A}{\Gamma[a / x] \vdash J[a / x]}   $$
where $J$ denotes a consequent of a generic judgment.
Note that $\Gamma$ is supposed to be a context in the premise.
But what exactly does $\Gamma[a / x]$ mean?
We need $\Gamma[a / x]$ to be a context for the conclusion of the rule to be a well-formed judgment, but just replacing the variable $x$ with the term $a$ may give $\Gamma[a / x]$ the wrong form since $a$ need not be a variable. Therefore, there seems to be an immediate issue here.
Could someone clarify the definition of substituting a term for a variable in a context?


texts: Maximum subset pairwise not divisible by $K$

texts:
I have a set of numbers, and want to calculate the maximum subset such that the sum of any two of it's elements is not divisible by an integer $K$.
I tried to solve this problem, but I have found the quadratic solution, which is not efficient response.
$K < 100, N < 10000$, where $N$ is the number of elements and $K$ is given constant. Is there better than quadratic solution?


texts: What is the minimal number of states for the DFA?

texts:
Let the regular expression $R = ((a^*\cup \emptyset \cup \varepsilon^*)^*b)^*$ above $\Sigma = \{a,b,c,d\}$. What is the minimal number of states for a DFA accepting this regex?

$1$
$2$
$4$
$5$ or more

So for my understanding, this regex is equivalent to $(a^*b)^*$. I was able to build the following DFA, nevertheless, I know the answer is $2$. How is it possible?


texts: Lower bounds for orthogonal matrix multiplication

texts:
Is it possible, according to the current state of knowledge, that orthogonal matrices can be multiplied faster than arbitrary matrices?
More precisely, let $T(N)$ denote the worst-case time of the fastest algorithm to multiply two arbitrary $N\times N$ matrices (in the real RAM model). Let $T_{\rm O}(N)$ denotes the worst-case time to multiply two orthogonal $N\times N$ matrices. Is there a proof that $T_{\rm O}(N) = \Omega(T(N))$?
It seems intuitive to me that $T_{\rm O}(N) = \Theta(T(N))$, but I couldn't come up with any proof. Below are my thoughts and failed attempt.

I became interested in this question at the prompting of a question on math stack exchange. It is easy to show that, for example, $T_{\rm S}(N) = \Omega(T(N))$, where $T_{\rm S} $ is the worst-case time to multiply two symmetric $N\times N$ matrices. This follows directly by reduction by embedding the arbitrary matrices $A$ and $B$ into the larger symmetric product
$$
\begin{bmatrix}
0 & A \\
A^\top & 0
\end{bmatrix}\begin{bmatrix}
0 & B^\top \\
B & 0
\end{bmatrix} = \begin{bmatrix} AB & 0 \\ 0 & B^\top A^\top \end{bmatrix}.
$$
However, the analogous emebedding of a matrix $A$ (normalized to be a contraction) into an orthogonal matrix
$$
A \mapsto \begin{bmatrix} A & (I - AA^\top)^{1/2} \\ (I - A^\top A)^{1/2} & -A^\top \end{bmatrix}
$$
requires at least $\Omega(T(N))$ operations to construct any way I am aware of, so I was unable to prove the result by the same embedding trick.
Is there a more clever proof that $T_{\rm O}(N) = \Omega(T(N))$?


texts: Faster way of calculating how many ways can $2n$ elements be paired?

texts:
So the problem is in how many ways $2n$ elements can be paired, my approach was multiply all odd numbers less then $2n$.

$(2n-1)*(2n-3)*...*1$
but my professor claimed it can be done much faster in algorithmic sense, but I don't really see the way to do so. Any hints? Thanks!


texts: Time-space tradeoff for missing element problem

texts:
Here is a well-known problem.

Given an array $A[1\dots n]$ of positive integers, output the smallest positive integer not in the array.

The problem can be solved in $O(n)$ space and time: read the array, keep track in $O(n)$ space whether $1,2,\dots,n+1$ occured, scan for smallest element.

I noticed you can trade space for time. If you have $O(\frac{n}{k})$ memory only, you can do it in $k$ rounds and get time $O(k n)$. In a special case, there is obviously constant-space quadratic-time algorithm.

My question is:

  Is this the optimal tradeoff, i.e. does $\operatorname{time} \cdot \operatorname{space} = \Omega(n^2)$?
  In general, how does one prove such type of bounds?

Assume RAM model, with bounded arithmetic and random access to arrays in O(1).

Inspiration for this problem: time-space tradeoff for palindromes in one-tape model (see for example, here).


texts: Is it possible to find a supersequence of a single array?

texts:
In Jeff Erickson's Algorithms textbook, the chapter on Dynamic Programming asks you to "Describe an efficient algorithm to compute the length of the shortest
oscillating supersequence of an arbitrary array A of integers".

A supersequence contains all of the elements from the original array X[1...n], and oscillating is defined as X [i] < X [i + 1] for all even i, and X [i] > X [i + 1] for all odd i.

However, I am not asking about the answer to this problem. I am just wondering if this question even is sound. How can you find a supersequence of a single array? Wouldn't the answer just be the length of the original array if all elements are oscillating? Else, 0. Usually, a supersequence is found between multiple arrays.


texts:
It's possible to return from a dpll algorithm M as maximum for MAX-SAT problem?:
I have a sample:
https://gist.github.com/davefernig/e670bda722d558817f2ba0e90ebce66f
we can modify recurrency to return the outcome of MAX-SAT?
Resources:
https://en.wikipedia.org/wiki/DPLL_algorithm


texts: Number of words within Hamming distance $\delta$

texts:
This is a problem I'm having reading Arora & Barak's book, page 378-379.  They define:

  For two words $x, y \in \{0, 1\}^m$, the fractional Hamming distance of $x$ and
  $y$ is
  equal to the fraction of bits on which they differ, i.e.  $\frac{1}{m} \cdot  |\{i : x_i \neq y_i\}|$, where the $x_i$ refers to the $i$-th bit of $x$ (same
  for $y_i$).

Now, in the proof of Lemma 18.9, they use the fact that

  for every string $y_i$ of $m$ bits, the number of strings
  that are of distance at most $\delta$ to it is ${m \choose \lceil \delta m \rceil}$

meaning that there are ${m \choose \lceil \delta m \rceil}$ words that disagree on not more than a $\delta$ fraction of bits.

But, I can't convince myself of that.
Suppose for simplicity that $y_i = 0000 \ldots 000$.  Here are the words that are of distance at most $\delta m$: all the words that have exactly one $1$, or two, or three, up to $\lfloor \delta m \rfloor$ of bits set to $1$.  Thus I rather think that this number is

$$
\sum_{k = 1}^{\lfloor \delta m \rfloor} {m \choose k}
$$

Can anyone explain?


texts: Random function "returns a uniformly distributed int". Does this mean the probability of every number is the same?

texts:
Most functions that generate random numbers are described as:

  Returns a pseudorandom, uniformly distributed int value between 0
  (inclusive) and the specified value (exclusive)

If I use it to generate a number in the range [0..9], does uniformly distributed mean that the probability for 3 and 8 is the same?

As I understand it, if I run the function a sufficient number of times, I'll have the same number of occurrences for each number, 0 through 9.  Is this correct?

Alternatively, would we instead have a normal distribution where we would get more occurrences of the numbers 4, 5, and 6, as they are closer to the mean and hence have a higher probability of occurring?


texts: Create automata from non regular grammar

texts:
I have two grammars:

 L → ε | aLcLc
 L → ε | aLcLc | LL

This two grammars are equals but the first one is regular, so it produces a regular language and a Finite State Automata. Instead, the second one is non regular but it might produces a regular language.
To prove it, I want to create two differentes automata: the first one should be a correct automata and if the second one can't be create then the language is not regular. Are all this statments correct?
If so, can someone help me build these two automata? Thank you!


texts: A context free grammar for the language of even-length non-palindromes

texts:
I am trying to find a context free grammar for the language

  $L = \{xy \mid |x|=|y| \text{ and } x≠y^R\}$

where $y^R$ is the reverse of string y and $x, y\in \{a,b\}^*$ . Here is a possible solution:
$G=\{V,Σ,R,S\}$
where
$V=\{A,B,a,b\}$
$Σ=\{a,b\}$
$R=\{S\rightarrow aSa|bSb|aBb|bBa,$
   $\ \ \ \ \ \ \ \ \ \ B\rightarrow aBa|bBb|aBb|bBa\}$

Is this correct?

I found a similar problem here.


texts:
Why an ARM processor with 32 bits address bus can address 4 billion different bytes?
I know that $2^{32}$ is equal to about 4 billions, but shouldn't it be 4 billion bits and not bytes?

Hence if I want to find how many different words it can address it should be $\frac{2^{32}}{8}$ so I will have the number of bytes, and if I want to find the number of words I divide it again by 4 (because a word in ARM is 32 bits = 4 bytes).


texts: Why integer division is of equal complexity as multiplication

texts:
I am trying to understand the fact that integer division is no more difficult than integer multiplication. I found some references - here and this lecture note. Wikipedia says if there is a way to multiply integers in time M(n), then we can divide them in CM(n). When I think of division a/b as finding
integers d and r such that a = bd + r, then this above fact somehow aligns with my intuition. But I could not find any way to mathematically prove this. Although the lecture note has proof, but I am not able to understand. Can anybody please give me a simple mathematical proof or any idea how to do it?


texts: Computer Vision - Algorithm for reconstructing tilted image

texts:
Recently I've seen this very good apps

https://play.google.com/store/apps/details?id=com.kingjim.shotnote&hl=en
https://itunes.apple.com/JP/app/id411332997?mt=8

this apps reconstruct the image from the camera based on the marker (this is what I think :) ) it also have a special paper that have marker. What I've still haven't got is what is the algorithm to do this? what computer vision theory used in this one? I understand artificial intellegence and basic computer vision, is there anyone have the ide how can this be done? at first I thought this based on stereo image but based on what I've studied before stereo vision need two camera. I hope my question is clear enough but if is there any information needed please ask in the comment :)

Thank you!


texts: Space and time complexy of operations on 32-bit array vs. binary array

texts:
Assume an array a of length $n$. I am wondering how to characterize the difference between time- and space complexity of 32-bit arrays of length $n$ and bit-arrays of length $n$.

Normally, you'd just state the array uses $O(n)$ space and algorithms run in $O(n)$, $O(n^2)$ and so on. But isn't there some difference between the two arrays?

I have read something about the word-size but I can't figure out how this fits into the picture..

PS.
In an actual implementation (e.g Python). There is no difference between the space used by:

a1 = [1, 402, 303]
a2 = [1,0,1]

Right?


texts:
I'm resolving indirect left recursion for these production rules:

S -> Aa / a   eq1
A -> Sb / b.  eq2

Where S is the starting symbol.

Now I can do this in two ways:

Putting A in eq1

So I'll get the solution (sol1):

S -> Sba /a /ba

and then

S -> aS' / baS'
S' -> baS' / epsilon

Replacing S in eq2:

So I'll get the solution (sol2):

S -> Aa / a
A -> abA' / bA'
A' -> abA' / epsilon

Both seem to be correct. Which is the correct answer?


texts: Turing-Complete Supervised Learning Algorithms

texts:
I'm trying to decide on what algorithm I should use for my machine learning project. I need Turing-completeness. What supervised learning algorithms are Turing-complete? Of those, what are the best?

Thanks


texts: How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum?

texts:
For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{denominator sum}}$ is maximized. As in this case, selecting $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$ will result in $\frac{4+2+1}{2+3+2}$ = 1 which is maximized.

How can I select $k$ fractions which will always result in the maximum $\frac{\text{numerator sum}}{\text{denominator sum}}$ value?

Edit:

Attempt 1: Sorting fractions in descending order. This passes a few test cases but that it's. This can also be proven by example that it is not the optimal solution. Let's say we have a list of 3 fractions sorted in descending order, $\frac{1}{2}$, $\frac{20}{59}$, $\frac{1}{3}$ and $k = 2$. The optimal solutions is $\frac{1+1}{2+3}$, not $\frac{1+20}{2+59}$.


texts: Nonuniform input distributions in average case analysis

texts:
When we perform average case analysis of algorithms, we assume that the inputs to the algorithm are sampled uniformly from some  underlying space. For example, the average case analysis of quicksort  assumes that the unsorted array is uniformly sampled from the $n!$ permutations of $\{1,\ldots,n\}$.

Suppose instead that the inputs to an algorithm are chosen  non-uniformly over the input space.

Is the resulting analysis still "average case" analysis?

If the distribution causes the algorithm to perform at its worst (resp. best), is there a standard name for it? E.g. "adversarial (resp. favourable) distribution of inputs".


texts: How many languages are described by a regular expression?

texts:
How many languages can a Regular Expression describe is it only one or infinite?
I have tried to google it but i haven't found any answer?
I know that a Regular Expression describes a Regular Language?


texts:
I'm trying to find out what the data of a packet means. I'm a newbie to networking, and I try to find what's sent in this packet:
https://pastebin.com/hZEqjmBx
How can I do that? What does that data mean? How do you decode it, or is it crypted or something? I pasted the whole HEX + ASCII dump of the packet.


texts:
I have a generator of files with approximately 7 bits /byte entropy. The files are about 30KB each in length. I'd like to use these as sources of entropy to generate random numbers. Theoretically I should be able to achieve about 26 KB (max) of randomness per file.

This is a hobby and I know about hashes, but they're primarily checksums.  I'm looking for more sophisticated methods of extraction designed specifically for that purpose. I'm hoping to use this as a true random number generator.

Supplemental:

Following comments, and in order to solicit non hash based responses, I'm evaluating the following architecture...

It works like this:-

The entropy is the 30KB file

The compressor reduces the entropy to a target size of 26KB

A seed is derived from all of the bytes of the entropy

Some PRNG implementation produces 26KB of pseudo random output

The two outputs are xored together to produce true random numbers

So in summary, a 30KB file of 86% entropy is manipulated into a 26KB file of 100% entropy.  Entropy is preserved throughout the extraction process, and all the output is totally dependant on the input.  26KB of full entropy goes in, and 26KB of full entropy comes out.

I suggest that this is a good method to extract entropy from complete files.  Or not.


texts: Number of 5-cycles and 6-cycles in a simple graph

texts: Is there any formula for computing the number of 5-cycles and 6-cycles in a simple undirected graph?


texts: Loop invariant: decreasing a variable and swapping it

texts:
As an example exercise, we were asked to find the loop invariant for this bit of code.

def mystery(a,b):
    # Precondition: a >= 0 and b >= 0
    while a >= 0 and b >= 0:
        if a < b:
            a, b = b, a
        else:
            a = a - 1
    return a

From what I can see, it first ensures that a >= b.
After that, each loop iteration decreases the value of a by 1.

This will continue until a and b are 0.

Then one final iteration terminates the loop with a == -1.

However from what I can tell, if the loop invariant is something like a >= b, it fails upon termination as a = -1 and b = 0.

Could anyone tell me the actual loop invariant of this function as I'm a bit confused.


texts: Time complexity dependent on magnitude of input

texts:
I'm trying to analyze an algorithm that looks like this:

def foo(L):
    for n in L:
        for x in range(n):
            ...

What would be its time complexity? First I thought $O(n)$, where $n$ is the number of elements in $L$, but that seems a little optimistic given that numbers can become very large. Then I thought $O(n^2)$ but that seem quite arbitrary too. $O(nm)$ where $m$ is the maximum value in $L$ perhaps?


texts:
Reconstructing a screen of permuted pixels

Summary

Given a video with the pixel locations randomly permuted (once, for the entire video), can we (efficiently) reconstruct the original picture?

Let:

$n=w\times h$ pixels.
$m=\text{number of frames}$

Details

You are given an LCD screen with $n = w \times h$ pixels, that has been altered so that the pixel locations are permuted, once, in some random manner.
Watching a video on this LCD screen would obviously result in quite a garbled picture.
The permutation is mapped by some unknown function, we shall call $\text{permute}\left(x_0,y_0\right) \implies (x,y)$
Each pixel on the screen has some permuted coordinate $(x,y)$ and some unknown original coordinate $(x_0,y_0)$ (such that $\text{permute}\left(x_0,y_0\right)=(x,y)$).
You (and your computer) are given to watch a particular video of an average film (movie) of average length, with $m$ frames, and having the same resolution as the LCD screen; however for simplicity, assume the video will be in grayscale (for example, each pixel is a single color in the range $[0,256)$).
You do not know *which* film is being played.
You (and your computer) can rewatch the garbled film as many times as you like.
As a frame of reference, you are also informed which pixel is the lowest location in the original non-permuted screen (i.e you are given the values $x$ and $y$, such that $(x_0,y_0) =(0,0)$, and $\text{permute}\left(0,0\right)=(x,y)$).

Goal

Algorithm to (efficiently) compute the mapping of the pixels to their original locations.
Can this be done in $o\left(n^2\right)$ space (i.e in better than $\mathcal O\left(n^2\right)$ space?)
Can this be done in $o\left(n^2f(m)\right)$ time?

I'm not sure how to ask this question correctly, but I am mostly wondering about reducing the $n^2$ factor.

Is this a known problem, or similar to any known problems?

PS. What about same question but for the case of binary images for each frame instead of grayscale.

Appendix

Figure 1 Example permuted "LCD screen", side view

Figure 2 Example permuted "LCD screen", front view

Figure 3 Example video frame (color)

Figure 4 Example permuted video frame (color)

Figure 5 Example video frame (grayscale)

Figure 6 Example permuted video frame (grayscale)

Figure 7 Example video frame (binary, using most-significant-bitplane)

Figure 8 Example permuted video frame (binary)

Related source codes are on gist.github.com

Credits:

Images courtesy of NASA (NASA GoPro footage from EVA 30).
More info on archive.org.
Licensed under the Creative Commons Public Domain Mark 1.0 license)


texts:
It is easy to know that there are LALR(K) grammars which are not LL(K) because any grammar with left recursion which is LALR(K), is not LL(K) because all LL(K) grammar must be left recursion free. And the opposite? Is there a LL(K) Grammar which is not LALR(K) Grammar? Do you have an example?

Related:

Are regular expressions $LR(k)$?
https://stackoverflow.com/questions/14674912/why-are-there-lr0-parsers-but-not-ll0-parsers
https://stackoverflow.com/questions/36652221/relationship-between-lr0-ll0-lalr1-etc


texts: Which properties of context sensitive languages are decidable?

texts:
There are two context-sensitive languages, $L_1$ and $L_2$. Which of the following statements about them are decidable respectively undecidable?

$L_1 = \emptyset$
$L_1 = \Sigma^*$
$L_1 \cap L_2 = \emptyset$
$\overline{L_1}$ is also a context-sensitive language.
$L_1 = L_2$


texts: Lambda calculus didn't seem abstract. And I can't see the point of it

texts:
The underlying question:

What does lambda calculus do for us that we can't do with the basic function properties and notation generally learned in middle school algebra?

First of all, what does abstract mean in the context of lambda calculus? My understanding of the word abstract is something that is divorced from the machinery, the conceptual summary of a concept.

However, lambda functions, by doing away with function names, prevents a certain level of abstraction. For example:

f(x) = x + 2
h(x, y) = x + 5 y

But even without defining the machinery of these functions, we can easily talk about their composition. For example:

1. h(x, y) . f(x) . f(x) . h(x, y) or
2. h . f . f . h

We can include the arguments if we want, or we can abstract away completely to give an overview of what's happening. And we can quickly reduce them to a single function. Let's look at composition 2. I can have student layers of detail I can write with depending on my emphasis:

g = h . f . f . h
g(x, y) = h(x, y) . f(x) . f(x) . h(x, y)
g(x, y) = h . f . f . h = x + 10 y + 4

Let's perform the above with lambda calculus, or at least define the functions. I'm not sure this is right, but I believe the first and second expressions increment by 2.

(λuv.u(u(uv)))(λwyx.y(wyx))x

And to multiply by 5y.

(λz.y(5z))

Rather than be abstract, this seems to get into the very machinery of what it means to add, multiply, etc. Abstraction, in my mind, means higher level rather than lower level.

Furthermore, I am struggling to see why lambda calculus is even a thing. What is the advantage of

(λuv.u(u(uv)))(λwyx.y(wyx))x

over

h(x) = x + 5 y

or a combined notation

Hxy.x+5y

or even Haskell's notation

h x y = x + 5 * y

Again, what does lambda calculus do for us that we can't do with the f(x)-style function properties and notation many are familiar with.


texts: Does the conservative two phase locking protocol produce cascadeless schedules?

texts:
Let us consider the following schedule :

\begin{array}{lcr}
\mbox{$T_1$} & \mbox{$T_2$}\\
\\
\mbox{lock-exclusive(a)}  \\
\mbox{lock-exclusive(b)}  \\
\mbox{read(a)} \\
\mbox{a=a+50} \\
\mbox{write(a)} \\
\mbox{unlock(a)} \\
\mbox{} & \mbox{lock-exclusive(a)}\\
\mbox{} & \mbox{read(a)}\\
\mbox{} & \mbox{a=a+50}\\
\mbox{} & \mbox{write(a)}\\
\mbox{} & \mbox{unlock(a)}\\
\mbox{read(b)} \\
\mbox{b=b+100} \\
\mbox{write(b)} \\
\mbox{unlock(b)} \\ \end{array}

Since in the schedule the lock on $a$ is released, it is possible for the transaction $T_2$ to acquire the lock on $a$. Now the transaction $T_2$ reads the value of $a$ which was written by transaction $T_1$. This implies that if the transaction $T_1$ aborts, the transaction $T_2$ must be aborted for consistency purposes. Does it mean that even though a conservative two phase protocol is used, the schedules may not necesssarily be cascadeless?


texts: What happens when two processes hold an election using bully algorithm simultaneously

texts:
A coordinator is used to sychronise the usage of resources in a distributed system.

The Bully Algorithm is a method to elect a new coordinator in a distributed system when the current coordinator disappears for some reason.

I am just wondering what happens when two processes realise the demise of the coordinator simultaneously and both decide to hold an election using the Bully Algorithm?


texts: Does every NP problem have a poly-sized ILP formulation?

texts:
Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem in NP.

But I've seen papers on specific NP problems where people write things like "this is the first poly-sized formulation" or "there is no known poly-sized formulation". That's why I'm puzzled.


texts: Generally, does the time it takes to compute (n mod m) depend on the size of n?

texts:
Example:
Suppose I have a number a with 100 decimal digits, b with 200 decimal digits, and m with 10 decimal digits.

Would the speed of the computation a mod m vary greatly from b mod m because of the size of a vs b?


texts: Is there a complexity viewpoint of Galois' theorem?

texts:
Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a polynomial there is no deterministic algorithm to find the roots?
Now consider a decision question of the form, "Given a real rooted polynomial $p$ and a number k is the third and the fourth highest root of $p$ at least at a gap of k?"

A proof certificate for this decision question will just be the set of roots of this polynomial and that is short certificate and hence it looks like $NP$ BUT isn't Galois theorem saying that there does not exist any deterministic algorithm to find a certificate for this decision question? (and this property if true rules out any algorithm to decide the answer to this question)

So in what complexity class does this decision question lie in?

All NP-complete questions I have seen always have a trivial exponential time algorithm available to solve them. I don't know if this is expected to be a property which should always be true for all NP-complete questions. For this decision question this doesn't seem to be true.


texts: The Haskell List: Type -> Type constructor implements the Functor typeclass with function fmap f = map f. This functor that applies the morphism f to each element of a list works, but there are other equally valid functors, for example fmap f = map f . rev which first reverses the list before mapping over it. Is there a concept in category theory that expresses the fact that the first choice of functor is in some sense "more natural" for this type constructor?


texts: Turing Machine that always returns a blank tape

texts:
Is it possible to construct a Turing Machine such that given any finite input on a tape $s$, it clears the tape in a finite amount of time?

I have used such a TM as an intermediate step to show a reduction from the State Entry Problem to is $w \in L(M)$ problem but I don't know if it is feasible to construct one.

Even if we assume that the head of the TM always starts at the leftmost character on the tape and keep moving write, clearing each symbol we encounter, if the tape is infinite, how will we know when to stop moving right?


texts: Given grammar, a nonterminal, and a string, does there exist a parse tree that uses the nonterminal?

texts:
Let $G$ be a CFG, let $A$ be one of its non-terminals, and let $x$ be a string. Define the language = $ \{ \langle G,A,x\rangle|$there exists a derivation of $x$ in which $A$ is used  $\}$. Is this language T-recognizable? Is it decidable?

Obviously, we can determine if there is at least one derivation for $G$, since context-free languages are decidable. But we cannot print every derivation. One idea could be to convert to Chomsky normal, and then print all possible derivations up to a certain length, but I am not sure if it would work.

Could one start with first designing a recognizer that is not necessarily decidable and then tweak it to be a decider?


texts: Why don't modern SAT solvers use the notion of a "watched clause", in the same way they use the notion of a "watched literal"?

texts:
Modern SAT solvers use the notion of "watched literals": when a value is chosen for a literal $l$, the solver only checks whether that falsifies clauses with $l$ in them if $l$ is one of the watched literals in the clause. This prevents checking every clause for every newly assigned literal.

The correctness of the scheme comes from the fact that clauses are disjunctions and will only be false if all literals in it are false. So we know it is not false until at least the watched literal is false, and we only need to check when that happens.

I am wondering why the dual idea of a "watched clause" is not used as well. This is how it would work: the overall formula is a CNF, that is, a conjunction of clauses. The watched literal scheme already checks very fast whether the CNF has become false. However, it would also be useful to detect when it becomes true: no further search would be needed then. A conjunction is only true if all clauses in it are true. So we choose one "watched clause" $C$ and, if a literal in $C$ is assigned a value, we check to see if $C$ has turned true. If so, we mark that clause as now irrelevant, and pick another clause not yet satisfied. If we cannot find a not-yet-satisfied clause, all clauses are satisfied and the problem is satisfiable.

I realize this would require keeping track of more information; assigning to literals would now not only require checking if they are watched literals, but also if they are in the watched clause. More importantly, looking for a new watched clause requires checking if other clauses are not yet satisfied, which means checking all their literals. Depending on the structure of the problem instance, this could be much slower. However, for some instances (for example, problems with small clauses) this would be much faster because satisfaction would be detected much sooner.

So my question is whether this is not used simply for empirical reasons (say, it would be slower for most benchmarks), or if there is a deeper flaw about it that I am missing.

A secondary question is: if this is a merely empirical issue, then is there some simple argument predicting this from the description of the technique alone, or is it something that would need to be observed in practice? Or, in other words, if this is a bad idea, is it so in principle, or just empirically?

Addendum:

It has been suggested by an answer that the notion of watched literals implies the use of DPLL which implies tracking which clauses have been satisfied, and that therefore the question does not make sense. It is true that watched literals are used in the context of DPLL, but it is not true that this means tracking satisfied clauses.

The paper on Chaff, which defined watched literals, describes DPLL in pseudo-code as

while (true) {
    if (!decide()) // if no unassigned vars
        return(satisifiable);
    while (!bcp()) {
        if (!resolveConflict())
            return(not satisfiable);
    }
}

This shows that satisfiability is decided as positive only when all variables are assigned, not when all clauses are satisfied (which could happen much earlier). Chaff and zChaff have been the basis for many of modern SAT solvers, including the very prominent MiniSAT.

The same idea is described in detail in Filip Maric's paper "Formalization and Implementation of Modern SAT Solvers", which describes this approach as the basis for many of the most prominent SAT solvers today.


texts: Running time complexity of finding maximal power of divisor that divides natural number

texts:
Given $n \in \mathbb{N}$, a divisor $p\vert n$, I would like to efficiently find $e\in\mathbb{N}$ with $p^e \vert n$, and $e$ maximal with this property. I will assume that multiplication/division of two $b$-digit numbers has time complexity $O(b^{\log_{3}{5}})$. (Ie. I use the Toom-Cook algorithm.)
Then it can be shown that the naive repeated division approach has a complexity that's worse than $O(\log^{2}(n))$.

An alternative I considered is performing a binary search like algorithm on $\{0, 1, ... \log{n}\}$, where I assume that $\log{n}$ is given. This means that instead of checking all $\log{n}$ candidate powers, it suffices to consider only $\log{\log{n}}$ elements of the above set of possible powers. For each candidate power $p^f$ a division $p^f \vert n$ is required, which can be performed in $O(b^{\log_{3}{5}})$. We only need to compute the maximal power of $p$, $p^{\log{n}}$ as we can store intermediate powers (even if we use repeated squaring , precisely because a binary search is performed on our search space). The cost of computing $x^y$ via repeated squaring is $O((y \log{x})^{\log_{3}{5}})$. Hence the overall complexity of this approach is $$O(\textit{exponentation_cost} + \textit{division_costs}) = O((\log{n} \log{p})^{\log_{3}{5}} + \log{\log{n}} \cdot (\log{n})^{\log_{3}{5}})$$

Now supposing that $p$ is small relative to $n$, that is $p \in O(\log{n})$, then the above expression belongs $O((\log{n} \log{\log{n}})^{\log_3{5}})$, which isn't too bad.

My questions are:

Does the above analysis look sensible?
Is there a standard/better way to do this?


texts:
In ciruclar queue the following command statement is very useful to use the determine the unused location. What is its importance? I know that without this line it won't be a circular queue. But how to say it in theoretical way?
rear=(rear+1)%max


texts: Regarding a theorem that says a language that is Turing-Recognizable iff some enumerator enumerates it

texts:
I am reading the proof of Theorem 3.21 in Sipser's textbook.

Theorem 3.21 A language is a Turing Recognizable iff some enumerator enumerates it.

First direction (<==).
Given an Enumerator E that enumerates language B, then we want to construct a TM M s. t. M that recognize language B. In order to do that, we do the following:
M="On input string x

Run E and compare each printed string with x
If x ever appears in the output of E, accept."

Given the following fact:

A TM M accepts input w if a sequence of configurations $C_1, C_2, ..., C_k$ exists s. t. $C_1$ is the starting configuration, $C_2$ to $C_{k-1}$ is the process configuration and $C_k$ is the accepting configuration.

My question: It is not clear how E accepts? e.g. What it does from my point of view is: It runs E without any input, if ever E printed out an arbitrary string, let's call it r, then if r==x, then we accept. I thought that we should do some processing like with given input x, then we should do some computation (moving from configuration to another) until we get to some arbitrary string that should be the output of the accepting state.
Note that I read all related answers to this question, but it didn't cover my question. For example: this and this.


texts: How to include both precedence and associativity in following grammar?

texts:
For the following grammar, how can I include both precedence and associativity of operators:

  S -> S|S

  S -> S.S

  S -> S*

  S -> (S)

  S -> a|b

Note: In the first rule S -> S|S, the symbol | is the OR symbol and not two rules.

Here, operators are |, ., * and ().

PS: Suppose the precedence order is : () > * > . > |. And all are left associative.


texts: Sampling from specific random distribution on sets

texts:
I have a random distribution on sets in mind, that has three parameters: $n, w, k$. The goal is to sample sets of $k$ integers from $[0, n)$ (without replacement) such that the elements within each set fit in a subrange of length $w$. That is, an outcome set $S$ must have properties:

$S \subset \mathbb{N_0} \; \wedge\;  |S| = k$
$0\leq \min(S) \leq \max(S) < n$
$\max(S) - \min(S) < w$

You can assume that $k \leq w/2 < w \ll n$.
Now there are many possible distributions possible over these sets. But I'm interested in those that have as property
$$\forall x:P[x \in S] = \frac{k}{n}\;,$$
that is each integer in $[0, n)$ has an equal chance of being in a set when sampled (or as close as possible). Beyond the above requirements, it'd be ideal if the distribution is an maximum entropy one, but this isn't as important, and something close would be fine too. As a minimum bar I do think every valid set should have a non-zero chance of occurring.
Is there a practical way of sampling from a random distribution that matches the above requirements?
I've tried various methods, rejection sampling, first picking the smallest/largest elements, but so far everything has been really biased. The only method that works that I can think of is explicitly listing all  valid sets $S_i$, assigning a probability variable $p_i$ to each, and solving the linear system $$\sum_i p_i = 1 \quad\bigwedge\quad \forall_x:\frac{k}{n} - \delta \leq  \sum_{x \in S_i}  p_i \leq \frac{k}{n} + \delta,$$ minimizing $\delta$ first, $\epsilon $ second where $\epsilon = \max_i p_i - \min_i p_i$. However this is very much a 'brute force' approach, and is not feasible for larger $n, k, w$.


texts: What kind of algorithm to use when reversing state?

texts:
I'm not sure what algorithm to use in the kind of problem described below, any suggestion to put me on the right track, even at any way is desirable.

Thank you in advance.

You have some 2D field in a form of two dimensional array (full of 0 & 1 values).
There are certain rules, that describe how to get from previous array state to the current array state.
Implement some solution so that you can find out all previous states that lead to the current state. If you have current state of the array.

I'm not looking for a coded solution of my problem or any shape of help like that. I just want to get on a right track and search for solutions in right area. For example: If you had some network and wanted to compute maximum flow, nice answer would be: "You should look up flow algorithms. For example: Ford–Fulkerson algorithm ... " etc. (obscure but it should do the thing).

If you need more specification for instance, if you need to know more about rules, feel free to ask!

EDIT 1:

Here are pattern details, and by the way, matrix won't be smaller than 2x2.
You need to figure out for given matrix/2D grid what was it previous state if a current state is for example:

\begin{array}{cc} 1 & 0\\ 0 & 1 \end{array}

You know that 1 in the matrix cell is determined by 4 cells next to it.

That cell
the one below it
the one to the right of it
the one below and right to it

If only one of the cells has 1 in it, in the next state 1 would stay. But any other combination and zero would be next state. So for the matrix given above as example, next state would be
\begin{array}{cc} 0 \end{array}


texts: I need help finding an algorithm that creates a permutation of graph nodes with the least total weight of all edges

texts:
Here is an imgur folder with the projects description (my apologies for the awfully wrinkled paper): http://imgur.com/a/a2vQM

There are a set of pegs, numbered from 0 to n - 1. Each peg can have a connection to another peg with a rubber band.

Basically, the program is given an adjacency list with all of the pegs and the ones they connect to. The idea of the project is to come up with an algorithm that returns a permutation with the all of the rubber bands stretching the least distance.

It's my understanding that this program will take a long time to run. Our teacher implied that the algorithm should run multiple times to get the best answer; each result of the algorithm should improve the overall "cost". (The cost is the distance spanned by all of the rubber bands, measured in pegs. For example, a set of 5 pegs in numerical order that has one rubber band between peg 1 and 3 has a cost of 2).
I've been struggling to come up with an algorithm that returns a "good" result. What I need is an algorithm that, when run an infinite amount of times, will improve the cost each time. If anyone recognizes the problem or has any suggestions, please let me know. Thanks!


texts:
Proving software is based on logics and there any many logics. AFAIK all of the logics can be shown as a tree diagram of how they are related; for example, a tree of how types of number are releated

Image from: https://byjus.com/maths/real-numbers/
I am looking for a similar diagram for logics.

While I have needed this for many years my current interest is related to

Separation logic is the twenty-first-century variant of Hoare logic that permits verification of pointer-manipulating programs.

from: PROGRAM LOGICS FOR CERTIFIED COMPILERS by Andrew W. Appel et al.


texts:
Let $L\subseteq \Sigma^*$ such that $\{\epsilon\}\not\in L$. Then for any $S\subseteq \Sigma^*,
 S=SL\implies S=\emptyset$.

So we suppose $S=SL$ and $S\ne\emptyset$. Then $\exists w\in S$ such that $0\le|w|\le |v|$ for some $v\in S$. Now $|w|\ne 0$, since $|w|=0\implies\{\epsilon\}=w\in S=SL\implies \{\epsilon\}=xy$ for some $x\in S$ and $y\in L\implies x=y=\{\epsilon\}\in L$ which contradicts that $\{\epsilon\}\not\in L$.
Thus $w\ne\{\epsilon\}$ and $\{\epsilon\}\not\in S$. So we have
\begin{align}
w \in S &\implies w\in SL\\
&\implies w=sl\;\text{for some}\; s\in S\; \text{and}\; l\in L\\
&\implies |w|=|s|+|l|
\end{align}
Here I'm stuck now. I think if I can show that $|l|=0$, then we can arrive at a contradiction.
Your help is highly appreciated.


texts:
Alright, I thought I understood this concept but now I am confused. I looked up similar problems and their solutions to practice, and that's what threw me off. The question is a homework problem which says:

Below is a list of 32-bit memory address references, given as word addresses.

3, 180, 43, 2, 191, 88, 190, 14, 181, 44, 186, 253

a) For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with 16 one-word blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty.

b) For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with two-word blocks and a total size of 8 blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty.

(How do I know how many bits the tag and index are supposed to have? Also, it is a miss unless both the tag and the index match, right? Or is it just if the index matches? I'm obviously extremely confused but I really do want to understand!)

My answer for a) :

Memory        Binary          tag          index         hit/miss
3             00000011       0000          0011          miss
180           10110100       0010          0000          miss
43            00101011       0010          0011          miss
2             00000010       0000          0010          miss
191           10111111       1011          1111          miss
88            01011000       0101          1000          miss
190           10111110       1011          1110          miss
14            00001110       0000          1110          miss
181           10101101       1010          1101          miss
44            00101100       0010          1100          miss
186           10111010       1011          1010          miss
253           11111101       1111          1101          miss

b)I'm not sure how to figure this out, but when I looked it up, people were saying the index should be left shifted one bit so that's what I got (I'd like to understand why)

3             00000011       0000          001          miss
180           10110100       0010          000          miss
43            00101011       0010          001          miss
2             00000010       0000          001          hit
191           10111111       1011          111          miss
88            01011000       0101          100          miss
190           10111110       1011          111          hit
14            00001110       0000          111          miss
181           10101101       1010          110          miss
44            00101100       0010          110          miss
186           10111010       1011          101          miss
253           11111101       1111          110          miss

As always, thank you so much for your help.


texts: On the language of Turing machines not accepting their own encoding

texts:
Let $\text{NOT-SELF} = \{\langle M \rangle : M \text{ is a TM that does not accept } \langle M \rangle \}$. How do you prove the following claim?

  If $Q$ is a TM so that $L(Q) \subseteq \text{NOT-SELF}$, prove that $\langle Q \rangle \in \text{NOT-SELF}$.


texts: Online version of bellman-ford algorithm?

texts: Suppose I have a graph on which I've run the Bellman-Ford algorithm. Now I change the weight of subset of edges. Is there an efficient way to re-run the algorithm without having to completely start over? That is, can I update the shortest path in an "online" manner, if I'm only changing a subset of weight edges each time?


texts:
This question has been asked and the top answer https://stackoverflow.com/a/38173155/12862537 is not satisfactory.

So, it would be nice if someone could specifically point out the similarities and differences between the two.

About the answer at the mentioned link:

  The term busy-waiting tends to mean that you are willing to spin and wait for a change in a hardware register or a memory location. The term does not necessarily mean locking, but it does imply waiting in a tight loop, repeatedly probing for a change.

Some unanswered queries:
Does this mean that spinlock waits without probing for change ?
If so, how does spinlock wait ?

The answer specially mentions that

  busy-wait waits for a change in hardware register or memory location

What is the reason to explicitly mention this ? Does spin-lock wait for something else ?


texts: Problems while trying to prove that $(r|s)^* = (r^*.s^*)^*$

texts:
I came across the following equality of regular expressions $$(r|s)^* = (r^*.s^*)^*\,,$$ where $r$ and $s$ are two regular expressions and $.$ denotes concatenation, but I don't know how could I prove it.

My try:

I call $L(r)$ the language defined by the regular expression $r$. And I want to use the fact that two regular expressions $r$ and $s$ are equal iff $L(r) = L(s)$.

The LHS can be writen as follows: $$ L((r|s)^{*}) = \bigcup_{i=0}^{+\infty} L(r|s)^{i} = \bigcup_{i=0}^{+\infty} (L(r)^{i} \cup L(s)^{i})\,. $$

The RHS can be writen as follows:
$$ L((r^{*}.s^{*})^{*}) = \bigcup_{i=0}^{+\infty} L((r^{*}.s^{*}))^{i}\,.$$

But I got stuck at this point and I don't know how to proceed.


texts: divide and conquer algorithm for finding a 3-colored triangle in an undirected graph with the following properties?

texts:
In an undirected Graph G=(V,E) the vertices are colored either red, yellow or green. Furthermore there exist a way to partition the graph into two subsets so that |V1|=|V2| or |V1|=|V2|+1 where the following conditions apply: either every vertex of V1 is connected to every vertex of V2 or no Vertex of V1 is connected to a vertex of V2 . This property applies recursively to all induced subgraphs of V1 and V2
I can find all triangles in the Graph by multiplying the adjacency matrix with itself three times and step up the nodes corresponding to the non zero entries of the main diagonal. Then I can see if the  nodes of the triangle are colored the right way. O(n^~2,8)! But given the unique properties of the graph I want to find a solution using divide and conquer to find the colored triangle.
this is an example graph with the given properties. I need to find the bold triangle:

Blue boxes symbolize the partitions are fully connected, purple boxes mean no connection between the partitions
There is no connection between the coloring of nodes and the partitions, also the partitions have to be computed on the fly


texts: How to find the distance between two nodes in an undirected graph, from a neighborhood matrix?

texts:
Given a distance-1 neighborhood matrix representing an undirected graph, I'm trying to calculate the distances between two nodes so I can work out the distance-2 matrix, then the distance-3 matrix, and so on...

How to find this distance?

Any help would be appreciated.


texts: What is the correct complexity of All paths from Source to Target DFS solution?

texts:
The question: "Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order."

The DFS solution is described here. https://leetcode.com/articles/all-paths-from-source-to-target/

I feel like the author likely got the time complexity analysis wrong. I would have asked the author themselves, but from the discussion below, they don't really respond to questions. So, what is the correct time complexity analysis for this problem, and how to derive it?


texts: How to avoid loops/cycles in iterative deepening with linear space?

texts:
Breadth first graph search adds states that have already been visited to an explored set to avoid getting stuck in loops and cycles. This is fine since breadth first search needs exponential space to keep all the nodes in memory.

One of the main reasons for using iterative deepening depth first search is to avoid the exponential space requirements. To ensure linear space you can't simply add every visited state to the explored set. How then do you avoid loops in iterative deepening graph search?

My intuition is that you could remove states from the explored set at some point? Or backtrack to the root but that seems more expensive.


texts: Maximal cliques in a multipartite graph - efficient?

texts:
I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class.
Now I am looking for the optimal subset such that each of the N classes is represented exactly once. Not all objects can be combined with each other, e.g. object (N=1,k=1) might not be compatible with (N=2, k=4).
I can formulate this problem as looking for the maximal clique on a N-partite graph (but maybe there are other formulations that I'm not aware of). My question is whether an efficient algorithm exists for solving this problem.
From https://stackoverflow.com/questions/2801138/find-all-complete-sub-graphs-within-a-graph:

This is known as the clique problem; it's hard and is in NP-complete in general, and yes there are many algorithms to do this.
If the graph has additional properties (e.g. it's bipartite), then the problem becomes considerably easier and is solvable in polynomial time

This implies that an efficient algorithm might exist for my problem, but I can't find it...


texts: Is this problem that's similar to integer linear programming also an NP-complete problem?

texts:
I've come across this problem while trying to work out a table-formatting algorithm.

It's very similar to standard linear programming (though it uses $>$ instead of $<$; I'm not extremely familiar with linear programming, but I believe this doesn't matter much).

Let $\vec v = (v_1, \dots, v_n)$ be a vector of positive-integer variables.

The problem is to find if there is an assignment to $\vec v$ such that

$$ v_1 + \dots + v_n = c $$

and

$$ A \vec v \geq \vec w $$

where $c$ is a known constant, $\vec w$ is a known constant, and $A$ is a matrix with the special property that each row of $A$ is of the form $(0, \dots, 0, 1, \dots, 1, 0, \dots, 0)$.

That is, each inequality constraint only uses coefficients 1 and 0, and only "consecutive" variables appear in each linear constraint.

I think that this problem is NP-complete, but I haven't been able to prove it.

I think a reduction to exactly-1-in-3-SAT or set-cover is most likely to succeed (variables would be literals/values respectively and rows in the matrix would correspond to clauses/sets), but the restriction that constraints only refer to consecutive variables doesn't seem strong enough to describe arbitrary clauses/sets.

Alternatively, I might be wrong, and this problem actually has an algorithm that I have been missing. (The problem I'm actually interested in solving is finding the smallest $c$ such that constraints remain satisfiable, but I've phrased the problem this way so that it remains a simple decision problem)

As an example, here's a small instance of this problem:

$$
\begin{array}{}
v_1 + v_2 + v_3 + v_4&=& 10 \\
v_1 &\geq& 1 \\
v_2 &\geq& 1 \\
v_2 + v_3 &\geq & 3 \\
v_3 + v_4 & \geq & 4 \\
v_3 &\geq& 1 \\
v_4 &\geq& 1
\end{array}
$$

which has a possible assignment $\vec v = (1, 1, 6, 2) $.


texts: Does a subcubic algorithm exist for the following problem?

texts: Given a symmetric real $n \times n$ matrix $A=(a_{ij})$, is there an algorithm which computes the sum $$\sum_{i,j,k}\max(a_{ij},a_{ik},a_{jk})$$ over all $1\leq i<j<k\leq n$ with time-complexity better than $O(n^3)$?


texts: Prove that inserting $n$ sorted values in to an AVL using AVL insertion is $\Theta\left (n \log \left ( n \right ) \right )$

texts:
We're asked to prove the above mentioned lemma but I having a hard time proving this rigorously.

We did prove that given $n$ values AVL's height is $\Theta\left (\log \left ( n \right ) \right )$ So I thought that after inserting a $\frac{n}{2}$ values the height of the tree will be at least $\Theta\left (\log \left ( \frac{n}{2} \right ) \right )$ which and because each isertion we make is now on a tree with at least $\frac{n}{2}$ and insertion is $\log \left (h \right ) $ where $h$ is the height of the tree.

So for a function $F$ using the previous logic:

$\begin{align}  F &= \frac{n}{2} \times \log \left (h \right )
\\& \geq \frac{n}{2} \times \log \left (\frac{n}{2} \right )
\\&=\Omega\left( n\log \left (n \right )  \right)
\end{align}$

But I have a few issues with this

This does feel fishy to me don't know why but it doesn't feel like a good well defined calculus proof :)
I'm not sure which way to take it in order to prove the upper boud i.e $\mathcal{O}$

If I haven't given all the required information I'd be glad to.


texts: Creating admissible and consistent Heuristic function Help

texts:
I am trying to create a heuristic function for use in an A* algorithm. The problem to be solved is a single row tile puzzle with 3 total w tiles and 3 b tiles and one "_" tile as shown below

WWW_BBB

The goal of this puzzle is to get the white tiles on the right of the black tiles regardless of the position of the "_".

The possible moves for this puzzle is as shown below

 The puzzle has two legal moves(i.e. actions) with associated costs:

• A title may move into an adjacent empty location. – This has a step cost of 1.
• A title can hop over one or two other tiles into the empty position.
– This has a step cost equal to the number of tiles jumped over.

My idea for the heuristic function would be the amount of spaces the black tiles would be away from the goal state and divide this number by 2 rounded up to the nearest int. Example of this would be wbw_bwb, this state would be a heuristic cost of (1+2+2 = 5).

Would this be an admissible estimate, Also i am looking for a secondary heuristic function that I could use to satisfy the assignment.

  Edit below

I have thought of a couple others that I think will work and probably will be closer to what the problem would actually be.

first one is the amount of total chars that are out of position so bwbb-ww this would be a heuristic of 2.

next would be the amount of w's are to the left of each b added together so wwb-wbb this would be (2 + 3 + 3) for a total of 8.


texts: Backwards and forwards automata languages compared with regular languages

texts:
Is every language accepted by a BAFDA regular? I am not even sure what the answer is. I tried thinking around canonical examples of non-regular languages (like $0^n1^n$ or $\{ww | w \in \{0,1\}^{*}\}$ provable by Myhill-Nerode or by the Pumping Lemma) but cannot think of a suitable BAFDA for any of them.

Update: I tried $0^{n+1}1^n$ with the two-state BAFDA "if the heads read different symbols, they stay at the same state; if they read different symbols, they switch states"- however, this accepts many more words than $0^{n+1}1^n$...

Hmm something like palindromes perhaps works! Take 2 states $(q_1, q_2)$, put the heads initially on $(q_1,q_2)$ and make only the pair $(q_1, q_2)$ accepting. While they read the same letter keep their state -- but if they read different letters then they switch states. If I am not mistaken, this BAFDA accepts all words $w_1\ldots w_k$ such that $w_i \neq w_{k-i}$ holds for an even number of indices $i$. On the other hand, this is an irregular language -- e.g. by the Pumping Lemma on sth like $0^{2p+1}1^{2p+1}$. Is this correct?

Update: Even palindromes should work with a similar example (just switch at the first time they read different letters; afterwards no matter what happens, do not change the states).


texts:
I'd like to reduce 3 colorability to SAT. I've stuffed up somewhere because I've shown it's equivalent to 2 SAT.

Given some graph $G = (V,E)$ and three colors, red, blue, green. For every vertex $i$, let the boolean variable $i_r$ tell you whether the $i$-th vertex is red (or more precisely, that the $i$-th vertex is red when $i_r = 1$). Similarly, define $i_b$ and $i_g$.

Suppose two vertices $i$ and $j$ were connected by an edge $e$. Consider the clause
        \begin{align}
   (\bar i_r \vee \bar j_r)
  \end{align}
        If we demand the clause is true, it means that the vertices cannot both be red at the same time. Now consider the bigger clause $\phi_e$
        \begin{align}
   (\bar i_r \vee \bar j_r)\wedge(\bar i_b \vee \bar j_b)\wedge(\bar i_g \vee \bar j_g)
  \end{align}
        which, if true, demands that the vertices $i$ and $j$ aren't both the same color. By itself, this clause is in 2-SAT.

For every edge $e \in E$, I now make a clause $\phi_e$ of the above form and put them all together using $\wedge$'s
          \begin{align}
              \phi = \wedge_{e \in E} \phi_e
           \end{align}
Thus, for the entire graph, I've come up with a 2SAT formula which is equivalent to 3 coloring.

This is obviously wrong, but I can't tell where I've screwed up.


texts: Time complexity of complex nested for loops

texts:
What are the time complexities of the following code?  I posted this on the general stackexchange website, but it was suggested that I post it here.

def func(n):
    for _ in range(n):
        if n == 4:
            for _ in range(n):
                <O(1) operation>

It will only be O(n^2) for one specific input (n = 4) but is O(n) for all other inputs. In this case the worst case is obviously O(n^2), yet my instructor says that O(n) is the correct answer. If "big-Oh" notation is to indicate the worst case scenario, why is it not O(n^2)?

Another one is:

def func2(n):
    for _ in range(n):
        if n%2 == 0:
            for _ in range(n):
                <O(1) operation>

I am not so certain about the run time of this piece of code. Again, worst case is O(n^2). This time half of all possible inputs results in the worst case. Would this suffice in saying that the code runs in O(n^2) time?

If the first part is O(n) and the second part is O(n^2), is there a general rule of thumb when you choose the truly worst case for the "big-Oh" representation?


texts: Proof of Correctness Request for Greedy Algorithm that solves “The Weight Job Scheduling” problem

texts:
Today, in my self-lead studies, I found out about greedy algorithms, more specifically, a greedy approach to solve The Weighted Job Scheduling Problem.
I understand how the solution is implemented but, I'd love to see a proof of correctness for this solution (i.e. partial correctness and termination). If anyone can help me understand why this solution is correct mathematically in a general form, that'd really great!


texts: Does a proof using the well-ordering principle need a base case?

texts:
For proofs by well-ordering principle the general template is to consider the negation of some predicate $P(n)$. Then assume the set of all elements that fulfill $\lnot P(n)$, i.e.

$\qquad N = \{ n \mid \lnot P(n) \}$

has a smallest element according to WOP, say $m = \min N$, and if we manage to prove that there is another element $m' \in N$ that is less than $m$ that also negates  then we contradict our assumption that $m$ is the smallest element.

My question is that should we be proving some sort of a base case as well for the above mentioned template. As in proving that for some base case, $P(\mathrm{base})$ is true?


texts: Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)

texts:
I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$.

The bound should be $nm \lg(m)$. I need to prove this using a decision tree.

I tried counting the number of possible permutations (which would be the number of leaves in the tree) but
I got stuck. I tried the following:

When merging the 2nd array with the first, we have $\binom{2n}{n}$ possibilities to place the elements. When merging the 3rd, we have $\binom{3n}{n}$ and so on, so the total number of permutations is:

$$\binom{2n}{n} \binom{3n}{n} \dots \binom{mn}{n}$$

The height of the tree is denoted $h$.

$$h > \lg{\binom{2n}{n} \binom{3n}{n} \dots \binom{mn}{n}}$$

And from here I don't know how to prove the complexity.

My question is - did I count the permutations correctly? Is there a more simple bound? How to continue from here?

Also, ould this problem possibly be equivalent to the problem of sorting an $m$-sorted array of size $nm$? Because in this problem it is easy to prove that the bound is $nm \lg(m)$.


texts: Steps to implement PageRank Algorithm on a local set of webpages

texts:
I just completed a detailed theoretical mathematical study about the PageRank algorithm, I want to make a sample implementation to make some tests and play with it, supposing that I have a local set/folder full of a several webpages, representing a mini Web, I want to make a small software where I can make searches by implementing the PageRank algorithm (with some modifications in the algorithm) and make tests and simulations.

From what I know, I should crawl and index those web pages, then play with my ranking.

Is there a solution that provide me crawling and indexing and spares me the effort of working on them so I can focus on my main problem ?


texts: Reduction from NP-complete problem to unknown complexity problem and vice-versa

texts:
Suppose I have two problems: $B$, which is NP-complete, and $A$, of unknown complexity.

Question:

If I show that $B \le A$ I can state that $A$ is also NP-complete because the two required conditions are satisfied: (i) $A$ is in NP; (ii) I reduced a NP-complete problem to $A$.
If I show that $A \le B$ I can say that $B$ is at least hard as $A$, so $A$ is at least NP-complete, but can be harder.

Are these statements correct?