texts: Why is this language Turing recognizable and not not-Turing recognizable

texts:
I read that the following language is r.e. but not not-Turing recognizable
$L$: On input $M$ (where $M$ is a Turing Machine), $M$ accepts at least 20 inputs
I am not sure why it is not not-Turing recognizable., since I could perhaps make the following reduction from $\overline{A_{TM}}$ to $L$ given this procedure $R$ namely:

$R$: On input $<M,w>$:

Construct TM $M_1$, where on input $x$, if $x=1$, accept
If input $x$ is not equal to $1$, run $M$ on input $w$ for $|x|$ steps. If after $|x|$ steps, $M$ does not accept $w$, then accept $x$

From this reduction, if $M$ does not accept $w$, i.e. $<M,w> \in \overline{A_{TM}}$, then $M_1$ accepts any input word, i.e. $M_1 \in L$.
Am I missing something here?


texts:
What would be the standard topics covered in an 'Advanced Placement Computer Science A' test? Is there any good study reference someone can share?

Edit: Answer

An adjustment for my search term returned a Wikipedia page just for this type of exam and the AB version.


texts: Class of languages that are equivalent to the lambda calculus

texts:
It is well known that all computable functions can be expressed as terms of the lambda calculus and computed according to its rules. It is also more or less obvious that many classical formal languages (i.e. languages with formalized semantics) can be translated into the lambda calculus (e.g. using a Church encoding). I am, however, pretty sure that there are languages where such a translation is not possible, the simplest example would be a language with a builtin primitive that solves the Halteproblem.

That makes me wonder if there is an established terminus for the languages that can be translated.

Is there a name for the class of languages that can be translated (correctly, completely) into the lambda calculus?


texts: Inductive proof for the Bubblesort algorithm

texts:
I'm studying Algorithms and Data Structures from The Algorithm Design Manual and I'm having a hard time going through the exercises.
Specifically, the proofs are a bit hard and not really explained in the book(It only gives two proof exmaples).
Prove the correctness of the following sorting algorithm.
    Bubblesort(A)
        for i from n to 1
            for j from 1 to i − 1
                if (A[j] > A[j + 1])
                    swap the values of A[j] and A[j + 1]

I would really appreciate if you could help me with an inductive (or any kind of proof I don't really know) for this exercise.


texts: How to use the concept of loop invariant to reduce errors in loops?

texts:
Most of time while writing loops I usually write wrong boundary conditions(eg: wrong outcome) or my assumptions about loop terminations are wrong(eg: infinitely running loop). Here is an small example where I got stuck several times, the example is a sub problem that I skinned out for solving insertion sort algorithm.

/**
 * Inserts the given value in proper position in the array.
 * @param array
 * @param rightIndex The index till which sub array is sorted.
 * @param value The value to be inserted into sorted sub array.
 */
function insert(array, rightIndex, value) {
    // assert sorted(array, rightIndex)
    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];
    }
    array[j + 1] = value;
    // assert sorted(array, rightIndex+1)
};

The mistakes that I did initially were:

Instead of j >= 0 I kept it j > 0.
Got confused whether array[j+1] = value or array[j] = value.

That time I don't have any tool to verify where I am doing wrong, fortunately on Googling I came to know about loop invariants.

To get hold of the above concept I thought to apply the concept here, although I am not mathematician but trying some equation I thought this
would be good invariant.

$$array[0...j] <= val < array[j+2...rightIndex+1]$$

As far as I understood the concept, its a loop invariant because the inequalities contains the loop variable j. How to utilize this equation here?

Being naive at this concept I am stuck and don't know how to use this invariant in my loop. How to gain confidence about the correctness of my loop?


texts: Amortized value of dequeue with potential function

texts:
A deque is implemented with 3 stacks. one for the head, one for the tail and one is always empty.
Pushing is therefor O(1), light popping (in case the head/tail respectively aren't empty) is also O(1).
A 'heavy pop' is in a scenario when we have k elements, only in 1 stack and we wish to pop the other stack.
For example, n elements in head and we want to pop the tail.
In this case, we push all elements from head stack to the empty stack, than push n/2 elements to the tail and the remaining n/2 back to the head.

I'm having troubles finding the potential function for this solution, or the amortized value for that case.
If I define the potential function to be the number of current elements in the deque, I get linear time. I don't know if this is true but I feel like it's not.


texts: What is the time complexity of the Bailey–Borwein–Plouffe formula?

texts:
How can I assess and derive the time complexity of the BBP formula?
$$
BBP(n)=4S(1,n) - 2S(4,n) - S(5,n) - S(6,n)
$$
where

$$
S(j,n) = \sum_{k=0}^n{\frac{16^{n-k}mod(8k+j)}{8k+j}}+\sum_{k=n+1}^{\infty}{\frac{16^{n-k}}{8k+j}}
$$

Note that the modulo is evaluated using the binary modular exponentiation algorithm (which is supposedly O(log N)) and the second sum iterates only over a few elements, i.e. up to a certain $\epsilon$.

I got O(N log N), but even if it is correct, I can't derive it.


texts:
Can someone explain the difference between first-order programs and higher-order programs in the context of programming languages?

My understanding so far is that Functional Languages (most) use higher order programs. Plus, higher functions either a) take other functions as arguments, or b) return functions as results.

Any correction, or further elaboration would on the difference between the two would be very appreciated.


texts: sum of squared distances from mean equals all-pairs sum of square distances?

texts:
In this variance based k-clustering paper they claim that for a cluster with S points:

$$|S|\sum_{i \in S}{\|x_i-\bar{x}\|^2} = \sum_{a,b \in S,\ a<b}{\|x_a-x_b\|^2}\,.$$

Why is that? can you please show me the derivation?


texts: How to prove that a language created from a context-free gramar's left side is regular(or left-linear)?

texts:
Given a context-free grammar $G$, let $\longrightarrow_G$ be the (one-step) rightmost derivation relation, and $\longrightarrow^*_G$ its reflexive and transitive closure.

Let $S$ be the start symbol of $G$, $\mathbf{N}$ the set of non-terminal symbols and $\mathbf{T}$ the set of terminal symbols. For each rewriting rule $A\rightarrow \alpha$ ($A\in\mathbf{N}, \alpha\in (\mathbf{N}\cup\mathbf{T})^*$), define the sets $\operatorname{Left}_G(A)$ and $L_{G,A\rightarrow\alpha}$ by:

$$\operatorname{Left}_G(A)=\{\beta\mid \exists w\in \mathbf{T}^*: S\longrightarrow_G^* \beta A w\}\qquad L_{G,A\rightarrow\alpha} = \{\beta\alpha\mid\beta\in \operatorname{left}_G(A)\}$$

I want to show, that for every context-free grammar $G$ and every rule $A\rightarrow \alpha$ of $G$, $L_{G,A\rightarrow\alpha}$ is a regular language over the alphabet $\mathbf{N}\cup\mathbf{T}$.

I can use the fact that a language generated by a left-linear context-free grammar is regular. Here a context-free grammar $G$ is said to be left-linear if $\alpha\in \mathbf{T}^*\cup (\mathbf{N}\mathbf{T})^*$ holds for every rewriting rule $A\rightarrow \alpha$ of $G$.

I've tried from both sides, the first thought was to show if I can get the language by getting the grammar from $G$ to $Left_G$, then maybe I can get some properties that $\beta$ may have, that lead to the fact that it's close to left-linear grammar, but I just can't, after thinking for a whole afternoon.
Then I thought maybe I can start from the goal language $\beta \alpha$, that I cut them into rewriting relation that is left-lineared, like we have $S\rightarrow_G^*\beta\alpha$, if we want to cut a left-linear grammar out of it, we need $S\rightarrow_G^*A\omega$, which $\omega \in T^*$ and we have$\alpha \rightarrow \alpha\omega$ or something, but as the $\alpha \in (N\bigcup T)^*$, so I don't even know if I can cut the language that way.

I'll appreciate if I can have some hint, like where may I begin to consider, or is there any properties about the relation I just missed or don't know?


texts: Predecessor query where the insertion order is known

texts:
Assume I want to insert elements $1$ to $n$ into a data structure exactly once, and perform predecessor queries while inserting these elements (so insert(x) and pred(x) always come in pairs). The predecessor of $x$ is the largest number in the data structure that is smaller than $x$.

The data structure is created by preprocessing the list of insertions.

When I start to insert elements, an adversary decides to delete some of the elements I have inserted, by adding any number of deletion operations between my insertions.

A query input to the data structure is a sequence of insertions and deletions, which is the insertion sequence with deletions inserted.
The output of the query is the result of the $n$ predecessor queries executed when the elements are inserted.

Can one design a data structure so the query takes $O(n)$?

Here is an example.

Insertions = [1,3,5,4,2]
DS = makeDataStructure(Insertions)//Runs in polynomial time
//add some deletions into insertions
Operations = [1,3,-3,5,-1,4,-5,-4,2,-2]
DS.query(Operations)//this runs in O(n) time

Assume -i = delete i. And pred(x) = 0 if there is nothing before it.
result would be:

[pred(1)=0, pred(3)=1, pred(5)=1, pred(4)=0, pred(2)=0]

for example, the 3rd in the result is pred(5)=1 instead of 3 because 3 is deleted when 5 is inserted.


texts:
I want to design a context-free grammar that generates words that either both start and end with $c$, or contain the same amount of $a$-s and $b$-s. Here is what I have. The nonterminals are $S,X,Y$, the terminals are $a,b,c$, the start symbol is $S$, and the productions are
\begin{align}
&S \to aYS \mid cXc \mid bXS \mid cYc \mid \varepsilon \\
&X \to a \mid bXX \\
&Y \to b \mid aYY \\
\end{align}


texts: Data Structures for BST where size uniquely determines shape

texts:
There are several data structures in which the number of elements uniquely determines the shape.
Examples would be binary heaps, arrays, lists, Braun trees, and Merkle mountain ranges.
Are there any such data structures that can be used to efficiently implement a binary search tree with good insertion/deletion performance?


texts: Global relabeling heuristic: Push-relabel maxflow

texts:
I have a correct, working implementation of the preflow-push-relabel maxflow algorithm [2]. I am trying to implement the global relabeling update heuristic [3], but have run into some issues.

I have a specific instance of the problem here to illustrate my questions 1:

a) For this problem instance, the "current preflow" is a state that is reached by my implemented max flow algorithm [[ even without global relabeling heuristic we reach this state ]]. Without applying any heuristics the algorithm proceeds to completion from this state giving the correct result.

b) The distance labels (in green) at this state represent a valid labeling as for every (u, v) \belong to E_{residual} d_u <= d_v + 1

Q1: The distance label (or height) is supposed to be a lower bound on the distance from the sink. However for several nodes in the residual graph (eg: 6, 7) this is not true. Eg. Node 7 has a distance label of 14...but clearly has a distance of 1 from the sink in the residual graph.

