Find the longest contigous subsequence where each pair's difference is at most p

You can solve this in $O(n\log n)$ using a Range Minimum Query data structure. This is a data structure that given two indices $i \leq j$ return $\min(x_i,\ldots,x_j)$. We can construct a data structure that answers such queries in $O(1)$ time using $O(n\log n)$ preprocessing. The idea is to compute $\min(x_i,\ldots,x_j)$ for every pair $i \leq j$ such that $j-i+1$ is a power of 2. This can be accomplished in time $O(n\log n)$ using the identity
$$\min(x_i,\ldots,x_{i+2^{\ell+1}-1}) = \min\bigl(\min(x_i,\ldots,x_{i+2^\ell-1}),\min(x_{i+2^\ell},\ldots,x_{i+2^\ell+2^{\ell}-1})\bigr). $$
Using this information, we can compute each range minimum query as follows. Given $i\leq j$, let $2^\ell$ be the largest power of 2 such that $2^\ell \leq j-i+1$; we assume that we can compute $\ell = \lceil \log_2 (j-i+1) \rceil$ in constant time. Then
$$
\min(x_i,\ldots,x_j) = \min\bigl(\min(x_i,\ldots,x_{i+2^\ell-1}), \min(x_{j-2^\ell+1},\ldots,x_j)\bigr).
$$

For each $i$, we use binary search to compute in time $O(\log n)$ the maximal $\ell \leq i$ such that $\min(x_\ell,\ldots,x_i) \geq x_i-p$ and the minimal $r \geq i$ such that $\min(x_i,\ldots,x_r) \geq x_i-p$. Thus $x_\ell,\ldots,x_r$ is the largest interval satisfying your constraint in which $x_i$ is the maximal point. Taking the maximum of $r-\ell+1$ over all $i$ reveals the solution to your task.


Why do Tarjan's and Kosaraju's algorithms for finding strongly connected components have the same running-time complexity?

they say that both have O(|V|+|E|) time complexity.

that didn't make sens for me since Kosaraju use two dfs pass and compute transpose graph, but Tarjan's use only one dfs

If you check the definition of Landau notation you will see that it does not say which function is smaller, that is (here) which algorithm is faster. It ignores constant factors.
Both algorithms have running times in $\Theta(|V| + |E|)$; that does not preclude one of them being $2^{100}$ times faster than the other for all $n \leq 2^{100}$.


space complexity of DFA intersection problem

Solving intersection Non-Emptiness for 2 DFA's:

It essentially just becomes a reachability problem for the product DFA.

Roughly, we can solve it deterministically in $O(n^2)$ time using $O(n^2)$ space.
Or, we can solve it non-deterministically with $O(\log(n))$ space.
By Savitch's Theorem, we can also solve it deterministically in $2^{O(\log^2(n))}$ time using $O(\log^2(n))$ space.

To the best of my knowledge, it is not known if we can solve it deterministically in polynomial time using $O(n^{2-\epsilon})$ space.

Feel free to share any thoughts or ideas in the comments.  :)


Time complexity of finding median in data stream

From a brief look at Leetcode streaming problem solutions, the complexity solutions provided for streaming problems refer to the time complexity of a single iteration for the stream i.e. after $n$ elements in the stream, what is the complexity of updating the data structure and answering a query with a new element?


How many shortest distances change when adding an edge to a graph?

Consider the following linear chain with $n+1$ nodes, $n$ edges and viciously chosen weights:

[source]

Clearly, the edges could have been added in order of their weights and there are $n \in \mathcal{O}(|V|)$ of them. Adding the dashed edge (which is legal) creates shorter paths for all pairs $(u_i,b_j)$ with $i,j = 1,\dots,k$. As $k \approx \frac{n}{4}$ and assuming that $n \in \Theta(|V|)$, both first and last row contain $\Theta(|V|)$ many nodes each and the addition causes $\Theta(|V|^2)$ many shortest path changes.

We can now move "outwards" now, i.e. add the next edge with weight $n+2$ between $u_{k-1}$ and $b_{k-1}$ and so on; if we continue this to $(u_1,b_1)$, we cause in total $\Theta(|V|^3)$ shortest path changes.

If this does not convince you, note that you can actually start this "process" with $(c_1,c_2)$ and work outwards from there; this way you add $\approx n$ edges which cause in total $\approx \sum_{i=1}^{n}i^2 \in \Theta(n^3) = \Theta(|V|^3)$ many shortest path changes---this is just impossible to draw to fit on one screen.


Use or Importance of $\Rightarrow^*$ operator

It is false that $\Rightarrow^*$ " just replaces the head of the production with the head itself". $A \Rightarrow^* B$ means that the sentential form $B$ can be obtained from the sentimental form $A$ by applying any number of productions (which might be $0$ or more than $0$).

For example if your grammar is $S \to a$, then all of the following are true  $S \Rightarrow^* S$, $S \Rightarrow^* a$, and $S \Rightarrow^+ a$, while it is false that $S \Rightarrow^+ S$.

If you are deriving strings and applying at least one production per step then both $\Rightarrow^*$ and $\Rightarrow^+$ are correct. The latter is more specific since it implies the former (but not vice-versa).


Is proof of totality of a semantic function for binary numbers cicular?

The proof is by induction on the length of the string. You're proving the inductive claim for all strings of length $n$, both those terminating in $0$ and those terminating in $1$. The proof goes by considering these two cases, but you're assuming and proving the inductive hypothesis for all strings of a particular length at once.


Efficient algorithm for finding optimal sum from both arrays

There are three ways how you could proceed:

If both arrays are already sorted for example in ascending order, then you start at the beginning of the first array and the end of the last array; if the sum is too small you skip to the next element of the first array, if the sum is too large you skip to the previous element of the second array, and so on.

If one array only is sorted, then you try each element x of the other array, lookup the element closest to M - x using binary search, and use the best pair.

If neither array is sorted, you sort either one or both. Calculate the runtime of either approach; it seems best to sort the smaller array, which then takes O (n log m) where m is the size of the larger array, and m the size of the smaller array.

If the larger array is already sorted, sorting the smaller array as well may be faster, because the sorting is done in O (m log m), and the first method takes only linear time. And if the arrays are of comparable size (say $m = n^{1/2}$) so log m vs. log n doesn't affect asymptotic behaviour, then what is fastest on some implementation will depend on the actual implementation.


Can any computably enumerable set be generated by a prefix-free set?

After a lot of thinking and reading, and getting a helpful answer and comments from Andrej Bauer to another question that my investigation prompted, I can answer my own question.  I post an answer for the benefit of anyone who may find the question to be similar to one of their own.  I expect no upvotes for answering my own question.
Downey and Hirschfeldt prove (2.19.2, p. 74) that every $\Sigma^0_1$ set of infinite sequences is one that can be generated by a c.e. set of finite strings.  Moreover, they define Martin-Löf randomness in terms of a sequence of $\Sigma^0_1$ sets $U_n$ of infinite sequences.  This is why they have the right to assume that every such $U_n$ can be generated by such a set of finite strings.
In my gloss of D&H's description of a Martin-Löf test, I stated the requirement that the test sets be $\Sigma^0_1$ as a requirement that they be computably enumerable.  One can see the equivalence of $\Sigma^0_1$ and c.e. as implied by D&H's proposition 2.19.2, but it's proved directly by, for example, Nies, 1.4.12, p. 22.  So the way that I characterized D&H's description of Martin-Löf tests was correct.
While it's true that $U_n=\{000\ldots\}$ can't be generated by finite strings, my mistake was thinking that such a $U_n$ is computably enumerable.  It was surprising to me to realize that such a trivially simple set is not c.e.  After all, the set has only one element, and a Turing machine that generates it or checks for it is trivial.  The crucial point, though, is that that machine cannot halt on $000\ldots$, since the sequence of zeros is infinite.  No program can ever successfully list or accept even (the) one member of this set.  Thus my sequence of sets $U_n$ do not form a Martin-Löf test.
(It is possible to define a Martin-Löf test that excludes only $000\ldots$ from the random sequences, but that test has to consist of sets such as, for example, $U_n=\{x:$ the first $n$ digits of $x$ are 0$\}$.  Each such set contains an uncountably infinite number of infinite sequences, but each is a subset of previous sets $U_1, U_2, \ldots, U_{n-1}$. The one sequence contained in each of them is $000\ldots$ .)


The optimal way to find leaves in a weighted full binary tree

Hint: How many paths are there from a given leaf to the root?


According to Wikipedia:

  A heuristic technique (...) is any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals.

Thus you can employ a heuristic to design an algorithm. This would give suboptimal answers, however you can still state theorems that relate to the correctness of such algorithm:

For optimization problems you may write something like:

  For any $\epsilon>0$, the algorithm approximates the problem $P$ with a multiplicative factor $1+\epsilon$ in time $O(T(\epsilon))$.

which means that for every input, if the expected answer of $P$ is $y$ and your algorithm returns $y'$, then:

$$y\le y'\le (1+\epsilon)y$$

You can also bound the error with an additive factor for instance.

For decision problems, if you fix a probability distribution on the input, you may state that your algorithm returns a correct answer with a probability of 90%. That would be a correctness result.

In any case you should keep in mind that a heuristic usually denotes general ideas applicable in many situations, which is said to work well empirically and for which you don't try to prove error bounds (such as in simulated annealing).


I want to learn more about computer science. Where should I start?

This sounds like a better fit for say academia.stackexchange, as this is mostly subjective, so bear in mind this is mostly "just my opinion".

My advice would be to start with Algorithms, at a high level: learning about the big algorithmic paradigms (greedy, dynamic, linear programming...), runtime analysis (all the landau notations and derivatives, amortised analysis...), and go through the sorting algorithms at least. A good resource for that could be [1]. This part should be seen as "fun problem solving" I reckon.
In parallel, I would study the foundations of computer science and computability (easier if you've studied Logic before):

Starting with finite automata/rational languages, and grammars
Building your way up to Turing Machines (with equivalency to recursive functions and lambda calculus)
Finally getting to the distinction between computable and undecidable

Along the way you should have got a small introduction to complexity theory, which should enable you to understand what the classes P and NP are, as well as what an NP-complete problem is.

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd. ed.). The MIT Press.


Generating integer vectors sorted by total weight

I'm assuming the following version of the problem. We are considering all vectors in the set $[N_1] \times \cdots \times [N_d]$ (of which there are $N_1\cdots N_d$). We are given weights $w_{i,1} \leq \cdots \leq w_{i,N_i}$ for each of the $d$ sets (if you prefer, you can index the elements starting from 0 instead of starting from 1). Our goal is to enumerate $[N_1] \times \cdots \times [N_d]$ in non-decreasing order of weight, where the weight of $(x_1,\ldots,x_d)$ is $w_{1,x_1} + \cdots + w_{d,x_d}$.

