Is the complement of $ww^R$ context-free? Identify the language given by $L = \{ x \in (0,1)^* : x \neq ww^R, w \in (0,1)^*\}$. Note: $w^R$ is the reverse of the string $w$.

Closure property can/should be applied only in the cases when the actual language is not specified. Otherwise, you may arrive at wrong conclusions. The language in question is fully specified, so I doubt whether one can directly apply closure property on $ww^R$, which you say, is its complement or vice versa. The given answer is CFL. But I don't seem to have arrived at it satisfactorily.

If you want to show that $L$ is context-free, you can proceed as follows:

Build a push-down automaton $P$ that accepts $L$. $P$ will read the input and put all the read characters on its stack. At some point it guesses (non-deterministically!) that half of the input has been read. Then it reads the remaining input and checks it a against its stack. If $P$ finds a mismatching character it accepts, if it does find not a mismatch, or the guess for the middle of the word was wrong, it rejects.


Relation and difference between information retrieval and information extraction? From Wikipedia

  Information retrieval is the activity of obtaining information resources relevant to an information need from a collection of information resources. Searches can be based on metadata or on full-text indexing.

From Wikipedia

  Information extraction (IE) is the task of automatically extracting structured information from unstructured and/or semi-structured machine-readable documents. In most of the cases this activity concerns processing human language texts by means of natural language processing (NLP). Recent activities in multimedia document processing like automatic annotation and content extraction out of images/audio/video could be seen as information extraction.

What are the relations and differences between information retrieval and information extraction?

Thanks!

Information retrieval is based on a query - you specify what information you need and it is returned in human understandable form.

Information extraction is about structuring unstructured information - given some sources all of the (relevant) information is structured in a form that will be easy for processing. This will not necessary be in human understandable form - it can be only for use of computer programs.

Some sources:

Information Extraction vs Information Retrieval
From  Information Retrieval to Information Extraction
Information    Extraction Stanford PPT
Introduction to Information Retrieval(link to place in the book with definition)


Difference between beta reduction and substitution I can not see the difference between beta reduction and substitution.

For example:

(+ x 1) [x -> 2]

Here I can do the substitution, replace the variable x through 2(lambda expression) and result is:

(+ 2 1)

An example of beta reduction:

(λ x. + x 1) 2

the result would be

+ 2 1

For me, there are no difference between them, but there is a rule, I can not substitute the lambda expression, when the metavariable is bound

(λ x. + x 1) [x -> 2] No possible to substitute it.

Only free variables can be substitute it.

What is the difference between the diction:

(λ x. + x 1) 2

and

(λ x. + x 1) [x -> 2]

The $\beta$ reduction is defined by using capture-avoidng substitution. That is,

$$
  (\lambda x. M)N \longrightarrow_\beta M[x \mapsto N]
$$

So it's the definition. Under the $\beta$-equivalence, $(\lambda x. M)N \equiv_\beta M[x \mapsto N]$, but syntactically, $(\lambda x. M)N \neq M[x \mapsto N]$.

Note that substitution is a meta-operation on $\lambda$-calculus terms (normally).
A $\lambda$-calculus term $M$ is whether a variable $x$,
a lambda abstraction $(\lambda x. M')$, or an application $M_1 M_2$.
That's it.
There is no substitution.
Substitution is a map on $\lambda$-calculus terms.
Therefore, for example, a term $({+}~x~y)[x \mapsto z]$ is syntactically equal to $({+}~z~y)$.
There is no reduction.
In contrast to this, $(\lambda x. {+}~x~y)~z$ is not syntactically equal to $({+}~z~y)$, although it can be reduced to $({+}~x~y)$.

Also, $(\lambda x. {+}~x~1)~2$ is different from $(\lambda x. {+}~x~1)[x \mapsto 2]$. The latter is equal to $(\lambda x. {+}~x~1)$.


Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma I am trying to show that $A = \{w \in \{a,b,c,d\}^{*}|w \textrm{ has equal occurences of } ab \textrm{ and } cd\}$ is not regular by using the Pumping Lemma.
My idea here was to use the string $ s = (ab)^{p}(cd)^{p} $.  Clearly, $ s \in A $, and $ |s| = 2p \geq A $.  So the the three conditions of the pumping lemma hold.
Where I am stuck is picking the correct decomposition of $ s $.  My idea was to do the following:
We can decompose $ s $ into $ xyz $ such that:

$ x = (ab)^{j}, j \geq 0 $
$ y = (ab)^{k}, k \geq 1 $
$ z = (ab)^{p-j-k}(cd)^{p} $

Now consider if we "pumped" $ y $.  Let $ i = 2 $.  Then $ xy^{2}x = (ab)^{j}(ab)^{2k}(ab)^{p-j-k}(cd)^{p} = (ab)^{p+k}(cd)^{p} \notin A $.  Therefore, we arrived at a contradiction and $ A $ is not a regular language.
But my confusion here is that the $ xyz $ I have chosen is not the only decomposition of $ s $.  For example, you could choose $ x = a $, $ y = b $, and $ z $ is the rest of the string.  Do I have to cover all possible cases?  If so, this seems like a bad choice for $ s $ -- any other ideas?
Another concern is that my chosen decomposition violates the condition $ |xy| \leq P $ of the Pumping Lemma will not hold for $ p = 1 $.

Ok I will split the answer into two parts, one for each of your questions \ concerns \ confusions:

Q: Are we allowed to use the pumping lemma if we chose a specific decomposition, or do we need to show for all decompositions?
A: The pumping lemma states, $\exists p.\forall w.|w|\ge p \rightarrow \exists x,y,z.w=xyz \land\text{ they are a valid decomposition }\land\forall k\in\mathbb{N}.xy^kz\in A$.
and you are trying to show the negation of this statement. as you can see, there is an "exists" sign before the "x,y,z" and therefore in the negation there will be a "for all" sign.
Thus, you MUST go over ALL possible decompositions in order to use the pumping lemma in this way.

Q: This doesn't work for $p=1$ but works for every other value of $p$. is this a problem?
A: no! its absolutely fine.
Say, for example, you know how to prove for $p=5$ and you don't know how to do $p=1$. define $w=(ab)^5(cd)^5$, and you know that $|w|\ge 5 \ge 1=p$. but since $|w|\ge 5$ and you know how to solve for $p=5$, you know how to deal with $w$.
This means that its enough to prove for some value of $p$ and all other values BELOW it will be automatically proved too!

Also, you are in the right direction. This is a good choice of a word, but you will need to work a bit more to show that every decomposition cannot be always pumped.
I hope this helped you a bit :)


Modified Knapsack Problem I have a problem with the following optimisation problem:

In total there are $n=100$ items. A quality level $L_i \in \{0,1,2,3,4,5\} $  must be selected for each of these items. The greater $L_i$ is, the greater  weight $w_i$ and its value $v_i$, starting with $w_i=0$ and $v_i=0$ for $L_i=0$.
Furthermore, $w_i$ depends on both item $n$ and its quality level $L_i$ and is calculated using function $w_i = w(n,L_i)$. $v_i$ depends on the total set of items and their selected quality levels $L_0 \dots L_n$ and is calculated using the relatively cost-intensive function $V$.

The question now is, what are the optimal quality levels improvements for each item, given random initital quality levels for the items and a capacity $W$? An important restriction is that a quality level can only be increased by one level in total. Each item must be selected exactly once (quality level $L=0$ is effectively the same as if the corresponding item had not been selected).

I see a difficulty in the fact that an items's value v depends on all other items. Can the problem still be solved optimally with an acceptable time complexity, or would it be necessary to use other algorithms, if so which ones? Maybe greedy algorithms?

Thank you very much for your help!

You can't.  If the function $V$  (for computing the $v_i$'s) is arbitrary, in the worst case you will need to try all possible combinations of quality levels -- there is no algorithm faster in the worst case.  That takes exponential time.

To do better, we need to know something about the function $V$: e.g., about its structure or proeprties.


Upper bound on the number of triangles in a planar graph For any $n \geq 4$, I was able to prove that every Apollonian network has $3n - 8$ triangles. An Apollonian network is a planar graph defined by recursively subdividing a triangle by three smaller triangles (adding a new vertex inside the face and connecting it to all three vertices). Now I am trying to prove a similar statement for arbitrary planar graphs. In particular, I am trying to show that every planar graph has at most $an + b$ triangles, for some constants $a$ and $b$, where the goal is to make the constants as tight as possible. The result I showed implies that we need $a \geq 3$ and $b \geq -8$ This is an assignment question, so I would only like a hint please. I believe that I should be able to prove that no planar graph has more triangles than an Apollonian network, but unsure how to proceed.

Presumably you have to show that if you triangulate an arbitrary planar graph then you get an Apollonian network. Then you have to show that the triangulated graph contains more triangles than the original one. This will complete the proof.


What is the significance of primitive recursive functions? I was studying the proof of Ackermann function being recursive, but not primitive recursive, and a question hit me: "So what?". Why does it matter? What is the significance of primitive recursive functions?

The halting problem is undecidable, but one might object that for most programs, it is easy to check whether they halt or not, by looking for any obvious infinite loops. Conversely, if you wanted to ensure that your program always terminates, you could do so by bounding a priori the number of loop iterations for every loop. For example, consider the pseudocode for repeated squaring:

def power(x, y, p):
   "compute x^y mod p"
   assert y >= 0
   result = 1
   while y > 0:
     if x is odd: result = result * x (mod p)
     y = y div 2
     x = x * x
   return result

How do we know that this procedure always terminates? One way would be to a priori bound the loop:

def power(x, y, p):
   "compute x^y mod p"
   assert y >= 0
   bound = y
   result = 1
   loop bound times:
     if x is odd: result = result * x (mod p)
     y = y div 2
     x = x * x
     if y == 0: break
   return result

Now it's clear that this program terminates, and if we haven't made a mistake elsewhere, the two programs would produce the same output.

  Primitive recursive functions are those computed by programs in which all loops are bounded and there is no recursion.

While we do not allow recursion (since it is not bounded), we can simulate it with a loop. We can ask several questions now:

Is every computable function presentable in this form?
If not, what is the relation between this class and all computable functions?

To answer 1, one can show that certain computable functions which grow "too fast" are not primitive recursive, for example the Ackermann function. Conversely, every function whose growth rate is "reasonable" is primitive recursive. And every computable function can be stated in the form $f(x) = \psi(\min_y \phi(x,y))$ for primitive recursive $\phi,\psi$, where we think of $\phi$ as a predicate.


Is L2 = {a^n| n is a product of one or more primes} regular? I am having a hard time proving the following with pumping lemma:
Is $L_2 = \{a^n \mid \text{$n$ is a product of one or more primes}\}$ regular?

Here's what I have so far:

Suppose $L$ is regular, and let $m$ be the constant pumping lemma.
Let then $w = a^m$ where $m$ is a product of at least one prime number, therefore $w$ is in the language $L_2$ and $|w| \geq m$.
Then $w = xyz$, where $|xy| \leq m$ and $|y| \geq 1$.
Then $y = a^j$ where $j \geq 1$.

This is where I'm not sure what to do:
Pumping down we get $w_2 = a^{m-j}$

I don't know where to keep going from here since I don't even know if pumping down is the right thing to do.

According to the Fundamental Theorem of Arithmetic, any integer $>1$ can be written as a product of one or more primes (in a unique way).  So, it seems that your language can be simplified as $\{a^n\mid n\geq 2\}$.


