Determining key from plaintext and ciphertext (Vigenère) I was wondering why mathematically we can know the key in the Vigenère cipher if we know in advance a message and its encryption.

A Vigenère cypher on an alphabet of size $M$, which we identify with the integers modulo $M$, works as follows.

The key is an arbitrary word, $k_0 \ldots k_{\ell-1}$.

Given a plaintext $p_0 \ldots p_{n-1}$, the ciphertext $c_0 \ldots c_{n-1}$ is given by
$$
c_i = p_i + k_{i \bmod \ell} \bmod M.
$$
For example, suppose that we are trying to encipher decimal digits, and use as key the word 2019. If we want to encrypt the plaintext 18446744073709551616, then we form the following table:

plain  18446744073709551616
key    20192019201920192019
cipher 38538753274629643625

(In this case $n$ was divisible by $\ell$, but that need not be the case.)

In this table, the key repeats enough times, and each digit of the cipher is just the sum of the digits above it, throwing away the carry (for example, from 4 and 9 we get 3 rather than 13).

To decipher a ciphertext $c_0 \ldots c_{n-1}$, we simply reverse the process:
$$
p_i = c_i - k_{i \bmod \ell} \bmod M.
$$
In the table above, given the cipher and the key, we just need to subtract the key from the cipher, borrowing if necessary (so 3-9=4 since 13-9=4).

Similarly, given a plaintext/ciphertext pair, we can recover the key in the sense of constructing the sequence
$$
k_i = c_i - p_i \bmod M.
$$
This recovers the key up to its length $\ell$, which need not be known in advance.

In the table above, given the ciphertext and the plaintext, we subtract the latter from the former to obtain

201920192019201920192019

Out of which we can guess that the key is 2019.


DP tiling a 2xN tile with L shaped tiles and 2x1 tiles? https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php

The second question in the above link requires us to fill an 2xN grid with tiles of dimension 2x1 and an L shaped tile.

Question 1) In the recursive formula for g(n):

g(n) = f(n-1) + h(n-1)

Why didn't we include the case that we can also put a 2x1 tile horizontally on the top row. Something like -

g(n) = f(n-1) + h(n-1) + x(n-3)

where f(n) = f(n-1) + f(n-2) + g(n-2) + h(n-2) still holds.

Basically, are we not looking into the cases how we can start tiling from the state g(n) ? ither we add an L-shaped tile, and look at f(n-1), or we add a 2x1 tile in the bottom layer and look at h(n-1), or add a 2x1 tile in the top layer and look at x(n-3) ?

Question 2) It seems like while writing the recursion, we should only deal with cases that we have already named, i.e. only moving from state g(n) to h(n-1) or moving from state g(n) to f(n-1) ? Is it true, that when once we have decided which states to deal with, we only consider those states?

Q1. Of course you can consider a third variable in the recursion, but that would not simplify the analysis. In fact from the case where you put the single horizontal domino, the next step would automatically put the second horizontal one below it. So the given recursion takes a little shortcut.

Q2. That is precisely the point. We have to make sure the analysis steps from existing state to existing state, in a kind of unique way. If we overlook a state we miss possibilities. But here we easily see how the states are related, and how we step from one to another.


Differences and relations between high-performance/throughput computing and parallel computing? I wonder if high-performance computing and parallel computing always mean the same?
If not,

what are the differences and relations between  them?
what are some examples of high-performance computing that are not parallel computing?
what are some examples of parallel computing that are not high-performance computing?

Are high-throughput computing and high-performance computing the same concept?

As noted by @JukkaSuomela, you can do parallel computing on low-end resources such as your laptop and even on your mobile phone (if they are equipped with a multicore processor). However, HPC (High Performance Computing) is, roughly stated, parallel computing on high-end resources, such as small to medium sized clusters (ten to hundreds of nodes) up to supercomputers (thousands of nodes) costing millions of dollars. Therefore, the difference is mainly in the hardware used.

Finally, HTC (High Throughput Computing) refers to executing the maximum number of tasks (or jobs if you prefer) per time unit. A classical example of HTC computation is the so called parameter sweep, in which you must run the same executable, but varying in each execution a set of parameters (thus the sweep spans the whole parameter space).


How to eliminate ambiguity of the follwing CFG? Consider the following CFG:

$S\to AED | F \\
A \to Aa  | a\\
B \to Bb  | b\\
C \to Cc | c\\
D \to Dd  | d\\
E \to bEc | bc\\
F \to aFd | BC$

The CFG produces $a^*bbb...ccc...d^*$ (equal number of b,c) and $aaa...b^*c^*ddd...$ (equal number of a,d)

There is ambiguity since $abbccd$ can be derived respectively by $S\to AED$ and $S \to F$.
I try to rewrite the production rule like:
$$S\to AED\\E\to BC$$ But my CFG produces $a^*b^*c^*d^*$ which is different from original. Could anyone give me some tips?

Basically you have $L = L_1 \cup L_2$ where $L_1 \cap L_2 \ne \emptyset$. So naively writing the two productions:

$$L \to L_1 \\
L \to L_2
$$
will create an ambiguity. What's needed is to create $Ḷ_1' = L_1 - L_2$ in order to use the CFG
$$L \to L_1' \\
L \to L_2
$$
This produces the same language, resolving the ambiguities in favour of $L_2$.

Context-free languages are not closed under set difference, so this is not a general solution. But in this particular case there is no problem.

Suppose we start with the two languages $L_1 = \{ a^ib^jc^kd^i \}$ and $L_2 = \{ a^ib^jc^jd^k \}$, which are not disjoint since $\{a^ib^jc^jd^i\}$ is a subset of both.

So we define
$$Ḷ_1' = L_1 - L_2 = \{ a^ib^jc^kd^i \mid j \ne k\}$$
and are pleased to observe that it is context-free:

$$\begin{align}L_1' &\to E \mid a \; L_1'\; d\\
E &\to B \mid C \mid b \; E \;c\\
B &\to b \mid B b \\
C &\to c \mid C c
\end{align}$$

Meanwhile, $L_2$ is simply

$$\begin{align}L_2 &\to A\; F\; D \\
F &\to \lambda \mid b\;F\;c \\
A &\to \lambda \mid A a \\
D &\to \lambda \mid D d
\end{align}$$


Show that the Kleene star of any unary language is regular An exercise asks me to show that the Kleene star of any unary language $L$ is regular. $E$ is the alphabet, $E = \{ 1 \}$

Here's my reasoning :

$L$ is regular $\implies$ $L^*$ is regular (closure property)
$L$ is not regular

$L$ contains the word of length 1 $\implies$ $L^* = E^* \cup \{\epsilon\}$ $\implies$ $L^*$ is regular (since $E^*$ is regular, and the union of two regular languages is regular)
$L$ does not contain the word of length 1 -> ... ?

This is where I'm stuck. I don't know what to do if $L$ does not contain the word of length 1. I do not think that there exists a relation between $L^*$ and $(L \text{ complement})^*$.

Does anyone have any idea to continue this proof ? Thank you.

Let $p$ be the $\gcd$ of the lengths of all the words in $L$.
We claim that there exists $N$ such that for all $n>N$, $1^n\in L$ iff $p|n$.

Observe that one direction is trivial: $p|n$ for every $1^n\in L$ by definition.

The converse is less trivial, you can find good guidelines in the answers here

Given this claim, you can write $L^*$ as the union of the relevant words up to length $N$, and then $1^{pi}$ for all large enough $i$.


Are there more easy SAT Problems? Apart from $2SAT$, what versions of SAT problem is complete for the class NL?
Is there dynamic programming algorithm to solve the $2SAT$ Problem?

(1) is hard to answer unless you clarify what you mean by "versions of SAT problem."  If we limit ourselves to the classes listed in Schaefer's "The Complexity of Satisfiability Problems", the only nontrivial class known to be in NL is 2-SAT.

As for question (2), 2-SAT is amenable to dynamic programming, as is SAT in general.  During the DPLL process each partial assignment produces a new subformula: the previous formula with false literals removed and all satisfied clauses deleted.  As subformulas are determined to be unsatisfiable, they can be memoized in a canonical form.  If a known unsatisfiable subformula is encountered again during the DPLL search, a table lookup can identify it and the search can immediately backtrack.  For SAT instances derived from problems with many symmetries (and therefore many identical subformulas) the time savings can be substantial.


Why is self-information defined the way it is? The self-information of an event of probability $p_x$ is defined as $I(p_x)=-\log_2(p_x)$.¹

I fully understand this for equiprobable events of the form $p_x = \frac{1}{2^k}$.
In that case, we want to encode $2^k$ events so we need $\log_2(2^k)=k$ bits.
So $I(p_x)$ should be $\log_2(\frac{1}{p_x}) = -\log_2(p_x)$

However I am confused about the generalization to events of different probabilities and probabilities where $p_x \neq \frac{1}{2^k}$.
Then, I am wondering why $\log$ is a good choice.

I've never come farther as to such tutorials:
http://www.i-programmer.info/babbages-bag/213-information-theory.html
But as I read it they just think about what they want, namely a function $I$ with $I(xy)=I(x)+I(y)$ and then find that $-\log_2(p_x)$ satisfies all their needs. But is $\log$ the only choice they have? $I(x)=0$ works too! What are the exact requirements that we need? And why do we finally choose $I(p_x)=-\log_2(p_x)$?

¹I know $2$ is just the special case for bits, chosen for simplicity.

Though it is more common to discuss axiomatic derivation of the expectaion of $I(\cdot)$, that it, the entropy function (to which, several sets of axioms exist, see here), for the self information $I(\cdot)$, we usually care about the following properties (as defined by Shannon):

If the event happens with certainty, there is no information in it. Thus, if $p=1$, $I(p)=0$
Furthermore, $I(p)$ must be decreasing with $p$: the more likely the event is, the less information it gives us (or alternatively, the more surprising the event is, the more information its occurrence contains)
As you mentioned, we want that the information of two independent events will add up: $I(p_xp_y)=I(p_x)+I(p_y)$. The event of both $X$ and $Y$ occurring has probability $p_x\cdot p_y$ if independent.

These axioms lead to $I(p) =\log \frac1p$, up to a normalization (e.g., choosing the basis of the logarithm).


Distance transform with variable "impedance" The distance transform gives the distance of each pixel in a mask to the nearest zero.
E.g. lets take the Taxicab distance transform:
input       distance
1 1 0       2 1 0
1 1 1   ->  3 2 1
1 1 0       2 1 0

I'm looking for a generalized distance transform where each each element in the mask also has a "weight" or "impedance" quantifying "how much it costs to step into this square".  Weight would be undefined for zeros.
input     weight      distance
1 1 0     0 2 X        2 2 0
1 1 1  ,  3 2 3   ->   4 2 3
1 1 0     1 0 X        1 0 0

My questions are:

Is there a name for this transform?
Can it be done in O(N) like the traditional distance transform?
Is there a nice way to generalize this to euclidian distance?

