Is the language of Turing Machines that halt on every input recognizable? I  am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is not recognizable. Does anyone know how to do this reduction, what I come up with is:

Using python-like syntax:

def R(<M>,w):
    def F(x):
        if M(w)loops: //Run M on w
            return True on every x
        else
            loop on every x
return F

Of course the problem here is that we can't really know when M loops on w

Does anyone know how to do this reduction, or if it is possible to prove that the language of TMs that accept every input string is unrecognizable using a reduction from a different unrecognizable language?

Preliminary

Let $H$ be the usual halting language:
$$
H=\{(\langle M\rangle, w)\mid M(w) \text{ halts}\}
$$
Its complement is
$$
\overline{H}=\{(\langle M\rangle, w)\mid M(w) \text{ doesn't halt}\}
$$
We know that $H$ is recognizable (just run $M$ on $w$ and do what it does), so $\overline{H}$ must be unrecognizable (otherwise $H$ would be decidable, which we know isn't true).

The Reduction

As you suggested, we'll produce a reduction from $\overline{H}$ to
$$
AH = \{\langle N\rangle\mid N \text{ halts on all }x\}
$$
thus showing that $AH$ is unrecognizable. As you suggested, what we want is to map $(\langle M\rangle, w)$ to a description of a TM $M_w$ where

Mw(x) =
   run M on w
   if M(W) halts
      loop
   if M(w) doesn't halt
      halt

That would do it, except for the fact that if $M$ didn't halt on $w$, we'd never get to the $\texttt{halt}$ instruction. What we need is a finite way of testing for non-halting. A standard way to deal with this kind of difficulty is to limit the number of steps our simulation will perform, like this:

N(x) =
   run M on w for |x| steps
   if M has halted
      loop
   if M(w) hasn't halted yet
      halt

How does this modification help us?

If $(\langle M\rangle, w)\in\overline{H}$, then $M(w)$ will never halt, so $N(x)$ will halt after $|\,x\,|$ steps and thus $\langle N\rangle\in AH$
If $(\langle M\rangle, w)\notin\overline{H}$ then $M(w)$ will eventually halt, say after $s$ steps. This means that $N$ will halt on all inputs, $x$ of length less than $s$, and will loop on all longer inputs, so $\langle N\rangle\notin AH$.

This establishes the reduction we needed, and so we can conclude that $AH$ is non-recognizable.


Unusual elevator algorithm An elevator with a capacity of N people in a building with E floors works in a pretty unusual way.

The elevator starts at the first floor and it goes to the top floor before returning to the first floor.

It stops at every floor that is a destination of a person in the elevator.

It also stops when 1) there is someone at the current floor who wants to travel in the same direction as the elevator is currently traveling and 2) there is still room in the elevator.

At least how many round trips to the top and back are necessary to carry every person to their destination?

I assume that some kind of Greedy algorithm can give a good algorithm to solve this problem, but I still have no idea how to write a pseudocode for it.

I don't see any optimisation problem, no need for any greedy algorithm, nothing.

You described the behaviour of the elevator. All you need to do is to simulate that behaviour and count the number of movements.


N-queens problem objective function I have read about the N-queens problem and I don't understand the following objective function:

$O(board)=N^2/2-L$

$N$ ... number of queens
$L$ ... number of pairs of queens that attack each other

Why they use $N^2/2$? They wrote that it is the number of pairs of queens but I don't understand that can someone maybe explain it to me maybe with visualization

The objective function you describe satisfies two properties:

It is maximized at a solution.
It is non-negative.

One can think of many other functions satisfying these two properties, for example $\binom{N}{2} - L + C$ for every $C \geq 0$. The exact choice is not so important – indeed, they chose $N^2/2$ whereas they could have chosen $\binom{N}{2} = N(N-1)/2$.


Need pointers for problem formulation I have very little experience with graph DBs but i imagine this problem suits one

Assume a dataset with two entities , Users and Foods. A user can have a relationship with a Food, specifically they can score it from 0 to 100.

What i'd like to achieve is, for every user, find all the other users that are similar to them. By similar i mean find the Users that have also liked similar Foods and get a match so essentially im trying to build a a matchmaking system.

Algorithms such as finding friend's of friends are relatively easy to wrap my head around however im unsure as to how to approach this one and wether describing my data as a graph is even the right way to go about it.

I originally made a thought experiment to see how this would look on a relational database and its clearly quite hard to achieve as for every insert of a new Food or User, recalibration would need to happen for the entire database ( which sounds unavoidable in the first place )

I dont know what i dont know so if you could give me some pointers from here i'd be happy to follow your leads. Thanks so much.

Yuval Filmus already pointed you towards recommender systems, which in your case is the right way to go.

However, since you asked for a graph formulation and tagged it with graph-theory, we will go out of our way to put this into such a setting.

Definitions

A graph is called bipartite if its vertices can be partitioned into two sets, say $U$ and $V$ in such a way that all edges are between $U$ and $V$.  (Coincidentally a graph is bipartite if and only if it is two-colorable.)

A bipartite graph is called complete if every edge between $U$ and $V$ are present, i.e., it is isomorphic to $K_{n,m}$ for some $n,m \in \mathbb{N}$.

A bipartite graph is called a bicluster if its connected components induce complete bipartite graphs.

The problem

An editing problem is a graph problem where we want to add or delete (as few as possible) edges to make a graph have a certain property.  So let us define Bicluster Editing as the following problem:

Given a bipartite graph $G = (V, U, E)$ and a natural number $k \in \mathbb N$, does there exists a set of edges $E'$ such that $G' = (U, V, E')$ is a bicluster and $|E \triangle E'| \leq k$ (where $\triangle$ is the symmetric difference)?

Now, what does this mean?  If such a set exists for a small $k$, you have partitioned your users and foods into equivalence classes such that in every equivalence class, all the users like the same foods and all the foods are liked by the same users, changing the graph very little.

Is it practical? No.  But at least it's NP-complete.


Is it possible to reduce the number of variables in bin packing? The bin packing problem can be formulated as:
\begin{align}
 & \underset{x,y}{\min}
 & & B = \sum_{i=1}^n y_i\\
 & \text{subject to}
 & & B \geq 1,\\
 & & & \sum_{j=1}^n a_j x_{ij} \leq V y_i,\forall i \in \{1,\ldots,n\}\\
    & & & \sum_{i=1}^n x_{ij} = 1,\forall j \in \{1,\ldots,n\}\\
    & & & y_i \in \{0,1\},\forall i \in \{1,\ldots,n\},\\
    & & & x_{ij} \in \{0,1\}, \forall i \in \{1,\ldots,n\}, \, \forall j \in \{1,\ldots,n\},\\
\end{align}

where $y_i = 1$ if bin $i$ is used and $x_{ij} = 1$ if item $j$ is put into bin $i$.

Why do we use $x_{ij}$ and $y_{i}$? We can just use $x_{ij}$.

if $x_{ij}=1$ than bin $i$ is used and item $j$ is put into bin $i$; and
if $x_{ij}=0$ than bin $i$ is not used.

Is that correct? If so, why can't I find any formulation with only $x_{ij}$?

An integer program, or more properly an integer linear program, consists of a linear program together with integrality constraints stating that some of the variables are integers. As such, its objective function is always a linear combination of variables.

When the objective is minimization, it is admissible to have $\max$ operators (appearing positively) in the objective function. This means that there is an equivalent proper integer program. This program is obtained by introducing auxiliary variables, just as the variables $y_i$ are introduced in your example to implement $\max_j x_{ij}$.

To answer your question, it all depends on what you consider as an integer program. The standard definition only allows linear objective functions, and in this case the $y_i$ are necessary. If you also allow $\max$ operators in the objective function, then the $y_i$ are not necessary.


Find vectors with elements of finite fields that sum up to given value Given a universe $U$ consisting of k sets of vectors with each vector $\vec{v} \in {\mathbb{F}_{p^m}}^n $. Given also another vector $\vec{c} \in {\mathbb{F}_{p^m}}^n$.
Now decide if there is a set $X$ with $|X| = |U|$ and $X_i \in U_i, i = 1,2,...,k$ such that $\sum\limits_i X_i = \vec{c}$. If there is, output this set.

In other words, I want to find a combination of one element out of each set that sums up to the given vector, given that the vectors' entries can only be the results of modulo operation with a given integer. I hope the problem becomes clear.

I want to find an efficient algorithm to solve this problem. It seems to me that it is NP-complete, but I find no other NP-complete problem that I can reduce. If there is one, existing algorithm (if any) to that other problem could be used for this problem.
I looked at integer programming, but I did not find anything with respect to finite fields.

Any ideas?

It looks like subset-sum problem. It should be possible to adapt the pseudopolynomial algorithm.


Can Strassen's multiplication algorithm be improved if we divide matrices to 3x3 or axa in general? Strassen's algorithm uses the divide and conquer approach to divide the matrix multiplication of two  nxn matrices to multiplication of 7 2x2 matrices to get an overall complexity O(n^c) where c=log_2(7). I also read a paper which proved that it was impossible to multiply two 2x2 matrices in less than 7 multiplication operations.

So my question is, what's so special about 2x2? Why not break the original matrix multiplication to  3x3 matrix multiplication. Surely, if we can make the multiplication in 21 multiplications or less, then we would have a better result than dividing it to 2x2. And then why stop at 3x3, when you can divide the problem to 4x4, or in general axa?

There is nothing special about 2×2 matrices. In fact you can do much better using larger matrices. The reason that you are only being explained the 2×2 algorithm is that it is simple to describe. The special thing about 2×2 matrices are that they are the smallest square matrices which are larger than 1×1.

You can read more in this recent survey by Dumas and Pan on fast matrix multiplication, which concentrate on practical algorithms.

From a pure mathematical point of view, the following theorem is known:

  Suppose that the algebraic complexity of matrix multiplication is $O(n^\alpha)$. Then for every $\epsilon > 0$ there is a divide-and-conquer algorithm for multiplying matrices in $O(n^{\alpha+\epsilon})$.

Here a divide-and-conquer algorithm is an algorithm which recursively applies some smart algorithm for multiplying $m\times m$ matrices, for some constant $m$.

The fastest theoretical algorithm for matrix multiplication, due to Le Gall, is based on the classical algorithm of Coppersmith and Winograd. Unfortunately, this algorithm isn't practical.


Algorithms for minimizing Moore automata Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times of these algorithms if any?

The original DFA minimization algorithm was actually designed for Moore Machines, guided by their apparently more observable behavior.
But the algorithm presented here is a reconstruction from the DFA minimization,
since I discovered the historical evidence after the fact.

After Wikipedia (with some notational changes):

  A Moore machine can be defined as a 6-tuple $(Q, q_0, \Sigma, \Pi, \delta, \gamma)$ consisting of the following:

  a finite set of states $Q$
  a start state (also called initial state) $q_0$ which is an element of $Q$
  a finite set called the input alphabet $\Sigma$
  a finite set called the output alphabet $\Lambda$
  a transition function $\delta : Q \times \Sigma \rightarrow Q$ mapping a state and the input alphabet to the next state
  an output function $\gamma : Q \rightarrow \Pi$ mapping each state to the output alphabet

From this definition, a Moore machine is a deterministic finite state
transducer.

I have no reference for minimization of Moore automata. However it
seems not too hard to imagine an algorithm, derived from the algorithm used for
deterministic finite state automata.

The idea in DFA minimization is based on the Myhill-Nerode
characterization of regular languages.

  Given a language $L$, and a pair of strings $x$ and $y$, define a
    distinguishing extension to be a string $z$ such that exactly one of
    the two strings $xz$ and $yz$ belongs to $L$. Define a relation
    $R_L$ on strings by the rule that $x R_L y$ iff there is no
    distinguishing extension for $x$ and $y$. It is easy to show that
    $R_L$ is an equivalence relation on strings, and thus it divides the
    set of all strings into equivalence classes.

  The Myhill-Nerode theorem states that $L$ is regular if and only if
    $R_L$ has a finite number of equivalence classes, and moreover that
    the number of states in the smallest deterministic finite automaton
    (DFA) recognizing $L$ is equal to the number of equivalence classes
    in $R_L$.

Indeed each state $q$ of the smallest DFA is such that $W_q$ as
defined above is one of the equivalence classes for the relation $R_L$.

For a non-minimal DFA for the regular language $L$,
it is easy to show that each set $W_q$ contains
strings that all belong to a same equivalent class with respect to
$R_L$.

Hence, the minimization of the DFA actually consists of merging states
(considered as sets of equivalent strings), whenever it is shown that
two distinct states contain equivalent strings.

Two reasonably fast algorithms exists for that purpose, Moore
algorithm (1956) which is in time $O(n^2)$ and Hopcroft's algorithm
(1971) in time $O(n\log n)$.

The extension to Moore automata is best understood in redefining the
equivalence relation as $R_T$ for a transducer $T$. The relation $R_L$
was concerned with whether future input would lead equivalently to an
accepting state. The $R_T$ equivalence relation of Moore automata is
concerned with whether future input will produce the same output.

Hence, given a transducer $T$, and two strings $x$ and $y$, we define a
distinguishing extension to be a string $z$ such that $T(xz)=T(x)u$
and $T(yz)=T(y)v$ with $u\neq v$, i.e. such that the output behaviour
of the transducer differs for $z$ depending on whther it is following
$x$ or $y$.

Again, $R_T$ is an equivalence relation, dividing all strings in
$\Sigma^*$ into equivalence classes. In the case of a Moore machine,
these classes will again correspond to state of the minimal
transducer.

The following algorithm mimics the Moore algorithm for DFA minimisation.

We define an initial partition $\mathcal P$ of $Q$  into classes of states $S_e$ as follow:

$\forall e\in\Pi:\; S_e=\{q\in Q\mid \gamma(q)=e\}$

Then we split the classes in $\mathcal P$ as follows:

repeat successively for each class of states $S$, until none
  changes
$\ \ $ repeat $\forall a\in\Sigma,\;$
$\ \ \ \ $ If $ \exists S'\in \mathcal P,\; \forall q\in S,\;
\delta(q,a)\in S'$  then do nothing
$\ \ \ \ $ else split $S$ into subsets $S_i$ such that
$\ \ \ \ \ \ $ for each
  subset $S_i$,  there is a different class $S'\in \mathcal P$ such that $ \forall q\in S_i,\;
\delta(q,a)\in S'$
$\ \ \ \ \ \ $ (the subsets $S_i$ replace $S$ in $\mathcal P$)

When there is no class left that needs to be split, the remaining
classes of states will form the states of the minimal Moore
machine.

By construction, all states in a class have the same output which is
the output for the class.

Similarly, for any input $a\in\Sigma$, all states in a class go to some
state in the same other class, which defines the transition function
for the minimal Moore machine.

Complexity analysis:
Let $n=|Q|$ be the number of states, and $s=|\Sigma|$ the size of the input alphabet.
The main loop is executed at most $n$ times, since each iteration must
split at least one class of states, and each class contains at least
one state. Each iteration of the loop examines each state a finite
number of times, and in proportion to the number of input symbols. Hence the complexity of the algorithm is $O(sn^2)$,
the same as that of the DFA minimization algorithm that served as a guideline
for this one.

I do not have any reference for this minimization of Moore
machines. Possibly it is included in his paper:

  Moore, Edward F (1956). "Gedanken-experiments on Sequential Machines". Automata Studies, Annals of Mathematical Studies (Princeton, N.J.: Princeton University Press) (34): 129-153.

This paper is the main reference introducing Moore Machines. It is also the reference for Moore's DFA minimization algorithm. It should thus be surprising if the adaptation of the algorithm to the
minimization of Moore Machines were not at least suggested in that
paper. I did check the paper, and the version of the minimization
algorithm that is presented is actually for Moore machines, not for
DFA. The paper is well written, but the style of the time makes it a
bit harder to read. It is interesting to see that many of the ideas of the Myhill-Nerode theory of Finite State Machines are already sketched in this paper.

The more recent $O(sn\log n)$ algorithm due to John Hopcroft (1971) should be similarly adaptable to Moore machines. It is not clear that there was any reason to publish this adaptation anywhere, and the Hopcroft paper seems to have no reference to Moore machines.


Algorithm to determine a set given the size of its intersection with sets you choose I am competing in a programming contest where the submission phase can be stated abstractly as follows : There is a known universe set, $U$, and a hidden target $T \subset U$.  I submit $S \subset U$, and for feedback I am given $|S \cap T|$.

What is a good/optimal strategy for finding $T$ in as few submissions as possible given no assumptions on the distribution of $T$?  What are the complexity bounds in terms of $|U|$ and $|T|$?  In my application, $|U|$ is in the tens of millions and $|T|$ has a known size of around 5000.

You are asking two questions. I will only answer the first, ignoring the fact that $|T|$ is much smaller than $|U|$. Your problem is very similar to the one tackled in this question. The same lower bound of $\Omega(n/\log n)$ holds here as well, where $n = |U|$. The same (apparently) matching upper bound also holds, since you can simulate a Hamming distance query using your kind of query.


Computer Architecture: How to determine the bits of the address used to access the cache? Given a non-associative, direct-mapped cache and its cache capacity, block size, and address size, how would I go about determining what bits of the address are used to access to cache? Is there a generalized formula?
If there is a generalized formula, how would that formula change or stay the same for an X-way set associative cache?

A direct-mapped cache is another name for a one-way set associative cache.
Calculating number of bits in address space
 Number of bits in address space = log2(Memory size)
 Bits in (Tag + Index + offset) = Number of bits in address space
In order to know the number of bits in Tag field, we would need to figure out the number of bits in Index and Offset fields. Then the above equation can be used to get the number of bits in the Tag field.
The index bits are used to select the row in the cache. The offset would then be used to get the cache block. This means we definitely need those number of bits to access information from the cache and the remaining bits from the total address space can be used to store the tag information.
Calculating the number of bits for the offset
The offset fields can be calculated using the information about the block size. A cache block is the basic unit of storage for the cache. For these set of problems the offset should be able to index every byte from within the cache block.
offset bits = log2(block size)
Calculating the number of bits for the cache index
Calculation for the number of index bits is slightly more involved than the calculation for the offset field. The reason being that the calculation needs to take the number of sets, block size and the cache size into account. The index bits are needed to select the cache row but before that we need to figure out the number of rows for a given cache configuration.
The number of rows would be equal to the cache size divided by the block size for a direct mapped cache (there's just one way). For a n-way set associative cache, the number of rows would be cache size divided by the number of ways and the block size, i.e.
Number of rows = Cache Size / (Block Size x Number of Ways)
Once the number of rows are known, the number of index bits would simply be the log base 2 of the number of rows:
Index bits = log2(Number of rows)
That's it. We can now work the number of Tag bits using the following relationship:
Tag + Index + Offset = Address bits
Source: https://blog.quicksilicon.in/setassociativecache/


Quick Sort vs Radix Sort In an coding exam, I was once asked this question:

  Assuming that you are only sorting Integers in ascending order, which algorithm do you use when you want to prioritize speed the most, but you also want to save space?

The options were:

  LSD Radix Sort
  Merge Sort
  Quick Sort

I think an argument can be made between LSD Radix Sort and Quicksort.

Radix sort would function in $O(k n)$ and Quicksort would function in $O(n \log n)$ and worst case, $O(n^2)$

I chose Radix Sort as the answer, but I'm curious as to what others had to say.

This depends... If the number of input numbers is $n$, assuming the word-ram model of computation, a word size of $\Theta(\log n)$ bits, and worst-case inputs:

Radix sort would require $O(n \log n)$  time and $O(n)$ auxiliary space.
Quicksort with fixed or random pivot selection would require $O(n^2)$ worst-case time and $O(\log n)$ auxiliary space.
Mergesort requires $O(n \log n)$ time and $O(n)$ auxiliary space.

Radix sort and Merge sort are then equivalent in this setting.

Notice that using quicksort with random pivoit selection results in a time complexity of $O(n \log n)$ with high probability. Selecting the pivot deterministically in a way that partitions the elements into two sets whose cardinalities are at most a constant factor apart gives your an algorithm with worst-case time complexity of $O(n \log n)$ and $O(\log n)$ auxiliary space.


VC dimension of complement Let $C\subseteq 2^X$ be a concept class over $X$ and let $\bar{C}:=\{X\setminus c\mid c\in C\}$ be the complement. Show that $VCdim(C)=VCdim(\bar{C})$.

Proof:

Let $d:=VC_{dim}(C)$, then there exists $S\subseteq X$, $|S|=d$, s.t. $S$ is shattered by $C$.

Let $d':=VC_{dim}(\bar{C})$, then there exists $S'\subseteq X$, $|S'|=d'$, s.t. $S'$ is shattered by $C$.

Show that $d\leq d'$ and $d' \leq d$. I know that a set $S$ is shattered by $C$ iff $\Pi_C(S):=\{c\cap S\mid c\in C\}=2^S$, but I have no clue how to show the two sides. Can someone help me with that?

First, observe that it is enough to prove that $d\le d'$. Then, the converse inequality follows from the fact that $\overline{\overline{C}}=C$, and by applying the initial argument to $\overline{C}$.

To prove the claim, we actually prove something stronger: we prove that if $C$ shatters $S$, then $\overline{C}$ also shatters $S$.

Let $S$ be a set that is shattered by $C$, and consider $\Pi_{\overline{C}}(S)$. Let $T\subseteq S$, then there exists $c\in C$ such that $c\cap S=S\setminus T$ (since every subset of $S$ can be reached this way). Let $c'=X\setminus c\in \overline{C}$, then $c'\cup c=X$. Thus, $c'\cap S=T$. Therefore, $\Pi_{C}(S)\subseteq\Pi_{\overline{C}}(S)$.
Applying the same argument to $\overline{C}$, we get $\Pi_{\overline{C}}(S)\subseteq \Pi_{\overline{\overline{C}}}(S)=\Pi_{C}(S)$, and thus we have the equality we wanted, and we conclude the claim.


How to draw a Turing Machine for Even-Even A TM to accept EVEN-EVEN (a collection of all strings with an even number of a's and an even number of b's) can be based on the algorithm:

Move up the string, changing a’s to A’s
Move down the string, changing b’s to B’s

Modified algorithm: To avoid the problem of crashing on the way down the $Tape$, change the letter in the first cell to an $X$ (if it's an $a$) and to a $Y$ (if it's a $b$). This way we can recognize the left end of the tape.

So far I have this but am not sure how to implement the modified algorithm (note: the e's from start to halt mean empty):

Any help is appreciated!

From what I understand, your first algorithm intends to process the $a$ and $b$ inputs separately, which doesn't seem necessary. Your difficulty seems to come from formalizing a TM, which you can do in a couple ways.

Direct Conversion (Courtesy of Raphael in the comments)

  You can view an NFA as TM that can not write and move only to the
  right. In other words, you don't have to do anything at all for the
  conversion, just add $R$ to transitions that consume a symbol and $N$
  to $ε$-transitions, and then you basically have your equivalent TM.

Multitape Approach - Suppose we know that a multitape TM is equivalent to a TM, so  we can have two tapes:

An input tape (with a string $x\in(a|b)^*$), which we'll read through exactly once.
A computation tape which will have one of four numbers $1$, $2$, $3$, or $4$, reflecting the state that the analogous finite automata (for which you have an image) might have. If we didn't want to expand the alphabet, we could instead have $\{\epsilon\epsilon,a\epsilon,\epsilon b,ab\}$ to indicate the parity of each letter.

As we proceed through the input, we update the computation tape accordingly: if we read an $a$, and we're in state $1$, we swtich to state $3$, etc. To reduce this back to one tape, we need another symbol $\#$ to separate tapes, perhaps $\hat{a},\hat{b}$ to designate the location of the heads and pre/append our computation tape (for which we only need two characters of space).

Formal Approach - we're going to define the set of states $Q$, the tape alphabet $\Gamma$, the blank symbol $\epsilon$, the input symbols $\Sigma$, the initial state $q_0$, the accepting states $F$ and the transition function $\delta$.

$$\langle Q=\{q_{\epsilon\epsilon},q_{a\epsilon},q_{\epsilon b},q_{ab}\},\Gamma=\{a,b\},b=\epsilon,\Sigma=\{a,b\},q_0=q_{\epsilon\epsilon},F=\{q_\epsilon\},\delta\rangle$$
$$\delta=
\begin{vmatrix}
    & q_{\epsilon\epsilon} & q_{a\epsilon} & q_{\epsilon b} & q_{ab} \\
  a & q_{a\epsilon} & q_{\epsilon\epsilon} & q_{ab} & q_{\epsilon b} \\
  b & q_{\epsilon b} & q_{ab} & q_{\epsilon\epsilon} & q_{a\epsilon} \\
\end{vmatrix}$$


What does "associative" exactly mean in "n-way set-associative cache"? I'm trying to grasp what does associative actually mean in n-way set-associative cache. I understand n-way set-associative cache as a concept; n is the degree of associativity, i.e., how many cache lines a set can hold.
If I take associative to mean "having the tendency to connect", I get to the "sets tend to connect to...", what, memory addresses?
But I'm not sure if this is the correct understanding.

An n-way set associative cache is a cache that is chopped up in sections called sets. And each set can hold n-blocks.
A cache-address can be broken up up in 3 parts.

the offset within the block
the index that identifies the set
the tag that identifies the block in the set.

When a request comes in, the index is calculated to identify the set. Then the tags of all blocks in the set are checked. And when a block with a matching tag is found, the right bytes are returned based on the offset.
A direct mapped cached is effectively a 1 way set associative cache.
So associativity doesn't mean the number of blocks the cache can hold, but the number of blocks a set within the cache can hold.
The big advantage of a n-way set associative cache compared to a direct mapped cache, is the latter can only have a single block for a set of addresses and the former can hold multiple blocks for a set of addresses.


How can I quickly guess if L is context-free or det. context-free? I have a language, for example

$\{a^m b^n c^n \mid m, n \in \mathbb{N}, m = 2n\}$
$\{a^l b^m \mid l, m \in \mathbb{N}, l=4^m\}$

How can I see at a glance whether the language is deterministic context-free, context-free or not context-free?  I'm not willing to try to prove the language to be context-free.  I just want a heuristic -- a quick test I can apply by inspection, without use of a computer, that will often be correct.

This answer was first written before the OP edited the question to specify
that he wanted "a quick test I can apply by inspection, without use of
a computer, that will often be correct."

Of course, I do not think anyone has such a test. To begin with, we
should first define a meta-language defining sets of strings to which
such a test could be applied. How general should this language be, as
we can even define metalanguages that can describe only context-free sets.
But that is no help, since the difficulty remains in the translation
between metalanguages.  In other words, this is simply an ill defined
question as asked.

And even if we were to agree on the language, as something that looks
more or less like the examples, we just do not have such
tests. Actually the question was raised before, as a suggestion for
research, but I do not recall there was any follow-up.

This discussion is mostly intended for the determination of
CF-ness. Raphael rightly commented that if the language is known to be
CF, even assuming that a CF grammar is known for it, it remains
undecidable to determine whether it is deterministic CF. However, the
OP is not asking for a decision procedure, but only a test which works
most of the time. So assuming there is a proper definition of what
most of the time means, such a test could still exist, though I do not
know of any. To take an example in a somewhat different family of
problems, there are primality tests that are fast and known to work
most of the time, with a probability of error that can be chosen
arbitrarily low (with increased cost).

Before I knew the OP wanted "a quick test", I thought he was only
asking for the heuristics we use to get a feeling that some language
is more likely to be this or that. I tried to give some hints on how I
do it. There is nothing more to my answer. It is based on a few
patterns that we see often enough, though the devil in the details may
sometimes change the answer.

Here is what I first answered

Since your question is whether we can see things at a glance, the
answer is that for many exercises, we can ... though we may
occasionally make mistakes.

Very often the stack is used simply as a counter, which is only a
small part of the CF power.

This is typically the case of the following example: $\{a^l b^m \mid l, m
\in \mathbb{N}, l=4m\}$, you have to check that 2 subparts of the
string have the same length $m$, up to a multiplicative rational
constant (4 in this case). That is easily done with a pushdown stack,
by pushing $m$ times in the stack the first time, and then popping $m$
times, checking that there is enough and not too much to pop. When you
push, or pop, you can do it for several symbols to account for the
constant.

However, this allows you to synchronize the sizes of two parts of the
input string, but not more. Once the information is popped, it is lost
and there is no way you can check a third part for the same size.
This is the case of your first example, where you would have to check
for $2n$ and twice for $n$, which makes three times, one too many.

The second example can be discounted as non CF for another reason. The
pumping lemma, without going into details, does tell you that an
infinite CF language has strings that can increase in size by constant
increments. That is, there is some number $n$ such that you can find an
infinite sequence of strings that increase in length by exactly $n$.

For a language of the form $\{a^l b^m \mid l, m \in \mathbb{N},
l=4^m\}$, when you increase $m$ by 1, the number of $a$ increases by
$4^{m+1}-4^m=3\times 4^m$.  That is incompatible with the presence of a linearly
increasing sequence. Exponentials usually do that.

This is an example of using the pumping lemma without even bothering
to try pumping anything. Geological considerations tell you the well will be dry.

Hence I conclude that none of your examples is CF,

But that is not always a full proof (though the pumping lemma use could be considered one). Mostly first evaluation at a glance, heuristics. One might combine exponentials so that things work.

As for deterministic, it is another kind of game. Basically, you try
to see whether you have to guess sometning in order to do your
counting right, so that it succeeds.

In the first example I gave, you obviously do not need any guess. It is
deterministic CF.

But if you consider the language
 $\{a^n b^{2n}c \mid n\in \mathbb{N}\} \cup\{a^n b^{4n}d \mid n\in
 \mathbb{N}\}$
it is non deterministic because you have to guess the last symbol of
the string before you decide to count with the constant 2 or with the
constant 4.

Thanks to  Hendrik Jan for pointing out my misreading of one example.


Lambda calculus outside functional programming? I'm a university student, and we're currently studying Lambda Calculus. However, I still have a hard time understanding exactly why this is useful for me. I realize if you do loads of functional programming it might be useful, however I reckon that it's not really needed for learning functional programming, what do you think?

Secondly, is there any use for Lambda Calculus within the realm of Computer Science but outside of functional programming languages?

You are asking for an application outside of computer science and logic. That is easily found, for example in algebraic topology it is convenient to have a cartesian closed category of spaces, see convenient category of  topological spaces on nLab. The formal language corresponding to cartesian closed categories is precisely the $\lambda$-calculus. Let me illustrate with a very simple example how this comes in handy.

First, as a warmup exercise, suppose someone asks you whether the function $f : \mathbb{R} \to \mathbb{R}$ defined by $f(x) = x^2 e^x + \log (1 + x^2)$ is differentiable. You do not actually have to prove that it is, you just observe that it is a composition of differentiable functions, therefore differentiable. In other words, you made an easy conclusion based on the form of definition.

Now for the real example. Suppose someone asks you whether the function $f : \mathbb{R} \to \mathbb{R}$ defined by
$$f(x) = \left(\lambda f : \mathcal{C}(\mathbb{R}) . \int_{-x}^{x} f(1 + t^2) dt\right)(\lambda y : \mathbb{R} . \max(x, \sin(y + 3))$$
is continuous. Again, we can immediately answer "yes" because the function is defined using the $\lambda$-calculus and starting from continuous maps $\max$, $\int$, $\sin$, etc.

Various extensions of the $\lambda$-calculus make it possible to do the same sort of thing in other areas. For example, because a smooth topos is a cartesian closed category, any map which is defined using the $\lambda$-calculus, starting from derivatives and the ring structure of the reals (and you can throw in the exponential function if you wish) is automatically smooth. (Actually, the main thrust of the smooth topos is the existence of nilpotent infinitesimals which allow you to meaningfully say things like "we disect a disc into infinitely thin isosceles triangles".)


Proving that if coNP $\neq$ NP then P $\neq$ NP I am new in complexity theory and this question is a part of a homework that I have and I am stuck on it.

Let ${\sf coNP}$ be the class of languages $\{\overline{L}: L \in {\sf NP} \}$.
Show that if ${\sf NP} \neq {\sf coNP}$, then ${\sf P}\neq  {\sf NP}$.

It is maybe easier to consider the contrapositive, that is ${\sf P}={\sf NP} \Rightarrow {\sf NP}={\sf coNP}$.

So assume ${\sf P}={\sf NP}$, then

for every $L\in {\sf NP}$, we have $L\in {\sf P}$, and since the languages in ${\sf P}$ are closed under complement,  $\bar L\in {\sf P}$ and therefore $L\in {\sf coNP}$.
for every $L\in {\sf coNP}$, we have $\bar L\in {\sf P}$, and since the languages in ${\sf P}$ are closed under complement,  $ L\in {\sf P}$ and therefore $ L\in {\sf NP}$.

Remark: Note that if ${\sf P}={\sf NP}$ the polynomial time hierarchy collapses to the lowest level, which implies that ${\sf P}={\sf NP}={\sf coNP}={\sf PH}$.


Irregularity of $\{0^x1^y : y \nmid x\}$ The language $L=\{W\in\{0,1\}^{*} \mid W=0^{x}1^{y} \text{ where } x\geq0, y>0 \text{ are integers and } y\nmid x\}$ is not regular.
How would one prove this using Pumping Lemma?
I thought about it for quite a while but couldn't quite figure it out. Lots of number theory is necessary I'd imagine.

Assume that $L$ is regular. Suppose that the pumping constant is $q$, and let $p$ be a prime larger than $q$. Consider the word $w = 0^{p+1}1^p \in L$. According to the pumping lemma, we can write $w = xyz$, where $|xy| \leq q$, $y \neq \epsilon$, and $xy^tz \in L$ for all $t \geq 0$. Let $y = 0^i$, where $1 \leq i \leq q < p$. Then
$$
xy^{t+1}z = 0^{p+1+ti} 1^p.
$$
Since $i \in \{1,\ldots,p-1\}$ and $p$ is prime, we know that $i$ has an inverse modulo $p$, that is, a number $j \in \{1,\ldots,p-1\}$ such that $ij - 1$ is a multiple of $p$, say $ij = ap + 1$ (we prove this below). If we take $t = (p-1)j$ then
$$
p+1+ti = p+1+(p-1)ij = p+1+(p-1)(ap+1) = p(a(p-1)+2)
$$
is a multiple of $p$, and so $xy^{t+1}z \notin L$, contradicting the pumping lemma.
The existence of $j$ can be proven in many ways. Here is one. Consider the integers $i,2i,3i,\ldots,(p-1)i$. Suppose that you divide them by $p$, obtaining remainders $r_1,r_2,\ldots,r_{p-1}$. Since $p$ is prime and $i \in \{1,\ldots,p-1\}$, all these remainders are non-zero. Furthermore, they must be different: if $r_u = r_v$ for $1 \leq u < v < p-1$ then $vi-ui = (v-u)i$ would be a multiple of $p$, contradicting the primeness of $p$. Therefore one of the remainders $r_j$ must equal $1$.


Decidable restrictions of the Post Correspondence Problem The Post Correspondence Problem (PCP) is undecidable.

The bounded version of the PCP is $\mathrm{NP}$-complete and the marked version of the PCP (the words of one of the two lists are required to differ in the first letter) is in $\mathrm{PSPACE}$ [1].

Are these restricted versions used to prove some complexity results of other problems (through reduction)?
Are there other restricted versions of the PCP that make it decidable (and in particular $\mathrm{PSPACE}$-complete)?

[1] "Marked PCP is decidable" by V. Halava, M. Hirvensalo, R. De Wolf (1999)

Ehrenfeucht, Karhumäki and Rozenberg have shown that binary PCP (where the domain is binary) is decidable. Halava and Holub later showed that it's actually in P.


this automata is NFA or DFA? That's my question, since it has two symbols but go to a single state, is DFA or NFA?

First of all, every deterministic finite automaton is a fortiori a non-deterministic finite automaton. An finite automaton is deterministic if there are no $\epsilon$ moves, and for each state $s$ and alphabet symbol $\alpha$ there is a unique outgoing edge at $s$ labeled $\alpha$. If a finite automaton satisfies this condition, then it you can think of it both as a DFA and as an NFA. If it doesn't satisfy this condition, it is an NFA.


Regular language such that L(r) = L(r₁) L(r) ∪ L(r₂) Prove or disprove the following statement: for arbitrary regular expressions $r_1$ and $r_2$ over an
alphabet $\Sigma$ such that $\epsilon$ belongs to $L(r_1)$, there exists a regular expression $r$ over $\Sigma$ such that $r = r_1r + r_2$.

My Solution: Let us consider $\Sigma =\{a\}$. $L_1$ is even number of symbols so $r_1 =(aa)^*$ and $L_2$ is odd number of symbols so $r_2 = a(aa)^*$. $r$ is either $r_2$ which is possible or $rr_1$. Now if we keep replacing $r$ with $rr_1$ in the expression we will end up getting an infinitely large string because $r$ cannot be $\epsilon$ (thats what I think). So in my opinion this language is not regular. But I am not sure if I am thinking correctly.

Take $r = (r_1 + r_2)^*$. We have to prove
$$(r_1 + r_2)^* = r_1(r_1 + r_2)^* + r_2$$

First note that both $(r_1 + r_2)^*$ and $r_1(r_1 + r_2)^* + r_2$ contain $\epsilon$ since we are given that $\epsilon \in L(r_1)$, so we will consider a nonempty string in our proof.

Let's first show that $(r_1 + r_2)^*\subseteq r_1(r_1 + r_2)^* + r_2$. But it is trivial since we know that $\epsilon \in L(r_1)$ and so
$$r_1(r_1 + r_2)^* + r_2 = (r_1 + r_2)^* + r_1'(r_1 + r_2)^* + r_2, \text { where } r_1 = r_1' + \epsilon$$

Now we have to show that $r_1(r_1 + r_2)^* + r_2 \subseteq (r_1 + r_2)^*$. Assume a nonempty string $s \in r_1(r_1 + r_2)^* + r_2$. Then either $s \in r_2$ or $s \in r_1(r_1+r_2)^m$ for some nonnegative integer $m$. In the first case since $r_2 \subseteq (r_1+r_2)^*$, we are done, so assume $s \in r_1(r_1+r_2)^m$. But we know that $(r_1+r_2)^{m+1} \subseteq (r_1+r_2)^*$. Thus
$$(r_1+r_2)^{m+1} = (r_1+r_2)(r_1+r_2)^m = r_1(r_1+r_2)^m + r_2(r_1+r_2)^m$$
meaning $r_1(r_1+r_2)^m \subseteq (r_1+r_2)^*$.


Can an algorithm that yields $O(n^2)$ answers run in $O(n)$ time? My question may actually be more broadly described as: can I use the fact that an algorithm is expected to return $(O(f(n))$ answers to show that it may never run better than $O(f(n))$? I would intuitively assume yes, but I am not sure.

Examples of what I'm talking about is algorithms to calculate all the paths that pass through a set of points. I can easily calculate a higher bound $O(f(n))$ on how many those paths are. Will that tell me the algorithm must be no better than $\Omega(f(n))$?

Thanks

Can an algorithm that yields $O(n^2)$ answers run in $O(n)$ time?

Yes.  The following algorithm yields $O(n^2)$ answers (remember what $O(\cdot)$ means!) but it runs in time $O(n)$.

halt;

You probably meant to ask if an algorithm that yields $\Theta(n^2)$ answers can run in time $O(n)$. The answer to that is no. Whatever exact definition you choose for "yielding an answer", yielding one answer must take at least one computation step in any reasonable model of computation, so writing $\Theta(n^2)$ answers must take $\Omega(n^2)$ steps.


Clear, intuitive derivation of the fixed-point combinator (Y combinator)? The fixed-point combinator FIX (aka the Y combinator) in the (untyped) lambda calculus ($\lambda$) is defined as:

FIX $\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. x~x~y))$

I understand its purpose and I can trace the execution of its application perfectly fine; I would like to understand how to derive FIX from first principles.

Here is as far as I get when I try to derive it myself:

FIX is a function: FIX $\triangleq \lambda_\ldots$
FIX takes another function, $f$, to make it recursive: FIX $\triangleq \lambda f._\ldots$
The first argument of the function $f$ is the "name" of the function, used where a recursive application is intended. Therefore, all appearances of the first argument to $f$ should be replaced by a function, and this function should expect the rest of the arguments of $f$ (let's just assume $f$ takes one argument): FIX $\triangleq \lambda f._\ldots f~(\lambda y. _\ldots y)$

This is where I do not know how to "take a step" in my reasoning. The small ellipses indicate where my FIX is missing something (although I am only able to know that by comparing it to the "real" FIX).

I already have read Types and Programming Languages, which does not attempt to derive it directly, and instead refers the reader to The Little Schemer for a derivation. I have read that, too, and its "derivation" was not so helpful. Moreover, it is less of a direct derivation and more of a use of a very specific example and an ad-hoc attempt to write a suitable recursive function in $\lambda$.

I haven't read this anywhere, but this is how I believe $Y$ could have been derived:

Let's have a recursive function $f$, perhaps a factorial or anything else like that. Informally, we define $f$ as pseudo-lambda term where $f$ occurs in its own definition:

$$f = \ldots f \ldots f \ldots $$

First, we realize that the recursive call can be factored out as a parameter:

$$f = \underbrace{(\lambda r . (\ldots r \ldots r \ldots))}_{M} f$$

Now we could define $f$ if we only had a way how to pass it as an argument to itself. This is not possible, of course, because we don't have $f$ at hand. What we have at hand is $M$. Since $M$ contains everything we need to define $f$, we can try to pass $M$ as the argument instead of $f$ and try to reconstruct $f$ from it later inside. Our first attempt looks like this:

$$f = \underbrace{(\lambda r . (\ldots r \ldots r \ldots))}_{M} \underbrace{(\lambda r . (\ldots r \ldots r \ldots))}_{M}$$

However, this is not completely correct. Before, $f$ got substituted for $r$ inside $M$. But now we pass $M$ instead. We have to somehow fix all places where we use $r$ so that they reconstruct $f$ from $M$. Actually, this not difficult at all: Now that we know that $f = M M$, everywhere we use $r$ we simply replace it by $(r r)$.

$$f = \underbrace{(\lambda r . (\ldots (rr) \ldots (rr) \ldots))}_{M'} \underbrace{(\lambda r . (\ldots (rr) \ldots (rr) \ldots))}_{M'}$$

This solution is good, but we had to alter $M$ inside. This is not very convenient. We can do this more elegantly without having to modify $M$ by introducing another $\lambda$ that sends to $M$ its argument applied to itself: By expressing $M'$ as $\lambda x.M(xx)$ we get

$$f = (\lambda x.\underbrace{(\lambda r . (\ldots r \ldots r \ldots))}_{M}(xx)) (\lambda x.\underbrace{(\lambda r . (\ldots r \ldots r \ldots))}_{M}(xx))$$

This way, when $M$ is substituted for $x$, $MM$ is substituted for $r$, which is by the definition equal to $f$. This gives us a non-recursive definition of $f$, expressed as a valid lambda term!

The transition to $Y$ is now easy. We can take an arbitrary lambda term instead of $M$ and perform this procedure on it. So we can factor $M$ out and define

$$Y = \lambda m . (\lambda x. m(xx)) (\lambda x.m(xx))$$

Indeed, $Y M$ reduces to $f$ as we defined it.

Note: I've derived $Y$ as it is defined in literature. The combinator you've described is a variant of $Y$ for call-by-value languages, sometimes also called $Z$. See this Wikipedia article.


Sum of unique integers to cnf constraint As a study project I try to solve the kakuro puzzle problem using SAT SOLVER.
I can't really find an efficient way to convert the sum of k unique integers (1...9) to a CNF constraint.
What I had in mind:

for a group of k cells (1,...k) and a sum of j:

    find all subsets with size of k from P({1,2,...9})
    correctSubSets <- filter out all subsets that SUM(subset)!= sum
    AllVars <- EMPTY_SET
    for i in 1...k:
       add to current cnf a union of correctSubSets s.t each prefixed with i
       add to AllVars a union of correctSubSets s.t each prefixed with i
       for each pair in AllVars:
              if pair represents two different cells ix,jy:
                  if there is no sum s.t x,y part of it:
                     add to cnf (-ix, -jy) (not ix or not jy)

example for sum = 5 and k=2:
AllVars={11, 24, 13, 22, 12, 23, 14, 21}
cnf = (11, 13, 12, 14), (21, 22, 23, 24), (-11, -22), (-11, -21), (-11, -23), (-12, -21), (-12,-22), (-12,-24) ....... and more and more

I fill like this is very though to implement and not efficient at all.
how to solve it correctly?

Here's a strategy for solving Kakuro with a SAT solver.

Make a nine variables for each cell, each variable indicating whether that cell contains $1$, $2$, etc.
Add a exactly-one-out-nine constraint for the variables of each cell. You can do this naively in 37 clauses by adding a clause that at least one of the nine must be true ($x_1 \vee x_2 \vee \dots \vee x_9$) and 36 clauses that no pair of them may be true at the same time ($(\neg x_1 \vee \neg x_2) \wedge (\neg x_1 \vee \neg x_3) \wedge \dots \wedge (\neg x_8 \vee \neg x_9)$).
For each row/column in the puzzle add an at-most-one-out-of-k constraint in the manner above for all the variables encoding ones, twos, threes, etc in that row or column to ensure each row/column uses unique numbers.
For each row/column make a new set of variables $q_1, q_2, \dots $ that encode "contains $1$, contains $2$, etc". As an example, if a row contains cells $a, b, c, d$ then "contains $2$" would be $(\neg q_2 \vee a_2 \vee b_2 \vee c_2 \vee d_2)$ and $(q_2 \vee \neg a_2) \wedge \dots \wedge (q_2 \vee \neg d_2)$.
Now for each row/column, take the target sum and find all partitions using unique parts smaller than or equal to nine of it, excluding order, using exactly the right amount of parts that fit in the row/column. This may sound like a lot, but this is at worst 11 unique partitions for digits 1-9. Then for each partition introduce a new variable $p$. Suppose our target is $14$ and our partition is $14 = 8 + 3 +2 +1$. Then we add clauses $p \vee q_9 \vee \neg q_8 \vee q_7 \vee q_6 \vee q_5 \vee q_4 \vee \neg q_3 \vee \neg q_2 \vee \neg q_1$ and $(\neg p \vee \neg q_9) \wedge (\neg p \vee q_8) \wedge (\neg p \vee \neg q_7) \wedge (\neg p \vee \neg q_6) \wedge (\neg p \vee \neg q_5) \wedge\\(\neg p \vee \neg q_4) \wedge (\neg p \vee q_3) \wedge (\neg p \vee q_2) \wedge (\neg p \vee q_1)$

You get the idea. The variable $p$ is now an indicator variable for the combination $q_8, q_3, q_2, q_1$  being true. It may not be necessary to also include the negated terms for $q_9, q_7, q_6, q_5, q_4$, but it may speed up (or slow down) the SAT solver. Experiment with it.
Finally for all partitions variables $p_k$ of a row/column add a single clause $p_1 \vee p_2 \vee \dots \vee p_k$ indicating at least one of the partitions must hold.


Smallest number close to 0 in IEEE754 (64bits)? I thought the smallest number close to 0 would be : 0 00000000001 (exponent) 0000000000000000000000000000000000000000000000000000 (significand)

But this site (http://binaryconvert.com/result_double.html?hexadecimal=0000000000000001) shows that the smallest number close to 0 is : 0 00000000000 (exponent) 0000000000000000000000000000000000000000000000000001 (significand) According to what I know, when all components of exponent are 0 then the number must represent 0. Thus, this is not possible! How could this happen?

It's not true that when all components of the exponent are 0 then the number must represent 0. A (normalized) floating point number is composed of two parts: sign, exponent, and mantissa. The value of the number is
$$ \text{sign} \times 1.\text{mantissa} \times 2^{\text{exponent} + \text{base}}, $$
where the sign is $\pm 1$ (though encoded as a bit), and $\text{base}$ is a constant which depends on the format.

As you can see, $0$ cannot actually be represented at all! Some numbers, like zero, infinity, NaN and denormalized numbers have special representations. Zero, for example, is represented in IEEE 754 (the standard format) using zeroes for both mantissa and exponent.

In IEEE 754, an exponent of zeroes represents a denormalized number. In such numbers, instead of 1.mantissa we have 0.mantissa, and this allows representing numbers which are closer to zero (calculate and see!).


Are programming languages becoming more like natural languages? Can we study programming languages in the context of linguistics? Do programming languages evolve naturally in similar ways to natural languages?

Although full rationality, and mathematical consistency is essential to programming languages, there still is the need (especially modern languages) to make them readable and comfortable to humans.

Are programming languages evolving to become more linguistic and thus more natural? For example machine code, punch cards and assembly languages have given way to more readable languages like Ruby and Python etc.

When I say computer languages are becoming more natural, I don't mean they contain more 'words we have in english', I mean they seem to becoming more like a natural language, in terms of their complexity of grammer and ability to express meaning (for example, being able to eloquently describe a query from a database in both rational and human understandable ways).

What do you all think? Are programming languages becoming more like natural languages, and thus becoming applicable to the laws of Linguistics?

Or perhaps languages live on a spectrum, where on one side you have the extreme rational languages and the other the more creative. Maybe, programming and natural languages are identical and both just lie on this language spectrum (their only difference, perhaps being the 'thing' they are trying to give their meaning to).

Is there a connection between the (Babel Tower effect) separation of human languages and of computer langages? Do they become more diverse for the same reasons (i.e. to solve different problems within ever-evolving computer-systems/culture-systems etc.)?

Not really, no. Programming languages have become more like natural languages only in the sense of “words we have in english” (sic).

A key feature of programming languages is that they are not ambiguous. When you write a program and execute it, it has a well-defined meaning, which is its behavior. If you want to write a program that works as intended (a difficult objective), it is important that the behavior¹ of the program be as predictable as possible. Programming languages haven't made much difference in the wide gap towards natural languages.

Conversely, there has been work in bridging the gap from the other side: analyzing natural languages with the same tools as programming languages. This field is called natural language processing. These approaches have been pretty much discarded in favor of machine learning. I'll cite a passage in the Wikipedia article which is directly relevant here:

  Up to the 1980s, most NLP systems were based on complex sets of hand-written rules. Starting in the late 1980s, however, there was a revolution in NLP with the introduction of machine learning algorithms for language processing. This was due both to the steady increase in computational power resulting from Moore's Law and the gradual lessening of the dominance of Chomskyan theories of linguistics (e.g. transformational grammar), whose theoretical underpinnings discouraged the sort of corpus linguistics that underlies the machine-learning approach to language processing.

One way in which programming is evolving is that as we design larger and larger systems, source code is not always a good way of understanding them. For example, an Intel CPU is one of the most complex objects ever designed by Man, and its “source code” is not just a collection of text files, far from it. But the full design isn't evolving towards anything resembling a human language either. I don't know what the appropriate cognitive tools or metaphors here, and I don't think anybody knows just yet; ask again in a couple of centuries.

¹  Or rather the set of possible behaviors annotated with the circumstances under which they arise, but that's only adding one step of indirection in the modeling, so this isn't really relevant here.


Uniform-cost Search Problem Suppose that we take an initial search problem and we add $c > 0$ to the costs on all edges. Will uniform-cost search return the same answer as in the initial search problem?

Definitions: Uniform-cost search is also known as lowest cost first. Initial search problem can be any graph with a start and a goal state. You just apply the uniform cost search algorithm on the graph.

The shortest path may indeed change. This is not because of some property of the uniform cost search, but rather, the property of the graph itself. Note that adding a constant positive cost to each edge affects more severely the paths with more edges. Here is an example, where the shortest path has cost $5$:

Adding a cost of $1$ to each edge changes the shortest path in the graph as:

The original shortest path has a new cost of $10$, whereas the other path has a cost of only $9$. Therefore, any optimal shortest path algorithm, such as Dijkstra's or uniform cost search, will find a different shortest path.

The shortest path will not change if it also has the least number of paths among all paths from source to destination. If the shortest distance is $d_{min}$ and $k_1$ edges, and there is some other path with distance $d_{min} + \Delta$ with $k_2$ edges ($k_2 < k_1$), it can be shown that adding any $c > \frac{\Delta}{k_1 - k_2}$ to all the edges will change the shortest path, and therefore your result.

Scaling the edges by a constant positive factor (multiplying all edges by $c>0$) will not change the shortest path.


prove every language got a language that is harder I am prety stuck over here:

prove or disprove that every $L$ got $L'$ s.t $L'\geq L$ and for every $L''\geq L$
$L''\ngeq L'$
basically it means L' is the hardest...

my intuition tells me that this is correct, but I cant prove why.
I tried to prove using counting but got stuck:

we got $\aleph_0$ pairs of functions that we can use in the reduction for both ways

we got $\aleph$ languages so there must be a language that got a function to compute the redaction in one way and doesnt got a function for the reduction to the other way

Its feels terribly incorrect any help will be appreciated
EDIT:
I just realized that I didn't write the question correctly please read it again.

The halting problem for a class of machines that can decide $L$ is always harder than $L$. You already know this when $L$ is computable and the proof of the more general result is essentially the same. For every $L$, you need to think of a class of machines that can decide $L$.


How often can a linear speed sort succeed? Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$.

What kind of bounds can we place on the success rate of such an algorithm? It obviously can't succeed 100% of the time, since then it would just be an ordinary list sorting function and it would have to be $\Omega(n \log n)$. The answer isn't 0% success, since you can check if it sorted in $\mathcal O (n)$, and so you can sometimes succeed.

Of course, the success rate depends on how we are choosing the list. The uniform case would be best, but any kind of bounds would be helpful.

David Eppstein gave away the answer: an $O(n)$ comparison-based algorithm will succeed on a negligible fraction of permutations. One way to see that is that an $O(n)$ algorithm can only take care of $2^{O(n)}$ different input permutations, compared to the $n! = 2^{\Omega(n\log n)}$ possible ones.


Show that a language is RE or recursive Consider these 2 languages:

  $L_{\ge5} = \left \{ \left< M \right> : M \text{ accepts at least 5 strings} \right\} $

  $L_{<5} =  \left \{ \left< M \right> : M \text{ accepts fewer than 5 strings} \right\}$

Are these recursive, R.E., or not R.E. sets (languages)?

I would say that they are not recursive, based on applications of Rice's Theorem.

For the first case $L_{e}= \left \{ \left< M \right> :L(M)= \emptyset \right \} \notin L_{\ge5} $ and $L_{\ge5}$ are not empty. For example, I define $L= \left \{ \left< M \right> : M \text{ accepts all palindromes} \right \}$, which is not finite set and accepts an infinite number of strings.
For the second case I would do the same thing. I have $L_{e}=\left\{ \left< M \right>: L(M)= \emptyset \right\} \in L_{<5}$ and $L=\left\{ \left< M \right>:M \text{ accepts all palindromes} \right\} \notin L_{<5} $

So I would say that both are not recursive. Is my reasoning correct?

Now about the R.E. of the languages I don't have an idea of how I can prove it, this should be the beginning (if L is not RE it can't be recursive), how can I check if they are RE or not?

From the definition: "$L$ is RE $\iff$ there exists a TM $M$ that accepts $L$", so I just have to define a TM that accepts each language?

$L_{\geq5}$ is RE. Basically, given a machine $M$, you iterate through all strings, starting with all of length 0, then length 1, etc. You simulate $M$ and test if the current string $s$ is accepted by $M$. If it is, then you increment some counter. If the counter ever hits 5, you accept. There's no guarantee that this will terminate, which is why it's RE and not recursive. There is a guarantee, however, that it will terminate for any input machine $M$ that does accept 5  or more strings.

We know from Rice's theorem that $L_{\geq5}$ is not recursive, and since it is RE, then we know its compliment is not RE. So $L_{<5}$ is neither RE or recursive.

Intuitively, you could iterate through all strings, but there would never be a point where you could say "Based on the strings I've seen so far, I know that this machine accepts less than 5 strings." Even if you accept less than 5 so far, there's no way of knowing that there aren't larger strings which would be accepted.


Efficiently count frequency of n-grams at start of words I have a text file with all possible 5-grams (26^5 = 11.881.376) organized in rows as:

aaaaa
aaaab
aaaac
aaaad
.....

and I have a txt file (organized in rows) with all English words. I have to find how much time every 5-gram is at the beginning of a word. I'm using this code:

def frequency(five-grams, dict):
    result = {}

    for gram in five-grams:
        freq = 0
        for word in dict:
            if word.startswith(gram):
               freq = freq + 1

        result[gram] = freq

    return result

However this method takes too long (after hours the algorithm is still running). Is there a more efficient and faster method?

There is a 11.881.376 times faster method. Instead of for every 5-gram looping over the entire dictionary, loop over the dictionary once, and for every word determine with what 5-gram it starts and then increment the counter for that particular 5-gram.


Why does if A is a spanning tree which doesn't have $e_1$ then $A\bigcup\{e_1\}$ has a unique cycle? I am studying the algorithm of Sollin and we recently studied a lemma:
Let be G a graph which values are diffferent on the edges.

We sort the edges  $e_1,e_2,...e_m$ such as $v(e_i)<v(e_j)$
Every tree of minimal value has at least $e_1$ et $e_2$

Proof
let be A a spanning tree which doesn't have $e_1$
$A\bigcup\{e_1\}$ has a unique cycle
let be $e_i \in$ cycle, $e_i\ne e_1$ then $A\bigcup\{e_1\}-\{e_i\}$ is a tree which value is < $v(A)$ because $v(e_i)>v(e_1)$

I don't understand why would $A\bigcup\{e_1\}$ would have a unique cycle?
Do you have a justification? A graphical example?

In a tree, there is exactly one path between any pair of vertices. When you add edge e1 you close that unique path to form a unique cycle.


What happens when thread is created When working on Linux what happens when a thread is created? It is a separate execution flow. Does each thread have their own code section? Personally I don't think threads would be able to share code section even if it's the same section. Say if the number of threads being created is dynamic. How is the memory allocated for each thread? Will the memory foot print, especially code section, increase as threads are created?

(Although you asked about Linux, which would be off-topic, the same principles apply on most operating systems, and general principles are on-topic here.)

Threads share their code section. In many systems, even separate tasks that are executing the same program can share their code section, because the code sections are read-only, so whatever one task does won't affect the other task. I don't know how to explain this better because you don't say why you don't think it would be possible. It is possible, and it's routinely done.

Each thread has its own set of register values, including the program counter. Each thread also has its own call stack. Having its own program counter and call stack (in a way, the program counter is the top of the call stack) pretty much defines a thread. Multiple threads of the same task have program counters that each point at some place in the shared code section.

Creating a thread requires allocating memory to store its stack, and to store its register values when switching between threads. It doesn't affect the code section.


Determine if two grammars for the same language are ambiguous I'm reading the book: Formal Syntax and Semantics of Programming Languages. I don't understand this exercise:

Consider the following two grammars, each of which generates strings of correctly balanced parentheses and brackets. Determine if either or both is ambiguous. The Greek letter ε represents an empty string.
<string> ::= <string> <string> | ( <string> ) | [ <string> ] | ε
<string> ::= ( <string> ) <string> | [ <string> ] <string> | ε

Consider this a hint.  As I write in my comment, what is the syntax tree of ()()()?  Does the first two pairs belong to the leftmost of the <string><string>-part, or does the two latter pairs belong to the rightmost?

$$ \left(
 \overbrace{  \overbrace{ () }^\text{string} \quad
 \overbrace{ () }^\text{string}}^\text{string}
\quad \overbrace{ () }^\text{string} \right)
\text{ vs }
\left(
 \overbrace{ () }^\text{string}\quad
 \overbrace{  \overbrace{ () }^\text{string}\quad
 \overbrace{ () }^\text{string}}^\text{string} \right)
$$


Approximability of the edge-disjoint shortest paths problem In the edge-disjoint paths problem (EDP), we are given a (possibly directed) graph $G=(V,E)$, and a set of distinct source-sink pairs $\{ (s_i,t_i) \mid 1 \leq i \leq k \}$, and we want to maximize the number of pairs that can be simultaneously connected in an edge-disjoint manner. When we add the constraint that the paths need to be shortest paths, we get the edge-disjoint shortest paths (EDSP) problem.

According to [1], the EDSP problem is hard for a graph with unit edge lengths, even when the graph is planar. Furthermore, it claims this is so for both directed and undirected graphs.

  What is known about the approximability of the EDSP problem?

I'm especially interested in results for undirected graphs. In [2], the authors seem to only consider variants of the EDP problem, but not the EDSP problem. Further following the references, it seems like the EDP problem has been studied extensively.

[1] Eilam-Tzoreff, Tali. "The disjoint shortest paths problem." Discrete applied mathematics 85.2 (1998): 113-138.

[2] Guruswami, Venkatesan, et al. "Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems." Journal of Computer and System Sciences 67.3 (2003): 473-496.

Below, we will assume there is exactly one shortest path between every pair of vertices. The following will also work for the case where $O(\log n)$ pairs of vertices have $O(1)$ shortest paths between them.

For each pair $\{s_i , t_i\}$ let the shortest path be $P_i$, $\forall i \in \{0,1\ldots k\}$. The shortest path can be found in polynomial time. Let us number the edges $e_1, e_2, \ldots e_q$. Let the maximum number of pairs $\{s_i , t_i\}$ for which there exist disjoint-shortest paths be $\text{OPT}$.

Now, we reduce this problem to an optimization problem.

Define a matrix $A_{k\times q}$ such that $A_{ij} = 1 \text{ if } e_j \in P_i$.

$$
\text{OPT} = \max \sum_{i=1}^k x_i \quad
\\
\text{s.t } Ax \leq \mathbf{1}_{n\times 1} \\
x \in \{0,1\}
$$

Let the optimal fractional solution for the above problem be $\text{OPT}_{\text{LP}}$ and $\text{OPT}_{\text{LP}} \geq \text{OPT}$. The above LP has an integrality gap of $O(\log k)$. Therefore, $O(\log k) \cdot \text{OPT}_{\text{IP}} \geq \text{OPT}_{\text{LP}}$. Thus $ O(\log k) \cdot \text{OPT}_{\text{IP}} \geq \text{OPT}$. Hence we obtain a $O(\log k)$ approximation algorithm.

The proof for the integrality gap result can be found in Vazirani's "Approximation Algorithms", chapter 20. Multicut in General Graphs.


Why is this language a regular language? Came across this in a book, and I'm wondering why the following language is regular?

$$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$

Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a regular language because it can be expressed by a regular expression $$a*$$, and $$ \{ww^R: w \in \{a,b\}^3\} $$ is a regular language because it is finite; therefore the union of the two regular languages makes a regular language?

This is not an union of two regular languages! It's a concatenation. Note the difference,

Union: $L_1 \cup L_2$
Concatenation: $\{ab : a \in L_1 \wedge b \in L_2\}$.

That said, your other observations are correct, and indeed the concatenation of two regular languages is also regular itself. You can prove this by  constructing two NFAs for the regular languages and connecting the accepting states of $L_1$ to the starting states of $L_2$ by an $\epsilon$-transition.


How to prove that $3$-Spanning-Tree decision problem is $NP$-Complete I am not sure what problem may reduce to $3$-Spanning-Tree where $3$-Spanning-Tree is defined as a decision problem which given an undirected graph $G$ determines if there is a spanning tree of $G$ in which every vertex has degree no larger than $3$.

I have already done this for $2$-Spanning-Tree using a reduction from Hamiltonian paths as this reduction seemed clear. A spanning tree where each node has degree at most $2$ is essentially a Hamiltonian path in the given graph.

I am not sure if I can extend this idea to $3$-Spanning-Tree or need to try a different approach entirely, any help would be welcome.

Reduce from Hamiltonian path, attach a dummy vertex to each original vertex. After removing dummy vertices, each original vertex would have degree at most $2$ in the (remaining) of the spanning tree. A connected graph every vertex of which has degree at most $2$ is a path or a cycle.


Minimum XOR for queries I was asked the following question in an interview.

Given an array $A$ with $n$ integers and an array $B$ with $m$ integers. For each integer $b \in B$ return and integer $a \in A$ such that $a \otimes b$ is minimum, where $x\otimes y$ for to integers $x$ and $y$ is the bitwise xor operation of $x$ and $y$.

For example:

Input:

A = [3, 2, 9, 6, 1]
B = [4, 8, 5, 9]

Output

[6, 9, 6, 9]

Because when 4 is XORed with any element in A minimum value will occur when A[I] = 6

4 ^ 3 = 7
4 ^ 2 = 6
4 ^ 9 = 13
4 ^ 6 = 2
4 ^ 1 = 5

Here is my brute force solution in python.

def get_min_xor(A, B):

    ans = []

    for val_b in B:
        min_xor = val_b ^ A[0]

        for val_a in A:
            min_xor = min(min_xor, val_b ^ val_a)
            # print("{} ^ {} = {}".format(val_b, val_a, val_b ^ val_a))

        ans.append(min_xor ^ val_b)

    return ans

Any ideas on how this could be solved in sub O(MxN) time complexity?

I had the following idea in mind.
I would sort the array A in O(NlogN) time then for each element in B. I would try to find it's place in the array A using binary search.Let's say B[X] would fit at ith position in A then I would check the min XOR of B[X] ^ A[i-1] and B[X] ^ A[i+1]. But this approach won't work in all the cases. For example the following input

A = [1,2,3]
B = [2, 5, 8]

Output:

[2, 1, 1]

Here is the trie based solution

class trie(object):
    head = {}

    def convert_number(self, number):
        return format(number, '#032b')

    def add(self, number):
        cur_dict = self.head

        binary_number = self.convert_number(number)

        for bit in binary_number:

            if bit not in cur_dict:
                cur_dict[bit] = {}
            cur_dict = cur_dict[bit]

        cur_dict[number] = True

    def search(self, number):
        cur_dict = self.head

        binary_number = self.convert_number(number)

        for bit in binary_number:
            if bit not in cur_dict:
                if bit == "1":
                    cur_dict = cur_dict["0"]
                else:
                    cur_dict = cur_dict["1"]
            else:
                cur_dict = cur_dict[bit]

        return list(cur_dict.keys())[0]

def get_min_xor_with_trie(A,B):

    number_trie = trie()

    for val in A:
        number_trie.add(val)

    ans = []

    for val in B:
        ans.append(number_trie.search(val))

    return ans

Using Trie Data Structure, you can solve this problem in $O(m + n)$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values).

Let say we know that all integers in $A$ are 32-bit values. Use the following steps:

Create an empty trie. Every node of trie may contains at most two children
for 0 and 1 bits.
Insert all values in $A$ into the tree in $O(32 \times m) = O(m)$
For each value in $B$, traverse the tree from the leftmost bit. If a bit doesn't match with child of a middle node, continue the traverse using the existing child until you reach a leaf. Traversing finishes in $O(32 \times n) = O(n)$

Which in total, the complexity is $O(m + n)$.


Algorithm for sorting with constraints I've got 30 elements which has to be  grouped/sorted into 10 ordered 3-tuple.
There are several rules and constraints about grouping/sorting.
For example: Element $A$ must not be in the same tuple same unit $B$.
Element $C$ must not be right in front of element $A$, etc.

I am searching for an approximated algorithm:

We don't need to achieve the exact optimum
It is OK for some rules not to be satisfied, if it helps to fulfill more rules.

Do you know of any algorithm/proceeding that solve this problem or a similar one?
I fear to solve it in an optimal way, you have to try out every possible solution-> $2 ^ {30}$

EDIT: Sorry for the bad explanation. I am trying to make it a bit clearer:
I got 30 elements for example: $\{1,2,3,\ldots,30\}$.
I need to group them into 3-tuples so that i get something like: $(1,2,3)$, $(4,5,6)$,$\ldots$,$(28,29,30)$.

There are several constraints. For example:

1 cannot precede 2 in an ordered tuple, so, for instance  $(1,2,3)$ is not a valid tuple.
5 must be together with 4.

Those constraints can be broken and its possible that there is no solution where all rules can be fulfilled. An solution is considered as good if the amount of rules broken is "low".

Hope that makes it clearer and thanks for the help so far.

The question of whether we can solve this problem without violating any rules is a set cover problem.

In particular, the universe is $U=\{1,2,\dots,30\}$, and each possible tuple $t_i$ that follows all the rules corresponds to a set $S_i \subseteq U$.  In this way, we get many sets $S_1,S_2,\dots,S_n$.  We want to know whether there is some 10 of these sets whose union is all of $U$.  That's the set cover problem.  There are well-known hardness results and approximation algorithms for the set cover problem.

Now let's introduce the opportunity to violate some of the rules.  Associate to each tuple $t_i$ a cost $c_i$.  If the tuple $t_i$ follows all the rules, there is no cost for using that tuple: $c_i=0$.  If the tuple $t_i$ violates some of the rules, we'll set $c_i$ to denote the cost of those violations (for instance, if each rule that is violated costs \$1, then $c_i$ can be set accordingly).  In this way we get a collection of sets $S_1,S_2,\dots,S_n$ with associated costs $c_1,c_2,\dots,c_n$ for each of them.

Now our goal is to find some 10 of those sets whose union is $U$, and where the sum of their costs is minimized.

This can be formulated as an integer linear program (ILP).  In particular, we'll introduce $n$ integer variables $x_i$; the intended meaning is that $x_i=1$ means that $S_i$ is one of the 10 sets that were selected, and $x_i=0$ means $S_i$ was not selected.  Now we want to minimize

$$\sum_i c_i x_i,$$

subject to the constraints

$$\sum_{j \in S_i} x_i \ge 1 \text{ for each $j=1,2,\dots,30$}$$

(where the sum is over all $i$ such that $j \in S_i$) and $0 \le x_i \le 1$.  Now you could throw any ILP solver at this problem and see what solution it turns up.


How to prove that $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\} $ is irregular? We know that $L=\{0^i 1^{j^2}|i> 0,j\ge 0\} $ is irregular (by the Pumping Lemma), we have to use it to prove two things:

$L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\} $ is irregular.
$L_1$ is making all the three conditions (I don't know the exactly word at English for this...) of the Pumping Lemma.

For the first one - how do I prove it by the Pumping Lemma?

For the second - I have no idea and I'd like to get ant help!
(Because I can choose any word that I want, and I need to prove it for all the words in $L$).

Thank you!

You don't need to use the pumping lemma to prove that $L_1$ is irregular. You can also make use of the closure properties of the regular languages.

We know that regular languages are closed under intersection. That is, if $L_1$ and $L_2$ are regular languages then $L_3 = L_1\cap L_2$ is also a regular language.

A nice way to prove that a language is irregular is to assume that it is regular and reach a contradiction using the closure properties of the regular languages.

For example consider the language $L_p = \{1^p: p\text{ is prime}\}$ we know that this is an irregular language. Let's consider $L_q = L_p \cup 0^*$. How can we prove that this language is irregular?

Let us assume for the purpose of contradiction that $L_q$ is regular, hence $L_q\cap 1^*$ is also a regular language since $1^*$ is a regular language. But wait.. The intersection is $L_p$ (the primes) which is not a regular language. Contradiction. So $L_q$ is irregular.

Your problem can be solved along the same lines.


Is this a correct grammar for untyped lambda calculus? I am trying to write a recursive-descent parser for untyped lambda calculus. While researching the way of formulating the grammar, I managed to put together something like this:

without left-recursion:
TERM         -> APPLICATION | ABSTRACTION
ABSTRACTION  -> LAMBDA LCID DOT TERM
APPLICATION  -> ATOM APPLICATION'
APPLICATION' -> ATOM APPLICATION' | ε
ATOM         -> LPAREN TERM RPAREN | LCID
LCID         -> 'a' | 'b' | ... | 'z'
DOT          -> '.'
LAMBDA       -> 'λ'

I assume that for writing the parser I do not necessarily need the productions that only expand into terminals.

Can this grammar be used to write a recursive descent parser that only does 1-token lookups? What would be the resulting AST for (λx.x)(λy.y) ?

Your grammar looks fine. You can make a recursive descent parser for it.

The AST for (\x.x)(\y.y) is, if I got everything right,

term
  application
    atom
      lparen
      term
        abstraction
          lambda
          lcid
            x
          dot
          term
            application
              atom
                lcid
                  x
              application'
                eps
      rparen
    application'
      atom
        lparen
        term
          abstraction
            lambda
            lcid
              x
            dot
            term
              application
                atom
                  lcid
                    y
                application'
                  eps
        rparen
      application'
        eps


monotonically increasing codeword length in optimal (maybe Huffman) code for alphabet with monotonically decreasing frequencies I'm working on exercise 16.3-5 of CLRS:

  Prove that if we order the characters in an alphabet so that their frequencies are monotonically decreasing, then there exists an optimal code whose codeword lengths are monotonically increasing.

Perhaps I'm misunderstanding the question, but how can the lengths be monotonically increasing? In order for the code to be optimal, the binary tree representation must be full (like the StackExchange CS logo), e.g. every node with degree either 0 or 2 (if it's not full, then it cannot be optimal, since the code could be shortened by promoting the child of a node with degree 1, as discussed in exercise 16.3-2). That means there exists at least one pair of leaf nodes at the same depth, and depth is the same thing as the codeword length.

The Huffman code is optimal, and it always begins by merging two characters, so again there's at least a single pair of leaf nodes that will be at the same depth and hence same codeword length in the resulting tree.

Is it a typo, e.g. should it read "monotonically increasing except for the final two characters, which have the same length" or maybe even "monotonically non-decreasing"?

In fact, there is a trivial counterexample: suppose there are only two characters 'a' and 'b', with frequencies 0.6 and 0.4 respectively. The optimal code is clearly 'a'=0 and 'b'=1, or vice versa. However, the codelength is 1 for both characters, so clearly is not monotonically increasing.

I misunderstood the phrase "monotonically increasing". It actually means the same thing as "non-decreasing", as explained on p 53 of the book. The phrase is different from "strictly increasing", also defined there, which is what I had thought it meant.

With "monotonically increasing" meaning "non-decreasing", the exercise makes a lot more sense.


Infinite sequence of graphs http://jgaa.info/accepted/2011/HasheminezhadMcKayReeves2011.15.3.pdf
 Hello I stumbled upon this paper. On page $4/20$ the figure shows an infinite sequence of $5-$regular, connected planar graphs. But they do not define it rigorously. The first graph of the sequence is clearly the icosahedron, and I feel that the next ones are constructed by "gluing" copies of $D_1$ but the only way I thought of constructing $D_k$ from $D_{k-1}$ and an icosahedron, would be removing a vertex from the border of its outer face. Then we remove a vertex from the border of the outer face of a copy of icosahedron and then we connected the vertices of degree $4.$ But this would leave us with less vertices than the graphs shown there.
 Is my construction ok? Also which procedure gives us the sequence shown on the article?
 thanks in advance.

Take the graph $D_1$, and cut the bolded edge in the middle, so that each of its two halves has degree 3 (including the bolded edge). Take $k$ copies of this, and paste them along bolded edges in a cyclic fashion. You get $D_k$.


Dijikstra's algorithm with "hull" value catch Whilst preparing for the CCC(Canadian Computing Competition), I encountered CCC 2015 Seniors problem 4, linked here.

Anyway, the problem describes a set of vertices(points) numbered from $1$ to $N$, and a  set of pathways $1$ to $M$, with pathway $p_i$ connecting two points
$a_i,b_i$, taking time $t_i$. The goal of the problem is to find and print out the minimum time required to get from a specific point of $a$ to point $b$, along the pathways.

This looks like a Dijkstra's algorithm implementation... however there is a catch.

For every such pathway  $p_i$ connecting two points $a_i,b_i$, not only is there a time $t_i$, there is also a hull value $k_i$. You travel by water along the pathways, and your ship has a hull $K$ to begin with. From point $a$ to point $b$, the sum of the hull values along your chosen pathway must not be greater than $K$, otherwise your ship will sink, i.e the pathway is no longer valid.

For this problem, what I first tried to do was to implement it similar to how a normal Dijikstra's algorithm would be implemented.

This passed $9/15$ test cases on the grader, which I am quite proud of for a first attempt. Time wasn't an issue as it usually was, but I am getting Wrong Answer.

I then realised that I cannot just save the minimal hull value for each vertex, as each valid path has a different hull value sum. I have to implement a sort of queue/stack like structure and distinguish between each path.

However, the second I do that, I get codes that score even fewer points than my initial attempt. Time Limit becomes an issue, and I get even more Wrong Answer test cases on the practice CCC grader.

I spent two days already on this problem, and don't seem to be making any progress.

Any help will be appreciated.

Use the product construction to build a graph on $NK$ vertices and $MK$ edges, where each vertex records both which island you are at and how much hull you have left.  Then, use Dijkstra's algorithm on that graph.  The graph can be built on the fly and does not need to be constructed explicitly.


CFG for a rather complex language I'm trying to construct a context free grammar for the language $\{a^ib^j:2i\neq3j+1\}$. I found that when $j$ is even, there are no problems. When $j$ is odd, there are some constraints on $i$. Now these are some examples of words that may NOT be parsed by the CFG:

aab
aaaaabbb (5 a's and 3 b's)
aaaaaaaabbbbb (8 a's and 5 b's)
...

But I'm completely stuck on finding a CFG for this language. Are there any tips that might help me in finding CFG's for a more complex language? I'm able to find the CFG for simpler languages, but I find this one particularly hard.

Try constructing CFGs for the two related languages
$$
\{a^ib^j : 2i > 3j + 1\}, \quad \{a^ib^j : 2i < 3j+1\}.
$$
This can be accomplished by constructing a grammar for
$$
\{a^ib^j : 2i = 3j + 1\}
$$
and some related languages.


Why are states called locations in Timed Automata? I started reading about timed automata lately. In the definition, they have locations instead of states as in automata theory. Can anyone explain why is this?

It is mainly a matter of avoiding ambiguity.

At any moment in a Timed Automaton (TA), available transitions depend on the current location and the current clock valuation.
Thus, the current state is the combination of the current control state (or location) and the current clock valuation.

If you see a Finite State Automaton as a TA with $0$ clocks, only one clock valuation is possible, and it is the same for every states.
The clock valuation is thus irrelevant, and the current state is entirely determined by the current location.
To simplify the vocabulary, we identify both terms.

The word "location" is often used because it is hard to mistake it for "state".
But it is not uncommon to see "discrete state" instead of "location", and "extended state" instead of "state".


Removing arithmetic within recurrences A similar question was asked here: Solving recurrences using substitution method, but I am still somewhat hazy as to how this process works.

Say, for $T(n) = T(\lceil n/5 \rceil + 36) + n \log n$

Statement: we wish to prove that $T(n) \le 5 \ n \log n$ for $n \ge 0$

Base case, $n = 0$ and $T(0) \le 0$

$T(0) = 0$

$T(0) \le 0 \log 0$

Holds, since $0 \log 0 = 0$

Inductive step, for $n > 0$

(Inductive Hypothesis is: $T(n) = 5 \ n \log n$)

$T(n) = T(\lceil n/5 \rceil + 36) + n \log n$

$\le 5 \, (\lceil n/5 \rceil + 36) \log (\lceil n/5 \rceil + 36) + n \log n$ by Ind. Hyp.

$\le 5 \, (n/5 + 36) \log (n/5 + 36) + n \log n$ by property of ceiling

$= (n + 180) \log ((n + 180)/5) + n \log n$ by algebra

This is the point where it gets hazy. According to the link, what I should do is say that for all $n \ge 180$, then

$\le (n + n) \log ((n + n)/5) + n \log n$

$= 2n \log (2n/5) + n \log n$

$= 2n \, [\log n + \log (2/5)] + n \log n$

$= 2n \log n + 2n \log (2/5) + n \log n$

$= 3n \log n + kn$ where $k = \log (2/5) * 2$

$\le 5n \log n$

Does this complete the proof? Or am I in error? I still don't understand why I can just set $n \ge 180$ and therefore get rid of the irritating arithmetic within the log.

The link doesn't say what you say it does.  I don't see the number 180 appearing anywhere on that link.  And that link doesn't say the purpose is to prove $T(n) \le 5 n \log n$ for all $n \ge 0$; it says to prove that $T(n) = O(n \log n)$.  Check the definition of big-O notation; it doesn't require proving $T(n) \le c n \log n$ for all $n \ge 0$; it suffices to prove it for all $n \ge 180$ (or for all $n \ge n_0$ for any other constant $n_0$ of your choice).


Conditions for LL(1) grammar One of the conditions for A → α | β to be LL(1) grammar states that

  If β → ε in one or more steps then α doesn't derive any string beginning with a terminal in FOLLOW(A). Likewise If α → ε in one or more steps then β doesn't derive any string beginning with a terminal in FOLLOW(A).

I couldn't understand what is the intuitive meaning of this condition and why this condition should hold? I could easily understand if an example is provided for the answer.

Considering the above condition, should α derive a string beginning with a terminal in FOLLOW(A), then it becomes impossible to determine which derivation will be used to produce this symbol with lookahead limited to one symbol.

For instance, should $\mathrm{s}$ be the symbol that is both on FIRST(α) and FOLLOW(A), and $x$ the leftmost substring already parsed, then the following sequences are both possible:

$xA$ω $ \Rightarrow x$βω $ \Rightarrow^* x$ω $ \Rightarrow^* x\mathrm{s}$…

$xA$ω $ \Rightarrow x$αω $ \Rightarrow^* x\mathrm{s}$…ω

Even if the grammar is not ambiguous, you can't decide which path to take by reading just $\mathrm{s}$.


How do I compute the huge numbers which occur in el gamal decryption? I'm trying to do decryption using el gamal. The formula to get the message M is
$$ M=\frac{b}{a^x} mod \:P $$ In one case, we may have $$ M=\frac{18}{62^{62}} mod \: 71 $$ This value cannot be computed on a calculator as $62^{62}$ gives an infinite value. How do we get the value of M?

Two techniques will be of use here and in many similar problems. To find $(1/a)^b\pmod n$,

First, compute $1/a = a^{-1}\pmod n$. In your example, compute $62^{-1}\pmod{71}$, namely, the modular inverse of $62\pmod{71}$. That happens to be $63$.
Then use repeated squaring to find $(1/62)^{62}\equiv63^{62}\pmod{71}$, which will be 8. This relies on the fact that $a^{62} = a^{32+16+8+4+2}=(a^{32})(a^{16})(a^{8})(a^{4})(a^{2})$ where, reading from the right, each value is the square of the preceding one, meaning that you can find $a^{62}$ using 9 modular multiplications, rather than 61.


How to find the minimal path cost from left edge of a grid to the right edge using dynamic programming? I need to find the minimal path cost from left edge of a $n\times n$ grid to the right edge where each node has some non-negative weight $cost(i,j)$. $i$ represents horizontal coordinates while $j$ represents vertical coordinates. Only the following movements are allowed in the grid:
  $$
(i,j)\to(i+1, j-1) \quad\text{aka diagonal down}\\
(i,j)\to(i+1, j) \quad\text{aka right}\\
(i,j)\to(i+1, j+1) \quad\text{aka diagonal up}\
$$
  The algorithm must run in $\Theta(n^2)$ time and use dynamic programming.

I thought:

1) first to select the minimal cost node in the left-most column, that is find $min(cost(i, 1))$. Let the node be $s$ (start node).

2) Now we can use Bellman-Ford algorithm as described here (page 53) in order to find the minimal cost path from $s$ to any other node. The recurrence for Bellman-Ford would be:
$$
opt(i,j) = cost(i,j) + min(opt(i+1,j-1),\\ opt(i+1, j),\\ opt(i+1,j+1))
$$