Why is my algorithm version so slow with this input? Here I'm trying to do a comparison of two simple as possible algorithms, solving the symmetric travelling salesman problem, finding the optimal solution without the support of heuristics. I'm showing (or just referencing) the code of both algorithms only to better specify the implementation details, which could be relevant for the comparison.
I've written my F# code to solve Advent of Code Day 18 Part 1.
It is a BFS adapted to find the optimal solution for a weighted graph (last version has been edited since the original question was posted here, but, as already said, ignore this sort of details).
While it seems to work fine with other simple demo inputs, it stucks forever with the following input.

#################
#i.G..c...e..H.p#
########.########
#j.A..b...f..D.o#
########@########
#k.E..a...g..B.n#
########.########
#l.F..d...h..C.m#
#################

It represents a list of lowercase char vertices with uppercase constrained predecessors and edges weighted by different dotted distances.
So here I'm looking for a comparison based on the time complexity of the algorithms, related to an analysis of the cases where the number of edges increases, at a fixed number of vertices.
There is a reference solution in Python which is correct and fast, but I fail to see where is the fundamental difference between the two algorithms, behind the other minor code differences (also because the languages are different).

I've tried with recursion vs a queue, with tree vs grid/map (see my github history) but with no luck until now.

The principal part of the code is described below.
It should fall under a breadth first search (BFS) algorithm, whose implementation details are reported below only to complete the theoretical description already given, because the standard BFS has been adapted to multiple targets, weighted edges and a tentative tree pruning.

Here is how I produce the single step, by which I elaborate the solution.

1 single step receives as input which is the move index i
2 then it updates the distance of the current solution draft by summing the distance to the vertex i
3 it updates the current position as of vertex i
4 it also updates the list of predecessors by including vertex i
5 it computes the new tree of reachable vertices starting from the `fullGrid` and taking into account the newly updated list of predecessors

Notice that this is a constrained version of the TSP where each vertex can have as constraint a list of predecessors.

The fullGrid is supposed to contain the matrix of distances and it looks fine to me, in terms of the values it contains when I debug it.
The wrapping solver is simply a recursion or queue based version of the BFS. Again, I'm not interested in the programming details but in understanding, at a conceptual level, why the underlying algorithm is not applicable for an apparently tractable input case (of "only" 16 nodes).

Start by receiving the graph topology and starting point
    Define a mindistance variable
    and a list of completed solutions, initially empty

    Start looping at the queue of partial solutions
        So a single partial solution is dequeued
        It computes possible vertices based on current predecessors
        Check if nothing remains and adds it to the completed alternatives updating mindistance
        Otherwise loop as in classical BFS
        For all possible moves = reachable vertices

                For each one applies above said single step
                If done updates mindistance and completed alternatives
                Otherwise enqueue such partial solution

    Finally select the min alternative by distance.

I've found the conceptual problem.
In a BFS kind of search, when optimization is needed because the length of the queue grows at critical speed, you have to take track of the visited items.

The goal is to avoid adding another item to the queue when it is already present a better item there.

Just some code, only to clarify the concept.

In my case I've added a visited map

let mutable visited = Map.empty<char,((char list) * int) list>

and I'm enqueuing only better items:

if visited.ContainsKey(solutionNext.tree.area)
    && (visited.[solutionNext.tree.area]
        |> List.exists (
            fun (keys, distance) ->
            distance <= solutionNext.tree.distance
            && solutionNext.keys |> List.forall(fun k -> keys |> List.contains k)
        ))
then ()
else
    solution_queue <- enqueue solution_queue solutionNext
    let previous = if visited.ContainsKey(solutionNext.tree.area) then visited.[solutionNext.tree.area] else []
    visited <- Map.add solutionNext.tree.area ((solutionNext.keys, solutionNext.tree.distance) :: previous)  visited

and skipping the worst ones

while (MyQueue.length solution_queue > 0) do
    let solution = dequeue &solution_queue
    if visited.ContainsKey(solution.tree.area)
        && (visited.[solution.tree.area]
            |> List.exists (
                fun (keys, distance) ->
                distance < solution.tree.distance
                && solution.keys |> List.forall(fun k -> keys |> List.contains k)
            ))
    then () else

Cost function

From a theoretical viewpoint, BFS can guarantee that the ﬁrst solution returned will be as short as possible, only if we can assume that every move has got a cost of 1. You could reduce the above examples to that, but the best fit remains a graph where the cost function is represeted by edges of different length.
With real cost functions finding the shortest path becomes more involved: this is exactly the case here. Especially because you have to optimize also the Space complexity (see previous paragraph), avoiding the worst-case time complexity of $O(b^d)$, with $b$ being the branching factor and $d$ the depth of the ﬁrst solution. You have described a scenario where $d$ is well known at start (the number of the keys in the maze) while the edge case you mention is obtained by a bigger $b$ (number of crossings of the maze)


What is the difference between user-level threads and kernel-level threads? After reading several sources I'm still confused about user- and kernel-level threads.

In particular:

  Threads can exist at both the user level and the kernel level

What is the difference between the user level and kernel level?

One of the roles of a multitasking operating system kernel is scheduling: determining which thread of execution to execute when. So such a kernel has some notion of thread or process. A thread is a sequential piece of code that is executing, and has its own stack and sometimes other data. In an operating system context, people usually use process to mean a thread that has its own memory space, and thread to mean a thread that shares its memory space with other threads. A process can have one or more threads.

Some operating systems, for example older unix systems, only provide processes: every thread that the kernel manages has its own memory space. Other operating systems, for example most modern unix systems, allow processes to contain multiple threads of execution: they provide a kernel-level notion of threads.

It's also possible for a process to manage its own threading. In cooperative multithreading, the code of each thread contains instructions to switch to another thread. In preemptive multithreading, the process requests periodic asynchronous notifications from the kernel, and reacts to these notifications by switching to a different thread. This way, multithreading is implemented with no kernel cooperation, at the user level, in a library.

A system can offer both kernel-level and user-level threads; this is known as hybrid threading.

User- and kernel-level threads each have their benefits and downsides. Switching between user-level threads is often faster, because it doesn't require resetting memory protections to switch to the in-kernel scheduler and again to switch back to the process. This mostly matters for massively concurrent systems that use a large number of very short-lived threads, such as some high-level languages (Erlang in particular) and their green threads. User-level threads require less kernel support, which can make the kernel simpler. Kernel-level threads allow a thread to run while another thread in the same process is blocked in a system call; processes with user-level threads must take care not to make blocking system calls, as these block all the threads of the process. Kernel-level threads can run simultaneously on multiprocessor machines, which purely user-level threads cannot achieve.


Is it decidable if there exists some input such that the TM makes at least five moves? I am reading this excerpt from Ullman's book:

I have following doubts:

(related to red underline) TM can make 5 left moves or 5 right moves. So it will  need at max 11 cells. Then how it says 9?
(related to green underline) Whats the significance of "finite"? Due to 9 (or 11 if I was correct in point 1)?
(related to blue underline) I am not able to understand the given proof. I tried it myself: I will run TM on all length 1 to 5 strings. If it makes 5+ moves on any of these strings, then "accept", else "reject". Hence decidable. Is my interpretation / approach correct? If correct then what was the significance of thinking about those nine cells?

It's 9 because it doesn't matter what symbol we land on after move 5.
It's finite because the number of cells is 9, yes. The significance is because otherwise the algorithm in point 3 wouldn't finish.
All strings of length 9, with the starting point in the middle. "Five or fewer" is an error, I believe.


Exclusive queue problem There is the exclusive queue problem in The Little Book of Semaphores, which is stated as follows:

Imagine that threads represent ballroom dancers and that two kinds of dancers, leaders and followers, wait in two queues before entering the dance floor. When a leader arrives, it checks to see if there is a follower waiting. If so, they can both proceed. Otherwise it waits. Similarly, when a follower arrives, it checks for a leader and either proceeds or waits, accordingly. Also, there is a constraint that each leader can invoke dance concurrently with only one follower, and vice versa.

The author's solution:

leaders = followers = 0
mutex = Semaphore(1)
leaderQueue = Semaphore(0)
followerQueue = Semaphore(0)
rendezvous = Semaphore(0)

def leader_thread():
   mutex.wait()
   if followers > 0:
      followers--
      followerQueue.signal()
   else:
      leaders++
      mutex.signal()
      leaderQueue.wait()

   dance()
   rendezvous.wait()
   mutex.signal()

def follower_thread():
   mutex.wait()
   if leaders > 0:
      leaders--
      leaderQueue.signal()
   else:
      followers++
      mutex.signal()
      followerQueue.wait()

   dance()
   rendezvous.signal()

However, I think there is a simpler solution:

leader_mutex=Semaphore(1)
follower_mutex=Semaphore(1)
leader_rendezvous=Semaphore(0)
follower_rendezvous=Semaphore(0)

def leader_thread():
   leader_mutex.wait()
   leader_rendezvous.signal()
   follower_rendezvous.wait()
   dance()
   leader_mutex.signal()

def follower_thread():
   follower_mutex.wait()
   follower_rendezvous.signal()
   leader_rendezvous.wait()
   dance()
   follower_mutex.signal()

It is quite obvious and very similar to the queue problem solution mentioned in this book, so I wonder why it was not included in the book. Is there something wrong with my solution? Could you prove that my solution is correct?

If you suspect that your solution is right, then try to prove it (since we are not dealing with foundations, e.g. how exactly is time represented in our system, the proof will be somewhat informal, but it is still a good way to convince yourself).

Claim 1: No more than one pair of follower and dancer can be at the dance floor concurrently.

This is obvious, since if we have one dancer and one follower dancing then both locks are acquired, and thus no more dancers are able to continue.

Claim 2: If a pair $(f,l)$ is dancing ($f,l$ are follower and leader correspondingly), no other dancers will be able to dance until both $f,l$ are done.

Obviously at least one of the dancers $f,l$ has to finish for others to be able to join (we need to release at least one lock). Suppose $l$ finishes first. More followers cant join unless $f$ is done (lock), so the next dancer has to be a leader. However, the next leader will be stuck waiting for follower_rendezvous, which will only be signaled when a new follower comes, and for that $f$ must finish dancing as well (to release the lock).

Claims 1,2, together with the observation that a pair of follower and dancer are able to dance concurrently, concludes the proof.


Why ASCII letter A has a Hamming Distance of 3? My question is what does [this construction gives a Hamming Distance a distance of 3] means? Why the Hamming Distance of ASCII letter A is 3? How do you determine the Hamming Distance is 3?

This is an excerpt from Computer Network by Andrew S. Tanenbaum page 206.

Tanenbaum is not saying that ASCII character "A" has a particular Hamming distance. Computerphile has a video that may clear things up.


Proving undecidability for a language which contains string with certain syntax Lets say we have the following problem:

$$\mathcal{L}_1 = \{\langle \mathcal{M} \rangle | \mathcal{M}\ \text{is a Turing machine and $\mathcal{L}(\mathcal{M})$ contains a string with exactly three zeros}\}$$

We would like to prove that $\mathcal{L}_1$ is undecidable. I would generally use Rice's theorem to prove that a language is undecidable, but in the present case, we aren't dealing with a semantic property of the language but rather its syntax. In cases where we have to prove based on the language's construction, how would the process look like and differ from proving with Rice's theorem?

It can be thought of a semantic property of the language, and its ok to use Rice's theorem here.

Define $C=\{L|\text{there is a string with exactly 3 zeros in }L\}$

So, $L_1=\{<M>|M \text{ is a turing machine and } L(M)\in C\}$ and because $C\neq\emptyset$ and $C$ is not every language, then by Rice's theorem, $L_1\notin R$.


