texts: Can a Turing machine have infinite states?

texts:
Does it make sense for a Turing machine to have infinite number of states ? I had previously asked a question Can Turing machines have infinite length input. From which I came to know about Type-2 Turing machines. If there can be infinite states, encoding of such a Turing machine would be infinite ( but again I am not sure if it make sense to encode a Turing machine with infinite states thus having an infinite description ). So it would make sense that if I have to give the encoding of such a Turing machines as input, I would give it as input to Type-2 Turing machines.
But is there any use of infinite states ( and what is there link to Type-2 Turing machines ? ) ? If I am not wrong there is no function which is uncomputable by normal Turing machine but computable by Turing machine with infinite states.


texts:
I am having trouble finding the time complexity of the below code.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        if root is None:
            return True

        def height(root):
            if root is None:
                return 0
            left = height(root.left)
            right = height(root.right)

            return 1 + max(left, right)

        def check(root):
            if root is None:
                return True

            if abs(height(root.left) - height(root.right)) < 2:
                return(check(root.left) and check(root.right))
            else:
                return False

        return check(root)

Is it O(n^2) or O(n) because first we are checking for the root, and that takes O(n) time and then we check for the left subtree and the right subtree, where the elements searched are halved each time?

Thanks!


texts: Reducing from NPC to Co-NPC => NP = Co-NP?

texts:
In my lecture we learned:

If X is NPC and X in Co-NP => NP = Co-NP

Would it be enough to prove NP = Co-NP if I reduce a problem just in one direction (from NPC to Co-NPC) in polynomial time?

Or would it be necessary to show this for both directions?


texts:
I know the basic definition between parallelism and concurrency. But there is not much information about
concurrency in multiple core.
what is the difference between concurrency in single-core vs concurrency in multiple-core?
Is there much difference performance-wise between concurrency in multiple core vs parallelism in multiple core?


texts: Interchangeable role of public/private key pair and encoding/decoding algorithms

texts:
In designing a public-key cryptosystem, there are often two desirable properties:

Public/private key pair of each participant can be exchanged. Meaning that whenever a participant has generated a key pair $(a, b)$, it is free up to him to choose to public either $a$ or $b$ (but not both, of course)
Encoding/decoding algorithms $(E, D)$ are interchangeable. It is up to all participants to choose either $E$ or $D$ to be the encoding algorithm, then automatically, $D$ or respectively, $E$ will be the decoding algorithm. But the choice must be made prior to any communication.

Note that if $D$ and $E$ are identical, for e.g. $\mathrm{RSA}$, then the property 2 is vacuously true.

The question is: Assume that $E$ and $D$ are different, is there any known public-key cryptosystem that satisfies property 1 but violates property 2.

Informally, the cryptosystems that we are interested are the ones in which the key generation is in some sense symmetric, but the encoding and decoding algorithms are not.

EDIT: We only consider deterministic encryption scheme. To be meaningful, we assume $\mathrm{M} = \mathrm{C}$ and $\mathrm{PU} = \mathrm{PR}$ where $\mathrm{M}$ is the message space, $\mathrm{C}$ is the ciphertext space, $\mathrm{PU}$ and $\mathrm{PR}$ are public and private key space.


texts: Determinant calculation - Bareiss vs. Gauss Algorithm

texts:
I've been working on a matrix-library in C++ for a while and amongst other functions, I've implemented two functions for calculating the determinant of a matrix:

Gauss-Algorithm:

This algorithm is based on the fact that the determinant of a triangular matrix equals the product of it's diagonal entries. Therefore it is pretty intuitive to convert the matrix into a triangular matrix by using elementary row operations.

My implementation:

double getDeterminantGauss(std::vector<std::vector<double>> matrix) {
    int n = matrix.size();
    int sign = 1;
    for(int i = 0; i < n - 1; i++) {
        //Pivot - row swap needed
        if(matrix[i][i] == 0) {
            int m = 0;
            for(m = i + 1; m < n; m++) {
                if(matrix[m][i] != 0) {
                    swap(matrix[m], matrix[i]);
                    sign = -sign;
                    break;
                }
            }

            //No entries != 0 found in column k -> det = 0
            if(m == n) {
                return 0;
            }
        }
        for(int j = i + 1; j < n; j++) {
            double ratio = matrix[j][i] / matrix[i][i];
            for(int k = 0; k < n; k++) {
                matrix[j][k] -= ratio * matrix[i][k];
            }
        }
    }

    double solution = 1;
    for(int i = 0; i < n; i++) {
        solution *= matrix[i][i];
    }

    return sign * solution;
}

Bareiss-Algorithm:

The Bareiss-Algorithm was introduced by Erwin Bareiss in his paper "Sylvester's Identity and multistep integer-preserving Gaussian elimination" (1968) and is mathematically quite complex (the interested can read the paper here). One advantage of this algorithm over Gauss is the following: To calculate the determinant of a integer determinant, only integer arithmetic is needed: Any division performed will have no remainder.

My implementation:

double getDeterminantBareiss(std::vector<std::vector<double>> vect) {
    int dim = vect.size();

    if(dim <= 0) {
        return 0;
    }

    double sign = 1;

    for(int k = 0; k < dim - 1; k++) {

        //Pivot - row swap needed
        if(vect[k][k] == 0) {
            int m = 0;
            for(m = k + 1; m < dim; m++) {
                if(vect[m][k] != 0) {
                    swap(vect[m], vect[k]);
                    sign = -sign;
                    break;
                }
            }

            //No entries != 0 found in column k -> det = 0
            if(m == dim) {
                return 0;
            }
        }

        //Apply formula
        for (int i = k + 1; i < dim; i++) {
            for (int j = k + 1; j < dim; j++) {
                vect[i][j] = vect[k][k] * vect[i][j] - vect[i][k] * vect[k][j];
                if(k != 0) {
                    vect[i][j] /= vect[k-1][k-1];
                }
            }
        }
    }

    return sign * vect[dim-1][dim-1];
}

Complexity:

Obviously both these algorithnms have a time-complexity of $\mathcal{O}{(n^3)}$. The Laplace-expansion here is not really an alternative with $\mathcal{O}{(n!)}$.

Question:

Why is the Gauss-Algorithm much more often used than the Bareiss-Algorithm? Is the Gauss-Algorithm just better? If yes, why?


texts: What is the job of Syntax Analyzer in a compiler?

texts:
What exactly is the job of a syntax analyzer? Suppose I have a mathematical expression. Is it true that the order of execution of the operations is found with the help of syntax analyzer?

Any example on exact jobs of Syntax Analyzer?


texts: Counterexample that B-A can be NOT context free

texts: Given that A is a context free language and B is a regular language, B-A can be not context free as it is equal to B ∩ A', and context free languages are not closed under complement. Could you give me a counterexample?


texts: Complexity of Block edit distance with Swapping only

texts:
Suppose I have distinct letters in an alphabet $\sum = \{a_1,a_2,...,a_n\}$. I also have two permutations of these letters, let's call them $A,B$. How can I find the Edit distance between $A$ and $B$ with block edit operations allowed?

To make it clearer, an example would be $\sum =\{a,b,c,d \}$. Two possible permutations are $A=``abcd",B=``dabc"$. The edit distance here would be $1$ because we can swap the block $``abc"$ with $``d"$ to get one string to the other.

Clearly, there won't be any deletions/insertions in this form of the problem, it will purely be swaps since the two strings are permutations of the same letters.

Now I know that the original edit-block problem with all operations is NP-Hard, however, would the restriction of only block swaps perhaps make this solvable in polynomial time? Most text I've read don't address this version and instead address variations of the original problem. Any help would be appreciated.


texts: Pi approximation with Montecarlo: Why not just evenly distributed points?

texts:
With the randomised algorithm for Pi approximation (see https://www.geeksforgeeks.org/estimating-value-pi-using-monte-carlo/ ), I keep wondering why just using points with an even distance should'n work just as fine.

Obviously, with the montecarlo method you get a better approximation the more random points you generate. But isn't an algorithm that just uses the 10000 in a 100x100 square just as good?


texts: Optimizing resource management game (similar to Farmville)

texts:
Given a fully deterministic single player resource management game
with a pre-known finite number of turns and reasonably simple rules
(eg, Farmville, if it were single player, deterministic, and ended
after a certain number of turns), is it usually possible to write a
computer program that can optimize the game in a reasonable amount of
time? Details:

I'm trying to create such a game (sort of a M.U.L.E. clone, but
not really). Players would compete individually to get the highest
score under a given set of starting conditions. The game must be
simple enough to be fun, but complex enough that someone can't write
a computer program to rapidly optimize it. The game is semi-tedious
(in its current form), so I encourage API/automated use.
Since the game is deterministic and finite, I realize that an
optimization algorithm must exist. So my question really is: can
someone always write an optimization algorithm that runs fast enough
to be useful?
I realize the answer depends on the actual game I write, so I'm
looking for one of these answers (roughly):

Give up. If you design a resource management game easy enough
for people to understand, someone could easily design an algorithm
to win it.
There's hope. Depending on how you design the game, it may or
may not be possible to write a reasonable algorithm to optimize
it. However, you have to be very careful.
Go for it. In general, there are no algorithms that can optimize
most resource management games. Barring extreme conditions, any
resource management game you design could not reasonably be
optimized by a computer.

There are Farmville strategy guides online, but they focus on
general strategy, not an explicit algorithm.
I realize this is a specific case of P != NP, and that's it
theoretically possible to create simple questions that cannot be
solved easily (eg, factor a product of two large primes) or even at
all (eg, the halting problem), but I'm wondering if resource
management games fall, in general, into the NP category.
For reference, the game will be a scaled down (and single player)
version of:

https://github.com/barrycarter/bcapps/tree/master/YAMC


texts:
What's the difference between a stream and a queue? They both have the concept of an ordered set of elements, but tend to have different implementations and a different vocabulary of 'insert'/'extract' (streams) vs. 'enqueue'/'dequeue' (queue). Are these interchangable? Do they suggest different concepts or patterns? If so, what are the differences?

Concrete example of 'stream insertion':
https://www.cplusplus.com/reference/ostream/ostream/operator%3C%3C/

Potentially useful conceptual pieces?

Stream as sequence of time-function data: https://web.archive.org/web/20160603162316/https://mitpress.mit.edu/sicp/full-text/sicp/book/node69.html
Stream as IO channel: https://en.wikipedia.org/wiki/Standard_streams


texts: 2D packing in fixed dimensions rectangle

texts:
Input:

a enclosing rectangle of size $(W, H)$
a family of rectangles $R= (R_1;R_2;\dots;R_n);R_i=(w_i;h_i)$

Output:

a scaling factor $s$
a 2D bin packing of $R$ in a rectangle of size $(sW, sH)$

I have a set of rectangles of various dimensions that I’d like to fit in an enclosing rectangle. This is a classic instance of the 2D-packing problem.
However, in my instance, the enclosing rectangle has fixed dimensions. All the rectangles should fit in it, but they possibly would have to be scaled and must keep their respective aspect ratios. They must not be rotated.

