The Law of Excluded Miracle in the language of guarded commands The definition of weakest precondition is familiar (let me use Isabelle's syntax here):

definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t"

the weakest precondition ensuring Q when executing a command in an initial state s is given by the formula in the RHS.

Now, Dijkstra, for instance in, "Nondeterminacy and Formal Derivation of Programs" talks about the law of the excluded middle:

definition "F ≡ λ t. False"

lemma "wp c F = F" unfolding wp_def F_def by simp

according to this article the meaning of this proposition would be:

  started in a given state, a program execution must either terminate or
  loop forever

However, I don't see how this proposition states this fact. Unrolling the definitions I get:

∃t. (c,s) ⇒ t ∧ (λ t. False) t = ∃t. (c,s) ⇒ t ∧ False = False

seen as a function in s, obviously this LHS matches the RHS. However, I don't see how this tells that the program terminates or loops.
Could you explain what is happening here?

The answer I can provide is I was reusing the definition of weakest precondition from the IMP language, but in fact I need a stronger definition. This definition looks as follows:

definition "wp c Q s ≡ (∃t. (c,s) ⇒ t) ∧ (∀ t'. (c,s) ⇒ t' ⟶ Q t')"

It is taking care of non-determinism. When one evaluates:

lemma excluded_miracle: "wp c (λ t. False) = (λ s. False)"

One realizes that the statement is simply saying that the program either terminates, or does not terminate. Therefore, the import point now is to see whether my proposed definition is correct or can be improved in any way.


Why is it meaningless to say the runtime of an algorithm is at least in the order of n squared? I would like to know why the following statement

  The running time of algorithm $A$ is at least $O(n^2)$

which means the best-case running time of $A$ is $O(n^2)$ is meaningless (CLRS page 53).

But the following is not

  The worst-case running time of algorithm $A$ is $\Omega(n^2)$

(used in CLRS page 160).

First of all, both sentences are a slight abuse of notation. $\mathcal{O}(n^2)$ and $\Theta(n^2)$ are sets; strictly speaking you can't compare a running time with a set. Saying "$f$ is $\mathcal{O}(g(n))$" is actually a shorthand for "$f$ belongs to the set $\mathcal{O}(g(n))$"; with that in mind, we can rephrase the statements you quote as follows:

  The running time of $A$ is at least $f(n)$ for some $f \in \mathcal{O}(n^2)$.

and:

  The worst-case running time of $A$ is at least $f(n)$ for some $f \in \Omega(n^2)$.

Put in this form, the first statement is well-defined, but it's not really insightful. In fact, it is always true. Let $g$ be the constant function $0$. Certainly $g$ is a member of $\mathcal{O}(n^2)$, and whatever the running time of $A$ is on input of size $n$, it is at least $g(n)$.

Intuitively speaking, big-oh is an upper bound: if I tell you: "I have at least $100 or less", I didn't really give you any information at all.

On the other hand, the second statement guarantees that the worst-case running time of $A$ cannot be too low: it must grow at least quadratically.


What is the bit complexity of Gaussian eliminaton over $\Bbb F_q$? Given matrix $M\in\Bbb F_q^{n\times n}$ with rank $r$ what is the complexity of converting to row-echelon form?

  Is it $O(n^3\log q)$ or $O(n^3q)$ bit operations?

Technically $O(n^3)$ row operations in $O(\log q)$ bit words should be $O(n^3(\log q)(\log\log q)^2)$ bit operations in worst case when $q$ is prime.

What I am confused about is

when $q$ is prime power
incorporating complexity of modular operations.

The dependence on the field is via the cost of arithmetic operations over the field. Since numbers in $\mathbb{F}_q$ have bit size $O(\log q)$, the cost of each individual operation is polylogarithmic in $q$.


Is there a way to modify Kadane's Algorithm such that we know the resulting subarray? Kadane's Algorithm is an algorithm that solves the maximum subarray problem by clever dynamic programming. Is there a way to further modify the algorithm so that we would get to know the resulting subarray that produces the corresponding maximum sum?

PS: I don't know whether I should post this here, or Stack Overflow, or both.

Yes, you can.

Kadanes's algorithm keeps the value of the best subarray in a variable, let's call it best_sum.
Notice the invariant in the algorithm.
best_sum will always (after each iteration) contain the value of the maxium subarray of the prefix of the array that you already visited.
Additionally you know the best suffix sum of the current prefix, let's call it current_sum, which you use to update best_sum.

You just need to do the same thing with the position.
Introduce three more variables current_startindex, best_startindex and best_endindex. current_startindex tells you, at which position the current best suffix starts. best_startindex and best_endindex indicate the start and end of the best subarray from the visited prefix.
Keep those variables valid in each iteration. E.g.
Whenever you update current_best, also update current_startindex.
And whenever you update best_max, also update the best_startindex and best_endindex, so that at the end of each iteration the value is correct.

After iterating over the complete array, best_sum will contain the sum of values of the maximum subarray, and best_startindex and best_endindex will tell you the positions.


Deadlock and cycle in a resource allocation graph Here is a resource allocation graph asked in my Operating Systems Theory midterm. The question is, "Is there a deadlock here? Explain your answer in detail"

Ra and Rb are resource sets and every dot inside of them are resources. Circles are processes. An arrow from process to a resource set means that process is requesting a resource from that set. An arrow from resource set to process means that process owns a resource from that resource set.

I want to have your opinions on this, because the lecturer's answer is conflicting with mine. Lecturer says there is a deadlock here. But my answer was, since Py and Pz are not requesting a resource, they will simply continue their execution and terminate, releasing their resources. Then Px and Pw can obtain their requested resources and keep executing. It is obvious there is a cycle in this graph as Px-Pw but this doesn't conclude us to a deadlock. Thus I can't see a way to make "there is a deadlock here"conclusion.

So is there a deadlock here?

I did some thinking and then searching and all RAG conditions of this example leads to conclusion that there is no deadlock (altho there is a cycle here).

Beside after searching I found this where you can find this:

Which clearly stands Graph With A Cycle But No Deadlock

Are you sure that you have your graph correct here?


Precise definition of oracle classes $A^B$ I was reading in Papadimitriou's "Computational Complexity" book Chapter 14, about Oracle Machines. Papadimitriou defines, in definition 14.3, page 339-340, Oracle Turing Machines with oracle a language $A \subseteq \Sigma^*$:

  The computation of $M^{?}$ with oracle access $A$ in input $x$ is denoted $M^A(x)$.

So far so good.

In the next paragraph, he writes:

  If $\mathcal{C}$ is any deterministic or non-deterministic complexity class, we can define $\mathcal{C}^A$ to be the class of all languages decided by machines of the same sort and time bound as $\mathcal{C}$, that have oracle access to $A$.

My question is:

  Given any complexity class $B$ and $C$, can we always define $B^C$?

This is motivated by a question I posted (and deleted) at TCS.stackexchange where , using Papadimitriou's notation, I defined $B^C$ for a complexity class $B$ and $C$ but I received criticism (besides the context of the question) that I am not allowed to do that because oracle is not an operation defined on languages and hence complexity classes. Does this contradict the extract from Papadimitriou's book (where he explicitly defines $B^C$ for a _complexity class $B$)?

My understanding is that

  We can define $B^C$ for a complexity class (i.e., a set of languages) $B$ if $B$ can be defined by a Turing Machine model.

If yes, why it is not explicit in Papadimitriou's book?

The simplest case is when $C$ has complete problems with respect to $\mathsf{F}B$ reductions (the function class corresponding to $B$). In that case, you can define $B^C$ as $B^L$ for some $C$-complete problem $L$, and everybody will be (mostly) happy, at least if $B$ is not a very weak class. This allows us to define $\mathsf{P}^{\mathsf{NP}}$, for example.

When $C$ doesn't have complete problems, sometimes the following definition is used: $B^C = \bigcup_{L \in C} B^L$, or perhaps $B^C = \bigcup_m \bigcup_{L_1,\ldots,L_m \in C} B^{L_1,\ldots,L_m}$. However, this definition doesn't necessarily have the right properties.

Another option is if you can enumerate all languages in $C$ (for example, $\mathsf{BPP}$ can be enumerated using probabilistic Turing machines with an explicit time bound), say they are $(L_n)_{n \in \mathbb{N}}$. In that case you can define $B^C = B^{L_1,L_2,\ldots}$, where the oracle for $L_1,L_2,\ldots$ accepts an index $i$ and a word $x$, and outputs whether $x \in L_i$. One drawback is that this definition depends on the enumeration; it's best to use a "natural" enumeration. Otherwise, you can "cheat" by putting information into the enumeration. A way out it to define $B^C$ as the intersection of $B^{L_1,L_2,\ldots}$ for all possible enumerations.

Things become even more complicated when $B$ is weak. For some of the issues involved, see Aehlig, Cook, and Nguyen, Relativizing Small Complexity Classes and their Theories. These issues are orthogonal to what we have described above: they cause problems even when trying to define $B^L$ for a language $L$.


Context Free Grammer and PDA (Palindrome but without characters repeating in a row) So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says

"L contains palindromes that don’t ever have the same character occur twice in a row."

Let $\Sigma = \{a, b, c\}$.

Let $L = \{w \in \Sigma^∗| w = w_1w_2\cdots w_n \mbox{ is a palindrome and } w_i \neq w_{i+1} \forall 0 \le i\lt n\}$.

In other words, $L$ contains palindromes that don’t ever have the same character occur twice in a row.

In the second part can someone guide me how to make it's PDA or give an idea?

The language in question consists of all palindromes in which no two consecutive characters are the same. For example, $aa$ is a palindrome, but doesn't belong to the language since $a$ repeats; but $aba$ is OK.

When the alphabet consists only of $a$ and $b$, you can modify the grammar $S \to aSa|bSb|a|b|\epsilon$ of palindromes to accept your language by using two nonterminals $A,B$ which generate the following languages:

$A$ generates all palindromes starting with $a$ in which no two consecutive characters are the same.
$B$ generates all palindromes starting with $b$ in which no two consecutive characters are the same.

I'll let you complete the construction, and generalize it to larger alphabets.

(In the particular case of an alphabet of size 2, the language is actually regular, but this doesn't happen when the alphabet is larger.)

The simplest way to construct a PDA is to use to use the production construction: starting with a PDA for the palindrome language and a DFA for the language of strings with no repeated characters, you can construct a PDA accepting the intersection. This is a standard construction that appears in many textbooks.


How much information, in bits, is conveyed by a 3-bit output representing how many 1s in a 7-bit input? Let's say I have a combinational device that has an input of 7 bits and outputs a 3-bit binary number that reflects the number of 1s among the 7 bits.
How much information would be conveyed by the following outputs: 000 and 001?
I know information, in bits, is calculated by log2(1/p), and p is M/N, where N is the number of equally probable choices, and M is the amount of choices left after being given a piece of data.

Assuming the 7-bit input is chosen randomly, the entropy of the number of 1s is
$$
 \sum_{i=0}^7 \frac{\binom{7}{i}}{2^7} \log \frac{2^7}{\binom{7}{i}} \approx 2.45 \text{ bits}.
$$
This is because the probability that the number of 1s is $i$ equals $\binom{7}{i}/2^7$.

You are asking how much information is conveyed by particular outputs, and this can be interpreted as the loss in entropy: if $X$ is the random 7-bit input and $Y$ is its sum, you could define the information conveyed by $Y=i$ as $H(X)-H(X|Y=i)$. Since $X$ has uniform distribution,
$$
 H(X) - H(X|Y=i) = \log 2^7 - \log \binom{7}{i} = \log \frac{2^7}{\binom{7}{i}}.
$$
The information conveyed by different outputs, under this definition, works out to be roughly (in bits):
$$
\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline
i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\hline
H(X) - H(X|Y=i) & 7 & 4.19 & 2.61 & 1.87 & 1.87 & 2.61 & 4.19 & 7
\\\hline
\end{array}
$$
The weighted average of these values equals the entropy calculated above.


#P complexity reduction We know that counting the number of Hamiltonian paths is in $\#\mathsf{P}$.

So, what complexity (counting version) class would the counting the number of Hamiltonian paths that have two or three particular vertexes in a graph be in?

Also, what would be like if counting the number of hampaths that have two or three particular vertexes in particular place - so, for example, calculating the hampath that has vertex 3 as the second place from starting point and so on?

Just an extended comment on the second part of the question (if I understood it correctly).

The problem is a special case of the general version; so if you allow $0$ "fixed" points (a fixed point is a point that must be in  a particular position in the Hamiltonian paths), then there is an immediate reduction from the problem of counting Hamiltonian paths.

If your problem says that at least $k$ points must be fixed, then this reduction should work: given a graph $G$ and two vertices $s$ and $t$, and $e_1,e_2,...,e_m$ are the edges from $s$; then for each $e_i$ split it in $k+1$ pieces adding $k$ nodes, and solve your problem fixing the first $k$ nodes (and the number returned will be equal to the number of Hamiltonian paths from $s$ to $t$ in $G$ that start with $e_i$).

At the end the total number of Hamiltonian paths in the original $G$ is the sum of the number Hamiltonian paths returned by your algorithm fixing the first $k$ points in the splitted $e_1, e_2, ... e_m$.


Having trouble understanding blatantly non-private definition because of Little-o notation I was pretty confident that I understand asymptotic notation until now. However, I am having a hard time understanding some basic definition that use asymptotic notation, specially little-o.

Definition 8.1.A mechanism is blatantly non-private if an adversary can
construct a candidate database 'c' that agrees with the real database 'd' in
all but o(n) entries, i.e.,‖c−d‖0∈o(n).

A bit of context. 'd' is a database where each row is one individual 'i' with 'n' individuals in total. the database has just one column representing some important questions. The values of the column can be 0 or 1.
'c' is a candidate database, a database that will try to be as similar as possible to the database 'd', it has the same structure one row for each individual and values for the column of {0,1}. Both are treated as a vector.
I watched a lecture and the informal description of the professor was "database 'c' will agree with database 'd' in 99,9..% of the cases".
But my interpretation of the definition is exactly the opposite "database 'c' will agree with database 'd' in all entries except 99,9..%".
My definition seems a bit odd to a "blantly" non-private mechanism. But I cannot understand how "except o(n)" would mean that a minority of the entries would not be equal in both databases.

The interpretation of your professor is "intuitively correct" (but still formally wrong).
The notation $o(n)$ denotes the set of functions that grow less than linearly with $n$.
That definition means that, if we look at databases $d$ whose number of entries $n$ grows towards infinity, the candidate database $c$ will agree with $d$ in all but a vanishingly small fraction of the entries.
Notice that if $c$ agrees with $d$ "only" on $99.9\%$ of the $n$  entries, then the number of disagreements still grows linearly with $n$. Indeed: $0.001n \in \Theta(n)$ and hence $0.001n \not\in o(n)$. See the page about asymptotic notation on Wikipedia.


Pittsburgh approach, how does encoding and fitness function work? I am writing a genetic algorithm for Machine learning and came across Pittsburgh approach in some research papers. The papers didn't explain the algorithms proper or I am too stupid to understand. I know that each Individual contains set of rules and I have also implemented in binary but am having trouble with 6 float type values.
My question is:

How am I generating uncertainty value in the genes?
How will I be using encoding with real/floating type values?
How is the fitness function going to work?

I would love to it also if you could send me references to which I might be able to better understand the algorithm. I will be using float number so no binary methods or explanation.

So both the Pittsburgh and Michigan approaches are techniques for applying evolutionary methods to learning (essentially) a set of "if/then" rules for performing some task effectively. The important bit is the "set" there in "set of rules". You need to learn multiple rules that can each fire in different situations in order to cover the entire space of behaviors the algorithm needs to learn. Where the Pittsburgh and Michigan approaches differ is in how you arrive at that set of rules.

They're both GAs under the hood, so there's a population of things. In the Pittsburgh approach, those "things" are complete candidate solutions to the problem. A single individual in a Pittsburgh algorithm might contain many rules. A single individual in a Michigan approach contains only one rule. In order to form a viable actual algorithm for solving the problem, the Michigan approach needs to take the entire population and hope that each of those individuals with their individual rules combine together in a way to cover the problem space well.

Under the hood though, as I said, they're basically just GAs. So you can do recombination and mutation however you like. You can handle floating point genes the same way you'd handle them in any other GA -- perhaps by using variation operators that natively work on floats or by encoding the values as binary yourself. Fitness in Pittsburgh systems can be reasonably straightforward. Every individual is intended as a complete solution, so you just run your simulation and calculate how well that individual's rule set solves the problem. The answer is that individual's fitness. For Michigan approaches, it's harder, because there's a credit assignment problem. One individual encodes one rule, and that rule may be perfect for its niche, but if the rest of the population is terrible, performance will be poor.

Another problem is that the structure inherent in classifier systems like this means that typical genetic operators won't necessarily work that well. You can use them, but tweaks to the ideas can perform quite a bit better. The Learning Classifier Systems community has done quite a bit of work figuring this stuff out. My general advice would be to start by looking at Stewart Wilson's XCS algorithm.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.363.2210&rep=rep1&type=pdf

http://opim.wharton.upenn.edu/~sok/papers/b/XCSAlgDesc01202001.ps


Pumping lemma: if you can keep pumping, what does this tell you? Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation, do you have to "throw out" the lemma so to speak? I am under the impression that the answer is yes, but I'm just not sure.

If you are not sure, it is probably because you want to know why. This question is frequent among students in computer science that are learning the pumping lemma for the first time and it is the cause of a lot of errors.

Logic

The reason is very simple. It is because of logic. I will explain it considering the pumping lemma for the regular languages but it is analog for the context-free version of the lemma. The statement that has been proved is the following:

$$1)\ L\text{ is a regular language}\implies L\text{ complies with the pumping lemma}$$

This is all we know. Notice that this implication is in one direction. In other words we can't conclude:

$$2)\ L\text{ complies with the pumping lemma}\implies L\text{ is a regular language}$$

