having issue with numbers in Polymorphic Lambda Calculus It is said that Church Numbers are encoded as following

   c0 = λX. λs:X->X. λz:X. z;
   c1 = λX. λs:X->X. λz:X. s z;
   c2 = λX. λs:X->X. λz:X. s (s z);
   c3 = λX. λs:X->X. λz:X. s (s (s z));

The church numbers are terms, right? but the terms are given by the following syntax.

  t ::=                          terms
       x                          //variable
       λx:T.t                     //abstraction
       t t                        //application
       λX<:T.t                    //type abstraction
       t [T]                      //type application

It seems church numbers do not respect the syntax of terms to me, strange.

I think it should be like

      c0 = λX<:some type here. λs:X->X. λz:X. z

So, how to write church numbers in a consistent way?

If possible provide simple examples to explain, i.e.  2 * 2, how to write this?

source1

Thanks in advance!

The syntax you written is probably of the System F<:.

However, the typed Church numerals you written are introduced in the context of System F (a.k.a. λ2) at Fig. 11 of the source pdf.

The terms of System F are defined like below in Types and programming languages (Benjamin C. Pierce, MIT press, 2002):

t ::=           terms:
      x         variable
      λx:T.t    abstraction
      t t       application
      λX.t      type abstraction
      t [T]     type application

The typed Church numerals at Fig. 11 are terms in this definition.

Moreover, in System F<:, Church numerals are also well-typed and can be more generalized. Below examples are taken from Types and programming languages. Top is the maximum type.

szero = λX<:Top. λS<:X. λZ<:X. λs:X→S. λz:Z. z;
sone  = λX<:Top. λS<:X. λZ<:X. λs:X→S. λz:Z. s z;


Some Questions related to Linear programming I have some question related to the Linear Programming problem:

If we have an objective function that needs to be maximized and let the feasible region be unbounded such that there is no finite optimum solution. My question is what is the meaning of "finite" here?
If we need to solve LP using the simplex method, we need to transform any constrain that is written as an inequality equation to equality equation using the addition of the slack variables, so my question is by doing this modification did we change the problem? I mean that we have added an extra variable so I think that we have created a new constraint?
Also to solve the LP using simplex method, we need to have a maximization problem, so if we have to minimize an objective function, in this case to transform it to a maximization problem all we need to do is to negate the coefficients? For example, we need to minimize $3x+y=2$; is this equivalent to maximizing $-3x-y=2$?

Let me answer your questions one by one:

The solution of the linear program $\max x$ is $\infty$. This is an example with not finite optimum solution. This is the same as just having no optimum solution.
When adding slack variables, the optimum value remains unchanged. As an example, you change $x \geq y$ to the equivalent $x = y+z$, where $z \geq 0$.
You never minimize $3x+y=2$. What you minimize is a linear function, not an equation. Minimizing $3x+y$ and maximizing $-(3x+y)$ are the same.


Is deep learning appropriate to approximate dynamic programming problems? I have a problem which can be completely solved using dynamic programming, but in a very intractable way (On^4, where n is around 1000).  I won't get into the details of the problem since it's a bit complicated, but it involves comparing properties of subsequences of a single string, where the property of subsequence (xi... xj) is related in a complex way to the property of subsequence (xi... xj + 1). I am fine with getting an approximation of the correct answer, but obviously would like to maximize correctness and minimize compute.

I have a well-defined metric for how good an answer is, but I have no idea what approach I should be using to solve it.  I was thinking about turning it into a reinforcement learning problem for a deep neural network, as a way of avoiding having to find the best algorithm myself.  I realized that I have no intuition for the kind of "algorithmic" problems for which deep reinforcement learning fits well.  For instance, playing Go well was considered an "algorithmic" problem and has been advanced by using deep reinforcement learning, but the fact that it is nontrivial to teach multiply makes me think that certain seemingly simple problems might be out of reach.  Is there a good way to think about what problems are well suited for deep reinforcement learning?

A good start would be to understand what reinforcement learning is; and identify which problems are reinforcement learning problems and which aren't.  Deep reinforcement learning is only relevant if you have a reinforcement learning problem; otherwise, it's almost certainly not relevant.  Among other things, reinforcement learning deals with a stateful system.  You don't seem to have a stateful system so it's not clear to me why you think reinforcement learning would be relevant.

Since you haven't told us what the problem is, it's hard to imagine how we can tell you how to solve it; all I can share is general principles.  In general, deep reinforcement learning isn't magic that you use whenever a problem is too hard for normal methods; it is useful for a specific purpose, and I don't see any reason to expect it to be effective or applicable here.


Why must a Turing Machine that Repeats the Same Configuration Twice be in an Infinite Loop? I have seen the following statement, and I don't quite understand the reasoning behind it:

  If a Turing machine repeats the same configuration twice, it must be in an infinite loop.

I thought that a $TM$ can be in a state $q_1$, with the tape on the left 000 and on the right 111. Let's say it moves right and then left, staying in the same state; aren't we in the same configuration?

This is because the transition function $\delta$ of a TM is deterministic. If the configuration is the same, then the arguments of $\delta$ are also the same, resulting in an infinite loop. Formally, this can be proved like @gnasher729 does.

Let's consider your example. If your $TM$ moves like the following,

$$
  (q_1, \dots00[0]111\dots) \xrightarrow{q_1, \text{right}} (q_1, \dots000[1]11\dots) \xrightarrow{q_1, \text{left}} (q_1, \dots00[0]111\dots)
$$

then the last step equals the first one, which means an infinite loop.


any hope for a universal automatic parser? Say you are a program, and you are given some source code but you don't know in what language, it can be C++/Java/Python/Lisp/... all you know is that it is highly structured and LR(1) parse-able, and you want to make some guesses on the corresponding syntactic tree.

How would you try to achieve this, and would you have any hope to make it working on some toy problems ?

To be clear, the goal isn't to make a parser for 4 or 5 different (but similar) programming languages, but really to detect -from some examples- the regularity in how the data is structured, and build from it a syntactic tree, with the hope to generate a grammar, a syntactic parser and -let's dream- a semantic parser and an interpreter.

My thoughts : a major problem is that in general the grammar needed for parsing a given source code isn't LR(1), but only locally LR(1), and globally recursive. For example HTML contains some Javascript, itself containing some HTML+Javascript hidden in a string :

 ");
</scritp>

For parsing this, you need to generate a grammar for HTML and another one for Javascript, and generate a recursive grammar saying that sometimes in the syntactic tree (from one node to its child) it can jump from one language to the other.

Do you have any reference/idea on this problem?

You might be interested in learning about grammar induction: given a set of examples of strings from a context-free language, there are algorithms to learn a context-free grammar that generates those strings.

To learn more about it, read the Wikipedia article I linked to, and Inducing a context free grammar, Is there a known method for constructing a grammar given a finite set of finite strings?, and the the Sequitur, Lempel-Ziv-Welch, and byte pair encoding algorithms.

There's no hope for automatically building an interpreter for the language, because that depends on the semantics (meaning) of the programs, and you can't determine that solely from the program source code; the most you can hope to learn is to characterize the syntax of the language, not the semantics.


Matching/finding mathematical plot images I'm trying to come up with a method to match a given mathematical plot against a database of other plots. To make it more specific: plots are generated in R as PNG and might have different dimensions. The latter means that simple pixel-by-pixel matching won't work, even when resized, because text, plotting symbol, margins etc. between two versions of the same old are non-linear transformations of each other.

There's a number of good image matching algorithms available online but those assume any area in the picture is relevant, whereas with mathematical plots it's predominantly about the artifacts representing data that's being plotted.

I'm looking for pointers: is there an algorithm, paper etc. related to this task? Or maybe someone heard of a specialized DNN (which could help in identifying those most important artifacts)?

Appreciate any suggestions.

A natural approach is to first scrape the data from each plot; then come up with a distance measure to compare the similarity of the data from two plots; then given a template plot, loop over all plots in the database, compute the distance, and find the most similar one.

There are many tools for scraping plots (i.e., given an image that contains a plot, extract the underlying data).  See, e.g., https://academia.stackexchange.com/q/7671/705, https://stats.stackexchange.com/q/14437/2921, etc.

You'll have to choose the distance measure yourself.  You haven't answered questions about what notion of similarity you want to use, and we can't tell you what to use.  You could, for instance, rescale the data so that the x-axis and y-axis both vary across the range [0,1] (so all plots share the same scale), then use the $L_2$ distance (Euclidean norm) between the two time series represented on the plots.  That might or might not suit your needs.

I don't expect deep learning to be particularly useful here.  I would try more direct methods first.


Search vs planning in artificial intelligence I'm studying artificial intelligence following the Russell & Norvig book.
We did a search and planning part that for me is the same (at least on the representation).
I'd like to know what is the difference between these two techniques, but I couldn't find it.

Looking online I found this resource:
Planning and Search, where it says: "The main difference between search and planning is the representation of
states."

Is the difference between these two techniques limited to the representation?

Short answer is "Yes".

Long answer is "No":

As far as I am concerned the difference is limited to a specific author/lecture:
(to the best of my understanding of the slides)
The author of the linked slides does not want to refer to "search" as a technique like planning, but rather as a general procedure.

Planning is the process of finding a set of (valid) actions that transform an initial state (set of properties) to a goal state. Such a problem can be represented by a state space graph, where each node defines a complete world state (i.e. a set of properties). Two nodes are connected if there exists a valid action transforming one state into another.

"Search" is the general procedure of finding a solution by searching the problem space. In this case it is the process of iterating a state space graph starting at the initial node, trying to find a path to the goal node, i.e., using DFS. The search problem is given an (perhaps implicit) representation of the graph and is not concerned about internal properties of nodes.
A non-search "Planning" algorithm on the other side may make use of the logical properties of the states to iterate the state space graph.

However, I would like to note that most "Planning" algorithms do use some kind of search procedure on the state space graph, significantly improving the search using planning-heuristics:
Consider the graph given on slide 4 (of the referenced link). The complete graph represents the planning problem. The search "only sees" nodes and edges. A DFS would simply iterate all possible paths until a solution is found. A heuristic (planning algorithm) may use additional relations between properties (i.e. getting milk implies going to the supermarket first).

Informal definition of plan: the solution to a planning problem. A sequence of actions that translate the initial (world) state into the goal state.

In terms of the (graph) search this would be a list of edges to traverse. If there exists a valid plan, then there exists a path in the graph.

(this may be a little out of scope)
Since planning is in general PSPACE-complete naive search algorithms perform exceptionally bad on many instances. Common heuristics/techniques used in planning are based on the relaxation of the state space graph, i.e., by relaxing preconditions or effects (resulting in easier problems; in P, or NP) which can be solved "easily". If you are interested in planning that is somewhat separated from "search" you might wan to take a look at hierarchical task networks (HTN) which is basically planning with additional domain knowledge.


Is the Kleene star of an intersection always equal to the intersection of kleene stars? I know that the  Kleene star of an intersection is contained in the intersection of Kleene stars, but are they necessarily equal?