Most examples of 2D-packing algorithms find the enclosing square of least area, or assume that one of the dimensions isn't constrained.

I think that a good solution would be to find an enclosing rectangle R of aspect ratio (roughly) equal to that of the target fixed-dimensions enclosing rectangle T, then scale all the enclosed rectangles down with the ratio of R over T. It seems better to have a global ratio, so that rectangles keep their relative proportions.

I did not find any convincing algorithms, and cannot think of one except enumerating enclosing rectangles until one with a suitable aspect ratio is found.
Could you point me towards a working algorithm that I missed, or a better solution?

Related question, but the answer isn’t satisfying.

Imagine you want to display a bunch of pictures in a screen, however the screen's too small. So you display the picture in a virtual screen keeping the aspect ratio of the original screen, the scale the whole thing down.

Thank you!


texts: Why is the transform in Schönhage–Strassen's multiplication algorithm cheap?

texts:
The Schönhage–Strassen multiplication algorithm works by turning multiplications of size $N$ into many multiplications of size $lg(N)$ with a number-theoretic transform, and recursing. At least I think that's what it does because there's some other cleverness and I really don't understand it well enough to summarize accurately. It finishes in $O(N \cdot  lg(N) \cdot lg(lg(N)))$ time.

A number-theoretic transform is exactly like a Discrete Fourier Transform, except it's done in the finite field $F_{2^N+1}$ of integers modulo $2^N+1$. This makes the operations a lot cheaper, since the Fourier transform has a lot of multiplying by roots of unity, and $F_{2^N+1}$'s roots of unity are all powers of 2 so we can just shift! Also, integers are a lot easier to work with than floating point complex numbers.

Anyways, the thing that confuses me is that $F_{2^N+1}$ is very large. If I give you a random element from $F_{2^N+1}$, it takes $O(N)$ bits to specify it. So adding two elements should take $O(N)$ time. And the DFT does a lot of adding.

Schönhage–Strassen splits the input into $\frac{N}{lg(N)}$ groups with $lg(N)$ bits. These groups are the values of $F_{2^N+1}$ that it will transform. Each pass of the DFT will have $O(\frac{N}{lg(N)})$ additions/subtractions, and there are $O(lg(\frac{N}{lg(N)}))$ passes. So based on addition taking $O(N)$ time it seems like the cost of all those additions should be $O(N \frac{N}{lg(N)} lg(\frac{N}{lg(N)}))$, which is asymptotically the same as $O(N^2)$.

We can do a bit better than that... because the values start out so small, the additions are quite sparse. The first pass' additions really only cost $O(lg(N))$ each, and the second pass' cost $2^1 O(lg(N))$ each, and the i'th pass' cost $O(min(N, 2^i \cdot lg(N)))$ each, but that still all totals out to a terrible $\frac{N^2}{lg(N)}$.

How is Schönhage–Strassen making the additions cheap? How much do they cost overall?

Is it because the algorithm actually uses $F_{N+1}$ (with $N$ guaranteed to be a power of 2)? There's enough stacked $2^{2^{n}}$ and german in the paper that I'm really not sure. On the other hand, I don't think that guarantees enough roots of unity for things to work out.


texts: Generalised letrec semantics for mutual recursion

texts:
I'm new to system types and I was wondering how mutual recursion is defined through generalized
e::= ..|let rec x1=e1 ,...., xn=en in e .What has to be added in the "simple" let rec semantics and evaluation rules and how is its syntactic sugar (using fix ) changed as well!


texts: Convert 24(decimal) to modified IEEE 754 floating point format?

texts:
Here's what I have as the tweaked format I'm to use:

S EEE MMMM (excess 8 format)
s = sign bit, E = exponent bits, M = mantissa/fraction bits
Otherwise, it follows the IEEE 754 in principle.
The values:

(-1)^s x 0.0: e == 0, && m == 0

(-1)^s x 0.M x 2^-2: e == 0, && M != 0

(-1)^s x 1.N x 2^(e - 3): 0 < e < 7

(-1)^s x infinity: e == 7 && m == 0

NaN: e == 7 && m != 0

That's the formula I've been provided. I need to change 24(decimal) into a floating point binary value, but I continually end up with NaN. Am I doing something wrong?

It is technically a homework question, so if you don't want to provide an exact answer, I'd still be very appreciative if someone can tell me if I'm doing this right or wrong.


texts: Under what conditions is K-means clustering transformation-invariant?

texts:
Given a set of data points $X = \{x_1, x_2, \ldots, x_m\}$ where $x_i \in \mathbb{R}^d$ we run K-means on $X$ and obtain the clusters $c_1, c_2, \ldots, c_k$.

Now, if we create a new dataset $Y = \{y_1, y_2, \ldots, y_m\}$ where $y_i = Ax_i + b$ and $y_i \in \mathbb{R}^d$ and run K-means on $Y$ to get clusters $g_1, g_2, \ldots g_k$.

Under what conditions of $A$ and $b$ are we guaranteed to get the same clusters?

Let's assume that K-means is using the euclidean distance and has same initial conditions on both algorithms, that is, if the initial centers for X are $c^0_1, \ldots, c^0_k$ then the initial centers for Y are $g^0_1, \ldots, g^0_k$ where $g^0_i = Ac^0_i + b$.

So far I've thought that $A$ has to be full rank and $b$ can be any vector. However, I haven't been able to prove it.


texts: Maximum number of states in minimized DFA from NFA with $n$ states

texts: If an NFA with $n$ states is converted to an equivalent minimized DFA then what will be the maximum number of states in the DFA? Will it be $2^n$ or $2n$?


texts: multiset variant of subset sum problem known algorithms

texts:
I have been working in the time analysis for an exact solver I designed for the subset sum problem accepting multisets as input instances, and determined its time complexity to be dependent on the multiplicity ($m$) of the elements in the input.

For input instances containing elements having $m \leq 2$, the  time complexity is $O(2^{n/2} \cdot 0.75^{\frac{d/2}{n}})$ where $d=$ # of elements with $m=2$.

For example, when $d=n/2$,  then:

$O(2^{n/2} \cdot 0.75^{\frac{d/2}{n}}) \approx  O((1.4142 \cdot 0.93)^n) \approx O(1.316^n)$

For input instances containing elements having $m = 1 $ and $m=4$, the  time complexity is $O(2^{n/2} \cdot 0.312^{\frac{d/2}{n}})$ where $d=$ # of elements with $m=4$.

For example, when $d=n/4$,  then:

$O(2^{n/2} \cdot 0.312^{\frac{d/2}{n}}) \approx  O((1.4142 \cdot 0.86)^n) \approx O(1.223^n)$

And following the above configuration, for $m=8$ and $d=n/8$ is

$O(2^{n/2} \cdot 0.035^{\frac{d/2}{n}}) \approx  O((1.4142 \cdot 0.81)^n) \approx O(1.147^n)$

I have yet to complete the time analysis for mixed cases (different multiplicities in the input instance) but my educated guess is it will be a composite of the above TCs.

Besides to ask for comments, I am looking as well for other known algorithms with a similar behavior to compare approaches (looked for them but found nothing so far...)


texts:
I am trying to learn CS fundamentals and I am confused by static vs dynamic allocated arrays.  My only programming experience is JavaScript and all online resources I am using refer to C language.

A dynamic allocated array is made when the application starts and it cannot be resized.  So how is this different from static allocated array, if to expand the array you have to make a new and bigger array and copy over the contents?


texts: What is the consequence of $\oplus P\neq PP$?

texts:
From $P\subseteq \oplus P \subseteq PSPACE$ and $P\subseteq PP \subseteq PSPACE$ we infer $\oplus P\neq PP$ gives that
$$P\neq PSPACE.$$

Are there any other consequences?


texts: If $g ∘ f$ is primitive recursive, are $f$ and $g$, too?

texts: Assuming I have functions $f, g : \mathbb{N} \to \mathbb{N}$ and I know that $g \circ f$ is a primitive recursive function. What can I tell about $f$ and $g$? Are they primitive recursive as well? Or at least one of them?


texts:
Does transforming a CFG to Chomsky normal form make it unambiguous?
And if not, is there a technique to convert a CFG G to an equivalent CFG G', so that G' is both unambiguous and LL(1)?


texts: Understanding A Recursive Definition of CL-Terms in Combinatory Logic

texts:
From page 26 of Lambda-Calculus and Combinators:

  Definition 2.18 (Abstraction) For every CL-term $M$ and every variable $x$, a CL-term called $[x].M$ is defined by induction on $M$,
  thus:

  (a) $[x].M \equiv \mathbf{K}M$ if $x \notin FV(M)$;

  (b) $[x].x \equiv \mathbf{I}$;

  (c) $[x]Ux \equiv U$ if $x \notin FV(U)$

  (f) $[x]UV \equiv \mathbf{S}([x]U)([x].V)$ if neither (a) nor (c)
  applies.

Here $\mathbf{I}$ is meant to denote the identity operator, $\mathbf{K}$ the constant operator, and $\mathbf{S}$ the "stronger composition operator" where in mathematical notation:

$$
\mathbf{S}(f,g))(x) = f(x, g(x)) \text{ for functions $f$, $g$}
$$

Question: It seems that (f) of this definition just comes out of nowhere. I have no idea what is motivating it behind the scenes. Does anybody have any insight on where this definition comes from?


texts: Does the Working Set Paging Algorithm use a separate page table?

texts:
I am doing research on paging algorithms. While learning about the working set algorithm from several scientific sources I was not really able to figure out where exactly the working set is defined or realized.

I can only imagine two ways of realising this. The first is to put it into the page table file with indication bits; the second is to have another page table for the working set.

To be more specific: is the Working Set a completely different, separate list derived from the page table entries, or is it defined in the page table entries?


texts: Is page size always equal to frame size?

texts:
I'm learning about paging. My book says that the logical addresses generated by the CPU are in the form |p|d|(page number, page offset) and the physical addresses are in the form |f|d|(frame number, frame offset). It is also specifically mentioned that d i.e. the offset is copied directly to generate the physical address from the logical ones.