It is a common mistake to invert the propositions in the first implication and expect to obtain a  logically equivalent statement (you can't use the second statement!).

When we use the pumping lemma we are actually using the contrapositive of the first implication:

$$3)\ L\text{ doesn't complies with the pumping lemma} \implies L\text{ is not regular}$$

The first and the third statements are logically equivalent. This is why we search for a contradiction when trying to force $L$ to fulfill the pumping lemma. If $L$ doesn't comply with the lemma then we are sure that $L$ is not regular. If you were paying attention you could have noticed that we can't prove that $L$ is regular using the pumping lemma. If you want to prove that $L$ is a regular language you should find a regular expression, NFA or a DFA (or even a regular grammar) that denotes $L$.

Inside the pumping lemma

Another big source of error is the incorrect interpretation of the lemma. Every word in the lemma is very important:

Pumping lemma: If $L$ is regular then there exists a constant $N\in \mathbb{N}$ such that for all $\sigma$ in $L$ with $|\sigma|\geq N$ there exists a decomposition $\sigma=\alpha\beta\gamma$ such that:

a) $|\alpha\beta|\leq N$

b) $\beta \neq \epsilon$

c) $\alpha\beta^i\gamma \in L\ \forall i \in \mathbb{N}_0$

Common mistakes

1) My word $\sigma$ complies with the pumping lemma so $L$ must be regular:
This is wrong for so many reasons. First, we can't conclude that $L$ is regular using the pumping lemma (see the Logic section). Second, a lot of words can comply the three conditions but the lemma clearly state that all $\sigma\in L$ with $|\sigma|\geq N$ should comply. So good luck trying with another word!

2) If I choose this particular $\alpha$, $\beta$ and $\gamma$ I find a contradiction!:
This is wrong too. The lemma states that there exists a decomposition(at least one) that fulfill the lemma. So if you choose one and it doesn't meet the three conditions it doesn't say too much... Now you have to try with all the remaining possible decompositions! You will find a contradiction when you prove that is impossible to find such a decomposition.

3) If I choose the word $\sigma=\epsilon$ I find a contradiction!:
This is wrong for two reasons. First, $N>0$. Second, the lemma states that there exists a constant $N$. If you choose $N=0$ (wrong by definition) or $N=1$, $N=2$, etc and you find a contradiction it is okay. Now you have to try all the remaining integer $N$! This is the reason why you should never try to choose a specific constant $N$ and why you should use a generic constant instead.

4) I tried a lot of words and all of them comply with the pumping lemma... what do I do?:
At this point you have two options. You can suspect that $L$ is regular and try to find a regular expression(or NFA, DFA, regular grammar...) that denotes $L$. If you suspect that $L$ is not regular then maybe it is time to use closure properties to simplify the problem or you can continue your epic quest of proving that $L$ is not regular by trying others words.

These are all the tips I have for now. If I can remember some more in the future I will add them here.


