How does maths consistency impacts on computer science? Lot of mathematicians have made several efforts to answer the question : are mathematics consistent ? Although we haven't yet had a proof of consistency, and surely we will never (Gödel second theorem), does this question has an impact on computer science ? I mean, does the work of those mathematicians, like Gödel's theorems or formal deduction systems, shows new answers or new problems in computer science ? What would happen in computer science if, for example, we found a paradox in set theory ?

Absolutely nothing will happen. Computers will still work, experts in machine learning will continue perfecting their tools, and even theoretical computer scientists will go on happily proving their theorems. Most mathematicians will also not feel much difference.

While we are trained to think that we are carrying out our proofs in ZFC, in practice proofs in mathematics and computer science are almost always carried out in English. Even if a contradiction is discovered in set theory, it is extremely likely that the axioms can be amended in such a way that the contradiction disappears and no proofs are affected apart from those in very specialized fields of a foundational nature.

More controversially, one can argue that most mathematicians argue in a nebulous system which actually does not rely on ZFC at all. Indeed, the average mathematician and nearly all computer scientists have little recourse to ZFC during their research life. Making this claim less nebulous, one can (and people do) argue that virtually all proofs in non-foundational fields can be carried out in weak subsystems of ZFC that are in less danger of being shown to be inconsistent. A nice reading in this general direction is McLarty's What does it take to prove Fermat's last theorem.


Data structure for storing edges of a graph I'm currently working on my masters thesis, and it's about clustering on graphs. I'm working with an idea using ants to solve the problem. I'm currently working on the implementation and am wondering exactly how well to represent the edges of the graph.

Each edge is augmented with certain information such as its pheromone value and the number of times an ant has visited that edge. I'll be working with undirected graphs, which can be end up being pretty huge (over a million vertices) and I was wondering what is the most efficient way for me to store the edges and look them up? I was thinking of sticking to a convention and store endpoints according to the one which has a lower vertex id for $v_1$ and the higher one for $v_2$ ($v_1$ and $v_2$ are the endpoints of the edge in the data structure). But I'm wondering how would I perform a look up in this case?

There is a mapping I came up with from the adjacency matrix to the edge array, but that works only if the underlying graph is a complete graph. So I came here for some suggestions as to how I should proceed because I need my lookup to be efficient while at the same time I don't want to blow up the storage space for the edges as the graphs will be huge.

If your graph is sparse then you should store it using adjacency "lists", though you probably want something more efficient than a list (or perhaps you don't, depending on usage). It's simplest if you store each edge at both endpoints. This can be implemented in many ways, for example you can store all data in some big array, and store only pointers in the adjacency "lists".


Product Matching problem in pattern matching The Product Matching problem is defined as follows:
Input: Text T=t0,...,tn and pattern P=p0,...,pm over alphabet Σ=N .

Output : All of the i places in the text where exists ci which holds
ti+j = ci * pj for every j=0,...,m

For example:
T= 2,3,9,12,1,8 P = 1,3,4
so in index 1 there is a match for ci=3 because:
1*3 = 3 , 3*3=9, 4*3=12

I've only managed to think about the naive way of multiplying the pattern for each number that gives
us less or equal value to max{T} and then checking it with a regular O(N) pattern matching algorithm.

Hint: Starting with the original text, form a sequence $s_1,\ldots,s_n$ by the rule $s_i = t_i/t_{t-1}$, and similarly from the original pattern form a sequence $q_1,\ldots,q_m$ by the rule $q_j = p_j/p_{j-1}$. Look for the pattern $q$ inside the text $s$.


Which algorithm for counting the occurrences of a certain pattern (spots) in an image? The Problem :

Finding the number of occurrences of a certain pattern (or shape) in an image. In my example, the problem is about finding the number of spots (in variety of sizes) in an image. See figure 1 below:

What I'm looking for here is an orientation. What class of algorithms can lead to a solution for this type of problems?

The best way to get an orientation is to read a textbook on computer vision or image processing.  There are lots of techniques known, and that's often the best way to get an introduction to a broad topic like this.

Anyway, for some specific techniques, I would recommend that you learn about the following candidate approaches:

Learn about morphological operators, and experiment with a few combinations of them.
Learn about the watershed transform, which might solve your problem immediately.  More generally, learn about image segmentation techniques, of which there are many.
You might want to consider applying thresholding to the image as a pre-processing step.

Your task looks pretty easy, so I imagine you should be able to find a very effective combination of techniques if you learn about them and try them out on sample images.


Disjoint union of NP-hard problem and P problem is NP-hard Let $Σ = \{0, 1\}$ and let $A, B ⊆ Σ^*$ be languages. Prove that if $A$ is NP-hard, $B$ is in P,
  $A ∩ B = ∅$, and $A ∪ B ≠ Σ^*$, then $A ∪ B$ in NP-hard.

How can I go about proving $A ∪ B$ is NP-hard given the conditions? Any help would be appreciated.

Given an instance $x$ of $A$, reduce it to an instance $y$ of $A \cup B$ as follows:

Check (in polynomial time) if $x \in B$, if the answer is yes, then $x \not\in A$ since $A \cap B = \emptyset$. Pick any $y \in \Sigma^* \setminus (A \cup B)$ (which is non-empty by hypothesis).
If $x \not\in B$, then $x \in A \cup B \iff x \in A$. Pick $y=x$.


Why is every finite language A ⊆ Σ* regular So I've been doing regular languages a while and still need a better understanding of why all finite languages A ⊆ Σ* are regular? Is there a formal proof of it or is it just because a DFA can represent any finite language since the states would be finite as well?

The proof goes something like this:

If $A$ is a finite language, then it contains a finite number of strings $a_0, a_1, \cdots , a_n$.
The language $\{a_i\}$ consisting of a single literal string $a_i$ is regular.
The union of a finite number of regular languages is also regular.
Therefore, $A = \{a_0\} \cup \{a_1\} \cup \cdots \cup \{a_n\}$ is regular.


Explanation of the complexity of a loop I am confused on the following:
In the following trivial code:

for (int i = 0; i < n; i++) {
  for(int j = i + 1; j < n; j++) {
     for(int k = j + 1; k < n; k++) {
          //some code here
     }
   }
}

I know that the complexity is N^3. But I am confused on some details.
The outer loop is executed N times.
The inner loop I thought that it was executed N*(N-1) times but when I tested with a small example of n=5 it is executed actually N*(N-1)/2 times. And the inner most loop I am lost on how the exact number of times it is executed. I originally thought that it is executed N(N-1)(N-2) but this is wrong again by using a small n the numbers don't work out.
So my question is:
1) Can someone help me understand how the exact complexity is calculated on this trivial example?
2) What is the usual process? Do we select some small numbers and try to derive a formula or what?

You are right that the outer-loop is executed $N$ times, and you are almost right regarding the inner loop. Observe that the inner-loop does not loop the same amount of times at every iteration of the outer-loop. In particular, it will first loop $N-1$ times when $i = 0$, then it will loop $N-2$ times when $i = 1$, $N-3$ times when $i = 2$, and so forth. Therefore, the inner-loop is executed $(N-1) + (N-2) + \ldots + 1 + 0$ times which is the following well known summation: $$\sum_{i=0}^{N-1}i = \frac{(N-1)\cdot N}{2}$$

A similar argument can be made to show what the runtime of the inner-most-loop is. In particular, you will get a similar type of summation.

In general, you will model the loops as summations, and simply evaluate the sum. In your example, you will have that: $$T(N) = \sum_{i = 0}^{N-1}{\sum_{j = i+1}^{N-1}\sum_{k=j+1}^{N-1}}O(1)$$ and evaluating this will give you your $O(N^3)$ answer. Remember that the goal is to "count" the number of primitive operations by the algorithm in question.


Bit distance and disruption Earlier, I asked a question defining disruption in Genetic Algorithms. Given that definition, I'm still confused on how to answer the following question.

  True or false? For  1-point  and  2-point  crossover,  the  schemata
  which  have  bits  that  are  close  together  on  the string encoding
  are more likely to be disrupted by crossover.

From my understanding of cross-over disruption should only be dependant on the number of matching bits strings between parents. So 1001 would be more likely to be disrupted by 0110 then by 1000. So I answered false, but their justification was that bits closer together encourage disruption, which I don't totally understand.

I'm assuming that "bit distance" can be defined as the number of zeros between sequential bits, but based on my proof above, I really don't see how this could affect disruption. Alternatively, I could consider "bit distance" as being the number of bits to flip to reach from one number to another, but based on my proof above, the greater the distance, the greater the chances of disruption.

Where is the mis-understanding between the official answer and my own?

Disruption refers to the phenomenon in which a schema represented by a particular parent is not passed down into its offspring.

That bit about schemata is important -- disruption isn't really defined except for in terms of schemata. Briefly, a schema is a ternary string containing 0s, 1s, and *s (don't-cares), whereas individuals are only binary (no *s). Each individual is a representative of $2^n$ schemata. For example,

10010011

is an instance of all of the following schemata:

1*******
*00**01*
1******1
...

The idea Holland had was that, for example, if good solutions tended to have a 1 in the leading bit, then the proportion of the population that is an instance of the schema

1*******

would increase over time according to a certain inequality. That's the schema theorem. Now, what if instead of that simple schema being more fit than average, we had a more complicated one, like

1*****0*

That is, suppose that individuals matching that pattern are above average in fitness. According to Holland, the GA should work by increasing the proportion of the population that conforms to that pattern over time.

But look at what happens with one-point crossover. It's going to pick a crossover point somewhere along the string and split it around that point. If both parents are instances of the schema, then both children will be as well. But if either parent is not an instance of the schema, then we have a probability that the children won't inherit that pattern. That failure to inherit the pattern is called disruption. Holland would have said that this was very bad. The presence of that schema in the population is evidence that it's good, and crossover is wrecking it. The modern understanding is much more nuanced than that, but that's the rationale behind considering disruption as a concept at least.

So you question asks whether schemata that have bits that are close together are more or less likely to be disrupted. We should really be more precise -- it's not whether any old bits are close together that matters. It's the distance between the first and last non-* bit that matters (called the defining length). The greater that distance, the more likely we'll put a crossover point in between them, and therefore the more likely we are to disrupt the schema.


Are Algebraic types just the combination of case classes and pattern matching? On this page describing the precursor to the Scala language - the pizza language - they refer to it having both case classes and pattern matching - and then imply that these taken together provide algebraic types.

Is this the case? To provide algebraic types - do you combine case classes and pattern matching?

Scala provides algebraic types and pattern matching in a way that is compatible with classes, but this is not what algebraic types are – it is Scala's realisation of the concept. Technically, pattern matching is not even needed for algebraic types; it just makes them must more convenient to use. One could instead use functions the pull apart the types. Early scheme's approach to ADTs would do just this.


Counterexample to greedy solution for set cover problem I am looking for the answer to the exercise 1-6 in "The Algorithm Design Manual" book. it is stated as follows:

1-6. The set cover problem is as follows: given a set of subsets
$S_1,\dots,S_m$ of the universal set $U = \{1,\dots,n\}$, find the smallest subset
of $T \subset S$ subsets such that $\cup_{t_i \in T} t_i = U$. For example, there are the following
subsets, $S_1 = \{1,3,5\}$, $S_2 = \{2,4\}$, $S_3 = \{1,4\}$, and $S_4 = \{2,5\}$. The set
cover would then be $S_1$ and $S_2$.
Find a counterexample for the following algorithm: Select the largest
subset for the cover, and then delete all its elements from the
universal set. Repeat by adding the subset containing the largest
number of uncovered elements until all are covered.

My answer is as follows:

$S = \{\{1, 2\}, \{3, 4\}, \{2, 5\}, \{5\}\}$, $U=\{1,2,3,4,5\}$.
The algorithm will use
the following sets: $\{\{1, 2\}, \{3, 4\}, \{2, 5\}\}$, while {{1, 2}, {3, 4}, {5}}$.
would be more minimal.

Do you think its correct? I assume here that algorithm minimizes number of uncovered elements in each iteration and not the entire size of set to choose – that's why it might choose $\{2,5\}$ instead of $\{5\}$.
I have found this answer online:

One counter-example consists of a series of subsets that increases in
size exponentially, plus 2 additional subsets that each cover half of
the elements. Example:
$S_1 = \{1,2\}$

$S_2 = \{3,4,5,6\}$

$S_3 = \{7,8,9,10,11,12,13,14,15,16\}$

$S_4 = \{1,2,3,4,5,6,7,8\}$
$
S_5 = \{9,10,11,12,13,14,15,16\}$
The greedy algorithm will choose
$S_3,S_2,S_1$, while the optimal solution is simply $S_4,S_5$.

My understanding is that the algorithm would choose $S_3,S_4$ and not $S_3,S_2,S_1$, since $S_4$ has more uncovered elements than $S_2$.

Usually the set cover problem is formulated such that the quantity to be minimized is the number of sets one picks rather than the sum of the numbers of elements of the sets picked.
Unfortunately, this means that your example does not prove that the given greedy algorithm fails to find optimal solutions as the cover it produces consists of 3 sets, which is minimal for your instance.
A valid (and perhaps minimal?) counterexample would be $\mathcal U = \{1, 2, 3, 4, 5, 6\}$ with $\mathcal S =\{\{1, 2, 3\}, \{4, 5, 6\}, \{2, 3, 4, 5\}\}$, which works similarly to the one you found.
The minimal cover consists only of the first two sets (these two must be in every cover since there is no other way to account for $1$ and $6$ otherwise) whereas the greedy algorithm will choose the last set first (since it covers 4 rather than 3 elements) and hence picks all sets, leading to a cover of size 3 which is not optimal.


How is the number of states in a Turing machine bounded? The definition of Turing machine says that the number of states is finite. However, I do not get how this can be true. Is the number of states in a Turing machine actually not fixed, that is not bounded? If not, can anyone explain how this is possible?

You seem to have misunderstood the definition of a Turing machine. The "state" refers not to the whole configuration of the machine (tape contents, position of the head, etc.) but to the state of the finite automaton that controls the tape head.  The automaton has a finite number of states by definition.


How is sound input and output data converted to use with machine learning networks? Suppose one has a couple of .wav files with English spoken words, multiple ones for each word, and for each such set there exists a transcription of their right output, the pronunciation as ascii text.

As far as I know, machine learning neural networks use arrays of floats as input and output, and also internally.

What do one do in machine learning in order to convert such 'real world' data formats/data sets into another data structure that is meaningful and suitable for the machine learning neural networks?

Furthermore, what classifies a particular data structure as 'suitable', except the fact that it can be expressed as arrays of integers (what fits every digital data)?

(I suppose it could be more sophisticated than stripping the headers and feeding the uncompressed binary data in as integers, or is it?)

edit: in an other SE site's question (regarding how to filter out an image of Justin Bieber), an answer asserts that one "has some method of feature generation to transform the raw images into features that are useful for machine learning purposes", but it doesn't explain how this is done, or how does one begin to create a method for such a feature conversion.

Probably the most common way to represent audio for speech recognition is using the Mel-frequency cepstrum coefficients. If you're interested in finding out more about state of the art neural network based systems for speech recognition, I'd recommend checking out some of the recent work by George Dahl.

In regard to the other, more general portion of your question, using "binary" data in the way you describe is a very bad idea (if you mean what I think you mean). The binary representations used to store information in a computer is primarily designed for efficiency, both in terms of operations and space. Thus, this sort of representation is not necessarily representative of the actual characteristics of the data.

An example of this is the difference between signed and unsigned integers. If you're using 8 bit unsigned integers, then 11111111 > 00000001 but if you're using signed (2's complement) integers then 11111111 < 00000001. But, if you just represented the data as binary vectors, then you're essentially forcing a machine learning system to not only figure out whatever relationship you're trying to model, but also whatever encoding scheme you've used. You can avoid this by using representations that respect the characteristics (real valued, categorical, etc) of the data.

Lastly, if you're trying to predict 1 of $k$ mutually exclusive classes (such as characters), then the most common approach is to represent the class label (target) as a $k$ dimensional vector with a 1 at the $i$th position, corresponding to the class, and 0 everywhere else. You'll frequently see this referred to as a 1-of-$k$ or one-hot representation. You'll also want to use an appropriate output function for you're neural net, most likely the softmax function given by

$$
f(x_i) = \frac{\exp(x_i)}{\sum_{j=1}^k \exp(x_j)},
$$
where $x_i$, $i = 1, \ldots, k$, is the total input to the $i$th output unit. You can interpret this type of output as representing the conditional probability of each class given the input. The derivative is also particularly simple under the log-loss, which is what you should probably be using in this scenario.

In conclusion, neural networks are not magic black boxes. Just like any other ML technique, if you just throw data at them without considering the choices (inputs, outputs, loss function, etc) you're making and why, you'll probably have little success.


What does sublinear space mean for Turing machines? The problem of deciding whether an input is a palindrome or not has been proved to require $\Omega(\log n)$ space on a Turing machine. However, even storing the input takes space $n$ so doesn't that mean that all Turing machines require space $\Omega(n)$?

Of course, there's no contradiction here, since any function that uses at least linear space also uses at least logarithmic space. But writing $\Omega(\log n)$ does suggest that it's possible for a Turing machine to use less than linear space – after all, why would people spend all that time proving $\Omega(\log n)$ if that was exactly the same thing what seems to be a trivial $\Omega(n)$ bound? So what does it mean for a Turing machine to use less than linear space?

When dealing with restricted space, we use the following model. The Turing machine has three tapes: a read-only input tape, a read-write work tape, and a write-only output tape. We only measure space consumption on the work tape. For palindromes, with space $O(\log n)$ on the work tape we can implement FOR loops that go over the input, comparing matching characters on both ends. Each index takes $O(\log n)$ space to store.


Reduction of Turing-machine language How to show that the following language is undecidable using reduction on the halting problem?
$L: = \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle M \rangle$ does not accept any input $\}$
When TM doesn't accept any input, does it mean that the Turing machine halts or it just rejects any words?
And how to show that this language is not semi-decidable? I think to do it with a complement but I don't know how to start. Should I use the Rice's theorem in this proof?

I'd assume that a TM does not accept any input if for every input $w$ it either loops or halts and rejects.
The general approach to show some language is undecidable goes as follows:

Assume that there exists a machine $M$ that recognizes the language you are given
Take some language that you know is undecidable
Create a machine $N$ that using $M$ solves the undecidable language
Since the language is undecidable, you have reached a contradiction

Do you see how being able to answer the question "is it true that machine $T$ doesn't accept any input?" would help you answering the question "does machine $T'$ accept $\epsilon$?"?
Hint: Sometimes it is useful to create a machine that ignores its input!
About semi-decidability: There's a theorem that says that a language is decidable if and only if it is semi-decidable and its complement is semi-decidable. Once you prove that your language is undecidable you can easily check that its component is semi-decidable, which immediately gives you that the language itself cannot be semi-decidable.
Regarding Rice's Theorem: Generally I'd say it is a very useful theorem, but I would recommend to solve some undecidability exercises using just pure contradictory reasoning, since it allows you to understand the concept of reducing one problem to another better, in my opinion :)


What's the difference between a reorder buffer and an instruction window? In an out-of-order processor, what is the difference between a reorder buffer and an instruction window?

Wikipedia says:
"In particular, in a conventional design, the instruction window consists of all instructions which are in the Reorder Buffer (ROB)."

Does this mean that the instruction window isn't a seperate hardware structure?

Correct.  The instruction window is not a hardware structure.  It is the set of instructions that is contained in the reorder buffer at any moment in time.  Looked at another way: the reorder buffer is a container (like a drinking cup is a container) and the instruction window is the thing the reorder buffer contains (like milk, juice or water is the thing contained in a drinking cup.)


Why do computers use binary, instead of ternary, or some other logic system? In binary a unit (bit), can store 2 separate values.

if you have ternary, then a unit can store 3 separate values.

why then don't computers use higher bases, for example in ternary you could have 3 different voltages, and even if transistors got a little bigger, wouldn't it still be more efficient?

3 different voltage levels makes building circuits harder and it is easier for little errors to occur in the signals.
Circuits need complex logic instead of the easy boolean logic which works perfectly.
Ternary is not compatible with binary that all computers use.


Deleting useless (dead) states from a finite automaton A useless state in a finite automaton is one from which no path leads to a final state, hence no (piece of a string) is recognized out of this state. Theoretically, the algorithm to determine the useful states is trivial: Let $G$ be the set of good (useful) states and let $\Omega$ be the set of all states. Initialize $G$ with all final states. Check all states $\Omega\setminus G$ for those that have a transition to a state in $G$ and add them to $G$. Repeat until nothing is added to $G$ any more.

A straightforward implementation mimicking the above, however, can be quite costly, looping over states and transitions over and over again. The number of loops checking $\Omega \setminus G$ is limited by the depth.

In a degenerate automaton containing transitions $a_0\to a_1 \to\dots\to a_n\to f$ where $f$ is a single final state and an additional transition $a_n\to u$ such that $u$ is useless, there would be around $n$ loops if you always loop over the $a_i$ in the order of $i$. But if you loop in decreasing order of $i$ shuffling found good states immediately into $G$, a single loop would suffice.

But this may lead to other degenerate situations (I am guessing).

I am looking for an algorithm to mark useful states, or remove useless states, that is not recursive (to prevent stack overflow, since I am looking at FAs with millions of states) and as efficient as possible.

Extra question: are there theoretical limits known for this algorithm?

Reverse all edges in the graph, and add a new state pointing at all accepting states. Find the set of states reachable from the new state in linear time (using BFS/DFS). These are the useful states (according to your definition).