3) We'd get a $n\times n$ matrix in the end where the right-most column would represent the right-most edge of the grid. Therefore the minimal cost path from left edge to the right edge would be the minimal cost in the right column.

Is my logic on the right track? I'm really not sure regarding the steps 1) and 3). Also because Bellman-Ford calculates edges costs do I need to perform any reduction in this algorithm because costs are not stored on edges but rather on nodes?

You can solve this problem filling the following table.

Let's say that $cost(row,col)$ is the minimal cost that can be achieved starting from one node on the leftmost edge of the grid and ending in the cell $(row, col)$, only performing valid operations.

The answer to the problem will be the minimum among all $cost(i,j)$ where $j=last\_col$. Notice that table $cost$ table is the same as $opt$ table, but now you have the proper semantic of it's entries, so it's easy to fill base values, and extract final values.

Step 1:
Base values: Fill first column entries with there current value. i.e $cost(i,j)$ where $j=0$. It is $cost(i,0)=value(i,0)$ since the only way you can reach node $(i,0)$ starting in a leftmost node and performing valid operation, is starting in the node itself.
Step 2:
The same you described before. This holds, because you can only get nodes on the $j^{th}$ column from the $(j-1)^{th}$ column, and since you are filling $cost$ table in increasing order of columns, previous values will be computed when you need to compute current values. [This is dynamic programming]
Step 3:
As I said before, and you said too, return the minimal value among all entries in the last column of $cost$ table.

