How to learn computer science the right way I looked through the sites and this seems to be the best place to ask this question. I am sure it has been asked 10000 times but I am looking for a tailored answer to me and my situation. I currently work as a project manager for a startup. I have a working knowledge into many different fields ranging from HTML, CSS, PHP, JS, MySQL, Server Administration, Marketing, SEO, Etc. I have been working in the web development industry for the last 10 years, I started when I was 11. I have associates level education but no BCS. I don't have the time right now to pursue that as much as I would love to in my current situation(newborn son) and my wife is pursuing her eduction currently. I knew all these language but I don't really know them. I wanna truly understand them, why they work the way they do and how I can master them. This is more of a personal desire then one driven by money, as they most likely wont affect my career. I really would like to learn a new language.

I have about 3-5 hours every week night while I have my son and my wife is in school to study at home. I can't really afford college or guarantee that I will have that time available to make that commitment so I would like to have a no pressure solution. I have completed a lot of treehouse and didn't find much of a challenge.  The courses really didnt drive into the languages either and teach me anything new.

I am looking to start learning things like computer logic, but I need some pointers of where to start and what terms to search to find this education info. After I truly understand the inner workings of a computer from the microprocessor to ram to harddrive to interpreter to etc, I would like to learn a new programming language. My current PHP skills arent great, and its more of a working knowledge then understand so treat me as a new programmer.

To sum things up

Can I have some recommendations of key concepts to learn for new software engineers
If anyone can provide good education sources, please do so
I would like some recommendations of languages to learn that are in demand and are new, and arent going anywhere anytime soon. From my current research it looks like Java or C# are my best options. Anything I should know about those, any assume the previous questions apply to them.
I am willing to pay for this

Firstly, most of the things you are talking about fall under the category of programming, rather than computer science. Programming is a useful tool for computer scientists, and indeed some computer scientists study programming, but it programming barely scratches the surface of what computer science is about.

Why not try a free online course, such as one offered by coursera? There are many many courses, from programming to theory to machine learning to software engineering. All are free and typically the standard of quality is extremely high.


How to prove that $n^2$ is not $o(n^2+10^{10}n)$? I need to prove that $n^2$ is not $o(n^2+10^{10}n)$. I thought of the limit test:
$$
\lim_{n \to \infty} \frac{n^2}{n^2+10^{10}n} = 1 \Rightarrow n^2 = \Theta(n^2+10^{10}n)
$$

However I'm not sure if the result of the test rules out the possibility of $o(n^2+10^{10}n)$.

One definition $f(n)=o(g(n))$ is that $\lim_{n\to\infty} f(n)/g(n)=0$. If this is the definition you're using, then showing that the limit is $1$ already shows that $f(n)\neq o(g(n))$.

The other definition is that, for every $c>0$, there is an $n_0$ such that $f(n)\leq cg(n)$ for all $n\geq n_0$.  The fact that $\lim_{n\to\infty} f(n)/g(n)=1$ means that, for all $\varepsilon>0$, there is some $n_0$ such that $f(n)/g(n)>1-\varepsilon$ for all $n\geq n_0$ (this is part of the definition of "limit").  So, for all $\varepsilon>0$, we have $f(n)>(1-\varepsilon)g(n)$ for all large enough $n$. This means that, in particular, we do not have $f(n)\leq cg(n)$ for $c=1-\epsilon$, so $f(n)\neq o(g(n))$ by the alternative definition.


How should we define the behavior of a Turing machine where the head tries to move left from the leftmost tape position? If we have a Turing machine in a model with a tape that is infinite only to the right and assume at some point the head tries to move left from the leftmost position.

How should we define the behavior in such a case? Is a machine doing so for some input not a valid Turing machine? And if so, how can we make sure when we define a Turing machine that this situation can't occur for any input?

I've read some sources about Turing machines though couldn't find the answer to this specific case, and I see no reason why this case won't happen for an arbitrary Turing machine and some input.

There is no single accepted model of Turing machines. Different choices would lead to very similar models, which simulate each other with very small overhead. That's why we usually don't care so much about the exact model.

Here are some possibilities:

If the Turing machine attempts to move to the left of the origin, then the head stays put. The Turing machine might or might not be notified.
The Turing machine has a mechanism to detect that it has reached the origin, and cannot move to the left of it (the specs don't allow it).
Same, but not the machine can move to the left, and crashes if it attempts to do so (you decide how to interpret a crash – acceptance, rejection, infinite loop).
If a Turing machine attempts to move to the left of the origin, then instead it moves right. This makes sense if the Turing machine is guaranteed to always move at every step.

You can probably think of several other alternatives.


Detecting errors changing an odd number of bits using CRC I was studying CRC from lecture notes of Schwarzkopf but I am stuck at this statement:

If $G(x)$ is a factor of $E(x)$, then $G(1)$ would also have to be $1$.

What does this statement means? It is the third point in the third last block of the article whose link is given. I know a similar question is asked but that is a specific question. I want to understand this particular statement.

Recall that we are working modulo $2$. Thus $E(x)$ is a polynomial whose coefficients are $0,1$, and $E(1) \in \{0,1\}$.
By definition, $G(x)$ is a factor of $E(x)$ if there exists a polynomial $H(x)$ such that $E(x) = G(x) H(x)$.
In this case, we assume that $E(1) = 1$. Since $E(1) = G(1) H(1)$, this forces $G(1) = 1$.


Theoretical CSPs where (in)equality constraints can be expressed as a single constraint? I'm designing puzzles by running a MAX-CSP solver, and it works nicely in practice. For concreteness, my problems have the following form (in a pseudo-modeling language):

# set up vars & their domains
x_1 {1}
x_2 {0,1}
x_3 {0}
x_4 {0,1}
# constraints
(x_1 != x_2)
(x_2 = x_3)
(x_3 = x_4)
(x_1 != x_4)
(x_2 = x_4)

The objective is then to choose values from the domains of each variable so as to maximize the number of constraints satisfied.

More generally, in all of my instances, we have a fixed value of $k$. The domain of each variable is of size at most $k$. Every constraint involves two variables, and is an inequality or an equality constraint.

  When CSPs are studied from a theoretical viewpoint, is there a model that captures the above in a straightforward way?

In complexity theory, CSPs are usually specified as a set of allowed predicates. If the (finite) domain is $D$, a predicate of arity $d$ is an arbitrary subset of $D^d$ of allowed values. In particular, equality (or inequality) is a predicate of arity 2.

This is the point of view taken in Schaefer's dichotomy theorem as well as the more recent universal algebra approach (see for example a short survey by Libor Barto). Another example is the celebrated Raghavendra's theorem, which states that assuming the unique games conjecture, every CSP can be approximated optimally using semidefinite programming.


Context Free Grammar $L=\{a^ib^{2i}c^{2i} | i>1\}$ In one of my exams I needed to find a CFG for $L=\{a^ib^{2i}c^{2i} | i>1\}$.

however, it really seemed to me that it is not a CFG.
I tried to show it is not using the pumping lemma, and think I managed, but I don't really know if I did something wrong there.

So was I wrong or the question is wrong?

Thank you.

Your language is not context-free. You can see this by applying the inverse of the homomorphism which sends $a$ to $a$, $b$ to $bb$ and $c$ to $cc$; this results in the language $\{a^ib^ic^i : i > 1\}$, which differs from a well-known non-context-free language by just a finite number of words.


Maximum number of augmenting paths in a network flow Let's say we a have flow network with $m$ edges and integer capacities.

Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.

A good way to start thinking about this is to imagine that we know the maximum flow already.  How can we figure the sequence of $m$ paths?

I got it myself... The idea is to set the flows of all edges to 0 one by one. It will take  M iterations to do so. Once all edges are set to zero it becomes clear that the highest number of augmenting paths can not exceed the number of edges that are 0.And since there are M such edges the maximum number of possible paths is M as well.


How to construct Context Free Grammar of words with equal number of 0's and 1's i am trying to find a cfg for this cfl

L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$

is there a way to count the number  of 0's or 1's in the string?

The question defining a context-free grammar for $\{\in\{0,1\}^*:\#_0(w)=\#_1(w)\}$ restricts its answers to one particular grammar and the proof for its correctness is somewhat involved. Here I would like to show a different grammar that is easier to figure out.

Since the requirement is the same number of 0's and 1's, we can grow the start non-terminal $S$ by a pair of 0 and 1 in all sorts of way. (This is more or less what your idea of "counting" should be). We will have the following production rules, $S\to S01\mid S10\mid 01S\mid 10S\mid 01S\mid 10S\mid \epsilon.$

However, if we check closely, the above grammar does not generate 00111100. What happens is that the above grammar will generate the first part 0011 as a whole, missing the second part 1100. That suggests us to add another rule $S\to SS$. Once we have added that rule, rules $S\to S01\mid S10\mid 01S\mid 10S$  become redundant. The final grammar is
$$S\to SS\mid 0S1\mid 1S0\mid \epsilon.$$

It is clear that the word generated by that grammar has the same number of 0's and 1's.

Are all such words generated by that grammar?

The rule $S\to\epsilon$ show that unique word of length 0 can be generated.

As the induction hypothesis, suppose all words of length less than $2n\le2$ can be generated.

Let $w$ be such a word of length $2n$.

Let $d(k)$ be the difference of the number of 0's and the number of 1's in the first $k$ letter of $w$. In particular, $d(2n)=0$. Since the situation is symmetric with respect to 0 and 1, WLOG assume $w$ starts with a 0, i.e., $d(1)=1$.

If $w$ ends with a 1, then $w=0w'1$ for some word $w'$. $S$ generates $w$ since $w'$ have the same number of 0's and 1's and $w'$ is shorter than $w$. So $S\Rightarrow0S1\Rightarrow0w'1=w$.
If $w$ ends with a 0, then $d(2n-1)=-1$. Since $d(x)$ changes 1 by 1, $d(k)=0$ for some $1\lt k\lt 2n-1$. Let $w_1$ be the first $k$ letters of $w$ and $w_2$ the rest of $w$. By induction hypothesis, $S\Rightarrow w_1$ and $S\Rightarrow w_2$. Hence $S\Rightarrow SS\Rightarrow w_1w_2=w$.

We have completed mathematical induction. All such words can be generated.


What can be said about the Fourier expansion of compositions of Boolean functions, if anything? Let $\chi_S: \mathbb{F}_2^n \to \{\pm 1\}, x \mapsto (-1)^{\sum_{i \in S}x_i}$ for every $S \subseteq [n]$ denote the parity functions from $\mathbb{F}_2^n$ to $\{\pm 1\}$. Then, of course, every $f: \mathbb{F}_2^n \to \{\pm 1\}$ can be written as a linear combination (over $\mathbb{R}$) of the parity functions. I have tried (without much ease or success), to produce the Fourier expansions of compositions of even simple Boolean functions, in particular of conjunctions of parity functions, like $\chi_S \wedge \chi_T$ (where under the encoding of $1_{\mathbb{F}_2^n} \mapsto -1,0_{\mathbb{F}_2^n} \mapsto +1$, $\wedge$ is just $\max_2$).
So, my questions are:

Are there good techniques/tools in general for computing/estimating the Fourier expansion of $f \circ g$ when we know both of the expansions for both $f,g$?
Is there something we can say about the particular case of conjunctions/disjunctions over parity functions?

If $f,g$ are two $\pm1$-valued functions and $f \lor g$ is their maximum (this is the standard notation for maximum; $\land$ stands for minimum), then
$$
f \lor g = \frac{1 + f + g - fg}{2}.
$$
Since $\chi_S \chi_T = \chi_{S \Delta T}$, this shows that
$$
\chi_S \lor \chi_T = \frac{1}{2} + \frac{\chi_S}{2} + \frac{\chi_T}{2} - \frac{\chi_{S\Delta T}}{2}.
$$
You can read the Fourier expansion from this (unless $S = T$, in which case $\chi_S \lor \chi_S = \chi_S$).


Searching a Treasure I was selected for a UG interview and the following was one of the questions asked:

"Suppose we have an $8 \times 8$ grid. Under one of the blocks, I (the
interviewer) have hidden a treasure which you have to find by asking
questions to me. The questions are to be of the form - "Is it under
this $n \times n$ square (where $n \le 8$)?" For each question, I
charge you some money and you have a finite amount with you. What is
the least number of questions that you can ask to find where the
treasure is?

I don't have any background in high school computer science and while discussing this problem with a senior, I discovered that the problem relates to "complexity" in computer science. Can somebody help me with this as a beginner?

7 is the least number of questions that you can ask to guarantee to find the treasure.

the idea of binary search

Every time when we ask a question, we try to reduce the maximum number of unit squares left to search as small as possible. That is, try to cut the number as nearly to a half as possible. This is the idea as binary search.

the binary search on a row or column of cells

Each unit square of the given grid is called a cell.

Whenever we are left with some number of cells that are contiguous on the same row or column, we can simulate binary search on those cells with questions on some $n$ by $n$ squares. For example, suppose the treasure is among the cells marked by "t".

$$\begin{array}{|c|c|c|c|c|}\hline
&&&&\\\hline
\phantom{t}&t&t&t&t\\\hline
&&&&\\\hline
&&&&\\\hline
&&&&\\\hline
\end{array}$$

We can ask whether the treasure is in the following square marked by the question marks.

$$\begin{array}{|c|c|c|c|c|}\hline
&&&&\\\hline
\phantom{?}&?&?&\phantom{?}&\phantom{?}\\\hline
&?&?&&\\\hline
&&&&\\\hline
&&&&\\\hline
\end{array}$$

If the answer is yes, then we have restricted the range to search to the two "$t$"-cells to the left; otherwise, to the two "$t$"-cells to the right. Continuing this way, we can accomplish binary search on a row of cells or on a column of cells.

the full scheme

First ask whether it is inside the 6 by 6 square at the bottom right corner.

If yes, ask whether it is inside the 4 by 4 square at the bottom right corner.

If yes, ask whether it is inside the 3 by 3 square at the bottom right corner.

If yes, ask whether it is inside the 2 by 2 square at the bottom right corner.

If yes, we have 4 unit square left. Ask another 3 questions to find it.
Otherwise, it must be at one of the following cells.
$$\begin{array}{|c|c|c|c|c|c|c|}\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
\phantom{t}&\phantom{t}&\phantom{t}&
\phantom{t}&\phantom{t}&t&t&t\\\hline
&&&&&t&&\\\hline
&&&&&t&&\\\hline
\end{array}$$
Now choose the following square to ask to determine whether it is on the top row of that 3 by 3 square except the top left cell. If yes, we are left with 2 cells on the same row; otherwise we are left with 3 cells on the same column. Now start binary search.
$$\begin{array}{|c|c|c|c|c|c|c|}\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&?&?\\\hline
\phantom{t}&\phantom{t}&\phantom{t}&
\phantom{t}&\phantom{t}&\phantom{t}&?&?\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
\end{array}$$
Otherwise, it must be at one of the following cells.
$$\begin{array}{|c|c|c|c|c|c|c|}\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
\phantom{t}&\phantom{t}&\phantom{t}&
\phantom{t}&t&t&t&t\\\hline
&&&&t&&&\\\hline
&&&&t&&&\\\hline
&&&&t&&&\\\hline
\end{array}$$
Now choose the following square to ask to determine whether it is on the top row of that 4 by 4 square except the top left cell. If yes, we are left with 3 cells on the same row; otherwise we are left with 4 cells on the same column. Now start binary search.
$$\begin{array}{|c|c|c|c|c|c|c|}\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&?&?&?\\\hline
&&&&&?&?&?\\\hline
\phantom{t}&\phantom{t}&\phantom{t}&
\phantom{t}&\phantom{t}&?&?&?\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
\end{array}$$

Otherwise, ask whether it is inside the 5 by 5 square at the bottom right corner.

If yes, inquire an appropriate square to determine whether it is on the top row of that 5 by 5 square except the top left cell. If yes, we are left with 4 cells on the same row; otherwise we are left with 5 cells on the same column. Now start binary search.
Otherwise, inquire an appropriate square to determine whether it is on the top row of that 6 by 6 square except the top left cell. If yes, we are left with 5 cells on the same row; otherwise we are left with 6 cells on the same column. Now start binary search.

Otherwise, ask whether it is inside the 7 by 7 square at the bottom right corner.

If yes, inquire an appropriate square to determine whether it is on the top row of that 7 by 7 square except the top left cell. If yes, we are left with 6 cells on the same row; otherwise we are left with 7 cells on the same column. Now start binary search.
Otherwise, inquire an appropriate square to determine whether it is on the top row of the original 8 by 8 square except the top left cell. If yes, we are left with 7 cells on the same row; otherwise we are left with 8 cells on the same column. Now start binary search.

Why cannot we succeed with less than 7 questions?

Since after the first question, one of the yes or no answer will leave us at least $\min(64-5^2, 6^2)=36$ cells to search. Each question can cut the maximal number of cells to search at most in half. Since $2^5=32 < 36$, we need at least another $5+1=6$ questions to guarantee success.

Open problem

Does the scheme above reach the minimum average number of questions, assuming the treasure can be in any cell with equal probability?

I believe it does. However, I am not able to obtain a complete proof as it is not clear how to reduce the many cases to a manageable level.

Exercise

What is the least number of questions to guarantee to find the treasure that is in one of the cells of a 7 by 7 grid?


Where do these DRAM row/column calculations come from? Let r be the number of rows in a DRAM array, and c be the number of columns.

Apparently, DRAM with organization 16x1 requires least pins when r = c = 4 because fewer address bits are required to represent them, and so does DRAM with organization 16x4. Why are these the same? Doesn't the latter have 4 columns instead of 1?

The first value describing the DRAM is the number of data-interface-sized "chunks" it contains and the second value is the width of the data interface in bits, i.e., bits per "chunk".  A 16x1 DRAM would only have 16 bits addressable at 1-bit granularity, with four rows and four columns allowing a minimization of address pins.  A 16x4 DRAM would have 64 bits addressable at 4-bit granularity (and with 16 addressable units a 4 row and 4 column arrangement would minimize address pins).


Disco Zoo Complexity A popular mobile game, DiscoZoo, is about "rescuing" animals from a 5x5 grid of cells. Each animal represents a unique pattern (some have 3 cells, some have 4). The object is that, given this 5x5 grid, find all (or as many as possible) of the given animals within 10 turns, where the pattern of animals can be at any place within the grid (but cannot be rotated, change size, etc. - only translated such that all the coordinates of each animal are valid, and there is only one animal per square). We can only "get" an animal if we can successfully find each of the squares of that animal within the number of turns left; otherwise, we do not.

Here is an example. The sheep has a pattern of 4 horizontal adjacent squares, so clearly the squares (5, 2) (indexing from 1 and as (row, col)) and (5, 5) will be a sheep (and thus get the sheep). For the rabbit, it has a pattern of 4 vertical adjacent squares, so the squares (2, 1) and (4, 1) will be the rabbit. For the cow, it has a pattern of 3 horizontal adjacent squares, and since square (4, 2) was selected (and no animal placed there), the only square left for the cow is (4, 5). This is assuming that we do have attempts left (but there aren't any for this example).

More formally, we are given a 2D array $a[1..n][1..n]$, and $m$ animals $A_1,...A_m$ such that $A_i$ has value $p_i$. In the grid are the values of the $p_i$'s (in their respective positions) and all the rest are 0. Each cell either has 0 or one non-zero value (i.e., only one animal). However, none of the values are given to us at the start. Once we "select" a cell, that cell's value is revealed to us. Our objective is to find all or the maximum possible number of non-zero cells in the grid within $g$ turns.

What is the complexity of this problem in general?

Edit: after some thinking about the problem, let's restrict ourselves to having $m$ copies of the same animal $A$, and let that animal be a 2x2 square (i.e., occupies coordinates $(x, y), (x+1, y), (x, y+1), (x+1, y+1)$). What is the complexity of this version of the problem?

Even if we restrict further by looking at 1x1 squares, this is equivalent to finding nonzero elements in the matrix - it is trivially solvable in $\Theta(n^2)$ time, but can we do better?

For the 2 by 2 block version in the edit, consider the promise problem where there is guaranteed to be just one block in each 3 by 3 region, where the regions have coordinates $(3i+1,3j+1)$ to $(3i+3,3j+3)$ for non-negative integers $i$ and $j$.  By an adversary argument, in the worst case one may have to probe one square in each of the first $\lfloor n/3\rfloor^2-m$ regions and then two squares in each of the last $m$ regions, so in the worst case at least $\lfloor n/3\rfloor^2+m \ge ((n-2)/3)^2+m\ge \Omega(n^2)$ probes.


Is the language Turing machine-Input pairs for which the computation loops recognizable? I'm wondering if the following language is $L \in \mathsf{R}$, $L \in \mathsf{RE} \setminus \mathsf{R}$, $\overline{L} \in \mathsf{RE} \setminus \mathsf{R}$:
$$L=\{<M,w> \,\mid M \mbox{ Loops on input } w\}$$
to be clear: We say that a TM loops on a string if during its run on the string it repeats the same sequence of configurations. Note that every TM that loops on a string is a TM that doesn’t halt on the string but not every TM that doesn’t halt on a string is a TM that loops on the string.
I'm leaning towards $\overline{L} \in \mathsf{RE} \setminus \mathsf{R}$ and wondering if it's possible to map $\overline{L}$ to HALT?

The language $L$ is recognizable: you can build a Turing machine that recognizes $L$ by simulating $M$ and keeping track of all the traversed states. As soon as a state is repeated, you accept. If $M$ halts and no stated is repeated, then reject.
Moreover, $L$ is not decidable. Suppose that $L$ was decidable, then you could do the following to solve the halting problem:

Create a new Turing machine $M'$ behaves as $M$, but instead accepting/rejecting, it goes into some looping state.

Simulate a Turing machine $T$ that decides $L$ to check whether $\langle M', w \rangle \in L$.

If $\langle M', w \rangle \not\in L$ then $\langle M, w \rangle$ must not halt.

If $\langle M', w \rangle \in L$ then either $\langle M, w \rangle$ halts or loops.

Simulate $T$ to check whether $\langle M, w \rangle \in L$.

If $\langle M, w \rangle \in L$ then $\langle M, w \rangle$ loops, and hence it does not halt.

If $\langle M, w \rangle \not\in L$  then $\langle M, w \rangle$ does not loop, therefore it halts.


How to solve linear equation with binary tree I'm working on a school project that takes in a simple linear equation and has to return the value of $x$. The code I have transforms $x + 3 = 3x - 2$ into a binary tree format like so:

        =
      /   \
     /     \
    +       -
   / \     / \
  x   3   *   2
         / \
        3   x

With the expression in this format could someone please explain how can I obtain the value of $x$.
Any help is appreciated - if you have an alternative method that may make it easier I'd love to hear it.

For solving this question you should assume a tree with '=' root
And in the left side of root push factors of x and in the right side push your constant values, now variable x is equal to sum of right side division by left side.


Fundamental and essential matrices, value of intrinsic parameters I observe a scene with two cameras, c1 and c2, that produce two images i1 and i2, respectively. What I ultimately want to do is to use information of image i1 and image2 simultaneously, e.g., for object detection.

As far as I understand it, I would not be required to find the intrinsic parameters of c1 and c2, also I do not need to know their relative position and rotation if I want to rectify i1 and i2. I can "simply" calculate F from a set of corresponding points - with no explicit relation in 3D of the points (like known distances). Which disadvantages would that have for me? I would not be able to do 3D reconstruction then, correct? But apart from that, there is no difference?

Or, asked differently, for rectification I do not need the intrinsic parameters. I only need them to do 3D reconstruction? What are the intrinsic parameters good for?

What are the intrinsic parameters good for?  They potentially allow mapping objects in the images to locations in the real world (in 3D).  For some applications, that can be very useful.  For instance, consider pedestrian detection, where we want to detect pedestrians.  Usually, it's not enough to detect the presence of a pedestrian: we also want to know exactly where the person is, and how far away they are.

Calculating alignment from a set of corresponding points is not an unreasonable approach to aligning two images.  The primary disadvantage is that you need a way to identify a set of corresponding points.  This typically requires either (a) explicit calibration or (b) heuristic methods.

Explicit calibration is a perfectly fine approach, if it is feasible for your application.  However, for some applications we only have images post-facto and we don't have any way to do an explicit calibration, so it's not always an option.

Heuristic methods are another possibility.  They try to find corresponding points, e.g., using Lucas-Kanade, optical flow, or other methods.  As heuristics, they are not guaranteed to work.  Sometimes they might fail to detect corresponding points, or output false detections.  Another issue is that their effectiveness depends upon characteristics of the scene that you're capturing: they're more effective for some kinds of scenes than others.  But this also could be a valid approach.

To be clear: 3D reconstruction requires two cameras (as mentioned in the question) or depth information; just one 2D camera plus its intrinsics are not enough to reconstruct where each object is in the real world, in 3D space.


Fastest algorithm for transforming points into graph Given a set of $n$ two-dimensional points in the plane
$$\{ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\}$$
and a real number $M$, I want to transform this set of points into a graph with the points as vertices with an edge between points $A$ and $B$ if the distance between $A$ and $B$ is at most $M$.

What is a fastest algorithm that can perform this task?

As you can imagine, evaluating every pair of points is very expansive ($O(N^2)$ for $N$ points).

If your set of point is sufficiently dense with respect to $M$, a simple solution is to use a grid. Build a grid of $M \times M$ cells, then for each cell, compute the list of points inside (doing one loop on points $O(N)$). Finally you just have to compare every point with every other point in the same cell or in one of the 8 surrounding it.

If you set of points is very dense you even can use a second grid of $\frac{M}{\sqrt{2}} \times \frac{M}{\sqrt{2}}$ cells so the points in the same cells have necessarly pair-wise distance lower than $M$. This may save some computation.

Note that in the case you have lot of empty cells (small density), it may generate memory issue. Imagine for instance 2 pairs of points very distant to each other (with respect to $M$). It may require a tremendeous grid, just to process 4 points... In this case, the basic "all-pair" comparison would be largely more efficient. k-d tree may be a solution to this problem. Or you can either identify the empty zones to process the points subset by subset.


Who was the first to define the RAM model? I am working on a project where I refer to the RAM model, I explain what it is, but I am not sure who defined it first.

The wikipedia article is not very explicit about it, and the first citation is from 1946.

Goldstine, Herman H., and von Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study, Princeton. Reprinted on pp. 92–119 in Bell, C. Gordon and Newell, Allen (1971), Computer Structures: Readings and Examples, McGraw-Hill Book Company, New York. ISBN 0-07-004357-4}.

According to the chapter notes of Chapter 1 of the book "Computational Complexity: A Conceptual Perspective" by Oded Goldreich,

  The RAM model is attributed to von Neumann's report [234].

where [234] refers to

  J. von Neumann. First Draft of a Report on the EDVAC, 1945. Contract No. W-670-ORD-492, Moore School of Electrical Engineering, Univ. of Pennsylvania. Reprinted (in part) in Origins of Digital Computers: Selected Papers, Springer-Verlag, pages 383--392, 1982.


What is the point of this lambda expression? Let's take this lambda expression : $\lambda\:x \:\ast\:x\:2$ that "computes" x * 2.

From what I understand, $\ast$ is a constant operator, but since its nothing else than a symbol, how does that let us compute the multiplication x * 2?

I would have thought that we should have defined $\ast$ as some sort of recursive function for instance, but I can't understand why this is a constant and what is the point of using it if it doesn't directly compute the multiplication?

Thank you

The “true” lambda calculus is defined by a syntax of terms:
$$
M,N ::= x \;\mid\; \lambda x.M \;\mid\; M\,N
$$
and a reduction rule called beta reduction:
$$
(\lambda x.M)\,N \to M[x \leftarrow N] \tag{$\beta$}
$$
(Plus context rules, plus the rules for alpha equivalence, but I'll omit them in this post.)

A lambda term is an object defined by the syntax above. What makes lambda terms interesting is the way they can be evaluated using the reduction rules.

It's possible, and common, to define extensions of the lambda calculus: languages that have additional syntactic forms and reduction rules. One common, simple extension is to add constants to the syntax of terms, and to add reduction rules called delta rules that allow evaluating these constants.

For example, we can define a new calculus which is the lambda calculus plus elementary arithmetic (LCPEA). If $n$ is a non-negative integer, I'll write $(n)_a$ for a constant in the LCPEA, so the LCPEA has constants $(0)_a$, $(1)_a$, $(42)_a$, etc. Note that what's in the parentheses is an integer, not a string: the constant is the same constant regardless of how the integer is written, so $(0)_a$, $(3-3)_a$, $(1+3-2*2)_a$, etc. are all the same constant.

$$
M_a,N_a ::= x \;\mid\; \lambda x.M_a \;\mid\; M_a\,N_a
        \;\mid\; (n)_a \;\mid\; \mathord{+}_a \;\mid\; \mathord{-}_a \;\mid\; \mathord{*}_a
$$ $$ \begin{align}
(\lambda x.M_a)\,N_a &\to M_a[x \leftarrow N_a] \tag{$\beta$} \\
\mathord{+}_a (n)_a \, (n')_a &\to (n+n')_a \tag{$\delta_+$} \\
\mathord{-}_a (n)_a \, (n')_a &\to (n-n')_a \qquad \text{if \(n \ge n'\)} \tag{$\delta_-$} \\
\mathord{*}_a (n)_a \, (n')_a &\to (n*n')_a \tag{$\delta_*$} \\
\end{align} $$

The delta rules directly translate the arithmetic operators into the LCPEA. So the LCPEA effectively contains elementary arithmetic. Note that these delta rules are necessary if we want the new constants we introduced to do anything useful. It would have been possible to define a different set of delta rules that caused $+_a$ to have nothing to do with addition and so on, but it would have been confusing.

It turns out that it is possible to define pure lambda terms (i.e. terms in the true lambda calculus) that reduce in the same way as corresponding terms in the LCPEA. That is, we can define a lambda term $\langle n\rangle$ for every natural integer $n$, as well as lambda terms $\langle\mathord{+}\rangle$, $\langle\mathord{-}\rangle$ and $\langle\mathord{*}\rangle$ such that
$$ \begin{align}
\langle\mathord{+}\rangle \, \langle n\rangle \, \langle n'\rangle &\leftrightarrow_\beta^* \langle n+n'\rangle \\
\langle\mathord{-}\rangle \, \langle n\rangle \, \langle n'\rangle &\leftrightarrow_\beta^* (n-n')_a \qquad \text{if \(n \ge n'\)} \\
\langle\mathord{*}\rangle \, \langle n\rangle \, \langle n'\rangle &\leftrightarrow_\beta^* (n*n')_a \\
\end{align} $$
The Church numerals are a classical example of a set of such terms; there are others.

There are several reasons why we may want to define something like the LCPEA.

One is that it is closer to how machines behave; this is important when using the lambda calculus to model compilers, but not when doing theory of computation.
Another reason, applicable even when doing theory of computation, is that we often don't care exactly how the integers are encoded. So we might define things like $\langle 3\rangle$ and $\langle\mathord{+}\rangle$ as lambda terms, and then forget their precise definition and just remember some reduction rules for them. So they're still pure lambda terms, but we treat them as if they were part of an extended language.
In a typed lambda calculus, encoding everything as functions is problematic, because we'd like to say that something like $1$ is “inert”, not like a function, and to say that $1 \, 2$ (“1 applied to 2”) is not well-typed and does not reduce to anything. With the pure lambda calculus, $\langle 1\rangle \, \langle 2\rangle$ does beta-reduce to something, but not to something useful. When we extend the language with constants, we don't define any reduction rule that would reduce $(1)_a \, (2)_a$.
There are extensions of the language that cannot be encoded as lambda terms at all. If we're interested in studying these, we have to extend the language.


Difference between UCB1 and UCT In Bandit Based Monte-Carlo Planning by Levente Kocsis and Csaba Szepesvári (2006) they propose the UCT algorithm which is derived from the UCB1 algorithm.

UCB1 algorithm:
$$X_j + \sqrt{\frac{2\ln n}{n_j}}$$

where $X_j$ is the average reward for machine $j$, $n_j$ is number of times $j$ has been played and $n$ is the entire number of games played.

In comparison, UCT is
$$\frac{W_i}{n_i} + c \sqrt{\frac{\ln N_i}{n_i}}$$
where $\frac{W_i}{n_i}$ is  win:lose ratio (the same as $X_j$),
$c$ is temperature parameter, which is often set to $\sqrt{2}$ (so they just put it in front...)
and $\frac{N_i}{n_i}$  is number of total games played for parent Node / number of games played for the corresponding node, which is the same as $\frac{n}{n_j}$.

So what's new here?

As the authors state in the introduction to their paper, UCT is an application of UCB1 for a specific problem:

  The main idea in this paper it to apply a particular bandit algorithm, UCB1
  (UCB stands for Upper Confidence Bounds), for rollout-based Monte-Carlo planning. The new algorithm, called UCT (UCB applied to trees) described in Section
  2 is called UCT.

It's not the algorithm but the particular application which is new.


Possible results of two programs running on a symmetric multicore system This question is from Patterson and Hennessy's Computer Organization and Design.

  Consider the following portions of two different programs running at the same time on four processors in a symmetric multicore processor (SMP). Assume that when this code is run, both $x$ and $y$ are 0.

  Core 1: $x = 2$;

  Core 2: $y = 2$;

  Core 3: $x = x + 1$;

  Core 4: $z = x + y$;

  What are all the possible resulting values of $x$, $y$, and $z$? You will need to examine all possible interleaving of instructions.

The given answer is, for $(x, y, z)$: $(3, 2, 5), (3, 2, 4), (3, 2, 3), (3, 2, 2), (3, 2, 0), (2, 2, 4), (2, 2, 3), (2, 2, 2), (2, 2, 1), (2, 2, 0).$

I understand how $x$ is either 2 or 3 and why $y$ is forced to be 2, but I don't know how $z$ takes those values.

x has 4 possible values throughout the execution of the program, but only two after execution is finished. x could be x = 2, or x = 0 + 1, or x = 2 + 1, or x = 0. If x = 0 + 1 executes first, then x = 2 executes second and x will be 2, but if x = 2 executes first, then x will be 3. But z could either receive 0, 1, 2, or 3 for x. Y is only ever either 0 or 2, with 2 being the value at the end always. So you have z = 3 + 2, z = 2 + 2, z = 1 + 2, z = 0 + 2, z = 3 + 0, z = 2 + 0, z = 1 + 0, or z = 0 + 0.


Tried to derive the Z combinator and instead derived another I was working to derive the Z-Combinator by starting with the factorial function and ended up deriving a different fixed-point combinator. What did I derive? Did I make a subtle mistake?
Here are the steps I performed (in JavaScript)
1. Declare factorial function
let fact = n =>
    n < 2 ? 1 : n * fact(n - 1)

2. Convert to combinator (closed expression)
let fact = (self, n) =>
    n < 2 ? 1 : n * self(n - 1)

3. Thread self call
Based on signature fact(?, 7), passing fact as first argument seems reasonable fact(fact,7). So thread the parameter through the tail call:
let fact = (self, n) =>
    n < 2 ? 1 : n * self(self, n - 1)

Usage is now fact(fact,7) → 5040
4. Refactor to curried form
let fact = self =>
    n => n < 2 ? 1 : n * self(self)(n - 1)

5. Move self application to local declaration
let fact = self => {
    let f = n => self(self)(n)
    return n => n < 2 ? 1 : n * f(n - 1)
}

6. Convert let declaration to lambda expression
let fact = self =>
    (f =>
        n => n < 2 ? 1 : n * f(n - 1)
    )(
        n => self(self)(n)
    )

Usage is still fact(fact)(7) → 5040
7. Separate the factorial expression
let _fact = f => n =>
    n < 2 ? 1 : n * f(n - 1)

let fact = self =>
    (
        _fact
    )(
        n => self(self)(n)
    )

8. Move self-application from caller to body
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact = (() => {
    let innerFact = self =>
        (
            _fact
        )(
            n => self(self)(n)
        )
    return innerFact(innerFact)
})()

Usage is now fact(7) → 5040
9. Convert let declaration to lambda expression
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact = (() => {
    return (
        innerFact => innerFact(innerFact)
    )(
        self => (_fact)(n => self(self)(n))
    )
})()

10. Simplify expression
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact =
    (innerFact => innerFact(innerFact))
    (self => (_fact)(n => self(self)(n)))

Sanity check. Usage is still fact(7) → 5040
11. Rename variables
The usage of innerFact and self look suspiciously similar. Rename to the same variable to discover a pattern. Separate lexical scopes so safe to do:
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact =
    (u => u(u))
    (u => (_fact)(n => u(u)(n)))

12. Abstract _fact usage and rename fact
Rename fact to setup and abstract _fact in body by replacing with parameter f
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

let fact = setup(_fact)

No need for separate _fact declaration so inline:
let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

let fact = setup(
    f => n => n < 2 ? 1 : n * f(n - 1)
)

13. Rename setup
Rename it to what? What combinator is this? According to Wikipedia The Z combinator is:
let Z = f =>
    (u => f(v => u(u)(v)))
    (u => f(v => u(u)(v)))

But what I've derived is:
let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

Defining fact in terms of either seems equivalent in behavior. Did I make a mistake? Did I accidentally rediscover another well-known combinator?

If I inline (u => (f)(n => u(u)(n))) into (u => u(u)) I get:
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))

Which is exactly the Z-Combinator.
From wikipedia:
let Z = f =>
    (u => f(v => u(u)(v)))
    (u => f(v => u(u)(v)))

My derivation:
let fix = f =>
    (u => f(n => u(u)(n)))
    (u => f(n => u(u)(n)))


Separating numbers with a minimal difference Given is a positive integer integer $n$, and integers $a_1,b_1,\dots,a_n,b_n$ with $ a_i\leq b_i$ for each $i$. What is the complexity of deciding whether there exist integers $c_1,\dots,c_n$ such that $a_i\leq c_i\leq b_i$ for all $i$ and $|c_i-c_j|\geq 2$ for all $i,j$?

What can be observed is that a greedy algorithm, wherein we assume that $a_1\leq\dots\leq a_n$ and choose $c_i$ according to this order, does not necessarily work. For example, we may have $a_1=1, b_1=4, a_2=b_2=2$. Putting $c_1=1$ does not work (it leaves no room for $c_2$), but what works is putting $c_1=4$ and $c_2=2$. Is the problem perhaps NP-hard?

As shown in the previous answer, this problem can be modeled as a scheduling problem with release and due dates. However, Schrage's heuristic works only for the case $p_j=1$ (all processing times are $1$) or when release and due dates agree (i.e. there is an order such that $r_1\leq\cdots\leq r_n$ and $d_1\leq\cdots\leq d_n$).

For the case $p_j=p$ polynomial algorithms have been found by Simons (1978), Carlier (1981), and Garey et al. (1981), running in time $O(n^2\log n)$, $O(n^2\log n)$, and $O(n\log n)$, respectively.

The algorithm of Garey et al. schedules unit-time tasks, but allows arbitrary release and due dates. The above problem can be reduced to this setting by dividing all dates and processing times by $p$. The main idea of the algorithm is to find a set of forbidden regions where no task is allowed to start. They show that Schrage's heuristic when respecting forbidden regions finds a feasible schedule of minimal makespan. When constructing the forbidden regions their algorithm may also detect infeasibility.

To see how the algorithm works, first look at a simpler problem: schedule $n$ unit-time tasks between a release date $r$ and a deadline $d$ respecting forbidden regions $F=\bigcup_i (a_i,b_i)$, where each region $(a_i,b_i)$ is  an open interval. (Note here we're not concerned with release and due dates of individual tasks.)

This problem can be solved by Backscheduling: define a sentinel starting time $s_{n+1}=d$, and for $i=n,n-1,\ldots,1$ set starting time $s_i$ to the latest time not later than $s_{i+1}-1$ that is not forbidden.

Write $B(r,d,n,F)$ for an application of Backscheduling for the above inputs, and define the return value as $s_1$, the latest possible starting date for scheduling the $n$ tasks. Now, if $B(r,d,n,F)<r$ there is no feasible schedule for the $n$ tasks. Further, if $r\leq B(r,d,n,F)<r+1$ no other task can start in $(B(r,d,n,F)-1,r)$ since otherwise there is again no feasible schedule for the $n$ tasks, and thus $(B(r,d,n,F)-1,r)$ can be declared a forbidden region.

It turns out that this logic is sufficient to find all forbidden regions that are required to make Schrage's heuristic work. Assume that tasks are ordered such that $r_1\leq r_2\leq\cdots\leq r_n$ and write $n(r,d)$ for the number of tasks which are released and due in the closed interval $[r,d]$.

set $F=\emptyset$
for tasks $i=n,n-1,\ldots,1$:
  $c=\min \{ B(r_i,d_j,n(r_i,d_j),F) \mid \forall j: d_j\geq d_i\}$
  if $c<r_i$: return "no feasible schedule"
  else if $r_i\leq c<r_i+1$: set $F=F\cup\{(c-1,r_i)\}$

A straightforward implementation as above would take time $O(n^4)$. Garey et al. show (besides correctness) that by updating the times obtained by Backscheduling, joining overlapping forbidden regions, and making "forbidden" queries $O(1)$ time can be brought down to $O(n^2)$, and by using even better datastructures to $O(n\log n)$.


What is the significance of negative weight edges in a graph? I was doing dynamic programming exercises and found the Floyd-Warshall algorithm. Apparently it finds all-pairs shortest paths for a graph which can have negative weight edges, but no negative cycles.

So, I wonder what's the real world significance of negative weight edges? A plain English explanation would be helpful.

Saeed Amiri has already given an excellent example in a comment: the weight on edges can represent anything in the real world, for example, the amount of money to be transferred from one account to another account. The amounts can be positive or negative. For example, if you want to go from $a$ to $b$ in your graph while losing as less money as possible (shortest path), then you can consider negative weights. For more, see this book chapter.
Apart from that, there are many more applications. The negative weights depend on what you model it to be. For example,
consider this graph

Chemistry: The weights can be used to represent the heat produced during a chemical reaction. (Nodes: compounds, Edge $e_{uv}$: if compound $v$ can be obtained ("chemically reduced") from $u$). In this graph: you produce $4$ kJ to convert $s$ to $a$ and $2$ kJ to convert $a$ to $t$. You need $5$ kJ to get back $s$ from $t$.

Real Life: Think of a driver, who gets paid to drive his employer from $s$ to $t$ but he pays between $a$ and $b$ (say traveling between his home and his workplace).

Games: Suppose you play rock-paper scissor for money. Nodes: rock, paper, scissors. Edges: any relation (clique). Weights: wager. In this graph: (forget about $b$), here, $s$ beats $a$, $a$ beats $t$ and $t$ beats $s$, and wins 4,2,-5 respectively.


How to find LCA in a directed acyclic graph? Firstly, I am trying to understand the meaning of LCA in DAG. I read a definition somewhere-"Define the height of a vertex v in a DAG to be the length of the longest path from root to v. Among the vertices that are ancestors of both v and w, the one with the greatest height is an LCA of v and w."

In a graph like this 1->3 1->4 2->3 2->4, 3 and 4 will have multiple LCA's because the height of 1 and 2 would be same.

So, How can I proceed to implement this? I am thinking of applying the same approach that we used to find LCA in a binary tree by starting from root node (In this case, nodes having in_degree=0) but due to cross edges between the nodes this approach wouldn't work.eg. 1->2 1->3 3->2.

So, Is there some better way to find the LCA in DAG's?

Assume that you want to find the ancestors of x and y in a graph.

Maintain an array of vectors- parents (storing parents of each node).

Firstly do a bfs(keep storing parents of each vertex) and find all the ancestors of x (find parents of x and using parents, find all the ancestors of x) and store them in a vector. Also, store the depth of each parent in the vector.
Find the ancestors of y using same method and store them in another vector. Now, you have two vectors storing the ancestors of x and y respectively along with their depth.
LCA would be common ancestor with greatest depth. Depth is defined as longest distance from root(vertex with in_degree=0). Now, we can sort the vectors in decreasing order of their depths and find out the LCA. Using this method, we can even find multiple LCA's (if there).


Reduction of A_LBA to E_LBA I have a rather interesting one to ponder and would love if I could get an answer for it. We were discussing the topic of mapping reduction today in my Computing theory course and I was wondering why this reduction can't exist, $A_{LBA} \leq_{m} E_{LBA}$, since both of them are linear bound automata (LBAs). I do realize that $E_{LBA}$ is undecidable, $A_{LBA}$ is decidable, and the normal proof uses $A_{TM}$, or $E_{TM}$, to prove the undecidibility of $E_{LBA}$. I am just curious why the proof is using a TM to prove an LBA. But, my Professor could not come up with a solution to my confusion. I was wondering is this possible, if so, why or why not.

Definitions:

$A_{LBA} = \{\langle M, w\rangle \mid \text{$M$ is a linear bound automaton that accepts the string $w$}\}$

$E_{LBA} = \{\langle M \rangle \mid \text{$M$ is a linear bound automaton with $L(M)=\emptyset$}\}$

$A_{TM}$ and $E_{TM}$ are the equivalent problems for Turing Machines.

You have your mapping the wrong way around. As it stands, it would be a reduction from a decidable problem to an undecidable problem. It's certainly possible (see below), but it doesn't tell us anything.

Recall that if $A \leq_{m} B$, then an algorithm solving $B$ (or deciding membership in this case) can be used to solve $A$ (decide membership in $A$). So the reduction you're looking at would tell us that any decider for $E_{LBA}$ could be used to decide $A_{LBA}$. We happen to also know that $E_{LBA}$ is undecidable, but this doesn't prevent there being some decider for $A_{LBA}$ that doesn't decide $E_{LBA}$.

In fact, the reduction that can't exist is $E_{LBA} \leq_{m} A_{LBA}$, as this would imply that we could decide $E_{LBA}$, which we know we can't.

For the second part, the proof (or rather, one of the possible proofs) that $E_{LBA}$ is undecidable is via constructing the mapping $A_{TM} \leq_{m} E_{LBA}$, so again a decider for $E_{LBA}$ would give us a decider for $A_{TM}$, but we already know that $A_{TM}$ is undecidable so $E_{LBA}$ must also be undecidable.

As to why the proof uses a language that involves Turing Machines to show something about linear bound automata, it's because it works.

A Reduction

As $A_{LBA}$ is decidable, we can take the input LBA $M$ and string $w$, and run the decider on $\langle M, w\rangle$. If it accepts, we map this to an LBA $M_{rej}$ that immediately rejects. If the decider rejects, we map it to an LBA $M_{acc}$ that immediately accepts. Thus $M_{acc}$ accepts all input and is not in $E_{LBA}$, and $M_{rej}$ rejects all input and is in $E_{LBA}$.

Note of course that this reduction is in a sense trivial, and the subset of $E_{LBA}$ it maps to is finite and therefore decidable (even regular!).

Another Perspective

Given two languages $A$ and $B$ such that $A \leq_{m} B$, there's two basic (useful) things we might be able to say:

If $B$ is decidable then $A$ is also decidable.
If $A$ is undecidable then $B$ is also undecidable.

In our case $A$ is decidable, and $B$ is undecidable, which matches neither of these possibilities, so the reduction $A_{LBA}\leq_{m}E_{LBA}$ doesn't tell us anything about the decidability of either.


Is this a new sorting algorithm? I just came up with a simple sorting algorithm that is faster than ShellSort when the range of values is smaller than the number of elements.
Is this new?  And if so, what should I do with it?

https://github.com/Frazer/hashSort

let hashSortNonUnique = (unsortedArray)=>{
  let myHash = {}
  let min = Infinity;
  let max = -Infinity;

  unsortedArray.forEach(val=>{
    myHash[val]=myHash[val]?myHash[val]+1:1;
    if(val>max) max = val;
    if(val<min) min = val;
  });

  let count = 0;

  for (let sorter = min; sorter <= max; sorter++) {
    let num = myHash[sorter];
    while(num--){
      unsortedArray[count]=sorter;
      count++;
    }
  }
  return unsortedArray;
}

let hashSortObjectsWithNonUniqueVals = (unsortedArray,valFunction)=>{
  let myHash = {}
  let min = Infinity;
  let max = -Infinity;

  unsortedArray.forEach(val=>{
    v= valFunction(val);
    myHash[v]=myHash[v]?myHash[v].push(val):[val];
    if(v>max) max = v;
    if(v<min) min = v;
  });

  let count = 0;

  for (let sorter = min; sorter <= max; sorter++) {
    let vals = myHash[sorter];
    for (let index = 0; index < vals.length; index++) {
      unsortedArray[count]= vals[index];
      count++;
    }
  }
  return unsortedArray;
}

The first is a counting sort with the change that you use a hashtable instead of an array to hold the mapping between element value and the number of elements of that value.

The second is a near textbook Bucket Sort with the change that you don't sort the bucket.


LL(1) parsing table of left-recursive grammar I have been taking a compiler course of Stanford on coursera. I have a slight misunderstanding on the parsing table of the following grammar:

S -> Sa | b

According to the professor parsing table looks like this:

If the leftmost nonterminal is S and the input is 'a', the production is nothing.
If the leftmost nonterminal is S and the input is 'b', the production is both Sa and b.

So if input is just b, then it is correct, it will go directly to production b.
But how will it go to production Sa for input b?

It appears you have misunderstood your professor. "If the leftmost nonterminal is S and the input is 'b', the production is both Sa and b." means that both Sa and b are correct answers if the leftmost nonterminal is S and the input is 'b'. This means that the parser does not know which production to go to and is stuck.

This means that this grammar cannot be parsed using this type of parser technology. You would either have to change the grammar or use a different type of parser.


Finding strings that are matched by a given regular expression I'm trying to be ahead of the game by studying some Theory of Computation concepts before class starts at the end of this month.  There's this question I came across that I don't understand below.

Let L be the language defined by the regular expression:
(c U ab U b)*bb(c U ab)

(U = union)

A.  Write 10 distinct strings that belong to L.
    If such strings don't exist, explain why.

B.  Write 10 distinct strings over alphabet {a,b,c} that don't belong to L.
    If such strings don't exist, explain why.

I'm totally lost, I have the answer but I just don't get how to go about it.

The only answers that I've came up with, that belong to L, was:

bbc, bbab

Which's only 2 correct out of the 10 listed in the answer key.  I just can't see how to come about the rest of them.

Thanks for taking the time to read.

Let's break down the regular expression $(c \cup ab \cup b)^*bb(c \cup ab)$. It has three parts $(c \cup ab \cup b)^*$, $bb$, and $(c \cup ab)$. The first part means "zero or more repetitions of $(c \cup ab \cup b)$", the second part matches two $b$, and the third part matches $c$ or $ab$.

As you already mentioned in your question bbc and bbab are strings that are matched. In both we choose zero repetition of the first part then the obligatory bb and then c, respectively ab, to match the third part. To make this easier to see I'll separate the parts of the string that are matched by the different parts of the expression with a - like so: -bb-c and -bb-ab.

We can generate more strings by choosing more than zero repetitions of the first part. For example we can choose one repetition of c to get c-bb-c. c-bb-ab would also be ok. We could also choose more repetitions of c or a c followed by ab for the first part. So cc-bb-c and cab-bb-c would also be acceptable strings.


Selection algorithm variant for an array Have a problem that's a variant of the linear time selection algorithm of a randomized array that I'm struggling with.

Let $A = A[1], ..., A[n]$ be an array of $n \ge 4$ distinct keys.
Describe an efficient algorithm to find the three smallest keys in $A$. Use words.
What is the worst case number of comparisons performed by your algorithm? Try to find an exact number. Ignore floors and ceilings. Explain your answer.

I would assume you use the randomized $k$-selection algorithm where $k=3$, but if you're recursively partitioning a group of integers around a pivot I'm not sure how you'd find $k=2$ and $k=1$ short of running the algorithm 3 times.
Ideas?

Well, here's what I came up with.

You could use Merge Sort, which has a worse-case time complexity of $O(n (log (n))$, then take the first 3 values of the array, but it felt like this question was seeking the use of the Randomized Select algorithm.

Best case for Randomized Select would be select $3$ (or $1$) as your random pivot and then make a comparison to the left or right of that for the other two spots, giving you a complexity of $n-1+1$ or $\Omega(n)$.

But this is asking for worst case. By my calculation if an adversary is always picking the furthest pivot from the target (say $k=3$), then the time complexity would be:
$$\frac{n(n-1)}{2} $$
For example. Let's say you have an unsorted array of $7,5,9,8$. The third smallest number is $8$ so the worst pivot is $5$. Compare $7,8,9$ (which is $n-1$ comparisons), you see there are 3 numbers greater.

The next worst pivot is either $7$ or $9$, so pick one of those, and $n-2$ comparisons, you see $8$ and $9$ are greater than 7. You know that $5$ is the smallest, $7$ is the second smallest, but you still need the third smallest. Repeat.

Pick $9$ as your pivot and make $n-3$ comparisons to see that $9$ is the 4th smallest, meaning $8$ is your 3rd smallest.

Add up those comparisons and simplify, you get the formula quoted above. Worst-case this seems less efficient than Merge Sort and selecting the first three numbers, but this seemed like the application of Randomized Select that the question was leaning toward (based on the book and classroom work).

Hope this helps someone else.


Languages that satisfy the pumping lemma but aren't regular? Given a regular language $L$, then it is easy to prove that there is a constant $N$ such that is $\sigma \in L$, with $\lvert \sigma \rvert \ge N$ there exist strings $\alpha$, $\beta$ and $\gamma$ such that $\lvert \alpha \beta \rvert \le N$ and $\lvert \beta \rvert \ne \epsilon$, and for all $k$ it is $\alpha \beta^k \gamma \in L$. It is widely stated that the converse isn't true, but I haven't seen any clear example. Any suggestions? Clearly the proof that the offending language isn't regular has to use stronger methods than the typical "doesn't satisfy the pumping lemma". I'd be interested in simple examples, to present in introductory formal languages classes.

The language $\{ \$ a^nb^n \mid n \ge 1 \} \cup \{ \$^kw \mid k\neq 1, w\in \{a,b\}^* \}$ seems to be simple. The second part is regular (and can be pumped). The first part is nonregular, but can be pumped "into" the second part by choosing $\$$ to pump.

(added) Of course, this can be generalized to $\$L \cup \{ \$^k \mid k\neq 1 \} \cdot \{a,b\}^*$ for any $L\subseteq \{a,b\}^*$. Sometimes the formulation is in the "if ... then ..." style: if $w$ starts with a single $\$$ then it is of the form. That I personally find less intuitive.

As noted by @vonbrand the (possibly) non-regular part of the language is isolated by intersecting with $\$\{a,b\}^*$. This can be separately tested using the pumping lemma if needed.


Semidecidability and NP-Hard Im studying the semidecidability of First Order logic.

According to wiki

  A logical system is semidecidable if there is an effective method for
  generating theorems (and only theorems) such that every theorem will
  eventually be generated. This is different from decidability because
  in a semidecidable system there may be no effective procedure for
  checking that a formula is not a theorem

The semidecidability seems to me exactly equal to halting problem, which is NP-HARD.
1) Is it correct ?
2) So also First Order Logic is NP-HARD ?

A language $L$ is semidecidable if there is a Turing machine that on input $x$, halts if $x \in L$, and doesn't halt if $x \notin L$. It is decidable if there is a Turing machine that on input $x$, halts at an accepting state if $x \in L$, and halts at a rejecting state if $x \notin L$. It's not hard to check that every decidable language is also semidecidable.

A logical system is semidecidable (decidable) if the language of all theorems in the system is semidecidable (decidable).

Being semidecidable is an upper bound on the complexity of a language. Being NP-hard is a lower bound on the complexity of a language. If all you know about a language is that it is semidecidable, you cannot deduce that it is NP-hard, just as you cannot conclude that $x \geq 0$ from the inequality $x \leq 1$.

The halting problem is $\Sigma_1^0$-complete, which means that it is semidecidable (an upper bound), and moreover, every semidecidable language can be reduced to it using a computable reduction (a lower bound). To be equivalent to the halting problem, you need both an upper bound on your language and a lower bound on your language. The language of theorems in a logical system is guaranteed (by definition) to be semidecidable, but it could also be decidable, in which case it is definitely not equivalent to the halting problem.

Finally, you don't explain what you mean by First Order Logic, but assuming that it can express propositional tautologies, then the corresponding language of theorems is definitely NP-hard, by reduction from SAT. In fact, the language of true quantified Boolean formulas, known as TQBF, is known to be PSPACE-complete.


Distinct elements count of huge multiset I know that HyperLogLog can approximate the distinct elements count of a huge multiset but I was wondering if it was possible, using a method I saw mentioned on an IRC channel, to get an exact answer while still using significantly less space than a traditional approach.

Would the following work to compute the exact (not approximate) distinct elements count of a huge multiset?

The idea is to use a Bloom filter twice, first processing the data one way, and then in reverse and additionally using a map (whose size is much smaller than the huge multiset -- this property is provided by the Bloom filter).

1st pass
create an empty bloom filter
create an empty map
for each element from the multiset
    if already in the bloom add to the map with key element / value 0
    else add to the bloom

Second pass is nearly identical but elements from the huge multiset are processed in reverse (multiset doesn't need to be an ordered set: it simply needs to have its elements iterated from the end to its beginning).

2nd pass
    empty the bloom filter (but not the set)
    for each element from the multiset (but processed this time in reverse order)
        if already in the bloom add to the map with key element / value 0
        else add to the bloom

At this point the map contains a list of potentially, but not necessarily, clashing entries in the multiset. So the entries are all set to zero.

3rd pass
   cnt = 0
   for each element in the multiset
       if present in the map, increment value in that map for that key
       else increment cnt

Exact cardinality is now equal to "cnt + nb entries in the map whose value is 1 or greater".

This requires three passes but uses space identical to a Bloom filter plus a map to count the x% of entries the Bloom filter couldn't answer if they were present or not.

I hacked a quick proof of concept and did some generative testing and it seemed to give the correct answer but I'm really not sure.

Is it possible to compute the exact distinct element count of a huge multiset this way?

Let me simplify your third step: count the number of elements in your multiset which are not in the map, and add to it the number of elements in the map.

Suppose that your elements are $x_1,\ldots,x_n$. For a given hash $h$, let $x_{i_1},\ldots,x_{i_\ell}$ be the elements hashing to $h$ (in order). If $\ell = 1$, then the elements won't be added to the map in the first or second step. Otherwise, elements $x_{i_2},\ldots,x_{i_\ell}$ will be added to the map in the first step, and elements $x_{i_{\ell-1}},\ldots,x_{i_1}$ will be added to the map in the second step.

In total, this shows that after the first two steps, the map will contain all elements whose hash appears more than once.

After the third step, cnt will contain the number of elements whose hash appears exactly once. All of these elements are distinct, and also distinct from the elements in the map. You then add to cnt the number of elements present in the map, and so obtain the number of distinct elements.


How to minimize this DFA with already merged states? The original nondeterministic FSA I have is:

After converting this to a DFA I get:

If I use the Myhill-Nerode theorem on the current DFA, I get all pairs marked, so this is already minimized. But I think this is incorrect.

I want to minimize this DFA. How should I do this using the Myhill-Nerode theorem, since some of the states are merged already?

After inputs $\epsilon$, $a$, $ab$, $abc$, $abca$ we must be in five different states because appending $b$ to one of these leads to an accept only for $abca$, appending nothing to any of the others leads to an accept only for $abc$, appending $c$ leads to an accept only for $ab$, appending $bc$ to any of the remaining only for $a$.

A bit more formally, given a string $\alpha$, we note in a 4-tuple whether $\alpha$, $\alpha b$, $\alpha c$, $\alpha bc$ are accepted. For $\alpha = \epsilon, a,ab,abc,abca$, these 4-tuples are $(0,0,0,0)$, $(0,0,0,1)$, $(0,0,1,0)$, $(1,0,0,0)$, $(1,0,0,1)$, hence all distintc. This is only possible if these $\alpha$ correspond to differnt states.


Why do we need epsilon-transitions in Thompson's construction? So as learned every DFA is an NFA. I feel like I understand DFA much better than NFA, so I try to convert my regular expressions to DFA, but I want to understand both sides.

For example a|b (a Union b):

However, are we losing anything if we eliminate the epsilon from these expressions, every DFA is an NFA right so what are we losing if we don't include it?

What you're looking at there is what's known as Thompson's construction. The idea is that any node in the regular expression parse tree corresponds to an NFA with a single entry and exit point. To see why the epsilon transitions are useful, try applying the construction to, say, $(a \cup b^*)c$.

Thompson's construction is particularly easy to understand and implement but it is also, as you rightly say, a bit wasteful. It is possible to construct Thompson's automaton with the epsilon transitions removed using Glushkov's method. You may also be interested in Xing's construction.


What happens if I replace $<$ with $\le$ in Dijkstra's algorithm? The following is Dijkstra's algorithm for finding the shortest path in a graph. I know something wrong happens if I replace d[u] + weight(u,v) < d[v] with d[u] + weight(u,v) <= d[v]. What would be an example of the algorithm working incorrectly with that replacement?

def dijkstraShortestPath(G,s,t):
  d[v] = Infinity for all v in G.vertices
  d[s] = 0
  unsureVertices = G.vertices
  while len(unsureVertices) > 0:
    u = a vertex in unsureVertices so that d[u] is minimized
    if d[u] == Infinity:
      break
    for v in u.getOutNeighbors(): //all v are in unsureVertices
       if d[u] + weight(u,v) < d[v]:
         d[v] = d[u] + weight(u,v)
         v.parent = u
    unsureVertices.remove(u)
  if d[t] == Infinity:
    return "Can't reach t from s!"
  path = []
  current = t
  while current!= s:
  path.append(current)
  current = current.parent
  path.append(current)
  path.reverse()
  return path

I would argue that this does not matter. Consider the case where there are multiple shortest paths from $s$ to $t$ in $G$. In the case of using $<$, we define the shortest path to be the first shortest path we come across. This is because latter paths will only be equivalent in length and thus not satisfy the invariant. However, in the case of using $\leq$ we define the shortest path to be the last shortest path we come across. This is because latter paths will be equivalent in length and thus trigger the invariant.

My point is that with $<$ or $\leq$ we could essentially flip the ordering of nodes in the adjacency list of adjacency matrix to mimic what the other comparison operator would do.


Benefit of Petri Net Transition as Separate Object In learning about Timed Automata, Coloured Petri Nets, and Process Calculi, I am wondering what the benefit is of having the Petri Net transition be a separate type of node in Petri Nets.

It seems that you can model the same stuff (eventually) using Timed Automata or Process Calculi, which both only have states and transitions (as edges, not objects). Instead of transition nodes, you could just have two types of "state", one be the Petri net place, the other be the Petri net transition. Then this second node does all it's queuing/guarding/checking of the tokens and whatnot. So I'm not sure the benefit is of having transition be a separate object in Petri Nets, when it could just be a second kind of "place" or "state".

That makes me wonder if there is a generalization of Petri nets to arbitrary number of node types (where instead of just place/transition, you have x, y, z, ...). In this sense it seems that process calculi are a generalization of Petri Nets.

The state transition graph underlying a Petri Net model is called the Reachability Graph. Yes, it exists, and it is the foundation of Petri Net semantics. However, it is possible to define simple, easily understandable Petri Net models that have reachability graphs of a size and structure that no human could make sense of. They might also be graphs with an infinite number of states.

It's similar to programming languages: every conceivable algorithm or program could be written in assembly language. But there are dozens, if not hundreds, of higher level programming languages that make it easier, simpler, and faster for humans to write and understand programs, to express the algorithms and the processing they need to implement. And then a compiler or interpreter turns the high-level program into a stream of processor instructions.

Petri Nets are meant as a way for humans to create meaningful, understandable models, without drilling down to individual states and transitions. Then Petri Net tools handle the simulation and/or analysis of the models.


Clarification on the inapproximability of set cover I'm trying to understand the inapproximability of the minimum set cover problem.

The wikipedia page states that it is hard to approximate within a factor of $(1-o(1))\ln n$ and that $n$ refers to the size of the ground set. It references the work of Dinur and Steurer (2013) who state that, for every $\varepsilon>0$, it is NP-hard to approximate min set cover within a factor of $(1-\varepsilon)\ln n$ where $n$ refers to the size of the instance. It seems they don't define what they mean by "size of the instance," but I take that to mean an encoding of the instance (which takes more space than just the size of the ground set).

Would I be correct in saying that set cover is hard to approximate within a factor of $(1-\varepsilon)\ln N$, where $N$ is the size of the ground set plus the sizes of all the subsets? Or, if $N$ is the size of the ground set plus the number of subsets?

The hardness proof appears in an earlier paper of Moshkovitz, The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover; Dinur and Steurer proved a version of the Projection Games Conjecture, thus completing the NP-hardness proof. Moshkovitz clearly states that $n$ is the size of the universe, and she also assumes that the number of sets is polynomial in $n$.

Feige had proved earlier that if you can approximate set cover better than $\ln n$ then $\mathsf{NP}\subseteq \mathsf{DTIME}(N^{\log\log N})$. He improved on earlier result of Lund and Yannakakis which showed a hardness of $0.72\ln n$ under the same assumption.

The threshold $\ln n$ (where $n$ is the size of the universe) is important since it is achieved by the greedy algorithm. The analysis of the greedy algorithm shows that after $OPT \cdot t$ steps (where $OPT$ is the size of an optimal solution), we have covered a $1-e^{-t}$ fraction of the universe. When $e^{-t} < 1/n$, we have covered the entire universe (since we cover more than $n-1$ elements). Hence after at most $t = OPT \cdot \ln n$ steps, the greedy algorithm manages to cover the entire universe. This is where the dependence on the size of the universe comes from.


m-functions in Turing's paper "On Computable Numbers and applications..." I was reading Alan Turing's paper "On Computable Numbers with an Application to the Entscheidungsproblem".

I was reading well until I encountered "4. Abbreviated Tables", page 235-236, where Turing uses a new way of writing a computation table for a machine. I am totally lost here. I don not understand the examples he gives (starting from page 236) to explain the idea of skeleton tables.

I need help with understanding how skeleton tables are to be read, and what they mean.

m-functions are quite similar to what we call today "macros". $f(\dots)$ is just the name of a supplementary m-configuration, that can be parameterized (like a macro). The trick is to not overthink it.


Machine error in computer arithmetic I'm wondering if if is possible to have a function $f$ such that there exists $x,y$ such that we have $f_t(x) > f_t(y)$ where $f_t$ denotes the true value of $f$ and $f_a(x)<f_a(y)$ where $f_a$ denotes the value of f as stored in a computer? (I am referring to floating point numbers and numerical analysis)

I am looking at programs that solve equations and so am concerned about if my programs will work in extreme cases. Things like if I have a function that is extremely close to $0$ in an absolute sense over the interval and I want to find the root. (In this case I think I can make an argument that if $f_t(x) \geq 0$, then we must have that $f_a(x) \geq 0$.) But if I'm looking for a maximum of a function that is almost constant, say $g$,  then I don't think I know that $g_t(x) > g_t(y)$ implies that $g_a(x) > g_a(y)$. Is this correct?

Any other resources on this matter would be greatly appreciated.

Yes! Various languages and APIs often specify the precision you are guaranteed.  If the underlying hardware doesn't offer that precision, they must emulate it with extra work.  For instance, some machine instructions that compute transcendental function (sin, cos, exp, log, ...) only offer a limited accuracy. Library implementations that guarantee a certain accuracy must execute extra instructions to accomplish that by correcting the error and improving the approximation.

As a concrete example, consider the native_sin function in OpenCL.  The error is "implementation defined." On the other hand, the regular sin function promises a certain accuracy and implementation of OpenCL must make that happen regardless of the extra work.


Dijkstra single-source shortest path $\Omega(n\log n)$? If I have a directed graph with $n$ weighted edges, is it possible to prove that Dijkstra's single-source shortest path algorithm takes $\Omega(n\log n)$ in the worst case?

I know heaps reduce Dijkstra's algorithm to $Ο(m \log n)$ and can be stored in an array.
Rooted, binary, as complete as possible tree with all nodes satisfy Heap property:
    node <= all children of node.. Is this the right direction?

**I have an implementation that runs $O( (n + m)\log n)$, could it work?

Let $m$ be the number of vertices and $n$ the number of edges. The best you can get is $O(n + m \log m)$ by using a Fibonacci heap.

A Fibonacci heap allows decreasing the key of an element in amortized constant time. For each edge in the graph, Dijkstra's algorithm executes at most one decrease key operation. All these operations take time $O(n)$ in total. On top of that we have $m$ minimum extractions, which take time $O(m \log m)$ in total. Therefore the final complexity is $O(n + m \log m)$.


Why are the control statements[if-else, while, for] commonly used in programming? One simple question I've never been able to answer is, "why use 'for', 'while', and 'if' as control statements?"

Could someone please elucidate the rationale behind using the above mentioned control statements, that have been embraced by most, if not all, high-level languages. I believe this has something to do with automata theory, but I'm generally uncertain.

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

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

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

if condition then cTrue else cFalse

is equivalent to

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

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

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

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

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


Does this "set intersection" problem have a different name? I've been back and forth about this one. I have the following theoretical homework problem, which describes the SET-INTERSECTION problem. In my homework, it's presented as being NP-complete.

Does this problem have a more common name in general Computer Science nomenclature? I'm trying to wrap my head around the definition itself -- and I can't find any resources that refer to the "set intersection problem" with similar parameters to this except in this pdf. It seems similar to the unit intersection problem described in a math stackexchange post. I also (naively?) think that it might be the set cover problem.

My actual intent is to understand what the problem describes -- so I'm looking for alternate names and resources that lead in the right direction. I'm not asking for any specific help in proving properties of it -- just understanding what it describes.

To the best of my knowledge, there is no other name for this.


Face recognition on on tilted images From what I learned, viola jones needs images with faces upfront. Tilting the head a few degrees to each side can botch the algorithm. Is it possible to take an image, take a several rotated copies of it and run the algorithm on each one?

This limitation sounds like only a minor neusense to me. Is there a stronger reason for the limitation?

Tilting your head a few degrees to the side doesn't cause Viola-Jones face detectors to fail.  They are more robust than that.  I suggest trying some experiments to see for yourself.

As an aside: It's not always possible to rotate an image to the extent one might like.  You have a 2D representation of a 3D object.  As an extreme case, imagine trying to take a photograph and simulate rotating the face by 180 degrees around the vertical axis.  You can't, because that would require knowing what the back of their head looks like.  Even tilting around a horizontal axis has limits; imagine trying to tilt by 180 degrees -- which would require simulating the effect of your hair pointing in a different direction.  So while it may be possible to simulate rotation to a limited extent, but there are limits to what kind of synthetic rotation is possible.


Trouble understanding theory for error detection and correction in repetition code Question 1

Consider a repetition code to detect $m$ errors. What is the smallest repetition parameter $k$ (i.e., the number of repetitions per bit) it should be used so that the code can always detect $m$ errors?

To be clear I know that you need $k=2m+1$ to correct errors, I am asking what is $k$ if you only want to detect errors.
I know the answer is $m+1$.

I read some articles about Hamming codes but I didn't understand the explanation.
I also read this post but it wasn't helpful enough:
Hamming distance required for error detection and correction

Question 2

Let a code make 3 repetitions and add a parity bit to the message. For example, $1010$ is encoded as $111 \; 000 \; 111 \; 000 \; 0$.
How many (maximum) errors can this code identify?
How many can it fix?

(The answer is fix one and identify three but I don't understand why.)

Question 1: Suppose $k$ is fixed. Then, if any group of repeated $k$ bits is flipped, the error is not detected, so we need $k \ge m + 1$. On the other hand, if $k = m + 1$, then any combination of $m$ errors will be detected because at least $k$ bits must be flipped (i.e, the whole group of $k$ repetitions) in order to arrive at a valid code word.
Question 2: The reasoning is similar. One bit errors can be fixed because of the parity bit. Two bit errors cannot because flipping the parity bit and any other repetition bit yields a word $w'$ with Hamming distance $2$ from the original code word $w$; from it, flipping the other two repetition bits yields a valid code word $w''$ which also has Hamming distance $2$ to $w'$, so the error cannot be corrected. The argument for identifying up to three errors is similar: at least four bits must be flipped to arrive at $w''$ from $w$ (as before), and anything less than that will not yield a valid code word.


If a problem is not in NP, prove that every NP problem can be efficiently reduced to it I understand that an NP-hard problem is a problem X such that any problem in NP can be reduced to X in polynomial time.

Does there exist a problem that is hard to solve but problems in NP cannot be reduced to it in polynomial time i.e. it does not satisfy the definition of NP-hard but is strictly not in NP? If not, what is the proof that if I can efficiently solve a problem that is strictly not in NP, then I can efficiently solve every problem in NP?

I suppose an analogous question can also be asked for P and NP. If a problem is in NP, then can every problem in P be reduced in polynomial time to it?

Note: The linked question asks the converse problem - does there exist a problem outside NP that cannot be reduced to a problem in NP. Indeed there are, for example the "(Non-)equivalence of two regular expressions" problem. However, from my understanding, every problem in NP can be reduced to this problem in polynomial time. Please correct me if I have misunderstood.

I suppose an analogous question can also be asked for P and NP. If a problem is in NP, then can every problem in P be reduced in polynomial time to it?

No. There is a stupidly simple argument here: the empty language (i.e., a problem with no yes-instances) is in NP, but no problem in P can be reduced to it.

  Does there exist a problem that is hard to solve but problems in NP cannot be reduced to it in polynomial time i.e. it does not satisfy the definition of NP-hard but is strictly not in NP?

Yes (conditional on some complexity theory assumptions). Let's take some stupidly hard problem $L$. To keep this answer as simple as possible we will assume that $L$ is undecidable but this is not necessary; a language obtained by applying the Time Hierarchy Theorem to the Ackermann function would easily suffice. Assume that instances of $L$ can be padded, i.e., adding extra zeroes at the end does not change whether an instance is a yes- or no-instance. Starting with undecidable language $L'$, $L$ could be obtained by taking every string from $L'$ and appending a $1$ followed by an arbitrary amount of zeroes. Clearly $L$ is still undecidable.

Now consider the subset of $L$ containing only those strings whose length can be expressed as a tower of powers of two (i.e., $1, 2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \ldots$). We split this subset into three languages $L_0, L_1, L_2$, depending on the height of the tower of powers of two. $L_0$ contains those strings where the tower has a height which is a multiple of $3$, $L_1$ contains strings whose height is $1$ modulo $3$, $L_2$ those strings whose height is $2$ modulo $3$.

Neither $L_0, L_1$ or $L_2$ are in $NP$. If they were, we could decide $L$ by padding instances to make their length the appropriate tower of powers of two, and then solving them using the $NP$ algorithm. Obviously the padding can increase the length of the instance exponentially, but if $L$ is sufficiently hard (e.g., undecidable) this does not matter.

Now, to answer the original question, can every problem in $NP$ be reduced in polynomial time to $L_0, L_1$ and $L_2$ (all of which are outside $NP$)? If we take some problem instance of a problem in $NP$, then at least one of the reductions (to $L_0, L_1$ or $L_2$) will result in an exponentially smaller instance. This is because the reduction, being polynomial, cannot increase the size of the instance too much, so (due to the large gaps in instance sizes) must - for at least one of $L_0, L_1$ or $L_2$ - give a much smaller instance as output.

Intuitively, this sounds very unlikely. It would mean we could take an arbitrary problem in $NP$ and in polynomial time output an exponentially smaller instance (albeit of a much harder problem).

Formally, this would mean that $NP\subseteq P/poly$, a consequence which is regarded as unlikely since it would imply the collapse of the polynomial hierarchy.


what is glushkov NFA. What is the difference between Glushkov NFA and Thompson NFA? I saw this term "Glushkov NFA" at http://lambda-the-ultimate.org/node/2064 . Search engines are returning references to articles that use glushkov nfa, but nothing specific about the glushkov nfa itself.

What is Glushkov NFA? How different is it from the NFA created from Thompson Construction?

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

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

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


Is there a correspondence between the syntaxes and the type systems of programming languages? I was reading the first chapter of Robert Harper's Practical Foundations for Programming Languages in which it introduced abstract binding trees, aka abt. It seems pretty like typed lambda calculus.

There are ground sorts, which are similar to ground types in typed lambda calculus.
There are abstractions; they accept multiple arguments. They remind me of uncurried version of lambdas. It's a bit odd that abstractions at the syntax level aren't first-class, though.
Later at the end of the chapter in the book, symbols are introduced. They seem to correspond to data types. (Or do they?)
Indexed operators are $\Lambda$ bounded terms in the sense of system F.

The author of the book seemed to be aware of the similarities. The set of symbols is even written $\mathcal{U}$ in the book!

What I'm asking is, is there known to be a correspondence of abt's and type systems, or is it too good to be true? Are there more advanced systems of abt's that correspond to system Fω or dependent types?

The question is kind of too broad. Hopefully it can be accepted on this website.

You seem to have a misunderstanding of the purpose of abstract binding trees (ABTs).  They are a tool for describing syntax, much like abstract syntax trees (ASTs).  They simply allow you to describe syntax that includes binders in a way that generic tooling can be applied.  Capture-avoiding substitution, for example, works basically the same way for first-order logic as it does for the untyped lambda calculus, so it would be nice to implement it once and then "instantiate" it to these particular languages.  This is what ABTs accomplish.

Just like ASTs, ABTs have little to no semantics on their own, even when instantiated to a particular syntax.  An ABT describing the syntax for the untyped lambda calculus is doing just that, describing syntax.  Until you add the beta rule, it's not the lambda calculus.  Similarly, if I make an ABT for the the syntax of the simply typed lambda calculus, the ABT won't stop me from making ill-typed nonsense.  A type checker still needs to be implemented.  Indeed, the exact same ABT could be used for very different type systems or semantics.  For example, the difference between the linear lambda calculus and the typed lambda calculus is not a matter of syntax. Similarly, the difference between the call-by-value untyped lambda calculus and the call-by-name lambda calculus is entirely in when the beta rule can be applied, syntactically they are identical.


Efficient algorithm for graph canonization for directed acyclic graphs? I'm interesting in generating directed acyclic graphs (see here, for example). As part of this search, I'm curious if there are any efficient algorithms for determining a canonization of a directed acyclic graph. Or, are there any tricks that allow the canonization of a dag to be computed more efficiently than a general graph?

Determining the canonical form in general is GI-complete, but there are many specialized graphs for which it can be calculated in polynomial time.  I didn't have any luck determining whether acyclic digraphs were among those specialized types, however.

According to Wikipedia (which references lecture notes of Zemlyachenko, Korneenko and Tyshkevic), isomorphism of directed acyclic graphs is GI-complete. Therefore any polynomial time canonicalization algorithm for directed acyclic graphs would result in a polynomial time algorithm for graph isomorphism. Since no such algorithm is known, one concludes that no polynomial time canonicalization algorithm for directed acyclic graphs is known, and it is conjectured that none exists.


A question about proving Rice's Theorem by reducing it to the Halting Problem I've read the definition for Rice's Theorem, here's the one from Wikipedia:

  In computability theory, Rice's theorem states that all non-trivial,
  semantic properties of programs are undecidable.

The classical proof for proving Rice's Theorem is on Wikipedia, which is similar to other sources.

However, I have a problem with this proof, made clear (hopefully) in the paragraphs following.

This proof goes like this:

  if we had an oracle for deciding these properties of program behavior, we would be able to use it to solve the Halting Problem, but the Halting Problem is undecidable, so an oracle for deciding these properties cannot exist either.

However, as far as I know, the impossibility of the Halting Program only occurs if the program checking whether something halts or not is trying to prove the hypothetical does_it_halt(a, i) wrong by using self-referencing tricks. But, in this proof, the oracle that is trying to decide the property is not trying to do that. So, it should be able to do its job without solving the Halting Problem.

I had some hope at the beginning that this proof may be wrong, but since it is apparently the "classical" proof for proving Rice's Theorem, I must be missing something. What is it that I am missing ?

However, as far as I know, the impossibility of the Halting [Problem] only occurs if the program checking whether something halts or not is trying to prove the hypothetical does_it_halt(a, i) wrong by using self-referencing tricks. But, in this proof, the oracle that is trying to decide the property is not trying to do that. So, it should be able to do its job without solving the Halting Problem.

The proof shows that, if we had a machine $M$ to decide a nontrivial semantic property, we can craft another machine $N$ to solve the Halting problem.

With "$N$ solves the Halting problem" we mean that $N$ can decide the termination of absolutely any other Turing machine, including those using "self-referencing tricks" -- no exceptions.

In a nutshell, "for all" means "for all". If we show that a machine decides a problem, then it must always do its job on all inputs. The mentioned proof crafts a machine $N$ which does not "decide the Halting problem, except for self-referencing cases" (whatever that might actually mean in formal terms). $N$ is proved to work "for all" inputs.

By the way, it's a common misconception to think that we actually detect when a program is "self-referencing", and that we could work around the impossibility of deciding the halting problem by weakening the goal to "decide whether $T$ halts on input $x$, as long as there is no self-referencing". What actually happens is that there are infinitely many machines $U$ equivalent to $T$ we could use for the "self-referencing", and
(by Rice!) deciding whether $T$ and an arbitrary $U$ are equivalent or not is impossible. No algorithmic "syntactic inspection" on two programs can hope to decide whether they are equivalent on all cases.

Indeed, at first the self-referencing trick looks as a quite unsatisfactory negative proof, making one think that it could be worked around easily by just excluding that case. However, it is far more general than it looks at first.


Is there an algorithm for checking if a string is a catenation of palindromes? Is there a linear-time algorithm to check that a sequence of characters is a concatenation of palindromes? The only thing that comes to my mind is the naive solution:

1. k = 1
2. Split string into k substrings (all possibilities) and check
3. k++
4. repeat

Note: the answer is trivially yes if length 1-strings are defined to be palindromes. Let's assume that this is not the case.

Assuming you want disjoint palindromes, this is known as the PALSTAR problem, and there is a linear time algorithm by Zvi Galil and Joel Seiferas. A Linear-Time On-Line Recognition Algorithm for ``Palstar'.

You can find an explanation of the algorithm in the book here: Text Algorithms  (look at linked page and the preceding pages).

If you are ok with a quadratic time algorithm, straight-forward dynamic programming seems to work.

Given a string $s[1,\dots n]$, we maintain an array telling us whether $s[1,\dots j]$ can be decomposed into palindromes.

We also maintain an 2D table which tells us whether $s[i, \dots j]$ is a palindrome or not. This we can construct in $O(n^2)$ time by choosing a center and moving two pointers outwards, checking for palindromes with that center. Do this for each possible center: $\Theta(n)$ centers, each taking $O(n)$ time.

Now, you can check $s[1, \dots j+1]$ whether can be decomposed into palindromes, by checking for each $1 \le i \le j-1$ whether $s[1,\dots i]$ can be decomposed, and  if $s[i+1,\dots, j+1]$ is a palindrome (using the above 2D table). This yields a $\Theta(n^2)$ time and $\Theta(n^2)$ space algorithm.

The space usage can be brought down to $O(n)$, if you use Manacher's on-line algorithm to compute whether $s[i+1,\dots j+1]$ is a palindrome (as $i$ goes from $j-1$ to $1$), basically getting rid of the 2D table.


State-elimination on FSA, after epsilon-removal construction I want to define the language of this FSA with a regular expression. I have learned that by state-elimination, I would be able to find a regular expression.

But there are already some epsilon transitions in this FSA.

My question is:

Should I first follow the epsilon-removal construction, and then do state elimination?

Or can I use state-elimination directly on this FSA?

Should I first follow the epsilon-removal construction, and then do state elimination?
  Or can I use state-elimination directly on this FSA?

If you would like to do more work to kill time, or if you would like to check the effect of epsilon-removal construction, or if someone higher on the command chain forces you to (for reasons I have no informed guess about), you should do the epsilon-removal construction before state elimination.

Otherwise, it is perfectly fine to start state-elimination directly and immediately.

By the way, the regular express I got is
$$\left(0+(0+02)(2+42)^*(4+\epsilon)\right)^*(0+02)(42+2)^*\,.$$


In a flow network, is it possible to restrict the flow going into a node? For example, if a node has 2 edges going into it and two edges coming out of it all with capacity 1, is there a way to make it so that only 1 unit of flow can go through this node (without just deleting edges)?

I believe you can represent node N as two nodes, A and B. Node A has all of the inbound flow edges of N, and Node B has all of the outbound flow edges of N. Nodes A and B are connected by a single edge which you can use to throttle the flow. The edge from A to B is the only edge out of A and the only edge into B.