Now, commonsense says that if the offset is copied directly, the page size HAS to be equal to the frame size (otherwise, offsets wouldn't correspond). But unfortunately my book doesn't say anything about that.

So, is page size always equal to frame size?


texts: How do I get and/or verify a formal Grammar for a given formal Language?

texts:
I was given the Language $L=\left \{ a^nb^na^nb^n |n\epsilon \mathbb{N} \right \}$ and I'm supposed to find a Grammar that generates that Language.
After some trying and fiddling I found one that I think works. The question is how do I verify it? On paper it looks fine, but are there some tools check this for me? Also are there easier methods than trying out by hand or brute force?

The Grammar I found is as follows:

$S\rightarrow aB_{1}A_{2}B_{2}|aB_{1}PA_{2}B_{2}$

$P\rightarrow A_{1}B_{1}A_{2}B_{2}|A_{1}B_{1}PA_{2}B_{2}$

$B_{1}A_{1}\rightarrow X_{A1}A_{1}$

$X_{A1}A_{1}\rightarrow X_{A1}X_{B1}$

$X_{A1}X_{B1}\rightarrow A_{1}X_{B1}$

$A_{1}X_{B1}\rightarrow A_{1}B_{1}$

$B_{2}A_{2}\rightarrow X_{A2}A_{2}$

$X_{A2}A_{2}\rightarrow X_{A2}X_{B2}$

$X_{A2}X_{B2}\rightarrow A_{2}X_{B2}$

$A_{2}X_{B2}\rightarrow A_{2}B_{2}$

$aA_{1}\rightarrow aa$

$aB_{1}\rightarrow ab$

$bB_{1}\rightarrow bb$

$bA_{2}\rightarrow ba$

$aA_{2}\rightarrow aa$

$aB_{2}\rightarrow ab$

$bB_{2}\rightarrow bb$


texts: Show that the equivalence problem for deterministic Turing machines and its complement is not semi-decidable

texts:
I would like to show that
$$EQ_{DTM} = \{ (\langle M_1\rangle,\langle M_2\rangle) \mid M_1\text{ and } M_2 \text{ are  DTMs  and } L(M_1)=L(M_2)\}$$
 and
$$\overline{EQ_{DTM}}$$
 are not semi-decidable. I think there must be a reduction from the complement of the halting problem.


texts: How to generate globally unique timestamps for transactions in distributed database systems?

texts:
According the paper [1] (Section 4), timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the following, it reads

  Each transaction is assigned a unique timestamp by its TM (transaction manager). The TM attaches the timestamp to all dm-reads and dm-writes issued on behalf of the transaction, and DMs (data manager) are required to process conflicting operations in timestamp order.

However, this paper did not explain

  Question: How to generate the globally unique timestamps for transactions in distributed database systems (assuming no centralized coordination)? What are the commonly used techniques (with references) in this area?

Specifically, is the <local clock, site-id> pair sufficient and appropriate as a timestamp mechanism? If not, why?

[1] Concurrency Control in Distributed Database Systems by Philip A. Bernstein and Nathan Goodman. Computing Surveys, Vol.13, No., 2, June 1981.


texts:
In the polynomial hierarchy we have $\Sigma_2=NP^{NP}$ and $\Pi_2=co\Sigma_2$.

So we have $\Pi_2=co(NP^{NP})$.

Is it same as $(coNP)^{NP}$?

I just wonder why not a hierarchy with $coNP$.


texts: Removing any arbitrary vertex from a directed graph?

texts:
I came upon this particular question which I do not understand from Jeff E. Algorithms, Chapter 9, ex. 8. https://jeffe.cs.illinois.edu/teaching/algorithms/book/09-apsp.pdf
How can we remove any arbitrary vertex from a directed graph, with weighted edges that can be positive negative or zero, without changing the shortest paths distance between all other pairs of vertices, in $O(V^2)$.

Let $G=(V,E)$ be a directed graph with weighted edges; edge weights could be positive, negative, or zero.
a)  How would we delete an arbitrary vertex $v$ from this graph, without changing the shortest-path distance between any other pair of vertices? Describe an algorithm that constructs a directed graph $G'=(V\setminus\{v\},E')$ with weighted edges, such that the shortest-path distance between any two vertices in $G'$ is equal to the shortest-path distance between the same two vertices in $G$, in $O(V2)$ time.

I have an idea would be to just consider the incoming edges $u \rightarrow v$ and outgoing edges $v \rightarrow t$ and for each $u$, add an edge $u \rightarrow t$ with the weight being the sum of the weights of $u \rightarrow v$ and $v \rightarrow t$, for all $t$. The second part builds upon the first, but now I am confused about how to go about it.

Now suppose we have already computed all shortest-path distances in $G'$.Describe an algorithm to compute the shortest-path distances in the original graph G from v to every other vertex, and from every othervertex tov, all in $O(V^2)$ time

Is there a way to do this now that I have deleted the node?


texts:
To show that some problem X is NP-complete, we usually show that it is in NP and that an efficient algorithm for deciding X implies an efficient algorithm for deciding some known NP-complete problem like SAT.

At the same time, informally, the NP-completeness definition usually says that solving any single NP-complete problem implies a solution to all NP-complete problems.

If both statements above are correct, then the above "proof approach" (showing that "solving X" $\implies$ "solving SAT") also somehow implies that an efficient algorithm for SAT implies an efficient algorithm for X.
In general reductions are not symmetric, so why is this the case here?


texts: Can not understand idea of the KMP algorithm

texts:
I am using Sedgewick's Algorithms (4th ed) to learn Knuth-Morris-Pratt substring search algorithm. The key step is construct the DFA array corresponding to a given pattern. The authors say:

  The key observation is that the characters in the text that would need to be rescanned are precisely pat.charAt(1) through pat.charAt(j-1): we drop the first character to shift right one position and the last character because of the mismatch.

I can't understand the above, for example. If the pattern is ABABAC, and the text string is ABACABABACA.  and there are two pointers i and j for text string and pattern respectively.

If $i=3$, the character $c$ in the text string is mismatch, where the pattern is $b$. then we need to rescan from the beginning of the pattern. not the second character : pat.charAt(1) .

I think I am misunderstanding what the author intended to express. What does the author mean?


texts: If a polygon is monotone with respect for a line, how can I determine the two monotone polygonal chains?

texts:
I need to determine the two monotone polygonal chains of a y monotone polygon.
I have the vertices stored in an array.

How can I do this?


texts:
I'm to write a syntax that will allow for a recursive function, i.e.
f(x) = if x == 0 then x else f(x+1)

Here's one attempt at creating the grammar:

But I don't think this is right since there's no such thing as parameterized syntax.


texts: purpose of stack segment in assembly language

texts:
The code snippet below is the "beginning lines of an assembly language program" used to display a single line string .
stack segment para stack 'stack'
       db 16 dup(0)
stack ends

my question is : why stack segment is available in assembly program? And how do I define this 'stack'? Any help will be appreciated. My basic idea is that it is used to temporarily hold data.


texts: BIT: What is the intuition behind a binary indexed tree and how was it thought about?

texts: A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in all the explanations, I cannot understand the intuition behind such a tree? How was it invented? What is the actual proof of its correctness?


texts: Algorithm for first-price, sealed bid simultaneous auctions for distinct items and budget-constrained bidders

texts:
Context:
I play in a simulated online basketball league (a la the NBA) where each human player controls one of the teams. When each simulated basketball player is a free agent (that is, their previous contract with a team has expired) they field offers from teams and a group of moderators decides which team that player will join. Teams have a limited budget, players have different values to different teams, and teams need to be able to bid on more players than they can afford using a list ordered by priority so that they can use all of their budget.

Our current system for handling the free agency period has several problems so I would like to devise a new system.

I would like to write a script that takes in a set of ordered bid lists (one for each team in our league) and outputs an order in which each item should be sent to a decision function (i.e. in this case, the group of moderators that decide among the bids for that item) optimized such that each team wins the auctions for their highest priority bids possible. Lower priority bids may become invalid as a result of teams using their budget by winning higher priority auctions.

I think there will be circular dependencies between auctions such that the algorithm will not be able to determine which should be send to the decision function first, and that's okay as long as that group of circularly dependent auctions is output and the moderators can decide those on a case-by-case basis.

I have found some papers (one, two) about similar scenarios but in these papers the items for auction are identical.

My hunch is that this problem for unbounded N (teams) and M (players) is intractable but for our limited N=30, M~=100 I think it should be possible to compute in a reasonable amount of time. I'm also okay with an approximation instead of an optimal solution, or to find out that no optimal solution exists - just a solution that approaches 'good enough' is good enough for me.


texts: NP-completeness of the exact distance problem

texts:
I am currently learning about NP-complete problems and I want to make sure my understanding is correct.

Here is a problem I am working on currently:

  The exact distance problem is, given an edge-weighted graph $G = (V,E)$, vertices $v_1,v_k$, and a distance $D$, is there a simple path from $v_1$ to $v_k$ with length exactly $D$?

The first part of my solution is proving that the problem is in NP. I did this by picking a solution to the problem and proving that we can verify the solution in polynomial time. My proof showed that we can verify the solution in $O(mn)$ time, where $m$ is the number of edges and $n$ is the number of vertices.

The next part is showing that a problem we know to be NP-complete can be reduced to the exact distance problem. I am having trouble deciding on an easy NP-Complete problem to use in this part. Would the Hamiltonian Path problem be a good choice?


texts: Is $O(\log_2 n)$ close to $O(n)$ or $O(1)$?

texts: We know that asymptotically $O(1)$< $O(\log_2 n)$ < $O(n)$, but $O(\log_2 n)$ is asymptotically close to $O(n)$ or $O(1)$?


texts:
A linear code is termed as an $\epsilon -$balanced code if all the codewords are having fractional hamming weight $\in (1/2-\epsilon,1/2+\epsilon)$. I want to show that for every $\epsilon\in (0,1/2)$, $\exists$ a linear $\epsilon -$balanced code $E:\{0,1\}^n\mapsto \{0,1\}^{poly(n/\epsilon)}$, with efficient encoding decoding algorithm.
If we ignore the efficient encoding decoding and polynomial stretch, then any $A_{n\times k}$ matrix over $\mathbb{F}_2$, where $2^n\geq k>2^{n-1}$, gives such a code, as any non zero vector in $\{0,1\}^n$, is orthogonal to exactly half of the total number of vectors in $\{0,1\}^n$. So, if we choose a random $A_{n\times k}$,  then $Ax$, $x\in\{0,1\}^n$ has fractional hamming weight, $\in (1/2-\epsilon,1/2+\epsilon)$.$\epsilon$ depends on $k$ and for $k=2^n$, $\epsilon=0$.
I also found in wikipedia that, if all the rows of $A$ are $\epsilon-$biased, then the corresponding code is $\epsilon-$ balanced. I am not quite sure what $\epsilon-$ biased code means and their ways of construction. Can anyone suggest me a simple way to construct these sets?
By the efficient encoding-decoding requirement, one method also comes in mind to use concatenation of Walsh Hadamard Code and Reed Solemon Code. These meets the encoding-decoding requirement and strech requirement, but whether it can be made $\epsilon-$balanced is unclear to me.
Can anyone answer this?


texts: Deciding if a Turing machine has made a left move

texts:
In writing a decider for a machine to see if it has made a left move or not on an input of w, it is said that if we continue the computation for $|w|+N+1$ ($N$ : number of states) number of steps, we can make a decision for this decide.

I didn't get why $|w|+N+1$ number of steps. Could someone explain this in more detail?


texts: Show Language is not context free without pumping lemma

texts:
Can we show that following language is not context free using Push down automata approach?

L = {a^i b^i a^i : i>=1}

For every a we will Push 'A' onto stack, for every b we will pop 'A' out of stack so at the end we will have a's onto stack and the input word would be empty as string would be something like aabbaa

