What is a non-ambiguous CFG for generating the set of natural numbers? I'm trying to write a non-ambiguous context-free grammar that can generate the set of natural numbers, including the 0. My current solution is the following grammar:

$\mathcal{G}: S \rightarrow 0\ |\ ...\ |\ 9\ |\ 1S\ |\ ...\ |\ 9S$

From what I understand, there is not an algorithm to determine whether my guess is correct, thus only I—or you—can convince myself it is (or it is not, of course).

"From what I understand, there is not an algorithm to determine whether my guess is correct." It looks like your understanding is wrong.

There is no algorithm that determines whether any given formal language grammar is ambiguous context-free. There is no algorithm that determines whether any given formal language grammar is inherently ambiguous context-free. However, it is possible to decide many particular grammars is (inherently) ambiguous context-free or not by some algorithms.  For example, the trivial algorithm that just outputs "ambiguous context-free" determines the grammar with rules $S\to A|B$, $A\to c$, $B\to c$ as ambiguous context-free. For example, the trivial algorithm that always outputs "not inherently ambiguous context-free" determines all regular grammars as not inherently ambiguous context-free.

As said by rici, your grammar is regular. There is an algorithm that can decide any given regular grammar is ambiguous or not. (Immediately by definition, a regular language is context-free.). As demonstrated by Dmitri Urbanowicz, your grammar is, in fact, not ambiguous.

As said by Dmitri Urbanowicz, your grammar is wrong since it cannot generate number 101. Here is a correct grammar, which can be shown to be non-ambiguous context-free.
$\quad S \to BT|A$
$\quad T \to AT|A$
$\quad A \to B|0$
$\quad B \to 1|2|3|4|5|6|7|8|9$


Complexities of basic operations of searching and sorting algorithms Wiki has a good cheat sheet, but however it does not involve no. of comparisons or swaps. (though no. of swaps is usually decides its complexity). So I created the following. Is the following info is correct ? Please let me know if there is any error, I will correct it.

Insertion Sort:

Average Case / Worst Case : $\Theta(n^2)$ ; happens when input is
already sorted in descending order
Best Case : $\Theta(n)$ ; when input is already sorted
No. of comparisons : $\Theta(n^2)$ in worst case & $\Theta(n)$ in best case
No. of swaps : $\Theta(n^2)$ in worst/average case & $0$ in Best case

Selection Sort:

Average Case / Worst Case / Best Case: $\Theta(n^2)$
No. of comparisons : $\Theta(n^2)$
No. of swaps : $\Theta(n)$ in worst/average case & $0$ in best case
At most the algorithm requires N swaps, once you swap an element into place, you never touch it again.

Merge Sort :

Average Case / Worst Case / Best case : $\Theta(nlgn)$ ; doesn't matter at all whether the input is sorted or not
No. of comparisons : $\Theta(n+m)$ in worst case & $\Theta(n)$ in best case ; assuming we are merging two array of size n & m where $n<m$
No. of swaps : No swaps ! [but requires extra memory, not in-place sort]

Quick Sort:

Worst Case : $\Theta(n^2)$ ; happens input is already sorted
Best Case : $\Theta(nlogn)$ ; when pivot divides array in exactly half
No. of comparisons : $\Theta(n^2)$ in worst case & $\Theta(nlogn)$ in best case
No. of swaps : $\Theta(n^2)$ in worst case & $0$ in best case

Bubble Sort:

Worst Case : $\Theta(n^2)$
Best Case : $\Theta(n)$ ; on already sorted
No. of comparisons : $\Theta(n^2)$ in worst case & best case
No. of swaps : $\Theta(n^2)$ in worst case & $0$ in best case

Linear Search:

Worst Case : $\Theta(n)$ ; search key not present or last element
Best Case : $\Theta(1)$ ; first element
No. of comparisons : $\Theta(n)$ in worst case & $1$ in best case

Binary Search:

Worst case/Average case : $\Theta(logn)$
Best Case : $\Theta(1)$ ; when key is middle element
No. of comparisons : $\Theta(logn)$ in worst/average case & $1$ in best case

I have considered only basic searching & sorting algorithms.
It is assumed above that sorting algorithms produce output in ascending order
Sources : The awesome CLRS and this Wiki

For general algorithm of bubble sort worst case comparisons are $\Theta(n^2)$ But for special case algorithm where in you add a flag to indicate that there has been a swap in previous pass. If there were no swaps then we come out of the loop since array is already sorted. In this case comparisons are $n$ not 0.

For Quick sort you have mentioned that worst case swaps are $n^2$. Well worst case scenario for quick sort is when all elements are in sorted order thus there won't be any swaps so it should be zero.


Efficient Algorithm Linear Temporal Logic to Deterministic Rabin Automata I am trying to construct an equivalent Deterministic Rabin Automata (DRA) given a Linear Temporal Logic (LTL) Formula. One (expensive) way to do this would be to construct an equivalent Non-deterministic Buchi Automata and then determinize it using Safra's construction.

I am interested to know whether there exist efficient algorithms which can
1. Directly construct DRA from LTL without intermediate NBA construction.
2. Are there any existing tools to do this.

[This is my first question posted here. Kindly point in comment, if I missed any conventions of the forum. Thank you.]

There is a very recent tool to translate from LTL directly to deterministic Rabin automata. It can be obtained here:

https://www7.in.tum.de/~sickert/projects/ltl2dra/

The page not only contains a link to the downloadable implementation, but also has link to a technical report that describes the construction for the translation. Apparently, a peer-reviewed paper about the construction has not appeared yet. Note that the construction is rather involved - the paper has 50 pages, and there is a reason why for many years, the detour though Büchi automata was (and somewhat still is) state-of-the-art.

Note that the computational complexity of the direct translation is not better than the one that one can obtain by translating LTL to non-det. Büchi automata and then applying Safra's method.


Efficient set data structure supporting insert and set equal What's the best way to represent sets that support the following two operations:

Insert(s, i)  - adds nonnegative integer i to set s
Equal(s1, s2) - Tests if s1 and s2 are the same set.

In addition, I have an upper bound on the integers added to each set. That is, I know $N$ such that $0 \le i < N$.

I'm also willing to accept that Equal is only approximate. ie Equal(s1,s2) could be true even if s1 != s2. I guess in that case I'm looking for a hash function. Does anyone know a good hash function?

We can assume that an integer is only inserted once into a set. $N$ can be about 3-5 million, and the number of sets I want to test for equality can be in the thousands.

Let $F$ be a finite field with efficient procedures for addition and

multiplication and almost-uniform sampling. $\:$ Let $z$ be a field element.

