texts: Multiple Knapsack Problem, but with exact weight/capacity? (All knapsacks have to be filled completely)

texts:
I have a few knapsacks of given capacities.

Also, much more items of given weights and values.

As usual, items have to be put into knapsacks to maximize profit.

What is different from a standard MKP, is that there’s a requirement
that each knapsack has to be filled completely. I.e. the sum of
weights of its items has to be equal to its capacity (while in the
standard problem, it is less-than-equal).

How to approach this? (I want to find an algorithm to solve this.)


texts: Is it decidable whether a pushdown automaton recognizes a given regular language?

texts:
The problem whether two pushdown automaton recognize the same language is undecidable. The problem whether a pushdown automaton recognizes the empty language is decidable, hence it is also decidable whether it recognizes a given finite language. It is undecidable whether the language accepted by a pushdown automaton is regular. But ...

  ... is it decidable whether a pushdown automaton recognizes a given regular language?

In case the answer is no, does the problem becomes decidable if the given regular language has star height $1$?


texts: How does CPU actually retrieve data from memory when you call a variable in a programming language?

texts: As I have understood from all the internet sources I can get to, when you declare and initialize a variable in java, you are allocating this data, say an 8-byte float, in a particular memory cell in the RAM, with the address specified as the row and column number. Now, suppose I want to access this memory location and print the float out. As a programmer, I will clearly not write the binary representation of the memory location of this float for the CPU to process; rather, I will call the variable name I declared before. When this variable name got transformed into binary code and sent to the CPU, how does CPU know what memory location this variable is referencing to? I mean, for that to work, doesn't the memory location of the variable has to be stored directly on the CPU? Because if not, you will have to store the the memory location of the float at some memory cell as well; in other words, when you call the variable, you have to first get from the RAM what memory address is the variable representing and then use that information to go to the RAM to retrieve the float. However, for the CPU to get to the memory address of the memory address of the memory address of the float, it still either has to store it directly on the CPU or has to store it in the RAM, and the same story goes one recursively. What is really happening when you need to call a variable? How to the CPU know the memory address associated with the variable in the first place without referring to the RAM? Because if the CPU is referring to the RAM, then that means it has already gotten the memory address f


texts: If 2's complement is the best way to represent numbers in computers, why worry about BCD and other binary codes?

texts:
I'm studying Digital Logic and Design. And in the first chapter, there's all this information about various binary codes. I did some searching on youtube and found this awesome video - https://www.youtube.com/watch?v=lKTsv6iVxV4&t=5s.

Now, my question is, If 2's complement is the best way to represent numbers in computers, what's the purpose of BCD?


texts: Difference between graph-partitioning and graph-coarsening

texts: What is the difference between graph-partitioning and graph-coarsening with respect to scale-free networks? I am trying to analyze graphs generated using the data from social networks. Do both the terms mean the same or are they different?


texts: Rice's Theorem: implication of having an undecidable property

texts:
I understand the assumptions that have to be true about a property or set of properties in a Turing machine description for Rice's Theorem to apply.

But then what?  If a set of Turing machines have an undecidable property, is the language itself necessarily undecidable? Or only if you can find a reduction from a known-undecidable machine is the language undecidable?

What does it really say about a language if it has an undecidable property? Are machines that recognize that language undecidable?


texts: Will computers always behave in an expected way, given constant electrical input?

texts:
For the purposes of this question, please forget about computers being unable to perform as expected due to excess workloads, exceeded capacities, or general bad hardware/devious software (e.g. a calculator programmed . I'm only concerned with a perfectly "healthy" computer's not what was expected of it.

What are some scenarios in which a computer did not behave as expected, even though it received constant electrical input and was, for all intents and purposes, "on"?


texts: Print the number of subarrays of an array having negative sums

texts:
Problem statement: Given an array of N integers, find its number of negative subarrays (i.e sub arrays having negative summation). E.g: for an array $[1,-2, 4, -5, 1]$ there are 9 subarrays whose sum is negative. Subarray means sequential array within an array.

My code: It's complexity is $\theta(n^{2})$ as we can see. I have applied brute force technique. How can I improve my code/pseudocode?

    int sum=0,count=0;
    for(int i=1,k,j;i<=N;i++){
        for(k=1;k<=N-i+1;k++){
            for(j=0;j<i;j++){
                sum += arr[j+k-1];
            }
            if(sum<0)
                count++;
            sum = 0;
        }
    }


texts: How can you define the notion of "state" using only a type theory language?

texts:
The notion of state I'm referring to is the one described in this wikipedia page : https://en.m.wikipedia.org/wiki/State_(computer_science)

Which defines it in this way:
 "a program is described as stateful if it is         designed to remember preceding events or user interactions; [1] the remembered information is called the state of the system."

My question is: Does there exist one or more formal definitions/descriptions that correspond to this notion of "state",  in a formal system of Type theory (might be system F , simply typed lambda calculus or any other)


texts: How to choose proper activation functions for hidden and output layers of a perceptron neural network?

texts:
As far as I know choosing an activation function for the input layer is relatively straightforward: I use Sigmoid if the input data domain is (0,1) and TANH if it is (-1,1).

But what activation functions to set for hidden and output layers? Is there any conventional logic for making thish choice reasonably? How do I know/set the domain of a neuron layer output?


texts: Short notation for Turing machine configurations

texts:
I'm writing about Turing machines and often need to denote the tape. I'm using exponential tapes, i.e. a repetition count for each symbol.

I usually use something similar to
$(x_k^{e_k})_{1 \leq k \leq m} \text{ Q } (x_k^{e_k})_{m+1 \leq k \leq n}$
(latex: $(x_k^{e_k})_{1 \leq k \leq m} \text{ Q } (x_k^{e_k})_{m+1 \leq k \leq n}$)
with $x_k$ the symbols and $e_k$ their exponents. The head in state $Q$ is at position $m$.

What (very slightly) annoys me about this is the need to include $Q$. Without it, it would just be
$(x_k^{e_k})_{1 \leq k \leq n}$
(latex: $(x_k^{e_k})_{1 \leq k \leq n}$)
, which is must easier to read.

The transitions may change various symbols and exponents at the same time, while $Q$ almost always stays in the same spot.

How should I note this down? Is there an easy to understand (and parse) notation which is shorter but still carries the same information? I could not find a solution in the papers I read. Or maybe I should just carry on, because this isn't an issue at all?


texts: Why does not the result in this notes show P is not NP in BSS model?

texts:
As far as I know (not understand that well though) BSS model is a real computation model and $P_{\Bbb R}\neq NP_{\Bbb R}$ is a real analog of $P\neq NP$ problem in BSS model.

The lecture notes http://www.cs.technion.ac.il/~janos/COURSES/ESSLLI-2014/E-abelian.pdf show $P_G\neq NP_G$ at every infinite abelian group $G$.

Each of $\Bbb Z$, $\Bbb R$ and $\Bbb C$ is an example of such $G$.

So why does this not settle the $P$ and $NP$ problem in BSS model?


texts: Prune and search Algorithm for Generating a Bottleneck Spanning Tree

texts:
I'm trying to wrap my head around a prune-and-search algorithm for returning a bottleneck spanning tree, currently I'm selecting the median weight of all the edges, then divide the original graph G into two graphs containing the edges which are less than or equal to the median or greater than.
After separating the graphs, I test the median weight against the original graph (G) to see if it is a bottleneck value. I'm stuck on what to do, if the median is not a bottleneck value, I was thinking maybe I could compact the graph of edges with weights less than the median - but the cut of a compacted graph would still have the weights so the median wouldn't change. I'm thinking I need to form an MST at some point as well?
So far I have something like:
def F(G):
  m = find_avg_weight_of_edges(G)
  G_le_m = get_g_w_edge_weight_less_than_or_eqal_to(G,m)
  G_gt_m = get_g_w_edge_weight_greater_than(G,m)
  if is_bottleneck_value(G,x):
    T = F(G_le_m)
  else:
    # note quite sure what to do...
    # I can't remove the less than or equal to edges
    # since they are needed to make up the MST
    # but if I don't remove them m won't change
    # maybe some kind of reduce/scc function?
return T


texts: Computability of a function and decidability

texts:
Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^∗$ to $B^∗$. We say $f$ is computable if there exists a Turing machine $M$ which given an input $x ∈ A^∗$, always halts with $f(x)$ on its tape.

Let $L_f$ denote the language $\{x\#f(x)∣x∈A^*\}$.

This is a part of the question and the answer says that if $L_f$ is recursive then $f$ is computable. If $L_f$ is recursive then we can accept all the string in the language but we have to reject the strings not in the language. A function is said to be computable when it has a halting Turing machine which computes the value for $f(x)$ for every $x$ in the domain and HALTS.
Then what about the values outside the domain?


texts: Cloning the output of a quantum program with unknown input but known measurements

texts:
Suppose Alice asks to use Eve's quantum computer. Alice loads her hidden quantum state into the computer, then gives Eve a program to run. The program will apply unitary operations and measurements to Alice's state, and Eve will report the measurements to Alice.

Eve wants to make an approximate clone of Alice's final state (the state after the program has run). Eve knows the program that ran, and all the measurement results that were generated, but isn't allowed to tamper with the program or the state.

If Eve has no measurement results, then the no-cloning theorem applies. The best Eve can do is use the optimal [approximate] cloning procedure, which will do terribly. But it's also possible that there's lots of measurement results that together imply Alice's whole state... it's just a matter of putting all the pieces together. I'm interested in the latter scenario.

Assuming Eve wants to generate an optimal clone given the available measurement information, what is the expected computational complexity of her task in terms of the number of qubits $n$ and the number of operations $m$? How hard is it to take a "this was done then that was measured then this was done then that was measured" history and produce a plausible output state? Are there any viable algorithms, or is this simply an exponentially difficult problem?

Notes

The measurement results are computed live; they're not given. As a result, exponentially unlikely measurement results (such as the ones you'd use to trivially encode NP-hard problems into Eve's task) have an exponentially reduced impact on the expected running time.
A naive classical algorithm is to store a $2^n \times 2^n$ density matrix on a classical computer and mimic all operations and measurements onto the density matrix. But this has complexity $O(m 4^n)$, which is not very good. Inference is expensive.
A naive quantum algorithm is to create lots random states, mimic all operations and measurements applied to the real state onto each of the initially-random states, and throw out any that don't match the observed measurements. This has complexity $O(m 2^m)$, which is worse than $m 4^n$ since $m$ will generally be much much larger than $n$. Post-selection is expensive.
A magical Post-BQP machine could trivially solve the problem in $O(m)$ time.
Related blog post
It seems like a lot of cryptography problems would fall under this regime. An answer that's just a hardness-by-reduction-from-cracking-AES is fine, though I feel like if Eve knows the qubits are not superposed in the computational basis then measuring them should be fair game.


texts: Prove: if $\delta_D(q0, w) = p$ then $\delta_N(q0, w) = {p}$

texts:
In my textbook, it presents the theorem, "A language L is accepted by some DFA if and only if l is accepted by some NFA". My textbook explains that the "if" portion of the proof is given by the subset construction and theorem if $D=(Q_D, \sigma, \delta_D, {q0}, F_D)$ is the DFA constructed from NFA $N=(Q_N, \sigma, \delta_N, {q0}, F_N)$ by the subset construction, then L(N) = L(D).

However, it leaves it up to the reader to prove the "only if" portion - essentitally, if $\hat\delta_D(q,a) = p$ then $\hat\delta_N(q,a) = {p}$. It suggests that we mu prove this by induction on $|w|$.

I understand how to complete the basis part of this inductive proof, I think.

If w is the empty string, then
$$\delta_D(q,\epsilon) = q$$ and
$$\delta_N(q,\epsilon) = {q}$$
by definition of the extended transition function.

However, I'm lost as to how to finish the proof. I've come up the starts of something, but I don't know if I'm even in the right direction:

Assume the statement is true for strings shorter than y and break y into $xa$ where $a$ is last symbol of $y$ and x is the string of symbols before a.

$\delta_N(q_0, y) = \bigcup\limits_{i=1}\delta_n(p_i, a)$

$\delta_D(q_0, y) = \delta(\hat\delta(q_), x), a)$


texts:
I have a problem with the following optimisation problem:

In total there are $n=100$ items. A quality level $L_i \in \{0,1,2,3,4,5\} $  must be selected for each of these items. The greater $L_i$ is, the greater  weight $w_i$ and its value $v_i$, starting with $w_i=0$ and $v_i=0$ for $L_i=0$.
Furthermore, $w_i$ depends on both item $n$ and its quality level $L_i$ and is calculated using function $w_i = w(n,L_i)$. $v_i$ depends on the total set of items and their selected quality levels $L_0 \dots L_n$ and is calculated using the relatively cost-intensive function $V$.

The question now is, what are the optimal quality levels improvements for each item, given random initital quality levels for the items and a capacity $W$? An important restriction is that a quality level can only be increased by one level in total. Each item must be selected exactly once (quality level $L=0$ is effectively the same as if the corresponding item had not been selected).

I see a difficulty in the fact that an items's value v depends on all other items. Can the problem still be solved optimally with an acceptable time complexity, or would it be necessary to use other algorithms, if so which ones? Maybe greedy algorithms?

Thank you very much for your help!


texts: Proving $ \{ \langle D_1, ... ,D_K \rangle : \text{ where } D_i \text{ are DFAs and } {\bigcap}_{i=1}^k L(D_i) = \emptyset \} $ is NP-Hard

texts:
The question (Prove L is NP-hard) was about proving that the following language is NP-hard:
$$ L = \{ \langle D_1, D_2, ... ,D_K \rangle : k \in {N}\text{, the } D_i \text{ are DFAs and } {\bigcap}_{i=1}^k L(D_i) = \emptyset \} $$

That got me thinking about the related problem:

$$ L' = \{ \langle D_1, D_2, ... ,D_K \rangle : k \in {N}\text{, the } D_i \text{ are DFAs and } {\bigcap}_{i=1}^k L(D_i) \neq \emptyset \} $$

I would imagine that $L'$ is also NP-hard, but I couldn't think of any reductions.. am I missing something obvious?


texts: Find the max of a convex function in fewest samples

texts:
Suppose there is a convex function, and a certain domain interval.  I want to find the max of this function within the interval.  The goal is to minimize the number of times the function is evaluated, because evaluating it is expensive.

I can think of a naive solution involving evaluating the function at two points of the interval (thereby partitioning the interval into three sub-intervals) and discarding the edge sub-interval of the point with the lower function value.  But, I am not sure whether it's optimal.


texts: Undecidable unary languages (also known as Tally languages)

texts:
An exercise that was in a past session is the following:

  Prove that there exists an undecidable subset of $\{1\}^*$

This exercise looks very strange to me, because I think that all subsets are decidable.

Is there a topic that I should read to find a possible answer?


texts: Example for the analysis of a recursive function

texts:
l is a matrix of size [1...n, 1...n]

function: rec(i,j)
  if (i*j == 0)
    return 1
  else
    if (l[i,j] == 0)
      l[i,j] = 1 * rec(i-1,j) + 2 * rec(i,j-1) + 3 * rec(i-1,j-1)
    return l[i,j]
end_function

for i=1 to n
  for j=1 to n
    l[i,j] = 0

rec(n,n)

The nested for's are O(n2). But i have difficulties to analyse the recursive part. There is another variation of this example with l as 3d. And the essential part of 3drec function is defined as:

if (l[i,j,k] == 0)
  l[i,j,k] = 2 * rec(i-1,j,k) + 2 * rec(i,j-1,k) + 2 * rec(i,j,k-1)

Anyway let's think about the 2d version again. I thought something like that (that's the running time for the whole code including the nested loops):

