How to solve the following recurrence? $T(n) = 4T(\frac{n}{2})+n!$ Hello all I am kinda confused on how to solve the above recurrence since the masters theorem would not work with the above equation. Could anyone please help me solving this and showing me the steps? Requirement is to find asymptotically tightest bound.

$$T(n) = 4T(\frac{n}{2})+n!$$

"... the masters theorem would not work with the above equation" is not right. From the master theorem, as we know $n! = \Omega(n^3)$, and $4\left(\frac{n}{2}\right)! < 0.9 n!$ ($k = 0.9$) for large enough $n$, so $T(n) = \Theta(n!)$.

To know more about this case, follow this link and find third case of the master theorem.


Call stack is hard to maintain in my brain. What should I? When I study Binary Search Tree, I try to use a pencil and paper to scratch the process of in-order traversal. However, I find that it is hard to maintain the call stack in my brain without paper and notes when the height BST is high.
Question: What should I? Is it normal and should I practice more?

Do not consider call stacks for recursive algorithms. Ever. Forbidden!
Learn to understand recursive algorithms like any other algorithm that calls other procedures: Assume the calls do their work correctly, and concentrate on making sure the right calls are made, and the results are combined correctly.
Separately, try to find some criterion by which the recursive calls are to "smaller" instances of the problem (assuming instance sizes are e.g. positive integers), and that all "small enough" instances are solved correctly by "base cases" (without recursive calls).
Often the recursive algorithm is modelled on some recursive definition of the structure at hand, then the mapping is simple to prove correct. For an entertaining example of a recursive program that doesn't clearly fall into this category, read and understand Rob Pike's regexp matcher (exegesis by Brian Kernighan)


Can someone clarify this unification algorithm? I've been having trouble understanding a unification algorithm for first order logic, as I don't know what a compound expression is. I googled it, but found nothing relevant. I also don't know what a list means in this context. A list of what?

Edit: I think I've cleared up with compound expressions are and what lists contain in this context, from Yuval Filmus's answer. However, now I have other problems:

In Unify-Var, it uses the variable(?) val, even though val was never declared. Could {var/val} E theta (with E meaning is a subset of) instead be a function that returns whether var is already in theta, regardless of what value it's mapped to?
The algorithm seems to break when unifying compound expressions. To unify them, it breaks compound expressions into two lists: one for function symbols and one for arguments and then calls Unify on both individually. When trying to unify the list of function symbols, it breaks the list into individual function symbols and then calls Unify on each individual function symbol. But Unify has no case to deal with function symbols, so it just returns failure, even if the two function symbols to be unified are identical!

Thanks.

Pseudocode from Artificial Intelligence A Modern Approach (3rd Edition): Figure 9.1, page
328:

function UNIFY(x, y, theta) returns a substitution to make x and y identical
  inputs: x, a variable, constant, list, or compound expression
          y, a variable, constant, list, or compound expression
          theta, the substitution built up so far (optional, defaults to empty)

  if theta = failure then return failure
  else if x = y the return theta
  else if VARIABLE?(x) then return UNIFY-VAR(x, y, theta)
  else if VARIABLE?(y) then return UNIFY-VAR(y, x, theta)
  else if COMPOUND?(x) and COMPOUND?(y) then
      return UNIFY(x.ARGS, y.ARGS, UNIFY(x.OP, y.OP, theta))
  else if LIST?(x) and LIST?(y) then
      return UNIFY(x.REST, y.REST, UNIFY(x.FIRST, y.FIRST, theta))
  else return failure

---------------------------------------------------------------------------------------------------

function UNIFY-VAR(var, x, theta) returns a substitution

  if {var/val} E theta then return UNIFY(val, x, theta)
  else if {x/val} E theta then return UNIFY(var, val, theta)
  else if OCCUR-CHECK?(var, x) then return failure
  else return add {var/x} to theta

Figure 9.1 The unification algorithm. The algorithm works by comparing the
structures of the inputs, elements by element. The substitution theta that is
the argument to UNIFY is built up along the way and is used to make sure that
later comparisons are consistent with bindings that were established earlier.
In a compound expression, such as F(A, B), the OP field picks out the
function symbol F and the ARGS field picks out the argument list (A, B).

First, unification algorithms are tricky. Studying other textbooks will help.

Second, things will probably get clearer if you look at actual code implementations. Have a look at the online code repository for your textbook. The code in Lisp, for example, is here.

A helpful note to remember when looking at first-order unification algorithms is that function symbols and predicates must match exactly in order to be correct.

On to your questions.

(Where is val declared?) This is a notational trick in the pseudocode that creates more confusion than good. It hearkens back to the old days of Lisp association lists. Maybe giving an example of theta would help: ((x 1) (y 2) (z 3)). This means x is bound to 1, y is bound to 2, and z is bound to 3. So var/val refers to a pair in theta like (x 1). So the first clause in UNIFY-VAR means, "if the pair (var val) is a member of theta, then return the result of doing UNIFY on whatever val is in that pair, with x and theta".
(How do function symbols get unified?) Remember that function symbols must match exactly as I pointed out above. So actually the clause else if x = y then return theta covers this. This is via a recursive call through an outer COMPOUND case.


Proof by induction concerning approximation algorithm for subset sum Assignment question

For algorithm APPROX-SUBSET-SUM, prove by induction on $i$ that for every element $y \in P_i$ that is at most the target sum $T$, there is a $z \in L_i$ such that

$$\frac{y}{(1+\frac{\epsilon}{2n})^i} \leq z \leq y$$

Here $\epsilon$ is the relative error bound, $P_i$ is the set of all subset sums of the first $i$ elements in the universe, and $L_i$ is the corresponding discretized set produced by APPROX-SUBSET-SUM.

My thoughts

I understand that proof by induction means that proving something for all natural numbers by first proving that it is true for $0$, and that if it is true for $n$ (or sometimes, for all numbers up to $n$), then it is true also for $n+1$. However, do I simply substitute $0$ and $n+1$ into $n$ and that would solve the question completely?

You haven't described the approximation algorithm, so I assume it's something like the following one (perhaps with a few changes in some details):

Input: a universe $U = \{x_1,\ldots,x_n\}$, a target sum $T$, and an accuracy parameter $\epsilon$.
Initialize $L_i = \{0\}$.
For $i = 1, \ldots, n$:

Compute $L_{i+1} = L_i \cup \{\ell + x_i : \ell \in L_i\}$.

Remove all element larger than $T$ from $L_{i+1}$.

Replace each element $\ell \in L_{i+1}$ by the largest power of $1+\epsilon/2n$ which is at most $\ell$.

Return the element in $L_n$ closest to $T$.

This is a $1+O(\epsilon)$-approximation algorithm, in the sense that it can tell whether there is a subset of $U$ summing to roughly $T$, up to a factor of $1+O(\epsilon)$.

The exercise asks you to show that for each $i \in \{0,\ldots,n\}$, the following is true: if $y \in P_i$ (the set of all sums of subsets of $\{x_1,\ldots,x_i\}$) is at most $T$, then there is an element $z \in L_i$ which is approximately equal to $y$, in the sense that
$$ \frac{y}{(1+\frac{\epsilon}{2n})^i} \leq z \leq y. $$
Taking $i = n$ will give the desired analysis of the complete algorithm.

Let us denote the claim symbolically by $C_i$. The exercise suggests that this claim can be proved by induction on $i$. This suggests the following plan to prove $C_0,\ldots,C_n$:

Prove $C_0$.
For $i=1,\ldots,n$, assuming $C_{i-1}$ is true, prove that $C_i$ is true.

To find out what claim $C_0$ or $C_{i-1}$ is, you will need to substitute $0$ or $i-1$ for $i$ in the claim.

Good luck with executing this plan.


Are partial recursive functions analogous to recursive languages or r.e. languages? From Ullman and Hopcroft's Introduction to Automata Theory, Language, and Computation 1ed 1979:

  The assumption that the intuitive notion of "computable function"
  can be identified with the class of partial recursive functions is
  known as Church's hypothesis or the Church-Turing thesis.

  A problem whose language is recursive is said to be decidable.
  Otherwise, the problem is undecidable. That is, a problem is
  undecidable if there is no algorithm that takes as input an
  instance of the problem and determines whether the answer to that
  instance is "yes" or "no."

  Note that one TM may compute a function of one argument, a different
  function of two arguments, and so on. Also note that if TM M computes
  function f of k arguments, then f need not have a value for all
  different k-tuples of integers. ...

  In a sense,

  the partial recursive functions are analogous to the r.e. languages, since they are computed by Turing machines that may or
  may not halt on a given input.
  The total recursive functions correspond to the recursive languages, since they are computed by TM's that always halt. ...

How do these go together?

From the following first two quotes

The first quote says that computability can be identified with the class of partial recursive functions,
the second quote seems to say that computability can be identified with recursive languages.

Note that the second quote says about decidability while here I uses computability, so I assume that computability and decidability are the same or consistent concepts, but is it true?

Do they imply that partial recursive functions and recursive
languages are analogous to each other, as far as computability/decidability is concerned?
The third quote says that "in a sense",

the partial recursive functions are analogous to the r.e. languages
The total recursive functions correspond to the recursive languages.

Does the third quote contradict the implication from the first
two quotes as pointed out above in part 1?

In what "sense", does the third quote mean?

For my related confusion about the third quote, see
Do the Turing machines involved in Chruch-Turing thesis have to halt on all the inputs?

Let me quote from the second edition of the same textbook, section 9.1 (sorry, I don't have the first one):

  Recall that a language L is recursively enumerable (abbreviated RE) if L = L(M) for some TM M. Also, we shall in Section 9.2 introduce "recursive" or "decidable" languages that are not only recursively enumerable, but are accepted by a TM that always halts, regardless of whether or not it accepts.

Therefore recursive languages are associated to total recursive functions, not partial.

Hope this answers both the questions.

EDIT: to answer the comment:

On the one hand, the reason lies on intuition: the Church-Turing thesis is about capturing the intuitive idea of "effective computability" or "things that we can actually compute". Imagine a program that, if there is a correct answer then it computes the answer, otherwise it never halts (i.e. it gives an answer only if there is an answer). Would you say that such a program computes the answer or not?

But on the other hand, if this intuitive picture doesn't convince you,  consider the following (way more concrete): consider an effective enumeration $(\varphi_i)_{i\in\mathbb{N}}$ of all total recursive functions and consider the function $\varphi:=x\mapsto\varphi_x(x)+1$. Now it is clear that you can compute $\varphi$: you can find the $x$-th function, you can compute it (as it is recursive) and you can sum 1 (as sum is recursive). But $\varphi$ cannot be total by a diagonal argument: if it were total than it would have its own index $i$, therefore

$$ \varphi(i) = \varphi_i(i)+1 = \varphi(i) +1 $$

which is a contradiction. This problem vanishes if you consider instead partial functions.


Axioms - proof of halt I am new to this forum and this is my first post. I am interested in solving a problem, but cannot find the way to think about it. If anyone can guide me through it, I would be obliged:

Let F be some system of axioms. You can assume F is sound (that is, it only proves true statements), and also that F is strong enough for Godel's Incompleteness Theorem to apply to it. Let G ( F ) be the mathematical encoding of "This sentence is not provable in F ." Also, let MF be a Turing machine that generates all possible F -proofs, one by one, and that halts if and only if it encounters a proof of G ( F ).

a) Does MF halt? Why or why not?

