As Yuval Filmus comments, your argument is flawed: just because a given algorithm is a SAT-solver doesn't mean that we can prove that it is a SAT-solver.

Technically, the same issue applies to the time bound - we can cook up a Turing machine which always runs in polynomial time iff ZFC is consistent - but this is easily avoidable: given a Turing machine $T$ and a polynomial $p$, we can form a machine $T[p]$ which behaves like $T$ except with the time bound $p$ artificially imposed: on input of length $n$, $T[p]$ simulates $T$ for $p(n)$-many steps and diverges if it hasn't halted within that time. We can decide whether a machine $S$ has the form $T[p]$ for some $T, p$, so if $T$ happens to be a SAT solver which operates in polynomial time $p$, then $T[p]$ is a polytime SAT solver which we can prove operates in polynomial time. The culprit is "is a SAT solver," for which there doesn't appear to be a similar trick.

The issue here is logical complexity. "Undecidability implies truth" holds for statements with verifiable counterexamples; these are the $\Pi^0_1$ statements.$^*$ The Goldbach conjecture is a good example: in order to be false, there would need to be a counterexample, and being a counterexample to Goldbach is an easily checkable property since it only relies on "bounded quantifiers." By contrast, the Twin Primes Conjecture is a priori merely $\Pi^0_2$, and so at the moment we don't have any reason to believe that its undecidability from (say) PA would imply its truth.

Even in the $\Pi^0_1$ context, however, undecidability is more than just a method for proving a statement. It establishes that the principle is true "for deep reasons" in some sense. If a statement $P$ about the natural numbers$^{**}$ is true but not PA-provable, this means that the reason $P$ is true is more complicated than just our simple intuitions about induction, since PA already incorporates the full arithmetical induction scheme. Now whether one consider this a worthwhile observation depends on one's particular interests, but it (and even weaker independence phenomena) is certainly noteworthy to me.

$^*$This is in fact an exact characterization, in the following sense. If $S$ is a reasonable theory of arithmetic, and the independence of $P$ from $S$ implies the truth of $P$, then $P$ is equivalent to the statement "$P$ is not provable from $S$" (part of "reasonable" here is soundness). But this latter statement is $\Pi^0_1$. Now this is actually silly - every sentence is either equivalent to $0=0$ if true or $0=1$ if false - but it can be "de-sillified" by phrasing it as: if $T,S$ are reasonable theories and $T$ proves that $S$ is consistent and that if $P$ is $S$-undecidable then $P$ is true, then $T$ proves that $P$ is equivalent to the $\Pi^0_1$ sentence "$P$ is not $S$-disprovable."

$^{**}$Or a statement interpretable as a statement about the natural numbers; e.g. "P=NP" is a statement about Turing machines, but by the usual techniques is "faithfully translateable" into the language of arithmetic.


Formal definition of a language accepted by PDA

I would say it's $L(A)=\{a^n c^m b^{2n}| n,m \in \mathbb{N}, m \geq 2\}$

For every a push 2 zeros on the stack, so it's for now just called a^n.
The number of c's is m, because it is not related to the number of a's. You can accept any number of c's (larger than 2) no matter how many a's were there.
The number of b's is twice the number of a's because you accept for every 0 on the stack 1 b, but wrote twice 0 for every a on the stack.

In fact the language $L(A)=\{a^n c^n b^n| n \in \mathbb{N}\}$ can't be accepted by any PDA, but only a linear bounded automate(LBA) or a Turingmachine (or other similar models) The reasoning is that if you count the number of a's and want to have the same number of c's and b's later(not mixed) your stack will be empty after you sucessfully counted all the c's and the PDA will have forgotten the number to check whether the b's appear in this number.


Algorithm for the complete parenthesization of n factors

As with most things involving trees, it's easiest to analyse recursively.

Given a one-element set $\{a\}$, the only parenthesisation is $(a)$.

Given a larger set $S$, we choose an arbitrary element $x \in S$. Then for each proper subset $T \subset (S \setminus \{x\}) $ we have parenthesisations $(p)(q)$ where $p$ is a parenthesisation of $\{x\} \cup T$ and $q$ is a parenthesisation of the remaining elements. There are a total of $(2|S| - 3)!!$ such.


What makes an operational semantics good?

I think you have it a bit backwards: proving type preservation is a good property of the type system with respect to the operational semantics, rather than the opposite.

Alternately: the whole point of a programing language is the ability to use it to perform some computational task. Because of this, the operational semantics is one of the requirements of having a programing language. The only real "fitness test" you need is

  Can I write the programs I want using this language?

You might then want to prove that say, a compiler is correctly implemented by showing that the computational behavior of (well-behaved) code is equivalent in some sense to the operational semantics, but again, here I would take the semantics themselves to be primal rather than the opposite.

In certain fields of mathematics, notably in the area which studies the propositions-as-types correspondence, one might be more interested in the static semantics (the type system) and have the operational semantics more as an afterthought, where progress, preservation and termination have consequences on the type system as a logic (typically, that the logic is consistent).

But again, usually the operational semantics is primitive, and it is well-defined exactly when it enables the programmer to write the program she wishes to write (and possibly prevents some "bad" programs).


VC dimension of finite unions of one-sided intervals

Finite unions of one-sided intervals can shatter only 2 points, because as said by @YuvalFilmus in comments the union of Finite unions is a single one-sided interval, and a single one-sided interval can shatter only 2 points.


Are there any benefits of implementing the Fisher–Yates shuffle algorithm from tail to head instead of head to tail?

With 0-indexed arrays, and stopping the loop at the last non-trivial random selection, we have

for x = n to 2 step -1:
    swap A[x-1], A[uniform_random(0 inclusive to x exclusive)]

vs

for x = 0 to n-2 step 1:
    swap A[x], A[uniform_random(x inclusive to n exclusive)]

which would probably be implemented as

for x = 0 to n-2 step 1:
    swap A[x], A[x + uniform_random(0 inclusive to n-x exclusive)]

So the forward loop has at least as much complexity.

I would claim that the simplest version is looping backwards in a 1-indexed environment (i.e. 1-indexed arrays and random number generation):

for x = n to 2 step -1:
    swap A[x], A[uniform_random(1 inclusive to x inclusive)]

There are various other variants possible: e.g. in the first example, we could loop x = n-1 to 1 step -1; in the second example, we could use two loop variables instead of one; etc.


Understanding Logical to Physical Addressing

I think you are confused in how logical address is get converted into physical address of main memory.
Let's take a walk from basics:
logical and physical memory are divided into fixed size pages and frames respectively to remove external fragmentation.

As size of logical memory is generally bigger than physical memory so we can't bring all pages from logical memory into physical memory that's why we require a page table that contains the entry of pair(page no. , frame no.).

Now as always CPU generates a logical address of say 15 bits with 10bits for page size and 5bits for identifying frame no. from page table(5bits means that there can be maximum 2^5 pages), now using those 5 bits cpu index page table and find the frame no. in which the required page is residing say that's of 4 bits(that mean a maximum of 2^4 frames ) then the physical address will be made by replacing 5bits by those 4bits + 10bits in logical address.

Your interpretation in question is correct.


Is substitution done to all occurrences?

A single substitution is one application of one rule. So the rule $A\to AA$ means "Pick any single $A$ in the string and replace it with $AA$" and "$A\to a$" means "Pick any single $A$ and replace it with $a$."  Substitutions are done one at a time, and there's no way to write a rule that says "Replace every $X$ with $Y$, or replace them all with $Z$."

If you start with $A$ and apply the first rule, you certainly get $AA$, since there's no other choice. But there are two ways of applying $A\to a$ to $AA$: you could pick the first or second $A$ to replace with $a$.

Indeed, there are two ways to apply $A\to AA$ to the string $AA$. However, replacing either the first or second $A$ with $AA$ gives the string $AAA$.


Constructing a reduction between two languages about pairs of Turing machines

Here are three hints.

Show that $L_2$ is not computably enumerable.
Show that $L_1$ is computably enumerable.
If $L_2$ mapping reduces to $L_1$, what does it imply?


What is the asymptotic complexity of the following code snippet?

The second loop runs in $O(i)$. The first loop goes over the powers $2^{2^0}, 2^{2^1}, 2^{2^2}, \ldots$, until reaching $n$. So the overall running time is
$$
O(2^{2^0} + 2^{2^1} + 2^{2^2} + \cdots + 2^{2^m}),
$$
where $m$ is the maximal integer such that $2^{2^m} < n$. We can bound
$$
2^{2^0} + 2^{2^1} + 2^{2^2} + \cdots + 2^{2^m} \leq 2^1 + 2^2 + 2^3 + \cdots + 2^{2^m} \leq 2^{2^m+1} < 2n.
$$
Therefore the overall running time is $O(n)$.

In fact, the same analysis gives the optimal bound $\Theta(2^{2^{\lfloor \log_2 \log_2 (n-1) \rfloor}})$, with a bit more work.


Iterative Depth First Search for cycle detection on directed graphs

You could add "colors" to the nodes similar to the method done for recursive DFS found in CLRS, for example. When you instantiate each node (assuming they are objects) put a color field such that every node initially has node.color $\xleftarrow{}$ white.

The following is your pseudocode modified that I believe would help:

    L ← Empty list of all nodes, where node.color ← black (once placed here)
    while exists nodes such that node.color is white do
    select a node n such that n.color is white
    visit(n)

function visit(node n)
    if n.color is black then:
        return
    if n.color is gray then:
        stop   (back edge is found indicates cycle exists)

    mark n.color as gray

    for each node m with an edge from n to m do
        visit(m)

    mark n.color as black
    add n to head of L

The idea is that all "unvisited" nodes begin colored "white". Then, when we encounter a node, we visit it and color it "grey" while exploring it. When we are done exploring this node, we color it "black". We only call DFS on nodes with "white" color.

Also regarding implementation, in addition to the stack, you could make L a set and just do a check on the size (since you know only distinct nodes will get added to this set) and once the size is equal to the number of nodes you know you've visited all the nodes of the graph, but as is if you use the coloring eventually it'll be the case that there is no node, n such that n.color == white.


I suggest expressing this as an instance of integer linear programming (ILP).  Express boolean logic operations in zero-one integer linear programming (ILP) might be useful to you in figuring out how to do that.

In particular, introduce zero-or-one variables $x_{n,j}$, which is one if person $n$ is placed into group $j$, or zero otherwise.  You can now express each of your requirements as a linear inequality,  and then use an ILP solver to test for feasibility. Now do binary search (or simple iterative search) over the number of groups, to find the maximum number of groups for which you can find a feasible solution.


Data extaction vs information extraction

Information gives semantics e.g. the meaning to data.  Consider pulling out of the tweets from the last hour as a raw data.    If you carry out sentiment analyses form this data you get something meaningful out of raw data: information about the mood of tweeters at the moment.

Data can be sourced by other means other than extracting.  For example apps can be developed to track information through sensors.  Imagine a sensor tracking movements in the wild, that would be raw data.  If you analyze the patterns of those movements you may infer the type of animal you have observed through the sensors e.g. information.

On a side note web extraction is possibly the most common way to extract data.
The only other common extraction scenario I can think of are ETL (Extraction and Transformation Loading) for Data-warehousing purposes using BI (Business Intelligence) tooling.


Is the reverse postorder of a digraph's reverse the same as the postorder of the digraph?