Finding certain elements when only able to ask in chunks I have a set of $n$ elements. Of these elements $b\ll n$ are blue and $r=n-b$ are red. I want to find all blue elements.
My only way to discriminate between red and blue objects is by asking a blackbox that takes a fixed number $k$ of elements (with $n \gt k \gg 1$) and returns an approximation of how many of those elements are blue. The approximation is such that the returned number $\hat N_b = N_b + u$ is the real number of blue elements $N_b$ combined with a Gaussian noise $u$ that has a Variance of $\text{Var}(u)\approx 1$ and an expected value of $E(u)=0$. $k$ is big enough that in a random sample the expected number of blue elements $E(N_b)$ greatly exceeds the variance of the noise.
Is there an efficient algorithm to determine (to a certain probability) which elements are blue?

You can eliminate the noise.  Any time you make a query, repeat it 1000 times, use the average of the 1000 responses, and round it to the nearest integer.  The noise in the result before rounding will have variance $1/1000$, so the probability that rounding creates an error is $\operatorname{erfc}(\sqrt{125})$, which is less than $10^{-54}$... i.e., negligibly small (smaller than the probability that a cosmic ray strikes your computer and causes it to give an incorrect result).  This will increase the number of queries by a factor of 1000, i.e., by a constant factor, so it will not affect the asymptotic complexity.
Now once there is no noise, it becomes much easier to solve it.  For instance, you can first find a set of $k$ objects known to be red, then repeatedly randomly sample $n/b$ unknown objects, add $k-n/b$ known-red objects, and query the result; if the response is 1, then you know that one of those is blue, and you can use binary search to find it.  This will require about $O(b \log b)$ queries.  I expect it should be possible to reduce this to $O(b)$ with more cleverness, but I haven't figured that out yet.  A good question is whether you can do substantially better than $O(b)$, if $k \gg b$.


What makes PROLOG Turing-complete? I know that it can be proven PROLOG is Turing-complete by constructing a program that simulates a Turing machine like this:

turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).

perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).

symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

Source

However, I’m wondering which parts of the PROLOG language one could strip away (esp. function symbols, clause overloading, recursion, unification) without losing Turing completeness. Are function symbols themselves Turing complete?

It's a fairly reliable rule of thumb that Turing-completeness depends on the ability to construct answers or intermediate values of unrestricted "size" and the ability to loop or recurse an unrestricted number of times. If you have those two things, you probably have Turing-completeness. (More specifically, if you can construct Peano arithmetic, then you certainly have Turing-completeness!)

Let's assume for the moment that you've already stripped arithmetic. We'll also assume that you don't have any non-logical features like atom_chars, assert, and so on, which enable general shenanigans.

If you stripped out function symbols, you can't construct answers or intermediates of unrestricted size; you can only use atoms which appear in the program and the query. As a result, the set of all possible solutions to any query is finite, so taking the least fixed point of the program/query will always terminate. Datalog (a relational database query language based on Prolog) works on this principle.

Similarly, if you restricted Prolog to primitive recursion only (that includes no recursion as a degenerate case), then the amount of recursion that you can do is bounded by the size of the query, so all computation terminates. So you need general recursion for Turing-completeness.

And, of course, if you have general recursion, you can cut a whole bunch of features and retain Turing-completeness, including general unification (construction and top-level pattern matching is sufficient), negation, and the cut.


How to prove the NP-completeness of the ``Exact-3D-Matching`` problem by reducing the ``3-Partition`` problem to it? Background: The Exact-3D-Matching problem is defined as follows (The definition is from Jeff's lecture note: Lecture 29: NP-Hard Problems. You can also refer to 3-dimensional matching):

  Exact-3D-Matching: Given a set $S$ and a collection of three-element subsets of $S$, called triples, is there a sub-collection of disjoint triples that exactly cover $S$?

The 3-Partition problem is defined as (It is also from Lecture 29: NP-Hard Problems. You can also refer to 3-partition problem.):

  Given a set $S$ of $3n$ integers, can it be partitioned into $n$ disjoint three-element subsets, such that every subsets has exactly the same sum?

It is known that the 3-Partition problem can be proved to be NP-complete by reducing the NP-complete Exact-3D-Matching problem to it. And the NP-completeness of the Exact-3D-Matching problem is proved by reducing the 3SAT problem to it (both are given in the book Computers and Intractability: A Guide to the Theory of NP-Completeness).

Problem:
My problem is:

  How to prove the NP-completeness of the Exact-3D-Matching problem by reducing the 3-Partition problem to it?

I have found neither papers nor lecture notes on it.

I think this reduction should work:

Given a 3-PARTITION instance: $n$ integers $a_1,\ldots,a_{3n}$ and a target sum $B$;
mark each integer with an unique identifier $\hat{a_i}$; then build a collection of 3-elements subsets $C_j = \{ \hat{a}_{i_1}, \hat{a}_{i_2}, \hat{a}_{i_3} \}$ such that $a_{i_1}+ a_{i_2}+ a_{i_3} = B$ and $i_1 \neq i_2 \neq i_3$ (the collection has $O(n^3)$ elements).

The original 3-PARTITION problem has a solution if and only if there exist an EXACT-3D-MATCHING $C_{j_1}, \ldots, C_{j_n}$ that covers $S = \hat{a}_{1}, \ldots,  \hat{a}_{3n}$.

For example given $A = \{5,4,3,3,3,2,2,1,1\}, B = 8$ we build:
$S = \{5a,4a,3a,3b,3c,2a,2b,1a,1b\}$ and the collection of 3-elements subsets:

C1  = { 5a, 2a, 1a }
C2  = { 5a, 2a, 1b }
C3  = { 5a, 2b, 1a }
C4  = { 5a, 2b, 1b }
C5  = { 4a, 3a, 1a }
C6  = { 4a, 3a, 1b }
C7  = { 4a, 3b, 1a }
C8  = { 4a, 3b, 1b }
C9  = { 4a, 3c, 1a }
C10 = { 4a, 3c, 1b }
C11 = { 4a, 2a, 2b }
C12 = { 3a, 3b, 2a }
C13 = { 3a, 3b, 2b }
C14 = { 3a, 3c, 2a }
C15 = { 3a, 3c, 2b }
C16 = { 3b, 3c, 2a }
C17 = { 3b, 3c, 2b }

An Exact-3D-MATCHING is given by:

C1  = { 5a, 2a, 1a }
C6  = { 4a, 3a, 1b }
C16 = { 3b, 3c, 2b }

that also uniquely identifies a valid solution for the original 3-PARTITION problem.


Given a TM $T$ does $T$ ever leave the initial state when start tape is blank? I want to determine whether this decision problem is decidable. I have tried to establish reductions from Halt and "Accepts empty-string", but I've not yet found a solution.

Can someone help me out?

I would say it is decidable.

If I understood correctly, here's what I think.

First of all a TM starts from some initial state $s_0$. How can it change the state? In your transition function you have something like $(s_0, x) \to (s_i, y, m)$ where $s_i$ is a state and $x$, $y$ are symbols and $m$ is the head move (left right or stay). So, if it leaves the initial state there should be a transition from $(s_0, \_)$ to some state not $s_0$. Easy to see that it is if and only if. Thus, you can construct another Turing machine which has the input as a TM in some encoding, goes through the transition function and checks the condition above, and the problem is decidable.


Algorithmic problem with many different time/space complexity solutions I am preparing a lesson about algorithmic thinking for beginner programmers. I would like to show them an easy to understand problem which has as many solutions as possible with different time or space complexities. Sorting quickly comes to mind but if you avoid intentionally stupid solutions such as Bogosort, you only really have O(n^2) and O(n*log n) complexities.

In this respect I love the problem for computing the n-th Fibonacci number with integer arithmetic. You can do it exponentially as a naive approach, linearly if you are a bit clever, and even logarithmically if you are smart as hell. On the other hand, fibonacci numbers would not appear very practical to novice programmers. I would like something that is related to more practical problems as I do not want the students to think that algorithm design is something really abstract and theoretical.

I like this one: given a string $S$, find the longest substring that appears two or more times in $S$.

There are plausible algorithms with running time $O(n^3)$, $O(n^2)$, $O(nk \log n)$, $O(nk \log k)$, $O(nk)$, $O(n \log n)$, $O(n \log k)$, and even $O(n)$, where $n$ is the length of $S$ and $k$ is the length of the longest such substring.

However I don't know if it has practical applications.

Computational biology is a good source of practical algorithm problems.


Proving a grammar only generates words whose alternating digit sums are multiples of three This is homework and I'm looking for a push in the right direction. Proofs were never something I was properly taught, so now they're kind of a weak point.

Here's the problem:

  The following grammar generates numbers in binary notation ($C$ is the
  start symbol):

  $\qquad \begin{align}C &\to C 0 \mid A 1 \mid 0 \\
                       A &\to B 0 \mid C 1 \mid 1 \\
                       B &\to A 0 \mid B 1
          \end{align}$

  Prove that the alternating sums of the digits of the generated
  numbers are multiples of $3$. The alternating sum of $w=w_0\dots w_n$ is defined as $\sum_{i=0}^n (-1)^i \cdot w_i$. As an example, $C$
  generates $1001$ via $C \Rightarrow A1 \Rightarrow B01 \Rightarrow A001 \Rightarrow 1001$ with alternating sum of $0$;
  clearly, $0$ is a multiple of $3$.
  Prove that all such numbers (i.e.,
  numbers whose alternating sum is a multiple of 3) are generated by the
  grammar.

I'm thinking I need to show that the grammar can only generate strings which are made up of repeated subsequences of digits which always add up to 0, 3, or -3. But I'm not sure how to show that it can only generate those three subsequences.

I also have worked out these thoughts:

Consider that any even number of consecutive 1s is irrelevant, as they cancel each other out.
Consider that all zeros are in of themselves irrelevant, as they add nothing.
Consider then that the only relevant pattern is that of alternating 1s and zeros, and where this pattern starts and ends.

Rough hint: play around with the many equivalent models you have for regular languages.

For 1), I find problematic that the contribution of an already generated digit changes as more symbols are added to the front. Things would be easier if the grammar was right-linear.

   Convert the given grammar to an NFA and convert that one to a grammar with the simple construction, which always yields right-linear grammars. (You should have proven algorithms for both.) Determinising/minimising the intermediate automaton might also help the proof.

Then, you have to figure out an induction hypothesis on sentences that works and implies the statement (for words), and perform induction over the whole set of sentences (by the length of the derivation).

   For example, if a non-terminal $C$ can only end the derivation by deriving a $1$, then for any sentence of the form $wC$, either $w$ has even length and its alternating digit sum plus one divides three, or it has odd length.

For 2), build an automaton that you can easily show generates all such words.

   For instance, use a counter construction, that is count the alternating digit sum modulo three in the states.

Now you can show equivalence of this automaton and the one derived from the grammar in 1).


Compute square root using (bit) additions and shifts as primitives Question: Given an $n$-bit natural number $N$, how to compute $\lceil \sqrt{N} \rceil$ using only $O(n)$ (bit) additions and shifts?

The tip is to use binary search. However, I could not achieve the required complexity (I got $O(n^2)$).

What does it mean by using only $O(n)$ (bit) additions and shifts:

This is an exercise in an algorithm book.
In my opinion, it means that adding two, say $n$-bit, natural numbers costs $O(1)$ and shifting a, say $n$-bit, natural number also costs $O(1)$. Then we are only allowed to use such $O(1)$ operations $O(n)$ times.
It does not mention the cost of comparison. I guess we can ignore it or assume that comparing two, say $n$-bit, natural numbers costs $O(1)$ as well.