One possible approach uses a heap. The heap is initialized with $(1,\ldots,1)$. At each step, we extract the element $(x_1,\ldots,x_d)$, output it, and insert the up to $d$ elements obtained by increasing each of the coordinates by 1 (unless it equals its maximum). It is hard to estimate the complexity of this algorithm, but it might work reasonably well in practice.


why don't we use machines with random access memory as our basic model of computation?

Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation?

The short answer is that this model is actually more complicated to describe and prove things about. "Jumping" from one place in memory to another is a more complex operation. Note that it requires:

Reading an address (requires that we define how the address is written on the tape)
Jumping to where that address says on the tape

Alternatively I'm not sure what you have in mind by "register machine", but this also requires care. How large can the registers be? And the machine then has separate mechanisms for how it accesses/modifies the registers, and how it accesses/modifies main memory.

In sum, it's a more complicated model and Turing machines are easier to deal with.

However, the long answer is that theoretical computer scientists do use a model with random access memory, in real practice: it's called the RAM (Random Access Machine) model. The Turing machine is not considered to be a good model for so-called "fine-grained complexity" (e.g. whether a problem can be solved in $O(n^2)$ or $O(n)$ time), and so this requires more careful models. The RAM model is standard and perhaps, arguably, more accepted than the Turing machine as a model of how real computers work, despite being more complicated.

For example, we can show that for a Turing machine to decide if two strings are equal requires $O(n^2)$ time. But this of course does not hold in more accurate models of computation like the RAM model, where it will take $O(n)$. Therefore:

If you just care about whether a problem can be solved at all (or whether it can be solved in polynomial time), Turing machines are considered sufficient.
But if you care about exactly how difficult it is to solve, then you have to resort to a more complex model, such as RAMs.


The statement (2) is ambiguous. It could mean either
$$
L \text{ is regular but } L \text{ is not equal to } 0^+ \tag{1}
$$
Or it could mean,
$$
L \text{ is regular but } 0^+ \text{ is not regular} \tag{2}
$$
(1) is true and (2) is false.
The authors of the question intended it to mean (1).
But you thought that the meaning was (2), so you were confused.


Can we implement every algorithm using only immutable variables?

Probably not, but I don't know if this has been definitely proven, and it depends on what you'll allow as "using only immutable variables".

In 1997 Pippenger published Pure versus Impure Lisp (Technical Report). This paper gives a negative answer when the programming language is Lisp with and without mutation (RPLACA and RPLACD) under some restrictions, namely the program consumes and produces sequences of atoms, and the program must be on-line meaning given potentially unbounded sequences as input, the program must output the $n$th output before consuming the $(n+1)$-th input. One thing to note, is that there is an unlimited supply of atoms, so each individual atom can contain an arbitrary amount of information. That said, it is difficult to get information out of an atom as it only supports equality. Part of the motivation for the first restriction is, as discussed in the papers introduction, "pure Lisp" can't make cyclic structures. If we allowed arbitrary structures as output, then there would be some (representations of) outputs that "pure Lisp" would simply be unable to make.

Now this is all well and good but also published the same year by Bird, Jones, and de Moor we have the paper More Haste, Less Speed: Lazy versus Eager Evaluation (PDF). This implements Pippenger's counter-example in the lazy language Haskell (but a lazy version of Lisp could also easily have been used) with the desired performance guarantees. (Not mentioned, but laziness also allows us to make cyclic structures.) That said, lazy evaluation, i.e. call-by-need not call-by-name, is usually internally implemented via mutation, but this internal mutation is unobservable from the language. I don't believe either paper discusses space usage.

More practically speaking, array algorithms are often the bread-and-butter of imperative programming, while in (pure) functional programming mutable arrays are awkward. (Graph algorithms are another area where pure functional programming struggles.) I'm pretty sure no one has demonstrated how to implement a persistent array with $O(1)$ lookups and updates to all versions. We can make persistent arrays with $O(1)$ lookups and updates to the latest version (and slower lookups/updates for older versions). Haskell's DiffArray implements this, though again the implementation utilizes mutation, but again this is not observable to the program. Since imperative programs are forced to use (mutable) data structures in a single-threaded manner anyway, this should allow any imperative array algorithm to be implemented in Haskell with no asymptotic slow-down (from the array at least).

The question gets murkier as we allow more features in the language. For example, the Clean programming language, another pure, lazy functional language introduced around the same time as Haskell, never had any trouble with arrays. Clean supports uniqueness typing which can guarantee that the reference you have to a data structure is the only reference. This allows operations to be implemented with in-place updates. The interface, though, is the same as the immutable interface except for an extra typing discipline. In particular, the updates could be implemented in an immutable fashion without the program being able to tell the difference.

Theoretically, I believe the question is still open, but it depends on what you consider the machine model. In some machine models it is answered. Practically, it's pretty clear that mutation is sometimes the only reasonable approach, but purely functional interfaces to mutation and mutable structures blur things a bit.


There's no list here. In this problem, $a, b, c$ are simply numbers, so the $k$ loop will iterate $c$ times, taking the values $k=1, k=2, \dotsc,k=c$ for any values of $i$ and $j$. Working outwards, the $j$ loop will iterate $b$ times and each time will perform a complete $k$ loop. In other words, the total amount of work done by the $j$ loop will be $bc$: $b$ iterations of the $j$ loop, each involving $c$ steps of the inner $k$ loop, no matter what the $i$ value is. Finally, in a similar way, the outer $i$ loop will iterate $a$ times, each time doing $bc$ work. The total number of iterations, then, will just be $abc$.

For example, with $a=2, b=3, c=2$ the $(i, j, k)$ values will be, in order,
$$\begin{array}{c}
(1,1,1) \\
(1,1,2) \\
(1,2,1) \\
(1,2,2) \\
(1,3,1) \\
(1,3,2) \\
(2,1,1) \\
(2,1,2) \\
(2,2,1) \\
(2,2,2) \\
(2,3,1) \\
(2,3,1) \\
\end{array}$$


If a solution to Partition is known to exist, can it be found in polynomial time?