T(n) = T(n-1, n2) + T(n, n-12) + T(n-12, n-12)

And i'm stuck here. Besides i don't know if i did right till this point.


texts: How can I code an algorithm (concerning networks)

texts: my question is basic but I want to know how to code algorithms containing maths like this https://web.stanford.edu/~skatti/pubs/sigcomm15-spotfi.pdf , TY for your help !


texts: Computational complexity vs Computational cost

texts: Is there a difference between the computational complexity and computational cost of an algorithm?


texts: Reducing states in a finite-state machine using compatibility classes, for an incompletely specified machine

texts:
In the process of reducing the states of a synchronous finite state machine first we need to create maximal compatibility classes (of states; which states can be compatible, i.e. the "don't cares" can be set such as the states become compatible). After creating maximal compatibility classes we have to create minimal compatibility classes, starting from the maximal classes (pick just some classes, so that every state appears in at least one).

The conditions that these minimal compatibility classes have to satisfy are:

Closure (for the same input, all the states from a class have to be followed by states belonging to a same class)
If two states are in the same class and this is a condition for other two states to be compatible, the other two states have to be in the same class.

I would like to know why is the second condition necessary.

The second condition says that if states $s_i$ and $s_j$ are compatible if states $s_m$ and $s_n$ are compatible, then if $s_m$ and $s_n$ are in the same class, then $s_i$ and $s_j$ must be in the same class too. I thought of a reason and I would like to know if I am right. I will use a notation: $s_i$ compatible with $s_j$ <=> $s_i$ ~ $s_j$. So if $s_i$ ~ $s_j$ if $s_m$ ~ $s_n$ and $s_m$ and $s_n$ are in the same class and $s_i$ and $s_j$ are in different classes means that I chose the "don't cares" in such a way that $s_i$ and $s_j$ are not compatible and that means that $s_m$ and $s_n$ are not compatible anymore (they can't belong to the same class).


texts: Is there any race condition in this code

texts:
Message buffer[N]
Int in=0, out=0

send(message msg)
    while in-out==N do nothing
    buffer[in modulo N]=msg
    in=in+1
    return

message recieve()
    while in == out do nothing
    msg = buffer[out modulo N]
    out=out+1
    return msg

This is a code for a producer consumer problem. The producer produces a message and with the send function saves it into the buffer. The consumer receives that message from the buffer. The buffer, in and out are global variables. Where is the race condition here? I can't find any?


texts: An example of a non-regular grammar for a regular language?

texts: I understand that a regular language can be specified by either regular or non-regular grammars.  What is an example of a non-regular grammar for a regular language?


texts: Minimum s-t cut in weighted directed acyclic graphs with possibly negative weights

texts:
I ran into the following problem:

Given a directed acyclic graph with real-valued edge weights, and two vertices s and t, compute the minimum s-t cut.

For general graphs this is NP-hard, since one can trivially reduce max-cut to it by simply reversing the edge weights (correct me if I'm wrong).

What is the situation with DAGs? Can min-cut (or max-cut) be solved in polynomial time? Is it NP-hard and, if so, are there any known approximation algorithms?

I tried to find work on this but wasn't able to (maybe I'm just using wrong keywords in my searches), so I was hoping somebody may know (or find) something about this.


texts:
I am wondering how to get started in studying theoretical computer science and how to apply it to my programming. I am fairly comfortable with basic programming, having been programming in mainly C++ but also Java for the past couple of years, so I don't necessarily need an introduction to programming.

What I am looking for to start is perhaps something fairly broad, so that it gives a wide overview of computer science, as I don't know exactly where I want to study within it yet. But it could also be nice to have directions of where to look to continue studying a specific aspect of it. However, this is just what I think could be helpful, and I am open to any recommendations.


texts: Cycles of a multigraph with a property on the edges

texts:
Let $n$ be a positive integer. On a circle are arranged $n$ points $A_1$, $\ldots$, $A_n$. We put some arrows from $A_1$ to $A_2$, from $A_2$ to $A_3$, etc., from $A_n$ to $A_1$. On each arrow are written a string ($\textit{name}$ - so that we could distinguish all arrows from each other) and a number. How can we find all possibilities for $n$ arrows (output them with the arrows' names and numbers on them) with the following properties:

For some $1\leq i \leq n$ the first arrow is from $A_i$ to $A_{i+1}$, the second one from $A_{i+1}$ to $A_{i+2}$, etc., the $n$-th one from $A_{i-1}$ to $A_i$.

For any two consecutive arrows $R_1$ and $R_2$ (with the endpoint of $R_1$ being the startpoint of $R_2$), (number on $R_2$) - (number on $R_1$) = $1$.

(If too hard to be done efficiently for bigger $n$, a solution for $n\leq 4$ would be satisfactory.)
I can do it for $n=2$, but my approach does not generalize for larger $n$, since when $n=2$ its easy to just compare the arrows from $A_1$ to $A_2$ with the arrows from $A_2$ to $A_1$.
Any help appreciated!


texts: Amount of expected loop iterations when searching an array by random index

texts:
Lets say we have an array A of size n. It has 1 as its first index and n as its last index. It contains a value x, with x occurring k times in A where 1<=k<=n

If we have a search algorithm like so:

while true:
  i := random(1, n)
  if A[i] == x
    break

random(a,b) picks a number uniformly from a to b

From this we know that the chances of finding x and terminating the program is k/n with each iteration. However what I would like to know is what would be the expected value for the number of iterations or more specifically the amount of times the array was accessed in this program given the array A as described above.


texts: Efficiently pick a largest set of non-intersecting line segments

texts:
Given a set of line segments, how do we identify a subset of maximal cardinality where all line segments are pairwise non-intersecting?

Brute force we would get $2^n$ sets to check where $n$ is the number of line segments, so that isn't viable. Anyone got a bright idea how the do this efficiently? I tried doing it this way: remove a line segment that intersects with the most other line segments, iterate until no line segments intersect anymore; but that didn't work.

Here is a "ready to help me" place, where you can test your solution; it visualizes the set of line segments.

To try it out, please implement your attempt in the following function on the linked site:

function showAnalysis() {
    debug("Just do it");
}

and then click on the top canvas. The fiddle generates randoms segments in the top canvas, and the bottom canvas is the place where an optimal subset will be displayed.


texts: Difference between reductions in algebraic problems versus reductions in computational intractability

texts:
When I read about NP-completeness for the first time, I really wondered why is the concept of reductions given such high emphasis, after all we have been looking at concepts such as reductions and 'special case of one another problem' in mathematics since elementary algebra. What I mean by reductions in algebra is the following.

Problem 1: Find value of x such that $x^2+ax+b=0$

Problem 2: Find value of x such that $(x+m/n)^2=0$

We can go on proving both the problems are same and one solution can be translated to another.

My question is that "Is the concept of reductions in computational intractability same as that in above algebraic theory?" If not, how are the reductions in CI theory different?


texts: Fixpoints of a transformation of an extended WHILE program

texts:
I am doing some excercises to train myself in computability.
There is one that I am not able to solve, here it is.

Consider the following transformation associated to an extended WHILE program:

For all $x \in \mathbb{N}$,
$\begin{cases}
  A f(x) = x \cdot f((x+3)/2) & \text{if \(x\) is odd} \\
  A f(x) = f(x+1) & \text{otherwise} \\
\end{cases}$

How many fixed points does $A$ have?
Is there a maximum fixed point?
Find the minimum fixed point.

I know that a fixed point is a function $f$ such as $A f = f$.

I would say there is an infinite fixed point. But how to prove it?

To calculate the minimum, I would make a table with on each row: $\bot$, $A \bot$, $A^2 \bot$, ... and if there are two similar lines, that's our minimum. But once again I am not sure this is enough to do this.


texts: What is the difference between a loop and a natural loop?

texts:
Is there a difference between a loop and a natural loop?  Natural loops are defined as having a back edge to a head block that dominates it.  If you have a natural loop nested inside of another natural loop, does this mean the actual loop is the merging of these two natural loops?

I'm curious to know if there's an agreed upon distinction between a natural loop and a loop.


texts: How to encode reachability in a graph with walls as a SAT problem

texts:
Suppose we have a graph that represents a grid of cells. We are given a cell to start in and a cell that's the destination. There are cells that we cannot enter and they are known as walls. Finally we may only move to adjacent cells (diagonal movements are not allowed).

My question is how would one encode this problem in CNF to be solved by a SAT solver?

For example, let the graph represent the following 2 x 3 grid:

0 1 0
0 0 0

where 0-cells are cells we may be in or move to and 1-cells are walls. Suppose we start in (0, 0) and want to move to (0, 2). Then there is a path.

On the contrary, consider another 2 x 3 grid with the same start and destination positions:

0 1 0
0 1 0

Then this graph does not have a path from start to destination.

Clearly we may run BFS on the graph and if there's a path we can encode it as a trivially satisfiable CNF, or if there isn't then encode it as a trivially unsatisfiable CNF. For example, $A$, or, $A \land \neg A$.  However, the point of my exercise is to encode the path existence in CNF.

This is indeed part of my homework. I have been stuck for a while now. Some help on this problem would be greatly appreciated.


texts: Median of medians confusion -- the "approximate" median part

texts:
I'm struggling with the median of medians algorithm, and I think it's perhaps more of a semantics thing rather than a technical thing. I've always thought the median of medians algorithm as finding an approximate median $p$ such that $p$ is within $20\%$ of the true median $M$ in the sorted array.
However, when I look at actual implementations, e.g., in https://brilliant.org/wiki/median-finding-algorithm/, the algorithm they posted returns an exact median, but at each level of the recursion, you may have some approximate median generated from a sublist of medians. And eventually you'll reach a level where the array is $\leq 5$ elements, ending the recursion. At this level, you obtain an exact median of the array you passed in. So I had thought all this time that this exact median computed at the last level is actually your estimate of the median in the original array passed in at the first level of the recursion.
So I had the same confusion as this poster https://stackoverflow.com/questions/52461306/something-i-dont-understand-about-median-of-medians-algorithm and some others.
Now that I understand this algorithm, I am now confused on how the median of medians actually finds an "approximate" median to the original array. In all the implementations I've seen, the median you find using median of medians is exact. So where does the approximate part come in other than approximating the median at each recursion level? Even Wikipedia describes as an algorithm that approximates a median. Yes, it approximates medians at various levels, but the final output is exact.
Or am I operating under a false premise in thinking that Median of Medians finds an approximate median to the ORIGINAL array?


texts: Algorithm deciding if a radius of a graph is two

texts: Given an unweighted, undirected graph, what is the time complexity to decide if its radius is at most 2? Are there any faster algorithms than doing BFS on each node?


texts: Understanding the geometrical interpretation of word2vec

texts:
I'm trying to understand how the $word2vec$ method actually nudges word vectors of similar semantic/syntactic content closer together in the word vector space.

I've read here (Quora answer) that it's because $word2vec$ tries to maximise the probability of target word $w$ given context $c$, and that this probability is roughly inversely proportional to the distance between $w$ and $c$ in the word vector space. I don't really see why the latter is the case though.


texts: Finding largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$

texts:
I need to find largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$ where $N$ can be as large as $10^{18}$.

I tried this approach , but is too slow.
Finding the just smallest prime number to $N$, as its $\frac{\phi(i)}{i}$ value is $\frac{i-1}{i}$, which is maximum in the range. (See Maximum of ϕ(i)i\frac{\phi(i)}i)

So, I was wondering if there is any other faster way to find the maximum value. More precisely I need the value of i where $\frac{\phi(i)}{i}$ is maximum.


texts: On clarification of intersection of classes definition

texts:
How do you define $\oplus P\cap PP$?

$L\in\oplus P$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)\mod2\equiv0$.
$L\in PP$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)>\#rej_M(x)$.