I don't know whether there is a name for the transform you want but it can be computed in time $\tilde{O}(N)$ where $N$ is the number of entries of the matrix, assuming that the weights are non-negative.
Let the dimensions of the input matrices be $n$ and $m$. Call $A$, $W$, and $D$ the matrix with the pixel data, the weights, and the distances in output, respectively. Assume for simplicity that $W[i,j]=0$ whenever $A[i,j]=0$.
Create a directed graph $G = (V,E)$  where $V = \{s\} \cup \{1, \dots, n\} \times \{1, \dots, m\}$ and $E$ contains all edges $(s, (i,j) )$ for which $A[i, j]=0$ and
and edge $( (i,j), (i',j') )$ with weight $W[i',j']$ for each pair of vertices $(i,j)$ and $(i', j')$ that satisfy $|i-i'|+|j-j'|=1$.
The distance $d(i,j)$ from $s$ to $(i,j)$ in $G$ is exactly the distance you are looking for, i.e., $D[i,j] = d(i,j)$.
To compute all values $d(i,j)$ it suffices to run any single-source shortest-path algorithm from $s$ on $G$. Using Dijkstra's algorithm the time required is $O(|E| + |V| \log |V|) = O(N \log N)$.
Faster algorithms might be possible if you have additional assumptions about the weights. For example, if they are bounded by a constant then $O(N)$ time suffices.


How do you create a sentential form in a given grammar? I am given the following grammar:
$$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$
I need to decide whether $aBaabda$ can be produced in the given grammar.
I am unsure how the grammar can actually be read. For example, under what circumstances can you read $abT$ in $S$? Can you skip past $aBS$ and go to $abT$ or $a$?
I understand that deciding whether $aBaabda$ can be produced is a theoretical question, so you can theoretically create anything as long as its within the bounds/rules of a language. But I don't fully understand the rules of producing a sentential form.
And on not understanding rules fully: can you stop reading input on a non-terminal? It's name, of course, implies not. For example, without creating a derivation tree can you tell that something like $aaaabdaaaaBS$ or $aabdaB$ can't be made because it ends in a non-terminal? Except, writing this I realised that a non-terminal such as $B$ has ϵ, so that implies you can end on $B$, right?
Or can you end simply when you have matched a sentential form? For example, if you create a derivation tree and have a node for $S$, do you have to carry on reading or can you simply end?

If you know how to decide whether a word belongs to the language generated by a grammar, then you can extend this to sentential forms, in the following way. For each nonterminal $A$, add a new terminal $\mathbf{A}$. Add rules $A \to \mathbf{A}$. Given a sentential form, replace each nonterminal $A$ with the terminal $\mathbf{A}$. Now ask whether the resulting word belongs to the language generated by the augmented grammar.
As an example, your grammar turns to
\begin{align}
S &\to aBS \mid abT \mid a \mid \mathbf{S} \\
T &\to d \mid dT \mid \mathbf{T} \\
B &\to da \mid \epsilon \mid S \mid \mathbf{B}
\end{align}
The original grammar generates $aBaabda$ iff the augmented grammar generates $a\mathbf{B}aabda$.


Doubt with a problem of grown functions and recursion tree I'm confused to conclude the recursion tree method a guess for the next recurrence:
$$T(n)=3T\left (\left\lfloor \frac{n}{2}\right \rfloor\right) +n$$
I write some costs for the levels of tree, you can see, but I'm confusing in the final guess. I know for the master theorem that the answer for the guess is like that
$$\Theta(n^{\log_2 3}) $$ but in the steps by tree and I don't belive, you can see my error (?). How can I finished or know the outcome for this method to calculate $T(n)$?
thanks,

And the final conclusion is (?)
$$=2 n^{\log_2 3}+\Theta(n^{\log_2 3})\leq cn^{\log_2 3} \rightarrow \ \ T(n)\in\Theta(n^{\log_2 3})$$ with $c=3$ ?

Instead of having logarithms in the working, I'll substitute $n=2^m$:
$$
T(n)
= n\sum_{i=0}^{m} \left(\frac{3}{2}\right)^i
= n \frac{\left(\frac{3}{2}\right)^{m+1}-1}{\frac{3}{2}-1}
= 2n \left(\left(\frac{3}{2}\right)^{m+1}-1\right)
= 2n \left(\frac{3}{2}\right)^{m+1}-2n
$$
I believe the previous step is where you didn't expand the $2n$ into the first term. I am also not making any guess of what the master theorem or order of complexity is. Guesses should not be necessary anyways, since we just assume $T(1) \in \Theta(1)$.

Simplifying by keeping only the first term, and removing constants:

$$T(n) \in \Theta(n 1.5^{\log{n}})$$

Then, with some rearranging:

$$n 1.5^{\log_2{n}} = 2^{\log_2{n}}1.5^{\log_2{n}} = 3^{\log_2{n}}=2^{\log_2{3}\log_2{n}}=n^{\log_2{3}}$$

Thus:

$$T(n) \in \Theta(n^{\log_2{3}})$$


Why DCFL is not closed under kleene star? I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example

The language $\{a^nb^nc^k \mid n,k \ge 1\} \cup \{a^nb^kc^n \mid n,k \ge 1\}$ I believe is a standard example of a non-deterministic context-free language. At least intuitively it is clear that we can push the $a$'s, but we do not know when to pop (compare with $b$'s or with $c$'s?)

The language $L = \{ a^nb^nc^k \mid n,k \ge 1\} \cup \{d\;a^nb^kc^n \mid n,k \ge 1\}$ however, is deterministic. The $d$ prefix gives away which part we are in.

Now consider $(\{d\} \cup L)^*$.


Find a CFG for $\{a^ib^jc^k \mid i,j,k\ge0 , \text{if } j=1 \text{ then } i=k\}$ I've tried but I can't figure out any solution. Is there any hint for me to solve the question?

$ S =>S_1 \mid S_2 \mid S_3 $

$ S_1 =>AC  $

$ S_2 => aS_2c  \mid b $

$ S_3 => AbbBC $

$ A =>aA \mid epsilon  $

$ B =>bB \mid epsilon  $

$ C =>cC \mid epsilon  $


Dynamic programming: Maximize total value I was trying to solve this problem using dynamic programming.
We have $n$ objects in a row where each object has a value represented with a positive number.
This is encoded with an array $V[1], . . . , V[n]$ where $V [1]$ is the value of the first object in the row,
$V [2]$ is the value of the second object in the row and so on. We want to select a set $I \subseteq \{1, . . . , n\}$
of objects in such a way that the sum of its values, $\sum\limits_{i\in I} V [i]$, is as large as possible. However,
we cannot select objects that occupy consecutive positions in the row. That is, if we select object
$i$, then we cannot select object $i − 1$ nor object $i + 1$. For example, if $V = (6, 4, 3, 7, 3)$ then the
best option would be to select the first object (with value $6$) and the fourth object (with value
$7$). It is easy to see that any other option would have smaller total value.
We want a dynamic programming algorithm that, given as input array $V$ , computes the value
of the set with highest value. Note that, in order to simplify matters, we do not ask that the
algorithm returns the set, only its total value.
The probleem comes when it says "we cannot select object $i − 1$ nor object $ i + 1$". For $i-1$, the recursive case should be Optimal$(j-2)$+Value$(j)$, but no idea about $i+1$.

For $k \in [\![1, n]\!]$, you can define $f(k)$ as the maximum value reachable using objects $1$, $2$, …, $k$, without two consecutives objects.
Now the key to the dynamic programming implementation is to see that:
$\forall k \in [\![3, n]\!], f(k) = \max(f(k-1), f(k-2) + V[k])$
The reason is that to compute $f(k)$, you can either keep the $k$-th object or not. If you keep it, then you cannot keep the $k-1$-th object.
Finally, you want to compute $f(n)$.


What does the set {n | n is an integer and n = n + 1} represent? I am reading Michael Sipser's book Introduction to the Theory of Computation, which mentions the set $$S = \{ n \mid \text{$n$ is an integer and $n = n + 1$}\}.$$ This  doesn't make any sense to me.
I would understand if $n$ were equal to infinity or something, so it probably wouldn't matter if we added $1$ to it.
Am I understanding it correctly?
Or is this just an empty set?

But infinity isn't an integer. Since there is no integer $n$ such that $n=n+1$, you're right that the set is empty.


Understanding compression/encoding in linear time I'm reading the paper N. J. Larsson, A. Moffat: Offline Dictionary-Based Compression, which describes a compression algorithm that, if I understand it correctly, is quite similar to Byte pair encoding.

Given a string $S$ of length $n$, I'm trying to understand how one can compress it in linear, $\mathcal O (n)$, time with this compression method. How exactly is this done? I've read the paper, but I still don't understand how they achieve linear time, so maybe I would understand it explained in a different way.

My first confusion arises in the first step in the algorithm, where we find the most common pair, e.g. in abcababcabc the most common pair ab would be replaced by a new symbol, say XcXXcXc. I don't understand how we can find the most common pair quickly enough. My naive approach would be to look first at the first pair ab and then count the number of occurrences, then look at the next pair bc and count the number of occurrences, etc. However this would already give $\mathcal O (n^2)$ just for finding the most common pair once.

Next, even if I understood how to find the most common pair in $\mathcal O(n)$ time. My next problem is that, don't we have to find the most common pair up to $\mathcal O(n)$ times? And hence this would give a total time of $\mathcal O(n^2)$?

I have checked the code, reread the paper and it seems that algorithm is not performing in $\mathcal O(n)$ in the way you have described.
The recursive calls of finding pairs works in $\mathcal O(n \log n)$ divided by constant if you wish to pack it to the end. In fact the structure underneath keeps pointers to the first occurence of pair, splits the queue of pairs by occurences to make it efficient, but still loglinear. On the other hand by analysing the code written by Ph.D. student of the author I have discovered several tricks - the length of pairs (the original name) is given as parameter (default is 2) and the recurrence is limited by parameter, which can discard further calls (default is about 5 levels), with ability to make only one pass or push to the end. The default code runs in $\mathcal O(n)$, but will not yield optimal compression. There is also switch to prefer memory, time or be neutral.

The paper and the code shows usage of hash-table, which runs only in expected constant time, but the function given works very well with characters. Also the code limits the input length by constant hardcoded.

Changing hashtable to suffix tree and rewritting the part of recurrence into bookkeepping partial pairs might yield better results - I am not sure if this is possible to make it $\mathcal O(n)$, this would be probably a different question.

There is also trick used to keep empty space from traversing - the start of empty block points to the first non-empty character, but this only speeds up traversing, still with loglinear time. The part responsible for this behaviour is replacing pairs by the new character every iteration - keeping only rewrite rules and operating on them would be faster, but still the access to check if new pairs were introduced would require to check rewrite rules against the new ones - in the case we build full binary tree with pairs at the leaves in such way that after replacing pair with new character and concating with the parent we got new pairs at the leaves up to the root - there are $n$ chatacters then $\frac{n}{2}$ pairs, then $\frac{n}{4}$, $\frac{n}{8}$, $\frac{n}{16}$... You see the pattern, there are $2n$ pairs, but according to algorithm description this yelds $\mathcal O(n\log n + n)$ time taking only input traversals.


Is a register machine built out of automata of some sort? I am looking at register machines like the Random Access Machine. Wikipedia says:

Random-access machine (RAM) – a counter machine with indirect addressing and, usually, an augmented instruction set. Instructions are in the finite state machine in the manner of the Harvard architecture.