For example, given two formal languages, $A$ and $B$, I know that $(A\cap B)^*\subseteq A^*\cap B^*$, but does $(A\cap B)^*= A^*\cap B^*$?

Clearly not.

Let $A=\{a\}$ and $B=\{aa\}$.

Now,

$A\cap B =  \emptyset$

so

$(A\cap B)^* = \{\epsilon\}$

but

$A^*\cap B^*=B^*=\{a^{2i} : i \in \mathbb{N}\}$

(all strings consisting of an even number of $a$).


Finding a correct regex for the strings with at least two $0s$ I am learning CFGs and before that I've made a RE (Regular Expression) for the language of "all strings with at least two $0$'s over the alphabet $\Sigma = \{0,1\}$."

I made this: $(0+1)^*0(0+1)^*0(0+1)^*$

I checked the answer and it is: $1^*01^*0(0+1)^*$

Is there any difference between the two?

If mine is also correct, what should be the CFG for it?

Your answer is also correct. Regular languages do not have unique regexes. For example, $0^\ast$, $0^\ast 0^\ast$, and $0^\ast 0^\ast 0^\ast$ are different regexes, all representing the language of strings containing only zeroes.

The problem of deciding whether two regexes are equivalent (i.e., whether they represent the same language) is actually very hard, as mentioned in this answer. (Spoiler: it is $\mathbf{PSPACE}$-complete.)

As to your other question (regarding a CFG for the language), here is a hint: divide and conquer. Split the regex in multiple "chunks" and try to generate each chunk separately, then pack everything together with the grammar's start symbol.


Are there decidable problems that are reducible to undecidable problems? I've seen a question asking if $A \le_m B$, then if $A$ is decidable, $B$ is also decidable. My initial intuition is that this is not the case, and that there are decidable problems that are reducible to undecidable problems. While I am not sure if this is completely correct, or even how to prove this if it is correct, I am thinking a decidable problem could be reduced to a recognizable, undecidable problem because a polynomial time verifier would work on a decidable problem. Is this a correct idea?

Any decidable problem can be reduced to the halting problem. Take a machine $M$ that decides some language $L$. Now produce a new Turing machine $M'$ that behaves identically to $M$ except that, if $M$ rejects, $M'$ loops forever. Now, $M'$ halts on input $x$ if, and only if, $x\in L$.

More generally, every decidable problem can be reduced to every undecidable problem. Let $Z$ be some undecidable language.  We know that $Z\neq\emptyset$ and $Z\neq\Sigma^*$, since both of those languages are trivially decidable. Therefore, there are strings $z^+\in Z$ and $z^-\notin Z$.  Now take any decidable language $L$.  Since $L$ is decidable, the function
$$ f(x) = \begin{cases}z^+&\text{if }x\in L\\z^-&\text{if }x\notin L\end{cases}$$
is computable, and it is a reduction from $L$ to $Z$.

  I am thinking a decidable problem could be reduced to a recognizable, undecidable problem because a polynomial time verifier would work on a decidable problem. Is this a correct idea?

I think you're confusing the set of recognizable languages with NP. A recognizable language has a computable verifier but the verifier doesn't necessarily run in polynomial time (and the time hierarchy theorem says that there are languages whose verifiers can't run in polynomial time). It's true that every decidable problem has a computable verifier (because being able to decide the problem essentially means that you can verify a given answer by just computing the correct answer and comparing) but that doesn't give you a reduction. Rather, it proves that every decidable language is itself recognizable.


Understanding Log(n) Loop Invariant When attempting to find the following loop invariant for:

int log(int x)
{
  int i = 0;
  int j = x;
  while (j > 1) {
    j = j / 2;
    i = i + 1;
  }
  return i;
}

I come up with the following loop invariant:

j >= 0 and i >= 0 must be true before, during and after each iteration.

For case where x >= 0, upon checking the condition the first time, the loop invariant holds true.

For case where any input x >= 0, the invariant loop also holds true.

However, going through some of the other loop invariant reads found here on stackexchange, I am convinced that this is not the loop invariant for this particular algorithm as it does not solve the problem we are trying to accomplish. More specifically, this loop invariant holds true, but without pointing out explicitly that this is a logarithm calculator, the loop invariant is invalid.

I am unsure of the loop invariant I provided as I don't even think it is sufficient for proving out the correctness of the algorithm. How would I create an effective loop invariant that will satisfy the simple algorithm above?

Your understanding is mostly correct.  That is a valid loop invariant.  It's just a relatively weak one.  It is common to find a situation like this, where there are multiple possible loop invariants, some more useful than others.  You've found a relatively weak (less useful, less informative) loop invariant.

Your real question is: how do I find a loop invariant that is strong enough to let you prove your code is correct?  The answer to that is that you need to start by specifying what it means for your code to be correct.  You need to start by writing a specification for your code, that outlines what it means for it to correctly compute the log function.

The specification will typically take the form of a precondition and a postcondition on the function itself.  The loop invariant is only a tool to help you prove that the code of log meets the specification for log.

I can't tell you what the right specification is, as you haven't told us what you want log to do.  But here is one example specification:

Precondition: $x=2^k$ for some $k \in \mathbb{N}$
Postcondition: if $x=2^k$, then the return value of log is equal to $k$

When you try to crank through a Hoare-style proof that log meets this specification, you'll find that you need a loop invariant.  The following loop invariant will be sufficient:

$$i \ge 0 \land j \ge 1 \land j = x \cdot 2^i.$$

I don't expect it to necessarily be obvious that this is a valid loop invariant, nor that this is sufficient to prove the code above meets the spec I gave.  Fortunately, there is a systematic step-by-step way to verify that: you use Hoare logic.  To learn about this, I recommend that your next step be to spend some quality time with a textbook that explains preconditions, postconditions, loop invariants, and Hoarse logic.

Of course, that's not necessarily the only specification you might have in mind.  Another possible specification would be

Precondition: $x \ge 1$
Postcondition: if $2^k \le x < 2^{k+1}$, then the return value of log is equal to $k$

or even:

Precondition: $x \ge 1$
Postcondition: the return value of log is equal to $\lfloor \lg x \rfloor$

Those might require different, more elaborate loop invariants.  The point is: whether a loop invariant is strong enough depends upon what you're trying to prove, and in particular, what spec you're trying to prove the code meets.

A small correction: When you write

  "without pointing out explicitly that this is a logarithm calculator, the loop invariant is invalid",

that's not quite right: the loop invariant you gave is a valid loop invariant.  It's just a relatively weak one.

Also, when you write "satisfy the simple algorithm above", that's probably not the right way to put things.  I've never heard the word "satisfy" used in this way before.  Instead, the right question to ask is: how do I prove that this code meets a particular specification?  To ask that, you first need to know what the specification that you're trying to meet is.


Confused about how to exactly determine the complexity of an Algorithm Let's take this algorithm as an example.

$PATH$ = {$G$, s, t | $G$ is a directed graph that has a directed path from s to t }.

Prove that $PATH \in P $.

Ok, I know the basic algorithm is to start from node s, place a mark on it, and then look over the rest of the edges and place a mark from node s to node x if there exists a edge from node s to node x. If you place a mark on node t, then accept; otherwise, keep doing this until you run out of nodes, which implies you reject.

I'm getting caught up in implementation details, really. I can most likely envision a turning machine that can do this in polynomial time, but I don't know if this is the right way to go about it,per say. In Sipser, it seems like a very "hand wavy proof." When I encounter an algorithm should I first figure out a way to implement it on a reasonable Turing machine? Or is there a better way to do this. Thank you.

To prove that an algorithm is in $P$ you basically have two options:

Show how to solve it using a number of operations that is polynomial in the size of the input. This means you have to specify a Turing machine to do it, and prove that each of the operations takes a polynomial amount of time. Alternatively, you would prove that the turing machine spends a polynomial amount of steps in any non-accept/reject state.
Show that your problem can be reformulated as a already-known problem previously proven to be in $P$. Here you have to prove that the reformulation is correct and that it takes polynomial time.


Are regex crosswords NP-hard? I was fooling around the other day on this website: http://regexcrossword.com/ and it got me wondering what the best way to solve it was.

Can you solve the following problem in polynomial time or is it NP-hard?

  Given an NxM grid with N regular expressions for the columns and M for the rows, find any solution to the grid such that all the regular expressions are satisfied, or say that no solution exists.

The problem is NP-hard.

We show this by reducing vertex cover:

  Given a graph $G=(V,E)$ and a threshold $k$, is there a subset $V' \subseteq V$ of cardinality at most $k$, so that each edge in $E$ is incident to at least one node in $V'$?

We translate this into a regex crossword with $|E|+1$ columns and $|V|$ rows as follows:

All columns, except for the first, correspond to an edge. They get a regex $0^*1(0|1)^*$.

All rows correspond to a vertex. They get a regex that allows to write either

a $1$ in the first column and each column corresponding to an edge incident to that node and zeroes in all other columns, or
$0^*$

Finally, the first column counts the size of the vertex cover. It gets a regex, that allows for at most $k$ ones.

The correspondence between solutions to the regex crossword and vertex covers should be obvious.

Example:

Find a vertex cover of size 2 for the following graph:

$V_A = 0^* \big| 10110$

$V_B = 0^* \big| 11101$

$V_C = 0^* \big| 10011$

$V_D = 0^* \big| 11000$

$Counter = 0^* \big| 0^*10^* \big| 0^*10^*10^*$

$E_1 = 0^*1(0|1)^*$

$E_2 = 0^*1(0|1)^*$

$E_3 = 0^*1(0|1)^*$

$E_4 = 0^*1(0|1)^*$

Lastly, you can set up the "crossword" so that $V_A$ through $V_D$ are the top regexes and $Counter$ and $E_1$ through $E_4$ are the left side regexes.

Solving this regex crossword give you a vertex cover of size 2 for nodes $V_A,V_B$ or $V_C,V_B$.

If we change k to be 1 and $Counter$ to be $0^* \big| 0^*10^*$ as another example, the regex crossword is impossible to solve because there is no vertex cover of size 1.


Treap union unrandomizes priorities? The algorithm for the union of two sets represented by treaps is defined in this paper and on Wikipedia, but the algorithm seems flawed.

Take for example the following loop.

X := {a}
for (i := 0; i < 1000; i := i + 1)
  X := X ∪ {a}

At the end of execution, the variable $X$ contains the set $\{a\}$, but the priority of the element $a$ is elevated and not random because the union algorithm always picks the element with the highest priority.

Am I missing something?

My question was answered by email after I posted it here.

The answer is that the priorities of the elements can't be chosen completely randomly when an element is inserted into the treap that represents the set. The priorities need to be given by a hash function. That way, the same elements are always associated with the same priorities and the union algorithm, which always picks the element with the highest priority, doesn't return a biased treap.


Prove the existence of regular $C$ so that: $A \prec C \prec B $ Given $A,B$ regular languages with $A \prec B$. Prove the existence of $C\in L_{\text{regular}}$ so that: $A \prec C \prec B$.

Here, $A\prec B$ stands for: $A\subset B $ and $B\setminus A $ is infinite.

I tried to go for: $C=\overline{B} \cup A$ and some other options but it didn't work out.

Hint: Note that $B \setminus A$ is regular by closure properties of $\mathsf{REG}$.

   Since $B \setminus A$ is also infinite, you can find an infinite language $D \in \mathsf{REG}$ so that $D \prec B \setminus A$.


what are the BUS MASTERS in a processor? I have multiple questions actually..

a)What is a System bus? Is there any other buses in the computer?

