Why are types and grammar non-terminals so distinct? Sorry ahead of time if some of my terminology is inaccurate, my formal training isn't quite to the level it should be.

Almost all programming languages with types separate built-in functions a + b and user defined functions f(x) into different steps of the compiler. a + b is dictated by some grammar that says something like expr ::= expr + term, and is dealt with by the parser. The precedence/associativity of operations is also defined by the parser, and all user defined functions are dumped into a common bucket. f(x) is defined by a declaration that requires x to be some type, and the result to be a particular type - which is then commonly checked post-parse in static analysis.

Thinking about it, it seems as though f (assuming for example, f goes from int to bool) could be defined in a grammar similar to

bool ::= "true" | "false" | bool-expr
bool-expr ::= "f" "(" int ")"
int ::= int-constant | int-expr ...

But doing some searches, it seems as though computer science research around types and grammars are formal, but always distinct.

Sure, there are practical concerns. Grammars tend to be static, preventing user defined functions from being... user defined. Grammars tend to be hard to make correctly/unambiguously, and letting random users meddle is troublesome. Having huge grammars would be more troublesome than doing the same sort of work split off to a more limited type-checker.

But there's all sorts of research which is done regardless of practical concerns. I find it hard to believe that the two research areas wouldn't benefit from ideas from each other. And by treating types like non-terminals (or vice versa), it seems as though you get quite a few benefits not commonly available (function overloading by return type, extensible language using types rather than a separate meta-language, better integration of user defined operators).

Given my lack of training though, I'm guessing there's simply something I'm missing that breaks the correspondence or that it was researched and promptly discarded due to something obvious to others. So what am I missing?

Clarification for svick's comment

function overloading by return type:

Since statements/expressions would need to be integrated with types, statement would need to map to void or unit or some analogy - and expressions would be typed as above. For example, f(x:int) -> void and f(x:int) -> int, only one is viable as a statement. This requires function signatures to be processed before implementations (akin to C), but that is rather implied for all of the approach.

extensible language without meta-language:

By making types act like grammar non-terminals, it would allow the parser behavior to vary based on function declarations (and the various symbols in scope). Consider the above example where statements are required to be void. f(x) would not even parse without some declaration that both matches that input and results in void. The function/variable/type declarations of the language effectively become the meta-language. But that's what programmers do already...

better integration of user defined operators:

Previous extensible languages had approaches to user defined operators, requiring the user to define precedence (usually some numeric value, relative to the built-in operators), and associativity. Having user defined and built-in operators/functions "speak the same language" as it were should provide a more uniform interaction between the two.

But mostly, the benefits I would expect are more theoretical. Things that can be proven/used about grammars could be applied to type checking and vice versa if types and non-terminals had some correspondence.

About operators and syntax extensions

Dave Clark comment is correct: "types is about semantics, grammar
non-terminals is about syntax." This said, you are perfectly right
that the semantic and syntactic issues could, possibly should, be both in the hands of
the programmer, or at least of the project designer. Indeed, that has
actually been the case for various languages, including older ones from
the early 1970s, when the concept of extensible languages was popular.

But first you should get your concepts rights. Though the addition may
be seen as a built-in function, that is not what characterizes it in
the context of your question. A built-in function is just a function
that happens to be predefined in the standard environment of the
language. For example sqrt (square-root) or abs (absolute value)
may be builtin functions in a language, but they are still defined
implicitly as function sqrt(r:real):real; .... and function
abs(z:real):real; ...., though abs is often overloaded to work also
with integer.

There could also be a built-in function plus, possibly overloaded, that would
perform additions. But who would use it. We prefer to write it with
the operator +.

There are built-in operators such as +, and one might want the programmer to be able to define new ones.

The use of operator has to do with the way we write things. It is a
syntactic issue. Using them does not help you to do more, but it
allows you to say it differently, if you think that makes things
easier to write or read and understand, or simply makes them closer to
standardized notations.

So you should see operators as nothing more than a special notation
for calling some function, which may or may not be extended to new
functions. Defining operators has nothing to do with typing.
Whatever semantic problems it causes can be caused as well with the
simple use of functions. But if it extends the syntax, it may create
syntactic problems such as grammatical ambiguity.

Operators are often overloaded, like + that can be used for both
integer and real, and possibly for boolean disjunction or set
union. But functions can be overloaded as well. It is only a
notational issue. And one constraint, for both functions and
operators, is that you cannot overload them using twice the same type
signature, but that is a semantic problem: finding which fuction is
actually associated with what is written, functionally or with an
operator.

Regarding extensions of a language, there are many ways to do it.  One
way is to allow overloading of existing operators with new function,
having new type signatures. Some languages limit it at that.

Another possibility is to introduce new user defined operators,
possibly written as a sequence of characters, such as >=, or **,
or and, and then associate functions with them.  This can be done
without touching the grammar, by defining for example the
associativity (left or right) and the precedence level of binary
operators, or the position of the argument for unary ones. Analysing
the actual structure of expression could be handled separately from
the context-free parsing of the syntax, thus not be really a parser
issue. but more associated with expressions evaluation.

A third possibility is to allow the introduction of new rules in the
grammars, but that requires appropriate techniques to properly
associate semantics to these rules, which can be very open, and thus
quite complex to handle.

Note also that we tend to see operators as unary prefix and binary
infix, but there are many other forms, such as postfix for factorial $n!$,
or the absolute value notation (endfix?): $|x|$, and more.

A last point is that, though the grammatical structure shoud remain
manageable, mostly for users to understand, the syntactic complexity
is not a major issue for modern syntax analysis techniques. I seems
that there is a tradition of trying to have very efficient parsers,
but it is not clear that the performance bottleneck is still there
(maybe for some programming environments). We can analyze quite
efficiently ambiguous languages.

Ambiguity may be a problem, when too frequent. But frequent ambiguity
can probably be detected statically, event though the problem is not
decidable in general (I do not know whether there has been work in
that direction). Then, ambiguity can be treated by the parser
as a syntax error, requiring the programmer to write things
differently.

Actually, it may well be that the syntax is not ambiguous, but the
typing is. While a big expression is parsed correctly, the overloading
of functions or operators can be such that there is ambiguity as to what
code (function body) should actually be understood.

A very simple example is:

function f(x:S):T1; ....
function f(x:S):T2; ....
function g(z:T1):T; ....
function g(z:T2):T; ....
declare u:S, v:T .....
  .....
  v := g(f(u))

It is not possible to decide which pair of functions f and g is
actually being called, because the typing of the expression is
ambiguous.

A language such as Ada (at least in its first release) allows such
ambiguity that is detected by the compiler. I would consider it a
semantic ambiguity, though some people consider type checking as part
of syntax. Whatever the case, is that any better or any worse than
syntactic ambiguities that would be detected by the parser.

I avoided giving concrete examples (there are many) because my memory
may fail me and I and not sure which language allows what. When I need
to know, I look.

About types

You question is mixing a lot of (I think) unrelated issues. So It is
taking me time to sort it out.

The existence of operators and their properties is not really related
to typing, as I explain above.

I think I finally understand what you are trying to say with the
example using bool as non-terminal.

However I fail to see how it relates to the use of operators, which
comes first in your question.  And I do not see what it is supposed to
bring you in terms of programming power.

This said, there is something like it that is possible, associating
types with non-terminal. It is actually a way to integrate type
checking in the syntax, though I do not know that it has ever been
used for programming languages. It is used for natural languages, and
is called feature structures. For example it can be used to test
number, gender or case agreement in natural language analysis, which
is quite close to type agreement.

The idea is to associate parameters with non-terminal, which then
become some kind of predicate. It can be seen as using an infinite
number of CF rules, all derived from a finite set by instantiating the
parameter to all possible values. But actually it is used by
instantiating the parameters as needed with unification.

This is possible because CF grammars may be seen as a special type of
Horn Clauses with binary predicates (the two arguments are the indices of the ends of the corresponding substring in the program text). Adding a type arguments to the
grammar non-terminals is just adding a third argument to the
corresponding Horn clauses.


Sort write-once array You have to sort a given array (assuming nothing more than the elements are totally ordered) which is write once read many (WORM) in constant space i.e using a constant number of variables.

So, my naive approach was to fix the position of one element at a time. But in what order? If I do it first to last then the information of the element of the index where I placed the first element is lost. So, if I start with the first element, then try to fix the element where the first element was placed, I will eventually run into problem because I'll have to remember the relative order of the current element and the elements sorted till now.

It seems doable but I can't really figure it out. For now, I don't care about running time.

Here is an approach which is not too efficient in terms of running time. Suppose your array has length $n$, say $A[1],\ldots,A[n]$. Given an element of your array, you can determine its rank (i.e., the value of $k$ such that it is the $k$th smallest element), so we can assume that the array contains a permutation of $1,\ldots,n$.

Consider now the cycle induce by the element $A[1]$, that is, write
$$
A[1] = x_1, A[x_1] = x_2, \ldots, A[x_\ell] = 1.
$$
If $x_1 = 1$ then $1$ is already at the correct place. Otherwise, you want to modify the array so that:
$$
A[1] = 1, A[x_1] = x_1, \ldots, A[x_\ell] = x_\ell.
$$
Hopefully you can see how to do it using constant space.

Go over all the elements $A[1],\ldots,A[n]$ in this way. Elements which you have already sorted (for example, $x_1$ in the example above) will already be at the correct place, so you will only modify each cycle once. In other words, you will only write to each position once.


Language of all words accepted by a TM by at most $t$ steps is regular Let $M$ be a Turing machine, $\Sigma$ an alphabet, $t \in \mathbb{N}$

$L = \{ w \in \Sigma^* : w$ is accepted by $M$ by at most $t$ steps$\}$

I want to show that $L$ is regular.

My attempt:

I'm trying to do this directly by constructing a DFA for $L$.

Let $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$

Define $\Gamma_0 = \Gamma \cup \{\sqcap\}$ where $\sqcap \notin \Gamma$.

Set $Q_0 = Q \times \Gamma_0^{t+1} \times \{i\}_{i=1}^{t+1}$ a finite set.

For $q \in Q$, $(a_1,..,a_{t+1}) \in \Gamma^{t+1}$, $1 \leq i \leq t+1,$ $b \in \Sigma$:

Say that $\delta(q, b) := (q_1, b_0, R $ or $L)$ and that $\delta(q, a_i) := (q_2, a_0, R$ or $L)$. We define $\delta_0: Q_0 \times \Sigma \to Q_0$ by

$\delta_0(q, (a_1,..,a_{t+1}), i) =
  \begin{cases}
    (q_2, (a_1,..,a_0,..,a_{t+1}), i+1)       & \quad \text{if } R \text{ and }a_i \in \Gamma\\
    (q_2, (a_1,..,a_0,..,a_{t+1}), i-1)       & \quad \text{if } L \text{ and }a_i \in \Gamma\\