Q2: On running the global relabel at this stage, we get a labeling as seen in the extreme right. From this point on (depending on how frequently you do the global update), the algorithm can get stuck [[ deadlock ]] -- eg. nodes 6, 3 keep circulating flow between them as they each get relabeled to a higher height. If you run the global update before the reach the final height, you will reset the heights and the process repeats.

I am reasonably sure I am making a very trivial error but am unable to put my finger on it. Can someone help me with this issue? I am happy to provide a code snippet if that would help.

A couple more points that may be relevant:
-> I am implementing a single phase version of the push-relabel algorithm (ie. do not stop when you have a min. cut, but continue till you obtain a valid flow).
-> I am processing active vertices in FIFO order in the current problem instance. But I have a highest label first [3] implementation as well. I do not think this affects the two questions I have.

Thank You!

[[ This question has also been posted on programmers stackexchange -- I was unsure which forum is better for this question ]]

[2] A new approach to the maximum flow problem; A.Goldberg, R.Tarjan; JACM, Vol 35. Iss 4, 1988

[3] On implementing the push-relabel method for the maximum flow problem; B.V.Cherkassky, A.Goldberg


texts: Prove the following claim on Hamilton Path?

texts:
I am trying to prove the following claim:

Given DAG graph, there is Hamilton path iff the following algorithm
returns true:

Do topologic sorting.
Move on the graph's vertices one by one (from low to high). In case there is no edge connecting 2 vertices with adjacent values from the topologic sorting then return false.
if no false was returned after we check all vertices, return true.

I am stuck of proving one side which is: if there is Hamilton path then the algorithm returns true.
I tried using induction on number of vertices in the graph n:

Base case is simple for n==0.

Assuming claim is correct for n I want to prove for n+1

So I said, let's exclude the last vertex in the given Hamilton path (let's call it a), and assume by contradiction that the algorithm returned false.
This means one of the 2:

Two vertices with adjacent values had no edge connecting them and both aren't a.
this contradictc the assumtion that the claim hold for graph with n vertices.

One of the two vertices is a and the other isn't a.

I am stuck on proving that case (2) will give us a contradiction, How may I continue?


texts: Confusion with analysis of hashing with chaining

texts:
I was attending a class on analysis of hash tables implemented using chaining, and the professor said that:

  In a hash table in which collisions are resolved by
  chaining, an search (successful or unsuccessful) takes average-case time θ(1 + α),
  under the assumption of simple uniform hashing.

and

  The worst-case time for searching is θ(n) plus the time to
  compute the hash function.

These are quoted from out textbook, ITA. Here α is the load factor, which is equal to n/m where n is the total number of elements to be inserted to the hash table and m is the size of the hash table (which is a constant for each implementation).

My confusion arises from the thinking that

  θ(1 + α) = θ(α) = θ(n/m) = θ(n)

So I claimed that θ(1 + α) = θ(n), ie the average case and worst case time complexities are the same and the professor disagrees with me.

She asked me to find out by myself why I am wrong. I did some brainstorming and the only deduction I can make is that either I am wrong in assuming that m is a constant or asymptotic notations can't be used to compare between worst-case and average-case running time in this case. Please help me find what is wrong here. Also  I don't understand why θ(1 + α) is not written simply as θ(α) and also why the professor insists on the value of α being less than, equal to, or greater than 1


texts:
The problem is informally defined as follows:

There is a pipe with holes in it, located at discrete positions. We have tubes that are used to cover the holes. Tubes come at fixed radius. Having a tube of a radius of 1, say, placed at position 3, covers holes at positions 2, 3, and 4. The puzzle is about providing positions for placing the tubes so that the lowest possible amount of tubes are used. Note that tubes are allowed to overlap each other.

For example, the tube radius is 1 and the holes are located at {2, 4, 6, 10}. Tubes need to be placed at position 3 (covering 2 and 4), 6 and 10.

Obviously this seems to be a covering problem, yet I wasn't able to find a specific, studied problem equivalent to this one. Any ideas on how to efficiently approach it?

EDIT: please consider an additional condition, which requires a tube's center to be placed exactly on top of a hole (for whatever strange reason). This should change the solution considerably.


texts:
My basic setup is very simple: I'm trying to sort N items now, and later on I'll need to incrementally sort more items. The unique part of the problem is that my item comparison is not a computational process; it's a high-latency external task. But I can run several comparisons in parallel. As a result, the duration of the sort is determined fully by the time needed for the comparisons, and the cost is determined by the number of comparisons. Other operations are essentially free.

Now I can optimize either cost or duration. To optimize for cost, I don't use parallel comparisons. I just get the ordinary O(N log N) comparisons, and also O(N log N) duration. Optimizing for duration is only slightly harder: I just compare every element with every other element in parallel. That's trivially O(N*N) cost, O(1) duration.

But I have a constraint in the number of comparisons C I can run in parallel, and it's significantly lower than N*N. It's even significantly lower than N.

This is not a theoretical problem. The practical implementation has humans involved in the comparison operation, which explains the cost and latency.

My current sketch is to create batches of 7 items. Each batch can be sorted in parallel. I can merge-insert them one batch at a time into the master list. When inserting this batch, I compare the middle element of the batch with the middle element of the master list, and depending on the result I then merge one half of the batch with the whole master list and the other half of the batch with only half the master list. The latter task is most expensive, but I use about C=4 comparisons in parallel for this part.


texts: Weighted interval set scheduling problem

texts:
Given a set of weighted intervals, the weighted interval scheduling problem is to select a subset of the intervals such that none of the intervals in the subset overlap and the sum of their weights is maximized. This can be solved in linear time with dynamic programming or memoized recursion.

Is there a version of this problem where intervals are grouped, i.e. interval $a$ can only be in the solution if intervals $b$ and $c$ are also in the solution? By this formulation, there would be a weight associated with each group, or set, of intervals.

The most similar problem I've come across is the exact cover problem, which is NP-Complete, but in this instance we're maximizing weight and all vertices need not be covered.

Any insight will be much appreciated. Thanks!


texts: About the turing machine's non-deterministic branches

texts:
I have three different cases of non-deterministic turing machine.
The first machine has:
Branch "accept" and branch "loop".
The second has:
Branch "rejecte" & branch "loop".
Third has:
Three branchs "rejecte" "loop" "accept".
The question is which machines will  rejecte and which ones will accept and which ones will enter a loop?
Thank you so much


texts: Closest-point heuristic approximation problem

texts:
I have an Approximation Algorithm problem and its answer but I am having a hard time to clearly understand.
The problem is as follows:

  Consider the following closest-point heuristic for building an approximate traveling-salesman tour whose cost function satisfies the triangle inequality. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex $u$ that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest $u$ is vertex $v$. Extend the cycle to include $u$ by inserting $u$ just after $v$. Repeat until all vertices are on the cycle. Prove that this heuristic returns a tour whose total cost is not more than twice the cost of an optimal tour.

The answer is (I apoligize for including an image but I couldn´t get the  some special characters displayed correctly)

What I do not understand is the part surrounded by the red rectangle. I will very much appreciate if you help me to get the idea behind it. I am studying for an exam and I am stuck with this problem.

Respectfully,
Jorge Maldonado


texts:
I need a little help with a lambda calculus reduction to normal form:
$$(\lambda xxxx.xx)(\lambda x.xx)(\lambda x.x)y((\lambda x.x)x)$$
It should be solved like this:
$$xx(\lambda x.x)y((\lambda x.x)x)$$
and then:
$$xx(\lambda x.x)y(x)$$

This is the result of any of the lambda calculators that you can find online.

My question is: why can't I go on with reductions and make also $(\lambda x.x)y$ so the resulting expression would be $xxy(x)$?

Can you give me a complete answer, with theory of lambda calculus rules/proofs?

I really want to understand this exercise, any help would be appreciated.


texts: Algorithm to solve a physical ring removal puzzle

texts:
Assume we want to solve the so-called "Super-G" problem from Jean-Claude Constantin. The goal of the puzzle is to get the ring off the other components. Here is a picture of the problem:

Source: http://gunnarmp.blogspot.com/2016/10/super-g.html

The question here shall not be how to do that - that's trivial after you figured out. The question shall be, how we can write a simulation for this problem that seeks for the proper solution.

I can think of two completely different approaches, both of them non-trivial:

May we find a way to represent all moves that we can do in an abstract way? The simulation would be trivial.
Should we use a 3D simulation and use some random walk to move the ring? The set-up might be much simpler, but the simulation itself much harder, also because the line might be very hard to simulate.

We are not looking for a solution in the form of a code, but what approach should be taken.


texts: Hitting Set Problem with non-minimal Greedy Algorithm

texts:
The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ such that $|\mathcal{H} \cap S_i| \geq 1$ for all $1 \leq i \leq n$.

We may ask for the minimal cardinality of $\mathcal{H}$, that is, what is the least number of elements needed to "Hit" every $S_i$?

Further, we may use a greedy algorithm to ensure we find a hitting set. In this greedy algorithm, we set $\mathcal{H} = \emptyset$, and while we still have sets $S_i$ that have not been hit, we add to $\mathcal{H}$ an element whom appears in the most $S_i$ that have not been hit, breaking ties arbitrarily if there are any.

My question is: What is an example of a Universe set $\mathfrak{U}$ and subsets $S_i$, where $1 \leq i \leq n$ for some $n \in \mathbb{N}$, such that the greedy algorithm above does not find a minimal Hitting Set $\mathcal{H} \subset \mathfrak{U}$?

For a longer (and probably clearer) description, and more info on the Hitting Set problem, see http://theory.stanford.edu/~virgi/cs267/lecture5.pdf, or Prove that Hitting Set is NP-Complete.


texts: Best way to make the jump from programming to computer science

texts: I have decent enough experience with programming to be able to tackle most things but I want to know how you recommend making the jump from just programming to computer science. I still have a couple years till college, I'm only a sophomore right now although I am taking Calc over this summer which should help with some of the math of things. Are there any great books, authors or resources you recommend looking at? thanks


texts: Why SAT Requires A Non-determinstic Algorithm?

texts:
I am getting started to understand the probelm of Satisfiability and i am reading (Computers and Intractability: A Guide to the Theory of NP-Completeness).

I do understand the difference between a Deterministic and Non-Deterministic Algorithm, however i don't understand why SAT requires a Non-Determinsitic Algorithm ? Why not a Deterministic Algorithm ?

How do we know for sure that a problem requires a Deterministic or Non-Deterministic Algorith that solves it ? (if it was solvable, i,e. not undecidable problem).


texts: Question about H-gate on entangled qubits

texts:
I have a question about the Hadamard Gate on entangled qubits. I’m very newb to quantum computing and does not have any professional knowledge in physics nor mathematics. However I’ve tried some different algorithms in IBM’s quantum experience and think I got the idea about how the qubits works in the block sphere. Because of my poor knowledge in physics I need a simple explanation and I want to understand it...

My problem:

When I do the following operation:

q[0]: H   ( + )   H
q[1]:          *