Why Bellman Ford (BF) works here in the way you do it.

BF algorithm finds shortest path in a graph from a single source to every other node inside the graph. In the $k^{th}$ step BF have already computed shortest path starting from source node $S$ to every other node using at most $k$ edges.

Let's transform our problem into a valid instance for BF, and the let's modify BF to run in $O(n^2)$.

Let's say we convert each cell of the grid into a node, and you put an edge between node $u$ and $v$ if the transition from $u$ and $v$ is valid. Let the cost of edge between $u-v$ be the original cost of the cell $v$, so moving through this edge adds to the overall cost getting into node $v$, as we expect.

Now we have two problems.

Problem 1, the running time of our algorithm will be $O(nodes \cdot edges)$ where $nodes$ is $n^2$ and $edges$ is $O(nodes) = O(n^2)$ so overall complexity will be $O(n^4)$.
Problem 2. There are several sources, so we need to run BF starting at every source, and this increase the overall complexity by a factor of $n$.

Let's get rid of both problems, starting from problem 2. If you add an extra node connected to every node at the first column, you simulate the process of starting at every node in one run. Look at the following image for more understanding. I didn't pain all connection but just a few.

To get rid of the first problem, you need to exploit the structure of our graph. It is not so general. You can only reach nodes in the $k^{th}$ column in the $k^{th}$ step, and since there is no backward edge, in this step only nodes in this column needs to be updated. So overall complexity will be $O(nodes) = O(n^2)$.