Does this mean the instructions are somehow encoded as a finite automaton? Or how exactly is a register machine implemented (theoretically and practically, at a high level). Where do automata fit into the picture?
I am wondering because I realize automata are pretty limited in what they can do, and once you need to "parse" something but have access to an entire database of information at each step of the parse, and then the result of parsing is a complicated object graph, you are no longer dealing with automata (as far as I can tell). Automata are basically recognizers returning a yes or no answer, with very little access to "data" to make their transition decisions. But I like the idea of "state machine", where it transitions around state to state.
So I'm wondering what a so-called "state machine" with access to a large database to figure out how to make each transition might be called, and if this is what a register machine could/would be.
My understanding is that a complex register machine is closer to something like x86, where you have instructions and data. But it seems that you might somehow be able to encode these instructions as a state machine somehow. Is this true? What am I missing from this picture? Is a register machine compiled down to automata of some sort, or otherwise built out of automata, or if not, how is it different from automata?

I can only react to this as seen from the perspective of a theoretical computer scientist.
A finite state machine/automaton is, as you know, usually represented by a finite directed graph. The vertices of the graph repesent the states of the automaton, the edges are the instructions: in state $p$, upon reading symbol $a$, move to state $q$.
Next to this graph is the "machine interpretation". The machine has a control unit and an input tape. That control unit is represented by the finite graph.
From these finite state machines/automata we can build more complex automata by adding external memory. For instance the pushdown automaton. The external memory is a single stack. The edges/instructions of the finite state repesentation are now extended with tests and instructions of the external pushdown: test what is the topmost symbol $A$, pop $A$ and push a new sequence $\alpha$.
The register machine likewise is obtained by choosing another external memory type. That of registers. The machine has a finite, fixed, number of registers each holding a natural number. Each register can be tested for zero, incremented and decremented. The instructions of the register machine are added to the finite state control. So we get edges/instructions of the form: in state $p$ upon reading $a$, when register $i$ is nonempty, increment it by $1$ and move to state $q$. If we allow the register machine to read $\varepsilon$, that is compute without reading input, these machines are Turing complete (even with two registers).


Data types for storing arbitrarily much information I've heard that YouTube had a problem with the view count on Gangnam style since the number of views exceeded the variable byte size.

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

Yes, you can create bigger and bigger variables to store big integer. There are many libraries that provide that functionality. For example BigInteger in Java. The problem with using big integer is that it makes program slower as more instructions are required to perform operations such as addition. Moreover, using a bigger representation will consumes more memory.


How can I create a language using set operation to prove a language is not regular? My goal is to show, that a given language is not a regular one by using the Properties of Regular Languages.

The language is $  A \triangleq\left\{w \in \Sigma^{*} \mid |\left.w\right|_{b} \neq|w|_{c} \wedge|w|>0\right\}  $ with $  \Sigma \triangleq\{a, b, c\}  $

My idea is to use this clearly non regular language (which is given in the task, so I can/should use it) $  \left\{b^{n} c^{n} | n \in \mathbb{N}\right\}  $ to prove $A$ is also no regular language.

Could the following work?

$(A\cap L(b^*c^*)) \cdot \mathrm{L}(\boldsymbol{\epsilon}) = \left\{b^{n} c^{n} | n \in \mathbb{N}\right\}$

It looks like you are onto the right track. However, your notation is confusing me.

I would believe the following is what you are coming at.

$$\overline{(A\cap L(b^*c^*))} \cup \{\epsilon\} = \left\{b^{n} c^{n} \mid n \in \mathbb{N}\right\}$$
where $\overline S$ is the language of words not in $S$, a.k.a. the complement of $S$. Here are the facts that you will use.

$b^*c^*$ is a regular expression.
the intersection of two regular languages is regular.
the complement of a regular language is regular.
$\{\epsilon\}$ is a regular language.
the union of two regular languages is regular.
$\{b^{n} c^{n} \mid n \in \mathbb{N}\}$ is not regular.

I will leave the rest of reasoning to you.


Construct PDA for ${ \{0^m1^n0^{2n} | n>0\}}$ I have to construct PDA for ${ \{0^m1^n0^{2n} | n>0\}}$

So my idea is to (informally) not pushing anything into the stack while having 0s at first, then when automata start accepting 1s it should push X onto the stack twice on every 1 and then when start accepting 0s it should pop X once every time until stack will be empty.

Is my understanding correct? If not, how should I proceed?

Yes, your understanding is correct. You may need a bit more mechanism to ensure there is at least one 1 after the initial 0's.


Minimizing Cost by minimizing delay There is a complete binary tree with its leaves as components of some system

The values from one node to another gives propagation time for a signal to propagate from one junction to another
For the signal to arrive at the leaves at exact same time starting from the root we must add delays to some wires.
The cost of adding delays into the system is given by the total amount of extra delay added to all the edges.

For example, one way to remove
clock skew from the tree to the right
would be to increase each edge so that it
has delay 6. This has cost 44.

Second way is to raise the costs
of all edges in the bottom layer to 6, all
edges in the middle layer to 5, and all
edges in the top layer to 4. This has cost
36.

One another way is calculate max delay and modify the bottom layer such that it has delay equal to maximum delay from the root

Is there any other way to get the best solution for minmizing cost to add delay??

You can do a lot better than a total delay of 36. In fact you can get a total delay of half that. The idea is to recursively adjust the delays from bottom up.

In your example, I'll count the edges in the bottom level starting at the left at what I'll denote by edge 1, then edge 2, and so on up to the rightmost edge at the bottom level, namely edge 8.

At the start, the component delays, reading from the left are:

  8, 11, 8, 12, 5, 5, 7, 10

In order to make the leftmost subtree at the bottom level have the same delays, add 3 to edge 1. The next subtree after that can be made to have the same delays by adding 4 to edge 3. The subtree after that needs no adjustments, and the final subtree will be adjusted by adding a delay of 3 to edge 7.

After the first adjustments, the component delays are now

  11, 11, 12, 12, 5, 5, 10, 10

Now pass up to the second level, where we'll have 2 subtrees. Label the second-level edges as we did, from 1 to 4. The leftmost subtree can be made to have the same times by adding 1 to edge 1, and the rightmost subtree can be similarly adjusted by adding 5 to edge 3.

After the second adjustments the delays are

  12, 12, 12, 12, 10, 10, 10, 10

Finally, pass to the top level, where we'll have a single tree. By adding 2 to the rightmost edge, both its left and right subtrees will have the same delays, so all the leaves will be in sync.

So finally, the component delays are

  12, 12, 12, 12, 12, 12, 12, 12

We added delays of 3, 4, 0, and 3 to the bottom level, 1, and 5 to the second level and 2 to the top level, for a total added delay of 18.

It's only slightly difficult to turn this into what's essentially a recursive depth-first traversal of the tree. Now all you have to do is convince yourself that this gives the minimum amount of added delay.


Finding the minterm expression of F + G I have a question that asks me to find the minterm expression of two functions added together. The two functions in this case are

F = m(0,4,5,6)

G = m(0,3,6,7)

At the moment my reasoning is that the minterm expression of F + G would be the combined minterms of each function, taking out any repetition. So the result would be:

H = m(0,3,4,5,6,7)

but I feel the problem cant be that simple, this obviously isn't the correct solution. Would finding the solution require me to break up the minterm expressions of each function back into their variable, then add them together and simplify? Thank you for any input

Here is my interpretation of your notation. The function $F = m(0,4,5,6)$ is in fact
$$ F = (x \land y \land z) \lor (\bar{x} \land y \land z) \lor (\bar{x} \land y \land \bar{z}) \lor (\bar{x} \land \bar{y} \land z). $$
(Perhaps positive and negative literals are switched, and possibly I am reading the bits in reverse order.)

The notation $F+G$ just means $F \lor G$. In that case, $m(S) + m(T) = m(S \cup T)$. Similarly, if $FG$ means $F \land G$, then $m(S)m(T) = m(S \cap T)$. Finally, the negation of $m(S)$ is $m(\bar{S})$. Basically, $m(S)$ is the function which is true on the truth assignments in $S$, so we can identify it with $S$. Boolean operations on functions correspond to boolean operations on sets.


ARM STM instruction: page fault problem with MMIO The ARM STM instruction is described here in the ARM manual.
This instruction writes all or a subset of registers at memory locations starting from a base memory address.
The manual does not impose any restriction on the start address. So, can the start address be such that some/all of the writes end up in MMIO address?
If so, there can be a problematic scenario where a page fault happens in the execution of the STM instruction:
Suppose the base memory address is b and 10 registers are to be written. The range b to b+5 belongs one page and the range b+6 - b+9 belongs to the next page. Suppose the virtual first page (where b belongs) is mapped to a physical page that corresponds to MMIO. Suppose the next virtual page is mapped to DRAM. Suppose that whe the STM execution tries to do the 7th write, to the address b+6, a page fault happens because the DRAM page is swapped out. The page fault handler loads that DRAM page and restarts the STM instruction. The first 6 writes (b to b+5) will be done again. Because these writes go to MMIO which can be mapped to devices, this operation may not be idempotent, e.g. it can launch some missiles twice!. The first 6 writes should not be repeated.
How do page handlers handle this problem, if they handle it at all?

The STM instruction is just an example. The same problem happens with any instruction that does multiple writes that span different virtual pages.

What if the STM instruction were executed speculatively, and an instruction ahead of it faults? Or it's behind a mispredicted branch?

I can't speak for all ARM variants (things have probably changed over time), but the semantics of any instruction must be that if the instruction causes a fault, it's as if the instruction didn't happen.

What modern ARM cores probably do is use the store buffer. All stores (apart from TCM, which is by definition not MMIO) go through the store buffer. The only difference is in how the store buffer is flushed.

Presumably the store buffer has enough entries to satisfy a STM instruction. If the instruction (or an instruction ahead of it) faults, the relevant entries in the store buffer are purged. When the instruction retires (i.e. when it reaches the head of the reorder buffer), the stores are released for writing.


Sampling from specific random distribution on sets I have a random distribution on sets in mind, that has three parameters: $n, w, k$. The goal is to sample sets of $k$ integers from $[0, n)$ (without replacement) such that the elements within each set fit in a subrange of length $w$. That is, an outcome set $S$ must have properties:

$S \subset \mathbb{N_0} \; \wedge\;  |S| = k$
$0\leq \min(S) \leq \max(S) < n$
$\max(S) - \min(S) < w$

You can assume that $k \leq w/2 < w \ll n$.
Now there are many possible distributions possible over these sets. But I'm interested in those that have as property
$$\forall x:P[x \in S] = \frac{k}{n}\;,$$
that is each integer in $[0, n)$ has an equal chance of being in a set when sampled (or as close as possible). Beyond the above requirements, it'd be ideal if the distribution is an maximum entropy one, but this isn't as important, and something close would be fine too. As a minimum bar I do think every valid set should have a non-zero chance of occurring.
Is there a practical way of sampling from a random distribution that matches the above requirements?
I've tried various methods, rejection sampling, first picking the smallest/largest elements, but so far everything has been really biased. The only method that works that I can think of is explicitly listing all  valid sets $S_i$, assigning a probability variable $p_i$ to each, and solving the linear system $$\sum_i p_i = 1 \quad\bigwedge\quad \forall_x:\frac{k}{n} - \delta \leq  \sum_{x \in S_i}  p_i \leq \frac{k}{n} + \delta,$$ minimizing $\delta$ first, $\epsilon $ second where $\epsilon = \max_i p_i - \min_i p_i$. However this is very much a 'brute force' approach, and is not feasible for larger $n, k, w$.