The running time of this algorithm is linear in the number of states plus number of transitions.  This is about the best you can hope for (in terms of asymptotic worst-case running time).


How to represent sums of piecewise quadratic functions for efficient optimisation? I'm trying to implement a decision procedure for finding solutions to a scheduling problem; this involves computing the point in time which is under the most contention. Each task to be scheduled has a continuous compactly supported piecewise linear distribution of possible time allocations; the total contention at any time is then a certain sum of pairwise products of these individual piecewise linear distributions (this is the JointHeight criticality estimate, see [1]). As a consequence I am interested in the following:

Question: How can one represent sums of continuous compactly supported piecewise quadratic functions, in a way which affords efficient implementations of:

adding/removing/modifying a summand,
finding the maximum.

As D.W. points out, if a summand that is added/removed/modified spans the whole domain of support of the sum, then it seems inevitable to need to traverse the whole thing. However, when that domain is rather smaller, I'd hope to be able to efficiently update the whole sum without incurring an $\textrm{O}(\#\textrm{Tasks})$ cost; I should only need to update the control points that overlap the domain of the modified task.

After making each search decision, constraint solving takes place, resulting in the modification of the availabilities of certain tasks. My goal is to be able to efficiently update the above representation with these modifications, so that one can efficiently recompute the new time which is under maximum contention after these updates.

Now, a sum of continuous compactly supported piecewise quadratic functions is itself continuous, compactly supported and piecewise quadratic. Once one has an explicit piecewise quadratic expression, it is straightforward to compute the maximum. However I haven't figured out an implementation which would allow me to efficiently recompute the control points when adding/removing/modifying a summand.

A point of comparison is the PiecewiseExpand function from Mathematica. PiecewiseExpand can take a sum of piecewise functions and return an explicit piecewise expression, with the minimal number of control points. So I'd be interested in knowing how such a function is implemented.

[1] Beyond Contention: Extending Texture-Based Scheduling Heuristics (1997, AAAI'97/IAAI'97).
J. Christopher Beck, Andrew J. Davenport, Edward M. Sitarski, Mark S. Fox

I'd suggest storing this in a tree data structure.  The tree represents a piecewise quadratic function (namely, the sum), and each leaf of the tree represents the domain of one of the pieces.  Each internal node corresponds to a range of intervals (the union of the intervals associated with the leaves under it).  Store in each node the maximum of the function on that interval.  Also, you will store in each node some of the summands (each of which is a quadratic function on some limited domain).  The quadratic function associated with a leaf is the sum of all of the summands found on the path from the root to that leaf.

If you maintain the tree using a self-balancing binary tree data structure, the height of the tree will be $O(\log n)$, where $n$ is the number of pieces in the sum.

Now, suppose you want to update the tree by adding a quadratic function $f$ with a small domain.  First, split the two leaves $f$'s endpoints fall into, if necessary.  Then, you can express the domain of $f$ as a union of $O(\log n)$ intervals, each associated with one of the nodes of the tree.  So, update those $O(\log n)$ nodes by adding in $f$ as another summand.  Also, for each leaf whose interval is contained in the domain of $f$, compute the maximum value of the quadratic function that leaf represents.  Now propagate these maxima up the tree, until you have eventually updated the maximum at the root; this lets you compute the maximum of the sum.  If the domain of $f$ contains $m$ leaves, then the running time for this update will be $O(m + \log n)$.  So, it will be quite slow if the domain of $f$ is large, but it will be fast if the domain of $f$ is very small.

I could not figure out how to make this run in $O(\log n)$ time regardless of the size of the domain of the summand added.

I suspect there may be a simpler data structure that also achieves $O(m + \log n)$ time updates -- I suspect the machinery of self-balancing binary tree isn't needed.


Successful applications of fuzzy logic to reasoning in AI? I've done some searching and it seems that fuzzy logic is used in (electronic) controllers. I'm interested in seeing how well it fares as a tool for reasoning. Are there any robots or programs that do clever things with it?

There are plenty of papers on fuzzy logic, and applications of it.

Fuzzy logic models a piece-wise control function, and is regarded as a non-linear controller. Generally, fuzzy logic can approximate any non-linear function if you divided the state-space into enough fuzzy sets.

Because it is non-linear, it is generally useful if it is controlling a non-linear system. If it were a linear system, a linear controller would be able to control it optimally already.

It is appropriate when you want to control things like movement or position (which is often the case in robots). When a system can rotate, the rotation will create the non-linearity that fuzzy logic may try to control.

In any case, the success of fuzzy logic more often has to do with how well you select the fuzzy sets (ie. their boundaries and membership functions), and how well you tune the fuzzy logic controller. In general, any controller can be successful if appropriately tuned - though their ideal performance may differ. And the most difficult part is probably tuning it - although it is not hard to get something that works, it may be hard to get something close to optimal.

If you are thinking of using a fuzzy controller, it may be a good choice if:

your system is moderately non-linear (if it is close to linear, a linear controller is sufficient)
your system is not mathematically modelled (if it is modelled, look at LQR and perhaps gain scheduling or SDRE)
or you are unsure of the parameters of your system
and any intuition of what the controller should do would be useful when trying to select the fuzzy sets and their appropriate control responses


executing threads with no synchronization suppose Threads 1 and 2 are executing concurrently with shared integer variables A, B, and C. Thread 1 executes:A=4, B=5, C=B-A; Thread 2 executes: A=3, B=6, C=A+B;

I'm trying to find what can the possible values of C be after execution of this fragment when synchronization is not implemented.

I know if there is no synchronization then the reads see writes that occur later in the execution order and it will be counter intuitive ( execution will be happens-before consistency)

I am confused what can be the possible values of C. Can the possible values for C be 1,2,3,8,9,10 after substituting the all possible values for A & B from both thread 1 and thread 2 for C=B-A & C=A+B

Hint: Let $C = B \pm A$ be the final instruction being executed. Clearly $A \in \{3,4\}$ and $B \in \{5,6\}$, and this shows that $C \in \{1,2,3,8,9,10\}$. For the other direction, show that by carefully scheduling both threads, you can choose which of $C = B \pm A$ is executed last, and choose the value that $A$ and $B$ get prior to that instruction being executed.


How to add two numbers in IEE754 half precision format? i'm trying to understand how to add two numbers in IEE754 half precision format , i haven't found a good reference/tutorial on this , so i've tried to follow the 32 bit floating point addition procedure , but at some point i'm stucked , what i know is:

Half precision (16 bit) IEEE 754 floating point number bit configuration is:

1 bit for sign 5 bit for exponent bit and 10 bit for mantissa.

i have two numbers:

1110001000000001
0000001100001111

so i rewrited them as

1 11000 1000000001
0 00000 1100001111

before adding them i have to convert them in normalized binary scientific notation (i don't know if i'm right):

Convert the exponent of the first number in decimal: 24
Subtract bias (that is 15) so i have: 24-15 = 9 so the exponent is 9

so the mantissa is : 1.000000001 * 2^9

But i don't know how to continue , can someone please explain me the correct process for solving this , or link me a good reference/title of a book for understanding this procedure? i'm searching on Google and trying to understand on different books , but i can't clarify this procedure to myself.


Problem with implementing Brzozowski's algorithm I've been trying to implement Brzozowski's algorithm but I've just discovered that it creates suboptimal automata for a certain class of inputs, having one more state than what is really needed in the result. I can show it on a trivial automaton:

   a b           a   b           a b            a     b            a b
>0 0 1  rev  *0 0,2  -   det  >0 - 1  rev  *0   -     -    det  >0 1 2
 1 1 2  -->   1  1   0   -->   1 2 5  -->   1   -    0,4   -->   1 1 2
*2 0 2       >2  -  1,2        2 2 3        2  1,2    -          2 2 3
                              *3 4 -        3   -     2         *3 1 3
                              *4 4 1        4  3,4    -
                              *5 5 5        5   5    1,5
                                           >6 3,4,5 1,2,5

Here rev is the edge reversal part, where I'd already removed the transitions on epsilon, and det is determinization through powerset construction, creating new states as soon as it discovers them, recursively.

The problem here is this: once I add the extra state to make up for the three different start states after the first edge reversal and powerset construction, nothing ever returns to that state and thus I can't get rid of it later for being equivalent to the original start state.

Is there something wrong with the way I'm doing it? Am I missing something?

This is an excellent question!

The reverting step in Brzozowski's Algorithm does not introduce a new virtual starting state that leads to the old accepting states via $\varepsilon$-transitions. Instead it allows multiple starting states, which is no big problem, if you construct the product-automaton anyway right after the reversion.

Conceptually, it is the easiest to consider reverting and determinization as one single step. If your DEA is $M=(Q,\Sigma,\delta,q_0,F)$, then define as the reverted DEA  $ M^R=(Q^R,\Sigma,\delta^R,q_0^R,F^R)$ as follows:

$Q^R=\mathcal{P}(Q)$,
$q_0^R=F$,
$F^R=\{ P\subseteq Q \mid q_0\in P\}$,
$\delta^R(P,a):=\{ p\in Q \mid \delta(p,a)\in P\}$.

(You might want to ignore states that are not reachable.)

Brzozowski's Theorem states that $(M^R)^R$ is a minimal DEA accepting $L(M)$.

For further reading I suggest Elements of Automata Theory by Sakarovitch pages 116-117.


Applying Expectation Maximization to coin toss examples I've been self-studying the Expectation Maximization lately, and grabbed myself some simple examples in the process:

From here: There are three coins $c_0$, $c_1$ and $c_2$ with $p_0$, $p_1$ and $p_2$ the respective probability for landing on Head when tossed. Toss $c_0$. If the result is Head, toss $c_1$ three times, else toss $c_2$ three times. The observed data produced by $c_1$ and $c_2$ is like this: HHH, TTT, HHH, TTT, HHH. The hidden data is the result of $c_0$. Estimate $p_0$, $p_1$ and $p_2$.

And from here: There are two coins $c_A$ and $c_B$ with $p_A$ and $p_B$ being the respective probability for landing on Head when tossed. Each round, select one coin at random and toss it ten times; record the results. The observed data is the toss results provided by these two coins. However, we don't know which coin was selected for a particular round. Estimate $p_A$ and $p_B$.

While I can get the calculations, I can't relate the ways they are solved to the original EM theory. Specifically, during the M-Step of both examples, I don't see how they're maximizing anything. It just seems they are recalculating the parameters and somehow, the new parameters are better than the old ones. Moreover, the two E-Steps don't even look similar to each other, not to mention the original theory's E-Step.

So how exactly do these examples work?

(This answer uses the second link you gave.)

$\newcommand{\Like}{\text{L}}\newcommand{\E}{\text{E}}$Recall the definition of likelihood: $$\Like[\theta | X] = \Pr[X| \theta] = \sum_Z \Pr[X, Z | \theta]$$
where in our case $\theta = (\theta_A, \theta_B)$ are the estimators for the probability
that coins A and B respectively land heads, $X = (X_1, \dotsc, X_5)$ being the outcomes
of our experiments, each $X_i$ consisting of 10 flips, and $Z = (Z_1, \dotsc, Z_5)$
being the coin used in each experiment.