(q_1, (a_1,..,b_0,..,a_{t+1}), i+1)       & \quad \text{if } R \text{ and }a_i = \sqcap \\
(q_2, (a_1,..,b_0,..,a_{t+1}), i-1)       & \quad \text{if } L \text{ and }a_i = \sqcap\\
  \end{cases}
$

Where the  change of letter in the $t+1$ tuple occured in the $i^{th}$ spot.

**Edit: also make the machine loop upon entering the accept or reject states

Then consider the DFA $A = (Q_0, \Sigma, \delta_0, g_0, F)$ where $g_0 = (q_0, (\sqcap,...,\sqcap), 1)$ and $F = \{(q_{accept}, x, j) : x \in \Gamma_0^{t+1}, 1 \leq j \leq t+1\}$

Now intuitively I think that this machine accepts $L$, but am having a hard time proving it.

So, is it true that $L(A) = L$? If so can you point some directions on how to prove it?

The language $L$ only depends on the first $t$ letters of the input (since the Turing machine never gets to any of the other letters). This implies that it is regular, since
$$
L = (L \cap \Sigma^{<t}) \cup (L \cap \Sigma^t) \Sigma^*,
$$
where $\Sigma^{<t} = \bigcup_{i=0}^{t-1} \Sigma^i$. The right-hand side is regular since $L \cap \Sigma^{<t}$ and $L \cap \Sigma^t$ are both finite, and so, regular.


Why is the dynamic programming algorithm of the knapsack problem not polynomial? The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack.

Why is this not a polynomial-time algorithm?

I have read that one needs $\lg W$ bits to represent $W$, so it is exponential time. But, I don't understand, one also needs $\lg n$ bits to represent $n$, doesn't one? So, for example, merge sort is not polynomial time, because its complexity is $O(n\lg n)$ and one needs $\lg n$ to represent $n$?

What am I missing here?

When we say polynomial or exponential, we mean polynomial or exponential in some variable.

$nW$ is polynomial in $n$ and $W$. However, we usually consider the running time of an algorithm as a function of the size of the input.

This is where the argument about $\log W$ comes in. Ignoring the values of the items for the moment (and considering only their weights), the input of the knapsack problem is $n$ numbers $\leq W$. Each number is represented with $\log W$ bits, and there are $n$ numbers, so the size of the instance is $n\log W$.

This makes $nW$ not polynomial in the size of the instance, since $W$ is exponential in $\log W$.

However, (coming back to your example about sorting) an instance for sorting consists of $n$ elements to be sorted, and representing these takes at least $n$ bits (and probably a bit more, since the elements themselves are probably bigger than $1$ bit each). We can represent the number $n$ using $\log n$ bits, but we can't represent $n$ things using $\log n$ bits.

The main difference is that $W$ represents a number in the input, while $n$ represents "the number of things".

Note that if we were to "cheat", we could represent $W$ using $W$ bits if we used a unary encoding. This version of the problem is technically polynomial, but really only because we were deliberately being less efficient.

It turns out that there is a whole class of Strongly NP-Hard Problems, which are still NP-hard even when the input is represented in unary format. But Knapsack
is not one of these problems.


Size comparison of NFA and minimal DFA Except for isomorphisms, the minimal DFA of a regular language is unique. However, is it possible that an equivalent NFA has less states than the minimal DFA? If so, what is the reasoning behind this? Due to the conversion of an NFA to DFA (which produces $2^Q$ states) it seems to me that a NFA can indeed have less states than a minimal DFA, but I'm not quite sure of this. Thanks in advance.

For every $n$ there is a language over $\{a,b\}$ which is accepted by an NFA having $n$ states, but its minimal DFA has $2^n$ states.

Unfortunately I don't remember the reference, but here is how to get almost this result. Let $L_n$ be the language of all words over $\{a_1,\ldots,a_n\}$ that don't contain all letters. Then $L_n$ can be accepted by an NFA with multiple initial states having $n$ states (or with a normal NFA with $n+1$ states), but its minimal DFA has $2^n$ states. Take it as an exercise to prove these statements (for the latter one, use Myhill-Nerode theory).


'Half-Close' figure of Data Communications and Networking, 5/e In the Figure 24.13 of Data Communications and Networking, 5/e the first ACK message from the server holds y-1 in it's Sequence no. field. Note that the first FIN message from the client message had y in it's Acknowledgement no. field. So shouldn't the first ACK message from the server be holding y in it's Sequence no. field instead of holding y-1? Is the diagram faulty or is there a reason behind it?

The FIN segment consumes 1 sequence number as it does not carry data. ACK does not consume a sequence number. The FIN segment is sent by the client process. The server process receives a FIN segment but does not send a FIN segment as the connection is not closed, since it is a half-close process. Server process send only an ACK segment to acknowledge receipt of FIN segment from the client. Hence, the sequence number decreases by 1 and becomes $y-1$.
Contrast this with the Three way handshaking, where the sequence number is $y$ because in that process, the server sends a ACK segment as it acknowledges receipt of FIN segment from the client and sends a FIN segment as it terminates the connection.


Recursion in pi-calculus In the book by Sangiorgi and Walker ("The $\pi$-calculus: A theory of Mobile Processes"), Subsection 3.2 is devoted to recursion. They state the following constraint (pages 132-133):

"The environment is finitary, in the sense that any process depends on only finitely many constant definitions. (Formally, the transitive closure of the relation that relates two different constants $K$ and $K'$ if an instance of $K$ occurs in the definition of $K'$, is well-founded.)"

I do not understand how the two sentences are related. Right after there is an example with the definitions of $B_0$, $B_1$ and $B_2$: instances of $B_1$ and $B_0$ occur in the definition of $B_0$; instances of $B_2$ and $B_0$ occur in the definition of $B_1$; and an instance of $B_1$ occurs in the definition of $B_2$. Thus the environment is "finitary" in the sense that each one of the constants $B_0$, $B_1$ and $B_2$ only depends on three constant definitions. But how is "the transitive closure of the relation that relates two different constants $K$ and $K'$ if an instance of $K$ occurs in the definition of $K'$" well-founded? This transitive closure should relate any of the three constants $B_0$, $B_1$ and $B_2$ to any of these same constants and thus, if I consider the set $\{ B_0, B_1, B_2 \}$, I cannot find a minimal element.

I am as puzzled as you are. Indeed, that looks wrong, as far as I can see. The mentioned relation can indeed have infinite descending chains, otherwise we could not have "cycles" which are needed for (mutual) recursion.

What should be ruled out is the presence of infinite descending chains involving infinitely many constants $K$. This is however a different requirement from well-foundation.


Determine if a vertex is a part of a cycle in O(m+n) complexity I am trying to apply BFS to the following problem, but I'm not sure how to do it

Input: directed graph $G$ defined by the array of adjacency lists with n vertices and m edges, and a vertex $v$ in $G$
Output: $true$, if $v$ is a part of a cycle, $false$ otherwise

Can someone explain in pseudocode or in words how to do this?

Simply apply Strongly connected components algorithm , Kosaraju's algorithm has complexity $O(m+n)$. Now, read through the SCC components and check if $v$ is part of a component with size $\geq$ 2. The second step is $O(n)$. Actually, the second step can be interleaved with the first step to get your required complexity result.

A simpler algorithm may be just to to use DFS on the graph. Have a look at Cormen's Introduction to algorithms, chapter 22. Your exact problem is solved there using DFS.


How to prove $L \cdot L^{*} = L^{+}$ How can one formally prove

$L \cdot L^{*} = L^{+}$

It looks obvious to me since with the concatenation you get rid of $\varepsilon$, but I cannot think of a formal proof through induction or something.

To summarize the comments.

A. Sometimes $L^+$ is defined to be $L\circ L^*$, where '$\circ$' is the  concatenations operator.

B. Assume the following definitions,

  $L^* \equiv \{\varepsilon\} \cup L \cup L^2 \cup \cdots$

  $L^+\equiv L \cup L^2 \cup \cdots$

Then, by the properties of the concatenation operator, $L\circ L^i = L^{i+1}$. Explicitly for the case of $i=0$, it also holds that $L\circ\{\epsilon\} = L$.

Then,
$$\begin{align}
L\circ L^* &= L \circ \left(  \{\varepsilon\} \cup L \cup L^2 \cup \cdots \right )
\\ &= (L\circ \{\varepsilon\}) \cup (L\circ L) \cup (L \circ L^2) \cup \cdots \\ &= L \cup L^2 \cup \cdots \\ &\equiv L^+
\end{align}$$

The only missing part is to explain the second transition--The distributivity of the concatenation operator over unions.


Sort algorithm input probabilities Suppose that there is an algorithm which sorts a sequence of $n$ elements

$$a_1, a_2, ..., a_n$$

Each of the $a_i$ is chosen with probability $1/k$ from a set of $k$ distinct integer numbers.

Is it true, given that $k \to \infty$, that:

The probability that any two of incoming sequence elements are equal, tends to $0$?
The probability that the incoming sequence is already sorted, tends to $\frac{1}{n!}$?

Why / why not?

Here is why you would expect these properties to hold. Suppose that $a_1,\ldots,a_n$ are chosen independently from the uniform distribution on $[0,1]$. The event $a_i = a_j$ has probability zero, and so with probability $1$ all numbers are distinct. Moreover, given that, all sequence orderings are equally likely, and since there are $n!$ of them, the probability that the sequence is ordered is exactly $1/n!$.

To prove that these claims hold in the limit even when the $a_i$ are sampled from a finite set requires some calculation, which I leave to you.


Can the structure of a "Complete Binary Tree", be uniquely identified if only its pre-order or post-order or in-order traversals are given? I am unable to reason if we can construct a complete binary tree if only one of the following 3 traversals is given: pre-order, post-order, in-order.

The following is the definition of a complete binary tree:

  A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

The above definition has been taken from this link:
https://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

It would be helpful if someone can prove or intuitively explain why we can or cannot uniquely construct a complete binary tree if only one of its 3 traversals is given?

Given $n$, there is only one shape for a complete binary tree (CBT) with $n$ nodes.

For any deterministic traversal, the correspondence between a node's position in a CBT and its position during the traversal of that CBT is completely fixed. So if a deterministic traversal is given, we can reconstruct the CBT uniquely. This applies not only to any one of pre-order, post-order, or in-order traversals, it also applies to breath-first-traversal (with the left child visited before the right child), or any other deterministic traversal as mentioned by Hendrik Jan in his comment.

Here is an example. The shape above is the only shape for a CBT with 12 nodes, which are, 1 root (at depth 0), 2 nodes at depth 1, 4 nodes at depth 2 and 5 nodes at depth 3. A pre-order traversal of that CBT visits the nodes in the following order.

the root node.
the first node of depth 1.
the first node of depth 2.
the first node of depth 3.
the second node of depth 3.
the second node of depth 2.
the third node of depth 3.
the fourth node of depth 3.
the second node of depth 1.
the third node of depth 2.
the fifth node of depth 3.
the fourth node of depth 2.