b) Is there a proof in F that MF halts, or a proof in F that MF does not halt? Why or why not?

Let $CON(F)$ denote the sentence: "F is consistent".

You can prove $CON(F)\rightarrow \text{ MF does not halt}$, since if MF halts you have $F\vdash G(F)$ and thus by soundness $F\not\vdash G(F)$.

You cannot however, prove this unconditionally (unless your system is inconsistent), since this would mean $F\not\vdash G(F)$ which implies consistency (why?).


Are $CF_{TM}$, $\space $ $\overline{CF_{TM}}$ Turing-recognizable? I have searched the site well through, and also using Google and notes and couldn't find an answer to a question I am wondering about.

Given:

$$CF_{TM} =\{ \langle M \rangle \mid \text{$M$ is a TM description and $L(M)$ is a context-free language} \}$$

Are $CF_{TM}$,$\space $ $\overline{CF_{TM}}$ Turing-recognizable?

In order for a machine to be turing recognizable, there should exist a Turing machine that will halt and accept only string on that language, and for strings no in that language, it should reject or not halt at all.

So i am truly wondering about the relationship between context free languages and being Turing-recognizable, are $CF_{TM}$, $\space $ $\overline{CF_{TM}}$ Turing-recognizable?

This question describes a nice situation to introduce a partial version of the generalized Rice's theorem.
A partial version of the generalized Rice's Theorem
For $S$ be a subset of Turing-recognizable languages, let $L_S$ be the set of TMs that recognize a language in $S$, that is,
$$L_S = \{ \langle M \rangle \mid L(M) \in S \}.$$
Suppose $L_1 \in S$, $L_1 \subset L_2$ and $L_2 \not\in S$. Then $L_S$ is not Turing-recognizable.
$CF_{\text{TM}}$ is not Turing-recognizable.
$CF_{\text{TM}}=L_{\text{CFL}}$, where $\text{CFL}$ is the set of all context-free languages. Let $L_1=\emptyset$ and $L_2=\{a^{n^2}\mid n\in \Bbb N\}$. Then $L_1\subset L_2$, $L_1\in \text{CFL}$, $L_2\not\in \text{CFL}$. So, $L_{\text{CFL}}$ is not Turing-recognizable.
$\overline{CF_{TM}}$ is not Turing-recognizable
$\overline{CF_{\text{TM}}}=\{ s : s\text{ is a string that does not encode a TM}\}\sqcup L_{\overline{\text{CFL}}}$, where $\overline{\text{CFL}}$ is the set of all non-context-free formal languages. Let $L_1=\{a^{n^2}\mid n\in \Bbb N\}$ and $L_2=\{a^n\mid n\in \Bbb N\}$. Then $L_1\subset L_2$, $L_1\in \overline{\text{CFL}}$, $L_2\not\in \overline{\text{CFL}}$. So, $L_{\overline{\text{CFL}}}$ is not Turing-recognizable.
Proof of the partial version of the generalized Rice's Theorem
Suppose $L_S$ is recognized by a TM $M_S$. We will construct a TM that recognizes $\overline{HALT_{\text{TM}}}=\{\langle M,w\rangle\mid M\text{ does not halt on }w\}$, which is known as not Turing-recognizable, hence a contradiction. The TM  works as follows.

On input $\langle M, w\rangle$:

Construct a TM $T_{M,w}$ that works as follows:
On input $x$:

Run $M_1$ on $x$, and accept if $M_1$ accepts. Here $M_1$ is a TM that recognizes $L_1$.
At the same time, also run $M$ on $w$. If $M$ accepts, run $M_2$ on $x$, and accept if $M_2$ accepts.  Here $M_2$ is a TM that recognizes $L_2$.

Run $M_S$ on $T_{M,w}$, and accept if $M_S$ accepts.

Note this TM accepts $\langle M,w\rangle$ if and only if $M_S$ accepts $\langle T_{M,w}\rangle$, which means $L(T_{M,w})\in S$. Also note
$$L(T_{M,w})=\begin{cases}
L_1 & \text{if $M$ does not halt on $w$},\\
L_2 & \text{otherwise},
\end{cases}$$
so the TM accepts $\langle M,w\rangle$ if and only if $M$ does not halt on $w$, which indeed recognizes $\overline{HALT_{\mathrm{TM}}}$.
The above proof is a modified version of xskxzr's nice proof of his lemma in his answer.

Exercises
Exercise 1. Show that a context-free language (that is defined by a context-free grammar) is Turing-recognizable. Show that a non-context-free formal language (that is defined by an unrestricted grammar and that cannot be defined by a context-free grammar) is Turing-recognizable.
Exercise 2. (One minutes or two) Check that both the question and this answer remain valid if we replace "context-free" by "regular".

Exercise 3. Show that $\overline{\text{CFL}}$, the set of all non-context-free formal languages given by their grammars properly encoded by some fixed scheme, is not Turing-recognizable. Hence, $L_{\overline{\text{CFL}}}$ cannot be Turing-recognizable either.
EXercise 3. Read the full version of generalized Rice's Theorem. Can you prove it? (This might not be easy.)


Why does Lamport clocks increment on both message received and sent? According to wikipedia, Lamport clocks need to be incremented when sending a message (time = time + 1) and when receiving a message (time = max(time_stamp, time) + 1).
In my implementation, Increment() is used when sending and Witness() is used when receiving, each of them following the previous rules.
I can't understand why not only Increment() actually increment the counter, that is why Witness() does not simply do time = max(time_stamp, time) instead of time = max(time_stamp, time) + 1.
The source of my confusion is the following scenario:

clock start at 1
a message is sent, clock is at 2
this message is seen locally, clock is now at 3

In this scenario, the clock incremented twice for the same message. Ideally it would just be one. Did I break something by witnessing the clock within the same process? Did I get something wrong?

From Leslie Lamport Time, Clocks, and the Ordering of Events in a Distributed System:

The space-time diagram of Figure 1 might then yield the picture in Figure 2. Condition C 1 means that there must be a tick line between any two events on a process line, and condition C2 means that every message line must cross
a tick line.

I think my confusion was on what actually is an event.
In Lamport's paper and in Wikipedia, sending and receiving the messages are the events. In that case, incrementing the counter both when sending and receiving a message make sense, to ensure that a clock tick separate those events.
In my case, the data structure modification are the events. The message passing between the processes is irrelevant. In that case, I believe that incrementing the counter only when the data change make sense.
Now, if applying this Lamport clocks principle this way still qualify as Lamport clocks and holds all the related properties, I do not know.


Computing the clustering coefficient I saw in this video that computing clustering coefficient of central node  of a star graph using the following algorithm is $\Theta(n^2)$ and for a clique it is $\Theta(n^3)$. is that correct?

def clustering_coefficient(G,v):
    neighbors = G[v].keys()
    if len(neighbors) == 1: return 0.0
    links = 0.0
    for w in neighbors:
        for u in neighbors:
            if u in G[w]: links += 0.5
    return 2.0*links/(len(neighbors)*(len(neighbors)-1))

Edit: My answer was based on assuming the code given as a pseudo-code, rather than a concrete Python example. For Python, the data structure is a dictionary (hash map) and so finding neighbors (the in) operation will in fact be $O(1)$ on average, giving $\Theta(n^2)$ overall complexity on average for both graphs. Rare worst cases in hash maps can depend on implementation. In general for pseudo-codes, see my original answer below.

The complexity also depends on the data structure being used for storing the graph $G$. If an adjacency list is used, where for every vertex $v$ in the graph, its neighbors are stored in an array/linked list, then the above complexities are valid. Here's how:

For the central node of the star graph, there are $n-1$ neighboring vertices. Then, the pair of neighbors of this central node - the $w$ and $u$ vertices - can be selected in $\Theta(n^2)$ ways. For each such $w$, checking if $u$ is a neighbor of $w$ can be done in $\Theta(1)$ time, since each such $w$ only has $1$ neighbor - the central node $v$. This gives overall complexity of $\Theta(n^2)$.

For a clique of size $n$, every node has $\Theta(n)$ neighbors. Then, the pair of neighbors $w$ and $u$ for any node $v$ can be chosen in $\Theta(n^2)$ ways - this is the complexity of the two outer for loops. For every such $w$, checking if $u$ is its neighbor requires going through the list of $\Theta(n)$ neighbors of $w$, and so the if statement has $\Theta(n)$ complexity. This takes the overall complexity of the two nested for loops and the if loop to $\Theta(n^3)$.

However, there are other representations of the graph data structure, which give different (generally better) complexities for the same algorithm. For example, having an adjacency matrix to represent the graph means that the check for $u$ is a neighbor of $w$ can be done in $\Theta(1)$ time, even for a clique. Similarly, using a hash set instead of list/array to store neighbors would mean checking for neighbors can be done in $\Theta(1)$ on average. These are the more common representation. You could also choose an arbitrary representation where neighbors are sorted (just to demonstrate how the underlying data structure can affect algorithm complexity). In such a case, checking for neighbors will take $\Theta(\log n)$, giving overall $\Theta(n^2 \log n)$. Each has its pros and cons, and the appropriate data structure must be chosen according to your situation.


Face recognition system with a sparse dataset I have a dataset of 100 ID's, each ID with only a single unique face image. How can I develop an effective face recognition system to recognise only these faces?

I was thinking Deep Learning but the dataset is so sparse. It would be 100 classes each with a single data point (the image).

You can apply transfer learning.  Leverage one of the existing datasets and deep learning networks that can classify faces e.g. celebrities.

Add/remove layers on top of the feature extraction layers and use your small data set.  Provided that the base dataset / network is large and rich enough you should be able to apply it to your dataset.

See https://cs231n.github.io/transfer-learning/


Literature request: Generating all vertex subsets of a graph I am working in an algorithm which finds a unique maximal independent set of vertices. Then, using this set, one can construct all other vertex subsets. I assume this might have some applications outside mathematics, especially in computer science, but I am not sure where I can read about such applications. Does anyone have any good literature suggestion which describes scenarios where this could be useful?  The idea is somehow similar to that of using edge activities as defined by Tutte in order to construct all possible subgraphs of a given graph by using the set of its trees.

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


