texts: Is the problem that intersection of two cfl is a cfl or not undecidable?

texts: I am trying to use the computation histories argument to fit this. But I am unable to find this as yet.


texts: Is it possible to implement a WeakMap with primitive keys and weak values?

texts:
Theory

Basically, I have a use-case where I would like to use primitives to store weak references to non-primitive values. If the value is no longer referenced anywhere else, then the entry should be GC'd from the WeakMap and checking the primitive key for an existing value would return false.

Is this possible to implement, and how so in a theoretical sense? If not, why isn't it possible to?

Use-case

Since people seem to be confused about the use-case, it's pretty straight-forward. Essentially, consider a function, when given a primitive, generates a non-primitive deterministically using an expensive operation. I expect a fair amount of these generated non-primitives to be used at run-time, and a large percent of them to be re-used.

For the non-primitives that have a reference held onto them, they are used as keys in an operation that coerces them back into the primitive that was used to generate them (this step cannot be avoided, unfortunately), that then must be used to re-generate the non-primitive again.

It would be convenient to have a WeakMap to access the original non-primitive, if it has already been made, instead of using the expensive operation to generate a copy of it, but currently I don't see a way to achieve this.


texts: Does simultaneously finding max/min in array of coordinates by x and y increase comparisons?

texts:
I have an unsorted array of (x,y) coordinates and need to find the min/max for both (x) and (y) separately so that I can build a bounding box using $O(\frac{3n}{2})$ comparisons.

If I use this method to find the min/max for the left/fight box boundaries, then use the same algorithm to find min/max of y for the top/bottom boundaries, does this double the amount of comparisons or can I still claim it’s $O(\frac{3n}{2})$?


texts:
Possible Duplicate:
  A puzzle related to nested loops

I am trying to count the exact/total number of iterations the following nested for-loops are executed:

s=0
for (i: 1 to n)
 for (j: 1 to i)
  for (k: j to i)
   s = s + 1

I know that the first two for-loops will have n(n+1)/2 iterations. My problem is with the third for-loop. Due to this third loop what factor am I supposed to multiply with n(n+1)/2 to get the total number of iterations?

Any help would be appreciated? Thanks


texts: Using Yao's principle to find a lower bound

texts:
This is a HW question, so I'm not expecting any answers, just a general guidance/help.

Definition. Given $\underset{\neq0}{\underbrace{s}}\in\left\{ 0,1\right\} ^{n}$, a function $f:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} ^{n}$ will be called s-difference-preserving if for all $x,y\in\left\{ 0,1\right\} ^{n}$ s.t. $x\neq y$: $x\oplus y=s\iff f\left(x\right)=f\left(y\right)$ (where $\oplus$ is the bitwise xor operation).

Given a difference-preserving (that is, there exists such s so it is s-difference-preserving) function $f$, we talk about algorithms that find such $s$.

We need to prove that every such random (las-vegas) algorithm worst case (w.c. input) average (on the randomness of the algorithm) complexity is $\Omega\left(\sqrt{2^{n}}\right)$.
Where by complexity, we talk about query-complexity. That is, how many times we need to query f, to find a value for an input $x$ - that is, find $f\left(x\right)$.

What I know and tried so far:

I assume this is a classic problem for Yao's principle.
So I want to find a distribution, and an optimal deterministic algorithm for it (optimal on average, on that distribution), such that its query-complexity is \Omega\left(\sqrt{2^{n}}\right) on average on that distribution.

Given an $s$, it's easy to create an s-difference-preserving function, since any $s$ defines a partition of pairs on $\left\{ 0,1\right\} ^{n}$. So we just need to choose a different value for every pair $x,y$ s.t. $x\oplus y=s$.

I also know $f\left(0\right)=f\left(s\right)$, and that to find $s$ for a fuction, it's enough to find a pair $x,y$ s.t. $f\left(x\right)=f\left(y\right)$, and then calculate $x\oplus y$.

I thought of defining $\forall i\in\left[\sqrt{2^{n}}\right]:\ s_{i}=i\cdot\sqrt{2^{n}}-1$. And create $s_{i}$-difference-preserving function $\forall i\in\left[\sqrt{2^{n}}\right]$.

Define a uniform distribution on them and have the deterministic algorithm check the values of every $s_{i}$. This is done in $\sqrt{2^{n}}$ queries on average. But I don't know how to prove this algorithm is optimal for that distribution. Furthermore, I suspect it isn't, since then I would be able to do the same with $s_{i},\ \forall i\in\left[2^{n}\right]$ and “prove” a lower bound of $2^{n}$ which is probably not true.

I would love any help with this.Also, not as part of the HW, but because I'm interested (these are questions we don't need to submit a solution to), can you think of any deterministic algorithm for the general problem? can you think of any monte carlo random algorithm (with 0.5 chance of success)?

I hope this is not too long, and written clearly enough. Would appreciate any help. Thanks!


texts: Can the HTML5 parsing algorithm be implemented in linear time?

