texts:
Consider the following problem:

  Let a $k$-wheel be defined as an indexed circularly linked list of $k$ integers. For example…

    {3, 4, 9, -1, 6}

  …is a 5-wheel with 3 at position 0, 4 at position 1, and so on. A wheel supports the operation of rotation, so that a one-step rotation would turn the above wheel into…

    {6, 3, 4, 9, -1}

  …now with 6 at position 0, 3 at position 1, and so on. Let $W_{N_k}$ be an ordered set of $N$ distinct $k$-wheels. Given some $W_{N_k}$ and some integer $t$, find a series of rotations such that…

  $$\forall\ 0 \leq i < k, \sum_{N \in W} N_i = t$$

  In other words, if you laid out the wheels as a matrix, the sum of every column would be $t$. Assume that $W_{N_k}$ is constructed so that the solution is unique up to rotations of every element (i.e., there are exactly $k$ unique solutions that consist of taking one solution, then rotating every wheel in $W$ by the same number of steps).

The trivial solution to this problem involves simply checking every possible rotation. Here is some pseudocode for that:

function solve(wheels, index)
    if wheels are solved:
        return true
    if index >= wheels.num_wheels:
        return false
    for each position 1..k:
        if solve(index + 1) is true:
            return true
        else:
            rotate wheels[index] by 1

solve(wheels, 0)

This is a pretty slow solution (something like $O(k^n)$). I'm wondering if it is possible to do this problem faster, and also if there is a name for it.


texts: Does the Rabin-Karp really need me to care about applying a mod Q operation on the rolling hashes?

texts:
I have been reading about the Rabin Karp algorithm and I kept wondering what's the big deal with keeping our rolling hashes values bounded by a value Q?

I'd thought that as our integer number representation on the typical computer is 2-complement, it's actually exactly equivalent as bounding all our operations over the rolling hashes by 2^31, so that in other words, I simply shouldn't care. Plus, the smaller we bound or hashes to, the more collisions we'd have, so a bigger Q should equal with improved performance!

I've tried coding a simple (Java) implementation:

public static int rabinKarp(String text, String pattern) {
    if (text.length() < pattern.length()) {
        return -1;
    } else {
        int patternHash = 0;
        int textHash = 0;
        int pow = 1;

        // preprocessing the pattern and the first characters of the text string
        for (int i = pattern.length()-1; i >= 0; --i) {
            patternHash += pattern.charAt(i) * pow;
            textHash += text.charAt(i) * pow;
            pow *= 10;
        }
        pow /= 10;

        // actual search
        if (patternHash == textHash && areEqual(text, 0, pattern)) {
            return 0;
        } else {
            for (int i = 1; i < text.length()-pattern.length()+1; ++i) {
                textHash -= text.charAt(i-1)*pow;
                textHash *= 10;
                textHash += text.charAt(i+pattern.length()-1);
                if (textHash == patternHash && areEqual(text, i, pattern)) {
                    return i;
                }
            }
            return -1;
        }
    }
}

From some preliminary tests, my hypothesis seems to be empirically accurate, yet I have not seen that written anywhere, so I am left wondering..

Am I missing something?


texts:
Let $S_1,\dots,S_n$ be variables representing unknown sets.  A set expression has the form $S_i$, $\overline{E}$ (the complement of $E$), or $E \cap E'$, where $E,E'$ are set expressions.  A constraint has the form $E = \emptyset$ or $E \ne \emptyset$, where $E$ is a set expression.  Given a conjunction of constraints, the problem is to determine whether they are satisfiable, i.e., whether there is an assignment from variables to sets that makes all of the constraints hold.

Conjecture: if there exists a satisfying assignment, then there is a satisfying assignment where all sets are subsets of a universe $U$ with $k$ elements, where $k$ is the number of constraints of the form $E \ne \emptyset$.

Is this conjecture true?

I suspect it is, but I can't seem to prove it.  I can prove it if there is no complement operator, but my proof strategy seems to go awry if there are complements.  (Proof strategy: suppose the constraints are $E_1 \ne \emptyset$, .., $E_k \ne \emptyset$, and suppose we have any satisfying assignment. Let $x$ be the smallest element of $E_1 \cup \dots \cup E_k$, where $x$ is an element of $E_i$; then add $x$ to $U$, discard $E_i$, and repeat.  Once this is finished, replacing each set $S_i$ with $S_i \cap U$ still leaves all constraints satisfied.)  If this conjecture is true, it is a sort of "small-world theorem", which says that a not-too-large universe suffices for checking satisfiability.  These kinds of theorems are helpful for improving the performance of constraint-solving algorithms.


texts: Number of comparisons in array where each element appears n/k times

texts: Given an array of $n$ elements with $k$ distinct elements, each appearing $n/k$ times, how can I show that the number of comparisons to the sort the array in the worst case is in $\Omega(n \log k)$?


texts: Proof of Lower Bound for Deterministic Distinct Elements Algorithm

texts:
There is a proof in this document (page 8, Section 4, Lemma 3: https://inst.eecs.berkeley.edu/~cs170/fa16/lecture-11-29.pdf) that mirrors a proof my professor gave in my algorithms class. The lemma states:

Suppose that there is a deterministic exact algorithm for counting distinct elements that uses o(min{|$\Sigma$|, $n$}) bits of memory to process a stream of $n$ elements of $\Sigma$.
Then there is a compression algorithm that maps $L$-bit strings to bits strings of length o($L$).

The conclusion is false, therefore the premise is false. The proof is by contradiction. This is proved by constructing a compression algorithm that encodes an $L$-length bit string in fewer than $L$ bits. A decoding method is then given for reconstructing the $L$-length bit string.
What confuses me is that the paragraph above is apparently the contradiction that proves that you cannot transmit an $L$-length bit string using fewer than $L$ bits. And yet it seems to show that this actually can be done.
I understand the counting argument that says you cannot map $2^L$ bit-strings losslessly onto a range of $2^L-1$ outputs. What I need to understand for my class is why the given proof by contradiction is valid. If anyone can help me with the intuition concerning why the proof is valid, I would appreciate it


texts: Is a k counter automata a special kind of PDA?

texts: I understand that a 1 counter automata is a special kind of PDA where the stack alphabet consists of one symbol (ignoring the fixed bottom symbol) but what about 2 counter automata? Is it a special kind of PDA where the stack alphabet consists of two symbols? Can we generalize like so: a k-counter automata is a PDA with k many symbols in the stack alphabet where k>0?


texts: Help me to make sure, that I got defunctionalized continuations right

texts:
I am reading this Defunctionalization at work paper. So, in order to ascertain that I got it right, I request a little code review. I'll start with a recursive definition of a factorial function and iteratively translate it to the almost iterative version.
Ok, this is what we start with:
def factorial(value: int) -> int:
    if value == 1:
        return 1
    else:
        return factorial(value-1) * value

Now, we'll traslate factorial from direct style to CPS form (mixed CPS and direct style really, but this would work):
def factorial(value: int, cont: Callable[[int], T]) -> T:
    if value == 1:
        return cont(1)
    else:
        return factorial(value-1, lambda res: res * value)

Identify two basic continuations here - Done and Mul. We'll use Done to simply print things to the screen, and Mul to do a multiplication after a recursive call.
So, again, theese are our defunctionalized continuations.
class Cont(Generic[T]):
    """The base class for my defunctionalized continuations."""
    pass

@dataclass
class Mul(Cont[T]):
    value: int
    and_then: Cont[T]

@dataclass
class Done(Cont[T]):
    pass

Here is an apply function, that accompanies our defunctionalized continuations:
def apply(cont: Cont[T], value: int) -> T:
    if isinstance(cont, Done):
        return print(value)
    elif isinstance(cont, Mul):
        return apply(cont.and_then, cont.value * value)
    else:
        raise TypeError("Should be unreachable!")

We notice, that the apply function is in it's tail call form, why no make it iterative:
def apply(cont: Cont[T], value: int) -> T:
    while isinstance(cont, Mul):
        value = cont.value * value
        cont = cont.and_then
    return print(value)

This is what the factorial function looks like now:
def factorial(value: int, cont: Cont[T]) -> T:
    if value == 1:
        return apply(cont, 1)
    else:
        return factorial(value-1, Mul(value, cont))

Optimize it's tail call recursion:
def factorial(value: int, cont: Cont[T]) -> T:
    while value > 1:
        cont = Mul(value, cont)
        value -= 1
    return apply(cont, 1)

And inline the apply function:
def factorial(value: int, cont: Cont[T]) -> T:
    while value > 1:
        cont = Mul(value, cont)
        value -= 1
    while isinstance(cont, Mul):
        value = cont.value * value
        cont = cont.and_then
    return print(value)

And here we have it - an iterative version of the factorial function.
So, my thoughts:

Did I get I right? The result makes sense to me - Mul(value, cont) is exactly equivalent to pushing to the stack, and cont = cont.and_then is similar to the stack pop.
Although this synthesized factorial function is technically iterative (uses constant stack space), it is obvious that having two while loops is redundant. Moreover, factorial can be trivially written without any stacks what so ever, for example using an accumulator. How do I handle this?


texts: Converting any computable function into a sequence of additions

texts:
Not sure if this question should be here, or on math.se.

That said, let me proceed:

On the Wikipedia page for the Ackermann function, it is mentioned that by passing the inputs of 0, 1 and 2 to the third parameter one could perform the three fundamental operations of addition, multiplication and exponentiation, respectively, on the other two parameters.
That is, addition, multiplication and exponentiation are the three fundamental operations.

But multiplication is merely repeated addition, and exponentiation repeated multiplication. So addition is the fundamental operation?

My question is this:

  Does there exist an algorithm to convert any sequence of (computable) mathematical operations, into another sequence of computable operations involving only addition.


texts: How to find a Graph Embedding given a metric space?

texts:
I am interested to learn more about topological graph theory and Graph Embedding.

Assume I have a metric space, $d \colon M \times M \to \mathbb{R}$ and a graph, $G=(V,E)$.

What is a rigorous way to define a valid embedding of $G$ given $d$ and how to find such an embedding?

Edit: I found this post about embedding graphs.


texts:
So, this is how I solved

$\displaystyle
        T(n-1) \approx{}  T(n-2)
    $

$\displaystyle
        T(n) = T(n-1)^2
    $

Add log in both sides

$\displaystyle
        log(T(n)) = 2log(T(n-1))
    $

$\displaystyle
       Let\:\: log(T(n)) = S(n)
    $

$\displaystyle
S(n) = 2(S(n-1))
    $

We know that from Fibonacci series

$\displaystyle
S(n) = O(2^n)
    $

$\displaystyle
log(T(n)) = O(2^n)
    $

$\displaystyle
(T(n)) = O(2^{2^n})
    $

Ok, so where did I go wrong here??


texts: Can someone provide a trivial example to the "reduction" procedure used to prove hardness?

texts:
I cannot comprehend how you can prove hardness between two NP complete problems.

For example, let X be a NP hard problem, I want to prove Y is also NP hard.

I can do this by reducing X to Y, if Y is as difficult as X then it is NP hard, otherwise it is not.

But how is this done exactly? Do we restate the problem?

When I looked online it was something about reducing 3 SAT problem to Clique problem, but I don't even know what these problem are.

Is there a trivial example showing how this is done? Thanks!


texts: On different characterizations of $\mathsf P$

texts:
In here it was clarified that $\cap_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})\subsetneq\cap_{\epsilon>0}\mathcal C(n^{n^\epsilon})$ where $\mathcal C(t(n))$ is the class of problems solvable in $O(t(n))$ time.