Give the list above, we know the root node is the 1st-node visited, the first node of depth 1 is the 2nd-node visited, ..., the fourth node of depth 3 is the 8th-node visited and the fifth node of depth 3 is the 11th-node visited.


How can another process call $signal()$ when one process is executing $wait()$ in its busy waiting loop? A semaphore is a variable that, apart from initialization is accessed through only two standard atomic operations wait(s) and signal(s).

wait(S){
    while S <= 0
    ; //no-op
    s--;
}

signal(S){
    s++;
}

The function $wait()$ is an atomic operation which means that either it is executed in its entirety or it is not executed. Let us suppose that we call $wait(a)$ upon a semaphore variable $a$. And let us assume the initial value is $0$. This means the criterion for the while loop is satisfied and it goes into a while loop. It can only come out of the while loop if the value of the semaphore $a$ is $\gt$ 0. This can occur, if some process sets the value of $a$ to $1$ by calling $signal(a)$. But since $wait()$ and $signal()$ are atomic operations and since we have already entered into the busy waiting while loop in $wait()$ when the value of $a$ was $0$, isn't this loop supposed to run indefinitely since its atomic? How can another process call $signal()$ when one process is executing $wait()$ in its busy waiting loop?

Your assertion that wait() and signal() are atomic is incorrect. The increment/decrement to s within the functions (s++, s--), are what's atomic.

That being said, what you have given here is only one possible implementation of a semaphore. An OS may or may not implement semaphores in this way, and they probably will choose a more efficient implementation. What's more important is to grasp the semantics of a semaphore, which you seem to understand correctly.


How do I tell if $G$ is a forest in log-space? How does to prove that language
$$\textbf{X} = \{G \mid\text{ all connected connected components in $G$ are trees}\} \in \textbf{L}\,?$$ I know how to prove that language of undirected trees is in $\textbf{L}$ but I don't know what to do next.

Using Reingold's algorithm, you can count the number of connected components in a graph. For example, you can count the number of vertices which have the minimal index in their connected component (assuming some arbitrary ordering of the vertices), that is, the number of vertices $i$ that are not connected to any $j < i$.

Now use the following criterion: A graph contains a cycle iff there is an edge whose removal does not increase the number of connected components.


How can I calculate the maximum sum/product of sequence? I am looking for an algorithm in $O(N^2)$ that finds the maximum value that be obtained from a sequence of real numbers greater than 0 (e.g. $\{ 1, 2, 3 , 4\}$) by inserting a plus ($+$) or multiplication ($\times$) between the elements.

Really not having much luck and wondering if anyone has any insight on this?

It must follow normal order of precedence.

For example with $\{1,2,3,4\}$, the maximum is $1+2\times3\times4 = 25$
not $1\times2\times3\times4 = 24$ and not $1\times2+3+4 = 9$.

Let's say all numbers are positive (i.e. $\geq0$). Before and after $0$s you should always use $+$. This could also solved in $O(n^2)$ by first finding all zeros and then find maximum value for each group separated by zeros. Inside each group, for positive numbers, you should always use $\times$ except in $1$ cases, if ones are in the middle of a group, still you should choose $\times$. But when ones are at the very beginning or at the very end of the group, you should choose $+$.


Closure of regular languages under non-contiguous subsequence Suppose there is a language $L$ on alphabet $Σ$.
Now consider the language

$$ S(L) = \{x : wxy ∈ L, w, y ∈ Σ^*\} ∪ \{x : w ∈ L,\text{ and $x$ is a subsequence of $w$}\}. $$

How to prove that if $L$ is regular then $S(L)$ is also regular?

For first part I think if there is a DFA that accepts $wxy$ then there is a DFA that accepts $x$. For second part I have no clue. Can anyone shed some light on this or can provide a formal proof for this?

Here are several ways of showing this:

Starting with a DFA/NFA for $L$, add $\epsilon$ transitions parallel to all other transitions.
Apply the regular substitution that maps $\sigma \in \Sigma$ to $\{\sigma,\epsilon\}$.
Starting with a regular expression for $L$, replace all copies of each $\sigma \in \Sigma^*$ by $\epsilon + \sigma$.


What does an NFA do if there's no transition with the correct symbol? So I am learning about DFA and NFA, and I need some clarification for it.

DFA

accept empty set
transition for every element in the alphabet
path are deterministic

NFA

accept the empty set and empty string
path are not deterministic

My question is does NFA need a transition for every element in the alphabet? If not, then let say the alphabet is {0. 1} and I am at a state without the transition for 1, do I go to the empty state or something?

In a DFA, if you are in state $p$ and see an input character $c$, one of three things may happen:

You can consume that character (i.e., read it) and change to state $q$ ($q$ may be $p$ or not).
There may not be a move defined for the pair $(p, c)$ in which case the DFA halts and rejects the input string.
If the DFA is in a final state after having read all the input, it accepts the input, otherwise it rejects the input.

For an NFA, you have more possibilities:

In state $p$ with input $c$ you can consume the input and change to several states $q_1, q_2, \dotsc$ .
In state $p$ you can elect not to consume the input and change to several states $q_1, q_2, \dotsc$. This is called an epsilon move. In essence, your machine may change state without reading any input.
As with a DFA, there may not be any move defined for the pair $(p, c)$ or $(p, \epsilon)$ in which case the NFA halts that branch of execution.
If the NFA is in a final state in any particular branch of its execution and has consumed all the input, it accepts the input. If it hasn't reached any accept state after having read all the input, it rejects.

In either a DFA or an NFA, you don't need to have moves defined for all possible (state, character) pairs. If you're in state $p$ and there is no move defined for an input character, the machine (or that branch) halts and rejects.

Some people don't like this behavior and complete the automaton by creating what you apparently call an empty state and defining transitions to that state on those missing inputs. Once you're in that state (also known as a dead or error state), you never leave, no matter what the input is.


How to calculate or estimate how long it takes to solve a recurrence relation? I am trying to understand how to solve complex recurrence relations and whether there is a general method or technique to help me. That being said I am not talking about recurrence relations that can be solved using the (generalized) Master Theorem or the Akra–Bazzi method.

This is by no means a "I have some homework to solve, please solve it for me" question. It is more at a conceptual level. I want to be able to solve and "see" through these relations with ease.

How do you efficiently calculate the time needed to solve a recurrence relation?

Is it something that, simply put, takes experience and personal intuition? Is there some cannon method that I am not aware of? Moreover, how do you go on to calculate the same relations for cases where you have memoization?

There are at least three questions here:

How does one solve a recurrence relation on paper?
How does one efficiently calculate a sequence given by a recurrence relation, say using memoization?
Given a recurrence relation, can one predict the running time of the best method for computing it?

Let me answer them one by one. For the first question, this is a particular instance of the classical question, how to solve problems. Consider the (finite!) recurrence relation given by
$$
\gamma_0 = 1, \quad \gamma_{m+1} = E, \quad \ell\gamma_{\ell+1} = (2\ell-m+c-1)\gamma_\ell + (m-\ell+1)\gamma_{\ell-1} (1 \leq \ell \leq m).
$$
(The sequence is $\gamma_0,\ldots,\gamma_{m+1}$, and $E,c$ are parameters.)
What is the solution of this recurrence? If you're interested, have a look at the top of page 7 in this paper, which unfortunately doesn't explain how the authors found the explicit formula; Mathematica manages to solve this recurrence somehow. For some general methods useful for solving recurrence relations, consult our reference question.

For the second question, we can consider a very general class of recurrence relations which produce a sequence $(\gamma_i)_{i \in \mathbb{N}}$ by giving each $\gamma_i$ in terms of values $\gamma_j$ for $j < i$. Such recurrences can be efficiently computed using memoization. The time required to compute $\gamma_n$ is upper-bounded by $n$ multiplied the time it takes to calculate the defining formula of $\gamma_i$. This bound can be tricky to evaluate, since the time needed to carry arithmetic operations depends on the size of the operands, which could grow rather fast depending on the recurrence (consider for example $\gamma_0 = 1$, $\gamma_n = n\gamma_{n-1}$).

For the third question, it is easy to artificially reduce the halting problem to my statement of the problem, so in general it is hard to predict the best running time. But one can probably predict (or at least upper-bound) the running time of memoization. Given my answer to the previous question, all you need is to somehow bound the size of the elements of the sequence. In many cases one can get reasonable bounds, for example this is probably possible for recurrence relations in which $\gamma_n$ depends polynomially on $n$ and $\gamma_{n-1},\ldots,\gamma_{n-c}$ for some finite $c$. While you shouldn't expect to get tight bounds this way, for a "generic" recurrence relations, one can probably predict the order of growth.


Loop Transforms to Increase Parallelism I have the need to parallelize as much as I can (in order to make it run fast) the following part of an algorithm:

do i=1, n
  do j=1, n
    A[i, j] = A[i-4, j-4] + A[i-3, j-3] + B[i, j]
  end do
end do

I was thinking that the best i could do here is a loop skewing (but with what factor?) and loop interchange that would allow me to finally have a DOALL on the inner loop. Any feedack and help regarding those thoughts?

This is an incomplete question because you have no base case; A[-3, -3] is not defined, for example. But let's assume we're looking at a window into a larger array, so those values have some consistent, distinct and independent value.

Denote those predetermined values with #, and look at the top-left corner. The values we can fill in are those three topmost rows and three leftmost columns, denoted by ·.

# # # # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # · · · · · · · · · ·
# # # # · · · · · · · · · ·
# # # # · · · · · · · · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·
# # # # · · ·

Doing those in parallel means that you need to take n / 3 sequential steps. Since the matrix is square, exclusively going down balances the costs better, but still gives you n / 3 sequential steps with parallelism of 3n.

This is remarkably excessive for a typical CPU for significantly sized n; rather you should be streaming memory into SIMD operations as fast as possible. You can do a straightforward N-wide SIMD loop over the x-axis.

A[i:i+N, j] = A[i-4:i-4+N, j-4] + A[i-3:i-3+N, j-3] + B[i:i+N, j]

This probably won't max out your bandwidth entirely, but it will get pretty darn close and it's unlikely you can get more from a multicore algorithm, though you are free to try partitioning the work along diagonals.


Quick calculation for $(x^y) \bmod z$ What are the possible ways to calculate $(x^y) \bmod z$ quickly for very large integers?
Integers $x,y \lt 10^{10000}$ and $z \lt 10^6$.

Computation with large integers is one of the topics of Knuth's "Seminumerical Algorithms" (volume 2 of "The Art of Computer Programming"). Results in elementary number theory, like the properties of modular arithmetic, the Chinese Remainder Theorem, Fermat's little theorem/Euler's theorem are critical here.

As commented, this operation is central in cryptography, like RSA. Doing this operation efficiently for fixed $y$ and $z$ are critical.

There are several efficient libraries for doing multiprecision computation, perhaps the most known is GMP, which in turn is used in several languages that offer "big integers." Most computer algebra systems offer computation with large integers.