Can deep learning be applied to nonlinear parameter estimation problems? Suppose $y=f(x,p)$ while $x$ and $y$ are variables and $p$ is the parameter (all in vector form), and $f$ is an explicit nonlinear function. We have:

$$y_1^{(1)} = f(x_1^{(1)},p_1), y_1^{(2)} = f(x_1^{(2)},p_1), ..., y_1^{(n_1)} = f(x_1^{(n_1)},p_1)$$

$$y_2^{(1)} = f(x_2^{(1)},p_2), y_2^{(2)} = f(x_2^{(2)},p_2), ..., y_1^{(n_2)} = f(x_1^{(n_2)},p_2)$$

$$...$$

$$y_i^{(1)} = f(x_i^{(1)},p_i), y_i^{(2)} = f(x_i^{(2)},p_i), ..., y_1^{(n_i)} = f(x_1^{(n_i)},p_i)$$

$$...$$

If given a set of $(x_i^{(1)},y_i^{(1)}), (x_i^{(2)},y_i^{(2)}), ...$, we can estimate the value of $p_i$ by means of optimization such as gradient descent or any other algorithms.

My question is : Can the parameter estimation problem described above, which is conventionally solved by optimization methods, be solved by deep learning?

Since $f$ is an explicit math formula, a very large training set can be easily generated by sampling $x$ and $p$ from some sort of prior distribution.

The difficulties I met during searching the answer on google:

Since DL itself is an optimization problem (or parameter estimation problem), what I found is mainly basic tutorials of DL rather than something directly relevant.
A similar question on Quora: How can I apply machine learning to parameter estimation problem in control theory? Is there any example study you can suggest?. The only answer to this question is very brief and only provides a 132-page thesis. I scanned the thesis and found that it seemed to solve a rather complicated image processing problem by reinforcement learning. I'm not sure if it is relevant.
A similar question on StackOverflow: Can I do nonlinear regression with deep learning ? How?. But the author tried to use deep learning to find the relationship between $x$ and $y$, which is different from my question: the function $f$ is already known, I just want the $p$.

The intuition of solving parameter estimation by deep learning instead of direct optimization could be:

Optimization methods such as gradient descent is prone to find a local optima. Maybe DL will have some magic.
In practice, the parameter estimation problem may need to be solved many times for different set of $(x,y)$, which requires speed. So conventional optimization methods may be too slow for this. In a real case that prompts me to ask this question, each parameter estimation takes 0.6s by the lsqnonlin function of MATLAB. In contrast, although training a neuron network is time-consuming, getting the output from the input only takes several milliseconds for a pre-trained network.
The formula $y=f(x,p)$ may be used in practice for many years and proves to be very effective. The parameter $p$ also has clear physical meanings and can indicate the actual conditions of the system/machine/experiment. Both $x$ and $y$ can be easily obtained. So I want to reserve the formula rather than use a blackbox-like network to predict $y$ from $x$ as most DLs do.

The difficulties I met when solving the problem myself:

Suppose the size of the $(x_i,y_i)$ set is $n_i$: $(x_i^{(1)},y_i^{(1)}), (x_i^{(2)},y_i^{(2)}), ..., (x_i^{(n_i)},y_i^{(n_i)})$. The problem is: $n_i$ is not fixed. If $n_i=5$, we may estimate $p_i$ with a great error. And if $n_i=1e6$, we may get a very precise estimation of $p_i$. But in both case we can get an estimation of $p_i$ at last. However, multi-layer perceptron (MLP) or convolution neuron network (CNN) both accept fixed number of inputs. If you do image processing, you even need to resize every image to the same size first. It seems that MLP and CNN don't suit for this question.
The $(x,y)$ set has no order as time-series. The 1 and 2 in $(x_i^{(1)},y_i^{(1)})$ and $(x_i^{(2)},y_i^{(2}))$ are just indices, which don't imply that $(x_i^{(1)},y_i^{(1)})$ is necessarily before $(x_i^{(2)},y_i^{(2}))$. So recurrent neuron network (RNN) doesn't seem to be a natural option.

No.  Deep learning is not useful or relevant here.  Deep learning is for classification.  You don't have a classification task.  Rather, you have an optimization task: find the parameter value $p$ that causes the best match between the given $x$-values and $y$-values.

Deep learning isn't magic sauce that you can apply to anything you might ever think of and expect it to solve your problem.  Your question is an instance of the XY problem.  There may be suitable methods to speed up optimization, but you'll probably need to ask a new question and tell us something about the structure/properties of $f$ and the typical range of values for $n_i$.


Mutex-/semaphore-/locking-algorithm using atomic reads/writes with data-propagation delays Is there a mutual exclusion or semaphore or locking algorithm that only relies on atomic reads and atomic writes of shared memory and can tolerate a delay in propagation of the written data between processes? I.e. if process A writes to shared memory, process B might not see the change for a while (but process A will see the change immediately).

It seems to me that this might be theoretically impossible if I don't have an upper bound on the delay, but if I do have such an upper bound, is there an algorithm that's a little more clever than just sticking busy-waits for the worst-case delay between the reads and writes of any other non-delay-tolerant algorithm?

(I'm trying to solve this problem: Cross-window synchronization (critical sections) in the browser)

If you don't have access to atomic primitives like CAS, you're going to have to depend on voluntary synchronization between the two halves.  This means side A cannot proceed until side B has acknowledged that side A took the mutex.

Since we know nothing about the shared memory, we cannot assume that write to two seperate regions will be seen in order (some caches will change the order that writes present).  We will have to assume that there is some atomic thing, like an int32.  We're also going to have to assume that when you say atomic read and write, you never see tearing on the integer, and it's monotonic (if I numbered A's writes, and I've observed #13, I will never again see the  #12 value that had been written).

If you do this, then just take one bit (say, the MSB) and use that as an ownership token over the communication used to handle locks.  If it's a 1, it means A gets to write.  If it's a 0, B gets to write.  Whenever A sets it to a new value, the MSB is always 0, and when B sets it to a new value, the MSB is always 1.  Now, with nothing but normal reads and writes, we can tell who has the "rights" to the communication channel.

Now the communication channel consists of the lower 31 bits.  You can send anything you please across this, including requests to acquire or release a "mutex."  If you want to acquire it, you simply have to wait for it to be your turn to read, send a "request mutex" message, and wait for the reply to say "mutex OK"

EDIT: From our chat discussion, it appears what is really needed is a lottery process to select a master thread, who then takes over the job of being the "kernel" that manages the mutual exclusions.  All it needs is a way to detect when the master thread died, and elect a new master.  This lets us split the problem up into a slow part, which is very robust, and a fast part that works as long as a master is present.


Is Dijkstra's algorithm just BFS with a priority queue? According to this page, Dijkstra's algorithm is just BFS with a priority queue. Is it really that simple? I think not.

You can implement Dijkstra's algorithm as BFS with a priority queue (though it's not the only implementation).

Dijkstra's algorithm relies on the property that the shortest path from $s$ to $t$ is also the shortest path to any of the vertices along the path. This is exactly what BFS does.

Or in another perspective: how would Dijkstra's algorithm behave if all the weights were 1? Exactly like BFS.


Can the edges of a graph be assigned directions such that all nodes in a given subset have in- or outdegree 0, and every other node indegree > 0? In a directed graph, the indegree of a node is the number of incoming edges and
the outdegree is the number of outgoing edges. Show that the following problem
is NP-complete. Given an undirected graph G and a designated subset C of G’s
nodes, is it possible to convert G to a directed graph by assigning directions to each
of its edges so that every node in C has indegree 0 or outdegree 0, and every other
node in G has indegree at least 1?

I need an idea how to prove it

take $C=\emptyset$ then you want to direct the graph so all node have in degree at least 1($DA1$) and now think about directed Hamiltonian cycle($DHC$) how you can reduce $DHC$ to $DA1$ !


Courses that give good insight on the nature of a Computer Science major? I'm a business informatics student so I am taking introduction to computer science and computer programming, and so far I hate everything that has to do with this major aside from these 2 courses which I am really enjoying so far, so I am considering changing to a computer science and engineering major, but I want to make sure this is what I will enjoy before I make this change so I am researching some stuff relating to computer science online, one of which being discrete mathematics. Do you think discrete maths gives good insight on how CS is like? How about 'Theory of computation' and 'Intro to Artificial Intelligence'? Do you have any other recommendations for courses or subjects that DO give good insight on CS and do not have any course prerequisites so I can look into them and be able to follow? Thanks in advance to those who take the time to answer and help :)

Here are some thoughts about your suggestions for further study, plus one that you didn't mention.

Discrete Mathematics

This course should be part of the background for every computer scientist. The material is relevant for lots of areas we deal with and can be interesting and engaging whether or not one is going to concentrate on CS. That said, though, the subject matter won't necessarily give you an insight into what CS is really about unless it is specifically tailored to computer science applications (which it rarely is, in my experience).

Theory of Computation

A great choice, though it takes a bit of "mathematical maturity" to get through (meaning that you might find Discrete listed as a prerequisite). In one sense, this is the foundation for much of the rest of CS, since it asks "What things can and cannot be computed?" and often proceeds to answer this question by looking at increasingly more powerful models of computation, asking what kinds of problems these models can and cannot solve. Full disclosure: I'm a theorist and so find this area to be particularly beautiful.

AI

Well taught, this can turn out to be an eye-opening introduction to a lot of CS topics as well as being, in many people's opinion, just downright fascinating. Poorly taught, though, this can be little more than a specialized data structures course (still interesting, just not as much fun).

Data Structures

You didn't specify what your programming course covered, but this is a natural follow-on. Learning to program, you were exposed to what one might call the standard collections of algorithmic basics, like selection (if statements), loops, arrays, function calls, and (if you were lucky), recursion. A course in Data Structures goes on from there and usually is organized around the "canonical" structures used for organizing data, structures like lists, trees, stacks, hash tables, and the like. This is absolutely indispensable for any practicing computer scientist. At many schools, in fact, it's the next course to be taken after the first programming course.

So, what should you do next? All of your possibilities have their merits, but I'd advise a Data Structures course, for a couple of reasons. First, if you take it and hate it (assuming that your reaction isn't just due to a lousy teacher or a poorly-designed course), then CS is probably not the way you want to continue and it'll be good to find that out early. If, on the other hand, you take it and walk out with the reaction "that was fun", then you'll not only have shown you probably have an aptitude for all the rest that will follow, but at most schools, you'll have placed yourself at the right point in the CS curriculum to continue.

Best of luck.


Why is there more frequent overflow in normalised Floating Point I read that overflow is more frequent when we work with normalised mantissas. Why is this?  Is it because when we adopt a normalised representation, our range is smaller than in a unnormalised representation?