texts:
Can the HTML5 parsing algorithm (https://html.spec.whatwg.org/multipage/parsing.html#parsing) be implemented in $O(n)$, or at worst $O(n\mathop{log}n)$, time, even for malicious input?  It seems difficult; there appear to be places where a malicious document could force the user agent to perform $O(n)$ traversals $O(n)$ times.  This is because the specification calls for the “list of active formatting elements” and the “stack of open elements” to be traversed in several places, and each of those can reach $O(n)$ size.

It appears that most of the queries could be done in $O(1)$ time by keeping a hash table from tag name to the list of unclosed elements with that tag name, along with using a multiset for the list of active formatting elements.  However, the adoption agency algorithm presents a problem.  It can only iterate 8 times, but each of those seems like it is $O(n)$.  And I am not sure what kind of ferociously complicated data structure would work.


texts: What is the Code2 and other concepts of variable encoding in Coding Redundancy?

texts:
Am learning the concept of Coding Redundancy in image compression and am finding it hard to understand the table on page 3 of this document. All other explanations seem to follow the same symbols and methodology but don't explain the concept clearly.

Question1:
In the first column, r1=1/7, r2=2/7 etc and r7 is 1. Why is that? According to the column "Code1", the Code1 is created based on the r value which should range from 0 to 7. Why then are there fractions like 1/7, 2/7 etc?

Question2:
What is "Code2"? At least for Code1, when the value is 000, I know it is the binary representation of 0. But the same thing in Code2, is 11. I don't understand what and how they are trying to represent with Code2.

Question3:
Even if 0 is represented by 11 and 6 is represented by 000001 in variable length encoding, how is the algorithm supposed to know which 0 starts where and which 1 ends where? For example, to represent 60, I'd have to encode it as 00000111. When decoding, how is the algorithm supposed to know that it's 60?


texts: Concurrent Shortest Paths with "Congestion Penalty"

texts:
Given a graph with positive edge weight representing "time to travel through", and 2 or more pairs of start/end vertices, we can find concurrent paths for the pairs such that the maximum cumulative weight along any path is minimum, using classic shortest path algorithms.

Now what if the weight is not static, but represents "congestion penalty", i.e. the weight will be larger if the edge appears in 2 paths in the solution (and increase even more as being shared by more paths)?

Are there algorithms for such a case (or something similar)? Is this NP-hard? We can assume only 2 pairs, all 4 vertices distinct, weights are positive integers, and such.

Thanks!


texts: Partitions of star-free languages and questions on the proof of the Splitting Lemma by Diekert/Gastin

texts:
I'm currently reading a paper on First-order definable languages by Volker Diekert and Paul Gastin.
Im having trouble understanding a part of the proof for lemma 3.2 (splitting lemma).
The part I'm having a problem with, is about the complement:
(Note: I've substituted $B^\infty = B^* \cup B^\omega$ with $B^*$ which shouldn't cause problems)
From the paper:
It remains to deal with the complement $\Sigma^* \setminus L$ of a star-free set. By induction, we have $L \cap B^* A B^* = \bigcup_{1 \leq i \leq n} K_iAL_i$.
If some $K_i$ and $K_j$ are not disjoint then we can rewrite $$K_iAL_i \cup K_jAL_j = (K_i \setminus K_j)AL_i \cup (K_j \setminus K_i)AL_j \cup (K_i \cap K_j)A(L_i\cup L_j)$$
We can also add $(B^* \setminus \bigcup_{i} K_i)A \emptyset$ in case $\bigcup_{i}K_i$ is strictly contained in $B^*$. Therefore, we may assume that $\{K_i \mid 1 \leq i \leq n\}$ forms a partition of $B^*$. This yields: $$(\Sigma^* \setminus L) \cap B^*AB^* = \bigcup_{1\leq 1 \leq n} K_iA(B^* \setminus L_i)$$
Questions:

In the last part of the proof $\bigcup_{1\leq 1 \leq n} K_iA(B^* \setminus L_i)$, why is it enough to only build the complement for $L_i$ with $B^* \setminus L_i$? Why don't we need $B^* \setminus K_i$?
Why does $\{K_i \mid 1 \leq i \leq n\}$ form a partition of $B^*$?


texts: Is $A \leqslant_P B \iff A \in \mathsf{P}^B$? If not are there counter-examples?

texts:
The way I think of reducing problem $A$ to problem $B$ in polynomial time, i.e. $A \leqslant_P B$,  is that you assume an efficient solution to $B$ which is enough to solve $A$. Now, this is suspiciously similar to $A \in \mathsf{P}^B$. I'm confident that $A \leqslant_P B \implies A \in \mathsf{P}^B$ but is the reverse implication true? If not, can you provide some counter examples?
Similarly can anything be said about the statement:
$$
A \leqslant_L B \iff A \in \mathsf{L}^B
$$
Edit: Clarified $\leqslant_P$ is polynomial reduction and fixed notation for PTIME, LOGSPACE.


texts: How does a Turing machine simulate itself

texts:
I have a problem regarding Recursion Theorem in Computation Theory.
So Turing machines can have themselves as input. So they can simulate themselves(this technique have been used in many proofs i saw).
what does a Turing machine that only simulates itself does?(assume the machine has only 2 commands get it's description and simulate it, so it looks like it falls into a loop and simulates forever) does it ever halt? if it does what is its output
I tried to ask around and some said this machine functions as an identity machine and does nothing. (because in the other case it brings down so many problems on the theory)
so I asked another question assume Turing machine T with input x. all this machine does is that it simulates itself on x+1.
the concept of Recursion Theorem is very vague in my mind and I will be thankful if you help me find it's deeper meaning.
p.s : I will be grateful if you recommend me any paper or article about similar concepts in other theories so I understand it better


texts:
I just realized a Control-Flow Graph (CFG) is composed of basic blocks, which is a set of instructions. It is mentioned that you can still do stuff like dead code elimination and whatnot, with the CFG, but that seems like you'd be reaching into the basic block to figure that out. At that point you are dealing with individual instructions. But that's the domain of Data-Flow Graphs (DFG). Data-Flow Graphs are made of connections between individual instructions.

My question is, why not just always deal with individual instructions instead of the basic blocks. It seems like in the end you are using individual instructions anyways. Wondering the advantages a CFG has over a DFG, and vice versa.


texts: What all can a valid approximation algorithm access?

texts: For example can an approximation algorithm call a subroutine which is solving a NP-Hard problem? (like say its trying to find the longest path in some graph as an intermediate step) Is that allowed?


texts: Is there a term for the general method used in XORed linked list?

texts:
The XOR linked list is perhaps the most prominent example of storing a reversible hash of two values and using a known value and the stored hash value to derive the other value.  Is there a term for the general mechanism (or a way to describe it very concisely)?

As a related question, are there other somewhat recognized examples of using this mechanism?

In informally studying computer architecture, I have encountered what I think are two or three examples.  One was a suggestion for a MRU-based cache way predictor by XORing the MRU bit with a bit derived from the address; the derived bit is the "known" value.  The other was a similar, XORing the hysteresis bit of a branch predictor with a bit derived from branch information.  A possible third example might be the agree branch predictor which uses a (possibly static) per-branch prediction to bias entries in a dynamic predictor so that aliasing tends to be non-destructive.  A confirmation that these actually should be recognized as the same general mechanism as used by the XOR linked list would also be helpful.


texts: Solving the following recurrence relation derived from a Markov chain

texts:
I have the following system of recursive relations on $y_{i,j}$ that are derived from a Markov chain and that I am having difficulty in solving.  For $i\ge 1$ and $j \ge 1$, we have

$$y_{i,j} \times (p_i+q_j+2)=y_{i-1,j} \times p_i+y_{i,j-1} \times q_j+2y_{i+1,j+1}.$$

Also we have

$$\begin{align*}
y_{1,0} \times (p_1+q_0+2) &=2y_{2,1}\\
y_{0,1} \times (p_0+q_1+2) &=2y_{1,2}
\end{align*}$$

Here $p_i=ai+b$ and $q_j=cj+d$.

I want to solve this infinite system of linear equations.  Ideally, I'd like a closed form for $y_{i,j}$, as an expression in terms of $i,j,a,b,c,d$. At least I would like to understand how the system evolves, such as the asymptotic behavior of $y_{i,j}$ as a function of $i,j$.

I observed a few things: for all $j$, $y_{0,j}$ and $y_{j,0}$ are independent. Also, $y_{1,1}$ is an independent variable.  That's all I could do, nothing more. Help is appreciated.


texts: Find a permutation that maximizes $\sum_i a_{i-1}a_ia_{i+1}$

texts:
I want to solve the following problem:

  You have a list of numbers, for example [10, 33, 7, 7, 12].

  The goal is to find the permutation of this list that maximizes the function $\sum_i a_{i-1} a_i a_{i+1}$, where indices are cyclic (taken modulo the number of elements).

My initial thought was to simply sort the list by descending order and put the second element at the end, but this doesn't work always. Can you suggest an optimal strategy?

EDIT:

My big problem is that i don't get why this is a hard problem.
I get that there is an exponential number of permutations, but why simply sorting the values isn't enough ?

I tried implementing an A star:

each node contains two lists: a list of already placed values and a list of the others that are left. for example the root will be [], [10, 33, 7, 7, 12]
and a final node [7,7,33,12,10], []
the children of a node are computed as follows: take a member of the second list and insert at the end of the first list. the root will have 5 different children.
now the most important part: how to evaluate each node:
$F(node) = G(node) + H(node)$

I evaluate the first list using the fitness function: $G$
Find the highest possible value for $a_{i−1} \times a_i \times a_{i+1}$ in the second list and multiply it by the size of the same list: $H$

This finds the optimal solution but performance-wise it's even worse than the naive algorithm.


texts:
I am trying to prove the first assertion in the following code, taken from notes of Damon Wischik:
def dijkstra(g, s):
    for v in g.vertices:
        v.distance = ∞
    s.distance = 0
    toexplore =  PriorityQueue([s], sortkey = lambda  v: v.distance)

    while not toexplore.isempty():
        v = toexplore.popmin()
        # Assert: v.distance is the true shortest path distance between s and v
        # Assert: v is never put back into toexplore
        for (w, edgecost) in v.neighbours:
            dist_w = v.distance + edgecost
            if dist_w < w.distance:
                w.distance = dist_w
                if w in toexplore:
                    toexplore.decreasekey(w)
                else:
                    toexplore.push(w)

Base case: The estimate of the source node is correct when it is popped.
Inductive step: Consider the shortest path from the source node $s$ to some destination node $d$,
$$ s \to v_1 \to v_2 \to \cdots \to v_k \to d. $$
Assume that the estimates for $s,v_1,v_2,\ldots,v_k$ are correct when they are popped.
When $d$ is popped, we can be sure that $s, v_1, v_2, \dots, v_k$ were popped prior to that as their true shortest distances from the source $s$ are lower than that of $d$. In particular, when $v_k$ is popped, we are sure that the edge $(v_k, d)$ will be relaxed since relaxing the edge $(v_k, d)$ gives us the true shortest distance from the source to the destination, which is definitely an improvement on any prior estimate of D. Hence D's estimate is the true shortest distance from the source when it is popped.
Hence the assertion is true.
Is there a flaw in my proof?


texts: Writing a factorial function in ARM assembly language

texts: I am required to write a factorial function in ARM assembly language that takes an integer $ n $ as input and returns the value of $ n! $. However, I can only use the $ 4 $ basic arithmetic operations $ + - * / $ (so no if-else or loop or recursion). Can anyone suggest a hint to do that? I can only do if I am allowed to use if-else or recursion.


texts:
I'm giving a presentation where I have a single slide dedicated to formal languages. In this slide I give a simplified overview of the Chomsky Hierarchy and I'd like to give an example of a real world language for each tier in the hierarchy.

For recursively enumerable languages I've chosen C++ because in theory its template system allows for infinite recursion (even though gcc does have a recursion limit).

For context sensitive languages I've chosen C, because its sensitive to pre-declared constructs, but AFAIK you can't get the compiler to go into an infinite loop when attempting to recognize if a C program has valid syntax.

For context free languages I take a few liberties and I give Python as an example even though Python is not context free, its closer to context free than it is to context sensitive.

Then we come to regular languages. I initially couldn't think if anything "real-worldy" off the top of my head, but then I considered assembly language. It seems like that might be regular. There isn't any nesting, its just a list of instructions. It seems like you could construct a regex that determines if a string is a valid ASM program.

Let A be the regex that matches a address
Let R be the regex that matches a register
Let K be the regex that matches a constant

Ignoring comments (which should be easy to include) for each command we can make a regex C A|R|K A|R|K ..., depending on the specific args that command C is allowed to take. AFAIK it is syntactically valid to chain any sequence of commands so we could write a gadget G that looks like (C1 | C2 | ... | CN)\n*, which effectively matches any command. A label can be L = \w+:\n*, so then a regex that accepts an ASM program might look something like: (L | G)*

Is that valid? Did I miss anything, or am I correct in using ASM as an example of a regular language?


texts:
I was looking at an example here:
https://blog.parasoft.com/finding-memory-leaks-in-c

#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[]) {
    char *string, *string_so_far;
    int i, length;     length = 0;
    for(i=0; i<argc; i++) {
        length += strlen(argv[i])+1;
        string = malloc(length+1);

        /*  * Copy the string built so far. */
        if(string_so_far != (char *)0)
            strcpy(string, string_so_far);
        else *string = '\0';
        strcat(string, argv[i]);
        if(i < argc-1) strcat(string, " ");
        string_so_far = string;
    }
    printf("You entered: %s\n", string_so_far);
    return (0);
}

and read that when we execute the program with the following arguments:

hello this is a test

The variable string_so_far points to the string “hello” which was assigned as a result of the previous loop iteration. But I don't understand how? A step by step explanation would be really helpful.

Secondly, I came across this example in course material:

int countPrimes(int n)
{
   PrimeSet *p = new PrimeSet(n);
      return( p->countPrimeNumbers() );
}

It was stated that there's a memory leak here but I don"t really understand how, probably because I am not sure what exactly is happening here.


texts: Red-black tree amortized cost of the rebalancing

texts:
I've read in different sources that the amortized cost of a red-black tree rebalancing is constant (at least during the tree creation using only insertions).
How can it be proven?


texts: Are there any hash functions/stateless RNGs that do not use XOR, but produce good quality visual randomness?

texts:
I'm looking for a small function from integers to integers - in a language that only has floats - that can act as a visual RNG. Normally I would use a function such as the one described here:

int cash(int x, int y){
    int h = seed + x*374761393 + y*668265263; //all constants are prime
    h = (h^(h >> 13))*1274126177;
    return h^(h >> 16);
}

However, for the thing I'm working on, I have the added restriction of only using arithmetic operations. the operations I have available are: +, *, -, /, %, sign(), abs(), pow(base, exponent), ln(), floor(), as well as basic trig functions. I'm having difficulty finding anything that doesn't rely on having bitwise operations available. Does anyone know of a hash function that doesn't use xor, that produces reasonable visual randomness when fed a linear sequence of integers?


texts:
We have a Directed Graph with 100 vertexes. v1 --> v2 --> ... v100 and all edges weights is equal to 1. we want to used bellman-ford for finding all shortest paths from v1 to other vertexes. this algorithm in each step check all edges in arbitrary order. if in each step the shortest distance v1 to all others vertexes is not changed, this algorithm halt. the number of steps is related to checking order of edges. what is the minimum and maximum of steps in this problem?

Solution: 2 and 100.

How this solution will be achieved?


texts:
I have studied in my Computability course that it is impossible to design an algorithm $A(x,y)$ which decides, for every couple of programs ($P_1$, $P_2$), whether they are equivalent (e.g. $\forall d \in Data:P_1(x) = P_2(x)$). This is easily shown with Rice's theorem.

I was wondering if a similar problem with SQL queries is solvable:

Is it possible to design an algorithm $A_D(x,y)$ which, given a fixed database schema $D$, decides if, for every possible instance of $D$, $Q_1$ and $Q_2$ return the same table $T$?

Appendix

As suggested in the comments, I'll now specify the legal operations for $Q_i$. I am talking about simple queries such as:

Simple queries with SELECT [DISTINCT] ... FROM ... WHERE
Queries with subqueries
Queries with aggregated operators
Queries with GROUP BY and HAVING
CREATE VIEW

Furthermore, let's assume our SQL is not turing complete, so no CTE or RECURSIVE are allowed.
Lastly, I mean only SELECT-like queries, no UPDATEs, INSERT INTOs, etc...


texts: What will be the output when using pass-by-value-result with parameters such n+1?

texts: Let's say a function $f$ is called with parameter $n+1$. Since I use pass-by-value-result, value of formal parameter will be transmitted to the caller's actual parameter at the end of the call. Let transmitted value be 10. What will be the value of $n$? 9 ($n+1 = 10$) or still 10?


texts: Is there a naming convention for the left child of a right child (and vice versa)?

texts: That is, the right child of a left child, or the left child of a right child. The best that I can come up with is the "opposing child" but I was wondering if anyone has come across an existing naming convention for this.


texts: Maximum product of contiguous subsequence over $\mathbb{R}$

texts:
For the problem of a subsequence of maximum product with negative, zero and positive integers, I have the following working solution (inspiration from here).

Let us first show how to solve the problem when the array contains no zeroes:

If there is a single entry, return the entry.
If the number of negative entries is even, return the product of all elements.
Otherwise, let the array be $A_1,\ldots,A_n$, let the index of the first negative element be $i$, and let the index of the last negative element be $j$. Return
$$
\max \left( \prod_{k=i+1}^n A_k, \prod_{k=1}^{j-1} A_k \right).
$$
(Since $n > 1$, both sums are non-empty.)

For a general array which is not all zeroes, we partition in into maximal subarrays with no zeroes, apply the preceding procedure to each subarray, and return the maximum over all outputs.

Besides this solution, I also have a dynamic programming solution inspired largely from the problem of maximum sum subsequence that works for positive real numbers but not for negative numbers.

Given an array $A_1,\ldots,A_n > 0$, we compute an array $S_1,\ldots,S_n$ such that $S_i$ is the maximum product of a subsequence of $A_1,\ldots,A_i$ containing $A_i$:
$$
S_1 = A_1, S_{i+1} = \max(A_{i+1}, S_i A_{i+1}).
$$
The answer is then $\max(S_1,\ldots,S_n)$.

I would like to know how to change the first solution to handle general numbers rather than only integers, and to understand how these changes work.

I tried to find a data structure for the problem with floating-point numbers, I thought of using $P_{\min}$ and $P_{\max}$ matrices where $P_{\min\ i, j}/P_{\max\ i,j}$ is the minimum/maximum product that can be computed from a subsequence in the $A_i,\ldots,A_j$ subsequence, but I could not find a recursive relation between the elements of the matrices. I think I found some sort of heuristic method using $P_{\min}$ and $P_{\max}$ as vectors that are updated in a single iteration of $A$, each value of $P_{\min}$ depending on $A$ and $P_{\max}$, and each value of $P_{\max}$ depending on $A$ and $P_{\min}$, but I did not test how adequate it is.

An example of why the first algorithm in my question is not working for floating-point numbers is the input $2, 2, 0.1, 2, 2$.


texts: I/O cost to traverse a tree stored in preorder form

texts:
Let T be a binary tree that is stored in the disk following the preorder layout.

For example if this is $T$:

then $T$ will be stored in the disk as follows:

10, 11, 0, 12, 13, 2, 7, 3, 14, 1, 15, 16, 4, 8, 17, 18, 5, 9, 6

Every node of the tree is a struct that stores the offset of the left child, the offset of the right child, the id of the node and a size variable. If a node is a leaf the offsets are set to -1.

Suppose that now in every node $u \in T$ we want to know what is the size of the subtree rooted on $u$. Assume that the elements between the disk and the memory are transferred in blocks of size $B$, the size of the memory is $M$ and it holds that $M \geq B$. Is it possible to do that in  $O(\frac{N}{B})$ I/Os?


texts: Finding a rational non-zero of a multivariate polynomial in polynomial time

texts:
Suppose we have a degree $m$ multivariate polynomial $p(x_1, x_2, \ldots, x_m)$ in $n$ variables (by degree I mean the highest sum of powers of factors in any monomial term). Such a polynomial can have infinitely many rational zeros. Suppose we have landed at one of them, then what is an efficient way to escape from the zeros? Schwartz's theorem gives us
that $p$ can be zero on an at most half of the integer points in any 2m x 2m x 2m x ... n-cube set of points such as the points with x,y,z,... in {0, 1, ..., d}, but this is computationally inefficient. Is there a better way to find a non-zero?

In the actual problem I'm trying to solve, there are restrictions on the $x_i$'s. I'm hoping to find a criterion that I can satisfy within these restrictions, so the more, the merrier!


texts: Empty intersection of longest path in connected graph

texts:
Do all longest paths share a common point? (Gallai 1966)

A few years later, Walther  produced a counterexample on 25 vertices (a). The simplest counterexample was found by both Walther and Zamfirescu independently and has 12 vertices (b).

I found this examples in numerous study, but i couldn't find a vertex that does not appear in all longest paths.

Could you explain how should i see these graphs? Where are paths which intersection are empty?


texts: Sorting a set of $n$ elements containing only $\log n$ unique elements

texts:
We have a set of $n$ elements which contains at most $\log n$ different numbers. I want to sort this set faster than $O(n \log n)$. Is it possible?

I tried using a hash table to find the set of $\log n$ unique elements, then sort them in $O(\log n \log \log  n)$, after that creating a new array of $n$ element with this array of $\log n$ elements in $O(n)$, but it is not the right answer since using hash table may fail, and the worst case still needs more than $O(n \log n)$.

Is there any algorithm faster than $O(n \log n)$?


texts: Space and time complexity of $L = \{a^nb^{n^2} \mid n≥1\}$

texts:
Consider the following language:
$$L = \{a^nb^{n^2} \mid n≥1\}\,$$

When it comes to determining time and space complexity of a multi-tape TM, we can use two memory tapes, the first one to count $n$, and the second one to repeat $n$ times the count of $n$. Thus, because of the way we’re using the second tape, it should have a $\Theta(n^2)$ space complexity, and I would say the same concerning the time one. I thought it was correct, but the solution is $TM(x)=|x|+n+2$, where, $x$ is, supposedly, the length of the string, hence $\Theta(|x|)$. It seems correct to me, so is my reasoning completely wrong, or just a different way to express it?

Could we have reasoned about it differently, and say, for example, for every $a$ we write down a symbol on the first tape, and then count the $b$'s, by scanning the symbols back and forth $n$ times? This time, the space complexity should just be $\Theta(n)$, while the time complexity should remain unchanged. What would change if we had a single-tape TM?


texts: Can we write a program that can say if any 2 given programs do the same w.r.t input - output pairs

texts:
I'm new to theoretical CS research. I have the following question: Given 2 different computer programs, each generating certain outputs for a given set of inputs. Assuming we are given the range of values for input variables (i.e., min to max values), is it possible to check with another program whether these 2 programs will give the same output values for all possible input values, without actually running the 2 programs for all input values?

Thanks.


texts: Is this book's definition of phrase correct?

texts:
I am fairly confident that my textbook (Concepts of Programming Languages 11th
edition, international edition, Robert Sebesta) has an error in its definition
of what a phrase is in the section on bottom-up parsers. After an infuriating
conversation with the professor using that textbook in which I was told that the
book's definition was correct, but was given no reason why or why my reasoning
was incorrect, I still think it has an error. I haven't been able to find any
information about errata in the book online (not the main point of the question,
but I'd like to find that also).

Here is the book's definition:

$\beta$ is a phrase of the right sentential form $\gamma$ if and only if $S \Rightarrow^{*}\gamma = \alpha_1A\alpha_2\Rightarrow^{+}\alpha_1\beta\alpha_2$.

Here is what I think the definition should be:

$\beta$ is a phrase of the right sentential form $\gamma$ if and only if $S \Rightarrow^{*}\alpha_1A\alpha_2\Rightarrow^{+}\alpha_1\beta\alpha_2 = \gamma$

Here is my reasoning: Definitions are mostly arbitrary, so I can't really prove
that it's "wrong" without comparing it with a bunch of other books out there (I
just have the one, so if those of you with more could check that for me, that'd
be great. I can't seem to find any definitions online). But I can prove that
it's not consistent with the rest of the book.

The book states that simple phrases are a subset of phrases, that the handle of
any rightmost sentential form is its leftmost simple phrase, and that in this
example grammar

$\begin{align}
E &\to E + T \mid T\\
T &\to T * F \mid F\\
F &\to (E) \mid id
\end{align}
$

the handle of the sentence "id + id * id" is the first id. Observe that
according to the book's definition of phrase, a sentential form consisting
entirely of terminals can have no phrases, because the sentential form is never
of the form $\alpha_1{}A\alpha_2$. This means that there are also no simple
phrases of sentential forms consisting entirely of terminals. This means that
there are also no handles of sentential forms consisting entirely of
terminals. This means that there are no handles in "id + id * id", despite them
saying there are. So the definition isn't consistent with what else they
say. Based on what I've read elsewhere and heard in class, the definition seems
wrong, not the other parts.

Is my reasoning sound? Is the definition of phrase correct / what is the "correct" definition of phrase?

(apologies if I left out anything essential, I lost the first draft when I got to the captcha requirement and filled it out with spyblock enabled)


texts: How does this proof show that sequences of $O(1)$ polynomially bounded Kolmogorov complexity are NOT the polynomial computable ones?

texts:
I'm trying to understand a proof from the paper: Balcázar, José L.; Gavaldà, Ricard; Hermo, Montserrat: Compressiblity of infinite binary sequences, Published in: Complexity, Logic, and Recursion Theory, A. Sorbi, ed., Marcel Dekker 1997, ISBN 0-8247-0026-0, 75-91.

Theorem 19 For every recursive time bound f , there is an infinite sequence that is in $C4[O(1), poly]$ but not $DTIME(f (n))$-computable. (The sequence is automatically in $C5[O(1), poly]$ and in $CK[O(1), poly]$.)
Proof: The main idea is to build a tally set $T\subseteq\{0\}^*$ with the following properties:

$\chi^T$ is not $DTIME(f (n))$-computable, where $\chi^T$ is the characteristic sequence of $T$ over $\{0\}^*$

$T \in\ DTIME(g(n))$, for some nondecreasing time-constructible time bound $g$ such
that $g(n) \gt f (n)$.

strings in $T$ are very far one from another; more precisely, $T$ contains only strings of
the form $0^{s(m)}$
, where $s$ is defined inductively by:
$s(1) = 1;$      $s(m + 1) = g(s(m))$
[...]

(the proof proceeds by using the third property to show that it's easy/polynomial to create $\chi^{T \leq n}$ up to an uncertainty in exactly one hard bit, and so it is possible to consider two machines, one answering $1$ and an other answering $0$ for it, fulfilling the requirement of $\chi^T$ being in $C4[O(1), poly]$ )
This Theorem is claiming to build a tally set that does the job, and I understand how the proof proceeds, once it is taken granted that the set with the specified properties exists, but I don't see its existence proven.
How do we know that such a tally set exists for every recursive $f(n)$ that is not $\mathrm{DTIME}(f(n))$ computable as specified in property (1)?
And why do we have to guarantee in property (2) that the $g(n)$ bound is greater or equal to $f(n)$?
Am I missing something basic about tally sets, or sets vs characteristic sequences in general, or some trivial hierarchy theorem?


texts: Given a list of strings, find every pair $(x,y)$ where $x$ is a subsequence of $y$. Possible to do better than $O(n^2)$?

texts:
Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know  all pairs $(x,y)$ where $x$ is a subsequence of $y$. We can assume all strings are of length at maximum $m$, where $m << n$ and are all over a finite alphabet $\Sigma$ with $|\Sigma| << n$. We may also assume that the number of pairs $(x,y)$ where $x$ is a subsequence of $y$ is much smaller than $n$.

A trivial algorithm would be this:

1. foreach x in L:
2.   foreach y in L:
3.      if x is subsequence of y:
4.         OUTPUT x,y

However, this has complexity $O(n^2 \cdot m)$ - I am curious to know whether there is a faster algorithm (Faster given that the number of pairs $(x,y)$ is much smaller than $n$, so for example an algorithm with complexity depending on the number of output pairs).

Note that this question is a follow up to this question, which is about the same problem but for substrings (not subsequences). There, the Aho-Corasick algorithm solved my problem perfectly - is there maybe somethign like this but for subsequences?


texts:
I have a graph and I'm trying to enumerate all paths that start at node $S$, end at node $E$, uses each edge, and minimizes the number of edges used (i.e. it can only re-use an edge if strictly necessary).

What I am wondering is that if I have a solution path, e.g. $SADBCABE$, can I find all other valid paths that use the same set of edges by iterating over the ways in which I can reverse loops?

In other words, the example path has two loops: one that over $A$ ($ADBCA$), and one over $B$ ($BCAB$). This leads to five possible paths that can be made by reversing these paths that can be named: $A_0B_0$, $A_0B_1$, $A_1B_0$, $A_1B_1$, and $B_1A_1$. Here, $B_1A_1$ refers to reversing path $B$ and then reversing path $A$. This example makes it clear that order matters.

Will this method of enumeration miss any paths containing the same edge set?

EDIT: After some discussion in the comments, it is clear that further reversals on the five paths listed above could produce previously unfound paths.  It seems like to use this methodology, I would also have to keep a fringe set and ensure that all reversals on the fringe produce paths that I've already found before removing it. This would no longer be a simple enumeration of permutations, but rather a BFS, which is unfortunately less deterministic. Is this already a known problem that I could read more about? I've tried Googling various things about domino trains (since each edge could be thought of as a domino), but I didn't find anything.


texts: How to find recurrences where Master formula cannot be applied

texts:
Given: $T(n) = T(\sqrt{n}) + 1$ (base case $T(x) = 1$ for $x<=2$)

How do you solve such a recurrence?


texts:
I needed help with the following question which belongs to Arden's theorem as I am having a hard time solving it. Please find the question below

Prove:
$$(0+ 11^*0) + (0 +11^*0)(1 +01^*0)^* (1 +01^*0) = 1^*0(1 +01^*0)^*$$


texts:
Suppose I have two generic problems $A_{1}$ and $A_{2}$: the instance of $A_{i}$ is a graph $G$ and a number $t$, and the question is whether a certain parameter $P_{i}(G)$ is at least $t$.

Suppose I want to reduce the NP-c problem $A_{1}$ to $A_{2}$. If I can show that $P_{1}(G) \geq x$ if and only if $P_{2}(G) \geq y$ for any $G$ with at least say $100$ vertices, do I have an admissible reduction?


texts: Register images from a camera which has undergone pure forward translation

texts: Images are taken by a DSLR camera, always set at a particular Focal length.  The scene contains objects with varying distance to the cameras.  Since the camera has undergone translation, homography no longer applies.  Thus looked into Epipolar Geometry for pure translation.  I know a very close estimate of the displacement of the camera (in between images, say Image 1 taken at x and Image 2 taken at x+d).  Is there anyway to find the transformation that maps Img1 to 2 or vice versa to accomplish image registration (need to do image differencing after) ? Can the fundamental matrix and the displacement be used to transform an image to another ?  I am using OpenCV for my implementation.


texts: What's the theoretical difference between class and type?

texts:
This question stems from my effort trying to learn ASN.1.

After I went through the PKCS#1 standard for RSA cryptosystem and X.680~X.683 side-by-side, I noticed that, they've defined

ALGORITHM-IDENTIFIER as a class, and
AlgorithmIdentifier as a sequence type that can be encoded using BER the basic encoding rule.

I've went through the Wikipedia pages on the subjects, in both computer science and mathematical fields. It seems to say that a "class" is more general than a "type" while "type" is more concrete than "class" on the other hand.

So what's the difference from a theoretical perspective? What are the examples? And possibly why the standard developers elect to use such terminology?


texts:
I'm studying Binary Search Trees (BST) and I would like to verify that my understanding of BSTs is correct.

For example, let S = [17, -10, 7, 19, 21, 23, -13, 31, 59].

Binary Search Tree for S, with S1 as root:

How many comparisons is needed to search this tree for the presence of each of the elements in I = {-13, 31}?

Search for -13:

Since -13 is less than 17: Go to left Child
Is -13 < 17?

Comparisons = 1

Since -13 is less than -10: Go to left Child

Comparisons = 2

Item (13) found with two comparisons.

Search for 31:

Since 31 is greater than 17: Go to right Child

Comparisons = 1

Since 31 is greater than 21: Go to right Child

Comparisons = 2

Sincer 31 is greater than 21: Go to right Child

Comparisons = 3

Item (31) found with three comparisons.

Total number of comparisons to find the presence of each item in I: 5.

Is my understanding correct?


texts: Can a Turing Machine be defined over many languages?

texts: What does it mean, if possible, for a Turing machine to be defined over many languages?


texts: How to partition a set into a given number of disjoint subsets subject to some conditions?

texts:
I am given a set $A\triangleq\{1,\ldots,k\}$, an integer $s\leqslant k$, and non-negative integers $a_{ij}$. My problem is to find $s$ disjoint subsets $S_j$ of $\{1,\ldots,k\}$ such that:

$\bigcup_{j=1}^s S_j=A$; and
$|S_j|\leqslant a_{ij}$ for all $i\in S_j$ and $j=1,\ldots,s$.

How to solve this problem? Is it hard to find a feasible solution?

I think it is not easy to solve the problem because I tried some procedure that starts by some $j\in\{1,\ldots,n\}$ and assigns $i\in\{1,\ldots,k\}$ until the number of $i$ assigned to $j$ are greater than $a_{ij}$ for some $i$ assigned. But this is not correct because I could be left of some $i$ that could not be assigned to any $j$ (because of their $a_{ij}$ which could be not satisfied).

The brute force method, when I have to generate all subsets of $A$ and test each one, works for me ($k=8,n=3$) but very inefficient.


texts: Max sum cyclic path of fixed length in matrix

texts:
Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves are up, down, left, right and each position can be visited multiple times but only contributes to your sum once.

Example: for K = 8

7 3 5 9
1 2 0 4
9 4 2 7
7 6 3 2

Optimal route (I think): 0 2 4 9 7 6 3 2 0

First off, of course K has to even (or the problem should state of length at most K). Secondly I was thinking of a solution along the lines of:

opt[i][j][t] = the maximum sum that can be obtained at position (i,j) at time t

The problem with this is that you can't be sure where you can come from. There is no way to (efficiently) know what values you can use to calculate opt[i][j][t]. I could keep the actual path for each position but that would be $O(nmk^2)$ memory, which is essentially $O(n^6)$ - which is extremely unfeasible. Even the solution itself which is $O(nmk) = O(n^4)$ is probably a little too slow. And, in fact, if I have to check each path that would make the complexity as bad as the memory necessary.

Does anyone have any ideas? I would appreciate hints to try to figure it out myself, not actual solutions. Thanks!


texts: Determining number of elements divisible by at least one prime of set

texts:
I have an array ($|A|\leq 10^6$) of numbers ($A_i\leq10^6$) and a set of prime numbers. I have to find the count of the elements in the array that are divisible by at least one of the numbers in the given set.

For example:

  Array: {3,5,7,15,21,143}

  Set: {3,5,7}

  Output : 5

The numbers are 3(3), 5(5), 7(7), 15(3,5), 21(3,7).

If the array size is $10^6$, an $n^2$ algorithm would time out.

Possible approach: I can preprocess all numbers in the array and store the count of elements each prime factors appear in.

For the example given above : The prime factors are 3,5,7,11,13 and values of the count array will be count[3]=3, count[5]=2, count[7]=2, count[11]=1, count[13]=1.

Can the principle of inclusion and exclusion be applied in this case or is there any other approach to the problem?


texts: How can I modify Kruskal's algorithm to work with limited resources?

texts:
In Kruskal algorithm, I decided to use it to construct a minimum spanning tree for a set of N = 100,000 points. Since my hardware does not allow me to keep all the distances between pairs of points, I decided to define the potential edges of the graph in batches of k * N edges (starting of course with the K * N shortest edges, and subsequent batches to compute only when necessary; prior to checking, it seems to me that k = 5 would be appropriate).

Please suggest the implementation of the functions determining k * N edges, so that could be used in the Kruskal algorithm.


texts: Hungarian Algorithm - Bipartite Graph Approach

texts:
I have been having some difficulty making sense of the Hungarian Algorithm outlined here.  It seems incomplete and/or erroneous to me.  The main issue is the line:

  If R_T ^ Z is nonempty, then reverse the orientation of a directed
  path in...

How do we know which path to select as "a path"?  If we select the wrong path, how do we recover?  This seems to be a monotonically assigning algorithm, in that we can only ever create new assignments, but never remove or alter existing ones.

Suppose we have a simple example of S = {A, B}, T = {W, X} with weights AW: 2, AX: 2, BW: 6, BX: 4.  How do we select whether to add AW or AX to the mapping first, or how to we recover from making the wrong selection?


texts:
Recently, I learnt about VC-dimension and how its boundedness assures PAC learnability on uncountable range spaces (let's assume that hypothesis class is the same as the family of concepts we want to learn).

My question is simple: What is/are the geometric intuition(s) behind the concept of VC dimension?


texts: How to analysis the complexity of this LIS program?

texts:
I found a pseudocode online and I don't know why the complexity of it is $O(2^N)$, according to the site.
Given a fixed curr, the for-loop in lis_ending_here(...) will recursively call curr times itself will new curr range from 0 to curr-1, then I stuck here and don't know what's the next step to get the conclusion $O(2^N)$. You can also provide me resource (i.e. book name) which is about the technique to analysis the complexity of recursion, since I don't know what are the beginner friendly ones.
int lis_ending_here(int arr[], int curr)
{
    // Only one subsequence ends at first index, the number itself
    if(curr == 0)
        return 1
    int ans = 1
    for(i = curr-1 to 0, decrement of -1)
        if(arr[i] < arr[curr])
            ans = max(ans, 1 + lis_ending_here(arr, i))
    return ans
}
int longest_increasing_subsequence(int arr[], int N)
{
    // Because a single number can be a subsequence too
    int max_ans = 1
    for(i = 0 to N-1)
        max_ans = max(max_ans, lis_ending_here(arr, i))
    return max_ans
}


texts: Facts about internal and external path lengths of binary tree

texts:
While learning binary tree's properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search.

My book specifies some facts about these as follows:

$S_n=1+\frac{U_0+U_1+...+U_{n-1}}{n}$
For large $n$, $S_n=2 \log_en$
Internal path length $I_n$ of binary tree with $n$ internal nodes is at least $n \times \lg(n/4)$ and at most $\frac{n(n-1)}{2}$

Where

$n \rightarrow$ number of (internal) nodes in binary search tree
$S_n \rightarrow$ average number of comparisons required for successful search in a random binary search tree with $n$ internal nodes
$U_n \rightarrow$ average number of comparisons required for unsuccessful search in a random binary search tree with $n$ internal nodes
$I_n \rightarrow$ Internal path length of binary tree with $n$ internal nodes
$E_n \rightarrow$ External path length of binary tree with $n$ internal nodes (not used above)

Out of these I can complete reason out only the maximum internal path length statded in point 3 as follows: It occurs in degenerate binary tree (point 3.6 on this page). In this case, internal path length is $0+1+2+...+(n-1)=\frac{n(n-1)}{2}$.

About the minimum internal path length, the book says following:

  The minimum internal path length occurs in case of the best case binary tree i.e. almost complete binary tree (maximum possible number of nodes having both children). Such tree has $(n+1)$ external nodes at height no more than $\lg {n}$. Multiplying these and applying the below property:
  $$E_n=I_n+2n$$
  we get the bound:
  $$(n+1)\lg n-2n<n \lg (N/4)$$

Q1. However I am still not clear how the above bound is obtained

Q2. Also I did not understood how first two facts out of above 3 are derived and especially what the first fact is meant to imply.


texts: Understanding the state vector in Quantum Computing

texts:
I have just started to learn QC. It is said that

  The quantum state of $N$ qubits can be expressed as a vector in a space
  of dimension $2^N$

If there is $1$ qubit then we have two possible state vectors $|0\rangle$ and $|1\rangle$ or $(0,1)$ and $(1,0)$ respectively. Getting to $2$ qubits we have $4$ possible state vectors $(1,0,0,0), (0,1,0,0), (0,0,1,0), $ and $(0,0,0,1)$.
Note that in each case, all entries are zero except 1. The point I am trying to get to is that:

$2^N$ seems like a big space but given a vector in this space - all
    components will be zero except $1$. So there are only $2^N$ possible
    values the state vector can take.  Is this not correct? If not, why?
Why don't we say the space is $N$-dimensional. A $N$-bit string has $2^N$
possible values.


texts: For a set of points P, connected by weighted edges (distances) I need a path through all points while minimizing the travel on any edge longer than X

texts:
For a given set of coordinates (lat/lng) I need a path which will visit each coordinate only once. The path needs to be selected to minimize the number of times the haversine distance between two subsequent points along the path is greater than X (ex: 200 miles).
The practical application:
I have airports on a map. I have a string of LED lights which are connected by a fixed distance of wire between them. I want the optimal path between all the airports where I minimize the number of times I need to splice additional wire into the string.
Suggestions on the approach? Maybe some type of genetic algorithm implementation?


texts: Is there a difference between top-down and bottom-up dynamic programming?

texts:
Is there a fundamental difference between top-down and bottom-up dynamic programming?

In particular, is there a problem which can be solved bottom-up but not top-down? Or is the bottom-up approach just an unwinding of the recurrence in the top-down approach?


texts: Is there a logic-to-numeral mapping which preserves uniqueness (contrary to the Gödel coding)?

texts: Given the two equivalent terms $A \vee B$ and $B \vee A$, Gödel numbering returns two various codes $2^{4}.3^{\overline{A}+1}.5^{\overline{B}+1}$ and $2^{4}.3^{\overline{B}+1}.5^{\overline{A}+1}$, respectively. These two codes do not generally equal to each other, which is an unfortunate if one would like to observe the equivalence after the mapping. Thus, is there any alternative logic-to-numeral mapping which takes such symmetries into account, for example, by yielding one code corresponding to both $A \vee B$ and $B \vee A$?


texts: Solve recursive function $T(n) = T(n/3) + T(n/6) + n^{\sqrt{\log{n}}}$

texts:
In one of my college assignments, I came up with the following recursive function which I'm asked to solve:
$T(n) = T(n/3) + T(n/6) + n^{\sqrt{\log{n}}}$
I tried a change of the variable or the recursion tree but I couldn't figure out its solution. I'll be highly grateful if I get some hint about how I can go about this.


texts: What is the relation between reversible circuits and invertible functions?

texts:
A reversible circuit, if I understand it correctly, is a circuit where every gate in the circuit is invertible, i.e. can simply be “turned in the opposite direction”, so that the entire circuit can in a sense just be “turned in reverse” without changing the circuit architecture.

An invertible function is not defined in terms of computational models, but in terms of whether the function is injective.

How are these two concepts related? Does an invertible function always have a corresponding reversible circuit? How does this relate to one-way functions? (Note that if for any invertible function there is a reversible circuit, that doesn’t disprove the existence of one-way functions, since the fast-to-compute circuit might not be reversible).


texts: Assembly language is converted in to machine language by assembler. Why would a compiler convert high-level language to assembly? Can't it directly convert from the high-level language to machine code?


texts:
How is n-times regex alternation operation, e.g. (0|1|...|n), handled in a DFA (MYT algorithm)?

Here are the rules for the MYT also (Converting Regular Expressions to NFAs
):
https://swtch.com/~rsc/regexp/regexp1.html


texts: If set membership problem can be solved for a particular language does this imply that the language is regular?

texts:
If we know that a language is regular, we can solve the set membership question for a given string by running it through the corresponding DFA  for that language.
But what about the other way? Means, if set membership question can be solved for a particular language does this imply that the language is regular?


texts: Optimization of Church-encoded booleans in System F

texts:
I can encode booleans in pure lambda calculus like this:

type Bool = forall t. t -> t -> t
true : Bool = \x y -> x
false : Bool = \x y -> y

Is there a procedure to optimize the following "dumb" function

dumb = \(b : Bool) -> b false false

to

dumb = \(b : Bool) -> false

I can imagine this is quite easy in Haskell with an ADT for example.

One way I can think of is counting the inhabitants of the type Bool (2) and then applying the function to both the inhabitants, discovering that the function will have the same result for any argument. This seems quite difficult to do in general though.


texts: Minimum weighted vertex cover on grid graph

texts:
Let $G'_{m,n}=(V,E)$ be the grid graph $G_{m,n}$, to which we add "diagonal" edges.  For example, here is $G'_{6,3}$:

And for each vertex $v_i \in V$, we have a associated positive value $c_i$

Consider the following algorithmic task:

Input: $m,n,\{c_i\}_{v_i\in V}$ (in unary)

Output: The minimum weighted vertex cover of $G'_{m,n}$

Is this problem strongly NP-hard?
I know the classical grid graph $G_{m,n}$ is a bipartite graph, so minimum vertex cover is equivalent to maximum matching (König's theorem) and thus is in P.

But here, $G'_{m,n}$ is not bipartite. I can't find a way to reduce this to a P problem, or to reduce a NP problem to this.


texts:
Given an undirected unweighted  multigraph $G=(V,E)$ and $s,t \in V$ find a simple $st$-path $P$ s.t. the number of edges leaving $P$ (i.e. the edges with exaclty one endpoint in $P$ ) is minimized.

Does anybody have any idea how to solve this?
I first thought about replacing edges by two arcs and weight them according to some node degrees but the edges staying in $P$ make life difficult.


texts: Why is the unary representation of a number exponentially larger than a base k representation of it?

texts:
According to a book I am reading, the unary representation of a number exponentially larger than a base k representation of it. I, however, feel that the unary representation should scale linearly with the input.

After all, 1 is 1, 2 is 11, 3 is 111, and so on, right? Wouldn't that be linear?


texts: Algorithm for keeping the Maximum and allowing Splits of Strings/sequences

texts:
The problem is as follows:

Given $k$ strings of size $n$, propose a data structure to support the following operations:

Return the maximum of a string.
Given an index $i$, and $2$ strings $a$ and $b$, create 2 strings to replace them:
One of them is compised of the $i$ first elements of $a$ and $n-i$ of the last elements of $b$, and the other string is the $i$ first elements of $b$ followed by the $n-i$ last elements of $a$.

I suppose we need to do a preperation for the structure, and answer the queries as fast as possible.

One solution I thought of is as follows:

For each string, memoize the maximum in all prefixes and suffixes.

Returning the maximum is trivial.
Given the index $i$, the prefixes of the first half are still correct, and only the prefixes of the second half need to be recomputed, and only the first half's suffixes need to be recomputed.

But this results in $O(kn)$ preperation, $O(1)$ maximum, and $O(n)$ splits.

I also thought of using some sort of a Cartesian Tree or RMQ for this.

How can this be done more efficiently, possibly $O(1)$ in both queries?


texts: How do i tell if a grammar is regular or not?

texts:
I know that a regular grammar has a definition

$$\begin{align}S &\to aS\\
S &\to \lambda
\end{align}$$

But I dont really know how to apply this information to check whether or not a grammar is regular...

So for example I have a grammar
$$\begin{align}S &\to aSbSb\\
S &\to \lambda
\end{align}$$

If I compare it to the definition of a regular grammar this is not a regular grammar right? Which also means that I can't turn this into a regex.

Also could you please give me an example of a regular grammar and a non-regular grammar hopefully that will solidify my understanding.


texts: Structuring a Regression Model for NCAA Basketball Spreads/Totals

texts:
I have a basic linear regression model that predicts the spread and total points of NCAA college basketball games. My inputs include various efficiency metrics about each team playing each other. A snippet of the data I am working with looks like:
Team_1 Team_2  Off_Eff_T1 Def_Eff_T1 Pace_T1 Off_Eff_T2 Def_Eff_T2 Pace_T2 Line Over_Under
UCLA   Michigan    116.9    95.2        64.2       118.9      88.7    66.8    6.5    135.5

These are my model coefficients:
adjO_T1 = offensive efficiency for Team 1 (UCLA), adjD_T2 = defensive efficiency for Team 2, etc.
(Intercept)  -5.39321
adjO_T1       0.65668
adjD_T1      -0.67104
adjT_T1       0.01819
Luck_T1      -2.79183
oppO_T1       0.16446
oppD_T1      -0.20572
adjO_T2      -0.66651
adjD_T2       0.66858
adjT_T2       0.09720
Luck_T2       0.30050
oppO_T2      -0.12808
oppD_T2       0.18562

As can be seen, I have efficiency metrics for both teams playing each other. As I have trained my model, the coefficients between "Team 1" and "Team 2" are obviously different. T_1 is the home team and T_2 is the away team. But if I were to switch these (enter T_2 as the home team), the prediction of the spread/total would be drastically different just due to the different model coefficients. Is there a way I can get around this? Aka, the prediction would be the same regardless of what team was entered as home or away. In the example above, if UCLA is T_1 it predicts they should be 2.5 point underdogs. But if Michigan is T_1, they are predicted to be 8 point favorites.
However, Home or Away is not an input to my model so I feel that the predictions should be the same. If someone could provide better suggestions as to how I could structure my data or if I am going about this the right way, that would be a huge help.


texts: Bipartite maximum matching with added constraints

texts:
Suppose you have two lists as follows
List $A$ = $(a_1, a_2, ..., a_m)$
List $B$ = $(b_1, b_2, ..., b_n)$
Each element in list $A$ can be paired with many or no elements in list $B$. I have a function $f(a_i, b_j)$ that returns true or false depending on whether the match is valid or not.  However, if you pair element $i$ in list $A$ then you also have to pair the $i$-th element in list $B$. So, for example, the pair can be $(a_i, b_2)$ and $(a_1, b_i)$ or even $(a_i, b_i)$.
I want to find the maximum number of pairings between the two lists with the added constraint of if the $i$-th element of list $A$ is paired, then the $i$-th element of list $B$ must also be paired.

My intuition says that modifying the maximal matching bipartite algorithm might be useful for this. However, I am stuck in actually figuring out how to do this. Any help would be appreciated.


texts: Finding a complexity by solving inequality

texts:
I would like to calculate the complexity of an algorithm using the "inequality strategy".

This algorithm takes two integers as an entry $n, m$. Moreover this algorithm is recursive and if we denote $C_{n,m}$ the number of operations this algorithm does for entry $n, m$ we have the following inequality :

$$C_{n,m} \leq C_{n, (m-1)} + C_{(n-1), (m-1)} + O(1)$$

Moreover the algorithm terminates for the entry : $(0,k)$ and $(k, 0)$ for all $k \in \mathbb{N}$ and $C_{0,k} = O(1)$ and $C_{k, 0} = O(1)$.

So now I need to somehow solve the inequality to get $C_{n,m}$ for all $n, m$. Yet I don't really know how to do this.

The problem is that it seems to me that any function work. For example If I say : $C_{n,m} = O(m)$ then it's tre since by unduction we then have :

$C_{n,m} \leq O(m-1) + O(m-1) + O(1) = O(m-1)$

Moreover If I say that :  $C_{n,m} = O(n)$ then it also work since by induction :

$C_{n,m} \leq O(n) + O(n-1) + O(1) $

So what is the problem with I am doing, and how to solve this inequality to get the complexity of $C_{n,m}$ ?

Thank you !


texts:
We know that number of coprimes less than a number can be found using Euler's totient function.
But if there are two numbers $p$ and $q$ and we need to find number of numbers less than $q$ and coprime to $p$, is there any efficient method?


texts:
I am a CS novice who just recently encountered the P vs NP problem. And I was wondering whether plain multiplication is a P problem. If it is, does that mean there is a polynomial relationship between the increasing complexity and the time required to solve? I.e. Is there a polynomial relationship between the time required to solve x*1, x*2, x*3, x*4, etc?

I tried to get some "experimental results" by writing simple a Java program that multiplies BigIntegers and counts time of execution. Curiously, I noticed that the execution time only increased in a polynomial manner (e.g. 2ms -> 4ms -> 6ms, etc) when the "complexity" grew in a exponential manner (e.g. x*2 -> x*20 -> x*200, etc), meaning that time and execution of multiplication is a logarithmic relationship instead? Why is this?

Thanks in advance.


texts: How to prove strict space lower bounds using crossing sequences in Turing machines?

texts:
I understand the notion of crossing sequences when talking about time, however how are they used to actually prove strict lower bounds for some decision/search problems?

For example, suppose that you have an array of size N and you want to find the maximum number in it.

Speaking informally, we need at least a pointer to run through the input and some other variable to update whenever we find a number in the input tape that is bigger than the temporary number in our work tape, thus leading us to use Ω(logn) space.

However, how can you prove that you can't do it in O(1) space? Many articles online are using crossing sequences for proving space lower bounds, but they don't show how to do it, they just say something along the lines of "using crossing sequences it's trivial to show that the space lower bound is ..."

which isn't very helpful for beginners like me. Thanks!


texts: How do you go about designing a vector processor architecture for the sum of matrix products?

texts:
The following equation is a matrix expression where $B_i$ and $C_i^T$ are $n\times n$ matrices and k is a positive integer:

$$P = \sum_{i=1}^k  B_i  C_i^T $$

So $P = B_1 C_1^T + B_2 C_2^T + \cdots +B_k C_k^T   $

If $B_i $ and $C_i$ are $n\times n$ matrices themselves, we have a total of 2 $\times$ k matrices that some how need to be stored in this vector architecture.

So this means P will end up being an $n\times n$ matrix after all the computation has completed.

What is the simplest possible vector processor architecture that is required to perform the matrix computation above?

Is there any literature or articles out there that discuss how this can be done?

Would appreciate all / any advise


texts: Relative efficiency of n tasks in 1 loop vs. 1 task each in n loops?

texts:
Say I have 3 simple tasks, to find the min, the max, and the average of an array of numbers.

A modular approach would be to write one function for each, thus iterating over the array thrice. However, that seems wasteful when all the information can be collected in a single iteration.

I understand that both approaches take 3n time but am wondering if one approach is better than the other in the general case and why.


texts: Can I use machine learning to predict someone will buy something in a specific time?

texts:
I have a dataset which has timestamp and goods variable for an object like the following example:

On Moday, John bought Beer, chicken, pizza.
On Tuesday, John bought pizza, pork and beef.
On Wednesday, John bought beer, coke and Vegetable

Can I use machine learning to predict what good will he buy in a specific time and what model can be applied?

Can we answer the question: "What will he buy on Thursday?"


texts: Does 1NF require that there can be no duplicate rows?

texts:
From Database   System Concepts, by  Silberschatz, Korth and Sudarshan :

  A domain is atomic if elements of the domain are considered to be
  indivisible units. We say that a relation schema R is in ﬁrst normal form (1NF) if
  the domains of all attributes of R are atomic.

From https://stackoverflow.com/a/724032/156458

  1NF is the most basic of normal forms - each cell in a table must contain only one piece of information, and there can be no duplicate rows.

If I am correct, "there can be no duplicate rows" in the second definition means exactly that there must exist at least one candidate key in the relation schema.

I wonder if the two definitions of 1NF above are the same?

In particular, is it correct that "there can be no duplicate rows" can't be implied by "the domains of all attributes of R are atomic"?

Thanks.

Updated:

This book seems to say that having a primary key implies atomic  and is it correct?

  In first normal form (INF), related attributes are organized into
  separate  tables, each with a primary key. A primary key is an
  attribute or set of attributes that uniquely defines a tuple. Thus, if
  a table is in INF, entities  within the data model contain no
  attributes that repeat as groups. W. Kent  has explained that in INF,
  all occurrences of a record must contain the  same number of fields.
  In INF, each data cell (defined by a specific tuple  and attribute) in
  the table will contain only atomic values.


texts: Extensional constructs in minimal extensional type theory without eta equality

texts:
The extensional version of Intuitionistic Type Theory is usually formulated in a way that makes extensional concepts like functional extensionality derivable. In particular, equality reflection, together with $\xi$- and $\eta$-rules for $\Pi$ types are enough to get the standard formulation of $\textsf{funext}$

$\Pi_{x \in A}\textsf{Eq}(B(x), f x, g x) \implies
\textsf{Eq}(\Pi_{x \in A}B(x), f, g)$

where $\textsf{Eq}$ is the identity type with rules of reflection and uniqueness of identity proofs (see page 61 of M. Hofmann, Extensional Constructs in Intensional Type Theory).

But what if $\eta$ is not assumed? In particular, consider a standard intensional Martin-Löf type theory with $\Pi$ formulated with $\xi$-rule and "elimination as application", and to which we only add an extensional identity type $\textsf{Eq}$ as described above.
What is the power of the resulting theory, in terms of extensional constructs (like functional extensionality) that can be derived in it? It seems to me that neither $\eta$ nor $\textsf{funext}$ should be derivable, although we can surely get to a weaker version using equality reflection and $\xi$:

$\Pi_{x \in A}\textsf{Eq}(B(x), f x, g x) \implies
\textsf{Eq}(\Pi_{x \in A}B(x), \lambda x . f x, \lambda x . g x)$

(so, from $\eta$ we could get to $\textsf{funext}$, and obviously vice versa).
Here R. Garner shows that the $\eta$ rule is not derivable if $\Pi$ types are given with "elimination as application". He does that for an intensional theory, but the same argument should be applicable in the presence of $\textsf{Eq}$ too, I think.

Are my suspicions correct? Are there any proofs of this in the literature, and in general any investigations on the kind of extensional constructs that can be derived in such minimal versions of ETT? What do we gain by only adding $\textsf{Eq}$, in the presence of such a "limited" $\Pi$ type (no $\eta$ equality, and no induction principle)?


texts: How to calculate time complexity of this problem?

texts:
The problem statement:
Append the length of the string to the string while the length is less than or equal to 10

Input: "a" -> Output: "a12345678910"

Input: "abcde" -> Output: "abcde5678910"

The solution of the problem would require lesser time for a larger input. What should be the time complexity of this?


texts: What's the true meaning of $(a + b)^\omega$ in regular expression

texts:
I'm starting to dabble in language theory, regular expression & infinite words.

I'm not quite sure I completely get the meaning of this expression:

$(a + b)^\omega$

$^w$ meaning infinite repetition, I'm not positive it's standard syntaxe or just our class.

My main question is - do I have to "settle" on either a or b after some position in the infinite word? $abbbbaab^\omega$ would be fine but not $abbbbaa[ a | b]^\omega$ (e.g. I keep having either a or b infinitely)? My understanding is that an English translation would be "you must either have a, or b, at any given position indefinitely". So the + would be like a or condition, essentially.

Expending on that, then $((a+b)(c+d))^\omega$ would accept any alternating patter of (a or b)(c or d), e.g. things like acbcbcadad... but again wouldn't have to "settle" on either $(ac)^\omega$ or $(ad)^\omega$ or $(cc)^\omega$ etc...


texts: Complexity of Estrin polynomial evaluation

texts:
The Estrin model for polynomial of degree $n$ is well known. But the reading of the Knuth (vol 2) or the original's paper Estrin do not help (or I miss it). I am not able to determine the complexity of the algorithm for the number of multiplication. The main equation is:

$$
\begin{align}
c_i^{(0)} &= a_i + x_0  a_{i+1}, \\
c_i^{(n)}     &= c_i^{(n-1)} + x_0^{2^n} c_{i+2^n}^{(n-1)}, \\
P(x_0)    &= c_0^{(n)}.
\end{align}
$$

and it leads for a polynomial of degree 10 to

$$
\begin{align}
P(x_0) &=  a_0 + a_1 x_0 \\
               &+  x_0^2(a_2  + a_3 x_0) \\
               &+  x_0^4(a_4  + a_5 x_0 + x_0^2 (a_6 + a_7x_0)) \\
               &+  x_0^8(a_8  + a_9 x_0 + x_0^2 a_{10}) \\
\end{align}
$$

For the additions: $n$

For the multiplication, it could be $n + \lfloor \log_2 n \rfloor$.

Can somebody confirm?

Best,

++t


texts: If a language X regular, then is the complement of X also a regular language? If yes, then thank you, else can you please explain why


texts: Termination of a composition of terminating functions

texts:
Suppose there are two functions:

$ f : X \rightarrow Y $ and $g : Y \rightarrow Z$

Both $g$ and $f$ can be implemented as algorithms that yield the correct result in a finite amount of time.

It appears to be obvious, that there is also a correct and terminating algorithm that computes the composition of the two $g \circ f$.

But why is that so? Do I need to argue that for both functions, there is a representation in the lambda calculus and in that calculus (with a small-step semantics), there is a trivial implementation of $\circ$? Doesn't that require an encoding of $X$,$Y$ and $Z$? Is there a more fundamental theorem?


texts: Language equivalency for modified CFG closed over intersection

texts:
Suppose "CFG+" was created, where it is identical to standard context-free grammars in every way, but rather than rules being limited to unions, was also closed over intersections, both between CFGs and between other CFG+'s.
Consider non-context-free language:
$$
\{ a^nb^nc^n|n≥0\}
$$
With the addition of intersections, consider the following "CFG+":
$$
S\rightarrow AB\ \&\ CD
$$
$$
A\rightarrow aAb\ |\ \epsilon
$$
$$
B\rightarrow cB\ |\ \epsilon
$$
$$
C\rightarrow aC\ |\ \epsilon
$$
$$
D\rightarrow bDc\ |\ \epsilon
$$
As AB covers when #a = #b, and CD when #b = #c, this intersection will match the non-context-free language given above.
It is obvious that context-free languages are a strict subset of the languages described by CFG+. However, how does this compare with other languages? Is this equivalent to a context sensitive grammar? An unrestricted grammar? Is there already a language category I should be recognizing this as?


texts:
Can anybody give me some hint on how to do this? I'm not really sure where to start. The problem says:

  We say that an array $A[1...n]$ is $k$-sorted if it can be divided
  into $k$ blocks, each of size $n/k$, such that the elements in each
  block are larger than the elements in earlier blocks, and smaller than the elements in later
  blocks. The elements within each block need not to be sorted. For
  example, the following array is 4-sorted: $$1,2,4,3 | 7, 6, 5 | 10,11, 9, 12 | 15, 13, 16, 14$$

  a) Describe an algorithm that $k$-sorts an arbitrary array in time
  $O(n\log k)$.

  b) Prove that any comparison-based $k$-sorting algorithm requires
  $\Omega(n \log k)$ comparisons in the worst case.

  c) Describe an algorithm that completely sorts an already $k$-sorted
  array in time $O(n \log(n/k))$.

Googling I found this paper with the solution of of a) and b), but I still don't fully understand how to solve this.