My $O(n^2)$ algorithm:

Determine the range of the number of bits $t$ of $\lceil \sqrt{N} \rceil$:
      $$2^{\frac{n-1}{2}} \le \sqrt{N} \le 2^{\frac{n}{2}} \Rightarrow 2^{\lfloor \frac{n-1}{2} \rfloor} \le \lceil \sqrt{N} \rceil \le 2^{\lceil \frac{n}{2} \rceil}$$
Therefore,
$$t_1 \triangleq \lfloor \frac{n-1}{2} \rfloor + 1 \le t \le \lceil \frac{n}{2} \rceil + 1 \triangleq t_2.$$
Binary search:
Find $\lceil \sqrt{N} \rceil$ between $2^{t_1}$ and $2^{t_2}$ using binary search. For each number $x$, to compute $x^2$ using additions and shifts as primitives and compare it with $N$.

The complexity is thus $O(n \times n) = O(n^2)$ for $O(n)$ times of binary search and computing $x^2$, each of which in turn takes $O(n)$ additions and shifts.

An iterative algorithm seems like it should work.

Let $M=\lfloor N/4 \rfloor$.  Suppose we know that $x$ is the integer approximation to $\sqrt{M}$, i.e., $x=\lceil \sqrt{M} \rceil$, and suppose we know the value of $x^2$ (obtained previously).

Now we want to find $y=\lceil \sqrt{N} \rceil$.  What are the possible values of $y$?  I'm pretty sure the only possible values are $y=2x$ or $y=2x+1$.   And, it's easy to try both of them and see which is correct.  In particular, for $y=2x$, we have $y^2=4x^2$, which can be obtained from $x^2$ by two left-shifts ($O(1)$ time); for $y=2x+1$, we have $y^2=4x^2+4x+1$, which can be obtained from $x^2$ and $x$ with four left-shifts and two additions ($O(1)$ time).  Now just compare those two values to $N$ to see which one is correct.

In this way, we get an iterative algorithm where we do $n/2$ iterations, and where each iteration takes $O(1)$ time.  The total running time is $O(n)$, as required.

I realize this didn't use binary search.  Oh well.


How can $A \cup B$ be decidable if $B$ is undecidable? My assignment says:

"Determine if the following statement is correct:
If $A$ and $A \cup B$ are decidable, then $B$ is decidable."

The solution says:

"Incorrect. If $B = H_0 \subseteq \{0,1\}^*$ is the halting problem with input $\epsilon$ and $A = \{0,1\}^*$, then $A$ and $A \cup B$ are decidable and $B$ is undecidable.

My question is:

How can $A \cup B$ be decidable if $B$ is undecidable? If for example $b \in B$ then $b \in A \cup B$ but a Turing Machine may not halt on $b$ because $B$ is undecidable, then how can $A \cup B$ still be decidable with $b \in A \cup B$ ?

If $A=\{0,1\}^*$ then $A\cup B=\{0,1\}^*$, regardless of what $B$ is. $\{0,1\}^*$ is decidable, and choosing to express it as something involving undecidable things doesn't change that fact.

The question "Is $w$ in $A\cup B$?" is equivalent to "Is at least one of the following statements true? $w$ is in $A$; $w$ is in $B$; $w$ is in both $A$ and $B$?" In the case $A=\{0,1\}^*$, we can answer "Yes, $w$ is in $A$" and the rest of the questions are irrelevant.  It doesn't even matter if we can't answer "Is $w$ in $B$?", because we don't need to.

Here's a more practical example that might help. Suppose I give you a number $x$ and ask you "Is $x\in\text{Integers}\cup\text{Primes}$?" Figuring out if a large number is prime is quite difficult, but you can easily answer my question by checking if $x$ is an integer. You can ignore the "prime" part completely.


Minimum difference between two subsets of an array of integers The Problem

Suppose we have an array A[1...n] of integers, with values ranging from 0 to K (so 0<=A[i]<=K for each i). We need to describe an algorithm to find an (X,Y) partition from the set {1,2,...,n} such that |Sx-Sy| is minimum, where Sx and Sy are the sums of the elements in X and Y. i.e., if A=[1,3,1,1], then X={1,3,4} and Y={2} and the solution is optimal with Sx=3, Sy=3, |Sx-Sy|=0.

My Solution (In pseudocode)

For i=0 to n
    if A[i]==K //If this element is the highest element in the array, put it in Sy
        Sy.add(A[i])
Else if A[i]=/=0 //We don't care about zeroes, the rest goes in Sx
    Sx.add(A[i])
min = |Sx-Sy| //Calculate our min as it is
DO
    go=false
    //Move the smallest element from the biggest group to the other one
    if Sx>Sy
        SyTemp = Sy + min(Sx)
        SxTemp = Sx - min(Sx)
    else if Sy>Sx
        SxTemp = Sx + min(Sy)
        SyTemp = Sy - min(Sy)
    //if this improves on our min, save it and check for another iteration
    if |SxTemp-SyTemp|<min
        Sx=SxTemp
        Sy=SyTemp
        min = |Sx-Sy|
        go=true
    else
        Return Sx,Sy //if the new sets are worse than the ones before, return the old ones
While(go)

My question

Apparently, this problem is NP complete (At least that is what my professor told me), and my question comes from the way he scored my solution. I got 3 points out of 9 because a dynamic programming solution is what was requested - while this is a greedy approach - and my solution has edge cases in which it won't work.

the example he gave me to prove that these edge cases exist was [1,2,5,5] and he said that in this case the algorithm would return {1,2,5},{5} instead of {1,5},{2,5}. Now, to me it seems like my solution would actually return what he wants, and I can't really think of an example this algorithm couldn't deal with, so I'm here to ask the community if you see any errors in my solution, if you think my professor is right in saying that his example wouldn't be solved optimally (or that there are edge cases in which this approach won't work), and if you think this will perform better than O(K(n^2)), where K is the sum of all values of the array (which apparently is the time complexity of his DP solution).

My algorithm got proven wrong by Ricky Demer in a comment to the OP, with the example [2,2,3,3], for which we have a suboptimal output ({2,2} and {3,3} instead of {2,3} and {2,3}, for those wondering). Altough this flaw could be fixed in my code, it would then perform suboptimally in the example my professore had given me (And that I wrote in the OP).

A good greedy version of the algorithm is given on Wikipedia and is as follows:

def find_partition(int_list):
"returns: An attempt at a partition of `int_list` into two sets of equal sum"
A = set()
B = set()
for n in sorted(int_list, reverse=True):
    if sum(A) < sum(B):
       A.add(n)
    else:
       B.add(n)
return (A, B)

This approach gives a 7⁄6-approximation of the optimal solution, thus the only viable technique to use in case you need an optimal algorithm is dynamic programming. An implementation can be found, again, on Wikipedia and will run in pseudo-polynomial time.


Permutation of n-size array with possible repeated elements. E.g [1, 2, 1] What would it be a recursive algorithm to get permutations for any list of n elements that might contain or not repeated elements?

For the following 3-element list [1, 1, 2] I would expect the following result:

[1, 1, 2]
[1, 2, 1]
[2, 1, 1]

So far I have the following result:

[1, 1, 2] <- duplicate
[1, 2, 1] <- duplicate
[1, 1, 2]
[1, 2, 1]
[2, 1, 1] <- duplicate
[2, 1, 1]

with algorithm below:

FUNCTION permute(array, nestingLevel) :
    FOR index = nestingLevel TO array size -1
        SWAP array[index] WITH array[nestingLevel]
        CALL permute (array, nestingLevel + 1)
        SWAP array[nestingLevel] WITH array[index]
    END FOR

    IF recursionNestingLevel EQUAL TO array size - 1
        PRINT array
    END IF
END FUNCTION

DEFINE array[] := 1, 1, 2
CALL permute (array, 0)

I will change your function a bit, because there is too much going on with swaps and there is variable recursionNestingLevel which is not really declared or needed.

FUNCTION permute(array, nestingLevel) :
    IF nestingLevel EQUAL TO array size
        PRINT array
        RETURN
    END IF

    CALL permute (array, nestingLevel + 1)

    SET index TO nestingLevel + 1
    WHILE index LESS THAN array size
        SWAP array[index] WITH array[nestingLevel]
        CALL permute (array, nestingLevel + 1)
        INCREMENT index BY 1
    ENDWHILE
END FUNCTION

DEFINE array[] := 1, 1, 2
CALL permute (array, 0)

Now there is a simple idea to prevent recursing over same elements - it eliminates first unnecessary swap of and all redundant calls when array[index] is equal array[nesting level]:

FUNCTION permute(array, nestingLevel) :
    IF nestingLevel EQUAL TO array size
        PRINT array
        RETURN
    END IF

    CALL permute (array, nestingLevel + 1)

    SET index TO nestingLevel + 1
    WHILE index LESS THAN array size
+       IF array[index] EQUAL array[nestingLevel] CONTINUE
+       array = CLONE array
        SWAP array[index] WITH array[nestingLevel]
        CALL permute (array, nestingLevel + 1)
        INCREMENT index BY 1
    ENDWHILE
END FUNCTION

DEFINE array[] := 1, 1, 2
CALL permute (array, 0)

CLONE here prevents passing by reference of array, which would propagate changes to every recursive call

When you prevent swapping same elements and calling permute, it effectively blocks call with same parameters, so there are no duplicates.
BTW I have tested this code, for [1, 1, 2] it yields [ 1, 1, 2 ], [ 1, 2, 1 ], [ 2, 1, 1 ], with JavaScript


how can a program be OS-dependent? I know the fact that you cannot run the same machine code on two different machines,

so the software must be machine dependent (i.e Arm program cannot run on either powerpc or x86).

but in reality the software is OS dependent (i.e linux programs cannot run on windows or mac).

how does this happen? my best guess for now is that every OS behaves like a virtual machine and the source is compiled for windows-machine,may be??
and this machine has its own assembly code?

Operating systems have Application Programming Interfaces, whose functionalities are available as libraries that are linked to the code produced by the programmer.

This does not mean they constitute virtual machines. They just encapsulate operations that are not directly accessible to the programmer, either because they depend on low level instructions or protocols that are protected, or because they are provided as high-level standard services.

What happens is simply that what you write in a language that compiles to machine code is only a part of what will be running. Usually a very small part.


Semi-decidability of the language $\overline{L_{\epsilon}}$ Firstly consider the problem: given $L_H = \{R(M)w : M \in TM_0, w\in L(M)\}$ where $R(M)$ are encoded transitions of $M \in TM_0$. Assume for contradiction $\overline{L_{H}}$ is semi-decidable, then there is $Q \in TM_0$ with $L(Q)  = \overline{L_{H}}$ therefore for every $M \in TM_0$ we have the following
$$Q \ accepts \ input \ R(M)w \iff M \ does \ not \ accept \ input \ w  \ \ \ \ (1)$$
Then we construct machine $Z$ s.t. doubles the input and runs machine $Q$. Observe the following for arbitrary $M \in TM_0$:
\begin{alignat*}{2}
Z  \ accepts \ input \ R(M) &\iff Q\ accepts \ input \ R(M)R(M)\\
&\iff M \ does \ not  \ accept \ input \ R(M)
\end{alignat*}
Taking $M = Z$ will yield us a contradiction. Hence, $\overline{L_{H}}$ is not semi-decidable.
The same technique I am trying to apply for the case $L_{\epsilon} = \{R(M) : M \in TM_0 \ \text{s.t. $M$ accepts $\epsilon$}\}$ where $R(M)$ are encoded transitions of $M \in TM_0$. But I am facing some troubles. Assume for contradiction $\overline{L_{\epsilon}}$ is semi-decidable, then there is $Q \in TM_0$ with $L(Q)  = \overline{L_{\epsilon}}$ therefore for every $M \in TM_0$ we have the following
$$Q \ accepts \ input \ R(M) \iff M \ does \ not \ accept \ input \ \epsilon$$
Then I cannot really find appropriate $Z$ for this case, as doubling the input simply won't work. Any suggestions are appreciated.

Assume for contradiction $\overline{L_{\epsilon}}$ is semi-decidable. It's easily proven that $L_{\epsilon}$ is semi-decidable by reduction to the HALTING problem, i.e. $L_{H}$ is semi-decidable. If $L_{\epsilon}$ and $\overline{L_{\epsilon}}$ are semi-decidable, hence $L_{\epsilon}$ is decidable. This is a contradiction, as $L_{\epsilon}$ as well as $L_{H}$ are semi-decidable.
In this prove the following claim was used:

$\textbf{Claim:} \text{ If $L$ and $\overline{L}$ are semi-decidable, then $L$ is decidable}$


RE Construction: Strings of even length in alphabet {a,b,c} that contain exactly one a i am reviewing older exams from my computational theories lesson in university and i am struggling to figure this one out:
Construct a regular expression for the following language: Strings of even length in alphabet {a,b,c} that contain exactly one a.

Roughly translated from greek, hope it makes sense. Thanks

The idea is that if a string contains one $a$, then it can be written as $xay$, where $x,y \in (b+c)^*$. Furthermore, $xay$ has even length if either $x$ has even length and $y$ has odd length, or vice versa. Using this, it is straightforward to come up with a regular expression.


For arbitrary RR(1) grammar $G$, is there an equivalent LL(1) grammar $G'$? Failed to find similar term, here I coin the noun RR(Right-to-left, Rightmost derivation) as an opposite concept of LL.

The question is inspired by an interesting example grammar $G$:
$$S \rightarrow S S + | a$$
It's obviously an RR(1) language. After some time to explore, I find an equivalent LL(1) grammar:
$$
\begin{array}{l}
S \rightarrow a A \\
A \rightarrow S + | \epsilon
\end{array}$$

So, there seems a road to more generalized conclusion. Consider arbitrary RR(1) grammar, is there an equivalent LL(1) grammar $G'$, where equivalent means $L(G) = L(G')$?