We want to find maximum likelihood estimator $\hat{\theta}$. The Expectation-Maximization
(EM) algorithm is one such method to find (at least local) $\hat{\theta}$. It works
by finding the conditional expectation, which is then used to maximize $\theta$.
The idea is that by continually finding a more likely (i.e. more probable) $\theta$
in each iteration we will continually increase $\Pr[X,Z|\theta]$ which in turn, increases
the likelihood function. There are three things that need to be done before going forward
designing an EM-based algorithm.

Construct the model
Compute Conditional Expectation under the model (E-Step)
Maximize our likelihood by updating our current estimate of $\theta$ (M-Step)

Construct the Model

Before we go further with EM we need to figure out what exactly it is we are computing.
In the E-step we are computing exactly the expected value for $\log \Pr[X,Z|\theta]$.
So what is this value, really? Observe that
$$\begin{align*}
\log \Pr[X,Z|\theta] &= \sum_{i=1}^5 \log\sum_{C\in \{A,B\}}\Pr[X_i, Z_i=C| \theta]\\
&=\sum_{i=1}^5 \log\sum_{C\in \{A,B\}} \Pr[Z_i=C | X_i, \theta] \cdot \frac{\Pr[X_i, Z_i=C| \theta]}{\Pr[Z_i=C | X_i, \theta]}\\
&\geq \sum_{i=1}^5 \sum_{C\in \{A,B\}} \Pr[Z_i=C | X_i, \theta] \cdot \log\frac{\Pr[X_i, Z_i=C| \theta]}{\Pr[Z_i=C | X_i, \theta]}.
\end{align*}$$
The reason is that we have 5 experiments to account for, and we don't know what coin
was used in each. The inequality is due to $\log$ being concave and applying Jensen's inequality. The reason we need that lower bound is that we cannot directly compute the arg max to the original equation. However we can compute it for the final lower bound.

Now what is $\Pr[Z_i=C|X_i,\theta]$? It is the probability
that we see coin $C$ given experiment $X_i$ and $\theta$. Using conditional probabilities
we have, $$\Pr[Z_i=C| X_i, \theta] = \frac{\Pr[X_i, Z_i = C|\theta]}{\Pr[X_i|\theta]}.$$

While we've made some progress, we're not done with the model just yet.
What is the probability that a given coin flipped the sequence $X_i$?
Letting $h_i = \#\text{heads in } X_i$
$$\Pr[X_i, Z_i = C| \theta] =
\frac{1}{2} \cdot \theta_C^{h_i} (1 - \theta_C)^{10 - h_i},\ \text{ for } \ C \in \{A, B\}.$$
Now $\Pr[X_i|\theta]$ is clearly just the probability under both possibilities of $Z_i=A$ or $Z_i=B$.
Since $\Pr[Z_i = A] = \Pr[Z_i = B] = 1/2$ we have,
$$\Pr[X_i|\theta] = 1/2 \cdot (\Pr[X_i |Z_i = A, \theta] + \Pr[X_i |Z_i = B, \theta]).$$

E-Step