I think the whole misunderstanding comes from an incorrect definition of TFNP. TFNP is for problems like factoring, where there is always a solution. Every integer has a prime factorization, so you don't have to make any restrictions on what inputs are allowed - i.e., every input string of bits represents a number that has a factorization. This is different from a promise, which is more like what you're describing.
Unlike integers and factorizations, there are sets that do not have equal-sum partitions. And if you change the input format to be some strange representation of sets of integers such that every set represented always has a valid partition, then you change the problem entirely. A program that solves this new problem probably couldn't be used to solve the original NP-hard Partition problem.
(GuaranteedPartition is also not a decision problem, so it's not NP-hard either - although a machine that solved GuaranteedPartition could be used to solve anything in NP, as you point out.)


Why can't we solve the Halting Problem by using Artificial Intelligence?

The halting problem is not a statement about intelligence (human or artificial) it is a statement about the limits of mathematics.  It is an historically important example of an undecidable problem.

An artificial (or human) intelligence can certainly look for and find many sorts of different infinite loops in real programs.  And the halting problem doesn't say that such a thing is impossible or even very hard.

What the halting problem says is that given any program $I$ ("I" for "intelligent"), (say a really complicated AI program written in Netbeans) that looks for infinite loops we can produce a program that $I$ can't analyze.  The way we do this is a clever technique called diagonalization, which is described in the question @Raphael linked: How to show that a function is not computable?, and also in Why, really, is the Halting Problem so important?

The halting problem is similar to the Liar's Paradox in that it demonstrates the limits of mathematical and logical definitions of "truth", and "provability".  The Liar's Paradox is: suppose I say "this statement is a lie."  Is that statement true or false?  If it is true then it must be a lie, so must be false.  If it is false, then it is not a lie, so must be true.  Writing a complicated artificial intelligence (or relying on a really smart person) won't make the question about whether I lied or not any more meaningful.


How can Chomsky hierarchy be applied to languages with alternated letters?

Every regular grammar produces a regular language.
But:
Not every grammar for a regular language is regular.
In other words, a regular language can be described by any of an infinitude of grammars, some of which are regular and some not.
In this case, you can easily create either a left- or a right-regular grammar for your language. For example:
\begin{array}{l}
\mathrm{S} \rightarrow \mathrm{X} \mid \mathrm{Y} \\
\mathrm{X} \rightarrow  \mathrm{X}  \mathrm{a}\mathrm{b} \mid \mathrm{ab} \\
\mathrm{Y} \rightarrow \mathrm{Y}   \mathrm{b}  \mathrm{a} \mid \mathrm{ba}
\end{array}
Of course, that transformation only preserves the language parsed, not the induced parse trees.


Why do you have to worry about cache coherence if you are using shared memory?

If two different processors share one memory, each having individual cache, they can end up having two different values in the same address.

Imagine each of two processors has private caches L1 and L2. The cache L3 is shared between both processors. Assume the processor A reads data from address X in L3 to L1 and the processor B reads the same data from the same address (address X in L3) to it's private cache L1. Then, if the processor A modifies the value and does a write-back, the processor B can't figure it out without the support of coherence protocol and would still have an old value in it's own cache.

Basically, you are right. The cache coherence protocol is a mechanism to notify processors about shared memory modification caused by other processors.

The main advantage of the shared memory architecture for a programmer is that there is no need  to explicitly describe communication and interaction between processors (like you would do using MPI, for instance). The coherence and consistency of the memory is fully the responsibility of the hardware.


Would you ever use a skip list over a treap?

here is an extensive 13 page analysis of considerations in this area including empirical analysis. coders sometimes ask for "one size fits all" answers. of course "best" implementation depends on the actual "forces" applied on the implementation. a single implementation may even behave ("dramatically") differently on different amounts of data and different conditions. for some data structures there is no significant difference and either can be acceptable.

raw performance is not the only factor. factors might involve how hard it is to implement/ test the structure vs whether it is already implemented etc. and this paper also considers caching considerations effect on performance. this research finds that skip lists have good variable-node-size performance (ie not all nodes have same size) and paged skip lists outperforms B+-trees in their case.

see p7 and fig6 p 10.

  The AVL tree is the best
  performing fixed-node-size data structure, and
  the paged skip list is the best performing
  variable-node-size data structure. Moreover, the
  gap between the cache-conscious data structures
  and their counterparts is growing, as shown by
  the 100 cycle memory latency configuration.
  The paged skip list outperforms the sequential search
  B+-tree by 12% on the Intel processor.

T-treap and Cache Performance of Indexing Data Structures /
Joshua P. MacDonald and Ben Y. Zhao


See https://en.wikipedia.org/wiki/Blockchain_(database)#Decentralization, which states that "Every node in a decentralized system has a copy of the blockchain. This avoids the need to have a centralized database managed by a trusted third party."

This is as true of 10 computers as it is of one.  It's not about redundancy from this perspective, though that is certainly a motivating factor.  It's about having zero centralized authorities,  and the only way to do that is to allow everyone to have a copy of the blockchain.


For regular languages A and B, determine whether B might match early in (A B)

If I translate your description properly, here is what you want to ask:

  Given two regular language $A$, $B$, is there a prefix of a word $b$ in $B$ that is a suffix of a word in $A$ so that the rest of $b$ is a prefix of another word in $B$?

Formally:

  Given regular $A$ and $B$, are there $a = wx \in A$ and $b = yz \in B$ so that $xy \in B$?

Deciding this boils down to deciding whether

$\qquad B \cap (\operatorname{suff}(A) \cdot \operatorname{pref}(B) ) = \emptyset$.

Now we employ some closure properties: $\mathrm{REG}$ is closed against right and left quotient, concatenation and intersection, so with

$\qquad \operatorname{suff}(A) = A \backslash \Sigma^*$ and
$\operatorname{pref}(B) = B / \Sigma^*$

the set we want to check for emptiness is regular, and therefore the check is indeed decidable.

In order to actually do this, I suggest you build automata for $\operatorname{suff}(A)$ and $\operatorname{pref}(B)$, concatenate them, intersect the result with the automaton for $B$ and use the standard check for emptiness (is a final state reachable from the initial state?).

Note that you never need DFA, all of this works nicely with NFA. Therefore, no exponential state explosion occurs; intersection multiplies the state numbers, though.


The formula for shifting is i - spi + 1 if you start indexing from 0 and i - spi if you start indexing from 1.


Finding shortest and longest paths between two vertices in a DAG

For the shortest path problem, if we do not care about weights, then breadth first search is a surefire way.  Otherwise Dijkstra's algorithm works as long as there are no negative edges.

For longest path, you could always do Bellman-Ford on the graph with all edge weights negated. Recall that Bellman-Ford works as long as there are no negative weight cycles, and therefore works with any weights on a DAG.


How to show that the set of machines which accept languages in $\mathrm{NP}\smallsetminus\mathrm P$, is decidable only if $\mathrm P=\mathrm{NP}$?

There are two cases to consider.

Assume that $\text{P=NP}$. Then $L=\{\langle M\rangle \mid L(M)\in \emptyset\}=\emptyset$. The empty language is decidable; as no word belongs to it, it is trivial to decide whether a word belongs to it or not.
Assume that $\text{P}\neq\text{NP}$. Now your result follows directly from Rice's theorem.


Why does binary search take $O(\log n)$ time?

This is only possible in data structures which allow random access like arrays and vectors.

So if you already know that you have to access the last car , then you can do it in O(1) time.
Data structures like linked lists won't allow you to perform a binary search in O(logn)

The example you have mentioned is similar to using binary search on a linked list. So it will need O(n) time as you will need to traverse all the nodes to reach the last node in the worst case.

So your argument that you cannot reach the middle car in no time is valid in your example but not in data structures which offer such properties.


Maximum possible file size in the filesystem

You may find the answers here and here

I should have posted this as comment but I don't have enough reputation points.


Universal hash function for strings of unbounded length

Any such hash function must have an infinite key.
Suppose that your hash function maps binary strings to some alphabet $\Sigma$ of size $m > 1$. We can identify binary strings with natural numbers, and so can think of the hash function as a function $h\colon K \times \mathbb{N} \to \Sigma$, where $K$ is the (finite) set of keys.
For each $n \in \mathbb{N}$, we can look at the function $h_n\colon K \to \Sigma$ given by $h_n(k) = h(k,n)$. There are finitely many possible functions $h_n$ (at most $m^{|K|}$), and so there must exist $n_1 < n_2$ such that $h_{n_1} = h_{n_2}$. In particular, $\Pr_k[h(k,n_1) = h(k,n_2)] = 1$, and so $h$ is not even a weakly universal function.


What to expect in a Computer Science and Mathematics course?

Firstly, from maths point of view, what are the prerequisites and what subjects do I get in the first 2 years? I understood that Linear Algebra and Discrete mathematics are very important! So can you name an example of a maths textbook I may get?

You want to select a textbook that "meets you where you're at" in terms of "mathematical maturity."  Selecting too basic of a textbook will bore you, but selecting one that is too advanced will allow you to progress only at a suboptimal rate.
If you don't already know stuff that's in a typical discrete math course, I would suggest looking at this thread on Math.SE.  My first Discrete Math course used Epp's book, but I found it somewhat basic.
If you already know some of what is covered in a typical discrete math course (e.g. elementary set theory, basic methods of proof, etc.--the stuff that would be covered in AoPS coursework), then I would highly recommend Graham, Knuth, and Patashnik's Concrete Mathematics.  It is literally the book on math with respect to computer science theory.  (If you learn everything in that book, I'd nearly guarantee you would know more math than 70-80% of CS students.)
However, graph theory and linear algebra are not covered in GKP's book.  For linear algebra, I don't really know of a "great" textbook.  For Graph Theory, I'd recommend looking at an algorithms textbook (CLRS's Introduction to Algorithms is really good), and perhaps going through this Coursera class and it's sequel.  I learned so much in that course.
Also, take a look at Project Euler; it gives some fun math-based challenges that build quite nicely on each other.  By solving those problems, I self-taught a ton of math from a very wide/eclectic basis.

Secondly, from a CS point of view, I already 'know' C#, F# and sometimes I play around with JS. Is it obligatory to learn ANOTHER language like python, java or c++? since knowing C# and F# already fulfils the 'need' of knowing different languages, F# with it's elegant functional-first programming paradigm and C# for imperative-first programming (technically, both F# and C# are multi-paradigm, which is awesome!)
To be more specific, I am into computer vision and ML. what textbooks do you think I may get in this area?

You'll probably be required to learn one of Java, C++, or Python depending on your school--most schools have a "favorite language" that they use by default in most of their classes.  This "favorite language" is typically one of those three.  (For example, University of Virginia uses Java as the language they assume all CS students know.)  If you're really into computer vision, you'll probably want to learn C++; it's speed is important in that field, or so I've heard.
I wouldn't worry too much about learning other languages; having a foundation in a procedural and a functional language is great, and if you're comfortable with OOP, you'll be fine.  When it comes time to use another language, you'll be able to pick it up really quickly with your background.


$\lambda x. \lambda x.x$ vs $\lambda y. \lambda x.x$

You have basically discovered the Barendregt convention.

Yes, it's silly to write terms such as $\lambda x. \lambda x. x$ when $\lambda y. \lambda x. x$ is $\alpha$-equivalent and clearer.

We could forbid the former form the syntax of the lambda calculus. This however would force us to check $x$ does not occur bound in $M$ every time we craft (introduce) the term $\lambda x. M$.

The Barandregt convention goes further. It stipulates that, when building (introducing) a term $\lambda x. M$ we are always allowed to do that. However, when destructuring (eliminating) a term $\lambda x. M$ we can assume that $x$ was $\alpha$-converted so no to cope with other bound names in $M$, nor with other names that we could have around elsewhere at the moment: e.g., if we are writing a proof involving terms $N$ and $O$, the convention stipulates that $x$ does not occur in $N,O$ as well.

The convention is just a convenient shortcut, made for lazy humans which do not want to spend their time and energy to fix trivialities. Basically, we pretend that $\lambda x.\lambda x. M$ is allowed when it's convenient to do so (introduction), yet we pretend that the same is no longer allowed when convenient to do so (elimination).  It feels a bit like cheating, but one could (in theory) always fix the proof to be perfectly sound.


Example of a non-regular language that is a subset of a regular language?

Every language over an alphabet $\Sigma$ is, by definition, a subset of $\Sigma^*$, which is regular. If you want a less trivial example,

$$\{a^nb^n\mid n\geq 0\}\subseteq L(a^*b^*)\,.$$


Is this program O(n^2logn) or O(nlog^2(n))?

The complexity is $O(n^2)$. The reason is that the two inner loops take $O(n)$ time. The first iteration takes $i$ operations, then $i/2$, then $i/4$ until it's 0. So we need to compute the sum of $i+i/2+i/4+...+1$ operations which its upper bounded to $2i$. Finally because your outer loop is clearly $O(n)$ the total complexity is $O(n^2)$.


What does Sigma notation mean, in the context of computability of functions?

Section 2.1 of that paper defines such computability for sets of natural numbers, and Section 2.3 of that paper then extends the notion to real-valued functions.


Regular expression for language with even number of 0's and 1's

Constructing regular expressions is usually more complicated than programming finite state automata. The standard way would be to construct a FSA and translate that one into a regular expression using standard techniques.

But if you prefer, it can be done directly, in two steps. Start by making two regular expressions $\alpha$ and $\beta$.

First $\alpha$ specifies strings with even number of $1$'s, and exactly two
$0$'s, one of which is the last symbol of the string.
Similarly $\beta$ specifies strings with odd number of $1$'s, and exactly two $0$'s,
one of which is the last symbol of the string.

Then build an expression for strings that have an even number of $0$ ánd an even number of $1$'s based on  $\alpha$ and $\beta$.


Closed-Form Expression for Recursive Function


FFT for expanded form of equation multiplication

The trivial algorithm that multiplies every monomial in $A$ by every monomial in $B$ takes time $O(|A| \cdot |B|)$ (where $|A|$ is the number of monomials in $A$ or $\deg A + 1$, depending on the representation), which is the same order of magnitude as the size of the output, and so optimal. You only need FFT if you want to actually compute the product $AB$. In particular, there is no way to compute your function in time $O(n\log n)$, simply because the length of the output is $\Omega(n^2)$.


Proving NP hardness about graph creation

If you are given just the degree sequence (the number of neighbors of each vertex), then the Havel–Hakimi algorithm is an efficient algorithm that constructs a graph conforming to the degree sequence, if possible, and alerts you otherwise. If you are given the second-order degree sequence (the number of vertices at distance 1 and at distance 2 from each vertex), then the problem of determining whether such a graph exists becomes NP-complete, as shown by Erdős and Miklós in their paper Not all simple looking degree sequence problems are
easy.


Is Bresenham's Line Drawing algorithm still used today?

Google Scholar reports hundreds of mentions since 2012.

Specifically, the patents

System and method of optical reading employing virtual scan lines (US 20100308114 A1, 2010),
System and method for data reading using raster scanning (US 8286877 B2, 2012) and
Compensated virtual scan lines (US 8335341 B2, 2012)

explicitly mention the algorithm, if only in exemplary fashion.

Further searches, e.g. on YouTube, suggest persisting interest in the algorithm; it still seems to be in the mainstream.

That does, of course, not mean that there are no better ones, or that professional products use it still. But since proprietary devices are usually closed-source, we won't be able to answer that question with confidence.


Follow the definition of $\leq_p$.

You have to find a function $f$ (define it!), computable in polynomial time (prove this!) such that