No. A language $\mathcal{L}$ is $RR(k)$ exactly if its reverse $\mathcal{L}^R$ is $LL(k)$. So if a $RR(k)$ grammar $G$ could be transformed into an $LL(k)$ grammar $G'$, that would mean that both $L(G^R)$ and $L(G') = L(G)$ are $LL(k)$.

But $LL(k)$ is not closed under reversal; there are $LL(k)$ languages whose reverse is no $LL(k)$. The classic demonstration that the set of $LL(1)$ languages is a proper subset of the set of $LR(1)$ languages also serves for this question.

The language $\{a^ib^j\mid 0 \le i\le j\}$ is $LL(1)$:

$$\begin{align}
S &\to A B\\
A &\to \epsilon \\
A &\to a A b\\
B &\to \epsilon \\
B &\to b B
\end{align}$$

However, its reverse $\{b^ja^i\mid 0 \le i \le j\}$ is not $LL(k)$ for any $k$, although the reverse is clearly $RR(1)$, since a n $RR(1)$ grammar for the reverse language can be constructed by simply reversing every production in the original grammar:

$$\begin{align}
S &\to B A\\
A &\to \epsilon \\
A &\to b A a\\
B &\to \epsilon \\
B &\to B b
\end{align}$$

(As it happens, the above grammar is LR(1). The language is an abstraction of the "dangling else" syntax.)


non LL(1) grammar but LL(1) language I'm reading a Basics of Compiler Design and on page 84 it is making the following statement:

  A language may well be LL(1) even though the grammar used to describe
  it is not.

Can someone give such an example? I'm not really sure how this is possible. I thought grammars generate languages, therefore if a grammar is non LL(1) then a language generated by it is also non LL(1). Apparently that is not the case.

Any help is appreciated.

Well a language is XX iff there exists an XX grammar for it. There might be other grammars for an XX language. For instance you might have a context-free grammar for what is actually a regular language.

Read the book. It contains techniques (with examples!) that show how some non-LL(1) grammars can be transformed into LL(1) grammars. The techniques are called elimination of left recursion and factorization.


Cost to convert one integer array into another This question is distilled from an interview question.
Given two arrays $a$ and $b$ containing $n$ integers each, change each integer in array $a$ into the corresponding integer in array $b$ by increasing or decreasing a single digit by $1$. What is the optimum algorithm?
The number of digits in $a[i]$ are the same as $b[i]$ and the length of arrays $a$ and $b$ are also the same.
An example, $a = [123, 456]$, $b= [124, 307]$. Then the minimum cost to convert array $a$ into array $b$ is 8.
I know of a naive solution to this question which of course is to count the number of increments to each digit but I'm wondering if there is a more efficient binary operation that can be used.

Let $\ell_{i}$ denote the number of digits in $a[i]$. Then the complexity of the naive algorithm as suggested by you is $O(\ell)$, where $\ell = \sum_{i = 1}^{n} \ell_{i}$.
Moreover, the algorithm must visit every digit at least once. For the sake of contradiction, suppose the algorithm did not visit some digit in the array. Then an adversary can modify the unvisited digit to a different digit. This will prove that your algorithm's output is incorrect. Therefore, any correct algorithm must require at least $\Omega(\ell)$  comparisons. Thus, you can not expect better than $\Theta(\ell)$ complexity for this problem.


What is the time complexity of text justification algo? The following algo is a simplified version of a text justification algo taken from dynamic programming lecture notes of MIT OCW.

I am confused why this particular algo has a time complexity of $\mathcal{O}(n^2)$ and not of $\mathcal{O}(n!)$ -:

function foo(int index) {
//some constant time operation like 2+2
       for( i = index + 1 to end ) {
           foo(i);
           }
}

Lets say end is 10.

So if foo(0) were called, the sequence of function calls would be something like this (correct me if I am wrong)-:

foo(0) = 9 calls to foo using (1 to 9)
Each foo(1) = 8 calls to foo using (2 to 9)
Each foo(2) = 7 calls to foo using (3 to 9)
and so on...

So it is $n * (n-1) * (n-2) ... * 1$ = $n!$

So shouldn't the time complexity be $\mathcal{O}(n!)$ ? Instead I find that in most cases this algorithm is represented as $\mathcal{O}(n^2)$.

Why is that ?

The original version was of the follwing form-:

DP[i] = min{DP[j] + badness(i,j), for (j in range(i+1,n+1))}

Where badness = (page width - total width of string) ^ 3

There are two problems, here. Your foo algorithm doesn't have $\Theta(n!)$ complexity and it isn't the proper tranlation of the dynamic programming system.

foo(0) makes calls with arguments $1, 2, \dots$. The call to foo(1) makes calls with arguments $2, 3, \dots$. So now we have two outstanding calls to each of foo(2), foo(3), .... Each call to foo(2) one more call for $3, 4, \dots$, so we now have four outstanding for each of those.  Thus, foo(i) gets called $2^{i-1}$ times.  The total number of calls is $\sum_{i=1}^n 2^{i-1}=2^i-1$.

But the main problems is that your foo isn't what the dynamic programming system does. The whole point of dynamic programming is to avoid making the same recursive call many, many times. To do this, you remember the results of the function in an array, precisely so you don't have to call the function again.  You can see this in the code fragment you posted: DP[j] isn't a function call, but an array look-up.


Savitch's theorem and time relation We know that $NTIME(t(n)) \subseteq DSPACE(t(n))$ and we know - by Savitch's theorem - that $NSPACE(s(n)) \subseteq DSPACE(s^2(n))$.

By the space/time relation $(s(n) \leq t(n))$ I know that $NTIME(t(n)) \subseteq NSPACE(t(n))$, then by Savitch's theorem $NSPACE(t(n)) \subseteq DSPACE(t^2(n))$ and not $DSPACE(t(n))$, as stated above.

Where am I wrong?

I believe you left out big-Os around those bounds.

In any case, $\; \{0\} \subseteq \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\} \;$ and $\; \{0\} \subseteq \{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.04 in}2\hspace{-0.02 in}\}$ , $\;$ even though $\: \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\} \neq \{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.04 in}2\hspace{-0.02 in}\}$ .


Dual-pivot Quicksort reference implementation? Has some sort of canonical - or reference - implementation of Dual-pivot Quicksort been posted anywhere?

I would like to include that algorithm in a comparison among sorting algorithms for a specialized need that I have, but the Java versions I've seen appear to have various kinds of tweaks applied to them, like using Insertion Sort for small (sub-) arrays, which makes it harder to compare the fundamentals.

I tried to do exactly such a comparison in my master thesis, which thus naturally includes pseudo-code of “basic” versions of several dual-pivot Quicksorts (there is a list of them on page 9).

Here is my basic implementation of Yaroslavskiy's algorithm (the dual-pivot scheme that is used in Java 7):

void sort(int[] A, int left, int right) {
    if (right > left) {
        // Choose outermost elements as pivots
        if (A[left] > A[right]) swap(A, left, right);
        int p = A[left], q = A[right];

        // Partition A according to invariant below
        int l = left + 1, g = right - 1, k = l;
        while (k <= g) {
            if (A[k] < p) {
                swap(A, k, l);
                ++l;
            } else if (A[k] >= q) {
                while (A[g] > q && k < g) --g;
                swap(A, k, g);
                --g;
                if (A[k] < p) {
                    swap(A, k, l);
                    ++l;
                }
            }
            ++k;
        }
        --l; ++g;

        // Swap pivots to final place
        swap(A, left, l); swap(A, right, g);

        // Recursively sort partitions
        sort(A, left, l - 1);
        sort(A, l + 1, g - 1);
        sort(A, g + 1, right);
    }
}

void swap(int[] A, int i, int j) {
    final int tmp = A[i]; A[i] = A[j]; A[j] = tmp;
}

The partitioning loop maintains the following invariant:

(Initially, the “?”-area is the whole array, at the end it is gone; the indices are moved in the direction indicated by the arrays, so $\ell$ and $k$ start at the left, $g$ at the right end of $A$.)

I did a mathematical average case analysis for these algorithms to determine the expected number of key comparisons, element swaps and also instruction counts for some specific low-level implementations (in Java Bytecode and MMIX, an RISC assembly language).

The main result is that Yaroslavskiy's algorithm uses $1.9n \ln n + O(n)$ comparison, which is 5% less than the $2n \ln n + O(n)$ comparisons of classic single-pivot Quicksort (both average case on random permutations).
However, it needs $0.6 n\ln n + O(n)$ swaps for that, where classic Quicksort only needs $\frac13 n \ln n + O(n)$ swaps;
similarly, my instruction counts also indicate that classic Quicksort is more efficient.
What exactly makes Java 7's dual-pivot algorithm faster remains an open question.
(In case you are interested in more details on that, I could elaborate further.)

Tweaks of the algorithm like switching to Insertionsort for subproblems smaller than some (constant) threshold or optimizing code outside the partitioning loop (while(k <= g) { ... }) will only change the numbers hidden by $O(n)$.
This means that for large lists, they are not important.
For practical input sizes, they still help a lot, so having them in library code is a must.


