Implications of truncation of numbers when converted into binary

This is specifically about real numbers — integers can be represented exactly. Actually, real numbers can be represented exactly too, at least the one that matter, but this is very inefficient, so for most applications real numbers are represented by a floating point approximation.

By the way, this isn't specific to decimal numbers (numbers that can be represented in base 10 with a finite number of digits after the decimal point). No matter what base you choose, you can only represent a tiny subset of the real numbers (you can't even represent all rationals).

When computing with approximations, it's important to keep in mind that each step of computation may make the approximation worse, so that after many steps it's not always obvious how precise the result is — in some cases, the result is meaningless because the magnitude of the uncertainty is larger than the result. Numerical algorithms need to be constructed carefully to minimize errors due to approximations.

There is a whole subfield of computer science devoted to floating point calculations. To start with, read the classic paper What Every Computer Scientist Should Know About Floating-Point Arithmetic by David Goldberg.


The Hindley-Milner type system plus polymorphic recursion is undecidable or semidecidable?

The answer you gave is right, but I'd like to stress the relationship between the two terms.

A formal language is decidable if and only if there exists an algorithm which correctly accepts or rejects every input in finite time. We also say it's computable.

A formal language is undecidable if and only if it is not decidable.

A formal language is semidecidable if and only if an algorithm exists that recognizing an input that is in the language. In particular, all decidable languages are semidecidable! However the halting problem is an example of a semidecidable language that is also undecidable. The complement of the halting problem is not even semidecidable.

We say type inference is undecidable rather than semidecidable (even though both characterizations are true) because the former is usually more relevant.


How to remove cycles from a directed graph by edge contraction?

Since the only way to get rid of a cycle by edge contractions is to contract all the edges of the cycle to result in a single vertex, the vertices of the new graph are the strongly connected components of the original graph. Two vertices have an edge between them if the original components corresponding to these two vertices had such an edge in the same direction.

Strongly connected components can ve found in linear time.


Definitions of Computer Architecture and Computer Organization seems confusing

It seems that the important difference between the terms as used here is that computer architecture is about useful things the system can do for its user (the programmer), and that computer organization is about how to build and connect "units" in order to create such a system.
I will first note that your argument here is not correct: while I agree architecture is about organizing and building things, computer architecture is, according to your book, not about building things. Note that "computer architecture" and "architecture" are not the same. A technical term with a definition is what the definition says it is, no more, no less.1 Any relation the name may have with the English language is irrelevant.2
For example, if I define a particular combination of points and lines to be a caterpillar, then a caterpillar is exactly that and any complaint that a combination of points and lines cannot turn into a butterfly is irrelevant.3
According to what the definitions computer architecture and computer organization say, it seems to me that (assuming "integrating functional blocks" and "interconnecting operational units" are interchangeable) Statements 1 and 2 are true, while 3 and 4 are false. I encourage you to work out the details on your own, using the definitions of the terms involved.

1: Or, as Lewis Carroll wrote:

"When I use a word," Humpty Dumpty said, in rather a scornful tone, "it means just what I choose it to mean—neither more nor less."

 2: That said, it certainly is annoying when the name of a term seems to outright contradict its definition (cf. the lines in the poem preceding the quoted line of Mr. Dumpty), and I think the particular names chosen for the definitions in your book are not that good, to be honest. Naming concepts is an art in itself and not many good scientists are also good artists, or even want to be. So many concepts have unfortunate names, but if you read a book that uses those names, you will have to live with it.
3: No, I did not make this up. Someone else beat me to it.


Lemma 2 in Knuth's "Notes on Open Addressing"

I think that the notes have been reported incorrectly. Indeed CruiskeenLawn, you are right. I've found some very old notes
here which report the correct result. Indeed, in your copy, they simply forgot to add $\left[\begin{matrix} t\\ t\end{matrix}\right]$ term.
The Lemma you are looking for is on Page 2.


Product of the entries of the product of two matrices

You are asking two questions. I will only answer the second one. Let $1$ be the all ones column vector of dimension $n$. The sum of all entries of $AB$ is $1^TAB1 = (1^TA)(B1)$, which gives an $O(n^2)$ algorithm: compute the vectors $1^TA$ and $B1$, each in $O(n^2)$, and then compute their inner product in $O(n)$. This corresponds to the identity
$$
\sum_{i,j,k=1}^n a_{ik} b_{kj} = \sum_{k=1}^n \left(\sum_{i=1}^n a_{ik}\right) \left(\sum_{j=1}^n b_{kj}\right).
$$

As for the product of all entries, I suspect you can't do better than the trivial algorithm which first computes the entire product matrix, and runs in time $O(n^\omega)$.


what is glushkov NFA. What is the difference between Glushkov NFA and Thompson NFA?

The most significant difference is that Glushkov's NFA does not use $\epsilon$-transitions.  Very roughly, the algorithm indexes the characters in the regular expression from left to right.  Each state in the NFA is a subset of possible indices of the last character read from the input string.

Glushkov's construction [3] is described in detail in Aho, Sethi, and Ullman's classical compiler textbook, aka "The Dragon Book" [1].  The same construction was also described earlier by McNaughton and Yamada [4] and later  by Berry and Sethi [2], so you may find it easier to search under those names.

A. V. Aho, R. Sethi, and J. D. Ullman.  Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1988.
G. Berry and R. Sethi. From regular expressions to deterministic automata.  Theoretical Computer Science 48:117–126, 1986.
V. M. Glushov.  The abstract theory of automata.  Russian Mathematical Surveys 16:1–53, 1961.
R. McNaughton and H. Yamada.  Regular expressions and state graphs for automata.  IEEE Trans. Electronic Computers 9(1):39–47, 1960.


Does a language have a regular expression if and only if it is regular?

Yes, a language can be described as a (pure vanilla) regular expression if and only if it is regular. You can see the proof in any decent textbook on formal languages.


Integer Problem Solving with two boolean selection variables

Sure, try integer linear programming.  Let $x_{RA1}$ be a zero-or-one variable that is 1 if you select RA1, or 0 if you don't.  Then each of your constraints can be expressed as linear inequalities with these variables.  You can then try applying an off-the-shelf ILP solver.

There are a bunch of other questions on this site with further examples of using ILP to solve combinatorial problems (e.g., Express boolean logic operations in zero-one integer linear programming (ILP)), so feel free to look around.


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


Understanding why the polynomial $p(n) = \sum_{i=0}^{k} a_in^i$ is in $\Theta(n^k)$

The starting point is the inequality $p(n) \geq a_kn^k - An^{k-1}$. We want to deduce from this inequality that for large enough $n$, $p(n) \geq bn^k$ for some $b > 0$. So take any $b > 0$ satisfying $b < a_k$. Since $$p(n) \geq a_k n^k - An^{k-1} = \left(a_k - \frac{A}{n}\right) n^k,$$ we have $p(n) \geq bn^k$ as long as $a_k - A/n \geq b$. As $n \to \infty$, $A/n \to 0$, and so it is clear that the inequality $a_k - A/n \geq b$ holds for large enough $n$. If we want an explicit lower bound on $n$, we can do some algebra to obtain the equivalent inequality $n \geq A/(a_k - b)$.


Why don't imperative languages like C or Go support Haskell-like parametric polymorphism?

The real answer is that the designers of those languages chose not to include it.

It's certainly technically possible. As has been said in the comments, Rust does, Java does, C# does, etc. However, there are some difficulties.

The first is in the choice of impelemtation strategy. Polymorphism is easy if you're working with Lambda Calculi and looking only at what reductions work. But when you want actual code that runs on a machine, there are two main strategies, each with their own tradeoffs:

Monomorphization: For each specialization of your polymorphic function that's used, you make a specialized copy of it in the machine code emitted. This option is great when you're using a language that actually emits machine code, and tends to be fast, since you can optimize the different versions of your code. But, it tends to increase the size of your program.
Pointers: The main reason you can't just use a function polymorphically is that you might give it arguments of different size, so when it's looking things up on the stack, it doesn't know their offsets. But if you always give it pointers to its arguments, then it can lay things out nicely. This way is simpler, but has slowness from an extra layer of indirection.

As for why the particular languages didn't use it, for C it's mostly historical. It wasn't really a mainstream thing when it was made, and it hasn't made its way into the main language. For Go, the decision has been quite controvertial, but again their main goals were simplicity, concurrency and code whose performance was easy to reason about.

Also, polymorphism breaks type soundness in the presence of mutable variables, which is why Rust only allows polymorphic functions, and ML has the value restriction.


What is the best way to merge cycles to minimise total weight?

This is NOT an answer. This post is just to construct a concrete numeric example out of the left diagram in the picture in the question.

(This answer, too long to fit as a comment, was requested by a user who wanted to see a concrete numeric example which his greedy algorithm may fail. It was written about the same time when OP added a numeric example that is exactly the same except a slightly different weight assignment.)

Let $G$ be the complete undirected graph on 12 vertices $A_1, A_2, A_3, A_4, B_1, B_2, B_3, B_4, C_1, C_2, C_3, C_4$.

Let $S$ be the set of the following three simple circles.

the circle $c_A$: $A_1, A_2, A_3, A_4, A_1$.
the circle $c_B$: $B_1, B_2, B_3, B_4, B_1$.
the circle $c_C$: $C_1, C_2, C_3, C_4, C_1$.

All edges in the three circles weigh 1. The edges $A_3B_2, A_4B_1, B_3C_2, B_1C_4, C_3A_2$ and $C_4A_3$ weigh 2.
  - All other edges weigh 16.

We are allowed to merge two cycles by removing an edge from each cycle and connecting them up with two new edges, repeatedly until we reach a single cycle. The goal is to reach a cycle with the smallest total weight.

A description of an optimal solution for $S$.

Remove edge $A_2A_3$ and $B_2B_3$. Add edge $A_3B_2$ and $A_2B_3$.
Remove edge $A_2B_3$ and $C_2C_3$. Add edge $B_3C_2$ and $C_3A_2$.

We end up with the simple cycle $A_1, A_4, A_3, B_2, B_1, B_4, B_3, C_2, C_1, C_4, C_3, A_2, A_1$, which has weight $3* 2+ 9*1 = 15$.

A description of greedy algorithm on $S$ that considers all pairs of two existing cycles at a time.

Since the three cycles are symmetric, WLOG, let us merge cycle $C_a$ and cycle $C_b$. To avoid adding an edge whose weight is 16, we have only one choice. Remove edge $A_3A_4$ and $B_1B_2$. Add edge $A_3B_2$ and $A_2B_3$. The resulting circle, named $c_{AB}$, is $A_1, A_2, A_3, B_2, B_3, B_4, B_1, A_4, A_1$.
Now it is time to merge $c_C$ and $c_{AB}$. To avoid adding an edge whose weight is 16, we have only two choices. We can either remove $B_3B_4$ and $C_1C_2$ and add $B_3C_2$ and $B_4C_1$, resulting with cycle $A_1, A_2, A_3, B_2, B_3, C_2, C_3, C_4, C_1, B_4, B_1, A_4, A_1$, whose weight is $4 * 2 + 8 * 1 = 16$. Or we can remove $C_3C_4$ and $A_1A_2$ and add $C_3A_2$ and $C_4A_1$ cycle, resulting with cycle $C_1, C_2, C_3, A_2, A_3, B_2, B_3, B_4, B_1, A_4, A_1, C_4, C_1$, with the same weight 16.