$$
\begin{array}{l}
\forall x.\  x\in A \implies f(x)\in B
\\
\forall x.\ x\notin A \implies f(x)\notin B
\end{array}
$$
(two more proofs!)

More intuitively, $f$ converts instances of $A$ (i.e. $x$) into instances for $B$ ($f(x)$), and must map $A$ inside $B$, and the complement of $A$ inside the complement of $B$. Very, very roughly, it describes how to solve $A$ exploiting $B$.

Finally, never write nonsense formulas like $A \implies B$ since sets do not imply other sets. Try to be as formal as you can, at least when you have not yet mastered the definition.


How to find the symmetry group of a polynomial

There is a reduction from your problem to graph isomorphism, as explained in this question on Math Overflow.  In particular, that answer shows how to obtain a random automorphism of the polynomial, i.e., a random permutation in the symmetric group.  For example, you can start by randomly picking a pair of variables $x_i,x_j$ and testing whether there exists an automorphism that sends $x_i \mapsto x_j$; if so, you can search to find another variable $x_k$ such that there exists an automorphism that sends $x_i \mapsto x_j$ and $x_j \mapsto x_k$; and so on until you obtain a complete permutation.

To obtain a set of generators for the symmetry group, you can repeat this search many times to obtain multiple random permutations known to be in the symmetry group; if you repeat enough times, with high probability, the resulting set will generate the entire symmetry group.  Or, you can systematically enumerate the space of all permutations that are in the symmetry group; if the symmetry group is small enough, this will be efficient.

This requires us to have an oracle for solving graph isomorphism.  Fortunately, there are existing graph isomorphism solvers that can solve typical instances of graph isomorphism very rapidly.  For instance, you can take a look at nauty, a graph isomorphism solver that typically finishes within seconds on graphs with at most 100 vertices or so.  The question on Math Overflow describes how to reduce the problem to isomorphism of colored hypergraphs; the nauty manual describes how you can convert this to an ordinary graph isomorphism problem, at the cost of some small increase in the size of the graph.

If you put all of this together, I expect it will be possible to construct an algorithm for your problem that is pretty efficient in practice, for polynomials of the size you describe.


How does a computer interpret real numbers?

They represent continuous quantities with discrete approximations.  Mostly, this is done with floating point, which is analogous to scientific notation.  Essentially, they work with something like $1.xyz\times 10^k$, with some appropriate number of decimal places (and in binary, rather than decimal).

It's also possible to work with some irrational numbers directly.  For example, you could create yourself an object called "$\sqrt{2}$" without particularly worrying about what it is, except that it obeys the usual arithmetic rules and that $(\sqrt{2})^2=2$.  So then you could compute $$(\sqrt{2}-1)(\sqrt{2}+1) = (\sqrt{2})^2 + \sqrt{2} - \sqrt{2} - 1 = 2 - 1 = 1$$
exactly, as an algebraic fact that's not susceptible to rounding errors.

Note that, if you're plotting a graph on screen, regardless of how far you zoom in, you're plotting it as discrete pixels so using an appropriate number of significant figures basically gets you everything you need.


How to find i largest numbers in unsorted array in O(n) where i <= n^(1/2)

Use a selection algorithm to find the $i$th largest number.  This can be done in linear time.  Then, do a second scan over the array to find all numbers larger than the $i$th largest number.  (With many selection algorithms, this last step is unnecessary, as they partition the array into elements smaller than the $i$th largest and larger than the $i$th largest.)


Use of sorting in counterexamples for equations

You want to find solutions to $u^6 + v^6 + w^6 = z^6 - x^6 - y^6$. Obviously any solution would also have to be a solution modulo k, for every k. So the idea is to find the set of all possible values of $u^6 + v^6 + w^6$ modulo W, and the set of all possible values of $z^6 - x^6 - y^6$, and you need to find the elements that are common to both sets.

Question: What is the easiest way to check which elements two sets have in common? Answer: Sort the elements, that makes the search very easy.

The further steps: If you are lucky then both sets had few elements in common. So you can deduce values of u, v, w, x, y, z modulo W or modulo some other value. Which means you have reduced the search space. If there was a good amount of reduction, try different values instead of W. And at some point you start with an exhaustive search, but with fewer values needing to be searched.


How to construct a NFA that the third symbol and the third from last symbol are same?

Hint:

Here is a NFA that accepts exactly those strings whose first and last character are both $a$:

Can you modify and extend this to become a solution to your problem?


Pick a random number in a pool with duplicates in O(1) time and less than O(n) space?

Why is $1$ returned with probability $33\% < \frac{1}{3}$ and not with probability $\frac{30}{30+90} = \frac{1}{4}$?

Anyway, this can be done in $O(NU)$ space (assuming $i_1, \dots, i_{NU}$ each fit in $O(1)$ memory words) and $O(1)$ time (assuming you can sample an integer between $1$ and $\sum_{j=1}^{NU} i_j$ uniformly at random in $O(1)$ time) using the alias method.

The Wikipedia page includes a pseudocode that uses rational numbers (which might lead to a loss of precision, depending on their representation). If you are interested in a C++ implementation that uses integers, like in your description, see here.


Proof of universality in the circuit model

I'm sure you are aware of the following problem: Turing-Machines can't compute any Boolean function. E.g. there is no such TM that prints $0$ if the input TM does not halt and $1$ if it halts (halting problem). This directly implies that TMs can't approximate any classical continuous function arbitrarily well. E.g. you could create the number
$$\xi = \sum_{i = 0}^\infty 2^{-i} h_i$$
where $h_i$ is $1$ if the $i$-th TM halts and $0$ if it doesn't for some mapping of $\mathbb{N}$ to the TMs. It's clear that $\xi \in \mathbb{R}$ and that you could work with the function $f(x) = \xi x^2 +\xi^2$ in analysis and differentiate it without a problem, but it's not computable, you can't approximate it's value arbitrarily well. One interesting field of study it computable analysis which deals with deals with a special kind of analysis where only functions and numbers are considered that are computable (arbitrarily closely approximatable  by a TM).
Now let us take a look at circuits. It's true that you can for a given table of inputs and outputs of a Boolean function construct a circuit that computes that table. The problem is that the table is sometimes not computable in the first place. E.g.
you could say that the circuit $C_n$ taken a binary representation of a TM up to length $n$ as input an outputs $0$ if it doesn't halt on the emtpy tape and $1$ if it halts. Now all circuits in the sequence $C_1, C_2, ...$ do exist in the sense that they are in the set of all possible circuits, but you can not build them, because of the halting problem. (It is very similar to $\xi$ it exists but you can not compute it). This also applies to your continuous functions. E.g. lets look at the function $f(n) = \xi$ (which is a normal real continues function). You could now define that $C_{n,k}$ is a circuit that takes $k$ as a binary number ($k < 2^i$) as input and computes $f(n)$ up to a precision of $2^{-k}$ that is $k$ places after the comma in binary. Now there are circuits $C_{1,1} C_{2,1}, ...$ that exist, because the mappings are all binary and if you had the Boolean tables for any particular $n,k$ you could build a circuit, but you can't compute the Boolean tables..., I hope you get a feel for the problem with computability and that there exists things, which you can define and use, but not construct. To answer your question, yes you can approximate continues functions with circuit sequences arbitrarily well, but that does not mean that there is an algorithm to find such circuits...
Anyhow I would recommend you to look into computable analysis. It seems to be what you are searching for.


2-tape TM that accepts words from $L := \{bin(n)$#$w \in \Sigma^* | n \in \mathbb N \land w \in \{0,1\}^* \land |w| \le n\}$ in $O(n)$

Think over how to convert binary representation of $n$ into unary one using two tapes. The result should be stored on the second tape. For example, if $n=6$ then the unary representation could be $111111$. Then compare number of symbols of $w$ and number of $1$s of the unary representation of $n$. If the number of $1$s is less than or equal to $|w|$ then accept, otherwise reject.

Since number of bits in $bin(n)$ is no more than $log(n)$ number of unary bits is no more than $2^{log(n)} = n$, so writing down each bit on the tape should not take more than $O(n)$ time, and comparison $w$ with the unary $1$s also takes $O(n)$.

So you just need to design and algorithm for conversion from binary to unary representation of $bin(n)$ using two tapes that runs in $O(n)$ time.


In RSA, must $p$ and $q$ have the same number of bits?

The RSA method works regardless of the size of the individual primes $p,q$. The reason that we would want $p$ and $q$ to be of roughly equal size is that one method of breaking RSA is factoring $n = pq$, and the running time of some factoring methods (notably ECM, the elliptic curve method) depends on the size of the smallest prime factor of $n$. Therefore to get the most "bang for the buck", you would like $p,q$ to be both as large as possible under the constraint on the size of $n$ (which determines the speed of encryption and decryption), and so of roughly equal size.


How to revert a carryless polynomial multiplication?

Yes, there are efficient algorithms for this.  All you need to do is factor the resulting polynomial, but taking all coefficients modulo 2.  This is known as polynomial factorization in the field $GF(2)$.  There are standard algorithms for polynomial factorization, and they are quite efficient.  For instance, you could look at Sage or another mathematical computation toolkit; it's likely to have an existing implementation of those algorithms.

Note that after you've factored the polynomial, there may still be some ambiguity about what the original two polynomials were.  For instance, if you are given the polynomial $x^5+x^3$, the two polynomials might be $x^2+1$ and $x^3$, or they might be $x^3+x$ and $x^2$, etc.  You won't be able to tell, given just the product.


Given set of grammar rules, how to find if they correspond to Context-free or unrestricted

It is undecidable to determine whether the language generated by a given grammar has a context-free grammar.

However, if you are simply asking whether a grammar itself is context-free, look no further than the left hand side of each production. A grammar is context free iff the left hand side of each production is a single non-terminal.


When we are in AC mode every rtt(round trip time) the congestion window increase by 1(MSS).
Here our current congestion window(cw) is 60 and we know that during transmission round t we get 3 duplicate acks-so our window is now 30MSS,now we also know that from t to t+1 for instance our window increase by 1,so from t to t+10 our window increases by 10-which means our window is now 40.
We know that during the t+10 round we will get 3 duplicate acks,so now our window will become 40/2=20.
From round t+10 to t+20 our cw increase by 10 more-so now its 30,and in addition we know we will get 3 duplicate acks-which means now our window will be 30/2=15MSS


How does the Weibull distribution work as fault model in wireless sensor networks?

Step 1: Fit a Weibull distribution to all transmitter circuit faults (with one set of parameters).  Fit a Weibull to battery condition faults (with another set of parameters).  You get five different Weibull distributions.

Step 2: During simulation, randomly draw one number from each of the Weibull distributions.  This gives you the time until the first transmitter circuit fault, the time until the first battery condition fault, and so on.  Pick the smallest number; that's the fault that occurs first.  Simulate a fault of that type, at that time.  (You can continue the simulation to simulate multiple faults if you want.)


RDT2.1 - does the Sender listener to "ack" even though state=ready?

From the code above, Yes.

Regarding your second note. A sender will go to the busy state if it sends a message and there it will wait for an ACK. I can imagine that the reciver would send multiple ACK's only if there is some fault. Usually, such faults are not considered in the basic protocol description, but are considered in the actual implementation.


What is the deterministic finitite automaton (DFA) for the regex ".*b."

Every language described by a regular expression has a DFA – this is Kleene's theorem (not to be confused with Kleene's recursion theorems, which are something completely different).  Standard algorithms to translate from regular expressions to automata give nondeterministic automata (NFAs), such as the one you found on the web.  There are standard algorithms to determinize NFAs but they make the state space exponentially larger.

