texts: Parallel algorithms on a fixed number of processors

texts:
Usual parallel algorithms require a number of processors that grow with the size of the input, usually $O(\log n)$ or $O(n)$.

This is great from a theoric point of view, but strange from a practical point of view, where the number of the processors that we can use is bounded by a constant. A corollary of the Brent Theorem allows us to simulate a parallel machine with less processors, but doesn't gurantee that the algorithm is still optimal.

Is there a branch of parallel algorithms that studies parallel algorithms that run on a number of processors bounded by a constant?

As commented below:

  If the number of processors is bounded by a constant, then any
  sequential algorithm will be asymptotically optimal.

I think that this fact implies that asyntotical optimality is not the best way to measure performances in real world parallel algorithms.

Is there another measure, like speedup or cost (defined as execution time multiplied by the number of processors) that can tell us how faster is an algorithm that runs on a constant number of processors?

A related question is: How to scale down parallel complexity results to constantly many cores?


texts: What is this approximation/error-reduction method called?

texts:
I'm wondering if anyone could help me find my footing in an approach I am taking with a student in my audio programming class for creating more accurate pitch detection algorithms. But the approach is not limited to pitch detection and in fact seems seems similar to Newton's Method, Euler's Method, Horner's Method, and so on. It is a very simple and general idea, and must have some background in numerical methods. I am looking for pointers to the literature.

Here is the idea. We have a function f which takes a signal and returns the fundamental frequency (such algorithms are close cousins to the Discrete Fourier Transform). In order to test its accuracy, I created simple sine wave signals of precise frequencies and tested the algorithm, and graphed the errors over a particular range; basically a perfect f would be the identity function, so we just had to record the deviation from the identity. The errors are basically sinusoidal. So I stored the errors in an array, and use cubic interpolation to create a continuous error function, and built that into the last stage of the algorithm. Of course, there is a problem, because the errors showed the deviation from a perfect f, and the original f is not perfect, so there would be errors in the errors, so to speak. So I iterated the process, correcting successively for errors in the errors, and the algorithm gets better each time. I have not yet figured out whether it will converge to some minimal error. I also have not tested it in musical settings. But it is very promising, and seems like a generally useful technique.

Separate from a programming trick, I would like to understand some of its properties such as convergence and so on. Anyone have any pointer, keywords, etc. for me to pursue this?  I'm guessing it is a standard technique in numerical methods.


texts: Why does the Count-Min Sketch require pairwise independent hash functions?

texts:
The Count-Min Sketch is an awesome data structure for estimating the frequencies of different elements in a data stream.  Intuitively, it works by picking a variety of hash functions, hashing each element with those hash functions, and incrementing the frequencies of various slots in various tables.  To estimate the frequency of an element, the Count-Min sketch applies the hash functions to those elements and takes the minimum value out of all the slots that are hashed to.

The original paper on the Count-Min Sketch mentions that the data structure requires pairwise independent hash functions in order to get the necessary guarantees on its expected performance.  However, looking over the structure, I don't see why pairwise independence is necessary.  Intuitively, I would think that all that would be required would be that the hash function be a universal hash function, since universal hash functions are hash functions with low probabilities of collisions.  The analysis of the collision probabilities in the Count-Min Sketch looks remarkably similar to the analysis of collision probabilities in a chained hash table (which only requires a family of universal hash functions, not pairwise independent hash functions), and I can't spot the difference in the analyses.

Why is it necessary for the hash functions in the Count-Min Sketch to be pairwise independent?

Thanks!


texts: Break an authentication protocol based on a pre-shared symmetric key, with message numbers

texts:
Consider the following protocol, meant to authenticate $A$ (Alice) to $B$ (Bob) and vice versa.

$$ \begin{align*}
 A \to B: &\quad \text{“I'm Alice”}, R_A \\
 B \to A: &\quad E(\langle 1, R_A\rangle, K) \\
 A \to B: &\quad E(\langle 2, R_A+1, P_A\rangle, K) \\
\end{align*} $$

$R$ is a random nonce.
$K$ is a pre-shared symmetric key.
$P$ is some payload.
$E(m, K)$ means $m$ encrypted with $K$.
$\langle m_1, \ldots, m_n\rangle$ means an assemblage of the $m_i$'s that can be decoded unambiguously ($n$ is encoded unambiguously as well).
We assume that the cryptographic algorithms are secure and implemented correctly.

An attacker (Trudy) wants to convince Bob to accept her payload $P_T$ as coming from Alice (in lieu of $P_A$). Can Trudy thus impersonate Alice? How?

This is a follow-up to Break an authentication protocol based on a pre-shared symmetric key.


texts:
I'm currently working on a reduction from $A_{TM}$ to another language, and have been reading through some example proofs. I've come across the situation where, for example, we have $L = \{ \langle M,w \rangle | \text{ ...etc} \}$, where obviously this would normally stand for $M$ being a TM and $w$ being a string. However, later in the proofs, we replace the $w$ (a string) with an "encoding of a turing machine". Sometimes it's even "an encoding of the TM, $M$".

I'm rather lost on this idea. How do we pass an "encoding of a TM" into a parameter for a string? How do we run that on a TM? Maybe I'm misunderstanding the definition of an "encoding of a TM", which I assume to be the TM itself somehow converted into a string format.

Would anyone mind explaining this to me? I'm sure truly understanding this concept would immensely help me in writing further reductions.


texts: Possible results of two programs running on a symmetric multicore system

texts:
This question is from Patterson and Hennessy's Computer Organization and Design.

  Consider the following portions of two different programs running at the same time on four processors in a symmetric multicore processor (SMP). Assume that when this code is run, both $x$ and $y$ are 0.

  Core 1: $x = 2$;

  Core 2: $y = 2$;

  Core 3: $x = x + 1$;

  Core 4: $z = x + y$;

  What are all the possible resulting values of $x$, $y$, and $z$? You will need to examine all possible interleaving of instructions.

The given answer is, for $(x, y, z)$: $(3, 2, 5), (3, 2, 4), (3, 2, 3), (3, 2, 2), (3, 2, 0), (2, 2, 4), (2, 2, 3), (2, 2, 2), (2, 2, 1), (2, 2, 0).$

I understand how $x$ is either 2 or 3 and why $y$ is forced to be 2, but I don't know how $z$ takes those values.


texts: Is the DPLL algorithm complexity in terms of # of clauses or # of variables?

texts: I'm a bit confused how worst case complexity is estimated for the DPLL algorithm. Is it in terms of number of clauses, number of variables, or something else?


texts: Dijkstra to favor solution with smallest number of edges if several paths have same weight

texts:
You can modify any graph $G$ so that Dijkstra's finds the solution with the minimal number of edges thusly:

Multiply every edge weight with a number $a$, then add $1$ to the weight to penalize each additional edge in the solution, i.e.

$w'(u,v)=a*w(u,v)+1$

This does not work for all values of $a$; $a$ needs to be at least $x$ for this to work. If $a$ is not this minimum number, it might not choose the shortest path. How do I find this minimum value $x$?

Ps. This was done recreationally, I'm done with homework long ago.


texts: Why is it true that given a monotonic heuristic function, A* can be seen as Dijkstra's algorithm where no node needs to be processed more than once?

texts:
Maybe I am missing something very easy and obvious.

But, I don't understand why estimate cost of source vertex is subtracted from the overall estimate cost, if heuristic function $h$ is monotonic: $$d′(x,y)=d(x,y)+h(y)−h(x)$$

What I currently know:

A* algorithm can be used as an extension for Dijkstra's algorithm. At each iteration of its main loop, it chooses the vertex with the minimum of estimation cost plus cost of the path to this vertex:

For vertex $u$ and its successor $v$, overall cost is calculated with $$f(u, v) = d(u, v) + h(v)$$ using some heuristic function $h$. Where:

$d(u,v)$ cost of the path from $u$ to $v$
$h(v)$ estimate cost from $v$ to the target vertex $t$

If for any adjacent vertices $u$ and $v$, it is true that $$h(u) <= d(u, v) + h(v)$$ then $h$ is a monotonic. In other words, graph holds triangle inequality property.

It is stated in Wiki page of A* algorithm:

  If the heuristic h satisfies the additional condition $h(x) ≤ d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where d denotes the length of that edge), then h is called monotone, or consistent. In such a case, A* can be implemented more efficiently—roughly speaking, no node needs to be processed more than once (see closed set below)—and A* is equivalent to running Dijkstra's algorithm with the reduced cost $d'(x, y) = d(x, y) + h(y) − h(x)$.

My questions are:

  and A* is equivalent to running Dijkstra's algorithm with the reduced cost $d'(x, y) = d(x, y) + h(y) − h(x)$.

Any proof for this equivalence ?

It is clear for me that $0 <= d(x, y) + h(y) - h(x)$, and it is feasible. But:

Why this formula is chosen as a new distance function ?
Is there any formal proof that it works ?
Why it is not enough to run Dijkstra with $d'(x, y) = d(x, y) + h(y)$ ?
What is the math behind it ?


texts: Probability that a random graph will remain planar after adding an edge

texts:
According to this answer, a random graph on $n$ vertices is a graph which has each of the $n\choose2$ edges independently with probability $1/2$ each. The probability of at most $3n-6$ edges (which is a necessary condition for planarity) is: $$2^{-n(n-1)/2}\sum_{k=0}^{3n-6}{n(n-1)/2\choose k}$$

Therefore, the plot for this equation is:

  If I choose a random graph with 10 vertices, what is the probability
  that it will remain planar after adding an edge between two randomly
  chosen vertices?

To be more clear:

Consider event $P_{1}$, the event of choosing a planar graph $G_{1}$ in the universe $U_{10}$ of graphs with 10 vertices.

Consider a subset $S$ of the universe of graphs with 11 vertices $U_{11}$ conditionally defined by the graph $G_{1}$ we got in event $P_{1}$ in this way: $S$ is formed by all possible graphs that can result from adding one edge to $G_{1}$.

And then finally consider event $P_{2}$, the event of choosing a planar graph in the universe $S$ defined in the previous step.

Therefore I want to know what is the probability of event $P_{2}$.

Possible solution:

I followed D.W.'s advice below and wrote a small simulation. According to the code, the probability of choosing a planar graph of 10 vertices is 0.0915 ( 9,15% ) and the probability of a given planar graph of 10 vertices remaining planar after adding one random edge is 0.6140 ( 61,40% ).

#!/usr/bin/python3
import planarity
from itertools import combinations
import random
from multiprocessing import Process, Manager, Pool, cpu_count
import json

nodes = [str(x) for x in range(10)]
edges = list(combinations(nodes,2))
tests = 10**6
filename = 'results.json'
runs = 100

def make_test():
    while 1:
        chosen_edges = list(filter(lambda x: x != None, [x if random.choice([0,1]) else None for x in edges]))
        if planarity.is_planar(chosen_edges):
            break
    extra_edge = random.choice( list(set(edges) - set(chosen_edges)) )
    chosen_edges += [extra_edge]
    return planarity.is_planar(chosen_edges)