I have a suggestion for an algorithm that might get close to what you want:

Pick $m$ from the distribution $\mu$ (which I will describe below).

Choose $S$ uniformly at random from all sets containing exactly $k-1$ integers in $[m+1,\dots,\min(m+w,n))$.

Add $m$ to $S$.  Output $S$.

So, how do we pick the distribution $\mu$ to make this algorithm pretty good?  I'll describe how, using linear programming.
Let $\mu_i$ denote the probability of $i$ according to the distribution $\mu$.  Then, we have
$$\begin{align*}
\Pr[x \in S]
&= \sum_m \Pr[x \in S \mid m] \Pr[m]\\
&= \mu_x + \sum_{m=x-w+1}^{x-1} {k-1 \over \min(w-1,n-m-1)} \cdot \mu_m.
\end{align*}$$
Notice that this is linear in the $\mu_i$'s.  Now, let's treat the $\mu_i$'s as variables to be solved for.  Introduce the linear inequalities
$$\left| \Pr[x \in S] - {k \over n}\right| \le t,$$
where $t$ is another variable.  Also add the equality $\mu_1 + \dots + \mu_{n-k}=1$ and $\mu_{n-k+1}=\cdots=\mu_{n-1}=0$ and the inequalities $\mu_i > 0$ for all $i$.  We'll try to minimize $t$ subject to all of these inequalities.  These are linear inequalities in the variables $\mu_0,\dots,\mu_{n-w},t$, so you can find a solution in polynomial time using linear programming.  That gives you a distribution $\mu$ to use in the algorithm above.
This comes close to meeting your requirements.  It ensures the set $S$ output by the algorithm meets your conditions 1, 2, and 3.  It gets close to having $\Pr[x \in S] = k/n$; this is not exactly true, but it will be approximately true; and you can measure how large the error is when you solve the linear program, by inspecting the value of $t$.  Also, due to the inequality $\mu_i > 0$, every possible set has a non-zero probability of occurring.  Of course, this is only a heuristic, and it probably is not the maximum-entropy distribution, so you'll have to decide whether it is good enough for your needs.
You mention that you are dealing with a very large value of $n$.  Given that, an additional heuristic would be to assume that $\mu_i$ is constant for all $i \in [3w,n-4w)$.  Intuitively, the endpoints are the problem cases, and there is a loose symmetry among the middle values that makes it feel reasonable that they'll end up having about the same probability.  So, we can enforce the constraint $\mu_{3w} = \mu_{3w+1} = \cdots = \mu_{n-4w-1}$, by replacing $\mu_i$ with $\mu_{3w}$ for all $i \in [3w,n-4w)$.  Now there are only about $6w$ variables, namely, $\mu_1,\dots,\mu_{3w},\mu_{n-4w},\dots,\mu_{n-w}$ and $t$.
Note that it is easy to express $\Pr[x \in S]$ as a linear sum of the $\mu_i$ variables; this sum can be computed in $O(w)$ time.  So, we end up with a linear program in about $6w$ variables, so you can apply a LP solver, and the resulting system will have $O(w)$ variables and inequalities instead of $O(n)$ variables and inequalities, so the LP solver should be a lot faster.


Can any problem that runs in exponential time on a deterministic RAM be run in polynomial time on a non-deterministic RAM? If P is a program that can be run in exponential time on a deterministic RAM. Can P always be run in polynomial time on a non-deterministic RAM?

We don't know, but probably not.

You shouldn't equate nondeterministic polynomial computation with deterministic exponential computation. A problem being NP-complete does mean that we probably don't know anything better than an exponential deterministic algorithm for it; however, there are a great many exponential deterministic algorithms for which we don't know any nondeterministic polynomial algorithms (e.g., anything that's EXP-complete).

There's no particular reason to assume that EXP$\,=\,$NP. In particular, exponential-time algorithms are allowed to use an exponential amount of storage, but any computation path of a polynomial-time computation can only use a polynomial amount.


Generating words in given format i am looking for an algorithm that will generate all possible combinations of words from given dictionary that satisfy given format.

Let me explain what i mean with format:

For example, if the format is "abcd" means that we are looking for one word, length of the word must be 4 and because all the letters in format are different, all the letters in the word must be different.

The format "computer science" means:

1) We are looking for 2 words (one of length len("computer") = 8 and one of lenght len("science") = 7)

2) The first char of the first word must be the same as the second char and the sixth char in the second word
   (letter "c" in format)

3) The seventh char of the first word must be the same as the the forth and the last char in the second word (letter "e" in format)

Is it better to generate all the possible strings in given format and the look them up in the dictionary or somehow build strings using dictionary ?

edit:

My idea:

1) split big dictionary (100 millions of words) into smaller ones based on word length.

2) for first word get trough all the entries in particular dictionary and try to match first word, then continue with the next one, but with more restrictions.

Thank you for your help!

Alright,
I managed to solve this problem using Prolog.

First of all, I've converted wordlist.txt from:

word1
word2
...

Into wordlist.pl:

w(w,o,r,d,1).
w(w,o,r,d,2).

Then I've found Prolog function, that tells me if all the elements in the list are different:

alldif([]).
alldif([E|Es]) :-
   maplist(dif(E), Es),
   alldif(Es).

After that I have written Prolog function, that takes predefined format and finds all the possible words from dictionary, that meet given format:

g(Format, String):-
    list_to_set(Format, Uniques),
    alldif(Uniques),
    w(Format),
    atomic_list_concat(Format, '', Atom), atom_string(Atom, String).

Now I'm able to call:

g([A,B,C], String1), g([A,D,A], String2).

That generates me all possible combinations of String1 and string2 with following format:

"ABC ADA"


Weak and strong completeness What does a pseudo-polynomial algorithm tell us about the problem it solves? I don't see how running time improves if the algorithm is exponential in the input length and polynomial in the input value; so how do we explain this shift from exponential to polynomial?

As it is stated in "Computers and Intractability: a Guide to the Theory of NP-Completeness" A pseudo-polynomial-time algorithm will display 'exponential behavior' only when confronted with instances containing 'exponentially large' numbers, which might be rare for the applications we are interested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time algorithm.”

You can consider knapsack as a good example of weakly-Np Complete problem. In this case the complexity of the dynamic programming solution is $O(nW)$ which is well in most practical cases.

It is known that there is no pseudo-polynomial time algorithm for Strong NP-Complete problems (like Steiner Tree) unless P=NP.


Amortized analysis for dynamic array - how to come up with a potential function? I learned about amortized analysis and the potential method, I also
leaned an example of a binary counter which I think I understand well.

In the case of the binary counter I understand the choice of the potential
function - we are paying in advance for a transition from one to zero
that must be made in the future when  a bit changes from zero to one
so the potential function is how much I payed that I haven't used
already.

I got an exercise to find a potential function for a dynamic array
with only inserts. I understand why a dynamic array have an amortized
time of $O(1)$ on inserts - either the array have sufficient size
and there is a simple insert costs $O(1)$ or the array is of size
$k$ and it is full and in that case we spread the cost of the $O(k)$
is costs to insert the element with the last $k/2$ elements of the
array (the new elements), the amortized cost is somewhat of $O(k)/(k/2)=O(1)$.

However I can't come up with a potential function, I don't see a methodical
way of taking this understanding and making it formal with the potential
method.

I have found online a potential function $\Phi=2n-m$ where $n$ is
the number of current elements in the array and $m$ is the size of
the array, I do see a factor of $2$ maybe relating to the $2$ in
the $k/2$ above, but I can't manage to get to the above $\Phi$ myself.

I would appreciate help in understanding how to take my argument and
derive $\Phi$ from it

One method is guess-and-check.  We might guess that the potential function has the form $\Phi = \alpha n + \beta m$ for some constants $\alpha,\beta$, then try to work out a proof, and see what properties $\alpha,\beta$ need to have, and look for (solve for) a value of $\alpha,\beta$ that makes the proof work out.

Another way is to use intuition.  Intuitively, the idea is that some operations are slow; and other operations might be fast to complete but are going to make our life harder down the road (i.e., are going to make other operations take longer).  We can then look for a potential function that charges extra for operations that are fast right now but will make life harder down the road, and then use the accumulated charges to pay for the slow operations.  Intuition might help us identify which operations should increase the potential and which should decrease the potential, and then we can go from there to try to work out the specifics.


Max Weight Path in a Graph I know that this problem is a known NP-Complete problem, but I'm curious as to why a particular algorithm won't work. Given a graph $G = (V,E)$, and edge weights $w(e)$, why can we not create a new graph $G' = (V,E')$, and flip the sign of each edge weight, i.e set the weight of each edge $e' \in E'$ to $w(e') = 0-w(e)$ and use an algorithm such as Bellman-Ford to find the minimum weight path on this new graph. I understand that flipping the sign of the edges could create negative cycles, implying there is no shortest path in $G'$, but won't this imply that there is a positive cycle in $G$, meaning there is no longest path? Can someone give a counter-example of when this algorithm would fail?

There's a problem with terminology here.  A walk in a graph is a sequence $v_1\dots v_k$ of vertices such that $v_1v_2, v_2v_3, \dots, v_{k-1}v_k$ are edges. A path is a walk that doesn't repeat vertices.  So, a graph with a positive-weight cycle contains no longest walk (you can always walk around the cycle one more time to get a longer one) but it does contain a longest path (paths can't go all the way around cycles).

Algorithms such as Bellman–Ford actually compute shortest walks between vertices and use the fact that, as long as the graph has no negative cycles, the shortest walk is also the shortest path.  (Any walk that isn't a path must contain a cycle and, if all cycles have positive weight, then the walk without that cycle is shorter.) The graph your algorithm generates contains negative-weight cycles, so Bellman–Ford will fail: it can't use its "the shortest walk is also the shortest path" rule because there is no shortest walk.


Equivalent formulae with different CNF I was not able to find or come up with two formulae which are equivalent but have different CNF. All my ideas reduce to the same formula after applying transformations. The requirements are the following:

Give an example which shows that proving equivalence of two formulas by bringing them into conjunctive normal form is incomplete. By incompleteness, we mean that there are examples of formulas which are equivalent but their conjunctive normal form is not the same.

It depends on the algorithm for obtaining CNF of a formula.
A simple truth table-based method will always produce syntactically the same CNFs for equivalent formulas, since it in a sense just gives you the rows of the truth table for which the formula evaluates to false.

A trivial example of equivalent formulas, which are both in CNF:

$$A \wedge B$$
$$(A \vee B) \wedge (A \vee \neg B) \wedge (\neg A \vee B).$$

Non-uniqueness of CNF means that one can build an algorithm, which returns essentially different CNFs for equivalent formulas. For example, as a first step the conversion algorithm can check if a formula already in CNF and return it immediately.


A Shortest Path Strange Formulation, or new modeling? We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set  $ w(i,j)= + \infty $. For each vertex $i$ put $w(i,i)=0$. we want using Dynamic Programming to find shortest path between any two vertex in this graph. by using which of them following recursive relation $d[i,j,n]$ is equal to shortest path among vertexes $i$ and $j$?

$I)$
$d[i,j,k]=\begin{cases}w(i,j) & k=1\\ \min_{1 \leq r \leq n} \left\{ d[i,r,k-1] +w(r,j) \right\}& k>1 \end{cases}$

$II) d[i,j,k]=\begin{cases}w(i,j) & k=0\\ \min \left\{ {d[i,j,k-1],d[i,k,k-1]+d[k,j,k-1]}\right\}  & k>0 \end{cases}$

$III) d[i,j,k]=\begin{cases}w(i,j) & k=1\\ \min_{1 \leq r \leq n} \left\{ {d[i,r,\lfloor k/2\rfloor ]}+d[r,j, \lceil k/2\rceil ] \right\} & k>1 \end{cases}$

  This is an exam on 2011 that solution is wrote all of them. Who Can
  Help this confusing question better understood?