H = Hadamard Gate
( + ) = CNOT control
* = target

I get the following results when I measure q[0] and q[1] after 1000 shots:

1/4 times: 11
1/4 times: 01
1/4 times: 10
1/4 times: 00

What I don’t get is why the first qubit is measured as as a 1 (only) 1/2 times and as a 0 1/2 of the times. My theory before the measurement was that q[0] would always be measured as a 1 all the times since I put it in superposition <+| and then put it back (after the second H gate and the CNOT) to be measured along the X-axis. So what have I missed?


texts: Floating point binary number to a 7 segment decimal display

texts: I have covered floating point (32 bit) conversion from float to decimal and decimal to float. I am happy with the theory and I have created a conversion tool in Excel VBA which works just fine following the IEEE754 , so I am happy with theory. Also happy with add, sub , mult , div of 32 bit floating point binary numbers. What I cannot understand or find anywhere online is the answer to this simple question. How do computers / calculators do the final conversion from the floating point binary number onto a display. For eaxmple , I have built a BCD to decimal converter using Logisim (combinational logic gates) and I have built a Binary to Decimal converter in Logisim using the Double Dabble algorithm si I can see how these can display on a set of 7 segment displays but how does the number (0 10000001 01 00 11 00 11 00 11 00 11 00 11 0) which is the floating point binary for decimal number 5.2 actually get converted using logic circuits.


texts: Search in a sorted array (Binary search)

texts:
My lecture states that search in a sorted array can be done in ω(n).

Why is that? I know it can be done with "normal" search in Θ(n) and with binary search in O(log(n)).

My guess would be, make the algorithm so bad that it is in
ω(n) but that's a kinda silly guess I think.

Thank you all in advance.


texts: What do you call a DAG with a single root/source?

texts:
What's the name for a DAG (directed acyclic graph) that has a unique root or source node from which every other node can be reached?

Alternatively, if you change the direction of the arrows, what's the name for a DAG that has some unique sink node that is reachable from every other node?

Here's an example graph:


texts:
I'm stuck on "For any language $A$, let $A^R = {w^R | w \in A}$ Show that if A is regular, so is $A^R$."

According to my research (see references), the steps required to prove this question, are:

Reverse all the links in the automaton
Add a new state (call it $q_s$)
Draw a link labeled with ϵ from state $q_s$ to every final state
Turn all the final states into normal states
Turn the initial state into a final state
Make $q_s$ the initial state

Anyway, I decided to make a toy-example to check if those steps made sense to me.

So here it is :

Consider $\Sigma = \{a,b\}$

I want to read $w = {ab}$, However, I'm extrapolating that we can also read $w = \{ab\}^+$.

So I have built an DFA for it :

Then, I followed the instructions and built this NFA :

Now the questions :

1- Why do I have to make it  as an NFA instead of making an DFA that recognizes $w = {ba}$ or $w = \{ab\}^+$ ?

2- Can i kill the state $q_3$ of this NFA ? It's dead so why it should be there anyway?

3- Why the first state of the NFA transitions with $\epsilon$ ?

Whats really bothering me is the first question.
I can make an DFA that recognizes the Reverse of w = "ab". So why everywhere I research says that I must do it as an NFA?

Here's the DFA that recognizes $w = {ba}$, Once Again, I'm extrapolating that we can also read $w = \{ba\}^+$. Not sure if i should assume that, anyway :

"You need at least 10 reputation to post more than 2 links."

So why isnt that DFA enough to prove that if A is regular, so is $A^r$ ?

References :

"You need at least 10 reputation to post more than 2 links."
cs.stackexchange.com/questions/3251/how-to-show-that-a-reversed-regular-language-is-regular


texts: State complexity of difference of two languages

texts:
Given $A_1$ - DFA with $n$ states, $A_2$ - NFA with $m$ states (both over the same alphabet - $\Sigma$). What's the state complexity, i.e. an upper bound for the amount of states of the minimal DFA, recognizing the language $L(A_1)\setminus L(A_2)=L(A_1) \cap(\Sigma^*\setminus L(A_2))$.
What I thought of: evaluate the state complexity of $\Sigma^*\setminus L(A_2)$ (hypothesis: $2^m$). Why? Because an upper bound of $2^m$ can be obtained for a DFA to accept the language of $A_2$. It's also known that the state complexity of the completion $\Sigma^*\setminus L(A_{min})$ is $k$, where $A_{min}$ is an arbitrary minimal $DFA$ with $k$ states. Therefore we can evaluate the upper bound of the minimal DFA, recognizing $L(A_1) \cap(\Sigma^*\setminus L(A_2))$ as $n2^m$ (the state complexity of the intersection is simply the product of states).


texts:
I saw the posted question here about a direct reduction from near-clique to clique.

Clique-or-almost is like near-clique but with the option for a complete clique of size $k$, I mean that perhaps an edge is missing and perhaps not.

I can't figure out how to change the proof in the link to fit to the reduction from Clique-or-almost to Clique.

  $$\text{CLIQUE-or-almost} = \{(G,k) \mid \text{ $G$ contains a $k$-clique with possibly one missing edge}\}.$$


texts: Finding shortest path for DAG using dynamic programming vs topological sort?

texts: Why is it that when I read about finding the shortest path for a DAG I usually just hear about topological sort? Why not use dynamic programming where the shortest path to a vertex is simply the minimum of all vertices that have a path to it?


texts: Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time

texts:
Let PARTITION-INTO-THREE-SETS be defined as following:

Input: Positive integers $a_1, ..., a_n$

Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup K = \{1, ..., n\}$, so that $\sum_{i \in I}{a_i} = \sum_{j \in J}{a_j} = \sum_{k \in K}{a_k}$?

It's easy to show, that PARTITION-INTO-THREE-SETS is NP-complete by doing a polynomial-time reduction PARTITION $\le$ PARTITION-INTO-THREE-SETS.

As PARTITION can be solved in pseudo-polynomial time with dynamic programming, there should be a way to solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time. Is there any solution to adapt the pseudo-polynomial algorithm for this problem?


texts: What is the literature on a sparse matrix encoding of rose trees?

texts:
I have 'discovered' a way to encode rose trees (see e.g. What are the applications of Rose trees? ) as a sparse matrix: if you have a node n with ID i and parent ID p, then you place n in the matrix at coordinates (row, column) of (p, i). This makes it easy to:

Get a node by its ID and parent ID (single lookup of the matrix)
Get all children of a node ID (lookup a matrix row)
Prune and graft subtrees (change the coordinates of the subtree root)

Now I'm thinking that I can't be the first person to have thought of this. Can anyone point me to any literature which discuss this encoding?


texts: "Practical forms" of Chernoff bound for inequality in expectation

texts:
From Wikipedia:

The above formula is often unwieldy in practice, so the following looser but more convenient bounds are often used:
(i) $Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}, 0<\delta<1$
(ii) $Pr(X\leq (1-\delta)\mu)\leq e^{-\frac{\delta^2\mu}{2}}, 0<\delta<1$

The assumption they use is $E[X]=\mu$.
Would (i) still hold if we only assume $E[X]\leq \mu$? Would (ii) still hold if we only assume $E[X]\geq\mu$?
If not, what "practical forms" do we have in these cases?


texts: How do RNN's map variable-length sequences to variable-length sequences?

texts:
According to Karpathy's blog "The Unreasonable Effectiveness of Recurrent Neural Networks", recurrent neural networks can map variable-length sequences to variable-length sequences, as shown by the one-to-many, many-to-one, and many-to-many diagrams.

How do RNN's do this mapping of possibly different-length sequences? It seems to me that there would need to be mechanisms that decide whether to accept input or to yield output on any given iteration. I don't see how RNN's have any such mechanisms.


texts: Does the heap property in the definition of binary heaps apply recursively?

texts:
The definition of binary heaps says that it should be a complete binary tree and it should follow the heap property where according to the heap property,  the key stored in each node is either greater than or equal to or less than or equal to the keys in the node's children.

In the above tree, the node with value 70 is greater than its parent 10 breaking the heap property. However, 70 is also greater than 40 and lies in the subtree of 40. Will we say that the heap property is also breaking at 40, even though 40 is greater than its two children 10 and 2?

In simple terms should every node in the subtree of a root be smaller than the root?


texts:
I was reading an article at

What does "context" in "context-free grammar" refer to?

The production

zA -> xy

is described as being an "unrestricted" production. In what way is it "unrestricted"?

I even visited https://en.wikipedia.org/wiki/Unrestricted_grammar

which talks about unrestricted grammar as the one that is comprised of productions which have no restriction on LHS or RHS. On this note, I assume that an unrestricted production is the one with no restriction on LHS or RHS.

What restrictions are being talked about and how is the production free from such restrictions?


texts: Sphere packing inequality for error-correcting codes

texts:
i am wondering if the following inequality is correct:

if a code allows repairing of no more than k errors (inclusive, included) and m is the number of information bits and r the check bits, then $$∑^k_{i=1}\binom{m+r}{i}+1≤2^r$$

holds true?

please if you can explain so i can understand how you choose answer you give.

the only inequality i find in books that look similar is about "perfect code" with the inequality given is: $2^n = 2^k\sum_{i=0}^k\binom n i$. but i not see how this code is relevant. i try to do research in other books or internet and no answer sadly. please help me understand if given inequality is true or not based on information given.

thank you much.


texts:
First of all, I have to mention that I am very new in the field of information theory.
I have a question regarding the Shannon Entropy calculation for binary values. As far as I understood, the main assumption in the Shannon Entropy formula is that all the bits have the same weights. However, I am looking for a formula/techniques to calculate the entropy based on the weight of each bit of a binary string. Let me elaborate on this.

Suppose we have a 3-bits binary number (b2, b1, b0) and let us assume that the probability of being 0 or 1 is 0.5. Based on the Shannon's theorem the entropy considers all these bits with the same weight. If I give tell you that (b1, b0) = (00) then you can guess that the final value is either 0 or 4. But if I give you (b2,b1) = (00) you can guess that the final value is either 0 or 1. To me it means b2, b1 provides more information than knowing b1,b0. Because, you can guess the final value with less error. Is it really related to information or it is something else?

It would be good if you could provide me some links to get more information about this topic.

This is the link to my related question:
Hamming Error Correction

Thanks


texts: Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines?