Consider the classes $C_1,C_2,C_3$.

$L\in C_1$ iff $\exists\mbox{ NTM }M:\forall x\#acc_M(x)>\#rej_M(x)\mbox{ and }\#acc_M(x)\mod2\equiv0$?

$L\in C_2$ if $\exists\mbox{ NTM }M_1:\forall x\#acc_{M_1}(x)>\#rej_{M_1}(x)\mbox{ and }\#acc_{M_1}(x)\mod2\equiv0$ and $L\not\in C_2$ if $\exists\mbox{ NTM }{M_2}:\forall x\#acc_{M_2}(x)\leq \#rej_{M_2}(x)\mbox{ and }\#acc_{M_2}(x)\mod2\equiv1$.

$\exists\mbox{ NTM }M'$ such that
$L\in C_3$ if $\forall x\#acc_{M_1}(x)>\#rej_{M'}(x)\mbox{ and }\#acc_{M'}(x)\mod2\equiv0$ and $L\not\in C_3$ if $\forall x\#acc_{M'}(x)\leq \#rej_{M'}(x)\mbox{ and }\#acc_{M'}(x)\mod2\equiv1$.

Which of $C_1,C_2,C_3$ defines $\oplus P\cap PP$ and which one $\oplus P\wedge PP$? What about last one?


texts: Finding a vertex coverage that is also an independent set

texts: Given a graph $G$ and integer $k$, find a vertex coverage set of size $k$ that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea?


texts: The expectation of the total number of pairs of keys in a hash table that collide using universal hashing

texts:
I am reading CLRS relating to perfect hashing. When computing the
$$
\mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}]
$$

where $m$ is the number of slots in the hash table, and $n_j$ is the number of keys in position $j$. I don't understand why we can directly conclude that

$$
\mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}]\leq{n\choose{2}}\frac{1}{m}
$$

I understand that since $h$ is randomly chosen from a universal hash function family, $\Pr{(h(x_i)=h(x_j))}\leq{\frac{1}{m}},\forall{i\neq{j}}$. I don't understand why we can use the total number of pairs (the combination part) directly because if $h(x_i)=h(x_j)$ and $h(x_j)=h(x_k)$, then we have $h(x_i)=h(x_k)$ immediately instead of a probability of $\frac{1}{m}$.

Someone can help me out? Thanks!


texts: Who was the first to show that there is a Universal Turing-Machine that uses a binary alphabet?

texts:
The title says it all, I think.
We know there are universal Turing-machines that only use a binary alphabet.  But who proved this first?
Turing himself showed the existence of a universal Turing machine ... but did he also show that such a machine can exist using only a binary alphabet? Or was that someone else?
Or was it just 'obvious' to him and others that this would be the case, and hence no explicit 'first' proof or publication of this result exists?
Of course, it is obvious that you can represent any number using binary.
But, first of all, Turing-machines can compute things about things other than numbers. Indeed, all that matters is that the Universal Turing-machine is able to represent, in binary, whatever symbol set the Turing-machine to be simulated is using, and a program, again in binary, that describes the state-transitions of that machine-to-be-simulated. Of course, since all of those things are enumerable, all representations of those things can still be done in binary, that is still fairly obvious.
But what is far less obvious to me, is that you can do all the computations on those represented objects still using only two symbols. For example, you'll need some way to indicate separations between the objects, and as those objects change (e.g. when the machine-to-be-simulated changes a symbol on the tape), you'll need to change the corresponding binary representation, and since they are of variable length, you'll need to constantly shift the location of those objects on the tape that the Universal machine is working with.
Indeed, to me the tricky part is to come up with some clever way to encode any kind of Turing-machine and input tape that the Universal machine will take in at its input, and to somehow simulate the behavior of that machine, keeping track of what state that machine is in and where it is on the tape, again, all with just two symbols. Yes, we now know it can all be done, and I successfully went through this exercise myself. However, I thought it was all rather less than obvious.
Of course, I am no Turing ... and so was it obvious to Turing that it could be done? Reading his paper, I don't think Turing really proves this .. or even considers this. In his paper, for example, he still uses special symbols (i.e. not 0 or 1) to, for example, indicate the left boundary of the simulated tape.  But was it still so obvious to Turing that it didn't even deserve mentioning?
So, let me put it this way: is there a publication that can be considered the 'first' proof of the result that you can have a dully binary Universal Turing machine? I would be very interested in knowing what that is.
Thank you!


texts:
I've been reading these:

Fast Reduction from RSA to SAT
CNF Generator for Factoring Problems (Also have C code implementation)

I don't understand how the reduction from FACT to $3\text{-SAT}$ works. Are there any simple articles in which I can read about it?

My final goal is to eventually implement a reduction from $3\text{-SAT}$ to the undirected Hamiltonian circuit problem.


texts: Subset selection with maximum sum and minimum variance?