Average case analysis by key comparisons of Max Sort I'm having trouble approaching this average case analysis in terms of key comparisons.
The pseudo-code is as follows:
maxSort(Array) {
    for (int i = Array.length - 1; i > 0; i--) {
        x = i - 1
        max_i = findMaxPos(x) # performs x key comparisons
        swapValues(max_i, i)
    }
}

findMaxPos returns position of largest value between index 0 and x of the array. Performs x key comparisons.
I believe the worst case is W(N) = n(n-1)/2 where n is the size of the array.
I am unsure how to contextualize the algorithm in an average case in terms of key comparisons. Should I create a decision tree and show the lower bound for average behavior? Or is there a way to use permutations? Any help is greatly appreciated
Edit: For context, the original question is asking for the number of key comparisons in the worst and average case. While working out the worst case was relatively straight forward I'm unsure how to write some sort of proof or perform analysis to show the average is the same

The number of comparisons on an array of length $n$ is $\binom{n}{2}$, regardless of the contents of the array. Therefore all of the following are $\binom{n}{2}$: the worst-case number of comparisons, the best-case number of comparisons, and the average-case number of comparisons, with respect to any input distribution.


Some questions regarding methods for solving pushdown automata problems I have found some problems whose solving "patterns" appear quite recently, and I am not sure if the way I'm solving them is the most correct/efficient one:
For example, take this language:
$\{w | w\in\{a,b,c\}^* \text{ with }|w|_a=|w|_b \text{ or } |w|_b=|w|_c\}$
The solution would be as follows, where $\\\$$ is the bottom of the stack, and $\epsilon$ the empty string:
The top part is $|w|_a=|w|_b$ and the bottom is $|w|_b=|w|_c$
Taking the top part as an example (the other one is almost identical), what I do is to push $A$ whenever $a$ is read and $A$ is in the top of the stack, or remove $B$ if $B$ is in the top.
Whenever $b$ is read, I push $B$ if I don't find any $A$'s, or remove an $A$ if it's found.
Then, the rest of the characters without restrictions are read between those, leaving the stack alone.
The string would be accepted if input stops and the stack is empty.
I am not sure if this is the most graceful solution since I basically cram all possible cases in one state, though I think this works. This pattern is used basically whenever I find a restriction such as $|w|_x=|w|_y$

The other pattern I found that I'm unsure about is the following one, taking this language as an example:
$\{a^nb^m | n=3m\}$
In this one, I push one symbol into the pile only whenever 3 consecutive $a$'s are read, which will be then equal to $m$ and be consumed by reading $b$'s, accepting the string again if input is done and the stack is empty.
In these cases, I create a series of states where there is only one symbol pushed (when we enter into them), and the rest force to read a certain number of symbols without pushing of popping anything.
I am uncertain if this is the good way to do it. What if it were to be $n=56m$, would I need 55 sub-states?

Your first solution is fine. I would not call this cramming into one state, it is kind of elegant to handle all this at the same place.
For your second problem, yes you can add 55 extra states. But also here you can use a single state instead, by coding that state into the topmost stack symbol. Simply have many stack symbols $A_0$, $A_1$ to $A_{55}$ (or so) and replace $A_i$ by $A_{i+1}$ until 56 is reached.
In general every pushdown automaton can be replaced by one having at most two states.


Data structure for map on intervals Let $n$ be an integer, and let $\mathbb{Z}$ denote the set of all integers.  Let $[a,b]$ denote the interval of integers $\{a,a+1,a+2,\dots,b\}$.

I am looking for a data structure to represent a map $f:[1,n] \to \mathbb{Z}$.  I want the data structure to support the following operations:

$\text{get}(i)$ should return $f(i)$.
$\text{set}([a,b],y)$ should update $f$ so that $f(a)=f(a+1)=\cdots=f(b)=y$, i.e., update $f$ to a new map $f'$ such that $f'(i) = y$ for $i \in [a,b]$ and $f'(i) = f(i)$ for $i \notin [a,b]$.
$\text{stab}(i)$ should return the largest interval $[a,b]$ such that $i \in [a,b]$ and $f$ is constant on $[a,b]$ (i.e., $f(a)=f(a+1)=\cdots=f(b)$).
$\text{add}([a,b],\delta)$ should update $f$ to a new map $f'$ such that $f'(i) = f(i) + \delta$ for $i \in [a,b]$ and $f'(i) = f(i)$ for $i \notin [a,b]$.

I want each of these operations to be efficient.  I would count $O(1)$ or $O(\lg n)$ time as efficient, but $O(n)$ time is too slow.  It's OK if the running times are amortized running times.  Is there a data structure that simultaneously makes all of these operations efficient?

(I've noticed a similar pattern come up in a several programming challenges.  This is a generalization that would suffice for all of those challenge problems.)

I believe logarithmic time for all queries is achievable.  The main idea is to use an interval tree, where each node in the tree corresponds to an interval of indices.  I'll build up the key ideas by starting with a simpler version of the data structure (that can support get and set but not the other operations), then add features to support the other features as well.

A simple scheme (supports get and set, but not add or stab)

Say that an interval $[a,b]$ is flat if the function $f$ is constant on $[a,b]$, i.e., if $f(a)=f(a+1)=\cdots =f(b)$.

Our simple data structure will be an interval tree.  In other words, we have a binary tree, where each node corresponds to an interval (of indices).  We'll store the corresponding interval $I(v)$ in each node $v$ of the tree.  Each leaf will correspond to a flat interval, and they'll be arranged so that reading out the leaves left-to-right gives us a sequence of consecutive flat intervals which are disjoint and whose union is all of $[1,n]$.  The interval for an internal node will be the union of the intervals of its two children.  Also, in each leaf node $\ell$ we will store the value $V(\ell)$ of the function $f$ on the interval $I(\ell)$ corresponding to this node (note that this interval is flat, so $f$ is constant on the interval, so we just store a single value of $f$ in each leaf node).

Equivalently, you can imagine that we partition $[1,n]$ into flat intervals, and then the data structure is a binary search tree where the keys are the left endpoints of those intervals.  The leaves contain the value of $f$ at some range of indices where $f$ is constant.

Use standard methods to ensure that the binary tree remains balanced, i.e., its depth is $O(\lg m)$ (where $m$ counts the current number of leaves in the tree).  Of course, $m\le n$, so the depth is always at most $O(\lg n)$.  This will be helpful below.

We can now support the get and set operations as follows:

$\text{get}(i)$ is easy: we traverse the tree to find the leaf whose interval contains $i$.  This is basically just traversing a binary search tree.  Since the depth is $O(\lg n)$, the running time is $O(\lg n)$.
$\text{set}([a,b],y)$ is trickier.  It works like this:

First, we find the leaf interval $[a_0,b_0]$ containing $a$; if $a_0 < a$, then we split this leaf interval into the two intervals $[a_0,a-1]$ and $[a,b_0]$ (thus turning this leaf node into an internal node and introducing two children).
Next, we find the leaf interval $[a_1,b_1]$ containing $b$; if $b < b_1$, we split this leaf interval into the two intervals $[a_1,b]$ and $[b+1,b_1]$ (thus turning this leaf node into an internal node and introducing two children).
At this point, I claim that the interval $[a,b]$ can be expressed as the disjoint union of $O(\lg n)$ intervals corresponding to some subset of $O(\lg n)$ nodes in the tree.  So, delete all the descendants of those nodes (turning them into leaves) and set the value stored in those nodes to $y$.
Finally, since we modified the shape of the tree, we'll perform any necessary rotations to re-balance the tree (using any standard technique for keeping a tree balanced).

Since this operation involves a few simple operations on $O(\lg n)$ nodes (and that set of nodes can be easily found in $O(\lg n)$ time), the total time for this operation is $O(\lg n)$.

This shows that we can support both the get and set operations in $O(\lg n)$ time per operation.  In fact, the running time can be shown to be $O(\lg \min(n,s))$, where $s$ is the number of set operations performed up until now.

Adding support for add

We can modify the above data structure so that it can also support the add operation.  In particular, instead of storing the value of the function in the leaves, it'll be represented as the sum of numbers stored in a set of nodes.

More precisely, the value $f(i)$ of the function at input $i$ will be recoverable as the sum of the values stored in the nodes on the path from the root of the tree down to the leaf whose interval contains $i$.  In each node $v$ we'll store a value $V(v)$; if $v_0,v_1,\dots,v_k$ represent the ancestors of a leaf $v_k$ (including the leaf itself), then the value of function at $I(v_k)$ will be $V(v_0)+\dots + V(v_k)$.

It is easy to support the get and set operations using a variant of the techniques described above.  Basically, as we traverse the tree downward, we keep track of the running sum of values, so that for each node $x$ that the traversal visit, we'll know the sum of values of the nodes on the path from the root to $x$.  Once we do that, simple adjustments to the implementation of get and set described above will suffice.

And now we can support $\text{add}([a,b],\delta)$ efficiently.  First, we express the interval $[a,b]$ as the union of $O(\lg n)$ intervals corresponding to some set of $O(\lg n)$ nodes in the tree (splitting a node at the left endpoint and right endpoint if needed), exactly as done in steps 1-3 of the set operation.  Now, we simply add $\delta$ to the value stored in each of those $O(\lg n)$ nodes.  (We don't delete their descendants.)

This provides a way to support get, set, and add, in $O(\lg n)$ time per operation.  In fact, the running time per operation is $O(\lg \min(n,s))$ where $s$ counts the number of set operations plus the number of add operations.

Supporting the stab operation

The stabbing query is the most challenging to support.  The basic idea will be to modify the above data structure to preserve the following additional invariant:

  (*) The interval $I(\ell)$ corresponding to each leaf $\ell$ is a maximal flat interval.

Here I say that an interval $[a,b]$ is maximal flat interval if (i) $[a,b]$ is flat, and (ii) no interval containing $[a,b]$ is flat (in other words, for all $a',b'$ satisfying $1 \le a' \le a \le b \le b' \le n$, either $[a',b']=[a,b]$ or $[a',b']$ is not flat).

This makes the stab operation easy to implement:

$\text{stab}(i)$ finds the leaf whose interval contains $i$, and then returns that interval.

However, now we need to modify the set and add operations to maintain the invariant (*).  Each time we split a leaf into two, we might violate the invariant if some adjacent pair of leaf-intervals have the same value of the function $f$.  Fortunately, each set/add operation adds at most 4 new leaf intervals.  Also, for each new interval, it is easy to find the leaf interval immediately to the left and right of it.  Therefore, we can tell whether the invariant was violated; if it was, then we merge adjacent intervals where $f$ has the same value.  Fortunately, merging two adjacent intervals does not trigger cascading changes (so we don't need to check whether the merger might have introduced additional violations of the invariant).  In all, this involves examining $12=O(1)$ pairs of intervals and possibly merging them.  Finally, since a merger changes the shape of the tree, if this violates the balance-invariants, perform any necessary rotations to keep the tree balanced (following standard techniques for keeping binary trees balanced).  In total, this adds at most $O(\lg n)$ additional work to the set/add operations.

Thus, this final data structure supports all four operations, and the running time for each operation is $O(\lg n)$.  A more precise estimate is $O(\lg \min(n,s))$ time per operation, where $s$ counts the number of set and add operations.

Parting thoughts

Phew, this was a pretty complex scheme.  I hope I didn't make any mistakes.  Please check my work carefully before relying upon this solution.


MAX SAT Optimization problem search problem: find the assignment that maximize the number of satisfied clauses

For decision problem: determine whether there is an assignment that satisfies k of clauses.

optimization problem : determine the number of clauses that maximize the number of satisfied clauses ( is this correct?)

If I want to reduce search to optimization, how would I do it? Or
how do I use the number of clauses (the answer from optimization problem)  to determine the assignment (the search problem)?

For MAX-SAT:

The optimization problem is, given a CNF, to find the maximal number of clauses that can be satisfied at once.
The search problem is, given a CNF, to find an assignment satisfying the maximal number of clauses.
The decision problem is, given a CNF and a threshold $k$, whether there is an assignment that satisfies at least $k$ clauses.

To reduce from search to optimization, use the self-reducibility of SAT: pick a variable $x$, and try substituting $x=0$ and $x=1$, using your optimization oracle to determine which of these partial assignments leads to an assignment satisfying the maximum number of clauses.


Get the previous and next values of a string in lexicographic order I'm working with a noSQL database and for certain reasons I can't use equality filtering in my queries

e.g

select all from database where id = 10

is NOT allowed

but inequality filtering is allowed

e.g

select all from database where id > 1

My ID's are UNIQUE strings (emails) and I need to use equality filtering so I thought to convert inequality statements to equality statements (e.g where id = 10 could be written as Where id > 9 AND < 11).

If my ids were numbers I would use code such as this to get my key:

function(id)
{

    //assuming no id can be 0 and no id can be larger than 2^53-1. This will return the row with id = 10
    var result = sendToDatabaseQuery('SELECT * FROM database where id > ' + (id-1) + ' AND ' id < ' (i+1)');

}

With numbers it would be very easy to do this, but with Strings I have found it to be more challenging. If I have an email such as mysuperfakeemail.gmail.com how could I get the previous and next lexicographic string (I am assuming they are mysuperfakeemail.gmail.col and mysuperfakeemail.gmail.con respectively)? Is there an established algorithm for this type of function already? I am writing this on a nodejs server with UTF-8 characters.

Computing the previous and next lexicographic string is the same as subtracting and adding 1 to a number, only your number is encoded in some higher base corresponding to your alphabet. I presume you already know how to add and subtract 1, but if not, there are many online resources explaining that.

You mention UTF-8, which is not quite an ordered alphabet. Yet your SQL interpreter has some specific rules for ordering strings, and is should include an ordering of the actual alphabet (UTF-8 or smaller).


What's the difference between $O(1)$ and $o(1)$? What's the difference between $O(1)$ and $o(1)$ ?

A function is $O(1)$ if it is bounded from above. It is $o(1)$ if it tends to zero. Any function which is $o(1)$ is also $O(1)$.

For example, $\sin^2 x$ is $O(1)$ but not $o(1)$, and $1/x$ is both $O(1)$ and $o(1)$.


Is this solution to the dining philosopher's problem entirely valid? In a question on Stack Overflow, the answer by Patrick Trentin lists the following solution to the dining philosopher's problem:

  A possible approach for avoiding deadlock without incurring
  starvation is to introduce the concept of altruistic philosopher, that
  is a philosopher which drops the fork that it holds when it realises
  that he can not eat because the other fork is already used.

  Having just one altruistic philosopher is sufficient in order to avoid
  deadlock, and thus all other philosophers can continue being greedy
  and attempt to grab as many forks as possible.

  However, if you never change who is the altruistic philosopher during
  your execution, then you might end up with that guy starving himself
  to death. Thus, the solution is to change the altruistic philosopher
  infinitely often. A fair strategy is to change it in a round robin
  fashion each time that one philosopher acts altruistically. In that
  way, no philosopher is penalised and you can actually verify that no
  philosopher starves under the fairness condition that the scheduler
  gives a chance to every philosopher to execute infinitely often.

I was intrigued by this solution because I hadn't heard it before. However, I can find no references to it anywhere in the existing literature.

I did a quick check, and saw that it isn't listed on Wikipedia as a standard solution.
Googling 'altruistic philosopher dining' yields only one result from Google Books that does not discuss the round robin strategy and only vaguely alludes to the altruistic philosopher to talk about the perils of starvation.
I tried looking up altruistic philosopher on ArXiv, only to return no results.
Trentin cites a book about nuXmv, a symbolic model checker, as his source but only provides a link to his own lab slides.

So my question: does this naive yet seemingly remarkable solution actually work? Or are there pitfalls that have been overlooked? I find it hard to believe that, if it works, it wouldn't have at least some mention somewhere - but at the same time I can't see why it wouldn't work, as it's a fairly naive solution.

If it does work, can I either a) have a reference to a proof, or b) an actual proof that this solves the dining philosopher's problem? If it doesn't, same standards apply, except for the negation of a proof. :)