Does it seem correct?


texts: The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols

texts:
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements about a pushdown automata (PDA) which accepts by empty stack, as:

1. $n$, the total length of the input, is surely an upper bound on the number of states and stack symbols.

2. One rule could place almost n symbols on the stack.

The following statements were made while the authors were about to make some notes about the decision properties of CFLs(Context Free Languages)

Now here are some points by which I am possibly able to contradict the claim rather than proving it correct.

Suppose $n$, is the total length of the input, but as per the design of the PDA it might so happen that to accept the input string all the states of the PDA is not involved, so by this we can't say that $n$ is an upper bound on the number of states the PDA has.
Though the PDA accepts by empty stack, it might so happen that a transition function adds more than $n$ elements on the top of the stack, but at the end on consuming the $n$ input symbols we can stay on the particular state and use epsilon transitions to just remain in the same state and pop the elements from the stack till it becomes empty. So how can we say that $n$ is an upper bound on the number elements on the stack? We arrive at a contradiction...

I don't understand where I am making the mistake, because the same statements are written in the 3rd edition of the book without any changes being made from the second edition which makes it probable that the statement is correct.

I have attached the corresponding portion of the text below:


texts: Search tree with associative union and worst case insert/delete better than O(n)?

texts:
Is there a search tree where union is associative, so $a \cup (b \cup c) = (a \cup b) \cup c$ gives a tree with the same structure?

A complete binary tree would be such a tree, but for example a red-black tree has several possible constructions for a given set of elements.

Is there such a tree that does better than $O(n)$ for common operations such as insert or delete?


texts: Determining the complexity of calculating n-th root of an integer, and performing modulo arithmetic?

texts:
For a while now, I have been struggling to find a source explaining the complexity of the following 2 elementary operations

Calculating the $n^\text{th}$ root of an integer $x$,
$$
\sqrt[\leftroot{-3}\uproot{3}n]{x}
$$
Checking whether
$$
a \equiv b \mod r
$$
for $a,b,r \in \mathbb{N}$

I now think I may have come close to finding an answer to the second of these problems, but I am not certain.

On pages 10-11 of the book Édouard Lucas and Primality Testing (by Hugh C. Williams), the following statement is made:

  For any $m$ and $a,b$ with $0 < |a|, |b| < m$ calculating
  $$
r \equiv ab \mod m
$$
  can be done in $O((\log m)^2)$ operations.

Am I to assume, based on this, that operation 2. has complexity $O((\log m)^2)$?

I also suspect that operation $1$ has complexity $O((\log m)^2)$, but I have no justification for this. Could someone please also tell me whether this is correct?


texts:
I need to determine which complexity class this problem belongs to:

  Given a graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of length $k$ exist between thesee two vertices?

How can I approach this problem to solve it?


texts: How Should I Disambiguate Symbols for Type Placeholders and the Free Monoid Operator?

texts: I've been writing kinds using asterisk * as a placeholder for a type. For example  → * is the kind of all functions of time. This was fine until I needed to use the free monoid operator *. I was thinking that I could write the free monoid as ٭ (the arabic five pointed star), but maybe there's a better option. What's a good way to disambiguate type placeholders and the free monoid operator?


texts: Prove, that $A^+\subseteq A^*$ where $A$ is a formal language

texts:
Prove, that $A^+\subseteq A^*$, where $A$ is a formal language.

The definition of $A^+$ is $\bigcup_{i\in\mathbb{N}\setminus \{0\}}A^i$,  which would be $A^1 \cup A^2 \cup \dots \cup A^i$. Likewise, $A^*$ is $\bigcup_{i\in\mathbb{N}}A^i$ and therefore $A^0 \cup A^1 \cup \dots \cup A^i$.

Suppose, $x\in A^+$. By definition $x\in A^+ \land x\in  A^*$ for all $x\neq A^0$, which is the set of the empty word. We can conclude, that $A^1\cup A^2\cup \dots \cup A^i \subseteq A^0\cup A^1\cup \dots \cup A^i$ and $\bigcup_{i\in\mathbb{N}\setminus \{0\}}A^i \subseteq \bigcup_{i\in\mathbb{N}}A^i$, that's why $A^+\subseteq A^*$.

Is this "proof" ok?


texts:
Lets consider a new operator $B$ where $a B b$ means "in every execution, if $b$ holds some time, then $a$ does so before it" and we're asked to define it in CTL.

My working: the system can only fail if $b$ holds. If $b$ doesn't hold, we're in the clear - so one possible path could be $(¬ □ b)$. The only other path that could hold is one where $a$ happens before $b$, so $(a$ $U$ $b)$ is another path. Overall we're left with $∀((a U b) ∨ (¬ □ b))$. For every path either $a$ happens before $b$ OR $b$ never happens.

Is the way I reasoned about this question correct? Are there any holes in my logic that I should re-consider? Please reply as a comment if possible, and many thanks in advance for any input.


texts:
I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it.

Question

Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma. I know the correct way of prove with factorial or using closure. However today someone explain a way to me and I couldn't find what is wrong with it. I think it is wrong but if it is true, is it possible to explain why?

Proof (Maybe correct):

we suppose that that $L$ is regular and there is a machine with $u$ state that accept it. If it is a NFA, we can convert any NFA to DFA with for example $k$ state.
We have a group of strings like $a^kb^{k + t}$ for every $1 \le t \le k$ which accepted with machine.
There is only one way for read $a^k$ because our machine is DFA so we can write $a^k = a^sa^ta^p$ that $|a^sa^t| \le k$ and $|a^t| \ge 1$ and $a^t$ is cycle, so with pumping lemma we can say that $a^{k + t}b^{k + t}$ (with one more time of cycle) belongs to $L$ and it is contradiction. (one of our strings in our first group will fail) so our language is not regular.

My Problem

Because we we get a group of strings (instead just one strings which is normal in proves) and use same $t$ when break $a^k$ to $a^sa^ta^p$, is it true anymore? If no or yes, please explain.

My explanation

I think we can construct a NFA that accept each of $a^kb^{k + t}$ (for each $t$) with different size of cycle (cycle that is used in pumping lemma) however when convert it to a DFA, I can't understand how to prove it.


texts:
I'd like to show that the language DISCONNECTED-SET, defined by $$ \{\langle G, k\rangle | \text{$G$ is an undirected graph that contains a disconnected set of size $k$}\},$$ is NP-complete. (A disconnected set $S$ is defined as a set of vertices such that for every pair of vertices $u,v \in G$, if there is no edge between $u$ and $v$, then at least one of the vertices is in $S$.)

I'm under the assumption that it could be done by reduction from CLIQUE. I've made the following observations (which I'm unable to utilize, though):

If we have a graph $G$, then the maximum disconnected set of its complement $G'$ has a size equal to the number of nodes in $G$ that belong to connected components of size at least 2 in $G$.
If we have isolated nodes in $G$, the sizes of the disconnected sets in $G'$ are unchanged.

May I just ask for a tiny tip that would get me going in the right direction, not a complete proof. Thank you.


texts: Regular expression for a binary string containing even number of 0's

texts:
To get the regular expression I made a finite automata as the following (not sure if you can directly write regular expression without it):

The regular expression for the above according to me should be $(1+01^*0)^*$ but elsewhere I have seen it can be $(1^*01^*01^*)^*$. Why is it different?


texts: Can we construct problems that can be solved in $\Theta(n^c)$ time, and tested in $O(n)$ time

texts:
CS sometimes seems take for granted that $\mathcal O(\text{poly}(n))$ is "easy", while $\mathcal O\left(2^{poly(n)}\right)$ is "difficult". I am interested in research into "difficult" polynomial-time algorithms, where the best-case solution to the constructed problem runs in $\Theta(n^c)$, where $c$ can be chosen to be large; but the solution could be tested in $O(n)$ time.

Question:

  Given an integer $c$, can we construct problems that would:

  Take $\Theta\left(n^c\right)$ best-case-time to solve,
  While taking $\tilde{\mathcal O}(n)$ time, and $\tilde{\mathcal O}(n)$ space, to test a solution?

($\tilde{\mathcal O}(n)$ is soft-big-oh, meaning $O(n \log^k n)$ for some $k$)

Something I note - I might be mistaken somewhere here - is that presumably, if there is a $\mathcal O(n)$ algorithm to test the solution, then perhaps there can be a $\mathcal O(n)$ reduction to $\rm k\text{-}SAT$. If so, and, if $\rm P=NP$, and there was a polynomial-time algorithm, say ${\rm S{\small OLVE}}\left(\Phi(\mathbf x)\right) \in O({|\mathbf x|}^{\alpha})$ time, then I think this might contradict our $\Theta(n^c)$ problem, if $\alpha < c$.

The motivation would be to research the possibility of having a "one-way-function", that is linear(ithmic)-time computable, and best-case "difficult"-polynomial-time invert-able, where "difficult" means a high degree polynomial, instead of the usual exponential-time definition of "difficult"; perhaps this might be able to be used for cryptography even if $\rm P=NP$ (like "post-P-equals-NP-cryptography", similar to how there is a field of "post-quantum-cryptography").


texts: How to solve this problem using the Maximum matching algorithm for general graph?

texts:
For any general graph G(V,E) , the maximum matching can be calculated in O(√V.|E|) time using the following algorithm :

https://www.researchgate.net/publication/221499631_An_Osqrtv_E_Algorithm_for_Finding_Maximum_Matching_in_General_Graphs

The following problem has 5-parts : -

1)Calculate maximum matching of Graph G

Can Tutte Matrix be used here ?

2)Calculate maximum matching of Graph G1 where G1 is the Line-Graph of graph G

3)Calculate maximum matching of Graph G2 where G2 is the Line-Graph of graph G1

4)Calculate maximum matching of Graph G3 where G3 is the Line-Graph of graph G2

5)Calculate maximum matching of Graph G4 where G4 is the Line-Graph of graph G3

Part-1 can be solved using the algorithm above.

My approach for solving part-2 is to construct G1 and then apply the algorithm on it , same for G2,G3,G4 , but the problem is that number of nodes and edges increase a lot in G1,G2,G3,G4 , if say , G has 3000 nodes and same number of edges, G3 might have more than 108/109 nodes and edges , so I cannot construct such a large graph as it will be inefficient in time and space to do it . How can solve the remaining parts efficiently ?


texts: A language in NSPACE(O(n)) and very likely not in DSPACE(O(n))

texts:
Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE(O(n)) = LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular languages) or $\mathbf{CFL}$ (context-free languages).
And also the open problem $\mathbf{DSPACE(O(n))} =^{?} \mathbf{NSPACE(O(n))}$ is not so famous as the "analogous" problem: "$\mathbf{P} =^{?} \mathbf{NP}$".

Well, is there really such an analogy:?