texts: So I am trying to tackle a combinatorial optimization problem and would like some insights on how to approach it. The problem statement is as follows: Consider a set of elements of size N, how do I select a subset of size k<N such that the sum of the elements in the subset is maximum and variance among the elements is minimum. Lets consider an set of 10 integers: [29, 63, 83, 50, 67, 45, 52, 66, 75, 13] . Suppose I want to select a subset of 4 integers, then one possible solution can be [67, 29, 63, 83]. I obtained this solution by forming all possible subsets of length 4. Then I calculated the variance and sum of each subset and chose the subset with minimum variance/sum ratio. Instead of brute-forcing it how can I solve the above mentioned problem efficiently?


texts:
I have the following program

x := y + 1;
if (y > 0) then
x := x + y
else x := y + 100;
x := x + y;

I want to compute the weakest precondition for getting {x = y} by executing this program.

The solution of this problem is the following

{(y > 0 & y + 1 + y = 0) | (y = -100)} = {( y > 0 & y = -0.5 | y = -100} = {false | y = -100}
x := y + 1;
{(y > 0 & x + y = 0) | (y =< 0 & y=-100)} = {(y > 0 & x + y = 0) | (y = -100)}
if (y > 0) then
{x + y = 0}
x := x + y
{x=0}
{y + 200 = 0} = {y = -100}
else x := y + 100;
{x=0}
{x+y = y} = {x=0}
x := x + y;
{x=y}

Can anyone explain this solution with a breakdown for each line?


texts:
Is there a linear time algorithm that, given a string of length n, tells if it is a sequence of non overlapping palindromes (each of even length, in a binary alphabet)?? I found algorithms that return the longest palindrome, but this does not apply since a string like "aabbaabb" should be accepted since it can be divided in four palindromes.

I can't come up with an idea that works in linear time since I think that there could be cases in which a certain factorization is not a sequence of palindromes but another one is.


texts: I am looking for open problems in complexity theory that an undergrad might have any possibility of tackling.


texts: Polynomial time reducibility is an equivalence relation

texts:
How do I prove the following statement?

The relation $≤_p$ (polynomial time reduction) is an equivalence relation.


texts: Why is it not possible to prove the equivalence of nondeterministic and deterministic Turing Machines the same way as for NFAs and DFAs?

texts:
I found en excercise asking this question.
I know that for proving the equivalence of NFAs and DFAs we can use the conversion through subsets, and that for proving the equivalence of nondeterministic TMs and deterministic ones we can build a 3-tape deterministic TM M which emulates the steps of a given nondeterministic one, let's call it N, proceeding this way:

It copies the input string of N on the first tape
On the 2nd tape, for each $i$th step of computation of N it produces a maximum of $d^i$ strings of length $i$ consisting of sequences of numbers between $i$ and $d$ representing the possible nondeterministic computations of N where $d$ is the nondeterminism degree of N
For each of the above strings, it copies the content of the 1st tape on the 3rd tape and it tries every nondeterministic choice represened by its symbols, one by one

Basically M does a breadth first search on the tree of the computations of N, so if N has an accepting configuration on a computation path, surely M will find it because it will travel that path sooner or later.

So, for answering the question, I thought that the main reason is that a Turing Machines has a tape whereas a finite state automaton not so we can't use the same procedure used for converting a NFA into a DFA. Is it a sufficient answer? Should I mention that a Turing Machine isn't guaranteed to halt on any input too? How would you answer? Thanks in advance.


texts: Necessity to define co-NP in the first place?

texts:
I've recently started to deal with complexity theory and I'm trying to wrap my head around all the definitions and why they make sense.

One thing I don't quite understand is the importance/necessity of co-NP as its own set/class of problems. Couldn't for example TAUT be classified as a NP-complete problem just like SAT or is there some specific motivation to not put complements of a problem in the same set as the problem itself?

I'm sorry if this has been asked before or if my question is silly and doesn't make sense at all (In this case I'd like to know why if possible), I've really tried to look for it beforehand on the internet.

Kind regards,


texts: Does my simple, static hash table have O(1) worst case lookup?

texts:
Will the following simple hash table construction algorithm be able to construct a
static hash table in $O(n)$ expected time, and will the worst case access time be $O(1)$? If not, what are the problems, and is there a simple solution?
Construction
Let's assume we have a static set of $n$ keys.
We also have a fully random universal hash function $h_i(x)$ (let's say we use SHA-2 with $i$ as the IV).
Now we try to partition the set of keys into $m$ buckets, where $m = \lceil n/100 \rceil$.
First we try with $i$ 0. If one bucket has more than 1000 entries
(this is possible, but extremely unlikely, much less likely than to get a SHA-2 hash collision), start from scratch, that is re-build the hash table but use a different hash function, that is $h_1(x)$. Do this in a loop until we find an index $i$ that works.
Now the largest bucket has less than 1000 entries.
Each bucket is stored as a list, sorted by hash value.
The index $i$ is also stored.
Evaluation
For the static hash table constructed above, with the stored index $i$, calculate $h_i(x)$. Calculate the bucket, and in this bucket, do a binary search. I believe (hope) that this is an O(1) operation, because there are at most 1000 entries in this bucket.
Closely related: (When) is hash table lookup O(1)?. But I have a static set, and I have a fully random universal hash function. I know about FKS hashing, but I can't use it in my case, because it would require too much memory, and I would like to have a simpler algorithm. I understand my algorithm is terribly inefficient, but I'm mostly interested in a guaranteed $O(1)$ worst case access time.


texts:
I have a simple question regarding reduction using K-Maps.
My professor gave this example:

While I somewhat understand that we can only group quantities of base 2 numbers, why did my professor group the K-Map values like the image above instead of the image below (what I drafted):

Why did my professor include elements 0 & 1? Why not just a group of 2 consisting of elements 4 & 5?
Thank you very much.


texts:
I'm trying to sort out in my mind the different ways of assigning semantics to a programming language. There are two main methodologies: operational semantics and denotational semantics (I asked a previous question on the relationship between the two).

It seems to me that an operational semantics is the same as defining a dynamics for the language - that is, defining how programs are evaluated. I know two different ways of doing this: equational and structural.

A structural dynamics defines evaluation via a system of transition rules (I believe beta reductions are the canonical example). An equational dynamics only specifies reductions indirectly, by defining when one expression is equal to another. (I'm going through the trouble of defining these terms because I am uncertain how standard the terminology is).

But I can't figure out why both systems are needed. I personally prefer structural dynamics, but it feels very subjective. What are the advantages and disadvantages between the two systems?


texts:
I'm studying for my computing languages and I have some problem on getting the production rules from a push down automata.

The automaton accepts all strings over alphabet $\{e,k,q,y\}$ of the form $w\,kyyk\,w'$ such that $|w|=|w'|$.

There are the productions rules I get.

S -> QkyykK
Q -> qQ
Q -> yQ
Q -> eQ
Q -> kQ
Q -> epsilon

K -> Kq
K -> Ky
K -> Ke
K -> Kk
K -> epsilon

I don't understand how to have the same number on the left and on the right. Hope anyone can help me or explain me cause I am having so problems with that exercice. I use jflap for testing if it's accepted or rejected.


texts: How to prove the NP-completeness of MOD-PARTITION

texts:
MOD-PARTITION: Given a set of integers $A={a_1,...,a_n}$, their weights $w = \{w_1, w_2, \dots, w_n\}$ and the number $k$, does there exist a subset $X$ of $A$ such that: $(\sum_{x \in X} w(x) * x) \mod k \; = \; (\sum_{a \in A \setminus X} w(a) * a) \mod k$?

Can some please provide some idea on how to prove the NP-Completeness of this problem? I saw the proof of the set-partition problem (using a reduction from subset-sum) and I suppose, that this proof maybe will be some little modification of it.


texts:
In CLRS book, in the road cutting example there is a recursion formula

$$
    1+\sum_{j=0}^{n-1}T(j)
$$
and it can be proved that the sum is
$$
    2^n
$$

by simple induction. In 3-rd edition it is a formula 15.3 on a page 364.

As I can understand from the recursion-tree aproach, the recursion tree which can be built for the said problem is
$$
    1->(n-1)->(n-2)|each.node->(n-3)|each.node->...
$$

and so on, which can be summed as
$$
    \sum_{j=1}^{n-1}[\Pi_{k=1}^{j}[(n-k)]]
$$

How can I come up with the suggestion of $2^n$ from this recursion tree (or why this tree is wrong and what can be the right approach to suggesting $2^n$ running time)?


texts: What does it take to massively parallelize a flow matrix equation?

texts:
I'm not a scientist nor am I math savvy, but I'd like to know what the feasibility would be of solving a shallow water flow equation using massive parallelization. CUDA and stuff like that.

Im referring to this paper: http://www.3di.nu/wp/wp-content/uploads/2014/03/Stelling_ice_2012.pdf

Would such an algorithm be suitable for parallel computing?


texts: The number of connected components in the context of cyclomatic complexity

texts:
Cyclomatic Complexity is defined with reference to the control flow graph of the program through this formula (borrowed from Wikipedia):
M = E − N + 2P,
where
E = the number of edges of the graph.
N = the number of nodes of the graph.
P = the number of connected components.

I can't understand the last. What is "the number of connected components" in this context? Wikipedia itself uses the notion of (connected) components in relation to undirected graphs only.
There is also the concept of strongly connected component: a directed graph is said to be strongly connected if every vertex is reachable from every other vertex. So one can guess that the number of connected components is the number of strongly connected components of the control flow graph. Is it right? If not, can someone provide samples of control flow graphs with differerent numbers of connected components?


texts: Can a language with some set of higher-order functions like map, fold and filter but without recursion or iteration be Turing complete?

texts:
I was reading this article and was wondering if there is any finite set of higher-order functions like map, fold or filter such that they could empower a language to be Turing complete even without having explicit constructs for recursion or iteration. Obviously the higher-order functions would be implemented with recursion or iteration, but the requirement is that recursion or iteration could not be directly exposed to the programmer. That is to say, recursion or iteration can be baked in a finite set of pre-defined, built-in higher-order functions, but the language must not have an explicit construct for iteration or recursion. The set of higher-order functions can be arbitrarily large, but must be finite.

Alternatively, if the answer is no, which is the biggest set of problems that could be computed by such a language? Is that set a known set (eg. equivalent to pushdown automaton)?


texts: An error on Introduction to Algorithms 3rd edition about closest pair of points

texts: In the book Introduction to Algorithms of Cormen 3rd edition page 1041 about of Closest Pair of Point divide and conquer algorithm, Is there an error? It's said: "...Create an array Y', which is the array Y with all point not in the 2$\delta$-wide vertical strip removed...", it should be: "...Create an array Y', which is the array Y with all point in the 2$\delta$-wide vertical strip removed..."?


texts:
Rules: A conveyor belt is giving you little boxes. They are labeled for your convenience: Box $1$, Box $2$,... For your inconvenience, though, you can't see the number (from $1...n$) hidden in it. You can sort the boxes into $n$ bins as you like. You may pause the belt at any time to resort the boxes. As soon as one bin contains a minimum of $k$ boxes (or more, doesn't hurt) all with the same number in it, and no other number in that bin, a siren goes off and you are declared programmer of the month. :-)

Here is a very stupid but surefire algorithm: Fetch at least $n(k-1)+1$ boxes and try out all permutations with $k$ boxes in bin 1 and $k-1$ in the rest of bins, in any order.

I guess you can do better than $O((nk)!)$?


texts: Minimum cost of "signal" cover in a tree with DP

texts:
I'm given a (not necessarily binary) tree. Now every node can have a signal with range $i$, reaching all nodes being at most $i$ edges away. The cost of a signal is determined by a function $f(n, i)$ with $n$ being a node and $i$ being the signal strenght. The cost for each node may vary, the only assumption one can make is that $f(n, i) \geq f(n, j)$ for $i > j$.

I need to find the minimum cost to cover the whole tree.

Example:

For $f(n, i) = (i + 1)^2$, the minimum cost would be 7:

Setting a signal with strenght 0 for every node covers the whole tree for the cost of 7. Setting a signal with strenght 1 for the nodes $b$ and $c$ covers the tree for the cost of 8 and setting a signal with strenght 2 for node $a$ results in a cost of 9.

Using Dynamic Programmming this task should be achieved in $O(n^2)$. This is an assignment so I'd be grateful for tips.


texts: What is the algorithmic complexity of DFS under the cache oblivious model?

texts:
Consider the basic non-recursive DFS algorithm on a graph G=(V,E) (python-like pseudocode below) that uses array-based adjacency lists, a couple of arrays of size V, and a dynamic array stack of size <= V. If I understand correctly, this is a cache oblivious algorithm since no information about the memory configuration is provided. Moreover, even if we suppose that every memory access in this algorithm produces a cache miss (the number of cache misses per line is given in comments), we would still have O(V+E) memory transfers, so I postulate this would be a worst case complexity upper bound under the CO-model. Is this correct?

def dfs(G, s):
    visited = [False for v in G] # V
    stack = [s] # 1
    nxt = [0 for v in G] # V
    degree = [len(v) for v in G] # V + E
    while stack:
        v = stack.pop(-1) # 1
        visited[v] = True # 1
        while nxt[v] < degree[v] and visited[G[v][nxt[v]]]: # 6
            nxt[v]+=1 # 1
        if nxt[v] < lens[v]: # 2
            stack.append(v) # 1
            stack.append(G[v][nxt[v]]) # 3

def main():
    #  e.g. dfs order of this graph is 0 1 2 3
    #
    #  0 -> 2
    #  | \  ^
    #  |  \ |
    #  v   v
    #  3 -> 1
    #
    G = [[1,3,2],[2],[],[1]]
    dfs(G,  0)


texts: experimental analysis of running times in extendable table

texts:
I was given the following homework question:

  Implement an extendable table using arrays that can increase in size
  as elements are added. Perform an experimental analysis of each of the
  running times for performing a sequence of n add methods, assuming the
  array size is increased from N to the following possible values:

  2N
  N + ceiling(√N)
  N + ceiling(log N)
  N + 100

I'm just a little confused about what this question is asking, and was hoping for some help/clarification. The way I understand it, you could implement something like this in Python with a two-dimensional array (the "extendable table"), and then append varying numbers of values for each scenario. Am I understanding the implementation correctly?

Then, I'm also a bit unclear on what number of values you'd be appending. Would you literally first test it with say, 16 values, then 32 (2N), then 20 (ceiling(√N)), etc? Or is it more complex than that?
Any help is appreciated!


texts: How is the space hierarchy theorem different for non space constructible functions?

texts:
Sipser first introduces space constructible functions. Then uses the definition to prove the space hierarchy theorem:

  if f(n) is a space constructible function then there are languages that can be decided in O(f(n)) space but not in o(f(n)) space.

The author only mentions as most encountered functions are space constructible, it is a good assumption. Are there any cases where non space constructible functions of are interest ? How does the space hierarchy theorem changes under such conditions ?


texts:
As far as i understand all loops have a loop invariants. My understanding is that loop invariant is an argument that is true at the beginning of the loop block as well as at the end of the loop.
For example:
while(P) {
  //predicate is true here
  body of the loop
  //predicate still true here
}

But let`s say i have the following loop (the code is in Java):
while(stack.size() > 0 && stack.peek() < 0) {
   stack.pop();
}

What i am trying to do here is to pop all negative numbers from the top of the stack - so at the end of the loop at the beginning of the stack will be a positive number or we have an empty stack.
It is not clear from this loop what its invariant?
What technic we can use to get loop invariant. In general, i would like to use loop invariants for validation of program correctness.


texts:
Let $L_1, L_2 \subseteq \Sigma^*$ be two languages, where $\Sigma$ is some finite Alphabet.

Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$?

What if $L_1$ and $L_2$ are regular languages?

Can you give counterexamples?


texts: Do all processes are allocated equal sized page map tables?

texts:
I have a simple question :
In a paged memory system, all processes are allocated equal sized page map tables ?


texts:
My competitive programming coach told me of a balanced binary tree used by a lot of Chinese competitors that has all the functions of any other balanced binary tree and is fully persistent and runs queries and updates in ${O(log^2N)}.$ What information is there on this tree, and does it go by a different, more popular name?

To be clear, any data structure that fulfills the above will be considered as a correct answer. The first one will be marked correct. If there is a link, that would be the best.


texts: What kinds of recurrence relations can be involved in a tabulation solution?

texts:
We all know F(n) = F(n-1) + F(n-2) is an easy example. We can compute this by using DP.

But what about F(n) = F(n-1) + k, we could compute this by tabulation but would you still call it DP?

Also, are there any recurrences that cannot be computed using tabulation?

Is there a general theory surrounding the kind if recurrences that can be effectively computed using tabulation / DP.

Thanks in advance.


texts: Understanding the Linear speedup theorem and how strong it is

texts:
Let $k \in \mathbb{N} $ and define the language $L = \{ n,m | n^k = m \}$

Consider a (deterministic) TM deciding $L$ then it has to compute $k$'th power which will take $f(|n|+|m|) + h(k)$ time in worse case for some polynomials $f,h$. now, by the Linear speedup theorem we can improve this to $\frac{f(|n|+|m|) + h(k)}{h(k)} = O(f(|n|+|m|))$
This means that for whatever $k$ we choose there is a (deterministic) TM deciding it in $O(f(|n|+|m|))$ even for cases $|n+m|<<k$. And this seemingly doesn't make sense, because it leads me to the fact that for every two choises of $k$ there are TM's deciding the corresponding languages in the same running time. What am I missing here?


texts: Closure properties of finite state transducers

texts:
Given $T_1, T_2\colon \Sigma^* \to \Gamma^*$ ($\Gamma$ is output alphabet), let $\Delta(T_1, T_2)$
      consist of all input strings $w \in Σ^*$ where $T_1(w) \neq T_2(w)$.
      Prove that FSTs are not closed under this operation $\Delta(T_1,T_2)$.

What I have tried is to create two FSTs $T_1, T_2$ (as 5 tuple functions of form  $(Q, \Sigma, \Gamma, \delta, s, γ)$  where $\Sigma$ - input symbols, $\Gamma$ - output symbols, $δ\colon Q \times \Sigma → Q$ transition function, to prove that the language $S = \{ w \mid T_1(w) \neq T_2(w) \}$ is not regular. I am having trouble creating the two FSTs. Especially defining the transition functions for the two FSTs. Any help with this is appreciated.Pretty much what I am trying to prove is there are two FST's $T_1$ and $T_2$ such that the language $L = \{w \mid T_1(w) \ne T_2(w)\}$ is not regular. To prove this, what I want to do is create the two FST's $T_1$ and $T_2$. I am not sure on how to define a 6-tuple FST. Especially coming up with the transition functions for the two FSTs


texts:
I was reading the book "The singularity is near" written by Kurzweil and he mentioned the reversible gates like for example the Fredkin gate. The advantage using such gates is that we could get rid of the thermal waste related to computation where bits just disappear into heat, and computation won't need any energy input. Those assumptions make these gates sound like a miracle solution. So the question is what technical hurdles are still preventing their large scale usage.

I also think it is a shame that I never heard about those gates in my electrical engineering bachelor and master studies at a top German university...


texts: Algorithm: Calculate every number in a given list using addition and numbers you've created

texts:
I'm creating an algorithm to calculate every number in an array using only addition and numbers we've created - in the shortest amount of steps. That's confusing so here is an example:

input: [5, 11], used numbers (start with 1): [1]
1+1=2, used: [1, 2]
2+2=4, used: [1, 2, 4]
1+4=5, [1, 2, 4, 5]
5+5=10, [1, 2, 4, 5, 10]
10+1=11, [1, 2, 4, 5, 10, 11]

We have hit 5 and 11 so we are done in 5 steps. There are other ways to get [5, 11], eg. [1, 2, 3, 5, 6, 11]. They are the same amount of steps. Imagine we have input [5, 11, 20]. Now it matters which we choose above because [1, 2, 4, 5, 10, 11] only requires one more step, 10+10.

The input can be hundreds of numbers. Certainly I can't attempt every possibility. I was thinking about an "elegant" solution using prime factors. If my input is [16, 30, 36, 40], does it help me to think about this as [2*2*2*2, 2*3*5, 2*2*3*3, 2*2*2*5]? I'm not sure. I've also thought about using the differences of each input, eg. [16, 30, 36, 40] would give me [14, 6, 4, 20, 24, 10], but I'm not sure how to use that either.

Any thoughts?


texts:
I'm studying the Sipser textbook for my theory of complexity class. In a part of the book (i.e., Space Complexity chapter), for showing that Generalized Geography game is PSPACE-complete, the author has given an argument to model this game with TQBF problem (which is proven to be PSPACE-complete).

In a step of the argument, he has tried to construct a directed graph by using the definitions of TQBF problem (universal and existential quantifiers). What he has come up with is the following graph:

I have some questions about this graph:

I, actually, don't get it why the diamond structure has been used for showing choice possibilities of player $x_i$. Couldn't we use a simple structure like what we do on binary trees?

How would it be if we use a hexagon shape instead of diamond for showing choices of $x_i$?


texts: Algorithm to extract line-like contour in 3d

texts:
Hello people on the internet,

I'm currently searching for some kind of fast algorithm that allows me to extract curves in three dimensional space that arise as the intersection of two level sets of smooth functions, i.e.
\begin{align*}\mathcal{C} = \{\vec{x} \in \mathbb{R}^3 | \; F(\vec{x})= l \; and \; G(\vec{x})=s \} \end{align*}

I was thinking that something similar to marching cubes might work, but not having a computer science background I'm struggling to make out if and how that would look.
Does anyone have a suggestion on what I could do?

Edit: I currently use a very inefficient solution where I compute one isosurface with a preimplemented python method on a 3d grid, then check the isosurface for wanted values of the other function (walking along curves in slices of the surface and checking for crossings of the value) and collect all such points. In the end I group them with a clustering algorithm.

Edit2: In my specific case, the functions are defined with a few random parameters for some finite natural $N$, which are $\varphi_n \in [0,2\pi), A_n \in [0,1], \vec{k}_n \in S^2$ (the unit sphere) and are restricted to a three-dimensional cube of some size $a$.
\begin{align*}F(\vec{r}) &= \frac{1}{T} \sum_{n=1}^N A_n \cos(2\pi \vec{k}_n \cdot \vec{r} + \varphi_n) \\
G(\vec{r}) &=  \frac{\partial_z F}{|| \nabla F ||}  \end{align*}
for some normalization constant $T$. I want to work with the intersection curves (that I made out to generally be several disconnected ones) for different parameters.


texts: Finding shortest path from a node to any node of a particular type

texts:
I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is to find the shortest path from A to any such node, if it exists.
This can be achieved by doing a breadth first search which would give the shortest distance between A and the desired node if it exists. Given that the graph can be pretty dense, what could be a better algorithm to achieve this? Both memory and time taken for the search are to be kept in mind while designing this.

If such queries could be optimized by doing some pre-processing while the graph is built, such additional hit on performance could be acceptable (not memory though).


texts: Algorithm to find a subgraph such that all of its edges has an anti edge

texts:
Let $G=(V,E)$ be a directed graph. The "invertible" part of $G$ is the subgraph $H=(V,E_2)$ such that $(u,v)\in E_2 \iff (u,v)\in E \land  (v,u)\in E$.
Find an algorithm that generate $H$ from $G$ in a linear time, where $G$ is represented with an adjacency list. Non linear memory is allowed.

Obviously the brute force approach won't be linear, and I thought to use an adjacency matrix but that would be at least $\Omega (n^2)$.
I also thought maybe it's possible to create a forest of DFS trees and then, checking each edge if it has an anti edge would be a lot more easier, but I'm not sure if it would be possible to keep all the information from the original graph...
Another way is to generate the anti graph of $G$, then intersect it with $G$ and then subtract the intersection from $G$, we'll be left with all edges that didn't have an anti edge, it sounds too complicated too work in linear time though and I'm not sure how to implement this algorithm..
Am I on the right track? Is there another way?


texts: Why does taking a gamma value > 1 make the image darker?

texts:
If I've understood gamma correction correctly (and I probably haven't), a gamma transform to an image raises the value of the intensity level of the input pixel to the power of gamma, where gamma can be greater than one or less than one.

Pout = (some_constant) x Pin^(gamma)

In every example that I've seen, a gamma value < 1 makes the image lighter (raises intensity of lower intensity pixels) and a gamma value > 1 makes the image darker. This seems counter intuitive to me since a gamma value > 1 should increase the intensity levels of all the pixels making it lighter and more saturated.

Can someone explain this to me? Where am I going wrong?


texts: Evolutionary algorithm for the Physical Travelling Salesman Problem

texts:
I want to solve the Physical Travelling Salesman Problem using an evolutionary algorithm.

The objective of the PTSP is to visit the maximum number of waypoints of the map in the minimum number of time steps.
The map takes the form of a two-dimensional board, where ten waypoints are scattered around and multiple obstacles are present.

Now, I have a way to run random games and create "population" — a list of waypoints in the order we visit them.
I need some idea how to do the crossover. I mean, how to create the next generation.
I saw ideas, but they take in account that each gene contains all the waypoints on the map. (Take a random part from parent1 and take the waypoints that do not appear in parent1 from parent2 in the order they appear in parent2).
What to do in case a gene contains just part of the waypoints?


texts: How to prove a Language is neither a Computably enumerable nor Co-Computably enumerable?

texts:
What would be the general approach for that? And what are the things that generally overlooked while proving such things?

For example,

I have a Language, L ={e:$L(M_e)$ such that it accepts only 'a where a$\in \sum^{*}$}?

Is it possible,
1. To prove its not a CE, Can we reduce $(Acceptance\space problem)^{complement}$ to L?
2. To prove its not a Co-CE, Can we reduce Acceptance problem to L?


texts: Existence of suitable pseudo-random number generators to derandomize BPP to P

texts:
I am struggling to understand how the known oracle, and conditional derandomization results connecting $BPP$ and $P$, relate to each other.

My understanding is that if there is a suitably strong pseduo-random number generator that only uses $O(\log n)$ seed bits, then we can derandomize $BPP$ to $P$ by simulating $BPP$ machines in polynomial time using the random number generator and looping over every possible seed.  If I understand correctly, the "suitably strong" details were made explicit with Impagliazzo-Wigderson's conditional result that unless $E$ has sub-exponential circuits, $P=BPP$ by way of simulating $BPP$ machines with a pseudo-random number generator.

However, it is known that there is an oracle to which $P^A \ne BPP^A$.

While I understand that this does not imply $P \ne BPP$, cannot we at least say that this means that $P$ cannot simulate $BPP$ machines? Because if $P$ could just simulate $BPP$ machines directly, then it could also access the oracle $A$ in exactly the same way as $BPP$, and it would not be possible to get an oracle separation.

So putting this all together, why can't we say that Impagliazzo-Wigderson's result actually proves $E$ has sub-exponential circuits?

Or alternatively worded, doesn't the oracle separation prove no "suitably strong" pseduo-random number generator exists that would allow derandomizing $BPP$ by just simulating it in polynomial time?

It's possible I'm missing something subtle, but I have a feeling I'm actually just way off the mark. So please help me understand what is going on here.


texts: Why can't fractional cascading be used on two unrelated arrays?

texts:
According to both Wikipedia and my professor (see question 5.1), fractional cascading has to be done on arrays with related data.

The specific question:

  A fellow student wants to compactly store A1 and A2 to support efficient range reporting queries on both arrays using a single binary search. He suggest using fractional cascading (as described in the lecture). Explain why this will not work.

I cannot understand why this will not work.

If we want to search for a specific key in both arrays, why does it matter if the data is related or not? If we have built a relationship between the two arrays, s.t. we can follow a pointer to a predecessor for a given index in A1, is it not irrelevant?


texts: Why is the halting problem unsolvable by a turing machine?

texts:
So my knowledge of CS is amateurish at best but to me, logically, it seems like the halting problem is solvable.

So any human can determine if a problem halts with rigorous inspection, so why can't a very advanced, say human AI, solve the halting problem?

Also, is there a machine, say more powerful than a turing machine, that can solve this problem?

PS: I might be making some bad assumptions, please point that out if so.


texts:
I'm reading a computer science paper, this one: https://arxiv.org/abs/1608.03960. It uses certain notation in one of the illustrations (Figure 9, page 8 in the PDF version) that I don't understand how to interpret.
Attaching here as well for better visibility:

$$ \text{EXEC} ~ \frac{\text{cmd}_1 : \text{CMD} \quad A_p, \text{cmd}_1 \implies A^\prime_p}{A_p, \langle \text{cmd}_1 ~ ; ~ \text{cmd}_2 ~ ; \ldots \rangle \implies A^\prime_p, \langle \text{cmd}_2 ~ ; \ldots \rangle} $$

I've tried to search for this online, but haven't come up with anything. I'd appreciate if someone explain it to me, particularly these questions:

Does this notation has an official or widely recognized name?
What's the relationships between expression above and below the horizontal line?
What's the meaning of $\Rightarrow$, long arrow?
What's the meaning of two expressions being separated by a comma, as in $A_p, cmd_1$? How is it different from two expressions separated by a blank space, as in $$\mathrm{cmd}_1, \mathrm{CMD}\ \ \ \ \ \ \ \ A_p, \mathrm{cmd}_1\,?$$

Here's another example from the paper:

$$ \text{VAR} ~\frac{x \in \text{dom}(A_p)}{A_p, x \implies A_p(x)}$$

What's the meaning of $dom(A_p)$ here?


texts: Intuition for Church-Turing thesis for Turing machines

texts:
I can very clearly see "why" mu-recursion is a universal model of computation, i.e. why the Church-Turing thesis -- that any physically computable algorithm can be executed with mu-recursion -- holds for mu-recursion. It reflects exactly the type of algorithms that I can carry out with my own brain.
I cannot see an analogous intuition for understanding why the Turing machine can execute any physically computable algorithm -- i.e. how did Turing "see" that the Turing machine was a good definition to use? Is there a good way to "imagine" the algorithms I perform in terms of the Turing machine, as opposed to general recursion as I am used to?


texts: Traveling salesman problem - negative distances allowed

texts:
I am interested in the following version of TSP:

Assumption: TSP where the distances are non-negative. We know the algorithm A which computes the optional solution for such instances of TSP.
Task: State an algorithm that uses the algorithm A and computes an optimal solition for instances where negative distances are allowed.


texts: Is "Extended Church-Turing Thesis" the same as "Cobham-Edmonds Thesis"?

texts:
I have been looking for any reference regarding the term: "Extended Church-Turing Thesis" [some people will call it,  Strong Church–Turing Thesis]?  Does anyone defined it or it is just people in computer science believed it long years ago.

I read some articles and no one put reference for who defined it.
for example:

In wikipedia, they write, "The extended Church–Turing thesis, which is not due to Church or Turing, but rather was realized gradually in the development of complexity theory".
In book, titled "An introduction to quantum computing" Nothing about reference of this term.

I can go for many pages without explicitly writing the reference of this term.

Thank you.

EDIT: I found this paper which refers to this old paper from 1986: Parallel speedup of sequential machines: a defense of parallel computation thesis by Ian Parberry. In the second page, he wrote, [Similarly, the sequential computation thesis [10] states that time on all "reasonable" sequential machine models is related by a polynomia.]" Sequential computation is the one that can be computed in logical order (from top line to bottom line without doing something else during this computation). So, sequential computation thesis looks like "Extended Church-Turing Thesis", since it says that time on all reasonable "like randomized or any other models" is related by a polynomial. I believe that reference [10] is the one that initiated this term. Reference [10] is: L.M. Goldschlager and A. M. Lister, Computer science: a modern introduction, PrenticeIlall, 1983. So, it is a book. I did not find any copy of this book, so I cannot verify this information. But I think it is clear now. Don't agree!

EDIT2: in Goldreich's textbook "P, NP, and NP-completeness - the basics of computational complexity", Goldreich states the following about The Cobham-Edmonds Thesis,

  The Cobham-Edmonds Thesis asserts that the time complexities in any two "reasonable and general" models of computation are polynomially related. That is, a problem has time complexity t in some "reasonable and general" model of computation if and only if it has time complexity poly(t) in the model of single-tape Turing machines.

I don't understand why people did not notice that Cobham-Edmonds Thesis is the same as Extended Church-Turing Thesis?


texts:
I'm numbering generated files with two digits 00-99 and I want to retain the last 50.
The algorithm should tell me the number of the current file that I'm about to save and which of the previous files to remove.

If I scale it down to a toy version with one digits, here's how I want it to behave.

As long as there are fewer than 5 files, we can just add files.
This is represented in the first block below.
Once there are 5 previous files, the oldest one should be deleted.
This is trivial as long as we haven't reached the maximum number, here 9. This is represented in the second block below.
Once the highest numbers has been reached, the numbering should roll around, and here is where things get tricky. See the third block below.

__prev__    __curr__   __drop__
<no files>     0         null
0              1         null
0 1            2         null
0 1 2          3         null
0 1 2 3        4         null

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

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

Some pseudocode to illustrate my progress:

if length(prev) < 5
   curr = length(prev)
   drop = null

else

if 9 not in prev
   curr = (1+max(prev)) mod(10)
   drop = curr-5

if 9 in prev

... and this is where I'm stuck. I've experimented with subtracting 10 from each element in prev.

I'm sure it's trivial and that It'll hit me when I least expect it. I also have a nagging feeling I'll find an expression that generalizes both cases (with and without max in prev).


texts: Why can't we exploite finiteness to prove incompleteness in NP?

texts:
It is well established that the class of recursive languages is strictly contained in the class of recursively enumerable languages (Rec $\ne$ RE). Any finite language is decidable and hence can not be RE-complete. My intuition is that an RE-complete language contains infinite number of (finite) strings (information) and can not be reduced to a finite language.

The situation is different for the class NP since we can not rule-out finite NP-complete languages. If P=NP then there is some finite NP-complete language (under Karp reduction).

  Is there an intuition (or evidence) that explains why finite languages can not be complete for NP?

I am looking for an intuition (evidence) that supports the conjecture that all NP-complete languages must be infinite (It should not assume anything about P vs NP). Different notions of completeness inside NP may have significant impact on the properties of complete languages inside NP.

This was moved from a comment. Finiteness of complete languages shifts the focus on using the right notion of reduction to define completeness inside NP. The following post on CS Theory shows that defining completeness using injective Karp reductions would prove $P \ne NP$. The reason is  that SAT is infinite language and can not be reduced to a finite language using injective Karp reductions.


texts: Linear probing number of probe sequences

texts:
According to Cormen book,number of probe sequences possible in linear probing if hash function is given as

$h(k,i) =( h' (k) + i)$ $\text % m $ is m

if h'(k) = k modulo 5  and m = 10, then how can we have 10 distinct probe sequences?

Initial probe is decided by h'(k), so number of probe sequences should be limited by h'(k) and should be 5 right ?


texts: Architecture of a chatbot - how to organize and fetch possibilities?

texts:
I'm building a chatbot that would respond to text messages.

Let's say that my chatbot works for customers of an internet provider and it can respond to the following things:

Problems:

About payment;
About internet connection.

General requests:

Change user's account e-mail;
Call for technical assistance.

My question is: what's the data structure that I could use to organize this tree?


texts: Existence / non-existence of a sequence with short longest increasing subsequence and decreasing subsequence?

texts:
Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Subsequence is less than $ \displaystyle \lfloor \frac{N}{2} \rfloor $?
If yes, then give an example of such a sequence. Otherwise, can anyone present a proof that there cannot exist such a sequence?
(Just to add some substance, can it be shown there can exist such sequences, given any arbitrary value of $ N > 1 $?)


texts: Number of submatrices with a particular sum

texts:
Given a $n\times n$ matrix A[0...n-1][0....n-1] where all entries are non-negative integers, and a non-negative integer K, I want to find the number of submatrices whose entries sum to K.

The best solution I can find has $O(n^4)$ running time.  Any ideas how to improve the running time?


texts: Is interaction more powerful than algorithms?

texts:
I've heard the motto interaction is more powerful than algorithms from Peter Wegner. The basis of the idea is that a (classical) Turing Machine cannot handle interaction, that is, communication (input/output) with the outside world/environment.

  How can this be so? How can something be more powerful than a Turing Machine? What is the essence of this story? Why is it not more well known?


texts: Why is this argument for $P\neq NP$ wrong?

texts:
I know its silly, but i managed to confuse myself and i need help settling this

Suppose $P=NP$, then clearly for every oracle $A$ we have $P^A=NP^A$ which contradicts the
fact that there exists some oracle $A$ for which $P^A\neq NP^A$, hence $P\neq NP$

Whats wrong?
Thanks!


texts: What's better for an algorithm complexity, O(log n) or amortized O(log n)?

texts:
Some context: I'm to write a program that sorts the lines of a file in C for Linux. Since I have to read all lines of the file (fgets() for example) I'm thinking about inserting them in a tree like structure in a sorted manner using the so called tree sort algorithm.

Looking for a self-balancing tree structure I came across two that may be interesting, the red-black tree and a splay tree. According to Wikipedia the red-black tree has an O(log n) worst case and the splay tree has amortized O(log n).

The actual question: I know how to roughly compare some complexity levels in O notation but what's that amortized time? Given two algorithms one that runs in O(log n) and the other in amortized O(log n) which one would be preferrable?


texts: Use dynamic programming to find a subset of numbers whose sum is closest to given number M

texts:
Given a set $A$ of $n$ positive integers $a_1, a_2,\ldots, a_n$ and another positive integer $M$, I'm going to find a subset of numbers of $A$ whose sum is closest to $M$. In other words, I'm trying to find a subset $A′$ of $A$ such that the absolute value $|M - \sum_{a∈A′}a|$ is minimized. I only need to return the sum of the elements of the solution subset $A′$ without reporting the actual subset $A′$.

For example, if we have $A$ as $\{1, 4, 7, 12\}$ and $M = 15$, then the solution subset is $A′ = \{4, 12\}$, and thus the algorithm only needs to return $4 + 12 = 16$ as the answer.

The dynamic programming algorithm for the problem should run in $O(nK)$ time in the worst case, where $K$ is the sum of all numbers of $A$.


texts: Determine if there are 2 integers in 2 separate arrays add up to a given number

texts:
If I'm given 2 unsorted arrays A and B of n distinct integers and an integer z, how can I determine if there exists an integer in A and an integer in B that add up to z with an expected run time of O(n)?

I'm pretty sure that I would have to use a hash table(s) of some sort since I'm dealing with expected run time but I'm not sure how the algorithm would work.

Any help would be really appreciated! Thanks!


texts: Complexity class of finding the number of walks of length $k$ that have different vertex sets

texts:
Vertex set $A$ is of the form: $A = \{(v_1,r_1),(v_2,r_2),...\}$ where $v_1 \in V$ and $r_1$ refers to the number of times $v_1$ is reached in some walk and $v_j \neq v_i$ whenever $i \neq j$.

Suppose that one wants to count the number of distinct vertex sets that each have $\sum_i r_i = k$ and are allowed by some walk in a graph.

What would be complexity class of this? I was not really able to find complexity class for it. Would this problem be in #P-complete or just in #P?


texts: Finding the Candidate Keys of a Relation Using the FD's

texts:
I have definitely checked out many different related posts. I have also done different sample problems from online sources as well from a similar problem. However, I am stuck on the problem below specifically.

  Given the following relation $R$ and the set of functional dependencies $S$ that hold on $R$, find all candidate keys for $R$. Show your work.

  $R(A, B, C, D, E, F)$

  $S:$

  $AB \rightarrow C$

  $AC \rightarrow B$

  $AD \rightarrow E$

  $BC \rightarrow A$

  $E \rightarrow F$

Initially, I broke the attributes into groups: attributes found only on the left, only on the right, and on both sides (they are $D$, $ABCE$, and $F$ respectively). I also know that I should try to compute the closure of $D$. This is where I get stuck. At first glance, this seems like I am unable to solve this problem, which isn't true. I also tried computing the closures of $(AD)$, $(BD)$, $(CD)$, and $(ED)$ because I thought that the closure of $D = D$. Any thoughts?


texts: How to generate a uniform random sample of unique vertex pairings from a undirected graph under constraint?

texts:
I'm working on a research project where I have to pair up entities together and analyze outcomes. Normally, without constraints on how the entities can be paired, I could easily select one random entity pair, remove it from the pool, then randomly select the next entity pair.
That would be like creating a random sample of vertex pairs from a complete graph.
However, this time around the undirected graph is now

incomplete
with a possibility that the graph might be disconnected.

I thought about using the above method but realized that my sample would not have a uniform probability of being chosen, as probabilities of pairings are no longer independent of each other due to uneven vertex degrees.
I'm banging my head at the wall for this. It's best for research that I generate a sample with uniform probability. Given that my graph has around n = 5000 vertices, is there an algorithm that i could use such that the resulting sample fulfils these conditions?

There are no duplicates in the sample (all vertices in the graph only is paired once).
The remaining vertices that are not in the sample do not have an edge with each other. (They are unpaired and cannot be paired)
The sample generated that meets the above two criteria should have a uniform probability of being chosen as compared to any other sample that fulfils the above two points.

There appear to be some work done for bipartite graphs as seen on this stackoverflow discussion here. The algorithms described obtains a near-uniform sample but doesn't seem to be able to apply to this case.


texts: How to predict the length and offset of the sequence in and array?

texts:
I have an input string similar to ABCDEFGHIJK from which a series of sequences has been generated into an array as following:

00: 'ABCD'
01: 'BCDE'
02: 'CDEF'
03: 'DEFG'
04: 'EFGH'
05: 'FGHI'
06: 'GHIJ'
07: 'HIJK'
08: 'ABC'
09: 'BCD'
10: 'CDE'
11: 'DEF'
12: 'EFG'
13: 'FGH'
14: 'GHI'
15: 'HIJ'
16: 'IJK'
17: 'AB'
18: 'BC'
19: 'CD'
20: 'DE'
21: 'EF'
22: 'FG'
23: 'GH'
24: 'HI'
25: 'IJ'
26: 'JK'
27: 'A'
28: 'B'
29: 'C'
30: 'D'
31: 'E'
32: 'F'
33: 'G'
34: 'H'
35: 'I'
36: 'J'
37: 'K'

The sequences in the array above has been generated by following these steps:

Set length to 4
Set offset to 0
Pick a sequence of length long characters from "ABCDEFGHIJK" (Input string)
Put the sequence at the bottom of output array
Increase offset by 1
If offset + length <= 11 (Input string's length) then goto 3
Decrease length by 1
If length >= 1 then goto 2
Exit

By looking at the output array, sequences in the array have a length which starts at 4 and gradually goes down to 1, and also an offset which is where in the input string the sequence has begun.

What I'm trying to achieve is to "predict" both the length and the offset of a sequence at a given index in the output array, only having the input string's length and index in the output array.

I'm preferably looking for a formula, however an algorithm which doesn't involve simulating the output array will work as well.


texts: Complexity of / best algorithm for finding the dichotomy that maximizes information gain?

texts:
Suppose that $X$ is a finite set with a probability measure $P$. I want to find the subset $A \subset X$ so that the information gain of conditioning on ${A, A^c}$ is maximal. That is, I want to find $A$ that maximizes

$$H(X) -H(X|\{A,A^c\}) = H(X) - (P(A)H(A) + P(A^c) H(A^c)),$$

where $H(A)$ refers to the entropy of the conditional probability distribution so $\mu(B) = P(B \cap A) / P(A)$. (If $P(A) = 0$, then set $P(A) H(A) = 0$. In any case, it won't be a maximizer.)

Since this splits $X$ into two sets, I am calling this a dichotomy, and the question is of finding the dichotomy that produces the largest information gain.

Question: What is the complexity of this problem? (As D.W. points out below, a reasonable corresponding decision problem is - for $t \geq 0$, is there an $A$ so that information gain is $\geq t$? This decision problem is in NP, and we can ask if it is NP-hard, etc.) Is there a good heuristic algorithm for making this choice? What if I ask for an approximately, probably correct algorithm?

I am asking this question since I'm studying decision trees in machine learning and also coding theory, and this seems like a basic question in both settings.


texts:
My understanding is that one way to build a perfect hash, as per CLRS, is to use two levels of hashing, with universal hashing functions at each level.

More specifically, CLRS shows that assuming $n$ is the total number of keys, and $n_j$ the number of keys hashed to the value $j$ for the second level, we can then make $m=n$ and $m_j=n_j^2$ to guarantee that the expected number of collisions is < 1/2 in the second level.

However, as far as I understand, collisions are still possible in this second level, so to truly have no collisions in this 2nd level, one may need to try a few hash functions in this level for each value of $j$.

Is my understanding correct? If so, CLRS does not seem to elaborate much on this algorithm. Is it fair to assume that a simple sequence of random "try and error" (i.i.d sampling) of hash functions (in this 2nd level) is "as good as it gets" at least for this perfect hashing design?


texts: How would I simulate a network to explore the percolation threshold of a network connected by the knight's move?

texts:
"If we consider the squares of an infinite chess board as nodes of our graph and consider each to be connected to the other eight squares that are a knight's move away from it what is the percolation threshold of this graph?"

Note:One way I have thought about this problem is to try to use vectors: We can think of a knight's move as a vector of the form $<\pm1,\pm2>$ or $<\pm2,\pm1>$ for the eight cases.

In answering this question I think I need to create a simulation. How would I create a program to simulate an infinite board, for instance, and remove random nodes to create a graph with a percolation value.


texts: Are Turing-recognizable languages closed under intersection?

texts:
Let $A$ and $B$ be Turing-recognizable languages. Must language $C = A \cap B$ be Turing-recognizable too?

I have a hunch that it should be because we can construct an enumerator for $C$ by enumerating all the languages in $A$ and then all the languages in $B$.

However, I also know that Turing-recognizable languages are not closed under complement, and $\overline{\bar{A} \cup \bar{B}} = A \cap B = C$, which seems to suggest that Turing-recognizable languages are not closed under intersection.

There is clearly a contradiction somewhere in my reasoning. Where is it?


texts: Are Epsilon-NFAs a way to make designing NFAs easier?

texts:
It seems that their purpose is in making designing certain NFAs less onerous? Does this mean that no automata that are implemented have Epsilon-transitions, and that they are kind of a mathematical conceit we adopt for our own ease of design? I'm having a lot of trouble understanding what is "happening" when an Epsilon-transition occurs - is it a way of saying, "have the NFA now switch, automatically, to this next state"?

EDIT: I'm  a CS student taking CS Theory for the very first time, so apologies if this question is very rudimentary. I'm a narrative person and I often understand abstract ideas through examples or by trying to understand the problems the ideas are engaging with. I ask very basic questions, but those questions help me hook into the ideas I'm studying.


texts: Solving recurrences (tree method) with square roots

texts:
I am trying to find the upper and lower bounds for this recurrence, but I am not sure how to handle to square root:
$$
T(n) = 4T(n/2) + n^2\sqrt{n}
$$


texts: Is finding a set cover of size $k$ NP-complete?

texts:
I know that set cover problem is NP-complete. We are given a universe  $U$ (a set) of $n$ elements and a collection $S$ of $m$ sets whose union equals the universe and an integer $k$. The set cover problem is to identify a sub-collection of $S$ of size $k$ or less whose union equals the universe?

Now if I remove or less, and ask instead that is there a sub-collection of $S$ of size $k$ whose union equals the universe? Is this still NP-complete?

Here, of course, $k<m$.

My answer is that the problem is still NP-complete. From the initial problem we simply keep the same instance and we find a set cover of size $s\leqslant k$  then the modified problem has a set cover of size $k$ if $s=k$.

Any help?


texts: Does CSL contain an empty string or not? Is empty string accepted by LBA or not?

texts:
I am confused and got contradictory statements from various sources. It is mentioned in Page no 292, Chapter 11 A Hierarchy of Formal Languages & LBA, Peter Linz -An Introduction To Finite Automata, 5th Edition that "A language L is said to be CSL if there exists context-sensitive grammar G such that $L = L(G)$ or $L = L(G) \cup \{\varepsilon\}$." So the Language contains empty string & grammar as per Peter Linz.
In another version, I found that the production $S\to\varepsilon$ is also allowed in CSL, provided that 'S' does not appear on the right-hand side of any productions. However, several other sources like this youtube lecture (https://www.youtube.com/watch?v=i3c_2c2KFpY) explain that CSL does not contain a null string. Here in this given link (https://gyires.inf.unideb.hu/GyBITT/14/ch06s04.html)  it is written that LBA accepts null string generated from a CSL.
In the book, "Theory of Computer Science: Automata, Languages and Computation" by Mishra K.L.P , third edition, Publisher-PhI, on page 299, subsection 9.8.1 that "The set of strings accepted by nondeterministic LBA is the set of strings generated by CSG, excluding null strings".
This is too much for making a complete confusion.
Example:
L=$\{a^nb^nc^n| n\geq 0 \}$, whether this is CSL or Not? This language contains empty string too!
Please help me to get the right knowledge.


texts: Duplicate dominating parents when using Deterministic Crowding in Genetic Algorithm

texts:
This is the pseudocode for using deterministic crowding:

for _ in (0, ..., n/2):
    p1, p2 = random_individual(), random_individual()
    c1 = mutate(crossover(p1, p2))
    c2 = mutate(crossover(p2, p1))

    if d(p1, c1) + d(p2, c2) < d(p1, c2) + d(p2, c1):
        population.add(winner_of(p1, c1))
        population.add(winner_of(p2, c2))
    else:
        population.add(winner_of(p1, c2))
        population.add(winner_of(p2, c1))

where d is a function that determines the difference between two individuals.

The question is:  Do I end up with duplicate individuals in the new population if an individual gets selected two times as one of parents, and wins over its child both times?


texts:
I am trying to rank $\log n $, $\log_{10} n $, $n \log n $, $n \log n^2 $, $n^{0.8}$, $\sqrt{n}$ in increasing asymptotic complexity. $\log n $ has base 2 unless specified otherwise.

The answer I have is $\log_{10} n $, $\log n $, $\sqrt{n}$, $n^{0.8}$, $n \log n$, $n \log n^2$,

Is this right? And possibly explain the reason behind it? thank you!


texts: How to determine maximum stack size of LL(1) parser?

texts:
I am generating an LL(1) parser generator for LL(1) grammars that have a maximum stack size when executed in the table-driven parser. Specifically, I'm parsing HTTP headers using a parser generated by the LL(1) parser generator.

In case somebody asks, yes, it's possible to parse plaintext HTTP using LL(1) parser, if the parser works together with the lexer, so that the parser automatically turns on and off tokens in the lexer. So, only those tokens that are valid in the context are matched in the deterministic finite automaton (DFA).

The particular grammar I'm using for my tests is this (yes, I know it's possible to fold the first header line incorrectly using the grammar, I'll fix this later):

headerField -> foldstart httpfield
headerField -> httptoken colon optspace httpfield
httpVersion -> httpname slash digit period digit
requestLine -> httptoken onespace uri onespace httpVersion crlf
requestHdrs -> (epsilon)
requestHdrs -> headerField crlf requestHdrs
requestWithHeaders -> requestLine requestHdrs crlf

The start nonterminal is requestWithHeaders. The terminals are:

crlf, onespace, httpname, slash, digit, colon, optspace
httptoken, httpfield, period, uri, foldstart

...so every name that is lowercase only is terminal, and if there are uppercase characters in the middle, it's nonterminal.

Now, if I start using the stack [(endOfFile), requestWithHeaders], the maximum stack size is ever going to be 9 according to my tests. So, this grammar appears to have a maximum stack size.

The question is: how to prove the maximum stack size? I'm looking for an algorithm that terminates and gives me the answer 9 for this grammar. The algorithm need not terminate for a grammar that doesn't have a maximum stack size, so infinite recursion and infinite loops are permitted if the maximum stack size doesn't exist. (I can always limit the amount of CPU time given to the algorithm.)

I already have the code to calculate first-sets and follow-sets, and the code to generate the parser table, and the code to execute the parser using the parser table, so I'm not looking for advice for standard LL(1) parser implementation. I have already tested my parser with valid and invalid HTTP examples, and everything seems to work just fine.

The reason I'd like to determine this maximum stack size is that I want to avoid dynamic memory allocation in the parser. There is no need to allocate memory dynamically for cases where there is an upper bound for the stack size.


texts: Is there an explicit example of a language which is EXP-complete? Or a weaker question, i.e., is there an explicit example of a language which is proven to be in EXP but not in P? By diagonalization theorem, we know the existence of such a language but is there a construction or explicit example known till date?


texts: Hash tables - probing for collisions run time

texts:
The question is a true or false question:

Hash tables using probing for collisions run in constant time with respect to how many items are in the hash but are at least linearly dependent on how full the hash is.

I think it's true but I don't fully understand why and I don't understand the term linearly dependent.

Any help would be great, thanks.


texts: Why is the subset of palindromes of a regular language context-free?

texts:
Why is $A(L) = \{x \in L \mid x = x^R \}$ context-free if $L$ is a regular language?

Trying to understand the approach to determining whether a regular language is context-free.


texts: Knapsack problem, partition problem, or in general dynamic algorithm with negative numbers allowed

texts:
How to think about dynamic algorithms which allows negative integers in input (where it's problematic, because obviously it's not always the case)?

Examples:

Partition Problem with negative numbers in set allowed
Knapsack problem with negative weights are allowed

Is there some general idea to handle these or other similar dynamic algorithms?