(I use that letter because things will be slightly more convenient if $z$ is

the zero element, although efficient sampling means that even if one

can't find the zero of $F\hspace{-0.03 in}$, one should still be able to find a field element.)

To initialize the data structure, sample a field element $x$.

Empty sets are represented by $z$, Insert(s,i) adds $x^i$ to the representation of s,

and Equal(s1,s2) just tests if the two representing field elements are equal.

Since addition is associative and commutative, there are no false negatives. $\:$ If each integer is only inserted once into a set, then the probability of there being at least one false positive is at most

the distance from $x$'s distribution to uniform $\;+\;$ $((N\cdot \text{number of equality tests})\hspace{.02 in}/($$\hspace{-0.03 in}\operatorname{card}$$(F\hspace{.03 in})) \;\;$.

To efficiently compute $x^i\hspace{-0.04 in}$, see this paper, and either avoid the methods that involve negative

powers or make slightly stronger assumptions on $F$. $\:$ I would recommend 5.1 on page 14.


Algorithm analysis question in growth of functions How would I solve the following.

An algorithm that is $O(n^2)$ takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500?

Can anyone help me answer dis.

Formally, there is absolutely no way to tell.  O( ) notation is about the limiting behavior of a function (in this case, the running time of an algorithm) as its argument (in this case, the input size) grows to infinity.  Without more information, it is absolutely impossible, even in principle, to predict behavior in the limit from a finite number of function values.


Finding the minimum vertex cover of planar graph given the planar representation The minimum vertex cover problem is $NP$-hard for the planar graph of degree at most $3$. However, the minimum vertex cover can be easily found in some certain types of planar graph, given the planar representation. For example, the planar graph that every face boundary is a cycle of even length.

Is there any proof that shows the $NP$-hardness of the minimum vertex cover of the (general) planar graph, given its planar representation as an auxiliary input?

Given a planar graph, one can always compute a combinatorial embedding for it.


Proof that (x-y)(x+y) is more accurate than x²-y² I was carrying on my reading of What Every Computer Scientist Should Know About Floating-Point Arithmetic but got stuck on the proof of Theorem 2 (page 34).

At some point it says:
\begin{align}
(x \otimes x) \ominus (y \otimes y) & = \left[x^2(1 + \delta_1) - y^2(1 + \delta_2)\right](1 + \delta_3) \\
& = \left[(x^2 - y^2)(1 + \delta_1) + (\delta_1 - \delta_2)y^2\right](1 + \delta_3) \\
\end{align}
I'm ok with the rewriting, but I don't understand the argument that:

  When $x$ and $y$ are nearby, the error term $(\delta_1 - \delta_2)y^2$ can
  be as large as the result $x^2 - y^2$.

This doesn't make much sens to me right now. I understand that if both quantities are close to each other, then the relative error is close to $1$. But not why they should be close to each other.

Suppose $y = x + \Delta$. Then $(x^2 - y^2) = x^2 - (x^2 + 2\Delta x + \Delta^2) = - (2\Delta x + \Delta^2)$ with leading term on the order of $2 \Delta x$. Multiply by $1 + \delta_1$ and that's still the leading term.

Compare to $(\delta_1 - \delta_2) y^2$ with leading term $(\delta_1 - \delta_2) x^2$.


Why every rational langage is the image of a local automaton I have seen this result but I don’t understand why it’s true :

  Every rational language is the image of a local language by a morphism : $\phi : \Sigma^{*’} \to \Sigma^*$

I know what a local automaton is. It’s just an automaton that recognizes a local language. A local language is basically a language where all factors of size two are not in a certain set $S$.
Now if I take a morphism from this language then it will still give me a local language right ? (i.e. the image of local language by a morphism is a local language). So I didn’t understand this result, I mean every rational language is not local...

Thank you !

(1) Indeed. Every regular [=rational] language is the morphic image of a local [=2-testable] language.

This is seen as follows. A finite state automaton can be "encoded" by a 2-testable language by using the transitions as letters. So we consider symbols $(p,a,q)$. The corresponding language is 2-testable: basically test whether the transitions are consecutive which is clear from letter pairs: $(p,a,\underline q)(\underline q,b,r)$. We find the original language by applying a coding: $(p,a,q)$ maps to $a$.

(2) No. Local languages are not closed under codings. $(ab)^*$ is a local language. Initial letter $a$, final letter $b$, two letter substrings $ab, ba$. The image $(aa)^*$ is not local. There is no way to distinguish odd length strings from even length strings by just looking at substrings.


Are there improvements on Dana Angluin's algorithm for learning regular sets In her 1987 seminal paper Dana Angluin presents a polynomial time algorithm for learning a DFA from membership queries and theory queries (counterexamples to a proposed DFA).
She shows that if you are trying to learn a minimal DFA with $n$ states, and your largest countexample is of length $m$, then you need to make $O(mn^2)$ membership-queries and at most $n - 1$ theory-queries.
Have there been significant improvements on the number of queries needed to learn a regular set?

References and Related Questions

Dana Angluin (1987) "Learning Regular Sets from Queries and Counterexamples", Infortmation and Computation 75: 87-106

Lower bounds for learning in the membership query and counterexample model

In his answer  on cstheory.SE, Lev Reyzin directed me to Robert Schapire's thesis that improves the bound to $O(n^2 + n\log m)$ membership queries in section 5.4.5. The number of counterexample queries remains unchanged. The algorithm Schapire uses differs in what it does after a counterexample query.

Sketch of the improvement
At the highest level, Schapire forces $(S,E,T)$ from Angluin's algorithm to have the extra condition that for a closed $(S,E,T)$ and each $s_1, s_2 \in S$ if $s_1 \neq s_2$ then $row(s_1) \neq row(s_2)$. This guarantees that $|S| \leq n$ and also makes the consistency property of Angluin's algorithm trivial to satisfy. To ensure this, he has to handle the results of a counterexample differently.
Given a counterexample $z$, Angluin simply added $z$ and all its prefixes to $S$. Schapire does something more subtle by instead adding a single element $e$ to $E$. This new $e$ will make $(S,E,T)$ to be not closed in Angluin's sense and the update to get closure with introduce at least one new string to $S$ while keeping all rows distinct. The condition on $e$ is:
$$\exists s, s' \in S, a \in \Sigma \quad \text{s.t} \quad row(s) = row(s'a) \; \text{and} \; o(\delta(q_0,se)) \neq o(\delta(q_0,s'ae))$$
Where $o$ is the output function, $q_0$ is the initial state, and $\delta$ the update rule of the true 'unknown' DFA. In otherwords, $e$ must serve as a witness to distinguish the future of $s$ from $s'a$.
To figure out this $e$ from $z$ we do a binary search to figure out a substring $r_i$ such that $z = p_ir_i$ and $0 \leq |p_i| = i < |z|$ such that the behavior of our conjectured-machine differs based on one input character. In more detail, we let $s_i$ be the string corresponding to the state reached in our conjectured machine by following $p_i$. We use binary search (this is where the $\log m$ comes from) to find an $k$ such that $o(\delta(q_0,s_kr_k)) \neq o(\delta(q_0,s_{k+1}r_{k+1})$. In other words, $r_{k+1}$ distinguishes two states that our conjectured machines finds equivalent and thus satisfies the condition on $e$, so we add it to $E$.


Data structure used to implement recursion Which data structure can be used to "eliminate" recursion from a recursive program? Array, stack, queue, or list? How is it used to that end?

When I eliminate recursion from the program computing factorial $n! = n(n-1)!$, I replace recursion with a loop. But I don't see how to do a similar transformation in general.

Let me restate your question: Which data structure does the CPU use to implement recursion? This data structure is knows as the call stack. As you can imagine, it's a stack. I strongly suggest that you consult the Wikipedia page (or any other source) and try to understand why a stack is used and how it works. This is much more important than answering a multiple-choice question.


Which time series prediction techniques are useful given harmonic properties? I have a time series dataset where events have harmonic properties, and seemingly the nature of the event's early segments can determine the remainder of the event (see example 1's oscillations). Additionally, these early segments might determine the properties/likelihood of some following/associated event (example 2).

Which time series prediction techniques may be suitable for making predictions based on this kind of behaviour? Specifically:

For determining how an event, from appearance, might oscillate and dissipate (forecast/extrapolation).
For predicting what event may follow (probabilistic model).

I am not very knowledgeable in this, but seemingly dynamic ARIMA may be appropriate for the extrapolation at a given point. Also, the early segment might be suitable as a feature for prediction in some other model (e.g. SVC)?

Example Event 1

Example Event 2

EDIT: I want to avoid fitting a highly specialised/targeted model based on observation - but would be happy for some process to learn this representation. I am interested in learning about existing models/methodologies that could be applied to this problem, references would be great.

I would suggest to make the correlation plot and observe the dependencies. Yes, ARIMA, is so far the best forecasting model for time series and it should work in this data set too.
For the implementation, in R, there is auto ARIMA, which automatically takes the best suited valued for the parameters(
    p: The number of lag observations included in the model, also called the lag order.
    d: The number of times that the raw observations are differenced, also called the degree of differencing.
    q: The size of the moving average window, also called the order of moving average.)

But as far as I am concerned, in Python, you have to manually tune the parameters by yourself by analyzing the correlation plot. This is a very well explained beginner level tutorial for the implementation in Python.
Let me know in the comments if it works (or not).


Memory Consistency vs Cache Coherence Is it true that Sequential Consistency is a stronger property than Cache Coherence?

According to

  Sorin, Daniel J; Hill, Mark D; Wood, David A: A Primer on Memory Consistency and Cache Coherence, Morgan & Claypool, 2011

sequential consistency can be described as (not formally):

  Sequential consistency memory model specifies that the system must appear to execute all threads’ loads and stores to all memory locations in a total order that respects the program order of each thread. Each load gets the value of the most recent store in that total order.

In other words, system is sequentially consistent, if given memory events (loads and stores) of each thread we can order all these events such that: 1) for each thread the order of its events is preserved, and 2) the global order is serial (any load returns latest value stored).

Now they continue and describe coherence:

  A definition of coherence that is analogous to the definition of Sequential Consistency is that a coherent system must appear to execute all threads’ loads and stores to a single memory location in a total order that respects the program order of each thread.

In other words, system is coherent, if given memory events of each thread for each location we can order events for that location, such that: 1) for each thread the order of its events to that location is preserved, and 2) for each location the order is serial.

Finally, they point out the difference:

  This definition highlights an important distinction between coherence and consistency: coherence is specified on a per-memory location basis, whereas consistency is specified with respect to all memory locations.

So it seems the difference is that for coherent systems we need a total order on all events for each location (thus the ordering between events for particular location), while for consistent systems the total order should be defined on the all events (and thus the ordering is also between events for different locations)?

Does that mean that coherence is less strict that consistency? (which seems amusing!) Are there traces that are coherent but not consistent?

As you pointed out, coherence is a property of an individual memory location while consistency refers to the order of accesses to all memory locations.  Sequential consistency is a strictly stronger property than coherence.  That is: every system that is sequentially consistent is also coherent at every memory location.  The opposite is not true, a memory that is coherent at every location is not necessarily sequentially consistent.  In fact, there are many real cache-coherent multiprocessors where the memory model is only weakly consistent (there are cases where different processors observe accesses to different locations happen in different orders.)

Proof of sequentially consistent implies coherent:

Given any trace from a sequentially consistent system, by definition that trace must have a total order that is agreed on by every processor in the system.  Now look at the accesses just to location $x$ in that trace.  Because a total order is transitive, the accesses just to location $x$ also have a total order on them that is agreed on by every processor in the system.  Thus all memory locations are coherent.

The reverse doesn't work out.  Consider two coherent memory locations $x$ and $y$ with just a single access to each $x_0$ and $y_0$.  All the processors agree on the order of accesses to location $x$ and all the processors agree on the total order of accesses to location $y$, but some processors may observe the order $x \rightarrow y$, while others may observe the order $y \rightarrow x$.  So coherence doesn't imply sequential consistency.

This can lead to surprising results.  For example

initially A=B=0
process 1               process 2
store A := 1            load B (gets 1)
store B := 1            load A (gets 0)

This trace is coherent:

for A the order is: proc2 loads A(gets 0), proc1 stores A:=1
for B the order is: proc1 stores B:=1, proc2 loads B(gets 1)

But it is not consistent! Since if proc2 load B returns 1, then proc1 store A := 1 already happened and proc2 load A should also return 1.


Add lines to star with fixed coordinates maximizing smallest angle I have the following problem:

There are existing stars (as in graph-theory stars) with a fixed representation in a 2D coordinate space, meaning that angles between the edges are not allowed to change.

Now I want to add additional edges from the star center. Both the amount of existing edges and the amount of edges to add can vary.

How can the new edges be added in a way that maximizes the smallest angle between edges in the resulting star? For this minimization, the angles between newly added edges, as well as the angles between newly added and existing edges are relevant.

Here are two trivial examples, the black edges are the existing ones, the blue ones the newly added:

However, there could also be more complex examples, consider adding a different amount of edges(1,2,3,..) to this star:

Ideally, the algorithm is fast and easy to implement in object-oriented programming languages.

Background:
The underlying use case is drawing of Hydrogens for 2D Molecule depictions. In a software, a 2D molecule depiction might be loaded from a file or even drawn by a user, then, the user can trigger an action, adding missing Hydrogen atoms to all existing atoms.
For each atom (star), a varying number of hydrogens depending on the atom type and charge (usually 1-3), should be added and drawn in a visually pleasing way.

The existing edges and angles can not be modified, because they are given by the user. Small angles tend to look bad, therefore, the goal is to maximize the smallest angle.

Currently, this is done by choosing the largest angle, then adding an edge in the middle. Then repeating this until no more edges are to be added. This is very fast and looks reasonably well, but obviously doesn't always find the best solution.

I'll describe an efficient algorithm for this problem.

Suppose we have an angle $\theta$, and we want to find out how many new edges we can add, with the constraint that the minimum angle between all pairs of edges must be at least $\theta$.  Then it's not too hard to compute this.  Pick any adjacent pair of existing edges; suppose they are at angle $\gamma$ from each other.  Then you can add $\lfloor \gamma/\theta \rfloor - 1$ new edges between them, while ensuring the minimum angle remains at least $\theta$.  So, sort all of the existing edges by angle, iterate through each pair of adjacent existing angles, count how many new edges you can add between them (using the formula in the previous sentence), and add them up.  That tells you how many new edges you can add, if you want the minimum angle between edges to be at least $\theta$.

Great.  But in your situation, we don't know $\theta$; we just know that we want to add at least $n$ new edges.  So, use binary search on $\theta$ to find the largest $\theta$ such that you can add at least $n$ new edges while preserving a minimum angle of at least $\theta$.  You can do this by choosing a value of $\theta$, computing how many new edges you can add (using the algorithm of the previous paragraph), then increasing or decreasing $\theta$ according to the rules of binary search based on whether the number of new edges you could add was above or below $n$.