Is there a language in $\mathbf{CSL}$ which couldn't be proved to be in $\mathbf{DSPACE(O(n))}$  (like $\mathbf{NP}$ complete languages)?
Moreover: Is there a language $L$ in $\mathbf{CSL}$ which is "complete" in the following sense: if we can prove that $L$ is in $\mathbf{DSPACE(O(n))}$ we get that $\mathbf{DSPACE(O(n)) = NSPACE(O(n))}$?
(Maybe just a matter of opinion) Are both problems on the same level of difficulty?


texts: Separating labelled points with a plane, minimizing label variance

texts:
Suppose we have observations with associated labels  $\{({\bf x}_1, y_1), ({\bf x}_2, y_2), \dots, ({\bf x}_n, y_n)\}$ where ${\bf x}_i \in \mathbb{R}^d$ and $y_i \in \mathbb{R}$.
Can we efficiently find a separating plane of the observation space $\mathbb{R}^d$ such that the sum of the variances of the labels of the observations within both groups is minimized?
That is, if a separating plane is parametrized by $({\bf v}, c)$ splitting the space into groups ${\bf x}_i^T {\bf v} < c$ and ${\bf x}_i^T {\bf v} \geq c$ we can formalize our search problem as:
$$\arg \min_{{\bf v}, c} {\Big (\text{var}(\{y_i : {\bf x}_i^T {\bf v} < c\}) + \text{var}(\{y_i : {\bf x}_i^T {\bf v} \geq c\})\Big)}$$
where $\text{var}(S) = \frac{1}{|S|}\sum_{t\in S}{\big(t - \frac{1}{|S|}\small\sum S\big)}^2$ is the standard definition of variance, optionally with Bessel's correction applied (either definition is fine).

The context  is that I had the idea of replacing the simple single-attribute decision nodes of decision trees with separating planes instead. The above method would find the greedy best split. I was wondering if doing this is even tractable?

Note that given $\bf v$ we can find optimal $c$ in $O(n \log n)$ time by computing all breakpoints ${\bf x}_i^T{\bf v}$, sorting, and computing the variances of each breakpoint in an online manner, choosing the best one as $c$. This gives us a randomized approximation algorithm, by repeatedly choosing a random (or better, quasi-random) unit vector $\bf v$ and finding optimal $c$. This continues for as long as desired, and the best result is returned. In theory given enough time this should return the optimal result (since a minimizing $\bf v$ is not unique and has constant probability of being chosen in any iteration), however I don't know how well it can be expected to approximate given a certain number of iterations.


texts: Addition errors in IEEE754 floating point representation

texts:
So in class, we were talking about the idea of floating point precision in IEEE754 format, and how, when some numbers are added, precision is lost. My professor then gave the following example of a large absolute error between what we think the answer might be, and what the answer actually is when our program (written in Java) actually compiles it:

$0.4 \times10^{30} + 1.1 \times10^{30}$

Compiling this in Java, i get $1.5000001 \times 10^{30}$

My question is, why does this happen? Printing out the IEEE754 format of the two numbers, I get:

$\space\space\space0[11100010]10111100010010010101011=+1.10111100010010010101011\times2^{99}$
$+0[11100001]01000011000111100001000=+1.01000011000111100001000\times2^{98}$

So, I suppose when you add these, you end up loosing precision, but exactly how? Moreover, how can I even tell, before adding, that the addition of two numbers will make them loose precision? Or is the only way to just plus into a program and see what happens? None of this was really covered in class unfortunately.


texts: A monad is just a monoid in the category of endofunctors, what's the enlightenment?

texts:
Pardon the word play. I'm a little confused about the implication of the claim and hence the question.
Background: I ventured into Category Theory to understand the theoretical underpinnings of various categorical constructs and their relevance to functional programming (FP). It seems (to me) that one of the "crowning gems" at the intersection of Cat and FP is this statement:
A monad is just a monoid in the category of endofunctors
What is the big deal about this observation and what are its programmatic/design implications? Sources like sigfpe and many texts on FP seem to imply the mindblowingness of this concept but perhaps I'm unable to see the subtlety that's being alluded to.
Here's how I understand it:
Knowing something is a monoid allows us to extrapolate the fact that we can work within a map-reduce setting where the associativity of the operations allows us to split/combine the computation in arbitrary order i.e., (a1+a2)+a3 == a1+(a2+a3). It can also allow one to distribute this across machines and achieve high parallelization. (Thus, I could mentally go from a theoretical construct -> computer science understanding -> practical problem solving.)
For me it was obvious (as a result of studying Cat) to see that monads have a monoidal structure in the category of endofunctors. However, what is the implication one can draw from this and what is its programmatic/design/engineering impact when we're coding with such a mental model?
Here's my interpretation:

Theoretical Implication: All computable problems at their heart are monoidal in a sense.

Is this correct? If so, I can understand the enlightenment. It's a different perspective on understanding the notion/structure of computable problems that wouldn't be obvious if coming from only a Turing/Lambda model of computation and I can be at peace.
Is there more to it?

Practical Implication: Is it simply to provide a case for the do-notation style of programming? That is, if things are monoidal we can better appreciate the existence of the do/for constructs in Haskell/Scala. Is that it? Even if we didn't know about the monoidal underpinnings, we needn't invoke the monoidalness to make this claim since bind >>= and flatMap constructs are defined to be associative. So what gives? Or is it more to do with the foldability of monadic constructs and that is the indirect enlightenment that is being alluded to?

Question(s): What am I missing here? Is it simply the recognition of the fact that monads are generalized monoids and that they can be combined in any order similar to map-reduce operations like monoids? How does knowing about the monoidal property help improve the code/design in any way? What's a good example of before/after to show this difference (before knowing about monads/monoidality and after)?


texts: Struggling with Pumping Lemma application

texts:
I have studied Pumping Lemma carefully and have solved many exercises about it but I can't get an idea on how to solve this one: can anyone help me?

Let L = { w#x | x is a substring of w }. Prove that L is not regular.

I have tried setting the Pumping length to |w| and to |x| but I just don't find words that are not in L..

Thx in advance


texts: Wikipedia says that Hamiltonian path problem is NPC, but Parity Hamiltonian path problem (i.e., is there an odd amount of hamiltonian path) is P. Does a reduction from, e.g., SAT, to HPP, unavoidably duplicate some solutions?


texts: What to consider while proving NP-completeness?

texts:
Suppose that a problem $P$ is known to be NP-hard.
The input to the problem is a set of $k$ lines in 2D, a set of $n$ points, and $m < n$ pairwise distances among the points.
The goal is to place each point on one of $k$ lines, satisfying the given pairwise distances.
Disclaimer This problem might not be an NP-hard problem, but for the sake of simplicity, suppose that it is.

Since the problem is assumed to be NP-hard, having a polynomial time solution checking algorithm is sufficient to show NP-completeness.

At first sight, it seems trivial
Step 1: check whether the pairwise distances are satisfied [takes $O(m)$ time].
Step 2: check for each point whether the point is on a given line. [takes $O(n*k)$ time].

However, if one of the coordinates has exponentially many bits with respect to the input, then is this considered as a exponential-time checking? Or it is still polynomial-time with respect to the length of the solution?


texts: Derandomize MAX-CUT problem using $\log n$ bits

texts:
Consider the MAX-CUT problem. We can flip $n$ coins to generate a random cut, and  by linearity of expectation we get that with "good probability" our cut we'll be bigger then $\frac{n}{2}$.

Using pseudo random generators (XOR for example) we can generate $n$ pairwise  independent bits from $\log n$ random bits. Using that approach, we can de-randomize the MAX-CUT problem with polynomial complexity.

With that algorithm, we are only checking $n$ possible cuts, where there are total of $2^n$. Is it promised that a "good" cut is within these $n$ cuts? Why?


texts: What real-world computer languages cannot be described by deterministic grammars?

texts:
Are there any examples of real-world computer languages that are non-deterministic?

By computer languages I include programming languages, markup languages, query languages, modeling language, transformation languages, etc.

By non-deterministic I mean they cannot be parsed with deterministic grammars.


texts: Why has Windows used NTFS for 20+ years, while many different systems have trendend in the linux community over the same time?

texts:
I'm a first year MS:CS student, and my data structures class has inspired me to research file systems and their implementations.  I recall using ext2, then ReiserFS, then ext3, then ext4, and now btrfs seems like the new thing.  I understand (more or less) what changed from each of these, and their relative improvements, but what I don't understand is how NTFS has stayed relevant during roughly the same period of time (looks like the last major version of NTFS shipped with Windows XP).
Was NTFS simply that well spec'd and designed from the beginning, or has Windows been working around some NTFS deficiencies in the interest of not having to rewrite some core parts of Windows from scratch?  If that is the case, why are linux distros much more flexible in changing FS (user can even select a different FS at install time).


texts: Confusion regarding the Definition of 2 Way Finite State Automata?

texts:
Here is a description I read from one of the sources about 2WNFA:

"Unlike ordinary finite automata, a 2DFA needs only a single accept state
and a single reject state. We can think of it as halting immediately when
it enters one of these two states, although formally it keeps running but
remains in the accept or reject state. The machine need not read the entire
input before accepting or rejecting. Indeed, it need not ever accept or reject at all, but may loop infinitely without ever entering its accept or reject state."

I am unclear what it means by: "..The machine need not read the entire
input before accepting."

For example in the automata M = ({qo, ql, q2, q3, q4, q5}, {1}, δ, qo, {q5})
(δ is transition function, L=Left, R=Right) and the transitions being:

δ(q0, 1) = (q1, R);
δ(q1, 1) = (q2, R);
δ(q2, 1) = (q3, L);
δ(q3, 1) = (q4, L);
δ(q4, 1) = (q5);

Does the above 2WNFA, accept any string (example: "1") as the first 4 transitions can be ignored as they bring the machine back to the 1st character in the input string, thus for the last transition to the final accepting state a single 1 is enough? On other hand I think the language it accepts is empty?

Terribly confused because of the bidirection along with above explanation.


texts: Complexity of solving multiple problems of the same complexity?

texts: If I am given two languages $A$ and $B$ which are in NP, then we know that there exists a NDTM that can decide $A$ in polynomial time, and there exists another NDTM that can decide $B$ in polynomial time. Can I decide $A$ and $B$ in polynomial time using a NDTM by simply using a NDTM to check for belonging in $A$ then use another NDTM to check for belonging in $B$ and if both accept then it belongs to both $A$ and $B$?


texts: Newbie 2s complement to binary circuits help

texts: I'm creating a circuit with in3, in2, in1, and in0, and outputs F11-F0. The circuit has to take the input in 2s complement and output the number in binary with the sign. F11 represents the sign bit (on for negative and off for positive). So for instance, 1001 would output as -7, with F11 on and F7 on, or 0100 would output as 4, so F11 off and F4 on. Using 3-8 0-cold decoders and normal gates how would I create this. I'm also a bit lost on using decoders. I included a picture of the decoders pin configuration.


texts: Algorithm to find optimal currency denominations

texts:
Mark lives in a tiny country populated by people who tend to over-think things. One day, the king of the country decides to redesign the country's currency to make giving change more efficient. The king wants to minimize the expected number of coins it takes to exactly pay any amount up to (but not including) the amount of the smallest paper bill.

Suppose that the smallest unit of currency is the Coin. The smallest paper bill in the kingdom is worth $n$ Coins. The king decides that there should not be more than $m$ different coin denominations in circulation. The problem, then, is to find a $m$-set $\{d_1, d_2, ..., d_m\}$ of integers from $\{1, 2, ..., n - 1\}$ which minimizes $\frac{1}{n-1}\sum_{i = 1}^{n-1}{c_1(i) + c_2(i) + ... + c_m(i)}$ subject to $c_1(i)d_1 + c_2(i)d_2 + ... c_m(i)d_m = i$.

For instance, take the standard USD and its coin denominations of $\{1, 5, 10, 25, 50\}$. Here, the smallest paper bill is worth 100 of the smallest coin. It takes 4 coins to make 46 cents using this currency; we have $c_1(46) = 1, c_2(46) = 0, c_3(46) = 2, c_4(46) = 1, c_5(46) = 0$. However, if we had coin denominations of $\{1, 15, 30\}$, it would take only 3 coins: $c_1(46) = 1, c_2(46) = 1, c_3(46) = 1$. Which of these denomination sets minimizes the average number of coins to make any sum up to and including 99 cents?

More generally, given $n$ and $m$, how might one algorithmically determine the optimal set? Clearly, one might enumerate all viable $m$-subsets and compute the average number of coins it takes to make sums from 1 to $n - 1$, keeping track of the optimal one along the way. Since there are around $C(n - 1, m)$ $m$-subsets (not all of which are viable, but still), this would not be terribly efficient. Can you do better than that?


texts: Can we enumerate finite sequences which have no halting continuation?

texts:
Note: this question has been cross-posted to Math.SE, after about a week here.

I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (not Incompleteness).

Specifically, as I understand it the Completeness Theorem guarantees a finite proof for any first-order logical statement which holds in all countable models of a first-order theory. (This is my restatement of Wikipedia's "Every syntactically consistent, countable first-order theory has a finite or countable model.")

Since the statement "Program $P_n$ (encoded by integer $n$) does not halt" can presumably be stated in first-order logic and cannot in general be proven, we need to understand why (for given $n$) it does not hold in all countable models.

Intuitively, I expect that any countable model can be encoded as an infinite program for a Turing machine, eg by listing the countable set of first-order propositions. Likewise, I expect that any such "infinite Turing machine" can be identified with a countable first-order theory, by the Church-Turing thesis plus induction.

So, just as the Completeness Theorem fails to "solve" arithmetic because of non-standard models with infinite integers (which eg satisfy otherwise unsatisfiable Diophantine equations), I'm speculating that it fails for Turing machines because of non-standard models with "infinite programs".

But by my understanding statements which are true in all models (including non-standard / infinite ones) should still be provable. So I expect that if some finite set of axioms, which "pins down" some finite set of digits of a potentially infinite program, is enough to prevent the possibility of halting, we should be able to prove it.

Or in other words, if a finite sequence does not have any continuation which encodes a halting program, that should be provable.

Does my logic hold? Or what am I misunderstanding?

The reason this is not trivially wrong by Rice's Theorem is that it's a property of the program itself, rather than the language recognized by that program, which is $\emptyset$ for the programs I'm talking about.


texts:
What will happen in a Prolog program, if I set two rules/facts which contradict each other..
will it go with the rule/fact that appears first.. or it will show an error?


texts: Algorithm to optimize polling frequency between producer and consumer

texts:
I am trying to optimize what we call AJAX request polling frequency in the domain of web design. Here's a general version of the problem in simple lingo:

Problem Statement:

Suppose there are 3 persons - consumer (C), producer(P) and a messenger(M). The consumer and producer are some distant apart and can't communicate directly. The messenger - who works for the consumer - takes order from consumer, walks up to producer, places the order and come back to consumer. Messenger needs some finite amount of time to make the travel between P and C.

Now different orders require different amount of time for processing. After an order is placed, the M and C have no way to know how long the order processing will take. Hence, the messenger is required to make repeated trips to the Producer to check if the order is ready. It works in this way:

Step 1: Messenger waits for W amount of time
Step 2: M Goes to the producer to see if order is ready
Step 3: a) Order ready - come back with the produced item
b) Not ready - come back and repeat from step 1.