Can I program a universal Turing machine to accept arbitrary input encodings? I've been reading about building Turing machines for specific purposes, and some sources talk about input encodings and some talk about programming specific machines, but I've been unable to find anything that discusses both. Here's a specific set-up:

  Suppose you have a universal Turing machine. It has a two-sided infinite tape, where the right side encodes a specific function to compute and the left side encodes the input to be provided to that function.

In general, I'm interested in the interaction between the encoding of the input, the specific program for the TM, and which UTM it is. My main question is:

  If I have a fixed underlying UTM, a fixed encoding of the input, and a desired function to compute, can I always find a way to program my UTM to compute that function on the input supplied in the specified encoding?

  For example, if I have the (2, 18) universal Turing machine, I encode the input using the system described here, and know that I want to compute the function $f(x, y, z) = x^3+xy+z^9$ is there guaranteed to be a program I can use to achieve this result?

I am under the impression that the answer is yes, but am not sure enough of my knowledge of Turing machine architecture to prove it.

More generally, if we think of this set up as having four parameters - the specific UTM, the specific input encoding, the specific function, and the specific program - is it always the case that if we fix three of these four parameters there will be a setting for the fourth?

I'm going to simplify your question, considering that a specific encoding for a universal Turing machine will necessarily include a method for the encoding of its programs. I'll also assume that the encoding of programs and their inputs are also interdependent, meaning that you can't define how the former is done well enough without defining how the latter is done, equally well, and vice-versa.

What's left for us to do then, is to be able to explore the correspondence between programs and mathematical functions. We know that there are functions that are definable, but not computable (there isn't a corresponding program). We tend to assume that every program is the encoding of a function, but that's debatable.

So, you ask (as I understand): if there is a program that computes a function under a specific encoding of the input, for a specific encoding of the machine on which it runs, if one of these encodings change, will the function still be "writable"?

The answer would have to be that, if this is not the case, then that proves the encodings are not really equivalent, i.e., the computational models they define are substantially different. In other words, with a change in encoding should come a proof of equivalence, and what that proof states is exactly that the different encodings should be able to write the same functions $-$ if writable they are.


Rigorous proof against pseudo random function I have the following problem:

Deﬁne the keyed function F as follows: On input k ∈ {0, 1}$^n$
and x ∈ {0, 1}$^n$ , Fk(x) = k ⊕ x.Rigorously prove that F is not a pseudorandom function.

How do I approach a proof against pseudorandomness for a keyed function? I don't know where to start with this one.

How to approach it? It's always the same answer - go back to the definitions.

the definition of PRF, talks about a family of functions $\{f_k\}$. The key $k$ just selects one specific function out of this big family.

Next, for $\{f_k\}$ to be a PRF family,the definition requires that any PPT algorithm $A$ will not be able to distinguish a member of the that family, from a really-random function (that is, a function sample randomly from all-the-possible-functions).

Since all the functions in your family have a very specific structure, you can easily built an algorithm $A$ that will always answer '1' if it's input function has the structure $f_k(x)=k\oplus x$, or otherwise, it  outputs '0' (I let you complete the details). This $A$ is a distinguisher for that family-- for functions from this family it always answers 1, and for a random-function, it will answer '0' most of the times (say, it will answer '0' for at least half of those functions). Since such a distinguisher exists, the given family of functions is not pseudo-random.


Efficient algorithm to compute the minimum of multiple piecewise linear functions Let $f_i(x)$ be a continuous, convex, piecewise-linear function for $i=1,\ldots,n$. Define
$$g(x) = \min_{1\leq i\leq n} f_i(x).$$
Clearly, $g(x)$ is also a piecewise linear function. What would be a good approach to compute all the pieces? In other words, it's clear that $g(x)$ can be represented as
$$g(x) = c_k + d_k x,\quad \text{for } x\in[e_k,e_{k+1}),$$
for some choice of $(c_k,d_k,e_k)$'s.  How do I compute these $(c_k,d_k,e_k)$'s in an efficient way, given the $f_i$'s?

This is basically an instance of the line segment intersection problem.  One standard approach is to use a sweep line algorithm.  For instance, the Bentley-Ottman algorithm would be a reasonable choice, and is not too difficult to implement.

At each iteration of the algorithm, we have some value of $x$, and we calculate what is the next largest value of $x$ where something interesting happens.  Here, "something interesting" is either (1) two pieces intersect each other at a point, or (2) we reach the end of one of the current pieces.  Then we advance $x$ to this next value.

At each iteration, we keep track of which pieces are currently active (i.e., $x$ is within the domain of that piece) and the order of the pieces, ordered by their $y$-value for that particular value of $x$.  Store them in sorted order, sorted by $y$-value.

All of the interesting bit is in how we determine the next largest value of $x$ where "something interesting" happens.  Fortunately, this is easy.  For each pair of adjacent active pieces (adjacent in their sorted order), we can find whether they intersect and where, and if it corresponds to a larger value of $x$, add it to a priority queue.  Also, for each active piece, we can add its right endpoint (the largest value of $x$ in its domain) to the priority queue.  Then finding the next "interesting" value of $x$ amounts to an ExtractMin operation on the priority queue.  Also, when you move to the next largest interesting value of $x$, it's easy to update the set of active pieces and maintain them in sorted order.

Let $n$ denote the total number of pieces among the $f_i$'s, and $k$ the total number of intersections between pieces.  Then each iteration can be implemented in $O(\lg n)$ time, and the number of iterations can be upper bounded by $O(n+k)$, so the running time will be $O((n+k) \lg n)$.


Is there such a thing as an "or" case in a dependency graph? Suppose $A$ depends on $B$ or $C$, but not necessarily exclusively. Is it possible to model this in a dependency graph?