b)Is it always the case that , the processor access the memory via the system bus?

c) I read that " another master requests the access ".. What are these masters exactly? Is processor the bus master by default?

P.S. I am reading in the context of 8086 microprocessor

(a) "System bus" was a common aggregation term for "data bus" and "address bus". There are a lot of other buses depending on your machine, e.g. between RAM and video card, or between SCSI controller and devices (hard disks, scanner, whatever).

(b) There's no such thing as "the" memory, it's a whole hierarchy of different memory systems, varying in speed/size/cost. For example, the fastest memory part are the on-processor registers. You can transport their content from and to the data or address bus (to move values to and from RAM), but for example the ALU won't access the registers via "system bus".

(c) Other devices which are able to "drive" the bus. For example, consider a SCSI controller, a scanner or a network card wanting to write something (a disk block, a scanned image, a received packet) to a previously assigned RAM area. Of course, the controller has to harmonize it's RAM access with the CPU. So the device will ask (via an extra control wire) to grant the bus, and wait. After the CPU acknowledges with a signal, the device becomes temporarily bus master and may use data and address bus exclusively (at least for some time), before it has to hand back control. As the CPU is present in every system, but (for example) a network card is not, it's a sensible design choice to make the CPU bus master.


Turing machine that accepts L = {#a != #b} Trying to figure out how to make a deterministic single-tape Turing machine for the language of words comprising as many $a$'s as $b$'s.

I am very confused, because I can't figure out how I would keep track of how many $a$'s and $b$'s there would be. The method for finding $a^nb^n$ goes right and back left to do this but this language would include things like $abaaaababab$.

How can I keep track of number of $a$'s and $b$'s?

You dont need to keep track of them. At each iteration you have three possibilities. Either you first see an A, or a B or a nothing. If nothing accept. If an A first, replace it with some special character and search for a B. If you see one replace that one as well with some special character go back to beginning but if you dont just reject. Do the same for B first. After you cross our 2 characters loop back to beginning. It is actually very similar to $a^nb^n$.

The TM design should be straightforward actually. Similar to $a^nb^n$ but considers $b$ first option as well at each iteration.


What is a good resource to learn about oriented matroids in the context of digraphs and optimization? I am interested in oriented matroids in the context of directed graphs and optimization. Unfortunately, I know very little of the topic. Is there a book, article or a resource that serves as a good introduction to oriented matroids, especially in the context of directed graphs? It's a bonus if the resource is suitable for an (under)graduate level course and is preferably even free.

These notes written by Winfried Hochstättler for an MAA short course on matroids look like a good, short, introduction. They also contain references to several longer references on oriented matroids.


Finite State Machine that only accepts strings with equal number of 0's and 1's Question: Suppose you have a finite state machine that accepts only strings with an equal number of zeros and ones. Show that you can then construct a finite state machine that accepts only strings of the form 0^n 1^n, i.e., an arbitrary finite number of zeros followed by the same number of ones.

My attempt at a response:

A Finite State Machine that accepts strings with an equal number of 0’s and 1’s (e.g. n zeros and n one's, where n is some arbitrary finite number), must have a counter that keeps track of the total number of 0's and 1's. This is impossible, since by definition a FSM has no counter or memory. But suppose this were possible. Then it’d be possible to construct another FSM that keeps track of the count of consecutive 0's in the prefix of a given string, and ensure that number equals the count of consecutive 1's in the suffix of that string.

I feel like there is more to the answer than this, but I don't really know what else can be said. I know that no FSM can be constructed to accept only strings in the format 0^n 1^n where n could be any arbitrary nonnegative integer, but that it is possible to do for any fixed, specific value of n. For example, it's possible to build FSM to accept only strings that contain three 0's, followed by three 1's. But I don't know whether this detail is relevant at all. Thanks for any help.

The question is not really well-defined since there is no FSM that accepts your language $L$, so the existence of such an FSM implies anything – for example, $2+2=3$.

However, the intended solution was to notice that
$$ L \cap 0^*1^* = \{0^n1^n : n \geq 0\}. $$
Since the regular languages are closed under intersection, this shows that an FSM for $L$ can be converted to one of $\{0^n1^n : n \geq 0\}$.

Your attempt claims that an FSM accepting $L$ must have a counter. This is not a formal statement: it has no formal content. It's just intuition. A PDA for $L$ also doesn't have a counter; it has a stack. Counter is not a well-defined technical notion.


How to choose the maximum number of nodes (with constraints) from a graph Consider a connected undirected acyclic graph $G$ with $n$ nodes and $n-1$ edges. The nodes have non-negative integer weights less than $n$.

A positive integer $x$ is given and you want to choose at most $x$ nodes so that

There is a path connecting all the nodes you choose that doesn't visit any node you haven't chosen.  A path can backtrack. This is to say the set of vertices you choose induces a connected subgraph in $G$.
Each node you choose has weight at least as great as all nodes you haven't chosen.

The goal is to maximize the number of nodes you choose.

Is there  a fast algorithm for this problem?

Assume the set of nodes have weights $v_1 < v_2 < \dots < v_n$.

Two observations that follow immediately from your restrictions:

Your selection has to be a set of the form $v_i, v_{i+1}, \dots, v_n$.
Every chosen node is neighbour of another chosen node.

That is, we want to find

$\qquad\displaystyle \min \{ i \mid \forall j \geq i\ \exists j' > j\,.\ j \in N(j')\} $

where $N(i)$ denotes the neighbourhood of nodes with (weight-)index $i$.

Therefore, the following algorithm solves the problem in time $O(n \log n)$ (assuming an adjacency matrix):

Sort the nodes by weight.
Choose nodes greedily from the back of the list as long as the new node is neighbour of one of its predecessors (and you have chosen less than $x$).
Output the result.

I'll leave the proofs of correctness and runtime to you.

Now, if weights can be equal we may be able to take some more nodes; if $v_i$ is the first weight we don't pick according to the above algorithm, we have to check all $k$ nodes of weight $v_i$ we have not checked yet, picking as many as we can. This adds a fix-point iteration with at most $k$ iterations running in time $O(k)$ each.

An alternative is to sort the weights in to buckets and pick reachable nodes from the next smallest buckets. Details again left to the reader.


What kinds of programming pitfalls modern languages are able to find? I often see claims that modern functional strictly-typed languages are 'safer' than others. These statement mostly linked with type systems and their ability to explicitly express the following pitfalls:

Alternatives in function result. Maybe and Either datatypes vs. exceptions and null-pointers in C++-like languages.
Access to mutable state (possibly inconsistent behavior over time). State datatype in Haskell vs. variables in C++-like languages.
Performing IO. IO datatype in Haskell vs. just doing things in C++-like languages.

Haskell allows to express constraints required for safe handling of these situations. And compiler is able to warn programmer when he doesn't follow them.
Although pitfalls above are definitely the most common ones I can think of much more, for example:

Unexpected resource consumption. Memory, CPU, disk, bandwidth.
Inconsistent access to shared resources. Like read and write interference, broken lock ordering.
System-level failure. Like crashing process or pulled plugs.
Unexpected execution time for IO, timing violation.

Is there languages, libraries or at least models which allow to express constraints from the second set and yield a warning when they are not met?

Substructural types ( http://en.wikipedia.org/wiki/Substructural_type_system ) can be used to provide some version of each of those. As a summary, while normal types control how something may be used, substructural types further control when or how often it may be used.

Affine types can be used to construct languages capable of expressing all, and only, polynomial-time functions. http://www.cs.cmu.edu/~fp/courses/15816-s12/misc/aehlig02tocl.pdf
Linear types can enforce that memory is accessible when variables go out of scope, enabling a kind of "static garbage collection." Similarly, ordered types can be used to require that variables are used in a LIFO order, allowing them to be stack-allocated. Regions ( http://en.wikipedia.org/wiki/Region-based_memory_management ) are also useful here. The first chapter of Advanced Topics in Types and Programming Languages provides a nice introduction to using linear and ordered types for this purpose.
Affine types also enable typestate-oriented programming ( http://www.cs.cmu.edu/~aldrich/papers/onward2009-state.pdf ). Typestate is used to enforce certain orderings in APIs (e.g.: can't read from a closed file), but can also be used to enforce safety properties. Requiring a block that handles some error can be encoded as requiring a function that transitions some object from an error state to a recovery state.


Determining if a langage defined by a given context-free grammar is finite using the pumping lemma Here is a question that I found into an old exam:

  Describe an algorithm that, given a context-free grammar $G$, can determine if the language $L(G)$ produced by $G$ is finite or infinite.
  Hint: use the pumping lemma.

While I found several possible solutions to the problem (mostly exploiting the presence or non-presence of cycles in the grammar or automata) none of them implies the use of the pumping lemma (that was given as hist).
For this reason I believe that none of the solutions that I found corresponds to the intended one.

Is there any way an algorithm could exploit the pumping lemma in order to solve this problem?

Here is the corresponding result for regular languages:

  Given a DFA with $n$ states, its corresponding language is infinite iff it contains a word whose length is between $n$ and $2n-1$.

This implies an inefficient algorithm for determining whether the language is infinite.

The proof uses the pumping lemma in its following formulation:

  If a regular language $L$ is accepted by a DFA with $n$ states, then any word $w \in L$ of length at least $n$ can be decomposed as $w = xyz$, where $|xy| \leq n$ and $y \neq \epsilon$, such that $xy^iz \in L$ for all $i \geq 0$.

In one direction, if the DFA accepts some word $w$ of length at least $n$, then the pumping lemma shows that there is some decomposition $w = xyz$ with $y \neq \epsilon$ such that the infinitely many words $xy^iz$ belong to the language.

In the other direction, if the language is infinite then it contains some word whose length is at least $n$. Let $w$ such a word of minimal length. The pumping lemma show that there exists a decomposition $w = xyz$, with $0 < |y| \leq n$, such that $xz$ is in the language. Since $|xz| < |xyz|$, it follows that $|xz| < n$, and so $|w| = |xyz| < 2n$.

If you use the pumping lemma for context-free languages in a formulation in which the pumping constant is related to the size of a context-free grammar for the language, then you can use similar reasoning to come up with an algorithm that determines whether the language generated by a context-free grammar is infinite.


Encoding first order formula (or its tree) into binary string? How to encode a first order formula into binary string, which I could give as input to Turing machine or program to do something with it (deciding is it satisfiable, or is concrete structure model for it, for example)?

I've read that I should first make a tree (which I know how to do) and then encode that tree, which I don't know how to do and I don't understand why I need to make that tree? Why don't just make binary number for every symbol which could appear in formula $( = , \vee, \wedge, <=>, =>, \exists, \forall...)$ and connect them into string for concrete formula?

There is one encoding scheme which is particularly obvious. Under this encoding scheme, the encoding of the formula $a \Rightarrow (b \Rightarrow a)$ is
$$ a \Rightarrow (b \Rightarrow a). $$
A C program can parse this string into a tree if it needs to, but it's up to the program.

It is of course possible to think of many other encoding schemes, but unless you are interested in very weak complexity classes, the exact encoding scheme doesn't matter.

There is one fine point here: the alphabet is finite, but there could be formulas with arbitrarily many variables. There are many ways to solve this problem. For example, you can name variables in the form "$v$ + number", for example $v5$, $v107$, and so on. This uses only a finite alphabet (since we encode the number in decimal, using 10 symbols).


Is big O notation additive? For example, I have one program that requires $O(i)$ time complexity, and a second program requires $O(j)$ time complexity. Would the total time complexity be $O(i+j)$? And why?

If $f(n) = O(A(n))$ and $g(n) = O(B(n))$ then $f(n) + g(n) = O(A(n) + B(n)) = O(\max(A(n),B(n))$. These are standard properties of big O, which follow almost directly from the definitions.


Write a regex to match string that does NOT contain a certain pattern Let's say our alphabet is 0 and 1.

How would you approach writing a regex to generate a language of words that do NOT contain 101.

The only regex operators allowed are concatenation , star * and OR |.

I am stuck now and I want to know if anybody has an idea.

If a string does not contain $101$, then every $10$ either terminates the string or is followed by $0$. So if $r$ is a regular expression for all strings not containing $10$, then a regular expression for all strings not containing $101$ is
$$
(r100)^*r(10+\epsilon).
$$
You take it from here. Note that there are also other solutions.

Complementing a regular expression can be a very costly operation. For example, the set of strings over $\{1,\ldots,n\}$ not containing all symbols has a regular expression of length $O(n^2)$ (exercise), but its complement requires a regular expression of exponential size $\Omega(2^n)$. This follows from the "fooling set" lower bound on NFAs, and the fact that regular expressions can be converted into NFAs with constant multiplicative overhead.

A fooling set for a language $L$ is a collection of pairs $(x_i,y_i)$ such that $x_iy_i \in L$ but for $i \neq j$, either $x_iy_j$ or $x_jy_i$ is not in $L$. If $L$ has a fooling set of size $n$ then every NFA for $L$ has size $n$ (exercise). In the case of all strings over $\{1,\ldots,n\}$ containing all symbols, there is a fooling set of size $2^n$: $\{(S,\overline{S}) : S \subseteq \{1,\ldots,n\}\}$, where we identify a set of symbols with the word containing these symbols in order.


Confusion about Definition of DPDA and $\epsilon$-move The DPDA definition is from sipser's book, and it mentions that the following PDA can convert to DPDA.

I tried it, then I confused the definition!

By definition, I could construct these

$\delta(q_1,\epsilon,\epsilon)=(q_2,\$) $

and because of "exactly one of the values"

$\delta(q_1,0 ,0 \text{ or } \$ \text{ or } \epsilon) = \varnothing$

$\delta(q_1,1 ,0 \text{ or } \$ \text{ or } \epsilon) = \varnothing$

$\delta(q_1,\epsilon ,0 \text{ or } \$ ) = \varnothing$

However, how about $\delta(q_1,\epsilon,\epsilon)$ , when I handle the $\{ 0^n1^n|n=0 \}$ ?

Does it means we can stop at two states $q_1,q_2$ with same string?

to stop at the $q_1$ is from no input string
to stop at the $q_2$ is from no input string, but $\epsilon$-move

And is it "deterministic" ?

Or why can definition allow $\delta(q,\epsilon,\epsilon)$?

Doesn't it break "deterministic" ?

Could I think that it finally stops at $\{q1, q2 \}$, and it at least contains one accept states $q1$ , so we accept it ?

Hence, by omitting the intermediate steps, I also can construct

$\delta(q_4,\epsilon ,\epsilon ) = q_r$, where $q_r$ is non-accept state with $\delta(q_r,\epsilon ,\epsilon ) = q_r$,

then all done.

The deterministic concept in pushdown automata means that next move of automata is determined uniquely.

This concept contains two points.
First, there are no multiple choices in reading an alphabet from the input. For example, you should not have both of following rules is your transition rule

$$\delta(q,a,\alpha)=(p,\beta), \delta(q,\epsilon, \alpha)=(p',\gamma),$$

because you either can choose the first rule (that is $\delta(q,a,\alpha)=(p,\beta)$ ) read the $a$ then go to next state, or you can choose the second one (that is $\delta(q,\epsilon, \alpha)=(p',\gamma)$ ) do some other job before reading $a$ by $\epsilon$-transition. In the other words your choice in reading $a$ is not unique.

The second point of the definition is that you should exactly know what to do when you are reading an alphabet. Pay attention that the definition says $$\forall q\in Q, a\in \Sigma, x\in \Gamma,$$ which means there should be no ambiguity when you read an alphabet. For example, in above state diagram, one of the undefined rules is $\delta(q_3,0,x)$, where $x\in \Gamma$. Of course, this undefined rule is not important in our intuition that the PDA works correctly, but if we want to satisfy the definition of DPDA, then we should not let machine crash in the middle of reading an input. In the other words, the DPDA should read all characters of its input, then stop either in final state or non-final state.

I hope the above explanations help you in understanding Deterministic pushdown automata.

Now let's take a look at your first question. You've asked is it possible to stop at two states with the same string? The answer is no.  I want to draw your attention to this part of definition again that says $\forall q\in Q, a\in \Sigma, x\in \Gamma.$ You missed the second point in the concept of determinism in the definition, that is you should define the rule $\delta(q_2,\epsilon,\$)$ for your DPDA. If we define $\delta(q_2,\epsilon,\$)=(\epsilon,q_4)$ and assume $q_4$ be the only final state, then the problem you arose will be solved.

To answer your second question, the definition allows $\delta(q,\epsilon,\epsilon)$ mostly because of the first transition rule. You will find some different definition for DPDA in some other books which handle the first transition rule in some other ways. For example, some people agree that at the beginning we already have $\$$ on the stack.

your statement about $q_4$ is ok.


Is Space Complexity Always Less Than Or Equal To Time Complexity? Background
I am working on proving a novel problem to be P-Complete, and this requires using a logspace reduction to reduce some known P-Complete problem to the novel problem. Particularly, I am reducing the Circuit Value Problem, the de facto P-Complete problem, to the novel problem.

The Experienced Difficulty
P-Complete reductions must use logarithmic space in the reduction in order to be meaningful. However, for the novel problem, it is very easy to show that the reduction takes logarithmic time, whereas it is difficult to show that it takes logarithmic space.

The Complicating Factor
There are many Q and A sites online which declare that an algorithm's space complexity is always less than its time complexity. For example: https://www.quora.com/Is-there-any-algorithm-whose-space-complexity-is-more-than-time-complexity. This is just one of many. I have scoured the literature on the subject, reading through Cook, Karp, Stockmeyer, and many more, yet I am unable to find this claim that space complexity is always less than time complexity captured in a rigorous manner. Yet this claim seems pervasive and almost treated as "common knowledge".

Why the Complication Matters
If it is true that space complexity is always less than or equal to time complexity, then instead of doing a logspace reduction, I can show that the reduction can be done in log time, which is much easier in my particular case.

What I Need
Can anyone point me to the paper which established this "common knowledge" idea that space complexity is always less than or equal to time complexity? Or a textbook or other authoritative source?

-Thank You

The reason it's common knowledge and not formally proved anywhere is because it's obvious.
During each time step, you can only access one memory location. Therefore you can never access more memory locations than you have time.

I found the following reference, showing an even slightly stronger result: every deterministic multitape Turing machine of time complexity $t(n)$ can be simulated by a deterministic Turing machine of tape complexity $t(n)/\log t(n)$.

  If it is true that space complexity is always less than or equal to time complexity, then instead of doing a logspace reduction, I can show that the reduction can be done in log time, which is much easier in my particular case.

This suggests that something is wrong with your understanding. Showing that it runs in logarithmic time is strictly harder than showing it uses logarithmic space. Something really weird has happened. As Robert Anderws rightfully points out in his comment, no reduction from the Circuit Value Problem can run in logarithmic time and be correct, since it can't even read the entire input.


Maximization problem I work at a company and i got to a seminar we're they told us to solve this problem below in the picture
Is there an algorithm that can help me solve this question.
I thought about a randomized algorithm after that i get stuck?

The case $k \ge n$ is trivial as you can give different value to every variable, which satisfy all inequalities and thus is optimal. So let's consider $k < n$.
This problem can be considered as building a paritition of the $n$ variables in $k$ subsets. All inequalities involving two variables in the same subset are unsatisfied, any other is satisfied.
I would first build an efficient structure to count the number of inequalities involving each pair of variables. Basically this is a $n^2$ array, built in $O(m)$. In case $m << n$, a graph may be more efficient than a sparse matrix.
Then, let's take arbitrarily $k$ variables and distribute them into the $k$ subsets (give them the $k$ different values). Any inequalities involving these first variables is satisfied (then the arbitrarily may target greedily the largest values in the array).
Then loop on the remaining variables. For each $x_i$, evaluate $A^i_k$, the number of unsatisfied inequalities (considering only the variables assigned so far), for each of the $k$ possible assignment. For this, one has to consider every assigned variable in the same subset, this step is $O(n)$.
Let's call $S_i = \sum_k A^i_k$.
By assigning $k_0$ to $x_i$,
you unsatisfy $A^i_{k_0}$ inequalities but satisfy $S_i - A^i_{k_0}$ ones.
So by picking $k_0$ that minimizes $A^i_{k_0}$, you unsatisfy at most $S/k$ inequalities, satisying at least $S(1-1/k)$ others. So overall you guarantee to satisfy $m(1-1/k)$ inequalities (and clearly $(1-1/k)OPT$ ones).
This achieves $O(m + n^2)$ in time and $O(n^2)$ in space.


Hardness and approximation of a problem with a parameter Let $H$ be a decision problem, where we are given an integer $k$ and some object, say a graph or a formula. We know that $H$ is NP-complete for $k \geq c$, where $c$ is some constant like 3 ($H$ could be $k$-SAT, or $k$-vertex coloring, or something like that).

I have a problem $X$ I think is NP-complete as well, and I want to prove it. $X$ is a graph problem, and it has a parameter $k'$ similarly.

Given an instance of $H$ with parameter $k \geq c$ (for example let's say $c=3$), I can build an instance of $X$ (in polynomial time), where $k' = c+8$. I can now prove two things:

If $H$ with $k$ has no solution, $X$ has no solution with $k$. (There might be a solution for $X$ with $k'$, I don't know).
If $H$ with $k$ has a solution, $X$ has a solution with $k'$.

To establish hardness for $X$ with $k'$, should I be able to prove in (1) that $X$ has no solution with $k'$ as well? (Or is my current reduction pretty much useless as it is?) If I were able to do that, would my proof also tell me something about the hardness of approximating $X$? $X$ is a minimization problem.

Yes.  To show that decision problem Q is at least as hard as decision problem P (via a many-one reduction), you need to prove that a yes-instance for P maps to a yes-instance for Q, and a no-instance for P maps to a no-instance for Q.  That's just what the definition of a (many-one) reduction is.

In your case, P = "X has a solution with parameter $k'$" and Q = "H has a solution with parameter $k$".  Therefore, the answer to your question is yes: in (1) you need to prove that $X$ has no solution with parameter $k'$.  The definition of P needs to be consistent for both kinds of instances, so it has to use the same parameter in both cases.


Do we have to calculate time for declaring statement in RAM model? Do we have to calculate time for declaring statement, in my case int num3 statement. The following question was asked by professor as a post-lecture quiz. I selected t(n)=3, but the correct answer was t(n)=4.
What is the time taken by following algorithm on RAM model ?

t(n)=3
t(n)=4
t(n)=5
None of the above

There is no standard answer, so you'll have to go by whatever convention is used in your course.


lambda calculus with church numerals today I found this term in our exercises: ((^fx.f(f(f x)) ^gy.g(g y )) ^z.z + 1) (0)

I am quit unaware how to solve this type of question.
I know this is the church numeral 3 , 2 , the identity function +1 and zero.
But for my understanding it lacks an operator like +-*/
as ex.

(λmn.m (succ n)) to connect two church numerals?

Some hints will be greatly appreciated.

Your term is the application $3\ 2\ succ\ 0$, where $succ$ is the successor function.

If you task is to reduce this term to a beta normal form:

First we can observe that for terms $M$ and $N$, the application $MN$ beta-reduces to the $M$-fold application of $N$, which is

in the case of $N$ an operation: the $M$-fold application of the operation $N$ to whatever term $P$ the term $MN$ is applied to; i.e., $MNP$ is $\underbrace{N(N(...N(}_{M\text{ times}} P)))$,
in the case of $N$ a church number: the (church number representation of the) exponentiation of $N$ with $M$; i.e, $MN$ with $M,N$ numbers is $N^M$.

as you can easily verify with simple numbers like $2$ and $3$.

So $3\ 2$ is $2^3$, which beta-reduces to $8$, and $3\ 2\ succ$ creates an 8-fold application of $succ$, which is then applied to $0$.
So your term is the $2^3$-fold = $8$-fold application of the $succ$-function to the number $0$, that is, $\underbrace{succ(succ(...succ(}_{8 \text{ times}} 0)))$, which eventually beta-reduces to the church number $8$, $\lambda fx.f(f(f(f(f(f(f(f(x))))))))$.


Looking for Rating Functions I'm looking for something i would call rating functions.
I'm searching for some literature about this concept.
I'm not really sure about the terminology, but what I mean should be pretty obvious.

A type of function that returns a rating of some input.

Lets have a function that gets some input and returns a number between 0 and 1 as a rating, where 0 is bad and 1 is great. Everything between is well between bad and great depending.

Lets assume inputs are just numbers

$f\colon \mathbb{N} \longrightarrow [0,1]$

I would like if I have several rating functions be able to compose them.
For example if I have the rating functions $r_1$, $r_2$ I would like to compose both to a new rating function that returns a new rating in dependency to $r_1$ and $r_2$

Now I'm looking for literature, but was unable to find any.
Can somebody hint me into the correct direction?
The correct name for the concept I'm looking for would be great.

Edit

I want to implement various Rating Functions and want to combine them

One functions could be

alwaysPerfect = (x) -> 1
alwaysBad = (x) -> 0
isOdd = (x) -> x%2
distanceToOne = (x) ->
  x = 2 if x is 0
  1/abs(x)

Anyone could implement this functions, but the contract for this functions would be to always return a value between 0 and 1

I need to evaluate some data with various evaluation conditions. Writing these evaluation seperate small functions and combine them seems to be more clearer than writing one big function that does all the evalauting

So you have a bunch of functions $f_1, \dots, f_k$ from $\mathbb{N} \to [0,1]$ and want to combine them to a new one. There is a myriad of possibilities, e.g.

$f(n) = \prod_{i=1}^k f_i(n)$,
$f(n) = \frac{1}{k} \cdot \sum_{i=1}^k f_i(n)$,
$f(n) = \sum_{i=1}^k c_if_i(n)$ for $\sum_{i=1}^k c_i = 1$ and $c_i \geq 0$,
$f(n) = \min\{f_1(n), \dots, f_k(n)\}$,
$f(n) = \max\{f_1(n), \dots, f_k(n)\}$,
$f(n) = \operatorname{median}\{f_1(n), \dots, f_k(n)\}$,
$f(n) = f_1( \lceil 1000 \cdot f_2 ( \lceil 1000 \cdot f_3( \dots )\rceil)\rceil)$,

or any other of infinitely many choices. Without context, it is impossible to know which one yields something meaningful in your context.


Can an Earley Parser be made into a fuzzy parser similar to the Levenshtein Automata Algo for DFA? There's a way to perform fuzzy parsing (accepts strings even with typos to a certain edit distance), with a DFA and a run-time constructed Levenshtein Automata of the input word.  Can something similar be done with an Earley parser?  I'm finding it hard to understand the algorithm, let alone answer this question.

The answer is yes. However I would not do that with an Earley parser
because there are simpler ones with the same capabilities.

Basically, Earley parser belongs to a family of general context-free
parsers, that produces all possible parses for a given string, when
the grammar is ambiguous.

There are two ways (at least) of understanding these parsers:

as dynamic programming interpretation of a pushdown automaton
corresponding to the grammar on the input string;
as the the construction of the intersection of the grammar
with a finite state automaton.

When parsing a single string, the finite state automaton to be
considered is a linear automaton that recognizes only the string $w$
to be parsed, one symbol at a time (number of state is $|w|+1$).  If
you apply the cross-product construction of a FA $A$ and a CF garmmar
$G$ (Bar Hillel, Perlis, Shamir 1961), you get a new CF grammar that
is a new grammar $F$ which generates $\mathcal L(A)\cap\mathcal L(G)$.
The interesting point usually overlooked is that $F$ preserves the
parse-trees used by $G$, up to non-terminals renaming (due to
cross-product).

Thus if the FA $A$ generates only your input string, the grammar $F$
will generate only that string (if it is in $\mathcal L(G)$, otherwise
it generates the empty language $\emptyset$). Furthermore, it
generates it with all the parse-trees that $G$ could use to generate
it.

This grammar $F$ is what is usually called a shared parse forest, and
all general CF parsing algorithms are a more or less optimized version
of the cross-product construction, whether CYK, Earley, generalized LR
or LL, or others. So all I am saying applies to them too.

But, as you see, this generalizes to parsing a whole regular set, if
anyone is interested in doing that.

That is precisely your question. You have a string $w$. You want to
parse it up to some variations defined by a finite state transducer,
which in your case is a transducer that produces all strings within
some given Levenshtein edit distance of $w$ (but the origin of the
transducer is immaterial). The set of those strings is a regular set
that can be defined by a FA, with weighted transition that can compute
the edit distance of each string.

If you do the cross-product with your grammar $G$, you get a shared
parse forest grammar $F$ that generates all the strings in the
intersection. Furthermore, you get the weights on some of the rules so
that you can compute the edit distance of each of the accepted
strings.

If desirable, this can be used to keep only the strings with minimal
distance.

However, this can be improved a bit since composition with finite
state machines is associative.

If you always use the same, finite state transducer, as is the case in
your question, the right way to go about is to compose the Grammar $G$
and the transducer (here the Levenshtein automaton), independently of
the input string. This gives you a weighted grammar that you can use
to parse the input string $w$. The problem is that parsing with the
brutal intersection construction with give you strings at any
Levenshtein distance, i.e. $\Sigma^*$.

It would be easy to prune that construction to get the same result as
before, but the best way is a more controlled intersection
construction, such as the dynamic programming organization used by
most parsers in the literature, including Earley's, and use it to
avoid generating useless rule by computing distances and aborting any
computational path when it exceeds the desired threshold. Dynamic
programming can also be used to compute directly the parse-forest (or
parse-tree) for the string that have the shortest distance to the
input.


Examples of higher order algorithms ($\mathcal{O}(n^4)$ or larger) In most computer science cirriculums, students only get to see algorithms that run in very lower time complexities. For example these generally are

Constant time $\mathcal{O}(1)$: Ex sum of first $n$ numbers
Logarithmic time $\mathcal{O}(\log n)$: Ex binary searching a sorted list
Linear time $\mathcal{O}(n)$: Ex Searching an unsorted list
LogLinear time $\mathcal{O}(n\log n)$: Ex Merge Sort
Quadratic time $\mathcal{O}(n^2)$: Ex Bubble/Insertion/Selection Sort
(Rarely) Cubic time $\mathcal{O}(n^3)$: Ex Gaussian Elimination of a Matrix

However it can be shown that
$$
\mathcal{O}(1)\subset \mathcal{O}(\log n)\subset \ldots \subset \mathcal{O}(n^3)\subset \mathcal{O}(n^4)\subset\mathcal{O}(n^5)\subset\ldots\subset \mathcal{O}(n^k)\subset\ldots
$$
so it would be expected that there would be more well known problems that are in higher order time complexity classes, such as $\mathcal{O}(n^8)$.
What are some examples of algorithms that fall into these classes $\mathcal{O}(n^k)$ where $k\geq 4$?

Most simple example gives nested cycles: we know that, if we want, for example, find similar elements for 2 arrays, then we used 2 nested loops and therefore we have $O(n^2)$ complexity.
Hence, every 4 nested loops gives complexity $O(n^4)$, $k$ nested loops $O(n^k)$.
Another examples Karmarkar's algorithm, AKS primality test


Why do public key systems involve private keys? I read up the definition of a public key cryptosystem. It mentions there is a public key and a private key. That's confusing. Why is it called a "public key" system if it involves a private key as well?

Public key cryptography means that the entire communication between both parties is public, including the setup. Contrast this with the case of two parties $A,B$ meeting in secret, agreeing on some keyword, and using this keyword to encrypt future communications.
Clearly, if $A,B$ decide on the encrpyption scheme in public, something has to be kept private (otherwise you could decipher the messages just like the parties involved). This is the private key, so the flow is something along the following lines: $A$ and $B$ publicly discuss and share some information with each other and the world, then they do something in private and send each other encrypted messages. Witnesses to the public exchange alone can't recover what is being said.
The child version of such scheme which I like is the following. Suppose $A$ and $B$ want to agree on some secret color, only known to  them, however the entire exchange must be public. Under the assumption that mixing colors is easy, but given a mixture recovering its components is hard, then they could do the following: $A$ and $B$ each choose a secret (private key) color denoted by $a,b$. Then $A$ sends $B$ the color $c$ (public key), and the mixture $(a,c)$. $B$ now creates the mixture $(b,c)$ and sends it to $A$, and also mixes $(a,b,c)$ and keeps this compound to himself. Finally, $A$ adds $a$ to $(b,c)$ and is now also in the possession of the secret mixture $(a,b,c)$, known to $A,B$ but unknown to anyone who solely witnessed the interaction between them.


Question regarding the assumptions of the No-Free-Lunch-Theorem for Search I am trying to understand the No-Free-Lunch-Theorem for search (can be found here: http://axon.cs.byu.edu/~martinez/classes/678/Papers/Wolpert_NFLsearch.pdf) and have a question regarding the assumptions that were made by Wolpert et al. with respect to the "general nature" of a search algorithm.
In the paper, the following definitions were made:

$\mathcal{X}$ is the (finite) population of solutions,
$\mathcal{Y}$ is the (finite) evaluation space (e.g. a subset of $\mathbb{R}$),
$f : \mathcal{X} \rightarrow \mathcal{Y}$ is a cost-function,
$d_m = \{ d_m(i) : 1 \leq i \leq m \} = \{ (d_m^x(i), d_m^y(i)) : 1 \leq i \leq m \} \in \mathcal{D_m}$ is the "history", i.e. the sequence of solution/cost-pairs $(x_1,f(x_1)),\dots,(x_m,f(x_m)) \in \mathcal{X} \times \mathcal{Y}$ that were found until time point $m$,
$a : \cup_{i \geq m} \mathcal{D}_m \rightarrow \mathcal{X}$ is a decision function that yields the next solution dependent on the recent history and
$\vec{c} \in \mathbb{N}^{\mathcal{Y}}$ is the histogram, which is the vector that stores the number of times every score was reached up until time $m$.

The work then shows that the equality $$ \sum_{f} P(\vec{c} \mid f,m,a_1) = \sum_{f} P(\vec{c}\mid f,m,a_2) $$ holds for all $m=1,2,\dots$ where $a_1$ and $a_2$ are arbitrary decision-functions and the sum spans over all possible cost-functions. The proof was done via induction on $m$, in which the equality
$$ P(x \mid d_m, f, m+1, a) = P(x \mid d_m, a) $$
was neccessary for the induction step (page 6). As I understood it, this basically means: the choice of the next solution $x \in \mathcal{X}$ is only dependent on the previous history $d_m$, since $x = a(d_m)$, and therefore independent of the cost-function $f$.
I agree that this holds if based on the above definitions, but I don't really think that this is how most search algorithms work? For example, a simple hill-climbing-algorithm would select a set of neighbours for every solution, compare them, and would then select the best neighbour, dependent on how they score on the cost-function. Therefore, the choice of the successor $x$ would depend on $f$, and one would have something like $x = a(d_m,f)$, i.e. the above part in the induction step wouldn't work.
So, my question basically is: am I missing something or is this work based on a wrong understanding of search algorithms?

I think that I was indeed misunderstanding something. Any search algorithm that wants to evaluate any point $x \in \mathcal{X}$ through $f$ would implicitly add $(x,f(x))$ to the histogram $d$. For example, one could design a hill-climbing algorithm in the following way:

for a solution $x'$, visit all neighbours $x_1,\dots,x_n$
afterwards, $(x',f(x')), (x_1,f(x_1)),\dots,(x_n,f(x_n))$ are all part of the histogram $d$
choose the best neighbour from $x_1,\dots,x_n$ by computing $a(d) = \arg\min_{x=x_1,\dots,x_n} f(x)$, which is independent of $f$ since $f(x_1),\dots,f(x_n)$ are already known
repeat


algorithm analysis - complex dependant nested loop First of all, I know there are many questions like this on the site. But I think this case is a bit different.

Consider the following code:

int i, j, k;

for (i = 1; i <= n; i++){
    for (j = 1; j <= (n-i); j++) {
        System.out.print(" ");
    }

    for (k = 1; k <= (i-j); k++) {
        System.out.print(i);
    }

    System.out.println();
}

What would be the time complexity of this code? It seems like O(n^2) to me but I can't justify it properly.

How our professor told us to compute complexity is just by adding all the summations together from every line.

$$
(n+1) + \sum_{j=1}^{N-i} + \sum_{j=1}^{N-i} + \sum_{k=1}^{i-j} + \sum_{k=1}^{i-j} + n
$$

However, I've never seen examples with summations like $\sum_{j=1}^{N-i}$, It's always either $\sum_{j=1}^{N-1}$ or some constant number being subtracted from N, which is easier to sum. So, How would I solve this? And is it O(n^2)?

The number of print statements executed is
$$
\sum_{i=1}^n \left[ \left(\sum_{j=1}^{n-i} 1\right) + \left(\sum_{k=1}^{i-(n-i+1)} 1\right) + 1 \right],
$$
where the second sum is zero if $1 > i-(n-i+1)$.

The running time is proportional to the number of print statements, so it remains to compute the value of the expression above, or at least to give a good estimate. This I leave to you.


Prove that the language represented having equal number of $0$'s and $1$'s and starting with a $0$ is not regular We have to prove that the language represented having equal number of $0$'s and $1$'s and starting with a $0$ is not regular.

Attempt: We assume that the language is regular. Thus it would satisfy the pumping lemma. Assume the pumping length to be $p$. Let us take the string would be length $p+1$ as  $0 0^p 1^{p+1}$. Now we need to divide this string into three parts $xyz$ such that the pumping property does not hold. The pumping lemma restricts the size of $xy$ to be less than or equal to $p$. So the y part can comprise entirely of only $0$'s. If we pump the $y$ part we can end up with strings having more number of $0$'s than $1$'s. Is this correct with respect to the string that has been considered? What other strings can be used to show this?

First of all, your language definition seems vague. By "starting with a 0", it can mean two things. Either there is an extra 0 at the beginning of the string, followed by equal number of 0s and 1s, i.e number of 0's is greater than the number of 1's by 1, or it could also mean the string has an equal number of 0's and 1's, but starts with 0 instead of 1. Please define it clearly for the sake of clarity. I'm assuming your language definition to be the former, since you've mentioned in your attempt that you're taking the generic string to be $00^p1^{p+1}$, basically implying the string is of the form $0^n1^n$.

Secondly, the length of the string you've taken, $i.e$ - $|0 0^p 1^{p+1}| = 1+p+p+1 = 2p+2$, and not $p+1$.

Given that the string you have taken is of length 2p+2 which is definitely greater or equal to $p$ (the pumping length you have assumed in this case), your approach seems right. Although you can use the generic proof of proving that any language of the form $L = \{ a^nb^n : n ≥ 1 \}$ is not regular, in this case.

Regarding what other string you could take, You can basically take any string of the form $0^n 1^n$ (divide it however you want), i.e it should just satisfy the condition that there should be equal number of $0$'s and $1$'s, and start with zero.

The generic string $0^n 1^n$ works for the general proof. It is obviously longer than $n$. Considering $xyz = 0^n 1^n$, $|xy| ≤ n$, hence $y$ can only contain $0$'s, $y ≠ \epsilon$, $\implies$ y must contain at least one 0. Now $xy^0z \in L$ according to the pumping lemma, but this is a contradiction, as it would imply that it contains at least one $0$ less, but the same number of $1$s as in $0^n 1^n$. Hence, L is not regular.


Comparison between: Maximum Absolute Difference & Min Steps in Infinite Grid There are two questions that I am trying to draw a comparison between:

Q1: Maximum Absolute Difference
You are given an array of N integers, A1, A2 ,…, AN. Return maximum value of f(i, j) for all 1 ≤ i, j ≤ N.
f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.

Q2: Min Steps in Infinite Grid
You are in an infinite 2D grid where you can move in any of the 8 directions :
    (x,y) to
    (x+1, y),
    (x - 1, y),
    (x, y+1),
    (x, y-1),
    (x-1, y-1),
    (x+1,y+1),
    (x-1,y+1),
    (x+1,y-1)

I was reading up about the Q2 and I came across this stackoverflow question. Here, the accepted answer reduces this question to given a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance)

Reading up, I think both these questions are exactly the same except that Q1 is asking for Manhattan Distance in 1D and Q2 is asking for Manhattan Distance in 2D.

I am not very clear about this. Can someone please verify my observation?

It is nice that you try to draw a comparison between two similar situations. However, it looks like you are driving too fast to stay on the right road. Henceforth I will be moving somewhat slowly so as to stay on the correct path.
What is generally considered as a distance? You might react, hi, I know what is a distance! Cool then. Here is the widely-agreed general definition of a distance according to Wikipedia as well as my years of practice in math and computer science.

In mathematics, in particular geometry, a distance function on a given set $M$ is a function $d: M \times M \to R$, where $R$ denotes the set of real numbers, that satisfies the following conditions:

$d(x,y) ≥ 0$, and $d(x,y) = 0$ if and only if $x = y$. (Distance is positive between two different points, and is zero precisely from a point to itself.)
It is symmetric: $d(x,y) = d(y,x)$. (The distance between $x$ and $y$ is the same in either direction.)
It satisfies the triangle inequality: $d(x,z) ≤ d(x,y) + d(y,z)$. (The distance between two points is the shortest distance along any path). Such a distance function is known as a metric. Together with the set, it makes up a metric space.

Now let us write out explicitly our distance functions and metric spaces.

In Q1, $f$ defines a distance function on all integers from 1 to $N$ such that $f(i,j) = |A[i] - A[j]| + |i - j|$. All integers from 1 to $N$, together with $f$ forms a metric space, say, $M1$.
Let $\Bbb Z^2$ be all the grid points in 2D. Let $d2$ be the minimal steps needed for you to move from point (x,y) to point (p,q), where each step must be one of the eight kind of steps listed. Then $\Bbb Z^2$, together with $d2$ forms a metric space, say, $M2$. Note that $d2((0,0),(0,1))=1$, $d2((0,0),(1,0))=1\,$ and $d2((0,0),(1,1))=1$.
Denote the Manhattan distance by $ma$, i.e., $ma((x,y),(p,q))=|x-p| + |y-q|$. $\Bbb Z^2$, together with $ma$ forms a metric space, say, $MA$. Note that $ma((0,0),(0,1))=1$, $ma((0,0),(1,0))=1\,$ and $ma((0,0),(1,1))=2$.

Now please follow my observations below.

$M1$ can be considered as a part of $MA$. Why? Define $e$: $i\mapsto (A(i),i)$. Then you can see that $d1(i,j)=ma(e(i), e(j))$, i.e., the distance between $i$ and $j$ in $M1$ is the same as the distance between $e(i)$ and $e(j)$ in $M2$. You can imagine that $e$ just embeds all integers $1, 2, \cdots, N$ in $M1$ to $MA$, keeping their pairwise distances. This is the simple reason why the accepted answer to Q1 can reduce it to given a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance).
$M1$ may or may not be considered as part of $M2$. It depends on how sequence $A$ is defined.

Let $A_k$ be 0 for all $k$. Then $M1$ is just those 1D integers with their usual Euclidean distance among them. It can be embedded easily into the $M2$, keep their pairwise distances.
Let $A_1=0$, $A_2=1$, $A_3=0$, $A_4=1$. Then you will find the four integers 1,2,3,4 in $M1$ has pairwise distance 2 except that $d1(1,4)=4$. However, you cannot find that kind of 4 points in $M2$. This particular example shows that your intuition "both these questions are exactly the same" is suspicious.

The distance in $M2$ is not a Manhattan Distance. You can have 8 points each of which is 1 distance away from any given points in $M2$. For example, $(1,0), (1,1), (0,1), (-1, 1), (-1,0), (-1,-1), (0, -1), (1, -1)$ are 1 distance away from $(0,0)$ in $M2$. However, there is only 4 points each of which is 1 distance away from any given point in $MA$. For example, $(1,0), (0,1), (-1,0), (0, -1)$ are 1 distance away from $(0,0)$ in $MA$. You can also check that $(0,0), (0,1), (1,1)$ is the vertices of an equilateral triangle in $M2$ with side length 1. However, you will not be able to find such an triangle in the Manhattan space $MA$.

Hopefully I have cleared all your doubts. Here are a few exercises for you to arrive at a better understanding of the concepts.
Exercise 0. Verify that $d1$, $d2$ and $ma$ are distance functions according to the definition.
Exercise 1. Suppose $A_1, A_2, \cdots, A_n$ is an increasing sequence of integers. Show that $M1$ can be considered a part of $M2$. Show that $M1$ can also be considered as a part of $MA$.
Exercise 2. Find 4 points in $M2$ whose pairwise distance are the same. Show that there is no 4 points in $MA$ whose pairwise distances are the same.
Exercise 3. Given an $m$ by $n$ grid in $M2$ with its bottom left corner $A$ at $(0,0)$ and its upper right corner $B$ at $(m, n)$. $0\le m \le 20$. $0\le n \le 20$.  Compute the number of paths starting at $A$ and ending at $B$, where you must always move closer to $B$ along the path.


If Q1 and Q2 are countably enumerable, then is Q1\Q2 countably enumerable? If Q1 and Q2 are countably enumerable, then is Q1\Q2 countably enumerable?

I am reading a text where they claim that this is not the case and ask the reader to come up with a counter example.

Can someone give a counter example to the claim that if both Q1 and Q2 are c.e. then so is Q1\Q2?

Since H is semi-decidable and hence also c.e., I was thinking of coming up with examples using it, but no success till now.

First of all, notice that not all c.e. sets have a c.e. complement, i.e. there are c.e. sets like $Q$ such that $Q^c=\mathbb{N}-Q$ is not c.e. In fact the  Halting Problem $H$ is such a c.e. set.

To see why $H^c$ is not c.e., notice that if both a set and its complement are semi-decidable, then both are also decidable. And since $H$ is not decidable, then $H^c$ should not be semi-decidable either.

Now for the counter example to your question, let $Q_1 = \mathbb{N}$ and $Q_2 = H$. Then $\mathbb{N} - H = H^c$, is not c.e.

Edit: Explained $H^c$ and added a simpler and more straightforward counter example.


Is there any importance in problems whose witness for membership in a set, cannot be bounded by a polynomial? The class NP can be defined as a polynomially bounded relation $R$. Where $x \in R$ if there exists some $y$ that has length bounded by $p(|x|)$, where $p$ is some polynomial.

Why do we not study the case where $y$ is not bounded by a polynomial?
Is there any significance in problems of this nature; in-efficient proof systems?

If we remove the condition on the size of the witness, then a problem is in the resulting class NANY iff it is recursively enumerable.

Indeed, if $L$ is in NANY, then given $x$, we can go over all possible $y$, and for each of them run the machine that decides whether $y$ is a witness for $x \in L$.

In the other direction, suppose that the Turing machine $M$ halts on $x$ iff $x \in L$. We can use the transcript of a halting computation as a witness that $x \in L$.


Exact meaning of metalinguistic variable Consider the following BNF

<join-command> ::= <string> + <string>

In this context <join-command> and <string> are normally called metalinguistic variables or syntactic categories. Note that the first usage of <string> don't necessarily represent the same terminal string as the second usage.

Recently however I come across a slightly different notion of "metalinguistic variable" (in a course about formal logic). Here it meant a variable of the metalanguage that represent one string of the object language (i.e. terminal language) and always that. So the previous syntax would become:

<join-command> ::= <string1> + <string2>

What's the correct terminology? Should I avoid calling BNF syntactic categories "metalinguistic variables"?

Maybe calling them "syntactic variables" would fix the ambiguity?

Personally, I call them "non-terminals", following Chomsky rather than Backus.

But I'm not going to attempt to argue any sort of universal correctness of that terminology. Definitions in mathematics are purely instrumental, just like variable names in a program (or even metavariable metanomenclature).

You can α-convert a mathematical exposition by consistently replacing a defined phrase with some other phrase not used anywhere in the text, say "colourless green ideas", and every assertion will retain the same truth value. It might be harder to follow, but that's a purely aesthetic consideration.

So here's my aesthetic argument for calling these things "non-terminals" rather than "metalinguistic variables" or "syntactic categories": the term "non-terminal" does not in any way imply that the objects have any useful semantics. A generative grammar does not rely on any particular semantic connotation for the intermediate symbols used in the derivation, and indeeds quite common to write grammars with rather artificial non-terminals which do not serve any need other than that of facilitating a particular parsing algorithm.

I suppose "metalinguistic variable" might also be neutral in that sense, but it seems a bit much to describe a placeholder and "non-terminal" rolls more easily off the tongue.


What's the maximum memory address space that the processor can access directly if it connected to a 16-bit memory? The question is the following:
3. Given a hypothetical microprocessor which generates a 16-bit address (assume that the program counter and address registers are 16 bits wide) and has a 16 bit data bus.
a) What is the maximum memory address space that the processor can access directly if it connected to a "16-bit memory"?
b) What is the maximum memory address space that the processor can access directly if it is connected to an "8-bit memory"?

It feels like the answer to both would be 2^16, which is equivalent to 24KiB. It also feel natural to say that an 8-bit memory can tranfer 8 bits and a 16 bit memory can transfer 8 or 16 bit words.

But the problem is that the actual answer booklet says the following:
In cases (a) and (b), the microprocessor will be able to access 2^16 = 64K bytes; the only difference is that with an 8-bit memory each access will transfer a byte, while with a 16-bit memory an access may transfer a byte or a 16-byte word.

So 1) 64K? Isn't the unit suppose to be KiB? I am very confused.
2) 16-byte word? Shouldn't it be a 16-bits word?

I think there is a confusion here between the number of memory addresses and the total size of memory that can be addressed.

The microprocessor can access $2^{16} = 65536$ memory addresses, regardless of the size of data held at each memory address.

If each memory address holds one byte ($8$ bits) of data then the total memory size that can be addressed directly is $2^{16} \text{ bytes}$, which is $2^6 \text{ KiB} = 64 \text{ KiB}$.

On the other hand, if each memory address holds two bytes ($16$ bits) then the total memory size that can be addressed directly is $2 \times 2^6 \text{ KiB} = 128 \text{ KiB}$.

It also appears your text is using KB as an abbreviation for KiB, which is a common shorthand but not strictly correct.


What is the Difference Between Many-to-Many (M:M) Threading and Hybrid (M:N) Threading? I have been researching threading and come across several websites which all say contradicting statements about which and how many thread models exist. Some websites say there are only three: 1:1, M:1 and M:M, while others say the three are 1:1, M:1 and hybrid (M:N). Still others say there are four types, including 2-level threading?

Google and stack exchange haven't been able to come up with a clear answer as of yet. I was hoping for someone to shed some light on this situation, namely the difference (i.e pros & cons) between M:M, M:N and two-level threading types.

Go to a website selling computers (or phones). Check how many cores the computers have, and whether they support hyper threading. So there you get the number how many threads can actually run at the same time.

On the other side, your software can use a single active thread, or 100 active threads. Some software can actually make use of many threads, other software can't. Your computer however can run more than one software at the same time, so there will be more active threads.

So everything is M:N. M = 1 or N = 1 is possible but rare. If M < N then some cores are unused and might as well not be there. If M > N then at any point in time, at most N of the M threads are running. And M changes all the time.


String Search - how to find the "most" accurate string? Assume I have the following list of companies:

Apple
Big Apple
Google

Then I have this sample string:

  Big Apple is a company that is trying to be the next Google.

Given the list of companies and the sample string above, how can I find the list of companies in the sample string?

If I iterate through the list of companies and search for it in the sample string, I would find three matches: Apple (because "Apple" exist in "Big Apple"), Big Apple, and Google. In my scenario, I wouldn't want just Apple to match since Big Apple is a more accurate match.

I'm trying to implement the solution in PHP, but a general description/strategy on how to solve this would be helpful.

One way to do so is as follows:

Sort the company names from longest to shortest.
For each company name $c$:

a. Find all the substrings of the input string that equal $c$ and don't use any characters from a previous occurrence of a company name.

b. If some substring exists, add $c$ to the solution.

This strategy works if you're trying to solve the problem you've stated. But if you want a more robust solution, you should look into using natural language processing tools like Python's NLTK. These tools allow you to take syntax and context into account, and might help you tell the difference between "I ate a big apple", and "I bought shares in Big Apple".


Algorithm: How to find the number of independent sets in a tree? I'm thinking that there are two cases for each sub-tree: the root is in the independent set and the root is not in the set. How to write a recursive algorithm for finding the number of independent sets in a tree? The tree is n-ary.

Let $T$ be the tree. For every $n\in T$, we indicate the number of independent sets in the subtree of $T$ rooted in $n$ that contain $n$ with $A(n)$, and the number of independent sets that do not contain $n$ with $B(n)$.

The following recursive relations hold:

$$
\left \{
\begin{array}{r c l}
A(n) & = & \prod_{m \in Adj[n]}B(m) \\
B(n) & = & \prod_{m \in Adj[n]}A(m) +B(m)
\end{array}
\right .
$$

Notice that we are using a constant number of memoization cells for each node of $T$. Interestingly enough, if $T$ is a line tree of $k$ nodes, the answer is exactly the $k$-th Fibonacci number.


what does "reduce A problem to B problem in polynomial time" mean? It is kind of NP-complete problem.
For example,

A problem:
Given a sequence of numbers, return the maximum value within these numbers.
B problem:
Given a sequence of numbers, return start index and end index of the maximum sum segment within these numbers.

To show how to reduce A problem to B problem in O(n) time.
Does this means we could solve A problem by solving B problems?
It seems a little bit strange for this case.

There are several types of reductions, the most common of which are many-one reductions and oracle reductions.

A many-one reduction from $A$ to $B$ is a computable function $f$ mapping strings to strings such that $x \in A$ iff $f(x) \in B$.

An oracle reduction from $A$ to $B$ is a computable function $f$ which has access to a $B$-oracle, and satisfies $f(x) = 1$ iff $x \in A$. That is, $f$ decides membership in $A$. The machine has a mechanism for accessing the oracle. When the oracle is presented a string $y$, it tells the program whether $y \in B$ or not.

Every many-one reduction $f$ can be formulated as an oracle reduction: the oracle reduction first computes $f(x)$, then asks the oracle whether $f(x) \in B$, and outputs the oracle's answer.

In the theory of NP-completeness, we always use many-one reductions. Reducing a problem A to a problem B in time $T(n)$ means giving a many-one reduction from A to B which runs in time $T(n)$. In particular, reducing A to B in polynomial time means reducing A to B in time $O(n^k)$ for some fixed $k$.

In your particular case it is hard to tell which kind of reduction is meant, since your problems are not decision problems. Perhaps some restricted kind of linear time oracle reduction, say one accessing the oracle only once. It's also not clear what computation model you should use. Under some computation models you can solve problem A in linear time, and so such a reduction trivially exists (it never asks the oracle anything).


Arranging tasks with specific constraints (scheduling) I have the following problem:

Given a set of tasks and their duration, i need to arrange them taking in consideration some constraints; Here's an example:

Suppose we are scheduling talks in a conferece. Each talk has a duration, and we can use as many rooms as we need. For each room, we have two sessions: one in the morning, and one in the afternoon. Morning one starts at, say, 9 AM and must end exactly by noon. The afternoon one starts at 1 PM and must end between 4PM and 5PM.

How do i arrange these talks in sessions in such a way that uses the least amount of rooms possible?

I've researched some scheduling problems, but none of them seem to take into account the constraints i need. I have read about:

http://en.wikipedia.org/wiki/Interval_scheduling

http://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling

http://en.wikipedia.org/wiki/Flow_shop_scheduling

This is actually a bin packing problem, rather than a scheduling problem.  If I remember correctly (it's been a long time) bin packing is the dual of scheduling.

In the most basic kind of bin packing problems each room would be available for exactly three hours, and the goal would be to minimize the total number of three-hour sessions you would consume.  Your problem has an extra constraint that rooms come in pairs that are available for 3 and 4 hours.

Bin packing problems are usually NP-complete, but there are some heuristics that tend to work well in practice.  For the basic bin packing problem the usual heuristic would be to sort the talks from longest to shortest.  Then start placing talks into rooms in that order.  For each talk examine the rooms in the same order.  Place the talk in the first room where it will fit.  You only rent a new room if you have a talk that won't fit in any of the existing rooms.

There's a bit more on the Wikipedia Bin packing page:
http://en.wikipedia.org/wiki/Bin_packing_problem

And I found this article, which describes some of the approximation algorithm results in this area (as of 1987):
http://www.columbia.edu/~cs2035/courses/ieor6400.F07/hs.pdf


Measuring time complexity of algorithm I was going through a past paper question but I don't have any answers to know if I'm working out the problems correctly or not.

I need to find the time complexity for:

i) repeat
      n:=n div 2;
   until n=1;

ii) for i:=1 to n do
       begin
          for j:=1 to n do
             begin
                for k:=1 to n do;
             end;
       end;

iii) repeat
        for i:=1 to n do
           begin
              for j:=1 to n do;
           end;
     n:=n div 2
     until n=1

In my opinion, the answer for (ii) is $O(\log n)$ and the answer for (ii) is $O(n^3)$ but I'm not sure about my answers. Regarding question (iii) I have no idea how to come up with a solution.

For 1, suppose that $n = 2^{m+\delta}$, where $m$ is an integer and $\delta \in [0,1)$, and compute how many iterations the loop has.

For 2, it's easy to see that it's $\Theta(n^3)$.

For 3, the "inner" loop is $\Theta(n^2)$. Now suppose that $n = 2^{m+\delta}$ and follow the same procedure as in 1. (For starters, you might want to assume that $\delta = 0$.) You will get $\Theta$ of
$$ n^2 + \frac{n^2}{4} + \frac{n^2}{16} + \cdots = \Theta(n^2). $$


Disprove unrealistic speed-up of total Turing machines Let $T_1$ be a total Turing machine deciding language $L_1$, and let $I_1$ and $I_2$ be two separate inputs to $T_1$. Further, let $I_{c}$ be $I_2$ concatenated to $I_1$ with some separation symbol in between, and let $S_{T}(I)$ be the number of steps total TM $T$ needs to run until it accepts/rejects input $I$. I am wondering about the following two statements:

For every $T_1$ there exists another total Turing machine $T_2$ such that for all valid inputs $I_1 \neq I_2$ for $T_1$, $T_2$ accepts $I_c$ if $T_1$ accepts $I_1$ or if $T_1$ accepts $I_2$.

For every $T_1$, there exists a $T_2$ with the above property such that for all valid inputs $I_1 \neq I_2$, it holds that $S_{T_2}(I_c) < S_{T_1}(I_1) + S_{T_1}(I_2)$

To me, it seems as if the second statement would imply an impossible speed-up and should have an obvious counterexample, but I haven't been able to come up with one.

Suppose that the input alphabet is $\{0,1\}$, and consider the language $L_1 = 0^*$. We can easily construct a Turing machine $T_1$ such that $S_{T_1}(I) = |I|+1$. On the other hand, $S_{T_2}(I_c) \geq |I_c|+1$. Since $|I_c|=|I_1|+1+|I_2|$, we get
$$
S_{T_2}(I_c) \geq |I_1|+1+|I_2|+1 = S_{T_1}(I_1) + S_{T_1}(I_2).
$$


Why is an Artificial Neural Network with high accuracy score giving poor results? I implemented my ANN using SKlearn module's class MLPClassifier. Fitting it on some data and testing it on a very specific subset of said training data, it gives a score of 1.0, but actually using the ANN to generate outputs for said testing data almost always gives incorrect output. What could be the possible reasons for this?
I am using this ANN as a memory network and there is never a case when input is out of training data.

You're testing your neural net with data from the training set, of course it will get you great results. But you're neural net is now trained for a specific data and is unable to make generalization. This is known as Overfitting.

You should either split your data into test/train or use another technique to estimate your NN performance. A good technique is K-fold Cross validation.

Also check Overfitting wiki page and Cross validation on sklearn if you want more details.


Using the Master theorem on a recurrence with non-constant a I am trying to solve the following equation using master's theorem.

$T(n)  = 3^n T(\frac{n} 3) + O(1)$

Extracting the b and $f(n)$ values makes sense they are $b=3$ and $f(n)=1$. I am not sure what my $a$ value is I don't think its just 3.

This is not solvable using (only) the Master Theorem. It's not in the correct form. The Master Theorem only applies when there's a constant in front of the $T(n/b)$, and $3^n$ is definitely not a constant.

You should try calculating a bound for $\log(T(n))$ instead. Even though that won't give a tight bound it will get you on the right track.


Parallelization of an iterative function application What I have
An iterative process based on the application of a very simple function to represent a rate, with total dependence among any iteration and its predecessor (one input parameter for (n)th iteration is the output parameter from the (n-1)th iteration). Specifically,
$\qquad  f(x, y, z) = x + \frac{y - x}{z + 1}$
with $x$ the modeled rate (typical value between 0 and 1),  $y$ the contribution of every new record to the learning about the rate (typical value 0 or 1) and $z$ some kind of convergence/learning speed parameter (typical value any integer between 30 and 900). While $y$ and $z$ are constant, $x$ would be the result of the previous calculation.
What I want
Some kind of manipulation of the function that allows some level of independence among sequential iterations, thus allowing parallelization.
What I know (or believe to) so far:
There is extensive published literature on parallel iterative methods, but most of them are about classical methods like Map-Reduce for Machine Learning on Multicore by Chu et al.
But I'm failing to recognize which of them I could "use" to help me with my simple function.
Can someone help me pointing literature on the basics of function transformation aiming towards parallelization? Any thoughts on that matter will be very helpful.

A good starting point is the Wikipedia article on Prefix Sums.  A particularly good source is Guy Blelloch's article about Prefix Sums.

The idea is this: if you have an associative operator (e.g., "+"), you can turn a long dependent chain of those operators into a tree that is more balanced.

For the example you gave, $f(x,y,z) = x + (y-x)/(z+1)$ we can actually generalize to an entire class of problems.
$$
\begin{array}{rcl}
x_{i+1} & = & x_i + (y_{i+1}-x_i)/(z_{i+1}+1)                                     \\
        & = & \frac{y_{i+1}}{z_{i+1}+1} + \frac{x_i (z_{i+1}+1) - x_i}{z_{i+1}+1} \\
        & = & \frac{y_{i+1}}{z_{i+1}+1} + \frac{z_{i+1}}{z_{i+1}+1} x_i           \\
        & = & a_{i+1} + b_{i+1} x_i\mathrm{,}
\end{array}
$$
where the $a_i$ and $b_i$ can be calculated completely in parallel.  So the calculation looks like:

Ok.  So let's look at a few iterations starting at $x_i$ through $x_{i+3}$:
$$
\begin{array}{rcl}
x_{i+2} & = & a_{i+2} + b_{i+2} x_{i+1}                                        \\
        & = & a_{i+2} + b_{i+2} (a_{i+1} + b_{i+1} x_i)                        \\
        & = & (a_{i+2} + a_{i+1} b_{i+2}) + b_{i+2}b_{i+1} x_i                 \\
x_{i+3} & = & a_{i+3} + b_{i+3} x_{i+2}                                        \\
        & = & a_{i+3} + b_{i+3} (a_{i+2} + a_{i+1} b_{i+2} + b_{i+2}b_{i+1}x_i)\\
        & = & (a_{i+3} + a_{i+2}b_{i+3}  + a_{i+1}b_{i+3}b_{i+2}) + b_{i+3}b_{i+2}b_{i+1}x_i\\
        & = & A_{i+1,i+3} + B_{i+1,i+3}x_i
\end{array}
$$

and so on.  The interesting thing is that we can calculate $x_{i+k}$ as $A_{i+1,i+k} + B_{i+1,i+k}x_i,$ where large chunks of computation can be summed up independently in the $A_{i+k}$ and the $B_{i+k},$ without knowing $x_{i+1}, \cdots, x_{i+k-1}.$

Now let's chunk up the work of calculating the $x_i$'s.  Here's what it might look like if we divided the calculation up into 4 equal parts and put each part on a different thread:

So each thread works completely independently to calculate the $A_i$ and $B_i$.  Then we have a final (sequential) phase where we calculate $x_{n/4}, x_{2n/4}, x_{3n/4},$ and $x_n$.

As Guy Blelloch's article shows, you can actually calculate all the partial sums with one last step, if you need them.