For a) my teacher said that we need to find the median and then do something like what quicksort does on finding a good pivot. I was searching over the net and I had the idea to put the $k$ first elements as leafs of a min-heap and then take the min element and with the next element of the array fill each block with $n/k$ elements, but it fails with the input: $8, 7, 6, 5, 4, 3, 2, 1$

Clearly, b) is something like proving that any algorithm based in comparisons takes $O(n\log n)$. Maybe $\log k$ is because we only need to sort each block with $n/k$ elements, that means for each block we need to do $O(n/k \times\log k)$ $k$ times, so we could actually do it in time
 $O(k\times n/k \times \log k) = O(n\log k)$

For c) I'm not really sure, but I can take all the elements of each block and put them as leafs of a min-heap $-$ which gives $O(\log n/k)$ $-$ and then sort them, which I think would take $O(n \log n/k)$.

Thanks in advance.


texts: Determine page number and offsets for address references

texts:
I'm working on learning operating systems and I've come across a strange question that I don't know how to answer.

The question is:

  Assuming a 1-KB page size, what are the page numbers and offsets for
  the following address references (provided as decimal numbers)?

  21205

The notes and slides I have are very confusing and I can't find anything quite like this from my searches. I understand that a 1KB page size means that it's 2^10 but what do I do after that exactly? Most descriptions I see involve splitting that in half and using the first half as your offset and the other half as the page number but then I see others saying not to do this and my notes, as I mentioned, are useless. I'm sure this is extremely easy but I feel like I've been given only 1/3 of the knowledge needed.