In this case, though, it's straightforward to produce a DFA by thinking about the language you're interested in. The language is all strings whose second-to-last character is $b$. So your automaton needs to accept if it gets to the end of the string and the previous character it saw was a $b$.  I don't have any drawing software to hand but the following textual description is, I think, more useful.  You need four states, corresponding to the combinations of "the character I just read was/was not $b$" and "the character before that was/was not $b$". You start in (not $b$, not $b$), since you haven't read any $b$s before you've read any characters.  The transition function and so on should be pretty obvious.


This equation expresses a confidentiality property. There are two ways of looking at it: what does it permit and what does it prevent.

Prevented: writing secure information to an insecure place.
Permitted: writing insecure information to a secure place.

Clearly, the former is good, otherwise, for example, your PIN number (secure) could become accessible to untrusted third parties.

From a security perspective, the former is safe, because no secure information is leaked. It allows cases such as where you report your daily activities (insecure) to your manager (trusted).

One concern you may have is that writing insecure information to a secure place could lead to problems. These problems would be related to integrity. An integrity violation occurs when bad data from an untrusted source is written into a secure variable. If the data isn't checked for validity, it could mess up programs running securely.


Complexity of space density and sequentiality

There are a few models that take into account the number of memory transfers an algorithm makes. One of the most successful ones is the cache-ideal model introduced by Frigo et al, Cache-oblivious algorithms, 1999. It is based on the external memory model introduced by Aggarwal and Vitter, The Input/Output Complexity of Sorting and Related Problems, 1988. The notes by Demaine give a nice, readable overview of the model and of some of the algorithms and data structures out there. Alternatively, check out the chapter on cache-oblivious data structures in the Handbook of Data Structures and Applications. If you prefer videos, Demaine covers all the basics and perhaps even more on the MIT Introduction to Algorithms lectures.

The model assumes no knowledge of the number of levels in the memory hierarchy. In addition, there are no parameters such as cache-line length or cache size to configure. One property is that if an algorithm performs optimally in the cache-ideal model, it performs optimally on any $k$-level memory hierarchy. Furthermore, algorithms that do perform optimally in the model are called cache-oblivious. They offer the advantages of simplicity, robustness and portability over the cache-aware algorithms, whose resource usage must be managed explicitly.

The ideal-cache model has two complexity measures. The first one is work complexity, that is the conventional running time of an algorithm in the RAM model. The second one comes from the external memory model, that is the number of memory transfers. The ideal-cache model however modifies the external memory model in a few ways. It has a optimal block replacement strategy, automatic replacement and full associativity. All of these assumptions are justified by a collection of reduction by Frigo et al.

Algorithms and data structures are then analyzed in the model. For example, consider the classic binary search. The runtime leads to a recurrence

$$T(N) = T(N/2) + O(1).$$

Looking at the recursion tree, each level attributes an $\log N$ factor yielding the solution of $\Theta(\log N)$. When analyzing algorithms in the RAM model, we often assume the base case of $T(1)=O(1)$ for our recurrences. However, in the cache-ideal model we often let the algorithm divide the problem all the way, but consider the point at which the problem either fits the cache or fits in $O(B)$ number of memory blocks. In fact here, we can we can improve on our analysis by using a stronger base case of $T(O(B))=O(1)$. With this, the classic binary search incurs $\Theta(\log N - \log B)$ memory transfers. What is more, the classic binary search is not optimal the in cache-ideal model. There are more clever ways needed to achieve the optimal $\Theta(\log_B N)$ bound.

I guess the success of the model comes from the fact that it is easy and fun to work with, and it also works in practice, meaning it has been fairly effective at predicting the costs of an algorithm on real systems. There are a lot of cache-oblivious algorithms and data structures. For example, we have cache-oblivious algorithms for many problems in computational geometry, scanning of dynamic sets, bioinformatics, stencil computations, linear algebra, suffix array construction and for some fundamental graph problems using cache-oblivious priority queues. The main techniques that are effective are linear scanning of memory and divide-and-conquer.

In practice, the overall conclusion has been such that cache-oblivious algorithms often outperform RAM algorithms. However, the cache-aware algorithms are usually even faster, since they are tuned for a specific problem size and memory hierarchy. For a nice example see Ladner et al., A Comparison of Cache Aware and Cache Oblivious Static Search Trees Using Program Instrumentation, 2002.


Sorting tuples with respect to multiple criteria

Multivariate optimisation (a subproblem of sorting) is usually hard, even offline, because there are no longer "optima" but you have to deal with several Pareto-optimal elements.

Luckily, you have specified that such ties should be broken by strict priorities. In that case, lexicographic sorting (w.r.t. your criteria and in order of the priorities) solves the problem.


Minimum unweighted anticlique (independent set) cover / partition

This is precisely the graph coloring problem. Each subset of $C$ is a color, and we are trying to prevent adjacent vertices from having the same color, while minimizing the number of colors used. According to these lecture notes there is a polynomial-time greedy algorithm for coloring interval graphs based on the fact that every interval graph has a perfect elimination ordering.


How to identify labels in unsupervised learning?

You can't, in a completely unsupervised setting.  You need something more: e.g., a training data set where you have labels for at least some of the instances, or some other information that allows you to set a label for each cluster.

How is the computer supposed to know that a circle means zero as opposed to some other number, if you don't tell it that?  Obviously, it can't.  In fact, in the Eastern Arabic numbering system, there's a zero-looking character that actually means the number 5, not the number 0.  Obviously, a computer can't possibly know which of those two meanings is intended, if you don't tell it somehow.


For these 2-word sentences, notice that the original equation for the MLE approximation of the probabilities of the bigram is:
$$P(w_i|w_{i-1}) = \frac{C(w_{i-1}w_i)}{\sum_w{C(w_{i-1}w)}} = \frac{C(w_{i-1}w_i)}{C(w_{i-1})}, $$
where the denominator $C(w_{i-1})$ only equals the count of $w_{i-1}$ iff there is an end-symbol $\text{</s>}$, otherwise the number of times $w_{i-1}$ appears at the end of the sentence has to be subtracted from its count. Therefore, the "count" function you are using in the denominator is wrong, and the true probabilities in your particular corpus are:
$$\begin{equation}
\begin{split}
P(a|a) &= \frac{C(aa)}{C(a)} &= \frac{1}{2} \\
P(b|a) &= \frac{C(ab)}{C(a)} &= \frac{1}{2} \\
P(a|b) &= \frac{C(ba)}{C(b)} &= \frac{1}{2} \\
P(b|b) &= \frac{C(bb)}{C(b)} &= \frac{1}{2} \\
P(a|\text{<s>}) &= \frac{C(\text{<s>}a)}{C(\text{<s>})} = \frac{2}{4} &= \frac{1}{2} \\
P(b|\text{<s>}) &= \frac{C(\text{<s>}b)}{C(\text{<s>})} = \frac{2}{4} &= \frac{1}{2} \\
\end{split}
\end{equation}$$
and now the sum of the probabilities of all possible 2-word sentences with this vocabulary becomes equal to 1:
$$\sum_{w, v\in\{a, b\}^2}P(\text{<s>}wv) = \sum_{w, v\in\{a, b\}^2} P(w|\text{<s>})\cdot P(v|w) = \sum_{w, v\in\{a, b\}^2} \frac{1}{4} = 1 .$$


Can we create binomial heaps in linear time?

Wikipedia claims that insertion takes $O(1)$ amortized time, and so converting an array of numbers into a binomial heap should indeed take time $O(n)$. This is also supported by these lecture notes, and probably mentioned in CLRS.


Series where each term is square of previous

As you say, the fine on day $n$ is $2^{2^n-1}$. To reach $D$, you need to solve the equation $2^{2^n-1}=D$, taking $\log$ we have $2^n-1=\log D$, rearranging and taking $\log$ again we get $n=\log(\log D+1)$.

If you want the answers in Big-O notation, you have $2^{2^n-1} =O(2^{2^n})$, and for the second part, $n=O(\log\log D)$.


In this case + stands for the OR-operation. So the automaton is indifferent using an $a$ transition or a $b$ transition.

It's sufficient to construct an automaton with one state which is initial and final state and having one transition labeled with a, b.


Why are the control statements[if-else, while, for] commonly used in programming?

From computability theory, we know that a programming language which only contains terminating programs (say, without loops and recursion) is strictly less powerful than a Turing machine (or any other Turing-complete programming languages).

So, if we want a programming language $P$ which is able to express, say, a Python interpreter, a JVM implementation, or even an interpreter for $P$ itself, we need a language having some sort of unbounded loop / recursion.

Technically, if we have a while loop, we no longer need if, since

if condition then cTrue else cFalse

is equivalent to

branchTaken = false
while condition and !branchTaken do
   cTrue
   branchTaken = true
while !condition and !branchTaken do
   cFalse
   branchTaken = true

where branchTaken is an otherwise unused boolean variable.
But this is terribly inconvenient to use in practice!
So, programming languages tend to include if, even if not strictly needed.

Now, about while (ans similar unbounded loops). We said that we need some construct for unbounded looping/recursion. Why while, then?

Well, recursion alone suffices, but it is not very convenient in imperative programming. Note that, by contrast, functional programming languages typically do not have any while loop, and only exploit recursion -- in functional programming, recursion is far more natural and convenient, especially if the language is pure (without side effects) and a WHILE loop would be pointless, since we can not mutate variables.

Most widespread imperative programming languages use while or similar loops. In principle, they could instead use if+goto, which have the same power. However, practice showed that goto often led to code which was very hard to read and modify. Dijkstra wrote his famous letter "GOTO considered harmful", advocating for using structured programming (while and friends) instead. One of the scientific motivations behind this, is that to properly reason about a while loop we need to think about a loop invariant. This is already quite hard, in general. In a goto-using program, we need an invariant for every label/line number which is being targeted by some goto. This is much harder, in general, since many gotos may point to the same label, so the invariant must take into account the multiple "incoming" points. A solution for this could be using goto in a more disciplined way, but if we do, we'll probably end up in using while (or another loop) under a different notation.