Source: I read this in: Hwang, K. Computer arithmetic. John Wiley & sons, 1979. Chapter 10 "Advanced topics on floating-point arithmetic (page 323)"
It says this:

  The operands are not required to be normalized, overflow may be expected to occur less frequently in unnormalized arithmetic.

In a nutshell: Normalized binary floating point requires the
  mantissa to start with digit $1$. When there is an underflow on the
  exponent, the computation may be saved, at the expense of precision,
  by allowing the mantissa to start with some leading $0$ in what is
  called subnormal or denormalized numbers.

It is always a bit chancy to guess the intended meaning of a statement
without enough context.

I am not sure either of what you means by

  when we adopt a normalised representation, our range is smaller than
    in a unnormalised representation.

With these disclaimers, here is my understanding.

A first point to note is that the meaning of qualifier normalized
depends on context. In scientific notation, wich is close to floating
point, it means that the mantissa is represented with a single
non-zero digit before the decimal point, for example $2.718\times
10^{24}$.

The definition is different in the IEEE standards for floating points.
They specify the number of digits used for the mantissa, with no
leading $0$, and with no decimal point (implying it is immediately
right of the last digit which can be $0$).

One characteristic of normalized binary representation is that the
mantissa (called "significand"or "coefficient" in the IEEE standard).
always start with a digit $1$.  This gives optimal precision with the
mantissa (though the ending $0$'s may not be significant), and can
save one bit, since a leading $1$ that is always present does not need
to be represented.

However the is a provision for representing subnormal numbers
(also called denormal or denormalized) which, as the names
indicates, are not normalized.

When there is a need to represent a number such that it requires an
exponent smaller than the possible minimum, the normalized computation
will cause an underflow exception, which is one of several possible
exceptions.

However, this can be recovered, as smaller values (subnormal numbers)
can be represented in denormalized format. This requires various
tricks as the leading digits of the mantissa can now be $0$ rather
than an implicit $1$. Skipping the details, what this amounts to
is that underflow can be overcome, to some extent, by using subnormal
numbers that have less precision than the normal ones.

Thus if the computation has provision for using subnormal numbers, it
is less likely to be aborted by an underflow. But then one should
watch for the precision which may not be as good as normally expected.


Find All possible Pairs in given Array It is required to count number of unordered pairs in an array of size n ,

l[i]+l[j] = 2*l[k] , where 1<=i< j<=n and 1<=k<= n

My Approach:

l = [1,3,5,4,2,5]
l.sort()
l2 = []
for i in l:
    l2.append(2*i)
count = 0
for combo in combinations(l, 2):
    if sum(combo) in l2:
        count+=1

print(count) # count comes out to be 7

Please help in reducing Time Complexity O(n^2) to less if possible. Space Complexity is not a problem.

Your problem (more accurately, the problem of deciding whether there is any solution) is 3SUM-complete. This can be shown in essentially the same way that the two main variants 3SUM and 3SUM' are shown to be equivalent (check the original paper of Gajentaan and Overmars, for example). Therefore it has an $O(n^2)$ algorithm, but it is conjectured that there is no $O(n^{2-\delta})$ algorithm for any $\delta > 0$.


How much can matrix multiplication algorithm be parallelized? You all may know that simple Matrix Multiplication algorithm:

for(i = 0; i < n; i++)
   for(j = 0; j < n; j++)
      for(k = 0; k < n; k++)
         C[i,j] += A[i,k] * B[k,j]
      end for
   end for
end for

When we want to parallelize it, we can, at first, parallelize the outer loop,
which is the most easiest thing to understand, since it is clear that it does not have data dependencies with other loops.

Most tutorial on the web stops here, like we can not parallelize anymore.

But it seems for me that even the second outer loop (the one in the middle):

for(j = 0; j < n; j++)

can be parallelized.

What about the inner loop?

Is thus possible to parallelize all three loops of a matrix multiplication algorithm or must we stop with parallelizing only the first two loops?

Ypu're starting from a completely wrong point.

The execution time of matrix multiplication does not come from the number of multiplications and additions, it's the number of uncached memory accesses that kill you. Reading a number that's not in any processor cache takes about 100 times longer than a multiplication.

So the first step is rearranging the order of operations to perform as many operations as possible using only data that is present in the fastest processor cache. That's your first step before you even think about doing things in parallel.

The next step is adding multiple sums in parallel, still in one thread. Instead of summing up C[i,j] for example you add six sums C[i, j], C[i,j+1], C[i, j+2], C[i+1, j], C[i+1,j+1], C[i+1, j+2] in parallel. This means you are limited by the throughput of operations, not the latency.

The next step is using SIMD instructions. Your processor quite likely has instructions that perform 2, 4 or 8 floating-point operations just as fast as a single floating-point operation.

Once you have done all this, especially the first part where the work is divided up into "blocks", you can easily process multiple blocks on multiple threads. What you need to be careful about is that you have enough cache memory to do so.


Can someone explain the language L = {w: w = uu, u \in La(1*01*)} I need help understanding the language L above.

These are my understanding:
- w = uu is a concatenation of u
- La(1*01*) can be expressed in regular language i.e. r1 = 1*01* so La(r1)
- also we have regular expression property of concatenation: L(r1r2) = L(r1)L(r2)

So base on my understanding the language L can be simplified to

I'm not quite sure about this.

No, your simplification is wrong.

Consider, as a simpler case, $A=\{a,b\}$ and $L'=\{ w \mid w=uu , u\in A\}$. Then, $L'=\{aa,bb\}$.

Instead, if we apply your simplification and write $L''=AA$ then we have $L''=\{aa,ab,ba,bb\}$ which is a larger language, since we forgot that both $u$'s in $w=uu$ must be the same word.

Keeping that into account, your original language $L$ seems to be $\{1^n01^m1^n01^m \mid n,m\geq 0 \}$


Finding a Good Estimate for Amount of Time Computers Spend Sorting Lists of What Lengths? I have an assignment to envision and calculate the possible effects the implementation of a general sorting algorithm that is O(n) time and O(1) space ( assuming general case ) would have on computation and society.
In order to do that, I am trying to estimate how much computation time computers in server farms spend on sorting, and what general orders of magnitude the lengths of lists being sorted fall in.  Server farms seem to be the most impactful area to analyze for pertinent effects, but if there are some other areas that people would expect to see an outsize effect, I would appreciate them being called out.
I can then present sets of assumptions with the "new" algorithm being faster at sorting lists at such a length and larger and how much faster than the current state of the art.  eg. "If the new algorithm is even with the state of the art for lists of 500 billion items, and increases in time with "n" while the soa increases in time with "log n", and 1/2 trillion item and larger sorts take X% of server-farm computation, you could expect to see computation time for the same tasks reduced by order of magnitude Y%".  Once I can get some firm numbers ( not the question here ) on how much electricity server farms use, then I can also electricity usage cost comparisons.
When I researched on the web, I found that an O(n)/O(1) sorting algorithm is considered theoretically possible, but undiscovered to this point.  I suspect that there might not be much impact on computation, because there seems to be no incentives put out for someone to come up with such an algorithm ( or a proof that it cannot exist ).
What is a the fastest sorting algorithm for an array of integers?
https://en.wikipedia.org/wiki/Sorting_algorithm
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap09.htm#:~:text=We%20have%20now%20introduced%20several,quicksort%20achieves%20it%20on%20average
I have presumed that sorting algorithms in general use, at least for large lists like web search results, are O(n log n) time and O(1) space as a general matter of course.  If this is in error, please point it out!
My apologies if this forum is not appropriate for this kind of question.  In that case, I would ask for pointers on where I should go with this question.
Thank you.

There is no comparison based sorting algorithm faster than O(n log n). So this is all theory.
There are plenty of situations where sorting an array takes O(n) time. These are special cases, but happen a lot. For example a sorted array. Or a sorted array with few elements changed. And there are cases where sorting the whole array isn’t needed. Like if I see my address book on the screen, apparently sorted - but only the bits that I’m looking up are sorted.
Log n isn’t very large, so O(n) doesn’t mean it’s faster than say Quicksort for anything that is small enough to sort.
Server farms rarely sort. Databases are indexed, and indexes are updated, no sorting needed.
The effect on society would be zero. Some people would be able to handle their computational needs for slightly less money, that’s all the difference.


what would be the drawbacks of lecturing two programming languages simultaneously? One colleage came with the idea/comment that it would be useful to lecture two programming languages, eg. Java and Scheme, at the same time while lecturing an Introduction to Programming course aimed for first term undergraduates.

I have my doubts that approach could stuck some students in learning the syntax of the programming language instead of the logic on how-to-program. Also I believe that some of them will get in their minds that Computer Science careers are equal to being a hardcore software developer.

While I have found some academic references about the last point I mentioned (that CS!=programming), I have not found any academic sustainable research that could prove wrong to teach two programming languages for an initial course, apart of discussions of lecturers against that idea in public forums. In ACM there is a paper in which they tried to lecture Python and Java at the same time, but the authors make so many assumptions and also mention a lot of pitfalls on their research, that I hardly believe it is a good article to be based on.

Has anybody found or read any article that mentions the advantages/disadvantages of that approach?

Avoid technical minutiae at all costs.  Devote your focus to the big concepts you want to teach.  I understand the desire to make the point that there is an underlying similarity between all programming languages, but I (personally) don't think the first course is the place to make that point.  Rather, I would focus on problem solving using real-life applications.

I don't have any references to studies that would confirm or refute your specific hypothesis.

Here is an article by Lenore Blum (CMU) on what CMU has done to increase women's enrollment in computer science.  CMU's experience with their introductory classes is discussed on page 8.

http://www.cs.cmu.edu/~lblum/PAPERS/women_in_computer_science.pdf

And here are several newspaper articles about the changes they have been making at Tufts and Harvey Mudd (both of which have had significant increases in the number of women graduating from their CS programs.)

http://www.boston.com/news/education/higher/articles/2005/12/18/in_computer_science_a_growing_gender_gap/

http://www.nytimes.com/2012/04/03/science/giving-women-the-access-code.html

Here are several analogies that come to mind.  See if you think any of them make any sense.

"We are going to teach Physics 101 by alternating lectures between MKS and cgs (or British Imperial Units).  This will open the students minds to thinking more abstractly."

"We are going to be teaching our high-school students driving safety by having them drive a variety of different vehicles, including a sports car with a manual transmission, a large moving van with an automatic transmission, and an off-road four-wheel drive pickup truck.  This is the only way we can get them to generalize the basic safety concepts from one vehicle to another."

"We've got a group of exchange students arriving from southeast asia that speak very little english.  So we're going to teach their intro calculus class half in German and half in Russian, since so much of the research literature from the early 20th century is in those two languages."

"I'm going to post a few of your assignments on the web.  But I'll also send a few to your university email address.  And you should friend me on Facebook and follow me on Twitter and Instagram, because I'll post at least one of your assignments on each of those platforms.  You need to learn these technologies sooner or later, so better sooner than later!"

"By the time a student graduates they need to be proficient at touch-typing on a keyboard.  But we're not a vocational school, we're a university, so we're going to teach the foundations of touch-typing.  Thus we alternate classes between the traditional QWERTY keyboard and the Dvorak layout, because we want the students to focus on the principles, not the details of one keyboard or another."


Undergraduate Computer Science Textbooks What books would you recommend for someone starting B.Sc in Computer Science?

My Personal Info:
I am currently looking at B.Sc in Computer Science (Games), which is computer science, accept for the last year which is tailored more towards game dev.

I have a fair bit of programming experience with Unity and other things. But as far as CS goes, have little to no experience. I have just finished reading 'Introduction to Computation and Programming Using Python'. But am after something more in-depth and maths based.

My maths experience is quite poor which concerns me, as I have only studied maths up to GCSE level. (GCSE = English, there is no American equivalent. Taken at age 16)

Understanding CS is a broad topic, I was just looking for some reading that could introduce me to some key ideas that could be covered in an undergraduate course at uni.

Thanks for your time,
Magnus :)