Any help would be greatly appreciated!

Addendum

I took a step back for a little while and I think I realized where my confusion was coming from.

I determined that 21,205 is within the range of 2^15, so it's a fifteen bit number. If I subtract the size of the page (10) from the size of the number (15) then that should, in theory, give me a page number of 10 and an offset of 5.

The next bit is pure speculation on my part but I'm assuming that I then take the decimal form of 21,205, which is 101001011010101, and segment it accordingly. The first ten bits (1010010110) equals 662 and the last five bits (10101) equals 21.
So my tentative answer is

Page Number = 662 & Offset = 21.

Is this at all reasonable or do I do it completely wrong?


texts: How to solve for recurrence with substitution or other methods?

texts:
Forgive me if I am new, I am trying to learn how to solve recurrences.

I have the following recurrence:

$$T(n) = 2 T(\lfloor\frac{n}{3}\rfloor) + \frac{1}{2} T(\lfloor\frac{2n}{3}\rfloor) + n^2 \text{ if } n>0$$

Now from my understanding is that I am not able to use the following methods.

Master Thereom (because it's not in the form $aT(\frac{n}{b}) + f(n)$)
Tree Method (because of the $\frac{1}{2} T$, you cannot have a node of $\frac{1}{2}$), please correct me if I am wrong.

So which leaves me with the following method:

Only the substitution method, but what I don't understand that is the fact that for the substitution method, you have to guess for the $f(n)$ to substitute into the recurrence.

So my question is, how does one select the correct $f(n)$ to substitute?


texts:
Suppose we have an undirected graph $G=(V,E)$ with $n$ vertices and with max degree of $d>0$.

I need to prove that number of connected subgraphs of $G$ with at most $n\geq k>0$ vertices is $M\leq n\cdot d^{2k}$

My approach was by induction.

For $k=1$ it is true

Suppose we want to prove it for $k=n$ .

let's take any vertice $v\in V$ and run $DFS(v)$ So we will get at most $ d\cdot d^{k-1} \le d^k$ connected commponents.

And because we can take any $ v \in V$ we get that the number of connected subgraphs of $G$ with at most $ k>0$ vertices is $n\cdot d^{k}< n\cdot d^{2k}$

Now my question is:
Am I right with my approach?
Is there any other solution for this problem?

I really didn't understand why they gave me this upper bound...


texts: Recurrence with a function of n times T()

texts:
The master method works well on problems like $T(n)=kT(an)+cn$, but it does not handle problems like
$$T(n)=n^{\frac{1}{3}}T(n^{\frac{2}{3}})+n^2$$
With the number of branches for each partition is a function of $n$. I wonder if there's a good solution to this kind of problems, I have no idea how to solve this, any help is appreciated!


texts: Is connecting islands with pontoons NP-complete?

texts:
I have a problem in my mind, I think it is a NPC problem but I don't know how to prove it.

Here is the problem:

There are k islands in a very big lake, and there are n  fan-shaped pontoons. Those pontoons are in the same size but have different initial directions and are in different original positions in the lake. The pontoons can rotate freely around its center of mass, and no cost associated with rotation.

Now we need to move those pontoons so that all islands in the lake can be connected. We can guarantee the number of pontoons is enough to connect all the islands.

[Note]: We cannot reuse the pontoons!!

The task is to find the solution having the minimum total distance of the moving pontoons in order to make all islands connected. The distance of moving one pontoon can be calculated as the distance between the center of mass's original position and its deployed position.

To make it clear, I have drawn such a figure. Suppose we have 3 islands A, B and C. They are located somewhere in the lake. And I have several fan-shaped pantoons. Now the solution is to find a minimum moving distance summation to connect A, B and C, shown in bottom part of the figure. Hope it help understand the problem. :)

