Since there is 8 word block, 2 element can stay in one block.
Now notice that each element is refered twice, one read and one write operation.
So when in a block when 1st element is refered for read, it will be miss, and hence that block will be copied to cache.
Now 2nd reference to that 1st element will be hit, as well as both reference to 2nd element will also ne hit sience block has 2 elements.
So out of 4 reference, 1 miss and 3 hit for one block. Gets repeated for each and every block.
So hit 3/4
and miss 1/4


A clique is a simple undirected graph with all of the possible edges. It is also known as a complete graph, but clique is more often used to referring to subgraphs that are complete graphs.

The clique cover problem asks whether a graph's vertices can be partitioned into $k$ or fewer sets such that each set of vertices induces a clique. That is, $V = V_1 \cup V_2 \cdots \cup V_k$ such that if $u, v \in V_i$ then $uv \in E$. For example, $C_4$ (a cycle of 4 vertices) can be partitioned into 2 cliques by choosing two non-adjacent edges. If the vertices were 1, 2, 3, 4 and the edges 12, 23, 34, 14, then we could write $V = \{1,2\} \cup \{3,4\}$, and check that $12$ and $34$ were edges as required.

This is different from the clique problem, which asks whether there is a clique in the graph of size at least $k$ (and does not care about the structure of the rest of the graph. For example, in $C_4$, there is a clique of size 2.


How to calculate the mergesort time complexity?

Imagine that we have an array $A$ of size $n$. Mergesort splits this array into two equal halves and sorts them individually. So in context of the paragraph you have provided, each node corresponds to some chunk of the original array that we want to sort. We divide a node $A[L,R]$ to two nodes $A[L,M]$ and $A[M+1,R]$ with $M = \frac{L+R}{2}$

The splitting of a node $A[L,R]$ into two nodes takes $R-L+1$ time and then merging the two child nodes $A[L,M]$ and $A[M+1,R]$ again takes $A[R-L+1]$ time. Thus for every node, the number of operations the algorithm performs is equal to twice the size of the array corresponding to that node.

Thus we have that on any particular level if we have an array of size $k$, splitting and merging of the array can be done in $k + 2\times \frac{k}{2} = 2k$ operations.

Now note that we keep splitting the array till we have arrays of size $1$ since we can't split them further.

Draw a binary tree with the root node corresponding to the array $A[1,N]$ and with each node having two children corresponding to its left and right halves and recursively draw  the structure for each child till we have arrays of size $1$. Denote each node by the size of the array that it corresponds to. We will get something that looks like this

(Taken from Khan Academy)

This is the recursion tree for merge sort.

The computation time spent by the algorithm on each of these nodes is simply two times the size of the array the node corresponds to. Therefore the total running time $S$ of mergesort is just the sum of all the sizes of the arrays that each node in the tree corresponds to i.e.
$$S = 2 \sum_{i=0}^k 2^i\frac{n}{2^i}$$

(How did we get this sum? There are $2^i$ nodes of size $\frac{n}{2^i}$ in the tree and it takes $2k$ time to finish computation on an array of size $k$)

Observe that when $i=k$, $\frac{n}{2^k} = 1 \implies n = 2^k \implies k = \lceil{\log n}\rceil$
Thus $S$ reduces to $$2 \sum_{i=0}^{\lceil{\log n}\rceil} n = 2n\lceil{\log n}\rceil = \mathcal{O}(n\log n)$$


For the time hierarchy theorem, how is the input translated efficiently?

This has been clarified in the book's online errata:

  Page 369, Proof of the Time Hierarchy Theorem 9.10.

  The proof requires some additional technical discussion at one place. In Stage 4 of D, it simulates M on w. This simulation may require representing each cell of M's tape with several cells on D's tape because M's tape alphabet is arbitrary and D's tape alphabet is fixed. However, initializating the simulation by converting D's input w to this representation involves rewriting w so that its symbols are spread apart by several cells. If we use the obvious copying procedure for spreading w, this conversion would involve O(n^2) time and that would exceed the O(t(n)) time bound for small t.
  Instead, we observe that D operates on inputs w of the form x10^k where x = ‹M›, and we only need to carry out the simulation when k is large. We consider only k > |x|^2. We can spread w by first using the obvious copying procedure for x and then counting trailing 0s and rewriting these by using that count. The time for spreading x is O(|x|^2) which is O(n). The time for counting the 0s is O(n log n) which is O(t(n)) because t is time constructible.

  Reported 11/15/12 by Kaveh Ghasemloo of the University of Toronto.


How does "solving" a game like connect four or tic-tac-toe work?

In  short, minimax is what you're looking for.

We say that a game is valued $1$ if player 1 wins, $-1$ if player 2 wins and $0$ if it's a tie.

You have your brute-forced game tree. At each level you check who's turn it is. If it's player 1's turn, he/she will try to maximize the outcome. If it's player 2's turn he/she will try to minimize the outcome.

So you apply that. Literally. At each node you take the maximum or minimum of the child nodes and assign it to that node, depending on the depth at which you're looking (AKA who's turn it is). Then the value of the root node is the outcome of the game with perfect play.


Showing that the pumping lemma cannot prove that some language is not regular

The idea of this exercise is to show that the pumping lemma is not a sure-fire method to prove that a language isn't regular. To show that, we need to come up with a language that (i) isn't regular, but (ii) cannot be proved not regular using the pumping lemma. This is the goal of your exercise.

The "pumping lemma method" for proving that a language $L$ isn't regular is a sort of game:

The adversary gives you an integer $p$.
You come up with a word $w \in L$ of length at least $p$.
The adversary partitions the word into $w = xyz$, where $|xy| \leq p$ and $|y| \geq 1$.
You come up with an integer $i$ such that $xy^iz \notin L$.

If you win this game then you have shown that $L$ is not regular. In order to show that the pumping lemma cannot be used to prove that $L$ is regular, you have to show that the adversary wins the game.

A winning strategy for you is, for each $p$, a word $w \in L$ of length at least $p$, and for each legal partition $w = xyz$, an integer $i$ such that $xy^i z \notin L$. This is how you apply the pumping lemma. A winning strategy for the adversary is an integer $p$ such that each word $w \in L$ of length at least $p$ can be legally partitioned as $w = xyz$ in such a way that $xy^i z \in L$ for all $i \geq 0$. This is your goal in this exercise.

If the pumping lemma doesn't work, what does work? There is a generalization of the pumping lemma in which you mark $p$ locations of the word $w$, and then the adversarial partition $w = xyz$ must satisfy (i) $xy$ contains at most $p$ marked locations, (ii) $y$ must contain at least one marked location. Sometimes this generalized version works when the usual one fails, but not always.

One method which is guaranteed to always work is the Myhill–Nerode criterion. If a language is not regular, you can always prove it (in principle) using the Myhill–Nerode theorem. In many cases it is also easier to apply than the pumping lemma, even when the latter does work. What pity that it is beyond the curricula of many courses!


There is a lower bound for multiplication of $\Omega(n\log{n})$ conditional on a conjecture in network coding. There is also an algorithm matching this bound.


Number of nodes in Van-Emde-Boas tree of universe size u?

The nice picture in the question does not include the summary nodes nor the min and max fields, both of which are indispensable components of a van Emde Boas tree (vEB tree). A better illustration might be the following picture taken from how to read off the set represented by a van-Emde-Boas tree, which was drawn by Raphael based on a figure in CLRS, where a number in orange is drawn at a min field that marks its presence in the set of integers being represented.

How many nodes are there in the vEB tree implemented like the illustration above?

There are $1 + 5 + 5 \times 3 = 21$ nodes in the illustration above.

For the sake of simplicity, let $w=2^h$ and $u=2^w=2^{2^h}$. A vEB tree over the universe $\{0,1,\cdots, u-1\}$ is of depth $h=\log\log u$.

There is one node of depth 0, which is the root node.
There are $2^{2^{h-1}} + 1$ nodes of depth 1.
Each node of depth 1 has $2^{2^{h-2}} + 1$ child nodes of depth 2.
...
Each node of depth i has $2^{2^{h-i-1}} + 1$ child nodes of depth $i+1$.
...
Each node of depth $h-1$ has $2^{2^{h-h}}+1=3$ child nodes of depth $h$.

In total, the number of all nodes is
$$1 + \sum_{i=1}^{h}\prod_{k=1}^i(2^{2^{h-k}} + 1)=(2^{2^h} - 1)\sum_{i=0}^{h}\frac1{2^{2^i} - 1}\tag{1}$$
which is 1, 4, 21, 358, 92007, 6029862760, 25898063359598159721, $\cdots$ for $h=0,1,2,3,4,5,6,\cdots$ respectively. When $h\ge4$, the number of nodes is about $1.404u$.

Similarly, the number of all summary nodes is, for $h\ge1$,
$$1 + \sum_{i=2}^{h}\prod_{k=1}^{i-1}(2^{2^{h-k}} + 1)=(2^{2^{h}} - 1)\sum_{i=1}^{h}\frac1{2^{2^i} - 1},\tag{2}$$
which is 0, 1, 4, 21, 358, 92007, 6029862760, $\cdots$ for $h = 0,$$1, 2,3,4,5,$$6,\cdots$ respectively.

What is the number of all non-summary nodes? Subtracting (2) from (1), we obtain

$$(2^{2^{h}} - 1)\left.\frac1{2^{2^i} - 1}\right|_{i=0}=2^{2^h}-1=u-1.$$

The formula also hold for $h=0$. So we have obtained the following surprising formula.
$$\text{the number of non-summary nodes in a vEB tree of universe size } u=2^{2^h}\text{ is }u-1.$$

Every node at the same depth use the same amount of space. Nodes at a smaller depth may use much more space than those at a larger depth. For example, for $h=5$, the root node contains a bit-array of size 65536 but a leaf node just contains several words. Since the number of nodes that use bigger space decreases very quickly as their depth becomes smaller, the total space used is $O(u)$.

Exercise. The number of all leaf nodes, which are vEB trees of universe size 2 in a vEB tree of universe size $u=2^{2^h}$ is $u-1$.


Calculating time complexity of two interdependent nested for loops

The $n^{th}$ harmonic number can be approximated by the integral $\int_1^n \frac{1}{x} \mathrm{d}x$.

\begin{align}
H_n \approx \int_1^n \frac{1}{x} \mathrm{d}x = \left[ \ln x \right]_1^n = \ln n - \ln 1 = \ln n
\end{align}

The limit of $H_n - \ln n$ is $\gamma \approx 0.577$, which is the Euler-Mascheroni constant.

Therefore, we get
\begin{align}
H_n & = \ln n + \gamma + r(n) \\
r(n) & \in \mathcal{O}\left(\frac{1}{n}\right)
\end{align}

Since $H_n - \ln n$ is not exactly $\gamma$, we need some remainder $r(n)$, whose limit is $0$.

So we get $T(n) = n \ H_n = n\ln n + n\gamma + n \ r(n) \in \mathcal{O}(n \log n)$