RAM and the degrees of freedom This question is about computation/computational physics.

Imagine that you want to solve $10^6$ equations of motion, and you have $10^6$ degrees of freedom (position of the particle).

How many RAM memory would you need (theoretically) to do this?

(I am not interested in the final answer, I am just interested in the thinking of estimate this.)

Thank you

As a first approximation, most of the memory will be spent on storing $10^6$ floating point numbers (one per degree of freedom). Assuming double precision numbers are used, each number takes up 8 bytes, for a total of 8MB.


Can integer linear programs have non-integer OPT solutions? Why is it that every integer linear program has optimal solutions that are integers? At least in online text books, they are always integers. Can solutions of ILPs only be integers?

Something that might be causing you confusion: "integer linear programming", by definition, restricts the variables to integer values.
Linear programming instances in which the input numbers are integers can easily have only non-integer solutions. Consider:

$\begin{cases}
\begin{alignat}{1}
2 &\cdot x \le 1
\\[1.5ex]
-2 &\cdot x \le -1
\end{alignat}
\end{cases}$


Normalizing edge weights and the effect on Dijkstra's algorithm If I had a graph $G$ with some negative edge weights, clearly Dijkstra's algorithm does not definitely halt, since it might get caught in a negative cycle (shedding infinite weight). However, would finding the minimum weight (most negative weight) $w$ and adding the absolute value to every edge's weight preserve the shortest path, and get rid of the possibility of a negative cycle in one fell swoop? I can't seem to find any good literature on this, which makes me think that it can't be true.

Your idea does not work. Adding an absolute value to every edge wont preserve shortest paths. To see this take this graph:

u------v
|      |
|      |
a------b

with all edge weights 1 except for $uv$ where the weight is 4. The shortest $uv$ path goes via $u \to a \to \to b \to v$. But if you add a +2 to every edge, the sortest $uv$ path is $u\to v$.

There is however a reweighting scheme that works. Check out Johnson's algorithm, which is built around this. Simply speaking: add a dummy vertex $x$ connected to all other vertices with a zero weight edge and add to every weight of an edge $(i,j)$ the value $d(x,i) - d(x,j)$.


Proof for P-complete is not closed under intersection Unfortunately I have no idea how to show this:

  Show that the set of ${\sf P}$-complete languages is not closed under intersection.

As far as I understand my lecture notes, ${\sf P}$-completeness is defined as follows:

$A \subset \Sigma^{*}$ is complete for ${\sf P}$ iff $A \in \text{P}$ and $\forall B \in {\sf P}, B \le_L A$
$\le_L$ is ${\sf LOGSPACE}$-reduction: for $A,B \subset \Sigma^{*}$, the relation $A \le_{L} B$ is defined by
$$A \le_{L} B \quad\text{iff}\quad \exists f \in {\sf FLOGSPACE}, (x \in A \Leftrightarrow f(x) \in B)$$

Let $A$ be any P-complete problem (say circuit evaluation). Here are two other P-complete problems: $A_0 = \{0x : x \in A \}$ and $A_1 = \{1x : x \in A\}$. The problem $A_0 \cap A_1 = \emptyset$, while definitely in P, isn't P-complete. The latter is true even if we allow Turing reductions, assuming $L \neq P$.


Use dynamic programming to merge two arrays such that the number of repetitions of the same element is minimised Let's say we have two arrays m and n containing the characters from the set a, b, c , d, e. Assume each character in the set has a cost associated with it, consider the costs to be a=1, b=3, c=4, d=5, e=7.

for example

m = ['a', 'b', 'c', 'd', 'd', 'e', 'a']
n = ['b', 'b', 'b', 'a', 'c', 'e', 'd']

Suppose we would like to merge m and n to form a larger array s.

An example of s array could be

s = ['a', 'b', 'c', 'd', 'd', 'e', 'a', 'b', 'b', 'b', 'a', 'c', 'e', 'd']

or

s = ['b', 'a', 'd', 'd', 'd', 'b', 'e', 'c', 'b', 'a', 'b', 'a', 'c', 'e']

If there are two or more identical characters adjacent to eachother a penalty is applied which is equal to: number of adjacent characters of the same type * the cost for that character. Consider the second example for s above which contains a sub-array ['d', 'd', 'd']. In this case a penalty of 3*5 will be applied because the cost associated with d is 5 and the number of repetitions of d is 3.

I need to design a dynamic programming algorithm which minimises the cost associated with s.

Does anyone have any resources, papers, or algorithms they could share to help point me in the right direction?

Here is an algorithm that computes the minimum cost that is about as simple as possible and as fast as possible.

Count the total number of each character in $m$ and $n$. Let them be $c(a), c(b), \cdots$ respectively. Let $x$ be one of $a,b,\cdots$ such that $c(x)$ is the maximum.
Let $\sigma$ be the sum of all $c(i)$ where $i$ goes through $a, b, \cdots$ except $x$.

If $c(x)\le 1 + \sigma$, return 0.
Else return $p(x)(c(x) -\sigma))$, where $p(x)$ is the penalty associated with $x$.

The time-complexity of the algorithm is $O(\ell)$, where $\ell$ is the sum of the length of $m$ and the length of $n$.

Since the algorithm above is simple and clear, there is no need to apply the heavy machinery of dynamic programming.

Exercises

Here are two exercises that prove the correctness of the algorithm above.

Exercise 1.  If $s(x)\le 1 + \sigma$, design a procedure to produce a merged array that does not have adjacent pairs of the same letter.

Exercise 2.  If $s(x)\gt 1 + \sigma$, then any merged array must have at least $s(x) -\sigma$ $x$s each of which is adjacent to another $x$. Design a procedure to produce a merged array that has no other penalties except for $s(x) -\sigma$ $x$s.


Search for range in continuous function satisfying some condition I am attempting to define an optimization for the following problem: given a graph find the largest interval(s) where S > S_th (the narrower the interval the smaller S will be) and P < P_th (the wider the interval the higher P will be).

I am not 100% certain the claims in parenthesis are always correct as, I think, it is affected by the distance between the Red and Green graphs.

The graphsR and G are KDEs generated with Gaussian functions, therefore continuous.
I already know that the conditions can be true only where the Red graph is above the Green one. I therefore find the intersections between the graphs (e.g. with brentq) and find relevant intervals by calculation a single point in them.
Below are a few examples of graphs I want to analyze. The blue vertical lines mark graph intersections; blue horizontal lines with the condition results on top are shown only when the conditions were met for the whole interval.
The vertical and horizontal lines in black are generated from a ML algorithm which I want to replace with a numerical calculation. As it can be seen it,  usually, finds intervals that are smaller then the whole area where red is on top.
Example 1: ML algo found better solution on the right section, neither found the left one interesting.

Example 2: on the right you can see the ML algo suggesting a range not quite between the blue lines. I am OK with the new algo clipping the portion on the left.

Example 3: showing that there may be more than one interesting range per marked section.

Example 4: ML algo missed the leftmost range

Let $x_1,x_2,\dots,x_n$ denote the $x$-values where the two curves intersect; you say you know how to find these.  Let's add $x_0=-\infty$ and $x_{n+1}=+\infty$.  Then in each interval $[x_i,x_{i+1}]$, either the red curve is consistently above the green curve or vice versa, so label that interval with the color of the curve that is on top.  This is easy to do by picking an arbitrary $x$-value in $(x_i,x_{i+1})$ evaluating the height of both points at that point.
Now your problem reduces to the following: find $x_i,x_j$ that maximize $x_j-x_i$, such that all of the intervals $[x_i,x_{i+1}],[x_{i+1},x_{i+2}],\dots,[x_{j-1},x_j]$ are labelled red.
This problem can be solved in a straightforward way, in linear time.  Iterate through $j:=1,2,\dots,$, scanning from left-to-right, keeping track of the smallest $i$ such that all intervals between $x_i..x_j$ are labelled red.  Thus, when you encounter a red interval $[x_{j-1},x_j]$, you do nothing; when you encounter a green interval $[x_{j-1},x_j]$, you reset $i := j$.  Keep track of the longest range you've found so far as you do the linear scan.


Is asymptotic ordering preserved when taking log of both functions? In one of my exercise sheets I have the following question;