Can we just link $A$ to $B$ and $C$ via a diamond (like in UML) (though I don't see how this can be represented mathematically)? Or do we have to condense $B$ and $C$ to a single node $D$?

It's possible to represent a general boolean function as a directed acyclic graph. Wikipedia has examples of this on the binary decision diagram and propositional directed acyclic graph pages.

In the case of the PDAG, the up triangle represents AND, the down triangle OR, and the diamond represents NOT. The PDAG seems to be the closest to an AND/OR dependency graph, with the topmost element only having its requirements satisfied if the function would yield a 1.

To represent this mathematically, you could use Boolean algebra.


Coordinated Attack Problem Different Requirements There is a famous Coordinated Attack Problem. Let define a simple message-passing system $S$ with requirements

Uniform Agreement: No two processes decide dierently.
Validity:

(a) If all processes start with 0, then no process decides 1.

(b) If all processes start with 1, and there are no failures, then no process decides 0.

Termination: All nonfaulty processes eventually decide.

System $S$ consisting of two processes $p$ and $q$ connected by a  bidirectional communication link such that (a) processes proceed
in synchronous rounds, (b) processes do not fail, and (c) any number of messages can be lost.

It's well known that system $S$ cannot satisfy all above requirements, therefore let consider different requirements.

Weak Termination: If there are no failures, then all processes eventually decide.

Is the problem consisting of Agreement, Validity, and Weak Termination unsolvable in system S?

  All processes eventually decide when there is no failures, so when inputs are $0$ and $0$ and no failures, both generals decide $0$. By dropping one of the message I cannot ensure the termination, therefore the standard reasoning doesn't work here.

Unanimous Termination: If any process decides, then all processes eventually decide.

Is the problem consisting of Agreement, Validity, and Weak Termination unsolvable in system S?

  It's also very tricky requirement. Assume the both inputs are $0$ and $0$ and no failures than both decide $0$, let drop the message from $P_1$ to $P_0$, regarding to $P_1$ it is the undistinguishable execution, therefore $P_1$ still decide $0$ and according to unanimous termination, someday $P_0$ will decide the same $0$ according to agreement, noq according to the standard schema, change the input of $P_0$ to $1$ and this undistinguishable execution to $P_0$, so the same agreement and so forth we reach a contradiction, no solution.

I am sure if it's correct. In addition the case with weak termination I don't know how to solve, even if it's solvable.

This looks like the Byzantine generals problem.  There's a lot written on that subject; I suggest you start by reading the available literature and material on that subject.

I'm not entirely clear on you mean by "solvable in system S" (system S says processes don't fail, but the weak termination condition refers to failures, so what's going on there?), so I can't confidently answer that part of your question.

There's an obvious algorithm for the case of two parties:

Each party continually broadcasts a message saying "my input is X" (fill in X with whatever its input bit is).
Whenever you receive one of those messages, you respond with an acknowledgement describing your input, what you received from the other party, and what you will output; then you immediately produce the appropriate output and halt.
If you receive an acknowledgement message and have not halted yet, then produce the appropriate output and halt.

It looks like this satisfies all three of your requirements, including weak termination, assuming that messages can be dropped/lost but are not modified in transit and no forged/fake messages are inserted by the network.


How can I create 10-character, unique codes with no collisions, but without being predictable? If we are using numbers and letters, there are $36^{10}$ unique combinations. Collision is already unlikely, but I need it to be impossible, so using hashing is out of the picture(?).

The use-case is users redeeming each one if they have been "activated" as redeemable. Think like Webkinz codes.

An inefficient solution would be to generate all of them at once, have a property on each saying whether it has been activated or not and keep a pool of those that have been redeemed and those that haven't.

Keeping a database of $36^{10}$ codes just because I can't come up with a clever algorithm is pissing me off, so I'm here for your help.

Any ideas?

$36^{10}$ is approximately 52-bit. Now;

Generate a secret key $k$ for AES-128
Encrypt the rowID with $\text{unique_code} = \operatorname{AES}_k(rowID)$, and assuming that the key never changes.

Since AES with a key selects permutation for all possible permutations from $2^{\ell}$ to $2^{\ell}$, where $\ell$ with a key, then by fixing a key, you fixed a secret permutation. Therefore the output is distinct for every distinct input. It is unpredictable since AES is assumed to be secure against Known-Plaintext Attacks.


What does 'true concurrency' mean? I often hear phrases like 'true concurrency semantics' and 'true concurrency equivalences' without any references. What does those terms mean and why are they important?

What are some examples of true concurrency equivalences and what is the need for them? E.g. in which cases they are more applicable than more standard equivalences (bisimulation, trace equivalence, etc)?

The term "true concurrency" arises in the theoretical study of concurrent and parallel computation. It is in contrast to interleaving concurrency. True concurrency is concurrency that cannot be reduced to interleaving. Concurrency is interleaved if at each step in the computation, only one atomic computing action (e.g. an exchange of messages between sender and receiver) can take place. Concurrency is true if more than one such atomic action take place in a step.

The simplest way of distinguishing both is to look at the rule for parallel composition. In an interleaving based setting, it would look something like this:

$$\frac{P \rightarrow P'}{P|Q \rightarrow P'|Q}$$

This rule enforces that only one process in a parallel composition can execute an atomic action. For true concurrency, a rule like the following would be more appropriate.

$$\frac{P \rightarrow P'\quad Q \rightarrow Q'}{P|Q \rightarrow P'|Q'}$$

This rule allows both participants in a parallel composition to execute atomic actions.

Why would one be interested in interleaved concurrency, when concurrency theory is really the study of systems that execute computation steps in parallel? The answer is, and that's a great insight, that for simple forms of message passing concurrency, true concurrency and interleaving based concurrency are not contextually distinguishable. In other words, interleaved concurrency behaves like true concurrency as far as observers can see. Interleaving is a good decomposition of true concurrency. Since interleaving is easier to handle in proofs, people often only study the simpler interleaving based concurrency (e.g. CCS and $\pi$-calculi). However, this simplicity disappears for concurrent computation with richer forms of observation (e.g. timed computation): the difference between true concurrency and interleaved concurrency becomes observable.

Standard equivalences like bisimulations and traces have the same definitions for true and interleaving based concurrency. But they may or may not equate different processes, depending on the underlying calculus.

Let me give an informal explanation of why interleaving and truly concurrent interaction are indistinguishable in simple process calculi. The setting is
a CCS or $\pi$-like calculus. Say we have a program

$$
   P \quad=\quad \overline{x} \ |\  \overline{y} \ |\  x.y.\overline{a} \ |\  y.\overline{b}
$$
Then we have the following truly concurrent reduction:
\begin{eqnarray*}
  P &\rightarrow& y.\overline{a} \ |\  \overline{b}
\end{eqnarray*}
This reduction step can be matched by the following interleaved steps:
\begin{eqnarray*}
  P &\rightarrow & \overline{x} \ |\  x.y.\overline{a} \ |\  \overline{b} \\
    &\rightarrow & y.\overline{a} \ |\  \overline{b}
\end{eqnarray*}
The only difference between both is that the former takes one step, while the
latter two. But simple calculi cannot detect the number of steps used to reach
a process.

At the same time, $P$ has the following second interleaved reduction sequence:
\begin{eqnarray*}
  P &\rightarrow & \overline{y} \ |\  y.\overline{a} \ |\  y.\overline{b} \\
    &\rightarrow & \overline{a} \ |\  y.\overline{b}
\end{eqnarray*}
But this is also a reduction sequence in a truly concurrent setting, as long
as true concurrency is not forced (i.e. interleaved executions are allowed even
when there is potential for more than one interaction at a time).


Why does a suffix tree have a linear number of nodes (relative to input string size)? Aren't there $n^2$ unique substrings of a string (irrespective of the alphabet size)? Perhaps the number of unique suffix substrings is less than the number of unique substrings of a string.

For a text of length $n$ we have up to $1+{ n+1 \choose 2}$ different substrings, however there are only $n+1$ suffixes (for every suffix you can pick the position where it starts).

I assume you consider the compressed suffix tree (edge labels are words). This is a tree with $n+1$ leaves and every internal node has at least two children. Thus we have less interior nodes than leaves an therefore the tree has size $O(n)$.

Notice that in the uncompressed version (edge labels a characters) with a large alphabet, you can have super-linear suffix trees. For example, consider the text abcdefghijk....


Is there a formal definition for iteration? I wanted know if there is a formal definition of iteration. In the sense that, this definition will say that after the 4th iteration is termination or the 5th iteration and not the 2nd iteration. Basically a rigorous definition of iteration.

The $k$th iteration is just the $k$th element of some appropriate sequence. In general, I doubt it's a formally defined concept; it's just one of those things whose meaning is basically the natural-language meaning of the word.


Divide and Conquer majority element algorithm The algorithm should return the majority element if it exists (majority meaning that there are $> n/2$ occurrences in the array)

I came up with this linear divide and conquer algorithm, but I'm not sure if it's correct. It returns an array with two elements, the name of the majority element and a number that is less than or equals to its occurrences. Can someone help to prove/disprove it?

def findMajority(arr):
    if len(arr) == 1:
        return [arr[0], 1]
    else:
        leftHalf = findMajority(arr[:len(arr)/2])
        rightHalf = findMajority(arr[len(arr)/2:])

        if leftHalf[0] is None and rightHalf[0] is not None: #Left half is indeterminate
            return [rightHalf[0], rightHalf[1]]

        if leftHalf[0] is not None and rightHalf[0] is None: #Right half is indeterminate
            return [leftHalf[0], leftHalf[1]]

        if leftHalf[0] is None and rightHalf[0] is None: #Both halves are indeterminate
            return [None, 0]

        if leftHalf[0] == rightHalf[0]: #Majority in both halves is the same
            return [leftHalf[0], leftHalf[1] + rightHalf[1]]

        elif leftHalf[1] < rightHalf[1]: #Right majority has more occurrences
            return [rightHalf[0], rightHalf[1]]

        elif leftHalf[1] > rightHalf[1]: #Left majority has more occurrences
            return [leftHalf[0], leftHalf[1]]

        else: #There is no winner between the two halves and they have equal occurrences
            return [None, 0]

EDIT: It returns the wrong answer for [2,2,2,2,1,1,1,0,1,1,1,0,1,1,1,0]
. So it doesn't work.

It's not correct. On input [a a b c], the left side yields [a, 2], the right side yields [nil, 1]. They would be merged into [a, 2].

I'll outline a linear time solution. If there exists a value $x$ such that more than $n/2$ of the elements of $A$ have value $x$, then certainly the $n/2$-th order statistic of $A$ must be $x$. The selection problem is solved in linear time using, for example, median of medians; checking that such value does indeed appear at least $n/2$ times is trivially linear time.


Reducing products in HoTT to church/scott encodings So I am currently going though the HoTT book with some people. I made the claim that most inductive types we will see can be reduced to types containing only dependent function types and universes by taking the type of the recuror as inspiration for the equivalent type. I started to sketch how I thought this would work and after some stumbling I came to what I thought was an answer.

$$\cdot \times \cdot \equiv \prod_{A, B, C : \mathcal{U}} (A \to B \to C) \to C$$
$$ (\cdot, \cdot) \equiv \lambda a : A. \lambda b : B. \lambda C : \mathcal{U}. \lambda g : A \to B \to C. g(a)(b)$$
$$ ind_{A \times B} \equiv \lambda C. \lambda g. \lambda p. g(pr_1(p))(pr_2(p)) $$

This gives the correct defining equations (defining equations for $pr_1$ and $pr_2$ omitted) but this would mean that $ind_{A \times B}$ would have the wrong type.

$$\text{ind}_{A \times B} : \prod_{C : A \times B \to \mathcal{U}} (\prod_{a:A} \prod_{b:B} C((a, b))) \to \prod_{p : A \times B} C((pr_1(p), pr_2(p)))$$

And there doesn't seem to be a simple fix to this. I also thought about the following definition.

$$ ind_{A \times B} \equiv \lambda C. \lambda g. \lambda p. p(C(p))(g) $$

But this just doesn't typecheck.

Another idea I had is to use $uniq_{A \times B}$ to convert $C((pr_1(p), pr_2(p)))$ to $C(p)$ but it's not clear how to make that work. First off I'd have to show how to reduce identity types dependent function types which is proving even harder in my scribblings than products. Additionally $uniq_{A \times B}$ doesn't seem to be definable without the proper form of induction so even if I allowed myself identity types as presented in the book I'd be no closer to having a definition of $uniq_{A \times B}$

So it seems like we can define the recursor here but not the inductor. We can define something that's pretty close to looking like the inductor but doesn't quite make it. The recursion lets us perform logic taking this type to be the meaning of logical conjunction but it doesn't let us prove things about products which seems lacking.

Can we make the sort of reduction I claimed can be made? That is, can we define a type using only dependent function types and universes that has a pairing function and inductor with the same defining equations and types as products? It's my growing suspicion that I made a false claim. It seems like we're able to get so frustratingly close but just not quite make it. If we can't define it what kind of argument explains why we can't? Do products as presented in the HoTT book increase the strength of the system?

The standard reference I often give is Induction is not derivable in second order dependent type theory by Herman Geuvers, which says that there is no type

$$N : \mathrm{Type}$$

with functions
$$Z:N\qquad S:N\rightarrow N $$

such that

$$\mathrm{ind}:\Pi P:N\rightarrow \mathrm{Type}.P\ Z\rightarrow (\Pi m:N.P\ m\rightarrow P\ (S\ m))\rightarrow \Pi n:N. P\ n $$

is provable. This suggests that indeed, such an encoding cannot work for pairs as you describe.

The system this is proven for is a subset of the Calculus of Constructions, which contains powerful product types and a universe. I suspect this result can be extended to the system you are interested in, depending on what you have.

Sadly, I don't know the complete answer to your question. I suspect that adding certain parametricity principles "internally" is exactly what is required to make these encodings work with the full induction principle. Neel Krishnaswami, whose knowledge is a strict superset of my own, wrote a paper along these lines with Derek Dreyer:

Internalizing Relational Parametricity in the Extensional Calculus of Constructions

Also of interest is the following paper by Bernardy, Jansson and Patterson (Bernardy has thought deeply about these topics):

Parametricity and Dependent Types

Obviously parametricity has a strong relationship with HoTT in general, but I don't know what the details are. I think Steve Awodey has considered these questions, since the encoding trick is useful in contexts where we don't really know what the eliminators should look like.


Number of n-node binary trees containing an m-node binary subtree In a paper I see the following lemma about unlabeled binary trees:

  If $s_1$ and $s_2$ are both m-node binary trees, then the number of n-node binary trees containing $s_1$ as a subtree is the same as the number of n-node binary trees containing $s_2$.

It goes on to use this to show that if you want to compute the number of n-node binary trees that have m-node as a subtree, it doesn't matter what m-node tree you use.

I feel like I'm either misinterpreting this or missing something obvious. But isn't the following setup a contradiction to this lemma:

Nodes 2a and 6a produce the same tree, so tree 1 is only the subtree of 5 4-node trees while tree 2 is a subtree of 6 4-node trees.

You haven't defined what a subtree is, so let's assume that $S$ is a subtree of $T$ if there is a node $x \in T$ whose subtree is isomorphic to $S$ (the notion of isomorphism depends on the definition of subtree).

Now suppose $S_1,S_2$ are two trees on $m$ of vertices. For any tree $T$, mark all the nodes whose subtrees contain $m$ vertices. Define $\pi(T)$ by replacing all such nodes whose subtree is isomorphic to $S_1$ by a subtree isomorphic to $S_2$, and vice versa. For any $n$, this is an involution on the set of trees on $n$ vertices which satisfies the following property: $T$ contains $S_1$ iff $\pi(T)$ contains $S_2$. This shows that the number of trees of size $n$ containing $S_1$ is the same as the number of trees of size $n$ containing $S_2$.


Is this grammar LL(1)? Consider following grammar:

$$X\to Yc|ZY$$

$$Y\to ab|cX$$

$$Z\to d|\epsilon$$

Can this be converted to LL(1)?

Cleary, its not LL(1) because of First/First conflict at first production. Can anyone suggest something to make it LL1?

I would do it the following way:

First remove the Z production:

X-> Yc | dY | Y

and leave the others intact. Now you still have the First/First conflict, but you don't need to descent to the epsilon.

Next step, introduce a new symbol Y' for deciding wether to read a c or not.

 X-> YY' | dY
 Y' -> c | epsilon
 Y -> ab|cX

now you have a first/follow conflict. How to solve that:

Let's take a look at the produced language(Assuming X is the Start symbol) and transform the grammar:

L(G) = abc or c^n ab d ab..

X-> cX| ab |abY |dX

this should be LL(1).


Peer grading design - choosing a graph, to get accurate rankings/ratings Background. I am writing some code for semi-automated grading, using peer grading as part of the grading process. Students are given pairs of essays at a time, and the students have a slider to choose which is better and how much better it is.  e.g., the slider might look something like this:

A---X-B

Based on the results of the peer grading, essays are ranked and the teacher will then grade the top X% and bottom X% and scores for all essays will be automatically calculated based on this.  I have already come up with methods for doing this ranking/scoring process; that part works well.

My question. How should I select which pairs of essays to give to students?

Simulations suggest we need an essay to be peer-graded at least 3 times, to get an accurate ranking.  Thus, each essay should appear in at least 3 of the pairs that are presented for peer grading.

We can think of this as a graph problem.  Think of the essays as nodes.  Each edge represents a pair of essays that are presented during the peer grading process.  The accuracy results above suggest that the degree of each node (or of most nodes) should be at least 3.  What sort of graph should I use?  How should I generate the graph to be used during peer grading?

One challenge is that if you have clusters in the graph, this will skew the peer-gradings.  For example, we wouldn't want to have high-quality essays peer-graded mostly against high-quality essays, because that would skew the results of the peer grading.

What would you recommend?

I think this problem could be modelled with a undirected graph using something like the following:

Start by taking the node with the least degree and link it with the next least
Continue until your average degree is at least 3
Maximise node connectivity
Minimise number of cliques

Is this a good approach? If not what would you recommend instead?

There are two parts to this: (a) selecting a graph (experimental design) to determine which pairs of essays the students will evaluate in the peer grading process, and (b) ranking all the essays, based upon the student's peer grades, to determine which the teacher should rank.  I will suggest some methods for each.

Choosing a graph

Problem statement.  The first step is to generate a graph.  In other words, you need to select which pairs of essays to show to the students, during the peer grading exercise.

Suggested solution. For this task, I suggest that you generate a random graph $G$, selected uniformly at random from the set of all 3-regular (simple) graphs.

Justification and details.  It is known that that a random $d$-regular graph is a good expander.  In fact, the regular graphs have asymptotically optimal expansion factor.  Also, because the graph is random, this should eliminate the risk of skewing the grading.  By selecting a graph uniformly at random, you are ensuring that your approach is equally fair to all students.  I suspect that a uniformly random 3-regular graph will be optimal for your purposes.

This raises the question: how do we select a 3-regular (simple) graph on $n$ vertices, uniformly at random?

Fortunately, there are known algorithms for doing this.  Basically, you do the following:

Create $3n$ points.  You can think of this as 3 copies of each of the $n$ vertices.  Generate, uniformly at random, a random perfect matching on these $3n$ points.  (In other words, repeat the following procedure until all $3n$ points are paired off: select any unpaired point, and pair it with another point chosen uniformly at random from the set of unpaired points.)
For each two points that are matched by the matching, draw an edge between the corresponding vertices (that they are a copy of).  This gives you a graph on $n$ vertices.
Next, test if the resulting graph is simple (i.e., it has no self-loops and no repeated edges).  If it is not simple, discard the graph and go back to step 1.  If it is simple, you are done; output this graph.

It is known that this procedure generates a uniform distribution on the set of 3-regular (simple) graphs.  Also, it is known that at step 3 you have a constant probability of accepting the resulting graph, so on average the algorithm will do $O(1)$ trials -- so this is pretty efficient (e.g., polynomial running time).

I have seen this approach credited to Bollobas, Bender, and Canfield.  The approach is also summarized briefly on Wikipedia.  You can also find a discussion on this blog post.

Technically speaking, this requires that the number $n$ be even (otherwise there is no 3-regular graph on $n$ vertices).  However, this is easy to deal with.  For instance, if $n$ is odd, you can randomly choose one essay, set it aside, generate a random 3-regular graph on the remaining essays, then add 3 more edges from the set-aside essay to 3 randomly chosen other essays.  (This means that there will be 3 essays that are actually graded 4 times, but that shouldn't do any harm.)

Ranking all the essays

Problem statement.  OK, so now you have a graph, and you have presented these pairs of essays (as indicated by the edges in the graph) to the students for them to grade during the peer grading exercise.  You have the results of each comparison of essays.  Now your task is to infer a linear ranking on all of the essays, to help you determine which ones to have the teacher evaluate.

Solution. I suggested you use the Bradley-Terry model.  It is a  mathematical approach that solves exactly this problem.  It was designed for ranking players in some sport, based upon the results of matches between some pairs of the players.  It assumes that each player has an (unknown) strength, which can be quantified as a real number, and the probability that Alice beats Bob is determined by some smooth function of the difference of their strengths.  Then, given the pairwise win/loss records, it estimates the strength of each player.

This should be perfect for you.  You can treat each essay as a player.  Each comparison between two essays (during the peer grading process) is like the result of a match between them.  The Bradley-Terry model will allow you to take all of that data, and infer a strength for each essay, where higher strengths correspond to better essays.  Now you can use those strengths to rank-order all of the essays.

Details and discussion. In fact, the Bradley-Terry model is even better than what you asked for.  You asked for a linear ranking, but the Bradley-Terry model actually gives a (real-number) rating to each essay.  This means you know not only whether essay $i$ is stronger than essay $j$, but a rough estimate of how much stronger it is.  For instance, you could use this to inform your selection of which essays to rank.

There are alternative ways to infer ratings or rankings for all the essays, given the data you have.  For instance, the Elo method is another.  I summarize several of them in my answer to a different question; read that answer for more details.

One other comment: The Bradley-Terry model assumes that the result of each comparison between two players is a win or a loss (i.e., a binary result).  However, it sounds like you will actually have more detailed data: your slider will give a rough estimate of how much better the peer grader rated one essay than another.  The simplest approach would be to just map each slider to a binary result.  However, if you really want, you might be able to use all of the data, by using a more sophisticated analysis.  The Bradley-Terry model involves doing logistic regression.  If you generalize that to use ordered logit, I bet that you could take advantage of the extra information you have from each slider, given that the results from the sliders are not binary but are one of several possibilities.

Efficient use of the teacher

You suggest having the teacher manually grade the top X% and bottom X% of all of the essays (using the ranking inferred from the results of the peer-grading).  This could work, but I suspect it is not the most efficient use of the teacher's limited time.  Instead, I'd like to suggest an alternate approach.

I suggest that you have the teacher grade a subset of the essays, with the subset carefully selected to try to provide the best possible calibration for all of the essays that weren't graded by the teacher.  For this, I think it might help if you selected a sample of essays that cover the range of possible answers (so for every essay, there is some teacher-graded essay that is not too far away from it).  For this, I can think of two approaches you could consider trying:

Clustering. Take the ratings that are produced by the Terry-Bradley model.  This is a set of $n$ real numbers, one real number per essay.  Now cluster them.  Suppose you want to have the teacher grade $k$ essays.  One approach would be to use $k$-means clustering (on these one-dimensional data points) to cluster the essays into $k$ clusters, and then randomly select one essay from each cluster for the teacher to grade -- or have the teacher grade the "cluster head" of each cluster.
Furthest-point first. An alternative is to try to select a subset of $k$ essays that are as different from each other as possible.  The "furthest-point first" (FPF) algorithm is a clean approach for this.  Assume that you have some distance function $d(e_i,e_j)$ that lets you quantify the distance between two essays $e_i$ and $e_j$: a small distance means that the essays are similar, a larger distance means they are dissimilar.  Given a set $S$ of essays, let $d(e,S) = \min_{e' \in S} d(e,e')$ be the distance from $e$ to the nearest essay in $S$.  The furthest-point first algorithm computes a list of $k$ essays, $e_1,e_2,\dots,e_k$, as follows: $e_{i+1}$ is the essay that maximizes $d(e,\{e_1,e_2,\dots,e_i\})$ (out of all essays $e$ such that $e \notin \{e_1,e_2,\dots,e_i\}$).  This algorithms generates a set of $k$ essays that are as dissimilar from each other as possible -- which means that each of the remaining essays is pretty similar to at least one of those $k$.  Therefore, it would be reasonable to have the teacher grade the $k$ essays selected by the FPF algorithm.

I suspect either of these approaches might provide more accurate scores than having the teacher grade the top X% and bottom X% of essays -- since the very best and worst essays probably are not representative of the mass of essays in the middle.

In both approaches, you could use a more sophisticated distance function that takes into account not just the strength estimates based upon peer grading but also other factors derived from the essays.  The simplest possible distance function would take into account only the result of the Terry-Bradley model, i.e., $d(e_1,e_2) = (s(e_1)-s(e_2))^2$ where $s(e)$ is the strength of essay $e$ as estimated by the Terry-Bradley model based upon the results of the peer grading.  However, you can do something more sophisticated.  For instance, you could compute the normalized Levenshtein edit distance between essay $e_1$ and $e_2$ (treating them as text strings, computing the edit distance, and dividing by the length of the larger of the two) and use that as another factor in the distance function.  You could also compute feature vectors using a bag-of-words model on the words in the essays, and use the L2 distance between these feature vectors (with features normalized using tf-idf) as another factor in the distance function.  You might use a distance function that is a weighted average of the difference in strengths (based upon the Terry-Bradley estimates), the normalized edit distance, and anything else that seems helpful.  Such a more sophisticated distance function might help do a better job of helping the clustering algorithm select which are the best $k$ essays to have the teacher grade.


Generating number of possibilites of popping two stacks to two other stacks Context: I'm working on this problem:

  There are two stacks here:

A: 1,2,3,4 <- Stack Top
  B: 5,6,7,8

  A and B will pop out to other two stacks: C and D. For example:

 pop(A),push(C),pop(B),push(D).

  If an item have been popped out , it must be pushed to C or D immediately.

The goal is to enumerate all possible stack contents of C and D after moving all elements.

More elaborately, the problem is this: If you have two source stacks with $n$ unique elements (all are unique, not just per stack) and two destination stacks and you pop everything off each source stack to each destination stack, generate all unique destination stacks - call this $S$.

The stack part is irrelevant, mostly, other than it enforces a partial order on the result. If we have two source stacks and one destination stack, this is the same as generating all permutations without repetitions for a set of $2N$ elements with $N$ 'A' elements and $N$ 'B' elements. Call this $O$.

Thus

$\qquad \displaystyle |O| = (2n)!/(n!)^2$

Now observe all possible bit sequences of length 2n (bit 0 representing popping source stack A/B and bit 1 pushing to destination stack C/D), call this B. |B|=22n. We can surely generate B and check if it has the correct number of pops from each destination stack to generate |S|. It's a little faster to recursively generate these to ensure their validity. It's even faster still to generate B and O and then simulate, but it still has the issue of needing to check for duplicates.

My question

Is there a more efficient way to generate these?

Through simulation I found the result follows this sequence which is related to Delannoy Numbers, which I know very little about if this suggests anything.

Here is my Python code

def all_subsets(list):
    if len(list)==0:
        return [set()]
    subsets = all_subsets(list[1:])

    return [subset.union(set([list[0]])) for subset in subsets] + subsets

def result_sequences(perms):
    for perm in perms:
        whole_s = range(len(perm))
        whole_set = set(whole_s)
        for send_to_c in all_subsets(whole_s):
            send_to_d = whole_set-set(send_to_c)
            yield [perm,send_to_c,send_to_d]

n = 4
perms_ = list(unique_permutations([n,n],['a','b'])) # number of unique sequences
result = list(result_sequences(perms_))

(answer for another problem, see the edit below)

First, generate all subsets $A_1$ of $A$. $A_1$ will go in $C$ and $A_2=A\backslash A_1$ in $D$. Likewise, generate all subsets $B_1$ of $B$. You then have to generate all possible ordered combinations of $A_1$ and $B_1$ for $C$ and the same for $A_2$ and $B_2$ in $D$.

This amounts to enumerate, given $(a_1,…,a_n)$ and $(b_1,…,b_m)$ all interleavings of length $n+m$ which can be viewed as an exploration of the intersections of a grid of size $n×m$. (There are $\frac{(n+m)!}{n!m!}$ paths)

This is a way of generating all possible $C$s and $D$s uniquely.

But maybe I misunderstood the question. Is this what you want? To help comparing with what you already have tried, here is the number of pairs of stacks it generates (where $A$ is the size of $A$):

$$N(A,B)=\sum_{n=0}^{A}\sum_{m=0}^{B}\binom{A}{n}\binom{B}{m}\frac{(n+m)!}{n!m!}\frac{(A+B-n-m)!}{(A-n)!(B-m)!}$$

Formula when $A=B$ on the OEIS.
Implementation in Haskell
Execution trace for A=["a", "b"] B=["1", "2"] with 54 pairs since $N(2,2)=54$

EDIT: I am wrong: my algorithm behaves like separating $A$ and $B$ into $(A_1,A_2)$ and $(B_1,B_2)$ before interleaving $(A_1,B_1)$ and $(A_2,B_2)$ which is presumably what you don't want (it generates too many stacks, e.g. from $A=[2,1], B=[4,3]$ it includes $C=[2,3],D=[4,1]$).

(Mitchus's answer does not have this problem.)


Why linear transformation can improve classification accuracy when the dimensionality of data is high? Let $X$ be an $m\times n$ ($m$: number of records, and $n$: number of attributes) dataset.  When the number of attributes $n$ is large and the dataset $X$ is noisy, classification gets more complicated and the classification accuracy decreases. One way to over come this problem is to use linear transformation, i.e., perform classification on $Y=XR$, where $R$ is an $n\times p$ matrix, and $p\leq n$. I was wondering how linear transformation simplifies classification? and why classification accuracy increases if we do classification on the transformed data $Y$ when $X$ is noisy?

Multiplying by the $n * p$ matrix decreases the dimensionality of the data set.  Think of this as projecting the highly dimensional space into a smaller dimensional space.  For example, you could do principle component analysis and project it into a small space.  This way things that are correlated together are projected into the same dimension and if one of those correlated dimensions is off because of noise, then it would be cancelled out by the values in the other correlated dimensions.

You have to choose your matrix $R$ in a way that essentially averages together things that reinforce each other and reduce noise.  Principle component analysis is one way of choosing such a matrix.


On importance of Stockmeyer theorem Theorem: (Stockmeyer, 1974)  Any circuit that takes as input a formula
  (in the language of WS1S) with up to 616 symbols and produces as
  output a correct answer saying whether the formula is valid or not,
  requires at least $10^{123}$ gates.

Suppose we have generalized theorem: Any circuit that takes as input a formula
with up to $n$ symbols and produces as output a correct answer saying whether the formula is valid or not, requires at least $10^n$ gates. Is this true that this theorem equivalent to statement that P is not equal to coNP?

The theorem is false. There is a circuit of size $\tilde{O}(2^n)$ that solves SAT. At any rate, the relevant conjectures you would be proving using statements of this form are the Exponential time hypothesis and its variants.


Are $\log_{10}(x)$ and $\log_2(x)$ in the same big-O class of functions? Are $\log_{10}(x)$ and $\log_{2}(x)$ in the same big-O class of functions? In other words, can one say that $\log_{10}(x)=O(\log x)$ and $\log_{2}(x)=O(\log x)$?

Yes. Because they differ only by a constant factor. Remember high school math:

$\log_2 x = \dfrac{\log_{10} x}{\log_{10}2}$.


If all edges are unweighted AND DIRECTED, can one use BFS to obtain a MST? I've looked through CS SE and I've found a page that said you could find use BFS to find a MST if the edges are unweighted, but what if the edges are directed?

Given a directed graph between V vertices, I'm trying to find the minimum directed edges I need to add in order for every vertex to be connected to every other vertex.

Is MST the way to go? Or, is there another way I'm not thinking of.

I apologize if this question is too easy, as I am very new to programming. I appreciate any help. Thanks!

This is known as an arborescence.  There are algorithms for this problem, such as the Chu-Liu/Edmonds algorithm, but they are more complex than just doing a BFS.  See also https://stackoverflow.com/q/21991823/781723.


Can PDA accept only by final state without finish reading input? I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the input is read fully or not).
I can guess PDA with the new definition of acceptance is less powerful, and easy to see every language accepted by this PDA is accepted by some PDA with the conventional definition. But, can anyone give some idea how to show some languages are not accepted by the new PDA?

Prefixes.
How would you accept both $a$ and $aa$ ?


Pumping Lemma for regular language for $a^n$ where $n$ is even fails $$L=\{a^n \mid \text{\(n\) is even}\}$$

This is regular but fails in the pumping Lemma.

Assuming $m=4$, $w=aaaaaa$, $|w|=6$ (even).
Let $w=xyz$,
$x=a$,
$y=aaa$.
We have $|y|>0$ and $|xy| \le m$.

Let $w_i=xy^iz$.
For $i=2$,
$w_2=xy^2z=aaaaaaaaa$.
$|w_2|=9$ therefore it is not regular.

Where am I going wrong?

The pumping lemma states that:
there exists a pumping length $p$
such that for any word $w \in L$ of length $|w| \ge p$,
there exists a decomposition $w = xyz$
meeting certain properties.

There are two errors in your proof. The first is that the lemma states that there exists a pumping length $p$ but doesn't say how to compute it; you assume without proof that $6$ is a valid pumping length. This makes your proof incomplete, but it is not actually wrong: the pumping length can be anything larger than the number of nodes in the smallest finite automaton that recognizes the language, and this language can be recognized by an automaton with just two states, so any $p \ge 2$ is ok.

The fatal mistake is that you don't get the choice of the decomposition. There has to be some decomposition $w = xyz$ such that $\forall i, xy^iz \in L$. The one you picked doesn't work. In order to prove that the language isn't regular, you'd need to prove that no decomposition works. But there is a decomposition that works: take $x = aa$, $y = aa$, $z = aa$ (or any decomposition where $|y|$ is even).

You might have gotten confused with what happens when proving that a language is not regular. When proving the negation, the quantifiers are reversed: to prove that a language is not regular using the pumping lemma, we usually assume that the pumping lemma holds, so we assume the pumping lemma, and in particular we assume that for any sufficiently large word, there exists a decomposition meeting the properties, and we deduce a contradiction from that. Here, you're trying to deduce that the pumping lemma holds.


Time Complexity of Halley's Method What is the time complexity of Halley's Method?

I am thinking ${\cal O}(\log(n)F(n))$, or something very similar to Newton-Raphson, but I feel as though there should be some change to the complexity in order to yield the greater convergence. However, I can't seem to find any solid ground to support any of my ideas (as nobody has ever seemed to have asked this question on the internet before)...

Halley's Method - Wikipedia

I'm assuming $n$ is the accuracy needed (in bits). Assuming that your starting point is reasonable, you converge in $O(\log n)$ iterations, just as in Newton's method. The absolute number of iterations is smaller than in Newton's method — Newton's method converges in $\log_2 n$ rounds, Halley's in $\log_3 n$ rounds (roughly speaking). However, this difference is lost in big O notation. For this reason, when analyzing methods like this, it is more meaningful to count function evaluations, keeping in mind that derivatives (and second derivatives in the case of Halley's method) may have a different complexity than the function itself.


Is my proof of my greedy algorithm to find subsequence correct? Credit to KleinBerg and Taros Book

Some of your friends have gotten into the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. Purchases at stock exchanges—what’s being bought— are one source of data with a natural ordering in time. Given a long sequence $S$ of such events, your friends want an efficient way to detect certain “patterns” in them—for example, they may want to know if the four events:

{buy Yahoo, buy eBay, buy Yahoo, buy Oracle}

occur in this sequence $S$, in order but not necessarily consecutively. They begin with a collection of possible events (e.g., the possible transactions) and a sequence $S$ of $n$ of these events. A given event may occur multiple times in $S$ (e.g., Yahoo stock may be bought many times in a single sequence S). We will say that a sequence $S'$ is a subsequence of $S$ if there is a way to delete certain of the events from S so that the remaining events, in order, are equal to the sequence $S'$. So, for example, the sequence of four events above is a subsequence of the sequence

{buy Amazon, buy Yahoo, buy eBay, buy Yahoo, buy Yahoo, buy Oracle}

Their goal is to be able to dream up short sequences and quickly detect whether they are subsequences of $S$. So this is the problem they pose to you: Give an algorithm that takes two sequences of events—$S'$ of length $m$ and $S$ of length $n$, each possibly containing an event more than once—and decides in time $O(m+n)$ whether $S'$ is a subsequence of $S$.

Here is my pseudocode to this solutions:

set i and j to 1
when i <= S.length & j <= S'.length{
    if S(i) is the same as S'(j)
    then increment i and j by 1
    else just increment i
}
if ( j > S'.length) {
    return true
else
    false

My proof of correctness of optimality:

Let $A = (j_1,\cdots,j_m)$ be the sequence found by our greedy solution and hence return true, and let $B = (l_1,\cdots,l_n)$, be the sequence found by an optimal solution and also returns true.

We prove by induction that the greedy algorithm will succeed in returning true if a match was found and will ensure that $j_m \ge l_n$, showing that the greedy is as optimal as the optimal solution.

Base:
Consider the case where $m = 1$ and $n = 1$, then the algorithm let $j_1$ of $A$ and $l_1$ of $B$ be the first events found and hence $j_1 >= l_1$.

IH:
Now the case where $m > 1$ and $n > 1$, and assume $m-1 < A.\text{length}$ and $n-1 < B.\text{length}$, and by the IH, we have found events matching the subsequence and hence also $j_{m-1}$ and $l_{n-1}$, has a match, giving use $m-1 \ge n-1$. Knowing that the next for either solutions would be at $j_m$ and $l_n$ and hence $A=B$, and hence $j_m \ge ln$. Hence the greedy is as good as the optimal.
///

Would this be a way to prove the optimality as I cannot find another optimal that takes more than $O(n+m)$, hence just showing that the optimal and greedy would give the same result.?? Very confused.

Thanks in advance.

A post that requests us to check if a solution to a problem is correct is off-topic in general, especially when the solution is correct. However, in the current case, there are a couple of minor conceptual misunderstandings in this question, which I would like to address.

  Would this be a way to prove the optimality as I cannot find another optimal that takes more than $O(n+m)$, hence just showing that the optimal and greedy would give the same result?

What is "the optimality"? In the original problem, there is no requirement of any kind of optimality. The requirements are

the algorithm should decide whether $'$ is a subsequence of $$.
the algorithm should run in time $(m+n)$.

Although your algorithm looks like a greedy algorithm, the quantity or the objective function that should be optimized is never defined. So, it makes little sense to "prove the optimality" of your algorithm. It does not, in fact, make much sense to say that your algorithm is a greedy algorithm without specifying the objective function! That is probably the source of your confusion. That is why your proof seems unclear and dangling at a few places, since your proof is only a proof of correctness.

On the other hand, we can list three objective functions. For one of them, your algorithm is the optimal algorithm. For the other two, your algorithm becomes a greedy and correct algorithm.

I will state the objective functions in the form of three easy exercises. Hopefully you will not be confused any more.

Exercise 1. Show that your algorithm run in $O(m)$ time. Show that any algorithm that finds $S'$ will run at least in $\Theta(m)$ time in worst cases. (Note that $O(m+n)$ cannot be used here unless we assume $m\ge n$, in which case $O(m)=O(m+n)$.)

Exercise 3. For each subsequence $sub=(S_{i_1}, S_{i_2}, \cdots, S_{i_k})$ of $S$, define its finishing index $FI(sub)=i_k$. Show that your algorithm is a greedy algorithm that finds a subsequence of S that is the same as $S'$ with the minimum finishing index if there is a subsequence that is the same as $S'$.

Exercise 3. For each subsequence $sub=(S_{i_1}, S_{i_2}, \cdots, S_{i_k})$ of $S$, define its total index $TI(sub)=i_1+i_2+\cdots+i_k$. Show that your algorithm is a greedy algorithm that finds a subsequence of S that is the same as $S'$ with the minimum total index if there is a subsequence that is the same as $S'$.


Number of submatrices with a particular sum Given a $n\times n$ matrix A[0...n-1][0....n-1] where all entries are non-negative integers, and a non-negative integer K, I want to find the number of submatrices whose entries sum to K.

The best solution I can find has $O(n^4)$ running time.  Any ideas how to improve the running time?

Here is an O(N3) algorithm (it is valid only for matrices of non-negative values).

Compute prefix sums for each column: B[k][j] = Sum(A[0..k][j]).
For each pair of row indices (p, q):
Apply a two-pointers algorithm for implicit array of values B[q][j]-B[p][j].

Where a two-pointers algorithm advances first pointer while sum of values between pointers is less than desired and advances second one when this sum is greater than desired. When the desired sum is found, advance first pointer (x times) while sum does not change and advance second pointer (y times) while sum does not change (we might need to advance pointers more then once in case of sub-matrix column summing to zero), then add x*y to counter of found sub-matrices and continue.


Given 2 sets of n points: minimize sum of traveled distances I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean distance.

I am aware that this transportation problem is a special case of the earth mover distance problem, but since its unweighted (and over points) I am wondering if there is a more efficient algorithm than the cubic time hungarian method for it?

As mentioned in the problem statement, this is the Assignment Problem (minimum weight bipartite matching) where it is known that the weights are the Euclidean distances.

There have been several improvements since the Hungarian Algorithm, at least in terms of asymptotic bounds.  Depending on the exact size of the graph, any of several algorithms may be the best.  A table in the paper by Cohen, et al gives details.  Edmonds and Karp's algorithm is $O(nm + n^2 log n)$, and is still the best bound that doesn't depend on the maximum weight in the graph.  Cohen's algorithm appears to be the best for sparse graphs, which is not your situation.  I think the best for your dense graph would be Sankowski's $\tilde{O} (W n^\omega)$, since it doesn't depend on $m$.

I do not know if there are ways to exploit this problem's specific weight structure (Euclidean distances) for further improvements.

Sources:

Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in $\tilde{O}(m^{(10/7)} log W)$ Time.
Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu
https://arxiv.org/abs/1605.01717v3 (preprint)

J. Edmonds and R.M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow
Problems. J. ACM, 19(2):248–264, 1972.

Piotr Sankowski. Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, chapter Weighted Bipartite Matching in Matrix Multiplication Time, pages 274–285. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
http://link.springer.com/chapter/10.1007%2F11786986_25


Building cycle in rectangle I have to build a cycle with fixed length $n$ that includes exactly $k$ corners inside $w$ x $h$ rectangle.

For example:
$w = 5\\h=3$

$n = 12\\k = 6$

I have already found out that I need at least $4$ corners and number of corners and number of non-corner elements needs to be even number.

Then I write an recursive algorithm that runs in exponential time complexity, but I have a strong feeling that this thing can be done much faster.

Problem is that I do not know which square will definitely be in the cycle so I run my algorithm on first $\frac w2$ fields to cover all chances, but I am aware that I search some branches multiple time.

I have also discovered that if the cycle exist it will start with corner in (0, 0) or corner in (0, 1)

Does anybody have an idea on how to speed this thing up?

Have a nice day!

your problem looks inherently exponential to me to find all the solutions. a rough sketch to show that is to create a large # of similar-looking objects. the objects are the same under translation and rotation. they (apparently?) can also be scaled. so in a rough sense there is no way to "speed it up" if you already have an exponential time algorithm. you ask for a better algorithm but also ask for general ideas. here are some ideas/ suggestions.

youve abstracted the problem but it might help to step back and describe the background that inspired it. is it from some field in particular? chances are there are papers that study the general area.
it looks like its in NP because its easy to verify solutions. think of solving it in terms of NP. a canonical problem in this area is the satisfiability problem. many problems have been converted to it and SAT solvers are "state of the art" for solving NP problems. SAT solvers can discover and handle the intrinsic symmetries in the problem not technically "efficiently" (in the sense of guaranteed P time) but in the "most efficient way known" based on heuristics, "best practices", and decades of optimization research/ theory. so consider translating it to SAT and studying it that way.
if you want a general idea of the algorithm behavior you can run it at different scales and graph the # of solutions to find basic scaling properties.
if you just want any solution, you might try a probabilistic approach where you lay down a simple starting shape say square/ rectangle and then randomly alter it until it gets closer to your requirements. see eg heuristics. genetic algorithms are also good for this. you can encode the shape in terms of genetic coding.
imagine a triangular shape that has 2 straight sides at right angles and then a 3rd that is diagonal and has any # of corners required. its not an "efficient" use of space because it has a large open area but it satisfies your criteria and can be created at any scale with arbitrary # of corners. you didnt specify any criteria about minimizing or maximizing space inside or outside. so maybe this is a bit underconstrained as stated.
actually think this might need to be described better. are you touching squares only at the edges squares and the squares touching those edge squares? what do you mean by "corners"? corners on your object? corner squares on the rectangle? you give only one example so think your description is somewhat ambiguous or subject to misinterpretation on closer inspection.


Are there any compression algorithms based on PI? What we know is that π is infinite and quite likely it contains every possible finite string of digits (disjunctive sequence).

I've seen recently some prototype of πfs which assume that every file you've created (or anybody else) or you will create, it's already there so it's a matter of extracting it. There is also piFile which can convert your files to pi metadata.

There is already BBP type formula (as part of experimental mathematics) which allows us to compute nth binary digit of pi. So storing position of our start and length of the data, we can theoretically extract the data of our interest. There are some arguments against it that our metadata (e.g. the offset to our data) could be larger than the extracted data. The matrix symbols and π can be encoded in base-256 to make it more efficient (see the joke).

Based on above, my main question is:

Are there any compression algorithms based on PI?

If not, does it make sense? Or were there any researches in that area?

Or maybe π is not the right one, so what about Euler's constant or Tau (τ)? Would it make any difference?

Image credits: Dinosaur Comics

See also:

Can any finite bit string be found in pi within a reasonable amount of time? at SO
Wouldn't storing the index into π be as big (or bigger) than the original data? at GitHub

Your suggestion doesn't make much sense, for many reasons. First of all, when trying to compress a large file, say a file of size $16$ bytes, you will have to find a place in the binary expansion of $\pi$ which agrees with your file. Since the file is $128$ bits long, one would expect this place to be around the $2^{128}$th bit. So it would be rather hard to find. This is not only because we have to go far into the expansion, but also since we expect to try $2^{128}$ different locations before finding a hit.

Second, while in some cases your scheme will result in a major compression, this will only happen when a certain string appears comparatively early in the expansion of $\pi$. There is no reason you would ever want to compress that sort of string. In contrast, other compression algorithms try to find structure in the data, and have guarantees that show that if such a structure exists, then they can always exploit it.

Changing $\pi$ with any other number wouldn't change the picture. The algorithm is too specific, compressing only strings we aren't really interested in; and very inefficient in the compression phase.


partial (and non deterministic) functions in dependently typed lambda calculus A partial function is one, that that is only defined on a part of its domain.
Haskell gives examples: https://wiki.haskell.org/Partial_functions

My end goal is to express types

$$
\prod_{D:\mathcal{U}} D
\qquad\qquad\qquad\qquad
\prod_{\mathcal{A}:\mathfrak{A}} \mathcal{L}(\mathcal{A})
$$

The first type should simply represent sort of (polymorphic) choice functions which accecpt a type and return an element of that Type.
The second is assuming, that I can express the Type of Automata $\mathfrak{A}$
as well as the language $\mathcal{L}(\mathcal{A})$ accepted by automaton $\mathcal{A}$. Given an Automaton a function with the given pitype should Select a word accepted by it.

As far as I understand, in a basic dependently typed lambda calculus, both types suffer from the same problem:
Their elements can never be introduced. Neither is it possible to select an element from the type $\bot$ nor select a word accepted by an automaton that doesn't accept any words.

I was wondering, if partial functions may be a solution to that problem.
But how are partial functions are represented in a typed lambda calculus?
An easy way I can imagine would be to be to create expressions, that allow the introduction of partial functions, such that there simply are no computation rules for undefined inputs.

So my questions are:

Does that make any sence, and is it common to solve this kind of problem that way? Is there good literature?
If the approach seems legit, is it possible to distinguish partial function types $A \rightharpoonup B$ from regular ones $A \to B$?

Note on the purpose:
To be honest, I haven't formalized automata in any calculus, since for now I mostly would like to steal the concept and notation of dependent types and use them in my work to get across a concept.
But if what i will do isn't completely bogus, it would maybe at least leave open a possibility to formalize things later.

A choice function of type $\prod_{D:\mathcal{U}} D$ is meant to represent user input - which should be non deterministic .. so there would also be no congruence)