My query now is whether there is a function of $g(n,\epsilon)$ that non-trivially depends on $\epsilon$ with $g(n,\epsilon)<g(n',\epsilon')\implies\epsilon<\epsilon'\vee n<n'$ such that
 $\cap_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})=\cap_{\substack{\epsilon>0}}\mathcal C(n^{g(n,\epsilon)})$ can hold?

That is I seek a different characterization of $\mathsf{P}$.


texts: Inapproximability bound for a variant of Graph Coloring Problem

texts:
The graph coloring problem, in which we have to decide whether a given graph can be legally colored using $K$ colors, is NP-complete for any $K>2$.

Consider the following more restricted variant of the problem:

Given a graph with $N^2$ nodes in which each node has degree at most $2N$. Provided that we can color the given graph instance with $N$ colors.

What is the best approximation or inapproximation bound known for this version of the graph coloring problem (in polynomial or superpolynomial time)?


texts:
Is it correct to say that since the SHA256 function domain is finite (as reported here) we can build a DFA that calculates this function (i.e. trivially a giant lookup table)?

Furthermore, if we eliminate the limitation on the length of the input, is it correct to say that SHA256 function belongs to the class of $\mathcal{PR}$ primitive recursive functions?


texts:
I am writing a function that can be split into cases

(1)$f(x) \leq f(y)$ and $f(x) \geq f(y)$

or into cases

(2)$f(x) < f(y), f(x) = f(y), f(x) > f(y)$

If I have f(x) = f(y), it is theoretically more efficient to use the cases outlined in (2), but is it actually more efficient in practice?

My concerns are that if $f(x) = f(y)$ theoretically, how often will they also be equal computationally? and if it happens that $f(x) \neq f(y)$ theoretically, how often will they be equal computationally? (As this would cause the algoritm to produce a wrong answer).

Note that if $f(x) = f(y)$ theoretically, but computationally are not equal, the algorithm will still produce a correct final answer - just will reach it slightly slower.


texts: Is per-record timeline consistency is somehow equivalent to causal consistency?

texts:
What I understand about per-record timeline consistency is:

  For a specific primary key all the insert/update/delete operations should
  be read in the same order by all replicas.

Since all modifications to a specific primary key are causally related (a client reads it, then modifies or delete it), then per-record timeline consistency is somehow equivalent to causal consistency. If they are essentially equivalent, then why put another name on it? Am I missing something?


texts:
I read a post about differences between synchronous and asynchronous transmission modes.
That post has a picture about how bits flows from terminal to computer in async mode.

But how computer can distinguish between 1s and determine what 1 does actually mean. Is it parity bit, is it start/stop bit or maybe it's start of idle bits?  Or just part of data is being transmitted?


texts: What cannot be proven at compile-time about a computer program?

texts:
Is there a Turing-Complete-ish programming language without runtime errors? Like segmentation faults, memory leaks, race conditions, deadlock/livelock/starvation, etc.? With strongly typed languages, the compiler can detect null pointer exceptions and refuse to compile code. How much can we statically check? Everything, or are there some things impossible to check?

Are there any language projects that are trying to do this (especially with concurrent and networked applications)?

EDIT:

I guess there are two sorts of behavior that I'm looking to avoid: unwanted erroneous behavior (deadlocks, etc), and runtime exceptions (divide-by-zero, etc).

Taking the example of divide-by-zero, can we create some computation x/y so that, whenever such a computation is done, we require y to be of the type T nonzero where T is integer, floating-point, or whatever for that overloaded operator?

With deadlocks, and other concurrent scheduling hazards, is there a set of control structures which cannot create those hazards, or better yet, can detect those hazards at compile time (better because I think it might be more expressive)?


texts: Which number representation takes the largest amount of memory?

texts:
Options are:

Signed magnitude
One's complement
Two's complement
Excess notation

This is the question from an 'example of a previous exam' I've been given at university. Answers were not provided.
As far as I understand only one answer must be chosen, but I'm not seeing which one.

My attempt at solution
As we see from Signed number representations  wikipedia article, both 1. Signed magnitude and 2. One's complement can be chosen as representations requiring the largest amount of memory, because they take up space for both negative and positive 0 (unlike 3. Two's complement and 4. Excess notation).
Is this reasonable, can we say that both 1. and 2. should be chosen as answers here despite question requiring only one answer?


texts: Distribute to pairs with efficient algorithms

texts:
The task is to find a efficient algorithm to the following problem. There are n boys and n girls who need to be divided to pairs. You get a list with all possible pairs that could be made. It means that if the pair (a,b) is in the list then the boy a can be paired with the girls b.

It is known that each boy appears in exactly two pairs, and each girls appears exactly in two pairs. I need to find an algorithm which will find me a proper division to pairs.

My idea was to define a graph. The vertices will be the n boys and the n girls. The edge (a,b) Will be in the graph if the pair (a,b) is the list of possible pairings.

Because each boy and girl appear in exactly two pairs, then each vertex in the graph will be of degree 2.
So every vertex in the graph will be of an even degree.

A connected graph with vertices that are only of even degree has an euler cycle. That way, each connected component in the graph I built will have such a circle.

For each component we fake the circle, with a boy being the starting vertex, and then we erase the last edge in the cycle. Then I define the pairing like this: a boy will be paired with the girl in front of him in the cycle, and the opposite for girls.

This will give me the needed division. Is it good enough?


texts: A variation of the graph coloring problem

texts:
Given a set of colors $M$ and a graph $G=(V,E)$. Allocate the colors to minimize the number edges with same color on the two vertices of the edge (i.e. minimize pairs of adjoining vertices with same color.).

This problem is different from standard coloring problem. Could someone please provide some literature where this problem is studied?


texts:
I am reading "Algorithms 4th Edition" by Sedgewick & Wayne.

The following method computes the number of self loops of an undirected graph $G$.
Why does this code return $\frac{count}{2}$ instead of $count$?
I think self loop appears in adjacency list only once.

// number of self-loops
public static int numberOfSelfLoops(Graph G) {
    int count = 0;
    for (int v = 0; v < G.V(); v++)
        for (int w : G.adj(v))
            if (v == w) count++;
    return count/2;   // self loop appears in adjacency list twice
}

Thank you for your comment, Zach Langley.
Now I have read the following code, and I understand why the above code is right.

 /**
 * Adds the undirected edge v-w to this graph.
 *
 * @param  v one vertex in the edge
 * @param  w the other vertex in the edge
 * @throws IllegalArgumentException unless both {@code 0 <= v < V} and {@code 0 <= w < V}
 */
public void addEdge(int v, int w) {
    validateVertex(v);
    validateVertex(w);
    E++;
    adj[v].add(w);
    adj[w].add(v);
}


texts: What is the equation for a spiral path in 3D?

texts:
I am developing games in Unity 3D. Currently, I am trying to place 3D objects in 3D space in a spiral pattern that looks like one of 2 the strands in a pair of the DNA (helix) spiral pattern.

Would anyone please show me the equation for 3D spiral patterns, which should involve X, Y, and Z coordinate ?

Thanks.


texts:
Let $A_j=\{(a^i_j,b^i_j)~:~ 0 \leq i \leq n,\text{and }  a^i_j,b^i_j \in \mathbb{Z}^+\}$

Given sets $A_1,\ldots, A_{p}$ and a positive integer $k$, the problem is to check whether there exists one element $(a^{i_j}_j,b^{i_j}_j)$ from each $A_j$ such that $\sum_{j}^{} a^{i_j}_j \geq k$ and  $\sum_{j}^{} b^{i_j}_j \geq k$.

It looks like the problem is related to set partitioning problem, however, I am not sure how to get a reduction from set partitioning problem.  Can someone help me to find the algorithm to solve this problem?


texts: Approximate a smooth f(x,y) function with a polynomial function

texts: I have a discrete function of two real variables defined as a set of point in a rectangular domain. The function is smooth. I need to approximate it with a polynomial function of the 2nd degree with the error as little as possible. What algorithm can I use to find out the constants for the polynomial?


texts: How can we convert between a program using `call/cc` and a program using functions written in CPS?

texts:
The Scheme Programming Language says

  It turns out that any program that uses call/cc can be rewritten in CPS without call/cc, but a total rewrite of the program (sometimes including even system-defined primitives) might be necessary.

What are the general techniques to

convert a program using call/cc to a program using functions written in CPS
convert in the reverse direction?


texts: C++: Minimization Using Levenberg Marquardt to Solve for Two Variables

texts:
I am trying to solve this equation using C++:

X and Y are both given sets of data.

X = [x1, x2, ... , xn], Y = [y1, y2, ... , yn]

a is a given integer.

The goal is to find a pair z and k that fulfills this equation based on the given data.

I am currently attempting to solve this equation using non-linear least squares with the Levenberg Marquardt algorithm and I am using ALGLIB as the library to implement it in C++.

The issue that I am having is that all the examples I see solve for one variable (This one in particular). However, I am trying to find the best pair that fits the solution (z and k).

What would be the best way to go about doing this?

Thanks!


texts: Data flow equations to determine value dependencies

texts:
I need to define the data-flow analysis equations to determine the value dependencies of an statement.

For example:

a = 9
b = a + 7
c = b * 2

the value of c depends on the value of a.

I'm sure this is a well known problem in data flow analysis, can any one point to the equations solving this? Static Single Assignment (SSA) form can be used.


texts: How is a dynamic length cpu stall implemented in hardware when the cpu is waiting for a memory fetch?


texts: Proof of NP-completeness of a special case of longest-path problem

texts:
Problem: Longest Path

Input: An undirected graph $G=(V,E)$

Question: Is there a path of length at least $\frac{|V|}4$?

I know that in order to prove the simple version of $k$ longest path, we reduce the Hamiltonian path to longest path. How we can prove the $NP$-completeness in this special case? Should I use a reduction from Hamiltonian cycle?

Edit: A hint : Reduction from Hamiltonian path. Try to think how many vertices should be added to a special instance $G'$ of Longest path problem so that if there is a path least $\frac{|V|}{4}$ vertices in length then there is a Hamiltonian path in $G$.


texts:
I am trying to make sense of the following:

Taken from the MIT website.

So I understand that we want to maximize the distance between the planes H0 and H1, where H0 is defined as wx+b=0 and H1 is defined as wx+b=1. I am following with the definition that the distance betweena point (x0,y0) and a line Ax+By+c=0 is |Ax0+By0+c|/sqrt(A^2+B^2).