I wrote a short example to test the hypothesis and found out that the reverse postorder of a reverse graph is indeed not the same as the postorder of the original graph.
Consider the following graph:

Link to source (archive of image used in original post)

Postorder for the above graph is: 0 1 3 2 4 5.

Postorder for the reverse graph is: 4 5 0 2 3 1.

Reverse Postorder for the reverse graph is: 1 3 2 0 5 4.

You are thinking on the correct lines, but what we should understand is that the postorder of a graph is not necessarily the reverse of the postorder of the reverse graph. This is because of the way we iterate over the vertices when calling the depth-first search. There could be different solutions to the same problem, given the iteration method is different.

And because of this, the reverse postorder of a digraph's reverse is not necessarily the same as the postorder of the digraph.


Prove that regular languages are closed under the cycle operator

The idea is to decide nondeterministically at the beginning how much the word is cycled, and have a copy of the automaton for every case. In terms of the automaton, that means that we guess in which state $D$ would have been after consuming a word's prefix (which is a suffix of our input), and start in that state.

Now the construction. For every state $q \in Q$, separate $D$ into two parts $A_1$ and $A_2$. $A_1$ contains the states from which $q$ is reachable and $A_2$ the states that are reachable from $q$:

[source]

Note that any given node may be contained in both $A_1$ and $A_2$. Therefore,  the number of states can double if we make this step explicit.

Now we rewire this automaton so it accepts all words for which $q$ marks the "cycle point":

[source]

We get $|Q|$ automata of this form; create a new initial state which has $\varepsilon$-transitions to all their starting states. The resulting automaton accepts $\operatorname{cycle}(L)$. Altogether, we get at most $|Q|\cdot(2|Q|+1) + 1$ states, only $|Q|$ more states than the reference claims are possible.

You can achieve $2|Q|^2 + 1$ states by modifying the component automata a little bit; eliminate all $q_0$ by replacing the incoming $\varepsilon$-transitions with copies of its outgoing transitions. That is, for every pair of transitions $(q_1,\varepsilon,q_0), (q_0,a,q_2)$, introduce a transition $(q_1,a,q_2)$.

Rigorous construction and correctness proof remain as exercise.


Why do we take null closure two times while converting from Epsilon-NFA to NFA?

You might need to do some $\varepsilon$-transitions before reading the first character of the input, and after reading the last character. It's probably easier to just consider them before and after every character, so every character is treated the same way, than to make a special case of the first or last character.


You don't have to prove that LL-grammars form a subset of DCFG. It is just a definition. For example according to the Wikipedia:

  Restricting the DPDA to a single state reduces the class of languages accepted to the LL(1) languages.

This is more about LL-parsers.

LL(1)-grammar alternatively can also be defined as

  A grammar whose parsing table has no multiply-defined entries is said to be LL(1). The first "L" in LL(1) stands for scanning the input from left to right, the second "L" for producing a leftmost derivation, and the "1" for using one input symbol of lookahead at each step to make parsing action decisions.

The latter definition is taken from Aho, Sethi, Ullman's "Compilers" book.

In general $LL(k)$ parser may lookahead $k$ tokens to decide what production rule to apply.

However, you might be given a grammar $G$ and prove that this grammar is, for example, LL(1). In this case you could create a parse table and check if it has no multiply-defined entries.


Evasiveness of acyclicity of undirected graph