Since you like to work through books, meaning you will spend a lot of time with one book and dig into the details using the book, I would recommend that your next book be

Introduction to algorithms by Cormen

I don't have this book as it didn't exist when I went to school but learning algorithms and data structures is where you will start at the University level once you have one programming language learned.

This is the kind of book that once you put it on your bookshelf and you will keep grabbing again and again for the rest of your life if you continue to program.

I know you asked about math, but if you can do problem solving, and converting word problems to math, then learning the math you need for programming is not something to worry about. In math you take word problems and convert them into the language of math, with programming you take word problems and convert them into algorithms and data structures. The thinking is the basically the same, one produces an abstract result and the other a program that can be run on a computer.


Decomposition of a relation to 3NF Given a relation $R(A, B, C, D, E, F)$, with the following functional dependencies:
$\{A \rightarrow BC, CD \rightarrow E, B \rightarrow D, E \rightarrow A\}$.

The objective is to decompose $R$ into 3NF relations.

So far, I have determined that the following candidate keys are present in the given relation:
$AF$, $EF$, $CDF$ and $BCF$.

Since every attribute is present as a part of some candidate key, for every $X \rightarrow A$, $A$ will be part of some candidate key, and so R itself should be in 3NF.

Since the question explicitly, however, states that it is not in 3NF, I have got a little confused. Where am I going wrong? Is there something that I have not understood?

The original definition of 3NF was "flawed".  Relvars such as yours could perfectly be in 3NF and still have undesirable redundancy.

And the flaw was exactly in cases when there was more than one candidate key.

Which was the very reason why BCNF was introduced, as a "fix" to the "flaw" that was discovered in [the definition of] 3NF.

The thing is, in cases of >1 candidate key, we wouldn't even want designs such as yours to even satisfy 2NF.  Both 2NF and 3NF can be violated only by nonprime attributes.  That is the flaw in their definition.  When the "fix" was applied to 3NF, superseding it with BCNF, the fix itself was flawed because actually what should have happened was to supersede the definition of 2NF with one that didn't limit itself to "nonprime" attributes".


What is the intuition behind the Potential Function in Amortized Analysis of some algorithm? I have come across many amortized analysis using a potential function. They all look magical to me. Everything works perfectly but I never got the intuition behind how they come up with such a "magical" potential function which makes everything work. My question is can someone share their experience in developing a potential function for amortized analysis and the intuition behind it?

Imagine filling up a huge water tank. Now when you open the faucet you have nice water pressure. The pressure will last probably until the tank is almost empty (depending on its size). At that point you need to refill it to have your constant pressure again, so you make the effort again.

The potential function is the water tank. You do some work that will "last" for a while and "store" the energy used in the potential function, e.g., allocating an new array in dynamic arrays/tables. You won't need to do any more work for a while, e.g., until the size of your array grows too much or shrinks too much. At that point you have used all the energy in your potential function (all the water is gone) and need to recharge (refill the tank).

As far as designing such a function, let's take as example the case of a dynamic array. The main point to bring home here is that the potential function Φ is linear in the input size. The coefficients and constant values matter to a certain point (in physics, what really matters is the derivative of the potential function, or the difference between values of the potential function in different points, so additive constants don't really matter in general). We know the function is linear in this case because the expensive operation that we want to amortize is a linear operation (resizing of the array) and we want to prove that this operation determines the cost of a sequence of operations. So, from a practical standpoint, we could have written Φ = a*n + c, performed our analysis and then assigned reasonable values to our two constants so that the potential is always positive. Note that these coefficients might heavily depend on the details of the algorithm/data structure being analysed. For example it's be interesting to try and change when the array gets resized and the amount by which it gets resized and see if the function still hold and also if the linearity still holds. This is discussed in CLRS.

It's also worth noting that, although possible, it might be impractical or tedious to apply amortized analysis to any algorithm. In many cases simpler approaches, e.g., the use of the master theorem, will suffice. The potential method works well for cases like the dynamic array, where you have an expensive operation that you are trying to "amortize" over a sequence of operations, thus not all the operations have the same cost, but the overall cost of performing a given sequence of operations is well defined (linear in this example).


Rice's theorem applicable to the following language? Let $L= \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle \} $
be a language where $\langle M \rangle$ is the Code of the TM $M$. $L$ is undecidable.

I've heard that I can't use Rice's theorem to proof its undecidability.

But why? I can construct a set $S = \{f_M \mid f_M(\langle M \rangle)\in \{0,1\}\}$.

It's clear that $S$ is not empty and $S$ contains not every TM.

Because there may be multiple $M$'s corresponding to the same $f_M$. That is to say, you cannot deduce $\langle M\rangle$ from $f_M$, so you cannot describe $S$ in this way.


What is the difference of temporal dynamics in RNNs and the NEF Both spiking neural networks created with the Neural Engineering Framework (NEF) and Recurrent Neural Networks (RNNs) can be connected recurrently to exhibit neural dynamics. What is the difference between the set of dynamics that they can approximate and/or exhibit?

There can be a lot of different ways in which recurrent neural networks can be used. RNNs can have any activation function (logistic sigmoid is most commonly used), and they can be multilayer. There are different algorithms which can be used to train them e.g., backpropagaion and different optimization techniques e.g., hessian free optimization which can be used to optimize the networks for a particular problem.

NEF has been used for simple recurrent connections (for implementing memory circuit), however, we need to do some work and try out multi-layer networks in order to truly figure out what the differences in dynamics would be.

We have also tried hopfield networks with pre-calculated weight matrices, and using sigmoid neurons and were able to achieve similar dynamics forming attractors. However, implementing hopfiled with dynamic learning of weight matrices is something which needs to be tried out.

I suspect that using sigmoid activation functions in NEF and applying the same learning algorithms should give results very similar  to RNNs (there might be some differences caused by synaptic filtering). However, if one uses an LIF curve as an activation function, then there is a possibility of greater differences.


L contains the concatenations of all k-bit long strings. Why is it decided in PSPACE(loglogn)? (This exercise is from Computation Complexity: A Conceptual Perspective by Oded Goldreich):

For any k $\in \mathbb{N}$, let $w_k$ denote the concatenation of all k-bit long strings (in lexicographic order) separated by *'s (i.e, $w_k = 0^{k-2}00*0^{k-2}01*0^{k-2}10*...*1^k$). Show that the set $S = \{w_k:k\in\mathbb{N}\} \subset \{0,1,*\}$ is decidable in double-logarithmic space.

The basic idea of the solution, if my understanding of it is correct, is:

iterate from i to k until the structure of the input suits some $w_k$, for example $\{0,1\}^k*\{0,1\}^k*...*\{0,1\}^k$.
For each pair of adjacent binary numbers, make sure $b_{i+1} = b_i + 1$

According to the guideline in the book, step 2 takes space $O(log(k))$.

Why do I need $log(k)$ space to check if $b_{i+1} = b_i + 1$? Can't it be done in constant space?

Try to implement it in constant space to see what goes wrong. You need to be able to count up to $k$, which takes $O(\log k)$ space.

More formally, consider the language
$$L = \{a\ast b : a,b \in \{0,1\}^k, b=a+1\}.$$
This is not a regular language, and so cannot be decided in constant space.


Show that a problem is NP-Complete The problem is, K_longestPath:

  We are given a graph in which some of the vertices are "cities". No two cities have an edge between them, thus every city must be at distance at least 2 from each other city. We have to find a path that goes through each such city without forming a cycle.

We are given the Graph with a valid configuration of cities and we have to find if there exists such a path.

At first I was thinking solving this with Hamiltonian path, but to show that the problem is NP-complete I have to find an algorithm that will change it's inputs to be inputs for this problem that we got, and I don't know how to do this..

You need to choose an NP-hard problem, and show a deterministic polynomial-time algorithm that transforms any instance of this NP-hard problem to an instance of your city problem that is true if and only if the original instance was true. As you suggested in the question, Hamiltonian path is a good choice for the starting problem.

Try to create an algorithm that takes any Hamiltonian path instance and constructs a "city problem" instance which has the same truth value. You must also write a proof that, for any input instance of Hamiltonian path, the corresponding output instance of the "city problem" has the same truth value.

Hint 1:

   Think about subdividing edges.

Hint 2:

   If you take an arbitrary (undirected simple) graph and subdivide each edge once, you get a graph in which none of the original vertices are adjacent to each other.


Number of nodes of height $h$ in a heap or almost complete binary tree I came up with the following statement:

  If there are $X$ nodes of height $h$ in an almost complete binary tree, there can be at most 1 node of height $h$ that is not full.

That is to say, $X-1$ must full and the last node of height $h$ may or may not be full.

Intuitively it seems right, but I can't seem to prove it. Could someone help me prove it. If the statement is false, please let me know why.

Except for the next to last level all nodes are full, nothing to show. On the last level there are only leaves.

Only on the next to last level there can be non-full nodes, i.e. nodes with only one child. And there can be leaves. So your reformulation should be "X-1 nodes must be full or leaves."

Now it depends on the definition if the statement is true. If the last level must be filled from left to right, for example (this is the case if you implement the tree as an array), the next to last level looks like:

full full ... full (one possibly non-full) leaf leaf ...leaf

If another element is added, it must be a child of the non-full node and thus will make it full. If one element is removed, the non-full node will become a leaf.

As I said, the exact details depend on the exact definition of almost full binary tree. If the last level can be filled in an arbitrary manner, then the statement does not hold.