if __name__ == '__main__':

    for i in range(runs):
        with Pool(processes=cpu_count()) as pool:
            results = [ pool.apply_async(make_test, ()) for i in range(tests) ]
            lst = [ res.get(timeout=1) for res in results ]
        pool.close()
        pool.join()

        n = len(lst)
        p = len(list(filter(lambda x: x != False, lst)))
        prob = ( p / n )
        print(prob)

        try:
            with open(filename,'r') as f:
                file_lst = json.load(f)
        except:
            open(filename,'w+').close()
            file_lst = []
        file_lst += [prob]
        with open(filename,'w') as f:
            json.dump(file_lst,f)


texts: Why does this recurrence give O(n) time?

texts:
Given this following recurrence: $$T(n) =  T(n/2) + O(n)$$Find the final time complexity.

My first thought is $O(n\log n)$, since there is at most $\log n$ times the
$O(n)$ will appear.

However, if we adopt the following analysis and let $n=2^m$, then we have:

$$T(2^m) = T(2^{m-1}) + k(2^m) = T(2^{m-2}) + k(2^m + 2^{m-1})...$$

Which we can then condense to have the cost become:

$$2^m + 2^{m-1} .... + 1 = 2^{m+1} - 1$$

And so since the cost is $O(2^m)$, we have our $O(n)$ time as required.

Is the analysis valid? Because I have so very often seen proofs using recurrences of the form $T(n) = T(n/2) + ...$, and they all similarly concluded that there will be $\log n$ times of the relationship.

Which is correct?


texts: Solving Recurrence Relation (quicksort )

texts:
I know quicksort to have a runtime of $\mathcal{O}(n \log_2 n)$

However trying to solve for it I get something different and I am not sure why that is.

Ok, so solving recurrence relations can be done several different ways.

The recurrence relation for quicksort is:

$$T(n) = 2 T(\frac{n}{2}) + \mathcal{O}(n)$$

Reinserting a few times we get:

$$T(n) = 2 \left[ 2 T(\frac{n}{4}) + \mathcal{O}(\frac{n}{2}) \right] + \mathcal{O}(n)$$

$$T(n) = 2 \left[ 2  \left[ 2 T(\frac{n}{8}) + \mathcal{O}(\frac{n}{4}) \right] + \mathcal{O}(\frac{n}{2}) \right] + \mathcal{O}(n)$$

$$...$$

Which can be generalised to:

$$T(n) = 2^kT(\frac{n}{2^k})+\sum_{i=0}^{k-1} \mathcal{O}(\frac{n}{2^i})$$

Now the sum can be solved like this:

$$\sum_{i=0}^{k-1} \mathcal{O}\left(\frac{n}{2^i}\right) = \sum_{i=0}^{k-1} \mathcal{O}\left(n\left(\frac{1}{2}\right)^i\right) = \frac{n -n\left( \frac{1}{2}\right)^{k-1}}{1 - \frac{1}{2}}$$

$$\lim_{k \to \infty} \frac{n -n\left( \frac{1}{2}\right)^{k-1}}{1 - \frac{1}{2}}  = \frac{n}{1 - \frac{1}{2}} = 2n$$

So the recurrence can be simplified accordingly:

$$T(n) = 2^kT(\frac{n}{2^k})+2n$$

Assuming $T(1) = C$ we get $$T(n) = 2^{\log_2 n}T(\frac{n}{2^{\log_2 n}})+2n = n C + 2n$$

And $ n C + 2n \not \in \mathcal{O}(n \log_2 n)$

Can somebody explain my error to me?


texts: Shortening the number of reductions to prove NP-Completeness

texts:
This question is based on the slides from this pdf:

Slide 54, they define the Subset Sum Problem.
Slide 65, they define the Partition problem.
Slide 74, they talk about the Job Scheduling problem.

My question is, is it possible to cut the middle man of the partition problem and reduce Subset Sum to Job Scheduling directly?

To prove scheduling is NP, we can use what is already stated since it's not related to partition.

I'm not sure how to combine the reduction from both onto one though.


texts: Why use comparisons instead of runtime for comparing two algorithms?

texts: I notice that in a few CS research papers, to compare the efficiency of two algorithms, the total number of key comparison in the algorithms is used rather than the real computing times themselves. Why can't we compare which one is better by running both programs and counting the total time needed to run the algorithms?


texts:
I recently asked a related question at the theoretical CS stack exchange, but I have modification to the problem that I think is a bit tougher. This seems like a better place anyways.
Let's define a "task" $T_k$ to be a tuple $(a_k, b_k, C)$, where $a_k$ is the amount of active time spent on a task, $b_k$ the inactive time, and $C$ a set of child tasks that cannot begin until this task is fully complete. For a given task, while I'm actively working on it I cannot do anything else. However, during the inactive period the task continues without my supervision and I can go do some other non-dependent task.
A good example is washing clothes: I might need $a_k = 5$ to load a washing machine, but then while the cycle runs ($b_k = 40$) I can go do something else with those 40 minutes. However, the tasks listed in $C$ cannot start until both the active and inactive parts have completed. So, using my existing example, I cannot run the dry cycle on my clothes until I've both loaded the washing machine and waited for the cycle to end.
So, given a set of tasks $T$ a question you could ask is: "What's the fastest I could complete a set of tasks?". In a way this is a topological sort, but there's also some weighting in there that I'm not sure how to navigate with existing topological sort algorithms. Perhaps there is a greedy way to pick the next node?
My question is this:

Is there an algorithm to solve this problem (that isn't brute-force enumeration of course)
Does this problem fall into an exist realm of research that I could investigate? Are there any introductory articles you could point me to?


texts: How profiling is done in trace scheduling?

texts:
I'm trying to understand how trace scheduling works. The book that I'm reading, Engineering a Compiler by Keith D. Cooper & Linda Torczon, states that this method is using profiling. Profiling ranks each edge if the CFG by its frequency of execution. In other words the more a particular edge is followed the higher rank it has. So basically first the algorithm profiles the CFG and then runs  trace scheduling. The only way (in my view) to do profiling is to run the code so that each edge of the CFG can be ranked. Somehow I don't think this is being done.

Here are my questions:

So how is profiling done?
Does the compiler guess the rank of each edge?
If it does, then what is the foundation for the guess?


texts: How to treat numerical errors in determinants of singular matrices when using LU decomposition

texts:
I want to calculate the determinant of a matrix. Currently I'm using LU decomposition.

To check my algorithm I wrote a unit test with random matrices. In one part I set one row to be equal to another row to test if the resulting determinant would be 0. This is the matrix:

$\begin{pmatrix}
    0  & 0  & 33 & 17 & 42 & 44 & 20 & 28 & 43 \\
    38 & 46 & 11 & 39 & 21 & 24 & 24 & 29 &  4 \\
    52 & 13 & 43 &  3 & 54 & 31 & 32 & 50 & 32 \\
     2 & 10 & 41 & 12 & 10 & 28 & 32 & 14 & 16 \\
    22 & 34 & 44 & 52 &  4 & 36 &  8 & 44 & 44 \\
    20 & 0  & 19 & 11 & 52 & 19 & 54 & 43 & 18 \\
    17 & 20 & 13 & 49 &  9 & 23 & 22 & 21 & 20 \\
    52 & 13 & 43 &  3 & 54 & 31 & 32 & 50 & 32 \\
    11 & 14 & 37 & 43 & 21 & 24 & 49 & 32 &  8
\end{pmatrix}$

As can be seen the third and 8th row are equal.
By reusing code from a Gauß-Jordan inversion I basically can get something alike to an LU-decomposition, i.e. I rewrite $A\vec{b}=I$ to $U\vec{b}=L$, so that $A=L^{-1}U$. The determinant can then be written as a product of the diagonal elements of L. It basically boils down to:

$|A| = 38 \cdot (-49.95) \cdot 33 \cdot (-20.7) \cdot (-58.6) \cdot (-14.61) \cdot 44.61 \cdot \left(-4.8 \cdot 10^{-15}\right) \cdot (-11.33) = 0.0027$

when using double precision. I expected a relative error of roughly DBL_EPSILON * 9, that's why my unit test failed. For single precision floating point I would get approx. 10000 instead of 0!

So the problem being here is that the error rises not additively, but multiplicatively for values near zero, so that even though the each diagonal element has roughly 10*DBL_EPSILON (-4.8e-15 instead of 0) relative error, the error on the calculated determinant becomes 1e12*DBL_EPSILON.

How can this be treated? Are there more stable algorithms for which I can get better precision on $|A|$, or should I just hard-code manually check whether one of the factors is near 0? Is such a check safe, or would it dirty other cases?


texts: Can simple recurrent neural networks be remedied with higher precision floating point numbers?

texts: I am of the understanding that tradition "simple" recurrent neural networks have the problem of "losing error" after a lot of time steps. But is this some kind of deficiency of the math, or the machines the RNN's are running on? If it's just the machines, couldn't you use something like an arbitrary precision float and store all the information "exactly"? (Then, even if you go out some ludicrous amount of time steps, you would presumably be able to calculate the gradient.)


texts:
Let $M$ be a square matrix with entries that are $0$ or $1$ and let $v$ be a vector with values that are also $0$ or $1$.  If we are given $M$ and $y = Mv$, we can computer $v$ if $M$ is non-singular.

Now let us take the second bit (from the right) of the binary representation of each $y_i$ as another vector $z$. So $z$ also has entries which are $0$ or $1$. If $y_i$ has fewer than two bits we just let $z_i=0$.

  If we are given $z$ and $M$, how (and when) can you find a $v$ so that
  $Mv$ would produce $z$ under this operation?

Here is an example

$$M = \begin{pmatrix}
  0 & 0 & 1 & 0\\
  1 & 1 & 0 & 1\\
  1 & 1 & 1 & 0\\
  0 & 1 & 1 & 1\\
\end{pmatrix}
, v = \begin{pmatrix}
  0 \\
  1 \\
  1 \\
   1\\
\end{pmatrix}
\implies Mv=\begin{pmatrix}
  1 \\
  2 \\
  2 \\
  3\\
\end{pmatrix}
.$$

So in this case

$$z =
\begin{pmatrix}
0 \\
1 \\
1 \\
1 \\
\end{pmatrix}.
$$

Is this problem in fact NP-hard?


texts: If L is a regular language, how to prove that L' is also regular?

texts:
I've been trying to construct a proof of the following statement the whole day but I got stuck:

If $L$ is a regular language, the language $L_{}{'}$ consisting of all words in $L$ containing the letter $\sigma$ (where $\sigma$ is an arbitrary fixed letter in $\Sigma$) is also regular.

I know that the first thing to do is to construct an NFA that recognizes $L_{}{'}$ from the NFA that recognizes $L$, but I can't find a conversion that is general enough. It might me silly, but I think one just have to change the transition function. I hope you guys can give me some advice.


texts: Maximum weighted antichain over a DAG with cardinality constraint

texts:
Let $G=(V,E)$ be a vertex weighted DAG (Directed Acyclic Graph), with positive real valued weights.

Let also $k\leq \left\vert V\right\vert$, is there any way to find a maximum weighted antichain over $G$ (a set of vertexes $A\subseteq V$ where there is no edges between elements of $A$) , with cardinality less or equal than $k$?

The unconstrained problem (i.e. where the size of the anti-chain is not bounded) can be solved by reducing it to a minumum flow problem (as can be seen in this Technical Report by Cong).

Is this problem NP-hard?


texts: How to evaluate the accuracy of a method for the extraction of the principal lines of the palmprint

texts:
Let's assume that I've implemented a method for the extraction of the principal lines of the palmprint. For instance, let's say that I'm able to do a transformation like the following one (image from Patprapa Tunkpien, Sasipa Panduwadeethorn and Suphakant Phimoltares):

Now, I want to make an evaluation of the accuracy level of my algorithm. In order to do this, I have only the algorithm, and a big set of palmprint images (on which I can execute the extraction procedure to obtain the corresponding set of binary images of principal lines of the palmprint).

How can I evaluate the accuracy level of my algorithm, without having any kind of reference extraction method?


texts: Expected number of iterations for bozo sort opt algorithm

texts:
I'm trying to figure out the upper bound for the number of iterations of the bozo sort opt algorithm, described in this paper on section 3.2:
http://www.hermann-gruber.com/pdf/fun07-final.html

I know the maximum number of inversions in this case is nC2, what i'm struguling with is the probability of two numbers in an iteration being an inversion.

Here is the relevant piece of the paper I'm focusing on, I know the answer to the number of iterations is there, I just can't seem to get to it.

  3.2 Comments on optimized variants of bogo-sort

  Though optimizing the running time seems somewhat out of place in the field of pessimal algorithm design, it can be quite revealing for beginners in both fields of optimal and pessimal algorithm design to see how a single optimization step can yield a dramatic speed-up. The very first obvious optimization step in all aforementioned algorithms is to swap two elements only if this makes sense. That is, before swapping a pair, we check if it is an inversion: A pair of positions $(i, j)$ in the array $a[1, \dots, n]$ is an inversion if $i < j$ and $a[i] > a[j]$. This leads to optimized variants of bogo-sort and its variations, which we refer to as bogo-sort$_{opt}$, bozo-sort$_{opt}$, and bozo-sort$^+_{opt}$, resp. As there can be at most $\binom{n}{2}$ inversions, this number gives an immediate upper bound on the number of swaps for these variants—compare, e.g., to $\mathcal \Omega(n*n!)$ swaps carried out by bogo-sort. It is not much harder to give a similar upper bound on the expected number of iterations. As the number of comparisons during a single iteration is in $\mathcal O(n)$, we also obtain an upper bound on the expected total number of comparisons:

  Lemma 14. The expected number of iterations (resp. comparisons) carried out by the algorithms bogo-sort$_{opt}$, bozo-sort$_{opt}$, and bozo-sort$^+_{opt}$ on a worst-case input $\overline x$ of length $n$ is at most $\mathcal O(n^2\log n)$ (resp. $\mathcal O(n^3\log n)$).


texts: Is there a recommended process for designing CSGs (other than intuition)?

texts:
I understand the differences between Regular, Context-Free, and Context-Sensitive languages. Designing a Regular Grammar can be easier if you have a DFA. Designing a CFG isn't too hard for the palindromic strings, but not easy per say for other combinations. But when asked to produce a CSG for Context-Sensitive language (not regular, not context-free), with restrictions on the terminals with respect to other terminals, it becomes difficult. I'm having trouble coming up with the production rules.

Is there some recommended process or method that people use to come up with the rules? Or do they just keep trying out example strings to "capture the essence" of them?

I would post an example, but this is for an assignment, so I can't give it away. In general I would just like to be better at coming up with the grammars.


texts: Is finding the smallest collection of subsets so that the number of elements among the subsets is <= the number of subsets NP-hard?

texts: Given a collection of non-empty subsets of $\{1,2,\ldots,N\}$ ($N$ not fixed), the problem is to find the smallest non-empty collection of subsets so that the number of distinct elements appearing among the union of subsets is less than or equal to the number of subsets chosen. This seems like an NP-hard problem but I can't prove it. Any help?


texts: how to find upper bound and lower bound of quadratic equation

texts:
I am relatively new to algorithms, I wrote one pattern matching algorithm and its running time is $O(n^2)$, I tried it by step count method, direct method and also the constant method which all yields same results. Anyhow now I am writing the upper and lower bound for that, the equation which I get is

$$20n^2+11n+1$$
I need to find the

$$c_1n^2 \leq 20n^2+11n+1 \leq c_2n^2$$

Here I am stuck and needs some assistance, I have gone through a lot of examples, books, and youtube videos, but no one has any method to solve it instead of assumption and different ways. Any help is much appreciated.

EDIT
Graph for the equation


texts: Efficiently enumerate all subsets of an ordered set

texts:
What's the most efficient way to enumerate all (ordered) subsets of an ordered set? So, for example, given the ordered set $\{2, 5, 6\}$ (using the normal ordering for integers), I need the following:
$$\{\}, \{2\}, \{5\}, \{6\}, \{2, 5\}, \{2, 6\}, \{5, 6\}, \{2, 5, 6\}.$$
Smaller subsets should come first, but the ordering of the subsets of equal size is not important.

I'm looking for an algorithm that is efficient both in theory and in implementation (in a general purpose programming language) for very large sets.


texts: A BST can be broken by accessing one of its nodes, how can I always make sure this happens?

texts:
I have an assignment that asks for this. So I am not looking for the answer itself but a hint on how to find a value that will always break the BST condition by myself.

If I have access to any node N of a BST that has at least 2 nodes in its root, and where every node will always be different.

If I were to replace N.key with x, what should the value of x be in order for the tree not to be a BST anymore?

I can use the following operations:
GetPre = key before N when seen from an inorder transverse.

GetSuc = key after N when seen from an inorder transverse.

MAX = gets the node value from the sub-tree that has N as root.

MIN = gets node value from the sub-tree that has N as root.

I broke it in several subcases, but I am sure this can be written as one single formula.

I came up with:

$x = N.key - GetPre(N)$ but it doesn't work as I expected.

I appreciate any insight.


texts: Is there any variant of the Boolean SAT or Max-SAT problem that has a flavor of maximizing or minimizing the average of the weights of the satisfied clauses of a WCNF formula? Any literature on an optimization problem of similar flavor would be appreciated. Thanks.


texts: Examples of problems for each class in $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$

texts:
Given that $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$ and that it is commonly believed that all these inclusions are strict can you provide examples of problems that are believed to be in each class and not in the preceding ones?

To try to narrow the scope of the question, could you provide paradigmatic examples of problems that are believed to be in each class and why they are so?


texts: Calculating miss rate for 2 way set associative cache

texts:
From my homework:

  Consider a 2-way set-associative cache with eight 32-byte blocks. Instructions and operands are 32-bits. There are an 8- bit data bus and a 16-bit address bus. A sample code is run a program that is saved from 1000H to 10FFH address and repeated 20 times. Suppose the cache memory is empty before running this code. Show the addressing architecture of this cache memory and also calculate the miss rate of the cache memory for sample code.

I believe that I have the first part correct.

Offset = 5 bits

Index = 2 bits

Tag = 9 bits

Is the offset correct? I am not sure if it supposed to be 5 or 3. Does the instruction and operand being 32 bits mean that data is pulled from cache 4 bytes at a time?

The sample code portion is confusing to me. From a discussion with the teacher:

  Sample code refers to the program stored at 0x1000-0x10FF as described in the problem(i.e  the memory blocks the cache will have to pull for the cpu)

How do I calculate the miss rate from this?


texts: What complexity class would this version of generalized chess fall?

texts:
By now I understand that generalized chess is harder than NP, and is EXPTIME-complete for the decision problem "Given an nxn board with a given position, can white force a win?" because the proof would require an exponential amount of steps to show that each branch of the tree eventually leads to a win. Therefore it's not in NP.

But if you were to ask the decision problem "Given an nxn board with a given position, can white win?" and apply it to generalized chess, would this variation be in NP? Because the verifiability of this proof would only require polynomial time (just play out the winning game). For this decision problem, would it fall in NP, because a problem solvable by a DTM in EXPTIME and verifiable in polynomial time would be NP-complete, yes?


texts: Is there an always-halting, limited model of computation accepting $R$ but not $RE$?

texts:
So, I know that the halting problem is undecidable for Turing machines. The trick is that TMs can decide recursive languages, and can accept Recursively Enumerable (RE) languages.

I'm wondering, is there a more limited model of computation which accepts only recursive languages, and not RE? And if so, is there such a model which is always guaranteed to halt?

Obviously this model would be strictly less powerful than TMs and strictly more powerful than PDAs.

I'm open to a machine-style model, or a lambda-calculus style model.

As an example of what I'm thinking: the Coq language has a restriction that for any self-recursive calls, the first argument must be strictly decreasing in "size" i.e. if it is a natural number, it must be smaller, if it is a list, it must be shorter, etc. This guarantees that it always halts, but I have no idea if you can compute all of R this way.


texts: Composition of handler types in algebraic effects and handlers

texts:
In the paper "An introduction to algebraic effects and handlers" (Pretnar, Matija. Electronic Notes in Theoretical Computer Science 319 (2015): 19-35), handlers get a handler type that looks like a function type:
$\underline{C} \Rightarrow \underline{D}$.
These can be "applied" with the with h handle c syntax.

What I've noticed is that the only way to get a handler type is with the handler syntax, which means there's no way to get composition of handler types:
given $\underline{A} \Rightarrow \underline{B}$ and $\underline{B} \Rightarrow \underline{C}$ there is no way to get $\underline{A} \Rightarrow \underline{C}$.

I believe this is because there is no abstraction for computations like there is an abstraction for values ($\lambda x . c$). Is this left out because of simplicity of is there a problem with such abstractions which means you can never have composition of handler types in a consistent system?


texts: What is the Haskell-style type signature called (i.e., who is it named after)?

texts:
A type signature in Haskell is written in the following format:

functionName :: arg1Type -> arg2Type -> returnType

There's a (hyphenated, after a person or persons) name for this style of type signature (which predates Haskell), but it's escaping me and I can't find it anywhere.


texts:
I have been looking for a while but I cannot find an algorithm for a particular generalisation of sequence alignment.
I have two posets $(A, <)$ and $(B, <)$ and a similarity score $s(a, b)$ for all $a \in A, b \in B$. I wish to find a maximal scoring alignment such that both partial orders are respected.
An alignment is a poset $(AB, <)$ of $(a, b)$ pairs such that any $a \in A$ or $b \in B$ should be in at most one pair in $AB$. We say $AB$ respects the orders of $A$ and $B$ if for all $(a, b), (a', b') \in AB$ then $(a, b) < (a', b')$ if and only if $a < a'$ and $b < b'$.
The score of the alignment is just the sum of the scores of the pairs.
$$
s(AB) = \sum_{(a,b) \in AB} s(a, b)
$$
In standard sequence alignment, both sequences are totally ordered (by their linear representation), in my case I only have a partial order. If it helps, this partial order is defined by each element's location in a planar graph.
I did find this paper that discusses these issues but I don't think it supplies an algorithm. It does suggest such an algorithm is possible.
This also seems related to the problem of bipartite graph matching (c.f. Hungarian algorithm) but those algorithms do not consider order respecting constraints.
The Euclidean bipartite matching problem also seems related but whilst my nodes $a, b$ live in Euclidean space, their similarity scores $s(a, b)$ are not a (simple) function of their location.


texts: Practical Application of Kadane algorithm

texts:
Kadane Algorithm is used to solve the maximum subarray problem which in simpler terms is to find the highest possible value of a continuous sub array in an array.

One often cited application of Kadane Algorithm is that given the prices of the stock over X days , on which days should we buy and sell the stock in order to maximize given profit. These example is not practical at all as it is impossible to predict future prices of stocks and hence impossible to apply it .

What are some real world application of Kadane algorithm?


texts: How to check whether a lattice polytope embeds into another lattice polytope?

texts:
Suppose I have two polytopes $P\subset \mathbb R^m$ and $Q\subset \mathbb R^n$ with vertices with integral coordinates.

How do I check whether $P$ is embeddable into $Q$?

More precisely, "embeddable" means that there should be an affine transformation $T(x)= Ax+b$, where $A$ and $b$ have integer entries, so that $T(P)\subseteq Q$ and $T(P)$ has dimension $\dim T(P)=\dim(P)$.
Are there known algorithms that can be applied to this problem?

To clarify,  I'm just looking for an algorithm that will terminate for "small" data; in my application $P$ and $Q$ have about $7$ vertices and $m=5$, $n=7$.


texts: Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?

texts:
We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^* $ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ satisfying $|x|\ge n \implies |f(x)|\lt |x|$.

Assuming $P\ne NP$

  Prove\Disprove: Every two NP-complete languages $L_1,L_2$ are decreasing reducible.

I'd appreciate a hint or direction


texts:
I am very new to PROLOG so it might be a very trivial question, but I absolutely have no idea how to solve it. There are 4 sentences I need to formulate into PROLOG code:

  All hounds howl at night.
  Anyone who has any cats will not have any mice.
  Light sleepers do not have anything which howls at night.
  John has either a cat or a hound.

I convert sentences to well-formed formula in first-order predicate calculus like that

- ∀x (HOUND(x) → HOWL(x))

- ∀x ∀y (HAVE(x,y) ∧ CAT (y) → ¬∃z (HAVE(x,z) ∧ MOUSE (z)))

- ∀x (Light_Sleeper(x) → ¬∃y (HAVE (x,y) ∧ HOWL(y)))

- ∃x (HAVE (John,x) ∧ (CAT(x) ∨ HOUND(x)))

Now I don't know how to write them in Prolog.
Also, how can I make query on them?


texts: How hard would it be to state P vs. NP in a proof assistant?

texts:
GJ Woeginger lists 116 invalid proofs of P vs. NP problem. Scott Aaronson published "Eight Signs A Claimed P≠NP Proof Is Wrong" to reduce hype each time someone attempts to settle P vs. NP. Some researchers even refuse to proof-read papers settling the "P versus NP" question.
I have 3 related questions:

Why are people not using proof assistants that could verify whether a proof of P vs. NP is correct?
How hard or how much effort would it be to state P vs. NP in a proof assistant in the first place?
Is there currently any software that would be at least in principle capable of verifying a P vs. NP proof?


texts:
The dominance law states that x + 1 = 1

If we go by that logic, does that mean that x' + 1 = 1?

Please just tell me if it's a yes(as I think that this is the answer but I just want to clear my doubts) and maybe provide a little explanation if it's a no.

Thanks!


texts: Can someone explain the logic diagram for the Boolean expression NOT A OR B AND C

texts:
An IB question requests:
Construct the logic diagram for the Boolean expression NOT A OR B AND C.

The answer

looks to me like not A or (B and C), whereas what I expected only gets partial credit. Can someone explain?


texts: Applying a multi qubit quantum gate to specific qubits

texts:
A controlled not gate matrix looks like this:

$$\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{bmatrix}$$

That works great when you only have two qubits and you want to use the first qubit as the control, and the second qubit as the input to be flipped (or not).

Is there a method to convert this matrix to use for instance if you had 3 qubits, and wanted to use qubit 1 as the control and qubit 3 as the input that is possibly flipped?

Thinking about it logically, I can come up with this:

$$\begin{bmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
\end{bmatrix}$$

Is there a better, more formal/generalized way to convert multi qubit gates to use any specified qubits, rather than the first $N$ in an $N$ qubit circuit?


texts: Multiplication of polynomials in value representation as done for Fast Fourier Transform

texts:
I am trying to understand the discrete Fast Fourier Transform. I get the idea of switching between coefficient and value representations to and then back but I am stuck in figuring out how the  multiplication of 2 polynomials using their value representation works.
The screenshot below is from a Reducible video (at time 6:39) that explains the Fast Fourier transform. I see that we need 5 points to get $C(x)$, which is of degree $4$, but I don't see how multiplying say the first point of $A(x)$ and $B(x)$, that is, $(-2,1) \times (-2,9)$ gives $(-2,9)$
There's a similar answer here but the steps aren't provided just the final answer, which still baffles me.


texts:
Suppose we have a set of binary trees with their inorder and preorder traversals given, and where no tree is a subtree of another tree in the given set. Now another binary tree $Q$ is given. Find whether it can be formed by joining the binary trees from the given set. (While joining, each tree in the set should be considered atmost once.) Joining operation means: Pick the root of any tree in the set and hook it to any vertex of another tree such that the resulting tree is also a binary tree.

Can we do this using LCA (least common ancestor) or does it needs any special data structure to solve?


texts:
Given that I have a simplified Bison BNF grammar:

%token T_EXP '^'
%token T_NOT '!'

%right T_NOT
%right T_EXP
%right T_FAC
%nonassoc T_LPAREN T_RPAREN T_NUMBER

%type expr

%%

expr:
  T_NOT expr # logical not, e.g. !a
| expr T_EXP expr # exponent, e.g. 2 ^ 3
| expr T_NOT %prec T_FAC # factorial, e.g 3!
| T_LPAREN expr T_RPAREN { $$ = $2; }
| T_NUMBER
;

%%

Given a classical example, 2 ^ 3!, it is natural to human that 3! should be produced first, then the exponent and the answer is 2 ^ 3! -> 2 ^ (3!) -> 2 ^ 6 -> 64. It makes sense to assert that factorial goes before the exponent operator, so its binding power must be higher than that of the exponent.

However, in reality, the parser didn't produce a correct result. I modified the grammar production so that it shows as an AST:

calc eval > 2 ^ 3!
unary !!
  binary ^
    number 2
    number 3
        [expr: 40320]

This expression was evaluated as (2 ^ 3)! -> 8! -> 40320. And no matter how I move the precedences, it always produces the wrong result. If I wrap the factorial with parentheses, i.e. 2 ^ (3!), the result is correct. What's happening in here? Shouldn't 3! be evaluated first?

At first glance, I thought this could be an ambiguity error.

2 ^ 3!    # Input
. 2 ^ 3!  # Lookahead is T_NUMBER(2), shift
2 . ^ 3!  # Lookahead is T_EXP(^), shift
2 ^ . 3!  # Lookahead is T_NUMBER(3), reduce as `expr -> expr T_EXP expr`?
          # But wait! There's a T_NOT behind it

Diverge 1:

2 ^ . 3!  # Lookahead is T_NUMBER(3), reduce as `expr -> expr T_EXP expr`
expr . !  # Lookahead is T_NOT(!), reduce as `expr -> expr T_NOT`?
expr ! .  # EOF reached, final stack: expr -> expr T_NOT -> (expr T_EXP expr) T_NOT // Incorrect

Diverge 2:

2 ^ . 3!   # Potential lookahead found T_NOT(!), shift
2 ^ 3 . !  # Lookahead is T_NOT(!), reduce as `expr -> expr T_NOT`
2 ^ expr . # EOF reached, final stack: expr -> expr T_EXP expr -> expr T_EXP (expr T_NOT) // Correct

But I considered this as a pure insanity and absurdity that comes out of nowhere in my mind, still ! should be shifted before the number gets reduced because the binding power of T_FAC is higher than that of T_EXP and T_NUMBER, so diverge 2 should have had happened, am I right?


texts: Running Time of Oral Messages Algorithm OM(m) for Byzantine Generals Fault Tolerance

texts:
Let us consider a byzantine generals problem assuming:

less than 1/3 of generals are traitors
Oral messages
No Crypto

One solution is the Oral Message algorithm  OM(m), m being the maximum number of traitors we tolerate.

For n Generals and m = 0, the number of messages sent is in O(n)
For n Genrals and m = 1, we have O(n^2) total messages sent in OM(m) solution
My reading indicates that for m = 2, we have O(n ^3) and for m = 3 O(n^4). Can someone explain to me how we have O(n^3) and O(n^4) for m = 2 and 3 respectively ?
Thanks in advance !


texts: Size of decision tree and depth of decision tree

texts:
I'm doing some classification experiments with decision trees ( specifically rpart package in R). By setting the depth of a decision tree to 10 I expect to get a small tree but it is in fact quite large and its size is 7650. So what is exactly the definition of size (and depth) in decision trees?

PS: my dataset is quite large.


texts:
I'm stuck on writing an algorithm for getting the amount of distinct partitions for a number $n$ with the partition being size $k$. It's important that there isn't any repetition in the partitions.
For example:

The partitions of size 2 for number 5 are:

[4, 1]
[3, 2]

The partitions of size 3 for number 6 exists only of:

[3, 2, 1]

Notice that [2, 2, 2] isn't a partition because it has a repeating use of 2.

I currently have implemented a dynamic algorithm that finds the amount of partitions that allow repetition. Here $m$ is is the number and $n$ is the size of the partitions.

def count_partitions(m, n):

    def e_at(i,j):
        if i == j and j == -1:
            return 1
        if i < j:
            return 0
        else:
            return p[i][j]

    p = [[-1 for _ in range(n)] for _ in range(m)]
    for i in range(m):
        p[i][0] = 1

    for i in range(m):
        for j in range(1, min(i + 1, n)):
            if i < 2*j:
                p[i][j] = e_at(i-1,j-1)
            else:
                p[i][j] = e_at(i-1, j-1) + e_at(i-j-1,j)

    return p[m-1][n-1]

I've also got a program to generate all the different distinct k-partitions of a number $n$

def generate_partitions(n, k):
    if n == 0:
        return []

    def rec_partition(m, b, n, a, l):
        if m == 0:
            l.append(conj_partition(a[:n]))
        else:
            c = a[n]
            for i in range(1, min(b,m) + 1):
                a[n] = i
                rec_partition(m-i, i, n+1, a, l)
            a[n] = c

    def has_double(l):
        for i in range(len(l) - 1):
            if l[i] == l[i+1]:
                return True
        return False

    l = []
    a = [0] * n

    a[0] = k
    rec_partition(n - k, k,1, a, l)

    return sorted([p for p in l if not has_double(p)], reverse=True)

So far the only way I found to get the number of distinct k-partitions is to generate them all and take the length of the returned list.

However I feel like there would be a better way to get the amount without generating them all by modifying the dynamic programming algorithm above. But I haven't had any luck with that.

Anyone has any idea that would help?


texts: Confusing method of proving PSPACE-completness

texts:
I don't understand a way of proving PSPACE-completness. The way was used by my lecturer. I can use reduction, however following method confuse me:

We consider sequence (of polynomial length) of configurations and check if transitions betweens configurations in sequence are legal. We also check if machine accept word $w$. In other words, we analyze run of polynomial-space machine $M$ on word $w$ and check if this run is legal and accepting.

I can't understand why such reasoning work. I don't show exact example because my lecturer use this technique fairly often.

Can you explain me why it work?


texts:
I need to find intersection of N line segments (given by coordinates of start and end points) which are either vertical or horizontal.So I read that Sweep Line Algorithm is a good way to solve this.

But I can't seem to find it's implementation in C++ anywhere on Internet. Can someone provide me it's code in C++ ?


texts: How to prove that "Total" is not recursive (decidable)

texts:
$\mathrm{Halt} = \{ (f,x) | f(x)\downarrow \}$ is r.e. (semi-decidable) but undecidable.

$\mathrm{Total} = \{ f | \forall x f(x)\downarrow \}$ is not r.e. (not even semi-decidable).

I need some help in proving that $\mathrm{Total}$ is not recursive (decidable).

I know the diagonalization proof for the halting problem, I just need the same kind of proof for $\mathrm{Total}$. I'm posting the proof for the halting problem for reference:

Undecidability of the halting problem

Assume we can decide the halting problem. Then there exists some total function $\mathrm{Halt}$ such
that
$$
\mathrm{Halt}(x,y) = \begin{cases} 1 & \text{if $\phi_x(y)$ is defined}, \\ 0 & \text{if $\phi_x(y)$ is not defined}.\end{cases}
$$

Here, we have numbered all programs and $\phi_x$ refers to the $x$'th program in this ordering. We can view $\mathrm{Halt}$ as a mapping from $\mathbb{N}$ into $\mathbb{N}$ by treating its input as a single number representing the pairing of two numbers via the one-one onto function
$$ \mathrm{pair}(x,y) = \langle x,y \rangle = 2^x (2y + 1) – 1 , $$
with inverses
$$
\begin{align*}
 \langle z \rangle_1 &= \exp(z+1,1), \\
 \langle z \rangle_2 &= ((( z + 1 ) // 2^{\langle z \rangle_1}) – 1 ) // 2
\end{align*}
$$
Now if $\mathrm{Halt}$ exists, then so does $\mathrm{Disagree}$, where
$$
\mathrm{Disagree}(x) = \begin{cases} 0 & \text{if $\mathrm{Halt}(x,x)=0$, i.e., if $\phi_x(x)$ is not defined}, \\ \operatorname*{\mu}_y (y=y+1) & \text{if $\mathrm{Halt}(x,x)=1$, i.e., if $\phi_x(x)$ is defined}. \end{cases}
$$

Since $\mathrm{Disagree}$ is a program from $\mathbb{N}$ into $\mathbb{N}$, $\mathrm{Disagree}$ can be reasoned about by $\mathrm{Halt}$. Let $d$
be such that $\mathrm{Disagree} = \phi_d$, then

$$\mathrm{Disagree}(d)\text{ is defined} \Leftrightarrow \mathrm{Halt}(d,d) = 0 \Leftrightarrow Φ_d(d)\text{ is undefined} ⇔ \mathrm{Disagree}(d)\text{ is undefined}.$$

But this means that $\mathrm{Disagree}$ contradicts its own existence. Since every step we took was constructive, except for the original assumption, we must presume that the original assumption was in error. Thus, the halting problem is not decidable.


texts: Why are finite automata defined as ordered $n-tuples$ and not as sets?

texts:
First off, I should mention that I am a new contributor on this site and as such, please bear with me if this has been asked and answered before. I searched to the best of my ability to find similar questions and didn't find any.

The Question

Consider the definition of a deterministic finite automaton given below:

  A deterministic finite automaton $M$ is an ordered $5$-tuple $
 (Q,\Sigma, \delta, q_0, F)$ where:

  $Q$ is the set of input states;
  $\Sigma$ is a finite set of input symbols;
  $\delta\colon Q \times \Sigma \to Q$ is the transition function;
  $q_0$ is the initial state
  $F$ is the set of final states

My main question is, would it be inaccurate to define $M$ as the set $ \{Q,\Sigma, \delta, q_0, F\}$ of five elements?
I arrived at this question when wondering if a DFA must necessarily be ordered since n-tuples are, by definition, ordered. In other words, the tuple $(Q,\Sigma, \delta, q_0, F)$ is, by definition, different from $(Q,\Sigma, \delta, F,q_0)$. But what if we define its elements the same way as given in the definition above? Will it be a DFA? If it will, then can a DFA be instead defined as a set?


texts: How can I generate first n elements of the sequence 3^i * 5^j * 7^k?

texts:
How can I efficiently generate the first N elements of the sequence $3^i 5^j 7^k$, where $i,j,k \in \mathbb{N}$?

I've googled around a bit and found the sequence in OEIS, but I don't really see a simple way of generating it.


texts:
I have a set of points corresponding to pictures on map. Because location precision is not very important, I want to separate the points inside the set to maximize the summed up distance between the points. There would be a maximum distance that points could be moved.

Any idea what kind of algorithm should I use?


texts: Can a Turing Machine compute the binary representation of $n!$ in $O(n!)$ time?

texts: We can compute the binary representation of $n$ and similarly by decrementing the value of $n$ by $1$ each time we can get all values from $2$ to $n$. We can now use a Turing Machine that multiplies binary numbers to get the value of $n$. But will this computation be bounded by $O(n)$? That is, can $n!$ be a time constructible function?


texts:
So, the task is to prove the following:

  If S is a schedule containing at most one write action, then S is conflict-serializable.

The answer is yes, but I disagree, because the following schedule contains at most one write action, and is not conflict-serializable:

  R1(A), R2(A), W2(A), R1(A).

Am I completely wrong? Or is the answer wrong?


texts: How to get Loop invariants to prove program is correct in Hoare logic

texts:
start off stating the definition of a loop invariant. It is a condition that must be true at the start of the loop and must be true after each iteration of the loop. I understand what it is but i have trouble trying to come up with one.

Here below is a program which i know is correct and I have stated the loop invariant. Could someone please go through explaining simply why this is the loop invariant. I've been looking at it for awhile now but cannot see why the loop invariant is what it is. I am very new to Hoare logic.

{N >=0}//Pre condition

x = 1;

i = 0;

{x == A^i}//Invariant

while (i != N)

{x == A^i || i != N}//Invariant and Guard

x = x * A;

i = i + 1;

{x == A^i} //invariant

{x == A^i    ||    i==N}// Invariant and !Guard

{x == A^N}//Post condition


texts: What is the formal definition of an algorithm?

texts:
I'm trying to find a formal definition of an algorithm but I only found this. I don't know if it is the accepted one, or even the only one, and I would like some literature on the formal definition(s?). Any help would be appreciated. Thanks.

EDIT:

I'm asking about the formal mathematical definition, not the definition of a sequence of reproducible steps that given some input, produces some output.


texts: Partial Sum operation & solution - Optimizing to O(logn)

texts:
I approached this problem where I have to write an add(key, value), insert(key, value), delete(key,value) and partial_sum(value) which reports the sum of all the elements in the structure that are larger than 'value'.

This was my attempt at the solution, which works! But sadly it runs at O(nlogn) instead of O(logn).. Is there a way I could optimize this?

My approach - binary tree and in each node of it store the sub tree sum for the left sub tree

Add: while descending the tree to the left, update the sub tree sum by adding the value

Insert: like add, but also adds a new node (the O(nlogn) comes from using any balanced
tree type). And to worry about the sub tree sums I can use an AVL tree, since balancing
operations are 3 rotations and the left sub tree sum values can be mantained in O(1)
during rotations.. Correct?

Delete: When the deleted element has a max of 1 child, only the node ancestors are
updated. Two children and it also needs to update elements on the path between the
deleted one and the successor.

Partial sum: Since the left sub tree sum values are stored in the nodes, it just needs
to search for the element with the specific key and sum sub tree sums along the way.

Any suggestions/improvements? Thank you so much :)


texts: Derivative and integral of experimental data

texts:
I have same experimental data with same noise:

I have to calculate the derivative and the integral of the function that fit the experimental data. I try with all the function in this page but the result was not good. How can I do that?

Update:
I look for same method to interpolate the data in order to calculate the derivative and the integral of the "best fit function" (because data have same noise I can't compute directly the derivative of them). The problem refers to the fact that I can't find a function that fits "exactly" the data; I try with a combination of sine and cosine and other method but the result don't work well.

I read the Cross Validate guidelines and I think my question is more related to this site, but I can't migrate the question to it.


texts:
How do you find the highest product of X items?
This should optimize for runtime complexity and protect from overflows from large products.

Inputs

An array of both positive and negative Ints representing potential products to the solution
An Int representing the number of products required for the solution

Output: An Int representing the highest product of X amount of numbers.

For example, for the highest product of 3 items, the input is iterated through while updating the following variables. After the iteration has completed in $O(n)$ time, the highest product of three variable is returned as the solution.

Lowest number
Highest number
Lowest product of two
Highest product of two
Highest product of three


texts: Is the language $\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free?

texts:
Is the language $ L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free ?

I guess that it's not context free because it seems too complicated for a PDA to decided whether 2 numbers are co-prime or not.

I tried using the pumping lemma to no avail.

Any help would be gladly appreciated.

Edit:

Here is one of my failed attempts with the pumping lemma:

Let $N$ be a constant. Take a prime $p$ such that $p > N!$ and then take the word $z = 0^p 1^{p+N!} \in L$. Let $ z = uvwxy $ be a decomposition of $z$ satisfying the conditions in the pumping lemma.

If $ vx $ contains only zeros then $ |vx| = k $ is an integer between $1$ and $N$. Define $m$ as $m = N!/k$. For $i = m+1$ the word $ uv^iwx^iy = 0^{p+N!}1^{p+N!} \not\in L $

However, I've failed to find such an integer $i$ for the other decomposition cases.


texts: Does the proof of the widely believed result P $\neq$ NP depend on the proof of NP $\neq$ Co-NP ?


texts: Quality of Reduction of finite automata using different congruences

texts:
I am looking for an example, which corresponds to what I've learned in my Applied Automata Theory Class:

Given a NFA $\mathcal{A}$,

a $\approx _\mathcal{A}$ quotient automaton can be bigger then a $\sim_\mathcal{A}$ quotient automaton and this can be bigger than an optimal quotient
and an optimal quotient does not need to be the smallest equivalent NFA.

$\approx _\mathcal{A}$ denotes the bisimulation relation (block refinement algorithm) and $\sim_\mathcal{A}$ denotes the canonical congruence, where $p \sim_\mathcal{A} q \text{ iff } \delta^*(p,w) \in F \text{ iff } \delta^*(q,w) \in F$, where DFA $\mathcal{A}= (Q, \Sigma, q_0, \delta, F)$.

Follow-up:

The original Automaton $\mathcal{A}$ over $\Sigma={\{a,b\}}$ recognizing $\mathcal{L} = \Sigma a^*$:

The original automaton $\mathcal{A} = (\{1,2,3,4,5,6\}, \Sigma, 1, \Delta, \{{3,4}\}) $ with $\Delta$:
\begin{pmatrix}
& 1 & 2 & 3 & 4 & 5 & 6\\
1 &- & b & a & -& -&- &  \\
2 &b & b & - & a & -&- &  \\
3 &- & b & - & a& a&- &  \\
4 &- & b & - & a& a&- &  \\
5 &- & - & - & -& -&b &  \\
6 &- & - &  & a& b&b &  \\
\end{pmatrix}

The quotient automaton $\mathcal{A}_{\approx}  = (\{12,34,5,6\}, \Sigma, 12, \Delta_{\approx}, \{{34}\}) $ with $\Delta_{\approx}$:
\begin{pmatrix}
& 12 & 34 & 5 & 6\\
12 &b & a & - & - \\
34 &b & a & a & - \\
5 &- & - & - & b \\
6 &- & a & b & b  \\
\end{pmatrix}

The quotient automaton $\mathcal{A}_{\sim}  = (\{126,34,5\}, \Sigma, 126, \Delta_{\sim}, \{{34}\}) $ with $\Delta_{\sim}$:
\begin{pmatrix}
& 126 & 34 & 5 \\
126 &b & a & b \\
34 &b & a & a  \\
5 &b & - & -  \\
\end{pmatrix}

The optimal quotient automaton $\mathcal{A_{OPT}}  = (\{1256,34\}, \Sigma, 1256, \Delta_{OPT}, \{{34}\}) $ with $\Delta_{OPT}$:
\begin{pmatrix}
& 1256 & 34 \\
1256 &a,b & a \\
34 &a,b & a  \\
\end{pmatrix}

The first property is satisfied since $\mathcal{A}_{\approx}$ has 4 states and $\mathcal{A}_{\sim}$ has 3 states. But in my example $\mathcal{A}_{OPT}$ is the smallest automaton recognizing the given language. When do they differ?


texts: Upper bound for reccurence relation with two variables, with linear dependency between them

texts:
Given the following reccurence relation:
$$T(M,k) = T(M-1,k)+T(M-2,k-1)$$
where $T(0,k)=0, T(1,k)=1, T(M,1)=1$
I have $M^k$ as a general upper bound for $T(M,k)$.
Now, suppose I want to give an upper bound only for cases where $M=n \cdot k$, i.e. I have the following new definition:
$$R(n,k) = T(nk,k)$$
and $R(n,1) = n-1$, $R(2,k)=f(k)$ (where $f(k)$ is some function of $k$ I know how to bound for any $k$).
is there a way to give an upper bound for $R(n,k)$, expressed with $n$ and $k$, which will by tighter than just placing it in $M^k$? I suspect that for those cases where $M=nk$ the value of $T$ is much lower than $M^k$, so a tighter bound should exists.
Is there a way to do such thing? I tried to unfold $R(n,k)$ to get an explicit definition but I get stucked when I need to express $T(nk-1,k)$ and $T(nk-2,k-1)$, since they do not "fit" to the defenition of $R(n,k)$.


texts: What are resources that I can use to learn about formal langauges?

texts:
What are some good resources for practice problems on formal languages? Every textbook I've seen contains few practice problems with even fewer answers. I would like a resource that has questions with varying degrees of difficulty, not just one really hard problem. For example if you learn about the pumping lemma, how do you get good at using it? Even a google search for practice problems with solutions doesn't return much.

Are there tools that can be used to check one's answers, for example given a regular expression it produces the DFA/NFA etc?

I'm using "Introduction to the Theory of Computation" and I personally found it hard to use: the layout is all over the place and there weren't enough questions with answers.


texts: two phase locking and a contest question?

texts:
In 2PL (two phase locking), what advantage(s) does the rigorous model have over  the strict model?

  I) There is no advantage over the strict model.

  II) In contrast to the strict model, it guarantees that starvation
  cannot occur.

  III) In contrast to the strict model, it guarantees that deadlock
  cannot occur.

  IV) In contrast to the strict model, there is no need to predict data
  needed in the future.

My TA says all of the above are false and the question is wrong. I am a bit confused. Can someone clarify for me why these are false. the answer sheet say IV is true !!


texts: Why does a DFA either contain all or no words $a^k$ if it loops for $a$ in all states?

texts:
I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below:

Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all states $q$ of $A$ we have $\delta(q,a)=q$.
Show that either $\left\{a\right\}^*\subseteq L(A)$ or $\left\{a\right\}^*\cap L(A)=\emptyset$.

As far as my understanding of the first part of the problem, the language accepted by $A$ is  $L(A)=\left\{a, aa, aaa, aaaa, aaaa...\right\}$.
Since, $\left\{a\right\}^*$ represents strings that belong to $L(A)$ including $\varepsilon$, therefore $\left\{a\right\}^*\subseteq L(A)$ is true.
How to show that $\left\{a\right\}^*\cap L(A)=\emptyset$?
Doesn't $L(A)$ represent strings generated by $\left\{a\right\}^*$? How can the intersection be $\emptyset$?


texts: Algorithm for assigning items to one of two sets (2-CNF?)

texts:
I have a set of items (A, B, C, D, ...) which I want to assign to one of two sets (set1, set2). Trying all possible assignments and selecting my favorite has complexity $O(2^n)$, so I am trying to prune the number of assignments evaluated. I want to do this based on available knowledge that certain pairs MUST be present in the same set.
For instance: given A, B, C, D, and knowing that the following pairs must be together:
A & B, B & C a solution would be set1 = {A,B,C}, set2 = {D}. Knowing that A, B, C must be together drastically reduces the number of assignments which have to be evaluated.
Note that there are pairs of items that may not occur in the same set. These relations however, are less obvious, which is why I restricted myself to finding the pairs listed above.
This already kind of looks like a satisfiability problem, which is good, as 2-CNF can be solved in linear time. In satifiablity, setting the variables to true / false could mean assigning the items to set1 / set2 respectively. However, expressing items must be in the same set looks like this: (A /\ B) V (!A /\ !B), which is 2-DNF.
2-DNF can be converted to 2-CNF in polynomial time, but would it be possbile to translate my problem directly to 2-CNF? This would allow me to keep the linear time complexity.
EDIT:
As explained in the comments, 2-CNF would be satisfied by placing all items in the same set, which would defeat the purpose as this may not result in a "favorite" assignment. A better solution is the answer by @D.W., where for each connected component (which represents a cluster of items that must appear together), we can choose in which set to place it. This reduces the number of assignments that have to be evaluated, and allows us to find our "favorite" assignment.


texts:
$3SATplus$

Input: 2 CNF formulas $F_1$, $F_2$ where all clauses have exactly $3$ literals.

Question: Does every truth assignment satisfy at-least as many $F_2$ clauses as $F_1$'s?

Assume $3SATPLUS \in NP$
Prove $3SAT \leq_p$ $3SATplus$
The reduction is as follows
$F_1 = (x \lor \bar{x} \lor x) \land \dots \land (x \lor \bar{x} \lor x)$
For $n$ clauses. This means it will always accept $n$ clauses.
$F_2 = F$
This is polytime because its $2n$ clauses only $n$ more than $F$
if $F \in 3SAT$, then $F_1 = F_2$ since they both satisfy $n$ clauses so $F_1, F_2 \in 3SATplus$
I'll prove the contrapositive
If $F \notin 3SAT$, then $F_1$ satisfies $n$ clauses and $F_2$ can satisfies only up to $n-1$ so $F_1 > F_2$ always. Hence,  $F_1, F_2 \notin 3SATplus$
Is there anything else left to say or does this confirm its $NP-hard$?


texts:
I am reading about planar graphs from this site.

It says:

  The complete bipartite graph K3,3 is not planar, since every drawing of K3,3contains at least one crossing. why? because K3,3 has a cycle which must appear in any plane drawing.

I am not able to get what cycle which must appear in any plane drawing has to do with edge crossing. Can't a cycle appear in plane drawing without crossing edges and thus letting the graph be planar? I must be missing something stupid.


texts: Develop the context free grammar to match this language (puzzle)

texts:
This is a puzzle type question which asks to create a context-free grammar to match this language:

{ x#w | x,w are in {a,b}*, and w contains the reversal of x as a substring }

So some example strings to try:
    #, a#a, b#b, ab#ba, ab#aaabbba

Does anyone have any advice on how to get better at these types of problems?  I am generally a good problem solver, but have trouble developing grammars for languages for some reason.  I am completely stuck on this question.  Here is my attempt:

S --> TR
T --> aTa | bTb | #R
R --> RR | 0 | 1 | empty

My guess is that we want to define the left side of the string in terms of the right side of the string.

Edit:  As far as I can tell, the above answer seems to be correct now.  Only took me an hour to figure out!


texts:
I know for factoring we have the RSA Numbers, in which factoring one of them quickly (usually) indicates a breakthrough in the field. However, I want to know if there's something similar for SUBSET-SUM, in which there are hard instances that if solved, would be a "big deal"? I found this, but they don't seem to be unsolved.
One way would to take the RSA numbers, convert them to 3-SAT, then convert to SUBSET-SUM, but the weights generated are very large. Maybe there's a way to convert FACTOR (the special case of two prime factors, to be specific) directly to SUBSET-SUM without having to go through 3SAT (not the main question; just a thought)?
For the RSA numbers in particular, we know how long each non-trivial factor is: $\frac k2$, where $k$ is the number of bits of the number $n$. Maybe we can use that to shrink the number of variables to only $n$, without having to make extra variables and unnecessarily fill the problem with "junk".


texts: Deterministic algorithms for computational distance between distributions

texts:
Computational distance between sequences of distributions $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ can be defined as the maximum, over all probabilistic polynomial time algorithms $A$, of
$$ \left|\underset{x \sim X_{n}}{\mathsf{Pr}}(A(x) = 1) - \underset{x \sim Y_{n}}{\mathsf{Pr}}(A(x) = 1)\right|, $$
for each $n \in \mathbb{N}$. We can, very similarly, define computational indistinguishability to be when the computational distance is a negligible function of $n$. Here is my question: can we use a deterministic polynomial-time algorithm in place of a probabilistic one without loss of generality? Can we say that the maximum computational distance is achieved by a deterministic algorithm? Will this algorithm be non-uniform?


texts: Does NP-Complete imply non-satisfiability?

texts:
I've seen a lot of text concerning the first NP-Complete problem, Boolean Satisfiability. I guess I'm confused concerning the language.

It sounds to me as though the problem could be difficult to compute (hence the NP-complete), however it still might be satisfiable. As in, there exists a satisfying mapping of literals. We can't necessarily compute it easily, but it's out there.

In fact, I would guess that the two adjectives really have no relation to each other. But, when working with problems, I am often asked to see whether a set of clauses is satisfiable. Does that mean, Can we compute a satisfying mapping? And by extension, does NP-complete imply that a given CNF setup is unsatisfiable?


texts:
There are $n<10^4$ points on the plane. How can one approximately (with a given precision $2^{-20}$ of points' coordinates) find the minimal radius of a circle that covers some $k$ out of $n$ these points?

There is lots of information on the case $k=n$ in Wikipedia, but I found nothing on general case.


texts: A curious question - an algorithm to determine how a list of vectors is sorted?

texts:
Given a list of vectors consisting n integers that has been sorted by their components in certain priority, how do you find the possible sorting keys, i.e. the order of precedence?

Suppose there is a sorting function:

def some_sort(vectors):
    priority = (vector[i],..., vector[j])
    return sorted(vectors, key=priority)

where priority is a tuple of the same length n as vector and is some permutation of vector (in other words, (i, ..., j) is some permutation of the set {0, ..., n - 1})

Now you are given the list sorted_vectors which is returned by some_sort(vectors, key=lambda vector: (vector[i],..., vector[j])) (it doesn't matter whether you know the original list vectors), how do you determine the permutation (i, ..., j)?


texts:
the following pseudo code returns the nth Fibonacci number:

 if n = 0 then
    return 0
 a ← 1
 b ← 1
 for i = 1 to n − 1 do
     c ← b − i
     b ← c + a
     a ← c + 2*i + 1
 return b

I am trying to find any loop invariant for the variables a and b, (as i understand it has to be valid before and after the loop, but i can't seem to be able to come up with anything, except maybe b >= i, but I'm not sure that counts as an invariant). As far as I get it, simply saying b = b - i + a wouldn't really mean anything. Any help on the subject would be greatly appreciated.


texts: What does it mean for a function to be decidable? (homework)

texts:
Note: This is part of a homework exercise. I am asking for clarifications, not a solution!

Given: Assume $g: \mathbb{N} \mapsto \mathbb{N}, g\in R$ ($R$ is the class of recursive functions) is a strictly monotone function, i.e., $\forall n\in \mathbb{N}: g(n)  < g(n+1)$.

Prove that $g(\mathbb{N})$ is decidable.

Clarification of the assignment:
I am not sure I understand the exercise correctly. What does it mean that a function is decidable? I assume that it's a decision problem of the form "For $x \in \mathbb{N}$, is $x\in range(g)$? For a function $g$ to be decidable, we can then define a decision procedure that returns $yes$ or $no$ for any $x$.

Is this correct? Or am I on the wrong track?


texts: I was wondering if its possible to use floyd warshall with constraints meaning lets say you have a group of "special vertices" of size logn and you want to calculate all the shortest paths but each path has to go through at least one "special vertex" is this even possible or is it hard n


texts: Union of every language within group of decidable languages is also decidable?

texts:
So I was trying to solve following exercise:
Let $(L_{i})_{i \in \mathbb{N}}$ be a family of decidable languages - this means that every $L_{i}$ is decidable. Then $\cup_{i \in \mathbb{N}}L_{i} $ is also decidable. Right or wrong?
The solution states, that this statement is wrong because we can set $L_{i}:=\{f(i)\}$ with $f : \mathbb{N} \rightarrow H_{0}$ and will therefore receive $\cup_{i \in \mathbb{N}}L_{i} = H_{0}$.
At the same time $L_{i}$ languages are still decidable,  for every $i \in \mathbb{N}$ because they are finite.
However I still struggle to understand how exactly a language can be decidable with $f : \mathbb{N} \rightarrow H_{0}$, because I thought that $H_{0}$ was not decidable.
Thanks in advance!!


texts:
On one hand, Horn-SAT is known to be tractable in linear time - where Horn-SAT is the problem of deciding whether a given set of propositional Horn clauses (with at most one positive literal) is satisfiable or not.
On the other hand, Double-SAT is NP-complete (see this post : Proving Double-SAT is NP-complete) - where Double-SAT is the problem of deciding whether a given set of propositionnal clauses has at least two models.

Let Double-Horn-SAT be the problem of deciding whether a given set of propositional Horn clauses has at least two models.

What is the complexity of Double-Horn-SAT ?


texts: Printing actual solutions for the coin exchange problem

texts:
As I teach myself dynamic programming, I have learned about the coin exchange problems. Specially this site: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ provides great insight about it. Specifically, the following implementation of a tabulated-DP-based solution for this problems is presented as follows:

def count(S, m, n ):
    # If n is 0 then there is 1
    # solution (do not include any coin)
    if (n == 0):
        return 1
    # If n is less than 0 then no
    # solution exists
    if (n < 0):
        return 0;
    # If there are no coins and n
    # is greater than 0, then no
    # solution exist
    if (m <=0 and n >= 1):
        return 0
    # count is sum of solutions (i)
    # including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );

However, this only counts the number possibles solutions.

Question: How can I actually save these solutions for post-processing?

Previous research: In this very helpful video: https://www.youtube.com/watch?v=ENyox7kNKeY they explain how to use an array of parent pointers, to generate the actual solutions, however, I am having issues with implementing this approach with the previous tabulated solution. Any hint?


texts:
I'm reading about MinHash technique to estimate the similarity between 2 sets: Given set A and B, h is the hash function and $h_\min(S)$ is the minimum hash of set S, i.e. $h_\min(S) = \min(h(s))$ for s in S. We have the equation:
$$
p(h_\min(A) = h_\min(B)) = \frac{|A \cap B|}{|A \cup B|}
$$
Which means the probability that minimum hash of A equals to minimum hash of B is the Jaccard similarity of $A$ and $B$.

I am trying to prove above equation and come up with a proof, which is:
for $a \in A$ and $b \in B$ such that $h(a) = h_\min(A)$ and $h(b) = h_\min(B)$. So, if $h_\min(A) = h_\min(B)$ then $h(a) = h(b)$. Assume that hash function h can hash keys to distinct hash value, so $h(a) = h(b)$ if and only if $a = b$, which means the probability is $\frac{|A \cap B|}{|A \cup B|}$. However, my proof is not complete since hash function can return the same value for different keys. So, I'm asking for your help to find a proof which can be applied regardless the hash function.


texts: What's the correct term for this analog of cryptography?

texts:
Suppose there is a communications channel between two parties. Suppose I want to send information through this channel, but I want to make it look like noise. Ie, I don't necessarily want to encrypt it, though I'm not prohibiting encryption - the point is I want to be able to transmit information to someone else such that what is sent across the channel cannot be distinguished from random noise by any potential eavesdropper.

Maybe something like the above is impossible to do "perfectly", but in any case the question I'm asking is - what is the correct term/keywords for problems in the spirit of what I described above?

Is there a mathematical theory of something of this type?


texts: In Ada95 how many bytes does integer occupied in memory?


texts: Is there a way to create a "captcha"-like problem that computers can verify, but only humans can solve?

texts:
In a normal CAPTCHA scenario, a computer creates a challenge and a correct response to it.  (The challenge is an image of distorted text, for instance, and the response is the characters depicted.)  These are constructed so that hopefully a human can easily determine the response from the challenge, but a computer cannot.  Ordinarily only the originating computer, which already knows the correct response, can determine whether a given response was correct.

My question: is it possible to create a CAPTCHA that computers can verify, but not solve?  In other words, is it possible to create a scenario that looks like this:

Computer A generates a challenge, sends it to Human B and Computer C

Computer C cannot feasibly determine the correct response, other than by brute-force search (which can hopefully be made impractical by the size of the response.)

Human B can feasibly determine the correct response.  ("Feasibly" is not easy to define.  We need the response to be much bigger than normal CAPTCHAs in order to deter simple brute-force searching by computers, so "as easy as a normal CAPTCHA" is going to be impossible.  But it's not out of the realm of possibility to make a human type in a large response.  It'd just be really annoying. A few hundred printable characters can get to 2048 bits, for instance.  So as a rough definition: it's allowed it to be annoying as hell, but it has to at least be feasible for a person.  Assume the person's physical and mental abilities are roughly average for a literate computer user.)

If Human B sends Computer C the correct response, Computer C can feasibly verify that the response is correct, without contacting computer A or having any prior knowledge other than the challenge.

Would it be possible, under today's technology and knowledge, to create such a protocol?

Furthermore, would it be possible to design the protocol such that even Computer A can't determine the correct response to the challenge it just generated without human input--and Computer C can verify that Computer A could not have known the response without a human providing the solution?  If this all this can be achieved, then the result is analogous to the "proof of work" seen in bitcoin and other protocols.  Instead of a proof of computational work, we'd have a proof of human work--the combination of the challenge and correct response would constitute proof that a human spent some marginal amount of effort.  This proof would then be verifiable by any computer.  Is such a thing even remotely plausible?

Of course, at some point in the future computers will probably overtake humans altogether.  Once that happens, there will not be any problems that are feasible for a human but not a computer, and therefore no CAPTCHAs or CAPTCHA-like protocols will be possible.

But what about under currently known human and computer abilities?


texts: Efficient algorithm for numerical estimation of 3D rotation matrix

texts:
I am writing a computer vision related program and stuck on a problem. I have a system of quadratic equations

where M is a constant 3x3 matrix,  is the 3x3 identity matrix, and we are solving for the 3x3 matrix R.

The first set of equations contains 6 independent equations which leaves us with 3 degrees of freedom of SO(3) group. The second set of 3 equations just states that the matrix  is symmetric.

Since this program will repeatedly solve these equations, I am searching for an efficient algorithm which I can run on Raspberry Pi, i.e. not monsters like Matlab, Mathematica or root.


texts: Algorithms for minimizing Moore automata

texts: Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times of these algorithms if any?


texts: How to approach NFA design questions intuitively?

texts:
I did see a lot of nice and informative questions, articles on inter-net and on StackOverflow itself, of-course. But I found all the questions or articles following a specific rule or a pattern to explain the topic. I mean, when a question was asked on NFA, DFA or Regular Expression, a solution was presented to the question abiding by the theorems / rules of these topics (Theory of Computation).

But what I feel is that, as most of the questions on DFA/NFA are of the type
"Design an NFA...." or "design a DFA..." , I feel that developing/Designing DFA/NFA must be an ART.

And where there is ART I feel there is an intuition. If these problems involve "DESIGNING" something ,then everyone must have their own way (of-course not going out-of-the-way of theorems or rules as such) of solving or attacking these problems. One should have developed a thinking process (over the years of practise) to solve these problems.

So I would like all the experts over this Site to share their knowledge (preferably in simple words) how they think over the problems (simple ones) of these topics.

I would like to elaborate the question with a simple example.

  Let F be the language of all strings over {0,1} that do not contain a pair of 1s that
  are separated by an odd number of symbols. Give the state diagram of a DFA with
  five states that recognizes F .

Or maybe this:

  Design an NFA to find a 4-state NFA for the complement of F.

These questions are from the Sipser's book and I have also found the solutions for them myself.

I just want to know , how one can develop an intuition for solving the problems?


texts: Simple Path between 2 nodes passing through specific nodes

texts:
I have an unweighted undirected graph and I have to find if there exists a path between two vertices $u,v$ that visits set of specific nodes $A$. $A$ can contain $1-10$ nodes. No node can be visited more than once.

I thought about finding all paths between $u,v$ and then check if those paths contain  vertices from $A$. I optimized it by not considering those paths in which no of vertices is less than cardinality of $A$. But this doesn't affect much. If $A$ has only one then it's useless.

As suggested in comments, I want to start with 1 node in $A$ to simplify it. I will try to extend it to multiple vertices on my own.

There's another way if we precalculate path between every  pair of nodes and then check if we have a path passing through $A$ but the time complexity will be very costly.

I was thinking if it can be done using lower bounds max-flow :
 The lower bound max-flow algorithm computes a flow, which must include all the edges that have a positive $(>0)$ lower bound value. If only one edge has a positive lower bound, the flow computed by the algorithm can be used to build a simple path, which includes such edge. The “edge” instance of the problem can be transformed into its “node” equivalent by first splitting the include-node into two half-nodes, i.e.,
$n_1$ and $n_2$. All incoming edges to the original node converge to
$n_1$. All outgoing edges of the original node emerge from $n_2$. A directed edge $e_l$ from $n_1$ to $n_2$ is added with a positive lower bound value.
All  other  (original)  edges  of  the  network  have  zero  lower  bound.  Now,  applying  the lower  bound  max-flow algorithm to this flow network, a feasible flow from source to destination can be found such that $e_l$ is included in at least one of the (flow) augmenting paths.

Then on merging $n_1$and $n_2$ the simple path can be traced. But I couldn't think of code or that matter a code to implement it.

EDIT: The problem here lies about how to make it a simple path so as to not to repeat vertices.

So is there any an efficient way to do this (maybe polynomial or less)?


texts: Can I simplify the recurrence T(n) = 2T((n+1)/2) + c by ignoring the "+1" part?

texts:
I have written a recurrence relation to describe a recursive algorithm finding the maximum element in an array. The algorthim has an overlap, meaning both of the subarrays that are recurred on contain the middle element of the array.

$T(n) = 2T((n+1)/2) + c$

However, I want to simplify this recurrence relation more.

Since you can often times omit floors and ceilings in recurrence relations, can I omit the $+ 1$?

If so, then my relation is now: $T(n) = 2T(n/2) + c$

Would this alter my big-Theta time complexity? Why or why not?


texts: Do self-loops in DFA cause infinite languages?

texts:
A true/false question: If a DFA $M$ contains a self-loop on some state $q$, then $M$ must accept an infinite language.

The answer is "false". I've read this question, but I'm still wondering why $M$ does not necessarily accept an infinite language. Isn't the language $b^*$ infinite? Don't all self-loops look like $b^*$?


texts: How to make a NFA (or DFA) from $\varepsilon$NFA?

texts:
I need to build a DFA from $\varepsilon$NFA, so first of all I assume that I need to convert the $\varepsilon$NFA to NFA and then to DFA (because I know the method of converting from NFA to DFA, and we learn how to remove $\varepsilon$'s from $\varepsilon$NFA and make it NFA.
But the I'm still stuck at some cases....
For example:
See this $\varepsilon$NFA:
I want to make it NFA (I don't know if to write the whole algorithm...), and I'm not sure which is right:
This:

Or this (at the comments.... I can't put more then 2 images)
I think that the first is the right one, but I'm not sure...
At the second one - the number of the 0-s must be even to be at $q_1$ but at the original $\varepsilon$NFA it can be any number of 0-s...
One more thing, it's correct that I'm not putting 0,1 insted of the $\varepsilon$? (Because 1 from $q_0$ brings me to $\varnothing$...)


texts: is the alignment between two sequences of points with 'no cross line' constraint an NP problem?

texts:
Given two sequences of points(i.e. ordered points), connect the points in seq_A with the points in seq_B according to some rules. A point could be connected to 0, 1, or many points in the other sequence. But there should not be any line crossing. And each line could be assigned with a weight(controlled by relation between two connected points) and the overall weights should be as low as possible.

Is this an NP problem? Can this problem be reduced to any of Karp's 21 NP-complete problems?

Thanks to David Richerby. The constraints that were missing are that the number of points that are not connected to any points should also be as few as possible.


texts: A commonly-used symbol for the set of all heads of directed edges?

texts:
Let $G = (V, E)$ be a digraph, and consider the set $\left\{ v \in V \; \middle| \; \left(\{v\} \times V \right) \cap E \neq \varnothing  \right\}$, the set of vertices which form edges with other vertices; or if you will, the set of "heads of edges".

Is there a commonly-used term for this set?


texts: Data types for storing arbitrarily much information

texts:
I've heard that YouTube had a problem with the view count on Gangnam style since the number of views exceeded the variable byte size.

What's the problem with creating really large variables? Why does it end with unsigned long, for example? Can you create bigger and bigger variables to hold more and more bytes?  Is there any reason why programmers don't just use a really big variable for everything?


texts: Breadth First Traversal for graph with multiple connected components

texts:
I read BFS and DFS from CLRS and realized that the BFS algorithm does not consider graph with multiple connected components but only with single connected component, whereas DFS algorithm considers graph with multiple connected components as can be seen in below pic:

Are my observations correct? If yes, why is it like that? Is their any significance to it? Is their any reason for CLRS to give such algorithm or its perfectly acceptable to modify BFS to loop over all vertices, something similar to DFS in order to traverse all connected components of graph?


texts: Are these modern operating systems monolithic or microkernel?

texts: I know that (at least at its conception) Linux and Mac OS were both monolithic kernels. My question is, what kind of kernels are Linux, Mac OS, and Windows today and why?


texts: Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$

texts:
I want to find a near-optimal solution for a maximum weight independent set.
i.e given a graph $G = (V,E)$ I want to find a set $S = \{v_1,v_2,\dots,v_n\}$ of nodes in $V$ such that the sum of their weights is maximum (The weights are positive), under the constraint that every pair is not connected by an edge,
i.e $\forall\ v_i,v_j \in S:(v_i,v_j) \not\in E$.

A common problem instance would be a graph with around $2 \times 10^5$ nodes, up to around $5 \times 10^5$.
The degree of a node is bounded by ~$100$, and the number of edges will be around $10^6$.

Can anyone recommend a heuristic algorithm for finding a near-optimal solution? A runtime of hours or even days is acceptable.

I've been looking so far at articles about Tabu search and that is the current direction I am going towards.


texts: How does the OS know the physical address of a process' first memory page?

texts:
If I have a program, its instructions are stored on the hard drive. When I double-click the executable the pages of memory for this process must get loaded in to RAM. However, for the pages to get loaded in to RAM, the CPU must already have resolved the virtual address to physical address. The latter requires the TLB to have been involved- which requires the L1 cache to have been queried- which cannot have happened as the process instructions haven't even been loaded in to RAM yet?

I am totally confused how the instructions for a process are loaded in to RAM the very first time when the L1 cache doesn't contain any information about the process.


texts: How to prove that { : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?

texts: My idea is to find a turing machine which recognizes this language in $\log N$ space, could anyone give me some clue on how to find such turing machine?


texts: What is the difference between "algorithm," "process" and "program"?

texts:
I am currently studying algorithms and algorithmic design, and I am confused those terms. What is the difference between them?

Thank you.


texts: How was $T(N)$ derived for this function?

texts:
I’m struggling to understand how $T(N)=C_1 \times N + C_2$ was derived
Assuming $C_1$ refers to l <- 0, and $C_2$ refers to return l
Shouldn’t it total $T(N)= C_1 + (N + 1) + N + C_2$, which simplifies to $T(N)= C_1 + 2N + 1 + C_2$ ?


texts: Is inserting into an ordered array by swapping has downsides compared to inserting into a position and offsetting elements

texts:
I'm thinking how I can insert an element into an ordered array. Assume the array has a capacity for one element. I've implemented two methods.

The one finds the position to insert, moves elements one position to the right and inserts the element into the position.

The seconds one which seems more intuitive to me is to put an element into the last position in an array and then put it in the correct position by swapping with the left element - the way it's done in the insertion sort.

However, I googled for the solution and almost all suggestions are some modification of the first algorithm. So I'm wondering if there's something I'm missing. Can you guys please help?


texts: Why does every member $f(n) \in \Theta(g(n))$, and $g(n)$ have to be asymptotically non-negative?

texts:
The following is an excerpt from CLRS:

The definition of $\Theta (g(n))$ requires that every member $f(n) \in \Theta(g(n))$ be asymptotically nonnegative, that is, that $f(n)$ be nonnegative whenever n is sufficiently large. (An asymptotically positive function is one that is positive for all sufficiently large $n$). Consequently, the function $g(n)$ itself must be asymptotically nonnegative, or else the set $g(n)$ is empty.

Intuition suggests that having one function with a positive domain while the other with a negative one perverts the purpose of asymptotic analysis (a measure of the order of growth) as the positive function can be an upper asymptotic bound of the negative function simply on merit of it being positive, even in cases where the negative function grows faster.
In cases where both functions have negative domains, asymptotic analysis would still be a valid measure of the order of growth, making the restriction of both functions having to be positive appear useless.


texts: Clarification on "clause learning" in DPLL algorithm

texts:
I am struggling to understand the idea of conflict-driven clause learning, in particular, I can not understand why the clause we 'learned' is a substantially new (i.e. the clause database does not already contain it, neither any subset of it). Here is what Knuth in his book says:

A conflict clause $c$ on decision level $d$ has the form $\overline{l} \lor \overline{a}_1 \lor ··· \lor \overline{a}_k$, where $l$ and all the $a$’s belong to the trail; furthermore $l$ and at least one $a_i$ belong to level $d$. We can assume that $l$ is rightmost in the trail, of all the literals in $c$. Hence $l$ cannot be the $d$th decision; and it has a reason, say $l \lor \overline{a}′_1 \lor ··· \lor \overline{a}′_k$.  Resolving $c$ with this reason gives the clause $c′ = \overline{a}_1 \lor ··· \lor \overline{a}_k \lor \overline{a}′_1 \lor ··· \lor \overline{a}′_k$, which includes at least one literal belonging to level $d$. If more than one such literal is present, then $c′$ is itself a conflict clause; we can set $c \leftarrow c′$ and repeat the process. Eventually we are bound to obtain a new clause $c′$ of the form $\overline{l}′ \lor \overline{b}_1 \lor ··· \lor \overline{b}_r$, where $l′$ is on level $d$ and where $b_1$ through $b_r$ are on lower levels.
Such a $c′$ is learnable, as desired, because it can’t contain any existing clauses. (Every subclause of $c′$, including $c′$ itself, would otherwise have given us something to force at a lower level.)

I can understand why the clause database has no subset of $c'$ that contains $\overline{l'}$ (because $\overline{l'}$ would have been forced (i.e. unit-propagated) at level lower than $d$), but what contradicts to the existence of clause, let's say, $\overline{b_1}\lor\overline{b_2}$?


texts: How can it be decidable whether $\pi$ has some sequence of digits?

texts:
We were given the following exercise.

  Let

  $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

  Prove that $f$ is computable.

How is this possible? As far as I know, we do not know wether $\pi$ contains every sequence of digits (or which) and an algorithm can certainly not decide that some sequence is not occurring. Therefore I think $f$ is not computable, because the underlying problem is only semi-decidable.


texts: Greedy Solution for Selecting Prefix Sum

texts:
Given $n$ arrays. Each has size of $h$. Let $a_{i, j} \in \mathbb{I}$ be the $i$-th element of $j$-th array. You can select at most $k$ numbers from all arrays but if you pick $a_{i, j}$, you have to pick $a_{1, j}, a_{2, j}, \dots, a_{i-1, j}$ as well. Each element can only be picked once. Find maximum sum of elements.

My greedy solution is : Let $p_{i, j}$ be $\sum_{x=1}^{i} a_{x, j}$. Sort a list of $\frac{p_{i, j}}{i}$ for all $i$ and $j$ in descending order. Then iterate through the list and check each value whether we have included the prefix sum of this array into our final answer or not. If no and $h \geq j$, we include it in the final answer, subtract $i$ from $h$, and mark $j$ as included. If yes and $j >$ the index of the previous one, we do the same thing just the part extended from the previous one.

Is this solution optimal or is there a better solution to this problem?