Conclusion: A simple greedy algorithm does not guarantee the desired smallest weight.

I have also constructed a planar graph out of that left diagram. However, it is much more messier to describe the construction and to show the algorithms and their results.

Furthemore, it is not hard to construct an example where the greedy algorithm that considers all triples of existing cycles at a time will not reach the smallest weight. I believe, with a bit of more work, we can show a greedy algorithm that considers all combinations of a fix number of existing cycles does not guarantee the desired smallest weight.

It is quite possible this problem does not have a polynomial solution that always yields the smallest weight. In fact, it looks like this concern is implied by the OP since the question asks for "an efficient heuristic that produces a cycle of small weight".


What is the difference between AM and IP

$AM$ is defined to be $AM[2]$, i.e. languages with 2-rounds Arthur-Merlin protocol, which is equal to $AM[k]$ for any constant $k$.

Two extra rounds are required to overcome the fact that the coins are public, i.e.

$IP[k]\subseteq AM[k+2]$ for any $k$ , constant or not, as stated in complexity zoo.

This means that $IP[poly]=AM[poly]=PSPACE$ (which answers your second question).

If $IP$ can be limited to a constant number of rounds (rather than polynomial), then we would have $PSPACE\subseteq IP[k]\subseteq \Pi^p_2$, and the hierarchy collapses to the second level, since $PH\subseteq PSPACE$.


Show that a regular language L contains only palindromes if and only if all words of length at most 3n are palindromes

Suppose that $L$ satisfies your condition. We prove that $L$ accepts only palindromes by induction on the size of the word.

Let $a \in L$ be a word of length at least $3n$. Tracing some accepting computation of $a$ on the given NFA, some state must repeat at least four times, so we can write $a=xuvwy$ (where $u,v,w$ are non-empty), where the state after reading $x,u,v,w$ is the same, say $s$. So $u,v,w$ all have a computation that goes from $s$ to $s$. This implies that the NFA also accepts $xy,xuy,xvy,xwy,xuvy,xvwy$. By induction, all of these are palindromes, and so they satisfy the prerequisites of the lemma with $x',u',v',w',y'$ being obtained by reversing the unprimed string. The lemma then implies that $a$ itself is a palindrome.


top-N recommendation in collaborative filtering

Apache Mahout has several implementations about this problem. Most common approach is to predict all unrated items of a particular user and sorting items by their predicted values. Then you can select top N items to recommend. (see class AllUnknownItemsCandidateItemsStrategy in Mahout).

A version of this implementation with better performance and low accuracy is SamplingCandidateItemsStrategy. This one does not select all unrated items to predict, instead it selects some of them randomly with a given rate and then predict only these items. Finally you can select best predicted items as usual. Advantage of this method is to predict less items but since you eliminate some items randomly accuracy of this method obviously will be worse.

Moreover, there are other implementations which use item based similarity to select candidate items such as  AllSimilarItemsCandidateItemsStrategy,  PreferredItemsNeighborhoodCandidateItemsStrategy,

AllSimilarItemsCandidateItemsStrategy finds similar items of the customer's preferred items and predicts this set. It has a better accuracy since you select relevant items for customer but selecting candidate items phase requires effort.

These are some methods which are used generally.


Data hazard after in load word after addi

THe answers are correct.
There is a data hazard when the information stored in the "regular" location (generally a data reg) is incorrect with respect to the program flow.

Here information copied in the ID stage at line 2 will be the previous value of $t1, as the new one will be copied at the end of WB stage of instruction 1 (and hence at the end of MEM stage of instr 2).

Forwarding means discarding the regular information and replacing it by the new (and correct value).
It can be done

1/ as soon as the new value is available in the processor. Lets call t_a this time

2/ up to the last time that this information is required (because it will be transformed by the ALU, written to the mem, etc). Lets call t_u this instant

If t_a <= t_u, simple forwarding can be done. Otherwise one or more stalls are required.

Lets look at the code

1 addi $t1,$zero,0x30
2 lw $t2,0($t1)

Say Stage IF of instr 1 is t1, ID t2, etc

1 the new value of $t1 will be available at the end of stage WB (t5)

2 the value of $t1 is read at the start of ID stage (t3)

There is a data hazard.

When is the information associated with $t1 available ? After EX stage of 1. So t_a=t3

When is the last time that this information is required by instruction 2 ? Just before the adresse (0+$t1) is computed by the ALU. I.e. t_u=t4

There is no need of any stall. The value read in $t1 register is just discarded and replaced by the one in the ppline register.

Consider now instructions 2 and 3.

2 lw $t2,0($t1)
3 sw $t2,0xff18($zero)

There is a hasard as  $t2 is written at the end of WB stage of inst 2 (t6) and read at the beginning of ID stage of inst 3 (t4).

When if the information associated with $t2 available in the processor. At the end of MEM of instr 2 it is written in some ppline reg of the proc (t5=t_a).

When is this information required ? Just before writing to the memory by inst 3. After it is too late. That is at the start of MEM stage of inst 3 t6=t_u.

Again a simple forward can solve the problem.

(note that if instr 3 had been
sw $t5,0xff18($t2)
the situation would have been different. $t2 would have been required for the address computation (start of EX stage of inst 3 at t5), that is before its production (end of MEM of instr 2 t5), and a stall would have been required over the forwarding.)


How does "language" relate to "problem" in complexity theory?

A (decision) problem is a predicate on strings (that is, a property of strings) that can be either TRUE or FALSE; the problem is to decide whether a string satisfies the predicate (that is, has the property). We represent this predicate as the set of TRUE strings (that is, strings satisfying the property). A language is a set of strings. Thus the denotations of problem and language are the same – they are both sets of strings – and they can be used interchangeably. But semantically we use problem when our set of strings comes from a predicate, and language in other cases.