texts:
I've always thought vaguely that the answer to the above question was affirmative along the following lines. Gödel's incompleteness theorem and the undecidability of the halting problem both being negative results about decidability and established by diagonal arguments (and in the 1930's), so they must somehow be two ways to view the same matters. And I thought that Turing used a universal Turing machine to show that the halting problem is unsolvable. (See also this math.SE question.)

But now that (teaching a course in computability) I look closer into these matters, I am rather bewildered by what I find. So I would like some help with straightening out my thoughts. I realise that on one hand Gödel's diagonal argument is very subtle: it needs a lot of work to construct an arithmetic statement that can be interpreted as saying something about it's own derivability. On the other hand the proof of the undecidability of the halting problem I found here is extremely simple, and doesn't even explicitly mention Turing machines, let alone the existence of universal Turing machines.

A practical question about universal Turing machines is whether it is of any importance that the alphabet of a universal Turing machine be the same as that of the Turing machines that it simulates. I thought that would be necessary in order to concoct a proper diagonal argument (having the machine simulate itself), but I haven't found any attention to this question in the bewildering collection of descriptions of universal machines that I found on the net. If not for the halting problem, are universal Turing machines useful in any diagonal argument?

Finally I am confused by this further section of the same WP article, which says that a weaker form of Gödel's incompleteness follows from the halting problem: "a complete, consistent and sound axiomatisation of all statements about natural numbers is unachievable" where "sound" is supposed to be the weakening. I know a theory is consistent if one cannot derive a contradiction, and a complete theory about natural numbers would seem to mean that all true statements about natural numbers can be derived in it; I know Gödel says such a theory does not exist, but I fail to see how such a hypothetical beast could possibly fail to be sound, i.e., also derive statements which are false for the natural numbers: the negation of such a statement would be true, and therefore by completeness also derivable, which would contradict consistency.

I would appreciate any clarification on one of these points.


texts: Number of vertices and edges lies on the boundary of bounded cells in line arrangement

texts:
I am learning computational geometry by myself using these lecture notes from ETH Zurich. Here is an exercise (8.9) I have been stuck for a few days:

For a line arrangement $A$ of a set of $n$ lines in $R^2$, let $F$ denote the union of the closure of all bounded cells. Show that the complexity
(number of vertices and edges of the arrangement lying on the boundary) of $F$ is
$O(n)$.

My intuition is to use induction, proving that when a new line $l$ is added, the number of added edges is a constant. This is similar to how we proved the zone theorem. However, I cannot figure it out. Can someone provide me with some hints?


texts: Maximizing cache utilization when scheduling a computation graph

texts:
So I’m making a program where I generate a computation graph that will be executed on an external device, where the goal is to order the computations in the graph so that the whole computation is done as efficiently as possible. I wonder if any of you know how my problem can be mapped to existing compiler or graph algorithms?

My computations have this kind of structure. There are $N$ values in memory, of which the computation device can load at most $M$ in some kind of local cache. Computations can only be done on what's in the local cache. There are only two kinds of operations, for arbitrary $f$ and $x, y \in [N], x \neq y$:

One operand instructions: $x \leftarrow f(x)$

Two operand instructions: $x \leftarrow f(x, y)$

The computation can be represented as an ordered sequence of these operations, but there is a lot of memory locations and therefore plenty of opportunity for reordering operations without breaking correctness. The computation device's cache can swap in memory values anytime and anywhere on command, e.g. it is not just a LRU cache.

How could I schedule the computation to minimize the number of swap-in operations? Is there a good algorithm to actually minimize this number, and if not are there good heuristic methods I can look into?

I feel like my problem can be thought of as trying to optimize register usage for a compiling a highly restricted imperative language. I know that if I write a C function that manipulates a lot of local variables with simple operations, and run a decent compiler on it, it will reorder the operations and fit all the variables around the limited registers available while trying to load from memory as infrequently as possible, similar to what I want. But I don't know exactly what algorithms are responsible for making this work, or if they scale well when $N$ and $M$ is large.

I also feel like topological sorting might be relevant to the algorithms used, but with the parallelism available in my problem there are intractably many topological sorts for the computation's dependency graph, and I'm not sure how I could find the best among them.


texts:
Let $G=(V,E)$ be a DAG. A subset $A \subseteq V$ is called a kernel if for all $u,v \in A$ $uv \notin E$ and for all $v \in V-A$ there exists an $a \in A$ such that $av \in E$ (note again, this is a directed graph).

I need to find an algorithm that runs in $O(V+E)$ that upon giving a DAG $G$, would find a kernel in the graph.

I started like this:

Sort the graph toplogically. Such a sorting exists since it is a DAG. Let us mark the output as $v_1, v_2,...,v_n$. Then we run right to left:

If $v_n$ has no ingoing edges, we add it to our kernel set $K$. Else, here I got stuck.

Maybe dynamic programming can help us here?


texts:
Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color?

I'm aware we can show that 3-colorable is an NP-complete problem by reducing 3-SAT to it. But I'm wondering is it possible to reduce clique to it?

I know for example that if a graph with n vertices contains a subgraph which is a clique of size k, then you need at least k colors (that is, the chromatic number is at least k).

So could we say that if a graph contains a clique of size 4, then it is not 3-colorable, and vice versa?

Edit: Hmm..upon further thought, maybe the reduction wouldn't work because in order to reduce clique, you can't fix ahead of time that you're looking for a clique of size 4? The size of the clique would be arbitrary..


texts: Understanding $\lambda \mu$-calculus in more programming way

texts:
I am learning $\lambda \mu$-calculus (self-study).
I learned it because it seems very useful for understanding Curry-Howard correspondence (e.g understanding  the connection between classical logic and intuitionistic logic)
I searched the internet, there is some information about $\lambda \mu$-calculus on Wikipedia, but it does not explore it further (at time of writing). https://en.wikipedia.org/wiki/Lambda-mu_calculus
Is there any more programming way to interpret the intuition behind $\lambda \mu$-calculus?
For example:
In $\lambda \mu$-calculus, there are two additional terms called $\mu$-abstraction $\mu \delta .T$ and named term  $[\delta]T$.
Can I think $\mu$-abstraction as a $\lambda $-abstraction which waiting for some continuation $k$ (here, is $\delta$)?
What's the meaning of the named term?
How does it connect to call/cc?
Can I find the corresponding roles in some programming language (e.g. Scheme)?
PS: I can understand $\lambda$-calculus, call/cc in Scheme, and CPS-Translation, but I still cannot clearly understand the intuition behind $\lambda \mu$-calculus.
Very thanks.


texts: Counting the number of unique syntax trees of a grammar

texts:
Lets say we have some arbitrary grammar for which we would like to know how many different syntax trees does it generate. For example the following:

S -> A1|1B

A -> 10|C

B -> C1 | $\varepsilon$

C -> 0|1

This is a quite simple language and the number of unique trees is not hard to figure out by just going through all of the different possibilities, but for more complex languages it gets difficult to count the number of unique trees by just examining it. For this reason, I'm wondering if there does exist some analytical approach, rules of thumb, or software that would allow to count the number of unique trees faster than just looking at the language long enough until all the possibilities are exhausted?


texts: Find the k length path that maximize a node associate metric

texts:
Let's say I have :

a Graph g
v vertices. Each vertex is associated to a cost c.
A special vertex called the starter vertex or vs.

I want to find the path p of length 10 (for example), that start from vs and that maximize the sum of the 10 seens nodes costs. I need to tell you that my graph represent a road network which means it has a big diamater, and the degree of each node is never above 6 or 7. Here is an example of the kind of a graph that I have. Obviously, I got way more nodes.


texts:
I'm having problems finding an algorithm to the following problem:

A and B take turns replacing a number $n$ of tokens with either $floor((n+1)/2)$ or $n-1$. The player who makes one token remain wins. We want to know, if there is a way for B to win the game no matter the moves of A. A begins the game.

My idea is the following:

Is n = 1 -> No way for B to win the game

We try all moves of first A then B and check for 1 -> There is a way for B to win

But this does not incorporate the "no matter the moves of A" criteria.


texts: Equivalence of Kolmogorov-Complexity definitions

texts:
There are many ways to define the Kolmogorov-Complexity, and usually, all these definitions they are equivalent up to an additive constant. That is if $K_1$ and $K_2$ are kolmogorov complexity functions (defined via different languages or models), then there exists a constant $c$ such that for every string $x$, $|K_1(x) - K_2(x)| < c$. I believe this is because for every Kolmogorov complexity function $K$ and for every $x$ it holds that $K(x) \le |x| +c$, for some constant $c$.

I'm interested in the following definitions for $K$, based on Turing-machines

number of states: Define $K_1(x)$ to be the minimal number $q$ such that a TM with $q$ states outputs $x$ on the empty string.
Length of Program: Define $K_2(x)$ to be the shortest "program" that outputs $x$. Namely, fix a way to encode TMs into binary strings; for a machine $M$ denote its (binary) encoding as $\langle M \rangle$.  $K_2(x) = \min |\langle M \rangle|$ where the minimum is over all $M$'s that output $x$ on empty input.

Are $K_1$ and $K_2$ equivalent? What is the relation between them, and which one grasps better the concept of Kolmogorov complexity, if they are not equivalent.

What especially bugs me is the rate $K_2$ increase with $x$, which seems not to be super-linear (or at least linear with constant $C>1$ such that $K_2 < C|x|$, rather than $|x|+c$).
Consider the most simple TM that outputs $x$ - the one that just encodes $x$ as part of its states and transitions function. it is immediate to see that
$K_1(x) \le |x|+1$. However the encoding of the same machine is much larger, and the trivial bound I get is $K_2(x) \le |x|\log |x|$.


texts: How to identify statistically distinct features of different sets?

texts:
I have two non-overlapping sets of items, with feature counts for each. What standard algorithms can I use to extract the most statistically distinct features of each set?

For example:

Items served at American restaurants (5 restaurants surveyed):

bread: 4
burgers: 2
cheese: 1
cronuts: 2
pasta: 2

Items served at Italian restaurants (10 restaurants surveyed):

bread: 7
pasta: 10
cheese: 8

I want to be able to know that cronuts and burgers are distinctly associated with American restaurant menus, and cheese and pasta are distinctly associated with Italian restaurant menus.

Thanks!


texts:
I've been studying this YouTube video on Powells method and it looks like when we have a single variable we start at the upper and lower bounds of the variable and then we keep dividing the search space until we find the minimum.
So for a single variable it looks pretty easy.  How do we do it for 2 variables?
Does anyone have a simple example of how to iterate through the algorithm?
For example suppose we have $F(X_1, X_2)$ and $X_1$ can range between 0 and 6 and $X_2$ between 0 and 4.
After the first iteration we determine that we need to focus $X_1$ between 0 and 3 and $X_2$ between 2 and 4.
I assume that we plugged in $F(X_1=1.5, X_2=1), F(X_1=1.5, X_2=3), F(X_1=4.5, X_2=1), F(X_1=4.5, X_2=3)$
And that we found out that the superior point was the $F(X_1=1.5, X_2=3)$, and so now we repeat.
Is that about right?


texts: Is there an structure that allows for a flat representation of trees with constant access to any element?

texts:
One can, for example, represent 2d arrays such as:

[[1,2],[3,4],[4,5]]

as flat arrays:

[1,2,3,4,5,6]

as long as he transforms the indices before accessing:

index(x,y) = x + y*2 // because internal width=2

This is often faster. My question is: is it possible to use a similar approach of representing an structure as a flat array, for, instead of n-dimensional tables, free-form trees such as:

[[1,2,3],4,[5,[6,7]],8]


texts: Optimizing method for counting length of elements between blocks

texts:
I'm currently trying to do a count of the number of elements between obstacles, for example:

000100001000 Would yield 3,4,3 and 01001110 would yield 1,2,1. More precisely i'm trying to find the sum of the above lengths passed to this function:

$f(x) =  \frac {x(x+1)} {2}$

So the first example would yield a result of 22 (6+10+6) and the second would yield a result of 5 (1+3+1).

This is done repeatedly with the first element 'chopped off'. So for 000100001000, this would be calculated for 000100001000, 00100001000,0100001000 ,100001000 ,00001000 and so on (note that the answer for 10010 and 0010 would be the same since we're counting the distance between ones)

Currently i've just been using an $O(N^2)$ brute force approach, but i feel that i can easily improve this to O(N) since most of the information is already calculated after the very first element is processed. I'm wondering if there's a constant time method to process the subsequent elements after the first one is processed, but if not, what is the best approach?

Edit: I found a way to optimize the algorithm that requires this algorithm, but that implies that some of the zeroes could be transformed into ones when a digit is 'chopped off'. It's safe to assume that the element(s) that get transformed would be random.
Eg:
0010 when chopped may transform into 011 or 110 or 111 instead


texts: Efficient data structure for matching 3D lines

texts:
I'd like to

Store a set of many infinite undirected 3D lines.
Make lookups against this set - i.e. given an arbitrary line, ask "Does the set contain a line coincident with this one?"

The incidence-checks would of course have to be fuzzy to account for floating-point errors.

Question:

What would be a good data structure to implement such a set?

My thoughts so far:

Each line is originally represented as:

$$\begin{align*}
    p &= \text{an arbitrary point on the line} &= 3 \;\text{floats} \\
    v &= \text{an arbitrary vector parallel to the line} &= 3 \;\text{floats}
\end{align*}$$

To facilitate lookups, this should probably be converted such that coincident lines turn into the same tuple of floating-point numbers (within the margin of error). For example like this:

$$\begin{align*}
    p' &= \text{the point on the line closest to}\;(0,0,0) &= 3 \;\text{floats} \\
    v' &= \text{normalized direction vector} &= 2 \;\text{floats}
\end{align*}$$

Where "normalized" means unified (that's easy) and reversed in half the cases (this will be a bit tricky to do without introducing inconsistencies).

And then I'd just need a data structure for fuzzy look-up of tuples of 5 floats.

A 5-dimensional Binary Space Partitioning Tree, maybe?
Or just multiply the 5 floats together to get one float per line, use them as keys in a sorted map (e.g. std::multimap<double, Line3D*> in C++ or TreeSet<Double, List<Line3D>> in Java), and do range lookups like $[x - \epsilon, x + \epsilon)$ for a given key $x$ and error margin $\epsilon$ and then only do the full incidence check for each line in that range?

Or maybe there's an altogether different approach?


texts: An algorithm to compute a set of states that satisfy a specific CTL formula

texts:
Working through a past exam question and I'm unsure where to start or what form they want the answer in:

Define an algorithm that receives as input a finite transition
system TS defined over the set of actions {a, b, c} and computes
the set of states of TS that satisfy the CTL formula ∃a U b.

Would anybody be able to give me a kick-start or a walk-through on how to answer this? Really appreciate any help.

edit: My attempt based on Klaus' answer

for all executions in TS
 for all states
  if **b** holds
   add current state to the stack, EXISTS = TRUE
  else if **a** holds
   if current state == next state in execution
    do nothing
   else if next state contains **a** or **b**
    add current state to the stack, EXISTS = TRUE
   else
    do nothing


texts:
I'm referring to a book where E and A were defined in text as follows

  The formula $A \phi$ states that all the executions out of the current state satisfy property $\phi$ whereas $E\phi$ states that from the current state, there exists and execution satisfying $\phi$

And formally, they were defined as

  $\sigma, i \models E\phi $ iff there exists as $\sigma'$ such that $\sigma(0)\ldots\sigma(i) = \sigma'(0)\ldots\sigma'(i)$ and $\sigma', i \models phi$
  $\sigma, i \models A\phi $ iff for all $\sigma'$ such that $\sigma(0)\ldots\sigma(i) = \sigma'(0)\ldots\sigma'(i)$, we have $\sigma', i \models phi$

$\sigma(i)$ was previously defined to be the ith state of an execution $\sigma$.

Here's where my confusion lies. Doesn't $\sigma(0)\ldots\sigma(i) = \sigma'(0)\ldots\sigma'(i)$ imply that the executions $\sigma$ and $\sigma'$ have both the same start and end state, therefore $\sigma', i \models \phi$ is same as $\sigma, i \models \phi$? That seems to be wrong.


texts: Removing lambda-productions when it's at the start symbol

texts:
I had a question regarding removing lambda-productions from context-free grammars.

I understand that the basic theorem or process for removing lambda-productions is to find nullable productions and replace them with the version of the same production when we use lambda. However, I had a question regarding special cases.

For example:

$$S \rightarrow aSSS$$
$$S \rightarrow bb\ |\ \lambda$$

How do I remove the lambda-production here? Is it even allowed to be removed? If we remove this, then we're fundamentally changing the grammar from one that accepts the empty string to one that doesn't.

This question has been really confusing me, and any help would be greatly appreciated.

thank you!


texts: Minimum Number of People Such That No Two People Know the Same Two People

texts:
In a population of $n$ people, each person knows $k$ other people and each person is known by the same $k$ people.  However, no two people, p1 and p2, know the same two people p3 and p4.  What is the minimum $n$ such that this is possible for a given $k$?  Or, in other words, what's the minimum number of nodes that must exist such that it is possible to connect each node to $k$ other nodes while not allowing a cycle of length 4?

Also, if it is possible, is there a program that can generate these graphs?

I don't have much on this problem yet besides a weak lower bound of $n\geq k^2-k+2$.

In the graphs below, an edge means that the two people it connects know each other.  In 1), this is a demonstration of what we don't want, both A and C know D and B.  In 2) these are configurations that work for k=2.  For k=2, n=3 and all n>4 work.  In 3) n=10, this is the smallest possible configuration for k=3.


texts: Showing that the number of primitive-recursion programs for each function is countably-infinite

texts:
Problem Statement

  Prove that if  a function $f$ is primitive recursive, then there are countably infinite number of primitive recursive definitions of $f$

Yes, this is a homework question.

My Work

I proved that there are infinite number of definitions using the following construction

$$g_k(n) = \underbrace{P_{1}^1(P_{1}^1( \dots( P_{1}^1}_{k \text{ times}}(f(n))\dots), \ \forall \ k \in \mathbb{N}$$

Here $P_1^1$ is the projection basis function which picks the $1^{\text{st}}$ element from a vector of size $1$

Now $k$ is unbounded and we will get an equivalent definition for $f$ for each $k$

Now the issue is that this is not the only way to construct an infinite number of equivalent definitions i.e. I could have also use the multiplication operator and multiplied the output of $f$ by 1 as many times as I liked.

How can I show that there is a $1-1$ correspondence of the set of all primitive recursive definitions with the set of naturals numbers? Unlike bit strings, I am unable to comprehend in what way I should assign some number to each function. In fact I don't even know in how many ways can I create equivalent definitions, so how can I even start to enumerate these functions?

Any hints?


texts: How to find $c$ and $n_0$ for Big-Oh questions

texts:
I understand the theory behind the definition of Big-Oh, but when I try a question, I don't get how you would find the $c$ and $n_0$ values.

For example: if $f(n) = n!$ and $g(n) = 2^n$, how would I go about finding the $c$ and $n_0$ values for $g(n) = O(f(n))$?


texts: Using the Master theorem on a recurrence with non-constant a

texts:
I am trying to solve the following equation using master's theorem.

$T(n)  = 3^n T(\frac{n} 3) + O(1)$

Extracting the b and $f(n)$ values makes sense they are $b=3$ and $f(n)=1$. I am not sure what my $a$ value is I don't think its just 3.


texts: Use 2SAT to show that an implication graphs must have a cycle if it's not satisfiable

texts:
Using 2SAT and implication graphs, how could I prove the following properties of implication graphs:

Suppose there is a directed path between literals l1 and l2 in G_φ.  Then there is also a directed path between their complements.  Then, there is  τ, a truth assignment satisfying φ where τ(l1) is true, then τ(l2) must also be true.

Using this, show that φ is unsatisfiable <=> there is some directed cycle in G_φ containing a variable x and its complement.

Where G_φ is the directed implication graph of 2SAT containing formula φ with n variables. Hence 2n vertices with one for every possible literal in φ, and edges (not l1, l2) and (not l2, l1) for every clause (l1 ∨ l2) in φ.

My first intuition was a proof by contradiction however I failed to construct a general enough assumption. I then tried to show that if the truth assignment means that l1 and l2 are true, then by building a cycle connecting all variables, the assignment is only valid when those edges exist. However this doesn't seem rigorous enough since I'm not properly understanding why the cycle requires the complement of x to exist.

Currently I build G by adding a vertex for every variable x and it's complement as well. Then for each clause (a v b) I add an edge between not a and b and not b and a.

However I fail to see how this would specifically form a cycle.

Working of the sipser textbook.


texts: How to come up with the runtime of algorithms?

texts:
I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site.

I've seen in many sites and books, the big-O notations like $O(n)$ which tell the time taken by an algorithm. I've read a few articles about it, but I'm still not able to understand how do you calculate it for a given algorithm.


texts:
With a stack, you can push and you can pop. There's also a generalization, let's call it a foo, in which key-value pairs are involved. The idea is that instead of just pushing a value, we push a key-value pair, as in L.push(key, value). Similarly, to pop a value, we have to supple a key. As in L.pop(key).

A straightforward implementation can be obtained as follows: choose an implementation for the dictionary data type, and then define that a foo is a dictionary in which the values are linked stacks. So L.push(key, value) is executed by querying the dictionary for the stack associated with the key key and then pushing value onto that stack. Similarly L.pop(key) is executed by querying the dictionary for the stack associated with the key key and then popping the top value.

A different implementation that can be more space-efficient under some circumstances uses a single linked list, whose nodes are key-value pairs. To perform L.pop(key), we search through the linked list until the desired key is found, and then pop that particular node. In fact there's situations where this single-list implementation is actually more time-efficient*; in particular, if you're mainly pushing and popping items in the reverse order, avoiding the cost of hashing the key can meaningfully improve the speed up of the lookup.

(*) You can't improve the big-$O$ time-complexity like this, only the practical running speed.

Anyway, since this data structure appears frequently in some of my amateur research into the foundations of mathematics, I'd be interested in getting a name for it.

Question. Does the "dictionary of stacks" ADT have an accepted name?


texts:
I was trying to solve problems in max flow algorithms.
And I came across this MIT Lecture Quiz.

http://people.csail.mit.edu/moitra/docs/6854hw4.pdf

solution : http://people.csail.mit.edu/moitra/docs/6854hw4solns.pdf

Questions :

(a) In any maximum flow, and for all vertices v and w, either the amount of flow from v to
w (f(v, w)) or the amount of flow from w to v (f(w, v)) is 0.

(b) Consider a directed graph G = (V, E). There always exists a maximum flow of G such
that, for all vertices v and w, either the amount flow on vw or the amount of flow on wv
is 0.

These two problems look one and the same.
And both are based on the trick of 'Flow conservation on any vertex'.
The main properties of both problems are the same. except that

first problem ---> any flow (all flow)

second problem --> a flow   (at least one flow)

So this made the difference

problem 1 -> False (because any flow on subtraction and add to incoming and out going we can make it non zero. So the statement 'ALL FLOWS' makes this statement false)

problem 2 -> True (because any flow on subtraction and add to incoming and out going we can make it non zero, so whatever be the flow, we can make manipulations such that one is zero and other is non zero. so there is 'A FLOW' with this property. this 'A FLOW' makes this statement true.

Am I right in my understanding of the key difference in both the questions, thought both look almost the same ?


texts: Are loop counters spatially or temporally local?

texts:
Consider this nested loop:

for (i=0 to n)
   for(j=0 to n)
      for (k=0 to n)
         sum := sum +k
      end for
   end for
end for

Do i,j and k have temporal or spatial locality?

I've considered j and k as temporal since they are revisited again in the loop. But I'm confused about i as it does not match the definitions of temporal or spatial.


texts: What is the relationship between oracle Turing machine $M^O$ and Turing machine $M$ (given $O$)?

texts:
An oracle Turing machine (OTM) $\bar{M}$ can be denoted $M^{O}$ if it is a Turing machine (TM) $M$ with an oracle $O$. Given the oracle $O$, there exists a relation $R$ between OTMs and TMs such that
$$\left( \bar{M}, M \right) \in R \Leftrightarrow \bar{M} = M^O$$

Given an OTM $\bar{M}$, how to find the TM $M$ such that $(\bar{M},M) \in R$?

Given a TM $M$, how to find the OTM $\bar{M}$ such that $(\bar{M},M) \in R$?

By using the definition of the OTM in wiki, In my opinion,
$$\bar{\Gamma} = \Gamma,~\bar{q}_{start} = q_{start},~\bar{q}_{accept} = q_{accept}, \bar{q}_{reject} = q_{reject} $$
and
$$Q_{0} = Q \cup\{ q_{query} , q_{response}\}$$
I have no idea about the relation between $\bar{\delta}$ and $\delta$. And what about the non-deterministic OTMs and NDTMs?


texts: $O(n \log n)$ simple polygon triangulation via divide and conquer

texts: I am looking for the simplest possible $O(n \log n)$ algorithm for triangulating a simple polygon.  It seems like there should be a simple divide and conquer variant that would fit the bill, ideally one avoiding auxiliary data structures such as trapezoidal decompositions.  Indeed, all that would be required is an $O(n)$ algorithm for finding a roughly balanced diagonal.  However, I am unable to find any algorithms that are as simple as I (perhaps naively) imagine should exist; nearly all the research is focused on $o(n \log n)$ algorithms, nearly all of which operate via trapezoidal decomposition.


texts:
I am solving the river crossing puzzle with 6 participants.
You must transfer all the people across the river in this flash game respecting the following rules:

The ferry can carry no more than 2 people.
Only the Adults (mom, dad and policeman) can operate the ferry.
Dad can not be in the presence of the girls w/out Mom
Mom can not be in the presence of the boys w/out Dad
The thief can not be alone with any of the family w/out the policeman.

We need to create the state space and as I am creating mine I am not sure if I am doing it properly.

In my case I represent the state as A/B where A are the people on the left side and B are the people on the right side. This is what I have so far.
I feel like I will get a lot of states, so I am worried that I am doing something wrong. Is this correct?


texts: Given an algorithm, what are the probabilities for its run-time cases?

texts:
I am given this algorithm

And I am also given the fact that $1 \leq k \leq n$.

If we let X be the number of times line 2 is executed, then I am supposed to find the run-time probabilities for the different cases.

Thus I know the best case will be when $A[n-1] = k$ because line 2 will only be called once.

I know that $k \in 1, 2, ... n$.

And by construction $A[n-1] \in 0, 1,2, ... n$.

Unfortunately, I am not able to come up with a formula that includes n and k that will let me calculate the probability that $A[n-1] = k$.

I was thinking that $P(A[n-1] = k) = P(k \in 0, 1....n)$, but it didn't lead me anywhere.

I was trying a more general approach for each index, not specifically $n-1$, and ended up with the formula $\dfrac{x+1}{x+2} \dfrac{k}{n}$ for $x \in {0, 1 ... n-1}$ which are the possible indices. However, it doesn't compute correct values.

Can someone help me here? How could I approach it.


texts:
I am trying to prove using the resolution technique that the following two clauses are contradicting:

$\forall_x Shaves(Barber, x) \iff \neg Shaves(x, x)$
$\exists_x Shaves(x, Barber)$

After turing those into the conjunctive normal form and skolemization I get the following clauses:

$\neg Shaves(Barber, x)\  \lor\ \neg Shaves(x, x)$
$Shaves(Barber, x)\  \lor\ Shaves(x, x)$
$Shaves(Someone, Barber)$

where $Someone$ is a Skolem constant (a Skolem function of of zero arity).

I am unable to prove that this set of clauses is contradicting. It looks like something is missing. Shouldn't there be a clause, which prevents $Someone$ from being a barber as well?


texts: Greedily Schedule Events based on value/hours

texts:
Suppose we are given a list of $n$ events $E = \{E_1, E_2, \ldots, E_n\}$ where each $E_i$ is represented by $(s_i, h_i, v_i)$ or $(start, hours, value)$. So if you attend an entire event that lasts 5hrs and has a value of 10 then you will gain 10 points. If you only attend for 3 hours, you only get 3*(10/5) = 6 points. The output that the algorithm should produce is the maximum number of points that can be obtained by attending combinations of various events. Note: you are allowed to leave and come back to an event.

My Algorithm (pseudocode):

Sort all the events $E$ by order of their $v_i/h_i$ ratio to produce a new set of events $E'$ such that $E'[1]$ has a higher value/hours ratio than $E'[2]$, $E'[3]$, etc...
$max = 0$
For each event $e \in E'$

$h =$ hours that have not yet been taken
$max\ += h* (e_{v_i}/e_{h_i})$

Note: I did not specify in the algorithm how to determine the hours that have been scheduled/taken already but you can assume that there is an array that flags hours that have been scheduled.

I do believe that my algorithm gives the optimal result, but how do I prove this?


texts:
Given the theorem that max flow <= min cut,
Would incrementing the min cut edges by 1 increase the max flow by 1 as well?


texts: Enumerate all ways to bin a series of integers into N bins, where each bin only contains contiguous numbers

texts:
I want an algorithm to list all possible ways to map a series of integers $M = \{1,2,3,...,m\}$ to another series of integers $N = \{1,2,3,...,n\}$ where $m > n$, subject to the constraint that only contiguous integers in $M$ map to the same integer in $N$.

E.g.: 5 -> 2:
  (1, 2, 3, 4), (5)
  (1), (2, 3, 4, 5)
  (1, 2, 3), (4, 5)
  (1, 2), (3, 4, 5)

This seems like it should be a standard problem with a well known solution, but I can't find it.

To clarify, I am not looking for the total number of solutions, but for pseudocode or the name of a corresponding algorithm to exhaustively list all solutions.


texts: 0/1 Knapsack problem with real-valued weights

texts: Is there a known solution for the 0/1 knapsack problem that allows the weights of the objects to be real numbers? The only algorithm I can think of is a brute force search. I have tried searching for a solution but couldn't come across any. When weights are natural numbers, the most common solution uses dynamic programming by caching solutions $V[i,w]$ to the subproblems in an $N\times W$ table, where $N$ and $W$ are the number of objects and weight limit of the knapsack. When the weights are real numbers, the dynamic programming solution breaks down: how do you define the table now? Granted there will be $N$ rows, but what about the columns?


texts: Why are word sizes in modern CPU’s a power of 2?

texts:
Word size of most modern cpu’s is 32 or 64 bits. Both are a power of 2.

This looks “intuitively reasonable”, because a bit has 2 states, but I don’t actually have a hard argument for why this is the case. Moreover, in the past, word sizes of processors have been multiples of other numbers, such as multiples of 6 (because characters were encoded in 6 bits).

What is the reason that chip designers have chosen to make word sizes a multiple of 2?


texts: Relation between best case and average case complexity

texts:
I have two questions,

Does $T_\mathrm{best}(N) = O(f(N))$ imply that $T_\mathrm{avg}(N) = \Omega(f(N))$?
Does $T_\mathrm{avg}(N) = O(f(N))$ imply that $T_\mathrm{best}(N) = O(f(N))$?

Where,
\begin{align*}T_\mathrm{best}(N) &= \min \{T_1, \dots, T_N\}\\
T_\mathrm{avg}(N) &= \frac1N \sum_{1\leq i\leq n} T_i
\end{align*}
for some sequence $T_1, T_2, \dots$.

I think both are true but don’t know how to prove them.
Any ideas?


texts: Does JPEG compression use a heuristic model similar to MP3?

texts:
I know that MP3 uses a compression heuristic that allows it to exclude storing frequency data outside a certain range due to the limits of human hearing.

Does JPEG employ some sort of non-linear quantization heuristic that accounts for the limitations of humans to perceive small differences in specific color bands or ranges?

Thank you in advance for any responses.


texts:
What happens if a CPU instruction (e.g. on ARM architecture) tries to access a physical address that is out of range. This easily could happen if the CPU is on non-virtual (non-paging) mode. This could also happen if the CPU is in paging mode and the page table maps the virtual address to a physical address that is out of range.
A physical address is out of range iff that address is not served by any of the plugged RAM chips.

Would the CPU run into an exception and invoke some interrupt service routine?
Would the CPU read/write some garbage value?


texts:
I am new to grammar and have written grammar for parsing math expression for asciiMath using ANTLR as below.
expression
    : expression BINARY_OPERATOR expression
    | UNARY_OPERATOR(expression)
    | LEFT_PARAM expression RIGHT_PARAM
    | VARIABLE
    | NUMBER
    ;

LEFT_PARAM
    : '(';

RIGHT_PARAM
    : ')';

VARIABLE
    : [A-Z]+
    | [a-z]+;

NUMBER
    : [0-9]+;

UNARY_OPERATOR
    : '-'
    | 'sqrt';

BINARY_OPERATOR
    : '+'
    | '-'
    | '*'
    | '/'
    | '^';

The problem is its not able to recogonize expression such as
sqrt(a)
The problem I guess for this is becoz [a-z]+ is matching sqrt its treated as variable not unary operator, so I changed rule to [a-z] and it works but i guess it would not be able to recognize ab+cd as ab is more that one char.
Similarly for a-b its not recognizing because - is present in both unary and binary operator. If I remove from unary it works fine.
So this is happening due to ambiguity in the grammar I guess, can someone suggest how to remove the ambiguity?


texts: Why can System F1 a.k.a. λ → have kind `*`, but no quantification `∀`?

texts:
In Types and Programming Languages by Pierce, on p461 in Section 30.4 Fragments of Fω

  30.4.1 Deﬁnition: In System F1 , the only kind is * and no quantiﬁcation (∀) or abstraction (λ) over types is permitted.

  F1 is just our simply typed lambda-calculus, λ → . Its deﬁnition is super-
  ﬁcially more complicated than Figure 9-1 because it includes kinding and
  type equivalence relations, but these are both trivial: every syntactically well formed type is also well kinded, with kind *, and the only type equivalent to a type T is T itself

Is it correct that  quantification ∀ means universal types?

* is the kind of proper types, which are introduced on p442:

  The level of types contains two sorts of expressions. First, there are proper
  types like Nat, Nat→Nat, Pair Nat Bool, and ∀X.X→X, which are inhabited
  by terms. (Of course, not all terms have a type; for example (λx:Nat.x) true
  does not.)

So universal types such as ∀X.X→X are proper types, and thus belong to kind *.
Why can System F1 have kind *, but no universal types, i.e. quantification ∀?

But if System F1 could have kind * and quantification ∀, then wouldn't it become the same as System F2 a.k.a. System F? Quoted from on p461:

  In System F2 , we still have only kind * and no lambda-abstraction at the level of types, but we allow quantiﬁcation over proper types (of kind *).

  F2 is our System F;

Thanks.


texts: Proving the decidability of whether a CFG generates a particular string or not

texts:
Let $G$ be a context-free grammar and $w$ be a string of length $|w| = n$.

Consider the language $A_{CFG}$ = { <$G$, $w$> | $G$ is CFG that generates $w$ }, where <$G$, $w$> is a string encoding of $G$ and $w$.

Now we have to show that $A_{CFG}$ is decidable, or in other words, there exists an algorithm that determines whether $w$ is generated by $G$ or not.

Now, the proof given in my book converts $G$ into an equivalent CFG $G'$ in Chomsky Normal Form and one-by-one checks all derivations in $G'$ that take $2n - 1$ steps, since a grammar in CNF takes exactly $2n - 1$ steps to generate a string of length $n$.

Now, I have an alternate algorithm in mind. I want you guys to tell me if there is something wrong with it or not because this one seems to be much simpler than the one given in my book.

So, since every CFG has a pushdown automaton which recognizes the same language, we convert the CFG into an equivalent PDA. Now we simulate the PDA on our Turing machine on the string $w$. This process must end in a finite number of steps since our string is finite in length.

Is this an alternate algorithm that illustrates the decidability of $A_{CFG}$ or is there something wrong with it?


texts: What is the rationale behind implicitly widening integer types in numeric operations?

texts:
Languages such as Java and C specify implicit widening of integer types for numeric operators, especially arithmetic operators, to a minimum of 32 bits. What is the rationale behind doing this?

My impression is that it's based on the end-programmer's expectations - that is, 200 + 100 should yield 300, and not overflow to 44. Is there additional impetus behind this implicit type conversion?

This decision to widen only to 32 bits seems a bit arbitrary to me. Besides performance/memory concerns (some target instruction sets don't support 64-bit numbers, so more instructions are necessary), why not widen to 64 bits to minimize overflow as much as possible? If a language were designed which required 64-bit integer promotion for the operands of a numeric operation, would a sufficiently sophisticated optimizer be able to optimize down to 32-bits where sufficient (or, given that I have a pretty poor grasp on computability, is such an optimization impossible)?

TLDR: why are 200 and 100 in 200 + 100 widened to 32 bits? Why not 64 bits? Would a language be significantly inefficient if converted operands to 64 bits, especially if implemented with a "good" optimizer?


texts:
I would like to find the best, average, worst-case complexities of below code.

Its a variant of selection sort. In each pass both min and max is calculated and placed at proper position

def double_selection_sort(arr):
    n = len(arr)
    for i in range(int(n/2)):
        _min, _max = i, n-i-1
        for j in range(i+1, n-i-1):
            if arr[_min] > arr[j]:
                _min = j
            if arr[_max] < arr[j]:
                _max = j
        arr[i], arr[_min] = arr[_min], arr[i]
        arr[n-i-1], arr[_max] = arr[_max], arr[n-i-1]

I think its in the order of O(nlogn).

Thanks in Advance


texts:
If I'm passing parameters as call by value-return and call a void function, will the local values within the function still be copied to the corresponding values in the caller function even though the called function doesn't return? For example:

int x = 4;

void foo(int a) {
    a = 8 + 8;
}

int main() {
    foo(x);
    print x;
}

Will the value printed be 4 or 16? My hunch is that because foo never returns, the local value for a within the stack frame of foo never gets copied back to the value for x in the stack frame for main, but I wanted to double check.


texts: Small space hash functions that are weakly but not strongly universal

texts:
This is a follow up to this this question about weakly universal hash functions

A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ :

$$P_{h \in H_w}(h(x) = h(y)) \leq 1/m$$

Here the function $h:U \rightarrow [m]$ is chosen uniformly from the family $H$ and we assume $|U| > m$.

A family of hash functions $H_s$ is said to be strongly universal if for all $x \ne y$ and $k, \ell \in [m]$:

$$P_{h \in H_s}(h(x) = k \land h(y) = \ell) = 1/m^2$$

I previously asked for an example of a hash function family which is weakly universal but not strongly universal.  The very nice answer was:

  Take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$,
  given by $$ h_i(x) = \begin{cases} x & \text{if } x \neq m+1, \\ i &
> \text{if } x = m+1. \end{cases} $$ The same approach can be used for
  arbitrary $|U|$: fix the first $m$ coordinates, and make all other
  coordinates uniformly and independently random.

For arbitrary $|U|$, it seems that in order to represent a single hash function in practice you would need to store a lookup table of size $|U|$ to ensure that the hashed values are independent and truly random. Then for every key, you would look up its random value in the vast lookup table to compute the hash function.

Is there a hash function family where the hash functions require constant or log space that achieves the same result of being weakly but not strongly universal?  In other words, are there any practical hash function families that are weakly not but strongly universal?


texts:
I'm trying to come up with an alternate DFA for accepting (a|b)*abb than the one present in the dragon book. Here's the one I tried:

It seems valid to me but I'm not sure. Also, is there a way to check for validity of automatons so that I don't end up bugging you guys next time?


texts: What is this question asking for?-->Test this code, find an error in the program and "construct an instance to demonstrate the error" (in C)

texts:
I am learning the basics of the language C, and so far we have covered up to loops. This question is related to my assignment. The problem is I do not understand what the question is asking.

I know the error in the code, but I don't understand what this question is asking me to do? What is an instance? Am I supposed to make a different piece of code? Because I am pretty sure the error is a semantic one(knowledge based rather than syntax). Here is the code anyways just for context:


texts:
I have the following question, and I need to write it as an integer programming problem:
A manager of a company wants to by presents to his 100 employers. He can buy the presents from two different suppliers:

Every present costs 110\$. For any present above 500, the manager would have to pay 5\$ extra for insurance (for example, for 502 presents, there will be 10\$ extra for insurance).
Every present costs 120$. For any present above 300, there is a discount of 30% (each present above 300 costs 84\$).

I need to find how many presents he should buy from each supplier, in order to spend the minimal amount of money.
I defined:
$x_1, x_2$ - The number of presents to buy from each supplier.
$z_1$ - Indicator which represents whether or not $x_1 \ge501$
$z_2$ - Indicator which represents whether or not $x_2 \ge301$
I know how to represents the indicators using linear functions, but I don't know how to find a linear objective function.
My best suggestion is:
$$ 110x_1+5z_1(x_1-500)+120x_2-36z_2(x_2-300) $$
However, this is not a linear function, because I multiply the decision variables.
How can I turn it into a linear function?


texts: Where are 'Base & Bounds' registers located?

texts:
I read about virtual memory from L08/CS152 of U.C Berkeley and used to deep dive into the details of VM hardware implementation, yet didn't find any document or figure on the course specifying where the 4 “Base & Bounds“ registers (Data Bound Register, Data Base Register, Program Bound Register, Program Bound Register) used in the figure below are located. In order to have more detailed information, I did many searches for “MMU architecture”, “X86 architecture”, “bound register',  “base register”, and so on .. But without success.

Are B&B registers located on the MMU or on the CPU? Can anyone provide any related hardware architecture reference?


texts: Is there a formal term for functions that have static state across executions?

texts:
Two examples, one in PHP:

function adder($i){
  static $a = 0;
  $a += $i;
  return $a;
}

A similar effect can be achieved with closures in javascript:

var adder = (function(){
  var a = 0;
  return function(i){
    a += i;
    return a;
  }
})();

In javascript I've really just created an object. Implementation details not withstanding, does stateful-functions have a formal name?


texts: Guaranteed existence of a blocking set in the accept definition of Stellar

texts: In the SCP, condition 2 of the accept definition allows a node to vote for one statement and later accept a contradictory one. Condition 2 assumes the existence of a v-blocking set which has not only voted for a but also accepted it. What is the argument to show that this is the case?


texts: Prove that the language of squares is not regular using homomorphism

texts:
If a language like $L$ is regular, then any homomorphism of $L$ is regular too. So, if $h(L)$ is not regular, then we can conclude that $L$ is not regular.

Assume that the language $L=\{yy:y \in \{0,1\}^*\}$ is given.
Can you provide a homomorphism for $L$ like $h$ that $h(L)$ is not regular?

Note : I don't want a simple homomorphism. I want a good homomorphism that $h(L)$ is obviously not regular. So there should be no need to use pumping lemma to prove that $h(L)$ is not regular. But you can use the pigeonhole principle.


texts: Decision problems in $\mathsf{P}$ without fast algorithms

texts:
What are some examples of difficult decision problems that can be solved in polynomial time? I'm looking for problems for which the optimal algorithm is "slow", or problems for which the fastest known algorithm is "slow".

Here are two examples:

Recognition of perfect graphs. In their FOCS'03 paper [1] Cornuéjols, Liu and Vuskovic gave an $O(n^{10})$ time algorithm for the problem, where $n$ is the number of vertices. I'm not sure if this bound has been improved upon, but as I understand it, more or less a breakthrough is needed to obtain a faster algorithm. (The authors give an $O(n^9)$ time algorithm in the journal version of [1], see here).
Recognition of map graphs. Thorup [2] gave a rather complex algorithm with the exponent being (about?) $120$. Perhaps this has been even dramatically improved upon, but I don't have a good reference.

I'm especially interested in problems that have practical importance, and obtaining a "fast" (or even a practical) algorithm has been open for several years.

[1] Cornuéjols, Gérard, Xinming Liu, and Kristina Vuskovic. "A polynomial algorithm for recognizing perfect graphs." Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on. IEEE, 2003.

[2] Thorup, Mikkel. "Map graphs in polynomial time." Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on. IEEE, 1998.


texts:
I am learning how to minimize a DFA. One helpful approach is the Myhill-Nerode Theorem, which explains:

Draw a table for all pairs of states (P,Q)
Mark all pairs where P is a final state and Q is not a final state.
If there are any unmarked pairs such that [delta(P,x), delta(Q,x)] is marked, then mark (P,Q)
Combine all the unmarked pairs and make them a single state in the minimized DFA.

I'm a little lost on the details of the third step.

In the example here, the unmarked pairs in the resulting table are (a,b), (c,d), (c,e), (d,e). The tutorial combines the latter three into a single state such that there are now two states (a,b) (c,d,e).

What are the rules for combining unmarked pairs? Can you combine two pairs
as long as each pair shares a letter with the other? And does the new, merged state take the union of transitions of previous state?

For instance, if state C went to state F on 0 and state D went to state F on 1 and state E never went to state F, then the new, merged state would go to F on 0 or 1, yes?


texts: Regular expression for set of strings with no two consecutive 1's?

texts:
I'm having trouble figuring out a regular expression over the alphabet {0,1} that contains all strings with no TWO consecutive 1's.

I'm also wondering if there is a pattern that could be extended to three consecutive 1s. etc...

Would something like this be correct?

(0 U (10))* U (0 U (10))* 1


texts: Big O understanding given different input sizes

texts:
I have a question about big O notation. Let's say I have 3 algorithms which, for an input of size $n$, have time complexity $O(n)$, $O(n^2)$ and $O(n \log n)$, respectively. Assume that all 3 algorithms take $a$, $b$ and $c$ seconds for the worst, average and best cases given an input of size $n$. What could be the actual time of these 3 algorithms given an input of size $2n$? Based on my understanding it should be:

$O(n)$: $2a$, $2b$, and $2c$.
$O(n^2)$: $a^2$, $b^2$, and $c^2$.
$O(n \log n)$: $a \log a$, $b \log b$, and $c \log c$.

My questions are:

Is this correct?
In case not, why?
In case this is correct, would the same hold for $\Theta$ and $\Omega$?


texts: Randomized response vs Output Perturbation

texts:
what are the difference between Randomized response and output perturbation?

The only one I can think of is that Randomized Response's output is not always perturbated while in the other case it is.


texts: Preprocess an array for counting an element in a slice (reduction to RMQ?)

texts:
Given an array $a_1,\ldots,a_n$ of natural numbers $\leq k$, where $k$ is a constant, I want to answer in $O(1)$ queries of the form: "how many times does $m$ appear in the array between indices $i$ and $j$"?

The array should be preprocessed in linear time. In particular I'd like to know if there's a reduction to Range Minimum Query.

This is equivalent to RMQ in the case where $k=1$ and you want to query the number of ones within an interval. So we can use it.
I couldn't answer my own question because of limits of SE.


texts: Semi-decidable problems with linear bound

texts:
Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a computable function. (Otherwise we’d know how long to wait for a positive answer. If the algorithm runs longer than that we know that the answer is no and the problem would be solvable.)

My question is now: Can such an algorithm still have a, say, a run-time bound linear (polynomial, constant,...) in the input size, but with an uncomputable constant? Or would that still allow me to decide the problem? Are there example?


texts: Membership in 1, 5, 2, 13, 10, ... (recursively defined sequence)

texts:
Find if a given integer is in the series $1, 5, 2, 13, 10, \dots$ in the most efficient way, where the sequence is given by
$$
f(n) =
\begin{cases}
1 & n=1, \\
2f(\tfrac{n}{2})+3 & n \text{ even}, \\
2f(\tfrac{n-1}{2}) & n>1 \text{ odd}.
\end{cases}
$$
The series is infinite of course, and $x$ can be a number with at most 9 digits. The idea is not to hardcode this and maybe find some kind of correlation that will allow you to solve this fast. I want to say that I have an idea of how to solve it but I don't.


texts: Are there typing rules for specific coinductive types such as conat or stream, or even in general the M-types?


texts: Where can I learn theoretical aspect of Reinforcement learning

texts: Every RL paper has a section with some finite sample analysis/error bound/ convergence proofs. I have difficulty fully understanding such proofs and coming up with my own analysis for my personal projects. Can anyone suggest books/courses where I can develop my skills to do such work?


texts:
Disclaimer: If not interested in my background, skip directly to the question below!

I am a complete newbie when it comes to complexity theory. I come from a physics background and I am currently working through the complexity-theoretical arguments behind Boson sampling and and other quantum supremacy proposals. These rely crucially on the Conjecture, that the Polynomial Hierarchy does not collapse to its third level.

The small piece of the argument, I am concerned with is the following:

Theorem 1: If $P^{\#P}=BPP^{NP}$ then the PH collapses to its third level, i.e. $PH=\Sigma_3$.

What I know:

By Toda's Theorem, $PH\subseteq P^{\#P}$, thus to prove Theorem 1, it would suffice to show that $BPP^{NP}\subseteq \Sigma_3$.
I have also found out (and seen proofs of) that $BPP\subseteq \Sigma_2$.

To me it looks like, that because of $BPP\subseteq \Sigma_2$, it should be true that $BPP^{NP}\subseteq \Sigma_2^{NP}$. Now, if $\Sigma_2^{NP}$ was the same as $NP^{\Sigma_2}=\Sigma_3$, I would be done proving Theorem 1.

Question: It is true, though? i.e. is

$$ \left(NP^{NP}\right)^{NP} \overset{?}{=}NP^{\left(NP^{NP}\right)}$$

and does the ordering of the parentheses in these oracle constructions matter? If it is not, I would be grateful, if someone could point out, how to prove Theorem 1.


texts: Is the set of all context-free languages contained in the set of all languages that have a w-grammar?

texts:
Word grammar (w-grammar) is a context free grammar in which all laws are of the following forms:
$A \rightarrow B, A \rightarrow \epsilon, A \rightarrow w_1B, A \rightarrow Bw_2$
$A, B \in N$ (nonterminal), $w_i \in \Sigma^\ast$
$ L_{w-grammar} $ - set of all languages that have a w-grammar
$ L_{CFG} $ - set of all languages that have a context free grammar
Is the following statement is true $ L_{CFG} \subseteq L_{w-grammar} $ ?


texts: Finding constrained random time intervals with a constrain also on their sum

texts:
I'm searching to devise an algorithm that finds a set of n time intervals with a random duration between min and max. On top of that, the total duration is also given (tot).

For example:

  n = 15

  min = 30 s

  max = 90 s

  tot = 15 minutes

means:
"Find 15 time intervals, each of a duration between 30 and 90 seconds, which, when summed together, produce a total time interval of 15 minutes"

To check whether there is a solution to the problem I would just make sure that
min * n <= tot <= max * n.

To make sure that the total duration is equal to tot I would apply a found ratio to all the time intervals.

However, how to make sure that the min and max constrains are met even after the ratio is applied? Am I on the right track?


texts: A visitor at a political convention with n delegates

texts:
So I have been asked to specifically construct a divide and conquer algorithm for the question:
"You  are  a  visitor  at  a  political  convention  with n delegates;  each  delegate  is  a  member  of exactly one political party.  It is impossible to tell which political party any delegate belongs to;  in  particular,  you  will  be  summarily  ejected  from  the  convention  if  you  ask.   However,you can determine whether any pair of delegates belong to the same party or not simply by introducing  them  to  each  other—members  of  the  same  party  always  greet  each  other  with smiles  and  friendly  handshakes;  members  of  different  parties  always  greet  each  other  with angry stares and insults.
Suppose more than half of the delegates belong to the same political party.  Describe an  efficient  algorithm  that  identifies  all  members  of  this  majority  party.   How  many introductions do you need?
So I came up with the pseudocode:
AMajorityPolitician(set of politicians S):

 if |S| == 1 :
  return S
 L = AMajorityPolitician(half of S)
 R = AMajorityPolitician(other half of S)

 if party[first item in L] == party[first item in R]:
  return L U R
 else
  return max(|L|,|R|)

AllMajorityPolititians(set S of n politicians):

 M = AMajorityPolitician(S)

 first = first item of M

 ans = {first}
 for each p in S:
   if first smiles to p:
     ans = ans U {p}

 return ans

But I don't think this works because if I have a list of politicians parties such as: 2,2,1,1,1 and it is split s.t. L=2,2,1 and R=1,1 then majority of L is party 2 of size 2 and majority of R is party 1 of size 2 so algorithm could pick 2 as the majority.
But I don't really know where to go from here to fix it. Do you guys have any suggestions?


texts: How to partition a digraph for later parallel computation?

texts:
I have a directed graph where all the nodes represent some task that needs to be computed. I need to compute the order of these tasks and also detect any cycles. Running Tarjan's algorithm on the graph gives me both.

To the problem:

I was wondering if there exists a good way to make use of parallelization. For instance, node A goes to node B and C. We can then compute task B and [C,F] in parallel. After that we can compute tasks [E,I] and [D,G] in parallel as well.

What kind of algorithm could detect which subsets of the tasks that can be computed in parallel?

I was thinking about the following procedure:

Select a start node $n_1$ and a finish node $n_f$.
Compute all possible paths $n_1 \rightarrow n_f$.
If there is only one path then this whole branch can be assigned to be computed by one processor.
Then I mark all nodes on this path.
Now i select another finishing node and repeat until I have marked all nodes.
Should there exist more than one path $n_1 \rightarrow n_f$ I reduce the path length by one and instead compute all paths $n_1 \rightarrow n_{f-1}$ where $n_{f-1}$ is a parent to $n_{f}$


texts: Decidability of bitstring languages with no ones' complements

texts:
For any string $s \in \{0,1\}^*$, let the ones' complement of $s$, denoted $1_c(s)$, be the string obtained by flipping all bits in $s$. For example, $1_c(001100) = 110011$. Now call a language $L \subset \{0,1\}^*$ ones' complement asymmetric or OCA  for short, if for every string $s \in \{0,1\}^+$, precisely one of $s$ and $1_c(s)$ is in $L$.

I want to come up with a mapping reduction from a language $L \subset \{0,1\}^*$ to an OCA language (and vice-versa) so as to prove the existence of decidable/recognizable and undecidable/co-recognizable and undecidable, etc., OCA languages. My problem is especially that we require every string in $\{0,1\}^+$ to be such that either it or its ones' complement appears in any OCA language. This seems particularly problematic if $L$ lacks strings of a particular length, meaning it isn't obvious how we'd go about constructing an OCA language from $L$.


texts: How to solve recursion with two separate converges rates

texts:
What is the correct way to solve the following recursion:
$T(n)=T(\lceil\frac{n}{2}\rceil) + T(n-2)$
Or basically any recursion that has two parts which converge in a different rate.
I'm trying to get big $O$ approximation, as tight as possible, but I couldn't figure it out with any "traditional" approach.