Forming polylines from a list of individual lines I want to optimize a SVG path made entirely of lines. Given a list of lines, each made of two 2D points connected together, I want to find an equivalent list of polylines. For example:

M10,10 L20,10 M20,10 L20,20 becomes M10,10 L20,10 L20,20.One line ends where there other begins, it can become a polyline.
M10,10 L20,10 M20,10 L30,10 becomes M10,10 L30,10.The second line extends the first line, they can be merged into one line.

I found a basic way to do it in $O(n^2)$.

Start with an empty list of polylines.
Loop over all invidivual lines. If a point of the line is the same as one of the polylines head or tail, extend the polyline. If the slope between the new and last points is the same as the slope between the last and before last points, then only replace the last point with the new point.
Remove the line from the list.
Repeat until list is empty.

As you can guess this algorithm performs quite badly, taking forever with as little as 20,000 lines.

How to do it in $O(n)$?

Loop over all invidivual lines. If a point of the line is the same as one of the polylines head or tail, extend the polyline

(My emphasis). How are you doing that test? To take $\Theta(n^2)$ time, I think you must be testing each point by linear scan in $\Theta(n)$. Use a decent hashmap instead and it will take $\Theta(1)$ on average.


Preparing precedence graph from fork and join code I was referring to this page which defines fork, join and precedence graph as follows:

  When the statement Fork(label) is executed by a thread of control, a second thread of control is started from the statement with the specified label. The two threads execute concurrently.
  When the statement Join(count) is executed, where count is an integer variable, the value of count is decremented. If the resulting value is positive the executing thread is terminated.
  A PRECEDENCE GRAPH is a directed, acyclic graph where nodes represent sequential activities and where arcs, say from node i to node j, require that activity i complete before activity j can start.

Base upon this I have been asked to draw precedence graph for a code containing fork and join constructs. For simple code, I can do. Also once given both code and precedence graph, I can see how the two correspond to each other. However when the code gets little bit complex, it becomes difficult to prepare precedence graph for me. Also doing reverse, from precedence graph preparing fork-join code is almost always difficult for me.

Can anyone give me intuitive stepwise procedure explaining how to obtain fork-join code from any given precedence graph?

Can we take example of following graph to apply the steps and get the fork and join code:

x=2;
y=2;
z=2;

p1;

Fork L1  ; start p2

Fork L2 ; start p3

goto L3 ; stat P4

L1: p2;

fork L3 ;start p4;

goto L5

L3: join (x)

P4;

L4:  join(y)

s6;

Quit();

L2 : P3;

L5:  join(y)

 P5;

 goto L4


Is English Turing-complete? Is English Turing-complete?
Intuitively it makes sense that English is Turing complete, since you can talk someone through building a Turing machine. But I also think there might be some operators used in programming that aren't used in person-to-person communication, at least in daily life.
Also, what level of English is required until it becomes Turing complete? For example: 1st grade? College level?

English is neither a language with a given operational semantics nor a model of computation of any other kind. Your question does not make sense.


Turing machine Representation for string of 3 letters Can someone explain to me what this statement implies? I am assuming that it means that a string consisting of three characters repeated. What I don't understand is if the repeated string is all 0s or all 1s or both?

Give the state diagram of a machine (any Turing-Complete model) that decides the following languages over {0,1}:

{w : w = xxx, x ∈ Σ*}

The language you are trying to decide here is xxx: that is, three copies of x. What is x? Well, it can be anything in $\Sigma *$: any string in your alphabet. (Usually this means "any binary string", but you can also use a different alphabet, the principle will be the same.)

So you're looking for any string which consists of something repeated three times. So strings in the language include 111, and 000, and ε (the empty string), and 100100100, and 101011010110101.

As for the machine that recognizes this, recognizing the language xx : $x \in \Sigma *$ is a classic demonstration of the power of Turing machines (since this language is neither regular nor context-free). Try starting from that machine and seeing what changes you'd need to make for xxx.


Lexicographically k-th small string The origin problem is here. Now it is deleted.

Suppose I have 3 'available' copies of a, 2 of b, 3 of c, and 4 of d.

I want to know the number of different strings with length $l$ using these characters (but no more than the available copies).
Is there an efficient (i.e. $o(k)$) algorithm for computing the $k$-th smallest string of length $l$ in lexicographic order?

For example, The first string of length 1 is a, the second string of length 3 is aab, the 5th string of length 5 is aaacc (following aaabb, aaabc, aaabd, and aaacb), etc.

What kind of algorithm or math can I use to calculate?

You are asking two questions. The first is an enumeration question, and the second is about generation or encoding/decoding. The enumeration question is a standard combinatorial exercise, which can be solved using exponential generating functions (and algorithmically, using dynamic programming). For example, the number of strings of length $\ell$ in your example is $\ell!$ times the coefficient of $x^\ell$ in the exponential generating function
$$
\left(1 + x + \frac{x^2}{2!}\right)
\left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!}\right)^2
\left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}\right).
$$

For the generation problem, the idea is as follows. Suppose that we want the $k$th lexciographically smallest string of length $\ell$. We will uncover the letters one by one. To find the first letter, we count how many strings of length $\ell$ start with each letter—an instance of the enumeration problem mentioned above—and use this information to determine the first letter. We find the subsequent letters in a very similar way.


Difference between the two regular expression I came across a question to create a regular expression to check whether there are even number of b's in a string of language {a,b}. The expression I came up with is (a+ba*b)*. However I found the solution online to be a*(ba*ba*). Is there any difference? If any where?

Also I know that (a+b)* is equivalent to (a*b*)*. So my solution comes out to be (a*(ba*b))*. So why that extra a*?

Your regular expression (a+ba*b)* won't match the string a which contains zero b's, an even number.  It also won't match the strings bb or bbbb, because the expression requires one or more a's before any occurring b's and requires at least one a between any two pairs of b's.

The regular expression a*(ba*ba*)* is the correct solution.  It allows any number of leading a's and then demands that there if there are b's present there be at least two b's among the remaining a's.  Thereafter b's are matched in groups of two among the a's and matching will fail if a b occurs outside such a pair.

The regular expression a*(ba*b)* is wrong because it won't match strings with a's between pairs of b's, such as the string bbaabb.


Further papers or code on SMA*+? I'm interested in the Lovinger and Zhang paper Enhanced Simplified Memory-bounded A Star (SMA*+).   Are there any further papers on this algorithm or publicly-visible code (in any language) implementing it?
I have some things I'd like to understand better about the algorithm (apologies, they're quite basic).