Solution I) is recursive definition where $k$ is number of links. This formulation comes from same as Bellman-Ford-Moore algorithm.

Solution II) is recursive definition where $k$ is an intermediate node. $d[i,j,k]$ is length of shortest path from $i$ to $j$ involving only $1..k$ as intermediate nodes. This formulation comes from Floyd Warshall algorithm.

Solution III) is recursive definition where $k$ is again number of links. I) and III) will give same value for $d[i,j,k]$. (See Shortest Paths)

Final solution will be $d[i,j,n]$ for every case.


Tackling overlearning neural network issue I'm trying to train a neural network using this sort of data (for a homework):
Number of Features : 42,
Target data : 0 or 1,
Number of Samples : 111 Individuals ( 69 Cases + 42 Controls )

However i'm facing an over-learning issue (the learning curve approaches the goal set, however the validation curve shows no improvement): the learning stops after less than 15 iterations because of a great number of validation fails: no improvement in the quality of validation tests.
I managed to have great results by using 444 (4*111) examples in my training as I repeated the initial data four times. but i'm not sure if this is clean.
In other words, is it alright to repeat existing examples to have more values for training ?

Thanks in advance.

Yes, it is alright to repeat training data, as long as each one is repeated an equal number of times: this does not violate assumptions.  That said, it smells to me like a kludge.  If you have no theoretical understanding of why the approach was failing without that adjustment, then just randomly tweaking things (like repeating points) in hopes that it will happen to succeed does not seem like the right approach.

Be careful that you don't do cross-validation on the result after repeating samples.  You need to separate the test set from the training set before repeating.  If you repeat samples, then do cross-validation, there is a high likelihood that most or all samples in the test set will also appear in the training set (due to the repetition) and thus you'll be over-fitting -- the cross-validation results won't be meaningful in that case.


Why does the state remain unchanged in the small-step operational semantics of a while loop? Usually I see that in the structural operational semantics representation for the while loop, the program state don't change:

$(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> then \>S; (while \> B \> do \>S) \> else \> SKIP, \sigma)$

For me, this not intuitive, if the state don't change (i.e. the status of the memory stays the same) then $B$ will continue to stay true and the program will never terminate.

Can anyone please explain why the state don't change in this rule?

The state can change in subsequent reduction steps because on the right hand side of

$$
   \langle while\ B\ do\ S, \sigma \rangle
\quad\rightarrow\quad
 \langle if\ B\ then\ ( {\color{red}{S}};\  while\ B\ do\ S )\ else\ skip, \sigma\rangle
$$

the $while$-loop is guarded (preceeded) by $S$. The computation of $S$ may change the state so that the condition $B$ can evaluate to $\mathsf{false}$.


What are the effects of the alphabet size on construct algorithms for suffix trees? For what size alphabet does it take longer to construct a suffix tree - for a really small alphabet size (because it has to go deep into the tree) or for a large alphabet size? Or is it dependent on the algorithm you use? If it is dependent, how does the alphabet size affect Ukkonen's algorithm?

A larger alphabet is usually a drawback. However there are algorithms that can deal with this as long as the alphabet size is $n^{O(1)}$.

Ukkonen's algorithm runs only in $O(n)$ if the alphabet size is a constant but it is $O(n \log n)$ without this assumption. However, there are alternatives. You can compute the suffix-array of a text in linear time with the DC-3 Algorithm. This is a super-cool fancy algorithm that can be implemented in 50 lines of readable C++ code - one of my all-time favorites. If you can compare two characters in constant time and the alphabet size is $n^{O(1)}$, then the DC3 algorithm runs in $O(n)$ time.

Notice that you can get the suffix tree out of the suffix array in $O(n)$ time, when you have the LCP-array. Basically, you compute the Cartesian tree of the LCP-array and use the suffix-array to label the nodes. The LCP-array can be also computed with the DC3-algorithm.


Is the language of words with as many a's in the first as b's in the second part context-free? Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language?

There is a book here that claims $L$ is not CF (without any elaboration), but I think we can construct a NPDA that accepts the language. My guess is we can construct the language with an NPDA where after reading some $a$ and $b$ and pushing $A$ for each $a$ into the stack, makes a guess to jump to a new state and consumes the pushed $A$ with each $b$.

Yes, the language is context-free.

Let $w$ be a word in $\{a,b\}^*$. Decompose it as $w = u v$ where $|u| = N_b(w)$.
$$ \begin{align}
  N_a(u) &= N_a(w) - N_a(v) && \text{because \(w = u v\)} \\
         &= N_a(w) - (|v| - N_b(v)) && \text{because \(v \in \{a,b\}^*\)} \\
         &= N_a(w) - |w| + |u| + N_b(v) && \text{because \(|v| = |w| - |u|\)} \\
         &= |u| - N_b(w) + N_b(v) = N_b(v) \\
\end{align} $$
Thus we can decompose any word in the desired form: $L = \{a,b\}^*$. Constructing a PDA is left as an exercise to the reader.

This still works if the language contains other letters, by the way, but you have to take a prefix of $w$ that contains $N_b(w)$ letters in $\{a,b\}$ and arbitrarily many other letters.

Another way to see this is to notice that if there is an $a$ in $u$ and a $b$ in $v$, then you can swap the two letters, which results in a word that has the same balance $N_a(u) - N_b(v)$. $L$ is the set of words whose balance is zero for some split position. Iterate this decomposition until it becomes impossible: either $u$ contains no $a$ or $v$ contains no $b$. If we choose the split position so that $|u| = N_b(w)$ and $|v| = N_a(w)$, then now $u$ contains all the $b$'s and $v$ contains all the $a$'s: $N_a(u) = 0$ and $N_b(v) = 0$, and in particular the balance is 0.


What is considered being proficient in a programming language? I am a college student looking to get into industry work soon and want to understand what employers consider 'proficient' when it comes to programming languages.  Right now, I understand that to mean that one can write a fully functional program without consulting any references.  However, is there a tangible project or projects that demonstrate proficiency with a language and its libraries?  Preferably projects that employers like to see in their candidates.  My portfolio is relatively weak right now so I want to build that up before I graduate.  Any recommendations are appreciated!

I wouldn't go with your definition:

that one can write a fully functional program without consulting any references

"Hello World" and Deep Neural Networks are both fully functional "programs". The complexity matters..

In the office nobody expects you to handle a program from beginning to end. Depending on the size of the office and their assembly line your assignments will vary a lot. For most of the time, you'll be implementing methods within a larger program.

It is a normal practice to use the documentation ("reference") even if you're on a senior position you're not supposed to remember everything by heart. Every developer I know spends at least  30 min on Stack Overflow every working day.

What is perhaps more valued is a solid foundation, understanding how the language works under the hood, ability to write clean readable code and be a team player.
Beyond a certain level of proficiency, it is not a criterion anymore because if you have a solid understanding of the language you can learn how to implement any complex algorithm or data structure in a reasonable amount of time.
You can never LEARN the whole language, you learn the Grammar...


Weighted probability using Huffman Tree I want to produce a value from a set, where each value has an associated weight.

Eg:

[(1, 4), (2, 3), (3, 3)]

should give me a 40% chance of picking 1, and a 30% chance of picking 2 or 3 respectively.

Using a cumulative sum table and binary searching on it yields the value I want in O(logN) where N is the number of values in the set.

I was thinking of another approach to this using a huffman tree (as described here) with the combined weights of its children stored on each node.

For the above case, the tree would look like

    (10)
   /    \
(1, 4)  (6)
       /   \
   (2, 3) (3, 3)

The algorithm for generate() would be something like:

Generate random number k in range [0, {value of root node})
Start at root node
If at a leaf node, return value
If k >= {value of left child}, go right else go left
Repeat from third step.

Now, in the case that the weights are about the same, this will take O(logN), similar to the binary search method.

However, if the weights increase in an exponential manner and the tree essentially becomes a list, the complexity becomes

$$
\sum\limits_{i=1}^N   k/2^k
$$

Which tends to 2.

I'm having some difficulty coming up with an expression for the average case for generate, but it definitely has an upper bound of O(logN) and a lower bound of O(1). Of course, worst case is O(N).

What's a good approach to figuring this out, and what are the possible pitfalls of this kind of an approach?

Given a distribution $\mu$ on a finite set, let us denote by $T(\mu)$ the average depth of a leaf in a Huffman tree of $\mu$ (depth is measured by the number of edges from root to leaf); we assume that no element has zero probability. Then
$$
H(\mu) \leq T(\mu) < H(\mu)+1,
$$
where $H(\mu) = \sum_i \mu_i \log_2 (1/\mu_i)$ is the entropy of $\mu$ (here $\mu_i$ is the probability of the $i$th element).

To prove this, let us start with Kraft's identity. In the statement below, a complete binary tree is one in which every internal node has exactly two children.

Kraft's identity. There is a complete binary tree whose leaf depths are the multiset $\{\ell_1,\ldots,\ell_n\}$ if and only if $\sum_{i=1}^n 2^{-\ell_i} = 1$.

Proof. Let us first show that the leaf depths satisfy Kraft's identity. The proof is by induction on $n$. If $n = 1$ then $\ell_1 = 0$, and indeed $2^{-\ell_1} = 1$. Otherwise, arbitrarily choose two sibling leaves, and remove them. If the original depth was $\ell$, this affects the multiset of depths by removing $\ell,\ell$ and adding $\ell-1$. The induction hypothesis shows that the new multiset satisfies Kraft's identity. Since $2^\ell + 2^\ell = 2^{\ell-1}$, the original multiset also does, completing the proof.

Let us now show that if a multiset $L$ satisfies Kraft's identity, then there is a complete tree whose leaf depths are $L$. Once again, the proof is by induction on $n = |L|$. If $n = 1$, then necessarily $L = \{0\}$, and the tree consisting of a single leaf works. Otherwise, let $\ell = \max L$. Notice that
$$
2^\ell = \sum_i 2^{\ell - \ell_i}.
$$
If $\ell_i = \ell$ then $2^{\ell - \ell_i} = 1$, and if $\ell_i < \ell$ then $2^{\ell - \ell_i}$ is even. Hence the number of copies of $\ell$ in $L$ is even, and in particular there are at least two such copies. Let us form $L'$ by removing two copies of $\ell$ and replacing them by a copy of $\ell-1$. Applying the induction hypothesis, we obtain a tree $T'$ whose leaf depths are $L'$. By construction, $T'$ has a leaf of depth $\ell-1$. Adding to it two children, we obtain a tree $T$ whose leaf depths are $L$, completing the proof. $\square$