You're not wrong, but neither are they. The normal formulation is to have the left subtree values be strictly less than ($<$) the current value and the right greater than or equal to ($\geq$) the current value, or vice versa ($\leq$ and $>$), however using $\leq$ and $\geq$ still results in a working BST in the sense that the tree provides an ordering. (Try constructing a few, you'll see that the difference is that if you have repeated values, they can get spread over the right-most part of the left subtree and the left-most part of the right subtree instead of being in one or the other).

To see that it still works, consider the cases when searching the tree:

$y = x$, you've already found it, so you can stop here;
$y < x$, it must be in the left subtree (if $y <x$ then $y \leq x$);
$y > x$, it must be in the right subtree.

So you can see that the operation is identical, the choice at each node remains unambiguous.

EDIT Just to highlight Svick's excellent point in the comments, if you're searching for all nodes with the same value, the "$\leq,\geq$" case introduces complications - it may require more than one pass to find all such nodes (a full traversal will get them all of course, if it's an inorder traversal you even get them in a row).


Does a binary code with length 6, size 32 and distance 2 exist?

Yes, there is such a set. You are actually on the right track to find the following example.
Let $C = \{c : |c|=6 \text{ and there are even number of 1's in c}\}$. You can check the following.

$|C|=32$.
$d(u,v)\geq2$ for all $u,v\in C$, $u\not=v$. (In fact, $d(u,v)=2$ or 4 or 6.)

Here are four related exercise, listed in the order of increasing difficulty. As in the question, only binary code is concerned.
Exercise 1. Give another example of a set of 32 words of length 6 and pairwise distance at least 2.
Exercise 2. Show that there are only two such sets, as given in the answer and in the exercise 1.
Exercise 3. Generalize the above to words of any given length and pairwise distance at least 2. (Hint, $32=2^{6-1}$.)

Exercise 4. (further generalization stated in Yuval's answer) If $A(n,d)$ is the maximum size of a code of length $n$ and minimum pairwise distance $d$, then $A(d,2d)=A(n-1,2d-1)$.


What areas in EE overlap closely with CS

One very close overlap is of course Computer Architecture.

Another close overlap (which incidentally happens to be my speciality) is EDA (CAD for VLSI designers). EDA requires development of fairly sophisticated parallel algorithms for things such as routing, RC extraction, optical proximity correction, etc., as well as understanding of the underlying VLSI physics.

Other subjects include telecommunication and signal processing, as pointed out in Subhayan's comment.


You are fine up to step 3 (the DFA) but your minimization is incorrect.

It's clear that the minimized DFA is not right, because both the inputs ba and ab (which are not in the original language, nor are they accepted by the DFA in step 3) lead to final state E.

Looking at your minimization steps, it seems that you have unified final and non-final states; for example J (final) -> F (not final) and I (final) -> E (not final). Merging a final state with a non-final state changes the language accepted by the automaton, leading to the acceptance of incorrect strings as noted above.


GOTO vs. including line in loop - will it affect efficiency?

With the question as it is written right now, I have no idea what "one thing" and "thing" are, the second version modifies a list named "relevant_reactions" that isn't present in the first version, so all in all I would say that your question is impossible to answer.

You say that "goto" is considered bad practice, but instead of removing the "goto", you complete rewrote everything from scratch. If you don't like the "goto" here's a way that doesn't change your algorithm at all:

1 eliminate stuff from a list called reactions
2 all_done = false
3 while all_done is false
4     all_computable = true
5     for each element in reactions:
6         if all_computable is false:
7             do nothing
8         else if one thing is computable:
9             compute it
10        else:
11            eliminate element from reactions, all_computable = false
12     if all_computable is true:
13         all_done = true


Difficulty in proving the existence of one-way functions

Apparently proving the existence of these functions would be more difficult than proving $P\not =NP$? And I'd like to know the technical reasons for this, does it have something to do with the "for every" in the definition?

The answer is in your question itself:

  I believe that since proving its existence would also prove $P\not =NP$

This is indeed the case. Somebody that proves the existence of one-way functions automatically also proves $P\not = NP$. On the other hand, it is conceivable that you could prove $P\not = NP$ without proving that one way functions exist. Thus, proving the existence of one-way functions is at least as hard as proving $P\not = NP$.

  What steps would a mathematician or computer scientist take to prove that one-way functions exist?

Coming up with an extremely clever and creative idea that nobody came up with before.


Converting if-then-else condition to integer linear programming with equality constraints

We have three binary variables $x, y, z \in \{0,1\}$ and the following if-then-else (ITE) condition

$$\text{if } x = 1 \text{ then } y = 1 \text{ else } y = z$$

If $x = 1$, then $y = 1$ but $z \in \{0,1\}$. If $x = 0$, then $y = z \in \{0,1\}$. Therefore, we have the following $4$ vertices of the $3$-cube

$$\{ (0,0,0), (0,1,1), (1,1,0), (1,1,1) \}$$

Using SymPy, we obtain the following product of sums (POS):

>>> from sympy import *
>>> x, y, z = symbols('x y z')
>>> minterms = [[0, 0, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]]
>>> POSform([x, y, z], minterms, [])
And(Or(Not(x), y), Or(Not(y), x, z), Or(Not(z), y))

Converting the formula in POS, i.e., in conjunctive normal form (CNF), to integer programming, we obtain the following system of linear inequalities

$$\begin{array}{rl} (1-x) + y &\geq 1\\ x + (1-y) + z &\geq 1\\ y + (1-z) &\geq 1\end{array}$$

which can be rewritten as follows

$$\begin{array}{rl} -x + y &\geq 0\\ x - y + z &\geq 0\\ y -z &\geq 0\end{array}$$

Verifying in Haskell:

λ> triples = [ (x,y,z) | x <- [0,1], y <- [0,1], z <- [0,1] ]
λ> filter (\(x,y,z)->(-x+y>=0) && (x-y+z>=0) && (y-z>=0)) triples
[(0,0,0),(0,1,1),(1,1,0),(1,1,1)]


Understanding the Linear speedup theorem and how strong it is

The linear speedup theorem says that, for any constant $c$, you can decide the language $c$ times faster. It does not say that you can make it faster by some non-constant function.

The speedup theorem works by defining a new Turing machine that writes $c$ characters of the old Turing machine in a single tape cell, and then adjusting the transition function so that it simulates in a single step everything that the original machine did between entering and leaving each $c$-character block.  If $c$ is a constant, it doesn't depend on the input, so you just compute the new machine once and use it on whatever input you want. But if you want $c$ to be some non-constant function, then you have to figure out what the new machine is every time you run it. That takes exponentially long, since there are exponentially many possible $c$-character blocks that you have to figure out the transition function for.


You can create a unique identifier by concatenating the two fields in question. If there are files where both fields are identical, concatenate an extra field disambiguating them.


Proving that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular with pumping lemma

It's not sufficient proof because you only proved that if you choose the decomposition $x=ab^q$ and $z$ the rest does not meet the three points of the pumping lemma but remember that the lemma says:

If $L$ is regular then there is a constant $N>0$ associated to $L$ such that  $\forall \sigma \in L$ with $|\sigma|\geq N$ $\textbf{exist}$ a decomposition $\sigma = xyz$ ...

Summarizing. you proved that your decomposition doesn't work. Now you have to try all other possible decompositions.


How precise to be when describing a Turing machine?

You are asking two different questions: whether your solution is correct, and whether the level of description of your Turing machine is appropriate. I will answer them separately.

Correctness Your Turing machine $M^*$ is not guaranteed to halt. In other words, your solution is incorrect. The missing observation is that if a Turing machine uses only space $k$, then there is an upper bound on the number of steps that it can run without getting into an infinite loop.

Level of description Here you should be asking two questions:

What does it mean to describe a Turing machine?
How do I prove that a certain language is decidable?

The level of description of Turing machines is a touchy subject. Usually they are described quite informally. The level of description should be such that in principle you could convert the informal description into a formal Turing machine. In practice, I suggest looking at some examples to get the general feel.

As to how to prove that a language is decidable, there is no need to describe a Turing machine. Decidability can be proved using any model of computation. In particular, you can use the "English" model of computation, in which you describe how to decide the problem in the English language (or in any other language). For example, you could say "Simulate $M$ on $w$, and if it ever uses more than $k$ space, immediately reject; otherwise, once $M$ halts, accept". (This is just your incorrect solution.)


Is open adressing with prime steps bijective?

The following proof only uses basic modular arithmetic, and the fact that the least common multiple $\mathrm{lcm}(a,b)$ is equal to $a\cdot b$, if $\gcd(a,b)=1$.

Injectivity:

Assume there are two different $a,b\in \{0,...,m-1\}$, $a>b$, such that $f(a)=f(b)$. This means that

$$
a\cdot w \mod m = b\cdot w \mod m
$$
and
$$
a\cdot w=b\cdot w+k\cdot m
$$
for some integer $k>0$. We reorder to
$$
(a-b)\cdot w=k\cdot m
$$
Both sides of the equation are a multiple of $w$ and $m$. However, since $w$ and $m$ don't share any divisor, any common multiple is larger than $w\cdot m$. The left hand side of the equation clearly contradicts this fact. Hence, there are no such choices for $a$ and $b$, and $f$ is injective.

Surjectivity

This can be argued by counting. The function $f$ is total on the set $\{0,...,m-1\}$, and since $f$ is injective as shown above, $f$ is also surjective.


Textbooks don’t have to include everything. There should be room for you to figure out things yourself. Otherwise, how would we ever create things not found in today’s textbooks?

Maintaining the TLB is a tiny bit of code in the operating system. But every single instruction accessing memory relies on the TLB. Do you think the TLB does NOT save enormous amounts of work? 99.99% of all memory accesses are fast because the TLB tells you immediately where the data is. Having to update the TLB sometimes is a very small price to pay.


Generate all permutations of 1,...,6 (outer loop below), and all binary numbers of length 6 (inner loop below), then combine each permutation in the first set with each one from the second set:
for π in permutations(1,...,6):
    for x in 000000,...,111111:
        output C(π[1],x[1]),...,C(π[6],x[6])

where $C(n,0) = n$, $C(n,1) = 13 - n$.


Why is simulation by non deterministic Turing machine faster than a deterministic one?

First of all, simulation of non-deterministic universal TM is better than simulation of deterministic universal TM only time-wise. But number of parallel executing threads is very high. In parallel algorithms parlance, $T(n)$ will be smaller but another metric $T(n)P(n)$ will be higher.

Deterministic UTM has extra $\log T(n)$ factor because it has to simulate multiple working tapes in a single working tape. If we use it as a simple multiple track tape, then to simulate a single step we will need to go to and forth for maximum $T(n)$ steps. We can improve this time by a clever trick. Instead of moving heads on the multiple tracks, we keep the head of the track(s) stationary and move the content of the tracks. We also keep a gradually increasing number of  interspersed blank spaces (another special blank space, instead of regular blank space) on both sides of head to do the shifting of tape content efficiently. By successfully executing this trick, each step can be simulated in amortized $O(\log T(n))$ steps.

We have to see how we can simulate non-deterministic UTM cleverly that does not require us to go to and fro, thus saving us $O(\log T(n))$ factor. Going to and fro in $k$ working tapes is the real bottleneck. We assume input and output tape are separate in both UTM and simulated TM, so they do not matter much.

Let us think how we can simulate a single work tape without going to and fro.
What we do, is whenever we need to go left, we do not go left, instead we guess what is in the left, maybe 0 or may be 1 (or maybe $B$ ot may be >, beginning of tape), and proceed to the right (non-deterministically of course, for both the cases), but we write what we guessed on a work tape. Since we are not moving left correctly, we cannot know tape symbols when we move right too. So whether we move left or right, we non-deterministically guess what is under the head, make note of our guess, and move on.

After the computation is over (by a series of $T(n)$ fake or  correct guesses and writings), for each thread of computation we have the content of guesses on a work tape, and we can check if the guesses and writings on the tape match in linear time $O(T(n))$ by actually going to and fro in yet another work tape. If we need our UTM not to exceed $T(n)$ execution time then we need to keep a counter for $T(n)$, some of the errant threads may go on executing for infinite time (there is a requirement on some non-deterministic TM models that every thread should stop after $T(n)$ time for acceptance, while in others only accepting threads need to stop after $T(n)$ time).

If we do this for all $k$ tapes together in a single tape, then too will be able to do this trick, but we will have to go to and fro $k$ times, one for each tape, to check if the guesses of each tape are consistent with what we are writing and what we are guessing later. This checking will take $O(kT(n))$ additional time overall for all tapes. So total running time of the non-deterministic UTM will be $O(CT(n)+kT(n))$.


How to prove that the Myhill-Nerode equivalence classes for L are the same as for its complement?

Note that the Myhill-Nerode equivalences are also defined for non-regular languages, so constructing a finite state automaton will not help.

What is the definition of such a class? $x \sim_L y$ iff $xz\in L$ whenever $yz\in L$ (for any string $z$). How does that change when we consider the complement of $L$? We use basic logic: $P\Leftrightarrow Q $ iff $\lnot P\Leftrightarrow \lnot Q $.

$x \sim_L y$
iff  $xz\in L$ whenever $yz\in L$ (for any string $z$)
iff  (not $xz\in L$) whenever (not $yz\in L$) (for any string $z$)
iff  $xz\in \bar L$ whenever $yz\in \bar L$ (for any string $z$)
iff  $x \sim_{\bar L} y$.


How to make a "Secure by Design" client-server communication?

The short answer is: No, you can't verify what code is running on the client.  As a result, you should never trust what is running on the client.

You could use all sorts of hashes, but nothing prevents a malicious client from lying to you about its hash and telling you what you want to hear.  Asking the client to hash itself and tell you its hash would be like having airport security ask passengers "Are you a terrorist?" and then believing them when they say "No".

In principle this problem could be solved with trusted hardware on the client, such as a a TPM.  Currently, a TPM is about the only way to check that the client is running unmodified code.  However, in practice using TPMs for this has major issues that typically render it not deployable in practice for the purpose you have in mind.

Therefore, in practice the answer is basically "no, there's no way to check".  See https://security.stackexchange.com/q/72091/971 for an explanation why there is no way to do this without trusted hardware (like a TPM).  As a result, the standard mantra is "you can't trust the client".  See e.g., https://security.stackexchange.com/q/40378/971 for some discussion of alternative architectures don't rely on trusting the client.

For a partial explanation why TPM-based solutions are not really deployable in practice, see https://security.stackexchange.com/q/2459/971.

If you want to explore the TPM approach, see https://security.stackexchange.com/q/5570/971 and https://security.stackexchange.com/q/4008/971.  However, I don't recommend it as a promising avenue.  In the future, Intel will be releasing SGX technology, which might be a better way to achieve this -- but it has not yet been released, so it will be quite some time before you can count on all your clients to run on hardware that supports SGX.


Problem with determining the shape and direction of the Huffman Diagram

Huffman's algorithm is non-deterministic — at several junctures you have more than one admissible choice. For example, at the first step, you can merge either $c$ and $d$ or $c$ and $r$. As another example, you can choose which child is left and which is right arbitrarily. Any particular implementation of Huffman's algorithm has some tie-breaking rule which makes it deterministic, but any choice would lead to a minimum redundancy code, and the generic Huffman algorithm doesn't specify any specific tie-breaking rule.

Huffman's algorithm is guaranteed to produce a minimum redundancy code, but not every minimum redundancy code can be produced by an admissible run of Huffman's algorithm. See Gallager's classic paper Variations on a theme by Huffman.


The term first described by Horst Feistel (1973)

As the input moves through successive layers the pattern of 1's generated is amplified and results in an unpredictable avalanche.

It is rather very good naming. Consider a bit flip in the AES's input; It enters the first Sbox, then according to the design of the Sboxes of AES the output is different since they are invertible (actually they are also designed to have avalanche effect). Now say we have at least two different output bits, then the Sub-Bytes and MixColums will distribute the changes. Therefore in the first round, you will have 2 changes, in the next round you will have 4,.. and so on. As you can see the minimum change becomes larger and larger in each round. That is how an avalanche is working.
Note that we have $2^{10}$ changes in the last round for AES-128. Contradictory, no, since some changes will cancel each other and that part together with the key's action is unpredictable for our computing capabilities!
The blow picture was drawn by Feistel, which should tell the idea; One small change at the beginning and it is a big effect on the output.


Implementing addition for a binary counter

Well, surely there is.

As a first thing I would convert $k$ to its binary representation $\text{bin}(k)$. If $c$ is the current value of your counter then in order to perform $\text{add}(k)$ just update the counter by setting it to $\text{bin}(c)+\text{bin}(k)$.

If you don't know how to add binary numbers efficiently, think how you would have done it using pen and paper.

For small $k\in O(\log c)$ the repeated increment might be efficient though.


Number of cycles that arithmetic instruction takes for 25% improvement in performance?

Hint: You have 100 fruit: 70 Apples, 10 Lychees and 20 Bananas. You want to reduce the number of apples until you have only 75 fruit left. How many apples do you have to eat?


Is it possible to build any regular expression in a computer language with just 3 basic operators?

Regular expressions using only concatenation, alternation and Kleene star describe regular languages. In contrast, extended regular expressions available in modern programming languages can describe non-regular languages. For example, (.*)\1 describes the language $\{ ww : w \in \Sigma^* \}$, which is not even context-free.


You have to operate on the memory to do anything useful. Reading next instruction, getting variable to operate on or saving calculated value - all that requires accessing memory.


Nondeterministic finite state machine without any initial state possible

In my favourite definition a finite state automaton is specified as 5-tuple $(Q,\Sigma,\delta,q_0,F)$, where $Q$ is the finite set of states, $\Sigma$ is a (finite, nonempty) alphabet, $q_0\in Q$ the initial state, $F\subseteq Q$ the set of final states, and $\delta\subseteq Q\times\Sigma\times Q$ the set of transitions. In that definition we would have exactly one initial state.

It is however very well possible that, for reasons of symmetry, one specifies a set $I\subseteq Q$ of initial states. There you can have one, several, of no initial state.

Short answer: consult the book, lecture notes, or scientific paper you are using. They set the rules for the game. Not us, not wikipedia.


Prove that if for every vertex in $G[U]$ there is an edge in to every vertex in $G[V-U]$ then there is a path from every $u$ to every $v$

You can use a direct proof. There is no need to assume that the graph is connected.
Take any $u \in U$. We will construct a directed path $u_0\to\cdots\to u_\ell$ in which $u_\ell \in U$ has out-degree zero in $G[U]$, as follows. First, $u_0 = u$. Given $u_i$, if $u_i$'s out-degree in $G[U]$ is zero, then $\ell = i$. Otherwise, let $u_{i+1}$ be an arbitrary out-neighbor of $u_i$. Since $G$ is acyclic, the vertices $u_i$ do not repeat, and so the path must terminate eventually.
Similarly, for any $v \in V \setminus U$ there is a directed path $v = v_0 \gets \cdots \gets v_r$, where $v_r \in V \setminus U$ has in-degree zero in $G[V \setminus U]$. By assumption, there is an edge $v_\ell \to u_r$. Combining both paths with this edge, we obtain a path from $u$ to $v$.


Question on the properties of red black trees

The left subtree cannot be a chain of $n$ black nodes, since it breaks the red-black tree properties.

In the worst case scenario, the left subtree is a minimal black binary tree of  height $\log n$, while the right subtree is a full maximal binary tree of height $2\log n$.

The black height of the right subtree must be $\log n$ as well, therefore its maximal total height (including red nodes) is $2\log n$. Since it is a maximal binary tree, it has
$ 2^{2\log n}  = 2^{\log n^2} = n^2 $ nodes.


This reduces to showing $\binom{n}{f} = O(n^f)$.

In one variable the idea of an approximation being tight is pretty simple; you just see if the limit of the quotient goes to one.

In multiple variables there's no such thing as "the" limit.  There are limits along different curves.  Some may be tight and some may not be, but as long as the limit along one curve is tight there's no way of improving things across the board.

In situation at hand we have $$\binom{n}{f} = \frac{1}{f!}n(n-1)\ldots(n-f+1)$$.  For f small compared to n, the $(n-i) \approx n$.  If n grows a lot faster than k!, then it also blows out the k! term in the denominator as well.  So along a curve like this the bound is tight.

(It's also possible we're considering fixed k and just considering the growth as a function of n, in which case the $1/k!$ is just a constant factor.)


Use the same formula as you do for two's complement. First, compute the complement of the number by complementing all letters. Then add 1. Complementing works using the following table:
$$
0 \leftrightarrow F, 1 \leftrightarrow E, 2 \leftrightarrow D, 3 \leftrightarrow C, 4 \leftrightarrow B, 5 \leftrightarrow A, 6 \leftrightarrow 9, 7 \leftrightarrow 8.
$$
Example: starting with 0000BDDA, we first get FFFF4225, and after adding 1, we get FFFF4226.

Why does this work? Exercise.


The complexity class $\mathsf{NC}$ is a uniform class. There are constant size circuits which don't belong to $\mathsf{NC}$.

What does that mean? Most circuit complexity classes don't really make sense for individual circuits. A single circuit can't have polynomial size, or rather, this doesn't mean anything (every circuit has size at most $n^k$ for some $k$). Instead, when talking about a circuit belong to a complexity class, we are really talking about sequences of circuits. These sequences can be uniform – that is, can be generated by a Turing machine – or arbitrary. (In the uniform case, you can get different complexity classes by constraining the strength of the Turing machine.)

The complexity class $\mathsf{NC}$ consists of uniform circuits of polynomial size and polylogarithmic depth. Consider the following sequence of circuits: $C_n$ (with $n$ inputs) is either the constant 0 or the constant 1, depending on whether the $n$th Turing machine halts on the empty input. This sequence doesn't belong to $\mathsf{NC}$ (since it's not even computable), but all circuits have constant size.

In order to compare $\mathsf{NC}$ and polynomial size circuits, you have two options. Either you compare $\mathsf{NC}$ to $\mathsf{P}$, which is the uniform analog of polynomial size circuits, or you compare non-uniform $\mathsf{NC}$ to polynomial size circuits (a complexity class known as $\mathsf{P/poly}$). In both cases, it is conjectured that the two classes are different, but this hasn't been proved yet.

One way of separating $\mathsf{NC}$ from $\mathsf{P}$ would be to separate non-uniform $\mathsf{NC}$ from $\mathsf{P}$, that is, to give an example of a problem in $\mathsf{P}$ (say, some $\mathsf{P}$-complete problem) that cannot be solved using $\mathsf{NC}$-circuits. In the same way, you could prove that $\mathsf{P} \neq \mathsf{NP}$ by showing that $\mathsf{SAT}$ doesn't have polynomial size circuits. In both cases, you are actually trying to prove stronger claims, which are believed to hold.


Can you give an inductive definition to define the length of a list L?

In an inductive definition what you have to do is to find a base case and the inductive step.

In your case, suppose to have a list $L$ and let head be the first element and tail the rest of the list.

For example, if $L=[1,2,3,4,5]$:

head = $1$
tail = $[2,3,4,5]$

In order to understand the meaning you could consider writing a recursive function to compute the length of the list.

According to the answer

Basis: the length of an empty list is 0
Induction: the length of a list is 1+(length of tail(list))

This corresponds to the recursive function

function len(list L)
   if L is empty
        return 0
   else return 1 + len(tail(L))

Same for the second question:

function member(elem x, list L)
   if L is empty
       return false
   if head == x
       return true
   else return member(x, tail(L))

and this corresponds to say: X is a member of a list L if either

X is the head of the list or
X is a member of the tail of L.


How can the 4-bit page number and 8-bit offset as well as the page table be used to a answer a question like, "how big is each page"? etc

4 bits page number + 8 bits offset = 12 address bits : A[11:0]

A[7:0] selects an offset within a page
A[11:8] selects the page
1792 = 7*256 : A=0111_00000000
2304 = 9*256 : A=1001_00000000
2814 =11*256 : A=1011_00000000
1024 = 4*256 : A=0100_00000000

What is the problem? You get 8 address bits within each page. So what is the page size?


How does variance in task completion time affect makespan?

As $m = k \times n$, we can look at this in terms of $k$ and $n$ instead of $n$ and $m$. Let's say $T_i$ is the time it takes the $i$-th processor to finish its work.

As $n$ grows, the probability that $T_i$ = $5k$ (the processor was assigned only $T=5$ tasks) for some $i$ approaches $1$, so makespan being defined as $\mathrm{max}(T_i)$, $E[M]$ approaches $5k$.

For the second scenario this is $4k$ so increasing the number of processors makes the 4–2 split better.

What about $k$ — increasing the number of tasks per processor? Increasing $k$ has the opposite effect, it makes it less likely to have a processor with an unlucky set of tasks. I'm going home now but I'll come back to this later. My "hunch" is that as $k$ grows, the difference in $E[M]$ between the 4–2 split and the 5–1 split disappears, $E[M]$ becomes the same for both. So I would assume that 4–2 is always better except maybe for some special cases (very small specific values of $k$ and $n$), if even that.

So to summarize:

Lower variance is better, all else being equal.
As the number of processors grows, lower variance becomes more important.
As the number of tasks per processor grows, lower variance becomes less important.


Difference between $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ and $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $

Indeed, $abaaabbb \notin L_1$ because the string is not of the form $(a^nb^n)^m$ which is the repetition of a fixed string with the same number of $a$ and $b$.
The language $L_2$ is the Kleene closure of $\{a^nb^n \mid n\ge1\}$, consisting of all arbitrary concatenations of strings of the form $a^nb^n$. We can choose different strings of this form, and do not have to stick with the same one each time, like in $L_1$. Hence $L_2$ contains $abaaabbb$.
As for your original version of the question (now edited) it contained the notation $\{(a^nb^n)^+ \mid n\ge1\}$. I would not denote a language that way. The Kleene plus is a language operator, which takes a language (set of strings), and turns it into a language. By writing $\{(a^nb^n)^+ \mid n\ge1\}$ you get the set $(a^nb^n)^+$ within the set brackets, which can be called a "type error".


Deriving recursive definition from function specification

Your notation and understanding are pretty good.

It is easier to consider (xs:x) as the inductive case instead of (x:xs)

\begin{align}
\sum_{i:\ 0 \leq i < \#(xs:x)} &(xs:x).i * (i + 1)\\
&=\sum _{i:\ 0 \leq i < \#xs+1} (x:xs).i * (i + 1) \\
&=\sum_{i:\ 0 \leq i < \#xs} (xs:x).i * (i + 1)+\sum_{i:\ i=\#xs}(xs:x).i * (i + 1)\\
&=\sum_{i:\ 0 \leq i < \#xs} xs.i * (i + 1)+x*(\#xs+1),\\
\end{align}
where we assume that list index starts with 0.

If we denote the function by $f$, the above equality becomes
$$ f(xs:x) = f(xs) + x*(\#xs+1), $$
which is the recursive step of a recursive definition.

The base case, as you have indicated, is
$$ f([]) =  \sum_{ i:\ 0 \leq i < 0} [].i * (i + 1)  =  \sum_{i: \text{ empty set}}[].i * (i + 1) =0.$$

Exercise. Derive the following recursive formula of the same function $f$.
$$ f(x:xs) = f(xs) + t(xs)+ x, $$
where $$t(xs)=\sum_{i:\ 0 \leq i < \#(xs)} xs.i,$$
the sum of items in $xs$.


Assuming the number of data points is much larger than the number of buckets:

The theory answer: any universal hash function will suffice to ensure that the parts are roughly similar in size (on average, in expectation, over the random choice of hash function).

The pragmatic answer: any hash function that provides roughly equidistributed outputs is likely to suffice.  Thus, any hash function that doesn't suck will normally be fine in most cases (e.g., as long as the inputs aren't adversarially chosen and as long as the hash function doesn't have serious problems).


Set Intersection with asymmetric set sizes

If you have exactly one intersection to compute, building a hash table from $N_1$ and doing $N_2$ lookups goes through the same number of hash operations as building one from $N_2$ and doing $N_1$ lookups.


Is there a way to map a multi-variable structure onto a single range?

If you want to solve this for colors, there are many techniques that are appropriate in that domain.  But you say you aren't really asking about colors, so I'll treat it as an analogy and try to give an answer that is more general (but wouldn't be what I would recommend for colors):
It sounds like you want to cluster the possible values into multiple clusters.  I would suggest you read about clustering algorithms. You'll need to pick a "similarity measure" that measures how similar two structures are.  That is domain-specific and not something we can tell you; you'll have to pick it based on your knowledge of the specific application domain.


Smallest number close to 0 in IEEE754 (64bits)?

It's not true that when all components of the exponent are 0 then the number must represent 0. A (normalized) floating point number is composed of two parts: sign, exponent, and mantissa. The value of the number is
$$ \text{sign} \times 1.\text{mantissa} \times 2^{\text{exponent} + \text{base}}, $$
where the sign is $\pm 1$ (though encoded as a bit), and $\text{base}$ is a constant which depends on the format.

As you can see, $0$ cannot actually be represented at all! Some numbers, like zero, infinity, NaN and denormalized numbers have special representations. Zero, for example, is represented in IEEE 754 (the standard format) using zeroes for both mantissa and exponent.

In IEEE 754, an exponent of zeroes represents a denormalized number. In such numbers, instead of 1.mantissa we have 0.mantissa, and this allows representing numbers which are closer to zero (calculate and see!).


Nandgame--I am not sure I understand the Data Flip-Flop specifications

I have worked 20 years as FPGA logic designer but I stop at task Data Flip-Flop!
It is possible to build Data Flip-Flop. Two latches is required (sequential connection). First latch stores input data when st&!cl, second latch stores result of first latch to output when st&cl. Unbeliveable! Thanks to google...


Clarification on an Hopcroft book DFA minimization example

It looks like you missed the paragraph for induction right before the Example 4.19 or figure 4.9 and the repetitive application of that induction.

INDUCTION: Let $p$ and $q$ be states such that for some input symbol $a,$ $\ r =\delta(p,a)$ and $s = \delta(q,a)$ are a pair of states known to be distinguishable. Then $\{p, q\}$ is a pair of distinguishable states.

That induction is all we employ to fill the table of state inequivalences besides the fact that every accepting state is distinguishable from every non-accepting state. (The fact holds because the empty string distinguishes them.) That is, we will never check strings that are more than one symbol long.
For example, to find whether $E$ and $G$ are distinguishable, we need to just check either $0$ or $1$ distinguishes them. Assuming $E$ and $F$ are distinguishable, since on input $1$, $E$ go to $F$, while $G$ goes to $E$, we know $E$ and $G$ are distinguishable.
You might ask, how do we know $E$ and $F$ are distinguishable? By the same procedure. "Since $\{C, H\}$ is distinguishable, and states $E$ and $F$ go to $H$ and $C$, respectively, on input $0$".
Note that we may not be able to determine whether $E$ and $G$ are distinguishable right from the start by this procedure. We will try the pair $\{E,G\}$ again and again together with other pairs until we cannot find more distinguishable pairs. Although we may have to check the same pair for many times, the number of times is bounded by the number of distinguishable pairs and each time we will check just 2 possible distinguishing strings, $0$ and $1$. We have avoided testing "all the possible strings", which are infinite.
You may want to look at another explanation of Hopcroft's algorithm such as this Wikipedia article or the excellent illustration at tutorialspoint.


An efficient method to compute a minimum set of sets that form the union of these sets?

In case $S_i$ sets are finite your problem is reduced to the Set Cover problem which is NP-complete. You can also attack this problem by any approximation algorithm, e.g. Greedy algorithm, or by using Linear programming.


What is the theoretical result of flattening a list containing only itself?

From a mathematical point of view, this is impossible: there is no such a thing as a set containing itself (in normal logic sense) or a vector who has itself as an element, so this question doesn't really mean anything outside the realm of using pointers in a list
BUT, on a second thought: I might be able to formulate what "flattening" is if you allow me to define things however I want.
Lets say our world is some graph $G$, nodes in it would be elements, and an edge $(v,u)$ would mean that the element $v$ contains the pointer to $u$. Then, in those terms, the array [[5,6],3,[7]] might look like this:

Flattening the graph in this sense means to take every non-direct child of the root node (the array's node) and make it a direct child of it.
Then, your array X looks like this:

And when you flatten it you would remain with the exact same graph, and therefore in this sense when you flatten X you would get simply X itself.
However, this is truly meaningless because it's only by the definition I just made up: you could have defined it in another way and it would have resulted in something else maybe!


Counting words that satisfy SAT-like constraints with BDDs

Yes, you can use a BDD to solve this, but BDD's aren't magic: they don't magically allow you to solve a #P-complete problem efficiently.  You can use BDD's to solve this, but the resulting solution might be highly inefficient.

How do you use BDD's to solve this?  Broadly, you build a BDD that represents all strings that satisfy the property, and then you count how many strings are accepted by this BDD.

To learn how to build a BDD that accepts all strings that satisfy the property, I suggest that you study basic material on BDDs.  The key property that's relevant here is that given BDDs for the sets $S,S'$, it is easy to construct a BDD for the set $S \cup S'$.  So, you build a BDD for the set of strings that are accepted by each row of the matrix, and then you take their union to get a BDD for the union.  Beware that the resulting BDD could have exponential size.

Once you have a BDD, it's easy to count the number of strings accepted by a BDD.  It's an especially simple application of dynamic programming: for each node $n$ in the BDD, you count the number of paths from $n$ to some leaf.  These numbers can be filled in by visiting the nodes in bottom-up order, and using dynamic programming.

There's nothing fancy here.  Once you are familiar with BDD's, everything here should look bog-standard.  So, if this looks mysterious, I recommend you spend some quality time with a textbook that explains how BDD's work.

Other algorithms: you could also use any algorithm for #SAT.  There are off-the-shelf algorithms and tools for computing #SAT.  It's straightforward to translate your problem to an instance of #SAT, and then apply one of those tools.  See, e.g., https://cstheory.stackexchange.com/q/1295/5038, Is there a sometimes-efficient algorithm to solve #SAT?, https://cstheory.stackexchange.com/q/18135/5038.


Why system calls via interrupts are slow and thus we have SYSENTER/SYSEXIT instructions?

There is the general rule about interrupts being slow, and the particular case of x86 CPUs.

x86 have had several ways to enter kernel mode : Call gates, interrupts. They are complex, microcoded instructions, requiring many register save operation and protection checks. SYSENTER/SYSEXIT are just optimised methods : For example, since the 80286, 4 protection levels were available, but rarely used (except, IIRC, by OS/2 ?) : SYSENTER/SYSEXIT support only ring 0 (user) to ring 3 (kernel)
On many instruction set architectures, software interrupts are used to enter kernel mode from user code. These instructions can be optimised, but, in the simplest implementation, they are handled like external hardware interrupts or MMU faults. They are slow because the pipeline must be flushed, prefetched instructions must be discarded, before jumping to the interrupt vector.


Yes.  You can build a data structure with the property that each operation takes at most $O(\log n)$ time.  Thus, your overall running time for doing $n$ operations will be $O(n \log n)$ instead of $O(n^2)$ -- a significant improvement.

As a warmup, imagine that the tree $T$ was balanced and in particular had depth $O(\log n)$.  Then it is immediate to see how to achieve $O(\log n)$ time per operation; your second approach suffices.  In particular, you set a flag in each node that is a split point.  Since the tree has height $O(\log n)$, walking up the tree takes $O(\log n)$ time.

What if $T$ isn't balanced?  We can generalize that answer.  Number the leaves of $T$ with the numbers $1,2,\dots,n$, from left to right.  Now build a new balanced binary tree $T^*$ with leaves $1,2,\dots,n$.  The shape of $T^*$ will be unrelated to the shape of $T$, but by construction the depth of $T^*$ will be $O(\log n)$.

Now, we store flags inside $T^*$ instead of inside $T$.  In particular, we will store a flag inside a node $v \in T^*$ if (1) the entire subtree of $v$ (including $v$ itself) is in the same partition, and (2) the parent of $v$ is in a different partition from $v$.  The flag identifies the partition that $v$ is in.  To find the partition that a node is in, you just walk up $T^*$, which takes $O(\log n)$ time.

And here is the key part.  When you split a partition, you can update the flags in $O(\log n)$ time.  In particular, when you split off a subtree of $T$, that corresponds to a set of leaves that are in a consecutive interval (namely, leaves numbered $i,i+1,i+2,\dots,j$ for some $i,j$).  But over in $T^*$, every consecutive interval is covered by a (disjoint) union of at most $O(\log n)$ subtrees of $T^*$.  So, you update the flags of the roots of those subtrees to reflect the new partition they are in.  That requires only $O(\log n)$ updates, so can be done in $O(\log n)$ time.


Can a Red Black tree be constructed of only black nodes using RB insert only?

Properties of Red Black Tree:

0) Every node is black or red. Ok, no problem.

1) Root is black. Ok, no problem.

2) All leaves (empty nodes) are black. Ok, no problem.

3) Every red node must have two black childs. Ok, no problem.

4) Every path from any node to leaf has equal number of black nodes. It seems problematic.

So now comes problems: When you insert element it's color is red. (In fact this not comes from properties but observation that adding red node does not violate $4$th rule, so it is easier to implement).

So for start you add one element, let me say 10.
It is black root. Ok.

Now You add 13. It must be red, otherwise it violates rule 4.

Now you add 19. Depending on implementation you can leave all black, or recolor.

Now adding 12 gives recoloring and comes red.

And after several numbers

And now it starts nightmare, as you should propagate changes from one side of tree to another convincing somehow that you will change everything to black after insertion.

Basically I asked you about rules to obey, as it comes to mind that with $4$th can be fulfilled only in perfectly balanced trees.

So to answer your questions:

No you cannot with common implementations of RBT, but extending balance operation to recolor when it is possible - it does not violate rules, so it is possible. Also with extension that whenever there is $n = 2^k - 1$ nodes, restructure it to perfectly balanced tree and recolor everything to black, it would be also possible.

I did firstly answer "no" as purpose of balancing operation is to guarantee bound on worst case search / insert, and such extensions comes at price of time complexity. It does not violate rules, but is not implicitly implemented in standard RBT.

Given only root, you have it. Given three nodes inserted in order with implementation changing all to black (rather rare case and counterproductive), you can. But this is last one that is without deletions possible.

When you are about to insert element and want all tree to be black that would mean there is violated rule $4$ (so not possible) or you have to rebalance tree, which would recolor nodes, so it is not pure black anymore.

With deletions on the other hand ;)


How to generate a degree sequence of a degree distribution

As you mention, the degree distribution follows a power law if the number of nodes of degree $k$ is roughly $N \times C^{-1} k^{-\gamma}$, where $C = \sum_{k = 1}^\infty k^{-\gamma} = \zeta(\gamma)$ (in your case, $C \approx 1.34$). Plugging in your numbers, we want roughly

75 vertices of degree 1.
13 vertices of degree 2.
5 vertices of degree 3.
2 vertices of degree 4.
1 vertices of degree 5.
1 vertices of degree 6.
1 vertex of degree 7.

This gives a total of 98 vertices. You can make it exactly 100 vertices in many ways — I'll let you think of one. Don't forget that the sum of degrees should be even.

The (potential) problem is that not every sequence is the degree sequence of a graph. Sequences which are realized by some graphs are known as graphic sequences, and are determined by the Erdős–Gallai criterion. If the resulting sequence doesn't satisfy this criterion, we're in trouble. However, I don't expect it to happen in your case. Indeed, my suggestion above (with 98 vertices) is graphical.


Whether same output is obtained for the two queries

where Eid field is empty.

What do you mean by "empty"? Perhaps you mean 'null'?

What words exactly does your "solution manual" use? "empty" or "null"?

If the Eid field is CHAR there could easily be a row with Eid "empty" -- that is: zero length, or containing only space characters. count(*) and count(Eid) return the same value in that case.

If the Eid field is NULLABLE there could easily be a row with Eid null. count(*) will include that row, whereas count(Eid) will not.

Usually fields in keys are expected to be NOT NULL. Some vendors' implementations of the SQL standard insist on NOT NULL. But some don't. It is good practice to make key fields NOT NULL. Presumably your manual is getting you to think about why.


L(M) ⊂ L(M') can be proved as below:

Suppose a string 'w' ∈ L(M') .Since it is given that F is a proper subset of F' , there exists a state q1 such that
q1 ∈ F' but not to F.
Since the transition function is same for both the DFAs, hence there is a transition possible as below:
δ(q0, w) = q1which means the state change takes place from the initial state to the state q1 on reading the input symbols from the string 'w'.

Since q1 ∈ F' but not to F, we can say that 'w' does not belong to L(M).
On the same lines it can also be proved that any string in L(M) is also present in L(M'), thereby proving the relation.


GRAMMAR FOR THE LANGUAGE:{a^n b^n c^n/n>=1}

S->abc|A

A->aABc|abc

cB->Bc

bB->bb

FOR EXAMPLE:INPUT STRING aaabbbccc when n=3

S->A

->aABc

->aaABcBc (A->aABc)

->aaabcBcBc   (A->abc)

->aaabBccBc   (cB->Bc)

->aaabBcBcc   (cB->Bc)

->aaabbcBcc   (bB->bb)

->aaabbBccc   (cB->Bc)

->aaabbbccc   (bB->bb)


DES encryption - what happens if all sub-keys are the same?

It will make the algorithm insecure.

It will be become vulnerable to slide attacks.

It will make encryption become equivalent to decryption, which is a weakness.  This is sometimes called a "weak key"; with your scheme, every key will be "weak".

It will also reduce the keyspace to 48 bits, which is too small to be secure.


Constraint satisfaction problem: solve system, then evaluate whether many additional constraints are satisfied one at a time

If the constraints you have are of the form $a < b$ and $a=b$ (i.e., only unconditional inequality constraints), you can model them with a directed graph: each node represents a variable, and an edge $v \to w$ corresponds to the inequality $v < w$.  Then you can answer queries by doing a straightforward reachability check.  (If you see the equality $v=w$, then merge the two vertices $v,w$ into a single vertex.)

When you add conditional equality constraints, the problem becomes NP-hard.
Proof of NP-hardness: I will show a reduction from 3SAT to your problem.  Suppose we have a 3SAT formula $\varphi$ on variables $x_1,\dots,x_n$.  Consider a single $C_i = \ell_i \lor \ell_j \lor \ell_k$, where $\ell_i,\ell_j,\ell_k$ are three literals (e.g., $\ell_i$ is either $x_i$ or $\neg x_i$, etc.).  We will translate this to the constraints
$$\begin{align*}
\ell_i \implies &y_{i0} > y_{i1}\\
\neg \ell_i \implies &y_{i0} < y_{i1}\\
\ell_j \implies &y_{i1} > y_{i2}\\
\neg \ell_j \implies &y_{i1} < y_{i2}\\
\ell_k \implies &y_{i2} > y_{i3}\\
\neg \ell_k \implies &y_{i2} < y_{i3}\\
\end{align*}$$
$$y_{i0} > y_{i3}$$
Notice that if at least one of $\ell_i,\ell_j,\ell_k$ are true, then these seven constraints are simultaneously satisfiable; but if $\ell_i,\ell_j,\ell_k$ are all false, then they are not satisfiable.  So, we translate each clause of $\varphi$ into several constraints as above, obtaining a large system of constraints.  Then this system has a satisfiable solution if and only if $\varphi$ is satisfiable.
In conclusion, testing satisfiability of your kind of constraints is NP-hard.  It follows that answering queries is also NP-hard (answering a query is the same as testing satisfiability of the constraints plus the query).  Consequently, you shouldn't expect any algorithm that is both efficient and always correct.
If you have to solve it in practice, you could try applying a SAT solver.  Add boolean variables $s_{b,c}$ to represent $b<c$; then you can translate each constraint into a clause.  For instance, $b<c$ translates into $s_{b,c}$, and $i \implies b<c$ translates into $\neg i \lor s_{b,c}$.  Finally, add clauses that enforce the consistency of the $s$'s, i.e., $\neg s_{a,b} \lor \neg s_{b,c} \lor s_{a,c}$ for each $a,b,c$.  Now answering a query amounts to conjoining the query and testing satisfiability of the resulting SAT formula, which you could do with an off-the-shelf SAT solver.  Some SAT solver allow you to "push" a clause, test satisfiability, and then "pop" the clause.


Role of Term Constants in Simply Typed Lambda Calculus

As per Sam's request, I rephrase my comment as an answer.

Constants play an important role in λ-calculi (not just the simply typed variant).

They are often convenient: even though we can usually represent our target data using
$\lambda$-terms without constants this tends to be unwieldy. For example
integers
directly by some variant of an unary encoding, e.g. the Church encoding has $$\lambda g x. \underbrace{g ( g ( ... g ( g\ x ) .. ) ) }_{n}$$ as representation of $n$. That leads to cumbersome, unreadable terms. With constants we can  do arithmetic with 0,1,2,..., and +,−,∗,...
In a typed calculus, we need  constructors for types, and constants play this rule. E.g. 0,1,2,..., or +,−,∗,...
for the type of integers, true,false... or ∨,∧ for booleans etc.

Note that the STLC was born with constants : Church's original
formulation contains constants $N_{oo}$, $A_{ooo}$, $\Pi_{o(o\alpha)}$
as well as $\iota_{\alpha(o\alpha)}$, representing negation,
disjunction, universal quantification and the selection operator,
respectively.


Why aren't existential types implemented in any mainstream language?

OCaml's idea of modules roughly correspond with existential types ;)

Let's set up some rough semantics in order to frame this correspondence properly. First, I'll give the intro/elimination rules for existential types (I'll only use a variable $\to$ type context $\Gamma$ for the sake of simplicity here):
$$
\frac{\Gamma \vdash e\{\alpha\mapsto \tau\} : \sigma\{\alpha\mapsto \tau\}}{\Gamma \vdash [\tau, e] : \exists \alpha. \sigma} ({\rm Pack}) ~~~~~~~
\frac{\Gamma \vdash e : \exists \alpha.\sigma ~~~ \Gamma, x:\sigma \vdash e' : \tau'}{\Gamma \vdash {\rm let} ~ [\alpha, x] = e ~ {\rm in} ~ e' : \tau'}({\rm Unpack})
$$
where $e\{\alpha \mapsto \tau\}$ substitutes all occurrences of the type variable $\alpha$ with the concrete type $\tau$. In practice, we will also decorate the packed form with its existential type in order to disambiguate the semantics.

Operationally, we have the context reductions:
$$
\frac{e \Downarrow v}{[\tau, e] \Downarrow [\tau, v]} ~~~~~~ \frac{e \Downarrow v}{{\rm let} ~ [\alpha, x] = e ~ {\rm in} ~ e' \Downarrow {\rm let} ~ [\alpha, x] = v ~ {\rm in} ~ e'}
$$
which corresponds to the reduction strategies that reduces the expressions in the existential packages and the expressions to be unpacked.

Finally, we have the extensional $\eta$-reduction rule:
$$
\frac{}{{\rm let} ~ [\alpha, x] = [\tau, v]_{\exists \alpha. \sigma} ~ {\rm in} ~ e \to e \{\alpha \mapsto \tau, x \mapsto v\}}
$$

So for example, the program
\begin{align*}
{\rm let} ~ [\alpha, x] &= [{\rm int}, (0, {\rm succ})]_{\exists \alpha. \alpha \times (\alpha \to \alpha)} ~ {\rm in} ~ ({\rm snd} ~ x : \alpha \to \alpha)({\rm fst} ~ x : \alpha)\\
&\to^{\eta} ({\rm snd} ~ (0, {\rm succ}) : {\rm int} \to {\rm int})({\rm fst} ~ (0, {\rm succ}) : {\rm int}) \\
&\to^* {\rm succ} ~ 0 \\
&\to^\beta 1
\end{align*}

This exact idea is present in OCaml's concept of modules, save that the packed type must be a record (but which can be made to be isomorphic to any other OCaml type). For example, the creation of an existential type is done through the module type keyword:

module type Bundle =
sig
  type α
  val data : α * (α -> α)
end

This signature corresponds to the existential type $\exists \alpha. \alpha \times (\alpha \to \alpha)$. We can witness an inhabitant of this type by instantiating it with the struct keyword:

module BundleInt : Bundle = struct
  type α = int
  val data = (0, (+) 1)
end

which corresponds to the pack/intro $[{\rm int}, (0, (+) 1)]_{\exists \alpha. \alpha \times (\alpha \to \alpha)}$. Unfortunately, there is no explicit ${\rm let} \dots$ elimination form, but something like open BundleInt is equivalent to let [α, data] = BundleInt in ... where α and data are specified in the creation of the module type Bundle.

So while module types aren't exactly the same as your traditional existential types (the variables to be bound are explicitly pushed into the intro-form rather than in the elimination-form), their expressiveness are the same.


Find minimum number 1's so the matrix consist of 1 connected region of 1's

If you model your problem with graphs, Your problem is like Steiner Tree problem:

See here for simplest possible definition.

  Given a weighted graph in which a subset of vertices are identified as
  terminals, find a minimum-weight connected subgraph that includes all
  the terminals.

As you can see it's NPC in general, but in your case your graph is grid graph, may be you can find good solution for it, but for your current example (when terminals are in boundary) you can see Steiner tree in grid graphs paper.

Anyway there are excellent heuristics for Steiner Tree problem, you can apply similar approach to your problem.

P.S: You can assume neighbor 1s are connected nodes, after that you can contract their edges to make a new graph, your new created graph is planar, and if you could solve the Steiner Tree for it you can solve your problem, but may be there is a good solution for your problem which is independent from Steiner Tree.


What does $\mathbf{Q}^+$ mean in approximation texts?

I'm going to say yes, positive rationals, because:

That's what it means throughout math literature.
That's a sensible domain for a cost function. It would possibly be a different algorithm problem if "negative" cost were legal. Furthermore real numbers introduce questions of representation and comparing them, so while mathematicians or economists often consider real numbers for quantity, computer scientists are more cautious.
There is no front or back matter indicating otherwise.


How to prove Exact cover problem is NP Complete using Vertex Cover problem?

You can reduce from vertex cover in cubic graphs since it is known to be $\textrm{NP}$-hard. Let $G=(V,E)$ be the graph in the instance of vertex cover and, for $v \in V$, call $E_v = \{ (v,u) \mid (v,u) \in E \}$ the set of edges incident to $v$ in $G$.

Construct an instance of the exact cover problem as follows:

The elements to be covered are those in $E$.
There are $7$ sets $S_1^v, \dots, S_7^v$ for each vertex $v \in V$, namely those in $2^{E_v} \setminus \{ \emptyset \}$.

If there is an exact cover $C$ for this instance, then there is a vertex cover of $G$ of size at most $|C|$, namely $\{ v \in V \mid \{S_1^v, \dots, S_7^v\} \cap C \neq \emptyset\}$.

If there is a vertex cover $C$ of $G$, then there is an exact cover of size at most $|C|$. Arbitrarily assign each edge $(u,v)$ of $G$ to one of the vertices in $\{u,v\} \cap C$. For a vertex $v$, let $A_v$ be the set of edges assigned to $v$ and notice that if $A_v \neq \emptyset$ then $A_v = S_i^v$ for some $i \in \{1,\dots, 7\}$. The sought exact cover is then $\{ A_v \mid v \in V \wedge A_v \neq \emptyset \}$.

To conclude the proof you just need to observe that exact cover belongs to $\textrm{NP}$ since the cover itself is a certificate that can be checked in polynomial-time.


Voronoi diagram algorithm with non-euclidean metric

It depends on the metric and your sites. There is a framework called abstract Voronoi diagram that allows you to compute Voronoi diagrams for well-behaved instances. In order to define what well-behaved means you have to give certain guarantees for the bisecting curves defined by your sites and your metric (for example two such curves intersect only in a finite number of points). The exact requirements might differ slightly depending on the paper you read.

If your problem is a abstract Voronoi diagram, then you can compute it with (a variant) of the randomized incremental construction due to Clarkson and Shor - see for example here. Then everything boils down to computations with the bisecting curves.

Note that there is quite some literature about these Voronoi diagrams and also recent progress has been made. I would advice you to go through this.


How to treat $\epsilon$ and '$' in top-down predictive parsing (predict table)?

$\epsilon$ is a terminal symbol

No.  $\epsilon$ is the empty string, i.e. no symbols at all.

  However, I've somehow interpreted that I could/should add '$' as a terminal symbol as well.

Yes, $ is the special symbol that marks the end of input, and you may have to do things at that place and when you want to go past it, you are done (or in situation of error for LR parsing if the stack is not empty).

  The rules given here also treat '$' and ϵ as if they were separate:
  http://www.jambe.co.nz/UNI/FirstAndFollowSets.html

Considering $\epsilon$ as a symbol to be put in $FIRST$ could be an worthwhile implementation trick instead of computing $NULLABLE$ separately (I haven't tried it, at first sight it seems to break useful properties and to add as much complexity as it removes, see the point 4 in the computation of $FIRST$), but it is nothing more than an implementation trick.


The set cover is not a decision problem, so it doesn't necessarily have a certificate.  Rather, it is an optimization problem.

To make it a problem in NP (a decision problem, with a certificate), you need to apply the standard trick to convert an optimization problem to a decision problem: introduce a budget.  Thus, the decision budget is: given a collection of sets and an integer $k$, determine whether there exists a subset of $\le k$ sets whose union is all of $\{1,\dots,m\}$.  That is a decision procedure, and does have a certificate: the subset of size $k$ is the certificate.

See also Optimization version of decision problems and standard textbooks.


Space and time complexity of $L = \{a^nb^{n^2} \mid n≥1\}$

Your confusion stems from a double use of $n$. Let's write $L$ differently:
$$
L = \{ a^i b^{n-i} : n-i = i^2, i \geq 1 \}.
$$
Here $n$ is the input length. It should be clear that the space complexity is $O(n)$.

Your first estimate just translates to a space complexity of $O(i^2) = O(n)$, since $n = i^2 + i$.


Which element is at its final position after the partitioning step in Quicksort?

The details depend on the partitioning method used, but usually the pivot ends up in its final position.

That follows from the second and third statement, by the way: all elements smaller than the pivot are to the left of it, and the larger to the right. The pivot is in between, and that is clearly its final position in the sorted array.

That the second and third statement hold is the central property of the partitioning method used.


Closed form of recurrence with two inputs

The candle burning rules are as follows: if you have c>=m candles, you can remove (m-1) of them and score m points while doing so. If you have fewer than c<m candles, then you score c points and are then done.
The total number of points you can score are then the points you score at the end (c % (m-1)), and the number of points you score before then (m * (c // (m-1))).


What is the difference between Cased-based Reasoning and Rule-based reasoning?

As said in the comments, there may be a part of subjectivity in the answers to this question.

Yet, I think it is fair to say that case-based reasoning mostly belongs to what is often called transductive methods, while rule-based (as well as neural networks and most statistical models) models mostly belong more to what is often called inductive approaches.

In short:

Transductive methods will not try to induce a generic model from your past observations/experiences, but will simply try to predict/find the answer of a new problem by looking at past experiences. This means you have to maintain a memory of past experience, and then select the most adequate one to answer your new problem. The most well-known representative of such approaches is probably K-NN.
Inductive approaches will try to induce a "compact" model from your past observations/experiences, and to generalise (make an induction) from those. Once this is done, you can forget your past experiences and only use your learned model to make prediction.

The parallel you can make is between looking up a table of stored input/output values (e.g., to get a p-value), which is transductive, and using a mathematical formula to compute a new prediction, which is inductive.

Lastly, it should be noted that the way you build your model when performing induction largely depends on your applications, available knowledge and needs (there are certainly ways to learn rule-based systems from data).


$\lambda$-calculus, is there encoding of for or while?

Sure! Let me show how to encode FOR using an example.

Suppose we want to translate a simple factorial FOR program

x := 1
for i := 1 to N do
   x := x * i

We rewrite it as

x := 1
i := 1
repeat N times
   x := x*i
   i := i+1

then we put all the variables we use in a tuple (a pair suffices, here)

(x,i) := (1,1)
repeat N times
   (x,i) := (x*i, i+1)

This effectively applies the function $\lambda\langle x,i \rangle. \langle x*i , i+1 \rangle$ to the initial pair $\langle 1,1 \rangle$ for $N$ times.

Since $N$ can be represented as a Church numeral, we get

$$
N (\lambda\langle x,i \rangle. \langle x*i , i+1 \rangle) \langle 1,1 \rangle
$$

The above syntax uses a few things beyond the plain lambda calculus. Numbers and arithmetic can be made precise using Church numerals. Pairs also have their own Church encoding:

$$
\langle x,y \rangle \equiv \lambda k.kxy
\qquad
\lambda \langle x,y \rangle . M \equiv \lambda z. M\{zT/x, zF/y\}
$$
where $z$ is a fresh variable, $T = \lambda ab.a$ and $F = \lambda ab.b$.

If you have more than two variables, you can generalize the above encoding to tuples, or simply represent tuples as nested pairs.

WHILE is best dealt with using recursion: instead of

while p(x,i) do
   (x,i) := f(x,i)

where p is a predicate and f is some (partial) function, we can use something like

def recFun(x,i):
   if p(x,i):
      return recFun(f(x,i))
   else:
      return (x,i)

In the lambda calculus, recursion is obtained using a fixed point combinator, e.g. Church's $Y$ or Turing's $\Theta$. We get something like

$$
Y (\lambda r . \lambda \langle x,i \rangle . {\sf if}\ p x i\ {\sf then }\ r(f \langle x,i \rangle)\ {\sf else}\ \langle x,i \rangle)
$$

where ${\sf if}\ b\ {\sf then }\ t\ {\sf else}\ e \equiv b t e$ assuming booleans are Church encoded.

Also note that WHILE is (strictly) more powerful than FOR. Every FOR can be encoded as a WHILE, so this encoding technique can also be used for FOR.


You must be able to verify in deterministic polynomial time that the certificate is correct.

If your certificate for SAT is a truth assignment, you can verify that it's a satisfying assignment in deterministic polynomial time, by substituting the truth values of the variables and simplifying the expression. However, if your certificate was just "It's satisfiable, honest!", then you would only be able to verify that if you could solve SAT in P, which you probably can't. The certificate has to be a proof that the string is in the language, not just a claim that it is.

Indeed, if it was enough to just claim that the string is in the language, then every language would be in NP!  For example, the certificate version of the halting problem would be just the set of all strings "$\langle M, w\rangle\text{ It halts, honest!}$" for all machines $M$ and inputs $w$ such that $M(w)$ halts, and all strings "$\langle M,w\rangle\text{ This one loops - too bad!}$" for all machines $M$ and inputs $w$ such that $M(w)$ doesn't halt.


Why are word sizes in modern CPU’s a power of 2?

There is no good reason really. Having 12/24/48/96 bit would have been much more useful.

Historically, if we had had 12 bit bytes, then color graphics storing 1 byte per pixel would have had 16 different values for red, green and blue components, and we would never have suffered the madness of color palettes in graphics hardware.

Nowadays, you could store Unicode codepoints usually in a 12 bit byte, and sometimes using two 12 bit bytes.

48 bit pointers would still be plenty (enough to address 256 Terabyte of RAM, but with 12 bits per byte, so this would actually equivalent to 384 Tera octets).

48 bit floating point is enough for most purposes (where 32 bit floating point isn't).


How do I represent this regular expression in regular grammar?

They are equivalent in the sense that every language that can be represented with a regular expression, can be represented with a regular grammar; and vice versa.
Also, you can convert any regular grammar to a regular expression that generates the same language, and vice versa.


Linear time algorithms on regular graphs

We usually analyze algorithms on the RAM machine model, in which each operation on a machine word has unit cost. A machine word consists of $O(\log n)$ bits, where $n$ is the bit-size of the input, or some other equivalent property. Thus representing a $k$-regular graph takes only $O(n)$ machine words, so there is no contradiction.


What is the recurrence form of Bubble-Sort

Bubble sort uses the so-called "decrease-by-one" technique, a kind of divide-and-conquer.
Its recurrence can be written as

$$T(n) = T(n-1) + (n-1).$$


Can data be compressed to size smaller than Shannon data compression limit?

Actually I don't fully understand this algorithm or the Shannon limit very well, I just know it's the sum of the probability of each character multiplied by log2 of the reciprocal of the probability.

Herein lies the crux. The Shannon limit is not some universal property of a string of text. It is the property of a string of text plus a model that provides (possibly context-dependent) probabilities of symbols. It tells us how well that model could compress the text, assuming the model is accurate.

If you use one model to compute the Shannon limit and then a different model to compress, if the second model is more accurate you can beat the original Shannon limit you had computed, but that's not really relevant.


Potential function binary heap extract max O(1)

Try the following:

The weight $w_i$ of an element $i$ in the heap $H$ is its depth in the corresponding binary tree. So the element in the root has weight zero, its two children have weight 1 and so on. The you define as potential function

$$\Phi(H)=\sum_{i\in H}2  w_i.$$

Let us now analyze the heap operations. For insert you add a new element add depth $d$ at most $\log(n)$. This increases the potential by $2d$, and can be done in $O(1)$ time. Then you "bubble up" the new heap element to assure the heap-property. This takes $O(\log n)$ time and leaves $\Phi(H)$ unchanged. Thus the costs for insert are $O(\log(n)+\Delta(\Phi(H)))=O(\log n)$.

Now consider the extractMin. You take out the root and replace it by the last element in the heap. This decreases the potential by $2\log(n)$, thus you can afford to repair the heap property, and therefore the amortized costs are now $O(1)$.

If you have a general question for the potential function you should pose this as a different question.


Trying to Classify MNIST where pixels are shuffled with a seed.Why is it not working?

A good indication, although quite rough, if an algorithm is capable of solving a task (especially pattern recognition tasks) is to check if humans can. We evolved to be quite good at it.

Obviously, that might not always be true. But in your case, by shuffling you loose all the structure of the data. The only possible feature your ML algorithm can use is the number of pixels set vs unset (or the pixel values, for grayscale images), thus basically losing all the structure. The problem is that this is a bad feature since there is little correlation between the number of pixels set and the digit. There is no pattern left, and any attempt to learn a pattern is doomed to fail. Thus, your algorithm may:

try to learn a pattern where there is none
not have enough features to do the classification

or a combination of the 2.


Hint: Let $L$ be the language consisting of a description of a Turing machine (bounded by $\#$ on both sides) followed by a terminating computation (both description and computation are over $\{0,1\}$). What is the language $\mathit{subwords}(L) \cap \#\Sigma^*\#$?


Clarification on halting predicate computability

Let's walk through the proof given by [Davis94].  I am familiar with this text and have it in front of me.  The HALT predicate is defined:

$$
HALT(x,y) \Longleftrightarrow \text{program number $y$ eventually halts on input $x$.}
$$

Given this defintion of HALT, don't worry about how such a program would be defined.  It is not important.  Just assume that HALT exists, that it works, and that this is what it does: It uses $y$ (a Gödel number -- see Section 8 of Ch. 3) which represents a particular program, and $x$, an input to that program, and tells us if that program halts when it is run with that input.  It can do this for any program, with any input.

Now, let's define a new program called $P$:

$$
[A]~\text{IF}~HALT(X,X)~\text{GOTO A}
$$

Look at how we are using HALT here: we are asking "Does program X halt when given an input of X (itself)?"  And if it does halt, we loop infinitely -- creating a program that does not terminate -- a program that does not halt.  In other words:

$$
\psi_P^{(1)}(x) =
\begin{cases}
\text{undefined} & \text{if} & ~~~~HALT(x,x) \\
0 & \text{if} & \sim HALT(x,x)
\end{cases}
$$

Let's pause and answer your first question about $\psi_P^{(m)}$ being undefined: this is part of the definition given in Section 4 of Chapter 2: $\psi_P^{(m)}(r_1,...,r_m)$ is undefined if $P$ never terminates.  And our program never terminates when $HALT(x,x)$ is true because we have written it that way, it loops infinitely.  As to your second question about the default output of 0: this happens when the program $P$ does terminate.

Now let the Gödel number of our new program $P$ be $y_0$.  This means that

$$
HALT(x,y_0) \Longleftrightarrow ~ \sim HALT(x,x).
$$

(we are taking the left side from the definition of HALT and the right side from our program $P$).  Since this is true for any input $x$ we could also write:

$$
HALT(y_0,y_0) \Longleftrightarrow ~ \sim HALT(y_0,y_0),
$$

which is clearly a contradiction; HALT cannot exist.


Automata with no transition for some character

In a deterministic automaton, every state must have exactly one transition for each symbol in the alphabet. In a nondeterministic automaton, this requirement is dropped and there could be multiple transitions or no transition for some symbol. If there is no transition for the next character in the string, the automaton rejects its input. This is what happens with the automaton on the left: it rejects the string $ba$ (and every other string beginning with $b$) because it has nowhere to go when it reads that first $b$.


FA for w when length of w is even or divisible by 3

A simpler solution is to use a DFA with 6 states which count the number of letters seen so far, modulo 6. This is a DFA with 6 states $q_0,\ldots,q_5$, and transition function $\delta(q_i,\sigma) = q_{i+1 \bmod{6}}$. The accepting states are $\{q_0,q_2,q_3,q_4\}$, since a number is even or divisible by 3 iff its residue modulo 6 is one of 0,2,3,4.

Using Myhill–Nerode theory, you can easily show that this is the minimal DFA for the language. Using an NFA with multiple initial states, you can improve this to 5 states: have two starting states $q_0^{(2)},q_0^{(3)}$ which also double as accepting states, states $q_1^{(2)},q_1^{(3)},q_2^{(3)}$, and transitions $\delta(q_i^{(m)},\sigma) = \{q^{(m)}_{i+1 \bmod{m}}\}$. This is likely the minimal number of states for this type of NFA.


In counting sort time complexity notation O(n+k), k is number of distinct elements?

Time complexity of counting sort is $O(n + k)$ where $n$ is the size of array, and $k$ is the maximum element in the array, not the number of distinct elements.

For example if we have the array $A = \text{{1, 2, 3, 3, 3, 4, 5, 8, 8}}$ Let's say that for our array $n = 9$ because we have $9$ elements, and $k =8$ because our biggest element is $8$.

Now we create another array $B$ of size $k$ where for each number in the range $[1, k]$ we keep how many times in occurs in the array $A$. $B = \text{{1, 1, 3, 1, 1, 0, 0, 2}}$.

Now we iterate through the array $B$ and for each index $i$ in $B$ we do exactly $B[i]$ iterations. We can see that sum of all numbers in $B$ equal $n$ so we do $k$ iterations in the first for and $n$ iterations in the second for.

In total the complexity is $O(n+k)$ where $n$ is the size of array and $k$ is the biggest element in the array.


It is true that if $q_0 \in F$ then $\epsilon \in L(A)$. The converse holds for DFAs and for NFAs without $\epsilon$ moves, but doesn't hold for NFAs which are allowed to have $\epsilon$ moves. That is, there is an automaton $A$ whose initial state is not accepting, yet $\epsilon \in L(A)$. I'll let you find an example.


Split into segments

One simple approach is to split $P$ into $k+1$ pieces, say $P = P_0 P_1 \cdots P_k$, as @j_random_hacker suggests.  You can make each of the $P_i$ be of approximately equal length, though this is not required.  Then, for each $i$, search for all instances of $P_i$ in $T$ (with no mismatches), and see if it can extend to an instance of $P$ with at most $k$ mismatches.  If there is a solution for your original problem, then this procedure will find it.

For non-degenerate cases, if every $|P_i|$ is large compared to $\log_{|\Sigma|} |T|$ and $P,T$ are more or less random, we can expect that there will be few "false matches" of a piece, and consequently  we can expect that the running time will be approximately $O(k \cdot |T|)$.  Thus this should be pretty fast in your specific situation.

This approach allows you to use any fast string-matching algorithm to search for instances of $P_i$ in $T$; e.g., you can use Rabin-Karp or any other existing algorithm -- this is nice because you can re-use existing well-tuned string matching libraries.  This approach might be not-too-difficult to implement and fairly efficient in practice.

Levenshtein automaton

You can build a NFA (nondeterministic finite-state automaton) to recognize instances of $P$ with at most $k$ mismatches.  In particular, the NFA recognizes all strings $S$ that end with something that matches $P$ with at most $k$ mismatches.  The NFA has $(k+1) \times |P|$ states: each state is of the form $(m,i)$, where $m$ counts the number of mismatches so far and $i$ counts the length of the prefix of $P$ that has been matched so far.

You can convert this NFA to a DFA.  Heuristically, I expect the size of the DFA to be pretty small, say $O(k \cdot |P|)$, though I don't know of any proof of this.  Next, you can run the DFA along the text $T$, to find the first place where there is a match, which takes $O(|T|)$ time.

This might be fast if $k$ is not too large.  If $k$ gets too large, it's possible the DFA will be enormous and the approach might fail.  This is probably most useful if you plan to re-use the same pattern $P$ with many different texts $T$, or if $T$ is far longer than $P$.  I wouldn't recommend it for your specific situation.

I have no proof that the resulting DFA will be small.  See also Levenshtein automata, which consider the far harder problem of building a DFA to recognize all strings $S$ that end with something that has edit distance $\le k$ to $P$ (i.e., they allow for at most $k$ mismatches, insertions, and/or deletions, in total).  The resulting DFA is much more complex, yet there are amazing algorithms to build the edit-distance DFA in running time that is linear in $|P|$ (but possibly exponential in $k$).  Your problem is considerably easier and will probably lead to DFA that are significantly smaller.


Free and bound variables in a lambda-calculus term

The free variables in the term you give are $f$ and $g$, $x$ is bound by the $\lambda$-binder.

I am also confused what you mean by "expanding"?  But I guess you want to abstract away those free variables.  If that is true, then you will get $\lambda x . \lambda f . \lambda g . f\ (g\ x)$ (or with the parameters permuted in another way.)


Heuristically determine a value f such that a probability d/f approaches 1/2

OK, another answer :)

Size of the set X' clearly depends on the distribution of points, choice of starting points, and random chance.

If the points are always chosen from the same distribution, I'd try drawing |X'| as a function of f and |X|. To do that, I'd just do some monte-carlo simulations.

Also notice that f is a linear function of mean distance between points.


Is there a binary representation where the encoding distance grows with the arithmetic distance?

You can get some kind of tradeoff between unary and binary.
Start by choosing some integer $k$ and set $w=2^k-1$.
Then write $x$ as $x=r+w+w+\ldots+w$, where $r$ is the remainder of $x$ when divided by $w$. Let $\bar{a}$ denote the binary encoding of $a$. You can encode $x$ as $e(x) = \bar{r}\bar{w}\bar{w}\ldots\bar{w}$.
This encoding is of length $k\times x/w$ and you have $d_{hamming}(x,y)$ which should be in the range from $\frac{1}{w}(|x-y|-1)$ to $\frac{k}{w}(|x-y|+1)$ (give or take some rounding errors on my part).
The smaller $k$ you choose, the better correspondence between Hamming distance and absolute difference, but the longer the encoding.
You can also use Gray code instead of binary to squeeze a bit more out of it.


Is the following true? log2(2n) ∈ O(log2(n))?

We have:
$$\log_2(2n) = \log_2(2) + \log_2(n) = 1 + \log_2(n) < 2 \times \log_2(n)$$

You can take $c = 2$ and as $\log_2(2n) < c \times \log_2(n)$ for $n > 2$, we can say $\log_2(2n) \in O(\log_2(n))$.


Enumerate all greedy choices of maximum independent set

Take the graph in the answer you linked to, and add another vertex G that has an edge to every other vertex except C.  Now C has the unique fewest number of neighbours, so it will necessarily be chosen first; then you can choose at most one of A, E, F or the new vertex G since each of these 4 vertices is linked to each of the others by an edge, so the algorithm forces you to produce an independent set of size 2 (either {C, A}, {C, E}, {C, F} or {C, G}).  But the same size-3 independent sets as before still exist (e.g. {B, D, F}).


Under which field of computer science does cloud computing fit?

According to the ACM classification, cloud computing belongs to:

Distributed architectures, under Architectures, under Computer systems organization.
Network services, under Networks.
Distributed systems organizing principles, under Software system structures, under Software organization and properties, under Software and its engineering.
Storage architectures, under Information storage systems, under information systems (as Cloud based storage).

So cloud computing is at the intersection of Computer architecture, Networking, Software engineering, and Information systems.

Cloud computing could also be considered its own area, since it has a dedicated conference, SoCC.


The common answer to "What to store?" is "As much as you need and nothing more."

You can instead store a reference to the previous state and the move(s) you made on the previous state to get to the current state.

This is more compact that a full copy of the state in each node but less convenient to work with because you'd need to reconstruct the state by following all the moves made since the last known full state node.

The next option is to throw away parts of the graph that you aren't looking at at the moment and instead recreate it later when needed.

Both of these options trade space for time.


Encrypting a 180-bit plaintext into a 180 bit ciphertext with a 128-bit block cipher

If you have a unique, unchanging identifier for each entry in your data store, you can use counter mode.

A nice thing about counter mode turns a block cipher into a stream cipher. No matter what the block size is, CTR mode encrypts an $n$-bit plaintext into an $n$-bit ciphertext.

In order to achieve that, CTR requires a unique counter value per block. Note: not just a unique counter value per message, but a unique counter value per block. The counter size is the same as the block size. In your case, you have messages that fit on two blocks, thus each message requires two counter values. If you have a unique identifier $k$ for each message, you can use $k$ and $k+1$ as the counter values for the two blocks (the second of which is partial) of the message.

Thus you need a 127-bit unique identifier for each message (128-bit block, minus one bit to distinguish the two blocks inside each message). The only security requirement for these 127 bits is that they are never reused for a given key. The initial counter value to encrypt a message is often chosen randomly, but this is not a requirement, just a convenience to ensure uniqueness. Of course, to decrypt the data, you need to be able to recover the unique identifier associated with each entry.

If your entries have some kind of unique identifier, which is often the case in databases, then you're set. Just remember that if you move data around or normalize it in a way that changes the identifiers, you will need to decrypt and reencrypt the data.

Some crypto libraries may present CTR mode through a function that randomly generates the initial counter value and prepends it to the message (so you'd input a 160-bit plaintext and get back a 288-bit ciphertext). Use a library that lets you specify the initial counter value (almost all implementations will increment the counter by 1 for each successive block, so pick initial counter values that are even, but you'll need to be aware of the endianness used by your library).

Keep in mind that encryption only gives you confidentiality, not integrity. In other words, someone who obtains the ciphertexts but not the key will not be able to find any information about the data; but if someone can inject fake ciphertexts or modify existing ciphertexts, the tampering cannot be detected. It is intrinsically impossible to detect tampering by cryptographic means in your scenario since there is no room for any redundancy.


As a hint, for any two numbers there is a third number in between.


Let $G = (V, E)$ be a graph. If the eccentricity of each vertex $v \in V$ is $c$. Then the center of the graph is $V$, the set of all vertices of the graph $G$. Note that the center is the set $V$ of vertices not the graph $G$. In general the center of a graph $G = (V, E)$ is a subset of $V$.


A stack is a last-in-first-out structure. This causes the reverse order you experience. What you need is a first-in-first-out structure, i.e., a queue.
This way or another, the stack in x86 is just a region in the memory you can access directly. Instead of popping each digit, initialize BP to point at the bottom of your stack (the first digit), then print it, and then advance BP to the next digit (i.e., decrease BP since the stack grows towards lower addresses). At the end of the print loop, just clean the stack by popping everything out, or by changing SP directly.
MOV BP, SP    ; init BP to the first digit

... <push digits> , <init CX> ...

PrintLoop:
   MOV DX, [BP]
   MOV AH, 2
   INT 21h            ; print

   SUB BP, 2          ; assuming each digit is a word
   LOOP PrintLoop     ; Loop according to CX

MOV SP, <...>         ; restore stack / "pop" everything


Proof of equivalence of L0 and language accepted by made up machine

You need to show that any language that is accepted by a Turing machine is accepted by one of your machines. So, start with an arbitrary Turing machine $M$ and show that one of your machines can accept $L(M)$, e.g., by showing how to directly simulate the operation of $M$.


Sort an array where $0\leq a_n\leq n^2$ and $a_n\in\mathbb{N}$

You can make a list of length $n^k$ which $k$ is $1$ for the first case and $2$ for the second one.
So you have an array and you can put each element in the relevant position. This idea may waste space but it's fast.
Time complexity of this algorithm is $O(n)$.
Space Complexity is $O(n^k)$.


λ -terms that correspond to Haskell functions

You are looking for Church encodings of datastructures in $\lambda$-calculus, and in particular of lists.


When you use recursion to solve a problem, you typically partition your input into one or more smaller instances (and possibly a part that you don't process further). Those smaller instances are what your exercise calls the small version.

Upon recursing, your inputs get smaller and smaller until it is no longer possible (or sensible) to further split them up. The inputs that are left to be solved directly are called the base case.