Dynamic subtraction game I came across the following dynamic subtraction game:

  There is one pile of n chips. The ﬁrst player to move may remove as many chips as
  desired, at least one chip but not the whole pile. Thereafter, the players alternate moving,
  each player not being allowed to remove more chips than his opponent took on the previous
  move. What is an optimal move for the ﬁrst player if n = 44? For what values of n does
  the second player have a win?

Now, I know how to solve basic subtraction games, i.e., when both the players are allowed the same set of moves throughout the game (e.g., subtract only 1, 2, or 3 throughout the game). But in the game mentioned above, this set of possible numbers for subtraction is not fixed. I have no clue how to go about solving this question. Any kind of help would be appreciated.

Hint: A player loses if they are presented with a pile of size 1. If presented with a larger pile, what should you do if it's the first move of the game?

Here is a more general solution, which will be applicable in other cases.

You can find the winner (and even the Sprague-Grundy function) using dynamic programming. Each state of your game consists of a pair $(n,B)$, where $n$ is the number of chips, and $B$ is an upper bound on how many chips you're allowed to remove. I'll let you figure out the edges of this dag and the starting state. Now you scan the graph from the sinks up: a sink (state with no outgoing edges) is a LOSE state (from the point of view of the player whose turn it is to play). A state leading only to WIN states is a LOSE state, otherwise it's a WIN state, and any edge pointing at a LOSE state is a winning move.