Bonus question: Can non-deterministic functions be represented in a calculus such that this may be expressed?

It is possible to take a typed lambda calculus and add general recursion or fixed points. See for instance Plotkin's PCF, or HOFL in Winskel's formal semantics book.

In that way, one keeps the type system but introduces partiality. This is a very common approach for Turing complete typed programming languages.

Of course, now the logic associated to the calculus via Curry-Howard is no longer consistent, since every type is inhabited (by non terminating terms). This is not a serious problem for programming.

If wanted, in the type system one could distinguish between terms involving general recursion (which might not terminate), and terms involving no recursion or some known-to-be-terminating one, like (higher-order) primitive recursion. Note that this will not separate the programs between "halting" and "non-halting", which is undecidable, but only between "statically known to halt" and "statically unknown to halt -- they might or might not".

I have not thought much about that, but intuitively a non-termination monad would fit nicely in such type system. With a non-deterministic monad, one can also address non-deterministic functions.

A final comment: after reading the question, I am actually more concerned about the posted automaton-based example than termination. With dependent types, one can use the $\Pi$-type of a selection function (as the one which was posted), which given an automaton return one of the accepted strings (or a "empty-language" token). However, let's keep in mind that when a dependent type system checks a term against such $\Pi$-type, the term must contain the recipe to generate the string, as well as a proof that such string is accepted by the automaton. The posted question, in my view, seems to forget about that -- as if the type system could check any algorithm correct (in the sense of returning an accepted string). This is not possible.