The description of an altruistic philosopher given in this answer, that you quoted in your question, is slightly imprecise. What it really is going on is that:

  A possible approach for avoiding deadlock without incurring in starvation is to introduce the concept of altruistic philosopher, that is  a philosopher which drops the fork that it holds when it realizes that no one can eat because there is a deadlock situation.

So the actual condition for altruism is stronger than the one in your quote. Another important condition is that the fork that is put down by the altruistic philosopher is handed over to the philosopher waiting for it, e.g. by waking up the process that is waiting on the resource. (Otherwise the deadlock situation could actually reappear one instant later).

I apologize for the confusion I may have created in this regard. In my stackoverflow answer I simplified the actual model to convey the basic idea, but this left out some details that are important for "formally proving" the correctness of the solution.

Note: I don't have the time to write down a formal proof in this moment, so I will try to make a simple argument.

The pre-conditions are as follows:

Ph_i is the altruistic philosopher
Ph_i holds the left fork and the right fork is hold by its successor Ph_{i+1}
There must be a deadlock: every Ph_k is holding the left fork

the actions performed are:

Ph_i gives his left fork to its predecessor Ph_{i-1}

the post-conditions are as follows:

Ph_{i+1} becomes the new altruistic philosopher
Ph_{i-1} is now holding two forks and can eat
After eating, Ph_{i-1} puts down both forks.

The important invariant is that the predecessor of the altruistic philosopher is guaranteed to eat after a deadlock situation.

Given N philosophers, the round robin policy guarantees that each philosopher becomes altruistic exactly once in a sequence of N deadlocks.
Hence, each philosopher is guaranteed to eat (at least) once every N deadlocks (because it is the predecessor of an altruistic philosopher exactly once every N deadlocks).

This is, of course, the analysis of the worst-case possible outcome. Depending on the work-load, deadlocks may not arise so frequently and in this case each philosopher would have the chance to eat pretty much anytime it wants.

The naive solution to the dining philosophers presented in this answer is quite effective for the limited purposes of teaching Model Checking / Formal Verification techniques. However, I would not assume that it is the best engineering solution for practical situations because it requires one to detect a deadlock. Also, it may be hard to reduce practical problems to the simple scenario of the dining philosophers (e.g. there could be many more resources involved, the order in which resources are grabbed is not fixed, etc.).


Pipeline hazards question i know that resources duplicate is solution to Structure Hazard but what about code scheduling ....
Can code scheduling considered as a solution to Structure Hazard ?
with Example please .

Assuming you're referring to how out of order execution can resolve a lack of resources. As resources are used and code is executed temporally, by reordering the code, the usage of resources can be rearranged in time, benefiting execution by a more efficient (less time waiting, more time using) use of resources.

I'm not a big fan of examples but let's suppose two super scalar pipelines want to use resources A, B, C and D, at the same time:

time = 0 | A | A
time = 1 | B | B
time = 2 | C | C
time = 3 | D | D

The CPU can reorder these instructions

time = 0 | B | A
time = 1 | C | B
time = 2 | D | C
time = 3 | A | D

Another example:
Suppose one instruction pipeline has the following instructions:

multiply_then_add
add_then_multiply
do_something_else

Then the usage of resources might look like this:

time = 0 | M |   |
time = 1 |   | A |
time = 2 |   | A |
time = 3 | M |   |
time = 4 |   |   | D

where M = multiplier, A = adder, and D = Doing something else. As you can see, the two add instructions back to back are an issue, if they were separated by a gap we could shorten the time taken, and out of order execution can resolve this:

multiply_then_add
do_something_else
add_then_multiply

time = 0 | M |   |
time = 1 |   | A |
time = 2 |   |   | D
time = 3 |   | A |
time = 4 | M |   |

Which can be optimised:

time = 0 | M |   |
time = 1 |   | A |
time = 2 |   | A | D
time = 4 | M |   |


Sorting "almost sorted" array in $O(n\log\log n)$ Given array $A$ of length $n$, we call it almost sorted if there are at most $\log n$ indices satisfying $A[i] > A[i+1]$.
Find an algorithm that sorts the array in $O(n\log\log n)$.

My attempt:

Create an array $B$ of size $\log n + 1$.
Go through the array $A$, recognize the $\log n$ pairs, and insert them into $B$.
Sort $B$ using insertion sort in time $O(\log^2 n)$.

At this point I am stuck.

Suppose that $A$ is an array with $m$ indices satisfying $A[i] > A[i+1]$. You can find these indices in $O(n)$. These $m$ indices split $A$ into $m+1$ nondecreasing arrays $B_1,\ldots,B_{m+1}$ of total length $n$. We now merge them according to the following strategy: at each step, take the two shortest arrays, and merge them. You can implement the choice mechanism in $O(m\log m) = O(n\log m)$ using a heap.

When merging two arrays of length $a,b$, the running time is $O(a+b)$. Hence we would like to understand the total sum $S$ of $a+b$, where $(a,b)$ goes over all $m$ pairs of arrays being merged. To this end, we consider a merge tree, which is formed in the following way. We start with $m+1$ vertices corresponding to $B_1,\ldots,B_{m+1}$. When two arrays corresponding to vertices $x,y$ are merged, we create a new vertex with $x,y$ its only children. You can check that
$$
S = \sum_{i=1}^{m+1} |B_i| \mathrm{depth}(B_i).
$$
Consider now a probability distribution $X$ on $[m+1]$ with $\Pr[X=i] = |B_i|/n$. Then $S/n$ is the average codeword length of an optimal prefix code for $X$ (this is because we're essentially running Huffman's algorithm). Therefore $S/n < \log m + 1$, showing that the merging steps take $O(n\log m)$ time in total.

Summarizing, the algorithm runs in time $O(n\log m)$.

(Strictly speaking, to handle the cases $m=1$ and $m=0$, we should replace $m$ with $m+2$.)