What I don't understand is... What is wx+b? So I understand w is the weight vector, x is an input and b is the offset, so wx+b gives an indication's of x's class as predicted using the model with weight vector w. But, when we are looking at the distances between H0 and H1, which are both lines, what 'line' and what 'point' are we referring to?


texts: Prove that if we take all the edges in directed graph that are on some shortest path from 1 to N we will get a DAG

texts:
We are given directed weighted graph with edges having strictly positive weight(>0) with possibly some cycles with $N$ nodes and $M$ edges. Let's observe all the shortest paths from $1$ to $N$ in this graph, finding the single-source-shortest paths from $1$ in the normal graph and the single-source-shortest path from $N$ in the inverse graph we can check for each edge whether it belongs to some shortest path or not.

If we take all the edges that belong on some shortest path and build a separate graph we will get a directed acyclic graph. How can we prove that this graph will never have a cycle? I haven't written many proofs on graphs before, so I solved the problem, however I'm not sure why this will always hold.


texts:
$\log(n)$ is not polynomial; is a problem solvable in $\mathcal{O}(\log n)$ time in P?

$n\times \log(n)$ is also not polynomial; is a problem solvable in $\mathcal{O}(n\times \log n)$ time in P?

If not, what complexity classes contain those problems?

The definitions I've found all refer to "polynomial time", not "at most polynomial time".  This may be at odds with $\mathcal{O}$ being defined in terms of bounds, but I haven't found a source which clarifies the discrepancy.


texts: Stochastic Computing: What is "Bundle Processing"?

texts:
I'm puzzled by a short paragraph found in the article on Stochastic Processing in Wikipedia. There it says:

  Bundle Processing involves sending a fixed number of bits instead of a stream. One of the advantages of this approach is that the precision is improved. To see why, suppose we transmit $s$ bits. In regular stochastic computing, we can represent a precision of roughly $O(1/{\sqrt{s}})$ different values, because of the variance of the estimate. In bundle processing, we can represent a precision of $1/s$. However, bundle processing retains the same robustness to error of regular stochastic processing.

Achieving precision $1/s$ sounds intriguing, but completely counter-intuitive.

Unfortunately the literature on the topic is old and hard to find. (Although I noticed that used Poppelbaum books can be had for a few $ on the usual channels.)

The article Cutler, JR. "ERGODIC : computing with a combination of stochastic and bundle processing" seems to be talking about what is called "Ergodic Processing" in the Wikipedia article. In more recent publications "bundle processing" seems to play no role anymore. Maybe it's going under a different name, now?

Any help with this (old?) topic would be greatly appreciated!


texts: How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

texts:
I have read of an algorithm that a non-deterministic Turing machine $N$ can run to determine whether a given graph $G$ has a Hamiltonian path from the start node $s$ to a certain node $n$:

Write a list of $x$ numbers $p_1, p_2, p_3 ... p_x$, where $x$ is the number of nodes in $G$. Each number in this list is non-deterministically selected to be from 1 to $x$.
Check for repetitions in this list. If a repetition exists, reject.
Check whether both $s = p_1$ and $n = p_x$. If either do not hold, reject.
For each $i \in [1, x - 1]$, check whether $(p_i, p_{i + 1})$ is an edge of $G$. If any are not, reject.
Accept.

I do not understand how this algorithm works. Specifically, in step 1, why am I making a list of random (potentially repeating) numbers from 1 to $x$ (What does this list have to do with the nodes of $G$?)?

Likewise, in step 4, why does $(p_i, p_{i + 1})$ represent a potential edge in $G$?


texts:
I am investigating a small database in a paper:

Each line is a selling record. For instance, Line 2 expresses that Store 100 in Week 383 sold Product 653; for this selling, the move was 16 and the price was 2.19, thus the profit was 16*2.19*2=7.01 (the other columns are not very important).

The authors then show a UML class diagram as follows:

What I cannot understand (and is not explained in the paper) is the relationship between OnSaleKey and DetergentKey. Could anyone tell me what it is about in a UML diagram language?


texts: Understand the DFA: accepting or not accepting "aa" or "bb"

texts:
I want to discuss the strings accepted by couple of DFAs:

DFA in Figure 1 has 3 final states. It looks like that it accepts both the substrings "aa" (q0q3q0q1) or "bb". So this is not I want.

DFA in Figure 2 has one final state q0. Its good because it does not accept "aa" or "bb" but the problem is that it does not accept any string so its useless.

DFA in figure 3 accept a, aba. It looks like that it can accept any number of "ab" but does it accept "aa" or "aaa"? Can the start state generate any number of 'a's to be accepted by the final state? I am not sure somebody please guide me.
Somebody please guide me.
Zulfi.


texts: How to find the “odd one out” in a list of numbers

texts:
I have an array of numbers [x1, x2, x3, etc] that is size is over 20 elements and I'm trying to put together an algorithm to sort the elements based on the "oddness" they have relative to the rest of the list.

I'm defining the "oddness" as the distance from the barycenters, given some threshold T1. The barycenters are where the values tend to concentrate, possibly given some second threshold T2.

Example: [20, 20, 21, 31, 24, 20, 70, 21, 31, 24, 20, 20, 21, 31, 24, 20, 20, 21, 31, 24] and T1=10 The barycenter is about 24 and only odd one out is 70

This case is trivial as the familiar "distance from the mean or median" metric will do eg. d(70)=|24-70|=46>10=T1 and d(31)=|24-31|=7<10=T1

I can't quite figure out how to deal with the more general case of having 2 or more barycenters.

Example 2: [20, 20, 21, 31, 24, 20, 70, 21, 31, 24, 120, 120, 121, 131, 124, 120, 120, 121, 131, 124] Now there are two barycenters d1=24 and d2=124 and the only odd one is still 70

But the previous metric breaks apart. Maybe the hard part is to figure out which are the barycenters.

Note: I'm looking for a fast algorithm rather than an accurate one


texts: Programming language where every expression makes sense

texts:
Per recommendation I am reposting this from Stack Overflow.

Recently I have been thinking about following issue.

Consider the code for a standard "Hello world!" program:

main()
{
    printf("Hello World");

}

Now almost any change in this code will make it completely useless, in fact almost every change will prevent the code from compiling.
For example:

main(5
{
    printf("Hello World");

}

Now to the actual question.
Is there a programming language where every possible combination of symbols - that is, every expression - makes sense?
I tried thinking about some sort of solution and came up with two:

Postfix with a limited number of variables. Essentially all variables are already defined before you write any code and you have to work just with them.
Theoretically you can than perform an arbitrary number of operations by forming a chain of many simple programs, each one of them feeding results to others.
Code could be written as a series of characters in postfix notation;
"Postfix" with a stack of variables. Variables are stored on a stack; every operation takes two variables from the top and puts the result in their place.
The program ends when it reaches the last operation or variable.

Personally I hate both of these. Not only are they limited, they are inelegant.
They are not even real solutions, more like workarounds, essentially "offshoring" some work to an external process.

Does anyone have any other idea how to solve this problem?


texts: Calculating force between n points placed on the x-axis

texts:
There are $n$ charges placed on the x-axis at points $1,2,3,\dots,n$.
We need to calculate the force on each charge by every other charge.
I need the exact force. Charges can be arbitrary. Inputs are the charges possibly in the form of an array.
Force is defined in the usual physical way.

I know an $O(n^2)$ algorithm to do the task. However, it can be done in $O(n\log n)$.

I have read about FFT, but I don't know how to apply it here. I know that we can multiply two degree $n$ polynomials in $O(n\log n)$. This problem is similar to that problem. Any help will be appreciated.


texts: Algorithms for logical synthesis of multiple output bits?

texts:
Karnaugh maps and the Quine–McCluskey algorithm can be good choices for coming up with fairly minimal logical expressions that match the requirements of a truth table.

What if I have a situation where I have $M$ input bits and $N$ output bits though?

A naive way to deal with it would be to solve each output bit independently and come up with $N$ logical expressions.  The problem with that is that in circuitry or in CPU implementations, you can do multibit operations which can potentially handle a more optimal logical expression which takes into account several, if not all, of the bits at once.

Are there any algorithms to come up with a fairly minimal logical expression when you have $M$ input bits mapping to $N$ output bits?


texts: $O(\log n)$ search algorithm for a sorted natural number array with block of 0s on right

texts:
Assume A is an m sized array containing n ($m \ge n$) natural numbers (excluding $0$), sorted on the left of it.
All remaining cells on right are filled with zeros.

For example, $m=10, n=4$:

$$A = \{5,7,11,24,0,0,0,0,0,0\}$$

How can I find the index of a natural number x in A with $O(\log \boldsymbol{n})$ complexity?

Edit: $n$ is not known.


texts:
I have this grammar I want to convert to LL(1):
S -> A B a | A B b
A -> A c | B d
B -> A a | b

I eliminated the left-recursions, I factored out the ambiguous prefixes, and got this:
S  -> A B S'
S' -> a | b
A  -> B d A'
A' -> c A' | ε
B  -> b B'
B' -> d a B' | ε

But then, I realized there's a First-Follow conflict in the last rule, which I couldn't remove.
Some help, please!


texts: Efficiently checking if two star graphs are disjoint

texts:
I have given an undirected graph $G$ with vertex $\{1, ... n\}$ and two star subgraphs $S_1$ and $S_2$, always consisting of ALL neighbors of a given vertex,  and the goal is to check wether the two star graphs have a vertex in common. This will be will be executed $M$ times for $M$ a large integer.

My approach would be to store the graph in adjacency list format and for each vertex store its adjacency list in sorted order.

We can then check in $O(M n \log n)$ time in total if two star graphs of the sequence of $M$ star graph pairs have a vertex in common.

But maybe this can be done more efficiently?


texts: Do we have knowledge bases only because the logics are not automated enough? I.e. - is it true, that the ideal situation would be that we use the set of logical formulas as the knowledge base together with the deduction services of the relevant logic as the reasoning services for this "knowledge base". But not all the logics are automated enough and that is why we are seeking approximations and representation and reasoning services for the more restricted deductive systems.


texts: What does "finite state transduction" mean?

texts:
Wikipedia says, the regular languages are closed under

  arbitrary finite state transductions, like quotient K / L with a
  regular language.

I wonder what kinds of operations "finite state transductions" are? Btw,
It links to finite state transducer, an automaton.
Thanks.


texts: How to generate regular expression for language of regular expressions?

texts:
Alphabets = $\{0, 1, \epsilon, \emptyset, [, ], \cup, \circ, \star\}$
where $\circ$ stands for concatenation, $\star$ is kleene star, $\epsilon$ is empty string, $[$ and $]$ are brackets to be used for language to be generated.
Only those Regular Expressions to be considered which don't have nested brackets $[[]]$.

How to handle $[ \ ]$ in this problem ?
An expression can be -
$[1\star\star \cup 0] \cup [\epsilon \cup 1 \circ 0] \cup 1\star$

What would be a regular expression that describes the language of such regular expressions?

Edit -

I want to come up with Regular Expression for the Language of Regular Expressions as show in example above. One thing though is that the regular expression should not generate such expressions which contains nested bracket ( we don't want to consider that ) so $[1 \cup [0 \cup \epsilon]]$ is not valid and should not be generated by the Regular Expression.
What I have done and my understanding so far -
For single character Regular Expression would be $(0 \cup 1 \cup \epsilon \cup \phi)$. Be reminded that we are creating regular expression for Language of Regular Expressions. So $(0 \cup 1 \cup \epsilon \cup \phi)$ accepts these regular expressions - $0$ , $1$ , $\epsilon$ , $\phi$.

For $0\star\star$ kind of expressions - $(0 \cup 1 \cup \epsilon \cup \phi)\star^{\star}$ should work.

For $0\star\star \cup 1\star$ types we can have $(0 \cup 1 \cup \epsilon \cup \phi)\star^{\star} \bigcup\ (0 \cup 1 \cup \epsilon \cup \phi)\star^{\star}$

I am getting feeling that somewhere I need to use recursion. So I how to handle bracket $[ ]$ in this case ? How to accept those expressions which have brackets and they are not nested ?
If anyone can give me logic or direction to solve this problem competely that will also be ok.


texts: What are Key benefits of Ontologies in Systematic Literature Review?

texts:
I am working on a Systematic Literature Review (SLR) and about to done with data synthesis. After SLR, I want to create an Ontology and include different details of the SLR in Ontology. I have almost completed the practical steps, but unable to write the motivation behind using Ontology in SLR.

I want you all to please briefly guide me about some key benefits of Ontologies over data which are described in tables and graphs. Please comment also if my question does not fulfill the stackoverflow criteria.


texts:
Suppose you have a matrix A (9x3) of Real numbers and want to sort in columnwise. In this case we can use Leighton ColumnSort algorithms to achieve this.

But question is, how can I sort 3 dimensional (parallelepiped) of real number using the same modified algorithm?

Algorithm for 2D matrix and My idea for 3D parallelepiped:
2D Column Sort:
1, 3, 5, 7 steps: Sort column (array of numbers) however you like
2, 4 steps: transpose columns to rows and reverse transpose
6, 8 steps: forewards shift and backwards shift

3D Column Sort:
1, 3, 5, 7 steps: Sort leftmost facet (matrix) by column sort
2, 4 steps: transpose facets from left side to facets to the front and reverse transpose
6, 8 steps: shift but HOW?
So, What will be the 6,8 steps for my approach? Or if that is not correct what is the algorithms for 3D Column Sort at all?


texts: How do I build a read/write 4-nibble RAM memory system using flip flops?

texts: Currently, I'm learning about flip flops and how it is used in RAM to store memory so I'm trying to recreate the circuitry in Logisim.  I know the components I need which are address register, 4-bit data register, 1 bit read/write register and the actual 4 nibble RAM with its own address space and data space.  How do I create each individual pieces and put them together?


texts: Length of shortest word accepted by exactly one of two DFAs

texts:
Let $M_1$ and $M_2$ be two deterministic finite automata with $M_1$ having $n$ states, and $M_2$ having $m$ states, over the same alphabet $\Sigma$. Show that if $M_1$ and $M_2$ are not equivalent, then there is some string $\omega \in \Sigma^*$ of length at most $n \times m$ that is in exclusively $M_1$ or $M_2$.

It is clear to me that since they are not equivalent, there is some string that is in exclusively $M_1$ or $M_2$. But how can we show that there is some string that does not exceed the required length?


texts: Minimize same placed elements in a list of permutations (Heap)

texts:
I'm trying to optimize the permutations generated from a set of n elements.

Here is the pitch:
I have a set of 6 elements $\{1,2,3,4,5,6\}$ and I want to create 10 permutations. I could use Heap algorithm to keep 10 among 6! possible combinations.

But I'd like to add specific constraint : I want to select the 10 permutations that minimize the number of elements at the same index.
(avoid having 10 permutations with the 3 at the same index for example)

For instance, I simply create the first 6 permutations by rotating my initial set from 1 to 6 to the right to obtain the following combinations: $\{1,2,3,4,5,6\}$, $\{2,3,4,5,6,1\}$, $\{3,4,5,6,1,2\}$, $\{4,5,6,1,2,3\}$, $\{5,6,1,2,3,4\}$, $\{6,1,2,3,4,5\}$

Now, I would like to generate additional combinations following my constraint, do you have any clue or advice ?


texts: Is greedy algorithm the best algorithm for set cover problem?

texts:
Theorem: Unless $NP \subset DTIME (n^{O(\log \log n)})$, there is no $(1-o(1))\ln n$-approximation for set cover problem.

I am a bit confused by this theorem. As we know, greedy algorithm is $(\ln n+1)$-approximation, does this mean greedy algorithm is almost the best algorithm for set cover problem?

In the wiki set cover problem, there is a very bad example about the greedy algorithm, so I think a $\ln n$-approximation is meaningless. Does the theorem above say that it is impossible to design a constant approximation algorithm?


texts: Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length?

texts: I think to prove that $\{a^ib^i | i\geq 0\}$ is not regular, we just have to consider the string $a^nb^n$ (which is in the language) and apply the pumping lemma. But I'm not sure how to proceed using the pumping lemma (even though I know it applies with our choice of string, since the string is at least $n$ long).


texts: Efficiently prime factorising an integer with an oracle

texts:
Suppose you have a program one_factor(N) that, given an n-digit binary number, N, returns one of the prime factors of the number in Theta(n^2) time (note that I used a lowercase n in my theta notation.)

Using this algorithm, I want to find an efficient algorithm to factor an n-digit binary number into primes and print the prime factors. Moreover, I want to know how fast the algorithm runs as a function of n, and I also want to compute the approximate number of times my algorithm uses the one_factor(N) oracle in the worst case as a function of n.

Suppose we can add, subtract, divide, and multiply two n-digit binary numbers in Theta(n) time.

Here are my thoughts:

If the function one_factor(N) returns N, then I know that N is prime, and this can be my stopping condition.
If one_factor(N) returns a factor f, then I know that N/f is also a factor of N.
Thus, with each call to one_factor(N), I can find two factors of N, and I can divide out these factors from N. Then I can repeat the procedure.

I'm not exactly certain that this procedure always works. However, if it does, then I'll be finding two factors for every call to one_factor(N).I have no clue how to find the worst case number of times I call one_factor(N) or how fast my algorithm is though.  It seems pretty difficult to analyze. I think I would be able to come up with an expression in terms of the number of prime factors that the number originally has, but I can't seem to come up with an expression in terms of the number of binary digits.


texts:
I am trying to understand how many states should be there in a Finite Automata which does not accept anything.

I thought it to be containing only one non-final state, the starting state, with all transitions going to itself.

But one of my teachers mentioned that the set of final states cannot be empty. Does that mean there will be two states states, one start state and one final state, with no transition between the two?


texts: Hardness of counting solutions to NP-Complete problems, assuming a type of reduction

texts:
The $\text{NP-Complete}$ class of problems is defined w.r.t Karp Reductions, which are polytime many-one reductions. However, they need not necessarily preserve the number of solutions. A more restrictive type: polytime one-one reductions do indeed preserve the number of solutions.

Suppose $f:\Sigma^{\ast}\to \mathbb{N}$ is a counting function in $\text{#P}$ and the decision problem $f_{ > 0}$ defined as: Is $f(x) > 0$ ? is in $NP$.

Now if $f_{> 0}$ is in $\text{NP-Complete}$, can we immediately tell that $f$ is in $\text{#P-Complete}$ or, do we could only say so, if the reduction map (showing $\text{NP-Completeness}$) was one-one.


texts:
I'm doing a practice test for a course on routing problems. There's a question asking to infere the time complexity of the 2-opt method.

I can see that the complexity per iteration is in $O(n^2)$ because you need to check all combinations of 2 arcs. I don't know how to calculate the worst case number of iterations though. The paper we got doesn't say anything about it's tc, so i'm kind of stuck here.

How do i calculate this?


texts: Parameterized complexity of Weighted Satisfiability with few variable occurrences

texts:
Given an integer $k$ and a Boolean CNF Formula $\phi$, Weighted Satisfiability asks whether $\phi$ is satisfiable by a model of weight $k$, i.e., a model that sets at most $k$ variables to true. This problem is W[2]-complete with respect to the parameter $k$.

Let $l$ be the maximum number of clauses that share a common variable, i.e., how often a variable occurs at most in $\phi$.
My question is the following:
What is the complexity of Weighted Satisfiability parameterized by both $k$ and $l$? Is anyone aware of work in this regard?

Note that this problem is NP-complete in classical complexity even if we fix $l$ to be 3, as we can introduce add copies of the variables and make them equivalent ($a\leftrightarrow a'$). This idea does not help in the parameterized setting with $k$ and $l$ as parameters, as it would require unbounded $k$ (all copies have to be set to true).

This problem seems to be connected to the model checking problem p-MC with bounded degree:
Given a first-order logic $\psi$ formula and a labelled graph $G$, decide if G is a model of $\psi$. (See Logic, Graphs and Algorithms by Martin Grohe pdf)

This problem is fixed-parameter tractable with respect to the parameters length of $\psi$ and maximum degree of $G$. In principle, Weighted Satisfiability (with bounded occurrences) can be translated to a p-MC instance, but I do not see how to achieve this with bounded degree. Vertices corresponding to variables would have bounded degree (they are only connected to a bounded number of clauses), but vertices corresponding to clauses could have unbounded degree (they may contain a large number of variables).


texts:
Reading an article on integer factorization I implemented the following -  rather inefficient - factorization method:

  Every odd
  composite can be factored as a difference of
  squares: $$ ab = \left[\tfrac{1}{2}(a+b)\right]^2 -
 \left[\tfrac{1}{2}(a-b)\right]^2$$
  We can look at values of $f(x) = x^2 - n$ until we find a perfect square and factor.

Here's my implementation in Python.

def fermat(n):
    x = int(np.sqrt(n))+1
    y = int(np.sqrt(abs(y*y - n)))

    while( n - x*x + y*y != 0):
        x += 1
        y = int(np.sqrt(abs(x*x - n)))

    return x, y

How expensive are the square root calculations here?  Are they necessary?
In order to check I have a perfect square, I compute $\lfloor \sqrt{x^2-n}\rfloor$ many times.


texts: Can a total programming language be Turing-complete?

texts:
I've seen two answers to this:
Wikipedia says no:

These restrictions mean that total functional programming is not Turing-complete.

And the Wikipedia article cites D.A. Turner as the coiner of "total functional programming," and Turner says on page 755 of Total Functional Programming:

There are two obvious disadvantages of total functional programming

Our programming language is no longer Turing complete
If all programs terminate, how do we write an operating system?

But Conor McBride says total programming languages can be Turing-complete:

Now represent the semantics of Turing machines as coinductive processes and review your hasty and inaccurate repetition of the common falsehood that totality prevents Turing-completeness. You exactly get to say “we know how to run it for as long as we’re willing to wait, but we can’t promise you it will stop”, which is both the truth, and exactly the deal when you work in a partial language. The only difference is that when you promise something does work, you’re believable. The expressive weakness is on the partial side.

Turner had indeed thought about codata, and it plays a big role in their article re problem (2), but they don't seem to think codata helps with (1).
Would an answer to McBride's Retort be something like:

Re "Now represent the semantics of Turing machines as coinductive processes ..." A Universal Turing Machine won't halt (if executing a program with an infinite loop), but a copgram will always halt until someone asks it to compute some more: to actually do computation for infinite time rather than just representing an infinite computation requires non-termination.


texts: Misunderstanding of proof with transitivity of logspace reduction

texts:
I read a commonly known proof of transitivity of logspace reduction:
Lemma 6.: http://www.cs.au.dk/~arnsfelt/CT10/scribenotes/lecture5.pdf
.  In this proof it is used following trick: Let some turing machine $M_f$ for language $f$ compute only $j$-th bit of output.  Ok, $M_f$ is logspace machine, however tape with output can require $O(n)$ space. Hence, we can't get $j$-th  bit in such easy way.

Where am I wrong ?


texts: Finding a subset of objects with max value with constraints

texts: There are m people and n kinds of objects. Each person has exactly one instance of each kind of objects, but these objects have different values associated. Now I want to find a subset of objects from all those m*n objects satisfying the condition: it should have p objects of each kind (p < m), and a person cannot contribute more than p objects. I want to maximize the total value of the objects picked. I have tried several obvious greedy algorithms, but none of them has found the optimal solution. Is there an algorithm that is not NP hard?


texts: Priority queue for partially ordered priorities with infima

texts:
I have a some objects with priority that is compound type and is only partially ordered. I need to select the objects in order of this priority (i.e. yield minimal item each time). But rather than arbitrarily completing the order, I would prefer if the queue was stable in a sense that if there is more than one minimal element, it should return the oldest first.

Is there any heap data structure that would work with partial ordering? Or a modification of regular priority queue to work with it? Common choice for the algorithm I need is simple binary or 4-ary heap, but that does not work with partial ordering.

The priority values support:

Partial ordering using operation $\preccurlyeq$. It's partial ordering, so it's possible that $a \preccurlyeq b$ is false and $b \preccurlyeq a$ is also false. I write $a \not\lesseqgtr b$ in that case.
Finding infima (glb) and suprema (lub). $\inf(x_i)$ is the maximal $y$ such that $y \preccurlyeq x_i$. Calculating the infimum of $n$ values takes $O(n)$ time. Infimum (and supremum) of every set exists.
A linear extension for the partial ordering could be defined. Using it for the priority queue is the easy way out as the algorithm does work that way. But the order affects performance and the order of insertion looks like it should be best in avoiding worst cases.

Additionally the algorithm that I want to use this in needs to know infimum of all priorities in the queue.

The priorities have some real-world meaning, but are subject to change, so it does not seem viable to rely on other properties they could have.

Note: Binary heaps don't work with partial ordering. Assume a binary heap with $a$, $b$ and $c$, where $a \preccurlyeq c$ and $a \not\lesseqgtr b$ and $a \not\lesseqgtr c$. They are positioned in that order, so

     a (0)
   /   \
 b (1)   c (2)

now d is inserted. Next free position is 3, the left child of $b$, so we get

        a (0)
      /   \
    b (1)   c (2)
  /
d (3)

If $d \preccurlyeq a$ (which implies $d \preccurlyeq c$ from transitivity, but does not say anything about $d$ and $b$) and $d \not\lesseqgtr b$, then $d$ does not get swapped with $b$, because it's not less. But it actually is less than $a$, but it's not compared with it, so now the main heap invariant does not hold; top is not minimal.

I suspect a forest of heaps somewhat in style of binomial heap could be made to work.  Basically it's important to always compare new values with root and only link together comparable elements. It would make the trees in the forest randomly sized and thus make the complexity dependent on number of mutually incomparable sets in the heap. I somewhat suspect the complexity can't be fixed (we have to keep comparing until we hit a comparable element) I might have missed something, so I am leaving this open.

Note: The ordering is partial and while there are ways to define a linear extensions for it, adding a timestamp and using it as secondary criterion is not one of them. Suppose we assigned the timestamp $t(a)$ for each $a$ and defined the ordering $\preccurlyeq'$ as $a \preccurlyeq' b$ iff $a \preccurlyeq b$ or
($b \not\preccurlyeq a$ and $t(a) \le t(b)$.
Then suppose we have distinct $a$, $b$, $c$, such that $t(a) \le t(b) \le t(c)$ and $c \le a$. Then $a \preccurlyeq' b$ and $b \preccurlyeq' c$, but $c \preccurlyeq' a$, so the relation is not transitive and therefore is not an ordering at all. This kind of extending only works for weak orderings, but not partial ones.

Edit: I realized that not only is infimum of any set defined, but I actually need to be able to get infimum of elements currently in the queue efficiently. So I am now contemplating whether adding special nodes containing infima of subtrees to some common heap structure would help.


texts: MergeSort k arbitrary words in linear time

texts: Given $k$ arbitrary words, such as $\{\text{"fjqke"}, \text{"gbqig"}, \text{"a"}\}$, is there a way to mergesort these words in linear time so that the final output would be "abefgggijkq"? I tried to approach it by first sorting all the words independently and then merging the words into the final output, but sorting all the words takes $O(kn\log n)$ time.


texts: Definition of Closed Under Left Polynomial Composition

texts:
I am studying Computation complexity using Papadimitrious's book: "Computational Complexity".
While doing Problem 7.4.4, I came across the definition of what it means for a class of functions $C$ to be closed under left polynomial composition.
Here is Problem 7.4.4:

"Let $C$ be a class of functions from nonnegative integers to nonnegative integers. We say that $C$ is closed under left polynomial composition if $f(n) \in C$ implies $p(f(n)) = O(g(n))$
for some $g(n) \in C$, for all polynomials $p(n)$. We say that $C$ is closed under right polynomial composition if $f(n) \in C$ implies $f(p(n)) = O(g(n))$ for some $g(n) \in C$, for all polynomials $p(n)$.
Intuitively, the first closure property implies that the corresponding complexity class is "computational model-independent", that is, it is robust under reasonable changes in the underlying model of computation (from RAM's to Turing machines, to multistring Turing machines, etc.) while closure under right polynomial composition suggests closure under reductions (see the next chapter).

My doubt is what is the correct way of interpreting this definition and proving that a given class of functions $C$ is closed under left polynomial composition. The definition got me confused since the part "for all polynomials $p(n)$" appeared after the part "for some $g(n) \in C$". I thought about two interpretations.

Given arbitrary $f(n) \in C$ and $p(n)$, exhibit some $g(n) \in C$ such that $p(f(n)) = O(g(n))$. Then, you have proved that $C$ is closed under left polynomial composition. I think this makes more sense, since by this definition I was able to prove that the class $C = \{n^k: k > 0 \}$ is "computational model independent", which makes sense to me.

Given an arbitrary $f(n) \in C$, exhibit some $g(n) \in C$ such that for all polynomials $p(n)$ we have that $p(f(n)) = O(g(n))$. While assuming this definition, I gave a counterexample and proved that the class $C = \{n^k: k > 0 \}$ is NOT "computational model independent", which sounds awkward to me.

Which interpretation is the correct one?
Thanks in advance.


texts: I have recently studied about interrupts and context switch i have read that the hardware interrupts cause the interrupt service subroutine to execute for this i read  mixed articles saying that there no need for a context switch to kernel mode and some say we need a context switch to kernel mode from user mode do we need a switch to kernel mode in case of hardware interrupts


texts: Can every node of a link/cut tree be accessed in $O(n)$ time?

texts:
Per the Sequential Access Theorem we can access every node of a splay tree in $O(n)$ time, when accessing the nodes in a specific order.

Given a link/cut tree, is it possible to access all of its nodes faster than the naive $O(n \log n)$ amortized time in the worst-case?


texts: Compile-time error control vs. interval arithmetic?

texts:
I use interval arithmetic for reliable computing. Now, a procedure coded in a good implementation of interval arithmetic takes perhaps about eight times as much as the same procedure carried out without interval arithmetic (if the lion's share of runtime is taken by floating-point computations). I have sometimes been asked why I don't do rounding-error analysis by hand instead. To me, that does not look like a good option: it amounts to saving computer time at the expense of human time, and creates one more occasion for human error.

Now, what would make sense for me would be for there to be a system for bounding rounding errors with the help of a computer. It might not be realistic to expect a computer to analyse the total error in fairly complex procedures, but a human and a computer might be able to do a quicker and more reliable job than a human working alone, and produce a certificate of correctness to boot. (Cf. how it is much easier to produce a formal proof with computer assistance.)

Note: perhaps it shows, but -- I am a pure mathematician; feel free to tell me if what I say seems a little naïve.


texts: Master Theorem Help - How to make the value of "b" greater than 1 as required by the Master Theorem? What math is involved?

texts:
I know how to identify the parts of the Master Theorem, and I know that it is a recurrence relation. I don't understand how to make the "b" value greater than 1.

Please see the image. I know the math is easy, but I am not seeing it. Can someone help?


texts: How to transform lambda function to multi-argument lambda function and how to rewrite or approximate terms?

texts:
I am trying to do the formal semantics (Montague grammar, abstract categorial grammar) of natural language and encode the sentence John is boss. The type system has to primitive types - e for entity and t for Boolean type. John has type e, is has type (e->t)->(e->t) and boss has type (e->t). The the full sentence is translated as the lambda expression:

(is(boss))(John): t

I don't like the chaining of functional application and more intuitive presentation could be by introducing new function IS of type (e, (e->t)) and hence the expression could become:

IS(John, boss): t

And by moving boss from the argument the function index we can arrive to the standard predicate expression with new predicate-function:

IS_BOSS(John): t

I have two questions regarding this example:

Does standard lambda calculus have multi-argument functions? As I guess that these calculus have such function by currying and hence the real type if IS is e->(e->t)->t. So, this part seems to be already answered.
And now is the main question - does lambda caluclus allow do function transformation - e.g. is there some operation which transforms is:(e->t)->(e->t) into IS:e->(e->t)->t? Are there some apparatus/algorithms/methods how can I express function is via the function IS and how can I transform terms involving is into terms that does not contain is and that contains IS? Are there some rewriting apparatus available for this in lambda calculus?

This question is inspired by the book https://www.amazon.co.uk/Elements-Formal-Semantics-Introduction-Mathematical/dp/0748640436 and uses notions and notation from this book.

Important note. I do not expect that is and IS are identical functions (but I would be glad to consider the case when some kind of identity is assumed as well). I expect that is is more general function (that is used for the processing of the raw text) and that I try to express it using more specialised function IS (which can convey more specific meaning, e.g. borrowing from pragmatics (branch of lingustics): I can analyse context and determine that in this context such detalization is desirable). Maybe rewrite operation should be used but maybe some other tools should be used - simply - how to transform term using these functions? Maybe I am just trying to approximate function is with function IS (of different type!) and is-terms with IS-terms? Are there such notions, theories?

Maybe I should look to higher-order rewriting of lambda terms? Is there example available how my terms could be rewritten inside such framework?


texts: How much is VLIW power- and area-efficient then superscalar anyway?

texts:
Most of texts say VLIW, which is lack of hardware to detect hazards and schedule the instructions. But I haven't see any evaluation about how much VLIW can save area(h/w complexity) and power compared to matching superscalar.

Any reliable source is welcomed. Please share with me.


texts: solve a rational equation as fast as possible

texts:
I would like to find the first positive solution(if there is one) to this equation:
$$\frac{ax^2+bx+c}{dx^2+ex+f} = gx+h$$
The simplest way I fond would be to do the following:
$$ax^2+bx+c = (dx^2+ex+f) * (gx+h)$$
$$(=)$$
$$ax^2+bx+c - (dx^2+ex+f) * (gx+h) = 0$$
$$(=)$$
$$Ax^3+Bx^2+Cx+D = 0$$
and find the roots of the cubic.
But, finding the roots of a cubic is computationally expensive.
As it requierers the use of sqrt, cos and sin.
(I am only looking for the smallest positive if there is any, if you know some algorithm that does that even for cubics, I would like to know more about it).
So my question is: "is there another way to find the solutions of this equation?"
Like IF the equation was:
$$(ax^2+bx+c) * (dx+e) = 0$$
it could be solved by solving the quadratic and the linear separately instead of calculating the resulting cubic and solve it afterward.
Any help is appriciated!
Thanks in advance.


texts: Optimal clustering with optimal number of clusters as well as max and min cluster size constraints

texts:
I need to cluster $N$ data points.
I don't know the number of clusters to be formed. It needs to be found optimally.
Also, there is maximum and minimum cluster size constraints, where $C_{\max}$ is the maximum size that one cluster can get and $C_{\min}$ is the minimum size that one cluster must get.
The coordinates of the $N$ data points are stored in a matrix $D\in\mathbb{R}^{2\times N}$, $D$ is a matrix of $N$ rows and each row has two elements defining the $x-$axis and $y-$axis coordinates. However, $D$ can be expressed in any convenient form, for example, $D\in\mathbb{R}^{N\times 2}$ or $D\in\mathbb{C}^{N\times 1}$ (where the coordinates are expressed as a complex number: $x+iy$)
How can I formulate this as a mathematical optimization problem and solve it efficiently?
Data points can be uniformly distributed over a 2D plan of any given size.


texts: Computational complexity of emulating (untyped) λ-calculus with a queue machine

texts:
I am looking for bounds - both lower and upper - on the time, spacial, and state/symbol (i.e. number of states and symbols required) complexity of simulating the (untyped) λ-calculus with a queue machine (roughly speaking, a pushdown automaton with the stack replaced by a (n unbounded) queue).

It is easy to emulate a tag system with a queue machine, and relatively easy to emulate a 1-tape Turing machine with a queue machine, albeit with quadratic time overhead.

As such, I know that it can be done (you can simulate a 1-tape Turing machine with a stack machine in quadratic time and O(1) space overhead, worst case, and simulate untyped λ-calculus with a Turing machine with I-have-no-clue time and space overhead). I am wondering about the complexity bounds.


texts:
Prove that if $g ( n ) ∈ ω ( 1 )$ and $f ( n ) ∈ o ( g ( n ) )$, then $2 f ( n ) ∈ o ( 2 g ( n ) )$.

I was going over this question in my Algorithms class and could'nt understand why first condition has to be met. How would $g ( n ) ∈ ω ( 1 )$ affect our reasoning? Also, what would happen if instead of $g ( n ) ∈ ω ( 1 )$, it was $g ( n ) ∈ o ( 1 )$?


texts: Dijkstra for negative weights by adding a constant

texts:
I have slight modification for graphs which has negative weights for finding shortest path . If the graph has all non negative weights then by Dijkstra's algorithm , it can be done in O(VlogV + E) . So for the graphs having negative edge weights , find min(weights) = K and subtract K from all weights so that we end up with positive weights. Then apply Dijkstra's instead of bellman ford algorithm which takes O(VE) time to find path and then add K to all paths.
Does this method work? If it does then why bellman ford algo is still relevant , If not why?


texts: Can we have a poly time reduction from 2-SAT to 2-Coloring problem?

texts: I know that given a 2-Coloring instance we can easily convert it into a 2-Sat instance in polynomial time . Is the reverse possible? i.e given a 2-sat instance can we convert it into an 2-Coloring instance in poly time?


texts: Integer Linear Programs: An instance or not?

texts:
Given a set of integers $\{x_0, x_1, ... , x_{n-1}, x_n\} \subseteq \mathbb{Z}$, a set of integer variables $\{y_0, y_1, ... ,y_{n-1}, y_n\} \subseteq \mathbb{Z}$ and an integer $m \in \mathbb{Z}$ is the following equation an instance of an integer linear program (ILP):

$
(x_1\cdot y_1) + (x_1\cdot y_1) + \cdots + (x_{n-1}\cdot y_{n-1}) + (x_n\cdot y_n) = m
$
i.e. is there an assignment of variables $y_i$ such that the equation is true?
After googling around I noticed that ILPs usually involve maximising or minimising a variable, but that is not what is needed here. If not, could anyone tell me what type of problem this is and if there are any known complexity results?


texts: Minimum pumping length of finite language

texts:
Background
Let L = {aa}. We know that the minimum pumping length of L is |aa| + 1 = 3. For this length all the three conditions of the pumping lemma vacuously hold true.
Doubt
Let L = {aa, aab}. Is it right to say the minimum pumping length is max(|w| | w belongs to L) + 1(in this case |aab| + 1 = 4) for finite languages?


texts: Is this a valid induction proof example ?

texts:
Learning induction proof now, found a "simple" example, which is a bit confusing to me (not sure if it is a valid example). If so, why the IH(
suppose a  root of rank k  has at least $2^k$ vertices in its tree
)is a valid one since it just repeating the statement that we are trying to prove ? What about the induction step?(Then a root ... in its tree.)

How should we add more information to make easy to follow and more convincing?


texts: How Does a "face" tend to be defined in Face Recognition Algorithms?

texts:
So I am working on implementing YOLOv2 using my own dataset, for face detection. This requires me to prepare a training set of images annotated with the bounding box extents of faces within each image.

My question is: is there any convention for what we define as the face in face detection? For example, do we include the ears? The chin? And if the face is orientated side-on, do we include the ears then?

Or is there no real convention with this?

Thanks for any help you can provide.


texts: Advantages of adaboost over gentleboost in applications, or vice versa?

texts:
I've been researching on AdaBoost and GentleBoost classifiers, but can't seem to find a clear answer to the question:

What is Adaboost better at classifying in computer vision?
What is GentleBoost better at classifying?

I've been told that AdaBoost is good for things with soft edges, like facial recognition, while GentleBoost is good for things with harder and more symmetrical features and edges, like vehicles. Is this true? Is there any proof for this or any evidence to back up this claim?


texts: Arithmetic coding and "the optimal compression ratio"

texts:
Trying to learn more about compression techniques and found something in the wikipedia article on arithmetic coding that I'm not sure I fully grok. In describing how Huffman Coding can sometimes be inefficient, the author refers to an 'optimal compression ratio' that seems to be a function of the probabilities of a given symbol being represented at any given position in the dataset. Am I correct in understanding this to mean:

Given a set of data and a set of probabilities describing the likelihood of any given member of the dataset being a given symbol, then there is no way to represent that data encoded in that manner in fewer bits than the calculated optimal compression ratio?

In other words: there's no way to encode something in few than 'optimal' bits so don't try?


texts: I want to pursue a career in computer programming. Where do I start?

texts:
I am currently finishing up my junior year as a Biochemistry major at a 4-year university. In a year, I will graduate with a B.S. in Biochemistry and way more credit hours than anyone should ever have due to AP classes in high school. To make a long story short, I want to pursue computer programming once I graduate next year. I need to know what to do now, where I should go next. My university does not offer any CS classes, but I am willing to work extracurricularly if it means gaining relevant experience. I'm not completely at square 1, I have some experience with programming, but not nearly enough to compete with a Bachelor's.

1) Do I need a Bachelor's in CS to pursue programming? I have developed and published a handful of websites and iPhone/Android applications over the years, but I never took it on as a full time job. I am conversant in most relevant computer languages, but never as a result of any official classes, just through personal study.

2) What resources are available to me regarding open positions in CS? I have been stuck in my birth state my entire life, and thus have little exposure to the job market outside of a 200-mile radius. I am engaged and plan to move away with my fiancé when we both graduate next year, but I would like to move somewhere that will be conducive to my programming ambitions. Are there any notable cities that are iconic in the CS market?

3) What should I be focusing on now? I would like to finish out my degree program so the past 3 years won't be completely for naught, but what should I be doing in the meantime? Should I pursue some form of internship, should I attempt to strike further out in freelance work, or should I take some sort of online classes?

4) What do employers look for? If I'm looking to make the best first impression, what sort of things should I become conversant in? Is there a core set of languages I should go ahead and start learning?

Honestly I'm just extremely lost and need to know what steps I should take from here. Also, if I can avoid paying for another 4 years of college, that would be great.


texts:
I've heard of bigO notation but I don't really understand how do I determine it for my code and what exactly does it represent?
I heard that there are two:

RunTime
Memory Complexity

How can I learn to use it?


texts: How does the slow All-pairs-shortest-paths algorithm work?

texts:
I am trying to fully understand the following algorithm from CLRS book:

I like to think that it works similarly to Bellman-Ford algorithm by relaxing all edges once for every vertex in the graph. Then we repeat the process for every source vertex $s \in V$. But then looking at the three nested loops in EXTEND-SHORTEST-PATHS and the additional loop in SLOW-ALL-PAIRS-SHORTEST-PATHS I am confused what is happening in every loop. The book says that in every iteration of the loop in SLOW-ALL-PAIRS-SHORTEST-PATHS it computes a matrix of size at most $m$ edges which confuses me even more.

Could someone please explain in simple terms how the algorithm works? Also in line 7 in EXTEND-SHORTEST-PATHS does it mean:
$$l^{'}_{ij} > l_{ik} + w_{kj} \Rightarrow l^{'}_{ij} = l_{ik} + w_{kj}$$
or
$$l^{'}_{ij} >= l_{ik} + w_{kj} \Rightarrow l^{'}_{ij} = l_{ik} + w_{kj}$$
While there might not be a difference in both of these cases on computing shortest path distances, it does, however, produce different results when computing predecessor-subgraph.

Thanks in advance.


texts: Complexity of numerical derivation for general nonlinear functions

texts:
In classical optimization literature numerical derivation of functions is often mentioned to be a computationally expensive step. For example Quasi-Newton methods are presented as a method to avoid the computation of first and/or second derivatives when these are "too expensive" to compute.

What are the state of the art approaches to computing derivatives, and what is their time complexity? If this is heavily problem-dependent, I am particularly interested in the computation of first and second order derivatives for Nonlinear Least Squares problems, specifically the part concerning first order derivatives (Jacobians).


texts:
We have two computers, Comp1 and Comp2, which hold binary matrices A and B of size $n\times n$.

We want to check if the matrices of the computers are identical except for exactly 1 entry.

Comp1 has to send $O(n\log^2n)$ bits to Comp2 and Comp2 should return 0 or 1 (for "no" and "yes" respectively) for the answer.

If the matrices differ by exactly 1 entry, Comp2 will answer 1 ("yes") always.

If they don't differ by exactly 1 entry, Comp2 will answer 0 in probability of at least $1/2$.

Both computers can make any manipulation of their matrix before sending a message. Comp1 of course doesn't have to send a part of its matrix. It can send an answer of computation on its matrix, and Comp2 can make also any calculation it wants before answering.

I've tried to solve it but whatever I tried it failed.


texts: Proof Review: Integer Factorization is in NP

texts:
I want to prove that integer factorization is in NP
I have a general idea of how to prove this, and was wondering if I could get a sanity check:
I'll show it's in NP by using a non-deterministic TM whose longest computational branch runs in polynomial time.
The TM will do the following:
Given an input (binary) word w of length n on the tape:
Non deterministically guess i factors,  1<=i<=n, such that each of the factors is a binary string no longer than n.
Multiply all of the factors together (I think this should take O(n^3)) and accept if the final number on the tape is equal to w.
Otherwise, reject.

Am I missing anything?


texts: What does distinct mean in terms of an array?

texts: I've tried searching this up, but from my what I think it is. It means there are no duplicate elements (ie. all elements are unique elements)?


texts: Graph isomorphism problem for labeled graphs

texts:
In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is exponential, one usually has a polynomial running time.

I was hoping that the situation is similar in the case of labeled graphs. However, I have a really hard time to find any reference which proposes an "practically efficient" algorithm.

Remark: Here, we require that the isomorphism preserves the labels. That is, an isomorphism between two finite automata/process algebra terms would imply that the automata/terms are essentially "equal up to renaming of the nodes".

The only reference I found was the one in Wikipedia that states the the isomorphism problem of labeled graphs can be polynomially reduced to that of ordinary graphs. The underlying paper, however, is more about complexity theory than practical algorithms.

I am missing something, or is it really the case that the there are no efficient "heuristical" algorithms to decide whether two labeled graphs are isomorphic?

Any hint or reference would be great.


texts: Pumping Lemma for Regular Language seems to Fail

texts:
Let $L = \{ab^ncd \mid n \geq 0\}$.  If we take $p = 5$ and $w = abbcd$ and write
$w_i = xy^iz$, where $x = abb$, $y=c$, $z=d$, then $w_2 = abbccd$ which is not in $L$.  We conclude that $L$ is not regular but it obviously is!

What am I doing wrong?


texts: Why is the inapproximability $2^{n^\epsilon}$?

texts:
Many inapproximability factors are $2^{n^\epsilon}$. I don't know why this is 2 instead of 3, 4, ..., etc.

To be precise, given a problem,

theorem 1 says: It's NP-hard to approximate the problem to $2^{n^\epsilon}$ for any $0 \leq \epsilon < 1$;

theorem 2 says: It's NP-hard to approximate the problem to $3^{n^\delta}$ for any $0 \leq \delta < 1$.

Can we say theorem 2 is tighter?

I know that given $\delta < 1$, we can find $\epsilon < 1$ such that $3^{n^\delta} \in \mathcal O(2^{n^\epsilon})$. However, the definition of approximation factor is not in asymptotics. We should get $3^{n^\delta} \leq 2^{n^\epsilon}$ if we want to say the two theorems are actually same.


texts: Is there a Q-like number format for decimal fixed-points?

texts:
As per Wikipedia, the Q number format is

A binary fixed point number format where the number of fractional bits (and optionally the number of integer bits) is specified.  For example, a Q1.14 number has 1 integer bit and 14 fractional bits.

Is there something like this for decimal numbers?
I'm writing a Solidity math library that works with fixed-point numbers, and I would prefer to give these numbers a bespoke name. I'm thinking of "signed 59.18 decimal numbers", since there can be up to 59 digits in the integer part and up to 18 digits in the fractional part.


texts:
There are two parties A and B going on.
Some people are going to party A, some are going to party B.
We are given instructions of the form

different 1 3,  meaning that person 1 and person 3 are attending different parties
same      3 4,
different 4 5,

and then given a command tell 1 4 we have to answer if they are attending the same party or a different.
Like from above we can conclude that 1 and 4 must be attending different party as 1 and 3 are attending different and 3 and 4 attend the same.

My thoughts :  Make a hash table for A and B
given x and y determine which one belongs to which hashtable
if any not present put it in the appropriate hashtable.
Not sure if this is an efficient algorithm for this.
I was wondering if we could build a graph from the given info and then we
can answer any amount of questions like that.


texts: Decidability of CFG that accepts at least one odd length string

texts:
Let $L$ be the language$\{\langle G \rangle : G\text{ is a CFG and L(G) accepts at least one odd-length strings}\}$.

  Prove that $L$ is decidable or undecidable.

Here is my attempt:

$L$ = On input $\langle G \rangle$, where $\langle G \rangle$ is a CFG:

Construct CFG, such that $L(O)$ contains only odd length strings.
Construct CFG $\langle H \rangle$ such that $L(H) = L(O) \cap L(G)$
Input $\langle H \rangle$ to the decider $E_{\text{cfg}}$
If it accepts, $reject$.
Else, $accept$.

Is my proof correct? In the first step, can I construct a DFA, $O$ such that $L(O)$ consists of only odd length strings instead of a CFG?


texts: how to mapping reduce any r.e. language to the diagonal language K?

texts:
We know that the halting problem $A_{TM}$ and the diagonal language K are mapping reducible to each other. Furthermore both are complete with respect to the mapping reduce relation.

I would like to prove that any r.e. language is mapping reducible to K directly without reducing to $A_{TM}$. How can this be done?


texts: Scalability of factor-solve vs. pseudoinverse + product

texts:
I’ve always read advice and warnings about the poor scalability and time spent trying to invert a matrix and why it’s better to solve a system of equations whenever the inverted matrix will be used with a product of something, e.g. (A^-1)b vs. solving Ax=b.

However, I’ve been playing with matrix factorization through alternating least squares and it seems to run reasonably faster at different problem sizes if I solve it by using inverses than by solving systems of linear equations (which is how this is implemented in most software), which is what everyone says shouldn’t happen.

For example, let's say I generate a random matrix X and factorize it as the product of two lower dimensional matrices A and B (initialized randomly), so as to minimize sum( (X-AB)^2 ):

import numpy as np

m1=10000
m2=5000
k=300

X=np.random.uniform(low=1,high=5,size=(m1,m2))
A=np.random.normal(size=(m1,k))
B=np.random.normal(size=(k,m2))

Then I solve this problem using factor-solve:

%%timeit
for i in range(10):
    A[:,:]=np.linalg.solve(B.dot(B.T),B.dot(X.T)).T
    B[:,:]=np.linalg.solve(A.T.dot(A), A.T.dot(X))

1 loop, best of 3: 37.6 s per loop

And solve the same problem by inverting the first term:

%%timeit
for i in range(10):
    A[:,:]=(np.linalg.pinv(B.dot(B.T)).dot(B.dot(X.T))).T
    B[:,:]=np.linalg.pinv(A.T.dot(A)).dot(A.T.dot(X))
1 loop, best of 3: 36.2 s per loop

Am I misunderstanding something? Why is the second option faster than the first one? I think this problem should be large enough for the algorithmic complexity to play a big role on running times, but it seems to bring no advantage.


texts:
A language $L$ is said to be sparse if there exist a polynomial $p$ such that $|L \cap \{0,1\}^n| \le p(n)$.

One trivial example is suppose language is over single alphabet $1$ then $$L = \{1^n | n \in Z^+\}$$

Question : What are the other non-trivial  examples of sparse languages?


texts: Approximating the set of witnesses of a BPP algorithm

texts:
Let $\mathcal{A}$ be a randomized algorithm that decides a language $\mathcal{L}$. For each input $x\in\mathcal{L}$, we define the set of witnesses of $x$ as $W(\mathcal{A},x) = \{r\in\{0,1\}^n:\mathcal{A}(x,r) \text{ accepts}\}$. Suppose that $\mathcal{A}$ is a $\mathsf{BPP}$ algorithm.  We wish to show that there exists an algorithm $\mathcal{A}'$ also deciding $\mathcal{L}$ such that
$$
|W(\mathcal{A}',x)| \geq \frac{2^n}{4}, \qquad \text{and} \qquad
\big|\{0,1\}^n - W(\mathcal{A}', x)\big| \geq \frac{2^n}{4}
$$
for all input $x\in\mathcal{L}$.

I am sincerely lost for this problem. An idea that was vaguely suggested to me was to flip two fair coins and proceed based on the result: trivially accept if the result is $(1,1)$, trivially reject if it's $(0,0)$ and run the $\mathsf{BPP}$ algorithm for the other two remaining cases. However, I am not sure how exactly that could be of any help, of if another way can be found.

Any help would be appreciated.


texts: Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?

texts:
NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction.
According to these posts :
Why not polynomial-space reductions for $PSPACE$-hardness?
PSpace-completeness under PSpace reductions
Every PSPACE language would be PSPACE-Complete if we defined completeness using a
Poly-SPACE reduction (instead of a poly-TIME reduction).
My question is, why does Log-space reduction doesn't imply completeness for every $L \in NL$, for the same reasoning?
Take any A,B $\in$ NL , and fixed $y,n$ s.t $y\in A$ and $n\notin A$.
We can define the following log-space reduction $f$ :
$$f(x)=\begin{cases}\ y&\text{if }x\in A\\
                    \ n&\text{if }x\notin A.\end{cases}$$
Just solve A in log-space and let our output be the fixed instance according to the right case.
How come log-space reductions are NOT useless for NL completeness while Pspace reductions are useless for PSPACE completeness? What am I missing ?


texts: Examples of sets $A$ and $B$ such that $A \leq_m B$ but not $B \leq_m A$

texts: I know that such sets exist and they are called sets that are not m-complete, but I am not sure how to find them. Can someone give examples?


texts: What is the time complexity of finding the residual network in this case?

texts:
Here are the details:

(1) We are given a number $f$ of units of flow that we wish to transmit from the source node to the sink node. For example, $f=5$ units of flow (data or goods) should be transmitted from the source node to the sink node.

(2) We are not given any plan or policy to transmit the flow. However, we know that $f$ is less than the maximum flow of the network. So, it is possible to transmit such an amount of flow through the network.

(3) We are given the arcs' capacities.

$\bullet$ Now, it is required to determine the residual network after sending these $f$ units of flow.

Very simple:

Input: A network with the given arcs' capacities and an amount of flow $f$. Also, two nodes are specified as source and sink nodes.

Output: A plan to transmit $f$ units of flow from the source node to the sink node, and the corresponding residual network.

It is clear that there may be more than one plan to send $f$ units of flow through the network, and so the residual network may change. It is not important to reach a special residual network. My main concern is only to find the time complexity of such a job (finding a way to transmit $f$ units of flow through the network, and then determining the residual network).

It is easy to see that if I have the plan to send $f$ units of flow, the residual network can be determined with time complexity of $O(m)$, where $m$ is the number of edges in the network.

$\bullet$ I highly appreciate any help in advance.


texts:
Can True Randomness be achieved by composing prngs in different states and with different algorithmsv(e.g. have $n$ different composition algorithms, use a prng to select any permutation of them. A lot $(\sum_{i=1}^{n}{^nP_i})$ of permutations exist. Compose the algorithms selected using the permutation. Whenever a new number is generated in a sequence of random numbers the entire algorithm selection process is repeated, and new seeds assigned to all algorithms.

The final result with/from the different prngs will be supplied as output.

For every new number, a fresh seed is taken to the random selection algorithm(to choose the composition of the PRNGs), this should be the most complex PRNG and have as much entropy as possible.

The sequence works something like this. Each PRNG takes two parameters; a seed, and some previous value.

For the first PRNG selected for composition, a seed $s$ is provided, and another randomly generated seed is used to generate another number $c$(This will be done by a randomly selected PRNG not in the sequence. So in actuality, we'll have $n+2$ PRNG algorithms). Each PRNG generates its own random number $k$. By choosing a permutation of some predefined composition algorithms (Whether the random number is to be floating or not, will define available composition algorithms, e.g final value $v \mod max$ will be used to arrive at the random integer) $c$ is used to modify $k$, to generate some $c_i$ to pass to the next algorithm in the sequence. The final $c_n$ will be adjusted to be within range as the random number.

I cannot conceive how such a system may be feasibly 'deterministic'.

Because of this, the algorithm shouldn't be philosophically deterministic. The next number is NOT based on previous numbers.

Arbitrarily designing a PRNG 'algorithm' isn't difficult (slightly modifying an existing algorithm, using different seeds to choose from, generating more than one result and choosing from it, etc). I read a post online about the security flaws of using prngs. How they are ultimately deterministic.

Will such a prng be deterministic?
Will it be able to achieve 'true' randomness?
Assuming all the prng algorithms have the same 'degree' of randomness
What is the minimum $n$ I should choose to make it non-feasibly deterministic? $\tag{*}$

My only worry now, is the computational expensiveness of such a model. It should have a worst case running time of $nf(n)$ where $f(n)$ is the worst case running time of the worst random algorithm. (Assuming PRNGS don't have their running time vary with their outputs) {Though the higher security, might be worth it}.

(*) Feasible deterministic, means that if all computers in the world were connected to make a super computer (assume this is possible and performance scales accordingly) this super computer will be able to 'crack' (be able to determine the next $k$ number(s) in line given an arbitrary list of generated numbers (from the same instance of this algorithm $n$ and arbitrary time $m$ s.
$n,m\colon n \ge m \gt 10^{10^{100}}$
$k$'s value is irrelevant. If it can crack the next 10, then given enough time, it'll crack the next 100.

True randomness, is defined as being non feasibly deterministic.


texts: Relation with the perfect partition problem and the single machine task schedule problem

texts:
Perfect partition problem (PPP): given $x_1,...,x_n\in \mathbb{N}$ we want to know if there's a set $S\subset \{1,2,...,n\}$ such that $$\sum_{i\in S}x_i=\sum_{j\notin S}x_j.$$

Single machine task schedule problem (SMP): a machine can perform only one task $T_i$ with duration $d_i$ at a time and we want to know if all tasks can be done, given that $T_i$ can't start before the time $a_i$ or be finished after the time $b_i$ with $i\in \{1,2,3,...,n\}$.

I want to know how to reduce PPP to SMP.

EDIT: I tried modelling SMP using the constraints and the existence of a bijection $f:\{1,2,3,...,n\} \rightarrow \{1,2,3,...,n\}$ such that $$a_{f(i)}\leq \sum_{j=1}^i d_{f(j)}\leq b_{f(i)}$$ for all $i\in \{1,2,3,...,n\}$. And I tried to make $x_i=d_i$ and get the conditions of the SMP to make the sum be equal to que complementary $\left (\frac{\sum_{i=1}^{n} x_i}{2}\right)$ at some point, but I got stuck as I can't find how to relate $f$ to $S$ from the PPP, that's not really working.


texts: Sub-optimal and fast solutions to assignment problem

texts:
I am looking for a fast solution to the assignment problem for large cost matrices (5000x5000 or larger). The Hungarian algorithm is $O^3$, which is impractical for any moderately large problem.
Are there similar algorithms but sub-optimal and fast, possibly in R (or Python)?

The problem I'm working consists of finding the best pairs of points in sets A and B (|A|=|B|), minimizing their overall distance.


texts: Algorithm to find the shortest walk with k leaf nodes on a tree

texts:
Let's say I have a general tree. What algorithm can I use to find a shortest walk that starts at the root, passes through exactly $k$ different leaves, and ends at the root?  Passing through a node/edge more than once is allowed.

For example, consider this graph:

For $k = 1$, the shortest walk would have the node 4. For $k = 2$, the leaf nodes would be 4 and 12. For $k = 3$, the leaves would be 4, 16 and 17.

What I actually need is the length of the shortest walk (if this simplifies anything).

I could not find an algorithm for this, but maybe I searched with the wrong terms.


texts:
I want to build an expert system for analyzing the personality of a number of people and then distribute them in groups , each group will have members with different personalities.

I have been reading about ES a lot but I still confused , does  rule-based system enough to build the system, or do I have to use matching algorithms like stable marriage or Maximum bipartite matching.


texts: Why isn't every monotonic grammar context sensitive free?

texts: The question is really confusing me. I know every context sensitive grammar is monotonic but not vice versa. e.g. AB--->BA is monotonic but not context sensitive. Can someone explain to me in simple terms why this is?


texts: If X (an NP-hard problem) is polynomial-time many-one reducible to problem Y, then Y is NP-hard. Why is it the case?

texts:
According to this source,

  If A is reduced to B and A ∈ class X, then B cannot be easier than X.  This reduction is used to show if a problem belongs to NPH – just reduce some known NPH problem to the given problem. This reduction thus gives a lower bound for the complexity of B.

Now consider the following scenario: X is an NP-hard problem. It is polynomial-time many-one reducible to problem Y. This makes Y NP-hard. My question is, it could be possible that X has a better solution like NP or P, which we could not find. Then why should Y be NP-hard? It could be NP or P. If Y turns out to be P (assume) then X becomes P.


texts: Define a finite automaton accepting the language below

texts:
$\{ w∈(a,b)^\ast | w $ does not contain '$ab$' as a subword $\}$.

About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite automata. Is there an easier way? Actually, I dont know the regular expression of it either.


texts: Why are programs executed in main memory?

texts: Why are programs kept in main memory for execution? As per my understanding, we need a memory management scheme to manage several processes in the main memory. These things can be done in secondary memory as well (I think). Just to improve performance, we need main memory or there is something more to it?


texts:
It is well known that any CNF formula can be transform in polynomial time into a 3-CNF formula  by using new variables (see here). If using new variables is not allowed, it is not always possible (take for instance the single clause formula : $(x_1 \lor x_2 \lor x_3 \lor x_4)$).

Let define the (SAT to 3-SAT) problem : Given $F$, a CNF formula. Is it possible to transform $F$ into an equivalent 3-CNF defined on the same variables as $F$ ? - where "equivalent" means with the same set of models.

What is the complexity of this problem ?

Edit : It has been shown on cstheory that the problem is co-NP hard.


texts: Show linear bounded automata accepting w is PSPACE-complete

texts:
ALBA={⟨M;w⟩ | M is linear bounded automata which accepts input w}

Show that ALBA is PSPACE-complete.
How I would try to solve it...

We need to prove ALBA belongs to PSPACE. So I would construct TM A which accepts <M;w>. Simulate M till qng^n steps or when it halts. If it halts: Accept <M,w> if M accepts w, otherwise reject.
How would be space complexity? I would say it will need n (=size of the tape) so space complexity should be O(n) and then ALBA belongs to PSPACE. Is it correct?

We need to do reduction from TQBH to ALBA to prove that ALBA is NP hard, but I have no idea how to do it. How should this reduction be done? TQBF must be 1 if ALBA accepts w i guess, but dont know how to show the proof...


texts: How does a given complexity class change under polynomial reduction?

texts:
Suppose we have a complexity class $C$ (say for example $C = DTIME(2^{cn})$).
Take a language that belongs to $C$: $L \in C$.
Define an arbitrary polynomial reduction from language $L$ to $L'$.
To what complexity class does the result language $L'$ belong?

Thoughts: I think it might depend on the model of the computation. Let's assume that the complexity class is $C = DTIME(f(n))$, which is simulated with a Deterministic Turing Machine.  Under a reduction function $h(n)$ of every language in this complexity would be $DTIME(h(f(n)))$, but I'm not sure how to write/prove it formally.


texts:
I have to create an algorithm for homework, but cant figure out where to start.

The divide and conquer algorithm muse be O(nlgn) and returns a pair of numbers p and q in an array A. p must appear before q in the array, and q-p must be the highest possible value

heres and example I made up:

A=[1,4,12,5,9,1,3,8]

the return values would be p=1 & q=12


texts: Grid Based DP: How do we tweak the Travelling Salesman Problem to work with Grids

texts:
The question is:

  There is a n x n grid (Maze) which has either 0, 1 or 2. 0 means a path
  exists, 1 means the cell is blocked and 2 means there exists gold in
  that cell.  Task is to start from 0, 0 and cover the grid such that
  all the gold is collected and then returned to a specific cell (x, y)
  in the grid. This task has to be done in the minimum number of steps.

  Example:
  Input: Maze = {0, 2, 0}, {0, 0, 1}, {1, 1, 1} and
  x = 1, y = 1
  (return to this cell)

  Output: 1 as there is only 1 gold (in 1,1) and we are to return also in
  (1,1) so 1 move is what we need.

Reading the question, I can speculate that this is perhaps a variant of the traveling salesman problem but I cannot think of how I should be applying it here. Also, since in Travelling Salesman we return back to the source node and here we do not, I am having second thoughts if this has TSP like implementation.
Any ideas?


texts: $NP$ is not in $P(n^k)$ for any fixed $k \geq 1$

texts:
I encountered this problem which asks to show that for any fixed $k \geq 1$, $NP$ is not contained in $P(n^k)$...
As an attempt, I thought of using the time hierarchy theorem which says that there exists a language in $P(n^{k+1})$ which is not decided in $P(n^k)$ given that $n^k \in o(n^{k+1})$... Since the space of polynomial verifiers in $NP$ is the union of all polynomials of $n$, using the time hierarchy theorem, this means that there exists a problem in $NP$ that accepts instances only if the accepting branch operates in time $P(n^{k+1})$, and so $NP$ could not be contained in $P(n^k)$...
But is this correct ? I only assumed that such a problem exists  in $NP$ (i.e. which accepts in nondeterministic time $P(n^{k+1})$ due to the time hierarchy theorem, but I have not really been able to construct a concrete problem...