What is the precise relationship between a state and a node in Algorithm 1?   They are clearly not synonyms otherwise $s(n)$ would not exist.
How does one efficiently determine the parent of $w$ in Algorithm 2?   Is it the case that $\forall n \vert n \in O$, $parent(n) \in O$?  If yes, is this simply because we only cull leaves?
Some problems (including the one I'm interested in) exhibit cycles.   If I encounter two identical  states $n$, $m$ at different depths $g(n) > g(m)$ I can always discount $n$.  As far as I can see though, nothing would seem to stop SMA*+ exploring some cycle $m \rightarrow x \rightarrow  y \rightarrow  z \rightarrow  n \rightarrow  m$ releatedly at ever-greater depth.   If this idea is wrong, what prunes these cycles?  If this idea is right, is there a simple way of avoiding this?    Do I have to simply prune $m$ from the successors of $n$ when computing $N$?

Your third question provides a hint as to why $s(n) \neq n$,
where $n$ is a node and $s(n)$ is the state of $n$.
Different nodes may contain the same state
but different parents,
and the path of a node may contain the same state multiple times
if it contains a cycle.
Theoretically,
you could define $path(n) = n$.
Practically,
it is useful to define $n$ as a record or class
containing useful data about $n$,
which brings us to:

You can store $parent(n)$ in your data structure for $n$
to find the parent of node $w$ in $\mathcal{O}(1)$.
There is no guarantee that $parent(n) \in O$ if $n \in O$.
We remove a node from $O$
and add its children
when it is expanded
in Algorithm 1.
In Algorithm 2,
we add $parent(w)$ to $O$
if it is not already there,
while removing $w$.

In terms of correctness,
you typically don't have to worry about cycles.
As long as the step cost from one state to another is always greater than $0$,
which is almost always the case in practice,
each cycle increases $f(n)$,
making nodes without cycles more favorable.
In terms of performance,
exploring cycles is a waste of time.
In regular A* search
you can detect and remove nodes with cycles
by either looking in the path of a node
or maintaining a set of explored states.
It has been a while since I worked on SMA*+,
but I think I tried to add cycle detection to SMA*+
but ran into an issue.
That could be a good area for future research .

The SMA*+ code is part of a search library I was working on.
It needs cleaning up
before I would consider publishing it,
but I'll post the node code here:
class _SMAStarPlusNode(Node):
    """Implements comparison for heapq."""
    def __init__(self, node, f_cost):
        # Copy attributes from node
        self.__dict__ = node.__dict__

        # Add SMA*+ attributes
        self.f_cost = f_cost
        self.num_successors = 0
        self.child_fs = {}
        self.open = True # Track whether in open list, to avoid scanning entire list

    def __lt__(self, other):
        return (self.f_cost, -self.depth) < (other.f_cost, -other.depth)
    def __le__(self, other):
        return (self.f_cost, -self.depth) <= (other.f_cost, -other.depth)
    def __gt__(self, other):
        return (self.f_cost, -self.depth) > (other.f_cost, -other.depth)
    def __ge__(self, other):
        return (self.f_cost, -self.depth) >= (other.f_cost, -other.depth)

class Node(object):
    """A node in a search tree.

    This class is very minimal, utilizing lazy evaluation for most attributes.
    Since thousands of instances of this class may exist at a time, every attribute
    adds greatly to the memory requirements of the program.
    """

    def __init__(self, parent, state):
        self.parent = parent
        self.state = state

        # Lazily evaluated attributes (added when needed):
        # _path_cost - added in Problem.path_cost
        # _depth
        # _path

    @property
    def depth(self):
        """Return the depth of this node."""

        # Lazily evaluate depth
        try:
            return self._depth
        except AttributeError:
            return self._make_depth()

    def _make_depth(self):
        try:
            # Non root have 1 more depth than their parent
            _depth = self.parent.depth + 1
        except AttributeError:
            # Root node has depth of 0
            _depth = 0

        # Cache and return
        self._depth = _depth
        return _depth

    @property
    def path(self):
        """Return the path to this node.

        Returns:
            tuple; a tuple of states.
        """

        # Lazy evaluation
        try:
            return self._path
        except AttributeError:
            return self._make_path()

    def _make_path(self):
        try:
            # Add current node to path to parent node
            _path = self.parent.path + (self.state,)
        except AttributeError:
            _path = (self.state,)

        # Add to cache
        self._path = _path
        return _path

class Problem(object):
    ...

    def path_cost(self, node):
        """Return the path cost to a given node.

        This method belongs to Problem instead of Node because Node does
        not store Problem (to minimize memory usage).
        """

        # Lazily evalute path cost
        try:
            return node._path_cost
        except AttributeError:
            if node.parent is None:
                _path_cost = 0.0
            else:
                _path_cost = (self.path_cost(node.parent) +
                              self.step_cost(node.parent.state, node.state))

            # Cache
            node._path_cost = _path_cost
            return _path_cost

I removed some code that only existed
to work around Python recursion limitations
while evaluating lazy attributes.
It was big and messy
and hopefully isn't an issue with the latest Python,
but be aware if you copy this code verbatim.


What is a "name/variable of base type" in applied $\pi$-calculus? I'm studying the articleVerifying privacy-type properties of
electronic voting protocols which uses Applied $\pi$-calculus to formalize voting protocols and verifies some privacy-related properties.

In certain parts of the paper they define some transformations over processes which are defined inductively. For example:

  Definition (Process $P^{ch}$) Let $P$ be a plain process and $ch$ a channel name. We define $P^{ch}$ as follows:

  $0^{ch} \equiv 0$
  $(P|Q)^{ch} \equiv P^{ch} \equiv Q^{ch}$
  $(\nu n.P)^{ch} \equiv \nu n.out(ch, n).P^{ch}$ when $n$ is name of base type
  $(\nu n.P)^{ch} \equiv \nu n.P^{ch}$ otherwise
  $\ldots$

The idea is that they want to model a voter, which is a process, that wants to provide information about how he voted to the attacker (think: guy $X$ buys the vote of $Y$ and wants a "receipt" to be sure that $Y$ voted how he wanted).  What I don't understand exactly is when is that $n$ a "name of base type"?

I've read the article Mobile Values, New Names, and Secure Communication where Applied $\pi$-calculus was first defined but here they just say that they assume that terms have some kind of type-system behind the scenes and the only thing they say is that the type system must include the type $\texttt{Channel}\langle \tau\rangle$ for every type $\tau$.

So, does the condition "when $n$ is name of base type" simply means "$n$ is not the name of a channel"? This would make sense, because in formalizing these protocols it is assumed that there exists some private channels between voter and authorities that the attacker can not eavesdrop due to physical limitations (they represent the voting booth).

“Base type” is a type that isn't built from other types. Types built from other types include data structures (e.g. lists, arrays, pairs, …), functions, etc. In the context of the pi-calculus, base types exclude channel types.

Some typical example of base types in practice are integers, booleans, floating point, etc. From a theoretical point of view, a base type is one that is a base case in the type grammar, and more generally this implies that there's no type equation that relates this type with “interesting” constructed types. For example, a value of a base type is not a channel or anything that contains a channel.

“$n$ is name of base type” here means that $n$ is a channel that transports opaque values, as opposed to a channel that can transport a channel name. So $(\nu n.P)^{ch} \equiv \nu n.\mathsf{out}(ch, n).P^{ch}$ holds only when the output operation isn't extruding any of the channels in $P$.


Does my grammar contradict LL ⊆ LR(1)? This answer claims that  $ LL \subseteq  LR \left( 1 \right )$ where $LL = \bigcup_k LL(k)$.

But is this true? Is this grammar a valid counterexample?

$ S \rightarrow a | Aaa $, $ A \rightarrow \varepsilon $

It's easy to show that this grammar is not $LR \left( 1 \right )$, but I think that it is in $LL(2)$ - the longest string that can be derived is two letters so a lookahead of two tokens should be sufficient.

Confusingly, the terms $LL$ and $LR$ are overloaded. There are two related but fundamentally different classes of objects that we'd call $LL$ or $LR$:

The sets of all grammars that are $LL(k)$ or $LR(k)$ for some choice of $k$. Let's call these sets $LL_{CFG}$ and $LR_{CFG}$.
The sets of all languages that have an $LL(k)$ or $LR(k)$ grammar for some choice of $k$. Let's call these sets $LL_{LANG}$ and $LR_{LANG}$.

The example you've given is a grammar that is $LL(2)$ (I believe) but not $LR(1)$. This shows that $LL_{CFG} \not\subseteq LR(1)_{CFG}$. However, there is a different grammar that you could pick for the same language that is $LR(1)$, which follows because $LL_{LANG} \subseteq LR(1)_{LANG}$. This happens because $LR(1)_{LANG}$ is precisely the set of all deterministic context-free languages and all $LL$ languages are deterministic.


Can epsilon be in the input alphabet of an FST? Can epsilon be in the input alphabet of an FST ?

The alphabet $\Sigma$ of an automaton can be any nonempty set of finite symbols. Surely Greek-speakers would be upset if we forbade $\{\alpha, \beta, \dots, \epsilon, \dots, \omega\}$ as a valid alphabet! If you want, you can use $\{\clubsuit,\diamondsuit,\heartsuit,\spadesuit\}$ as your alphabet.  Or $\{A, \alpha, \clubsuit,8\}$. Or any other finite, nonempty set.

However, certain symbols have special meanings and we tend not to use them in automaton alphabets. For example, if you want your alphabet to consist of the symbols $\}$ and $\{$, things get a bit awkward: you start writing $\Sigma = \{\},\{\}$ and, er, yeah, that doesn't quite work.  Likewise, it's confusing if $\Sigma$ contains symbols such as ${}^*$, $($, $)$, $+$ and so on: you can easily write $\Sigma = \{{}^*, (, ), +\}$ but, now, when you try to write regular expressions over that alphabet, it's impossible to tell which characters in the regular expression are symbols from $\Sigma$ and which are operators in the regular expression.

$\epsilon$ fits into this second class. When $\epsilon$ isn't in the alphabet, we use that symbol to denote the empty string. As such, if you include $\epsilon\in\Sigma$, it becomes unclear whether writing "$\epsilon$" means "the empty string" or "the string containing one symbol, which is the Greek equivalent of 'e'". So, as a practical matter, we usually prefer not to use $\epsilon$ as a symbol in the alphabet. If you do need to include $\epsilon$ in your alphabet, you should use some other symbol to denote the empty string and you should say so. Similar reasoning applies to all other symbols that could be confused in this and other ways.


A doubt on converting NOT gate to CNF formula For a NOT gate if $x_1$ is input and $x_2$ is the corresponding output, I see the equivalent CNF (conjunctive normal form) is $(x_1 \lor x_2) \land (\overline x_1 \lor \overline x_2)$.

My expectations was that the CNF should not include $x_2$ as it is the output of the gate. I was rather hoping the formula to be of a form $x_2=F(x_1, b_1, b_2, ...)$ where $b_1$, $b_2$, .. are the boolean constants such that when $x_1$ is zero, the $F(.,.,..)$ would yield true just like the NOT gate.

Can anyone help me understand, how come this CNF including $x_2$ is equivalent to a NOT gate. How to draw a truth table for this CNF form as in what value to assign for $x_2$!

Your formula does actually look like $x_2 = F(x_1)$, it's just written with different symbols.

First, we can rewrite the two clauses using implication. Since $(a \to b) \iff (\neg a \lor b)$, we can rewrite the formula as

$$
(\neg x_1 \to x_2) \land (x_2 \to\neg x_1)
$$

Now, you can recognize that this is $(a \to b) \land (b \to a)$, which is to say $a \iff b$.

$\iff$ as a boolean operator behaves the same way as $=$; it evaluates to true when its left hand side and right hand side are the same. So your formula is equivalent to

$$ x_2 \iff \neg x_1 $$

Viewing this as a constraint (assuming $x_1$ can be treated as "fixed"), $x_2$ is fixed as $x_2 := \neg x_1 $


Write a pseudo code for a Graph algorithm Given a DAG $G=(V, E)$ and a function $f(v)$ which maps every vertex to a unique number from 1 to $|V|$, I need to write a pseudo code for an algorithm that finds for every $v\in V$ the minimal value of $f(u)$, among all vertices $u$ that are reachable from $v$, and save it a an attribute of v. The time complexity of the algorithm needs to be $O(V+E)$ (assuming that time complexity of $f(v)$ is $\Theta (1)$).
I thought about using DFS (or a variation of it) and/or topological sort, but I don't know how to use it in order to solve this problem.
In addition, I need to think about an algorithm that gets an undirected graph and the function $f(v)$, and calculate the same thing for every vertex, and I don't know how to do it either.

Yes, you can use the topological sort. Suppose topological sorting of the vertices gives you the sequence: $v_{1}, \dotsc, v_{n}$ such that there is no edge of the form $(v_{j},v_{i})$ for any $i < j$.
Following would be the pseudocode to compute the minimum reachable $f(u)$ value for each vertex $v_{i} \in V$:
fun()
----- int min_val_reachable[n];    // array that stores minimum reachable f(u) value for each vertex

----- for(i = n to 1; i--)
-------- min_val_reachable[i] = f(v_i) // since a vertex v_i is reachable to itself
-------- for each vertex 'u' in adj_list[v_i]
-------------- if (min_val_reachable[i] > min_val_reachable[u])
-------------------min_val_reachable[i] = min_val_reachable[u]
-------------- end
--------- end
----- end
----- return min_val_reachable[];

The time complexity of the topological sort is $O(|V| + |E|)$, and the time complexity of the above procedure is also $O(|V| + |E|)$. Thus, the overall complexity is $O(|V| + |E|)$.

You can prove the correctness of the above procedure using the induction technique as follows:
Hypothesis: After $t$ iterations of the outer "for loop", we get the correct min_value_reachable[] for every vertex from $v_{n}$ to $v_{n-t+1}$
Base Case: For $t = 1$, it is easy to see that min_value_reachable[$v_n$] = $f(v_n)$ since $v_{n}$ does not has any child, and $v_{n}$ is reachable to itself.
The induction case is also simple. Hope you can figure out the details yourself.


What does this mean: "The compile-time and load-time address-binding methods generate identical logical and physical addresses"? I read this in my Operating System textbook. Does it mean that the logical addresses generated by compile-time binding scheme are the same as the logical addresses generated by load-time binding? Or does it mean that the logical addresses and the physical addresses generated are the same in both compile-time binding as well as load-time binding?

If the first interpretation is correct, then how is it possible to generate same logical addresses in both compile-time and load-time? AFAIK in compile-time binding, we already have a fixed location in the memory where we'll load our program, so we can generate absolute addresses. But in load-time scheme, we do not know where the program will be loaded in memory. So we put relative addresses. How can absolute and relative addresses be the same?

What your TB says is absolutely correct & the answer is the latter i.e. the second interpretation.
More particularly:

The logical address & the physical address generated in the compile-time address binding scheme are the same.
The logical address & the physical address generated in the load-time address binding scheme are the same.

Why?
Context:

Definition of Logical address: A logical address or virtual address is an address that is generated by the CPU during program execution. - afteracademy

Definition of Physical address: physical address refers to a memory address or the location of a memory cell in the main memory - Techopedia

The compile-time binding is used when the base address of the process memory allocation is known before hand i.e. " a priori ". This never happens in real-life because you never know any mechanism/system to predict what the addresses will be at the time of writing the program itself.
However, in case that really happens (How? Static allocation / magic), the address generated by compiler (i.e. the logical address/virtual address) is indeed the actual physical address because the programmer hard-coded the addresses.
Similar (but not same) is the case with Load-time binding.


Environment requirement in training image dataset for classifier I have a question about preparing the dataset of positive samples for a cascaded classifier that will be used for object detection.

As positive samples, I have been given 3 sets of images:

a set of colored images in full size (about 1200x600) with a white background and with the object displayed at a different angles in each image
another set with the same images in grayscale and with a white background, scaled down to the detection window size (60x60)
another set with the same images in grayscale and with a black background, scaled down to the detection window size (60x60)

My question is that in Set 1, should the background really be white? Should it not instead be an environment that the object is likely to be found in in the testing dataset? Or should I have a fourth set where the images are in their natural environments? How does environment figure into the training samples?

I think you should have a fourth dataset where the images are in their natural environments because you will need information with white background when you will be testing the datasets.


Is the complexity of problems in NP exponential at most? I read on Wikipedia the following:

  Since NP-complete problems are in NP, their running time is at most exponential.

Is that correct? I thought a problem is in NP-complete if:

the problem is also in NP (i.e. accept verification in polynomial time)
Every problem in NP can be reduced to it in polynomial time.

These two conditions don't necessarily limit (to our knowledge) how hard a problem in NP Complete can be, right? (other than bounding the complexity of verification to polynomial time).

What am I missing?

Intuitively, the difficulty of all $\mathsf{NP}$-Complete problems is related: solving any single $\mathsf{NP}$-Complete problem in time $O(t(n))$ immediately yields an algorithm for any other $\mathsf{NP}$-Complete problem with a running time of $O(t(\mbox{poly}(n)))$. This shows, for example, that either all $\mathsf{NP}$-Complete problems admit polynomial-time algorithms or none of them does.

Your first statement "Since NP-complete problems are in NP, their running time is at most exponential" is NOT a definition of a $\mathsf{NP}$-Complete problem. It is just a property that NP-Complete problems have.

This is equivalent to saying that $\mathsf{NP} \subseteq \mathsf{EXPTIME}$. In fact it is conjectured that the containment is proper, i.e., $\mathsf{NP} \subset \mathsf{EXPTIME}$ . This would imply that there are (decision) problems that can be solved in exponential time but are not in $\mathsf{NP}$. We also know that $\mathsf{P} \subset \mathsf{EXPTIME}$, showing that we must have $\mathsf{NP} \subset \mathsf{EXPTIME}$ if $\mathsf{P}=\mathsf{NP}$.


Generating project network graph I had a problem of generating project network graph (like there and there) from list of activities and their dependencies.

Informal description:

Every activity is represented as edge of directed acyclic graph (DAG), so such layout of the graph is called activity-on-edge, as opposed to activity-on-node layout. If the dependency of two activities can not be represented as single vertex, the zero-weight edge (drawn as dotted line) is added to satisfy this dependency.

There is example of activities and dependencies table. In addition, the weights of activities are given.

Desired project network graph looks like this:

Formal description:

Given a list of directed edges names, their weights and list of their predecessor edges (so there is a path between head of predecessor edge and tail of listed edge), build a directed acyclic graph having exactly one vertex with no predecessor edges (source) and one vertex with no successor edges (sink).

Question:

So, the problem of generating project network graph and making some analysis of related project looks so easy if we represent activities not as the edges of DAG but nodes (e.g. activity-on-node layout). But is there an algorithm solving this generating problem? Could we use prepared activity-on-node graph to generate corresponding activity-on-edge graph?

You can build a graph from this by identifying a name for each vertex, and then identifying for each edge the names of the start vertex and end vertex for that edge.

I suggest you name a vertex by the set of edges that are entering that vertex.  For instance, the name for vertex $x_5$ in your picture would be "$a_4,a_5,a_6$" if we assume that $a_4,a_5,a_6$ are the names of the three edges that go to $x_5$ -- and similarly.  (If you like, you can use the SHA256 hash of the list of edges as the name of the vertex, instead of using the list itself as the name -- that will make the names shorter but won't change anything).

Given your table, we can easily identify the set of all vertex names.  Then, for each edge $e$, you can identify the name of its start vertex (by looking at the list of direct predecessor edges of $e$) and the name of its end vertex (by looking at any successor edge $e'$ of $e$, i.e., any edge $e'$ such that $e$ is a direct predecessor of $e'$, and then finding the name of the start vertex of $e'$).

This gives you a description of the graph as a set of edges, where each edge is represented by the name of its start vertex and the name of its end vertex.  From this, you can easily construct an adjacency list representation of the graph.  This then gives you the output you were seeking.


Heuristically determine a value f such that a probability d/f approaches 1/2 We have a set X of N elements. We want to get a new set X' having a size M < N.

Choose a first element x from X and put it in X'
for each element x in (X - X')
  Let x' the element from X' which is the closest to x (that is x' = argmin distance(x, x') for all x' in X')
  d = distance(x, x')
  if ( uniform_random([0,1]) < d / f )
     add x to X'

How can I choose the value f such that the size of the set X' at the end will be for instance the half of the size of X (that is, M approximates or equals N/2). I suppose that I should choose f such that the probability d / f equals 1/2 (or approximates 1/2 for most values of d), but how to do that ?

Additional details (that are not necesarily usefull for this question): the elements are actually vectors, and the distance between two vectors is the euclidean distance.

Note that d is not a constant (while f is a constant that I want to fix). d depends on the distance between each element x and its closest element x', so d is not always the same.

Suppose that the order in which we test the elements x is always random. For any set X, if we choose the value of f relatively small then we will get a relatively hight number of elements in the final set X', if we choose the value of f relatively big we will get a relatively small number of elements in the final set X'. If I experimentally vary the value of f many times I can always (for any set X) find a value of f for which the final number of elements in X' approaches N/2. So experimentally I can find a good value for f if I test many times which different values of f, but I want to determine it heuristically (not by testing many times and varying f).

EDIT:
By the way, the only one method which seems to give an acceptable results is: let mean_d the mean distance of each x to its nearest x'. We put f = 2mean_d, thus the probability d/f = d/(2mean_d) usually approximate 1/2 if the most of distances d are not far from mean_d. We also put f = (2mean_d)+d' where d' depends on how many distances are higher than mean_d, or f = (2mean_d)-d' where d' depends on how many distances are less than mean_d. Does this make sense ? Do you think it can be improved ?

OK, another answer :)

Size of the set X' clearly depends on the distribution of points, choice of starting points, and random chance.

If the points are always chosen from the same distribution, I'd try drawing |X'| as a function of f and |X|. To do that, I'd just do some monte-carlo simulations.

Also notice that f is a linear function of mean distance between points.


Theoretical foundations of robust and distributed services I have the notion of a social network which is robust against malicious attacks from the outside. My vision is a system that is structurally built up as a distributed network of equal servers that operate on the same data and offer the identical services. Users should all interact on the same network, independent of the respective server they communicate with. The idea is to prevent (at least theoretically) every opportunity to bring the whole system down and to achieve a total failure of the whole service. Obviously the design of such a system is not trivial because of proper synchronization mechanisms. On the other hand there is the challenge to convey the participants to the appropriate servers. Hope you got my idea roughly.

The thing is that I only have a vague notion how such a system can function, and furthermore have seemingly successful passed over the relevant lectures about distributed systems in my cs studies. I'm therefore a little bit in a lack of an overview of relevant literature, scientific papers describing theoretical models and also real world examples.

Can anyone help me out with references, links and helpful explanations?

You might be interested in these papers:

The LOCKSS system
Publius: A robust, tamper-evident, censorship-resistant web publishing system
The Eternity Service
The Free Haven Project: Distributed Anonymous Storage Service
Freenet: A Distributed Anonymous Information Storage and Retrieval System
Tarzan: A Peer-to-Peer Anonymizing Network
Anonymizing Censorship Resistant Systems
Tangler: A Censorship Resistant Publishing System Based on Document Entanglement
The Economics of Censorship Resistance


Permuting natural numbers We have two integers $z, k$

We form a sequence now of first z natural numbers. i.e. $1, 2, 3, 4, \ldots z$.

Now we have to find total number of permutations of this sequence such that the sum of any two adjacent numbers is $ \le k$

( $z \leq 10^6$, $\;\;z < k < 2*z$ )

Here is what I have been able to think untill now. If k=2*z-1, the answer is z!

Now if we reduce the value of k to 2*z-2, then we take the highest pair as a group and permute with rest of the elements, we subtract this value from the previous case of k=2*z-1

i.e. dp(z,k)= z! for k=2*z-1. and dp(z,k-1)=dp(z,k)-(z-1)!*2 for k=2*z-2.

I want to know if I am going in the right direction. Any help on the closed form would be good.

Let $D(z,k,l)$ be the number of permutations $p_1,\ldots,p_z$ of $1,\ldots,z$ in which the condition $p_i + p_{i+1} \leq k$ is violated exactly $l$ times. Then $D(z,k,l)$ is given by the following recurrence relation, which is valid whenever $z \geq 2$ and $z+1 \leq k \leq 2z-1$:
$$
D(z,k,l) = \begin{cases}
(z-l) D(z-1,z,z-2-l) + (l+1) D(z-1,z,z-3-l), & k = z+1, \\
(z-l) D(z-1,k-2,l) + (l+1) D(z-1,k-2,l+1), & k \neq z+1.
\end{cases}
$$
I leave the proof of correctness to you.

(Here is a hint for the first case: show that $D(z,z+1,l) = D(z,z,z-1-l)$ and that $D(z,z,l) = (z-l) D(z-1, z, l-2) + (l+1) D(z-1, z, l-1)$.)

The following Python program implements this recurrence:

def D(z, k, l):
    if z < 2 or k < z+1 or k >= 2*z:
        raise "Error"
    if z == 2:
        return 2 * int(l == 0)
    if k == z+1:
        return (z-l) * D(z-1, z, z-2-l) + (l+1) * D(z-1, z, z-3-l)
    return (z-l) * D(z-1, k-2, l) + (l+1) * D(z-1, k-2, l+1)

A more efficient implementation will use dynamic programming, I leave that also to you. One thing to notice is that case II preserves the quantity $2z-k$ while case I always has $k = z+1$, so the algorithm is quadratic rather than cubic.

For concreteness, here is a Python implementation of the dynamic programming method:

def DP(z, k):
    if not (z >= 2 and z+1 <= k <= 2*z-1):
        raise "Error"
    z_crit = 2*z-k+1
    L = [2, 0]
    for w in range(3, z_crit+1):
        L = [(w-l) * L[w-2-l] + (l+1) * L[w-3-l] for l in range(w-2)] + [2 * L[0], 0]
    for w in range(z_crit+1, z+1):
        L = [(w-l) * L[l] + (l+1) * L[l+1] for l in range(w-2)] + [2 * L[w-2], 0]
    return L[0]


Optimal 4-input sorting network In his paper The Bose-Nelson Sorting Problem (1973, Chapter 15 of A Survey of Combinatorial theory on page 163 available on Google books), Knuth says that the optimal bound of 5 comparators for a 4-input sorting network comes from an "elementary information-theoretic argument".

Information theory is not a part of my tool set, yet I have to prove this result.

I have managed to construct a 5-comparator network that solves the problem, and am trying to prove that any 4-comparator network does not work.

I have managed to prove that 3 comparators are needed if we want the top output to be the max of all inputs. In fact, for each input, at least three comparators are needed, but I cannot prove that they are different for each output.

Suppose that there were a network using only 4 comparators. The correct order of the inputs can be recovered by known the result of all 4 comparisons, since given these results, you can simulate the effect of the network. However, there are only $2^4 = 16$ possible results of the comparisons, whereas there are $4! = 24$ possible orders of inputs.


What is the eta-rule for nat? As far as I am aware of, the beta-rule of the natural numbers type nat states that (please correct me if I am wrong)

natrec 0 t0 (lambda i ti. ts) := t0
natrec (succ k) t0 (lambda i ti. ts) := (fun i ti. ts)

But what does the eta-rule says? I wonder how the following formulation is correct / accurate / complete

natrec n 0 (lambda i ti. s i) := n

I do not understand your notation, but the $\beta$-rule is not right (because you write down abstractions). It is:
\begin{align*}
\mathtt{natrec} \; 0 \; x \; f &= x \\
\mathtt{natrec} \; (\mathtt{succ}\;n) \; x \; f &= f \; n \; (\mathtt{natrec} \; n \; x \; f)
\end{align*}
where $x$ and $f$ are arbitrary (well-typed) terms. (Beware: not every term of a function type is of the form $\lambda x . e$!)

You can read $\beta$ rules as saying what happens when you apply a destructor to a constructor (for instance $\mathtt{fst} (a, b) = a$). An $\eta$-rule says what happens when you destruct a thing and then put it back together (for instance $u = (\mathtt{fst}\;u, \mathtt{snd}\;u)$.

We take numbers apart with $\mathtt{natrec}$ and put them together with $0$ and $\mathtt{succ}$, so the $\eta$-rule would be:
$$\mathtt{natrec} \; n \; 0 \; (\lambda \; x\; m \,.\, \mathtt{succ}\; m) = n.$$


Back propagation in neural networks I just finished watching these 3 Coursera videos on back propagation in neural networks. I get the idea of what we're trying to do, but I don't get how we achieve that by calculating error in each step as weight * cascaded error (eg. the formula at the top right of screen at 12:07 in the linked video). Let's say we start off with all the weights (theta) at zero. Wouldn't back propagation always calculate 0 error for everything, causing nothing to change?

Weights must be initialized to random, distinct, small values.

If all the weights are initialized to zero, our optimization function (eg. gradient descent) will not work. According to a later video, it's a problem of symmetry that will happen when you initialize weights to the same value. So if you used 0.4 instead of zero, the same problem would happen.

From course material:

  When training neural networks, it is important to randomly initialize the parameters for symmetry breaking. One effective strategy for random initialization is to randomly select values for weights uniformly in the range [-x, x]. One effective strategy for choosing x is to base it on the number of units in the network. A good choice of x is x = sqrt(6) / sqrt(in + out) where in and out are the number of units in the layers adjacent to [the weights]. This range of values ensures that the parameters are kept small and makes the learning more efficient.


Types and Programming Languages - proof for theorem about principles of induction of terms Types and Programming Languages book introduces a theorem about principles of induction on term (p. 31, theorem 3.3.4):

  Suppose P is a predicate on terms.

  Induction on depth:

  If, for each term s, given P (r) for all r such that depth(r) <
  depth(s)  we can show P(s), then P(s) holds for all s.

Proof of this theorem is left as the exercise for the reader. The solution to the exercise given in the book hints at defining a new predicate Q(n) on natural numbers such as:

  ∀s with depth(s) = n. P(s)

and apply the principle of complete induction on natural number (p. 19, axiom 2.4.2):

  If, for each natural number n, given P(i) for all i < n we can show P(n),
  then P(n) holds for all n.

Since I lack experience in writing mathematical proofs, I'm struggling with applying the hint from the book and proving that theorem.

Given that:

n = i + 1
for all natural numbers i less than i + 1, the predicate Q(i) holds (from the induction axiom)

How do I prove that Q(n) (or Q(i + 1)) is true? Should I use depth function definition introduced previously for the simple arithmetic language?

While you should get in the habit of providing definitions so your question is self-contained, especially when the original text is not easily accessible, the first thing to note is that the theorem doesn't actually depend at all on what "terms" are or how "depth" is defined.

Given any set $S$ and any function $f:S\to\mathbb N$, the theorem will hold. That is, $$(\forall s\in S.(\forall r\in S.f(r) < f(s) \to P(r))\to P(s))\to \forall s\in S.P(S)$$

How useful this theorem is depends on $f$. For example, if $f$ is a constant function then this theorem simplifies to $(\forall s\in S.P(s))\to(\forall s\in S.P(s))$ which isn't very useful.

To prove this via complete induction, you should, as is always a helpful strategy, write out the definitions, in this case, of complete induction. Complete induction states: $$(\forall n\in\mathbb N.(\forall m\in\mathbb N.m < n\to Q(m))\to Q(n))\to\forall n\in\mathbb N.Q(n)$$

So the bulk of the task is choosing an appropriate $Q$ to get the result that you want. As the hint states, the fairly obvious choice is $Q(n)\equiv\forall s\in S.f(s)=n\to P(s)$. If you stick this $Q$ into the formula for complete induction, you can simplify it into the first formula. All the work comes down basically to showing that $\forall n\in\mathbb N.\forall s\in S.f(s)=n\to P(s)\iff\forall s\in S.P(s)$ which is a simple and  purely logical exercise. Indeed, we don't even need the fact that $\mathbb N$ is the naturals to prove this lemma, though we do need that fact to apply complete induction for the theorem overall.


Does indirect diagonalization a relativize technique? My main question is can with R.kanon , Fortnow ,... technique that shows lower bounds for SAT seperate P and NP ?

Baker-Gill-Solovay showed that $P?=NP$ could not be solved with relativization. Does indirect diagonalization a relativized proof?

Suppose with indirect diagonalization  we show that $NP\not\subset A$ (A is an arbitrary class). how $A$ class can be big with indirect diagonalization technique?(I know it is possible that $TISP(n^{1.8},polylog n)=P$ and the bigger class for me is P or $TISP(n^{O(1)},polylog n)=P$ ). we know that $A$ is at least $TISP(n^{1.8},polylog(n))$(class of languages decides with $O(n^{1.8})$ time and $O(polylog(n))$ space simultaneous).

According to Baker-Gill-Solovay proof I think this approach can not seperate P and NP with indirect diagonalization according this pdf. that mentioned "we will show that such techniques alone cannot prove NP=P"

In special case I want to know that if someone shows $NP\not \subset TISP(n^{O(1)},poly(\log(n)))$ with indirect diagonalization ?

Buss and Williams codified the technique in their paper Limits on alternation-trading proofs for time-space lower bounds, and showed that the best bound that it can give is that SAT cannot be solved in time $n^{2\cos(\pi/7)}$ and space $n^{o(1)}$. This bound had been achieved earlier by Williams in his paper Alternation-Trading Proofs, Linear Programming,
and Lower Bounds.


Is $L=\{\langle M\rangle\mid L(M)\subseteq HP\}\in coRE$? My intuition is that $L\notin coRE$, but I haven't managed to prove that $HP \le L$, as previously I only saw reductions from $HP$ or from $\overline{HP}$ with $f$ such that $f((\langle M\rangle,x))=\langle M_x\rangle$, while $M_x$ performs some simulation of $M$ on $x$.

(The answer eluded me for some time, so I started writing a question here. After I found the surprisingly simple answer, I decided to post it (Q&A-style) anyway.)

We would show that $HP \le L$.

Let $f:\Sigma^*\rightarrow \Sigma^*$ be a function such that for any $x\in \Sigma^*$:
$$f(x)=\langle M_x\rangle$$
while $M_x$ is a TM that accepts $x$ and rejects every other word.

$f$ is computable, as it only requires writing the encoding of a very simple TM.

Now, for any $x\in \Sigma^*$:

$L(M_x)=\{x\}$
If $x\in HP$, then $\{x\}\subseteq HP$, and so $\langle M_x\rangle \in L$.
Otherwise, $x\notin HP$, and then $\{x\}\not\subseteq HP$, and so $\langle M_x\rangle \notin L$.

Therefore, indeed $HP \le L$.

Thus, it must be that $L\notin coRE$, because otherwise the reduction would imply that $HP\in coRE$, which is false.


Acceptance conditions when translating LTL to Büchi automaton? As an exercise in better understanding, I have been implementing the LTL to Generalized Büchi Automaton translation algorithm of Gerth, et al. (which is also discussed in Clarke, et al., Model Checking).

What I have ended up with seems incorrect, but also seems to accord with the discussion.  Both of the presentations state that we should create a separate multiple sets of accepting states as follows: for each "subformula of $\phi$ [the LTL property to be checked] of the type $\mu U \psi$, there will be a[n accepting] set $F \in \cal F$ which includes the nodes $q \in Q$ such that either $\mu U \psi \not \in Old(q)$, or $\psi \in Old(q)$."  By the standard translation of GBA to BA, the BA will be compelled to step through an accepting state for each of these component machines infinitely often.

Can someone clarify this definition? It seems wrong to me for a few reasons, which suggests I have failed to comprehend it:

As I understand it, the definition of "subformula" means that any formula contained, arbitrarily deeply, in $\phi$ would have its own acceptance condition.  But surely this must be wrong, because, for example, an until condition buried in a release condition might not ever need to be satisfied. Even more simply, Clarke's textbook gives as an example the property $$ (A U B) \rightarrow F C) $$ which gets translated to $$( (\neg A) R (\neg B) ) \vee ( \top U C )$$ ($\top$ is the boolean constant true; Clarke, et al. use R for "release" where Gerth, et al. use V).  In this case, the algorithm as described seems to demand that we satisfy $(\top U C)$, but this is only a disjunct.  Perhaps that is correct because parts of the graph where this disjunct has not been introduced, will be accepting for it?
The following seems to be a more difficult example of the same question: $$((p U q) R r)$$ In this case, if r holds universally, then $(p U q)$ need never hold, so I don't believe I should have a GBA acceptance condition for it.
The discussion of the algorithm directs the implementer to translate into a negation normal form, which is what gives the subformula $( (\neg A) R (\neg B) )$, above.  But this is not an "until" subformula, so does not give rise to any acceptance condition at all, which means that it's not possible to satisfy the above disjunction by satisfying this release condition.  Is this an oversight? Should one be generating acceptance conditions for these subformulas, as well?  Looking at the experimental results reported, I see that the expression $$\neg (p_1 U (p_2 U p_3))$$ is listed as not having any entries in the acceptance table.  In a sense, this agrees with my expectation, because this is equivalent to $$\neg p_1 R (\neg p_2 R \neg p_3)$$  But surely this is satisfiable by infinite traces where, for example, $\neg p_3$ is always satisfied?  So why are there no acceptance states?  There's a caption to this example, but unfortunately, it's syntactically garbled: "The rightmost column represents the number of pairs in the acceptance table of the constructed automaton.  Notice that for the safety property ...[described above]... there are no U subformulas satisfy [sic].  Yet, for the automaton to be nonempty, it has to contain a reachable cycle. [???]"  I suppose in this case, it might be that when we translate this formula we get zero sets of accepting states and so vacuously any cycle is treated as accepting?  But even so that would leave the earlier disjunctive case...

I will start with the last question and then come to the question at the top of your post.

The construction assumes that the LTL formula is given in negation normal form, so that no temporal operator occurs in negated form (as you wrote).
So $\neg (p_1 U (p_2 U p_3))$ gets translated to $\neg p_1 R (\neg p_2 R \neg p_3)$, and because in the latter formula, there is no Until subformula, we have 0 acceptance pairs in the Generalized Buchi automaton.
Now, a generalized Buchi automaton accepts all words for which there exists an infinite run on which all acceptance sets are visited infinitely often. If there are none, then this condition is vacuously true on any infinite run, which still has to exist. For example the word $(\{p_1,p_2\}^\omega)$ does not satisfy the LTL formula, and the corresponding generalized Buchi automaton has not infinite run for the word. If you model check with this automaton, every reachable cycle represents a case in which the LTL property holds. If you translate the generalized Buchi automaton to a Buchi automaton, then the standard construction makes every state in the latter accepting.
As far as the subformulas are concerned, you have to take the definition quite literally. For every Until-subformula in the NNF LTL property, you have an acceptance set. For instance, for $(a\,\mathcal{U}\,b)\,\mathcal{U}\,c$, you will have acceptance sets for $(a\,\mathcal{U}\,b)\,\mathcal{U}\,c$ and $(a\,\mathcal{U}\,b)$. For the All states in the generalized Buchi automaton containing $b$ or not containing $(a\,\mathcal{U}\,b)$ as a disjunct are accepting for  the latter acceptance set. All states containing $c$ as a disjunct or not containing $(a\,\mathcal{U}\,b)\,\mathcal{U}\,c$ as a disjunct are labeled as contained in the acceptance set for $(a\,\mathcal{U}\,b)\,\mathcal{U}\,c$.
The example $((\neg A)R(\neg B))\vee(\top U C)$ that you mentioned is actually not problematic. Depending on how you write down the algorithm, either (1) no state will ever be labeled by $((\neg A)R(\neg B))\vee(\top U C)$, but only by $((\neg A)R(\neg B))$ or $(\top U C)$ (and you will have two initial states), or (2) all states labeled by $((\neg A)R(\neg B))\vee(\top U C)$ need to also be labeled by either $((\neg A)R(\neg B))$ or $(\top U C)$, and for determining in which acceptance set a state is, you only look at the whole subformulas, so a state labeled by $((\neg A)R(\neg B))$ would be accepting for all acceptance sets, while one also labeled by $(\top U C)$ would not be labeled by the acceptance set for $(\top U C)$ (unless it is also labeled by $C$).


Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data So in biology (DNA sequences), sequence alignment is a generalization of longest common subsequence where an alignment of two sequences is scored typically with a linear function of how many spaces are inserted into each sequence and how many times each possible pair of aligned characters appears in the alignment. Just like longest common subsequence, finding the optimal alignment of two strings under an arbitrary linear scoring scheme can be solved in quadratic time using dynamic programming. (Needleman-Wunsch algorithm). The longest subsequence problem and variants that use linear scoring schemes and ask for the optimal multiple sequence alignment are NP-hard when the number of input strings is not fixed.

However, in biology, there is a probabilistic generative model that generates related DNA sequences. Starting with an unknown root ancestor DNA sequence, bifurcations occur that create two daughter sequences (species) that are independently derived from the ancestral sequence by potentially adding some characters in random locations, deleting some characters, and changing some characters. Then the bifurcations continue with additional changes at each level until the modern day DNA sequences of extant species are obtained. Then we want to align the modern day species' sequences (e.g. find the longest common subsequence in the simplest case) without knowing the exact ancestral sequences. In this case, fossil records can help identify the bifurcation events and estimate the sequence mutation rates after each bifurcation. So a reasonable estimate of the generative model that generated the related modern day DNA sequences can sometimes be obtained.

Now, my question is, for such an NP-hard optimization problem with a well-defined probabilistic generative model that generates input data, has anyone studied the hardness of finding either an optimal or nearly optimal solution, where either the worst-case or expected running time depends on the parameters for the model that generates the input data? For example, if DNA mutation and insertion/deletion rates are very low for a particular group of species, then it should be fairly easy to get at least a nearly optimal alignment of all the DNA sequences using partial alignments and pruning and heuristics, without resorting to a full-blown exponential time solution.

Here is a similar recent example due to Mossel et al. There are $n$ vertices which are partitioned randomly into two classes. Two vertices of the same type are connected with probability $p$, and two of opposite types with probability $q$. For what values of $p, q$ can we recover the partition with high probability (with respect to $n$)? It turns out that if $p$ and $q$ are too close then it is statistically impossible, and otherwise a simple algorithm succeeds with high probability.

The question you are asking is very specific, and the answer likely depends on the exact model and its parameters. It seems likely that for a low mutation rate, some iterative algorithm should work, perhaps even provably (with high probability).

One way to formulate this question more concretely is to come up with constraints on the relations between the sequences, constraints that hold with high probability. It could be that for an appropriate choice of constraints, the problem becomes feasible.


Finding the private key in BB84 quantum cryptography I'm trying to teach myself Quantum Cryptography for an exam I have soon, and I came across the following question:

  To establish a common key, Alice and Bob analyse a sequence of 20 photon pairs. Alice measures the photon sequence: $$1\:1\:0\:1\:0 \qquad 0\:0\:0\:1\:0 \qquad 1\:0\:1\:0\:1 \qquad 0\:1\:1\:0\:1$$ using the random series of detection bases: $$\otimes \oplus \oplus \otimes\otimes \qquad \otimes \oplus \oplus \otimes \otimes \qquad \oplus \otimes \oplus \oplus \oplus \qquad \oplus \oplus \otimes \otimes \oplus$$ while Bob is analysing the photons using the following sequence: $$⊗⊕⊗⊗⊗ \qquad ⊕⊗⊕⊕⊗ \qquad ⊗⊗⊕⊗⊕ \qquad ⊕⊗⊕⊗⊕$$ Hence find the sifted data set they get as an encryption key as in BB84.

Examining all the cases when the detection bases were the same and discarding the bits when they were not; we find that the encryption key is:

$$111\:000\:011\:101$$

Is this the right key?

Note: I apologise if this is in the wrong forum, I'm only really familiar with Math.SE, SO and EE.SE so feel free to migrate this if it's more appropriate elsewhere

The first stage of the BB84 protocol involves throwing away any measurements where the measurements were performed with a different basis.  After throwing those away, we are left with the following binary sequence:

$$11 10 0 0 01 10 01.$$

However, in the BB84 protocol as it was originally published, this is not the final key.  There are several subsequent steps that are performed after this.

In the second stage, Alice and Bob check whether they both got approximately the same sequence, by comparing a randomly chosen subset of this sequence.  If there are too many errors (differences between Alice's string and Bob's string) in those randomly selected positions, then they declare it a failure and go back to the beginning and start over.

In the third stage, a privacy amplification protocol is applied to the remaining bits, to derive a key that Alice and Bob can use.

Consequently, in the real BB84 protocol, the final key is not $111000011101$.  That's just the output of the first stage.  The final key is the output of the third stage.

However, I don't know what they taught you in your class.  I'd hope that they taught you all three stages, but if they only taught you the first stage, then you'd get a different answer than if they taught you the full protocol.  Therefore, we can't really tell what the right answer to your exam might have been.  If you want to know about that, I suggest you contact your instructor.


Theoretical justification of "halting problem avoidance" The wikipedia page for the Halting problem mentioned practical solutions to avoiding the halting problem such as avoiding infinite loops. And there is a mention that "by restricting the capabilities of general-purpose (Turing-complete) programming language, it is possible to guarantee the completion of all sub-routines (written under the restriction)".

What seems unclear to me is the underlying computation model of such restricted programming languages.

Say, if we remove -- from a general-purpose (Turing-complete) programming language -- the capability to conduct infinite loops (i.e. making the loop variable to always enumerate a finite list of elements, avoiding circular function recursions, etc), what would be the expressiveness of the resulting programming language or (the capabilities of) the corresponding computation model.

Possibly related questions

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

It is absolutely theoretically justified.

First realize that a loop is just a form of recursion: do the loop body, then either stop or do the loop body again with different variable values.

System F is a lambda calculus (programming language) with no recursion built in, and it is known to be strongly normalization. That is well typed every computation in this system halts. It's also powerful enough to compute basically every function you can think of, including the infamous Ackerman function.

In this system, you can use Church numerals to simulate the finite looping you mention in your question.

If you take a programming language without loops, you can model it in System F, which will give you a guarantee that all programs in this system halt.

It's implicit that if you remove loops, you also remove GOTO, which can be used to build loops.


How does each element in the output array of a DFT correspond to a specific frequency? I have a basic understanding of the Fourier Transform, though I'm trying to use it in a program and I'm confused on the specifics. Based on source code I can find online, the DFT takes a set of samples/numbers, performs a summation for each term, and returns a set of these summations which is the same size as the input set. Suppose I have a periodic function. As I understand it, the output array should contain the amplitudes/weights of each frequency which sum to that function. What I can't figure out is how each frequency is encoded in the array as just an index. In each example I read, we just assign a summation at each iteration of the inner loop to the next consecutive index in the output array. How are these indices indicative of which frequency they correspond to?
I'm attaching the source code I'm referencing to the bottom of this in case the website I linked to ever goes down.
import cmath
def compute_dft_complex(input):
    n = len(input)
    output = []
    for k in range(n):  # For each output element
        s = complex(0)
        for t in range(n):  # For each input element
            angle = 2j * cmath.pi * t * k / n
            s += input[t] * cmath.exp(-angle)
        output.append(s)
    return output

Let us denote the input signal by $x(0),\ldots,x(n-1)$ and the output signal by $y(0),\ldots,y(n-1)$. Your program is using the following formula:
$$
y(k) = \sum_{t=0}^{n-1} e^{-2\pi i tk/n} x(t).
$$
We also have
$$
x(t) = \frac{1}{n} \sum_{k=0}^{n-1} e^{2\pi i tk/n} y(k).
$$
In other words, any input signal can be represented as a linear combination of the functions $\chi_k(t) = e^{2\pi i tk/n}$, and the output signal gives the coefficients of this representation (up to a normalization factor).
The parameter $k$ is analogous to frequency. You can see the analogy more clearly if you write
$$
\chi_k(t) = \cos \frac{2\pi k}{n} t + i \sin \frac{2\pi k}{n} t.
$$


How to prove an identity of regular expressions I am in trouble how to prove that these two regular expressions are equivalent. I know what are closures and all the basics of automata. But the problem is I don't know the method or way of solving this kind of problem.
Question:

Prove that R.H.S regular expression is same as L.H.S
$$ (a+b)^* a (a+b)^* b (a+b)^* = (a+b)^* ab (a+b)^* $$

Regular expressions stand for languages. To show that two languages are equal, we show that every string in the first also belongs to the second, and vice versa.

As an example, let us prove the identity
$$
a(ba)^*b = ab(ab)^*.
$$
Denote the language of a regular expression $r$ by $L[r]$. A word $w$ belongs to $L[a(ba)^*b]$ if there exists $n \geq 0$ such that $w = a(ba)^nb$. Now $w = a(ba)^nb = (ab)^{n+1} = ab(ab)^n \in L[ab(ab)^*]$. Similarly, a word $w$ belongs to $L[ab(ab)^*]$ if there exists $n \geq 0$ such that $w = ab(ab)^n$. Now $w = ab(ab)^n = (ab)^{n+1} = a(ba)^nb \in L[a(ba)^*b]$.

(You can prove the various identities I used, such as $(ab)^{n+1} = a(ba)^nb$, by induction on $n$.)

Your particular identity states that if a word over $\{a,b\}$ contains an $a$ followed by $b$ (with possibly letters separating them) then it contains the substring $ab$, and vice versa. You should start by understanding why this holds.


Find the computational complexity of the given program int seq(int n)
{
   if(n == 0 || n == 1)
       return n;
   return(seq(floor(n/2)) + seq(ceil(n/2));
}

Find the computational complexity of the above program.

I have tried doing it in the following way:
$$\begin{align*}
T(0) &= 1 \\
T(1) &= 1 \\
T(2) &= 2T(1) = 2 \\
T(3) &= T(1) + T(2) = 3 \\
T(4) &= 2T(2) = 4 \\
T(5) &= T(3) + T(2) = 5 \\
&\vdots
\end{align*}$$

So the thing I have observed here was:

$$T(n) = n$$

However I am not sure if this result/approach is even somehow correct, is it? If not can someone show me the way how to approach problems like this one? Thanks

You can analyze using master theorem:
$$T(n) = T(\lfloor\frac{n}{2}\rfloor) + T(\lceil\frac{n}{2}\rceil) + 1$$

As we can suppose $n = 2^k$ and there is no a difference in the asymptotic complexity, We can say $T(n) = 2T(\frac{n}{2})+ 1$.

Hence, from master theorem we can say $T(n) = \Theta(n)$.


What's the advantage of typed assembly? I've seen scattered references to typed assembly in high assurance literature, but I don't really understand the advantage.

If the compiler/runtime are capable of passing the types down to the CPU, then aren't they are capable of emitting equivalent checks in assembly?  Bloating an instruction set with high-level primitives increases the complexity of the assembler and slows down execution time because the assembler is busy doing the compiler's job.

It sounds like this would make a compiler writer's job easier but expands the TCB without any real gains in speed or safety.

If the compiler/runtime are capable of passing the types down to the CPU, then aren't they are capable of emitting equivalent checks in assembly?

It could be done, but then

we move those checks from compile time to run time, impacting performance
we detect type errors at runtime instead of compile time, losing all the benefits of a type system

  Bloating an instruction set with high-level primitives increases the complexity of the assembler

True, but this instruction set may still be different from the CPU one, so it's just another (intermediate) language, not something the CPU needs to follow.

  and slows down execution time because the assembler is busy doing the compiler's job.

No, the assembler does not run at run time. At compile time, the assembler emits machine code. Compile time may get longer, but the runtime performance should not be affected.

  It sounds like this would make a compiler writer's job easier but expands the TCB without any real gains in speed or safety.

Expanding the TCB is not always detrimental to safety. Assume a nuclear power plant with some software to check that the temperature is kept in the safe range. Removing that software would make the TCB smaller, but the plant would hardly be more safe.

Adding a type system to a TCB puts more safety checks in the system. As long as the type system is not allowed to modify the program code, but only to report "well-typed / ill-typed", it can not harm safety. If it passes ill-behaved programs, say because of some bugs in the type checker, those would be executed anyway without the type system. If it fails some well-behaved programs, that's unfortunate, but preventing the deployment of a new program is always a safe choice -- this impacts productivity but not safety.


Provide a derivation from backwards on? Suppose you have to provide a derivation by natural deduction, e.g.

$((A \rightarrow B) \rightarrow A) \rightarrow A$

Is it a good advice to start from backwards on in general?
I mean doing the derivation from bottom to top. The required premises or hypothesis should arise by itself.

In general, proof crafting is a dark art. There is no simple universal strategy which in all cases leads to a proof, in the shortest way, with the least effort. One usually relies on instinct and experience (doing several exercises helps greatly).

Trying to reconstruct the derivation bottom-up is often a good strategy. However, note that in natural deduction (unlike some other systems) going bottom-up one needs to cope with infinitely many possibilities.

For instance, if I have to prove $A$, I could try to deduce it through modus ponens / implication elimination:

$$
\dfrac{\dfrac{\vdots}{B\rightarrow A} \qquad \dfrac{\vdots}{B}}{A}
$$

However, formula $B$ above could be anything! I have to chose among infinitely many formulas, which is not easy.

Worse, in some cases it is needed to exploit some rule like double negation elimination

$$
\dfrac{\lnot\lnot A}{A}
$$

It is not obvious when this is needed. For instance, I know that using this rule (or something equivalent like the law of excluded middle) is needed to prove $((A \to B)\to A)\to A$, but I can see this only because this is a very famous logical formula (called Peirce's Law).

At the end of the day, one can try a few heuristics, but should expect to have to backtrack a few times. In general the problem is very hard, but fortunately the exercises which one finds in books / exams usually are solvable with some intuition and little backtracking.


How to implement insertion sort on linked list with best case performance O(n)? I have an almost sorted linked list containing N distinct elements with only 1 element not in it's place. Every implementation I have seen start insertion from the beginning (unlike insertion sort on arrays) therefore the complexity will be $O(N^2)$.

Best case performance is attained when only one element is not in place. Assume the following list

1->2->3->4->0

You can easily show that it takes you $O(n)$ to sort via insertion sort: The inner while loop will run $n$ times when the outer loop reaches node 0. Otherwise, it will never be executed.


Is $\{ w_1cw_2 \mid w_1 ≠ w_2 \}$ a context-free language? Is the language $L_1 = \{w_1cw_2 ~|~ w_1,w_2 \in \{a,b\}^{\ast} \text{ and } w_1 \neq w_2\}$ a context-free language?

It certainly isn't regular, but is it context free?

I'm having trouble creating a grammar that creates terminal symbols from the outside-in; Is there anything to look for explicitly that tells me it is/isn't CF?

And if it was in fact context-free, how would I go about proving that?

The idea is that $w_1 \neq w_2$ if and only if either (1) $|w_1| \neq |w_2|$ or (2) the $i$th letters of $w_1,w_2$ are different. This leads to the following partition of $L_1$:
$$
\begin{align*}
L_1 &= (a+b)^+(a+b)^nc(a+b)^n \\ &\cup (a+b)^nc(a+b)^n(a+b)^+ \\ &\cup (a+b)^na(a+b)^*c(a+b)^nb(a+b)^* \\ &\cup (a+b)^nb(a+b)^*c(a+b)^na(a+b)^*
\end{align*}
$$
Each of the summands is clearly context-free, hence so is their union.


Why are these FIRST sets not combined into a single set? In Sebesta's Concepts of Programming Languages 10th edition on page 189 he explains the concept of $\text{FIRST}$ sets using the following example:

$A \rightarrow aB \ | \ bAb \ | \ Bb$
$B \rightarrow cB \ | \ d$
The $\text{FIRST}$ sets for the RHSs of the $A$-rules are $\{a\}$, $\{b\}$, and $\{c, d\}$, which are clearly disjoint.

Why aren't the first two sets combined into a single set $\{a, b\}$ instead? If $\{c, d\}$ is constructed by taking the two leftmost terminal symbols from $B$ then why don't we likewise take the two leftmost terminal symbols from $A$ into a single set?

There are three $A$-rules, each one with its right-hand side: $aB$, $bAb$, and $Bb$. Each produces a set as its value for $FIRST$. $FIRST(aB) = \{a\}$, and $FIRST(bAb) = \{b\}$.

In its turn, $FIRST(Bb) = FIRST(B)$ (because  $B$ does not derive the empty string), and $FIRST(B) = FIRST(cB) \cup FIRST(d) = \{c\} \cup \{d\} = \{c,d\}$.

Naturally, $FIRST(A) = \{a, b, c, d\}$.


Pumping lemma regular language can't be pumped Suppose we have a regular language that describes every string with the exact length of 3.That is obviously a regular language and it still can't be pumped because there is no cyclic behavior in that string/ the corresponding dfa

Can you please help me figure out my mistake?

Have a look at the exact wording of the pumping lemma: It has a precondition that only words exceeding a certain size need to be pumpable. This is exactly so that only words with repetitions have to be pumpable.

For your language (and every other finite one) you can simply set that size beyond the maximum word size (e.g. at 4). No words are longer than that, and all of them can be pumped.