Okay... that wasn't so fun but we can start doing some EM work now. The EM algorithm
begins by making some random guess for $\theta$. In this example we have $\theta^0 = (0.6,0.5)$.
We compute
$$\Pr[Z_1=A|X_1,\theta] = \frac{1/2 \cdot (0.6^5 \cdot 0.4^5)}{1/2 \cdot ((0.6^5 \cdot 0.4^5) + (0.5^5 \cdot 0.5^5))} \approx 0.45.$$
This value lines up with what is in the paper. Now we can compute the expected number of heads
in $X_1 = (H,T,T,T,H,H,T,H,T,H)$ from coin $A$,
$$\E[\# \text{heads by coin }A | X_1, \theta] = h_1 \cdot \Pr[Z_1=A|X_1,\theta] = 5 \cdot 0.45 \approx 2.2.$$
Doing the same thing for coin $B$ we get,
$$\E[\# \text{heads by coin }B | X_1, \theta] = h_1 \cdot \Pr[Z_1=B|X_1,\theta] = 5 \cdot 0.55 \approx 2.8.$$
We can compute the same for the number of tails by substituting $h_1$ for $10 - h_1$.
This continues for all other values of $X_i$ and $h_i$ $1 \leq i \leq 5$.
Thanks to linearity of expectation we can figure out
$$\E[\#\text{heads by coin } A|X ,\theta] = \sum_{i=1}^5 \E[\# \text{heads by coin }A | X_i, \theta]$$

M-Step

With our expected values in hand, now comes the M step where we want to maximize
$\theta$ given our expected values. This is done by simple normalization!
$$\theta_A^1 = \frac{E[\#\text{heads over } X \text{ by coin } A|X ,\theta]}{E[\#\text{heads and tails over } X \text{ by coin } A|X ,\theta]} = \frac{21.3}{21.3 + 9.6} \approx 0.71.$$
Likewise for $B$. This process begins again with the E-Step and $\theta^1$ and continues until the values
for $\theta$ converge (or to some alloweable threshold). In this example we have 10 iterations
and $\hat{\theta} = \theta^{10} = (0.8, 0.52)$. In each iteration the value of
$\Pr[X,Z|\theta]$ increases, due to the better estimate of $\theta$.

Now in this case the model was fairly simplistic. Things can get much more complicated
pretty quickly, however the EM algorithm will always converge, and will always produce
a maxmimum likelihood estimator $\hat{\theta}$. It may be a local estimator, but to
get around this we can just restart the EM process with a different initialization. We
can do this a constant amount of times and retain the best results (i.e., those with the
highest final likelihood).


Finding a specific "balls-into-bins" partition given its index in the lexicographical ordering Given numbers $n,k\in \mathbb{N}$, we consider $\mathcal P$ to be the set of all possible partitions of $n$ balls into $k$ bins.

Alternatively, $\mathcal P$ is the set of all $k$-ary vectors in $\{0,1,\ldots,n\}^k$ such that the sum of the entries is exactly $n$.

For example, if $n=4$ and $k=3$, we get:
$$\mathcal P =$$$$ \{<0,0,4>,<0,1,3>,<0,2,2>,<0,3,1>,<0,4,0>,<1,0,3>,<1,1,2>,<1,2,1>,<1,3,0>,<2,0,2>,<2,1,1>,<2,2,0>,<3,0,1>,<3,1,0>,<4,0,0>\}$$

Simple combinatorics (Stars and bars) tells us that $|\mathcal {P}| =$$n+k-1 \choose n$.

Now the goal would be to compute $p\in \mathcal P$ given it's index in a lexicographical ordering on $\mathcal P$ (alternatively, consider each vector as a number in base $n+1$ and order $\mathcal P$ based on the number).

In the example above $\mathcal P$ is ordered, so for example, given the input $3$, we'd like to output
$<0,2,2>$.

So the question is:

  How to we compute $\mathcal P(i)$ efficiently (without enumerating all $\leq i$ partitions)?

The procedure of generating the $i$-th structure according to some ordering of a combinatorial class is called unranking.

In your specific case an unranking algorithm for $P_{n,k}(i)$ can be created as follows:

Define $s_m := \sum_{j=0}^m |P_{n-j,k-1}|$, the number of vectors that start with $m$ or a smaller number, $s_{-1}=0$.

If $k=1$, the vector contains the single entry $n$.
Otherwise,

The first entry in the vector is $m$ so that $s_{m-1} < i \le s_m$.
The remaining vector is $P_{n-m,k-1}(i-s_{m-1})$.


Is the weighted transitive reduction problem NP-hard? The transitive reduction problem is to find the graph with the smallest number of edges such that $G^t = (V,E^t)$ has the same reachability as $G=(V,E)$.

When $E^t \subseteq E$ it is NP-complete. When $E^t \subseteq V\times V$ but not necessarily of $E$, this problem is polynomial time solvable. I am wondering about the edge-weighted version without the subset requirement.

My initial feeling was that with weights, the problem is very similar to TSP. The greedy approach seems to be invalid when adding weights. But several articles (http://bioinformatics.oxfordjournals.org/content/26/17/2160.short for instance) seems to imply that the problem is solvable in polynomial time.

If it was easy, then you could just add arbitrarily large edge weights to each edge not in the original edge set and keep the weights at unity for the others. Then you would have a polynomial time algorithm for the subset constrained problem.

So this should mean it HAS to be NP, right?

edit: Are there immidiate examples that come to mind of problems whose unweighted version is easy, but gets hard when weights are added?

edit: by edge-weighted, I mean we are interested in finding the graph with the smallest total edge cost

Consider $G=(V,E)$. Let $w_{ij} = 1$ if $e_{ij} \in E$ and let $w_{ij} \gg 1$ if $e_{ij} \notin E$. This choice of weights correspond exactly to the constraint $E' \subseteq E$. Thus, if the weighted transitive reduction is polynomial time solvable, then so is the minimum equivalent graph problem.


How polynomial interpolation of polynomial multiplication algorithm works? I'm trying to apply the following algorithm from DPV's textbook to an example to see how it works. First, the algorithm is as following:

Algorithm [DPV, p. 60]
Input: Coefficients of two polynomials. A(x) and B(x), of degree d.
Output: Their product $C = A . B$

Selection: Pick some points $x_0, x_1, x_2, ..., x_{n-1}$ where $n\geq 2d+1$
Evaluation: Compute $A(x_0), A(x_1), ...., A(x_{n-1})$ and $B(x_0), B(x_1), ...., B(x_{n-1})$
Multiplication: Compute $C(x_k)=A(x_k) \times B(x_k)$ for all $k=0, 1, ..., n-1$
Interpolation: Recover $C(x) = c_0 + c_1 x + c_2 x^2 + .... + c_{2d} x^{2d}$

Now, I took an example $A(x) = 3x^2 -4x + 1$ and $B(x) = x-2$. The output should be $C(x) = 3x^3 - 10 x^2 + 9 x -2$. Now, the algorithm first choose an arbitrary points, so I will choose the following: $x_0 = 1, x_1 = 3, x_2=6,$ and $x_3 = 9$. Now, we evaluate the A(x_i) and B(x_i) for $i=0, 1, 2$ and $3$. Thus, $A(x_0) = 0, A(x_1) = 16, A(x_2) = 85, A(x_3)=208, B(x_0) = -1, B(x_1) = -2, B(x_2) = -5,$ and $B(x_3)=-8$. Thus, we compute $C(x_i)$ for $i=0, 1, 2,$ and $3$. So, we get $C(x_0) = 0, C(x_1) = -32, C(x_2)=-425,$ and $C(x_3) = -1664$.
Now, I have $x_0=1, x_1=3, x_2=6,$ and $x_3=9$ and the corresponding $C(x_0) = 0, C(x_1) = -32, C(x_2) = -425,$ and $C(x_3)=-1664$. This I will apply the polynomial interpolation to get the output. I used this page to compute the coefficients of C(x). So, I got the output as following: $-3x^3 + 7x^2 - 5x + 1$ but it should be this one: $C(x) = 3x^3 - 10 x^2 + 9 x -2$. So, where is the problem? Is it because finding interpolation cannot be in exact so the coefficient is an approximation to the exact one.


What will a given CPU architecture do in the event that we were to invert all of the instruction bits to a given instruction? Given an arbitrary CPU - Architecture and its instruction set... What would be the outcome of the given inverted instruction within that Architect?
For simplicity, let's use an 8-bit CPU architecture that has an 8-bit Bus design where that bus is used for both addressing and data transfer operations. A single instruction or micro instruction will act on an 8-bit string of binary digits per clock cycle. Each clock cycle may consist of 3,4,or 5 micro instructions before incrementing the instruction register for the next full instruction to be processed. These would account for the Fetch, Decode, and Execute phases of a single CPU clock cycle instruction.
The following is a mock-up only to demonstrate or illustrate my curiosity and concern while designing the layout of a given ISA(Instruction Set Architecture)...
Here we have the range of possible instructions from [0000 0000, 1111 1111] which are all of the possible permutations that this arbitrary CPU-Architecture's Machine Language can support. We could use Ben Eater's 8-bit Bread Board CPU and its ISA as an example... You can find that here along with other useful videos from his YouTube channel: Comparing C to Machine Language, and Programming 8-Bit Computer. With his given implementation, the first 4 bits are used to define the instruction and the second 4 bits are used for data {either memory address or immediate value}...
Now to my question: Given a specific instruction word and its accompanying data field, what would be the resulting outcome if we invert all of the instruction bits?
First, I know that this would be independent on each Architecture's ISA design implementation... Second, I'm just curious to what the ramifications would be when designing your own specifications in that, would it be possible to carefully design and layout your bit fields per instruction in a manner that you could have a special invert operation, that would automatically invert a given instruction where that inversion would produce the opposite or inverse effect of the given incoming instruction? Now, the inversion won't necessarily happen to the entire instruction string that includes all 8-bits, but only to the bit-fields that pertain to the instruction type while preserving the data field... For example:

If we have an Add instruction, the invert op would turn this to a Sub...
If we have an And instruction, the invert op would turn this to an Or instruction...
If we have either a Bit Shift Logical Left or Bit Shift Arithmetic Left, the invert op
would respectively turn these into Bit Shift Logical/Arithmetic Right operations...
And so on...

Would such a design be possible to have perfect symmetry within it's ISA?
-Note- I don't know if this is the correct StackExchange site for this question... if it is not please don't down vote it due to being irrelevant and be kind enough to point me in the right direction letting me know where the appropriate site for this question would be.

If you are decoding instructions using logic based on individual bits in the opcode, this "inversion' scheme is probably counter productive.  If the opcodes are decoded using a simple table lookup of the "value" of the opcode, then the actual pattern of the opcode is just arbitrary and the inversion scheme is just as valid as one based on the alphabetic order of the mnemonics.
For stack based machine, variable length opcodes could be more valuable, shorter opcodes for push, pop, and any immediate value instructions to give more space for address or data bits.
Self-modifying code has been out of fashion for decades, so being able to flip the meaning by inverting the bits would seem to have no utility.


Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size There is a complete graph $G$ with $n$ vertices and each edge has a distinct weight.

Is there an efficient (not necessarily optimal) algorithm to select $k$ vertices from the graph $G$, such that the total cost of the min-spanning tree of the selected $k$ vertices will be highest?

In my case, $n$ is around 1000, and $k$ around 100.

Your problem is NP-complete, so you should not expect to find any efficient algorithm for it.

If we could solve your problem efficiently, we could solve the $k$-clique problem, too.  Let $G$ be an unweighted, undirected graph; we are curious whether it has a $k$-clique.  Translate it into an instance of your problem by making each edge have weight 2, and then for each pair of vertices $u,v$ that are not connected by an edge, add a new edge of weight 1.  Now ask for the solution to your problem.  Notice that there exists a way to select $k$ vertices such that the corresponding spanning tree has cost $2k$, if and only if $G$ has a $k$-clique (if $G$ does not have a $k$-clique, no matter how you select $k$ vertices, the cost of the spanning tree will always be $\le 2k-1$).

Since the $k$-clique problem is NP-complete, your problem is NP-complete, too.  Therefore, we cannot expect an efficient solution for your problem, when $k$ is arbitrary.


Complexity of CFG grammar for a regular language I know that each regular language can be generated by a CFG.
This makes, in one sense at least: context-free languages more general than regular languages.

Are there known results about the 'complexity' of regular languages in the CFG context? For example, is it true that every regular language can be generated by an unambiguous LL(1) grammar?  Or is something similar true?

The general question above comes from the attempts I made to build a 'simple' grammar generating $L=\{(ab)^i|(ba)^i : i\geq 0\}$.
None of the grammars I could build were 'simple'.

A regular grammar is context-free. So regular languages are
context-free.

Every regular language has a right regular grammar, which is simply derived from a finaite state automaton for that language.

Every regular language can be recognized by a deterministic finite state au tomaton. From that deterministic FSA you can construct a right regular grammar
which is LL(1) since you can decide what to do for
parsing by simply looking at the terminal on the rules applicable at any time. There always is only one such rule. Actually you do
not even need the pushdown, and use the non-terminal for the states.
(this is a bit informal, but it is so simple being formal seems
silly).

The key part is producing the deterministic FSA.

So, yes, every regular language can be generated by a LL(1) grammar.

A LL(1) grammar is always unambiguous, as it allows constructing a
deterministic push-down automaton. So it is unnecessary to specify
that it is unambiguous.

As for your language, it seems strangely defined, and I wonder whether
you copied that correctly. What is the "$+$" supposed to mean ?


How can P=NP relate to creativity and proof automation, as said by Scott Aaronson? I read several times of Scott Aaronson saying that P=NP implies that human creativity is boring and something like that, and that P=NP has something to do with proof automation. I don't get his argument, despite having studied basic complexity theory. What is he talking about?

There is a relatively often cited quote

  "If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett."

However, Scott has later distanced from it:

  Given how many confusions and weird misinterpretations it’s spawned, I, Scott Aaronson, hereby formally disown my statement about how “everyone who could appreciate a symphony would be Mozart” if P=NP.

(source)


How can I do an optimization problem that involves finding a sequence? The problem I am trying to solve is to find the fastest way to produce an total amount of something. There are several different producers that each have a different production and cost (based on the number of the item that is already owned) which can be purchased during production.

For example, assume that the goal is to produce 1000 units total (including the amount spent on buying new producers), and the three producers that can be bought $A$, $B$, and $C$, have productions and base costs of $1$ per second and $20$, $7$ per second and $50$, and $14$ per second and $100$, respectively. Buying a producer multiples the price of the next producer of the same type by 1.1 (so, for example, buying an $A$ for the base price of 20 means the next $A$ will cost $1.1 \cdot 20 = 22$, and the next $1.1 \cdot 22 = 24.2$, et cetera). When a producer is bought, the price of the produced is subtracted from the current units produced, but not the total production (so if you have 30 units, and you buy an A, you now have 10 units left). Selling a producer returns half of the units used to purchase it, and reduces the cost by 1.1 times (so if the cost was at 24.2, it would go down to 22). By starting with 1 $A$, what is shortest amount of time to produce 1000 units and in what order should you purchase producers?

The shortest time is 68 seconds, buying producers in the following order:
A,B,B,B,C,C,C,C.

My first solution was simply to try all the different sequences, then determine the one that will be the fastest after $n$ purchases, but, naturally, this was very slow.
My second solution was to try a greedy search where I just look for the best solution in terms of time at every step.
My third solution was to try a search where I used the increased in production as the score for each sequence, and backtrack to earlier solutions if any of them had better scores.

Are there any other problems or generalizations I can make to find an optimal (or near optimal solution faster)?

Graph search

I recommend you formulate your problem as a graph search problem.  Each vertex represents a state of the system.  The state of the system lists the number of units you currently have and the number of each producer you currently have (e.g., "20 units, 1 A, 3 B's, and 0 C's").  You add an edge $s \to s'$ if you can get from state $s$ to state $s'$ in a single step.  The start state is "0 units,  0 A's, 0 B's, 0 C's".  The goal states are all states with 1000 units.

You can now use breadth-first search to find the shortest path from the start state to a goal state.

For better performance, use A*.  It's not too hard to construct a consistent and admissible heuristic that always underestimates the distance to the goal state.

As long as the number of producers is not too large, I expect this to be pretty efficient.

Greedy algorithm

It might be possible to build a greedy algorithm for your problem.

Consider a simplified variant where you are not allowed to sell producers you own, and where the number of units you have is allowed to go negative (you can still buy a producer even if it would put you in debt).  This has an efficient greedy solution.  In particular, consider the decision problem variant: given $t$, determine whether there exists a sequence that gets you to the goal within at most $t$ seconds.  This can be answered greedily.

Consider our first action.  We have $k$ options for actions: "buy $P_1$", "buy $P_2$", ..., or "buy $P_k$".  Note that it's always advantageous to make all your producer-buys as early as possible; there's no point in waiting.  Assume that for producer $P_i$ we have base cost $b_i$ and production $p_i$.  If we buy $P_i$, the net profit from that purchase (over the entire $t$-second time window) is $(t-1) p_i - b_i$.  So, for your first action, choose the action with largest net profit.  Now, for your second action, we have the same problem, except that $t$ is one smaller, so we can continue iteratively.  After $t$ seconds, we check whether the resulting sequence has reached a goal state.

[You can also consider a kind of exchange operation, where you compare "buy $P_i$ then $P_j$" to "buy $P_j$ then $P_i$".  You'll find that the decision rule for making that choice is as follows.  Associate to the action "buy $P_i$" a 'profit foregone if we defer buying $P_i$' value of $0.1 b_i + p_i$.  Determine which of $P_i$ or $P_j$ has lower 'profit foregone', and then choose to do that one first.]

You could check whether you can generalize this analysis to the case where you're allowed to sell producers and where you're not allowed to let the number of units owned go negative.  It looks a little tedious, so I'll leave the case analysis to you.


Count number of the ways to fill a N-lengthed binary string From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more than $K$.

For $N \le 2\times 10^6$, my approach is to using DP. dp[N][K][2] is the number of ways to fill string of length $N$ with the current $1$'s consecutive sequence length is $K$ and last parameter is to tell whether the current string contains the $1$'s consective sequence of length $K$.

This would work if N is small enough but the constraints of this problem is : $1 \le N \le 10^{10}, 0 \le K \le 50$.

The approach I need is obviously Matrix Exponentiation so I can solve it in $O(\log N \times ?)$. Storing every possible binary strings of length K is not possible ($2^M$). Can anyone provide the solution of the problem? Or at least some hints

Construct a DFA for your language (without the length $N$ restriction). It should contain $S = O(K)$ states. Consider the corresponding $S \times S$ matrix $A$, in which $A(s,t)$ is the number of characters that cause the DFA to move from state $s$ to state $t$. Let $x$ be the characteristic vector of the initial state, and let $y$ be the characteristic vector of the accepting states. Then the number of words of length $N$ is $xA^Ny$. You can compute $A^N$ quickly using matrix exponentiation.


Do we include Transmission delay in Round trip time? Is RTT = $2*T_{Propagation delay}$ only. Or we include Transmission delay to send packets as well. Some examples include Transmission delay some not. I'm confused. Can anyone help.

Suppose you have two computers (A and B) both connected to a switch with cut-through forwarding. When you are interested about RTT between computer A and computer B, you'll omit transmission delay, because the switch transmits the frame to B as it arrives from A, so transmission delay is not significant. Now, suppose that our switch uses store-forward, in this case, when the frame arrives, the switch will first store it completely, and then sends it to B, so we have to deal with transmission delay.


Disk scheduling and process scheduling Whats the diffrence between Disk scheduling and process scheduling? I mean i know the roles of disks and processes, but it seems to me they both have the same aim. to reduce monopolies, they even both share similar algorithms like first come first serve. Am i right?

Disk scheduling has an additional physical constraint.  Accelerating and moving the disk head takes times in the msec range.  Wikipedia says average seek times are around 10 msec (to move halfway across the radius of the disk) and the time to move just to the adjacent track is about .5 msec.  Thus an algorithm like FIFO might be reasonable for process scheduling because it would deliver about the same compute throughput as any other scheduling algorithm, but FIFO would be a disaster for disk scheduling.

You are not correct that the primary objective of either disk scheduling or process scheduling is "to reduce monopolies".  In real time process scheduling, for example, the primary objective is to make sure that processes with lower priority never run when there is a higher priority process available.

There are things that are worse than monopolies on workstations too.  If you are time sharing between some number of processes that are consuming so much VM that you are thrashing then no-one is getting any service, and you are better off being less fair (swapping out processes until the ones that are left can get some CPU service and hopefully finish.)

Finally, most real operating systems try to give priority to "interactive" processes.  But you can't figure out which processes are interactive until you've seen them running.  So you use an algorithm like Corbato's Multi-level feedback queue.

Edit: I forgot to mention  that disk scheduling algorithms are often variants of the elevator scheduling algorithm.  This moves the disk head in one direction, doing requests in the order that they lie on the disk.  The objective in the elevator algorithm is to maximize throughput while putting a bound on unfairness.


Proving the equivalence of two definitions of NFA acceptance Recall that an NFA $N = (Q,\Sigma,\delta,S,F)$ accepts $w=w_1w_2\ldots w_n$, where $w_i \in \Sigma$, if one of the following holds:

  (a) $\hat\delta(S,w) \cap F \neq \emptyset$, where $\hat\delta\colon P(Q) \times \Sigma^* \to P(Q)$ is given by
  $$
\hat\delta(Q',w) =
\begin{cases}
Q' & w = \epsilon \\
\bigcup_{q \in \hat\delta(q',w_1\ldots w_{n-1})} \delta(q,w_n) & |w| = n > 0
\end{cases}
$$

  (b) $\exists r_0,\ldots,r_n$, where $r_i \in Q$, such that:

  $r_0 = q_0$
  $r_n \in F$
  $r_{i+1} \in \delta(r_i,w_{i+1})$

  Show that (a) $\leftrightarrow$ (b)

I think I have proven from (b) to (a) but I'm not sure, and I seem to have no idea where to start the other way around. This is part of the first exercise in the computational models course I'm taking and I would really appreciate the help.

Just a hint:

First, generalize the problem: show that, for any $q\in Q$ and any word $w$, $q \in\hat\delta(S,w)$ if and only if $\exists r_0,...,r_{|w|}\in Q$ such that $r_0\in S$, $r_{|w|}=q$, and $r_{i+1}\in\delta(r_i, w_{i+1})$.
Second, show this statement by induction on the length $|w|$ of $w$. This is trivial for the base case, and should be easy for the inductive case, just apply the induction hypothesis and the definition of $\hat\delta$.
Finally, show that your equivalence follows from the general statement: apply it for any $q\in F$.


Modified Bellman Ford to find minmum cost cycle in O(E²V) time? I'm thinking about how you can modify Bellman Ford a bit to calculate the minimum weight cycle in an undirected graph with positive weights. Note that the constraint is that the algorithm must run in $O(VE^2)$ times, and Bellman Ford runs $O(VE)$ time so we are looking at a modification that runs $O(E)$

My approach is first make a directed graph by doubling the edges in both directions, then run Bellman Ford to come up with the shortest path, then compute the strongly connected components in this graph. After you have a tree of strongly connected components, calculate the weights around the perimeter of the SCC and then compare the weights. But I'm not sure how you could calculate SCC using Bellman Ford and this algorithm is going to take too long.

Does anyone see an obvious solution?

Some hints for you, so you can solve your own exercise:

If the graph has a negative-weight cycle, what is the proper answer?  Can you detect this situation?
If the minimum-weight cycle has positive weight (strictly greater than zero), how could you find it?  If you knew the distance between every pair of vertices, could you use that to help you find the minimum-weight cycle in this case?  Does that suggest an algorithm that could handle this case?
If the minimum-weight cycle has zero weight, can you detect this fact?  What could you do in this situation?


Why does induction with big-O lead to paradoxes? For example, say I want to analyze $T(n)=3T(\lfloor n/3 \rfloor )+2n$ for $n>2$, and $T(n)=1$ otherwise. This is clearly $O(n\log n)$; however it seems that with induction you can prove it is $O(n)$:

Base case: $T(1)$ is $O(1)$, $T(2)$ is $O(2)$

Inductive step: $T(n) = 3\times O(n/3) + 2n \in O(n)$

Where does this go wrong? Why can I do this? Induction clearly is a valid technique, but what subtlety of $O$ causes me to be able to prove a wrong bound?

You have to carry around the big-O constant. Suppose that we are trying to prove that $T(n) \leq Cn$. In the inductive step, we have
$$ T(n) \leq 3C\lfloor n/3 \rfloor + 2n \leq (C+2)n. $$
So we are not able to maintain the constant $C$. Let's have another go, with $T(n) \leq C_nn$. The argument above shows that we can put $C_n = C_{\lfloor n/3 \rfloor} + 2$, and so $C_n = O(\log n)$ works, and we get the correct asymptotics $O(n\log n)$. (To know that this is tight, we would also need a lower bound, proved in much the same way, with some minor technicalities stemming from the floor.)


Remove duplicates from dictionary in a safe and clever way I have a dictionary that has keys and multiple values per key. Same value can be assigned to multiple keys.

For the sake of simplicity, the keys are ints and the values are strings,
so that it would look like in C#:

Dictionary<int,string[]>

As an example the dictionary is filled as follows:

{ 1, ["A","B"] },
{ 2, ["A"] }

I now have to remove duplicate values, under the condition that each key keeps at least one value (if at all possible).

So we cannot say 1 gets A, because 2 will then have no associated value anymore.

The result for the example should be:

{ 1, ["B"] },
{ 2, ["A"] }

Another example with result:

{ 1, ["A", "B"] },
{ 2, ["C", "D"] }
-->
{ 1, ["A", "B"] },
{ 2, ["C", "D"] }

One key cannot contains multiples times the same value, so the following scenario is not considered, it cannot happen:

{ 1, ["B"] },
{ 2, ["A", "A"] }

What I tried so far, but where I am not sure if I captured all edge cases or if there are more efficient or more logic ways:

If a key has only one value assigned, this is fixed. The value is removed from all other keys and the key value pair is removed from the iterating list and stored elsewhere

1.1 If after that removal one key does not have any values associated, the algorithm failed, it is not possible.

1.2 Repeat 1. until no key with only a single value is left.
Search for values that are only assigned to one key. The key value pair is removed from the iterating list and stored elsewhere
Repeat 1. to 2. until 2. does not find a result
No we have a list with only n to n relations. All keys have at least 2 values and each value is at least assigned to 2 keys.
Now we randomly remove one value from a single key.
Repeat 1. to 5. until nothing changes anymore.

Is there a standard algorithm for this requirement? I am still not sure if I considered all edge cases.

Your question is very well written. Let me make one requirement even clearer. "Remove duplicate values" means that one value can be assigned to at most one key in the end, as explained in the given examples.

Your algorithm might return the wrong result. For example, consider the following dictionary.

{ 1, ["A", "B"] }
{ 2, ["A", "B"] },
{ 3, ["C", "A", "B"] },
{ 4, ["D", "A", "B"] }
{ 5, ["C", "D", "E", "F"] }
{ 6, ["C", "D", "E", "F"] },

Your algorithm might proceed to remove value "C" from key 3 followed by removing value "D" from key 4. You can check that each keys still has at least 2 values and each value is still at least assigned to 2 keys. However, you can see that key 1, 2, 3 and 4 have two values in total, "A" and "B". So it is not possible to assign each of those four keys with a different value. However, there is an assignment that is possible in the beginning, i.e., { 1, ["A"] }, { 2, ["B"] }, { 3, ["C"] }, { 4, ["D"] }, { 5, ["E"] } and { 6, ["F"] }.

The problem you are trying to solve is fundamentally finding the maximal matching in unweighted bipartite graphs. You can find various algorithms given in that Wikipedia page such as Ford–Fulkerson algorithm and Hopcroft–Karp algorithm. I will let you figure out how to adjust or extend those algorithms a bit to solve your task of "removing duplicates from dictionary".


Are regular languages and their regular expressions part of computer science? I am trying to understand if regular languages and their regular expressions are concepts of computer science in general and if these are discovered, or invented, by computer scientists, in particular.

In math discourse there was always the question like "Are mathematics discovered or invented?".
I am quite sure regel-regex is not a mathematical theory but a linguistics theory (even though it was first theorized by a mathematician - Stephen Cole Kleene).

Is regex part of computer science and if so, is it generally accepted as "discovered" or as "invented", and what could be one example of what's being further researched in regards to matching information on a computer document?

There are several things that are all called regular expressions. The answer to your question is different depending upon which thing you want to talk about.

The three relevant distinctions for this question in my opinion are as follows:

First

The notion of regular languages and related things like recursive enumerability.

Individual regular languages are isomorphic, (i.e. able to be losslessly transformed to and from,) to deterministic finite automata and reducing something to a regular language demonstrate results about that thing's computablity,
so I would argue it is part of computing science.

If linguistics folks find the notion or regular languages useful, however, then we can share it. Human languages are (generally?) not regular languages but something more complex, so I would be surprised if that was the case.

I think most interested people would give the same answer to whether regular languages are invented or discovered as they would about mathematics.

Second

The particular notation for describing regular languages, in the formal literature, developed by Kleene and others.

This is clearly invented. There's no particular reason we have to have used * and + in particular to represent those ideas. If you want to assign this notation to one or more fields, I would argue it belongs to any field that publishes papers using it.

Third

Computer programs which take as input an expression in a language and produce an automata or something resembling one and that result can then be used to perform operations on a different input including search and replace.

The languages these programs define which usually contains some form of the Kleene Star and Kleene Plus, along with several other more complicated but useful constructions, which are generally absent from formal regular language literature to my knowledge. Backreferences would be one example of this. These programs are invented, as are their particular sets of notations. They are also instances of computer engineering rather than computing science per se. Although of course they are building on at least a certain amount of computing science results, and computing science results can be stated about these programs. For example, it is possible to construct regular expressions of this sort that produce exponential running times, and subsets of those notations can be defined where that is impossible.


Reduction from $A$ to $B$ as execution of Turing machines As explained in answers to this question, reduction from $A \le B$ can be represented in the following way.

But in this example:

from here
At least as I understand it:
The reduction is from $\overline{HP}$ to $L_2$, so $A$ is $\overline{HP}$ and $B$ is $L_2$.
But it's implemented in the way that $M'$ is TM of $L_2$ and $M$ is TM of $\overline{HP}$, and $M'$ execute $M$ (I mean $L_2$ is the external and $\overline{HP}$ is the internal).
Where am I wrong?

What confuses you is that the words in the languages are encodings of machines that simulate runs of other machines, but at the end of the day, these are just words. Specifically,
given input $x = \langle M, x\rangle$ for the reduction, the reduction itself does not simulate the run of $M$ on $x$, the reduction only outputs $f(x) = \langle M'\rangle$ which is an encoding of a machine. The machine $M'$, by definition, simulates the run of $M$ on $x$, given any input $w$ for $M'$. You can think of this reduction as a python code $f$ that is given as input another python code $M$ and an input $x$ for $M$. Then, $f$ halts and outputs a python code $M'$. Note that $M'$ may never halt on any input $w$, but this is okay as $f$ never runs $M'$.
Please note that the first attached figure is irrelevant here as it does not describe how the reduction operates (how $M_f$ computes $f(x)$, given $x$), it only describes how you can define a machine $M_A$ for $\overline{HP}$ assuming that you already have: 1) a machine $M_B$ for $L_2$, and 2) a machine $M_f$ that computes the reduction $f$.


What class of problems does this problem belong to I recently took a test and I had a particularly difficult time with one problem.  I would like to know more about this problem: what general class of problems does this problem belong to, what are some good resources to learn more about this class of problems, how should I have recognized the problem for what it was?

So here is the problem, distilled down to its essential components.

You have a task you are trying to accomplish.  There are n different ways to to accomplish that task but each approach has a cost and probability of success associated with it.  The problem is to figure out how to order your attempts at the task so that the average cost is minimized.

There is a small twist, if all but your last attempt has failed then you are guaranteed success on your last attempt regardless of the probability of success associated with it.

So here is a concrete example.  The following list of tuples represents three ways to complete a task.  The first value is the cost and the second value is the probability of success:

[(10,0.5),(8,0.25),(5,0.2)]

One possible order would be [0,1,2] (each value is the index of an attempt in the above list).

That has an average cost of:

0.5*10 + (1-0.5)*0.25*(10+8) + (1-0.5)(1-0.25)(10+8+5) = 8.975

But the optimal order is [0,2,1]:

0.5*10 + (1-0.5)*0.2*(10+5) + (1-0.5)(1-0.2)(10+8+5) = 8.8

The obvious way to solve this problem is to simply try every possible order but that has a runtime of O(n!).  What you are supposed to know is that by dividing the cost by the probability and sorting the list using that value as the key you will get the optimal order.

I did figure that out eventually but it was not obvious to me at all, I went down a long and winding route and hit many dead ends before I arrived at that solution.  So what was the trick here to quickly come to this conclusion?

The algorithm that you have found is an example of a "greedy algorithm". When trying to find an algorithm for a problem there is a small bag of standard tricks that you can use but these are quite limited and for most problems, there's no easy solution: you have to "go down the long and winding route".

The trick here was to recognize that this problem has a property known as "optimal substructure": a solution to the problem consists of making some top-level choice, and then solving a smaller subproblem. The optimal substructure property states that any optimal solution consists of a top-level choice, and then an optimal solution to the subproblem (the way to solve the subproblem does not depend on previous choices).

If your problem has optimal substructure you can try solving it with dynamic programming (but that does not give a polynomial algorithm here because the problem does not have sufficient overlap between subproblems). Another option is using a greedy strategy, which happens to work here. The greedy strategy is (simply put): define some criterion by which to pick the locally "best" top-level choice and do not consider the possibility of making any choice.

In this case, the "right" criterion apparently is the expected cost of accomplishing that task by using that method. This intuitively makes sense (the option with highest success/cost ratio should be the one you try first) but to show that this choice indeed results in an optimal order, you have to show that the problem, coupled with this criterion, satisfies the "greedy choice property": any solution that does not use the "best" choice, can be modified to a solution that uses the "best" choice and whose objective value is at least as good or better as the objective of the solution that does not use the "best" choice. You can usually show this by some sort of exchange argument ("suppose the solution does not start with the best success/cost ratio, consider what happens if we swap the first step in the solution with the best success/cost ratio one, then the objective can only improve,...")


How to find the alphabetically min and max of substrings that begin with [a, b, c, d, e] and end with [h, i, j, k, l, n] I was asked this question today:
given a very long string x, which contains only lower case alphabets. A valid substring can only started with [a, b, c, d, e] and ends with [h, i, j, k, l, n]
IF we sort the valid substrings alphabetically, what will be the first one and what will be the last one?
If we do need to sort all the substrings, then we might need a suffix tree or suffix array. However, here we do not need to sort --- we don't care all the substrings except the first and last one. So I am wondering if there is any more efficient solution than using suffix array.
Thanks

Find the last occurence of any h, i, j, k, l, n. If none is found, there is no solution. If the last one is found at position r, then the string we are looking for must start at position before r.
Then you start from the left looking for the first letter among a, b, c, d, e. If you don't find one before position r then there is no solution. Otherwise call this index l; the first string in the alphabet might start at index l.
Look further for more characters starting with a to e. If you find one at position l', you then find the first difference between the string starting at l and l', up to and including position r. If there is a different character, and the first character in the string starting at l' is earlier in the alphabet, replace l with l'.
Finally, the first string in the alphabet is the one starting at position l, and up to and including the first letter in 'h' to 'n'.


Normal form Lambda calculus expression I need a little help with a lambda calculus reduction to normal form:
$$(\lambda xxxx.xx)(\lambda x.xx)(\lambda x.x)y((\lambda x.x)x)$$
It should be solved like this:
$$xx(\lambda x.x)y((\lambda x.x)x)$$
and then:
$$xx(\lambda x.x)y(x)$$

This is the result of any of the lambda calculators that you can find online.

My question is: why can't I go on with reductions and make also $(\lambda x.x)y$ so the resulting expression would be $xxy(x)$?

Can you give me a complete answer, with theory of lambda calculus rules/proofs?

I really want to understand this exercise, any help would be appreciated.

As pointed out in the comments, the first term seems broken - too many $x$es.

The key is that function application is not associative (both in the lambda calculus and outside it). In particular, $a(bc)$ is different from $(ab)c$. In the first term, we apply $b$ to $c$ and then $a$ to the result. In the second term, we apply $a$ to $b$ and then apply the result on $c$.

In your case $xx(\lambda x.x)yx$ is parenthesised as $(((xx)(\lambda x.x))y)x$, because function application associates to the left. This means that there is no redex there, it can't be reduced further.

Your mistake was in that you added parentheses like $xx((\lambda x.x)y)x$, which is a completely different term.


Most probable value of randomized procedure output Let $n, m \in \mathbb{N}^{+}$. Let $\mathsf{rand}$ be a procedure which returns some random $x \in \{0, 1, \ldots, m - 1\}$ with a flat probability distribution. I have the following procedure:

W := an array of length m full of 0s
for i in 0, 1, ..., n - 1; do
    (x, y) := (rand(), rand())
    W[y] := max(W[x], W[y]) + 1
x := 0
for i in 0, 1, ..., m - 1; do
    if W[i] > x; do
         x := W[i]
return x

My question is: what is the most-probable value of $x$? I'm not even sure where to begin with the analysis here, due to the probabilities involved.

The question sounds a bit difficult. I was able to calculate the expectation of $x$ when $m = 2$. The most probable value of $x$ should be very close to its expectation. Perhaps this will give you some ideas.

The idea is to construct an infinite Markov chain whose states are $|W[0]-W[1]|$, and whose transitions are labeled by whether $\max(W(0),W(1))$ increases or not. Here are the transitions (explained below):

At state 0, we transition to state 1 w.p. 1, increasing the maximum.
At state $n > 0$, we transition to state $n-1$ w.p. 1/4; to state $n+1$ w.p. 1/2, increasing the maximum; and to state 1 w.p. 1/4, increasing the maximum.

The first case is trivial.
For the second case, consider the array $a+n,a$. There are four options, each occurring w.p. 1/4:

When $x=y=0$, the new array is $a+n+1,a$ (the maximum increases).
When $x=y=1$, the new array is $a+n,a+1$ (the maximum doesn't increase).
When $x=0,y=1$, the new array is $a+n,a+n+1$ (the maximum increases).
When $x=1,y=0$, the new array is $a+n+1,a$ (the maximum increases).

The next step is to calculate the stationary probability (it is easy to check that the chain is ergodic). Denoting it by $p_n$, we have

$p_0 = \frac{p_1}{4}$.
$p_1 = p_0 + \frac{p_1 + \cdots}{4} + \frac{p_2}{4} = p_0 + \frac{1-p_0}{4} + \frac{p_2}{4}$.
$p_n = \frac{p_{n-1}}{2} + \frac{p_{n+1}}{4}$ for $n \geq 2$.

The sequence $p_1,p_2,\ldots$ satisfies the recurrence
$$
p_n = 4p_{n-1} - 2p_{n-2}.
$$
The roots of $x^2 - 4x + 2$ are $2 \pm \sqrt{2}$, and since the series $\sum_{n \geq 1} p_n$ converges, we must have $p_n = C (2-\sqrt{2})^n$. In particular, $p_2 = (2-\sqrt{2})p_1$. Substituting this in the formulas for $p_0,p_1$, we can calculate
$$
p_0 = \frac{4\sqrt{2}-5}{7}, \qquad
p_1 = \frac{16\sqrt{2}-20}{7}.
$$
Notice now that when at state $n>0$, the maximum increases with probability 3/4, and when at state 0, it always increases. Hence the probability that it increases at the stationarity is
$$
\frac{3}{4} + \frac{p_0}{4} = \frac{4+\sqrt{2}}{7}.
$$
Denoting by $X_n$ the expected value of $x$ when $m=2$ and $n$ is given, we deduce that
$$
\lim_{n\to\infty} \frac{\mathbb{E}[X_n]}{n} = \frac{4+\sqrt{2}}{7} \approx 0.773459.
$$
This is corroborated by experiment. When $n=1000$, the empirical average of $10^6$ trials is $0.773733$ (the expected error is of order $10^{-3}$).

The expected gap between $\max(W)$ and $\min(W)$ is
$$
\sum_{n=1}^\infty np_n =
p_1 \sum_{n=1}^\infty n(2-\sqrt{2})^{n-1} =
\frac{p_1}{(\sqrt{2}-1)^2} = \frac{4+8\sqrt{2}}{7} \approx 2.18767.
$$
In particular, the limits of $\mathbb{E}[\max(W)]/n$ and $\mathbb{E}[\min(W)]/n$ (after $n$ steps) are the same.

In a similar way, it should be possible to compute $\lim_{n\to\infty} \mathbb{E}[\max(W)]/n$ for any fixed $m$, though I don't know if there is a nice formula for this limit in general.

Other limits could also be interesting. For example, one could ask what happens if $n$ is fixed and $m\to\infty$ (this should be easy to answer), or when $n=m \to \infty$ (seems more difficult).

Calculating the exact expectation for given $n,m$ is possible using the same ideas, but there isn't probably any nice formula.


Which redexes are there in $\lambda s. \lambda z. (\lambda u. z)(\lambda v. v)$? How to substitute arguments? I'm having difficulties understanding lambda calculus, specially identifying what's a redex. Which redexes are there in $\lambda s. \lambda z. (\lambda u. z)(\lambda v. v)$?

The book uses
$(\lambda u. z) [u \to (\lambda v. v)]$,

but isn't $(\lambda s. \lambda z. (\lambda u. z))[s \to (\lambda v. v)]$ valid too?

You must learn how to put in parentheses and then it will be easier to figure out what is what. In the above case, we first put in parentheses:
$$\lambda s . (\lambda z . ((\lambda u. z) (\lambda v . v))).$$
This is the only correct way to put back parentheses. For instance, this is wrong
$$(\lambda s . (\lambda z . (\lambda u . z))) (\lambda v . v)$$
Why is it wrong? Because the rules for writing expressions without parentheses say that when you see $\lambda x . \cdots$ that means that $\lambda x$ binds the whole expression. For instance $\lambda x . x (\lambda y . y)$ is the same as $\lambda x . (x (\lambda y . y))$ and is diffrerent from $(\lambda x . x) (\lambda y . y)$.

If this is not resolving your dilemma you have to explain why you think that the other redex is valid.


After the training phase, is it better to run neural networks on a GPU or CPU? Sorry if this is the wrong forum for this question. My understanding was GPUs were more efficient for running neural nets, but someone recently suggested GPUs are only needed for the training phase. Once trained, it's actually more efficient to run them on CPUs.

Is this true?

Running trained artificial neural network is repeated performing of a matrix with vector multiplication and performing the same nonlinear function for each element of a vector. If both operations could be parallelised and vectorised, it is what is GPU well suited for. But it strongly depends on the size of given vectors and matrixes which depend on the size of the neural network. For small nets, CPU could be faster than GPU but it would not matter anyway. For huge nets, GPU would be probably much better suited if algorithm is written right.


Why is this code uniquely decodable? Source alphabet: $\{a, b, c, d, e, f\}$

Code alphabet: $\{0, 1\}$

$a\colon 0101$
$b\colon 1001$
$c\colon 10$
$d\colon 000$
$e\colon 11$
$f\colon 100$

I thought that for a code to be uniquely decodable, it had to be prefix-free.
But in this code, the codeword $c$ is the prefix of codeword $f$ for example, so it is not prefix-free. However my textbook tells me that its reverse is prefix free (I don't understand this), and therefore it is uniquely decodable. Can someone explain what this means, or why it is uniquely decodable? I know it satisfies Kraft's inequality, but that is only a necessary condition, not a sufficient condition.

Your code has the property that if you reverse all codewords, then you get a prefix code. This implies that your code is uniquely decodable.

Indeed, consider any code $C = x_1,\ldots,x_n$ whose reverse $C^R := x_1^R,\ldots,x_n^R$ is uniquely decodable. I claim that $C$ is also uniquely decodable. This is because
$$
 w = x_{i_1} \ldots x_{i_m} \text{ if and only if } w^R = x_{i_m}^R \ldots x_{i_1}^R.
$$
In words, decompositions of $w$ into codewords of $C$ are in one-to-one correspondence with decompositions of $w^R$ into codewords of $C^R$. Since the latter are unique, so are the former.

Since prefix codes are uniquely decodable, it follows that the reverse of a prefix code is also uniquely decodable. This is the case in your example.

The McMillan inequality states that if $C$ is uniquely decodable then
$$
\sum_{i=1}^n 2^{-|x_i|} \leq 1.
$$
In other words, a uniquely decodable code satisfies Kraft's inequality. Therefore if all you're interested in is minimizing the expected codeword length, there is no reason to look beyond prefix codes.

Sam Roweis gives in his slides a nice example of a uniquely decodable code which is neither a prefix code nor the reverse of a prefix code:
$$
0,01,110.
$$
In order to show that this code is uniquely decodable, it suffices to show how to decode the first codeword of a word. If the word starts with a $1$, then the first codeword is $110$. If it is of the form $01^*$, then it must be either $0$ or $01$. Otherwise, there must be a prefix of the form $01^*0$. We now distinguish several cases:

$$
\begin{array}{c|cccc}
\text{prefix} & 00 & 010 & 0110 & 01110 \\\hline
\text{codeword} & 0 & 01 & 0 & 01
\end{array}
$$
Longer runs of $1$ cannot be decoded at all.


Survivors classes in the extremely unlikely scenario of P = PSPACE If its proven today that $P=PSPACE$ the whole polynomial hierarchy collapses. Moreover since $BQP \subseteq PSPACE$, it will also result in $P=BQP$.

However unlikely the above scenario is, hypothetically if this were the case what are the complexity classes (the most important ones) that will survive this collapse into $P$. The classes we are talking about:

Should be above $P$ (thus $L, NC, NL$ etc. could be temporarily ignored)
Are interesting and open enough to be studied (thus $E, EE, ALL$ etc. can be ignored)

We are concerned about both the traditional as well as Quantum Complexity classes.

The time hierarchy theorem still tells us that
$$\mathrm{P}\subsetneq \mathrm{EXP}\subsetneq\mathrm{2\text{-}EXP} \subsetneq \dots\,,$$
and likewise for the analogous space classes and nondeterministic time and space classes.


Is there a generic algorithm for translating equational rules into corresponding data structures? When implementing a term rewriting system, one “optimization” one can do is to represent operators known to have certain equational properties with a more directly representative data structure.  For example, one can use lists to represent uses of a binary operator known to be associative, rather than using the naïve syntax tree representation one is forced to use in the absence of any information about an operator.

I thought I recalled a result that stated that there was an algorithm that could take any (finite) set of equational rules about an operator and transform them into a data structure definition specialized for that set of equational rules.  However, when I tried to look for this result, I couldn't find anything like it anywhere.  Am I not looking hard enough or not in the right places, or did I just imagine this result entirely?  If I did imagine it out of thin air, is there any less-powerful result of the same form that is known, or any counter-result that dashes my hopes of such a generic algorithm existing?

It sounds like what you are asking for is, for a given equational system $\cal E$, to give a canonical representation for equivalence classes modulo $\cal E$.

Indeed, if your signature is the binary operation $\_\cdot\_$, and your equation is
$$ (x\cdot y)\cdot z=x\cdot(y\cdot z)$$

then you can represent any element as $a_1\cdot(a_2\cdot(\ldots\cdot a_n)\ldots)$ (where the $a_i$) are atoms. As Derek Elkins points out, a good way to do this is to apply Knuth-Bendix completion to $\cal E$, (possibly) obtaining a rewrite system $\cal R$ that is confluent and terminating and computes, for each term $t$, a unique element that is a representative of $t$'s equivalence class under $\cal E$.

Now it is useful to note that in this case, the set of canonical forms happens to be isomorphic to the data types of lists of atoms. The fact that elements of an algebraic datatype captures the equivalence classes is not obvious, and is not true in general: if you add commutativity, that is the equation
$$ x\cdot y = y\cdot x$$
then it's clear that there is no algebraic (first-order) datatype that captures exactly the normal forms, as this is isomorphic to sorted lists of atoms.

A reasonable question is to ask whether there is always such a data structure using dependent types. In particular, there is a version of sorted list using dependent types, namely:

data SortedList =
  Nil : SortedList
  Cons : forall x:Atom, forall l:SortedList , x <= min l -> SortedList

taking inspiration from this agda code. Note that min needs to be defined on SortedList, making this an inductive-recursive definition, but I'm pretty sure this can be avoided with a little more messiness (say, embedding list into sorted list).

I think the question needs to be made more precise though, because there is a type in extensional dependent type theory such that each element of that type represents exactly one equivalence class: namely, the type of all equivalence classes! It can be defined by

$$ \mathrm{Q}_E:=\{y|\exists x, \overline{x} = y\}$$
where $\overline{x}$ is defined by:
$$\overline{x}=\{z| z=_E x\} $$

In general, quotient types are a tricky subject in type theory though, especially without sufficient extensionality, see e.g. Pragmatic Quotient Types by Cyril Cohen.

In conclusion:

In the naive version of your question, the answer is that it is impossible to associate an inductive data type to an equational theory such that each element of the type represents a unique class.
It is sometimes possible to compute a rewrite system which computes a unique representative of that class if the algorithm terminates and succeeds.
When allowing for dependent types, the question becomes more complex and is, I believe, still somewhat open, with some progress.


Assignment Problem -- finding the $k$ agents with the best assignment I have a question that I have been thinking about. Suppose we have $n$ agents, $m$ tasks, a cost matrix with $M_{ij}$ being the cost of agent $i$ performing task $j$, and are given a value $k \leq n$. How can we find the $k$ unique agents, who when each optimally allocated a unique task, result in a minimum total cost? Can this be related to the assignment problem? Thank you very much for any guidance or assistance.

The assignment problem can be extended to solve this problem. The regular problem without the $k$ restriction can be solved by building a Minimum Cost Maximum Flow network is as follow:

We have a source $S$ a sink $T$ and the corresponding bipartite graph in the middle. Note that each edge has two values $f/c$ which denote maximum flow allowed through this edge and cost of each flow unit. Now, the problem is that we want to allow at most $k$ units of flow from $S$ to $T$. To do this, just duplicate node $S$ into $S_1$ and $S_2$ and put an edge among them such that cost of each unit is 0 (no penalty) and maximum flow allowed is $k$. The new graph will look like this:

The minimum cost maximum flow from $S_1$ to $T$ is the solution to the original problem for a fixed $k$.