Let $f,g\colon \mathbb{N}\longrightarrow\mathbb{R}$ be positive functions with $f(n) \in O(g(n))$. Prove or disprove;  $\ln(f(n)) \in O(\ln(g(n))$.

I first thought this would be the case since $\ln$ is a monotonically increasing function (derivative is positive), and so the asymptotic ordering of these functions wouldn't be affected. But then there was an example stuck in my mind and which I have later on seen on the internet as well.

Let $f(n) = 2^n,g(n)=3^n$. Since $f(n) \in O(g(n))$ given $\lim_{n\to \infty} \frac{3^n}{2^n}=\infty$. Then $\ln(f(n))=n\ln 2$ and $\ln(g(n))=n\ln 3$ which leads to $ 0< \lim_{n\to \infty} \frac{n\ln 3}{n\ln 2} < \infty$ which implies $\ln (f(n)) \in \Theta(\ln(g(n)))$. The growth rates have changed, yes, but since $\Theta(f) = O(f) \cap\Omega(f)$ isn't, technically speaking, $\ln(f(n)) \in O(\ln(g(n)))$? I am a bit confused as going by my own steps the initial assumption seems right but I am not entirely convinced for either possibility. Because if this is correct I feel like I can extend the same idea for exponentiation as well maybe.

Anything to prove or disprove the statement with an explanation would be really welcome as I am a bit lost at the moment.

If $f(n) = \Theta(g(n))$, then in particular $f(n) = O(g(n))$. This is just like saying that if $x = y$, then in particular $x \leq y$.

Suppose that $f(n) = O(g(n))$. According to the definition, there are $N,c$ such that all $n \geq N$ satisfy $f(n) \leq cg(n)$. Taking logarithms, this implies that $\log f(n) \leq \log c + \log g(n)$. Does this imply the existence of a constant $c'$ such that for large enough $n$, $\log f(n) \leq c' \log g(n)$?

Here is a simple counterexample: $f(n) = e$ and $g(n) = 1$. Clearly $f(n) = O(g(n))$, but $\log f(n) = 1$ whereas $\log g(n) = 0$. However, in this case $\log g(n)$ is not positive, so you may want to rule that case out. However, we can correct this example so that $\log g(n)$ is strictly positive, by taking $g(n) = 1 + 1/n$. In this case $\log g(n) = 1/n$ which is strictly positive, yet still $\log f(n)$ is not $O(\log g(n))$.

Here is a sufficient condition for the deduction to work. Suppose that there exists $N'$ and $C > 1$ such that for all $n \geq N'$, it holds that $g(n) > C$. Then for $n \geq \max(N,N')$, we have
$$\log f(n) \leq \log c + \log g(n) \leq \left( \frac{\log c}{\log C} + 1 \right) \log g(n),$$
and so $\log f(n) = O(\log g(n))$.


Traveling Salesman Problem: Big O Complexity of Algorithm I'm trying to figure out how to do this problem in my intro algorithm class, but I'm a little confused.

  The Traveling Salesman problem (TSP) is famous.  Given a list of
  cities and the distances in between them, the task is to find the
  shortest possible tour that starts at a city, visits each city
  exactly once and returns to a starting city. A particular tour can be
  described as list of all cities [c1,c2, c3, ... ,cn] ordered by the
  position in which they are visited with the assumption that you return
  from the last city to the start.This is a hard problem, that is, there
  is no known efficient solution for this problem and we are not
  expecting one any time soon. Your task is to analyze the following
  brute force approach to solving the problem:

  Consider the following algorithm for solving the TSP:

n = number of cities
m = n x n matrix of distances between cities
min = (infinity)
for all possible tours do:
    find the length of the tour
    if length < min:
         min = length
         store tour

  State the worst-case (big-O) complexity of this algorithm in terms of
  (number of cities)?You may assume that matrix lookup is one step
  O(1). For deriving big-O here, you need not count the if-statement or
  the for-loop conditional (i.e., testing to see when the for-loop is
  done), or any of the initializations at the start of the algorithm.

So far I know that there are 2 statements that will be executed after the if statement and I think there n! permutations of tours. Am I correct so far. How would I figure out the amounts of steps for "find the length of tour"?

You've almost got it! Remember, you're going to visit each city exactly once in a tour. Which means you have to look up $n-1$ distances for each one. This is $O(n)$, since the problem specifies that matrix lookup is assumed to be $O(1)$.


Upper bound $T(n) = 9T(\sqrt[3]{n}) + O(1)$ The problem is this: Use the recursion-tree method to give a good asymptotic upper bound on $$ T(n) = 9T(\sqrt[3]n) + \Theta(1). $$ I am able to get the tree started and find a pattern with the sub-problems, but I am having difficulty finding the total cost of the running times throughout the tree. I cannot figure out how to get the number of sub-problems at depth $i$ when $n=1$. I have a feeling the answer is $O(\log_3 n)$, but I cannot verify that at the moment. Any help would be appreciated.

The recurrence can be written as $$T(n) = 9T(\sqrt[3]n) + C, $$ where $C$ is some constant, since any constant will always be treated as 1 asymptotically. My recursion tree is explained by each level below:

Level 0: This is the constant $C$

Level 1: $T(\sqrt[3]n)$ is written 9 times which represent the sub-problems of $C$. This adds up to $9C\sqrt[3]n$.

Level 2: Each of the 9 sub-problems from level 1 gets divided into 9 more sub-problems, which are each written as $T(\sqrt[9]n)$. All of these add up to $81C\sqrt[9]n$.

Sub-Problem Sizes and Nodes: The number of nodes at depth $i$ is $9^i$. We know that the sub-problem size for a node at depth $i$ is $n^{1/3^i}$. The problem size hits $n=1$ when this size equals 1. Solving for $i$ yields:

$$ (n^{1/3^i})^{3i} = 1^{3i} n = 1^{3i}. $$

This results in $n$ being 1 which doesn't give a logarithmic form!

You can solve this using the master theorem, whose proof uses a recursion tree argument.

Define $S(n) = T(2^n)$. The main observation is that $\sqrt[3]{2^n} = 2^{n/3}$, and so
$$ S(n) = 9S(n/3) + O(1). $$
The solution is $S(n) = \Theta(n^2)$, and so
$$ T(n) = S(\log n) = \Theta(\log^2 n).$$

You can also open the recurrence directly, obtaining
$$
T(n) \propto 1 + 9n^{1/3} + 9^2 n^{1/3^2} + 9^3 n^{1/3^3} + \cdots.
$$
The general term is $9^i n^{1/3^i}$. The recurrence will terminate when $n^{1/3^i} \approx 1$, which happens when $3^i \approx \log n$, that is, when $i \approx \log_3 \log n$. For this value of $i$, $$ 9^i = 3^{2\log_3 \log n} = \log^2 n. $$
This is the value of the bottom level of the tree. The contribution of the other levels is negligible in comparison, which is something you have to prove by calculation.


The set of valid sentences in FO is not decidable as a consequence of rec. inseparability Two given languages $L_1$ and $L_2$ are called recursively separable iff there exists a recursive languge $R$ such that $L_1 \subseteq R$ and $L_2 \cap R = \emptyset$.

Now consider first order logic, and some finite axiomatisation of $\mathbb N$ in it (surely this is way to weak, as we have no induction). Then we have three sets, 1) the set of valid sentences, i.e. the ones derivable the the rules of first order logic, 2) the set of provable sentences using the axioms of $\mathbb N$, and the set of truth sentences, i.e. the ones fullfilled by $\mathbb N$. Also as a superset of all these, we have the set of first order sentences that have some model, and contrary to that the set of sentences that are unsatisfiable, i.e. have no model, which equals (by Completeness of first order logic) the set of inconsistent sentences.

Now, the following holds:

Theorem: The set of unsatisfiable sentences and the set of sentences provable from the choosen axioms of $\mathbb N$ are not recursively separable.

From this it follows that the set of provable sentences from the axioms itself, as well as the set truth sentences, as well as the set of satisfiable sentences, are all not recursive/decidable.

But does this implies that the set of valid sentences is not decidable? This is states in the classic text Computational Complexiy by Cristos H. Papadimitriou, on page 133. But as this set is a proper subset of the provable sentences, I do not see that this is implied by the above Theorem? Or am I missing anything?

The chosen finite axiomatization of $\mathbb N$ is consistent, since $\mathbb N$ is a model for them. Hence, any sentence provable from it must be satisfiable (e.g. by $\mathbb N$).

From this, we get that the set of provable sentences is disjoint from the set of unsatisfiable formulas.

Hence, the set of unsatisfiable formulas must be undecidable, otherwise we would have separability (taking $R$ to be the set of unsatisfiable formulas), and we would contradict the theorem.

Hence, the set of valid formulas must be undecidable as well, since we have the reduction "$P$ unsatisfiable $\iff \lnot P$ valid" (also mentioned by SimonJ above).


Regular expression to show that all strings contain each symbol atleast once I'm studying for my exam and I came across the following exam question from last year, the only way I know how to solve this is build a regex that accounts for all six different series of letters so for example to recognize a string that has the letters a,b and c occur in that order:

$(a+b+c)^*a(a+b+c)^*b(a+b+c)^*c$

The question:
Give a regular expression r over the alphabet A = {a, b, c} such that the
language determined by r consists of all strings that contain at least one occurrence of each symbol in A. Brieﬂy explain your answer.

Your solution looks good to me, and it is probably what they expect of you.

It is interesting to consider the more general question: how large does a regular expression for this language be, as a function of the size of the alphabet? Denoting the size of the alphabet by $n$, Theorem 9 here shows a lower bound of $\Omega(c^n)$ for some (explicit) $c > 1$. (The theorem is for context-free grammars, but a regular expression can be translated to a context-free grammar.) Your construction is $O(n\cdot n!) = 2^{O(n\log n)}$, so there is a some gap here.


Greedy algorithm for vertex cover Given a graph $G(V, E)$, consider the following algorithm:

Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$)
Let $v$ be one of the vertices with degree equal to $d$
Remove all vertices adjacent to $v$ and add them to the proposed vertex cover
Repeat from step 1. until in $G$ there are only vertices with degree $0$ (no edges in the graph)

At the end the removed vertices are a vertex cover of the given $G(V, E)$, but is it a minimum vertex cover? Is there an example where the algorithm does not find a minimum vertex cover?

Start with a clique on the vertices $A,B,C,D$.
Connect $A,B$ to a new vertex $a$.
Connect $B,C$ to a new vertex $c$.
Connect $a,c$ to a new vertex $b$.
The vertex $b$ is the only one of degree 2, so your algorithm will start by adding $a,c$ to the vertex cover. The remaining graph consists of the clique $A,B,C,D$ and the isolated vertex $b$, so the algorithm will add 3 more vertices, ending up with a vertex cover of size 5.
In contrast, the 4 vertices $A,B,C,b$ cover all edges.


Showing that the language of graphs and nodes on an odd cycle is in NL Let L be the language containing all the pairs (G,v) where G is a directed graph and v is a vertex in G such that G contains a cycle that contains v and the number of different vertices that appear in that cycle is odd. Find the smallest class (NP, P or NL) that contains L.

Clearly L is in NP, I didn't manage to show that it is in P so I tried to show that it's NP-Complete, however the answer in the textbook is NL?

The question is ambiguous. Specifically, it is not clear what "different vertices that appear in that cycle" means. It can mean two things (1) the size of the set of nodes that appear in the path, or (2) the total number of nodes in that path, i.e., the length of that cycle (minus 1).

If the interpretation is (2), then the language is clearly NL:
you perform a random walk (of length $\le n$), counting the number of nodes you see. If you get back to $v$ and the number of nodes is odd, you accept, otherwise you reject.

If the interpretation is (1), I don't see an immediate way to show it is in NL.


How to reduce UNSAT problems so that less than $7/8+\epsilon$ of clauses are unsatisfied? In this question I ask about what use is a solver that can find an assignment that satisfies, say, 90% of the clauses of a known satisfiable 3SAT problem in polynomial time.  The answer seems to be: given a problem ϕ that may or may not be satisfiable, you perform a reduction on an input formula ϕ to another formula ϕ′ such that ϕ′ is 90% satisfied iff ϕ is SAT and run my hypothetical algorithm on ϕ′, which will tell you if ϕ is SAT or not.

My question is a follow-up: what is the reduction from ϕ to ϕ'?

The reference is Håstad's classic paper, Some optimal inapproximability results. It relies on the PCP theorem and on Raz's parallel repetition theorem. The proof is not particularly easy, and even the reduction itself is not so simple to state (if you take into account the PCP component).


Is it possible to produce different shortest path trees using bellman ford and Dijkstra algorithm? Given a graph G=(V,E)  with positive edges weights, Is it possible to produce  different shortest path trees for the Bellman-Ford algorithm and Dijkstra's algorithm?

If there are multiple shortest paths (equal distances), you could get different results even between two runs of Bellman Ford, if for instance, the two runs consider edges in different orders.  But, for any graph with unique shortest paths, they obviously must both return the unique answer.


What is more effective, a do while or a while? I mean, with the same code, if I modify a do while into a while in this way:

do {$S;$} while ($B$) into a $S;$ while ($B$){$S;$} , there is any change
in the code?

B = condition

S; = instructions

While and do while differ only in the first execution when condition is false. If you ignore this difference it boils down to the place of condition check, in while the condition is checked and if it is true the statements are executed. In the do while the condition check is executed after the block execution.

The code is exactly the same, with one line reordered.

If you want to do micro-optimisations please check whether these are worthy of your time. Compiler does really great job nowadays, unless it doesn't then change the compiler.

So under the hood they are equivalent.


Let $ L = \{ \langle M \rangle : L(M) = \Sigma^* -\{\epsilon\} \}$, Show that $L\notin RE$ Let $ L = \{  \langle M \rangle : L(M) = \Sigma^* -\{\epsilon\} \}$

Determine whether $ L\in RE, \space L\in R, \space L\in co-RE$, or none of the above.

I tried to show a reduction function from $L_{\Sigma^*}$ to $L$ to prove that $L\notin RE$ , here is my attempt:

$\forall M\in L_{\Sigma^*} : f(M) = M'$, where M' is a Turing machine which works as follows:

$\forall w\in \Sigma^*: $ if $w=\epsilon$ accept w; Otherwise run M on w and answer as M.

I manged to show that if $X \in L_{\Sigma^*}$ than $f(X)\in L$, but the other direction ($X \notin L_{\Sigma^*}$ than $f(X)\notin L$) seems to be more problematic and I'm not sure that reduction will even work.

I will appreciate any direction.

Btw, I'm new to reduction so please try to be patient and understanding.

Thanks!