Here is an example. The NP-complete problem CLIQUE is the set of all pairs $(G,k)$ such that $G$ is a graph that has a $k$-clique. As stated, this is not really a set of strings, but rather a set of pairs $(G,k)$. But when we say the set of all pairs $(G,k)$ we really have some encoding in mind. For example, we can encode a graph $G$ as a list of edges, where the vertices are indexed by numbers, in the format $((i_1,j_1),\ldots,(i_\ell,j_\ell))$. For example, the following is an encoding of a triangle $((1,2),(1,3),(2,3))$. Under this encoding, the language CLIQUE contains the string $(((1,2),(1,3),(2,3)),3)$ but not the string $(((1,2),(1,3),(2,3)),4)$ nor the string $()()($, for example. Another issue that comes up when we talk about strings is: strings over what alphabet. In this case, our strings are over the alphabet $(),0123456789$; but since everything can be encoded in binary, we typically imagine such binary encoding of our strings.

CLIQUE is a predicate on pairs $(G,k)$ that holds if $G$ is a graph containing a $k$-clique. It is also a property of pairs $(G,k)$, that of $G$ having a $k$-clique. The corresponding language (which we identify with the CLIQUE problem) consists of all strings encoding (in a fixed way) pairs of graphs $(G,k)$ such that $G$ has a $k$-clique. The corresponding decision problem (which we identify with the language of all accepted instances) is to decide, given a pair $(G,k)$, whether $G$ contains a $k$-clique.


Convert 24(decimal) to modified IEEE 754 floating point format?

Since $e=111$ is saved for indicating NaN and  $\infty$, then the maximal number that can be represented with this 8bit-floating point structure is
$$ (-1)^0 \cdot (1.1111)_b \cdot 2^{6-3} = 15.5$$

Therefore, you cannot represent 24(Dec) using the above system.

However, the correct translation would be infinity rather than a NaN, that is, 24 should be represented as $0\ 111\ 0000 \equiv \infty$.


What are staged functions (conceptually)?

To the best of my knowledge, the term staged computation was first used by Bill Scherlis in this paper.  Prior to that, the term "partial evaluation" was used for much the same concept, but the idea of staged computation is subtly different.  Both the ideas are related to Kleene's S-m-n theorem.

If you have a function $\phi(m,n)$ of two arguments, but you know one argument, say $m$, then you can perform some of the computation of the function right away using the knowledge of the first argument.  What you are then left with is a function $\phi_m(n)$ whose computations only depend on the second, unknown, argument.

The idea of partial evaluation is to compute the specialized function $\phi_m(n)$ automatically.  Given the code for the original function $\phi$, partial evaluation does static analysis to determine which bits of the code depend on $m$ and which bits depend on $n$, and transforms it to a function $\phi'$ which, given $m$, constructs $\phi_m$.  The second argument $n$ can then be fed to this specialized function.

The idea of staged computation is to think about the function $\phi'$ first.  It is called a "staged" function because it works in multiple stages.  Once we give it the first argument $m$, it constructs the code for the specialized function $\phi_m$.  This is the "first stage."  In the second stage, the second argument is provided to $\phi_m$ which does the rest of the job.

So, the job of partial evaluation is to transform the code for an ordinary function $\phi$ to a staged function $\phi'$.  Scherlis envisaged that this transformation could be done by more general mechanisms than the earlier partial evaluation methods.  The subject of "staged computation" now deals with issues such as:

How to define staged functions?
What programming languages and type systems should be used for defining staged functions?
What is the semantics of such languages?
How do we ensure the coherence and correctness of staged functions?
What techniques are useful for automatically or semi-automatically constructing staged functions?
How do we prove the correctness of such techniques?

Staged computation can be very important in practice.  In fact, every compiler is in effect a staged computation.  Given a source program, it constructs a translated and optimized target program, which can then take the actual input and calculate the result.  It is hard to write staged computation programs in practice because we have to juggle the multiple stages and make sure that the right things are done at the right time.  Everybody who has written a compiler has struggled with such issues.  It is also hard to write programs that write other programs, may they be machine language programs (compilers), SQL queries (database manipulations) or HTML/Server Pages/Javascript code (web applications) and myriads of other applications.  The researchers in staged computation aim to create good languages and tools that make it easier and safer to create such applications.


What is the Curry-Howard analogue for linear logics?

Linear logic corresponds to a type system for a process calculus (a variant of the internal π-calculus), where:

proofs correspond to processes;
propositions correspond to session types (communication protocols).

This is a pretty active area of research. While people expected a correspondence between linear logic and some concurrency model since the inception of linear logic by Girard [1987], finding something that is satisfying from both the logical and the concurrency modelling perspectives has been somewhat elusive.

Here is a summary of the key developments so far.

Abramsky [1994] and Bellin and Scott [1994] proposed the first "Proofs as Processes" correspondence, where linear propositions are types for linear channels in a process calculus. For example, the proposition $A \otimes B$ is interpreted as the channel type "send $A$ and $B$"; it is used to type a process that uses a channel to output a message including something of type $A$ and $B$ (a pair, if you like), respectively, and then the channel must not be used anymore. The key idea is that the cut rule of linear logic can be used to type the parallel execution of two processes that communicate over a private channel. The duality check performed by the cut rule in linear logic corresponds to checking that the two processes use the shared private channel in compatible ways.
The idea of duality inspired also several typing disciplines for process calculi, most notably linear types and session types, but the direct link to linear logic was lost. Session types in particular, by Honda [1993], describe communication protocols and their applicability became evident pretty soon: the idea spawned a research area.
Seven years later after Honda developed session types, Caires and Pfenning [2010] found that propositions in intuitionistic linear logic can be interpreted as session types. For example, the proposition $A \otimes B$ is interpreted as the protocol "send $A$ and then proceed as $B$". This discovery has rejuvenated the "Proofs as Processes" research line: there are a lot of papers on this topic published in the last decade. Thanks to the logical foundations, we can import ideas from logic for extending the typing discipline of session types.
Wadler [2014] reformulated the correspondence with session types for classical linear logic and formalised the first connection between a standard presentation of session types for a functional language and linear logic.
There is an "issue" shared by all the works cited above: while the linear logic side is the expected one, the process calculus side is not, both syntactically and semantically. For example, a notable discrepancy is that parallel composition ($P|Q$) is not a standalone term constructor, because it lacks a corresponding rule for reasoning about it directly in linear logic. This issue has been resolved in [Kokke et al., 2019] (disclaimer: I'm one of the authors), by conservatively reformulating the rules for $\otimes$, cut, and mix. This gives rise to new proof transformations, which turn out to correspond to the expected observational semantics of the π-calculus.

If you're looking for a couple of papers to get started, I would start from [Wadler, 2014] and then [Kokke et al., 2019] (to see the latest system).


Yes. These definitions are equivalent,  noting that not all valid formula have the form $P\to Q$, though any formula $Q$ is equivalent to $\top\to Q$.


Is there an algorithm for random sampling from a priority queue with probability proportional to priority?

This is exactly what the A-Res algorithm is for
If you have a positive weight for each sample, then you can achieve a probability of sampling proportional to the weight, even without knowing all of the other weights at a given time.  The way you achieve this is:

For each sample: randomly generate a number between from 0 to 1
Raise the result to the power of (1/weight).

It can be shown that a sample with N times the weight of another sample is N times more likely to be greater (have higher priority)


To begin with, note the the Myhill-Nerode equivalence classes for a language $L$ is the same as the Myhill-Nerode classes for its complement $\overline{L}$. This follows immediately by definition, and I leave it you (it also appears here).
So given $\Sigma = \{a, b, c\}$, we need to find the Myhill-Nerode classes for $\overline{L} = \{ \epsilon, cc\}\cup \{cca^i: i\geq 2 \}$. There are many ways to do so, one can, for example, consider what happens in a minimal deterministic automaton for the language - it is known that the states of the minimal deterministic automaton correspond to the Myhill-Nerode classes. Yet, the given language is simple enough, you can actually experiment with it a bit and show that the following are the equivalence class for $\overline{L}$ (indeed, $\overline{L}$ has a simple structure - every word of length at least $4$ in the laguage is of the form $cca^i$, so clearly all these words are equivalent. Then, you can look at words of length < 4, and try to see which among them are equivalent, etc.):

$C_1 = \{ \epsilon\}$.
$C_2 =  \{ c\}$.
$C_3 =  \{ cc\}$.
$C_4 = \{ cca\}$.
$C_5 = \{ cca^i: i\geq 2\}$.
$C_6 = \Sigma^*\setminus \left( \bigcup_{i\in [5]} C_i\right)$.

Clearly the 5 sets above partition $\Sigma^*$, so to show that they are indeed the Myhill-Nerode classes, we need to show that all the words in the same set are Myhill-Nerode equivalent, and for every $ 1\leq i < j \leq 6$, it holds that the words in the set $C_i$ are not equivalent to the words in the set $C_j$.
There you go, try to prove that the above sets are indeed the equivalence classes. That should be easy enough now.


A condition ensuring that a bipartite graph have a perfect matching

Hint: Use Hall's criterion.

In more detail, suppose that Hall's criterion didn't hold. Choose a set $X$ of minimal size satisfying $|N(X)| < |X|$. Show that $X$ is not empty, and let $Y = X \setminus \{x\}$ for some arbitrary $x \in X$. Show that $Y$ has a perfect matching with $N(Y)$, and prove that $N(N(Y))=Y$ by counting the edges connecting $Y$ and $N(Y)$ in two ways. Show that $\emptyset \neq N(x) \subseteq N(Y)$, and reach a contradiction.


There is an $O(n \log n)$ algorithm for this problem.

To formalize, lets say that the task is to partition $n$ given integers into two partitions $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. Denote the maximum integer with $M$ and the sums of integers in $A$ and $B$ with $\sum_A$ and $\sum_B$. The partitions should satisfy that $|\sum_A - \sum_B| \le M$.

Start by putting the $a$ largest integers into $A$ and the $b$ smallest to $B$. Now, if $\sum_A < \sum_B - M$, there is no solution because we cannot make the sum of $A$ any larger. If $\sum_B - M \le \sum_A \le \sum_B + M$, the partition $(A, B)$ is a solution and we are ready. The case that is left is $\sum_B + M < \sum_A$. In this case, we can repeatedly choose the largest element of $A$ and the smallest element of $B$ and swap them. The difference $\sum_A - \sum_B$ changes by at most $2M$, so either we find a solution or maintain the invariant $\sum_B + M < \sum_A$. At some point we must find a solution, because $a$ is smaller than $b$, and thus $\sum_A$ will become smaller than $\sum_B$ by repeating this operation.
This can be implemented in $O(n \log n)$ with sorting and two pointers.


What units should Shannon entropy be measured in?

Generally bit was introduced by Shannon in 1948. Using bit instead of any other information measurement unit it's because of convenience any information can be represented by single bit or by set of bits.

I bet you already ran into most popular example which is coin tossing. You can represent head as 1 and tails as 0. You can also use stream of bits as representing more complex information as integer.

  Simple example

  Consider W as information about current week day you might use 7bit length stream as representation of week. Eg Monday would be represented as 1000000 and Wednesday as 0010000. So each bit in stream represents one day.

You should always consider domain for your problem and use bit encoding which fits best. Using code alphabet of length n shows universality of that particular encoding (like ASCII or Unicode).

Another thing is that bit can be efficently represented in low powered (5v) circuits. There exists interference detection and fixing functions for such circuits.

Consider domain different then bit, eg real numbers, and let them represent information using some relation R. Now because real numbers are dense even minimal interference will have impact on end result.


In which order to solve subproblems when using memoization?

Let me show you the general approach to figuring this out.  Then I'll let you apply that technique to your specific situation.

Well, it's clear that you need to solve $A(i,j-1)$, $A(i-1,j-1)$, and $A(i-1,j+1)$ before solving $A(i,j)$.  So, you need to pick an order that ensures all three of those are solved before you try to solve $A(i,j)$.  What order would work for that?

I suggest you try drawing a picture.  Draw a grid, with one dot for each $(i,j)$.  Draw an arrow from $(i,j-1)$ to $(i,j)$, an arrow from $(i-1,j-1)$ to $(i,j)$ and an arrow from $(i-1,j+1)$ to $(i,j)$ for each $(i,j)$.  You might do this for, say, a 4x4 grid.  Look at the resulting picture.  Can you find an order of traversing the dots, so that is consistent with all of the arrows?  Hint: try topological sorting that graph.  What order does that give you?  Can you generalize?  What would work for a 5x5 grid?

If you're not sure, just write a recursive program and apply memoization.  Then you won't need to explicitly pick an order to build things out bottom-up; the computer will take care of that for you.  See When can I use dynamic programming to reduce the time complexity of my recursive algorithm? and https://en.wikipedia.org/wiki/Memoization.


Relations of some exponential functions -- which is correct?

(1) is not the correct answer.  Perhaps there is an error in the book, or an error in what you entered.  As you correctly concluded, $f(n) = 3 e^{n^{1/2} \log n}$ and $h(n) \approx e^{n \log n}$ (by Stirling's approximation), so it is not true that $h(n) = O(f(n))$.

I can't tell whether you've drawn the correct conclusions about the pairwise relationships between these three functions.  You wrote that $f(n) < g(n) < h(n)$, but this is not correct.  For instance, $f(1) = 3$, $g(1) = 3$, $h(1) = 1$.  Those inequalities don't hold for all $n$ -- but if we care about big-O notation, then that's not the right question anyway, since big-O notation relates to the asymptotic behavior of these functions (as $n\to \infty$).

The right question is whether $f(n) = O(g(n))$, whether $g(n) = O(f(n))$ (be careful here!  better double-check your work on this one another time), and so on.

See also Sorting functions by asymptotic growth and How does one know which notation of time complexity analysis to use?.  They should answer your remaining questions.


What complexity class is this ciruit problem?

Assuming that the probability is over the randomized preprocessing and $p > 0$, by fixing the correct random choice you get a circuit of size $S = O(2^{\log^{O(1)} n} q^{O(1)})$ for $k$-SAT. The corresponding complexity class is non-uniform circuits of size $S$. If, for example, $q$ is quasipolynomial ($2^{\log^{O(1)}n}$), the you get a non-uniform circuit of quasipolynomial size.

We usually don't care too much about the time required to construct the circuit unless it is very low.


Is there a basic proof that there exists some edit distance between two strings?

Given two strings $v,w \in \Sigma^*$ with $m = |v| \geq |w| = n$ (w.l.o.g.), align them like so:

$\qquad\displaystyle\begin{array}{ccccccc}
v_1 & v_2 & \dots & v_n & v_{n+1} & \dots & v_m \\
w_1 & w_2 & \dots & w_n & - & \dots & -
\end{array}$

This alignment implies an edit distance of

$\qquad\displaystyle 0 \leq d_{\text{edit}}(v,w) \leq d_{\text{Ham}}(v,w[1..n]) + (m-n)$.

In particular, there is an alignment for any two strings. Note furthermore that there are only finitely many alignments of $v$ and $w$ (we forbid columns $\genfrac{}{}{0pt}{}{-}{-}$), so one with minimal score (which is the edit distance) must exist.

Hence, any two strings have finite edit distance and the graph is connected.


Fair assignment of storage for multiple writers (load balance)

There are multiple solutions to this problem:

Consistent hashing with bounded loads
Generic Bin packing algorithm(Knapsack or other)

Both require that the writer know the free storage amount of the drives.
Consistent hashing with bounded loads is based on the consistent hashing algorithm published by akamai and fixed the issue of load inbalancing by overflowing across the ring to the next free "bin".


Algorithm to decide whether two vertices are ancestors/descendants of each other

DFS only requires $O(|V|+|E|)$ time, not $O(|V| \cdot |E|)$ time.  (Same for BFS.)  Therefore, DFS is an efficient solution for this problem.  This is about as efficient as you hope for, as it takes that much time just to read the entire input -- you can't hope for something faster.

The problem becomes more interesting if we're provided the graph $G$ and allowed to do some precomputation, and then want to answer many queries efficiently.  This is considerably more challenging, but in some cases, it is possible to do better than running a DFS from scratch every time you receive a new query.

For instance, if the graph is a tree, there is an efficient solution: do a DFS once, and store the pre and post numbers at every node; then each ancestor query can be answered by testing for interval containment.
In a more general graph, this is known as a reachability query, and there are algorithms in the literature for this problem.  See, e.g., https://cs.stackexchange.com/a/41432/755 and https://cstheory.stackexchange.com/q/25298/5038 and https://cstheory.stackexchange.com/q/21503/5038.  Without loss of generality, you can assume the graph is a dag (if not, first compute all strongly connected components in linear time, and label each vertex with its scc; then you only need to consider the dag of scc's).


Proof of correctness of algorithms (induction)

how do I include the if else statement in the proof?

In this example, the if statement describes the basic case and the else statement describes the inductive step.

Induction on $z$.

Basis: $z = 0$.

$$ \text{multiply}(y,z) = 0 = y \times 0. $$

Induction Hypothesis: Suppose that this algorithm is true when $0 < z < k$. Note that we use strong induction (wiki).

Inductive Step: $z = k$.

\begin{align}
\forall c>0 : \text{multiply}(y,z) &= \text{multiply}(cy, \lfloor \frac{z}{c} \rfloor) + y \cdot (z \text{ mod } c) \\
&= cy\cdot\left\lfloor \frac{z}
{c}\right\rfloor+y\cdot (z \text{ mod } c) \\
&= yz.
\end{align}


Merging of two increasing binary trees why do we exchange left and right subtree

Both leftist heaps and the skew heaps you consider here join two trees by "zipping" the trees along the rightmost path.  Then left and right children are swapped to keep the left leaning property. In leftist heaps this in done where necessary, where in skew heaps left and right are always swapped. Hence the code.

You ask whether the skew heaps will never deteriorate into trees that have linear behaviour, instead of logarithmic. Well, this can happen.

  One may ask whether amortization is really necessary in the analysis
  of skew heaps, or whether skew heaps are efficient in a worst-case
  sense. Indeed they are not: we can construct sequences of operations
  in which some operations take O(n) time. For example, suppose we
  insert $n, n + 1, n - 1, n + 2, n - 2, n + 3, \dots  , 1, 2n$ into an
  initially empty heap and then perform delete min. The tree resulting
  from the insertions has a right path of $n$ nodes, and the delete min
  takes $\Omega ( n)$ time. (See Fig. 3.)

Quoted from the original reference "self-adjusting heaps" by Sleator and Tarjan,  SIAM Journal on Computing, which is linked on the wiki-page for skew heaps.


The correct running time is indeed probably $O((m+n)\sqrt{n})$. However, this is a mouthful, and the expression $O(m\sqrt{n})$ looks nicer and is also more succinct. In most cases, $m \geq n/2$, since otherwise there is an isolated vertex. In fact, by finding isolated vertices, we can improve the running time of the algorithm to $O(n + m\sqrt{n})$.

An alternative way of stating the running time would be $O(m\sqrt{n})$, assuming $m \geq n$. The case of small $m$ is not so interesting (since then there are isolated vertices which can be eliminated), and so it is usually assumed that $m = \Omega(n)$.


The sequence of losing positions can be found in the OEIS, A030193, as is the sequence of positions having Grundy value 1, A224839. The encyclopedia cites several relevant articles. Perhaps some of them discuss non-trivial algorithms for computing the sequence.


The exercise being asked about is pretty stupid (this is criticism against the person who set it as an exercise, not the OP). Every (positive) function $f$ is its own big $\Theta$, that is $f(n) = \Theta(f(n))$. Nevertheless, whoever asked the question expected the following answers: $f(n) = \Theta(n^3)$ and $f(n) = \Theta(\log n)$. There are many online and offline resources that can explain why this is the case and how to prove it, or you can try working through the algebra yourself.

Please let the poser know that the following answers are as mathematically correct as the expected one: $n^3 - 3n^2 + 5 = \Theta(17n^3 - 2n\log n + 4\log\log n)$ and $2\log_2 n - 4 = \Theta(4\log_4 n - 2)$. In order to rule out these answers, the poser should have phrased the question as follows:

  For each of the following functions $f(n)$, find a function $g(n)$ of the form $n^\alpha (\log n)^\beta$ such that $f(n) = \Theta(g(n))$, and prove that $f(n) = \Theta(g(n))$.

Note that in general a function $g(n)$ of that specific form might not exist, for example if $f(n) = n\log\log n$, or for the following more exotic function: $$f(n) = \begin{cases} n & \text{ if $n$ is odd,} \\ n^2 & \text{ if $n$ is even.} \end{cases}$$
Such functions nearly show up in modular exponentiation, FFT-based algorithms, and fast matrix multiplication, though in these cases the difference is only in the constant (e.g. $n$ vs. $2n$) rather than the asymptotics.


Programming in Propositional Logic article notation question

The set $X$ is a collection of ordered pairs $[v,i]$ (this is just a strange notation for an ordered pair), in which $v$ is a vertex and $i$ is an index from $1$ to $k$. Informally, $[v,i] \in X$ means that $v$ is the $i$th vertex in the dominating set. The formula $F$ states two things:

There is at most one $i$th vertex (i.e., $X$ doesn't contain $[v,i],[u,i]$ for $v \neq u$).
The vertices in $X$ form a dominating set.

The reason we want the index $i$ is that the logic isn't strong enough to count the size of $X$. It is strong enough to express "at most one" and "at least one", so we use this particular encoding to be able to express "the dominating set has size at most $k$".


What the State is, and Where it comes from, when Generating Reachability Graphs

Timed automaton case: Here, a state is typically composed of the current location and the values of all clock variables. Thus, timed automata induce transition systems with an infinite number of states.

The usual approach in this context is thus to build a finite representation of this state set, which is a finite transition system. In the paper "An Efficient State Space Generation for Analysis of Real-time Systems" by Inhye Kang and Insup Lee that you linked to, the state set for this finite transition system is given on page 5, left column. The classical approach involves building a so-called region graph, which is referenced in column 2 of page 4.

Note that CTL model checking of the resulting transition system makes little sense, as the "next-time" operator of CTL does not have a usable semantic in this case. Rather, there are specialized logics (such as TCTL) to reason about properties of timed systems.

Petri net case: In the Petri net case, the states are the possible markings of the network. Note that the state set could be finite or infinite depending on the network. In paper that you referenced ("Petri Net Reachability Graphs: Decidability Status of First Order Properties" by Philippe Darondeau, Stéphane Demri, Roland Meyer, Christophe Morvan), the reachability graph is defined on page 4 as consisting of all markings and having a transition between a marking $M$ and $M'$ if we have $M[t\rangle M′$ some $t$. This notation is in turn explained at the beginning of the page, in Definition 2.


Can we write algorithms without conditional statements?

Here is a Turing complete "programming" language. It has just two constants, called $K$ and $S$, and one operation called "application", written $x \cdot y$. The two constants satisfy the rules
$$(K \cdot x) \cdot y = x$$
and
$$((S \cdot x) \cdot y) \cdot z = (x \cdot z) \cdot (y \cdot z).$$
This is known as a combinatory algebra and is well known to be Turing complete. There is an actual programming language based on $S$ and $K$, called unlambda. I think we can agree that there is no builtin conditional. Of course, since this language is Turing complete, it can also simulate conditional statements.


Identifying system events affecting timing behavior of an application

You forgot the most obvious factor: the input of the program. The time taken by a program heavily depends on the input unless it does not have any input or  the input comes from a small fixed set.

Other factors can be classified into two classes: 1) Internal factors and 2) External factors.

Internal factors:
1) Input
2) Waiting for I/O
3) Waiting for System resources like memory/semaphores etc.
4) How effectively memory is cached in CPU (may be different for different runs, what you have termed as cache misses.)
5) Disruptions in instruction pipeline
6) Interactive events
7) If the process needs to swap in/out some pages to swap area
8) If the process uses other hardware such as graphics card/audio/network
9) Hardware interrupts from graphics card/audio/network
10) Clock interrupts
11) Scheduler running
12) If the process is multi-threaded, then delays because of thread switching
13) If the process is multi-core and you need to share data between core, delay depends on the architecture of the CPU