Is converting boolean formulas to sum-of-products a hard problem? My reasoning is as follows.

Every boolean formula can be expressed as a sum-of-products.
Every sum-of-produts is a list of minterms.
For each minterm, there is 1 combination of inputs that satisfy the formula.

So if I have the sum-of-products representation of a boolean formula I can tell if it satisfiable.

But that is the SAT problem, which is hard.

So the hard part of the 3 step procedure above must be transforming a boolean formula into a sum of products.

Is this reasoning right?

Your reasoning is correct.  Your "sum-of-products" is more commonly known as disjunctive normal form (DNF).  It is easy to show that conversion from conjunctive normal form (CNF) to DNF is NP-hard, so converting from general Boolean formulas to DNF can't be any easier.


The Inverse of a function with logic operators How would one be able to tell whether or not a function has an Inverse? I've got  a question in my discrete mathematics/ combinatorics class that asks whether or not the following function has an Inverse and if so give the Inverse.

{(p, q) | q =¬p}

where p and q are elements of the set {T,  F}  where T is tautology and F is contradiction.

I know for regular xy functions, it has an Inverse if it is one to one and also how to find the Inverse.  But how would I apply that knowledge to this question?

The above is an injective function so that means it has an Inverse but will that be p= ¬q?

Yup. We have $f(T)=F, f(F)=T$ so $f^{-1}(F)=T, f^{-1}(T)=F$, which means that $f^{-1}(q)=\lnot q$. In this case $f^{-1}=f$: they're the same function.