Multiple correct answers for compilation When you are asked to hand compile into assembly language, are there multiple correct answers? For example, in https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c11/c11s3/compilation_answers.pdf, can you get the correct solution even if your solution doesn't match the solution given?

Yup.  There are multiple sequences of assembly instructions that all do the same thing.  (For instance, one trivial way to see this is to notice that you can insert a no-op instruction anywhere.)  They might not all be equally good, but they'd all be correct.


Solving linear system of nonhomogenous equations that are known to have natural solutions Any idea is appreciated. A generic approach that works for any system would be best but if you want more info about what I'm looking for, the equations are usually short (having few variables, from 1 to 4 at most), but in exchange, there are a lot of equations (30-60).
The system is known to always have these properties:

The equations are linear and nonhomogenous, coefficients and solutions are natural. In other words, equation $k$ has form $a_{k1}x_{k1}+a_{k2}x_{k2}+...+a_{kn}x_{kn}=b_k$ where

$b_k\in N$
$a_{k1},a_{k2},..,a_{kn} \in N$
$x_{k1},x_{k2},..,x_{kn} \in N$

There is at least one non trivial solution.

Currently I am going with a bruteforce and heuristic approach that tries to narrow down the range I need to bruteforce before trying out all possible values but it can get messy pretty quick when I get a tricky system.

You can represent the system as a matrix equation as $Ax = b$, where $k^{th}$ row of $A$ is the coefficients $[a_{k1},a_{k2}...,a_{kn}]$, $x = [x_1, x_2,...,x_n]$ and $b = [b_1,b_2,...,b_m]$.
Unique Solution:
If the system has a unique solution, you should be able to get $A$ into row-echelon form. Then, you'll find a row with only one non-zero coefficient, corresponding to an atomic expression like $x_j = b_k$. Plug this in by dropping the $j^{th}$ column and the $k^{th}$ row and updating all other rows as $b_l' = b_l - a_{lj}b_k$. Recursively keep doing this until all values are found.
I finally remembered that the name of this procedure: Gaussian Elimination. Here is a nice concise description with a solved example.
Underdetermined System:
If there are multiple solutions, then the number of linearly independent rows is less than the number of variables. Since you seem to have many more equations than variables, this is great news. Using the row-echelon form, you can weed out redundant equalities and end up with a much smaller system of equations.
Now, let $$z_k = \min_{\substack{1 \leq i \leq m \\ a_{ki} \neq 0}}\left\{\frac{b_i}{a_{ki}}\right\},$$
so we get $1 \leq x_k \leq z_k$ as the feasible set for each variable. One way to shrink the brute-force approach is to order the variables by their upper bounds. If $z_{k_1} \geq z_{k_2} \geq ... \geq z_{k_n}$, suppose variables satisfy $x_{k_1} \geq x_{k_2} \geq ... \geq x_{k_n}$. Then, you can enumerate the solutions under this constraint by enumerating.
For example, let's say $z_1 = 3, z_2 = 2, ...$. Then, you would have $(3,2,..),...,(3,1,..),...,(2,2,..),...,(2,1,...),...,(1,1,...),...$.
With this ordering assumption you are searching over a much smaller set. Once you have that, you can check the permutations of these solutions and if they are feasible for all variables, they are valid solutions.
For example, for $x_1 + x_2 + x_3 = 3$, let's say we break the tie as $x_1 \geq x_2 \geq x_3$. Then, the constrained solutions are $(3,0,0), (2,1,0), (1,1,1)$ and the permutations of these give you the whole set since they are all the feasible due to $z_1=z_2=z_3$.


randomized algorithm for checking the satisfiability of s-formulas, that outputs the correct answer with probability at least $\frac{2}{3}$ I'm trying to practice myself with random algorithms.

Lets call a CNF formula over n variables s-formula if it is either unsatisable or it has at
least $\frac{2^n}{n^{10}}$ satisfying assignments.

I would like your help with show a randomized algorithm for checking the
satisfiability of s-formulas, that outputs the correct answer with probability at
least $\frac{2}{3}$.

I'm not really sure how to prove it. First thing that comes to my head is this thing- let's accept with probability $\frac{2}{3}$ every input. Then if the input in the language, it was accepted whether in the initial toss($\frac{2}{3}$) or it was not and then the probability to accept it is $\frac{1}{3}\cdot proability -to-accept$ which is bigger than $\frac{2}{3}$. Is this the way to do that or should I use somehow Chernoff inequality which I'm not sure how.

Basic idea: Pick a random assignment and check it.
Then, repeat it many times. Even if one of the assignments satisfies the formula you answer "YES" (otherwise, you answer "NO")

We know that the input formula is "simple": in plain words it means that either it is not-satisfiable or it has "many" satisfying assignments. If it is not satisfiable - no matter what assignment(s) you choose, it will never satisfy the formula. Therefore, the above algorithm always answers correctly for such inputs, and from this point and on we consider only satisfiable inputs.

If the input is satisfiable, what is the probability that a random assignment satisfies it?

Let $\varphi$ be a CNF over $n$ variables with more than $2^n/n^{10}$ satisfying assignments, then
$$ \Pr_{x\sim U}[ \varphi(x)=T] \ge \frac{2^n/n^{10}}{2^n}$$

Now we repeat it $k$ times (you'll have to pick $k$ carefully. Let's do it later).
Each time we pick a random $x$. Let $E_i$ be the event that in the $i$-th instance $\varphi$ is satisfied. What is the probability that we find out at least one satisfying assignment after $k$ tries?

It is $\Pr[\bigcup_{i=1}^k E_i]$. We know that $\Pr[E_i] \ge 1/n^{10}$, and you can use standard linearity (of independent events) to work it out.

Final step - find the (minimal) $k$ that makes $\Pr[\cup_k E_i] \ge 2/3$ as required.

Bonus question: how low can you make $k$ (and make your algorithm more efficient) if you analyze the above using Chernoff's inequality?


Finding topologically sorted connected components in directed acyclic graph I am aware topological sort and connected component algorithms are very related, but I have been looking for an algorithm to simultaneously compute both, rather than one after the other, and I am finding it surprisingly hard.

Assuming a directed acyclic graph, is it possible to simultaneously find the list of connected components while at the same time topologically sorting the nodes in each of the components?

To clarify, the output would be a list of components, where each component is a topological order of the nodes contained in that component.

Bonus points if the list of connected components is sorted following the insertion order of nodes in the graph (i.e. the first connected component will contain the first node ever inserted in the graph, regardless of global topological order; etc for subsequent components).

Standard algorithms for computing strongly connected components label each vertex with a number indicating which component it is part of.  Then, you can use that to construct the "metagraph" of components (where each component of the graph is a vertex of the metagraph, and there is an edge $i \to j$ in the metagraph iff there is an edge $v \to w$ in the original graph where $v$ is in component $i$ and $w$ is in component $j$) in linear time.  Finally, you can apply a topological sorting algorithm on the metagraph.