External factors:
1) Multiprocessing (the biggest culprit)
2) Priority of the process
3) Context switching
4) Operating System preemptions
5) Hardware errors and service interruptions (of course)
6) Communication with other processes
7) Communication with other processes in other machies
8) Input that is not readily available, (it is available as a stream)

We need to have a good guess of running time of a process for majority of scheduling algorithms and for real-time systems. But a perfect calculation is simply impossible in real cases. The usual practice is to run the process for typical  (or typically worse) case input many times, make a guess and then over estimate it. This is done even in real-time system, if I understand correctly. In quite a few real-time systems the running process quite arbitrarily demands a guarantee of what it thinks is the over-estimated time it will take to finish the computation.


Are two CCS processes equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML formulas?

(This probably does not fully answer, but I think it can still help)

According to their Def. 4, there is no modality $\langle \tau \rangle$ in their HML logic. Their syntax only allows $\langle\!\langle u \rangle\!\rangle$ where $u \in A \cup\{\epsilon\}$, and $\tau$ is assumed not to be in $A$ (Def. 1), hence $u\neq\tau$.

Also, there seems to be no recursion allowed in their logic.

Further, as far as I can see, in the Concurrency Workbench <a> indicates a strong possibility, while <<a>> indicates a weak possibility.

I can't recall which variant of the HML logic precisely corresponds to weak bisimilarity, but I think that it can't involve a strong <tau> modality since otherwise we would distinguish lol and tau.lol.


How do we place $8n$ objects in a grid of size $n \times n$?

Given a set of objects in a cell grid, if no 4-set of it forms a rectangle with sides parallel to the sides of the grid, we will call those objects rectangle-free.

The more general problem is to determine sequence A072567, whose $n$-th term $M_n$ is the size of maximal set of rectangle-free cells in an $n \times n$ cell grid. Its first 13 entries are

$$1, 3, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45, 52, \cdots$$

It looks like the value of $M_{14}$ is unknown, which does not matter for the current problem, though.

We know that $M_{q^2+q+1}=(q+1)(q^2+q+1)$ when $q$ is a power of a prime number. In particular, letting $q=4,5,9,11,13$, we get $M_{21}=105$, $M_{31}=186$, $M_{91}=910$, $M_{133}=1596$, $M_{183}=2548$.

For a square grid of size $n\ge100$, we will select disjoint smaller square grids along its main diagonal line and fill the maximal set of rectangle-free cells in each of those smaller squares.