Now, I tabulated the time taken by each orders and plotted them against the number of orders taking that time. I got this:

   |                |  |
25 |                |  |  |
   |             |  |  |  |
20 |             |  |  |  |  |  |
   |          |  |  |  |  |  |  |  |
15 |          |  |  |  |  |  |  |  |  |
   |       |  |  |  |  |  |  |  |  |  |
10 |    |  |  |  |  |  |  |  |  |  |  |  |  |
   | |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
0  +-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|---
  1  5  10 20 25 30 35 40 45 50 55 60 65 70 75 85 90

As you can see, most orders take around 35 to 40 units of time (let's say seconds) to complete whereas some orders get completed in 5-10 seconds and some takes 80-90 seconds.

My Goal:

It is costly to have a high-frequency W. Right now my messenger is checking back in every W seconds. Instead of keeping this checking frequency W as constant, can we find some other checking frequency - may be a variable one where we adjust the frequency as we go along - that would ensure the least overall waiting time combining consumer and producer waiting time together.

As you can tell, I am obviously not very good in articulating the problem very well. So, let me know if you need clarifications in comments.

~~~ EDIT - Defining an Evaluation Model ~~~

As some of the comments suggest, it's important to include W in the evaluation model. I think what I am really trying to do here is to minimize unsuccessful pollings (like polling that comes back empty handed as producer hasn't finished producing)

Say, messenger takes W amount of time to do one polling. If I take a given sample set of N pollings and if only S fractions of those polls were successful, then my intuition tells me that,

  S = function (N, W)

So the question is - given a specific set of N, how do I find a W that maximizes S


texts:
I'm doing a research on NLG systems.
I need to annotate my corpus (~6 million words) automatically. My algorithm works well and I want to calculate Cohen's Kappa. What I cannot understand is the second annotator; I don't have the possibility to have another annotation.
Is there any solution for this problem? Can I have a set of data as my sample and manually doing the annotation to calculate Cohen's Kappa? Is there any measurement for corpus analysis?

Thanks


texts:
Consider a sequence of $n$ flips of an unbiased coin. Let $H_i$ denote the absolute value of the excess of the number of heads over tails seen in the first $i$ flips. Define $H=\text{max}_i H_i$. Show that $E[H_i]=\Theta ( \sqrt{i} )$ and $E[H]=\Theta( \sqrt{n} )$.