Some algorithms for computing strongly connected components (such as Tarjan's algorithm) already do that for you for free.  Or, you can do it yourself as a postprocessing phase; since it takes only linear time, it won't increase the asymptotic running time of the algorithm.

See, e.g., https://en.wikipedia.org/wiki/Strongly_connected_component, https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm, and https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm.


Proving that a language is not in P using diagonalization Pardon me if i'm missing something which is very obvious here but i cant seem to figure it out.

$E=\{ \langle M, w \rangle \mid \text{ Turing Machine encoded by $M$ accepts input $w$ after at most $ 2^{|w|}$ steps}\}$

We have to prove $E\notin P$

The book (Papadimitrou, Elements of the ToC) assumes $E\in P$ and it constructs another language (a diagonal one)

$E_1=\{\langle M\rangle \mid \text{ Turing Machine encoded by $M$ accepts input $M$ after at most $  2^{|M|}$ steps}\}$

and takes its complement language $E_1'$ and it follows that with the assumption $E\in P$ , it is true that $E_1' \in P$

The question it then asks is the following: Say the polynomially bounded turing machine to decide $E_1'$ is $M^*$ then what happens when $M^*$ is presented with $M^*$ as an input?
Now I understand it cant give an yes because that results in a contradiction. My doubt is where is the contradiction if the answer is no?

The idea (which doesn't quite work) is that given that $E'_1 \in P$, $M^*$ runs in time at most $2^n$ on an input of length $n$ (that's not quite true). Given that, if $M^*$ rejects $M^*$ then by the definition of $E'_1$, $M^*$ accepts input $M^*$ after at most $2^{|M^*|}$ steps, which is a contradiction.

The other direction, which you were happy with, is problematic: if $M^*$ accepts $M^*$ then by the definition of $E'_1$, $M^*$ does not accept input $M^*$ after at most $2^{|M^*|}$ steps. That's not a contradiction since our assumption that the running time of $M^*$ is $2^n$ was wrong - perhaps it's $2^{|M^*|} n$. So you need to be more subtle - presumably Papadimitriou addresses this.


How to design this synchronous circuit? I have seen this model question on synchronous circuit , but i could not understand the logic,  can anyone please help me?

"Develop the state diagram for a synchronous sequential circuit which will recognize the bit sequence 1101 (ie, every time the sequence 1101 is detected in the input bit stream, the circuit has to output a 1 and otherwise a 0)."

What is the question here?? do we have consider all possible combinations ( 2^4 - 16 ) to do this ? if so , according to the question , do we have only one occasion where we get the output 1??

please explain it.
-Regards

The question asks for a circuit which is given a sequence of bits, one in each round, and is supposed to output $1$ each time that the last $4$ bits form the subsequence $1101$; otherwise $0$ should be output. For example, if the input is $110110101$ then the output should be $000100100$. Naturally, the circuit will have to retain some memory.


Constructing right-linear grammar Is the grammar

$\qquad S \to 1A0A \mid 0A \mid \varepsilon$

a right-linear grammar? $A$ is a nonterminal here, $0$ and $1$ are terminals.

I know $0A$ is right-linear but what about $1A0A$?

Trying to construct a right-linear grammar for language $10(0+1)^*10$.

I'll give some hints as plain text, do try to have a go at solving the questions with this help before revealing the spoilers.

The first part you should be able to answer very easily - check the definition of a linear grammar, how many non-terminals can be on the right-hand side of the production?

   At most one, so this isn't a linear grammar, let alone right-linear.

For the second part, perhaps one way to approach it is to first build an NFA that recognises the same language that the grammar generates, then you can use the transitions of the NFA to generate the transitions of the grammar.

   $S\rightarrow 1A$
 $A\rightarrow 0B$
 $B\rightarrow 1B \;|\; 0B \;|\; C$
 $C \rightarrow 1D$
 $D\rightarrow 0$
 This grammar is certainly not the only one, but should look something like an NFA for the same language - the non-terminals are states, and $D$ is the accept state.


Big-O Notation Statement True? Considering functions f and g, is the following true?

$ (f \in O(g)) \implies (f \in \Theta(g)) \lor (f \in o(g))$

If not, can you please state an example? Despite thinking hard, i could not find one.

Thanks a lot!

No, this is not true. For example, let $f$ be the constant $1$ function, and define $g$ by $g(2n) = 1/n$ and $g(2n+1) = 1$.


Lexicographic permutation Consider that you have a permutation of $n$ elements from $1$ to $n$ and you need to sort the elements lexicographical . for example sorted permutation for $n=11$ is $1,10,11,2,3,4,5,6,7,8,9$ .Now consider this notation $Q(n,k)$ as position of number $k$ in  lexicographical  sorted permutation. $Q(11,2)=4$. We are given $k$ and $m$ we need to find minimum $n$ such  that $Q(n,k)=m$ holds.
I could only find that $n>=max(m,k)$ and for next i do not know how to solve it .
Source of question  link

First, there is one special case of $k$, the powers of 10, which are 1, 10, 100, etc. Their positions at a lexicographically ordered sequence of positive integers are fixed.

1 is always at the 1st position.
10 is always at the 2nd position once it appears. Any number except 1 and itself will be sorted after it.
100 is always at the 3rd position once it appears. Any number except 1, 10 and itself will be sorted after it.
And so on.

We should process this peculiar case first.
The position of $k$ in the lexicographically sorted sequence is determined by the numbers that are before $k$ (lexicographically). These numbers fall into three categories.

the numbers that are smaller than $k$. If a permutation of 1, 2, ..., $n$ contains $k$, it must contain all these numbers as well.
$k$ itself.
the numbers that are bigger than $k$.

Let us compute how many numbers before $k$ are smaller than $k$. For example, take k $=$ 619. Any number smaller than $k$ has at most three digits.

All three-digit numbers before 619 constitute the interval [100, 619).
All two-digit numbers before 619 constitute the interval [10, 61].
All one-digit numbers before 619 constitute the interval [1, 6].

In total, there are 519 + 52 + 6 $=$ 577 numbers that are smaller than 619 and before 619. So if $m\le$ 577 + 1, where 1 stands for 619 itself, no $n$ can satisfy $Q(n,\,$619$)=m$. If $m=$ 578, the minimum $n$ is 619 itself.
Otherwise, the given $m$ is bigger than 1 plus the number of numbers smaller than $k$ and before $k$. We have to include numbers bigger than $k$ that are before $k$ to increase the position of $k$. For the same example, when $m\gt 578$, $n=$ 619 is not enough.

Try adding the number between 1000 inclusive and 6190 exclusive.
If that is not enough, try adding the number between 10000 inclusive and 61900 exclusive.
If that is not enough, try adding the number between 100000 inclusive and 618900 exclusive.
And so on.


Combinatorics approach to staircase problem There are $n$ stairs and a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs every time. What is the total number of ways they can reach the top?

There are many ways to do this by using code. But when I first read this problem was to use a combinatorics approach. This problems seems very similar to a "stars and bars" problem. The stars would be the number of stairs and the bars would be the number of steps that be taken.

Given this is the case, my solution is simply: ${(n)+(2-1)}\choose{1}$.

Is the concept of stars and bars the simplest approach to solving this problem or is there a simpler combinatorics concept at play here and if so, how do I recognize such things? By simple, I mean can I solve this problem by simpler computation than combinatorics (even if it requires some sort of brute force method)?

Let $W(n)$ be the number of ways you can reach step $n$ by 1- or 2-step moves. Then $W(1)=1, W(2)=2$ (by two 1-step moves or one 2-step move). Then to reach $n$ height, your last move is either a 1-step move from height $n-1$ or a 2-step move from height $n-2$, giving us the recurrence $W(n) = W(n-1) + W(n-2)$. I'll leave the solution of this recurrence to you. (Hint: it should be familiar.)


Logic gate which checks if the input is a negative number and changes its output based on that I need to create a HDL which will use logic gates to demonstrate if something is a negative number in two's complement. The input is 8 bits, while the output is 1 bit, and if the input is a negative number then the output should be true, and in any other case, the output should be false.

I've noticed that all the negative numbers in two's complement start with a 1 in their binary notation, i.e the number -8 is written as 1000 in binary, -7 as 1001 and so on until 0, which is when it switches to 0000, 1 being 0001 and so on until +7.

I originally had the idea of using a Not gate for this, but i'm not entirely sure how it would work out. I tried something like:

Not(in=in[1], out=in[2]);
Not(in=in[2], out=in[3]);

etc but it didn't work. I also thought of using an Or gate, as if either of the inputs are true (negative number) then the output would also be true to signify a negative number, but if both of the inputs are false (not negative) then the output would also be false.

Any help?

You miss the obvious solution, just wire the MSB to output.


Matrix to Multi-level security How to convert access control matrix to Bell-LaPadula. Can teach me step by step
What best way to control converting Bell-LaPadula Model lattice using Access Control Matrix

Matrix GIVEN

$\quad\quad\quad\quad$O1      O2      O3    O4
    S1      w       r       w     rw
    S2      rw                    r
    S3              w       w     r
    S4      w       w       w     r
    S5              rw      rw    r

convert to BLP lattice diagram

Subject S2 has read-write access to Object 1, which is something no other subject has. On the other hand, subject S2 has no rights to Objects 2 and 3, which is something no other subject has. So Subject S2 has incomparable rights to all other subjects.

Similarly S1 is incomparable to the others.

S4 clearly has more rights than S3.
S5 clearly has more rights than S3.

So the subjects' "security levels" can be shown like this:

$\,\,\,$S5 S4
   \ /     S1   S2
    S3

(I don't know this subject before your question so this is just my impression. This subject has been discussed in three questions at cs.stackexchange.com in the past.)


understanding loop invariants I have a bit of experience with loop invariants but I'm not really clear on them. I'm trying to learn them through an Algorithm I have.
Reverse(X,Y)
   n = X.length
   for(i = 1 to n)
      Y[n - i + 1] = X[i]
   return Y

This copies values in array X into array Y in reverse order, and returns array Y. If X and Y both have length n (i.e., n = X.length = Y.length) and both arrays are indexed from 1 to the length of the array, what would be some loop invariants for the for loop which would prove its correctness?

The reverse of X[:i], the prefix of X up to the $i$-th position is equal to Y[n-i+1:], the suffix of Y from the $(n-i+1)$-th position onward.
Before the loop starts, which we could consider as $i=0$, we have that the reverse of the prefix of X of length zero is equal to suffix of Y of length zero.
Each step of the loop preserves the property for the previous value of i and makes the property true for the current value of i.
At the end of the loop the property is satisfied for i=n, which implies that the reverse of X is equal to Y.


Counter example to graph coloring heuristic using BFS I am considering the following heuristic for the graph coloring problem (i.e. to color a graph $G$ using a minimal number of colors so that no two adjacent vertices have the same color):

  Explore the vertices of $G$ in the order that they would be explored by a BFS search (with arbitrary starting vertex) and assign each vertex the lowest numbered color not yet used for one of its neighbors.

Since I don't think this algorithm is correct, I am trying to find a counterexample where coloring a graph in this way does not yield a coloring with the minimal number of colors. Does anyone know of such an example?

Here's one:

The labels indicate the intend BFS ordering (alphabetical). A different ordering can produce a different result, so more work would have to be done to get a graph where your BFS approach fails for every starting point (it would probably be very messy too).

Assuming we follow this ordering however, we get the following colouring:

The key being that $e$ and $f$ get coloured last, so $c$ removes blue from the possibilities, and $d$ removes red, so $e$ and $f$ must have two new colours.

However this graph is 3-colourable:

By choosing to use more colours earlier, it relaxes the constraints later.

I'll also throw in a conjecture that this is smallest counterexample, for no other reason than to challenge others to find smaller ones ;).


Prove that there isn't a DFA characterized by (a*)+(b*) for which |Q| = 3 Let $R=(a*)+(b*)$ be a regular expression. Prove that there cannot exist any DFA $M=(Q,\Sigma,\delta , q0, A)$ such that $|Q| = 3$ and $L(M)=L(R)$.

The problem is, I think IT IS possible to construct such a dfa that has 3 states in total.

Am I missing something?

What you draw is an NFA, because you do not have both transition for $a$ and $b$ in two accept states.
Indeed, you need 4 states at least. Because you have 4 different states:

Initial state
Detect $a^*$ strings
Detect $b^*$ string
None of them

You can't merge the first 3 steps because they are exclusive. Now, you can suppose that we can merge the 4th state with the others. Definitely you can't merge the 4th state with second and third state. Hence. the only possibility is merging the 4th state with the first state. But, we have some transitions from the initial state to other states, and if we merge the 4th and the first state, we will accept some strings that are not totally $a$ or $b$. And that is the contradiction to the definition of the language. Therefore, we need a state to go there if we found any $b$ in the middle of some $a$s or vice versa.


$k$th Largest Algorithm in a range $[k, k+c]$ The well-known algorithm for computing the $k$-th largest element in an unsorted array of size $n$ runs in $O(n)$ time.

How about for a range $[k, k+c]$, where $c$ is not necessarily independent of $n, k$? The obvious "brute-force" algorithm is to find the $k$th largest using the original $O(n)$-time algorithm, then the $k+1$-th largest the same way, ..., find the $k+c$-th largest (and also, the algorithm outputs these in sorted order). However, this takes $O(nc)$ time, and $c$ can possibly be $\Theta(n)$, which can lead to an $O(n^2)$ algorithm. In this case, we could have just sorted the array and extracted the elements, which takes $O(n \log n)$ time.

Is there a better (known) way of doing this? I can't find any references online.

Step 1. Use QuickSelect to find the $k$th largest number in the array.  Call it $x$.

Step 2. Use QuickSelect to find the $k+c$th largest number in the array.  Call it $y$.

Step 3. Find all elements in the array that are at least $x$ and at most $y$.  This can be done by simply iterating over the array and comparing each element to $x$ and $y$.

Each step can be done in $O(n)$ time.  Therefore, the total running time is $O(n)+O(n)+O(n) = O(n)$ time.


Unique min-cut means unique max flow? This is not a home work question.

Is that correct to say in a flow network, if min cut is unique then max flow must also be unique?

Assume we have two max flow in a network. Then for each max flow, we can get a min cut and they are surely different.

I do not agree with the downvoters of your question. This questions seems like a legit misunderstanding of the statement of the min-cost-max-flow theorem.
The theorem states that the value of the sum of edge weights in a minimum $s$-$t$ cut of a graph is equal to the value of the maximum $s$-$t$ flow in the graph interpreted as a flow network. It does not establish a one-to-one correspondence between flows and cuts.
In fact, this correspondence cannot be established in general. Here is a counter example of an unweighted undirected graph (all weights/capacities are unit):

$1$-$5$ max-flow/min-cut is equal to one. While there is a single minimum cut ({1 - 2}). There are a lot of possible maximum flows (take the unit of flow entering 2 and distribute it between 3 and 4 as you like).


Formal notion of a call graph for Turing machines To most computer programs one can assign a "call graph".
Is there a formal notion of call graphs of Turing machines?

Motivation is, that one could intuitively call a decidable language $L$ "irreducible" if every Turing machine which decides $L$ has a "trivial call graph" (Trivial here intuitively means, that the machine $M$ which decides $L$ can not call another machine $M'$ during the computation on words). This would intuitively correspond to the notion that "irreducible problems" cannot be solved by breaking them up into smaller problems, for example by divide and conquer.

Another motivation is to understand the concept of composition of Turing machines, which is "equivalent" to understand what is meant when one speaks of "subroutines" (which one could call a "submachine").

Turing machines have no concept of "calling".

Tou can jump to another state and that can look quite a lot like a procedure call, especially if an author's description of the machine in English uses words that make it sound that way. But that's all you can do. In particular, there's no notion of "return" in a Turing machine. There's no way to say "OK, this procedure is finished – now go back to wherever we came from." All you can do is say "OK, this procedure is finished – now go to this specific point."

Of course, because Turing machines are Turing powerful, you can simulate these things. For example, you can write some notion of a return address on the tape as part of your simulation of a procedure call. But that's not intrinsic to Turing machines: it's just a property of the particular Turing machine you're writing at the moment. A coding convention, if you like.


Understanding church numerals I am learning lambda calculus as my previous questions indicate . But in a different book , namely , The structure and interpretation of  computer program I cam across the concept of "church numerals " and the stumbled upon the following link about church numerals :

https://www.cs.rice.edu/~javaplt/311/Readings/supplemental.pdf

It goes on stating the following in the first page :

The Church numerals that follow just have additional applications of the successor function:

$$\begin{align}
C_2 &= \lambda f . \lambda x . f(fx) \\
C_3 &= \lambda f . \lambda x . f(f(fx))\\
C_4 &= \lambda f . \lambda x . f(f(f(fx)))\\
&\vdots\\
C_n &= \lambda f . \lambda x . f nx
\end{align}
$$

and then he mentions that had we been having a little more powerful language then we could define the following two functions :
$$\begin{align}
S &= \lambda r.\text{“ring the small bell (ding) and apply r”}\\
Z &= \lambda r.\text{“ring the big bell (dong)”}
\end{align}
$$
and then says that the application of

$C_4$ to  $S$ and $Z$ would yield "ding ding ding ding dong"

How to explain the above result without even knowing what "f" is ?

POST EDIT :
After I got the first answer , I tried computing the sequence by the help of clue provided .

By applying step by step I will get (lambda r.ding r)^4 (lambda r.dong) = (lambda r.ding r)^4 dong .

Now each evaluation of (lambda r.ding r) leads to "ding r " .

So the overall evaluation becomes "ding ding ding ding r dong ".

Am I doing it right ?If yes then , how to account for omission of r in the expression?

P.S :
For some trivia information , has there been any known application of this idea of church numerals to any field of mathematics ?

Using your definition for Church Numerals and trying to see what's going on:

$$ \begin{align} 0 &= \lambda f. \lambda x. x \\
                 1 &= \lambda f. \lambda x. f x\\
                 2 &= \lambda f. \lambda x. f f x\\
                 3 &= \lambda f. \lambda x. f f f x\\
&\vdots
\end{align} $$

Now let's say have a function $g$ and some $a$, try to use $g$ and $a$ as arguments to $0$, that is:

$$ \begin{align} 0 ~ g ~ a &= (\lambda fx. x)~g~a\\
\quad &\rhd_{1\beta} ([g/f] (\lambda x.x)) a = (\lambda x.x) a \\
\quad &\rhd_{1\beta} [a/x]x = a
\end{align} $$

So $g$ applied $0$ times to $a$ returns $a$.

Now try to do the same with $1$.

$$ \begin{align} 1 ~ g ~ a &= (\lambda fx. f~x)~g~a\\
\quad &\rhd_{1\beta} ([g/f] (\lambda x.f~x)) a = (\lambda x.g~x) a \\
\quad &\rhd_{1\beta} [a/x]g~x = g ~ a
\end{align} $$

So $g$ applied $1$ time to $a$ is indeed $g(a)$.

Your problem is $4 ~ g ~ a$, where $g$ is $S$ and $a$ is $Z$.

$$ \begin{align}
S &= \lambda r.\text{“ring the small bell (ding) and apply r”}\\
Z &= \lambda r .\text{“ring the big bell (dong)}”
\end{align}
$$

Doing $1 ~ S ~ Z$ we already know that evaluates to $S(Z)$. And that translates to "print 'Ding' then apply $r$ ", where $r$ just prints 'Dong'. So it outputs 'Ding Dong'.


L closed under logspace reduction Given two languages $A$ and $B$ I have been asked to show that, if $B \in L$ and we have a logspace reduction $f$ from $A$ to $B$ then $A \in L$.

I read the proof that $L$ is closed under logspace reductions in Arora-Barak's textbook. The idea of the proof is, if I'm not getting wrong, to simulate the Turing Machine $M_B$ that computes the solution to $B$, carefully recomputing the $i$-th output bit of $f$ whenever we need it (so to save space).

My (probably naive) question is: since we are only interested in remaining within $L$, why can't we just compute the output of $f$ and store it entirely on the work tape of $M_B$ (this should require only logarithmic space), maybe separating it from the rest of the work tape with a special symbol, and use it as input to $M_B$? Since $B \in L$ this should require just an additional logarithmic amount of space, so there shouldn't be any risk to exit from $L$…where am I getting wrong?

The output of $f$ doesn't have to be of logarithmic size. This is why there is something to show.

To give an example, the function $f(x) = x$ can be computed in constant space but its output length is linear.


How does this non-deterministic algorithm to find if a Hamiltonian path exists work? I have read of an algorithm that a non-deterministic Turing machine $N$ can run to determine whether a given graph $G$ has a Hamiltonian path from the start node $s$ to a certain node $n$:

Write a list of $x$ numbers $p_1, p_2, p_3 ... p_x$, where $x$ is the number of nodes in $G$. Each number in this list is non-deterministically selected to be from 1 to $x$.
Check for repetitions in this list. If a repetition exists, reject.
Check whether both $s = p_1$ and $n = p_x$. If either do not hold, reject.
For each $i \in [1, x - 1]$, check whether $(p_i, p_{i + 1})$ is an edge of $G$. If any are not, reject.
Accept.

I do not understand how this algorithm works. Specifically, in step 1, why am I making a list of random (potentially repeating) numbers from 1 to $x$ (What does this list have to do with the nodes of $G$?)?

Likewise, in step 4, why does $(p_i, p_{i + 1})$ represent a potential edge in $G$?

There's a couple of bits of information that are key to making this make sense:

Each $p_{i}$ should be a label for a vertex in $G$. Typically $p_{i} \in [1,x]$, but it's not compulsory that you have to label the vertices from 1 to $x$. So the first step is effectively producing a putative list of vertices that could be a path. The rest just checks that it is actually a path (a hence why $(p_{i},p_{i+1})$ could be an edge).
The list is not random. It is selected non-deterministically. This is most definitely not the same as randomly selected. Non-determinism is a special theoretical property where a non-deterministic machine can "guess" a correct answer if it exists, however correct also has a special meaning, in that it selects an answer that will lead to an accepting state if such an answer exists. This may not be the right answer, just one that will make the Turing Machine say Yes - so we still have to check it.

So the algorithm guesses really cleverly a list (in fact an ordering) of all the vertices of the graph, and then checks that it actually makes a Hamiltonian Path from $s$ to $n$.


Decidability of languages $L_1$ is a recursively enumerable language over some alphabet
  $\Sigma$. An algorithm effectively enumerates its words as $w_1, w_2, ...$.  $L_2$ is another language over $\Sigma \cup \{\#\}$ as
  $\{w_i\#w_j : w_i, w_j \in L_1, i < j\}$ Consider the following
  assertions.

  $L_1$ is recursive implies $L_2$ is recursive
  $L_2$ is recursive implies $L_1$ is recursive

  Which statements is/are true?

I reasoned both the statements to be true.

Statement 1 is true. $L_1$ is recursive means it can lexicographically enumerate its strings. The membership question for $L_2$ can be easily settled using the decider and lexicographic enumerator of $L_1$.

Statement 2 is true. The algorithm which decides $L_2$ can be modified to accept if the input string matches either $w_i$ or $w_j$. This settles the membership question for $L_1$.

The given solution to this question however says that statement 2 is false. Could you let me know if my reasoning has gone wrong someplace?

You seem to be right. But as Raphael says, be careful.

Statement 1. Note that the $L_2$ is defined using the enumerating algorithm $\cal E$ for $L_1$, not by $L_1$ itself. To decide whether $u\#v \in L_2$, decide whether both $u,v$ in $L$, and if confirmed run the enumerator $\cal E$ and see whether $u$ is output before $v$. As we know both strings are in $L_1$ this will terminate.

Statement 2. If $L_1$ is finite, it is recursive, so we assume $L_1$ is infinite. Run $\cal E$ and wait for first word $w_1$. Now a decider for $L_2$ can be turned into one for $L_1$ as follows. To test $u\in L_1$ first check whether $u=w_1$, and then check $w_1\#u \in L_2$. This is then equivalent to $u\in L_1$ as we do not have to worry about the $i<j$ requirement, which is now true by construction.

I am not even certain we need to know $w_1$ by running $\cal E$: we only want to verify there exists a decider, not whether one can be effectively constructed. That seems impossible.

(edit) Just to note that Raphael has posted a more explicit "implementation" of these suggestions, which avoids possible ambiguities.


Run-time analysis of distributed network decomposition algorithm I'm trying to understand the run-time analysis in the article [1].

The authors define the following notation: $g(n) = \hat O(f(n))$ if $g(n) = O(f(n)^{O(1)})$. In the run-time analysis of their algorithm, they find that
$$T(l) \leq \hat O(p\log n)10^{\log_{p/2} l} \equiv f(l,p)$$
where $n$ is the number of nodes in the network, $l$ is the number of nodes in the input to the (recursive) algorithm and $p$ is a parameter.

Then they claim that the minimum of $f(n,p)$ is attained when $p=2^{\Theta(\sqrt{\log n})} = \hat O(n^{\epsilon(n)})$ with $\epsilon(n) = \frac 1{\sqrt{\log n}}$. This is the part that I don't understand. How do you minimize $f(n,p)$?

On the Complexity of Distributed Network Decomposition by A. Panconesi and A. Srinivasan (1996)

Calculus: any local minimum of the function $f(x)$ must be a point $x$ that satisfies $f'(x)=0$, where $f'(x)$ is the first derivative of $f(x)$.  So, take the derivative, set it to zero, and find all solutions.  Each solution is a candidate for the minimum.  You then need to check each candidate to see which makes $f(x)$ smallest.  You'll also need to check the "endpoints", e.g., the smallest and largest possible value for $x$ need to be added as candidates.

You can do the same for functions of two variables, and for asymptotics.