If $100\le n\le 113$, select a grid of size 91 since $91<100$ and $M_{91}=910 \gt 8 \times 113.$
If $114\le n\le 125$, select one grid of size 91 and one grid of 21 since $91+21\lt 114$ and $M_{91}+M_{21}=910 + 105\gt 8 \times 125.$
If $126\le n\le 132$, select one grid of size 91 and one grid of 31 since $91+31\lt 126$ and $M_{91}+M_{31}=910 + 186\gt 8 \times 132.$
If $133\le n\le 182$, select one grid of size 133 since $133\le 133$ and $M_{133}=1596\gt 8 \times 182.$
If $183\le n\le 300$, select one grid of size 183 since $183\le 183$ and $M_{183}=2548\gt 8 \times 300.$
if $200+100k\le n\lt200+100(k+1)$ for some $k\ge1$, select one grid of size 183 and $k$ grids of size 91 since $183+91k\lt 200+100k$ and $M_{183}+kM_{91}=2548+910k>800(300+100k)\gt8n$.

Now the problem is shifted to realize $M_{q^2+q+1}=(q+1)(q^2+q+1)$ for $q=4,5,9,11,13$. The realizations comes from finite projective planes that is built on top of finite fields, which is explained in detail here.

There are many packages that helps computation of finite fields.

Here is how to fill $21\times21$ grid with 105 objects. Note that there are exactly 5 objects in each row and each column.

000000000000000011111
010001000100010000001
000100010001000100001
001000100010001000001
000011110000000010000
010010000001001001000
000110000010010000100
001010000100000100010
000000000000111110000
010000010010100000010
000100100100100001000
001001000001100000100
000000001111000010000
010000101000000100100
000101001000001000010
001000011000010001000
100010001000100000001
100001000010000101000
100000100001010000010
100000010100001000100
111100000000000010000

Here is how to fill $31\times31$ grid with 186 objects, where empty cells are left as whitespaces. Note that there are exactly 6 objects in each row and each column.

                         111111
    1    1    1    1    1     1
  1    1    1    1    1       1
   1    1    1    1    1      1
 1    1    1    1    1        1
                    111111
    1   1   1   1   1        1
  1      1 1      1 1       1
   1  1       1  1  1      1
 1     1     1     11     1
          11111          1
    1  1  1       1  1     1
  1   1   1        1   1     1
   1     11     1     1   1
 1      1 1      1      1   1
               11111     1
    1 1      1 1      1     1
  1     1     11     1    1
   1   1   1   1        1    1
 1       1  1  1       1   1
     11111               1
    11     1     1     1  1
  1  1       1  1       1  1
   1 1      1      1 1      1
 1   1        1   1   1      1
1    1    1    1    1         1
1        1   1   1   1       1
1       1  1       1  1    1
1      1      1 1      1    1
1     1     1     1     1 1
11111                    1

Exercise 1. Refine the algorithm so that it uses only $M_{21}=105$, $M_{31}=186$, $M_{91}=910$, $M_{133}=1596$, i.e., without $M_{182}$.

Exercise 2. (Open problem) The smallest $n$ such that we can fill $8n$ rectangle-free objects in an $n\times n$ grid is 57 since $M_{57}=8\times57$ for $q=7$. What is the biggest $n$ such that we cannot fill $8n$ rectangle-free objects?


The typical reason for smoothing in the first place is to handle cases where $\#\{X_i = x_i | Y = y\} = 0$. If this wasn't done, we would always get $P(Y=y|X=x) = 0$ whenever this was the case.

This happens when, for example, classifying text documents you encounter a word that wasn't in your training data, or just didn't appear in some particular class.

On the other hand, in the case of the class prior probability, $P(Y = y)$, this situation should not occur. If it did this would mean you are trying to assign objects to classes which didn't even appear in the training data.

Also, I've never encountered the term $k$-smoothing. Laplace or Additive smoothing is much more common.


Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?

Note [2019-07-30] The proof is wrong ... the question is more complicated than it sounds.

After a failed attempt here it is another idea.

If we intersect $L$ with the regular language $L_{reg} = 0^*10^*10^*10^*$ we get a CF language.

Perhaps we can have more luck if we use $L_{reg}' = 0^*10^*10^*10^*10^*$ (a string with exactly 4 1s).

Let $L_1 = L \cap L_{reg}'$, informally $w \in L_1$ if it can be split in two halves, such that one half contains exactly $\{0,1,3,4\}$ $1s$  or both halves contain two $1$s but  their positions don't match.

Suppose that $L_1$ is CF and let $G$ be its grammar in Chomsky normal form, and let

$$w = uv = 0^a 1 0^b 1 0^c 1 0^d 1 0^e \in L_1$$

We have $|u|=|v|$ (even length) and $d(u,v) \geq 2$

If we restrict our attention to the ways in which the four 1s of $w$ can be generated we have the three cases shown at the top of the figure 1. The central part of the figure 1 shows the first case (but the others are similar).

Figure 1 (the full picture can be downloaded here)

If we pick $a=e, c=2a$ and $b,d \gg a$ we see that the zeros between the two pairs of 1s must be independently pumpable (red nodes in the figure): in particular, for large enough $b \gg a$, we get a duplicate nonterminal node on a internal subtree (node X in figure 2)  or a repeated subsequence in the path towards the first or the second 1 (node Y in figure 2). Note that Figure 2 is a little bit simplified: there can be more nonterminal nodes between the two $X$s, and also between the two $Ys$ ($Y\to ... \to Z_i \to ... Y$ but with $Z_i$ that produces only 0s on the right of the first 1).

Figure 2

So we can fix an arbitrary $a = e = k, c = 2a$, then pick large enough $b$ to get an independently pumpable node on the sequence of zeros between first and second $1$. For the sequence of zeros between the third and fourth 1, we can choose $d = b! +b$.
But $0^b$ is independtly pumpable so there is a $p \leq b$ pumpable substring $y$, i.e. such that $b = xyz, |y|=p, |x|\geq 0, |z|\geq 0$ and $xy^iz = b!+b$. The string we get is:

$$w' = 0^k 1 0^{b!+b} 1 0^{2k} 1 0^{b!+b} 1 0^k$$

but $w' \notin L_1$. Thus $L_1$ is not CF and finally $L$ is not CF.

If the proof is correct (???) it can be extended to every language $L_k = \{ uv : |u|=|v|, d(u,v)\geq k\}, k\geq 2$


First algorithm that came into my mind:

P = initial set of polygons
for every pair (p,q) of polygons in P
  if p intersects q
    remove p and q and insert the three polygons that make up p union q
repeat until P can't be grown anymore

If vertices have integer coordinates. You can use a matrix $M$ (initially $0$) and use the following algorithm:

for every polygon
  for every point p = (x,y) in the polygon
    M[y,x] += 1

A disjoint polygon is then a contiguous sub-area of the matrix. The entries in the sub-area are all equal.

One way to speed up the first algorithm is first to compute AABB's for each of the polygons and use a quadtree or some BSP data structure.