Why are regular tree languages closed under intersection, but deterministic context free languages are not closed under intersection?

The intuition is that the strings of a context-free language are formed by the "frontier" (the leaves) of the derivation trees. The trees themselves are no longer directly visible.
Thus, the intersection of two tree languages consists of the trees the structure of which belongs to two tree grammars. We must be able to map productions of both grammars onto the same tree. Moreover, the tree is visible, we do not have to guess it.
For the intersection of two context-free languages we need two trees, one for each grammar and we only need the two frontiers to be the same. Hence we can find languages like $\{a^nb^nc^n \mid n\ge 1\}$ which is the intersection of two context-free grammars. The first one has a tree structure that verifies that the $a$'s and $b$'s are equal, while the second grammar checks the $b$'s and $c$'s with another tree structure. Also we need to 'guess' the two trees as we only 'see' their frontiers.
I do not think that determinism is essential in this discussion.


How to write a DFA where the second digit is equal to the last digit of binary strings?

You are on the right track.

When constructing a DFA, you have to consider what information you need to store to decide in the end whether the string is accepted or not. The information you need is indeed: the second symbol of the string and the symbol which was read last. So you need four states to store all combinations of these two flags, and the accepting states are the ones where the second symbol and the last symbol are equal. The only thing you still need to do, is glue these states together.

First, there is a third kind of information: the length of the string. If you have read less than two symbols, you are not in one of four states mentioned earlier. So there are six states:

A: no symbols have been read (this is the initial state)
B: one symbol has been read
C: at least two symbols have been read, the second symbol is a 0 and the last a 0
   (this is an accepting state)
D: at least two symbols have been read, the second symbol is a 1 and the last a 0
E: at least two symbols have been read, the second symbol is a 0 and the last a 1
F: at least two symbols have been read, the second symbol is a 1 and the last a 1
   (this is a in accepting state)

To finish the automaton, you have to consider what happens to the state if you read in a 0 or a 1. This will then give you the transition function.


Prove NP-completeness of deciding satisfiability of monotone boolean formula

The "parent" of the problem you're looking at is sometimes called Weighted Satisfiability (WSAT, particularly in parameterized complexity) or Min-Ones (though this is normally an optimization version, but near enough). These problems have the "at most $k$ variables set to true" restriction as their defining feature.

The restriction to monotone formulae is actually surprisingly easy to show hardness for, you just need to thing outside satisfiability problems for a moment. Instead of trying to modify a SAT instance, we instead start with Dominating Set (DS).

See if you can get it from there. More is in the spoilers, broken into bits, but avoid them if you can. I won't show membership in NP, you should have no problem with that.

   Given an instance $(G, k)$ of DS (i.e. we want a dominating set of size at most $k$ for $G$), we can construct an instance $(\phi,k)$ of WSAT where the formula $\phi$ is a monotone CNF formula:

The basic construction:

   For each $v\in V(G)$ we have a variable $v' \in \text{var}(\phi)$, for each $v \in V(G)$ we have a clause $c_{v} = \bigvee_{u\in N(v)} u'$.

A sketch of the proof:

  Each vertex either has to be in the dominating set, or have a neighbour that is, so if we can find $k$ vertices that form a dominating set, the corresponding $k$ variables can be set to true in $\phi$, and each clause must contain at least one of them. Similarly if there is a weight $k$ satisfying assignment, the true variables correspond to the vertices we place in the dominating set - every clause $c_{v}$ must have at least one, so each $v$ is dominated (by itself or otherwise).


Dynamic programming: Maximize total value

For $k \in [\![1, n]\!]$, you can define $f(k)$ as the maximum value reachable using objects $1$, $2$, …, $k$, without two consecutives objects.
Now the key to the dynamic programming implementation is to see that:
$\forall k \in [\![3, n]\!], f(k) = \max(f(k-1), f(k-2) + V[k])$
The reason is that to compute $f(k)$, you can either keep the $k$-th object or not. If you keep it, then you cannot keep the $k-1$-th object.
Finally, you want to compute $f(n)$.


Number of literals in the given boolean expression

Does your material use the (strange) convention of notating $\neg A$ as $A'$?

If so, there are 6 literals (5 without the LHS). If $A'$ is distinct from $A$, there are 9 (8 without LHS) and the solution book is wrong.


Cannibals missionaries problem - solving usings graphs

You did most of the job. Each vertex is a state $(M, K, B)$ and edges represent the possibility to pass from a state to another with one ship transport. Let say $B$ can take the values $L$ or $R$ for left and right edges respectively. $K$ is the number of cannibals on left edge and $B$, the number of monks on left edge. Initially all monks and cannibals are on left edge with the boat: state is $(M_0, K_0, L)$. Note that for any state there are $M_0-M$ monks and $K_0-K$ cannibals on right edge.
You can notice that any ship transport would change $B$ value from $L$ to $R$ or vice-versa. Thus your state graph is a bipartite graph. It changes nothing to the problem, but it is interesting to notice it.
Concerning $K$ and $M$, to respect the "cannibal constraint", a valid node must have:

$K \le M$ for left edge (or $M = 0$),
$K_0-K \le M_0-M$ for right edge (or $M=M_0$)

A valid left->right transport (edge) should be:
$(M_i, K_i, L)$ -> $(M_i-m, K_i-k, R)$, such that $(m, k)$ in $\{(1, 0), (2, 0), (1, 1), (0, 1), (0, 2)\}$.
and a valid right->left transport (edge) should be:
$(M_i, K_i, R)$ -> $(M_i+m, K_i+k, L)$, such that $(m, k)$ in $\{(1, 0), (2, 0), (1, 1), (0, 1), (0, 2)\}$.
Of course you must keep $0 \le M \le M_0$ and $0 \le K \le K_0$.
BFS in the graph
So now, how to proceed ? You can create all possible vertices that is to say all $(M, K, B)$ with $M \le M_0, K\le K_0, B \in {L, R})$ that does respect the cannibals constraint. Then build all the possible edges (up to 5 from any vertex). Finally you can run the BFS in this graph to find an eventual solution. The graph would have up to $2 M_0 K_0$ vertices and $10 M_0 K_0$ edges.
A stronger solution is to build your graph as you explore it. You can express formally all states reachable from any state and check if the vertex of this state is already explored or not.
Also note that BFS is generally a good exploration method to find the shortest distance, but here you can expect left->right transports should move 2 persons and right->left transports should move only one person to decrease the left edge population.
This is indeed a good exercise for graph state representation and exploration, but after it you should try to answer these questions:

What property between $M_0$, $K_0$ is necessary and sufficient to have a solution ? (exception of $M_0 = 0$)
What is the straight forward method to find such solution ?

Here is a small example for $M_0 = 3, K_0=2$. In blue the edges enconutered and in red the followed one.


Regex for the language over $\{a,b,c\}$ that contain at least two $a$'s but no two consecutive $b$'s

You'll need to guarantee the following:

at some place, you have $aa$
whenever there is a $b$, then there is a different letter between it and any further $b$

So one part of your regular expression will be $aa$, and that'll be need to be "in the middle" since we don't want to exclude the word $bcaab$ for example. The other part needs to take care of the restriction for $b$s.

One way to make ensure the restriction with regard to $b$ is to put at least one letter before every $b$ except for the first $b$ before and the first $b$ after $aa$. So you could do:

$(b + \epsilon)((a+c)^+b)^*(a+c)^*aa(b + \epsilon)((a+c)^+b)^*(a+c)^*$

where $\epsilon$ is the empty word. If you don't want to use $\epsilon$, you can split that expression up into 4 expressions without epsilon and sum them up.


Calculate the number of iterations in unusual nested loop

If you want to compute an upper bound of the asymptotic complexity, you can consider the maximum value for the most inside sum. Hence,$\sum_{n=n_0}^{n_T}1 \leqslant n_T + 1$. Therefore, we will have:

$$
N \leqslant \sum_{j=0}^{j_T}\sum_{k=0}^j\sum_{l=0}^k (n_T+1) = \sum_{j=0}^{j_T}\sum_{k=0}^j (n_T+1) (k+1) = (n_T+1) \sum_{j=0}^{j_T}\sum_{k=0}^j (k+1)  =
$$
$$
(n_T+1)\sum_{j=0}^{j_T}\frac{(j+1)(j+2)}{2} = \Theta(n_T (j_T)^3)
$$

Therefore, $N = O(n_T (j_T)^3)$.


One of the 4 Color Theorem most notable applications is in mobile phone masts. These masts all cover certain areas with some overlap meaning that they can’t all transmit on the same frequency. A simple method of ensuring that no two masts that overlap have the same frequency is to give them all a different frequency. But, as the government owns all frequencies and charge for each, one wants to use the minimum possible number of frequencies. The areas covered can be drawn as a map and the different frequencies can be represented as colors.


Covering a polygon with n circular rings

This problem might be hard to solve exactly.  I would suggest you try gradient descent (or another mathematical optimization technique).

[ The stuff below here is obsolete, now that the question has been edited to change the problem statement along these lines. ]

Note that minimizing your error ratio is equivalent to minimizing

$$\text{Area}(S-R) + \text{Area}(R-S),$$

since $S$ is given (so $\text{Area}(S)$ is fixed).  This observation does not seem to help very much, though.


The main reason for choosing D* is that it is incremental. Basically, when your initial route gets blocked, an incremental search algorithm is able to take advantage of the previous calculations. Dijkstra doesn't do this; it needs to recompute everything from scratch. Such an incremental approach is often used in robotics, navigation, and planning.

This is the short answer. For much more, I think you would be interested in How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?


When is a permutation k-wise independent?

A permutation cannot be $k$-wise independent. A distribution of permutations is $k$-wise independent if for $\pi$ sampled according to the distribution and any $k$ different indices $i_1,\ldots,i_k$ and $k$ different values $j_1,\ldots,j_k$, the probability that $\pi(i_1)=j_1,\ldots,\pi(i_k)=j_k$ is $1/n(n-1)\cdots(n-k+1)$. (An earlier version of this answer contained a different definition that, while interesting, is not the standard one.)

A $k$-wise independent distribution is $\ell$-wise independent for any $\ell \leq k$, and the uniform distribution over all permutations is trivially $n$-wise independent. A $k$-wise independent distribution is a distribution which "looks like" the uniform distribution when considering at most $k$ points at a time.

It is easy to see that any $k$-wise independent distribution needs to have support $n^{\Omega(k)}$, and conversely, Alon and Lovett construct such distributions with support $n^{O(k)}$.

Here is a simple example of a $1$-wise independent distribution: it is the uniform distribution over the permutations $\pi_1,\ldots,\pi_n$ given by $\pi_t(x) = (x+t) \pmod{n}$. It is easy to check that for all $1 \leq i,j \leq n$, the probability that $\pi_t(i) = j$ is exactly $1/n$.