Determine if two edges of a graph cross? Is there a standard way to check if two edges of a graph cross? I'm having trouble coming up with an algorithm to do this, and any insight/intuition into how this can be done would be great.

To be clear, here's an example:

The algorithm would ideally return that the edge shared by 7 and 8 crosses with that between 5 and 11. Similarly for 11 and 10, 8 and 9.

If you don't care about time complexity, the following algorithm would do. Go over all pairs of edges. For each pair, we have to find whether the two segments intersect. There are two cases: the two segments have the same slope, or they don't have the same slope.

If they have the same slope, then they could be two segments on the same line, or they could belong to different lines. In the second case, they don't intersect. In the first case, this is a one-dimensional problem which is easy to solve (you can reduce it to checking whether two intervals on the real line intersect).

If the two segments have different slope, then the corresponding lines intersect at a unique point. It remains to find whether this point also belongs to both segments.

There are probably more efficient solutions out there, but this shows how to solve your problem in a naive way.


Gaussian distribution with condition? What does this expression mean?
Normal distribution with condition
I am reading a research paper and found the following expression (Eq.28 in the paper below).

It means a Gaussian distribution, but the mean component seems conditional probability-like expression $\it{\bf{s}}_t | \it{\bf{m}}_{b, t, m}^{(j)}$.
I have never seen this expression before and cannot find any info about it.
The variables $\it{\bf{s}}_t$ and $\it{\bf{m}}_{b, t, m}^{(j)}$ are both vectors and $\bf{\Sigma}_{b}$ is a covariance matrix.
Does anybody have an idea of what this expression means?
Original paper where the expression is.
The original paper can be found here: https://eprints.soton.ac.uk/437941/1/08340823.pdf
Thanks in advance.