Apparently all algebraic topology is useful for is earning imaginary internet points. More than I expected, I guess... (Actually now that I've finished writing I expect to lose points on this...)

tl;dr: Honestly, I don't think anyone here can give you an easy way to really understand what homology and cohomology are, with just a short description. I made an attempt below, but I took a whole course on the subject and I still don't really know what they are. Particularly if you don't know, or care to know, what a group is. These things are groups, that's sort of the whole point. As they relate to graph theory, you can treat a graph as a simplicial complex of dimension 1. Thus you can consider the homology and cohomology groups of the graph and use them to understand the topology of the graph. Here are some notes by Herbert Edelsbrunner on homology and cohomology, the latter of which provides a useful example.

Before I can define cohomology I must first make sure you understand the definition of homology. For simplicity I'll describe everything using simplicial complexes, but (co)homology can be, and usually are, defined for more complex complexes (see what I did there?). Simplicial complexes are enough for graph theory, at least as far as I've seen.

It turns out that it's really difficult to try to create homeomorphisms between two topological spaces to show that they're topologically equivalent. It's even harder to try an show that no such homeomorphism exists. So the idea is to establish topological invariants, a property that must be equal for two topological spaces if they are topologically equivalent. If the invariant isn't the same for both spaces, then they can't possibly be topologically equivalent. Homology and cohomology groups are two such invariants. They attempt to put a group structure on a topological space, so that we can work with groups and homomorphisms instead of topological spaces and homeomorphisms. Computer scientists like homology groups because they are easy to compute and lead to fast algorithms. The downside is they're much more difficult to visualize.

So how do we describe a topological space in such a way that we can place a group structure on it? Well we build our topological space with a set of simplicies, called a simplicial complex. A 0-dimensional simplex is a vertex, a 1-dim simplex is an edge, 2-simplex is a triangle, 3-simplex is a tetrahedron, etc. A valid simplicial complex must obey certain rules about how it's simplices connect to one another: the intersection of two simplices must also be a simplex in the set and all subsimplces must be in the set. Notice that graphs can be thought about in this way.

It makes sense to talk about sums of simplices of the same dimension $p$, what we call $p$-chains. So a $p$-chain can be written as $\sum_{i} a_i \sigma_i$ where $\sigma_i$ is a $p$-simplex and $a_i$ is an integer.  With this operation we can define the group of $p$-chains $(C_p,+)$, or just $C_p$.

We also have one more operation called the boundary operator, which takes a chain to it's boundary. So for an edge $(v,u)$ in some graph, the boundary is just the sum of its vertices $u+v$. The boundary operator of a $p$-simplex $\sigma = [u_0,\ldots, u_1]$ is defined as $\partial \sigma = \sum_{i}[u_0, \ldots, \hat{u_i}, \ldots, u_n]$ where $\hat{u_i}$ means that we remove the $u_i$ simplex and create a sum of $p-1$-simplices. To apply the boundary operator to a $p$-chain $c$, we just apply it to each of it's $p$-simplices, $\partial c = \sum_{i}a_i \partial \sigma_i$.

Now there are two very important types of chains which we use to construct homology groups, cycles and boundaries. A $p$-cycles is a $p$-chain $c$ with no boundary, meaning $\partial c = 0$. A $p$-boundary $c$ is a $p$-chain that is the boundary of some $p+1$-chain $d$, $c = \partial d$. Once again we can define groups $Z_p$ (our group $p$-cycles) and $B_p$ (our group of $p$-boundaries). The group $B_p$ is a subgroup of $Z_p$ which is a subgroup of $C_p$.

Homology groups are not a group of functions where one element can be deformed into another. Intuitively, what the homology group is trying to do is characterize the different loops. Think of a torus (donut) which has two distinct loops, colored in the image below. I can move the blue loop anywhere around the torus, but it's still the same loop because it differs only by it's boundary.

The elements of a homology group are equivalence classes, where two $p$-cycles in the simplicial complex are in the same equivalence class if and only if they differ only by a boundary chain. Meaning if you take two cycles $c,d \in Z_p$, and there exists boundaries $a,b \in B_p$ such that $c+a = d+b$, then $c$ and $d$ are in the same equivalence class. They are constructed as the quotient groups $H_p = Z_p/B_p$.

Now cohomology is much less geometrically intuitive and motivated by algebraic considerations.

We define cohomology groups in terms of cochains. A $p$-cochain is a homomorphism $\psi: C_p \rightarrow G$, where $G$ is the group used for the coefficients $a_i$ (usually $\mathbb{Z}$ or $\mathbb{Z_2}$). Instead of considering a group of chains, we consider the group of cochains, all homomorphisms between $C_p$ and $G$ denoted as $C^p=Hom(C_p, G)$.

Similarly we can define a boundary operator on cochains, as the dual homomorphism of $\partial$, which we denote $\delta: C^{p} \rightarrow C^{p+1}$. Notice that since the boundary operator $\partial$ took $p+1$-chains to $p$-chains, the dual homomorphism takes $p$-cochains to $p+1$-cochains. Now consider a $(p-1)$-cochain $\psi$ and $\partial c$ a $p-1$-chain. The coboundary operator $\delta$ requires that $\psi$ applied to $\partial c$ is the same as $\delta \psi$ applied to $c$.

Once we have the coboundary operator, we can define cocycle and coboundary groups, denoted $Z^{p}$ and $B^{p}$, just as we did before. Then the $p$th cohomology group is a set of equivalence classes where two cocylces are equivalent iff they differ by a coboundary. They are constructed as the quotient groups $H^{p}=Z^{p}/B^{p}$. Do you see why this is much less geometrically intuitive?


You can indeed assume that you know a polynomial bound on the time it takes to compute a polytime function. This is an example of a non-constructive argument.

The down side is that you won't be able to construct a computable function transforming polytime function of one model to the other. In some situations (say a diagonal argument) this is needed, and then the trick is to assume that programs are clocked, i.e. come with their own time bounds. This makes sense in that application since we can enumerate all polytime functions as computed by polynomially clocked machines. In your case, however, you don't need to worry about such issues.


Algorithm to separate circles to reduce collision the maximum between them

If you want to brute force it, this is a constrained optimization problem where the quantity you're minimizing is the overlap area, the variables are the x and y coordinates of each circle's center, and the constraints are that each center lies within a red circle.

Depending on how you want to count areas inside three or more circles, the formula for the overlap arra can be reasonably simple or a huge mess that gets worse with the number of circles.


What is the current status of parallel or concurrent programs in the Curry-Howard isomorphism?

The Concurrent Logical Framework is one interesting area including its descendants, like Linear Meld and LolliMon.  This is based on intuitionistic linear logic.

Classical linear logic has connections to the Linear Chemical Abstract Machine (CHAM) as described by e.g. A Calculus for Interaction Nets Based on the Linear Chemical Abstract Machine which explicitly describes the result as a Curry-Howard type result.

Alexander Summers' thesis Curry-Howard Term Calculi for Gentzen-Style
Classical Logics which I have not read seems to be aimed directly at the problem of providing a Curry-Howard correspondence for Gentzen-style calculi.  The $\lambda\mu$-calculus by Curien and Herbelin introduced in The Duality of Computation is a seminal work in this vein of (non-linear) lambda calculi corresponding to classical logics.

At any rate, this is all still a lively area of research.  There are many recent papers on this topic.  The above doesn't even mention the even more substructural side of separation logic and the corresponding Hoare Type Theory which focuses on imperative programming languages.  For example, there's Towards type-theoretic semantics for transactional concurrency whose references you can trace for prior work.

(As a bit of a pedantic note, most of these are focused on concurrency, not parallelism per se.)


How can I make automaton that has given language?

You want to make an automaton that accepts the language
$L_1 = \{ s \in \{a, b\} \mid \text{each $a$ in $s$ is immediately preceded and followed by }b \}$.

A few examples of words that should be accepted are:

$\lambda$ , which is the empty word. There is no $a$ in the empty word so this word should be accepted.
$b^*$, which is any word only containing $b$'s.
Other examples: $bab$, $bbbbbab$, $babababab$.

So let's start constructing. Since the empty word is accepted, the initial state $q_0$ should be an accepting state. A word starting with $a$ can't be accepted, therefore we forward such a word to $q_3$ and let it be stuck there. $q_3$ is not an accepting state.

Now consider a word starting with $b$. The word $b$ should be accepted, so $q_2$ is an accepting state. $b^*$ should be accepted, therefore we define the transition function $\delta(q_2, b) = q_2$. (Any $b$ in $q_2$ goes to $q_2$.)

Now the transition from $q_2$ to $q_4$ is triggered by an $a$. $q_4$ is not an accepting state. If there is another $a$, we know that the input should not be accepted so we define the transition $\delta(q_4, a) = q_3$. Once in $q_3$ it will loop there, so the word can't be accepted.

The transitions between $q_2$ and $q_4$ make sure that any word ending with b is accepted, provided that a sequence of multiple $a$s never occurs. If it does it will go to state $q_3$ and it will be stuck there.


Satisfiability Toward A Sequential Circuit

OK so now I figured this out. The problem is $NP$-complete. We could simply verify an assignment by checking each gate as an equation. For solving SAT of boolean function A(x), simply construct a equation, $y=y\otimes\lnot A(x)$ would suffice.


Using Huffman Encoding to improve Lempel-Ziv Encoding

Huffman encoding is already used this way.

Huffman encoding is already used together with LZ77 to improve its compression rate.  The most widely used instance of LZ77-style compression is DEFLATE.  DEFLATE combines LZ77 with Huffman encoding.  See https://en.wikipedia.org/wiki/LZ77_and_LZ78#Implementations and
https://en.wikipedia.org/wiki/DEFLATE.

Huffman encoding is commonly used together with standard LZW (Lempel-Ziv-Welch) encoders to improve their compression rate.  See the Wikipedia article on LZW and other standard resources on LZW coding for details: https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch


Showing that a problem in $NP$ admits two distinct verifiers that satisfy additional constraints

Since $S \in \mathsf{NP}$, there is a non-deterministic poly-time Turing machine $T^*$ that decides $S$.
Given $x \in S$, let $y^* = \langle y^*_1, y^*_2, \dots\rangle \in \{0,1\}^*$ be the list of non-deterministic choices of $T^*$ that lead to an accepting state in the execution of $T^*(x)$.
It is easy to see that $|y^*| = O(\mathrm{poly}(x))$ and that $y^*$ is a certificate for the the polynomial-time (deterministic) verifier $V^*$ that, with input $V^*(x,y^*)$, checks that the (unique) computation path of $T^*(x)$  when the non-deterministic choices are those in $y^*$ leads to an accepting state.
Define $y_1 =\langle 0, y^*_1, y^*_2, \dots \rangle$ and  $y_2 =\langle 1, y^*_1, y^*_2, \dots \rangle$.
When $y=\langle y_0, y_1, y_2, \dots \rangle$, the verifier $V_i(x, y)$  behaves as follows: if $y_0 \neq i-1$, it rejects. Otherwise $V_i(x, y)$ simulates $V^*(x, \langle y_1, y_2, \dots\rangle)$ and accepts iff $V^*$ accepts. It is clear that $V_1$ and $V_2$ are polynomial-time verifiers for $S$ for the certificates $y_1$ and $y_2$, respectively.
It remains to show that they satisfy the additional constraints from your question.
Notice that, if $V_1(x,y)$ accepts, then $y_0=0$, and hence $V_2(x,y)$ rejects since $y_0 = 0 \neq 1 = 2-1$.
Similarly, if $V_2(x,y)$ accepts, then $y_0=1$, and hence $V_1(x,y)$ rejects since $y_0 = 1 \neq 0 = 1-1$.


Cryptography substitution frequency analysis

I'm by no means an expert but it seems to me that your sample is far too short to be amenable to frequency analysis or, indeed, to cryptanalysis of any kind. Assuming a substitution cypher, you have only the information that eleven letters are used, and characters 1, 4 and 14; 3 and 10; and 8 and 11 are the same. There are fifteen unused characters so there's a huge amount of freedom. You only have a little more information than a one-time pad would give you.

In a long sample of text, it is likely but is not guaranteed that the most frequent character is 'e'; in a fifteen character sample, it's perfectly possible that there are no e's at all. ("Look at my odd words" is a sixteen-letter example.) Frequency analysis helps you figure out the substitutions but it doesn't guarantee to give you the answer with no more work.

Assuming the spaces are significant, your message could be "My emus love no imp". Or it could be something completely different.


Reference request: Monads, continuations, and other functional CS concepts

I would focus on learning a functional language in order to learn these. There's no need for it to be Haskell. It could be Scheme or ML, or even Coq or Agda. Frankly, Clojure will probably do. But to me, monads and continuations are only programming tools. They don't let you do any new computations, they just let you do them in a different way. So understanding them outside of the context of a particular style of programming to me doesn't make much sense.

I'd recommend Real World Haskell as an introduction to some of these concepts, particularly in how they can be used in programming. I'm not sure how much it has on continuations. I learned continuations from Essentials of Programming Languages, which I quite liked, but deals with Scheme rather than Haskell, and doesn't do anything monadically.


Is finding the longest path of a graph NP-complete?

First, it is easy to see that the problem is in $\text{NP}$. The longest path is a Hamiltonian one since it visits all vertices. Indeed, there is a straightforward reduction from $\text{HAM-PATH}$ to it. For details and some special cases, see for example here. Likewise, it is $\text{NP}$-complete to decide whether there is a path of length $k$ with the a similar argument: just set $k$ such that the problem is equivalent of solving $\text{HAM-PATH}$. Finally, if I understood your third point correctly, it doesn't make the problem any easier if you in addition require the path to visit a specific vertex $v$. Similar reasoning holds for this case.


This depends on what you mean by linear time. If you want $O(n)$, then you're out of luck, there's too many edges to consider in the worst case.

If you mean $O(n+m)$, then it is possible, and it is reasonable to consider this as linear time, as the input needs to represent the edges as well as the vertices, which takes at least $O(n+m)$ symbols.

After each round of selecting which new edges to add, we keep track of which pairs of components are being merged, then we look at these in order (any order is fine) and look at all edges from the new component to each other new component, and record the smallest we have seen. (Note that this is symmetric, so we when we find the smallest edge from new component $A$ to new component $B$, it is also the smallest from $B$ to $A$, so we only need to consider edges going to new components later in the ordering, but this doesn't affect the complexity). To achieve this we can simply look at all edges in order and update the appropriate information.


The short answer is: I don't know.

Visualizations

There's been lots of work on visualizing the MNIST data set, in 2 dimensions, and even in 3 dimensions.

For instance, here's an embedding into 2D space using a neighbor embedding visualization technique (a highly nonlinear embedding):

Credit: Zhirong Yang, Jaakko Peltonen, and Samuel Kaski.  See their page on MNIST visualization.

However, the NE embedding is not linear.  It doesn't try to be a linear map from the image space ($\mathbb{R}^{768}$) to the plot ($\mathbb{R}^2$).  Rather, it tries to preserve the topology: it tries to make images that are nearby (e.g., in L2 metric) be near each other in the visualization.

See also this blog article for exploration of different ways of embedding MNIST into two or three dimensions, including both linear embeddings (e.g., PCA) and nonlinear embeddings.

Here's another visualization of doing PCA to 2 dimensions on MNIST:

Credit: taken from this nice blog post

One thing that is clear from those visualizations is that if you do PCA onto two or three dimensions, the result is not linearly separable.  It's not even close to linearly separable.

Even if you look at just two different digits and apply 2-dimensional PCA to project linearly onto the two principal components, the result is again not even close to linearly separable:

Credit: the same blog post

So at least 2 dimensions don't seem to be enough to distinguish 4's from 9's.

In contrast, PCA onto 2 dimensions does give you something that's pretty close to linearly separable: it's enough to distinguish some other pairs of digits pretty well with a linear classifier, but not perfectly -- to get best accuracy, you need more than a linear classifier and more than 2 dimensions.

Read the rest of that blog post to see what happens when you try to do a locally linear embedding to project all MNIST digits onto 2 dimensions.  You'll see that, while there are some commonalities, the result doesn't look good enough to get high accuracy.

A note of caution

We need to be careful about what you mean by "lay on a manifold".  Of course, if you consider all the ways to write a 7 (say), those 7's will all lie on some manifold in $\mathbb{R}^{768}$.  I doubt that manifold is going to be a linear subspace (i.e., a hyperplane).

If you allow arbitrarily nonlinear manifolds, it's not clear that it is useful or meaningful to ask what is the dimension of this manifold.  For instance, consider a mapping that maps each digit to $\mathbb{R}$ (1 dimension), e.g., all 0 digits get mapped to 0, all 1 digits get mapped to 1, all 2 digits get mapped to 2, and so on.  This is clearly possible in principle, but the mapping is extremely nonlinear.  Would you consider this evidence that the digits lie on a 1-dimensional manifold?  Probably not.  This highlights the challenge in making our intuition more precise.

So you need to make sure you are asking the right question.

Measuring dimensionality by learning

One way to think about this is to look for an embedding $f:\mathbb{R}^{768} \to \mathbb{R}^d$ into some lower-dimensional space ($d$-dimensional space), with the two properties that:

The embedding $f$ is "nice" in some fashion -- it need not be linear, but hopefully it is continuous or locally linear or something like that.
Enough information is preserved that we can still classify which digit it is, based on the result of the embedding.  In other words, given an image $x$ of an image, we should be able to tell which image it is given only $f(x)$: the result $f(x)$ of the embedding should be enough for a classifier to tell which digit it is, with about as high accuracy as would be possible given the original image.

People have studied this.  For instance, people have built autoencoders, which are basically a way to use a deep neural network to build an embedding $f$ such that you can still reconstruct the image with reasonable accuracy.  You can train an autoencoder on the MNIST digits to build an embedding $f$ that maps to a lower-dimensional space, then train a classifier that tries to label the digits based on the result of the embedding.  The following paper looks at one approach to that, on the MNIST data set:

Wei Wang, Yan Huang, Yizhou Wang, Liang Wang.  Generalized Autoencoder: A Neural Network Framework for Dimensionality Reduction.  IEEE Conference on Computer Vision and Pattern Recognition, 2014, pp.490--497.

They build autoencoders that map to a 30-dimensional data space, and where a simple classifier achieve an error rate of 4-5%.  For MNIST, 4-5% error rate is very high: the state of the art is an error rate of 0.5% or so, when training a classifier on the original images.  So this means that, as far as we know, if you try to map down to 30 dimensions, a lot of information is still preserved, but a significant amount is lost: you lose enough information that the classifier's error rate increases by an order of magnitude.

In short, 30 dimensions doesn't seem to be enough, at least for an embedding built in this way.

The other caveat is that the embeddings built in this way use a multi-linear neural network, and thus might still be fairly nonlinear.  If you demand a particularly "smooth"/"nice" embedding, this result might not be relevant.


Encoding first order formula (or its tree) into binary string?

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

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

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


Examples of random deployment in wireless sensors networks

One scenario that I've heard discussed is the idea that an airplane flies over a remote area and drops wireless sensors.  They fall somewhat randomly, and then need to establish a network amongst themselves.


Every LEFT-RESET Turing machine has an equivalent conventional Turing machine

The other write-ups you mention show that the two models are equivalent. That is, they also show that a normal Turing machine can be simulated by a left-reset Turing machine.


Algorithm for finding fixed cycles in bipartite graphs in sublinear time

In general, you can't determine if there is a e.g., 4-cycle in an arbitrary graph in sublinear time. This is shown by a simple adversary argument: if you don't read the whole input (this is what sublinear means), how can you possibly know if a critical edge is present that creates the 4-cycle? There are similar questions asked already, but these appear in a different context (usually, these are related to sorting). For instance, see this question.

If you assume the input graph is complete, or has some other structure that guarantees the existence of a 4-cycle, an algorithm for solving the problem can immediately output YES. But if the input graph is arbitrary, again by an adversary argument you cannot determine if the graph is say complete in sublinear time.

For example, if the input is a $K_{3,3}$, you can immediately answer YES. So suppose the input graph is an arbitrary bipartite graph, and we are looking for a $k$-cycle for a fixed $k$. If $k$ is odd, we can output NO, as bipartite graphs are characterized by having no odd cycles. Otherwise, an adversary argument shows that for even $k$, sublinear time is not achievable. Similarly, it is easy to see you cannot test for bipartiteness in sublinear time. (For both cases, consider having read $m-1$ edges, and the last $m$th edge to be read decides if you have a path or a cycle).


If you could create the convex-hull in $o(n \log n)$ time, this would imply, that you can sort $n$ numbers in $o(n\log n)$ time.

You do this with contradiction. You have $n$ numbers $(x_1, x_2, \ldots, x_n)$, which you would like to sort. From these numbers, you create points $P$ in 2D space in some fashion. For example $p_i=(x_i,x_i^2)$.

On these newly constructed points $P$ you call the algorithm for convex hull, which returns you the actual convex hull.

After that, you simultaneously traverse upper and lower hull, from the lower left-most point in (which you find in $O(n)$ time), to the upper right-most point. With this traversal you actually sort the numbers. Let $p_i$ and $p_j$ be the next points on lower and upper hull, then if $x_i<x_j$, you move one step ahead on the lower hull and add $x_i$ to the end of the sorted array (else you take one step ahead on the upper hull and add $x_j$ to the array). You then finish when the traversals meet in the upper right-most point of the convex hull.

The algorithm that I described is run in $O(n)$ time. So if the convex-hull algorithm would be $o(n\log n)$, the sorting of $n$ numbers could be also done in $o(n\log n)$ time, which is a contradiction since we know that sorting $n$ numbers takes at least $\Omega(n \log n)$ time.


Here are a few random ideas:

The dynamic-programming algorithm can be flipped to look for a smallest sum instead of a largest sum. You just end up looking for a sum congruent to the remainder of the sum of the entire array, instead of one congruent to zero. If we process the elements in increasing order, this sometimes allows the dynamic algorithm to terminate before processing the entire array.

The cost would be $O(n k)$ if we processed $k$ elements. There's not a lower bound of $\Omega(n \log n)$ on this algorithm because we don't have to sort all the elements. It only takes $O(n \log k)$ time to get the $k$ smallest elements.
If we cared about the set with the larget size, instead of the set with the largest sum, we might be able to use fast-fourier-transform-based polynomial multiplication to solve the problem in $O(n (\log n)^2 (\log \log n))$ time. Similar to what's done in 3SUM when the domain range is limited. (Note: use repeated squaring to do a binary search, else you'll get $O(n k (\log n) (\log \log n))$ where $k$ is the number of omitted elements.)
When $n$ is composite, and almost all remainders are a multiple of one of $n$'s factors, significant time might be saved by focusing on the remainders that aren't a multiple of that factor.
When a remainder r is very common, or there are only a few remainders present, keeping track of 'next open slot if you start from here and keep advancing by r' information can save a lot of scanning-for-jumps-into-open-spots time.
You can shave a log factor by only tracking reachability and using bit masks (in the flipped dynamic algorithm), then backtracking once you reach the target remainder.
The dynamic programming algorithm is very amenable to being run in parallel. With a processor for each buffer slot you can get down to $O(n)$. Alternatively, by using $O(n^2)$ breadth, and divide and conquer aggregation instead of iterative aggregation, the circuit depth cost can get all the way down to $O(\log^2 n)$.
(Meta) I strongly suspect that the problem you were given is about contiguous sums. If you linked to the actual problem, it would be easy to verify that. Otherwise I'm very surprised by how difficult this problem is, given that it was assigned in a course called "Introduction to Algorithms". But maybe you covered a trick in class that makes it trivial.


For large enough $p$, consider the word $w = 0^{p+1}1^{p+1}\#0^{p+1}1^{p+2} \in L$. Mark the part $1^{p+1}\#0^{p+1}$. According to Ogden's lemma, we can write $w = uxyzv$ such that $xyz$ contains at least $1$ and at most $p$ marked symbols, and $ux^iyz^iv \in L$ for all $i \geq 0$. The pumped part $xyz$ cannot lie all to the right of $\#$ since then pumping it down would result in a word not in the language (here we crucially use the fact that only the $0^{p+1}$ part to the right of $\#$ is marked). It also cannot lie all to the left of $\#$ since then pumping it up would result in a word not in the language. It follows that the part of $xyz$ to the right of $\#$ is of the form $0^k$, and the part of $xyz$ to the left of $\#$ is of the form $1^\ell$ (otherwise, there would be more than $p$ marked symbols). However, pumping up, the resulting word is not in the language. This contradiction shows that $L$ is not context-free.


1 bit register with data flip flop doesn't store bit?

Your table is incorrect. A MUX element selects one of its inputs based on a secondary input. In this case it's a binary mux and load is used to select the input.

If we say that load = 0 means it selects the DFF and load = 1 means that it selects in you shall see that when load = 0 the circuit repeatedly refreshes the previous value, and load = 1 will read the new value from in.


If each set maintains a record of what other sets exist, and you have a total of $s > 0$ sets, you can easily turn any data structure for a collection (e.g. binary search trees, etc.) into one where you can have retrieval of an element of the intersection of two sets in time $O(\log s)$.

Each set should have a unique identifier from some totally ordered set. If you explicitly name your sets $S_1, S_2, \ldots$ then the identifier could just be the index.
You should implement a "registry" of the sets; a data structure which maintains a collection of all of the sets which you have defined. The registry should be implemented as a search-tree data structure, to allow easy retrieval (e.g. if you wish to delete the set) and linear-time traversal of the sets.
Each set $S_j$ also maintains an "index" of each of the other sets — not a copy of them, but rather a data structure which is indexed by the labels of the other sets. This index will be used to maintain, for each set $S_k$, a binary search tree of all of the elements of $S_j \cap S_k$. (The two sets $S_j$ and $S_k$ share one copy of that search tree.)

Initialization

Initialization of a set $T = \varnothing$ consists of $O(1)$ operations to initialize the tree of its elements, $O(s)$ operations as you initialize (copying from the registry) the index for the set $T$, and $O(s \log s)$ operations as you traverse the registry to add $T$ into the indices of each of the other sets $S_j$. In the index of $T$, we create search trees representing $T \cap S_j = \varnothing$ for the other sets $S_j$; we copy the same pointer for the index of $S_j$.

Adding an element to a set $T$

Adding some $x \in V$ to the set $T$ takes time $O(\log n_T)$ as usual, where $n_T = |T|$. We also test for membership of $x$ in each of the other sets $S_1, S_2, \ldots$, which takes time $$O(\log n_{S_1} + \log n_{S_2} + \cdots) \subseteq O(s \log n) ,$$ where $n = |V|$ is the size of the universe (or of the largest set $S_j$) and $s$ is the number of sets in the registry.
For each set $S_j$ such that $x \in S_j$, also insert $x$ into the index for the set $S_j \cap T$.
For each such set $S_j$, this takes $O(\log s + \log n_T)$ time, to look up  $S_j$ in the index of $T$ and to insert $x$ in $S_j \cap T$; across all sets $S_1, S_2, \ldots$ this takes time $O(s \log s + s \log n_T)$. If we suppose that the number of sets $S_j$ is much less than the size of the universe $V$ (that is, if we suppose $s \ll n$), the total time for element insertion is then $O(s \log n)$.

If you do not allow duplicates in sets, we can save time in the case that $x \in S$ already by forgoing the membership test and insertions for the other sets $T$. "Insertion" in the case that $x$ is already present then takes time only $O(\log n_T)$.

Intersection testing

The index of each set is maintained precisely in order to allow quick evaluation of whether or not two sets $S_j$ and $S_k$ intersect.
For a set $S_j$, simply by checking its index for the set $S_k$, we can not only determine in time $O(\log s)$ whether or not $S_j$ intersects $S_k$, but we can also retrieve a binary tree containing the entire set $S_j \cap S_k$.

Element Removal

To delete an element $x$ from a set $T$, we remove it not only from the search tree for $T$ itself, but from each of the intersections $S_j \cap T$ for the sets $S_j$ in its index. This takes time $O(s \log n_T)$, where $n_T = |T|$.

Set Deletion

Because of the overhead of searching the registry, if you have many sets, it may be desirable to delete sets once they are no longer needed.
By traversing the entire registry, we may delete $S$ from the index of all other sets $S_j$ in time $O(sn_T)$, dominated by the cost of deleting the search tree representing $S_j \cap T$ for each of the other sets $S_j$, where $n_T = |T|$.

Remarks

If you expect only to implement a constant number of sets, then the above run-times reduce to:

initialization: $O(1)$
element insertion: $O(\log n)$
intersection testing (and retrieval of the intersection): $O(1)$
element removal: $O(\log n_T)$
set deletion: $O(n_S)$

where $n$ is the size of the largest set in the registry, and $n_T = |T|$ for the set $T$ which you are operating on.

If you expect to have $O(|V|)$ sets, where $V$ is your universe, you may need a different data structure if you want these operations to operate in sub-linear time. However, if you have pairs of sets whose intersection you know you will never test, you might be able to reduce the size of the index for the sets (by not including any sets whose intersection you will test) or use more than one registry (one for each collection of sets whose intersection you might test). In fact, a registry is only useful if you want centralized control of ensuring that each pair of sets has a record of each other in the index: it may be practical in some cases, at the initialization of a set $S$, simply to record ad hoc each new set into the indices of the other sets $T$ whose intersection with $S$ you are interested in.


Build a context-free grammar for a context-free language

$ S \rightarrow EG $ ,
$ E \rightarrow aO \mid λ $ ,
$ O \rightarrow aE $ ,
$ F \rightarrow bFcc \mid λ $,
$ G \rightarrow bFcc $ .
I am assuming $λ$ stands for empty string.

Better one:

$ S \rightarrow EF $ ,
$ E \rightarrow aO \mid λ $ ,
$ O \rightarrow aE $ ,
$ F \rightarrow bFcc \mid bcc $.


Maximum Spanning Tree vs Maximum Product Spanning Tree

You state several beliefs but no reasoning. In math, if things are true then usually there is a good reason, namely a proof that the thing is true. Don't just make guesses, try to prove that your claims hold.

Regarding your conjecture, consider Kruskal's algorithm, modified so that it arranges the weights in decreasing rather than increasing order. If we apply any monotone increasing function on the weights, the algorithm would make exactly the same choices. Consider what happens when you replace each weight $w$ by its logarithm $\log w$. The weight of a spanning tree containing the edges $e_1,\ldots,e_{n-1}$ is then
$$
\log w(e_1) + \cdots + \log w(e_{n-1}) = \log [w(e_1) \times \cdots \times w(e_{n-1})].
$$
In other words, after replacing all weights with their logarithms, you are actually computing the maximum spanning tree with respect to product. Since both algorithms compute the same spanning tree, your conjecture is correct.


Prove that regular languages and context-free languages aren't closed under $Perm(L)$

Hints:

For regular languages, consider $Perm((01)^*) \cap 0^* 1^*$.
For context-free languages, consider $Perm(0^n 1^n 2^m 3^m) \cap 0^* 2^* 1^* 3^*$.


Firefly algorithm number of objective function calls

It seems to me that you are correct. I haven’t read the whole algorithm carefully though. One alternative is that maybe they intend for the movement to be simultaneous, so that the firefly that’s currently being placed moves towards all the bright fireflies at once, then recalculates once for the new position?

But as is, it seems like the pseudo code for the algorithm and the description don’t line up.


No. Consider the counterexample $C_4$

$V = \{1,2,3, 4\}, E = \{ \{1,2\}, \{2,3\}, \{3, 4\}, \{1,4\} \}$

with $c(1,2) = 1, c(2,3) = 100, c(3,4) = 1, c(1,4) = 2$.

Obviously the MST is the one ST not containing $\{2,3\}$, but if your algorithm starts at 1, it goes to 2, then to 3 and then to 4 and finds a suboptimal ST containing $\{2,3\}$.

The main problem of your algorithm is that it always computes a path (i.e if there is no path of length $|V| - 1$ your algorithm can terminate without finding a ST), which the MST must not always be.


Simplyfing a particular boolean expression

I will use $\land$ instead of * and $\lor$ instead of +.

a) You could  simplify it as following:

$ \ \ \ (y\land w) \lor y \lor w = (y\land w) \lor (y \land T) \lor w = y\land(w \lor T) \lor w = (y \land T) \lor w = y \lor w$

b) and prove it as following:

Since $x \land y = x$ we have $\lnot x \lor \lnot y = \lnot x$ by De Morgan's law. By substituting $\lnot x$ in the given equality we have
$$\lnot x \land \lnot y = (\lnot x \lor \lnot y) \land\lnot y = (\lnot x\land \lnot y) \lor (\lnot y \land \lnot y) = (\lnot x\land \lnot y) \lor \lnot y = $$
$$=(\lnot x \lor T)\land \lnot y = T \land \lnot y = \lnot y$$

Recall that for any boolean $x$ and $y$ the following identities always hold

$x \lor T = T$
$x \land T = x$
$x \land x = x$
$x \lor x = x$
$\lnot(x \land y) = \lnot x \lor \lnot y \text{ (De Morgan's law)}$
$\lnot(x \lor y) = \lnot x \land \lnot y \text{ (De Morgan's law)}$


Proof that multi-armed bandit optimization has exponential regret if loss function is general

I'm not exactly sure what he means, but here's a very similar example in a discrete version. Imagine the strategy space weren't continuous but instead consisted of all points in $\{\pm 1\}^d$, one point in each of the $2^d$ orthants. The cost function $C$ is $0$ in all but one of those locations, where it is $-10$.

In order to get any decent regret, you have to figure out which point is the one with cost $-10$ and start choosing it repeatedly. But how will you figure it out? Your only way is to just try different points until you find the right one. But it will take on the order of $2^d$ tries to find it since that are the number of options.

This raises the question - how can a restriction like making $C$ convex rule out this kind of example?


Unrestricted grammar for the language of strings whose length is not $2^n$

Your method is correct to generate $L$. But if you change the rule to $0a \to a^k0$ then the language you generate is $L^{'}=\{a^k,a^{k^2},a^{k^3}....\}$ ( $k >2$) .
You can show that language $L$ is indeed decidable. One way is to give an algorithm that halts on every input in $\sum^{*}$ and gives the correct result. Following is the approach

(1) If the input is empty reject.
(2) If not empty , check if there are even number of 'a' or odd. If only one 'a' is there accept. If odd 'a' ( > 1 ) are there reject.
(3) If even 'a' are there, go back to starting of input and cross off alternate 'a' from beginning to end of input. Go back to step (2).
The algorithm accepts the string $a$ in addition. You can always modify the above algorithm, keeping a special check that if the input is 'a' reject.


A

  $k$ represented this number of digits of maximum value.

B

  k is the number of bits required to represent largest element in the array

This translates to number of digits required to represent the max value in binary.

A is equivalent to B.

Here is how:

Say largest element in the array is 1233.

According to B, $k = log_2(1233) \approx 11$

According to A, $k = 4$, which is just $log_{10}(1233)$.

There is formula for converting between the
$$log_a(n) = \frac{log_b(n)}{log_b(a)}.$$

The denominator here $log_a(b)$ is a constant.

So $log_2(n) = O(log_{10}(n))$. So it doesn't really matter to radix sort what base you are using.


You want to access every leaf in a tree, you probably do not want to start from the root every time. If you would then you need indeed $O(N \log N)$ time. If you only want to access all the leaves in the tree, do a depth-first-search traversal and you are done in $O(N)$. If you only want to have every other leaf, do the same, but ignore the "unwanted" elements.

In data structure design one often takes the leaves and put them (in order) in a double linked list. This only costs a constants factor more place, but speeds up sequential access.


Here are some ideas:

Suppose that $\ell$ is a leaf of $T$ which doesn't belong to $S$. Then we can safely remove $\ell$.

Suppose that $\ell$ is a leaf of $T$ which does belong to $S$. If its unique neighbor is also in $S$, then we can safely pair them up.

Suppose that $\ell$ is a leaf of $T$ which belongs to $S$, but its unique neighbor $r$ doesn't belong to $S$. We can safely remove $\ell$ and replace it in $S$ by $r$.

(How to implement these ideas efficiently is a different matter, but for an existence proof these ideas suffice.)


This requires some basic logarithm concepts. You may have come across logarithmic equations with general definition as:

logb(x) = y is valid if by = x | Here b is the base, y is the exponent value that makes by = x

Let's consider x having a value 64. Below are some logarithmic outputs (y) with different bases:

log2(64) = 6 | As, 64 = 26 (base 2)
log4(64) = 3 | As, 64 = 43 (base 4)
log8(64) = 2 | As, 64 = 82 (base 8)

If you notice above, the logs of different bases are only different by a constant factor. (between 6, 3 and 2)
Now let's consider no change in base and this time we will consider exponential base, a general expression would be something like:

loge(x) = y , or ln(x) = y

Let's consider x having value 2n. So y will be:

y = loge(2n), or y = ln(2n)

Now if we change value of x to 8n then y would be:

y = loge(8n) = loge(23n)

23n can be represented in terms of 2n as:

23n = 22n * 2n (or 23*n or 2n * 2n * 2n)

If you notice, the difference between x being 2n and x being 23n is not by any constant factor.
Hence validating the statement:

The base of an exponent does matter. Compare 2^n and 8^n. If you expand 8^n, you get (2^3)^n, which equals 2^3n, which equals 2^3n * 2^n. As you can see, 8^n and 2^n are different by a factor of 2^2n. That is very much not a constant factor.