Hint: Let $L_{\Sigma^*}$ the language of descriptions of Turing machines halting on all inputs. Choose some computable surjective mapping from $\Sigma^+$ to $\Sigma^*$, and use it to reduce $L_{\Sigma^*}$ to $L$. Since $L_{\Sigma^*}$ is neither RE nor coRE, it follows that the same holds for $L$.


Boyce-Codd Normal Form vs. 3rd Normal Form Any schema that satisfies BCNF also satisfies 3NF. But how can this be true if BCNF does not necessarily guarantee dependency preservation, whereas 3NF guarantees dependency preservation?

Because they are two different concepts.

A schema satisfies 3NF iff for every functional dependency in the relation such as X -> A, X is a key or A is prime (part of the key).

A schema satisfies BCNF iff for every functional dependency in the relation such as
X -> A, X is a key.

You can clearly see from these definitions that every BCNF must also satisfy 3NF. However, precisely for the reason that to achieve BCNF you may need some extra splitting on the relations, it could be impossible to preserve all the FDs.

I'll give you an example: say you have a relation

R(A, B, C, D, E)

With FDs:

ABCD -> E
E -> BCD

This relation is in 3NF since E depends on the key and BCD is prime; however, since BCNF doesn't have the prime clause, the relation fails BCNF due to E -> BCD.

On the other hand, when you break down the relation to meet BCNF

R1(E, B, C, D), R2(A, E)

the FD ABCD -> E is lost because of the over-splitting we had to do.


How to convert 010111 to decimal using only odd numbered positions while still applying the correct positional exponent? I am trying to understand what this question is asking in terms of conversion. I know how to convert binary to decimal and vice versa, but the method you need to use has me confused.

I need to convert 010111 to decimal using only odd numbered positions while still applying the correct positional exponent in the conversion. What I did was take every odd numbered position from base 2 digit from 010111 so "111" I skipped every other number and took the digit from that position (if that makes sense) I only had three digits so I added a 0 to make it 4 bit 0111 which equals 7 in decimal. I know this is wrong but why??

This is the question: - Imagine that a processor is faulty and reads only odd-numbered positions when converting binary numbers to decimals, but it applies the correct positional exponent in the conversion. In radix 10, the binary number 010111 converted by this processor would be:

The mock test answer says the result is 2 but I cannot figure out why

I'm assuming positions are counted from $1$ starting from the least significant bit.

In this case you're using the exponents as if the number was 0111.
The question is asking to use the same exponents you would use for the odd-position digits of the number 010111.

To break it down, from the least to the most significant bit, the contribution to the final decimal value of each digit is:

First digit: $1 \cdot 2^0 = 1$.
Second digit: would be $1 \cdot 2^1 = 2$ but it is 0 since digits in even position are ignored.
Third digit: $1 \cdot 2^2 = 4$.
Fourth digit: ignored.
Fifth digit: $1 \cdot 2^4 = 16$.
Sixth digit: ignored.

The final result is: $16+4+1 = 21$.

Edit: Since you added that the answer should be $2$ this tells us that positions are either numbered starting from $0$, from the least to the most significant bit, or starting from $1$ from the most to the least significant bit.

In either case you would select the bits $001$ whose contribution would be $1 \cdot 2 + 0 \cdot 2^2 + 0 \cdot 2^4 = 2$.


Functional Dependencies in Relations I'm currently reading about functional dependencies.
I've read Armstrong's axioms about:

Relexivity: $if$ $B\subseteq A$ $then$ $A\to B$
Augmentation: $if A\to B$ $then$ $AC\to BC$
Transitivity: $if A\to B$ $and$ $B\to C$ $then$ $A\to C$

and also about:

Union Rule: $if A\to B$ $and$ $A\to C$ $then$ $A\to BC$
Decomposition Rule: $if A\to BC$ $then$ $A\to B$ $and$ $A\to C$

I also know that for a relation R(A, B, C, D, E) that:
$if A\to B$ $then$ $ACDE\to B$.
 In fact, the left side could be any superset of A.
Is there a name for this rule?
I've looked at various books but while they use it in examples, they never mention a name.

While I'm unaware that your suggested rule has a name and couldn't find it in any texts on my shelf, it's a consequence of reflexivity and transitivity, as you probably know already. Here's how:
$$
\begin{align}
ACDE &\rightarrow A &\text{(reflexivity)}\\
A &\rightarrow B &\text{(hypothesis)} \\
ACDE&\rightarrow B &\text{(transitivity)}
\end{align}$$


How to prove that a language is not context-free? We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free.

How do I show the opposite, though? My TA has been adamant that in order to do so, we would have to show for all grammars (or automata) that they can not describe the language at hand. This seems like a big task!

I have read about some pumping lemma but it looks really complicated.

To my knowledge the pumping lemma is by far the simplest and most-used technique. If you find it hard, try the regular version first, it's not that bad. There are some other means for languages that are far from context free. For example undecidable languages are trivially not context free.

That said, I am also interested in other techniques than the pumping lemma if there are any.

EDIT: Here is an example for the pumping lemma: suppose the language $L=\{ a^k \mid k ∈ P\}$ is context free ($P$ is the set of prime numbers). The pumping lemma has a lot of $∃/∀$ quantifiers, so I will make this a bit like a game:

The pumping lemma gives you a $p$
You give a word $s$ of the language of length at least $p$
The pumping lemma rewrites it like this: $s=uvxyz$ with some conditions ($|vxy|≤p$ and $|vy|≥1$)
You give an integer $n≥0$
If $uv^nxy^nz$ is not in $L$, you win, $L$ is not context free.

For this particular language for $s$ any $a^k$ (with $k≥p$ and $k$ is
a prime number) will do the trick. Then the pumping lemma gives you
$uvxyz$ with $|vy|≥1$. Do disprove the context-freeness, you need to
find $n$ such that $|uv^nxy^nz|$ is not a prime number.

$$|uv^nxy^nz|=|s|+(n-1)|vy|=k+(n-1)|vy|$$

And then $n=k+1$ will do: $k+k|vy|=k(1+|vy|)$ is not prime so $uv^nxy^nz\not\in L$. The pumping lemma can't be applied so $L$ is not context free.

A second example is the language $\{ww \mid w \in \{a,b\}^{\ast}\}$. We (of course) have to choose a string and show that there's no possible way it can be broken into those five parts and have every derived pumped string remain in the language.

The string $s=a^{p}b^{p}a^{p}b^{p}$ is a suitable choice for this proof. Now we just have to look at where $v$ and $y$ can be. The key parts are that $v$ or $y$ has to have something in it (perhaps both), and that both $v$ and $y$ (and $x$) are contained in a length $p$ substring - so they can't be too far apart.

This string has a number of possibilities for where $v$ and $y$ might be, but it turns out that several of the cases actually look pretty similar.

$vy \in a^{\ast}$ or $vy \in b^{\ast}$. So then they're both contained in one of the sections of continguous $a$s or $b$s. This is the relatively easy case to argue, as it kind of doesn't matter which they're in. Assume that $|vy| = k \leq p$.

If they're in the first section of $a$s, then when we pump, the first half of the new string is $a^{p+k}b^{p-k/2}$, and the second is $b^{k/2}a^{p}b^{p}$. Obviously this is not of the form $ww$.
The argument for any of the three other sections runs pretty much the same, it's just where the $k$ and $k/2$ ends up in the indices.

$vxy$ straddles two of the sections. In this case pumping down is your friend. Again there's several places where this can happen (3 to be exact), but I'll just do one illustrative one, and the rest should be easy to figure out from there.

Assume that $vxy$ straddles the border between the first $a$ section and the first $b$ section. Let $vy = a^{k_{1}}b^{k_{2}}$ (it doesn't matter precisely where the $a$s and $b$s are in $v$ and $y$, but we know that they're in order). Then when we pump down (i.e. the $i=0$ case), we get the new string $s'=a^{p-k_{1}}b^{p-k_{2}}a^{p}b^{p}$, but then if $s'$ could be split into $ww$, the midpoint must be somewhere in the second $a$ section, so the first half is $a^{p-k_{1}}b^{p-k_{2}}a^{(k_{1}+k_{2})/2}$, and the second half is $a^{p-(k_{1}+k_{2})/2}b^{p}$. Clearly these are not the same string, so we can't put $v$ and $y$ there.

The remaining cases should be fairly transparent from there - they're the same ideas, just putting $v$ and $y$ in the other 3 spots in the first instance, and 2 spots in the second instance. In all cases though, you can pump it in such a way that the ordering is clearly messed up when you split the string in half.


Finite Automata Input Confusion I am looking at the following non-deterministic finite automata which accepts all strings that end with at least 2 bs.  I am wondering what would happen when you have the input string 'abba' with this automata:

The possible computations I have so far are

q0, q0, q0, q0, q0

q0, q0, q1, q2, ??

q0, q0, q0, q1, ??

Would anyone be able to fill in the '??'s in this automata and be able to explain why they occur?

If you're at a state $q$ reading $\alpha$ and there is no outgoing edge labeled $\alpha$, then there is way to extend the computation path. In view of that, the only valid computation path upon reading $abba$ is $q_0,q_0,q_0,q_0,q_0$; in fact, the same is true for any word ending in $a$, whose computation paths are of the form $q_0,\ldots,q_0$. Words ending in $b$ have the additional computation path $q_0,\ldots,q_0,q_1$, and words ending in $bb$ have the additional computation path $q_0,\ldots,q_0,q_1,q_2$, making three in total.


Doubt regarding binary trees and counting Question:

A binary Tree T is semi-balanced, if for every node m  in T:
$$
\frac{R(m)}{2} <= L(m) <= 2*R(m)
$$
where, L(m) is the number of nodes in the left sub-tree of m and

R(m) is the number of nodes in the right sub-tree of m.

Write a recurrence relation to count the number of semi-balanced binary trees with N nodes.

My Attempt:

Let T(N) denote the number of semi-balanced trees with N nodes.

For N = 1, T(N) = 1 (Trivial)

For N > 1, T(N) can be found by splitting N into 3 parts, a root, a left subtree and a right subtree, let M be the number of nodes in the left portion, then the N - M - 1 is the number of nodes in the right portion, so by the constraint in the question,

$$
\frac{N-1}{3} <= M <= \frac{2*(N-1)}{3}
$$

So for N > 1,$$
T(N) = \sum_{M=\frac{N-1}{3}}^{\frac{2*(N-1)}{3}} T(M) * T(N-M-1)
$$

However, the answer is given as,$$
T(N) = \sum_{M=\frac{N-1}{3}}^{\frac{2*(N-1)}{3}} 2 * T(M) * T(N-M-1)
$$

Why is there a factor of 2 in the solution?

I think your answer is correct. Without bothering with recursive relations, we can observe that the only semi-balanced binary trees are perfect trees.

In fact, the only semi-balanced binary trees of heights $1$ and $2$ respectively are perfect (obvious for height $1$, casework for height $2$). Now, assume by inductive hypothesis that all semi-balanced binary trees of height at most $n$ are perfect trees. By definition, the root of a semi-balanced binary tree of height $n+1$ must have two semi-balanced subtrees as children, one of which has height $n$. By inductive hypothesis, that subtree is exactly the perfect binary tree of height $n$. By inductive hypothesis and definition of semi-balanced binary tree, the other subtree must therefore be too the perfect binary tree of height $n$, which completes the proof.

We can see that for e.g. $N=7$ the presence of a factor $2$ yields a wrong answer.

Nitpicky thing: you should take the upper integer part of the lower limit of the sum, and the lower integer part of the upper limit.