Yes there is a data structure which name is  Treap   You can also do other things too (ex. range sum, range min-max, etc.) using this or you can also use BBST (Balanced binary search tree like  AVL ).

Okay i will explain some terms i am assuming you have some Knowledge about Trees and BST(Binary search Tree)
Q. What Treap is?
A. Treap = Tree + Heap (in easy way)

Q. Use of Treap?
A. its randomized balanced tree basically its contain 2 values first one is data and second is rank (data, rank) and it has two property using data we keep BST(Binary search Tree) property it mean smaller than data will go on left side and bigger will be on right side and rank keep heap property its your choice that you want min heap aur max heap property. trick here is that rank is given uniformly random. So when we heapify using rank height of tree will not exceed O(LogN). so in easy implementation we can get a self balanced binary search tree.

Q. How to implement above requirements?
A. Insert and Delete methods are easy and equal to BST's methods

struct Node *insert(struct Node *root, int pos, int data) {
  if(root == dummy) {
    ptr ->left = ptr ->rig = dummy;
    ptr ->size = 1;
    ptr ->pri = rand();
    ptr ->data = data;
    return ptr++;
  } else if(root ->left ->size >= pos) {
    root ->left = insert(root ->left, pos, data);
    if(root ->left ->pri > root ->pri) root = rot(root, root ->left);
  } else {
    root ->rig = insert(root ->rig, pos - root ->left ->size - 1, data);
    if(root ->rig ->pri > root ->pri) root = rot(root, root ->rig);
  }
  update(root);
  return root;
}

here you can see 2 methods which are unknown to you actually one it rot which is rotation when our tree violate heap property and update where you can update your tree's attribute here we keeping size so you can updated this information here

Delete method is homework for you it will be same as insert in above code pos define that you want to insert an element in between pos-1 pos.

okay now lets come on your requirements :

enqueue -> call insert and pos will be root ->size
denqueue -> call delete
lookup -> search method same as binary search tree's search method
update , insert -> call insert
length -> root ->size


For the first solution suppose, given  $id2$ and $size2$ which $\neg pizza(id2, size2)$ and $size1 < size2$. Although, the first solution said $pizza(id1, size1)$ is not maximum (because it is not true for all $id2$ and $size2$), but it can be false.
Because, if $(id1, size1)$ is the only member of the table, it is the maximum.
Therefore, the first solution have some fallacy.

To correct the case, you should mention that if $(id2,size2)$ is member of $pizza$ relation, then $size1 \geq size2$ and you can write this proposition as $pizza(id2, size2) \rightarrow size1 \geq size 2$.


Why is $\sum_{j=0}^{\lfloor\log (n-1)\rfloor}2^j$ in $\Theta (n)$?

If you have a series of numbers that are consecutive power of 2s, like $1+2+4+8+16+\cdots+2^k$ you get as sum $2^{k+1}-1$. You can either see this by looking at the formula for the geometric series or you can prove this by induction.

Then the statement of the lectures follows, since here $k=\lfloor \log (n-1) \rfloor$. Therefore the sum is less than $2n$.


Coming up with loop invariants involving k?

There is a very simple way to determine whether you have the correct loop invariant:

Can you prove that it holds when entering the loop?
Can you prove that the loop maintains it?
Can you deduce correctness of the algorithm using the invariant?

I trust that you can do all these checks yourself.


A question from Computer Organization on Peak Clock Frequency

The peak possible frequency is, no doubt, equal to the inverse of maximum time supported by each stage. The stage consuming maximum time is the limiting condition and your anwer is correct.


There is a general historical trend.

In the olden days, memories were small, and so programs were perforce small. Also, compilers were not very smart, and many programs were written in assembler, so it was considered a good thing to be able to write a program using few instructions. Instruction pipelines were simple, and processors grabbed one instruction at a time to execute it. The machinery inside the processor was quite complex anyway; decoding instructions was not felt to be much of a burden.

In the 1970s, CPU and compiler designers realized that having such complex instructions was not so helpful after all. It was difficult to design processors in which those instructions were really efficient, and it was difficult to design compilers that really took advantage of these instructions. Chip area and compiler complexity was better spent on more generic pursuits such as more general-purpose registers. The Wikipedia article on RISC explains this in more detail.

MIPS is the ultimate RISC architecture, which is why it's taught so often.

The x86 family is a bit different. It was originally a CISC architecture meant for systems with very small memory (no room for large instructions), and has undergone many successive versions. Today's x86 instruction set is not only complicated because it's CISC, but because it's really a 8088 with a 80386 with a Pentium possibly with an x86_64 processor.

In today's world, RISC and CISC are no longer the black-and-white distinction they might have been once. Most CPU architectures have evolved to different shades of grey.

On the RISC side, some modern MIPS variants have added multiplication and division instructions, with a non-uniform encoding. ARM processors have become more complex: many of them have a 16-bit instruction set called Thumb in addition to the “original” 32-bit instructions, not to mention Jazelle to execute JVM instructions on the CPU. Modern ARM processors also have SIMD instructions for multimedia applications: some complex instructions do pay after all.

On the CISC side, all recent processors are to some extent RISC inside. They have microcode to define all these complex macro instructions. The sheer complexity of the processor makes the design of each model take several years, even with a RISC design, what with the large number of components, with pipelining and predictive execution and whatnot.

So why do the fastest processors remain CISC outside? Part of it, in the case of the x86 (32-bit and 64-bit) family, is historical compatibility. But that's not the whole of it. In the early 2000s, Intel tried pushing the Itanium architecture. Itanium is an extreme case of complex instructions (not really CISC, though: its design has been dubbed EPIC). It even does away with the old-fashioned idea of executing instructions in sequence: all instructions are executed in parallel until the next barrier. One of the reasons Itanium didn't take is that nobody, whether at Intel or elsewhere, could write a decent compiler for it. Now a good old mostly-sequential processor like x86_64, that's something we understand.


How can a universal Turing machine simulate "bigger" ones?

The answer to both subquestions is the same: by using the tape to store the necessary data. We can assume that the state set and alphabet of the machine to be simulated are subsets of the natural numbers ("State 1", "State 2", "State 3", etc.). Even with just two non-blank characters, the universal machine can represent all those integers as binary strings.

Note, though, that the universal machine has a fixed number of states, which makes computing the transition function a little tricky. What we'd like to do is write some instructions that implement a big switch statement of the form, "If the state is $s$ and the character under the head is $x$, then move to state $s'$, write character $x'$ and move the head in direction $d$." So – and I think this may be the root of your question – how do we calculate the transition function if we don't even have enough states in the universal machine to store the transition function's input?

One way is to store the transition function as a binary tree. Suppose all the simulated machine has $2^q$ states and $2^\ell$ tape symbols. Store the transition function as a binary tree of depth $q+\ell$  where, at the first $q$ levels, you go left or right according to whether the next bit of the simulated state is a one or a zero and the next $\ell$ levels are the same but for the successive bits of the simulated tape character. Now, your universal machine can walk backwards and forwards on its tape, checking the next bit of the state/character, remembering that bit in its own states, moving back to the tree, putting a marker at the correct node, and so on.

This gets somewhat easier if you let your universal machine have multiple tapes but then you still have to show that your multitape machine is equivalent to a single tape machine.


Algorithm to find non-overlapping intervals that minimize standard deviation

Let the $n$ numbers be $x[1..n]$, and the minimum interval size $k$.

Formulating an objective function

There's a conflict here between two goals: Reporting more intervals will often mean reporting worse intervals.  We need an unambiguous way to decide which set of intervals is "best".  A good way to resolve this is by assigning some score value to any interval that includes two terms: a positive term (perhaps dependent on the length), as well as a negative term for the "quality" (here, standard deviation).  The goal is now to choose a set of nonoverlapping intervals that maximises the sum of scores.  For example, we could say that the score $s(i, j)$ of the interval $i..j$ is $10 + j - i - 7*StdDev(x[i..j])$.

A quadratic-time dynamic programming algorithm

The following dynamic programming algorithm takes $O(n^2)$ time and $O(n)$ space to find a solution having optimal score (there may in general be more than one such), and works for any scoring function $s$ that depends only on the beginning and end positions of the given interval (so you may certainly tweak my example function until you get results that look good).  It seems likely to me that a faster (linear or at least log-linear) algorithm exists for simple scoring functions, but in any case the following is flexible and will certainly handle $n$ up to 10000 in well under a second on any modern-day computer.

For any $1 \le i \le n$, let $f(i)$ be the maximum sum of scores achievable by any set of nonoverlapping intervals on the subproblem consisting of just the first $i$ elements of $x$.  So in particular, $f(n)$ will be the maximum sum of scores achievable on the entire dataset.  For now, let's imagine that we have an algorithm to compute $f(i)$, and use that to compute a related quantity for an "end-inclusive" variant of the problem: let $g(i)$ be the maximum sum of scores achievable by any set of nonoverlapping intervals on the subproblem consisting of just the first $i$ elements of $x$ that places the final ($i$-th) element inside an interval.  We can compute $g(i)$ as follows:

$g(0 \le i < k) = -\infty$

$g(i \ge k) = \max_{0 \le j < i}(f(j) + s(j+1, i))$

The first equation expresses that there can be no valid end-inclusive solution if there are fewer than $k$ items in total.  Using negative infinity is essentially a trick to ensure that this value is "ignored" by any $\max$ expression it happens to find itself in.  You wouldn't need to actually represent negative infinity in a program; any sufficiently large negative number would work.

The second equation says that we can always form an optimal solution to the length-$i$ end-inclusive subproblem by taking an optimal solution to some length-$j$ subproblem (which may or may not be end-inclusive), and appending a final interval to it containing every element after the $j$-th, up to the $i$-th -- specifically, whichever choice of $j$ yields the highest combined score.  This is the core insight of the algorithm; it's worth taking the time to convince yourself that this is really true.

From here, it's simple to compute $f(i)$:

$f(0) = 0$

$f(i \ge 1) = \max \{g(i), f(i-1)\}$