This problem appears in the first chapter of `Randomized algorithms' by Raghavan and Motwani, so perhaps there is an elementary proof of the above statement. I'm unable to solve it, so I would appreciate any help.


texts: Modal logic equivalent to two-variable first-order logic?

texts:
It is well-known that many modal logics can be viewed as fragments of $FO^2$, i.e. two-variable first-order logic.
But is there a modal logic that is not a fragment, but is expressively equivalent to $FO^2$?


texts: Efficient Algorithms for Destroyed Document Reconstruction

texts:
I am not certain this is the proper site for this question however I am mainly looking for resources on this topic (perhaps code). I was watching TV and one of the characters had a lawyer who destroyed his documents using a paper shredder. A lab tech said that the shredder was special.

I am not familiar with this area of computer science/ mathematics but I am looking for information on efficient algorithms to reconstruct destroyed documents. I can come up with a naive approach that is brute force fairly easily I imagine but just going through all the pieces and looking for edges that are the same but this doesn't sound feasible as the number of combinations will explode.

Note: By destroyed documents I am talking about taking a document (printed out) and then shredding it into small pieces and reassembling it by determining which pieces fit together.


texts: Can a collection of oracle machines decide every language?

texts:
If I have a collection of oracle machines, can I decide every language? (I got this question from a former university exam and it sparked my interest).

I thought if my collection has to be countable than I can't decide every language, since there's an uncountable amount of languages.

But if my collection can be of any kind I figured could just add an oracle machine for every language with an oracle for that language, which would be sort of a trivial - brute force approach (the size of the collection would be uncountable than).

Is there an issue with my approach / did I miss something? What happens if I have a countable number of oracles that can be used?


texts: How to remove objects from an array most efficiently?

texts:
I am wondering if I can rearrange an array faster when I would like to delete more than one object.

You are given a List:

1
2
2
3
4
5
7

And now you want to delete every "2" in the list. So what I would do, is:

int size = 7;
int array[size] = {1,2,2,3,4,5,7};
for(int i = size-1; i >= 0; i--){
   if(array[i] == 2){
      memcpy(&array[i],&array[i+1], size-i);
      size--;
   }
}

But this is not a efficent way doing so, is it?
So I wonder if I could do this on a smarter way without allocating extra memory.


texts: Why does the NP completeness of the Hartree-Fock method not lead to difficulty in practical calculation?

texts:
I read  Computational Complexity of interacting electrons
and fundamental limitations of Density Functional Theory. In appendix, it is claimed that

  In the following, we show that approximating the
  ground state energy using the Hartree-Fock method is
  an NP-complete problem

As far as I know, if a problem being NP-hard, it is unlikely to be solved within polynomial time. If Hartree-Fock is NP-complete, computation for large system is unlikely to be possible. However, experience seems to suggest that Hartree-Fock could always be done within polynomial time. There are vast applications of Hartree-Fock method on various many-electron system: atoms, molecules, and solids. The claim from the arxiv paper is rather in contraction with my experience

My question is, why the Hartree-Fock method is applicable to wide class of many-electron system while it is NP-complete? Is that because its average complexity is low or any other reason?


texts: What is the duality between path cover and flow?

texts:
Let there be a bipartite directed graph $G=(V,E)$.
Let's say we have a path cover of the graph. In some texts it is said that this path cover "induces" a flow on $G$. What does this mean?
How can we extract a flow from a path cover (and similarly, extract a path cover from a flow)?


texts: How does size of list in merge-sort, quick-sort, insertion-sort, matter?

texts:
We have been taught that:

Insertion-sort will best work if we have a small list.
Quick-sort will best work if we have a long list.
Merge-sort will best work if we have a huge list.

It is not intuitively understandable.
However, let us say if we have a list with 20 elements and want to sort it because shifting action does cost a lot for us, that would be a perfect choice to go with Insertion-sort.
I do not know If I am getting the idea right or not, but my issue is that I can not correlate the logic behind these sorting algorithms with the size of lists, Also does worst, average and best cases affect the size list.
getting me out of confusion would be really much appreciated, thanks.


texts: Is a very long plain text password harder to crack than a short complicated password?

texts: Is it true that a password consisting of the alphabet, even of common known names is much harder to find for a computer program than a short password, even though it uses numbers and other characters?


texts:
I have found two different versions for State Transition Diagrams for XOR.

I'm confused as to why one has 2 states and the other has 3. What are the implied states in each please?

Are they both functionally equivalent? Are there situations where one is more appropriate than the other?


texts: Can formal languages be used to study mathematical notation?

texts:
Question: Are there any introductory texts in formal language or programming language theory which discuss how to apply it to the study of optimal notation?

In particular, I am interested to learn what stack-languages, parse trees, and indices are, and how to predict when a certain type of notation will lead to exponential redundancy.

I have basically no background in either formal language/grammar or programming theory, since as a math major the only computer science I learned was algorithms and graph theory, as well as very modest smidgens of complexity theory and Boolean functions. Thus, if the only books which discuss this are not introductory, I would be grateful for answers that both list such books discussing exponential notation blow-up as well as introductory books that will prepare for the books which directly address my question.

Context: This question is inspired primarily by an answer on Physics.SE, which says that:

  It is very easy to prove (rigorously) that there is no parentheses notation which reproduces tensor index contractions, because parentheses are parsed by a stack-language (context free grammar in Chomsky's classification) while indices cannot be parsed this way, because they include general graphs. The parentheses generate parse trees, and you always have exponentially many maximal trees inside any graph, so there is exponential redundancy in the notation.

Throughout the rest of the answer, other examples of "exponential notation blow-up" are discussed, for example with Petri Nets in computational biology.

There are also other instances where mathematical notation is difficult to parse, for example as mentioned here when functions and functions applied to the argument are not distinguished clearly. This can become especially confusing when the function becomes the argument and the argument becomes the function, e.g. here.


texts: Proof of universality in the circuit model

texts:
I'm starting to study Turing machines, the Church-Turing conjecture and the circuit model. In particular, I'm interested in the proofs of universality that one can find in this context. So far, I have only found the universality proof of the circuit model for boolean functions (i.e., the gates AND, OR and NOT can be used to compute any boolean function). However, our experience with digital computers indicates that they can approximate really well more things than only boolean functions.
My question is: are there more proofs of universality in the context of the circuit model? For example, to approximate continuous funcitons. I have tried to find something about this particular case but I didn't find any proof nor any reference where approximation of continuous functions with boolean functions is discussed. And it is something that puzzles me because, in the context of machine learning, feed-forward neural networks are universal approximators of continuous functions, but we compute the feed-forward neural networks models in digital computers. All the possible references are wellcome!


texts: Does the concept of the array pre-date physical computer memory implementations?

texts:
Does the concept of the array (a sequence of equally-sized elements accessible in O(1) time, occupying O(n) space) pre-date physical computer memory implementations?

I am trying to gauge whether computer memories were designed for the array or whether the array concept was designed to work with computer memories.


texts:
As it is, how do you prove that SAT is NP-complete?

I know what it means by NP-complete, so I do not need an explanation on that.

What I want to know is how do you know that one problem, such as SAT, is NP-complete without resorting to reduction to other problems such as hamiltonian problem or whatever.


texts: Is there an algorithm to find all the shortest paths between two nodes?

texts:
Given a directed graph, Dijkstra or Bellman-Ford can tell you the shortest path between two nodes.

What if there are two (or n) paths that are shortest, is there an algorithm that will tell you all such paths?

Edit:

I have just thought up a possible solution. Could you just do a Bellman-Ford but when relaxing edges, if (distance[u] + w == distance[v]) then add u to the set of predecessors of v? Does this work?


texts: Prove L = {a = b ⊕ c | a, b, c ∈{0, 1}*} is not regular

texts:
Given that language $L = \{a = b ⊕ c \mid a, b, c ∈ \{0,1\}^*, a = b \oplus c\}$, with an alphabet $Σ = \{⊕, =, 0, 1\}$, I need to prove that this language is not regular. The following is as far as I have gotten in my proof, but I am getting stuck when showing why it is contradicting the pumping lemma:

$s = (1^p = 1^p ⊕ 0^p)$

$x = 1^l$

$y = 1^m$, where $l+m \le p$ and $m > 0$

$z = (1^{p-l-m}=1^p ⊕ 0^p)$

Taking $i=2$, $xy^2z = (1^l1^{2m}1^{p-l-m}=1^p ⊕ 0^p) = (1^{p+m}=1^p ⊕ 0^p)$

—This is where I am getting stuck. From my example, this appears to be a contradiction, but there is nothing in the language dictating that $b$ and $c$ be of equal lengths. Were they to be different lengths, it could certainly be possible that no contradiction would be found by adding $m$ to $p$. How could I fix my proof via pumping lemma?

---EDIT: SECOND TRY---

$s = ((10)^p = (01)^p ⊕ (10)^p)$

$x = (10)^l$

$y = (10)^m$, where $l+m \le p$ and $m > 0$

$z = ((10)^{p-l-m}=(01)^p ⊕ (10)^p)$

Taking $i=0$, $xy^0z = ((10)^l(10)^{p-l-m}=(01)^p ⊕ (10)^p) = ((10)^{p-m}=(01)^p ⊕ (10)^p)$

Now, I have that $|a|<|b|$ and $|a|<c$, which is not possible, since the result of the exclusive-or must contain a leading 1, which cannot be truncated to a smaller string length. Therefore, this is a contradiction.

Is this a contradiction strong enough to prove the language is not regular? It only works in the case of a leading 1; do I need to show something that is a contradiction even with leading 0's?


texts: Finding the Kth largest element can be optimized to O(n) only if k is a constant?

texts:
There's a famous question posted on this site which asks about finding the $k$th largest element. Many answers are written there which optimized it and found algorithms with expectation of $O(n)$.

The thing I don't understand is....  Those algorithms wouldn't work if $k$ is dependent on $N$.  Therefore $k$ must be a constant.

But if it's a constant why isn't it easiest to simply loop like bubble sort for $k$ times?  So you pushed the $k$ largest elements to the end of the array. No?    Complexity would be $O(nk)$ but $k$ is a const so it would be $O(n)$.

Why do we need crazy algorithms like median of medians and using quicksort if this alone works?


texts:
A magnetic disk has 1000 cylinders, 10 tracks per cylinder, 128 sectors per track, 1 KB per sector. The rotation time is 6 msec, maximum seek time is 150 msec, switching between adjacent cylinders takes 15 msec, and switching between adjacent tracks within a cylinder takes no time. Assume this disk has 4 MB of data stored on it.If data is stored on consecutive tracks and is twice as likely to start on the first half (upper 5 tracks) of a cylinder than the second half (lower 5 tracks), find the average access time

Solution'

#Tracks: 4 MB x 1024 KB/1 MB x 1 sector/1 KB x 1 track/128 sectors = 32 tracks
Transfer time = 32 x 6 = 192 msec

Exp. switch and wait: Probability (twice as likely) -> If x = probability,
5 x 2x + 5 x 1x = 1 -> x = 1/15

         Track  Probability   # switch s/w time
           1     2/15               3               18x3
           2     2/15               3               18x3
           3     2/15               3               18x3
           4     2/15               3               18x3
           5     2/15               3               18x3
           6     1/15               3               18x3
           7     1/15               3               18x3
           8     1/15               3               18x3
           9     1/15               3               18x3
          10     1/15               4               18x4

        Exp. s/w = 5 x [(18x3) x 2/15] + 4 x [(18x3) x 1/15] + [(18x4) x 1/15] = 55.2 msec

        Exp. access time = exp seek + exp latency + transfer + exp s/w = (1/3 x 150) + (1/2 x 6) + 192 + 55.2
                = 300.2 msec

Is there a easier method to this question maybe with formulas or something,


texts: Is there a general form of polynomial reductions in complexity theory?

texts: While reading Sipser, in computability I read about many to one mapping reducibility and Turing reducibility,the latter one being a more general form of reducibility. But in the introductory chapter about complexity, where the book shows examples of NP-Complete problems,the polynomial reductions used are only many to one mapping reductions. So in polynomial reductions is there a general form of reductions? For example the author first proves that 3-SAT is NP-Complete and then for clique problem,subset sum problem,vertex cover problem and Hamiltonian path problem he reduces 3-SAT to the respective problems. The reductions used are many to one mapping reductions. Are general Turing reductions used while proving NP-Completeness of a problem ?


texts:
Possible Duplicate:
  How to use greedy algorithm to solve this?

You are given $n$ integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ between $0$ and $l$ with the requirement that the $b_i$'s form a non-decreasing sequence (i.e. $b_i \le b_{i+1}$ for all $i$). Define the deviation of such a sequence to be $\max(|a_1−b_1|,\ldots,|a_n−b_n|)$. Design an algorithm that finds the $b_i$'s with the minimum deviation in runtime $O(n\sqrt[4]{l})$.

There were also two hints, one is to first find an algorithm in $O(nl)$ time, the other is that the runtime of the optimal algorithm is actually must less than $\Theta(n\sqrt[4]{l})$.

I was able to find a solution that runs in $O(n^2)$ (without using any of the hints), but I have no idea how to find an algorithm that runs in $O(n\sqrt[4]{l})$. Can anyone offer some insight into this? Maybe give a rough sketch of your algorithm? Thanks!


texts: What is the complexity of computing $n^{n^2},\;n \in \mathbb{N}$?


texts:
Processor has the internal clock which is a multiplier of the main clock which is present on the motherboard which is designed by keeping in mind the critical path and the slowest device on board,

My question is :-

How there are two clocks working simultaneously in the computer system, what is the mechanism of their working, We know the processor is the one which is executing the instructions and then send the relevant signal out to the other components for any read or write operations. Processor runs at different clock and lets suppose it executes a read instruction to get some data from the memory in its one of registers and next instruction is to use that data for any ALU operations if the processor runs on different clock and rest of the system runs at different clock, doesn't make it any conflict ?  I know there is a concept of wait state, is it in the hand of programmer or hardware designer ?


texts: Efficient permutation of given ranking that preserves given distance

texts:
Ranked Biased Overlap (RBO) is a metric for comparing two rankings and is used when the sizes of the given rankings are different and/or the elements that they carry are not the same. Ranked Biased Distance (RBD = 1 - RBO) is the distance metric emanating from RBO. A simple demonstration of the metric can be found here, along with a link to an implementation in Python.

Currently, I want to find an efficient way of calculating the "inverse" of RBO. Typically, RBO is a function like the following:

double rbo(List<A> rankingA, List<B> rankingB)

The double value returned, is the RBO value of rankings rankingA and rankingB. I want to implement the following method:

List<A> generateRanking(List<A> rankingA, double rbo)

which given a ranking (rankingA) and an RBO value (rbo), it generates a random permutation of rankingA, that its RBO value with the initial ranking is rbo. Apart from a trial-and-error approach, in which I randomly permute rankingA until I meet rbo, can you think of a better way (more computationally efficient) of doing so?

Thank you


texts: What would you get if you add parameters to context free grammars?

texts:
I was thinking of grammars for indendation-sensitive languages and it looks like CF grammars would do the trick if combined with parameters. As an example, consider this fragment for simplified Python grammar in ANTLR-like format:

// on top-level the statements have empty indent
program
    : statement('')+
    ;

// let's consider only one compound statement and one simple statement for now
statement(indent)
    : ifStatement(indent)
    | passStatement(indent)
    ;

passStatement(indent)
    : indent 'pass' NEWLINE
    ;

// statements under if must have current indent plus 4 spaces
ifStatement(indent)
    : indent 'if' expression ':' NEWLINE (statement(indent '    ')+)
    ;

My question: Does this kind of grammars (CFG with parameters) have a name?

It looks that it wouldn't be hard to write a recursive descent parser for this grammar (parameters should be basically parsers). What could be the difficulties with this approach?

Does addition of parameters raise the supported language class above context-free?


texts: How to build a parser for syntactic analysis of regular expressions?

texts:
Is it possible to build a parsing algorithm that build a parse tree using a top-down method that simulate a derivation process for regular expressions, like we do for type 2 languages?

My guess

Given a regular expression r, build its FSA, then obtain the grammar that generate r in order to build a parse tree


texts:
A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode.

For instance, if I enter the stream $012345$, I am trying each of the combinations $0123$, $1234$, and $2345$.

Clearly, a 40000-length string $000000010002...9999$ is guaranteed to crack the safe.

Can we try each of the 10000 combinations using a shorter string? What's the shortest string we can devise to try every combination?


texts: What are the reasons behind using constraints in convex optimization?

texts:
We use the following notation to describe a minimum convex optimization problem:

               minimize     f0(x)
               subject to   fi(x) ≤ 0,     i = 1, . . . ,m
                            hi(x) = 0,     i = 1, . . . , p

  to describe the problem of finding an x that minimizes f0(x) among all x
  that satisfy the conditions fi(x) ≤ 0, i = 1, . . . ,m, and hi(x) = 0, i =
  1, . . . , p.

What is the reason for using fi(x)<=0 and hi(x)=0.

How do someone arrived at only these two constraints?


texts: What is the runtime of the following code?

texts:
Can you explain to me how you get the Big O notation for the runtime of the following snippet of code?

for x = 1 to n
{
    y = 1
    while y < n
       y = y + y
}

Can you explain the steps on how you get the big O notation for it? Also why doesn't it matter if there a bunch of statements inside a for loop when calculating the big O notation? Wouldn't the number of operations increase as n gets larger if there are more O(1) statements inside the for loop? Help would greatly be appreciated.


texts: How to encode each possible b-tree of a sequence of n numbers?

texts:
Lehmer codes can be used to encode each possible permutation of a sequence of n numbers. Often the main goal is just to map a range of numbers from 1 to x to the possible permutations of a sequence of numbers from 1 to n. An example to visualize this goal would be:

n := 3, x := 6
[1, 2, 3] = 1
[1, 3, 2] = 2
[2, 1, 3] = 3
[2, 3, 1] = 4
[3, 1, 2] = 5
[3, 2, 1] = 6

Instead of encoding each possible permutation of a sequence of n numbers, I want to encode each possible b-tree which can be created from a sequence of n numbers.
When creating a b-tree from a sequence of n numbers, the possible solutions can be branched differently due to the order of (additional) insertions, deletions or reorganizations.

Example: Create a b-tree from the sequence of numbers from 1 to n := 5. The b-tree's (non-root) nodes must have at least 2 and at the maximum 4 children. With this conditions these b-trees would all be valid:

    3         2               4       2|4
   / \       / \             / \     / | \
1|2   4|5   1   3|4|5   1|2|3   5   1  3  5

I could write an algorithm to generate every possible b-tree and then map them to a list of numbers. But that does not work very efficient for n getting bigger because obviously memory is a limitation here. So what I'm looking for is something like the above described Lehmer code for b-tree possibilities instead of permutations.

I would also appriciate a solution for this problem but with binary trees or other tree data structures instead of b-trees because I didn't find anything at all regarding to encoding trees like that and a first approach is always nice to work with.

If you think this question would be more appropriate on Mathematics Stack Exchange, let me know as well.


texts: How does one show Lovasz theta of even $n$-cycle ($n$ is even) is of form $\frac{n}{2}$? Why is the Lovasz theta of such cycles not of form $\frac{n \cos(\frac{\pi}{n})}{1+\cos(\frac{\pi}{n})}$. Could someone provide a derivation for even cycle Lovasz theta number. It is clear that the Shannon Capacity is $\frac{n}{2}$. why is the cosine form tight only for odd cycles?


texts: Is a Turing Machine "by definition" the most powerful machine?

texts:
I agree that a Turing Machine can do "all possible mathematical problems". But that is because it is just a machine representation of an algorithm: first do this, then do that, finally output that.

I mean anything that is solvable can be represented by an algorithm (because that is precisely the definition of 'solvable'). It is just a tautology. I said nothing new here.

And by creating a machine representation of an algorithm, that it will also solve all possible problems is also nothing new. This is also mere tautology. So basically when it is said that a Turing Machine is the most powerful machine, what it effectively means is that the most powerful machine is the most powerful machine!

  Definition of "most powerful": That which can accept any language.
  Definition of "Algorithm": Process for doing anything.
  Machine representation of "Algorithm": A machine that can do anything.

Therefore it is only logical that the machine representation of an algorithm will be the most powerful machine. What's the new thing Alan Turing gave us?


texts: How to interpret these asymptotic runtime bounds for discrete logarithm algorithms?

texts:
I am trying to compare asymptotic runtime bounds of a few algorithms presented in this research paper, A quasi-polynomial algorithm for discrete
logarithm in finite fields of small characteristic.  The functions are,

$L(\alpha) = \exp(O(\log(n)^{a}(\log\log(n))^{1-\alpha}))$,

which I'd like to plot for $\alpha = 1/3, 1/4+O(1)$, and $1/4 + O(n)$,

and $O(n^{\log n})$

  Where n is the bit-size of the input. ... Such a complexity is smaller than any $L(\epsilon)$ for any $\epsilon > 0$

I would like to plot each of these functions together to compare their growth.  The problem is that the second function grows much faster than the first, which implies I am misinterpreting something.

So what is the correct way to interpret and compare these functions?


texts: What is this prize-collecting optimization problem with travel times?

texts:
There exist very rich literature on discrete optimization problems such as variants of knapsack problem, traveling salesman problem, orienteering problem, tourist trip design problem and etc. Recently, I have encountered a question during my research which I like to know what this problem is? Is it a variant of a famous problem like the above list and is there any literature on it?

Problem: Suppose there is a tourist moving over a graph and in visiting each vertex collects a reward respective to that vertex. Let ${\mathcal G}=({\mathcal  V},{\mathcal E})$ be the graph and $T(t)=(\tau_{ij}(t))$ be a time dependent matrix where $\tau_{ij}(t)$ represents traveling time from vertex $i$ to $j$ if the travel being started at time $t$, for any $i,j\in {\mathcal V}$ and $t\in {\mathbb R}$ (Note that if $ij\notin {\mathcal E}$, then $\tau_{ij}(t)=\infty$). Also, let ${\rm r}(t)=(r_i(t))$ be the time dependent vector for vertex visits, i.e. if the vertex $i$ be visited at time $t$ then a reward equal to $r_i(t)$ is collected ($r_i$ is a strictly decreasing function, for any $i\in {\mathcal V}$).
The goal is maximizing the total collected reward.

In a simpler form one may let $T$ be constant.


texts: Stable and fast computation of the squared euclidean distance matrix

texts:
Let's say I want to compute the matrix $M$ of the squared euclidean distances between each pair of vectors $(x, y)$ belonging to two sets $X$ and $Y$ respectively. The sets of vectors $X$ and $Y$ have size $m$ and $n$. Each vector has $k$ floating point coordinates.

As far as I can tell, there are mainly two ways to implement the computation of an euclidean distance matrix. The direct formula, which is slow but accurate, and the expanded formula which can be fast but numerically inaccurate. I'm wondering if there would be a way to compute the squared euclidean distance matrix in a stable and fast way.

The direct formula compute for each pair of vector $x \in X$ and $y \in Y$: $\sum_i (x_i - y_i)^2$. It is pretty accurate and could even be combined a with compensated summation algorithm. It is however relatively slow as this is an $\mathcal{O}(mnk)$ algorithm and can only take advantage of level 1 BLAS routines.

On the other hand, the expanded formula compute $\sum_i{x_i^2} + \sum_i{y_i^2} - 2\sum_i{x_i y_i}$. It is pretty fast as it only makes 2/3 of the operations of the direct formula and can use the BLAS matrix multiplication for the last term. Unfortunately, it is numerically very unstable and often produce negative result.

Intuitively, the computation of an euclidean distance matrix seems very redundant when $k \ll min(m, n)$. Once we know the distance from a vector $x \in X$ to $k+1$ vectors from $Y$, then the distance from $x$ to all the other vectors $y \in Y$ are pretty much determined. But I can't find a useful way to exploit this redundancy to make less computations.

Side note: the expanded formula also gives us an upper bound on the minimal reachable complexity of the computation of the euclidean matrix. Since its complexity is basically that of the matrix multiplication, it is theoretically possible to compute the euclidean distance matrix in $\mathcal{O}(n^{2.3737})$. But maybe there's a structure to the squared euclidean distance matrix that would make this bound practical. Who knows?


texts: What are good counter-examples when training an apple classifier?

texts:
I am doing a project in order to recognize an apple. (I am using Emgucv with Visual Studio 2010 C#, if that's relevant). My project is a classification (is or is not an apple). I have 2000 images of apples but I need images for the second class.

I have read about classification using ANN but they have multiple classes but I need to recognize if image contain an apple or not. So what kind of images do I need for the second classes? I want to use background of apples like second class. Is that a good idea?

I only want that ANN recognize if a image contain a pen or not so I have 2 classes(pen and non-pen) My question is What kind of image can I use to the second class? For example My first class are images of pen and second class are images of non pen (pencil, apples, grapes, tables); is that correct?


texts: How are randomized restarts in local search 4 times likely to give bad local minima?

texts:
I am reading section 9.3.3 Dealing with local optima in Algorithms by Dasgupta et al. and the authors mention that in randomized restarts, it is four times likely to end up with a bad solution. They,  then in the next sentence, imply that this a good thing as there will be fewer repetitions needed. Here's the text for context and the referenced figure. The next citation block contains the crux of my question.

Figure 9.10 shows a small instance of graph partitioning, along with the search space of solutions. There are a total of  $ {8\choose 4}= 70$possible states, but since each of them has an identical twin in which the left and right sides of the cut are flipped, in effect there are just 35 solutions.In the figure, these are organized into seven groups for readability. There are five local optima, of which four are bad, with cost 2, and one is good, with cost 0.

If local search is started at a random solution, and at each step a random neighbor of lower cost is selected, then the search is at most four times as likely to wind up in a bad solution than a good one. Thus only a small handful of repetitions is needed.

How do you end up with the multiple of 4?
How is it that the chance
of picking a bad solution being 4 times as likely a good thing? How
does this translate to needing fewer repetitions?