What is the advantage of Rete algorithm compared to relational database engines? Per my understanding, the Rete algorithm and relational database engines essentially solve the same problem: answering to a certain query about a (large) set of relational facts. To me, the Rete algorithm is just more special-purpose along with a fancy caching procedure; I fail to see why it is superior to any of the existing state-of-the-art database solutions such as SQL. In terms of flexibility, SQL is certainly superior. In terms of performance, it is not apparent that Rete yields better average performance.

As you say, relational databases are designed for, essentially, answering queries. Rete, I would rather say, is designed for the specific task of materialized view maintenance (i.e., keeping updated the results of a query, once new changes to the data are applied). Of course, you can answer queries by building a materialized view of them, and this is why SQL query answering and Rete relates to each other.
With regards to efficiency, Rete has been critiziced for wasting too much time mantaining its internal data-structures. This motivated the apparison of other algorithms such as Treat.
In any case, it is worth to hightlight that Rete only deals with relational algebra queries, whereas SQL includes non relational-algebra expressions (e.g.: aggregation functions).


Alan Perlis Epigram on Recursion So, while trying to dive into "recursion" and the like, I came across an epigram about recursion by Alan Perlis:

  Recursion is the root of computation since it trades description for time.

  -- Alan Perlis

Common to epigrams, this sounds like a deep insight. But I've already got stuck on "root of computation" and in which sense recursion "trades description for time".

Any explanation would be nice. : )

I can't presume to speak for Perlis, but my intuition is as follows:

Recursion is descriptive

Especially at the time this was written, the specification of a recursive function seems much more descriptive than prescriptive, in the sense that a recursion describes a mathematical property we want the result to satisfy, rather than a series of computation steps. E.g. for mergesort

 sort(l) = let l1, l2 = split(l) in merge(sort(l1), sort(l2))

Recursion involves a notion of time

But obviously recursion also describes a process or series of steps. In the case of mergesort:

Split l into l1 and l2
then compute sort(l1) and sort(l2) (in either order)
then compute the merge of those two results
the result of this is the value we wished to compute

This suggests that the time taken by this computation is the time of each of these individual steps, which itself involves a recursive equation (over integers) to compute, namely the time taken to sort the sublists l1 and l2.

Trading description for time is the essence of computation

One way of characterizing computation is that we want to go from an abstract mathematical "timeless" description of an object to a concrete representation which can be manipulated symbolically.

Computation can be defined as the process which goes from the abstract to the concrete, and the time which this process takes is one of the central considerations of CS as a field.

My last advice is that sometimes it is important not to overthink epigrams or koans, but let understanding come naturally with experience.


Does NTIME($n^\alpha$) $\subset$ EXPTIME imply NP $\subset$ EXPTIME? I think I'm able to prove NTIME($n^\alpha$) $\subset$ EXPTIME for arbitrary $\alpha$.

Is this a new result?
If it was, would there be a way to deduce NP $\subset$ EXPTIME from it?

Upon reflection this is an easy consequence of the Time Hierarchy Theorem.

NTIME$(n^\alpha) \subseteq$ TIME$\left(2^{n^\alpha}\right)$ by brute force
TIME$\left(2^{n^\alpha}\right) \subset$ TIME$\left(2^{n^{2\alpha}}\right)$ by the Time Hierarchy Theorem
TIME$\left(2^{n^{2\alpha}}\right) \subseteq$ EXPTIME obviously

So there's nothing new here.


What is an array of arrays called when all arrays have the same size? If I have an array a of arrays, in many languages they may have different size. Is there a word for an array of arrays where all the arrays have the same length?

Edit:
An array of arrays may have the following form:

[
  [ 1, 2, 3 ]
  [ 1, 2, 3, 4 ]
  [ 1, 2 ]
]

But in order to convert this to a matrix you would have to assume some default value or trim the arrays. The following array of arrays is possible to convert into a matrix without any asumptions or trimming as all arrays have same length.

[
  [ 1, 2, 3, 4 ]
  [ 1, 2, 3, 4 ]
  [ 1, 2, 3, 4 ]
]

Is there some name or classifier for a matrix of this kind?

In C# world there are 2 kinds of array declarations, and 2 names for it:

Jagged:

[
  [ 1, 2, 3 ]
  [ 1, 2, 3, 4 ]
  [ 1, 2 ]
]

Rectangular:

[
  [ 1, 2, 3, 4 ]
  [ 1, 2, 3, 4 ]
  [ 1, 2, 4, 4 ]
]


Unambiguous CFG for $a^ib^j$ where $i \le j \le 2i$ could you please help me for finding an unambiguous CFG for the following expression:
$a^ib^j$ where $i \le j \le 2i$

$S \rightarrow$ $aSb$  |   $J$

$J \rightarrow aJbb$ | $ε$

This has only one derivation tree for a word in that language.


When does a PDA split? In case of NFA, if the NFA is in a state and reads $\epsilon$ ( empty string ) the NFA splits in to two, with one being at the current state and other with the state along the $\epsilon$ transition. In case of PDA where transitions are of the type $a,b \to c$, with $a$ being the input alphabet being read, $b$ being the stack element being read and popped and $c$ being the stack element being pushed. In NFA I understood the splitting upon $\epsilon$ as the ability to guess. So I assumed that a PDA in a state $r$ with stack being $S$ splits into  two PDA only when the transition is $\epsilon,\epsilon \to \epsilon \\$ ( that is when $a=b=c=\epsilon$ in the figure below the PDA splits into two with one being in state $r$ and other in $s$ with same stack $S$ ). But now I am a bit doubtful, about when does a PDA split. I feel I am wrong and am misunderstanding something trivial. ( The figure below just shows the part of a larger PDA ). How would it affect the power of a PDA if it were only allowed to split on $\epsilon,\epsilon \to \epsilon$ transition?

A PDA (or an NFA) doesn't split. At any given point in time, it non-deterministically chooses a valid next step, if any. If there are several options, you can say that the PDA "splits" if you wish, trying all of them in parallel.

A PDA (or an NFA) could have more than one possible move even if it has no $\epsilon$ moves, and conversely, there might be situations in which an $\epsilon$ move is the only possible move of the automaton (can you think of such a situation?). So your identifying $\epsilon$ transitions with "splitting" is wrong.


Let u and v be two strings. What about the reverse order of their concatenaited string? let $u$ and $v$ be two strings. Is $(u.v)^R$ equals to $u^R.v^R$?

Note: The $R$ notation means reverse order and the $.(dot)$ notation means concatenation.

No, $(u\cdot v)^R\not=u^R\cdot v^R$ more often than not.

For example, if $u$ is the string $race$ and $v$ is the string $car$. Then  $$(u\cdot v)^R=(racecar)^R=racecar$$
while
$$u^R\cdot v^R=(race)^R(car)^R=ecarrac.$$

Here are a few related exercises. All variables stand for strings.

Exercise 1. If $u$ or $v$ is the empty word, then $(u\cdot v)^R=u^R\cdot v^R$.

Exercise 2. If $u$ or $v$ are words of length 1 such that $(u\cdot v)^R=u^R\cdot v^R$. Then $u=v$.

Exercise 3. If $u=u^R$ and $v=v^R$, can we guarantee $(u\cdot v)^R=u^R\cdot v^R$?

Exercise 4. Prove that $(u\cdot v)^R=v^R\cdot u^R$.


Determining cycle time and and hold time in logic circuits First I have general question. In a circuit with both logic and D edge flip flop does hold time have to satisfy $t_{hold} < t_{setup}($D-FF$) + t_{pd-min}$(Logic),

or is it enough that $t_{hold} \le t_{setup}($D-FF$) + t_{pd-min}$(Logic) ?

Also i have a question about a specific circuit:

with the following times:

the question is how much time at least, before and after the fall of the clock does the Input have to be steady? when it is given that $t_{hold}=8ns$

Now, from what I know, the input has to be kept steady for at least $t < t_{pd-min}$(Logic) +$t_{setup}$ time. So I don't understand how $t_{hold}$ comes into consideration here. I'll be glad if could explain.

Well if someone is interested I have solved the question myself.

First of all, it indeed is possible that $t_{hold} = t_{setup} + t_{pd-min}$.

And about the input time, it has to satisfy: $$t_{hold} \le t_{pd-min}(logic) + t_{input-valid-min}$$

since $t_{hold} = 8ns$ and $t_{pd-min}(Logic) = 10ns$ , even $t_{input-valid-min} = 0$ satisfies this.


Meaning of ε in NFA-ε? In wikipedia NFA-ε transition function defined as follows $Δ : Q × (Σ ∪ \{ε\}) → P(Q)$, where $Σ$ is an alphabet and $ε$ - empty string. I don't understand the meaning of $ε$ in this context.

Assuming $ε$ means a sequence of symbols with length of zero, as per definition.

Alphabet $Σ$ is a set of symbols. But symbol $\neq$ sequence of symbols (string). Thus, $(Σ ∪ \{ε\})$ is no longer set of symbols, but a mixed set.
I don't know much of set theory, but is this mixed set allowed in this context?

Also. When does NFA ε-transition happen?

ε-transition happens when input symbol is an empty string? Meaning, that presence of empty string is necessary condition for ε-transition .
ε-transition happens when there are no input symbol at all? Meaning, that
presence of empty string is not necessary condition for ε-transition.

I think that the latter case, or I am wrong?

I would have avoided this confusion, if $ε$ would mean "NO_INPUT" symbol, rather an empty string as per definition.

An epsilon transition is simply a transition that doesn't consume any characters in the input string.

Taking it is optional, and it is what makes the non-deterministic finite automata non-deterministic: by allowing it to 'branch' it can 'explore' two plausible paths through the language it accepts. It is essentially just a space saving measure: DFAs (which do not permit epsilon transitions) are computationally equivalent to NFAs. There are steps to convert an NFA to an equivalent DFA, removing epsilon transitions is part of this conversion.

To explicitly draw out answers to your questions: In your example it is akin to a 'NO_INPUT' symbol, but more like 'NO_COST'. Think of it like this: Each edge has a 'cost' in the symbol along it that you must pay to transition along that edge. An epsilon has no cost. You don't 'spend' any characters from your input string to traverse that edge. Because of that, you now have multiple paths: Take the epsilon transition (or transitions) and spend no symbols from the input string, or 'spend' an input string along an edge. So it essentially the computation 'branches', and your NFA accepts a string if any path through it concludes in a success state.


Greedy heuristic for buying fewest fridges of set temperature for products that can be kept in some temp. ranges? We have a set of $n$ products, each $i$th product can be kept in a
  temperature between $c_i$ and $h_i$.

  We have to buy fewest number of fridges for these products. The
  fridges can only have a fixed temperature.

For me I think of this problem as intervals of product temperatures that are placed on the axis.