The first equation is obvious.  The second says that we can always form an optimal solution to the length-$i$ unrestricted subproblem by taking either the optimal solution to the corresponding end-inclusive variant of this subproblem (which puts $x[i]$ in an interval), or an optimal solution to the one-shorter unrestricted subproblem (which doesn't) -- whichever has higher score.  Again, it's worth checking that this is indeed true.

Memoisation

You can turn each of the above equations into program code to get a working, but exponential-time recursive program that can calculate $f(n)$, the maximum score achievable.  To speed this up to quadratic time only requires not recomputing answers to subproblems that we have seen before.  This can be as simple as using an array $m[0..n]$, initially filled with some placeholder value like -1, to record answers just before you return them: When $f(i)$ is called, we first check whether $m[i]$ contains a non-placeholder value, and if so immediately return that.  This approach to dynamic programming is called memoisation (that's right, there's no "R" in there).

Actually computing a solution

You may have noticed that until now, the things we have been computing ($f(\cdot)$ and $g(\cdot)$) are not actual solutions to the problem but just the scores of those solutions.  Fortunately, an actual solution can be recovered without much effort using a technique called traceback.

The key idea is that $\max$ function evaluations encode the "decisions" made by the algorithm.  We start at the end with the final total score value $f(n)$, which we know to be optimal, and work backwards, at each step determining which argument to a $\max$ function "won" (was highest): this tells us which subproblem to consider next, and (implicitly) describes one piece of the optimal solution.  (Actually there may be multiple highest-equal arguments to a $\max$; convince yourself that choosing any of them will lead to an optimal solution.)  We must do this for both $f$ and $g$.

For example, suppose that $n=1000$ and that in the very first step we have $f(1000)=150$.  From looking at the second equation defining $f$, our first question is whether this 150 value arose from $g(1000)$ (indicating that $x[1000]$ is in an interval) or from $f(999)$ (indicating that it isn't).  Suppose $g(1000)=150$ and $f(999)=133$: then the former wins, so it must be that $x[1000]$ is in an interval in every optimal solution.  The next step is to determine which $j$, in the range 0-999, gave rise to the value $g(999)=150$; this will implicitly tell us the length of this final interval, and provide the next subproblem to consider.

Often tracing back is sped up by storing the index of the "winner" in an extra array during the initial forward pass, but it can also be accomplished by recomputing the $f(\cdot)$ or $g(\cdot)$ function value at each step during the backward pass (which is slower, but not asyptotically so).


Recursion Theorem : why does $SELF$ need $A$ and $B$ parts?

No, it can't.

Intuitively, $A$ can be described by print "B". Whatever $B$ is, there is such an $A$. Note that, by construction, $A$ is a program "longer" (roughly speaking) than $B$.

If we try to write $A$ as print "A", we incur in a problem, since $A$ should be "longer" than itself. Hence, such a definition is ill-posed.

For the same reason, you can't write a description of a TM inside its own finite control: you would need an infinite amount of states for that.

You can search the web for "quines": programs printing their own source code. Virtually all of them have to workaround the fact that they can't include their own source code in themselves, and have finite length. Hence, they must exploit something analogous to the $q()$ function you mention.

A typical quine can be designed as follows. Start from a clumsy attempt:

myself=""
print myself

Obvious partial fix: copy its source code within myself

myself="myself=\"\" \n print myself "
print myself

Not yet there: we should replicate the source code inside the innermost quotes, and so on, infinitely many times. Not good.

Instead, we use a placeholder for that "infinite" replication, which we replace at runtime with the whole code.

myself="myself=\"PH\" \n print myself "
print replace(myself, "PH", myself)

Obvious fix

myself="myself=\"PH\" \n print replace(myself, \"PH\", myself)"
print replace(myself, "PH", myself)

Assuming that replace only replaces the first occurrence of the placeholder PH, and that we fix the whitespace precisely in myself, this is now a program printing itself -- a quine.

Note how the replacement of PH must be done at runtime. Similarly, in the Sipser proof, we must compute q() at runtime -- we can't encode that in the finite control.


Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case

If your shapes are not too elongated, you could calculate their axis-aligned bounding boxes (BBs) and store these bounding boxes in an index, such as R-Tree, quadtree or one of their more modern variants.
Then:

Define a distance function that gives the closest BB to the BB of your search-object.
Find the BB in the index that is closest to the BB of you search object.
Calculate the actual distance $d$ between the search-object and the object from the index.
Search the index again, this time with a window query that is by $d$ larger than the previous search BB. This should return all objects that are potentially closer than $d$.
Brute force all returned objects to calculate their actual distance to your search object.

Worst case complexity of the worst case is $O(N)$ for $N$ objects, but average case should be closer to $O(log N)$.


Yes, there are more efficient ways.  If you have two polynomials $p(x)=\sum p_i x^i$ and $q(x) = \sum q_i x^i$, then the coefficient of $x^k$ in $p(x) q(x)$ is given by

$$\sum_{i=0}^k p_i q_{k-i}.$$

This can be computed in $O(k)$ time, which is more efficient than multiplying the polynomials and extracting the coefficient of $x^k$.

With preprocessing, you can just multiply the polynomials during the preprocessing phase and store all of the coefficients.  Then looking up any desired coefficient can be done in $O(1)$ time.


Minimum square side length to enclose n circles of radius r

This is known as circle packing in a square.  The Wikipedia article I link to has a citation to this webpage, which lists the best packings known for $n \le 10000$, and also has many references to papers that study this problem.  I suggest studying them to see what methods they have used.


Proving worst-case running time is in $\Omega(n^2)$

The worst-case running time of an algorithm $A$ is a function $T(n)$ which accepts an input length and outputs the maximum running time of algorithm $A$ on an input of length $n$:

$$ T(n) = \max_{|x|=n} \mathrm{runtime}(A,x). $$

Therefore to prove that $T(n) \geq S(n)$, it suffices to show that for each $n$ there is an input $x_n$ of size $n$ such that $\mathrm{runtime}(A,x_n) \geq S(n)$. The fact that there exist other inputs on which $A$ performs better is completely immaterial, since the worst-case running time depends on the worst input.


Why have quantum circuits won out over quantum Turing machines?

I've popped up here 7 months too late but in response to the question here's my short-ish answer: Quantum Turing machines are physically unreasonable. Prof. Peter Shor originally wrote his factoring algorithm using a Turing machine and so from a theoretical perspective they work just fine. However, it requires the tape heads to be entangled, which is why you couldn't realistically make it work. The Circuit model (which has been around longer than Turing machines) also has it's own problems which is why Turing needed his machine. One main reason (there are others) is that circuits are designed for a given input size whereas Turing machines are independent of input size. Therefore the circuit model is better suited to quantum computation as it is a more realistic reflection of the devices we could build.


Two Turing machines $M_1$ and $M_2$ with $L(M_1) \subseteq L(M_2)$

"Halt" is not synonymous with "accept", although the latter implies the former. A TM can halt and reject. On the other hand, $L(M)$ stands for the set of words accepted by $M$, not the words it halts for.

Hence, alternative (C) is correct. (B) is incorrect because $M_1$ could halt on and reject a word which is accepted by $M_2$ (i.e., a word in $L(M_2) \setminus L(M_1)$), or for which $M_2$ does not halt, even.

Note the question makes little sense, if any, if we assume $M_1$ and $M_2$ to be deciders since, then, all alternatives are correct, (A) because the premise is always false (since $M_1$ always halts) and the others because the respective implications are always true.


Linear Discriminant Method as Pre-processing for inputs going into a Neural Network?

This is not a useful method.  LDA is basically a two-class classifier, which works under certain assumptions on the distribution of the data.  If those assumptions hold, LDA is optimal and there is no reason to use a neural network.  If those assumptions don't hold, LDA might not be a useful tool.  Even if you do use LDA, LDA maps each data point to one of two classes, so there is no information left for the neural network to do any further processing.
In short: LDA is not useful as a preprocessing step before a classifier; you either use LDA as the classifier itself, or you don't use LDA at all.


If you have a DFA M, how do you construct a new NFA that accepts L(M) and {e}?

You've got the right idea, but there's a slight bug.
If you add an $\varepsilon$-transition from the start state to all accepting states, then the new machine recognizes a subtly different language.
Let $L_k = \{w_1 \cdots w_k : \exists u_1, \dots, u_{k-1} \in L(M) \text{ such that } w_1 u_1 w_2 \cdots u_{k-1} w_k \in L(M)\}$.
Note that $L_1 = L(M)$.
This new machine will recognize the union of the $L_k$, i.e., it recognizes $\bigcup_{k=1}^{\infty} L_k$.

Instead, you can create a new state $q_{\text{empty}}$, add an $\varepsilon$-transition from $q_0$ to $q_{\text{empty}}$, and take the new set of accepting states to be $F \cup \{q_{\text{empty}}\}$.


UInt128 - Compute the product of two UInt128's that are each represented by two UInt64's?

It depends what operations are available to you for 64 bit integers.

The product of two 64 bit integers is a 128 bit integer. Many programming languages don't provide such a product, for example in C you will likely have an operation that produces the 64 bit (x * y) modulo $2^{64}$, but not an operation that produces the 128 bit number x * y.

On the other hand, given two 64 bit numbers x, y, many processors have instructions that produce 64 bit integers a and b such that mathematically x * y = a * $2^{64}$ + b.

If such an operation is available to you, you would calculate the 128 bit product x.s2 * y.s2, and the two 64 bit products x.s1 * y.s2 and x.s2 * y.s1 and use these to calculate the 128 bit product. If you want a 256 bit product, then you need to calculate four 128 bit products.

If you have no easy means to calculate the 128 bit product of two 64 bit numbers, then hopefully you can calculate the 64 bit product of two 32 bit integers, so you can use the same operations with half the number of bits.


Why Do Computers Use the Binary Number System (0,1)?

Since we're in Computer Science, I'll answer this way: they don't.

What do we mean by a "computer?" There are many definitions, but in computer science as a science, the most common is the Turing machine.

A turing machine is defined by several aspects: a state-set, a transition table, a halting set, and important for our discussion, an alphabet. This alphabet refers to the symbols which the machine can read as input, and that it can write to its tape. (You could have different input and tape alphabets, but let's not worry about that for now.)

So, I can make a Turing machine with input alphabet $\{0,1\}$, or $\{a,b\}$, or $\{0,1,2\}$,
or $\{\uparrow,\downarrow\}$. It doesn't matter. The fact is, I can use any alphabet I choose to encode data.

So, I can say that $0001001$ is 9, or I can say that $\uparrow \uparrow \uparrow \downarrow \uparrow \uparrow \downarrow$ is 9. It doesn't matter, since they're just symbols we can distinguish.

The trick is that binary is enough. Any sequence of bits can be interpreted as a number, so you can convert from binary to any other system and back.

But, it turns out unary is enough too. You can encode 9 as 111111111. This isn't particularly efficient, but it has the same computational power.

Things get even crazier when you look into alternate models of computation, like the Lambda calculus. Here, you can view numbers as functions. In fact, you can view everything as functions. Things are encoded not as bits, 0s and 1s, but as closed mathematical functions with no mutable state. See the Church numerals for how you can do numbers this way.

The point is that, 0s and 1s is a completely hardware specific issue, and the choice is arbitrary. What encoding you're using isn't particularly relevant to computer science, outside of a few subfields like operating systems or networking.


You can look at the length of words.

Any element of $A^+$ is a concatenation

$$ a_1 a_2 \ldots a_n $$

where $a_i \in A$ and $n \geq 1$. The length of such a word is

$$ L(a_1 a_2 \ldots a_n) = L(a_1) + L(a_2) + \ldots + L(a_n) $$

But the length is always nonnegative; for example,

$$ 0 \leq L(a_1) \leq L(a_1) + L(a_2) + \ldots + L(a_n)$$

If you're given that

$$ \epsilon = a_1 a_2 \ldots a_n $$

then putting all of the above together gives

$$ 0 \leq L(a_1) \leq L(\epsilon) = 0 $$

and thus $L(a_1) = 0$, so $a_1 = \epsilon$ and $\epsilon \in A$.

If you were to assume that $\epsilon \notin A$, you could modify the above argument by the fact that $L(a_i)$ must be positive, and so

$$ 0 < L(a_1) \leq L(a_1) + L(a_2) + \ldots + L(a_n) $$

and then the final deduction would be

$$ 0 < L(\epsilon) $$

which is a contradiction.


Show linear bounded automata accepting w is PSPACE-complete

Savitch's theorem shows that PSPACE=NPSPACE, which immediately implies that ALBA is in PSPACE.
In the other direction, suppose that $L$ is a language in PSPACE. Thus $L$ is accepted by some machine that uses space $p(n)$. We can construct another machine $L'$ which accepts an input $(x,y)$, erases $y$, and simulates $L$ on $x$. We can reduce $L$ to ALBA by mapping $L$ to $L'$ and $x$ to $(x,0^{p(|x|)})$.


Is an infinite language of halting TM is in $RE$? in $RE \setminus R$?

The empty set $\emptyset$ satisfies trivially the constraint as all the TM it
contains (actually none) halt for all input. But the emptys set is
also in $R$ since it is very easy to decide whether a TM is in it: the
answer is always NO. But unfortunately, this example cannot be used, because we hav a requirement that the set $L$ of TM be infinite (Thanks to @FrançoisG for reminding me).

So we choose another simple counter example, the set $L_{\emptyset,0}$ of TM recognizing the empty language that halt and reject after 0 steps, but may have a lot of useless states and transitions. There is also an infinite number of such machines, and it is easy to see by inspection of its transitions whether a TM is in $L_{\emptyset,0}$. Thus $L_{\emptyset,0}$ is infinite and recursive.

Since the set $L_{\emptyset,0}$ is recursive, there is a computable bijection   $\phi: \mathbb N\to L_{\emptyset,0}$

Then given any subset $S$ of $\mathbb N$, we can get get with the bijection $\phi$ a subset $\phi(S)\subset L_{\emptyset,0}$ which has the same level of computability.

Thus if we take any non-recursive RE subset $S_{RE\setminus R}\in\mathbb N$, we have $\phi(S_{RE\setminus R})\subset L_{\emptyset,0}$ which is RE but not recursive. And it contains only (Gödel indexes of) TM machines that always halt.

Of course, other levels of computability can be obtained in the same way.


First of all, $\mathrm{NP}\subset\mathrm{P}/log$ would imply that $\mathrm{NP}=\mathrm{P}$ (try all possible log-long advice to search for a satisfying assignment in SAT problem).

Second, the situation for $\mathrm{BPP}$ is more complicated. Since $\mathrm{BPP}$ languages do not have short certificate, one cannot hope to deduce that $\mathrm{BPP}=\mathrm{P}$ from $\mathsf{BPP\subset P/}log$.

What we can deduce from $\mathsf{BPP\subset P/}log$ is that $\mathsf{BPP\cap NP=BPP\cap co}$-$\mathsf{NP=RP=co}$-$\mathsf{RP=P}$. That is, the part of $\mathsf{BPP}$ inside $\mathsf{NP\cup co}$-$\mathrm{NP}$ is just $\mathrm{P}$.


Can a DPDA decide if two letters appear the same number of times mod 5?

What does $|w|_0 = |w|_1 \mod 5$ means ?
It could either mean (depending on your book's notations) :

$\exists k\in\mathbb Z, |w|_0 + 5k = |w|_1$
The remainder from the Euclidean Division of $|w|_1$ by 5 is $|w|_0$

Let's first resolve the first case. You should accept if and only if  5 divides $|w|_1 - |w|_0$. This can be done with a finite automaton with 5 states, to keep track of $|w|_1 - |w|_0\mod 5$ and only accepting when it is in state 0 (I'll let you find the transitions).

In the second case, you need to also ensure that the value of $|w|_0$ never goes beyond 4. That can be done by copying the same finite automaton as above 4 times, fixing the transitions accordingly (I would recommend to try doing that) and adding a "trash state" to go to if you have read more than four 0.

So we have deterministic finite state automata for both those languages. Finite state automata are just specific cases of PDA where you never use the stack. So there you have a DPDA for each of those languages.

Another way to do this, which is probably what the author was looking for, is to try to build a grammar. Hint : such a grammar has 5 non-terminal symbols, 2 terminals symbols, and 11 rules (this is for the first case).
Those two constructions are equivalent though.


You can show directly how to simulate a polynomial fan-in modular gate using polynomially many threshold gates. The idea is that given inputs $x_1,\ldots,x_m$, you can use two threshold gates and an AND gate to determine whether $x_1 + \cdots + x_m = w$ for any $w$. Taking at most $m+1$ copies of this gadget and ORing them, we can simulate a single modular gate.


Finding the required value of an algebric expression

This is classical Integer Linear Programming. You have the following problem:

$$\begin{align}
Ax+Bx+Cx & \to \max \\
\text{s.t} \quad x,y,z &\ge 0\\
Ax+Bx+Cx &\le T \\
x,y,z &\in \mathbb{Z}\\
\end{align}$$

There are several algorithms available for such problems. Google "branch and bound" or "branch and cut" and you will get to them.

You can picture your problem as follows. Your variables $x,y,z$ decode a grid point in 3d. The constraints cut of hyperplanes, which keeps you left with a  set of candidate solutions. In your example this set is finite. You could basically test out all cancidates brute force. But it is more practical to add additional constraints to make the candidate set smaller - or in other words you filter out points. If you relax the condition that $x,y,z$ are integers, then the problem becomes much easier (Linear Programm), because then you know that the optimal point you are looking for is on some "corner" of your candidate set.


Suggested solution: use a k-d tree

I recommend you use a k-d tree to store the points of $Q$, with $k=3$ (3 dimensions).  The three dimensions of each point are the $x$-coordinate, the $y$-coordinate, and the $v$-value (the value/weight of the point).

Store all of the points of $Q$ in a k-d tree.  Then given a point $p$, you can use the structure of the $k$-d tree to find the point $q \in Q$ that maximizes $f(p,q)$ in a relatively efficient way -- more efficient than naively testing each possible point $q \in Q$.  Then, you can iterate through the points of $P$, and for each point $p \in P$, use this procedure to find the point $q \in Q$ that maximizes $f(p,q)$.  Keep track of the best pair you've seen, and this will solve your problem.

I guess I'd better describe how to use the k-d tree.  Recall that each node in the k-d tree splits by a binary condition of the form $x \le c$ or $y \le c$ or $v \le c$, where $c$ is some constant (all points that satisfy the condition are stored in the left subtree of that node and all points that don't satisfy the condition are stored in the right subtree).  Each point $q \in Q$ is stored somewhere in the tree.  So, any node $s$ in the k-d tree corresponds to a subset $S_s \subseteq Q$ of points from $Q$, namely, the points that appear somewhere in the subtree rooted at $s$.  Due to the splitting criteria, each set $S_s$ has the form $Q \cap R$ where $R$ is some axis-aligned 3-dimensional rectangle.  For a particular node $s$, define

$$\begin{align*}
s.x_\text{max} &= \max\{q.x : q \in S_s\}\\
s.x_\text{min} &= \min\{q.x : q \in S_s\}\\
s.y_\text{max} &= \max\{q.y : q \in S_s\}\\
s.y_\text{min} &= \min\{q.y : q \in S_s\}\\
s.v_\text{max} &= \max\{v(q) : q \in S_s\}\\
s.v_\text{min} &= \min\{v(q) : q \in S_s\}
\end{align*}$$

As you form the k-d tree, precalculate the above 6 values for every node and store them in that node of the k-d tree, so they're available for ready lookup.

Define $R_s = [s.x_\text{min},s.x_\text{max}] \times [s.y_\text{min},s.y_\text{max}] \times [s.v_\text{min},s.v_\text{max}]$.  We can see that $S_s = Q \cap R_s$.  It will be helpful to define

$$d(p,R_s) = \min \{d(p,r) : r \in R_s\}.$$

Note that you can efficiently calculate $d(p,R_s)$, given the point $p$ and the 6 values associated with $s$.  (Basically, this involves a case analysis through 27 cases, depending upon where $p$ is relative to $R_s$.  The running time to compute $d(p,R_S)$ is $O(1)$.)

Let's fix a point $p$.  I'm going to describe an algorithm to find the point $q \in Q$ that maximizes $f(p,q)$, by recursively searching the k-d tree for $Q$ in a suitable way.  The idea is that we'll recursively visit the nodes of the k-d tree, but pruning the traversal when we reach a node that cannot possibly hold any point $q \in Q$ that will be better than the best seen so far.

To help us prune the traversal, notice that we can bound the maximum possible value of $f(p,q)$ over all $q \in S_s$, as follows:

$$f(p,q) \le v(p) + s.v_\text{max} - \alpha \cdot d(p,R_s) \text{ for all } q \in S_s.$$

Thus, whenever our recursive traversal reaches a node $s$ of the k-d tree, we'll use the above bound to figure out whether there is any possibility that exploring the subtree rooted at $s$ could possibly yield some improvement over the best result seen so far.  If not, we'll prune the traversal and won't visit any of the children or descendants of $s$.

Thus, the algorithm looks something like the following:

def findbestpoint(p):
    bestsofar := -infinity
    visit(p, root of k-d tree for Q)
    return bestsofar

def visit(p, s):
    if v(p) + s.v_max - alpha * d(p,R_s) <= bestsofar:
        return
    update bestsofar based upon the point q stored in node s (if any)
    if s is a leaf:
        return
    visit(p, s.rightchild)
    visit(p, s.leftchild)

Given a k-d tree for $Q$ and a point $p \in P$, this algorithm computes $\max \{f(p,q) : q \in Q\}$.  It will visit some of the nodes of the k-d tree but not all of them.  So, iterate through the points $p \in P$ and call findbestpoint() on each one.

The above is correct but not necessarily optimal in performance.  As an optimization, I suggest that at nodes that split on the $x$-coordinate or $y$-coordinate, you should choose the order of the recursive traversal to prefer the subtree that contains $p$; and for nodes that split on $v$-value, always prefer the subtree with the larger $v$-value.  In other words, I suggest you replace the last two lines of visit(p, s) with

    if the condition associated with s is a split on the v-value:
        visit(p, s.rightchild)
        visit(p, s.leftchild)
    else if p satisfies the condition associated with s (i.e., p is contained within the subtree rooted at s.leftchild):
        visit(p, s.leftchild)
        visit(p, s.rightchild)
    else:
        visit(p, s.rightchild)
        visit(p, s.leftchild)

This will choose a traversal ordering that is more likely to help you prune many unpromising nodes.

As another optimization, rather than resetting bestsofar to $-\infty$ on each call to findbestpoint, I suggest you initialize it to $-\infty$ once and then don't reset it again.  This will enable you to prune more effectively, and since you only want to find one pair $p,q$ that maximizes $f(p,q)$, this optimization is valid.

As yet another optimization, you can choose the order in which you iterate through the points of $P$ based on some heuristic.  For instance, you could try sorting $P$ by value and iterating through $P$ in order of decreasing value; or you could use value minus $\alpha$ times the distance to the centroid of $Q$, or something like that.  Basically, you want to first try values of $P$ that are more likely to yield you a large $f(\cdot,\cdot)$ value, as that will make the pruning more effective.

I have no theoretical guarantees on the asymptotic running time of this algorithm.  However, when the set $Q$ is large, I expect this will give significant improvements.  Once you understand how k-d trees, it should be relatively easy to code this up and give it a try.

Note that you can always choose whether to store $Q$ in the k-d tree and iterate through $P$ (as outlined above) or whether to store $P$ in the k-d tree and iterate through $Q$.  I suggest you store the larger set in the k-d tree and iterate through the smaller set.

A better algorithm using k-d trees

The idea above can be generalized further, to obtain an algorithm that might be even more efficient, at the cost of making the algorithm more complicated and more tedious to implement.

The algorithm above explores pairs $p,s$ where $p$ is a point and $s$ is a node in the tree (summarizing some subset of points from $Q$).  In the refinement, we'll explore pairs $s,t$ where $s$ is a node in the k-d tree for $P$ and $t$ is a node in the k-d tree for $Q$ (so $s$ summarizes some subset of $P$ and $t$ summarizes some subset of $Q$).  This will expose further opportunities for pruning.

Assume we have built a k-d tree for $P$ and a k-d tree for $Q$, augmented with the information listed above.  For simplicity of exposition, assume we're using one of the variants of the k-d tree data structure where the points of $P,Q$ are stored in the leaves of the tree; the internal nodes don't store points.  (You can generalize the ideas here to the case where each internal node also stores a point from $P$ or $Q$; the extension is messy but not conceptually difficult.)

Also, if $s$ is a node in the k-d tree for $P$ and $t$ is a node in the k-d tree for $Q$, define

$$d(R_s,R_t) = \min \{d(r_1,r_2) : r_1 \in R_s, r_2 \in R_t\}$$

to be the distance between the two rectangles $R_s,R_t$.  This is the distance between the "closest point of approach" between the two rectangles.  For example, if the two rectangles $R_s,R_t$ overlap, $d(R_s,R_t)=0$.  This distance is a property solely of the rectangles $R_s,R_t$ and doesn't have anything to do with the points $p,q$ that are contained within them.  Given the descriptions of $R_s,R_t$ (i.e., the 6 values stored in the nodes $s,t$), you can compute $d(R_s,R_t)$ in $O(1)$ time via an ugly but straightforward case analysis.

Now notice that

$$f(p,q) \le s.v_\text{max} + t.v_\text{max} - \alpha d(R_r,R_s)$$

for all $p \in R_s, q \in R_t$.  This gives us an upper bound on the value of $f(p,q)$ over all class of possible pairs $p,q$ of points.  Conceptually, the node $s$ summarizes a bunch of points $p$ (the set $S_s \subseteq P$), and the node $t$ summarizes a bunch of points $q$ (the set $S_t \subseteq Q$); the above bound lets us upper-bound the best possible $f(\cdot,cdot)$ value, among all pairs of points $p,q$ in these sets.

Based on this insight, we can get a recursive algorithm to find the best pair of points:

def findbestpair():
    bestsofar := -infinity
    visitpair(root of k-d tree for P, root of k-d tree for Q)
    return bestsofar

def visitpair(s, t):
    if s.v_max + t.v_max - alpha * d(R_s,R_t) <= bestsofar:
        return
    if s is a leaf and t is a leaf:
        let p := the point contained within s
        let q := the point contained within t
        if f(p,q) > bestsofar:
            bestsofar := f(p,q)
    else if s is a leaf:
        visit(s, t.rightchild)
        visit(s, t.leftchild)
    else if t is a leaf:
        visit(s.rightchild, t)
        visit(s.leftchild, t)
    else:
        visit(s.rightchild, t.rightchild)
        visit(s.leftchild, t.leftchild)
        visit(s.leftchild, t.rightchild)
        visit(s.leftchild, t.leftchild)

We can see that this explores pairs $s,t$ (corresponding to a set $S_s \times S_t$ of points), pruning when we can prove that none of the pairs $(p,q) \in S_s \times S_t$ will have a larger value of $f(p,q)$ than the best we've seen so far.

You can apply similar optimizations to those mentioned above (e.g., when $s$ is a leaf that splits on $x$-coordinate or $y$-coordinate, first try the child of t that $s$ is contained in; when $s$ is a leaf that splits on $v$-value, first try the child with the larger $v$-value; and symmetrically when $t$ is a leaf).

I would conjecture that if the size of the both sets is large enough, this might perform better than the solution mentioned above. However, I have no proof, and the only way to know for sure is to implement it and give it a try on your data set.

A connection to computational geometry

I also noticed that your problem is related to the following classical problem:

Given a set of discs in the 2-D plane, determine whether any pair of discs overlap.

and the following version of the problem:

Given a set of discs in the 2-D plane, determine the pairs of discs that are closest (where the distance between two discs is given by the closest point of approach, i.e., the minimum distance between any point in the first disc and any point in the second disc).

These are classic problems in computational geometry which I think have sub-quadratic time algorithms (by sweepline methods or something, if I recall correctly).  Unfortunately your problem seems harder those questions about discs, so I don't know whether those methods will transfer over.

Here is the connection.  Define $w:P \cup Q \to \mathbb{R}$ by $w(p) = v(p)/\alpha$ and $w(q) = v(q)/\alpha$.  Define $g:P \times Q \to \mathbb{R}$ by

$$g(p,q) = d(p,q) - w(p) - w(q).$$

Your problem is equivalent to asking for the pair of points $p \in P,q \in Q$ that minimizes $g(p,q)$, as $f(p,q) = - \alpha \cdot g(p,q)$.

Next, treat each point $p$ as being associated with a disc centered at $p$ and having radius $w(p)$; and similarly for each point $q$.  In this way if all of the $w(\cdot)$ values are positive, we obtain a collection of discs in the two-dimensional plane.  Notice that if two discs $p,q$ don't overlap, then $g(p,q)$ denotes exactly the distance between those two discs.  This condition is equivalent to requiring that $g(p,q)$ be positive for all $p,q$.

In summary, if we were promised that $v(p)$ was positive for all $p,q$ and that the maximum value of $f(p,q)$ was negative, then your problem would be equivalent to finding the closest pair of discs in the 2-D plane.

Of course, in your problem, we're not promised any of those things.  Therefore, your problem is harder.  However, if you were really eager on trying to find the best possible algorithm, you could explore the literature to find algorithms for finding the closest pair of discs and see if any of them can be generalized to your setting.


Your function has constant running time (or linear running time, depending on how range is implemented). I suggest running it step-by-step and seeing what happens.


Showing that $\lg(n!)$ is or is not $o(\lg(n^n))$ and $\omega(\lg(n^n))$

You seem tot be trying to prove something that is false. If $f=O(g)$ then $\lim_{n\to\infty}g/f > 0$ so $f\neq \omega(g)$. Similarly, if $f=\Omega(g)$ then $f\neq o(g)$.

Since you already have that $\lg n! = \Theta(\ln n^n)$, that gives you big-$O$ and big-$\Omega$, which preclude little-$\omega$ and little-$o$, respectively.


Is "flops" a reliable measure of deciding computational capacity?

Much computing is shuffling data around, from memory to CPU(s) and viceversa, from disk to memory, and so on. Performance could well be determined by non-processing needs. If there are several CPUs involved (many supercomputers really do the computing on graphics cards, which are massively parallel SIMD computers), jobs that can't be sped up by processing separate data streams with the same instructions will go much slower than extensively studied and paralellized to death computations like massive matrix operations.

So the answer is no, raw FLOPS aren't a good measure of performance. Again, the only reliable performance measure for your specific problem is the performance on it. "Performance" isn't a number, it is a vector with multiple independent aspects, and the requirements of your problem are also a vector, in the same dimensions. How well they match over a wide range of possible problems to a particular machine can't be reduced to a single number.


Algorithm to extract the subgraph of all nodes with degree at least four

The object you are trying to find is known in graph theory as the 4-core. Batagelj and Zaveršnik give a simple linear time algorithm for finding the $k$-core for any given $k$.


Abstract algebra and programming languages

Initial algebras and free algebras are basic concepts of category theory. Thus
you may try the first chapters of [1] (in particular Section 2.2 Functional programming languages as categories) or the books [2] or [3].

[1] Category Theory for Computing Science by Michael Barr and Charles Wells

[2] Basic Category Theory for Computer Scientists
by Benjamin C. Pierce.

[3] A taste of category theory for computer scientists by Benjamin C. Pierce.


What is the regular expression of this language?

Check RE and FA for finite automata construction.

It has to be regular since we can create Regular Expression for it.


Can Dijkstra's algorithm outperform A star, in terms of vertices checked?

No,

Dijkstra will explore all nodes with cost less than the cost of the completed path. While A* will explore all nodes with cost+heuristic less than the cost of the completed path.

Thus if the heuristic is always positive then A* will expand less or equal nodes.


Databases and B-Trees: What are Keys and how are they related

There's an indeed a relation that maps the database keys to the B-trees keys $K_d \mapsto K_b, K_b \in \mathbb{Z}$
The B-Tree keys are not random though, they represent the physical location of data stored for that key.   At the leaf level there are multiple ( up to the order of the tree) database $K_d$s associated with a single $K_b$ key. The relation is thus not an injective function.


Select certain number of column elements of a stochastic matrix, maximum one element per row

Duplicate the $j$th column $k_j$ times to reduce to the case in which $k_j = 1$. You are now looking at the assignment problem, which can be solved efficiently.


An underestimated tradeoff between Memory and the Effectivity of Computation?

I'm not sure I understand your question entirely, but I'm going to assume that you're talking about the space-time tradeoff. The gist of the aforementioned tradeoff is as you put it, in the context of an algorithm, the balance you have to strike between the memory it will use (its space complexity) and the time it will take to run (its time complexity).
Obviously, the faster you want it to run, the more memory you will need to use, and vice-versa. The tradeoff is in general present in most fields of computer science besides pure algorithm design, but this provides I believe a nice abstract starting point.

Let's start with the bad news: from a rigid theoretical computer science point of view, tough luck, no such unifying formula exists and it is actually a fairly well-known open problem (for more info you may want to check this question about the space-time tradeoff, but it is fairly technical). Even worse, few general results are known about this.

Now the good news, of which there are two. First of all, I highly encourage you to think about the problem yourself and come up with your own (even incomplete theory), as it isn't very hard to qualitatively come up with some pretty interesting remarks.

For instance, let us try to develop a (very!) basic theory here. At its core, a result to be obtained through computation can be decomposed into a bunch of dependencies and operations. For instance, to compute c=a+b, you need to know a and b (the dependencies, also known as operands), and add them together (the operation). This decomposition can be applied iteratively many times until all of the dependencies are directly known (present in the problem instance/the input you receive).
There are many ways of looking at this, one of them is as a DFG (Data Flow Graph), but there are of course many more with varying degrees of complexity, which each offer accuracy for different factors. For convenience, have this nice picture of a DFG:

Abstracting the compute cost of one operation to 1 (no matter its complexity or the number of operands), we can see that the lower time bound to obtain the value of a node of the DFG is equal to the length of the longest path from the node to an input operand. Indeed, if we assume entirely parallel computation (possible if no interdependencies exist between nodes at the same depth), this bound can be attained. If we would however assume entirely serial computation, we would need to add the cost of obtaining each result one by one and I choose not complicate myself with this here.
If we add memoization, this time becomes the length of the longest path from the node to a memoized operand (but we stop when we reach the first one on a given path backwards from the target node).

This sounds suspiciously simple, right?
If we know the DFG beforehand and we assume parallelism, it indeed isn't very complicated, but a few avenues of thought would be if we consider as mentioned serial (or partly serial execution) and then memoization strategy.

I'll just point out that while it's not what you're looking for, for practical purposes it's always a good idea to benchmark on real hardware as well.

Now since I mentioned that there are two good news: there are bounds on this tradeoff which have been found and proven for specific problems and computation models. If you're interested, you can find some of these purely theoretical results in this answer.


Sublinear query time for the $i$th element of an array after some additions?

Yes, there are good data structures for this.  The running time to handle  $q$ queries and $\ell$ lookups will be $O((q+\ell) \lg n)$ time in total, or in other words, $O(\lg n)$ time per query and $O(\lg n)$ time per lookup.  This can be much faster than linear time in general.

Let $A_\text{orig}[1..n]$ denote the original value of the array $A$.  We're going to build a data structure to represent the array $\Delta[1..n]$ of integers, where $\Delta[i]$ holds the amount that $A[i]$ has been increased by (given the queries so far).  Thus, to compute $A[i]$, it suffices to look up $A_\text{orig}[i]$ and $\Delta[i]$ and return their sum.

The question is, how do we maintain the $\Delta[]$ array in a way that we can efficiently look up $\Delta[i]$ at any index $i$, and that we can efficiently update $\Delta$ in response to a particular query?

If we represent $\Delta$ as an array, then lookups take $O(1)$ time, but updates (handling a query) may take $\Theta(n)$ time, which is no good.

A better solution is to represent $\Delta$ using an interval tree.  With the proper data structures, each lookup will take $O(\lg n)$ time, and each update (processing each query) will take $O(\lg n)$ time.  This should give an efficient algorithm.

An interval tree holds a set of non-overlapping intervals.  In our case, the intervals will be consecutive ranges of array indices for which $\Delta$ holds the same value.  We will augment the data structure to hold the value of $\Delta$ for each such interval.

For example, initially the interval tree could be represented as $[1,n] \mapsto 0$, to represent that all indices in the interval $[1,n]$ yield the value 0; so $\Delta[i]=0$ for all $i$.  If we now receive the query $(1,2,5)$, then $\Delta$ is updated to the interval tree $[1,2] \mapsto 5, [3,n] \mapsto 0$.  If we then receive the query $(2,5,6)$, then the interval tree should be updated to $[1,1] \mapsto 5, [2,2] \mapsto 11, [3,5] \mapsto 6, [6,n] \mapsto 0$.

We can store the interval tree using a binary search tree.  If we have $m$ intervals, then there will be at most $2m$ unique endpoints of the intervals.  We store these endpoints in a binary search tree.  Each leaf node represents a single endpoint.  We will augment the nodes with a value: if a node represents the integer $a$ (an array index) and the next-largest integer endpoint is $b$, then the value $v$ at the node for $a$ means that the interval tree contains $[a,b-1] \mapsto v$.

Note that each query can be processed in $O(\lg n)$ time.  That's because a query might possibly split two existing intervals in the tree into two sub-intervals.  Each split operation can be handled in $O(\lg n)$ time by inserting one node into the  binary search tree.

Similarly, lookups can be handled in $O(\lg n)$ time, by traversing the binary search tree to find the largest node that is less than or equal to the index you're looking up.

This provides a sub-linear time solution to your problem.  Processing $q$ queries and $\ell$ lookups to the array takes $O((q+\ell) \lg n)$ time in total.


Why some Huffman codes have efficiency better than others?

First off, though the codes you gave are what the Huffman coding process produces, they aren't the only possible prefix codes for those two cases of sources.

For example, imagine if you used the code $\{\texttt{00}, \texttt{01}, \texttt{10}, \texttt{11}\}$ - then the average length is $2$ and the efficiencies drop to $82.5\%$ (case 1) and $87.5\%$ (case 2).

What the Huffman coding process guarantees is the most efficient prefix code possible for a given source, not a perfectly efficient code for every source.

So your question really is "why is it possible with some sources to make 100% efficient Huffman codes, and with other sources the most efficient possible Huffman code is less than 100% efficient?"

The answer there is that if you have a perfectly efficient Huffman code, then it's impossible to tell the difference between a stream of (source -> Huffman code) and a stream of uniformly random $\texttt{0}$s and $\texttt{1}$s. In your case number 2, with the first Huffman code, you have that situation: a stream of the source encoded by the Huffman code begins with $\texttt{0}$ half the time, and with $\texttt{1}$ half the time. When it starts with $\texttt{0}$, you start a new character from the source and so the next digit naturally is also evenly distributed. When it starts with $\texttt{1}$, half the time the next digit is $\texttt{0}$, half the time $\texttt{1}$, etc. This property (that after any sequence of bits, the chance of the next bit being $\texttt{0}$ or $\texttt{1}$ is $\frac{1}{2}$) means that the resulting binary stream has an entropy of 1 bit of entropy per output bit. (The same as a random binary source)

However, in case 1, (again using the first Huffman code) after seeing a $\texttt{1}$ in the stream, you're more likely to see a $\texttt{0}$ than a $\texttt{1}$. This means that the binary stream you get by connecting your source to the Huffman code has an entropy of less than 1 bit of entropy per output bit. (and therefore, that the binary stream is carrying less information per output bit than a random binary source)

The perfect match in case 2 happens because the probabilities of the source are all (negative) powers of $2$ and the probability of each output symbol matches the probability that a uniformly random noise source would output the symbol's Huffman string. Basically, the maximum possible efficiency for a Huffman code is a measure of how well a source's output probabilities can be approximated in binary.

Note that if we took your case 1 source and considered outputs two at a time, we'd be able to better approximate the probabilities in binary, and therefore get a more efficient Huffman code:

$$
\begin{array}{|c|l|l|}
\hline
\mathrm{output}& p & \mathrm{Huffman}\,\mathrm{code} \\ \hline
a_0a_0 & 0.25 & \texttt{10} \\ \hline
a_0a_1 & 0.15 & \texttt{000} \\ \hline
a_0a_2 & 0.075 & \texttt{0100} \\ \hline
a_0a_3 & 0.025 & \texttt{01110} \\ \hline
a_1a_0 & 0.15 & \texttt{001} \\ \hline
a_1a_1 & 0.09 & \texttt{110} \\ \hline
a_1a_2 & 0.045 & \texttt{1110} \\ \hline
a_1a_3 & 0.015 & \texttt{011010} \\ \hline
a_2a_0 & 0.075 & \texttt{0101} \\ \hline
a_2a_1 & 0.045 & \texttt{1111} \\ \hline
a_2a_2 & 0.0225 & \texttt{011000} \\ \hline
a_2a_3 & 0.0075 & \texttt{0110011} \\ \hline
a_3a_0 & 0.025 & \texttt{01111} \\ \hline
a_3a_1 & 0.015 & \texttt{011011} \\ \hline
a_3a_2 & 0.0075 & \texttt{01100100} \\ \hline
a_3a_3 & 0.0025 & \texttt{01100101} \\ \hline
\end{array}
$$

This has an average code length of $3.3275$, whereas the double-output source has an entropy of $3.30$ for an efficiency of $99.04\%$.

If you continued this process to 3 symbols at a time, you'd be able to get a $99.24\%$ efficient code. To 4 symbols, $99.43\%$ efficient.


Finding pairs of points that have a given offset

One optimization I would propose is over the brute force search:

$$
\begin{align*}
d(\mathbf{x}_i, \mathbf{x}_j) &= \lVert (\mathbf{x}_i-\mathbf{x}_j) - \mathbf{v} \rVert^2\\
&= \sum\limits_{k=1}^N (x_i^k - x_j^k-v^k)^2\\
&= \sum\limits_{k=1}^N ((x_i^k-x_j^k)^2+(v^k)^2-2v^k(x_i^k-x_j^k))\\
&= \sum\limits_{k=1}^N ((x_i^k)^2+(x_j^k)^2-2x_i^kx_j^k+(v^k)^2-2v^k(x_i^k-x_j^k))\\
\end{align*}
$$
as $(v^k)^2$ is the same for all pairs, we could simply drop it - doesn't effect minimization.

\begin{align*}
d(\mathbf{x}_i, \mathbf{x}_j) &= \sum\limits_{k=1}^N ((x_i^k)^2+(x_j^k)^2-2x_i^kx_j^k-2v^kx_i^k+2v^kx_j^k)\\
&= \sum\limits_{k=1}^N (x_i^k)^2 + \sum\limits_{k=1}^N(x_j^k)^2 - 2\sum\limits_{k=1}^N x_i^kx_j^k - 2\sum\limits_{k=1}^N v^kx_i^k + 2\sum\limits_{k=1}^N v^kx_j^k\\
\end{align*}

Let's go back to matrix notation:

\begin{align*}
d(\mathbf{x}_i, \mathbf{x}_j) &= \lVert \mathbf{x}_i \rVert+\lVert \mathbf{x}_j \rVert - 2(\mathbf{x}_i \cdot \mathbf{x}_j)- 2(\mathbf{x}_i \cdot \mathbf{v}) + 2(\mathbf{x}_j \cdot \mathbf{v})\\
\end{align*}

Note that all the terms, except the middle one is free of the pairwise computations and can be computed in $O(N)$ time and stored. To compute $(\mathbf{x}_i \cdot \mathbf{x}_j)$, one can assemble matrix $X$, which contains $\mathbf{x}_i^T$ at each row and compute $D=XX^T$. Each element in this huge symmetric matrix, would then give you the dot product per pair: $D(i,j)=(\mathbf{x}_i \cdot \mathbf{x}_j)$. If memory is of concern, you can simply revert to iterative computation and not store the intermediate dot products. All in all, this would save a lot of time in pairwise comptutations, speeding up the entire search. I assume that you could couple this easy to implement approach with any other optimization to further boost the performance. In all the calculations I omitted $sqrt$ because it doesn't influence the relative comparison of distances.

If the assumption is that $\mathbf{v}=\mathbf{0}$ ($\mathbf{v}$ is null), the entire procedure boils down to a fast computation of distance matrix - this view might benefit certain applications.


Prove or disprove NP-Completeness: An optimal ordering problem

I think your question is better written as follows (to avoid ambiguity):
Find an order $\mathbf{s}=(s_1,s_2,...s_n)$ (that is, a permutation of $(1,...,n)$) such that
$$
E_{\mathbf{s}}(\mathbf{v},\mathbf{p})=p_{s_1}w_1v_{s_1}+(1-p_{s_1})p_{s_2}w_2v_{s_2}+\cdots+\left[\prod_{j=1}^{n-1}(1-p_{s_j})\right]p_{s_n}w_nv_{s_n}.
$$
is maximized, where $w_i$ is the positive weight for the expected achievable value at the $i^{th}$ stage, $\mathbf{v}=\{v_1,v_2,\ldots,v_n\}$ and $\mathbf{p}=\{p_1,p_2,\ldots,p_n\}$ are the positive profits and the probabilities associated with the $n$ receivers. If $w_i$ is a linearly decreasing function, say, if $w_i=1-i\tau$, the objective function becomes:

$$
E_{\mathbf{s}}(\mathbf{v},\mathbf{p})=p_{s_1}(1-\tau)v_{s_1}+(1-p_{s_1})p_{s_2}(1-2\tau)v_{s_2}+\cdots+\left[\prod_{j=1}^{n-1}(1-p_{s_j})\right]p_{s_n}(1-n\tau)v_{s_n}.
$$

Now, let us consider the following two orders which differ only in the $(i-1)^{th}$ and the $i^{th}$ positions: $\mathbf{s}=\{\ldots,\underset{i-1}{1},\underset{i}{2},\ldots\}$ and $\mathbf{\tilde{s}}=\{\ldots,\underset{i-1}{2},\underset{i}{1},\ldots\}$. It is easy to show that

$$
E_\mathbf{s}>E_\mathbf{\tilde{s}}\Leftrightarrow\frac{v_1}{\frac{\tau}{\theta_1}+w_i }>\frac{v_2}{\frac{\tau}{\theta_2}+w_i }.
$$
which (I believe) implies that the problem cannot be solved by a simple index policy (i.e., a sorting algorithm), because whether $\mathbf{s}=\{\ldots,\underset{i-1}{1},\underset{i}{2},\ldots\}$ or $\mathbf{\tilde{s}}=\{\ldots,\underset{i-1}{2},\underset{i}{1},\ldots\}$ is better really depends on $w_i$ (or the stage number $i$).

Here is a paper Optimal wideband spectrum sensing order based on decision-making tree in cognitive radio, which gives an exact algorithm assuming $w_i=1-i\tau$ and they claim that it runs in polynomial time $O(n^3)$, although the space complexity seems to be exponential.

I believe their algorithm holds for general monotonically decreasing $w_i$ values (with respect to $i$).

However, it seems that they solve the problem by finding the optimum from a set of candidate sequences. The running time is assumed to be proportional to the size of this candidate set. In order to find this candidate set, a branch and bound approach is adopted, but the time needed to compute this candidate set is ignored. So I double if their running time claim is valid.. I would really appeciate it if someone can convince me that their $O(n^3)$ claim is valid (and so it only takes at most $O(n^3)$ time to find the candidate set)? or if the problem (with $w_i=1-i\tau$) is actually np-hard? Thank you!


All Turing machines are fixed in advance, independent of the input. This applies to all aspects of the machine: the state set, the alphabet, the transition function, the number of tapes. The only thing that changes from input to input is the input!


The answer depends on your standard of proof. Let's try to be very strict.
First of all, let us define words. In contrast to Peter Linz, we will not be afraid of the empty string. The set of words $\Sigma^*$ satisfies the following:

If $w \in \Sigma^*$ then either $w = \epsilon$ or $w = x\sigma$, where $x \in \Sigma^*$ and $\sigma \in \Sigma$.
$\epsilon \neq x\sigma$ for every $x \in \Sigma^*$ and $\sigma \in \Sigma$.
$x\sigma = y\tau$ iff $x=y$ and $\sigma=\tau$.
Define an inductive subset of $\Sigma^*$ to be a subset $S \subseteq \Sigma^*$ such that (i) $\epsilon \in S$ and (ii) if $x \in S$ then $x\sigma \in S$ for all $\sigma \in \Sigma$.

$\Sigma^*$ is an inductive subset.
If $S$ is an inductive subset then $S = \Sigma^*$.

Now we can define concatenation of words inductively:

$w.\epsilon = w$.
$w.(x\sigma) = (w.x)\sigma$.

Finally, we define reversal:

$\epsilon^R = \epsilon$.
$(x\sigma)^R = \sigma.x^R$, where $\sigma$ is syntactic sugar for $\epsilon \sigma$ (which we know to be in $\Sigma^*$ since it is an inductive subset).

We need several lemmas.
Lemma 1. For all $x \in \Sigma^*$, we have $\epsilon.x = x$.
Proof. Let $S = \{ x \in \Sigma^* : \epsilon.x = x \}$. We will show that $S$ is an inductive subset, and so $S = \Sigma^*$, that is, $\epsilon.x = x$ for all $x \in \Sigma^*$.
If $x = \epsilon$ then $\epsilon.\epsilon = \epsilon$. If $x = y\sigma$, where $y \in S$, then $\epsilon.x = \epsilon.y\sigma = (\epsilon.y)\sigma = y\sigma = x$, using $y \in S$. $\square$
Lemma 2. For all $x,y,z \in \Sigma^*$, $x.(y.z) = (x.y).z$.
Proof. Fix $x,y \in \Sigma^*$, and let $S = \{ z \in \Sigma^* : x.(y.z) = (x.y).z \}$. We will show that $S$ is an inductive subset, and so $S = \Sigma^*$.
If $z = \epsilon$ then $x.(y.z) = x.y = (x.y).z$.
Now suppose that $z = w\sigma$, where $w \in S$. Then
$$
x.(y.z) = x.(y.w\sigma) = x.((y.w)\sigma) = (x.(y.w))\sigma = ((x.y).w)\sigma = (x.y).(w\sigma) = (x.y).z,
$$
using $z \in S$. $\square$
Now we are ready to prove your claim.
Fix $x \in \Sigma^*$, and let $S  = \{ y \in \Sigma^* : (x.y)^R = y^R.x^R \}$. We will show that $S$ is an inductive subset, and so $S = \Sigma^*$, that is, $(x.y)^R = y^R.x^R$ for all $y \in \Sigma^*$.
If $y = \epsilon$ then
$$ (x.y)^R = x^R = \epsilon.x^R = \epsilon^R.x^R, $$
using Lemma 1.
If $y = z\sigma$, where $z \in S$, then
$$ (x.y)^R = (x.(z\sigma))^R = ((x.z)\sigma)^R = (\epsilon\sigma)^R. (x.z)^R. $$
Let us notice that $(\epsilon\sigma)^R = \epsilon\sigma.\epsilon^R = \epsilon\sigma.\epsilon = \epsilon\sigma$. Also, since $z \in S$, $(x.z)^R = z^R.x^R$. Therefore
$$ (x.y)^R = (\epsilon\sigma).(z^R.x^R) = ((\epsilon\sigma).z^R).x^R = (z\sigma)^R .x^R = y^R.x^R.$$
using Lemma 2. $\square$

While I tried to be rather strict, a completely formal proof will be even stricter: it will justify every single step, referring to a definition, a lemma, or a logical axiom. However, the proof above should be easy to convert to something that proof assistants can grok.

In practice, you can prove your claim as follows. Let $x = \sigma_1 \ldots \sigma_n$ and $y = \tau_1 \ldots \tau_m$. Then
$$
(xy)^R = (\sigma_1 \ldots \sigma_n \tau_1 \ldots \tau_m)^R = \tau_m \ldots \tau_1 \sigma_n \ldots \sigma_1 = (\tau_m \ldots \tau_1) (\sigma_n \ldots \sigma_1) = y^R x^R.
$$
At a more advanced stage, this proof can be summarized by "obvious".


What does it mean when a computer runs 'faster'?

The performance of a computer for most programs cannot be simply derived from the computer's capacity to perform operations (i.e., peak performance). As Shitikanth's answer states, the memory system and other bottlenecks can keep performance below the peak.

In addition, processor frequency is not necessarily proportional to processor performance. It is possible to increase performance without increasing frequency and to reduce performance by increasing frequency.

A substantial number of techniques can be used to increase performance.

Increasing the execution width of the processor (how many operations it can perform in parallel) can also increase performance. While increasing width tends to require reducing the frequency and programs rarely fully utilize the extra width at all times, no modern high performance processor only begins executing one instruction each cycle. (Supporting vector operations is somewhat similar, but that requires more support in software. Likewise using multiple processing cores or multiple threads within a single processing core can provide greater parallel operation while requiring more software effort.)

Speculation can also be used to increase performance. By doing work that might not have been necessarily, it is possible to increase the amount of parallelism available and to reduce execution delay. In current processors this includes branch prediction, out-of-order execution, and hardware prefetching. By predicting the path taken by a branch, the processor does not have to wait until the branch condition and target address are computed before fetching (and even executing) instructions after the branch.

(Increasing the accuracy of branch prediction can be very helpful for some workloads. Reducing the number of branch mispredictions reduces the amount of useless speculative work done by the processor. This can allow more electrical power/thermal budget to be applied to useful work. Such can also allow a deeper pipeline to have an acceptable amount of performance loss from the misprediction penalty. A deeper pipeline allows higher frequency but increases the cost of a branch misprediction--simplistically N pipeline stages of work must be discarded on a misprediction so increasing the number of pipeline stages increases the cost of mispredictions.)

Out-of-order execution allows (usually useful) work to be done while one or more instructions wait for a result from a previous instruction. Increasing the number of "future" instructions that can be considered as candidates for execution increases the processor's ability to tolerate delayed results. Out-of-order execution also allows more operations to execute in parallel by relaxing name dependencies (where an instruction reuses an address/name but does not have a value dependency).

Hardware prefetching speculates that the value prefetched will be used in the near future. Such allows the latency of memory accesses to be reduced. Theoretically prefetching could even be used to distribute the use of memory bandwidth through time (by scheduling useful prefetches during low demand access activity), though prefetching is generally a trade-off between latency and bandwidth use. In addition, it is often more bandwidth efficient to fetch multiple cache blocks that are within a single DRAM page. (Scheduling writebacks to memory can also increase effective bandwidth.)

Cache performance is also an area where computer performance can be improved. Placement policies (where a block is allocated within the physical cache--e.g., Non-Uniform Cache Architectures have been proposed and even implemented) and replacement policies (which block to drop from the cache when a new block is brought into the cache) can increase cache performance by reducing latency in more common or more timing critical cases.

Greater integration of the components of a system can also increase performance by reducing communication delay (and power use which is a significant limiter of computer performance).

In addition, specialized hardware can perform operations faster and/or more efficiently than more general-purpose hardware. (E.g., for decades performance-oriented processors have implemented specialized hardware to perform multiplication rather than reusing the hardware provided for addition. More recently, cryptographic and other specialized hardware has been added.)


Is $x^2+x+1 (mod 2)$ a one-way function?

A one-way function is a function from $\{0,1\}^*$ to $\{0,1\}^*$ which satisfies certain properties. Your function only accepts a single bit as input, so in particular isn't a one-way function.

We don't know whether one-way functions exist, though many people conjecture that they do. Proving that one-way functions exist is harder than proving $\mathsf{P} \neq \mathsf{NP}$, that is, if one-way functions exist then $\mathsf{P} \neq \mathsf{NP}$. Therefore proving that a given function is one-way is expected to be very difficult, though some candidates do exist.


No.  An algorithm that has access to some information can always ignore it and make decisions without looking at it, and then its externally observable behavior will be indistinguishable from an algorithm that doesn't have access to that information; so no verifier can tell the two apart.
I suggest being a bit cautious: when we talk about words like "knowledge" in the context of algorithm, we are applying some human intuition and interpretation to the underlying mathematics.  The precise meaning is given by the formal mathematical definition.
Incidentally, it's called a proof of knowledge, not a knowledge proof.


First of all, we can enumerate over all 32 possibilities of which of the two alternatives is chosen for each $m_i$ (whether $m_i \geq n_i$ or $m_i = 0$). We will analyze, for simplicity, the case where $m_i \geq n_i$ for all $i$. Let $\mu_i = m_i - n_i$, so that $\mu_i$ is some arbitrary non-negative integer. We now want to minimize the quantity $\sum_i \mu_i a_i p_i$ under the constraint $\sum_i \mu_i a_i \geq P$ (where $P$ is a function of other known parameters).

You can now reduce your problem to KNAPSACK as described in a question on cstheory.


When is Huffman code the most unoptimal?

There are several definitions of "unoptimal".
As vonbrand noted, Huffman coding falls back to binary encoding if all frequencies are equal.
For longest code length, this happens if the frequencies are Fibonacci numbers.
For worst compression rate compared to the entropy, this happens with an alphabet of two symbols where $p_0 = \varepsilon$ and $p_1 = 1-\varepsilon$. The Shannon entropy approaches $0$ bits per symbol as $\varepsilon \rightarrow 0$, but any Huffman code requires $1$ bit per symbol.
For size of the Huffman tree, there is no "worst case", because the size is the same no matter what the frequencies are. For an alphabet of $n$ symbols, the Huffman tree must have $n$ leaves and $n-1$ branches.


step 1 : At first let me say that , property 4 which states that children of a red node , should be black , comes from the definition of red-black tree , because 2 (or more) red nodes can't come after each other .
step 2 : For the statement that is a result of property 4 :
let's consider a path from root to a leaf , which consists of 2K nodes, and the number of Red ones, is more than the number of black ones, so at least number of red nodes must be K+1 and therefore number of black nodes is K-1. From property 4 we shouldn't put 2 (or more ) red nodes consecutively , so between every 2 red nodes , we should put a black one and since we have (at least) K+1 red node and (at most) K-1 black nodes , after we put the Kth red node , we will run out of black nodes and we have to put the (K+1)th red node right after the Kth red node , so we get two red nodes placed consecutively (you can prove it by induction )and this is in contradiction with Red-Black tree definition. so "at least half the nodes on any simple path from the root to a leaf, not including the root, must be black"
step 3 : For the Height of the tree :
we know that the height of a tree ,  is the number of edges in the longest path from root to a leaf and from what we proved in step 2 , at least half of the nodes on this path can be black , so if we have the height of h , at least we have h/2 black nodes , which comes to say that the black-height is at least h/2 .
step 4 : And for your solution , I guess you are being too general , in my idea you'd better consider number of red and black nodes , in an arbitrary path from root to a leaf rather than in the whole tree .
Hope it works as an idea not the whole solution :)


How do we formally regard a function that takes a lookup set as a parameter?

Your $\phi$ is stateful; the value of $\phi(x,A)$ depends on what parameters you have previously evaluated it with.  As such, it is not a mathematical function.  Mathematical functions are stateless.

Formalization serves a purpose: to describe clearly and precisely.  It's not to blindly follow rules, but to serve as an aid to communication.  As long as you have described what you want clearly and precisely,  in a way that a reader is likely to understand, you are good.  So, don't call $\phi$ a function, as that will confuse readers; but you can describe the intended semantics of what you want the procedure $\phi$ to return, in terms of its parameters and its state.


Optimizing cheap functions on mixed search space

In general you can't. Optimization is a tricky business and proper solutions are only known if your $f$ and/or your search space belong to some restricted class.

You can try various heuristics. Things to google for include "genetic algorithms", "evolutionary algorithms", and "simulated annealing".


I think there is a problem here because we are not using the fact that $f$ and $g$ are partial recursive.

Yes, you are, or at least you should be. Consider $h'(x) = \textrm{step}(f(x), \Omega(x))$ where $\Omega$ is not partial recursive. Would you consider that to be partial recursive? If not, why not?

If you define $h(x)$ as your friend has, you need to prove firstly that it's equivalent to the original definition. Once you've done that, it suffices to prove that it's partial recursive. But composition of p.r. functions gives a p.r. function, which is the key step that either your friend forgot to state or that you have overlooked.


Finding recurrence relation for running time of an algorithm

For starters, there are a few ways to prove recursive complexity. Some helpful notes can be found all over. For this problem, we can think about the recursion tree. The root of the tree is the Calc_a(n) call, and it's children are all $n-1$ nodes for each Calc_a(i) call initiated by the original Calc_a(n) call. For each of it's children, we can define the subtree rooted at them in the same manner. Our first step will be to determine how many nodes are in this tree.

Lets for some call Calc_a(n), lets see how many times Calc_a(i) is called for some $i<n$. This is the same as counting all Calc_a(i) nodes in the tree defined above. Let's first notice a pattern.

Calc_a(n-1) is only called once, that is clear.
Calc_a(n-2) will be called by the original Calc_a(n) call as well as the Calc_a(n-1). 2 calls
What about Calc_a(n-3)? Well we have 1 from the original call, and we can see that there will be two calls from Calc_a(n-1), and one more from Calc_a(n-2) 4 calls

Why are there two calls from Calc_a(i-1)? Well, in the previous bullet point we see that for any $i$, Calc_a(i-2) will be called twice for every Calc_a(n). We can use that logic here.

Calc_a(n-4)? We have one from the original call. As we can see in the previous bullet point, there will be 4 resulting calls to Calc_a(n-4) from Calc_a(n-1), 2 from Calc_a(n-2), and 1 more from Calc_a(n-3) 8 calls

Again we use the fact that the previous bullet point showed that there are 4 resulting calls to Calc_a(i-3) from any Calc_a(i) call.

We notice the pattern unfold that any Calc_a(i) is called twice as many times as Calc_a(i+1). Therefore Calc_a(i) is called $2^{n-i-1}$ times.

$$\sum_{i=1}^{n-1}2^{n-i-1}=\sum_{i=0}^{n-2}2^{i}=2^{n-1}$$
(I'm not sure if you're expected to include the original Calc_a(n) call, if you are, just add 1)

Proof Method 1

Now, as far as $T(n)$ goes, we can define it as $T(n)=f(n)+\sum_{i=1}^{n-1}T(i)$ where $f(n)$ is the work done in the function not including the recursive calls. As I'm sure you can tell, this is just a constant, so each node in the work tree does constant work. So we've determined the number of nodes in the tree. This means that the total work of the tree is simply $T(n)\approxeq 2^{n-1}$ or $T(n)=\theta(2^{n-1})$.

You may be wondering why the sum doesn't contribute to the complexity. Well, we could look at the loop and include the sum, then $T(n)=f(n)+\sum_{i=1}^{n-1}(g(i) + T(i))$ where $g(i)$ is the complexity of computing the sum from $T(i)$. However, we can just consider $g(i)$ as a constant as well, since most arithmetic operations can be theoretically considered constant time (this is definitely not always the case, but that is a whole nother topic). Because the constant complexity of the addition is dominated by the complexity of the accompanying $T(i)$ call, we arrive at the same complexity.

Proof Method 2

A more formal method of proving this, and one that may be required (from my experience) on an exam or homework, is to use induction. Generally, the Method 1 above is useful for getting a guess on the complexity. Once you have a good guess, you use induction to prove it, as suggested in the comments below.

Claim: $T(n)=\theta(2^{n-1})$

Base case: $T(1)=1$ (we can also see that $T(2)=2$ and $T(3)=4$) (Notice we are counting the number of calls to Calc_a()

Inductive step
\begin{align*}
T(n+1) & = f(n+1) + \sum_{i=1}^n ( g(i) + T(i)) \\
& =     f(n+1) + \sum_{i=1}^{n-1} (g(i) + T(i)) + (T(n) + g(n)) \\
& =   f(n+1) + T(n) - f(n)+ T(n) + g(n)\\
&  =     2T(n) + g(n) \\
& \leq 2^n+c  \quad \text{for some } c\geq g(n)
\end{align*}
Where the last line follows from the inductive hypothesis and the fact that $g(n)$ is a constant i.e. $g(n)=O(1)$.


Calculating Floating point Operations Per Second(FLOPS) and Integer Operations Per Second(IOPS)

It really depends on the optimizer. If you compile it with optimization, it might get rid of the loop, and then it will take rather less than 0.431635 seconds. Otherwise, it seems like you have four to five floating point instructions per iteration (including int to float conversion, once or twice, depending on the optimizer), so $4\cdot10^9$ or $5\cdot10^9$ in total. Divide this by 0.431635 to get your FLOPS, which will be around $10^{10}$, or 10 GFLOPS.


LTL Model of (infinitely often p) ∧ ( infinitely often q) ∧ (¬ Eventually (p ∧ q))?

Hint: Take $p$ to mean even number, $q = \neg p$ meaning odd number.

Can you come up with a model where you have infinitely often $p$ and infinitely often $q$ but never both at the same time?


SQL, optimizing a select statement in relational algebra

I suspect this is a homework question.

Edit: OK, you're trying to invent your own homework. Well done for trying. You might have bitten off too much.

We need first to sort out the headings of your relations. As per my comment above, Cartesian product must have no attributes in common between operands. I'll assume headings: R(a,b), S(c,d), T(e,f) -- that is, no b in common between R, S; no d in common between S, T. Then I don't need to put the dot-prefix on attribute names. Your question becomes:

$\pi_{a,d} (\sigma_{(b = "d" \land d \geq 100) \lor f \geq 200}((R\times S)\times T))$

(If you do want attributes in common, then instead of $\times$, use Natural Join $\bowtie$. And the whole point about Natural Join (a beautiful operation, at the heart of the Relational Model) is that it 'commons up' the attribute names. So you still don't need the dot-prefix.

And what it's trying to teach you is that the Boolean operators (AND /\, OR \/) within a Select expression (sigma) are equivalent to certain set operators over the relations.

Edit: OK you've shown one equivalent for $\land$, which is to push the $\sigma$ inside the $\times$. More usually, you'd use set intersection $\cap$.

Yes you are allowed to 'split' a selection that is a disjunction (your sigma x\/y). Think about what is the set-theoretic operator that's equivalent to disjunction.

Edit: The set-theoretic operator is union $\cup$. For both intersection and union, we need the headings of the operands to be the same -- that is, the full Cartesian product.

Also beware: what's the relative precedence of the disjunction vs the conjunction in that sigma expression?

Edit: OK, you've answered that. So the outermost operator is $\lor$. Let's rewrite that to $\cup$ between relation values:

$\pi_{a,d} (\sigma_{(b = "d" \land d \geq 100)}((R\times S)\times T) \cup \sigma_{(f \geq 200)}((R\times S)\times T))$

Now in the left operand of $\cup$ we have a $\sigma$ with a $\land$. We can push that inside, as you've already shown. Similarly in the right operand we can push the $\sigma$ inside:

$\pi_{a,d} ( ((\sigma_{(b = "d")}R\times \sigma_{(d \geq 100)}S)\times T) \cup ((R\times S)\times \sigma_{(f \geq 200)}T))$

But notice in the right operand of $\cup$, we still have bare $(R \times S)$. So the union is going to include every (a,b) pair from S, and every (c,d) pair from R. (I suggest you try that out with a few sample sets of attribute values for those relations.) Your outermost projection, just takes a from R and d from S. So all the business with the $\sigma$s and $\land$, $\lor$ is rather pointless. And relation T is superfluous.

The most reduced form of your formula is:

$\pi_{a,d}(R \times S)$

Or even:

$(\pi_{a}(R)) \times (\pi_{d}(S))$


How to evaluate dynamical conditioning/pseudo code

First, your terminology is unusual. I wouldn't speak about "evaluating an array on an expression", but rather about "evaluating an expression using a variable assignment". Your array is, essentially, a variable assignment stating which boolean variables are true and which are false.

You can represent the expression as a syntax tree, having AND/OR internal nodes, and variable names MATH101 as leaves.

Then, you can evaluate the expression simply visiting the tree. In pseudocode:

boolean function eval(tree, array):

    if tree is a leaf X:
       return the boolean answering (X in array?)
    else if tree is OR(t1,t2):
       b1 = eval(t1, array)     # recursive calls
       b2 = eval(t2, array)
       return (b1 || b2)
    else tree must be AND(t1,t2):
       b1 = eval(t1, array)     # recursive calls
       b2 = eval(t2, array)
       return (b1 && b2)

If you want, you can even implement short-circuit evaluation to save some time. If your expressions are short it won't make any difference w.r.t. performance, though.


AVL tree balance property states for the two subtrees of a node, their height can differ at most one. Why can't it be zero?

What matters is that the height  of the tree is limited by $O(\log n)$. As long as you maintain that property your searches will remain efficient.

Forcing the height difference to be zero we get the above property. However we also get the property if we allow the difference to be 1. The crux is that the latter requires a lot less rebalancing to achieve. The average height of a node will very slightly increase due to our more relaxed tree structure but this downside is greatly overshadowed by the reduction in rebalancing operations.


What do functions look like, if I stated out with the categoical model of my type theory?

Your intuition is correct: terms are "somehow" elements of the objects. The only thing left is to figure out what elements in a category are. They cannot be literally elements because objects need not be sets (and more generally there may be no way to even "convert" an object to a set with a functor).

If I say "consider a mass point $p$ moving in $\mathbb{R}^3$" then you will immediately understand that $p$ is not actually an element of $\mathbb{R}^3$ but a map $\mathbb{R} \to \mathbb{R}^3$, i.e., the point is parameterized by time (which we take to be a real number). It is a general phenomenon that "entities" can be parameterized, and so they can be thought of as either variable elements or maps. For instance "temperature" may be thought of as a scalar field mapping the points of Earth's surface to real numbers, or it can be thought of as a real number which varies with position on the Earth.

In any case, this leads to the idea that the elements of an object $A$ in a category are simply all morphisms $B \to A$. When $B$ is the terminal object, we get the global (non-parameterized) elements, but in general we allow elements to be parameterized by any object, and so we call them generalized elements. One way to understand the Yoneda lemma is that an object in a category consists of its generalized elements.

You asked how to pass from a category to its internal type theory. Let me answer the opposite question first. Given a type theory, we can think of terms in context as the generalized elements of a type, while the closed terms are the global elements. But since generalized elements are the same thing as morphisms this tells us how to build a category out of a type theory: the morphisms are just terms in a context, quotiented by whatever equations the theory proves.

To go in the opposite direction, suppose we have a category $\mathcal{C}$ and we want to make a type theory out of it. As you said, we take the types to be the objects of $\mathcal{C}$. According to our view that "generalized elements are morphisms", the morphisms $f : A \to B$ ought to correspond to terms of type $B$ in context $A$. But we cannot just write $x : A \vdash f : B$ because there is no $x$ on the right-hand side. It would make more sense for $f$ to have the type $A \to B$, which is precisely what we do. For each morphism $f : A \to B$ we introduce a constant of type $A \to B$, which we also write as $f$. Then the correspondence is recovered: given $x : A$ there is a term $f\, x : B$.

If our type theory does not have arrow types then we have to do things a bit differently. For each morphisms $f : A \to B$ in $\mathcal{C}$ we add a unary term constructor $f$ and the typing rule
$$\frac{\Gamma \vdash e : A}{\Gamma \vdash f\,e : B}.$$
Note that $f\,e$ is just a syntactic form, namely application of the unary term constructor $f$ to the term $e$. It would make no sense to apply the morphims $f$ to the term $e$!
A type theory consists not only of types and terms, but also of equations. Our category gives us some equations, too: if the morphism $h : A \to C$ is the composition of $f : A \to B$ and $g : B \to C$, then we get the equation
$$x : A \vdash h \, x =_C g (f \, x).$$
There are some further equations. For instance, if $A$ and $B$ are objects and $C$ is their product, then we need to relate the type $C$ with the product type $A \times B$. That is, in the category there are projections $\pi_1 : C \to A$ and $\pi_2 : C \to B$ and a pairing operation $\langle{-}, {-}\rangle$, while in type theory there are projections $\mathtt{fst} : A \times B \to A$ and $\mathtt{snd} : A \times B \to B$ and pairing $({-},{-})$ (where $A \times B$ is the formal product type). We need equations which relate these, but let me skip the technicalities.

The $\beta$ and $\eta$ reduction rules are validated by a cartesian closed category. The rules about product and function types correspond to various parts of the adjunction between cartesian products and exponentials.

In conclusion, it may seem strange that we take all morphisms in a category and make them into unary constructors of the corresponding type theory. If the category is very big that gives us a very large type theory which is not syntactic in any sense of the word syntactic. Just free your mind and the rest will follow.


Using the pumping lemma for a specific language

Option 1: the word is in the language and it is of length $\geq n$, yet there is no guarantee that pumping it yields a contradiction. That is, the word can be used in the pumping lemma, but its not a good choice for proving non-regularity. Indeed, if $\text{LONGERB}$ is regular, then we know that there is a partition of $abab^{n+1}$ to three words, $xyz = abab^{n+1}$, where $|xy| \leq n$, $|y|> 0$, and $xy^iz\in \text{LONGERB}$ for every $i\geq 0$. Thus, if for example $y = ba$, then $xy^iz$ is indeed in $\text{LONGERB}$ for every $i\geq 0$ -  so we cannot reach a contradiction to the assumption that $\text{LONGERB}$ is regular.

Option 2: the word is in the language and it is of length $\geq n$. Clearly it is good for pumping in the sense that it can be pumped for some $i$ so that $xy^i z \notin \text{LONGERB}$ - this is an easy exercise and the details are left to you.

Option 3: the word is of constant length that does not depend on the pumping constant $n$, so there is no guarantee that it is of length $\geq n$, so the pumping lemma says nothing about this word. Thus, we cannot use it to apply the pumping lemma on any language with a pumping constant $n$.

Option 4: you're right, the word cannot be used when applying the pumping lemma directly on the language $\text{LONGERB}$. However, it can be used to prove the non-regularity of $\text{LONGERB}$ indirectly by applying the pumping lemma on the language $\overline{\text{LONGERB}}$ which is the language of the words over $\{a, b\}$ where the longest substring containing only $b$’s is equal or shorter than the longest substring containing only $a$’s. Indeed,  assume by contradiction that $\overline{\text{LONGERB}}$ is regular. If you consider the word $w = a^n b^n$, it is longer that $n$ and it is in the language $\overline{\text{LONGERB}}$. Then, there is a partition $xyz = a^nb^n$, where $|xy| \leq n$, $|y|> 0$, and $xy^iz\in \overline{\text{LONGERB}}$ for every $i\geq 0$. If you pump with $i = 0$, you get a contradiction. (BTW, I implicitly assumed that both a language and its complement have the same pumping constant $n$. This assumption is okay. Can you tell why?)


How does an automaton actually "compute"?

Most generally, an automata is a model of computation that describes the process how to convert an input to a solution. Converting means that there is a certain set of finite, elementary, local transformation rules, that is applied to the input. The idea behind the automata might be motivated by mechanical designs, however the concept is purely mathematical. In other words an instance of an automaton is a simplistic form of an algorithm. The concept of an automaton describes the way how computations in this model are carried out. Different models have different computational powers.

A realistic computer can be also described as a mathematical model. However the setting here is slightly different, since you will not want to build a new computer for every algorithmic problem you encounter. Also a computer is an interactive system, whereas classical automata are not. The closest model for a computer is the DFA. A computer has a large but finite set of ressources, hence the status of the system can be determined by a fixed-size description (think of a huge core dump). Depending on the input (clock, user input, etc.) the computer jumps form one state to a new state in a certain well-defined and unique way.

You might be disappointed, when you hear that closest model to a realistic computer is a DFA. But you should think of an automaton more as a formalism how to write an algorithm. And from that perspective, the way you write software (algorithms) on you computer, is equivalent to writing Turing machine programs.

Maybe you are confused by the fact, that automata work on strings, and not on other problem instances. However, this is not a big deal, since we can encode an instance as a string.


draw DFA with {w|w= Σ*0100}∩{w|w≠Σ*11Σ*}

How to draw $\{w|w≠\Sigma^*11\Sigma^*\}$:

Three states $S_0, S_1, S_2$ are needed. $S_0$ is both a initial state and an accepted state, $S_1$ is an accepted state. Whenever you read a $1$, go from $S_i$ to $S_{i+1}$. Finally let $S_2$ be the dead state.

Similarly you can draw the $\{w|w=\Sigma^* 0100\}$.

In the end, we combine these two DFAs with a cartesian product. You can look up here: https://stackoverflow.com/questions/7780521/how-to-use-the-intersection-construction-to-form-a-dfa


How to compare two objects for percentage of equivalence

One approach is to use low-rank matrix factorization to approximate the ratings matrix, then use a nearest neighbors data structure.

In particular, let $M$ be the $m \times n$ ratings matrix, where $M_{ij}$ is the rating that user $i$ has provided to user $j$.  Look for a $m\times r$ matrix $U$ and a $r \times n$ matrix $V$ such that $M$ is well-approximated by $UV$ (e.g., $||M-UV||$ is minimized, except that missing entries of $M$ are ignored).

Once you've done this, each user can be mapped to a $r$-dimensional vector that summarizes their scores.  Store the set of all of these vectors in a data structure that supports nearest neighbor search, e.g., a k-d tree.  If you have chosen $r$ small enough (e.g., 10 or so), then nearest neighbor search should be very efficient.  This will let you find the users who are most similar to a given user, and thus make a recommendation (e.g., using the  k-nearest neighbors classifier).

There are many other approaches you could use: read the extensive literature on recommender systems and collaborative filtering.

As far as your other issue:

  I have to load in all the users, every time I need to find a set of matching users for just 1 user

Keep the data structure in memory, rather than re-loading it into memory each time.


If an algorithm is $O(\log n)$, then you can conclude absolutely nothing about the running time of the algorithm. This is due to many factors, one of which is that $O(\log n)$ hides an arbitrary constant factor: both $\log n$ and $100\log n$ are $O(\log n)$ (not to mention functions such as $10^6\log\log n + 10^{15}$). There are also other reasons, but this reason is probably enough.


Is there C++ code that takes infinite time to compile?

In theory this code should compile infinitely

template<long long K>
struct t {
  enum { value = (K&1) ? t<K+1>::value : t<K-1>::value};
};
int main() {
  int i = t<1>::value;
}

But in real life compilers are limiting template instantiation depth.
Another thing is that long long is limited so you cannot represent all integers.


What are constraints on some new logic programming language and system?

It sounds like you have the impression that there are some rules on what languages you are allowed to define.  There are no such rules.  You can define whatever language you want.  You can do whatever what you want -- you're not required to do anything (there are no language police who will come arrest you for failing to prove some theorem about it).  Whether it will be useful, or used by anyone else, is a different matter.


show that special case of NP-complete problem is also NP-complete?

"Are there any general guidelines for how to do this?"

Frequently, one does that by reducing from the general case to the special case.

Otherwise, being a special case of a known NP-complete problem isn't really helpful for that.

How would one go about showing this?

Due to dynamic programming, one would prove  P = NP .


If the grammar is amenable to limited-lookahead bottom-up parsing, then the parallelism is more or less implicit in the parsing algorithm, and there is little to be gained from parallel computing, at least in the sense proposed in the post. A standard LALR(k) parser is deterministic; it only does a single table-lookup for each action, based on the current state, the lookahead token(s) and -- in the case of reductions -- a single state value popped from a known location on the parse stack.

That's not to say that there is no possible benefit from the availability of multiple CPUs, but I suspect that benefit would come from segmenting the input using some kind of simple lexical analysis (text inside balanced braces, for example) and constructing individual parse trees for each segment.

If the grammar itself is highly ambiguous, as is the case for natural-language parsing, then different algorithms will be employed. CYK parsing, for example, used as the basis for many probabilistic parsers, can benefit significantly from parallel processing, and it is easy to find recent (and not-so-recent) papers on the subject on the internet. I found a dozen in a few seconds, and I won't bother pasting all of them particularly since I didn't read them, but I think that this paper by Mark Johnson has some pretty impressive results.

The answer dodges around the actual question, because I think the algorithmic analysis required to efficiently parallelise chart-parsing is more sophisticated than simply exploring alternative productions in parallel. But I hope it has some utility.


Find Hamiltonian cycle in polynomial time

Perhaps the most comprehensive list is available via ISGCI, along with references. Examples for which the problem is easy include bounded treewidth graphs and many subclasses of chordal graphs.

As to why exponential time seems unavoidable in general, we don't strictly know. As far as we know, P = NP is also possible.