How to prove greedy algorithm is correct

Ultimately, you'll need a mathematical proof of correctness.  I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a proof, try random testing.
Random testing
As a first step, I recommend you use random testing to test your algorithm.  It's amazing how effective this is: in my experience, for greedy algorithms, random testing seems to be unreasonably effective.  Spend 5 minutes coding up your algorithm, and you might save yourself an hour or two trying to come up with a proof.
The basic idea is simple: implement your algorithm.  Also, implement a reference algorithm that you know to be correct (e.g., one that exhaustively tries all possibilities and takes the best).  It's fine if your reference algorithm is asymptotically inefficient, as you'll only run this on small problem instances.  Then, randomly generate one million small problem instances, run both algorithms on each, and check whether your candidate algorithm gives the correct answer in every case.
Empirically, if your candidate greedy algorithm is incorrect, typically you'll often discover this during random testing.  If it seems to be correct on all test cases, then you should move on to the next step: coming up with a mathematical proof of correctness.
Mathematical proofs of correctness
OK, so we need to prove our greedy algorithm is correct: that it outputs the optimal solution (or, if there are multiple optimal solutions that are equally good, that it outputs one of them).
The basic principle is an intuitive one:
Principle: If you never make a bad choice, you'll do OK.
Greedy algorithms usually involve a sequence of choices.  The basic proof strategy is that we're going to try to prove that the algorithm never makes a bad choice.  Greedy algorithms can't backtrack -- once they make a choice, they're committed and will never undo that choice -- so it's critical that they never make a bad choice.
What would count as a good choice?  If there's a single optimal solution, it's easy to see what is a good choice: any choice that's identical to the one made by the optimal solution.  In other words, we'll try to prove that, at any stage in the execution of the greedy algorithms, the sequence of choices made by the algorithm so far exactly matches some prefix of the optimal solution.  If there are multiple equally-good optimal solutions, a good choice is one that is consistent with at least one of the optima.  In other words, if the algorithm's sequence of choices so far matches a prefix of one of the optimal solutions, everything's fine so far (nothing has gone wrong yet).
To simplify life and eliminate distractions, let's focus on the case where there are no ties: there's a single, unique optimal solution.  All the machinery will carry over to the case where there can be multiple equally-good optima without any fundamental changes, but you have to be a bit more careful about the technical details.  Start by ignoring those details and focusing on the case where the optimal solution is unique; that'll help you focus on what is essential.
There's a very common proof pattern that we use.  We'll work hard to prove the following property of the algorithm:
Claim: Let $S$ be the solution output by the algorithm and $O$ be the optimum solution.  If $S$ is different from $O$, then we can tweak $O$ to get another solution $O^*$ that is different from $O$ and strictly better than $O$.
Notice why this is useful.  If the claim is true, it follows that the algorithm is correct.  This is basically a proof by contradiction.  Either $S$ is the same as $O$ or it is different.  If it is different, then we can find another solution $O^*$ that's strictly better than $O$ -- but that's a contradiction, as we defined $O$ to be the optimal solution and there can't be any solution that's better than that.  So we're forced to conclude that $S$ can't be different from $O$; $S$ must always equal $O$, i.e., the greedy algorithm always outputs the correct solution.  If we can prove the claim above, then we've proven our algorithm correct.
Fine.  So how do we prove the claim?  We think of a solution $S$ as a vector $(S_1,\dots,S_n)$ which corresponds to the sequence of $n$ choices made by the algorithm, and similarly, we think of the optimal solution $O$ as a vector $(O_1,\dots,O_n)$ corresponding to the sequence of choices that would lead to $O$.  If $S$ is different from $O$, there must exist some index $i$ where $S_i \ne O_i$; we'll focus on the smallest such $i$.  Then, we'll tweak $O$ by changing $O$ a little bit in the $i$th position to match $S_i$, i.e., we'll tweak the optimal solution $O$ by changing the $i$th choice to the one chosen by the greedy algorithm, and then we'll show that this leads to an even better solution.  In particular, we'll define $O^*$ to be something like
$$O^* = (O_1,O_2,\dots,O_{i-1},S_i,O_{i+1},O_{i+2},\dots,O_n),$$
except that often we'll have to modify the $O_{i+1},O_{i+2},\dots,O_n$ part slightly to maintain global consistency.  Part of the proof strategy involves some cleverness in defining $O^*$ appropriately.  Then, the meat of the proof will be in somehow using facts about the algorithm and the problem to show that $O^*$ is strictly better than $O$; that's where you'll need some problem-specific insights.  At some point, you'll need to dive into the details of your specific problem.  But this gives you a sense of the structure of a typical proof of correctness for a greedy algorithm.
A simple example: Subset with maximal sum
This might be easier to understand by working through a simple example in detail.  Let's consider the following problem:
Input: A set $U$ of integers, an integer $k$
Output: A set $X \subseteq U$ of size $k$ whose sum is as large as possible
There's a natural greedy algorithm for this problem:

Set $X := \emptyset$.
For $i := 1,2,\dots,k$:

Let $x_i$ be the largest number in $U$ that hasn't been picked yet (i.e., the $i$th largest number in $U$).  Add $x_i$ to $X$.