My idea to solve it is to see which product's temperature range overlaps with most other products temperature ranges, then we can place these products in one fridge.

But the algorithm for this would be inefficient..

What's a simple greedy solution for this? any ideas?

The formalized problem here is selecting the minimum number of points such that for each temperature interval $\ell_i\in L$ we have at least one point that covers it. Let each interval $\ell_i$ be represented by $(c_i, h_i)$

Order all $\ell_i\in L$ by their $h_i$.
While there are still items that need fridges.

Buy a fridge and set it to $h_1$.
For every item with $c_i\leq h_1$, put item $i$ in the fridge and discard the interval from $L$

The runs in $O(n\lg n)$ time.

We can show this is optimal. Let the solution obtained above be $S$ and let any feasible solution be $R$. We can show that for any point $x_i\in R$, there is at most one point from $S$ between $x_{i-1}$ and $x_i$.

If the above is not true then we have some $x_{i-1}\leq y_{j-1} < y_j < x_i$ for both $x\in R$ and both $y\in S$. In this case, the interval $\ell_k$ ending at $y_j$ would not be covered by $R$. $x_i$ can’t cover it, since by definition $y_j < x_i$. $x_{i-1}$ can’t cover it either. If it did, that would mean the start point of $\ell_k$ would be less than $x_{i-1}$ and thus also less than $y_{j-1}$. This can’t be the case, though, because then $y_{j-1}$ would have covered $\ell_k$, therefore removing it from the list of intervals in the next step our algorithm. Thus we have shown that for any point $x_i\in R$, there is at most one point from $S$ between $x_{i-1}$ and $x_i$ and therefore $S$ is optimal.


Is this algorithm for partial ordering of sets complete and sound? I need to build a partial order tree of sets for analysis.

Where the order is defined as A <= B <=> for all x in A, y in B, x <= y.

I realized that if I pre-sort all the maximal and minimal elements of the sets, like this:

// A [1,3]
// B [2,4]
// C [3,5]
// D [6,7]
// E [8,9]
// F [10,11]
const input = [['A', 1], ['B', 2], ['C', 3], ['A', 3], ['B', 4], ['C', 5], ['D', 6], ['D', 7], ['E', 8], ['E', 9], ['F', 10], ['F', 11]]

I can achieve it in O(n), with the following algorithm:

let i = 0
const closed = []
const opened = {}
const lists = []
for (const item of input.reverse()) {
  if (!opened[item[0]]) { // Opening the range.
    // May need to create a new list.
    if (i <= closed.length) {
      lists.push([[i - 1, closed.length], []])
      i = closed.length + 1
    }

    // Add to list.
    lists[lists.length - 1][1].push(item[0])
    opened[item[0]] = true
  } else // Closing the range.
    closed.push(item[0])
}

This is javascript and you can pretty print the result like so:

console.log(lists.map(l => `${closed.slice(l[0][0],l[0][1])}:${l[1]}`).join('\n'))
// :F
// F:E
// E:D
// D:C,B,A

Are there orders for which this might not work?

It is pleasing to see such a nice algorithm.

Your algorithm is correct for all inputs except possibly for two corner cases.