Consider any algorithm for acyclicity. We will use the following adversary:

  Whenever the algorithm asks for an edge, say that the edge exists if it connects two different connected components. (That is, if it doesn't close a cycle.)

You can show that the graph constructed by this dialog is always a forest, and moreover the constructed graph has the same connected components as the query graph (which contains all queried edges). In particular, when the last edge is asked, the graph is a tree (assuming $n \geq 3$; otherwise every graph is acyclic), and the graph is acyclic if and only if this edge does not belong to the graph.


Solving a recurrence of uneven subproblems without Akra-Bazzi

You could use "guess-and-check": guess the solution to the recurrence, then use induction to prove that it is a solution, i.e., to prove that your solution satisfies the recurrence.
In your case, since you know Akra-Bazzi, your "guess" can actually be obtained through Akra-Bazzi, but you don't have to tell anyone that's how you obtained your guess.


Pushdown automation where number of letter `a` is at least as twice as letter `b` in the word

General strategy:

What you want to do is every time you read an input symbol a, if the stack has a b on it delete the b, and if the stack is empty/has a's, add an a. Every time you read a b, if the stack is empty/has b's add bb, if the stack has one a, remove the a and add a b, and if the stack has two or more a's, delete two of them. You're in an accepting state as long as the stack has no b's on it.

You can implement this strategy if you use epsilon transitions and intermediate states in a fairly straightforward way.


Can PRNGs be used to magically compress stuff?

You've got a brilliant new compression scheme, eh? Alrighty, then...

♫ Let's all play, the entropy game ♫

Just to be simple, I will assume you want to compress messages of exactly $n$ bits, for some fixed $n$. However, you want to be able to use it for longer messages, so you need some way of differentiating your first message from the second (it cannot be ambiguous what you have compressed).

So, your scheme is to determine some family of PRNG/seeds such that if you want to compress, say, $01000111001$, then you just write some number $k$, which identifies some precomputed (and shared) seed/PRNG combo that generates those bits after $n$ queries. Alright. How many different bit-strings of length $n$ are there? $2^n$ (you have n choices between two items; $0$ and $1$). That means you will have to compute $2^n$ of these combos. No problem. However, you need to write out $k$ in binary for me to read it. How big can $k$ get? Well, it can be as big as $2^n$. How many bits do I need to write out $2^n$? $\log{2^n} = n$.

Oops! Your compression scheme needs messages as long as what you're compressing!

"Haha!", you say, "but that's in the worst case! One of my messages will be mapped to $0$, which needs only $1$ bit to represent! Victory!"

Yes, but your messages have to be unambiguous! How can I tell apart $1$ followed by $0$ from $10$? Since some of your keys are length $n$, all of them must be, or else I can't tell where you've started and stopped.

"Haha!", you say, "but I can just put the length of the string in binary first! That only needs to count to $n$, which can be represented by $\log{n}$ bits! So my $0$ now comes prefixed with only $\log{n}$ bits, I still win!"

Yes, but now those really big numbers are prefixed with $\log{n}$ bits. Your compression scheme has made some of your messages even longer! And half of all of your numbers start with $1$, so half of your messages are that much longer!

You then proceed to throw out more ideas like a terminating character, gzipping the number, and compressing the length itself, but all of those run into cases where the resultant message is just longer. In fact, for every bit you save on some message, another message will get longer in response. In general, you're just going to be shifting around the "cost" of your messages. Making some shorter will just make others longer. You really can't fit $2^n$ different messages in less space than writing out $2^n$ binary strings of length $n$.

"Haha!", you say, "but I can choose some messages as 'stupid' and make them illegal! Then I don't need to count all the way to $2^n$, because I don't support that many messages!"

You're right, but you haven't really won. You've just shrunk the set of messages you support. If you only supported $a=0000000011010$ and $b=111111110101000$ as the messages you send, then you can definitely just have the code $a\rightarrow 0$, $b\rightarrow 1$, which matches exactly what I've said. Here, $n=1$. The actual length of the messages isn't important, it's how many there are.

"Haha!", you say, "but I can simply determine that those stupid messages are rare! I'll make the rare ones big, and the common ones small! Then I win on average!"

Yep! Congratulations, you've just discovered entropy! If you have $n$ messages, where the $i$th message has probability $p_i$ of being sent, then you can get your expected message length down to the entropy $H = \sum_{i=1}^np_i\log(1/p_i)$ of this set of messages. That's a kind of weird expression, but all you really need to know is that's it's biggest when all messages are equally likely, and smaller when some are more common than others. In the extreme, if you know basically every message is going to be $a=000111010101$. Then you can use this super efficient code: $a\rightarrow0$, $x\rightarrow1x$ otherwise. Then your expected message length is basically $1$, which is awesome, and that's going to be really close to the entropy $H$. However, $H$ is a lower bound, and you really can't beat it, no matter how hard you try.

Anything that claims to beat entropy is probably not giving enough information to unambiguously retrieve the compressed message, or is just wrong. Entropy is such a powerful concept that we can lower-bound (and sometimes even upper-bound) the running time of some algorithms with it, because if they run really fast (or really slow), then they must be doing something that violates entropy.


Remove duplicated in array with best performance

Sorting is $O(n\log n)$, not $O(n)$.

Also these are asymptotic bounds. Even if one algorithm is $O(n)$ and another is $O(n^2)$, it is possible that, for small-ish values of $n$ the second algorithm is faster.

More concretely, $f(n) = 1000 n$ is $O(n)$ and $g(n)=n^2/1000$ is $O(n^2)$, and both bounds are tight. Still, it will take a while for the first function to become smaller than the second one: for $n<1000000$ the second one is smaller.


How to prove that the decidable languages are closed against iteration only by enumerators?

I don't really see how to use induction here.

Let's take as an example $L = \{0,1\}$. Then $L^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, \ldots\}$. You probably know how to enumerate $L^*$. Same thing works if $L = \{w_0,w_1\}$ for two arbitrary words.

The next step is to handle a language with infinitely many words. Following the earlier convention, I'll just indicate how to solve it for the special in which $L = \mathbb{N}$, and instead of $L^*$ I will use comma-separated sequences. Here is my enumeration:
$$
\epsilon; 1; 2; 1,1; 3; 1,2; 2,1; 1,1,1; 4; \ldots
$$
and so on. See if you can figure out a pattern (or if you don't like my pattern, come up with a different one).


Understanding a proof in the sweep line algorithm when finding all line segment intersections

The proof is absolutely correct. Of course, the algorithm only computes something when the sweep line comes to an eventpoint. Nevertheless you can think of the sweep line as a continiously moving line even if the algorithm does not hold everywhere to compute something.

Therefore you can always find a position, where the sweep line $l$ is close enough to $p$ and has no event point on it. In other words, you can always find a position above $p$ without eventpoints, where $p$ is the next eventpoint (maybe one of many). On this position, $s_i$ and $s_j$ are adjacent. There is no word here, that the algorithm computes something at this point and there is no conflict between the continuously moving sweep line and the discrete computing-positions of the algorithm.


General name for linked lists based on hashes

This is known as hash chaining.  The blockchain uses this technique, as do some kinds of timestamping schemes (see, e.g., Haber & Stornetta) and in some cryptographic schemes for append-only audit logs.


How Dynamic programming can be used for Coin Change problem?

Work an example.  I worked through the Scheme version with the input 35 (and with the denominations of the coins as 1, 5, 10, 25, 50) and I'm seeing a ton of repetition in the search tree.  (cc 5 1) has already come up 3 times and I'm only about half way through.

Also, memoization actually does a little more than lazy evaluation.  Lazy evaluation caches the thunk for the expression assigned to a particular dynamic instance of a variable so that the thunk gets evaluated at most once.  But memoization caches all expression evaluations, so if the expression is assigned to different dynamic variable instances you'll also only get a single evaluation.  This requires a bit more machinery (you have to hash the arguments of the expression, and store the argument/result pair in a hash table.)  If you were to rewrite the function in a lazy functional language (like Haskell) you wouldn't automatically get memoization benefits in this case.


You can prove by contradiction, assuming there is a value of $k$ that allows you to anticipate the sequence of derivations that is guaranteed to produce a unique tree for any input string, given some unambiguous grammar that accepts the language.

You then prove that there is a string for which a lookahead  $>k$ will be needed, no matter how the grammar is constructed, because the derivation sequence is affected early in the process. A strategy similar to the pumping lemma for context-free languages comes to mind.

Incidentally, your grammar is equivalent to the following LL(1) grammar:

$\begin{align} S &\to aT \\
               T &\to f \mid bXcV \\
               X &\to bXc \mid \epsilon \\
               V &\to d \mid f \end{align}$

Perhaps a more interesting example would be

$\begin{align} S &\to T \mid U \mid V \\
               T &\to aTb \mid \epsilon \\
               U &\to aUc \mid \epsilon \\
               V &\to dVc \mid \epsilon \end{align}$

whose language is both not $LL(k)$ and not $RR(k)$.


Proof that a language involving $gcd$ is not context-free

Let $p$ be the pumping length guaranteed by the pumping lemma (for context free languages). Then we choose $m \neq n$ such that $m,n \geq p$ and are both prime. Then clearly $s = a^{n}b^{m} \in L$.

By the pumping lemma we can divide $s$ such that $s=uvxyz$ and

$|vxy| \leq p$
$|vy| \geq 0$
$s' = uv^{i}xy^{i}z \in L$ for all $i \in \mathbb{N}$

For this language we get three similar cases, and one trivial case. The trivial case is where either $v$ or $y$ contains both $a$'s and $b$'s, in which case $s'$ doesn't have the correct ordering, and thus $s'\notin L$.

The nontrivial cases:

 $v$ and $y$ are both strings of $a$'s, then when we pump $s$ we get $s' = a^{n+ik}b^{n}$ where $k\geq 1$. Then $s' \in L$ if $gcd(n+ik,m)=1$, however the modular equation $n+ik\equiv 0 (m)$ has the solution $i \equiv nk^{-1} (m)$, and as $m$ is prime we are guaranteed that $k^{-1}$ exists. Therefore any element of the residue class $i \equiv nk^{-1} (m)$ would give us $gcd(n+ik,m) > 1$. Ergo $s' \notin L$.

Short version: we can pump the string so that $n+ik$ is a multiple of $m$ for any $k$ with $1 \leq k \leq p < m,n$ (which is what we set up at the start).

$v$ and $y$ are both strings of $b$'s, but this case is just the symmetric case to case 1, so we derive a contradiction in this case too.

$v = a^{k}$ and $y = b^{h}$ for some $k$ and $h$ with $1 \leq k+h \leq p$. Then when we pump we get $s' = a^{n+ik}b^{m+ih}$. Now $s' \in L$ if $n+ik \equiv m+ih (m)$ has no solution, but as I'm sure you can see from here, rearranging just gives $n+i(k+h)\equiv 0(m)$, and as before this has solution $i \equiv n(k+h)^{-1}(m)$. So again we derive a contradiction.

Thus there is at least one string in $L$ that cannot be divided as per the pumping lemma and still have all pumping results remain in $L$. Therefore $L$ is not context free. $Q.E.D$

Some additional notes: of course there is an infinite number of strings which can't be pumped, and it's not actually necessary for $m$ and $n$ to be prime, it just simplifies that argument, as we don't have to fiddle around with a prime decomposition - though if you did want to, you just pick one of the prime factors and do the same (or even all of them if you want).


How to show that i have significant improvements over the baselines?

Odds are, you can't.  That's a judgement call, and it's notoriously hard to get other people to change their judgement.  The path is to find new evidence or facts they might not be aware of; assemble a persuasive argument; and see what happens.

But in this case, without knowing anything about the domain, I suspect the reviewers might be right.  Why would a difference in accuracy of 0.20% make a practical difference?  What new capability would it provide?  How much money would it save?  Often it's not that significant.

I see this misconception a lot.  People see another paper was accepted (to a different conference/journal), see that it had improvement of X%, assume that it was accepted because of X% improvement, and assume that if they get X% improvement their paper will/should be accepted too.  Neither of those assumptions is valid.  You don't know why that other paper was accepted.  Maybe it was accepted because the ideas it had were intriguing.  Maybe it was accepted because the paper made other contributions.  Maybe it was accepted because that conference/journal has lower standards.  Maybe it was because that kind of improvement was worth one paper being published, once, but not two.  Maybe it was because the reviewers were in a good mood that way.  Maybe it was something else.  Who knows.  And just because reviewers want to accept one paper with X% improvement on task T, doesn't mean they'll want to accept 10 papers or 100 papers with X% improvement on task T.

Don't delegate your judgement to reviewers (that other paper was accepted, so it must be good). Form your own standards of what counts as valuable work. Then, strive to make your work meet those standards.  That will enable you to articulate why your paper is significant and should be accepted, on its own merits.

This is a topic you should be discussing with your advisor/supervisor and your co-authors, as they know the work you're doing and (hopefully) know the domain area and can give you much more informed advice.


Constructing a PDA with an unequal number of a/b

The intuition is push the number of $a$'s then pop while reading $b$'s. The result should be non-zero: either there are still items on the stack (which we can check), or the stack has been emptied before the end of the string.

There is a problem with instructions like "$b/\varepsilon/\varepsilon$". This instruction means "read $b$ and do not push nor pop". The middle $\varepsilon$ is misleading. It does not mean that the stack is empty. It just means the PDA does not look at it.

The solution is to start by pushing a nice bottom-of-stack symbol $Z$ at the start of the computation. When we  see a $Z$ we know the bottom has been reached.


Why doesn't playing audio stop other tasks?

Since the CPU works in fixed clock cycles, nothing is really continuous, only seems so because the discretization is sensitive enough.

Suppose your CPU clock rate is $1\text{GHz}=10^9Hz$. If the CPU only devotes one in $t$ clock cycles to processing audio (and utilizes the remaining clock cycles for unrelated tasks) then you have a delay of $\approx t\cdot 10^{-9}s$ between every "audio processing tasks" preformed by the cpu (for simplicity, we assume the cpu preforms this processing using only one clock cycle).

Lets say we allow a delay of $10^{-5}s$ (humans hear frequencies in the range of 20Hz to 20Khz, so the human hearing will not be sensitive to such delay), then we need to require $t<10^4$, so the CPU can handle simultaneously $10^4$ more tasks while keeping a delay of $10^{-5}s$.


Is Morse Code binary, ternary or quinary?

This answer isn't as long as it looks; this site just puts a lot of spacing between list items! Update: Actually it's getting pretty long...

Morse Code isn't "officially" binary, ternary, quaternary, quinary, or even 57-ary (if I count correctly). Arguing about which one it is without context is not productive. It is up to you to define which of those five it is based on your application and the encoding requirements for your specific situation. To that end, there are pros and cons to each symbol set size, which you should consider for your situation before making a decision.

For the basis, M.1677, the international Morse Code standard, section 2, defines timings as:

  2 Spacing and length of the signals
  2.1 A dash is equal to three dots.
  2.2 The space between the signals forming the same letter is equal to one dot.
  2.3 The space between two letters is equal to three dots.
  2.4 The space between two words is equal to seven dots.

Note that that defines timings only, e.g. a dash does not mean the same thing as three dots, it is simply the same length. The base unit of time is a dot.

Binary

We can choose binary if we'd like. It is possible to represent Morse Code with "strict binary", as you call it -- that author's approach was to assign the digits to "dot" and "dash". That approach does not work and I do not think the author has a firm grasp of Morse code. But there is a different approach that works. If we choose binary, we essentially represent whether the signal is high or low with each symbol occupying a single dot-lengthed time slice. Note that this is also the approach described on the List of Binary Codes page you cited.

Other binary codings can be chosen as well (e.g. Bob Jarvis' answer) at the expense of increases in difficulty decoding back to audible Morse Code (Bob's encoding cannot be decoded statelessly, for example, the tradeoff is it provides shorter encoded sequences).

Symbols:

Low, off, etc. (0)
High, on, etc. (1)

Encoding Examples:

Signal separator: 0
Letter separator: 000
Word separator: 0000000
Three dots: 10101
Three dashes: 11101110111
The word "son": 101010001110111011100011101
The phrase "is a": 10100010101000000010111

Pros:

Minimal symbol set size
Easily managed with typical digital logic
Easy to decode into audible Morse Code (presuming no validation is done); stateless decoding and does not require storing information about the timing of symbols (every symbol is the same length).

Cons:

Long encodings.
Many opportunities for invalid encodings.
Individual symbol meanings (0, 1) depend on context.

Ternary

With this choice, we define letter and word spacings as rests, and signal spacings are implicit (although you could choose to require dot length rest symbols between signals, if it suits you better).

Symbols:

Dot-length rest (0)
Dot (1)
Dash (2)

Encoding Examples:

Letter separator: 000
Word separator: 0000000
Three dots: 111
Three dashes: 222
The word "son": 11100022200021
The phrase "is a": 11000111000000012

Pros:

Small symbol set size.
Signal separator no longer needed.
Shorter encoding lengths than binary.
Removes some invalid encodings (e.g. 0110 with the binary choice no longer possible).

Cons:

Still lengthy encodings.
Still many possibilities for invalid encodings, in particular, the rests.
Cannot be decoded statelessly† unless you choose to place explicit dot length rests between signals.
Signal separators are implicit‡ unless you choose to place explicit dot length rests between signals.
Some individual symbol meanings (0) depend on context.

Quaternary

Symbols:

Letter separator (0)
Word separator (1)
Dot (2)
Dash (3)

Encoding Examples:

Three dots: 222
Three dashes: 333
The word "son": 2220333032
The phrase "is a": 220222123

Pros:

Very short encoded length.
Possibility of invalid encodings is reduced.
Symbols are semantically accurate.
Arguably, more human-readable.

Cons:

Large symbol set size.
Cannot be decoded statelessly.†
Signal separators are implicit.‡

Quinary

A direct interpretation of Wikipedia's list. Note this is very similar to the binary choice except the various valid combination of binary 0's or 1's are given their own symbols.

Symbols:

Signal separator (0)
Letter separator (1)
Word separator (2)
Dot (3)
Dash (4)

Encoding examples:

Three dots: 30303
Three dashes: 40404
The word "son": 303031404041403
The phrase "is a": 3031303032304

Pros (compared to quaternary):

Can be decoded statelessly.
The only symbol set size that unambiguously, directly and concisely represents the five objects mentioned in section 2 of the standard: "dot" (to which all timings are relative to), "dash", "space between the signals", "space between two letters", "space between two words".

Cons (compared to quaternary):

Higher possibility for invalid encodings.
Increased encoding lengths without adding extra information (tradeoff is decoding ease).
Not as easy to decode as the binary choice, in that each symbol is a different length in time and this association must be maintained somewhere.

57-ary:

Included for completeness.

Symbols:

26 letters
10 numbers
20 punctuation marks and miscellaneous signs
Word separator (space)

Encoding Examples:

The word "son": son
The phrase "is a": is a

Pros:

Shortest encoding
Human readable
Invalid encodings are impossible.

Cons:

Largest symbol set
Difficult to decode into Morse Code; necessary to maintain tables of Morse Code output sequences for each symbol and necessary to detect word boundaries and adjacent letters to determine where to insert various rests.
Impossible to expand beyond the Morse Code specification without adding new symbols (tradeoff for being immune to invalid encodings).
Signal and letter separators are implicit.‡

Termination

For storage as a symbol stream on a device, if you need to do that, it's worth noting that M.1677 defines message and transmission termination sequences. From Part II:

  5 Every telegram shall be terminated with a cross signal (. – . – .)
  6 The end of the transmission shall be indicated by the cross signal (. – . – .) followed by the invitation to transmit signal K (– . –)
  7 The end of work shall be indicated by the station that transmitted the last telegram. The correct indication is the end of work signal (. . . – . –)

Unfortunately, the standard is silent on the ability to distinguish e.g. the string "+K" from the sequence (end-of-telegram, invitation-to-transmit). However, end-of-work is unique. If you are storing morse code, then, you will have to make a choice as to how you want to indicate the end of a stored sequence.

If you are storing an entire conversation, for example, and are using the binary symbol set, you could reasonably consider end-of-work to be the end of sequence indicator, represented as the unique bit sequence 101010111010111. You need to consider the type of data you are storing (e.g. message fragments, entire messages, entire conversations) as well as the facilities offered to you by your storage medium (e.g. ability to prefix with message length) before deciding. I suppose you could go so far as to define your own end of sequence indicator. In any case these are all matters of underlying storage and have too many possibilities to list here. The choice is really up to you based on whatever is appropriate for your situation.

† Cannot be decoded statelessly: These encodings require some state to be maintained in order to decode into audible Morse Code. They all require "If preceding symbol was a dot/dash and current symbol is a dot/dash then insert signal separator". While you could try and "cheat" and automatically append a signal separator to all symbols while reducing word separator to 5 rests and letter separator to 1, M.1677 afaict does not explicitly prohibit consecutive word separators, which breaks this kludge.

‡ Signal separators are implicit: This is directly related to the above note but more semantically oriented. These encodings have implicit signal separators in their notation. That is "zzz" is intuitively three separate z's, the boundaries are "piggybacked" on whatever it is that separates symbols in the encoding itself. Consider the description "three dots in a row"; intuitively we take this to mean three separate dots, but if separators weren't implied this could be taken to be indistinguishable from a dash. Only the Wikipedia-style binary and quinary (or ternary with the explicit signal separator option) representations remove all ambiguity and "shortcuts" here, which can be of great value depending on the situation. It is for this reason that there is a strong argument for the quinary choice.

TL;DR:

As you can see, there are advantages and disadvantages to each, and it's up to you to decide how you want to treat it based on your requirements. There is no right answer. You could attempt to argue that one is more appropriate than the other in general, but these arguments would boil down to pedantic preferences, as without context, there is no correct answer.

Now, all that said, in my own opinion, the quinary choice is the representation that feels the most "right" to me for Morse Code itself (originally I had favored quaternary). It is the only choice that provides all of the following:

Context-free symbols (a symbol on its own contains all information about its meaning without examining adjacent symbols).
Representation of all primitives defined in M.1667.
Separators (signal, letter, word) are not implied by notation or underlying encoding (this is important, if I wrote { dot, dot, dash }, those ,'s are significant and easy to overlook).

However, there are strong arguments for all. The arguments related to encoding are also applicable to the treatment of Morse itself. There is no 100% concrete answer, but it can certainly make a good topic for debate with your friends at the bar.

. . . – . –


Yamakami showed in their paper Analysis of Quantum Functions that the quantum analog of PP is the same as classical PP. This is mentioned in the Wikipedia article on PP.


All strings that contain no run of a's of length greater than two for $\Sigma = \{a,b,c\}$

The $+$ sign stands for union, but you got the order of operations wrong. Your regular expression is the sum of $(b+c)^*$ and
$$ (b+c)^*((a+aa)(b+c)^+)^*(a+aa)(b+c)^*. $$


Is every planar graph a possible dual graph of a voronoi diagram?

No. The dual graph of a Voronoi diagram is the Delaunay triangulation of its point set so, in particular, every interior face of it is a triangle. But there are plenty of planar graphs (e.g., the $4$-cycle) that have non-triangular interior faces.


insert and delete in order statistic tree

The exact implementation of Insert and Delete depends on the underlying binary tree structure which is used, but the idea is that you maintain the size field throughout the operation. Consider for example the following Insert procedure, which always inserts its element as a new leaf:

Insert(Tree, $x$)

If Tree is empty, set Tree to be $x$, and return.
Let $r$ be the root of Tree, and Left, Right its children.
If $x < r$ then call Insert(Left, $x$), otherwise call Insert(Right, $x$).

Here is the updated algorithm, which maintains the size information:

Insert(Tree, $x$)

If Tree is empty, set Tree to be $x$ and size(Tree)=1, and return.
Increase size(Tree) by 1.
Let $r$ be the root of Tree, and Left, Right its children.
If $x < r$ then call Insert(Left, $x$), otherwise call Insert(Right, $x$).

This is the basic idea. You can take it from here.


Is the problem of determining whether a CFG generates a string in the form 0*1* decidable?

Yes it is decidable.
We can construct a total Turing machine M that on input $G$ (where G is a CFG) checks whether it generates at least one string in $0^*1^*$.
Let $G_1$ be a regular language such that $L(G_1)=0^*1^*$.
Note that the intersection of CFL and a regular language is indeed a CFL. And hence a CFG for the intersection of $G$ and $G_1$ can be constructed. Call the constructed CFG $G'$. Also, the emptiness problem for CFG is decidable and hence just check the emptiness of the constructed CFG $G'$.
If it's empty, G doesn't generate any string in $0^*1^*$; and likewise if it's  not empty.


Is it possible to derive a string in this rewriting system?

Notice that the parity of the number of $A$s does not change. Since one string contains an odd number $A$ and the other even, they are not reachable.

I believe in general (for an arbitrary set of rules, not your specific example), this is likely to be an undecidable problem. If the transforms are one way(i.e rules of the form $A \to BA$) it is so , for eg see: Tag System.


Counting the number of words accepted by an acyclic NFA

Here's one approach that I expect should give you a multiplicative-factor approximation, with polynomial time running time.
Let $L$ be a regular language that is a subset of $\{0,1\}^n$, e.g., $L=L(M) \cap \{0,1\}^n$.  We will try to compute the approximate size of $L$.
At a high level, our approach to approximate $|L|$ will look something like this:

Pick a fraction $p$, where $0<p<1$.

Choose a regular language $R$ such that, roughly speaking, $R$ is a random subset of $\{0,1\}^n$ of size approximately $p2^n$ (i.e., $|R|\approx p2^n$).

Check whether $L \cap R$ is non-empty.  Note that this check can be done in polynomial time.

Repeatedly perform steps 1-3 for various values of $p$.  This gives you some information that will let you approximate $|L|$.
In particular, if $|L|=m$, then we'd expect
$$\Pr[L \cap R = \emptyset] = (1-p)^m \approx e^{-pm}.$$
So, if you happen to choose $p=1/m$ and repeat steps 1-3 a bunch of times, you should expect to see an empty intersection about 37% of the time.  If you see an empty intersection significantly more often then that, then increase $p$ and try again.  If you see an empty intersection significantly less often then that, you might decrease $p$ and try again.
In this way, using something like binary search, you should be able to approximate $|L|$ to within a multiplicative approximation factor.
You'll still need to pick some way to choose $R$ so that it is regular but also behaves like a random subset.  There are many possibilities, but one might good way might be to choose a random 2-universal hash $h:\{0,1\}^m \to \{0,1,2,\dots,k-1\}$, pick $y \in \{0,1,\dots,k-1\}$ randomly, and let $R=\{x \in \{0,1\}^n : h(x)=y\}$.  Choosing $k=\lceil 1/p \rceil$ gives you a random set $R$ of approximately the right size, and because $h$ is 2-universal, all of the mathematics above should work out properly.
This should solve your problem for the case where all strings in the NFA have the same length, say $n$.  If they have varying lengths, then you can handle each possible length separately.  Since $M$ is acyclic, the maximum lengths of any string in $L(M){}$ is at most the number of states in $M$, so this does not increase the runtime too much.
(This construction might remind you of the Valiant-Vazirani theorem about unambiguous SAT.)


Can PDA accept only by final state without finish reading input?

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


Number of balanced binary trees (The Art of Computer Programming)

The way I tend to interpret these parameters is to think of them as stand-ins for some type of basic structure in your enumeration problem. This might sound a bit too abstract, so let's look at a (simpler) concrete example.

Let's consider the task of enumerating linked lists. The question I'm interested in is, given a list of unit types (those whose only element is the unit $\circ$), how many lists over unit are there such that their length is $n$? Now, this question was chosen for a very simple purpose: it's easy to see what the answer is. If each element of your list can only be a single element $\circ$, then obviously there's exactly one list of size $n$.

Now, one way to solve this is to look at the inductive definition of a list.
$$
\textrm{List}_{\circ} = \circ :: \textrm{List}_{\circ} ~\textrm{or}~ []
$$

This says that a list over $\circ$ is either a $\circ$ prepended to another list, or it is an empty list. Flattening out the fancy operators into tuple form, and turning the word $\rm or$ into a $+$, we have

$$
\textrm{List}_{\circ} = (\circ * \textrm{List}_{\circ}) + []
$$

Since an empty list [] can be thought of as a tuple with zero $\circ$s inside, let's rewrite it as $\circ^0 = 1$. This then gives an equation

$$
L = \circ * L + 1
$$

Suppose that we're working over the complex field, then this is equivalent to (assuming that $\circ \ne 1$)
$$
L = \frac{1}{1 - \circ} = \circ^0 + \circ^1 + \circ^2 + \circ^3 + \dots
$$

Now, notice that the formal power series of $L$ with respect to $\circ$ exactly specifies all of the possible lists over the unit $\circ$. That's kind of cool, but is it just a coincidence?

To find out, we turn our attention to a related problem, that of counting lists over the booleans $(\bot, \top)$. Once again, we start with the inductive definition

$$
\textrm{List}_{2} = (\bot ~\textrm{or}~ \top) :: \textrm{List}_{2} ~\textrm{or}~ []
$$

Doing the same transformation as before, we find that

$$
L_2(\bot, \top) = \frac{1}{1 - (\bot + \top)} = 1 + \bot + \top + \bot^2 + \bot\top + \top\bot + \top^2 + \bot^3 + \bot^2\top + \dots
$$

Interesting, it seems like for certain enumeration problems, the inductive definition we use to specify/construct a type can be translated into this functional over the complex numbers. What's more, this functional's formal power series seems to generate a series of constructions that are isomorphic to the objects from your inductive specification. This is more or less the idea behind these generating functions: their series representation "generates" the combinatorial structures that you are studying.

Now, let's come back to the counting problem. So what if we know that $\frac{1}{1 - \top - \bot}$ represents our combinatorial class? How does this help us with the enumeration problem? Well, the counting problem asks for the number of lists that contains a certain number. This tells us that even if $\top$ and $\bot$ are distinct, they still each contribute the same number of elements (namely, 1) to the list. We can specify this "blindness" with the equality $z = \bot = \top$, so that

$$
L_2(z) = L_2(z, z) = \frac{1}{1 - 2z} = 1 + z + z + z^2 + z^2 + z^2 + z^2 + z^3 + z^3 + \dots
$$

simplifying, this series yields

$$
L_2(z) = 1 + 2z + 4z^2 + 8z^3 + \dots + 2^k z^k + \dots
$$

Since each of the lists under $z^3$ are lists of length 3, this series then tells us that there are $2^3$ distinct boolean lists of length 3.

Herein lies the power of these generating functions. By "erasing" properties that you don't care about (like the distinctness of true and false in a counting problem), you end up with this formal series whose coefficient gives the total count of a subclass of interest. Therefore, the question du jour of these "analytic" enumeration problems is not how one interprets giving $z$ a specific value, but rather how one can show that the function is analytic/differentiable around the origin and what its coefficients are.

This glosses over a lot of the details, but the intuition should hopefully remain. For your particular problem, we can follow the same recipe to eventually derive Knuth's tower of balanced tree construction.

Now, a height-balanced tree is a binary tree such that the height of each child of a tree is always within one unit of any other child of a tree. This gives a simple case-analysis to consider.

A balanced tree of height $h$ is a root node together with children such that they are:

Balanced, so that the height of both children are the same, aka $h - 1$.
Unbalanced but left-skewed, so that the height of the left children is larger, aka $h - 1$ and $h - 2$.
Unbalanced but right-skewed, so that the height of the right children is larger, aka $h - 2$ and $h - 1$.

This then yields an inductive specification

$$
BBT_h = (BBT_{h-1}, \circ, BBT_{h-1}) ~\textrm{or}~ (BBT_{h-2}, \circ, BBT_{h-1}) ~\textrm{or}~ (BBT_{h-1}, \circ, BBT_{h-2})
$$

Where the tuple $(L, \circ, R)$ denotes the balanced tree rooted at $\circ$ with the left branching to $L$ and the right branching to $R$. Transferring to the complex field, this gives
$$
B_h = \circ B_{h-1}^2 + \circ B_{h_2} B_{h-1} + \circ B_{h-1} B_{h-2}
$$
taking advantage of the newly found freedom of commutativity, and reassociating, we have
$$
B_h(\circ) = \circ B_{h-1}(B_{h-1} + 2 B_{h-2})
$$
Since this is a two-step recurrence, we need to specify their initial conditions. $B_0$ is the class of balanced trees with zero nodes, so we have $B_0(\circ) = \circ^0 = 1$. $B_1$ is the class of balanced trees with one node, so we have $B_1(\circ) = \circ^1$. Finally, substituting $z = \circ$ gives Knuth's generating functions.

Of course, we've skipped over one bit: we haven't shown that there's some neighborhood around the origin such that $B_k(z)$'s formal series actually converges. Fortunately for us, these forms of inductive constructions are all generally admissible, so we need not worry about them here.

Finally, the last step is to characterize the coefficient of $z^k$. To be fair, the full problem is to find the coefficients of $\sum_h B_h(z)$, but it suffices to just find the coefficient for some $B_h(z)$, since we can then sum over the rest independently. There's two general strategies we can pursue:

Find an explicit characterization of $B_h(z)$.
Use the implicit recurrence directly and see if we can find the coefficients directly.

Here, I imagine that Knuth's approach is probably the second approach. In particular, given two functions $A(z) = a_0 + a_1 z + a_2 z^2 + \dots$ and $B(z) = b_0 + \dots$, we have
$$
A(z) * B(z) = \sum_n \sum_{k \le n} a_k b_{n-k} z^n
$$
and in particular
$$
zA(z) = a_0z + a_1z^2 + \dots
$$

Letting $[z^n]f(z) = f_n$ be the coefficient of $z^n$ in $f(z)$, then we have
\begin{align*}
[z^{n+1}]B_h(z) &= [z^n](B_{h-1}(z)^2 + 2B_{h_1}(z)B_{h-2}(z)) \\
&= \sum_{k \le n} ([z^k]B_{h-1}(z) + [z^k]B_{h-2}(z)) \times [z^{n-k}]B_{h-1}(z)
\end{align*}

This then gives a rather mundane dynamic programming algorithm to compute these coefficients. You can also probably appeal to some analytic techniques to solve for asymptotic properties, but that's for another time.


What does it mean to "show algebraically" in propositional logic?

Although you haven't posted any of the logical rules the problem statement refers to, it is reasonable to assume they are similar to those found in many standard logic textbooks. To prove your identity, I will make use of
$$
\begin{align}
P \land Q & \equiv Q \land P, &\text{$\land$ commutativity} \\
P \land (Q \lor R) & \equiv (P \land Q) \lor (P \land R),  &\text{$\land$ distribution} \\
P \land \lnot P & \equiv \bot  &\text {(3)} \\
P \lor \bot &\equiv P, & \text{$\bot$ annihilation}
\end{align}
$$
where $\bot$ denotes falsehood. With that in mind
$$
\begin{align}
p \iff q \equiv & \\
(\lnot p \lor q) \land (\lnot q \lor p) \equiv &  & \text{By definition}\\
((\lnot p \lor q) \land \lnot q) \lor ((\lnot p \lor q) \land p) \equiv & &\text{By distribution of $\land$} \\
(\lnot q \land (\lnot p \lor q)) \lor (p \land (\lnot p \lor q)) \equiv & &\text{By commutativity of $\land$} \\
(\lnot q \land \lnot p \lor \lnot q \land q) \lor (p \land \lnot p \lor p \land q) \equiv & &\text{By distribution of $\land$} \\
(\lnot q \land \lnot p \lor \bot) \lor (\bot \lor p \land q) \equiv & &\text{By $(3)$} \\
(\lnot q \land \lnot p) \lor (p \land q) \equiv & &\text{By $\bot$ annihilation} \\
(\lnot p \land \lnot q) \lor (q \land p) \equiv & &\text{By commutativity of $\land$} \\
& &\square
\end{align}
$$
I've assumed throughout $\land$ to have higher precedence than $\lor$.


Yes, you are right.  The pseudocode is clumsy, poorly constructed, and confusing.  At the end of the outer loop, modecount holds the number of times that value appears in the array, plus one.  That's weird and not what you'd expect from the variable name: from the variable name, we'd expect it to hold the number of times value appears (without the plus one).

That said, the algorithm still returns the correct answer: it does indeed return a mode, as claimed.  For example, with your example input, it correctly returns 2.

(Why?  Because the exact value of modecount isn't returned.  It's one too high for every value, so the mode will indeed have the largest value of modecount.)

So while the pseudocode is confusing and poorly constructed, it happens to return the right answer -- i.e., it happens to be a correct algorithm for the "find a mode" problem.  But it's still ugly.  Yuck.  I agree with you that they should have initialized the count to 0, not 1; then the algorithm would be both correct and easier to understand.


Proof that $A_{DFA}$ is decidable in Sipser

The computation will always halt. If $M$ doesn't reject right away, then $B$ is an encoding of a DFA. DFA always halt on any finite input, so the simulation must halt too.


It is a well known problem, known as the multidimensional knapsack problem, and it is easily solvable by dynamic programming for the parameter / problem size you are dealing with here. A very similar formulation is discussed, for example, here.


The halting problem of Turing machines in view of enumeration of initial tape configurations

The Halting problem is stated in terms of any admissible numbering. There are effective (i.e. Turing-computable) compilers between all such numberings, so the Halting problems are all the same. That is, in particular not decidable.

There are numberings of all partially-recursive functions for which the Halting problem is decidable -- of course. For instance, give all "yes"-instances even and all "no"-instances odd numbers. Such a numbering would certainly not be admissible; in this case because it would not be partially recursive.

Thus, it comes down for you to show that your numbering is admissible or not. If not, the Halting problem may be decidable but the numbering would be ... not very useful.


Relations between deciding languages and computing functions in advice machines

I think the answer to Question 2 is "no", as far as we know.  For instance, let $f$ be the function that parses its input $s$ as a 3CNF formula $\varphi$ and then returns the lexicographically earliest satisfying assignment to $\varphi$, or $\bot$ if none exists.  Then it is easy to decide $L(f) = \{\langle s,f(s) \rangle\}$ in polynomial time, but (assuming P $\ne$ NP), you cannot compute $f$ in polynomial time (and assuming P/poly $\ne$ NP, advice doesn't help).
The following might be a better way to translate between functions and languages.  Let $L'(f) = \{\langle s,i,b \rangle : f(s)_i=b\}$, where $y_i$ denotes the $i$th bit of $y$. (I assume that if $y$ has fewer than $i$ symbols, then $y_i=\bot$.)  Then if you can compute $f$ in polynomial time, you can decide $L'$ in polynomial time; and if you can decide $L'(f)$ in polynomial time and the length of $f(s)$ is polynomial in the length of $s$, then you can decide $L'(f)$ in polynomial time.


Prove that A** = A*, where A is a language over Σ*

Since $L \subseteq L^*$ for all $L$, we have $\mathcal{A}^* \subseteq \mathcal{A}^{**}$. In the other direction, suppose that $w \in \mathcal{A}^{**}$. Then there exists an integer $n \geq 0$ and words $x_1,\ldots,x_n \in \mathcal{A}^*$ such that $w = x_1 x_2 \ldots x_n$. Since $x_i \in \mathcal{A}^*$, there exists an integer $m_i$ such that $x_i \in \mathcal{A}^{m_i}$. Thus $w \in \mathcal{A}^{m_1 + \cdots + m_n} \subseteq \mathcal{A}^*$, and it follows that $\mathcal{A}^{**} \subseteq \mathcal{A}^*$.


Proving that a certain graph contains a 4-cycle

The question says "IF $G$ contains a certain number of edges, then..." and, as you've demonstrated, if $G$ has only four vertices, then it can't contain that many edges, since a graph (without self-loops) can contain at most $\tfrac12|V|\,(|V|-1)$ edges. So, for the condition to be true, we must have
$$\begin{align*}
    2|V|^{3/2} &\leq \tfrac12|V|\,(|V|-1) \\
    4|V|^{1/2} &\leq |V|-1 &\text{(dividing through by $\tfrac12|V|$)}\\
    16|V| &\leq |V|^2-2|V| + 1 &\text{(squaring both sides)}\\
    |V|^2-18|V|+1&\geq 0 &\text{(collecting terms)}
\end{align*}$$

Then, by the quadratic formula, we see that $|V|\geq 9 + 4\sqrt5 \approx 17.94$ (or $|V|\leq9-4\sqrt5$ but we're only interested in positive solutions for $|V|$).
It's not a problem that $17.94$ isn't an integer: the number of vertices must be greater than or equal to that number, so we actually have $|V|\geq 18$.


Is this definition of $\alpha$-equivalence correct?

The approach itself makes sense, but the relationship with runSubst_Var probably makes proofs more difficult.
I think it's better to work on De Bruijn indices for alpha-equivalent semantics.


Can one truly build a schedule from graph coloring?

[...] is this feasible in a real world scenario?

I'm not sure.  But note that determining the chromatic number of a graph and determining the minimum number of timeslots needed to schedule lectures with a given pattern of conflicts are exactly the same problem. So, if the scheduling problem can't be feasibly solved by colouring, it can't be feasibly solved any other way, either.

  Say I have 30 professors and 200 students, can we determine a minimum number of meeting times with a graph this size?

Note that the size of the graph depends only on the number of classes. The only effect that the number of students has is that having more students means there are more likely to be conflicts between more classes.

  And does the graph tell us when they need to meet?

No. It will just tell you "Here are sets $S_1, \dots, S_k$ that partition the classes."  All the classes in one set should be scheduled at the same time; different sets need to be at different times. The graph doesn't care whether you study algorithms at 10am and Java at 11am, or algorithms at 11 and Java at 10, or algorithms at 3am and Java at 3pm. All it knows is that, if at least one person is studying algorithms and Java, those two classes have to be at different times.

  In addition, could the graph take into account some lectures twice as long as other lectures?

Not directly.  But you could pretend that your two-hour electronics lab is really two one-hour labs called electronics1 and electronics2 which, of course, can't be at the same time, because students take both courses. And, because the graph doesn't care what time the classes are at, you can schedule electronics2 to be in the slot immediately after electronics1.


Can non-metric TSP be approximated within some non-constant value?

Indeed, it trivially can.
If each edge has positive integer weight $w_e$, then any algorithm that outputs a valid tour has approximation ratio $w_{max} = \max_e w_e$, since the optimal solution costs at least $n \cdot 1 = n$ while the cost of any valid tour $T$ is at most $\sum_{e \in T} w_e \le n \cdot w_{max}$.

Note: If edges can have weight zero this argument won't work, because in that case even deciding if a tour of cost zero exists is NP-hard; you can reduce Hamiltonian Cycle to it. Hence your algorithm will sometime output a nonzero cost tour, when a zero cost tour exists, which means the approximation ratio cannot be bounded.


Why is $A \lor (A \land \neg B) \equiv A$?

I find pictures are great for anything simple enough to use them, which this is.

Remember:

AND means the area taken up by both things. So the middle one is what is taken up outside B, but also inside A. Their junction is not counted because it is inside A but not outside B.

OR means it is covered by either one or both. Both of them cover the part of A that is outside B, and the junction is covered by A (first picture) so it is counted too.
All in all, you just have A again.

Sorry if this is too simplistic, not sure what level you are at.


The alphabet is {a, b}. Show that the set of words with the same number of occurrences of a and b is not regular

I am purposefully not going though all the steps required to solve the exercise (comment if you need more help).

You might want to have a look at pumping lemma for regular languages
.

It gives you a property that all regular languages must satisfy. If you want to show that a language  $L$ is not regular, you can show that this property cannot hold. In practice, the proof usually follows these steps:

assume towards a contradiction that $L$ is regular
choose a suitable word $w \in L$
apply the pumping lemma on $w$ to conclude that a new word $w'$ must belong to $L$
Use the language definition to show that $w'$ does not belong to $L$ (hence the contradiction).

Hint:

   Here is a string $w$ that belongs to your language: $a^n b^n$, for a sufficiently large integer $n>0$.


Are Context-Free Grammars with only one Production Rule always Unambiguous?

Unfortunately, your conjecture is wrong.

For instance $S \rightarrow aSSb | \epsilon$ is ambiguous.

To see that take $w: aabb$. For this string we have following two distinct derivation tree possible. In following derivation trees $e$ represents $\epsilon$

        S                            S
  /  /    | \                  / /    |    \
a  S      S  b                a S     S     b
 / | \ \   \                    |   / / | \
a  S  S b   e                   e  a S  S  b
   |  |                              |  |
   e  e                              e  e

Second counter example:

Consider grammar $S \rightarrow SaSbSaS | \epsilon$
It's easy to see that this grammar is ambiguous. (hint: take $w: abaaba$.)

Third counter example:

Consider grammar $S \rightarrow abSabSab | \epsilon$.
Take $w = abababababab$. It's easy to see that there are two distinct derivation trees.

Actually this grammar is directly derived from grammar $S \rightarrow aSaSa|\epsilon $ by homomorphism $h(a) = h(ab)$.


Orlp gives a solution using $O(n)$ words of space, which are $O(n\log n)$ bits of space (assuming for simplicity that $n=m$). Conversely, it is easy to show that $\Omega(n)$ bits of space are needed by reducing set disjointness to your problem.

Suppose that Alice holds a binary vector $x_1,\ldots,x_n$ and Bob holds a binary vector $y_1,\ldots,y_n$, and they want to know whether there exists an index $i$ such that $x_i=y_i=1$. They run your algorithm for the $2\times(2n-1)$ matrix whose rows are $x_1,0,x_2,0,\ldots,0,x_n$ and $y_1,0,y_2,0,\ldots,0,y_n$. After the first row is read, Alice sends Bob $\sum_i x_i$ as well as the memory contents, so that Bob can complete the algorithm and compare $\sum_i (x_i+y_i)$ to the number of connected components. If the two numbers match, the two vectors are disjoint (there is no index $i$), and vice versa. Since any protocol for set disjointness needs $\Omega(n)$ bits (even if it can err with a small constant probability), we deduce an $\Omega(n)$ lower bound, which holds even for randomized protocols which are allowed to err with some small constant probability.

We can improve on Orlp's solution by using noncrossing partitions. We read the matrix row by row. For each row, we remember which 1s are connected via paths going through preceding rows. The corresponding partition is noncrossing, and so can be encoded using $O(n)$ bits (since noncrossing partitions are counted by Catalan numbers, whose growth rate is exponential rather than factorial). When reading the following row, we maintain this representing, and increase a counter whenever all ends of some part are not connected to the current row (the counter takes an additional $O(\log n)$ bits). As in Orlp's solution, we add a final dummy row of zeroes to finish processing the matrix. This solution uses $O(n)$ bits, which is asymptotically optimal given our lower bound.


ZigZag sequence without dynamic programming

Your simple algorithm is correct.

In fact, you have proved the correctness of your algorithm basically since your algorithm is, as you have written, based on finding all the local maximum and minimum of the original sequence. The simple mathematical reason is that for each zigzag, i.e., $a[i]<a[i+1]>a[i+2]$ or $a[i]>a[i+1]<a[i+2]$, there must exist a local maximum or a local minimum respectively.

A more rigorous and rather tedious proof is needed to convince all of us that there is no off-by-one error in your program. However, I will skip it since it is routine and not enlightening at all.


Literature request: Generating all vertex subsets of a graph

This does not seem likely to be useful in any application.  We already know of straightforward algorithms for constructing all vertex subsets, and they are are about as efficient as possible.  So, if you have a complicated way to construct all vertex subsets, that's not particularly useful, as it is a more complicated way to do something we already know how to do in a simpler way.  I cannot imagine any reason why an application would choose your method instead of standard methods.


Can the heaviest edge ever be in an MST?

No, it is not true. Consider a graph with 2 vertices and an edge between them. This is the heaviest edge, and it will be in the minimum spanning tree of $G$.


How a Symbolic Evaluator Generates Test Input for this Example

Tools that solve problems like this often use a SMT (Satisfiability Modulo Theories) solver. This a SAT solver combined with a "theory solver" that can understand operations in some domain.

For example, constraints involving = and != can be decided using union find; constraints involving < on numbers can be decided using the simplex algorithm.

Operations on strings are trickier. Searching "regex string constraint" on Google Scholar finds many papers discussing approaches.

The abstract of this survey papers gives a very brief preview From An Evaluation of Automata Algorithms for String Analysis but notes there is no consensus on a single algorithm (emphasis mine):

https://doi.org/10.1007/978-3-642-18275-4_18

  There has been significant recent interest in automated reasoning techniques, in particular constraint solvers, for string variables. These techniques support a wide variety of clients, ranging from static analysis to automated testing. The majority of string constraint solvers rely on finite automata to support regular expression constraints. For these approaches, performance depends critically on fast automata operations such as intersection, complementation, and determinization. Existing work in this area has not yet provided conclusive results as to which core algorithms and data structures work best in practice.

It seems the best way to algorithmically process regexes is to operate on the NFAs/DFAs that they represent, and, judging by the number of papers on it, there are effective algorithms for making the required decisions.

HAMPI seems to be an important early paper describing how this can be done, which is provided online by one of the authors:
https://homes.cs.washington.edu/~mernst/pubs/string-solver-tr004.pdf


Maximum number of points that two paths can reach

The problem, restated and generalized: given a finite set $S$ equipped with a partial order $\le$, find chains $C_1, C_2 \subseteq S$ maximizing $\lvert C_1 \cup C_2 \rvert$. The question is about the case where $S \subseteq \mathbb R_+^2$ and $(x, y) \le (z, w) \Longleftrightarrow x \le z \wedge y \le w$.

Naively, one might try to find the single best chain in $S^2$, where best is measured by how many distinct values the components of the chain have. Unfortunately, one component can retrace the steps of the other, e.g., $$\bigl((0,0),(0,0)\bigr) < \bigl((1,0),(0,0)\bigr) < \bigl((2,0),(0,0)\bigr) < \bigl((2,0),(1,0)\bigr),$$ so this notion of best does not have optimal substructure.

Instead, we look for chains in the set $T := \{(x, y) \mid (x, y) \in S^2 \wedge x \nless y \wedge y \nless x\}$. By requiring that the components be equal or incomparable, we prevent retracing but now need to argue that some best chain conforms to the new requirement.

Lemma 1 (no retracing). Let $C \subseteq T$ be a chain and define $C_1 := \{x \mid (x, y) \in C\}$ and $C_2 := \{y \mid (x, y) \in C\}$. For all $z \in S$, we have $z \in C_1 \cap C_2$ if and only if $(z, z) \in C$.

Proof. The if direction is trivial. In the only if direction, for all $z \in C_1 \cap C_2$, there exist $x, y \in S$ such that  $(x, z), (z, y) \in C$. Since $C$ is a chain, $(x, z) \le (z, y) \vee (z, y) \le (x, z)$. Assume symmetrically that $(x, z) \le (z, y)$, which implies that $x \le z \le y$. We know by the definition of $T$ that $x \nless z \wedge z \nless y$, so $x = z = y$, and $(z, z) \in C$.

Lemma 2 (existence of restricted best chain). For all chains $C_1, C_2 \subseteq S$, there exists a chain $C \subseteq T$ such that $C_1 \subseteq \{x \mid (x, y) \in C\} \subseteq C_1 \cup C_2$ and $C_2 \subseteq \{y \mid (x, y) \in C\} \subseteq C_1 \cup C_2$.

Proof (revised). We give an algorithm to construct $C$. For convenience, define sentinels $\bot, \top$ such that $\bot < x < \top$ for all $x \in S$. Let $C_1' := C_1 \cup \{\top\}$ and $C_2' := C_2 \cup \{\top\}$.

Initialize $C := \varnothing$ and $x := \bot$ and $y := \bot$. An invariant is that $x \nless y \wedge y \nless x$.
Let $x'$ be the next element of $C_1$, that is, $x' := \inf \{z \mid z \in C_1' \wedge x < z\}$. Let $y'$ be the next element of $C_2$, that is, $y' := \inf \{w \mid w \in C_2' \wedge y < w\}$.
If $x' \nless y' \wedge y' \nless x'$, set $(x, y) := (x', y')$ and go to step 9.
If $y < x' < y'$, set $(x, y) := (x', x')$ and go to step 9.
If $y \nless x' < y'$, set $x := x'$ and go to step 9. Note that $x < x' \wedge x \nless y$ implies that $x' \nless y$.
If $x < y' < x'$, set $(x, y) := (y', y')$ and go to step 9.
If $x \nless y' < x'$, set $y := y'$ and go to step 9. Note that $y < y' \wedge y \nless x$ implies that $y' \nless x$.
This step is never reached, as the conditions for steps 3–7 are exhaustive.
If $x \ne \top$ (equivalently, $y \ne \top$), set $C := C \cup \{(x, y)\}$ and go to step 2.

Dynamic Program. For all $(x, y) \in T$, compute $$
D[x, y] := \sup\biggl(\Bigl\{D[z, w] + [x \ne z] + [y \ne w] - [x = y] \mathrel{\Bigl|\Bigr.} (z, w) \in T \wedge (z, w) < (x, y)\Bigr\} \cup \bigl\{2 - [x = y]\bigr\}\biggr),
$$
where $[\textit{condition}] = 1$ if $\textit{condition}$ is true and $[\textit{condition}] = 0$ if $\textit{condition}$ is false. By Lemma 1, it follows that the bracket expressions correctly count the number of new elements. By Lemma 2, the optimal solution to the original problem is found.


Approximability of convex programming (convex optimization)

You haven't defined convex optimization in general, and indeed it is not clear how one would encode a general convex optimization problem. However, to answer your question it suffices to consider the special case of copositive programming. It is known that Independent Set can be expressed as a copositive program, and this problem is NP-hard to approximate up to a factor of $n^{1-\epsilon}$ for every $\epsilon > 0$. In particular, there is no PTAS.


What is the set of all minimal 3CNF formulas?

The number of minimal formula is finite.  Indeed, if a formula is minimal, then no clause can be repeated.  Now there are $(2n)^3=8n^3$ possible clauses, so there are at most $2^{8n^3}$ different formulas with no repeated clauses.  Thus there are at most $2^{8n^3}$ minimal formula, which is finite.

I don't know of any clean way to count the number of minimal formula; probably there is no simple formula for it.  You could try computing the number for $n=1,2,3$ by brute-force, then looking up the resulting sequence in OEIS, but I don't expect you to find any simple expression for this number.

What you are thinking is wrong.  A minimal, unsatisfiable formula can have more than 8 clauses.


Maximising a particular colour in a vertex colouring

Your problem is just the (maximum) independent set problem.


Suppose the first byte of the compressed file indicates which decompression algorithm to use, and then you use that algorithm to decompress the rest.  Sure, you could do that.  Absolutely.  Some compression formats already do exactly this.

That said, it's also possible to view this as a single decompression algorithm.  The master algorithm looks at the first byte of the file and then branches to a subroutine that handles the rest of the file.  That can be considered a single algorithm.  So at a fundamental level there is no fundamental distinction that can be drawn.


How to calculate sum of binomial coefficients efficiently?

Hint: Use Lucas's theorem.

In general, any time a programming contest problem wants you to compute something mod $p$, check for opportunities to reduce everything mod $p$ before doing any further work.

Spoilers

Don't peek at any hint until you've spent a good amount of time thinking about the previous one!

A more in-depth hint if the previous wasn't enough:

   Let $p=10^9 + 7$.  Use Lucas's theorem to express $\binom{n}{i}$ in terms of functions of $n \bmod p$ and $i \bmod p$.  Simplify the resulting sum by grouping terms.

If that's still not enough of a hint:

   Consider the case where $k$ is a multiple of $p$.  You should be able to come up with an efficient algorithm for that whose running time is something like $O(k/p)$.

Then for a final answer:

   Generalize to the case where $k=ap+b$.  You should be able to express this as a sum of the previous form, plus $b$ more terms.  As a result you should be able to achieve a final running time of $O(p)$.


A context-free grammar is in Chomsky normal form if all productions are of the form $A \to BC$ (where $B,C$ are not the starting symbol), $A \to a$, or $S \to \epsilon$, where $S$ is the starting symbol. A context-free grammar is in Greibach normal form if all productions are of the form $A \to a\alpha$, where $\alpha$ consists only of non-terminals (but not the starting symbol), or $S \to \epsilon$, where $S$ is the starting symbol.

Every context-free grammar has an equivalent context-free grammar in Chomsky normal form, and another one in Greibach normal form; there could be several equivalent context-free grammars in either normal form.

When you applied the rules to convert your grammars into normal form, you got Chomsky normal form because the rules were designed for converting a given context-free grammar to Chomsky normal form. You could follow other rules and get Greibach normal form.


Have any natural complexity classes been proven not to be closed under complement?

There may be no such natural class, i.e. all natural classes are closed under complement.

Despite that $\mathrm{DTIME(n)\neq NTIME(n)}$ was proven, it is still possible that $\mathrm{NTIME(n^k)=co-NTIME(n^k)}$ for all natural number $k\geq1$.

For other kinds of model,we can similarly say that it is still possible:
$$\mathrm{RTIME(n^k)=co-RTIME(n^k)=ZPTIME_{\geq\frac12}(n)}$$ for all $k\geq1$.

Also, $\mathrm{UP=co-UP}$, etc.

And more importantly, all of these could SIMULTANEOUSLY hold if $\mathrm{L=CH}$ or $\mathrm{P=PP=CH}$ without violating any known complexity result.


Iterative lengthening search: iterative version of Uniform Cost Search or DFS?

Typically iterative deepening searches are used with DFS to improve the memory usage.

Consider BFS and IDDFS, both are optimal and complete but IDDFS in a tree search will use only $O(bm)$ space, where $b$ is thebranching factor and $m$ is the maximum height of the goal.

Now extending this to Uniform Cost Search using DFS, if we increase the max depth step by step, we are doing too many iterations over already visited nodes, whereas this was not true in case of IDDFS because of one step increase at a time (look for the overhead factor). So though using iterative search with DFS can save huge space ($O(bm)$), it gets worse with time complexity.

Secondly, there is no point in using Iterative Search with UCS as it is never a better upgrade over simple UCS in terms of space and time complexities.


Failing to solve a recurrence by induction

Ok lets try solving this by substitution ,
$T(n) = 2T(n-1) + 1$
from this we know , $T(n-1) = 2T(n-2) + 1$
so $T(n) = 2(2T(n-2) + 1) + 1$
$T(n) = 2^2T(n-2) + 3$
lets substitute one more time
$T(n-2) = 2^2T(n-3) + 1$
$T(n) = 2^2(2T(n-3)+1) + 3$
$T(n) = 2^3 T(n-3) + 7$
Hopefully you can notice the pattern now $T(n) = 2^{k}T(n-k) + 2^{k}-1$
So , for $k = n$
$T(n) = 2^{n}T(n-n) + 2^{n}-1$ , we know that $T(n-n) = T(0) = 1$
$T(n) = 2^{n} + 2^{n}-1$
so clearly , $T(n) = O(2^n)$


Usually, when reducing problem B to problem A, not all possible instances of problem A appear in the image of the reduction. This is absolutely not an issue.

In your case, you can say that problem A is NP-hard even if restricted only to complete graphs. This is a stronger result, which is a good thing, and definitely allowed.

As an example, 3-coloring is hard even for 4-colorable graphs, and even just for planar graphs. You show this (say) by reduction from SAT to 3-coloring, in which all the resulting graphs are planar. This is not a drawback – in fact it's a bonus.


Interactions between predictive analytics, ML, and case-based and rules-based reasoning

Personally, I'm not that enamored of the "rules-based reasoning vs case-based reasoning" categorizatin; I'm not sure it is a particularly useful mindset for modern machine learning.  For instance, deep learning is one of the most effective ML methods used today in several domains, yet it doesn't seem to fall into either of those categories.  That's just my opinion; perhaps others might find it useful.

Rather than trying to find this kind of high-level generalization about how ML works, I think it might be more useful to study some specific ML techniques: linear regression, k-nearest neighbors, SVM, random forest, deep learning, etc.


With only 2 possible values, you want to use an algorithm such as Counting Sort.

Since you only have 2 possible values, true and false, it's easy to just count how many true/false values you have. But to be more efficient, you can just count how many trues you have (or falses) instead. Because size - numTrue = numFalse.


Lower bound on number of comparisons needed to search for a number in a sorted 3-d array

Let's suppose that the array is indexed using $\{1,\ldots,N\}$, and assume for simplicity that $N$ is odd. Divide the cells in the array into three parts:
$$
\begin{align*}
X &= \{ (i,j,k) : i+j+k < 3 \tfrac{N+1}{2}, \} \\
Y &= \{ (i,j,k) : i+j+k = 3 \tfrac{N+1}{2}, \}, \\
Z &= \{ (i,j,k) : i+j+k > 3 \tfrac{N+1}{2}, \}.
\end{align*}
$$
Consider a 3D array $A$ with $A(i,j,k) = -\infty$ for all $(i,j,k) \in X$ and $A(i,j,k) = \infty$ for all $(i,j,k) \in Z$ (you can think of $-\infty,\infty$ as stand-ins for large negative and positive numbers). We claim that any such array is sorted. Indeed, suppose for example that $i_1 < i_2$ and $j,k$ are given. If $i_1 + j + k < 3\frac{N+1}{2}$ then $A(i_1,j,k) = -\infty \leq A(i_2,j,k)$. If $i_1 + j + k \geq 3\frac{N+1}{2}$ then $A(i_1,j,k) \leq \infty = A(i_2,j,k)$.

It follows that you cannot rule out that a finite number is in $A$ without checking all entries in $Y$ (formally this can be proved using an adversary argument). The number of entries in $Y$ is at least $N^3 / (3N-2) = \Omega(N^2)$.

The same idea extends to give a lower bound of $N^{d-1}/d$ in the $d$-dimensional case.


CPU Scheduling - Round Robin order on ready queue

With round-robin, the scheduler always selects the process that's had the most time since it was last run, and new processes coming in are always assigned a last run time of 1 time unit before the oldest last run time in the current list. (There are other equivalent ways to state this, but this is the simplest one for me. One other way to phrase this that works for many people is "processes that haven't had a chance to run yet have priority".)

So at t=8, we have:

Process Last-run Time-left
P1      0        5
P3      3        1
P4      -1*      6

Note the -1 for P4. The oldest last run time is P1, with 0. So P4 gets assigned -1, and hence gets selected.


Shoup (Section 3.3.5, Theorem 3.3, p. 62) gives a bound for computing the residue $r$ in time $O(n\log q)$ where $a = q\cdot p +r$ and $\log a = n$.

I guess that if $p$ and $a$ are both roughly $n$ bit numbers, then $q$ (and hence $\log q$) should be rather small, giving $O(n)$.

If $a$ is an $n$-bit number, and $p$ is relatively small, then the multiplication approach should be faster.


Eliminating left recursion and left factoring this grammar

check this image the problem is explained


How can random array access be considered $O(1)$ if bits must be stored in space and light travels at finite speed?

When we talk about "running time" of algorithms, we don't mean literally time in seconds but number of operations in some abstracted machine model. In such a model, accessing a memory cell is taken to be a single operation, taking unit time.

Note that this is hiding much more significant details of real computers than the speed of light across a chip.  Whether or not the required data is in the cache will have a much more significant effect than any consideration based on the speed of light.


Is it true that $FP^{NP[log\cdot n]} = FP^{NP}$ if $P = NP$?

The reverse

The reverse is true. If $FP^{NP[log]} = FP^{NP}$ then $P = NP$.

You can quickly find this in the Complexity Zoo; It was proven in
M. Krentel. The complexity of optimization problems, Journal of Computer and System Sciences 36:490-509, 1988.

The actual question

The other way around is easier. To quote the definition from Complexity Zoo:

  $FP^{NP[log]}$: $FP$ With Logarithmically Many Queries To $NP$

Therefore, if $P = NP$, $FP^{NP[log]} = FP^{P[log]}$. Logarithmically many queries to $P$ is certainly a subset of $NP$, so (if $P = NP$) $FP^{NP[log]} = FP^{NP}$.


Regex for bit strings with at least two zeros but no consecutive zeros

The shortest regex I came up with is: 1*01+0(1+0?)*

Start with arbitrary amount of 1s (1*)
Exactly one 0 (0)
One or more 1s (1+)
Another 0: (0)
Arbitrarily often ((...)*):

One or more 1s (1+)
At most one 0 (0?)


Minimal DFA for language of all strings over $\{a,b\}$ whose penultimate symbol is $b$

Note that we have at least three states:

The second last character is $b$ so the tail 2-substring is either $ba$ or $bb$.
The last two characters are $ab$ (read at least one more character).
The last two characters are $aa$ (read at least two more characters).

which leads to the following DFA:

The above DFA contains minimal number of states if and only if it equals its minimization. Following this page in DFA Minimization using Equivalence Theorem we have

$P_0 = \{(1, 2), (3)\}\\
P_1 = \{(1), (2), (3)\}$

In $P_1$ we used the fact that one single character may lead state 2 to an accepting state, whereas 1 does not "reach that far". Since $P_1$ gives no opportunity for further refinement, we may stop and we know that the DFA is minimized.


Why can't we simulate an NP oracle with an NP machine?

You don't have exponential time, what you have is a nondeterministic polynomial time machine.

What you can try to do, in order to simulate the oracle call to $\mathcal{O}\in NP$ on a string $s$, is to run the nondeterminstic polynomial machine $M_\mathcal{O}$ on input $s$. If $M_\mathcal{O}$ returned "yes" then you know $s\in\mathcal{O}$, but if it returned "no", then you cant be sure, and you don't have enough resources to try out all possible branches in an NP machine.


Can problems of class P be transformed into SAT formula?


Curry-Howard, void, and type checking in Haskell

I would find a different tutorial because the author of that one is fundamentally confused. They wrongly claim that $\neg a$ and $\bot\to a$ are equivalent ($a\to\bot$ would be correct), and also wrongly claim that you can't write a function of type $\texttt{Void}\to a$.
$\texttt{Void}\to a$ is vacuously true. In principle a function of that type should require no definition at all because the number of cases for which you need to define it is zero. GHC doesn't accept that, but (with -XEmptyCase) it does accept
f :: Void -> a
f x = case x of {}

which is a perfectly valid, logically sound definition.

Why does the Haskell compiler approve the type of proposition?

The proposition as written in the Haskell code is actually true. The proof is invalid though since it uses $\texttt{undefined}$.
If you replaced the right hand side with $(b\to\texttt{Void},a)$ then it would be false, but you could still "prove" it using $\texttt{undefined}$; in fact you could just write $\texttt{proposition} = \texttt{undefined}$ and the type checker would accept that. It would also accept $\texttt{proposition} = \texttt{proposition}$. If you want to use Haskell as a Curry-Howard sandbox you have to take care that your code doesn't throw an exception or fail to terminate, because the compiler won't catch those errors.

Response to edit: your proof is correct but it can be simplified. In the first case, there's no need to create a function and immediately apply it to one of its arguments. Instead of (\z1 z2 -> z1) x you can write \z2 -> x, or \_ -> x since the argument/premise isn't used. In the second case, you don't need to prove b -> a since you already have g :: b -> a. The simplified proof is
proposition (Left x, _) = Right (\_ -> x)
proposition (Right g, _) = Right g

In addition to the pitfalls that Dan Doel mentioned in a comment, missing cases are another thing to watch out for. GHC by default doesn't even warn about them. With -Werror=incomplete-patterns it will refuse to accept programs with missing cases.
You can prove negations. You need to return a value of type $\texttt{Void}$, which you can't create yourself but you can get from elsewhere. For example here's a proof of $((P\Rightarrow Q) \mathbin{\&} \neg Q)\Rightarrow \neg P$:
f :: (a -> b, b -> Void) -> (a -> Void)
f (x, y) = \z -> y (x z)

You may reasonably wonder where your caller got the value of type $\texttt{Void}$, but that's the caller's problem, not yours. Deriving a contradiction in a subproof doesn't mean the logic is inconsistent, it just means you've shown that you'll never actually reach this point in the real world.


The first thing that comes to mind would be a divide-and-conquer method where, for some reason, 50% of the time you only need to do one subproblem, and the other 50% of the time you need to do both subproblems.

The recursion for the average case runtime would be

$$ T(n) = 0.5 \cdot T(n/2) + 0.5 \cdot (2 \cdot T(n/2)) + f(n) = 1.5 \cdot T(n/2) + f(n) $$

(the fine print: this require some assumption of independence between the probability you have to do both problems and the runtime of the subproblems)

That said, the master theorem is for asymptotically solving recurrences. Not every recurrence solving problem is about the runtime of an algorithm.

Furthermore, there is no point in going out of your way to excluding cases. Insisting that $a$ is an integer doesn't simplify anything at all, so all it achieves is to make the statement (and proof too, probably) more complicated, and to frustrate those people who find a use for those cases anyways.


No, just take as counter example $L_1=\epsilon$ and $L_2$ any other langage different from $L_1$.


simulation of PDA with 2-tape Turing machine

The first tape for input and the second for storing symbols (like on a stack). The first tape should be read-only so that the TM reads symbols one by one from left to right.

Every time your PDA writes a symbol on the stack, your TM moves the second head right and writes a symbol on the rightmost empty cell. When the PDA removes a symbol from the stack the TM replaces the rightmost symbol with the blank symbol (erases) and moves the second head left. On each state transition the first head should always move right.

In addition, your TM shouldn't be allowed to arbitrarily move heads right and left violating PDA rules.

Consider the following formal definition of moves for PDA (assume deterministic for simplicity):

UPDATE

Definition of PDA moves

$\delta(q, a, Z) = (p, \alpha)$: the PDA in state $q$ with input $a$ and $Z$ on the top of the stack. The PDA enters the state $p$ and replaces the top symbol $Z$ with the symbols of the string $\alpha$. So, $\delta(q, a, Z) = (p, \epsilon)$ means remove the top stack symbol (pop). Advance the input head one symbol.

$\delta(q,\epsilon, Z) = (p, \alpha)$: the PDA in state $q$ with $Z$ on the top of the stack. Independent of the input symbol, PDA enters the state $p$ and replaces the top symbol $Z$ with the symbols of the strings $\alpha$. Input head does not advance in this case.

Examples of translation of PDA moves into TM moves

Example 1.
PDA move $\delta(q_1, 0, A) = (q_2, B)$ is translated as: TM in state $q_1$, head 1 (input head on the tape 1) reads $0$, and head 2 (stack head on the tape 2) reads $A$. Replace $A$ with $B$ (head 2 writes the symbol $B$ while it is on $A$). Advance head 1 one symbol. Enter state $q_2$.

Example 2.
$\delta(q_1, 0, A) = (q_2, BC)$ is translated as: TM in state $q_1$, head 1 reads $0$, and head 2 reads $A$. Head 2 writes $B$ (replaces $A$), advances head 2 one symbol, TM enters state $q_{21}$. Then, while TM in state $q_{21}$ and head 1 reads $0$, and head 2 reads the blank symbol: head 2 writes symbol $C$, enters state $q_2$. Advance head 1 one symbol.

The basic idea: in order to write $BC$ we introduced a new state $q_{21}$.

Analogously, $\delta(q,\epsilon, Z) = (p, \alpha)$ means head 2 just writes the blank symbol and moves left.

$\delta(q,\epsilon, Z) = (p, \alpha)$ means that you define the same transition for every input symbol.

This is how a multitape Turing machine is defined.


How do I see SSL/TLS packet data in clear?

Sure.  Yes, you can capture the packets and view them.  That'll work.  It's a useful, informative exercise.

You can use Wireshark (or some other packet capture tool) to capture the packets involved in the TLS handshake and view the captured  packets.  It'll show you the raw bytes, and also decode the handshake messages for you.  Wireshark has a nice GUI that might make it easier to use, so I recommend that as your first choice, if you haven't done anything like this before.

I don't see any reason why you'd use SSL strip.


Complexity of calculating independence number of a hypergraph

did not find a proof of complexity class harder than "NP hard" for this problem (ie the presumably more complex hypergraph version of the problem does not seem to have been proven harder than the graph version) however did find the following. Saket has recent research in the area. results in complexity theory in active areas of research tend to be highly specialized and in the form "for limited hypergraph types [x], the following improved complexity bound [y] is shown." (ie more as approximability results, & more specialized than what you request but it can be mined for nearest desirable results/refs.)
basically hypergraphs while an old mathematical concept are a more recent area of complexity theory research and there is a large active/ongoing research program of determining complexity of operations around them and how those complexities relate to corresponding graph operation complexities, and translating theorems and knowledge about graphs into their hypergraph analogs.

Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisﬁable CSPs Saket (Dec 2013)

This work revisits the PCP Veriﬁers used in the works of H˚astad [H˚as01], Guruswami et al. [GHS02],
Holmerin [Hol02] and Guruswami [Gur00] for satisﬁable MAX-E3-SAT and MAX-Ek-SET-SPLITTING,
and independent set in 2-colorable 4-uniform hypergraphs. We provide simpler and more efficient PCP
Veriﬁers to prove ... improved hardness results ...

Hardness of Maximum Independent Set in Structured Hypergraphs Saket powerpoint slides overview


Is there a LL(K) Grammar which is not LALR(K) Grammar?

Every $LL(k)$ grammar is $LR(k)$, but there are $LL(k)$ grammars which are not $LALR(k)$.

There's a simple example in Parsing Theory by Sippu&Soisalon-Soininen

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

The language of this grammar is finite, so it is obviously $LL(k)$. (In this case, $LL(3)$.) The grammar is also $LR(1)$. However, the grammar is not $LALR(k)$ for any value of $k$.

The canonical $LR(k)$ machine has two states with $LR(0)$ itemsets $\{[A\to c \cdot], [B\to c\cdot]\}$. These two states have different lookahead sets in each item, corresponding to the two different predecessor states before shifting $c$. The $LALR$ algorithm merges these two states, thereby losing the distinction between the lookahead sets. This produces two reduce-reduce conflicts. Since there is only one token of lookahead at this point, increasing $k$ would make no difference.


Worst-case time algorithm?...which one is faster?

If $g(n) = \Omega(f(n)\log n)$ then for large $n$, $g(n) \geq Cf(n)\log n$ (for some $C > 0$, and so algorithm $B$ takes more time than algorithm $A$ (in the worst case). In other words, algorithm $A$ is faster.

If $g(n) = O(f(n)\log n)$ then all we know is that for large $n$, $g(n) \leq Cf(n)\log n$; it could be that also $g(n) = \Omega(f(n)\log n)$, in which case algorithm $A$ is faster; or it could be that $g(n)$ is constant while $f(n) = n$ (for example), in which case algorithm $B$ is faster; and there are other possibilities.

If $g(n) = \Theta(f(n)\log n)$ then in particular $g(n) = \Omega(f(n)\log n)$, and so we revert to the first case.