It's probably more challenging to find a general formula for which player wins the game given $n$, but one way would be to compute it empirically for several values of $n$ (or more generally, of $n$ and $B$), figure out a formula, and prove your formula.


How to represent calculable real numbers? Suppose I want to do arithmetic without any loss of precision. Floats and doubles are inappropriate. I want to use dynamic memory allocations to store any real number obtained after a finite amount of finite operations (addition, subtraction, multiplication, division), starting from natural numbers without ever losing the slightest chunk of the result.

This means, I don't care at all about Pi or the square root of 2, because I have no finite method to obtain them in the first place. I don't want to apply any transcendental function either (cos/sin) because by definition they would never end.

Intuitively, it is obvious that 1/3 cannot be stored in base 2 or 10 using a finite amount of memory (0.33333...), therefore a correct representation would have to be at least fractional.

If this is possible, surely there must be some software out there who already does this. What would be the standard way to go? Preferably, I want a fast (hardware-accelerated) solution, for example using words as digits instead of bits.

A number is obtained from natural numbers using addition, subtraction, multiplication, or division if and only if it is rational. You can store rational numbers as pairs $(p,q)$ of integers, which represent the number $p/q$ (so $q \neq 0$). You can further assume that $p,q$ are mutually prime.

Libraries implementing rational numbers using arbitrary-precision integers are available, for example GMP.


NP-completeness of solving quadratic equations over $\mathbb{Z}_2$ Let $\chi$ be a degree 2 equation over $\mathbb{Z}_2$ of the form:
  $$x_{i_1}x_{j_1} + x_{i_{2}}x_{j_1} + \cdots + x_{i_m}x_{j_m} + x_{k_1} + \cdots + x_{k_l} = b $$ for $ k_i \in \{1, \dots, n\}, b \in \{0,1\}$ for some $m, l \in \mathbb{N}$

  Prove that deciding whether a system of such equations has a solution is NP-complete.

So, we should to prove two things:

1) The problem $\in NP$

2) Another  NP-complete problem can be reduced to that problem.

I have no idea how to start. Please hint me. It is tempting to use $SAT$ problem, but, when I am trying to convert that problem I got stuck:
How to get $1$ (the truth value)?

You can express the constraint $x \lor y = z$ (where $\lor$ is the OR operator) as the equation $(1-x)(1-y) = (1-z)$, that is, $xy+x+y+z=0$. Using this primitive you can express SAT, showing that your problem is NP-hard. Showing that it is in NP is easier.