It seems that the problem is a NPC one, but I don't know to prove it. Can anyone help me on this?


texts: Algorithm for computing $Pr[s \vDash C \bigcup^{\geq n} B]$ for probabilistic verification

texts:
I'm having some difficulty trying to come up with an algorithm for computing $Pr[s \vDash C ~\bigcup^{\geq n} B]$ given a finite Markov chain where $S$ is the set of states, $s \in S$, $B,C \subseteq S$, and $n \in \mathbb{N}$ where $n \geq 1$.

I have algorithms for computing $Pr[s \vDash C~\bigcup~B]$, $Pr[s \vDash C~\bigcup^{\leq n}~B]$, and $Pr[s \vDash C~\bigcup^{=n}~B]$. Instead of going down to the Markov chain itself I was thinking of using a combination of these algorithms to calculate $Pr[s \vDash C ~\bigcup^{\geq n} B]$, however, I'm worried about overcounting as it is not necessarily true that $B$ and $C$ are disjoint.

I am using the Principles of Model Checking book by Baier and Katoen.


texts: What is the actual scope of the Halting Problem impossibility result?

texts:
Consider the Halting problem : No TM H exists which given any TM and input, decides whether that TM will halt on that input. The usual proof (informally) is that if such an H existed, then a function D(X) = {if H(D,X) then loop; else Halt;} can be constructed, with D(D) leading to a contradiction => hence H can’t exist.
However, this proof relies on the fact that H decides Halting for any (TM,Input) pair as input - and so in particular, it can be given (D,D) to decide. But what if we suppose that H decides Halting for everything except D(D). Does the proof fall apart?
It seems that from “H can’t decide D(D)” we jump to the conclusion that “No TM exists that solves the Halting problem for any TM”. While that conclusion is technically valid, maybe there’s a TM that decides Halting for ‘virtually all’ Turing Machines, except a tiny subset - which includes D(D), or possibly D(any input), or even some slightly larger set. The above proof doesn’t preclude that.
Is there a more quantitative statement of the Halting Problem impossibility result - something that gives some measure of how many TMs (or a description/characterization of which ones), out of the set of all possible TMs, no single function can decide whether they halt or not?
To put it another way, maybe it's possible to construct a Halts() function that will be correct on 99.99999…% of its inputs? Or to be more precise, given a Halts() function candidate, we can state something quantitatively, along the lines of : Correctness = $ \lim \limits_{n \to \infty} \sum_{1}^{n} \frac {IsCorrect(Halts(n))}{n}$ (where the sum is over the indices of TMs in some fixed enumeration, and IsCorrect returns 1 if Halts(n) is correct). Now we can ask 1) Are there Halts() functions for which this limit exists? 2) Out of those, which ones maximize this limit?
The import of this is that if there's a Halts() function with a correctness close enough to 1, then the Halting undecidability theorem can be viewed as having little practical value and as being more of a curiosity applicable to a tiny subset of degenerate cases. Even though Rice's theorem shows a wide variety of questions that are undecidable because they can be reduced to the Halting problem, for each of those questions individually, the 'Correctness' limit above might still be close to 1, and so again, we'd be able to find algorithms that decide them for all practical purposes (save a few odd cases).
Note: This question is similar to what's asked in "Attempt #3" of this answer, but it doesn't look like that was ever addressed further (i.e. whether there's any research or literature that investigates such a limit).


texts: Can the most general unifier be defined categorically?

texts:
I remember from my reading of Category Theory for Computing Science that classical concepts like weakest preconditions can be seen as the categorical notion of pullback.

I was wondering if the same is true for the notion of most general unifier.


texts: Would hypercomputation machines be capable of simulating/computing/programming everything?

texts:
If uncomputable numbers existed, could this hypercomputation machines compute them? Could hypercomputation compute all types of uncomputable things? Even truly inconsistent things? Even things that cannot be described by any type of information (like a way of factorizing number 181 using classical mathematics, the mathematics we usually use, without changing nothing (without changing conditions, axioms, definitions...) of it, which it is clearly impossible)?

(I ask this because I was told by an important user in Physics Stack Exchange that this was possible for hypercomputation (if it existed), but later I spoke with other computer scientists and physicists and they told me that in no way this could happen. I can't contact the original scientist that told me that this was possible for hypercomputation, so maybe you can clear my doubts)


texts:
How to find a local minimum of a complete binary tree?

Consider an $n$-node complete binary tree $T$, where $n = 2^d − 1$ for some $d$. Each node $v \in V(T)$ is labeled with a real number $x_v$.  You may assume that the real numbers labeling the nodes are all distinct.  A node $v \in V(T)$ is a local minimum if the label $x_v$ is less than the label $x_w$ for all nodes $w$ that are joined to $v$ by an edge.
You are given each a complete binary tree $T$, but the labeling is only specified in the following implicitly way: for each node $v$, you can determine the value $x_v$ by probing the node $v$. Show how to find a local minimum of $T$ using only $O(\log n)$ probes to the nodes of $T$.

Attribution: this seems to be Problem 6 in Chapter 5 "Divide and Conquer" from the book "Algorithm Design" by Jon Kleinberg and Eva Tardos.


texts: How to calculate number of nodes opened by BFS?

texts:
In the below diagram, each node takes up a space of 2KB. I need to find the total memory consumed to reach the goal : I

I know that the equation for BFS is

b1 + b2 + ...... + (bd+1 - b)

Where b is the branching factor and d the depth

But how do I calculate the branching factor in the below diagram, where the branches are uneven?

Also, is the depth on A node 0 or 1?


texts: proving that $P\ne NP$ under an assumption

texts:
Suppose that $P^{SAT} \not\subseteq coNP$. Prove that $P\ne NP$.

What I did:

Suppose that $P=NP$. Then, $P = coP = NP = coNP$.

We know that $P^P = P$.

Then, by assumption: $P^{NP} = NP = coNP$

Since $SAT$ is $NP$-complete we get: $P^{SAT} = coNP$ in contradiction to the assumption.

So $P\ne NP$.

I've been told that my proof is false, but I don't understand why.


texts: Find all sets of nodes that can be connected with a single path

texts:
**  Edit: I just noticed my current algorithm is incorrect, as it only finds paths starting/ending at the given node. I'm trying to figure out a solution, but I'm a bit stuck.

Say I have an undirected graph. I would like to find all possible combinations of nodes that could be connected with a single path, that include a certain node.

--clarification: That is paths starting and ending at any node. Not just paths starting at the node in question.

Take this graph for example:

A----B
|    |
|    |
D----C

The solution for node A would be:

ABCD; example path A->B->C->D. Alternatively B->A->C->D or many others. As long as we have one, we're good.
ABC; example path C->B->A, etc.
ADC
AB
AD
A; 'path' from itself to itself

I understand this is a -very- hard problem with a lot of results. To make it simpler it is allowed to have some duplicates in the end result, but less would be better(this makes cyclic graphs a bit easier).

My current(naive) solution is as follows:

Start at the node in question
Note current path as possible path.
If no possible connections, return.
For each possible connection, go into recursion via [2].

See the following example. The problem with my algorithm is that a lot of duplicates are generated. Here the bottom two items in the example tree are the same solution.


texts:
Can you have simple unit tests for complicated function?
For example: Turing test for AI.

Do you always can find simple unit tests for any complicated enough function / algorithm?


texts: Good Reference For Design And implementation Of Proof-Assistant

texts:
Hello I'm searching for any good review article or book about the design an implementation of a proof-assistant, something such as the Dragon book for programming language. My background is undergraduate in maths.

Thanks in advance !


texts: If one hypothesis class is a proper subset of another, what is the relation of their VC dimensions?

texts:
Assume two hypotheses classes $H_A\subset H_B$ defined over the same instance space $\delta$. Assume also $VC(H_A)=d$, does this mean $VC(H_B)\geq d$ ? where $VC$ is the VC dimension.

We can use the same set of instances shattered $H_A$ to shatter $H_B$. Seems obvious to me but is it true? is there a reference for this?


texts: Proving a grammar only generates words whose alternating digit sums are multiples of three

texts:
This is homework and I'm looking for a push in the right direction. Proofs were never something I was properly taught, so now they're kind of a weak point.

Here's the problem:

  The following grammar generates numbers in binary notation ($C$ is the
  start symbol):

  $\qquad \begin{align}C &\to C 0 \mid A 1 \mid 0 \\
                       A &\to B 0 \mid C 1 \mid 1 \\
                       B &\to A 0 \mid B 1
          \end{align}$

  Prove that the alternating sums of the digits of the generated
  numbers are multiples of $3$. The alternating sum of $w=w_0\dots w_n$ is defined as $\sum_{i=0}^n (-1)^i \cdot w_i$. As an example, $C$
  generates $1001$ via $C \Rightarrow A1 \Rightarrow B01 \Rightarrow A001 \Rightarrow 1001$ with alternating sum of $0$;
  clearly, $0$ is a multiple of $3$.
  Prove that all such numbers (i.e.,
  numbers whose alternating sum is a multiple of 3) are generated by the
  grammar.

I'm thinking I need to show that the grammar can only generate strings which are made up of repeated subsequences of digits which always add up to 0, 3, or -3. But I'm not sure how to show that it can only generate those three subsequences.

I also have worked out these thoughts:

Consider that any even number of consecutive 1s is irrelevant, as they cancel each other out.
Consider that all zeros are in of themselves irrelevant, as they add nothing.
Consider then that the only relevant pattern is that of alternating 1s and zeros, and where this pattern starts and ends.


texts:
How would about proving this is not regular with the pumping lemma. Please include all steps and explain all steps. I am really new with this.

$1^{2x}0^y$ and $y>= x$

Does it matter which side you pump? How do you pick which side to pump?

This is what I was thinking:

$$u = 1^{2x}$$
   $$v = 0^y$$
   $$w = 1^{2x}0^y$$

Am I on the right track? What else do I need to do?


texts: is co-NP-hard contained in EXPTIME-hard or vice-versa?


texts: How to find all numbers that there distance from given point are less or equall to integer n?

texts:
Given a set of numbers $D$ and some number $k$ I want to find all numbers that are in $D$ such that the distance between $k$ and any found number is less or equal to integer $n$?

Example: suppose we have $D=\{5,9,0,6,7\}$ and $k=8$ and $n=1$ then the result should be $\{9,7\}$.

I was thinking to use a k-d tree or VP tree but both as I understand find nearest neighbors and do not care about $n$ in my example, but please correct me if I am wrong.


texts: Is it still transfer learning if you consider input as well as output? (neural networks)

texts:
I'm new to the CS stack exchange, so a fond hello to you all!

I joined since I have a question I've been curious about. I have recently been running some experiments in transfer learning - specifically I train a network to recognise a certain image, let's say a cat, and then I transfer the input and hidden layers of the network to another dataset and see if the trained weight distribution is a better starting point as opposed to a random distribution through XAVIER etc. etc.

I now wonder, what if the input is different, rather than the output? For example, if I have a dataset of Hotel reviews and build a sentiment analysis type predictor that would predict whether a review is negative or positive, one would have a binary classification problem. If you were then to apply those layers and weights as the starting point to Restaurant reviews, one has changed the input attributes (eg. word stems from a different domain) but the output may still be a binary classification problem for positive and negative classes.

All of the examples of transfer learning I see will change the input and output layers while retaining the hidden layers. If the input changes, but the output does not, is it still Transfer Learning?

Thank you!


texts:
We have n deck of cards. To shuffle i-th deck we need a(i) seconds. Our task is to give a greedy algorithm, which will merge two decks until we have one deck.

My idea is to create a priority queue. At top of the queue we have a minimum value of a(i). And then shuffle Q.top() with the next Q.top() while Q.size() > 1.

Could you help my proving, if it works, or not?


texts: Is a "stacked", "local" version of 3-SAT NP-hard?

texts:
In this previous question, I learned that if each variable in a string $C \in 3\text{-SAT}$ appears only "locally", then finding a satisfying assignment is no longer NP-hard.  My question below builds on this to ask whether NP-hardness is recovered when, loosely speaking, there are multiple "layers" of variables leading up to the formula of interest.  (This elaboration emerges naturally from a study of spatial Bayesian networks.)

Question

Consider a graph with nodes arranged in rows.  The number of nodes doubles in each subsequent row; the graph has one node in the first row, two in the second, four in the third, and so on, for $m$ rows.  (There are $n = 2^m - 1$ nodes total in the graph.)  Each node takes a state of either 0 or 1 and has up to three "parent" nodes in the subsequent row (when there is such a row).  Each parent is "$k$-local":  there are fewer than $k$ nodes between the first and last nodes for which it is a parent.  ($k$ is a fixed natural number that does not change with $n$.)

For each node $v$, there is a table $T_v$ that lists all possible combinations of states of the parents of $v$ and, for each combination, assigns a state of 0 or 1 to $v$ in a fashion consistent with $v$ being a disjunctive clause of literals of its parents.

Let $(3,k)\text{-SATSTACK}$ denote the decision problem of determining whether there is an assignment of states to the nodes of the graph that assigns state 1 to the first node and is consistent with all $T_v$.

Are there $k$ for which $(3,k)\text{-SATSTACK}$ is NP-hard?

Notes

(1)  It appears that $(3,k)\text{-SATSTACK}$ is in NP, since we can choose an assignment for each node in the last row, then work backward through the rows, computing the assignment for the rest of the graph in linear time and accepting it if and only if it assigns state 1 to the first node.

(2)  It also seems plausible that $(3,k)\text{-SATSTACK}$ is NP-hard, at least for $k$ large enough, since it seems difficult to do better than a procedure in which we work forward from the first row, applying the polynomial-time algorithm noted above to each row and keeping inventory of all satisfying assignments out to that row (which may be an exponentially growing collection).

(3)  Nevertheless, it appears challenging to find a polynomial-time reduction showing that $(3,k)\text{-SATSTACK}$ is NP-hard because many of the subsets of $3\text{-SAT}$ (and related problems) that map naturally into $(3,k)\text{-SATSTACK}$ are not NP-complete (see again).  So how should we proceed?


texts: Is the following problem NP-hard? (or have you seen it before?)

texts:
I genuinely don't know if the following problem is NP-hard. I have never seen it mentioned online, but it's hard to even search for exact problems like this. I have been trying to find an efficient algorithm for a while and intuitively it feels very NP-complete to me, but I haven't been able to prove it. A solution would be directly applicable to my work, if it could be found.

Problem: Assume you have $N$ different tasks which each have a unique integer length $l_n$. These tasks are arranged in a dependency tree so that each task can only be started after zero or more other tasks are completed. You also have $M$ different resources. Each task requires a given resource and each resource can only be used by one task at a time. What ordering of tasks allows for the fastest completion of the overall program (based on maximizing the amount of tasks that can be parallelized).
Example: In less abstract terms, imagine that each task is a step in a recipe. The resources are elements of a kitchen like an oven or mixer. If cooking one part of a meal requires a short use of the oven followed by a lot of manual work, and cooking the other part of the meal requires a long oven time, you should schedule the shorter cook first so that you can do the rest of the work for that component while the other half is in the oven.
Another example: Consider the dependency tree below. $a \rightarrow b$ indicates "$a$ depends on $b$". The length of a block indicates the time it takes to complete (1 or 3 in this case). There are two resources/channels: red and blue.

An example solution might look like this:

This shows that a greedy approach (like scheduling (1) and (2) simultaneously) is not sufficient -- you have to look ahead to minimize waiting for resources.


texts: Decidability of languages with dfa/turing-machines

texts:
For any alphabet and any natural number k, a language of strings at least k is decidable.
So my question is having some alphabet (let's say (0,1)) and some number let's say k=5 then my language has every string of 1's and 0's that are 5 or more characters at length (ie 01101, 011011 belong to language, while 011,10,1100 does not). Can such language be decidable and how so?


texts: Lookahead set: Determining minimum $k$ such that $G$ is a strong $LL(k)$ grammar

texts:
How do we determine minimum $k$ such that $G$ is a strong $LL(k)$ Grammar

Like for grammar $G$ with the following rules
$S\rightarrow aAcaa \mid bAbcc,A\rightarrow a \mid ab \mid \epsilon$