For example, if we have
input = [['A', 1], ['B', 2], ['A', 2], ['B', 3]], then your algorithm will not produce the expected A<=B.
For example, if we have input = [['A', 1], ['B', 1], ['A', 1], ['B',1] or input = [['A', 1], ['A', 1], ['B', 1], ['B',1], then your algorithm will not produce the expected A<=B and B<=A.

The issue is not in your algorithm proper but how you define your input and expected result and how you specify the way to sort all endpoints of the intervals. Here is a sample solution.

Require that all input intervals are non-degenerate and different.
When sorting, break ties with the other endpoint. That is, given A=[1,2] and B=[2,3], when ['A', 2] and ['B',2] are compared, we must put the former before the latter since 1 < 3.

By the way, you can just use const item of input instead of const item of input.reverse(). Also, you may use ${closed.slice(l[0][0],l[0][1])} <= ${l[1]} instead of ${closed.slice(l[0][0],l[0][1])}:${l[1]} since you use "<=" to define the relation. You should get a slightly prettier output.

Last but not least, Code View Stack Exchange should probably be a better place to post this kind of question.


Optimal encoding scheme for semi-rewritable memory? Let's define a "semi-rewritable" memory device as having the following properties:

The initial blank media is initialised with all zeroes.
When writing to the media, individual zeroes can be turned into ones.
Ones can not be turned back into zeroes.

Making a physical interpretation of this is easy. Consider for instance a punch card where new holes can easily be made, but old holes can not be filled.
What makes this different from a "write once, read many" device is that a used device can be rewritten (multiple times), at the cost of reduced capacity for each rewrite.
Implicit assumptions I would like to make explicit:

The memory reader has no information about what was previously written on the device. It can therefore not be relied upon to use a mechanism such as "which symbols have been changed?" to encode data on a device rewrite. That is, the reader is stateless.
On the other hand, different "generations" of the device may use different encoding schemes as the available capacity shrinks.
The data stored can assumed to be random bits.

Sample storage scheme, to demonstrate rewrite capability:
Information in this scheme is stored on the device as pairs of binary symbols, each pair encoding one of the three states of a ternary symbol, or [DISCARDED] in the case where both symbols have been written.
The first generation thus stores data at a density of $\frac{log_2(3)}{2} \approx 0.79$ times that of simple binary encoding.
When the device is rewritten, the encoder considers each pair of binary symbols in sequence. If the existing state matches the one it desires to write, the encoder considers the data written.
If on the other hand the pair doesn't match, it writes the necessary modification to that pair, or in the case where that isn't possible, writes the symbol [DISCARDED] and considers the next pair instead until it has successfully written the ternary symbol.
As such, every rewrite would discard $\frac{1}{2}$ of existing capacity.
For a large number of cycles, the device would in sum have stored $log_2(3) \approx 1.58$ times the data of a simple one-time binary encoding.
(For a variation of the above, one could also encode the first generation in binary and then apply this scheme on every subsequent generation. The loss from the first generation to the second would be larger, and the total life time capacity reduced, but the initial capacity would be larger).
Question:

Is it possible to have a better life-time capacity than $log_2(3)$? I suspect the the real asymptotic capacity is 2.

Can a scheme do better than having $\frac{1}{2}$ capacity loss between rewrites?

The lifetime capacity can be arbitrarily large.
One may change the weight of the ternary symbols from 1/3, 1/3, 1/3 to 1/2, 1/4, 1/4 (favouring the symbol with blank bits). This reduces the entropy of the ternary symbol from $log_2(3)$ to $\frac{3}{2}$.
What it also does is reducing the capacity loss between generations, to a factor of $\frac{5}{3}$
Thus, instead of a lifetime capacity of:
$$\frac{log_2(3)}{2} \cdot \sum_{i=0}^{\infty}\left(\frac{1}{2}\right)^i = log_2(3) \approx 1.58$$
The lifetime capacity is instead:
$$\frac{3}{4} \cdot \sum_{i=0}^{\infty}\left(\frac{3}{5}\right)^i = \frac{15}{8}\approx 1.88$$
This can be generalised.
By weighted as $x$, $\frac{1-x}{2}$, $\frac{1-x}{2}$, the loss of capacity for each generation is a factor that can be written as:
$$generation\ loss =\frac{1}{2} - \frac{1}{x - 1}$$
And the entropy of the symbol is:
$$S = - \left(xlog(x) + (1-x)log\left(\frac{1-x}{2}\right)\right)$$
For a lifetime capacity of:
$$\frac{- \left(xlog(x) + (1-x)log\left(\frac{1-x}{2}\right)\right)}{2} \cdot \sum_{i=0}^{\infty}\left(\frac{1}{2} - \frac{1}{x - 1}\right)^i$$
Which grows unbounded when $x$ approaches 1, however quite slowly (logarithmic). This makes the capacity per generation very low, but the sparseness of the set bits allows the memory to be reused many many times.


What does the "principle of deferred decisions" formally mean I have encountered the phrase "Principle of deferred decisions" in Mitzenmacher and Upfal's book on Randomized Algorithms and several other courses online. Isn't it just conditional probability? In my understanding, it seems to be an intuitive way of using conditional probability:

$\Pr(\bigcap_{i = 1}^{n} E_i) = \prod_{i = 1}^{n} \Pr(E_i | E_{i-1},\dots,E_{0})$ where $E_0 = \emptyset$.

Is my understanding right?

The principle of deferred decisions is the concept that we have two ways to make a random choice both of which are equivalent.

One way is that you can toss a coin yourself at the exact step when you need a random input in some algorithm. In the other way you can imagine that there is an oracle who has already tossed a coin infinitely many times and has some sequence of the form $HTHTHH\dots$, and we query this oracle to tell us the next randomized outcome.

Basically we can defer the act of actually using a randomized input for  as long as we have to and this won't affect the randomness of this input.


How to construct a truth table Yes this is a homework problem, but I only need help setting it up, there are 7 parts to the question once I set it up:

  We want to build a function Y = 2X + 3 where X denotes a 3-bit
  unsigned value(x2x1x0) and Y = y4..y0 is a 5-bit value in hardware.
  Contruct its truth table where input bits are x2, x1, and x0 and
  output bits are y4 through y0.

The homework problem then asks for a bunch of other things which I can get. I just don't understand the question, how do you create a truth table based on a function and these input bits?

Should the truth table look something like this?

x2 x1 x0 y4 y3 y2 y1 y0
0  0  0  0  0  0  1  1
0  0  1  0  0  1  0  1
0  1  0  0  0  1  0  1
0  1  1  0  0  1  1  1
1  0  0  0  1  0  1  1
1  0  1  0  1  1  0  1
1  1  0  0  1  1  1  1
1  1  1  1  0  0  0  1

For each of the eight inputs, you compute the output. You will get a table with eight rows and $3+5=8$ columns, containing the three input bits and the five output bits.


Claimed problems with Lisp dynamic scoping What would be the problem of running the following scala codes assuming we are working with dynamic scoping and a global stack to store environments as some variants of Lisp do?

def fact(n:Int,f:() => Int):Int =
 if(n == 0) f()
 else fact(n-1,() => n*f())
fact(7,() => 1)

def incrementer(x:Int)  = y => y+x
incrementer(2)(3)

With fact, the primary problem is with f.  If n is 0, then it works fine.  However, for any other value of n, fact is called with an f of () => n * f().  So when the base case (n = 0) is finally encountered, f is () => n * f().  When f is invoked, f is still () => n * f().  So the call to f results in unbounded recursion with itself.

With incrementer, x will be not be defined when y => x + y is called in your example.  This is because y => x + y does not close over x (because of dynamic, as opposed to lexical, binding), there is no call on the stack that binds x to a value when the closure is invoked, and there is no global / top-level binding for x.


How is an Assembly Language Processed by a CPU's Circuitry? I'd like to have a bit more understanding of how, on a circuitry/hardware level, an assembler program works.

I think I have a very broad-brush understanding of how a CPU would process machine code on a hardware level. Please bear with me for this very generalised, hypothetical example:

If you took 00101110 in machine code, with the first part 0010 as an opcode and the second part 1110 as location address...

I think I understand, broadly, how those 8 bits of data would be fed along 8 wires to an instruction register, and how from there, the opcode 0010 gets fed along 4 wires into a variety of checking circuits to check the opcode, and a checking circuit would output true if if the opcode corresponded to the configuration of that circuit. Like this (yes I've been watching crash course computer science):

And i think I understand how, in broad terms, the location address 0111 would be sent along 4 wires that feed into multiplexors attached to four latch matrices, causing address location 0111 to be accessed in each of those matrices, each of which then feeds back whether its data bit at the location was a 1 or 0 / on or off.

What I'm saying is that I think I can begin to see, or at least imagine, how a processor 'processes' a binary number, on the level of hardware/circuitry, without it seeming like magic.

My question is, can someone explain to me on this level how a CPU, as part of an assembler, would translate assembly code?

For example, how would the circuitry take MOV EAX [EBX] and act on that as an instruction? I know that it would parse it, etc., but HOW does it parse it, on the level of wiring? Like how does it take a 'MOV' and translate that into the correct configuration of on/off wires?

On a related note, obviously the 'MOV' isn't stored as 'MOV' in the computer's memory - it's stored in binary. So if it's already stored in binary, why do we need to bother to translate it to a different binary configuration using an assembler?

An assembler is a program that reads assembly language commands and translates then into a sequence of binary instructions, addresses and data values that is called machine code. The machine code is stored in the computer's memory and can be executed by the computer at some later time. Machine code is read and "understood" directly by the CPU.

So a command such as "load the value 10 into register A" might be written in assembly language as "LDA 10" and then stored in machine code as one byte 00101010. The first four bits of the machine code instruction 0010 represent the LDA instruction and the second four bits 1010 represent the value that is to be loaded.

Note that the assembler makes life easier for the programmer by translating the "LDA" instruction and translating the value 10 from decimal to binary. It will also do other stuff like allowing the programmer to use labels, which it then translates into specific memory addresses.

In the simplest CPU architecture, when the CPU executes the instruction 00101010 it actually runs a sequence of low level microinstructions which will be something like this:

Add 1 to the register that tells the CPU where the next instruction is stored in memory
Set a control line to take control of the data bus.
Load the lowest four bits of the machine code instruction onto the data bus.
Release control of the data bus.
Set a control line to tell Register A to read and store the value on the data bus.
Read the next instruction from memory.

In the very simplest/oldest CPU architecture this final translation from machine code to microinstructions is hard wired in logic gates.

A good guide to this sort of stuff for beginners is "But How Do It Know".

Bonus question: If an assembler is a program that creates other executable programs, how is the assembler created in the first place ?


How to iterate over vectors in order of probability Consider a random $n$ dimensional vector $v$ where $v_i \in \{0,1\}$.  For each $i$ we know $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent.  Using these probabilities, is there an efficient way to iterate over all possible binary $n$ dimensional vectors in order from most likely to least likely (with arbitrary choices for ties)?

Take for example $p = \{0.8, 0.3, 0.6\}$. The most likely vector is $(1,0,1)$ and the least likely is $\{0,1,0\}$.

For small $n$ we could label each vector with its probability and sort although this isn't very efficient. However, consider $n=100$ for example. This is no longer an option.

You can solve this with a priority queue.

Let $L(x)$ be the log-probability of the vector $x$, i.e.,

$$L(x) = \log \prod_i p_i^{x_i} (1-p_i)^{1-x_i} = \sum_i \ell_i(x_i)$$

where

$$\ell_i(b) = \log (p_i^b (1-p_i)^{1-b}).$$

Since the log is monotone, your problem is equivalent to looking for a way to enumerate the vectors $x \in \{0,1\}^n$ in order of decreasing $L(\cdot)$ value.

Of course, it is easy to identify the vector which has highest probability, i.e., highest $L(\cdot)$-value.  We simply put a $1$ in the $i$-th position if $p_i\ge 1/2$ and a $0$ otherwise; call the result $x_{\text{best}}$.  So create a priority queue that will hold a set of $n$-vectors.  Initialize it to a single element, $x_{\text{best}}$.  Assign it the priority $L(x_{\text{best}})$.  In general, if $x$ is in the priority queue, its priority will be $L(x)$.  Also, create a set $S$ of nodes that have been previously output; initially we will have $S = \emptyset$.

Now repeat the following loop:

Find the value of maximum priority and remove it from the priority queue.  Call it $x$.
Output $x$.  Add $x$ to $S$.
For each $i=1,2,\dots,n$: Let $y$ denote the vector obtained by flipping the $i$th bit of $x$; if $y \notin S$, add $y$ to the priority queue, with priority $L(y)$.

This loop will output the elements of $\{0,1\}^n$ in order of decreasing $L(\cdot)$-value.

Why does this work?  Basically, if $x$ has the highest $L(\cdot)$-value, then the next-highest must be obtained by flipping a single bit; flipping two bits will give you something strictly worse.  The same kind of justification can be applied inductively.  Or, to think about it another way, this is basically Dijkstra's algorithm applied to the $n$-dimensional cube (vertices are $\{0,1\}^n$), and Dijkstra's algorithm is an efficient way to enumerate the nodes of a graph in order of decreasing distance.  Since $L(\cdot)$ is additive, it can be understood as a distance from $x_{\text{best}}$.


Proving $\{0^{2^n}\}$ is not regular using pumping lemma I am currently learning the pumping lemma, and encountered the following question, which I am unable to solve:

Prove that $L = \{ 0^n \mid \text{$n$ is power of 2}\}$ is not regular.

I considered $w = 0^{2^n}$, where $n$ is the pumping lemma constant. Then I divided $w$ into $xyz$, where $y \ne \epsilon$ and $|xy| \leq n$. Hence, $|y|$ will be between 1 and $n$. So, $|xy^kz|$ satisfies $L$ if $|y| = 2$ for all values of $k$ and it is within the bound. So, how is $L$ irregular?
The question is to prove it is irregular but here it is coming as regular.

If you choose $k = 2$ then, writing $|y| = m$, we get
$$ xy^2z = 0^{2^n+m}. $$
Since $1 \leq m \leq n$, we have
$$ 2^n < 2^n+m \leq 2^n+n. $$
Cantor's theorem shows that $n < 2^n$, and in particular,
$$ 2^n < 2^n+m < 2^{n+1}. $$
Therefore $xy^2z \notin L$.

Let me take this opportunity to mention another misconception. There are some non-regular languages which satisfy the pumping lemma. Therefore the fact that you couldn't prove that a certain language is non-regular using the pumping lemma does not imply that the language is regular.


Need clarification regarding certificates of coNP problems NOTE: this is not an attempt to prove $NP \neq coNP$

There is one thing I have never been able to completely digest about the certificates of problems in $coNP$ and I would very much appreciate a definitive clarification from this community.

Let's focus on the subset sum problem ($SUBSUM$), now we all know that this problem is in $NP$ since,
to accept language membership, a Prover $P_v$ can emit a certificate which a verifier $V_r$ can check in polynomial time. Up to here no problem. The complement of this problem ($\overline{SUBSUM}$) is in $coNP$ which means that
we do not know if there is a succinct (ie polynomial) certificate to decide the language.
If such a certificate does not exist, then $NP \neq coNP$
and therefore $P \neq NP$.
What I don't understand is this:

If I have (for example) a set $S$ of integers and the number $0$ as an input and I ask:
Prove me that $\forall s \in S \space\space\lnot SUBSUM$, ie $\nexists$ a subset of $S$ such that the sum of its element give $0$ as a result (this is  $\overline{SUBSUM}$, the complement of the subset problem).
How can a certificate exist for this problem whose verification is in $P$? I mean, i need to prove it for all the subset so the search space must be the powerset of $S$. If $|S|=n$ then $\mathcal{|P(S)|}=2^n$. So if the prover, for example, produce a $2^{n/3}$ certificate, this means that I systematically leave out $2^{ \frac{2}{3}n}$ subsets.
What I don't completely understand and for which I need clarification is why this argument is not accepted as evidence that $NP$ is not closed under complement.

The proof does bot need to be a subset. It might be another indicator that the given set has a some stricture preventing it from being a positive instance of the subsetsums problem. A good example with a non-trivial certificate is linear programming. Linear programs admit both a positive and a negative certificate (For the question whether the optimal can be smaller/greater than a value k). The positive instance is of course an assignment of the variable. The negative however is given by Faraks lemma and the weak duality.

A good exercise for you is to look up linear programs, weak duality and Farkas lemma :)


Should all internal node keys in B+ tree also be in the leaves? I was reading about B+ tree insertion.
The algorithm takes following form:

Insert the new node as the leaf node.

If the leaf node overflows, split the node and copy the middle element to the parent index node.

If the index node overflows, split that node and move the middle element to the parent index node.

However, adding the new index value in the parent node may cause it, in turn, to split. In fact, all the nodes on the path from a leaf to the root may split when a new value is added to a leaf node. If the root node splits, the tree grows by one level.

Now the book asks to insert 33 in following tree of order 4:

I was guessing how those [10,20,30] occur to be the root node. Before performing first split while forming above tree, these [10.20,30] should be in some leaf and in any case they should be present in some leaf.
In other words I feel that all internal node keys should also be present in the leaves. However thats not the case with [10,20,30]. This is also inline with the fact that in B+ tree all data is present in the leaves, so all keys should be present in the leaves.
Another example on youtube also have 13 and 30 in the root node but not in any leaf.
Am I wrong with the fact that all internal node keys should also be in the leaves?

The internal keys come from values also stored in leaves, but if you allow deletions, the value could be deleted from the leaf after it is created and used in the internal node.  Deleting the value from a leaf won't change any internal nodes, unless the leaf becomes underfilled.  With the insertion you list, it would have the property you are thinking of if there were no deletions.

On the other hand, it is possible that the author wasn't thinking of either the property you name, nor the possibility of deletions, when making the question, and just used 10, 20, 30 as easy separators.  For sure, I have written questions with mistakes before, and usually, even with a mistake in the question, it can usually be answered properly to see if the student understands the material (insertion in this case).  If a student then asked me what your post asks?  I would be pleased with their understanding of the material to notice this property.


The feedback polynomial is $x^7 + x^6 + x^5 + x^1 + 1$ and can be computed using the Berlekamp-Massey algorithm.