We can now prove the inequalities on $T(\mu)$, starting with $T(\mu) \geq H(\mu)$.

Lower bound on $T(\mu)$. Consider any tree whose leaves are labeled by the support of $\mu$, and suppose that element $i$ is on a leaf at depth $\ell_i$. Let $\nu_i = 2^{-\ell_i}$. Kraft's identity shows that $\sum_i \nu_i = 1$. Since $\ell_i = \log_2(1/\nu_i)$, we have
$$
T(\mu) - H(\mu) = \sum_i \mu_i (\ell_i - \log_2 (1/\mu_i)) = \sum_i \mu_i \log_2 (\mu_i/\nu_i).
$$
The function $\log_2 (1/x)$ is convex, hence Jensen's inequality shows that
$$
\sum_i \mu_i \log_2 (\mu_i/\nu_i) =
\sum_i \mu_i \log_2 \frac{1}{\nu_i/\mu_i} \geq \log_2 \frac{1}{\sum_i \mu_i (\nu_i/\mu_i)} = 0,
$$
using $\sum_i \nu_i = 1$. We conclude that $T(\mu) \geq H(\mu)$. $\square$

The other direction uses Shannon–Fano coding.

Upper bound on $T(\mu)$. Let $\ell_i = \lceil \log_2 (1/\mu_i) \rceil$. Then
$$
\sum_i 2^{-\ell_i} \leq \sum_i 2^{-\log_2 (1/\mu_i)} = \sum_i \mu_i = 1.
$$
If $\sum_i 2^{-\ell_i} < 1$, let $\ell = \max_i \ell_i$. Notice that
$$
\sum_i 2^{\ell-\ell_i} < 2^\ell,
$$
where all summands are integral.
If we decrement one copy of $\ell$ to $\ell-1$ then we increase the left-hand side by $2^{\ell-(\ell-1)} - 2^{\ell-\ell} = 1$, so the left-hand side is still at most $2^\ell$. Hence after the update, we still have $\sum_i 2^{-\ell'_i} \leq 1$, where $\ell'_i$ are the new values. Continue doing so until the sum reaches 1; this must happen, since the decreasing process cannot continue forever (the depths keep decreasing while never dipping below zero). Denoting by $r_i$ the new values, Kraft's identity implies that there exists a tree whose leaf depths are the $r_i$. The average depth of a leaf in this tree is
$$
\sum_i \mu_i r_i \leq \sum_i \mu_i \ell_i < \sum_i \mu_i (\log_2 (1/\mu_i) + 1) = H(\mu) + 1.
$$
Huffman's algorithm will find a tree which is at least as good. $\square$

Finally, let me show that for every $\epsilon>0$ there are distributions $\mu$ for which $T(\mu) \geq H(\mu) + 1 - \epsilon$. Given $\delta>0$, consider the distribution $\mu$ on two elements with $\mu_1 = 1-\delta$ and $\mu_2 = \delta$. Clearly $T(\mu) = 1$, while $\lim_{\delta\to0} H(\mu) = 0$. Therefore we can find positive $\delta$ for which $H(\mu) \leq \epsilon$. For such $\mu$ we have $T(\mu) = 1 \geq H(\mu) + 1 - \epsilon$.

What happens if we force all probabilities to be small? Gallager, in his classic paper Variations on a theme by Huffman showed that even in this regime, there are distributions for which the gap is roughly $\log_2 [(2/e)\log_2 e] \approx 0.086$. Amazingly, this is attained by uniform distributions!


Is there any property about height of PDA? I'm trying to find a PDA for $L$ which modifies the stack height at most one.

$L=\{a^ib^i\mid i\geq 0\}$

I think there is no such PDA but how can I prove it?

My attempt is for a given string, find a relationship between stack height in PDA and  leftmost derivation in CFG then prove that there's no CFG which satisfies the condition using pumping lemma. But I couldn't find any relationship. Am I doing right way?

Any help appreciated.

If you could bound the stack height, say to some constant $c$, then it would have been possible to define an NFA for the task: Simply encode in the NFA states another $c$ values that represent the current values in the stack (by defining $\hat Q=Q\times\Sigma^c$. The rest i will leave to you)

This would contradict the non-regularity of this language, and therefore you cannot give such a bound.


Number of computations for multiplication I just read Marvin Minskys' "Form and Content in Computer Science" and found myself confused with the following paragraph:

  A startling discovery was made about multiplication itself in the
  thesis of S.A. Cook [3], which uses a result of A.L. Toom, as
  discussed in Knuth [4]. Consider the ordinary algorithm for
  multiplying decimal numbers: for two n-digit numbers this employs
  n-squared one-digit products. It is usually supposed that this is
  minimal. But suppose we write the numbers in two halves, so that the
  product is N = (#A+B)(#C+D), where # stands for multiplying by 10 subscript{n/2}.
  (The left-shift operation is considered to have negligible cost.) Then
  one can verify that

  N = ##AC + BD + #(A+B)(C+D) - #(AC+BD).

  This involves only three half-length multiplications, instead of the
  four that one might suppose were needed. For large n, the reduction
  can obviously be reapplied over and over to the smaller numbers. The
  price is a growing number of additions. By compounding this and other
  ideas, Cook showed that for any e and large enough n, multiplication
  requires less than n*(1-e) products, instead of the expected
  n-squared.

I got stuck when I read stands for multiplying by 10 ... because I didn't understand what the subscript in this example means. I tried to find it out by googling about the complexity of multiplication and stuff like that, but couldn't find the answer.

Can you point me in the right direction here? I guess that this exact part is essential for understanding the formula in the middle. I would like to find out how this computation would resolve a multiplication.

It should be "10 superscript{n/2}" meaning $10^{n/2}$. For example, if $n=4$, then "6#2" would represent $6\cdot10^2=600$. All he's doing is shifting a decimal number to the left.


Does solving mathematical equations with Cellular Automata structures means it is universal? I'm working on a research about Elementary Cellular Automata (ECA), and i found a method to build a system that can solve mathematical equations by using a specific cellular automaton structure.

The system is about encoding the equation into numbers and by applying some rules, these numbers are transferred to a Cellular Automaton structure.

For example => x^3-81=0 , after encoding it to numbers, it showed a structure contains 3 triangle, which is the answer of the equation encoded     ===>  (x^3-81=0)  ==> (x^3=81) =>  (x=3).

So, i have read the article about turing-complete:

  a system of data-manipulation rules (such as a cellular automaton) is said to be Turing complete or computationally universal

What i want to say is, the equation was transferred to numbers {data-manipulation rules} and it computed the input (the equation), then showed the answer (output).
Does that makes the system a turing complete ?

I have also tested other equations:

x^2-25=0
x^3-27=0
x^4-16=0

And the system always shows the right answer as triangles.

If you can solve arbitrary equations involving an arbitrary number of unknowns, then you have shown universality, as explained below.  So there is a sense in which your broad question "solving mathematical equations means universality" is actually true -- but we have to precisely define what "mathematical equations" mean here. From your actual examples it seems you are not at the final goal of showing universality: it is not sufficient to solve ploynomial equations in a single variable.

If the equations you can solve are so-called Diophantine equations, then your system is universal.  That is, polynomials with multiple variables and integer coefficients, and solved with solutions in the natural numbers. According to the solution of Hilbert's tenth problem such equations encode recursively enumerable sets (of natural numbers). The question whether the polynomial can have value $0$ with fixed `input' value of the first variable codes membership of that value in the set we compute. Or as wikipedia states: "Every recursively enumerable set is Diophantine". This seems universal to me.

To see how complicated these polynomials can be, have a look at this Formula based on a system of Diophantine equations for the prime numbers. (This example generates prime numbers, so is slightly different, but can be tweaked.)

The right definition of universality is not always clear. We must encode input and output in a way suitable to the machine at hand (here the cellular automaton) without giving away parts of the solution. I remember some controversy concerning this.


A problem regarding Extended Euclidean Algorithm Alex has some (say, n) marbles (small glass balls) and he has going to buy some boxes to store them. The boxes are of two types:

Type 1: each box costs c1 Taka and can hold exactly n1 marbles

Type 2: each box costs c2 Taka and can hold exactly n2 marbles

He wants each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them.
Since he finds it difficult to figure out how to distribute his marbles among the boxes he seeks his friends' help.
It is worthy of mention that the value of n,c1,n1,c2 and n2 are given.

His one friend solved this problem using extended euclidian algorithm and found out two values everytime .Thus his result for the input.

1.n=43,c1=1,n1=3,c2=2,n2=4 the result will be 13 1

2.n=40,c1=5,n1=9,c2=5,n2=12,the result will be "no valid values".

Though I understand extended euclidian algorithm I can not catch how he solved this problem.
Can anyone tell me how his friend sovled it using extended euclidian algorithm.
Since I'm a novice learner of extended euclidian algorithm I need better explanation.

Here are some ideas to get you started.

A number $n$ cannot be represented as a linear combination of $n_1,n_2$ unless $(n_1,n_2) \mid n$, since all linear combinations of $n_1,n_2$ are multiples of $(n_1,n_2)$.
The extended Euclidean algorithm gives you values $a_1,a_2$ such that $a_1n_1+a_2n_2 = (n_1,n_2)$, and in particular $$\frac{n}{(n_1,n_2)} a_1 n_1 + \frac{n}{(n_1,n_2)} a_2 n_2 = n.$$
If $n = b_1 n_1 + b_2 n_2$ then all other representations are of the form $$n = \left(b_1 + \frac{n_2}{(n_1,n_2)} t \right) n_1 + \left(b_2 - \frac{n_1}{(n_1,n_2)} t \right) n_2.$$

Try to use these ideas to solve the problem on your own.


how os can calculate cpu cache size? There's an interview question.

In my opinion, os can calculate cache hit rate and miss rate(with the total running time of process and the number of transfer of block of memory to cache).
But how can know the size of cache? Is it possible to calculate with os's certain information? (such as size of transfer size to cache)

We can assume anyting we need to calculate easily(like only one cache-no l1 l2 and so on, cache is fully associative or set associative or directed mapped and so on)

It's not clear to me what you want.

An OS can query the processor about its cache structure as long as the processor have the feature (for instance, X86 has this possibility tied with the CPUID instruction).

An OS could deduce the information from any mean of identifying the processor (nowadays something like CPUID, but in a given processor family there always had been more or less precise means to deduce which member your were running on, especially if you have access to privileged instructions as an OS does) and having hardcoded tables giving the sizes for each model.

Any program can try to measure the number of cache levels, their size, associativity, line size and latency.  What you have to do is measure the latency of memory accesses using well-thought-out patterns and plotting the the latency versus the total memory touched by the pattern.  You get some plateaus giving the latency of the cache, and the jumps positions give the cache sizes.  Comparing the results of different patterns give the associativity and the line sizes.  The more the cache is advanced (eviction buffers, pre-loading, ...) the more you have to be careful in the way the patterns are computed (a common technique is implementing the pattern as a pointer chase so that it is more difficult for the processor to guess the next address to be loaded) or you'll measure something different from what you want. Other factors to take into account is the effect of TLB, the presence of shared cache between cores and processors the load on the other cores, the effect of process migrations between cores by the OS, the effect of throttle by the OS or the hardware due to temperature or battery load.  In conclusion such measurements are pretty technical, and although you can deduce a lot of things it is better to have a preconceived notion of the memory structure and of the external factors which may have an influence.


How to model a logical indicator when two inequalities hold in Integer Programming? I have an IP program where $\forall i \in I, j \in J$ my decision variables are $x_{i,j}$. I have two sets of inequalities (one inequality for every $i,j$ pair) that are of interest which are $$a_{i,j} x_{i,j} \geq 1 \ \ \ \ \forall i \in I, j\in J$$ and $$ \sum_{j \in J} b_{i,j}x_{i,j} \leq b_{i,j}- 1 \ \ \ \ \forall i \in I, j\in J$$

I now want to introduce a logical indicator variable $\delta_{i,j}$ which equals 1 if and only if both of the inequalities are true and 0 else.
How could I implement this idea by introducing appropriate constraints for my Integer Progamming model?
I was thinking about defining a variable $\delta^1_{i,j}$ and $\delta^2_{i,j}$ which equals 1 iff the first and second inequality are true respectively and then maybe combine these two auxiliry logical variables into a single variable $\delta_{i,j}$, but I couldn't figure out exactly how to make this work.

Your general approach is a good one.  Use Boolean variable that captures whether an inequality holds to define $\delta_{i,j}^1$ and $\delta_{i,j}^2$.  Then, use Express boolean logic operations in zero-one integer linear programming (ILP) to define $\delta_{i,j}$ in terms of $\delta_{i,j}^1$ and $\delta_{i,j}^2$ (via a logical-AND operation).


How to find total number of minimum spanning trees in a graph with n edges? I had this question on my final exam so sadly I don't have the question but as far as I remember, the question was saying:

  How many minimum spanning trees does a graph with 20 edges have.

I know that we can find minimum spanning trees with algorithms like Prim's algorithm etc. But how can we know the total number of minimum spanning trees in a graph with no figure given in the question (text only)?

I'm hoping you misremembered the question, as the number of MSTs (minimum spanning trees) is not uniquely determined by the number of edges.  It depends on what edges are and are not present and also what their weight's are.

For example, if the graph has 21 vertices and 20 edges, then it is a tree and it has exactly one MST. On the other hand, if it has seven vertices and 20 edges, then it is a clique with one edge deleted and, depending on the edge weights, it might have just one MST or it might have literally thousands of them.

(A clique on seven vertices has 21 edges, which is only one more than your graph is allowed. If all the edge weights were the same, every subtree would be an MST and, by Cayley's formula, there are $7^5=16807$ different trees with seven vertices.)


Big O Notation of $n^{0.999999}\log(n)$ I'm taking the MIT Open Courseware for Introduction to Algorithms and I'm having trouble understanding the first homework problem/solution.

We are supposed to compare the asymptotic complexity (big-O) for different functions:

$f_1(n) = n^{0.999999}\log(n)$
$f_2(n) = 10000000n$

$f_2(n)$ is obviously O(n), but the big-O given for $f_1(n)$ confuses me and I don't follow the given solution.

The solution says $f_1(n)$ has less Big-O complexity than $f_2(n)$:

"recall that for any $c > 0$, $log(n)$ is $O(n^c)$.

Therefore we have: $f(n) = n^{0.999999}log(n) = O(n^{0.999999}n^{0.000001}) = O(n) = O(f_2(n))$"

I do not understand the logic underlying the solution. I may be forgetting something simple? Can someone break it down for me? Thanks!

If $g = O(g')$ and $h$ is nonnegative then $h \cdot g = O(h \cdot g')$ — in English, if $g$ grows slower than $g'$ then multiplying by a positive function doesn't affect that fact. (If you aren't sure about this, do the proof with quantifiers).

Since $\log(n) = O(n^{0.000001})$, $n^{0.999999} \cdot \log(n) = O(n^{0.999999} \cdot n^{0.000001})$. Since $n^{0.999999} \cdot n^{0.000001} = n$, we have $f_1(n) = O(n)$.

While it is true that $f_2(n) = O(n)$, this is not relevant here. What you need is $n = O(f_2(n))$, which is also true.

Intuitively, a higher exponent trumps a logarithm. A multiplicative constant is not significant.


Distinction between paging and segmentation? In my operating systems textbook, there is a paragraph which states:

As for the contents of each PTE, we have a number of different bits
in there worth understanding at some level. A valid bit is common to
indicate whether the particular translation is valid; for example, when
a program starts running, it will have code and heap at one end of its
address space, and the stack at the other. All the unused space in-between
will be marked invalid, and if the process tries to access such memory, it
will generate a trap to the OS which will likely terminate the process.
Thus, the valid bit is crucial for supporting a sparse address space; by
simply marking all the unused pages in the address space invalid, we
remove the need to allocate physical frames for those pages and thus save
a great deal of memory.

However, the bold sentences confuse me. I thought the whole point of paging was that you do away with the contiguous regions of logical code segments like stacks and heaps? With paging, couldn't the stack and heap be anywhere and non-contiguous? What guarantee do you have that the code, heap and stack will be separated to the top and bottom of the address space,as they say?

There are two different address spaces, let's call them logical and physical.  The addresses a programmer thinks about are the logical addresses, the page table translates logical addresses to physical addresses.

As you point out, paging allows you to sparsely map the logical address space to the physical address space.

But the bold sentences in your quote are talking about the sparsity of the logical address space.  The quote is arguing that the valid bit is necessary for the sparsity of the logical address space.


Minimum Subsequence Sum Algorithm Verification I have an algorithm which is meant to solve the following computational problem:

Input: Sequence of positive integers
Output: A Sub-sequence of some desired length derived from original Sequence such that the sum of the sub-sequence's elements are the minimum sum possible

The Algorithm I have to solve this problem is implemented as a method in Java:

public int[] runA(int k) {

        //k is desired length of sub-sequence

        /*Sequence S is the original sequence provided as input, it is available as a class variable
        for the class 'MinimumSubsequence' which this method 'runA' is apart of*/

        //A is Sequence S copy with pseudo-boolean values attached to each element in S
        int[][] A = new int[this.S.length][2];
        //B is size K array storing the k smallest elements found in S along with their indexes
        int[][] B = new int[k][2];

        //initialization
        for (int i = 0; i < this.S.length; i++) {
            A[i][0] = this.S[i];
            A[i][1] = False;
        }
        for (int i = 0; i < k; i++) {
            B[i][0] = this.S[i];
            B[i][1] = i;
        }

        //Execution
        //search for k smallest elements in sequence S
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < this.S.length; j++) {
                if (A[j][0] <= B[i][0] && A[j][1] == False) {
                    B[i][0] = A[j][0];
                    B[i][1] = j;
                }
                A[(B[i][1])][1] = True;
            }
        }

        //build subsequence
        int[][] C = new int[this.S.length][2];
        for (int i = 0; i < C.length; i++) {
            C[i][1] = False;
        }
        for (int i = 0; i < C.length; i++) {
            for (int j = 0; j < B.length; j++) {
                if (B[j][1] == i && (C[i][1] == False)) {
                    C[i][0] = B[j][0];
                    C[i][1] = True;
                }
            }
        }
        int[] D = new int[k];
        int j = 0;
        for (int i = 0; i < C.length; i++) {
            if (C[i][1] == True) {
                D[j] = C[i][0];
                j++;
            }
        }

        return D;
    }

The algorithm basically works by scanning the original sequence provided, each time scanning for the next smallest number. Once it has found the k smallest numbers in the sequence it builds and returns a sub-sequence made from those smallest elements in the original sequence

I believe that this algorithm does correctly solve the computational problem and that the running time of this algorithm is in O(N) (N being size of input sequence). I would just like some verification about the correctness and efficiency of this algorithm. I am also wondering if there exists are more efficient algorithm to solve this computational problem as I'm just not very satisfied with this one but can think of no other approach.

The fact that your algorithm is in Java or the source itself are not really relevant. That said, your algorithm requires time $\Theta(n \cdot k)$, where $n$ is the length of the input sequence, and $k$ is the length of the desired subsequence. This can be as bad as $\Theta(n^2)$, when $k=\Theta(n)$.

You can improve the time complexity of your algorithm to $O(n)$ by first finding the $k$-th smallest element $x$ in $O(n)$ time, and then selecting all elements smaller than $x$, plus the necessary number of copies of $x$ (there might be multiple copies of $x$ in the input sequence and not necessarily all of them belong to the output).

An easy selection algorithm is quickselect with randomized pivot selection. This algorithm has complexity $O(n)$ with high probability. If you want a $O(n)$ worst-case complexity you'll have to be a bit more careful with the pivot selection.
You can start by reading the Wikipedia pages on selection, quickselect, and median of medians.

If you want to be lazy and you don't care about losing a $O(\log n)$-factor over the optimal time complexity, then you can simply sort the input sequence in time $O(n \log n)$ (e.g., using Mergesort) and then return the first $k$ elements.

Another solution that is easy to implement if you have access to priority queues and has complexity $O(n \log k)$ is iterating over the input sequence while maintaining a max-Heap $H$ of the smallest $k$ elements encountered so far.
Initially $H$ is empty and, for each element $x$ of the input you: (i) push $x$ into $H$, (ii) if $H$ contains $k+1$ elements, you extract one element from $H$.
After examining all elements, $H$ contains exactly the $k$ smallest elements of the whole input sequence.


Confusion of halting problem Show that the following problem is solvable.Given two programs with their inputs and the knowledge that exactly one of them halts, determine which halts.
lets P be program that determine one of the program will be halted.
P(Program x,Program y){

    if(x will be halted)

          then return 1;

    else

           then return 2;
}

since we know that exactly one of them will be halted,if 1 then program x will be halted.Otherwiae program y will be halted.
then we construct a new program call D
D(X,Y){

     if(P(X,Y) == 2)

         D will halt;

      else

         while(1)//D will not halt;

  }

lets S be aritbrary program.
So if we have D(D,S)
if D will halt then D will not halt
if D will not halt then D will halt
It impiles a contradiction same as halting problem.
But the question stated that it is solvable.

To start with an important side note: what are the inputs for $X$ and $Y$ that they will halt on? you need to specify a specific input for the machines in order for the question to be well-defined (for example, the question could be "given $X,Y$ where exactly one terminates on $\epsilon$, find who halted." Or maybe, "given ... where exactly one always halts on itself as an input...")
I see what confused you there. The problem is indeed solvable: in $P$ emulate both $X$ and $Y$ and answer whoever halted first.
The problem in your solution is that an input to $P$ must be $X,Y$ where exactly one of them halts, and the other doesn't.
So, a proper input to $D$ must be a proper input to $P$. Now notice you called $D(D,S)$. To make sure that $D$ will return a correct output, we must have proper inputs: only one of $D$ or $S$ halts! But... If $S$ halts then your $D$ also halts and this is not a proper input to $P$, and therefore also not a proper input to $D$. Thus you cannot rely on output from $D(D,S)$ as it may not be correct


Do all states in a DFA must be connected? Could I construct (for some wired reason) a DFA that has a state that is not connected to anything, and it would still be legal?

I'm studying for a test, and I found a question that asks if an infinite DFA could represent a regular language, and I want to use a regular DFA and add all the infinite states not connected to the original. Can I do that?

I suspect a trick question in the material you are studying - there are no DFAs with an infinite number of states in the first place.

in fact, the whole point of D/NFAs is their finiteness. if you could have an inifinite number of (reachable) states in your NFA you'd actually be able to recognize any language; just take for every word in your language the trivial deterministic recognizer and connect a global start state with $\lambda$-transitions to the start state of each of these automata.


Karger's min cut and tips on bounding nonlinear recurrences I was recently working on an old qualifying exam problem asking us to generalize Karger's randomized global min cut algorithm to that of a global min $k$-cut. I recalled the strategy of running a recursive version of the randomized edge contraction algorithm to help with the shrinking the error probability and ultimately help with an efficient algorithm for getting the global min $k$-cut with probability $1/2$.
Most of the analysis was going well until I started to analyze the probability of success of the recursive algorithm. I found that this probability was ultimately described as
$$P_i \geq P_{i-1} - \frac{1}{4} P_{i-1}^2$$
where $P_{i}$ is the probability of success on some call of the algorithm at level $i$ of the recursion tree, with a leaf having $i = 0$. One could show that the depth of the tree was $d = \frac{c \log_2(n)}{(k-1)}$ for some constant $c$ and ultimately I was looking to lower bound $P_{d}$. However, I struggled to lower bound this recurrence. I knew from studying the algorithm for a min cut that this recurrence should have the lower bound $P_{d} = \Omega(1/\log(n))$. I wanted to try and show this but the best I got on my own was doing
\begin{align}
P_{i} &\geq P_{i-1} - \frac{1}{4} P_{i-1}^2 \\
&\geq P_{i-1}\left( 1 - \frac{1}{4}\right) \tag{ $P_{i-1} \leq 1$ } \\
&= \frac{3}{4} P_{i-1} \\
&\geq \left(\frac{3}{4}\right)^{i} P_{0}
\end{align}
which, when we evaluate $P_{d}$, gives us that
\begin{align}
P_{d} &\geq (3/4)^{d} P_0 \\
&= (4/3)^{-c \log_2(n)/(k-1)} \\
&= n^{-\frac{c}{(k-1) \log_{4/3}(2)}} \\
&\geq n^{-\frac{2.41 c}{(k-1)}}
\end{align}
This is a much worse lower bound than what can be found. After this point, I investigated the original paper for the recursive randomized min cut algorithm. The trick they used was to perform a nonlinear change of variables to the recursion, something of the form $P_{k} = 4/Z_{k}$, where $Z_{k}$ is the new recurrence variable. This change leads to a new recurrence of the form
$$Z_{k} \leq Z_{k-1} + 1 + 1 / (Z_{k-1} - 1)$$
Since $Z_{k} = 4 / P_{k} \geq 4$, this implies we can upper bound the above recurrence as
$$Z_{k} \leq Z_{k-1} + 2 \leq 2 k + Z_{0} = 2 k + 4/P_{0}$$
which finally implies that indeed $P_{d} = \Omega(1/\log(n))$. I see that this transformation worked, but I do not have intuition for why one might think to try such a transformation. Can anyone help me with that intuition? Are there any other useful tips for tackling bounds of nonlinear recurrences?

First of all, let me explain why your estimate is lossy: when $P_i$ becomes small, $P_{i-1} - P_{i-1}^2/4$ is very close to $P_{i-1}$, and in particular, it doesn't decrease exponentially.
Since the function $x - x^2/4$ is monotone in the range $[0,1]$, if you solve the corresponding recurrence $Q_i = Q_{i-1} - Q_{i-1}^2/4$ (with base case $Q_0 = 1$), then $P_i \geq Q_i$.
Let us write the recurrence relation as $Q_i - Q_{i-1} = -Q_{i-1}^2/4$. This is a difference equation which can be approximated by a differential equation $q' = -q^2/4$, with $q(0) = 1$. Using standard techniques, you can determine the solution, which is $q(i) = 4/(4+i)$. This suggests that $Q_i \approx 4/(4+i)$, and so hints that $4/Q_i$ is a useful quantity to look at.
Here is another way to estimate the recurrence. Write the recurrence as $$ Q_i = (1-Q_{i-1}/4) Q_{i-1}. $$
In a range of $i$ where $Q_i \approx \theta$, it takes $\Theta(1/\theta)$ steps to reduce $Q_i$ by a factor of $1/2$. In particular, after
$$
\Theta(1+2+\cdots+2^{\ell-1}) = \Theta(2^\ell)
$$
steps, we reach $Q_i \approx 2^{-\ell}$. This suggests that $Q_i$ scales like $\Theta(1/i)$. With a little bit of work, this argument can be made completely formal, though it is hard to get a hold on the exact constant factor in this way.


How do I use the Myhill-Nerode theorem to show that a language is not regular? My language is the repetition of 0 to a length that's a power of 2:

$L = \{ 0^k \mid k=2^n, n \geq 1 \}$

I want to know how to use the Myhill-Nerode theorem to show that this language is not regular.

This is my first attempt at doing this although I am confident that I am wrong:

$j, p = 2^h$ for 2 distinct values of $h$, $h \in \mathbb{N}$:

$a = 0^{j/2}$

$b = 0^{p/2}$

$c = 0^{j/2}$

$ac = 0^{j/2}0^{j/2} = 0^j$ is in my language since $j$ is of the form $2^n$

$bc = 0^{p/2}0^{j/2}$ is not guaranteed to be in my language for every $p$ and $j$, since $j \ne p$

Thus my language must not be regular since $ac$ is in it but $bc$ is not.

If you want to use Myhill-Nerode to show that a language is not regular, you need to prove that there are infinitely many equivalence classes.

Basically here, it suffices to prove that each $0^j$ is in a different class.

For instance $0^9$ and $0^{10}$ are not in the same class, because $0^90^7\in L$ while $0^{10}0^7\notin L$. Try to write the general proof for any $0^i$ and $0^j$ with $i\neq j$.


Finding C-convex holes in a planar point set I am looking for an efficient algorithm to find convex holes in a given point set.
The problem is

  Given $n$ points in the Euclidan plane, and a constant $c$, determine how many empty convex polygons $P_1, \dots, P_k$ there are, such that for each $i = 1,\dots,k$; $P_i$ has exactly $c$ vertices from the given point set.

Although there are some papers that considers finding possibly non convex holes [1] [2] [3], and some others that show existence of such holes [4] [5], I could not find a paper that describes an algorithm to find them.

Obviously, a naive algorithm that runs in $\mathcal{O}(n^c)$ comes to mind, where each $c$-subset is traversed. However, I would like to know whether there exists a more efficient algorithm.

In "Counting Convex Polygons in Planar Point Sets" (link) Mitchell et al. show an algorithm which can do this in time $O(cn^3)$.

Note however that if you need to report those polygons then you can't do better than $O(n^c)$ as there might be $\Omega(n^c)$ such polygons to begin with (consider for example $n$ points in convex position).


Implementation-level description of a Turing Machine I am new to Turing Machines!

I need to work on an implementation-level description of a Turing machine that
decides the language L = an where n is a Fibonacci number.

I know Fibonacci numbers include  1 1 2 3 5 8 13 21 34 55 89 144 233 377...

So would this be as

M= "On input a^n:
    Scan a^n, if a '1' is found, cross it out, and move the head
    of the tape back to the left-hand end, and then go to II
    (****could I make II my accept state? Or should I make two the recursive calculation I explain in C below?)

    If a '0' is found, cross it out, and go to the reject state
    (can I make this three?)
    II. Accept
    III. Reject

I want to incorporate the recursion aspect of this in the implementation. Because if I were in C, and n is not a 0 or 1, it is a fibonacci number if you do a sort of fib(n) where inside it 'return fib(n-1) + fib(n-2)'.

Thoughts? Thank you.

One approach is using Fibonacci words (each word is the concatenation of the preceding two words):
$$
\begin{align*}
&0 \\
&01 \\
&010 \\
&01001 \\
&01001010
\end{align*}
$$
You can generate them according to the following scheme:
$$
\begin{align*}
&\color{blue}0\color{red}1 \to \color{blue}0\color{red}1\color{green}0 \to
\color{blue}{01}\color{green}0 \to \\
&\color{blue}{01}\color{red}0 \to \color{blue}{01}\color{red}0\color{green}{01} \to \color{blue}{010}\color{green}{01} \to \\
&\color{blue}{010}\color{red}{01} \to \color{blue}{010}\color{red}{01}\color{green}{010} \to \color{blue}{01001}\color{green}{010} \to \\
&\color{blue}{01001}\color{red}{010} \to \cdots
\end{align*}
$$
I hope the algorithm is clear. The basic operations are copying of words and changing colors.

Why is this helpful? The lengths of the Fibonacci words are exactly the Fibonacci numbers. If you can compare lengths of words, then by generating the sequence of Fibonacci words, at some point you will either reach or exceed the input, and using that information will be able to decide your language.

While I explained how to generate the Fibonacci words, you can actually just generate the words $a^{F_n}$ directly, which is slightly easier. You can even do that on top of your input for a really slick approach.


Computing epsilon-closure. What does $E(n) \leftarrow \{n\};$ and $E(p)$ mean? I'm currently reading "Engineering a Compiler" book. In the chapter that explanes computing epsilon-closure there is listed the following algorithm:

But I couldn't understand what does $E(n)$ and $E(p)$ mean. I know that it has something to do with sets.

For each state $n \in N$, we maintain a set of states $E(n)$. Eventually, $E(n)$ would contain all states reachable from $n$ via $\epsilon$-transitions.

You can think of $E$ as an array of sets. The notation $E(n)$ just means the value of $E$ at position $n$. So $E(p)$ is just the value of $E$ at position $p$.


Computing the running time of a divide-by-4-and-conquer algorithm I write this code in python:

def sub(ma):
    n = len(ma); m = len(ma[0])
    if n != m : return
    n2 = int(ceil(n/2))
    a = []; b = []; c = []; d = []
    for i in range(n2):
        a.append(ma[i][0:n2])
        b.append(ma[i][n2:n])
        c.append(ma[n2+i][0:n2])
        d.append(ma[n2+i][n2:n])
    return [a,b,c,d]

def sum(ma):
        if len(ma) == 1 : return ma[0][0]
        div = sub(ma)
        return sum(div[0])+sum(div[1])+sum(div[2])+sum(div[3])

Do you know what is a possibly recurrence equation $T(n)$ to the 'sum' method?
I suppose that is like that
$$T(n) = 4T(n/2) + f(n)$$
what it is $f(n)$ ?
Thanks,

The subroutine sub quarters the matrix into four parts. This takes time $f(n)$, and so the running-time of sum (which sums all entries in its input square matrix in a curious divide-and-conquer fashion) satisfies the recurrence
$$ T(n) = \begin{cases} O(1) & n=1 \\ 2T(\lfloor n/2 \rfloor) + 2T(\lceil n/2 \rceil) + f(n) + O(1) & n>1. \end{cases} $$
The subroutine sub is quite simple, and I'm sure you can figure out its running time yourself (though you'll have to be careful about the semantics of list appending in python).