Random testing suggests this always gives the optimal solution, so let's formally prove that this algorithm is correct.  Note that the optimal solution is unique, so we won't have to worry about ties.  Let's prove the claim outlined above:
Claim: Let $S$ be the solution output by this algorithm on input $U,k$, and $O$ the optimal solution.  If $S \ne O$, then we can construct another solution $O^*$ whose sum is even larger than $O$.
Proof. Assume $S \ne O$, and let $i$ be the index of the first iteration where $x_i \notin O$. (Such an index $i$ must exist, since we've assumed $S \ne O$ and by the definition of the algorithm we have $S=\{x_1,\dots,x_k\}$.)  Since (by assumption) $i$ is minimal, we must have $x_1,\dots,x_{i-1} \in O$, and in particular, $O$ has the form $O=\{x_1,x_2,\dots,x_{i-1},x'_i,x'_{i+1},\dots,x'_n\}$, where the numbers $x_1,\dots,x_{i-1},x'_i,\dots,x'_n$ are listed in descending order.  Looking at how the algorithm chooses $x_1,\dots,x_i$, we see that we must have $x_i > x'_j$ for all $j\ge i$.  In particular, $x_i > x'_i$.  So, define $O^* = O \cup \{x_i\} \setminus \{x'_i\}$, i.e., we obtain $O^*$ by deleting the $i$th number in $O$ and adding $x_i$.  Now the sum of elements of $O^*$ is the sum of elements of $O$ plus $x_i-x'_i$, and $x_i-x'_i>0$, so $O^*$'s sum is strictly larger than $O$'s sum.  This proves the claim. $\blacksquare$
The intuition here is that if the greedy algorithm ever makes a choice that is inconsistent with $O$, then we can prove $O$ could be even better if it was modified to include the element chosen by the greedy algorithm at that stage.  Since $O$ is optimal, there can't possibly be any way to make it even better (that would be a contradiction), so the only remaining possibility is that our assumption was wrong: in other words, the greedy algorithm will never make a choice that is inconsistent with $O$.
This argument is often called an exchange argument or exchange lemma.  We found the first place where the optimal solution differs from the greedy solution and we imagined exchanging that element of $O$ for the corresponding greedy choice (exchanged $x'_i$ for $x_i$).  Some analysis showed that this exchange only can only improve the optimal solution -- but by definition, the optimal solution can't be improved.  So the only conclusion is that there must not be any place where the optimal solution differs from the greedy solution.  If you have a different problem, look for opportunities to apply this exchange principle in your specific situation.


There's a simple solution which takes advantage of the fact that semaphores naturally allow controlling access to a resource with multiple instances. Model the exclusion as a resource with two instances. A requires both instances while B and C each require one. When A starts, it grabs both instances, preventing B and C from starting. When B or C starts, it grabs one instance, which allows the other to start concurrently, but blocks A.

A:                  B:                  C:
  V(S, 2)             V(S, 1)             V(S, 1)
  …                   …                   …
  P(S, 2)             P(S, 1)             P(S, 1)

This solution works even if the processes run multiple times. A critical ingredient that makes it work is that A atomically excludes both B and C from running.

If you treat B and C's resources as distinguishable, with A requiring both, you run into a classical problem, which is the order of grabbing locks. This problem is similar to the dining philosophers problem. When A starts, it either grabs the B resource first, or the C resource first. Let's say A grabs B, and then tries to grab C. If C is not available, what should happen? If A keeps the B resource then it prevents process B from starting. So A must release B and try again. Since A knows that C is busy, it can wait on C first. In this particular exercise, where the processes only run once, this works. Note that this requires semaphores with a non-blocking “try” operation.

A:                  B:                  C:
  lock(B)             lock(B)             lock(C)
  if try_lock(C):     …                   …
    …                 release(B)          release(C)
    release(C)
    release(B)
  else:
    release(B)
    lock(C)
    lock(B)
    …
    release(B)
    release(C)

If B and C could run multiple times, this strategy wouldn't work: A must never keep one lock while waiting for the other, because that prevents the corresponding process from running again. In this case, I think there's no wait-free solution with only binary semaphores.


The following approach will solve the problem in $O(km^2\log m + n)$ time, which is only better than $O(mn)$ if $n$ is extremely large compared to $m$ and $k$ is relatively small.  My hope is that someone can come up with a refinement of my "caching mechanism" that decreases the dependence on $m$.

The view from one position in the string

From the point of view of a particular position in the string, replace queries appear as a sequence of instructions of the form "If you are an x, change to a y", each of which occurs at a particular time.  The only instructions that are "visible" to a particular position in the string are those whose $[l, r]$ range includes that position.  The timestamp of an instruction is simply its position within the list of all replace queries: timestamps are therefore unique.

The idea is to build a directed graph that represents these time-stamped instructions as seen by the "current" string position (initially, position 1).  The vertices in this graph are the characters $c_1, \dots, c_k$; each directed edge $uv$ represents the instruction "If you are a $u$, change to a $v$", and is labelled with a timestamp, which is the position where it occurs within the list of all replace queries (starting from 1).  Note that an edge can be present multiple times, with different timestamps.  To find the "final" character at the current position, we start at time 0 at the vertex corresponding to the initial character at this position, and repeat the following steps as long as we can:

Choose the outgoing edge from the current vertex with the smallest timestamp that is greater than the current time
Move to the endpoint of this edge
Update the current time to the timestamp on this edge

The first step, choosing the "next" instruction, can be performed in $O(\log m)$ time if we use an adjacency-list graph representation that uses a self-balancing binary tree keyed by the timestamp to hold the set of outgoing edges for each vertex.  In the worst case, all $m$ instructions are visible to the current string position, so a single traversal therefore takes at most $O(m\log m)$ time.

Maintaining the instruction graph

Initially, we build this graph for position 1.  After determining the final character at that position, we update the graph as we move left-to-right through the string, processing each position in turn.

The $t$-th replace query $(l, r, c_i, c_j)$ requires 2 changes to the graph: An edge $c_ic_j$ with timestamp $t$ needs to be inserted when we reach position $l$, and that same edge needs to be removed when we reach position $r+1$.  Each of these changes takes $O(\log m)$ time using the graph representation described earlier.

Caching

The algorithm described so far performs the graph traversal at each of the $n$ string positions, so it takes $O(nm\log m)$ time -- worse than the original!  But all is not in vain.

Notice that for $m$ queries, there are only $2m$ times at which the graph changes -- so if we cache the final destination character for each distinct initial character $c_1, \dots, c_k$ whenever the graph changes, we can simply look up the answer in $O(1)$ time for each position until we hit the next query boundary.  This way, the full traversal need be performed at most once per distinct character after each change to the graph, for $O(km^2\log m + n)$ time.  (This approach -- "flush the entire cache as soon as the graph changes" -- is a very simple caching mechanism.  It may be that more sophisticated caching techniques can drop the time complexity further, by avoiding the recomputation of some cached final destination characters that do not change.)


When does a semaphore issue a wait and when does it issue a signal?

The semaphore doesn't issue those.  A semaphore is an object that can be used by processes to coordinate between themselves.  Thus, a process will call semSignal or semWait on a shared semaphore.  We can't describe the conditions under which it will do that in general, because it's up to each process how it wants to use semaphores.  Semaphores are a primitive that can be used in many ways.  You should be able to find many examples online or in your textbook of using semaphores for coordination; that will give you some examples of specific processes and when those particular processes will invoke those operations on a semaphore.


Copying items in arrays while checking their indexes

All you're looking for is some mapping between the elements of $P$ and their indexes, that can be found in $O(1)$ for each element of $P$. Suppose given $p_i \in P$, you can use the fact that $p_i \in \{0, \dots n-1\}$, and that no $p_j \in P$ exists s.t $p_j = p_i$ (other than $j=i$).

How will you do it? Set $R[x]$ to the index of element $x \in P$.

Since $x$ is unique, no elements of $R$ will be overridden.
Suppose $p_i , p_j \in P$, and $p_i$ occures before $p_j$ ($i<j$). Then $R[p_i] = i$ and $R[p_j] = j$, and it holds that $R[p_i]<R[p_j]$

You should be able to take it from here.


Relations between different time complexities of an algorithm

Let us use the following notations:

$L$ is any lower bound on the running time.
$U$ is any upper bound on the running time.
$B$ is the best case running time.
$W$ is the worst case running time.
$A$ is the average case running time.

These parameters are related in the following way:

$$ L \leq B \leq A \leq W \leq U. $$

You can solve the question using these relations.

Make sure that you understand why they hold.


Context-free language and regular expressions

The subtlety is that in the first case, the number of $a$'s before the unique $b$ must be at least the number of $a$ after, i.e. your language is $\{a^nba^m|n\geq m\}$, so it is not regular. This is because each $A$ produces at least one $a$.

In the second case however, this constraint disappears, and your language becomes indeed $b+a^*ba^+$ which is regular.


Does a collision oracle for the pigeonhole subset sum problem produce solutions?

The way I understand it is the following.

Note that for $s_1$, $f_\vec{a'}(s_1)=T$  (because the sum was $T'$ and we replaced $a_j$ with $a'_j$ and we know that $j\in s_1$.

Now, they search for a collision, i.e., another $s_2$ such that $j\notin s_2$,
but $f_\vec{a'}(s_2)=T$. (is there a typo there, having $T'$ instead?)
Now, what is $f_\vec{a}(s_2)$? also $T$, right? since $j\notin s_2$...

Does it help?


Finding the upper bound of states in Minimal Deterministic Finite Automata

This is wrong. Determinization of an NFA with $r$ states could result in a DFA with up to $2^r$ states. Therefore your argument actually gives an upper bound of
$$2^{nm}. $$
This can be improved if you switch the order of operations. If you first convert your NFA to a DFA and only then apply the product construction, then you get the better bound
$$ n2^m. $$

This bound is tight for infinitely many values of $n,m$. Consider the language $L_2$ of all words over $\Sigma^*\{\sigma_1,\ldots,\sigma_2\}$ that do not contain all letters. There is an NFA for $L_2$ (with multiple initial states) using only $m$ states. However, any NFA for $\overline{L_2}$ needs to contain at least $2^m$ states. Since $\overline{L_2} = \Sigma^* \setminus L_2$ and $\Sigma^*$ can be accepted by a single-state DFA, we see that the bound above is optimal.

You can probably show that the bound is tight for (practically) all $n,m$ by slightly modifying the above construction, replacing $\Sigma^*$ with $(\Sigma^n)^*$.


Unique representation of 5-number sets with values 1-13

Here is a solution with 20 bits. Consider the following array:

0x000f2616, 0x000dbcce, 0x000533cf, 0x0007d943, 0x000a180c,
0x000f69f2, 0x0005e214, 0x0009da04, 0x000e101a, 0x000c495c,
0x0009cfaa, 0x000ff60d, 0x0000103d

Each of these numbers $x_1,\ldots,x_{13}$ is 20 bits long. Given a hand $a,b,c,d,e$, compute the 20 least significant bits of $x_a+x_b+x_c+x_d+x_e$. You can easily check that this results in a value that identifies a hand uniquely.

I found these values by randomly generating arrays until one of them worked, so it's possible that a better construction exists (such as one using codes over $\mathbb{F}_5$).

Here is another solution, which results in keys in the range [0,441100]. Let $p = 441101 \approx 2^{18.75}$, which is prime. The key corresponding to a hand $a,b,c,d,e$ is $5^a+5^b+5^c+5^d+5^e \bmod{p}$. This is the minimal prime that works. I calculated it by factoring all differences of $5^a+5^b+5^c+5^d+5^e$ for all pairs of hands.

You can also implement this using the array

1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 188721, 61403, 307015, 211772

Add the corresponding numbers, and (optionally) reduce modulo 441101.


Find All permutation of String using Iteration

Wikipedia describes several algorithms, including:

Heap's algorithm.
Steinhaus–Johnson–Trotter algorithm.


How can I prove $P \rightarrow (Q \rightarrow R)$ is equivalent to $(P \wedge Q) \rightarrow R$

You could just construct the truth tables for the two formulas: there are only three variables, so the tables are only eight lines.
Use de Morgan's laws, distributivity and so on to rearrange one formula into the other.
Use similar techniques to show that $[P\rightarrow (Q\rightarrow R)] \leftrightarrow [(P\wedge Q)\to R]$ is equivalent to true.
Use similar techniques to show that $[P\rightarrow (Q\rightarrow R)] \leftrightarrow \neg[(P\wedge Q)\rightarrow R]$ is equivalent to false.
Use one of the various propositional proof systems to accomplish one of 2–4, though that sort of thing will probably come up later in your course.


To fix symbols, let us choose the decomposition $z = uvwxy$.

One of the examples where $|vwx|\le p$ comes in, is the language $L =\{ a^mb^na^mb^n\mid m,n\ge 1\}$.

Start with the "generic" string $a^pb^pa^pb^p$ where $p$ is the pumping constant. To have any chance of finding a pumping pair $v,x$ such that $uv^iwx^iy$ is within the language is by choosing $v$ in the first set of $a$'s and $x$ in the second set of $a$'s (or similarly for the $b$'s). Now the length of $vwx$ will be more than $p$ as it contains all $b$'s between the two sets of $a$'s.

Without that restriction $L$ can be pumped, and the pumping lemma is no longer suited for proving $L$ is not context-free.


The stable marriage algorithm with asymmetric arrays

Yes, the stable marriage problem still makes sense with unequal arrays. Permit me to use men and women as opposed to students and dorms. There are different stable matchings that you can ask for resulting in different cases.

A specific stable matching is desired, either male optimal or female optimal solution
Any valid stable matching is desired
All the stable matchings are required

Let's consider the first case where we want a specific stable matching. Suppose there are $m$ men and $w$ women. Depending on which set is larger we modify the termination condition of the standard algorithm accordingly. Suppose without loss of generality we want the male optimal solution. If $m < w$ we continue until $m$ women have been proposed to. If $m > w$ then we continue until each man is either on the string of some women or has been rejected by all the women.

It's easy to see how the above algorithm can be applied to the second case where any such stable matching is required. Just have the smaller set be the one that proposes.

The third case depends on a theorem that states that if a person is unmarried in one stable matching then they are unmarried in every stable matching. The case then becomes identical to the case with equal sized sets.

More detail on all three cases as well as pseudo-code for each algorithm can be found in McVitie and Wilson's paper titled "Stable marriage assignment for unequal sets".


What is the reason that is FFT multiplication slower than other methods for small N?

The Wikipedia FFT article says that the split-radix FFT algorithm requires $4N\log_2N-6N+8$ real multiplications and additions.  Multiplying 2 degree $M$ polynomials results in a polynomial of degree $2M$, so the "FFT multiplication of two polynomials" goes like this:

FFT (size 2M) of polynomial f(x) (evaluate f(x) at the 2M primitive roots of unity)
FFT (size 2M) of polynomial g(x) (evaluate g(x) at the 2M primitive roots of unity)
multiply each of the 2M fourier coefficients together
inverse FFT (size 2M) of the fourier coefficients to get the resulting polynomial

Perhaps there is a way to make the first two FFTs faster based on the fact that the $M+1$th through $2M$th coefficients of f(x) and g(x) are all zeros, but I don't know it offhand.

So we are doing 3 FFTs of size $2M$ plus an additional $2M$ complex multiplies (each of which is 4 real multiplies and 2 real additions so:
$$3 (4(2M)\lg2M - 6(2M)+8)+4M = 24M\lg M -8M+24$$
additions and $24M\lg M - 4M + 24$ multiplications.

Meanwhile the naive polynomial multiplication algorithm (convolution) takes $M^2$ real multiplications and $(M-1)^2$ real additions.  (Proof left as exercise for the reader.)

Thus the naive algorithm will be faster for $M \leq 128$, while the FFT based algorithm will probably be faster at $M \geq 256$, and the crossover will be somewhere between 128 and 256.  (Proof left as exercise for the reader.)

I did this quickly and sloppily, so I'm probably off somewhere (e.g., the forward FFTs are real -> complex, (but is there a DCT version that would be cheaper?) while the reverse is complex -> real (which may have slightly different constants than the ones I used,) and I only did the evaluation at $M$ power of 2 (FFT of non-power of 2s is more expensive.))  Nonetheless, the point stands: the constant multiplier for the FFT is approximately 24, while the constant multiplier for the naive convolution is 1, so you need to compare (something like) $24M\lg M$ to $M^2$.