$$\mathcal{N}(x|m,\Sigma)=(2\pi)^{-k/2}|\Sigma|^{-1/2}\exp\left(-2^{-1}(x-m)^T\Sigma^{-1}(x-m)\right)$$
where $x,m$ are vectors of dimension $k$, $\Sigma$ is a $k\times k$ matrix, $|\Sigma|$ is its determinant. The vector $m$ represents the mean of the multivariate normal, and $\Sigma$ the covariance matrix, which must be positive definite.


Terminology for reducing runtime of an algorithm by using a property of the problem? It is a very standard situation that we have a class of problems $P$, and a subclass $\tilde P\subset P$ which has a certain restricted property.

For example, $P$ could be the problem of searching through an arbitrary list of people for someone with height $1.8$ meters, while $\tilde P$ could be the same problem, except that it is known that the list is ordered by height.

Searching through an ordered list is far more efficient than through an arbitrary list.

My question is: what would be the term for an algorithm using/relying on a certain particular structure of the problem in order to run more efficiently than would be needed in the general case?

Or alternatively, what is the term for "omitting calculations" that are necessary to do in the general case but that can be omitted in the restricted problem case?

I'd call it "special-casing".

There are variations. Variation 1 would be: You examine the input, and if the input has a special form, then you use an algorithm that cannot handle every input, but only input like the one you detected.

Variation 2: You run an algorithm that will run fast, but will not be successful for every possible input. You may detect while you run the algorithm or after you ran it that it failed, and use a more general algorithm.

Variation 3: You run a general algorithm, knowing that it will be fast in some cases, and hope your case is a fast one.


Is this language $\{0^n1^m | (n+m) \text{is even}\}$ regular or not? $$L=\{0^n1^m | (n+m) \text{is even}\}$$

Using the pumping lemma ,
let me choose a valid string $W=0011$ $(n=2,m=2$ and $4$ is even$)$.
Let the number of states in the DFA ($C$) be $3$ (I find this step to be fishy)
$|W|\ge C$
Let $W=XYZ$
I choose $X=00,Y=1,Z=1$ such that $|xy| \le C ,|Y| \ge1$
So, for all $i$, $00(1)^{i}1$ should be in $L$
But when $i=2$,String $00111$ is not in $L$, hence this language is not regular.

But I came across a regular expression for the same language:

$$0(00)^*1(11)^*+(00)^*(11)^*$$
Is there a flaw in my pumping lemma or the regular expression? Someone please help me out.

You seem to have misunderstood the pumping lemma.

Taking the definition from Introduction to the Theory of Computation by Michael Sipser

  If $A$ is a regular language, then there is a number $p$ (the
  pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

  for each $i ≥ 0, xy^i z \in A$,
  $|y| > 0$, and
  $|xy| \le p$.

A few points:

The lemma only says that a pumping length $p$ exists. You do not get to choose the value of $p$. So, you cannot say that let $p=3$.
For every string $s$ in the language with length at least $p$, it may be divided into three pieces, $s=xyz$. Notice that this again talks only of the existence of a way to split $s$ into $xyz$ given that $A$ is regular. So, you do not get to choose how the string splits into $x$, $y$, and $z$ in the general case. Finding a split that does not satisfy the conditions does not show that the language is not regular. You need to find such a string that cannot be split as stipulated by the definition to show that a language is not regular.
Finally, the pumping lemma does not say what happens if $A$ is not regular. So, even a non-regular language may satisfy it, and the pumping lemma cannot be used to show that a language is regular.