Is there a defined set of steps or principles on how to reduce time complexity of algorithms? I have been watching some big (Google, Facebook,..) company interview examples and usually when pair programming, they develop the most straightforward algorithm and then the interviewer asks 'could you make it faster (reduce time complexity)'.

I have worked on optimizations of algorithms too and things that immediately spring to head when I optimize is to take out as many nested loops as possible, look for sorted data, change data structures, etc.

Since algorithm optimization is a common thing I was wondering is there a defined set of steps or principles on how to approach the reduction of time complexity of algorithms? something akin to SOLID for Object-oriented programming, but for reducing time complexity.

Just something to remember: You said "could you make it faster (time complexity)". What counts in practice is the resources used for practical cases. Reducing the runtime by a factor ten may be extremely valuable, but doesn't reduce time complexity. It is in practice more valuable than reducing time complexity by a factor log log n.
Next thing to remember: In many cases "could you make it faster" has the valid response "Probably, but I wouldn't bother". Making it faster takes time in money. The first step is to figure out whether it's worth the effort. Especially in an interview.
One method that works very well is called "brute force and ignorance". It doesn't care about algorithms, but about making the identical code run faster. Removing all unneeded overhead. Check for cache usage and so on.
And the other method is finding better algorithms. O (n*n) can often be changed to O (n log n), which is massively better. And with really complicated algorithms, you may find some heuristics that improves it. For example, optimisation algorithms tend to work a lot better if you manage to start with a good solution that may be good enough to allow you showing that many other solutions cannot be optimal.
But general principles? No.


Counterexample that B-A can be NOT context free Given that A is a context free language and B is a regular language, B-A can be not context free as it is equal to B ∩ A', and context free languages are not closed under complement. Could you give me a counterexample?

Consider the languages

B = { a*b*c* } -- an obviously regular language.
A1 = { aibjc* | i > j }
A2 = { aibjc* | i < j }
A3 = { a*bicj | i > j }
A4 = { a*bicj | i < j }
A = A1 ∪ A2 ∪ A3 ∪ A4

The An langauges are all context-free, so their union is also context free, but the language B-A is the non-context free language { aibici }


Why is the number of states for DFA is 3n + 1 for this language I'm taking online compilers course. It's long ended, so it wouldn't be cheating to ask a question on quiz here.

Let $S_i$ be the string consisting of $i$ 0's followed by $2i$ 1's. Define the language
$L_n = \{ S_i | 1 \leq i \leq n \}$. For example,

$L_3 = \{\, 011,\, 001111,\, 000111111\; \}$

For any given $n$, what is the smallest number of states needed for a DFA that recognizes $L_n$?

I know regexes a bit and I can't think of a way of expressing this with regular expression. But I thought even if it's possible it should involve some kind of backreference, and isn't backtracking impossible with DFA?

So the quiz gives the correct answer $3n + 1$ and explain it like so.

  We need states to count how many 0 we meet and how many 1 we meet, so we need 3*n+1 states including the start state.

And this explanation doesn't explain anything to me. I mean okay the $+1$ part obvious, but why is there $3n$? I mean I agree that we probably need states to count how many 0 and 1 we meet, but exactly how we're gonna do it? If anything we should have 4 states in my opinion. One recognize 0, one to recognize 1 and another two states to count the numbers of them.

Right now I'm reading articles and papers about NFA, DFA, regular expressions and backreference, but maybe the answer is much simpler?

EDIT1.
Okay, I've tried my best and constructed kind of obvious DFA for this task.

The total number of states would be $\sum_{i=1}^{n}i+2i$ which looks like arithmetic progression to me with a difference $d=(i+1)+2(i+1)-(i-2i)=i+1+2i+2-i-2i=3$ So the sum will be equal to $\frac{n(a_1 + a_n)}{2}=\frac{n(3 + (n + 2n))}{2}=\frac{n(3+3n)}{2}=\frac{3(n^2+1)}{2}$

I don't see $3n + 1$ here.

Okay, I think I finally got this. The main problem I think was that I haven't tried to actually draw automaton initially and If I would it would be much easier. So once I've noticed that it could be changed into this

And this would give $3n+1$ obviously.

This is indeed a curious example. The reason why it works is the following (I show you on the example of $L_3$, but the argument is generic).
Start with the minimal DFA accepting $\{S_n\}$, which clearly has $|S_n| + 1 = 3n + 1$ states. The states can be encoded by factorisations of $S_n$ in two factors (the reason of this encoding will appear shortly). Thus for $S_3$ you get
$$
  (\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{0} (00, 0111111) \xrightarrow{0} (000, 111111) \xrightarrow{1} (0001, 11111) \xrightarrow{1} (00011, 1111) \xrightarrow{1} (000111, 111) \xrightarrow{1} (0001111, 11) \xrightarrow{1} (00011111, 1) \xrightarrow{1} (000111111, \varepsilon)
$$
Now it is possible to accept the words $S_i$ by adding new transitions (but no new state!). For instance, if you want to accept $011$, you add the transition $(0, 00111111) \xrightarrow{\color{red}{1}}(00011111, 1)$ to get
$$
  (\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{\color{red}{1}}(00011111, 1) \xrightarrow{1} (000111111, \varepsilon)
$$
and to accept $001111$, you add the transition $(00, 0111111) \xrightarrow{\color{red}{1}}(000111, 111)$ to get
$$
(\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{0} (00, 0111111) \xrightarrow{\color{red}{1}}(000111, 111) \xrightarrow{1} (0001111, 11) \xrightarrow{1} (00011111, 1) \xrightarrow{1} (000111111, \varepsilon)
$$
The trick is that you still get a deterministic automaton, due to the choice of the words added to the original automaton.


Construct a pushdown automaton for $\{a^{2n}b^{3n}|n\ge0\}$ My idea is to (not formal) push an 'a' when we see an a, nondeterministically guess when n a's were seen from the input word, go to the next state. From there, when we see an a, push 2 'a's into the stack and again guess when n a's were seen (now there should be 3n 'a's in the stack) and go to the final state, where if we see a b, we pop from the stack. So the stack will be empty in the last state iff we saw 3n b's.
The problem that with this line of thought we can construct an automaton for$\{a^{n}b^{n}c^n|n\ge0\}$. So where am i wrong in this thinking?

Your PDA accepts the language
$$ \{a^{i+j} b^{i+2j} : i,j \geq 0 \}, $$
which is different from the one you are interested in. In fact, you can show that it equals
$$ \{a^kb^\ell : k \leq \ell \leq 2k \}. $$


Does the following transformation preserve context-freeness? I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always context-free?
My guess is that it will preserve context-freeness. Can anyone provide an elementary proof of this?

Counter-example:

$L_1 = \{a^n b^n c^m \mid m,n \ge 1 \}$

$L_2 = \{a^m b^n c^n \mid m,n \ge 1 \}$

$L = (L_1 \cdot L_2^*) \cup \epsilon$ is context-free.

Any nonempty word $x \in L^\#$ has a prefix $p = a^n b^n c^m \in L_1$. It must be $n = m$, because due to $L_2$, any pair of a $b^+$ and a directly succeeding $c^+$ in $x$ (after $p$) must share the same exponent. Therefore:

$L^\# = (\{a^n b^n c^n \mid n \ge 1 \} \cdot L_2^*) \cup \epsilon$, which is not context-free.


Finding the longest overlapping interval pair Say I have a list of $n$ integral intervals $[a,b]$ where each represents a set $S = \{a, a+1, \ldots, b\}$. An overlap is defined as $|S_1 \cap S_2|$. Example: $[3,6]$ and $[5,9]$ overlap on $[5,6]$ so the length of that is 2. The task is to find two intervals with the longest overlap in $o(n^2)$ using just recursion and not dynamic programming.

Naive approach is obviously brute force, which does not hold with time complexity condition. I was also unsuccessful trying sweep line algo and/or Longest common subsequence algorithm.

I just cannot find a way of dividing it into subproblems. Any ideas would be appreciated.

Hint: Try divide-and-conquer.  I can only see about two plausible ways to do the "divide" step; try both of them, and one of them should work to yield a useful algorithm.


Word Frequency with Ordering in O(n) Complexity During an interview for a Java developer position, I was asked the following:

  Write a function that takes two params:

  a String representing a text document and
  an integer providing the number of items to return.

  Implement the function such that it returns a list of Strings ordered by word frequency, the most frequently occurring word first. Your solution should run in $O(n)$ time where $n$ is the number of characters in the document.

The following is what I answered (in pseudocode), it is not $O(n)$ but rather $O(n \log n)$ time because of the sort. I cannot figure out how to do it $O(n)$ time.

wordFrequencyMap = new HashMap<String, Integer>();
words = inputString.split(' ');

for (String word : words) {
  count = wordFrequencyMap.get(word);
  count = (count == null) ? 1 : ++count;
  wordFrequencyMap.put(word, count);
}

return wordFrequencyMap.sortByValue.keys

Does someone know or can someone give me some hints?

I suggest a variation of distribution counting:

Read the text and insert all the word encountered into a trie, maintaining in each node a count, how often the word represented by this node has occured. Additionally keep track of the highest word count say maxWordCound . -- $O(n)$
Initialize an array of size maxWordCount. Entry type are lists of strings. -- $O(n)$, since the count can't be higher.
Traverse the trie and for each node add the corresponding string to the array entry indicated by the count. -- $O(n)$, since the total length of strings is bounded by $n$.
Traverse the array in descending order and output the desired number of strings. -- $O(n)$, since that is a bound on both the size of and the amount of data in the array.

You can probably replace the trie by other data structures in the first phase.


Reduction from 3 SAT to Monotone Exact 1 in 3 SAT Can someone please help with a clear reduction from a 3SAT to a Monotone Exact 1 in 3 SAT. I tried searching by didn't find much.

Here are some ideas to get you started. You can find on the internet simple gadget reductions from 3SAT to 1-in-3SAT. In monotone 1-in-3SAT you are not allowed to use negations, but if you allow clauses of width 2, you can add clauses
$$ x_i^+ \lor x_i^- $$
for each variable $i$. This clause forces $x_i^- = \lnot x_i^+$, and so allows you to simulate negations. If you really insist that your clauses have width 3, you need to be slightly more devious. Try to figure out a way yourself, and only if you're unsuccessful, take a look at my solution below:

   For example, you can add three new variables $a,b,c$, replace $x_i^+ \lor x_i^-$ with the pair of clauses $ x_i^+ \lor x_i^- \lor a$, $x_i^+ \lor x_i^- \lor b$, and add the clause $ a \lor b \lor c$.


Is this set computable? Let be $B$ a Busy Beaver function and set $W=\{\langle M \rangle :\text{$M$ stops in less than $B(10^{1000})$ steps on an empty tape}\}$. Is this set computable?

I'm not sure how to approach this question. I suspect that this set is computable and have tried to see if it is finite, but haven't reached anything.

Your function is computable. Just run the input machine on the empty input for $B(10^{1000})$ steps. Note that $B(10^{1000})$ is just a constant which can be hardcoded into your code.


Counting tokens in compilers, lexical analyser Let's start with the question.  Say I have a C language statements follows

it 458cat 2.01 = 96.87abc a.2 ;

-my question is how many tokens are there in the above statements. Secondly does white space like tabs, newline, makes a token or not?
If you are interested in my solution then  proceed on your own risk. Firstly I think in lexical analyser there is no such thing as white space so after removal of that the above statement would look catastrophic so, I have not taking that approach.
Now we see 'it' as an identifier similarly, '458' as integer, 'cat' as identifier, (please not that I may have mistaken here which i don't know that is '458cat' may be invalid identifier so the lexical analyser may report an error, but I don't know will that happen or not. you may argue that what I have written is wrong because  if it was true then the identifier like '678hello' will be a valid identifier but since its not then iam wrong. But take a different approach like if all white space between '468   abc' being vanished (this is what lexical analyser does first) then it would like '468abc' . Initially in case of  468 abc we were taking 468 as integer and abc as valid identifier but after  white space removal things are changed so what I think is it will be reported in syntax analyser  but I don't know that am I right), similarly, '2.01' as real integers, '=' as operator, '96.87' as real number, 'abc' as identifier, 'a ' as identifier, .2 as real number and ' ; ' as special symbol.
I most certainly know that iam not right but if you could correct where I was  wrong it will be helpful

In C, 458cat is a single ppnumber token. It's not a valid number, so it will eventually produce an error message, but it is tokenised as a single token.

There's a longer explanation of this behaviour in this StackOverflow answer.


Algorithm to find sets of vertices connected to at most one incoming and one outgoing vertex outside the set I have a directed graph with vertices $V$, and I need to find a strict subset $U$ of its vertices such that:

$U$ contains at least two vertices, and $U \neq V$
There is at most one vertex in $V \setminus U$ connected to a vertex in $U$
There is at most one vertex in $U$ connected to a vertex in $V \setminus U$

(assuming there is such a subset).

The current algorithm I have works by recursively calling itself with one added vertex until the set has the appropriate conditions, but it's much too slow.

Is there any algorithm I could use to do this more efficiently?

Let's name the vertices $v \in V \setminus U$ and $u \in U$ the vertices that are allowed to have out-neighbors anywhere.

Suppose that we know the vertex $u$ and delete all its out-edges.

Now we are looking for a vertex $v$ that "separates" the graph in two components, $V \ni v$ and $U \ni u$.

We can find $u$ in $O(n)$ time by trying all possibilities.  We can also find the strongly connected components in $O(n + m)$ time.  In this graph, we must find $v$ with the above property.  That can be done in linear time $O(n + m)$.  Hence it all runs in $O(n(n+m))$ time, which is at most $O(n^3)$.


What's the difference between environment and memory in terms of programming languages? I've been reading up on programming languages to better my understanding with the textbook Essentials of Programming Languages (3e) - Friedman & Wand.

In a chapter regarding the states of languages (i.e. when we account for the effects that a computation may have rather than the immediately evaluated value), I've noticed that the terms environment and memory are used frequently, but I'm not sure how to grasp the difference.

  According to the text, "an environment associates a value with each element of a finite set of variables," and "memory is a finite map from locations to a set of values called stored values."

Does this mean that environments are a part of memory? The part that especially confuses me is when we "extend the environment."

To give a short example, if I had a procedure such that

let f = proc (x) (x + 1) in
  f (1)

then the text states that we "extend our environment" so variable f points to a location (say, l1) and argument x points to l2.

l1 in turn points to the procedure tuple (x, (x + 1), empty_env), and finally l2 points to the actual argument 1.

We update the location contents according to the procedure, which means we update l2 with 2, and the program finally returns 2.

Thank you.

Functions

The terms "associate" and "map" together with "finite" indicate that both definitions refer to finite mathematical functions.

A (mathematical) function is a relation that associates each element of a set, the domain of the function, to a single element of another set (possibly the same set), the codomain of the function [Wikipedia].

Another way to put this, for finite functions are: a finite set of ordered pairs.

Map is usually defined as a synonym to function.

Thus the definitions could be rewritten as follows:

Environment

An environment is a finite function that associates each element in the finite set of variables (domain), to a single element in the finite set of values (codomain). The range would be the set of all possible values (possibly infinite).

Memory

A memory is a finite function that associates each element in the finite set of locations (domain), to a single element in the finite set of stored values (codomain). The range would be the set of all possible values (possibly infinite).

Sets

  Does this mean that environments are a part of memory?

Since this is about sets, if you by part mean subset, then the answer would be no.

However, the codomains are definitely related, if a variable is associated with a value in the environment, a location must also be associated to a stored value in the memory, that corresponds to the variable value.

Extending the Environment

  The part that especially confuses me is when we "extend the environment."

It seems the aim of the text is to build an interpreter. You start out with no variables declared (including procedures), i.e., an empty environment and then you interpret/parse/analyze the code to make these associations, i.e., extending the environment.

In Practice

It might be helpful to think of the memory as the values stored somewhere in the physical memory and the environment as the values that the interpreted process currently knows about.


Intro to Algorithms: asymptotic function analysis I'm reading "Introduction to Algorithms" 3rd edition by Cormen, Leiserson, Rivest, Stein Page 46.  The authors place formal upper and lower bounds on a function which is quadratic.   Can anyone explain where the values for $c_1$, $c_2$ and $n_0$ are taken?  I'm also confused why the $max$ function is used and it's parameters.

The values of $c_1$ and $c_2$ are pulled out of thin air. Their actual values don't matter except for the property that $$0<c_1\leq a\leq c_2$$
The value of $n_0$ also doesn't matter except for the property that $$n>n_0\implies c_1n^2\leq an^2+bn+c\leq c_2n^2$$
This implication is equivalent to saying that the interval $n\geq n_0$ is inside the set of solutions of the system of inequalities $$\begin{cases}(a-c_1)n^2+bn+c&\geq0\\(c_2-a)n^2-bn-c&\geq0\end{cases}$$
So, they solved the system of inequalities
$$\begin{cases}\frac{3a}{4}n^2+bn+c&\geq0\\\frac{3a}{4}n^2-bn-c&\geq0\end{cases}$$
You can see now that the concrete values of $c_1$ and $c_2$ were chosen such that the two inequalities in the system are nearly the same, except for the sign of the coefficients. The two are quadratic polynomials with positive leading term. They are going to be non-negative outside the interval formed by their roots. So, for the interval $n>n_0$ to be inside, we just need to take $n_0$ to be a bound from above of the absolute value of the roots.
There are many known bounds of the roots in terms of the coefficients. It looks like they took this bound by Lagranges. Although $2\max\left(\frac{|b|}{a},\sqrt{\frac{|c|}{a}}\right)$ would be the bound for the roots of the polynomial $an^2+bn+c$ and we have instead $\frac{3}{4}an^2+bn+c$. The bound would be instead $2\max\left(\frac{4|b|}{3a},\sqrt{\frac{4|c|}{3a}}\right)$, which is somewhat larger.


$P/poly$ as oracle to itself? How can we show $P/poly^{P/poly}=P/poly$?

What tricks are generally used for self lowness of a class such as $BPP$, $SPP$ etc?

There are no general tricks for proving self lowness, note that the classes that you yourself mentioned are very different in nature. Recall that $L\in P/poly$ iff there exists a Turing machine $M(x,y)$, which runs in time polynomial in $|x|$, and an advice sequence $\{\alpha_n\}_{n\in\mathbb{N}}$, such that for all $x\in\Sigma^*$ it holds that:

$x\in L \iff M\left(x,\alpha_{|x|}\right)=1$

$L\in P/poly^{P/Poly}$ if the machine $M$ above can also query membership to some other language $O\in P/Poly$, so there exists a machine $M_O(x,y)$ which satisfies the above conditions with advice sequence $\beta_n$.

To show that $L$ lies in $P/Poly$, the natural approach would be to use $M$ with the same advice sequence $\alpha_n$. The problem arises when $M$ queries its oracle $O$ on some string $s$, what do we do then? Here the natural approach would be to simulate $M_O$ on $s$, but what advice should we feed to $M_O(s,\cdot)$ ? Suppose $M$ runs in time $n^c$, then on a length $n$ input, $M$ can only query its oracle on strings of length $\le n^c$. This leads to the following solution, on length $n$ inputs, your $P/Poly$ machine for $L$ would use the advice $\left(\alpha_n,\beta_0,\beta_1,...,\beta_{n^c}\right)$, and simulate $M$ on the input with advice $\alpha_n$. Whenever $M$ queries the oracle on a string $s$, simulate $M_O(s,\beta_{s})$ to obtain an answer, and continue executing $M$.


Why Don't We Use Non-ML Artificial Evolution? I remember reading about Tom Ray's Tierra and how amazing the results it obtained were. However as far as I know, the only "evolution" based computer technology we use now is ML, which is very limited in its abilities. Why haven't we used artificial evolution perhaps similar to Tierra for practical purposes? Is it too hard? Do we lack the technology to make it practical so far or have we decided we don't need to do it, even if we had the technology?

Because we don't know how to make it work well to solve practical problems we care about.

If your'e asking about evolutionary algorithms in general: As a rough rule of thumb, evolutionary algorithms haven't turned out to be all that wonderful.  As a starting heuristic, they're... usually OK.  But, practical experience is that other methods often seem to perform better.

If you're asking about Tierra specifically: Tierra was a demo applied to a very specific, artificial situation.  It doesn't seem to have generalized to allow us to solve many practical problems we care about.  Also, I'm not sure, but it looks like Tierra might have been intended more to try to understand evolution, more than to apply evolution to solving practical computing problems.


if I want only one element of the inverse matrix, does there exist a fast algorithm? I use Mathematica to solve problems. I have a question about matrix inverse.

if I want only one element of the inverse matrix, does there exist a faster algorithm than using Inverse to calculate the whole inverse matrix and extract the element which I want?

I have not seen exactly this in Mathematica but I think being able to solve an equation set for only one unknown may be supported.

The direct way would be of course to implement the inverse matrix algorithms and have them stop when the particular element is determined. It would probably be interesting to see what optimizations you can have for each algorithm if the goal is to get one element only.

But according to the first paragraph, one idea could be to express your matrix inverse as unknowns in equation system and then try solving only for the unknown you need (since solving equation set for a single unknown should be supported). If you get better memory and CPU performance then it may be safe to say that Mathematica did not actually solve the whole equation but just did its optimizations to determine only your unknown. You may get worse performance of course since you are not using inverse algorithms directly. If you decide to try let us know if it worked!


Why doesn't descriptive complexity theory solve P = NP? According to the Wikipedia page on Descriptive complexity theory:

  In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time.

  Existential second-order logic yields NP, as mentioned above.

If P = NP, wouldn't it be possible to convert any Existential second-order logic into a corresponding first-order logic with a least fixed point operator?  That would also imply a bijection between those sets (is there a bijection between existential second-order logic and first-order logic with a least fixed point operator?).

My understanding is first order logic cannot express second-order logic - why doesn't this prove P != NP?

Note the difference between second-order logic, and existential second order logic. Full logic is much more powerful than existential logic.

Also, it's important not to underestimate the power of a least-fixed point operator. Linearly-ordered first order logic is likely far less powerful than the version with fixed-points.

In short, we know that vanilla first-order logic is weaker than vanilla second-order logic, but we don't know that linearly-ordered first order logic with a least-fixed point operator is weaker than the existential fragment of second order logic.


How to construct a perfect BST from an unbalanced BST with n elements (assuming that n=(2^i)-1, i is natural) How do I construct a perfect BST from an unbalanced BST with $n$ elements (assuming that $n=2^i-1$, $i$ is natural). ** At the worst case of $O(n)$**.

A simple way is as follows: do a symmetric visit of the BST (in time $O(n)$) and write down the elements in increasing order to an array $A$. Then reconstruct the BST from $A$.

If you're fine with a recursive algorithm, and the positions of $A$ are indexed form $0$ to $n-1$, then the root $r$ of the new BST will be exactly the element $A[\frac{n-1}{2}]$. The elements in $A[0], \dots, A[\frac{n-1}{2}-1]$ will be those of the subtree $L$ rooted in the left child of $r$, and the elements in $A[\frac{n-1}{2}+1], \dots, A[n-1]$ will be in the subtree $R$ rooted in the right child of $r$.

Notice that $|L| = 1 + \frac{n-1}{2}-1 = \frac{2^i - 2}{2} = 2^{i-1}-1$ and
$|R| = 1 + (n - 1) - (\frac{n-1}{2} + 1 ) =  (n - 1) - \frac{n-1}{2} = \frac{n-1}{2} = 2^{i-1}-1$, so you can apply this algorithm recursively.

The time required is $T(n) = T(2^i - 1) = 2 T(2^{i-1} - 1) + \Theta(1)$, with $T(1)=\Theta(1)$, which has solution $T(n)=\Theta(n)$.


How is this algorithm in these two complexities? How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal to, but I am not fully sure. Any have any ideas? Thanks.

The $O(\cdot)$ notation only gives an upper bound on the complexity. An algorithm has running time $O(n^2)$ if its running time can be bounded by $cn^2$ for some $c$. If it has running time $n$, say, then it's certainly bounded by $cn^2$ and so $O(n^2)$, though that's not the optimal bound.

A complement to $O(\cdot)$ is $\Theta(\cdot)$. An algorithm has running time $\Theta(n^2)$ if its (worst-case) running time is between $c_1n^2$ and $c_2n^2$ for some $0<c_1\leq c_2$. If an algorithm is $\Theta(n\log n)$ then it is not $\Theta(n^2)$ (though still $O(n^2)$). In fact, even if all you know is that it is $O(n\log n)$, then that rules out $\Theta(n^2)$.

Summarizing, $\Theta$ is "exact" complexity (up to constant multiples), and $O$ is just an upper bound. There is also $\Omega$ which is for lower bounds, for example an algorithm is $\Omega(n^2)$ if its (worst-case) running time is at least $cn^2$ for some $c > 0$.


How do i prove this language is regular? I have this language {0+1+0+} and i need to prove it is regular,i had the idea to use the closure properties but i can find any regular languages to unify perhaps.Any ideas?

Build a finite state machine. Or look up the definition, your definition will either say "there's a finite state machine", or "it's defined by a regular expression".


Comparison Based Sorting Run-time with respect to Total Number of Bits of Input Comparison-based sorting algorithms are lower bounded by $\Omega(nlogn)$, where $n$ is the number of elements in the input list.

However, when dealing with different models of computation, such as algorithms that deal with arithmetic operations (Euclid-GCD) or, $n$, the size of the input, is no longer the number of elements but the total number of bits required to represent the input. In these cases, time complexity is measured as the number of bit operations needed with respect to the total number of bits in the input.

Looking at the post What Is Pseudo-Polynomial Time How Does It Differ From Polynomial Time?

Polynomial time is defined as:

  An algorithm runs in polynomial time if its runtime is O(xk) for some constant k, where x denotes the number of bits of input given to the algorithm.

Pseudo-polynomail time is defined as:

  An algorithm runs in pseudo-polynomial time if the runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it.

Looking at How Can We Assume That Basic Operations on Numbers Take Constant Time?

For word size $w = \theta(logn)$, standard arithmetic operations on these words take $O(1)$ time, by definition.

With these definitions in mind, I have trouble seeing how some comparison-based sorting algorithms are polynomial time with respect to both $n$, the number of elements in the input, and $x$, the total number of bits in the input; the first post I referenced makes this claim.

Why they are polynomial with respect to $n$ is pretty obvious, so I will only look at the bit representation of input $x$ for comparison-based sorting algorithms with 2 different time complexities.

Merge or Quick Sort on a List of $n$ Elements

We need $w = \theta(logn)$, as defined in CLRS, since we at least need to be able to index into an array of size $n$. Assuming all elements fit in a word, which I think is a reasonable assumption here, $x = wn = \Theta(nlogn)$. Please let me know if my $x$ is wrong!!!

Since the running time was $O(nlogn)$, the time complexity with respect to $x$ is $O(x)$. I will interpret this as meaning we need a linear number of operations on the total number of bits needed to represent this input list.

Selection Sort on a List of $n$ Elements:

I will assume the same $x = wn = \Theta(nlogn)$ for the input size. The running time is $O(n^2)$. Here I need some help: how do I write the running time cleanly in terms of $x$, like I did for Merge/Quick Sort above? The first post I referenced just used $w = 32$ bits and easily got $O(x^2)$ polynomial time but this doesn't seem right to me, since the [second post] I referenced (How can we assume that basic operations on numbers take constant time?) and CLRS stressed $w$ is not a constant but $\Theta(logn)$.

I have a similar question for counting sort, that has not been answered yet.. the first post I referenced claims it is exponential with respect to $x$ without the $k = \Theta(n)$ condition when $x = \Theta(nlogk)$ bits, but I have trouble changing from $O(n + k)$ in terms of $x$. Please help!!

Assume, as is often the case, that all elements in the list have width $\Theta(\log n)$. This means that $w = \Theta(\log n)$ and so $x = nw = \Theta(n\log n)$. You can check that $n = \Theta(x/\log x)$, and this allows you to convert running times stated as a function of $n$ to running times stated as a function of $x$. For example, if the running time of some algorithm is $\Theta(n^2)$ as a function of $n$, then its running time as a function of $x$ is $\Theta(x^2/\log^2 x)$.


Can String be a subtype of Character in a programming language? Could a programming language be designed so that there is an inheritance relationship between string and character (both of which are native types), such that the inheritance alone resolves the use of an arbitrary binary operator between the two types: <string> @ <character>; coercion and overloading cannot be used. My intuition is that string would be a subtype of character because a string may be composed of characters, and all basic methods defined for a character work with a string. As a subtype, string could have very specific functionaity such as a length method or attribute. On the other hand, I can see how it might make sense that string is the supertype and character is the subtype. Namely, a character could be thought of as a string of length 1. Which interpretation is correct, or at least which interpretation is more sound?

Character and String are conceptually very, very different. Google for "inheritance vs. composition" - you seem to think that Character and String should be connected via inheritance, but in reality a String is composed of 0, 1 or more Characters.

And to throw a spanner in the works: Strings are often large, and String operations must be very efficient. Therefore, even though conceptually a String is an array of Characters, it will not be implemented as a sequence of objects, but as an array of somehow simpler elements, for example UTF-16 codes.

And then you can think about how to implement Character efficiently if you use Unicode and an emoji character can easily be made up of a dozen Unicode code points - but the huge majority of Characters doesn't need that complexity, and you want an implementation that is space efficient and fast.


Control of the combinatorial aspects of a dynamic programming solution I am exploring how a Dynamic Programming design approach relates to the underlying combinatorial properties of problems.

For this, I am looking at the canonical instance of the coin exchange problem: Let S = [d_1, d_2, ..., d_m] and n > 0 be a requested amount. In how many ways can we add up to n using nothing but the elements in S?

If we follow a Dynamic Programming approach to design an algorithm for this problem that would allow for a solution with polynomial complexity, we would start by looking at the problem and how it is related to smaller and simpler sub-problems. This would yield a recursive relation describing an inductive step representing the problem in terms of the solutions to its related subproblems. We can then implement either a memoization technique or a tabulation technique to efficiently implement this recursive relation in a top-down or a bottom-up manner, respectively.

A recursive relation could be the following (Python 3.6 syntax and 0-based indexing):

def C(S, m, n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    if m <= 0:
        return 0
    count_wout_high_coin = C(S, m - 1, n)
    count_with_high_coin = C(S, m, n - S[m - 1])
    return count_wout_high_coin + count_with_high_coin

However, when drawing the sub-problem DAG, one can see that any DP-based algorithm implementing this recursive relation would yield a correct amount of solutions but disregarding the order.

For example, for S = [1, 2, 6] and n = 6, one can identify the following ways (assumming order matters):

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1 + 1
1 + 1 + 2 + 1 + 1
1 + 1 + 1 + 2 + 1
1 + 1 + 1 + 1 + 2
2 + 2 + 1 + 1
1 + 2 + 2 + 1
1 + 1 + 2 + 2
2 + 1 + 2 + 1
1 + 2 + 1 + 2
2 + 1 + 1 + 2
2 + 2 + 2
6

Assumming order does not matter, we could count the following solutions:

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1
2 + 2 + 2
6

When approaching a problem solution from the Dynamic Programming standpoint, how can I control the order? Specifically, how could I write functions:

count_with_order()
count_wout_order()

?

Could it be that the need for order mattering implies choosing pruned backtracking over a Dynamic Programming approach?

There is absolutely no problem adapting dynamic programming to count solutions without regard to order (i.e., when order doesn't matter). Let $D(S,m,n)$ be the number of ways to obtain a change of $n$ using the first $m$ coins of $S = S_1,\ldots,S_M$. We have $D(S,m,0) = 1$, $D(S,m,n) = 0$ when $n < 0$, and otherwise
$$
D(S,m,n) = \sum_{i=1}^m D(S,i,n-S_i).
$$
This recurrences forces the indices of coins used to be non-increasing: after using $S_i$, we are only allowed to use $S_1,\ldots,S_i$. Counting non-increasing (or non-decreasing) solutions is the same as counting all solutions without regard to order.


Myhill-Nerode classes for a Language $L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$ This problem is from an exercise sheet so it would be nice if you could guide me to the solution.
The problem:
For $ k \in \mathbb{N}\setminus\{0\}$ let
$$L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$$
be the set of words with have at the k-last Position a 1.
(a) How many Myhill-Nerode-equivalence classes does $L_k$ have? Prove your answer.
(b) Construct an minimal DFA for $L_2$ from the equivalence classes.
(c) How many states does a minimal NFA for $L_k$ have? Prove your answer.
What I have:
a) I am pretty clueless, how to approach this problem. I tried to find classes for $k=1, k=2, k=3$ from which I think the amount as a function of k would be $2^k$. But I don't know how to continue.
b) Is pretty easy in comparision, I just added it for the sake of completeness.
c) I think with a) this would be much easier. Because the minimal amount of states is equivalent to the amount of NM classes. But for that I first need a).
Thank you in advance for any advice!

First, I think you have to review the Myhill Nerode Theorem and its relationship to the states of finite automata. You seem to think the number of equivalence classes is the same as the number of states in the minimal NFA, but it's actually the same as the number of states in the minimal DFA.
As a side note, minimization of NFAs is apparently much trickier than minimization of DFAs, so in an introductory formal languages class, you're not going to hear much about minimal NFAs (except in cases like this, where it's straight forward).
So this means it's parts (a) and (b) that are closely related.
As this is a worksheet question, I'll try to only give a guiding hint, rather than a straight-out answer.
The key thing (at least in my opinion) is to realise that each language $L_{k}$ is that it is only really concerned with the last $k$ symbols in the string. So the number of equivalence classes is closely related to this, and the proof that the obvious guess here works is informed by this observation.
This same observation is what gives the minimal DFA (unsurprisingly, as the equivalence classes exactly correspond to the states!). As the DFA doesn't know when the end of the string is coming up, one way you can think of it is as a little sliding window algorithm, and you should be able to relate the states, transitions and equivalence classes in terms of moving this window along one symbol.
To get the minimal NFA, lean on the nondeterminism. What is the piece of information that the DFA doesn't have that you can just nondeterministically guess?


Is the lambda calculus referentially transparent? In an answer of this Reddit discussion somebody defines referential transparency (RT) as "a context $K[ ]$ is RT if, for all $M$ and $N$ s.t. $M = N$, then $K[M] = K[N]$". Based on this definition, Lambda Calculus (LC) (and any other language with binding constructs) is non-RT.

For example, let $\Omega = (\lambda w.ww)(\lambda w.ww)$. In the expressions $(\lambda x.K[x]) \Omega$ and $(\lambda x.K[\Omega])\Omega$, we have $x = \Omega$, so given any RT context $K[]$ both expressions must evaluate to $\bot$. However, if we define $K[] = (\lambda x. [])(\lambda y.y)$, the first expression terminates while the second does not, proving that LC is non-RT.

Is this definition of RT wrong or LC is really a non-RT language?

Quoting the paper referenced in that thread, i.e. What is a Purely Functional Language by Amr Sabry:

  Finally, two informal definitions of purity: referential transparency
  and independence of order of evaluation, do not have universally
  agreed-upon definitions and are not considered any further. (See,
  however, the treatment of referential transparency by Søndergaard and
  Sestoft (1990).)

This refers to the paper Referential Transparency, Definiteness, and Unfoldability by Harald Søndergaard and Peter Sestoft.

So, first off, there is no "right" definition of referential transparency (especially of an entire language as opposed to a single context) to which to contrast to "wrong" definitions. Secondly, the devil is in the details, which is part of why there is no universally agreed-upon definition. Probably the main factor as alluded to by the original Reddit post is: what notion of equality should we use? Obviously using contextual equivalence would be an absurd choice for this purpose. It would make all contexts referentially transparent tautologically. Another factor is what is the domain of things we're considering plugging into the context: raw terms, $\alpha$-equivalence classes of terms, terms-in-context, closed terms? To extend referential transparency to a whole language further requires specifying what exactly the set of contexts is. Finally, often the term "referential transparency" refers (at least roughly) to what Søndergaard and Sestoft call "unfoldability". This is the ability to replace a variable with what it is bound to without changing meaning.  For the pure untyped lambda calculus, this just means the full $\beta$ rule holds which is true for call-by-name but not call-by-value.

In their paper, Søndergaard and Sestoft essentially answer the above questions as follows (extrapolating to the untyped lambda calculus): equality is denotational equality with respect to a given semantics; the domain is raw terms (or perhaps $\alpha$-equivalence classes of terms, whichever the semantics operates over); contexts are as follows: $$\mathcal{K}[\_] ::= \_\mid (\mathcal{K}[\_]) E \mid E (\mathcal{K}[\_]) \mid \lambda x.(\mathcal{K}[\_])$$ where $x$ stands for any variable. At any rate, the upshot of these choices is that your example and psygnisfive's example fail to demonstrate a violation of referential transparency (in this sense) because the terms you are plugging in to the context are not denotationally equal in the first place. In fact, any compositional denotational semantics will guarantee that all contexts are referentially transparent in this sense. Indeed, the example from the paper of a non-referentially-transparent language also has a non-compositional denotational semantics which is "fixed" by making it compositional.

The issue with this definition for more elaborate languages, particularly languages with side-effects, is that we can almost always give a compositional semantics to a programming language. Certainly we can for the lambda calculus extended with mutable state, for example. This leads to the notion not having much bite. The lambda calculus with mutable state equipped with a compositional denotational semantics will be referentially transparent in the above sense because two expressions that have potentially different side-effects won't be considered equal in the first place.


Is there a name for this type of Turing machine? I'm considering turing machines with tape alphabet equal to $\{0,1\}$ and the blank symbol equal to $0$. Is there a name for this type of Turing machines? Isn't this type the one computers are based on?

Not sure about a name, but real computers aren't based on Turing machines at all.


Restricted version of vertex cover I am interested in the complexity of the restricted version of the vertex cover problem below:

Instance: A bipartite graph $G =(L, R, E)$ and an integer $K$.
Question: Is there $S \subset L$, $|S| \leq K$ and every vertex in $R$ has a neighbor in $S$ $( S$ is vertex cover for $R)$

Vertex cover is $\mathsf{P}$ if $S \subset L \cup R$ and cover $L \cup R$; and it is $\mathsf{NP}$-complete for nonbipartite graphs. However, the problem I am looking at does not fit in either cases. Any pointers where I could find an answer will be appreciated.

Let us call your problem as $\mathsf{RESVC}$. $\mathsf{RESVC}$ is NP-Complete.

Given a subset $S \in L$ its easy to verify in poly. time whether it forms a
valid cover of size k. Hence, $\mathsf{RESVC} \in \mathsf{NP}$
$\mathsf{RESVC}$ is also NP-hard because the decision version of the Minimum Dominating set problem reduces to it. And, we know that the decision version of Minimum Dominating set is NP-complete. The reduction goes as follows:

$\qquad \displaystyle \mathsf{D\text{-}MIN\text{-}DOM\text{-}SET} = \{ \langle G,k \rangle : G \text{ has a dominating set } S \text{ s.t. } |S| \leq k \}$

Reduce the instance $\langle G,k \rangle$ of above language to $\langle G',k \rangle$ as follows:

Lets say $G = (V,E)$ and $V = \{v_1,v_2,\dots,v_n\}$ and define $G' = (L \cup R, E')$ with

$L  = \{v_{11},v_{21},...,v_{n1}\}$
$R  = \{v_{12},v_{22},...,v_{n2}\}$
$E' = \{(v_{i1},v_{j2}) : (v_i,v_j) \in E \vee (v_j,v_i) \in E\} \cup \{(v_{i1},v_{i2})\}$

Now, it is easy to see that $\langle G',k \rangle \in \mathsf{RESVC}$ if and only if $\langle G,k \rangle \in \mathsf{D\text{-}MIN\text{-}DOM\text{-}SET}$.


The convoy effect in process scheduling As I understand the convoy effect, in the context of vehicular traffic in a road system. A slow moving group of vehicles passes through the system, slowing traffic even in areas which were not directly affected by the convoy.

How does this apply in the context of CPU scheduling? It does not seem to be an analogous situation.

FCFS (First-Come, First-Served) scheduling can also cause blocking in a busy dynamic system in another way, known as the convoy effect.

When one CPU intensive process blocks the CPU, a number of I/O intensive processes can get backed up behind it, leaving the I/O devices idle. When the CPU hog finally relinquishes the CPU, then the I/O processes pass through the CPU quickly, leaving the CPU idle while everyone queues up for I/O, and then the cycle repeats itself when the CPU intensive process gets back to the ready queue.


Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines? I've always thought vaguely that the answer to the above question was affirmative along the following lines. Gödel's incompleteness theorem and the undecidability of the halting problem both being negative results about decidability and established by diagonal arguments (and in the 1930's), so they must somehow be two ways to view the same matters. And I thought that Turing used a universal Turing machine to show that the halting problem is unsolvable. (See also this math.SE question.)

But now that (teaching a course in computability) I look closer into these matters, I am rather bewildered by what I find. So I would like some help with straightening out my thoughts. I realise that on one hand Gödel's diagonal argument is very subtle: it needs a lot of work to construct an arithmetic statement that can be interpreted as saying something about it's own derivability. On the other hand the proof of the undecidability of the halting problem I found here is extremely simple, and doesn't even explicitly mention Turing machines, let alone the existence of universal Turing machines.

A practical question about universal Turing machines is whether it is of any importance that the alphabet of a universal Turing machine be the same as that of the Turing machines that it simulates. I thought that would be necessary in order to concoct a proper diagonal argument (having the machine simulate itself), but I haven't found any attention to this question in the bewildering collection of descriptions of universal machines that I found on the net. If not for the halting problem, are universal Turing machines useful in any diagonal argument?

Finally I am confused by this further section of the same WP article, which says that a weaker form of Gödel's incompleteness follows from the halting problem: "a complete, consistent and sound axiomatisation of all statements about natural numbers is unachievable" where "sound" is supposed to be the weakening. I know a theory is consistent if one cannot derive a contradiction, and a complete theory about natural numbers would seem to mean that all true statements about natural numbers can be derived in it; I know Gödel says such a theory does not exist, but I fail to see how such a hypothetical beast could possibly fail to be sound, i.e., also derive statements which are false for the natural numbers: the negation of such a statement would be true, and therefore by completeness also derivable, which would contradict consistency.

I would appreciate any clarification on one of these points.

I recommend you to check Scott Aaronson's blog post on a proof of the Incompleteness Theorem via Turing machines and Rosser's Theorem. His proof of the incompleteness theorem is extremely simple and easy to follow.


Proof by restriction: when is it valid to restrict to a special case? I was reading a few notes on Proof by Restriction and I am confused:
A Valid Proof by Restriction is the following:
Directed Hamiltonian Cycle Problem is NP Complete because if we look only at instances of DHC where For $G=(V,E)\quad (u,v)\in E \leftrightarrow (v,u) \in E$ then it reduces to Hamiltonian Cycle which we know is NP complete.
A wrong proof is the following:

Subset Sum problem
INSTANCE: Integers $a_1, a_2,…,a_n$ and integer B.
QUESTION: Is there a sequence of 0’s and 1’s, $x_1, x_2,…,x_n$ such that:
$$\sum_{i=1}^n a_ix_i \leq B$$

is a special case of

Real Subset Problem
INSTANCE: Integers $a_1, a_2,…,a_n$ and integer B.
QUESTION: Is there a sequence of real numbers  $x_1, x_2,…,x_n$  such that:
$$\sum_{i=1}^n a_ix_i \leq B$$

so it is NP Complete.
My notes say that the this proof is wrong since it restricts the question and not the instances but I don't seem to understand the difference.
Further, I can't really understand how Proof by Restriction works; for all I know I could be restricting an NP Complete problem to a trivial case which can be solved in Polynomial time.

Think about the set of all possible instances of DHC. A subset of these instances are those where, for every directed edge $(u, v)$, there is always a matching directed edge $(v, u)$. (In general, this doesn't have to be the case, but it CAN be the case, which is why this is a valid restriction.)

Now think about the set of all possible instances of SubsetSum. For each such instance, you're supposed to answer with a set of 0/1-valued $x_i$. By your first definition, there are NO valid answers that include a real number in the $x_i$. So, when you suddenly allow real-valued solutions in the second version of SubsetSum, you're relaxing the problem, not restricting it. (You're giving yourself more leeway by allowing more possible solutions.)


Consensus and Perfect Failure Detector I try to get a better understanding about Failure Detectors in the field of Distributed Computing.

Let consider the algorithm for reaching consensus with Perfect Failure Detector, it's named as Perfect FDAgreement in the textbook Distributed Algorithms by Nancy A. Lynch on the page 679. In addition, it can be found in the following presentation Asynchronous Network Computing with Process Failures. Slide 16.

The basic idea of the algorithm is each process $P_i$ attempts to stabilize two pieces of data: a vector val, indexed by $\{1,2,...,n\}$, with values in $V \cup \{null\}$.$val(j) = v \in V$, it means that $P_i$ knows that $P_j$’s initial value is $v$. A set stopped of process indices. If $j \in stopped$, it means that $P_i$ knows that $P_j$ has stopped.

The question is as one of the step of the algorithm every process that receive a message ignores it from the processors it has already placed in stopped.

I don't understand why we need this, even we don't ignore the message from stopped process it won't broke anything. This case may occur when  $P_j$ sends a message to $P_i$ and crashes, FailureDetector see the crash and informs the process $P_i$ that $P_j$ is stopped after that $P_j$'s message reaches $P_i$, but this message contains a correct data, and it doesn't change the state of $P_j$ in stopped set, because only INSERT (insert new values that previously was null) and COMPARE are allowed operations on the set.

If you see the real reason for ignoring messages from the crashed process please share it with us.

Addendum: Unfortunately I didn't find any use of the aforementioned fact (ignoring message from crashed node) in the algorithm (Perfect FDAgreement in the textbook Distributed Algorithms by Nancy A. Lynch).

In addition, in main papers Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors forasynchronous systems and Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest
failure detector for solving consensus slightly different algorithm can be found without ignoring messages from crashed nodes.

It could be that the analysis works either way, or perhaps the analysis (or the algorithm) could be slightly modified to handle this change. I suggest you go over the correctness proof of the algorithm and see where this step is used (if at all).


Machine code: How can an OS prevent user-level programs from accessing each other's memory? Okay, I’ve done a lot of research on this, but I can’t seem to wrap my head around it. Essentially, the question is as follows: How can an operating system prevent a machine instruction from a user-level program (Firefox, Word, etc.) from accessing memory locations that it isn’t supposed to access?

Here’s what I think I understand so far: Machine code, as you would for example find it in a .exe file after building your C/C++ program, is a sequence of binary instructions. These instructions can run directly on the CPU (assuming that the program was compiled for that CPU’s instruction set, e.g. x86). So, you don’t technically need an operating system to “run a program” in a broader sense – which isn’t surprising, since an operating system is just a program itself. Also, the CPU doesn’t work in terms of “programs” or “processes”, but in terms of individual instructions.

Now, if we do have an operating system (e.g. Windows), part of its job is to assign an encapsulated memory segment to each running user-level program (e.g. Firefox, Word, my own C++ program, …), and to make sure that they can’t read/corrupt each other’s memory.

This is where things get fuzzy for me. If I were to write my own operating system (or other bare-metal program), I would need to be able to use machine instructions to read/write to and from any existing location in the entire memory, right? So, how does an operating system make sure that no user-level program sends such instructions to the CPU on its own, without “asking the OS for permission” to access a certain memory location?

I would actually love to learn more on the entire topic of going from high-level code to machine instructions. For instance, I would also like to understand what user-level program threads and OS-level processes look like on bare-metal, etc. So, if anyone could point me to a good resource, that would be highly appreciated. Nonetheless, this isn’t the core of my post, just a side note.

The key is Virtual Memory.

There might be many ways to do this, but the reigning one across most OSes (*nix or Windowses alike) is Virtual Memory. And it needs CPU support, which is given in x86 by the MMU (Memory Management Unit) and in which I'll base my examples further on.

The secret is: no user-level process has access to the whole CPU. x86 has four rings of execution, and certain CPU opcodes (instructions) execute only within the appropriate ring. Ring 0 is for the kernel (the heart of the OS), and ring 3 is for user-level processes (rings 1 and 2 are most often not used, and if used, it's usually for virtualisation purposes -- out of the scope of this answer). If you execute an instruction within the wrong ring, the CPU faults to the kernel. Hence, if a process tries to execute a privilege instruction, when the CPU is on ring 3 mode, the CPU itself stops that process and gives control to the kernel, which will usually kill that process. Only the kernel can change the ring mode.

The secret-key for memory protection is that, all memory accesses, unless executed within the kernel's ring 0 (and perhaps even within that ring mode, but that's not relevant for this discussion, as we're talking only about user processes, not the kernel), need to go through the MMU, which will translate the memory address of the process to that which the kernel has actually given.

So two different processes can access a memory cell by the same address, say, 0x45b3c1, whatever. In reality, the MMU will translate real-time each process's request to what the kernel says it should be.

For this, the kernel prepares page tables, which you can imagine as a "map<void*, void*>" (forgive my over-simplification here, and try to imagine the crazy optimisations needed), of what the process actually has. And it prepares tables only for what the process previously said it would use. If the process asks for an address that hasn't previously asked the kernel to prepare a table for him, then the CPU says this process got nuts and in reference of this process, it signals the infamous SEGFAULT to the kernel, which will decide what to do next.

I know that this is sort of self-promotion, but I just recently wrote a lot about this topic and even gave a talk at my company, in case the link is welcomed I'd like to share: https://www.farfromready.com/malloc-alone-a-story-of-the-computers-memory/


3Sum Why this O(nlogn) solution doesn't work? I have been doing LeetCode and tackled the problem of the 3Sum and first I tried to do a O(nlogn) solution and after seeing the proposed solution I see that the solution is $O(n^2)$ or $O(n^2 \times \log n)$ and not only that but the problem is a highly researched topic so I don't think I found a better solution but can't see why my approach wouldn't work, can use help to figure it out.
The problem is the following
Find three numbers in an array such that $a + b + c = t$,
the LeetCode problem is slightly different in which you need to find the closest sum.
My code is the following:

Sort the array.
  Start with two pointers i=0 and j= last element of array
    Use binary search between i and j to find m such that arr[m] == target - arr[i] - arr[j], if such m doesn't exist return m such that arr[m] is the closest.
    If arr[i] + arr[m] + arr[j] == target then your finished.
    Otherwise if arr[i] + arr[m] + arr[j] < target then add 1 to i else subtract 1 form j.
Repeat 3 → 5 until j - i == 2
Return the best found i,m,j

The logic in step 5 is that if the solution found is less than the target then we should increase i such that our next guess is bigger.
Code:
def binSearch(arr, s, e, t):
    m = (s + e) // 2
    r = m
    d = 9999
    while s <= e:
        m = (s + e) // 2
        if arr[m] == t:
            return m
        elif arr[m] > t:
            e = m - 1
        else:
            s = m + 1

        if d > abs(t - arr[m]):
            d = abs(t - arr[m])
            r = m
    return r

class Solution:
    def threeSumClosest(self, nums, target: int) -> int:
        nums.sort()

        s = 0
        e = len(nums) - 1
        minn = 999999
        t = ()
        while e - s >= 2:
            left = nums[s]
            right = nums[e]
            remaining = target - (left + right)
            m = binSearch(nums, s + 1, e - 1, remaining)
            middle = nums[m]
            r = left + middle + right

            # print("i's: ", (s,m,e))
            # print("values: ", (nums[s], nums[m], nums[e]))
            # print("r", r)
            # print("**************")

            if r == target:
                return r
            elif r < target:
                s += 1
            else:
                e -= 1

            if abs(target - r) < minn:
                minn = abs(target - r)
                t = r
        return t

This fails for, e.g., [1, 9, 55, 55, 100], t=111. The first iteration finds 110 and increases i to exclude 1 as a possibility, but the only solution, [1, 55, 55], needs 1.
The basic problem is that when you increase i or reduce j, you are assuming that the element you just advanced past is not needed -- that there exists some solution that does not include it. But this is not justified by anything, and it could well be that all solutions need that element.
A great way to test algorithm ideas like this is to write a small program that generates many small random inputs, and compare the result of your algorithm on each of them to the result of a known-correct brute-force approach.


Partition points on a 2d plane with arbitrary line segment Let's say I have a 11x11 grid with a few points (around 8) marked in the grid. One of the points is in the center cell. Call it point P.

I choose a point other than P and connect it with a line segment to P. Call that point C1

I choose another point that is not C1 and connect it with a line segment to P. Call that point C2.

Now, if we extend the line segments out from P to the edges of the grid, then the grid will be split into two regions A and B.

How can I determine which of the remaining points are in A and B efficiently?

Hint: Instead of storing them as cartesian points, store them as polar coordinates (with a tiny drop of preprocessing).


Proof that there are same number rotation moves in any binary tree with both children compulsory I am working on this project where I am required to find the theoretical proof for following.

I have a particular type of binary trees, where

1) each internal node will definitely have two children.

2) There are n leaf nodes and can be assumed in order 1 to n from left most to right most.

Now this is clear that there are multiple such trees. And I am performing tree rotation (https://en.wikipedia.org/wiki/Tree_rotation) operation in any of one internal node of the tree.

I was thinking that in any such type of tree with n leaf nodes there will be guaranteed n-1 internal nodes and total n-2 possible rotation moves. (The rotation is only valid if the rotated tree also has the two given properties i.e. an internal node with just left node as leaf node cannot be right rotated.)

I have tried various resources but couldn't find any proof for it. I have tried it myself but not able to reach to a solution. I'd be glad if someone can help me out here.

EDIT:

I could get to one possible proof, please see if it's correct.

There are 3 parts of the proof:

a) With these rotation moves, you can convert to any of the tree into a completely left branching tree, I have the proof for it and it's well known in graph theory.

b) Any rotation moves preserves the number of possible rotations in the tree. This is critical, I will prove it in the end.

c) In any left branching tree, out of total n-1 internal node, everyone except one can be right rotated. So total n-2 rotations.

All 3 together gives that total n-2 rotations possible.

Now the critical (b) part:

From the wikipedia image on the link (https://en.wikipedia.org/wiki/Tree_rotation), the number of rotations for subtrees A, B ,C remains the same and reverses for P and Q. So the total moves will remain same.

I can give more details for the above statement if required, but it's hard to write it here.

Each rotation involves a node and its left or right child. We can associate this rotation with the child – the rotation is fixed once the child is known. In your case, a child can be rotated as long as it is an internal node. So the number of possible rotations is the number of non-root internal nodes. A simple induction shows that a full binary tree having $n$ leaves has exactly $n-1$ internal nodes, and so $n-2$ non-root internal nodes.


Probability of winning a turn-based game with a random element I am preparing for a programming exam on probability theory and I stumbled across a question I can't solve.
Given a bag, which contains some given amount of white stones $w$ and some given amount of black stones $b$, two players take turns drawing stones uniformly at random from the bag. After each player's turn a stone, chosen uniformly at random, vanishes, and only then does the other player take their turn. If a white stone is drawn, the player, who has drawn it, instantly loses and the game ends. If the bag becomes empty, the player, who played second, wins.
What is the overall probability that the player, who played second, wins?
I assume it's a dynamic programming question, though I can't figure out the recursion formula. Any help would be greatly appreciated. :)
Example input: $w$ = 3, $b$ = 4, then the answer is, I believe, 0.4, which I arrived at after computing by hand all possible ways for the game to go, so not very efficient.

Let us denote by $\Pr(w, b)$ the probability of P2 winning given its their turn and there are $w$ white stones and $b$ black stones remaining and similarly we write $\overline\Pr(w, b)$ for the probability of P2 winning given it is P1's turn.
From the rules of the game we get that any of the following cases can occur in P2's turn (assuming that enough stones are left):

White is drawn and P2 loses. This happens with probability $w / (w + b)$.
Black is drawn and a white stone vanishes. The probability for this is $b / (w + b) \cdot w / (w + b - 1)$.
Black is drawn and a black stone vanishes. We find the probability for this to be $b / (w + b) \cdot (b - 1) / ( w + b - 1)$.

If it is P1's turn to play we find similar cases:

White is drawn and P2 wins. This happens with probability $w / (w + b)$.
Black is drawn and a white stone vanishes. The probability for this is $b / (w + b) \cdot w / (w + b - 1)$.
Black is drawn and a black stone vanishes. We find the probability for this to be $b / (w + b) \cdot (b - 1) / ( w + b - 1)$.

We can now factor $\Pr$ and $\overline\Pr$ using our case distinctions and some simple probability theory:
$$
\begin{align*}
\Pr(w, b) &= \Pr(\text{Case 1.2}) \cdot \overline\Pr(w - 1, b - 1) + \Pr(\text{Case 1.3}) \cdot \overline\Pr(w, b - 2), \\
\overline\Pr(w, b) &= \Pr(\text{Case 2.1}) + \Pr(\text{Case 2.2}) \cdot\Pr(w - 1, b - 1) + \Pr(\text{Case 2.3}) \cdot \Pr(w, b - 2)
\end{align*}
$$
Note that we can combine these 2 equations to find a recursive formula for $\Pr$ (which I will not type out here for brevity).
Coupling these with the initial values $\Pr(w, b)$ where $w + b \leq 4$ (which can be precomputed) will give us an algorithmic way to find the desired probability.


Confusion about data types, compilers, hardware data representation and static vs dynamic typing I am trying to understand static vs dynamic typing, but am really struggling to see how everything fits together.

It all starts with data types. As far as I understand, data types are quite abstract notions, which exist 'in' compilers in order to categorise data so that the operations on various types of data can be validated (i.e. in an attempt to stop you adding a string to an integer), and in order to generate the right machine code for the hardware interpretation of the value. I.e. say we have the following:

int myInt = 5;
char myChar = '5';

Console.WriteLine(myInt);
Console.WriteLine(myChar);

Both would ultimately write a five to the console window, but, since the representations in memory of integers and characters are different, the machine code which interprets the value in the memory location bound to the variable myInt, which takes that value and displays it on the console window, would be different to the machine code for myChar. Even though Console.WriteLine() 'does the same job', the different representations of five require different low level code.

So my question is this: if data types 'exist only in the compiler' - i.e. once the program has been compiled into machine code there is no knowledge of what type of data the value in a particular memory cell is (everything is just 1s and 0s) - then how can any type-checking be done at runtime? Surely there is no concept of data types at run time? So surely dynamic typing can't be anything to do with type-checking occurring at run time?

Where is my understanding going wrong, and could somebody please explain static and dynamic typing with respect to the argument given above? What is the big picture of what is going on?

I am trying to understand this for an essay, so references to books or online sources would be useful :) Thank you.

First, you must be aware that computer science is full of terms which have multiple, related but conflicting definitions.  The fact that two authors are using the same term such as "type" does not mean they are using the same definition and thus there may be inconsistencies if you are not careful when you try to combine different sources.

A type is a property attached to entities (values, variables, ...) which allow to know what operations are allowed on those things and what is the result of those operations (including the type of the result).  That means that type determines the interpretation of the bits pattern representing a value, but that's not the only effect of types.  It is common to introduce several types which gives the same meanings to bits patterns, just to prevent to use them in some context (an extreme example would be to have different types for X and Y coordinates to be sure they are not swapped at the wrong time).

A language may be:

statically typed: an analysis of the program allows to know the type of an entity without the need to execute it (that is what you were thinking about).  That is common for languages which are compiled.
dynamically typed: value carries information about their type. Choices which need that information must be done at execution time, looking at the information attached to the value at hand. That is common for languages which are interpreted.
untyped: operations assume that their arguments are correct (note that this is different from implicit conversions, implicit conversions tries to conserve a notion of value, in an untyped language that does not happen), there is no typing error (but an argument may be invalid and trigger an error) nor choice of behavior depending on types. Nowadays the more common languages which are untyped are the assembly languages. Historically languages like BLISS and BCPL were also in that class.  The original TCL language was also in that class.

Note that it is quite common for languages to have aspects of several kinds. C++ for instance has a notion of static type which determines some things such as overload resolution, a notion of dynamic type which determines other things such as virtual function dispatch and reinterpret_cast allows to circumvent the typing system and behave in an untyped way.  A language may be defined in a dynamic way, as if the values carried the type information, but a compiler may analyze a program and remove part of the checks that would be needed and even remove the need to attach a dynamic type information on some values.  And a language may have types (static or dynamic) but be used in an untyped way (Lisp variants often have a notion of dynamic type, but lists are also often used to represented everything not built-in).

  So my question is this: if data types 'exist only in the compiler'

I've tried to show that this assumption is false. It may be true for some languages, but others attach type information to values (and that's the case for object oriented one -- I've in the past described OO as a way to get the benefits of dynamic typing without dropping completely the benefits of static typing --, if there is a dynamic dispatch based on type, you need to have dynamic type information).  Note that the information may be part of the value as a tag, as a pointer to a type-descripting data structure (the vptr of common implementation of C++), or even implicitly (that area of memory is used only to store values of that type, the bits don't have to show what type is the value, the place where they are is giving the information).

References

Types and Programming by B. Pierce (but IIRC it is strongly oriented towards static typing)

Concepts, Techniques, and Models of Computer Programming by P. van Roy and Seif Haridi, wider of scope but also more oriented towards dynamic typing and may also be useful to organize things before a reference such as B. Pierce which is more concerned about just typing issues.


How does a co-NP problem differ from an NP (its complement) one? I have quite a hard time understanding co-NP problems.

If we can reduce every problem to decision problem. NP problems should accept YES instances -> instances where the answer is yes. So for example for Traveling Salesman problem, we would ask "Is there a path that visits every city, and is shorter than N" ?

For co-NP problem, they should accept NO instance -> answer to them is NO. But given this, how would we formulate co-NP problem to Traveling Salesman problem I mentioned earlier? if we formulate it "Isn't there a path that visits every city and is shorter than N"? If there wasn't the path, the answer would be YES -> so it would be YES problem, if the answer was NO, we would have to try the path which would be same as YES problem.

So what is the difference? Was my co-NP decision problem to said TSP correct?

I have read wiki and tried to find some sources but nothing helped...

Thanks for help!

A co-NP problem differs from its complementary NP problem exactly by being its complement! That's the whole story.

  NP problems should accept YES instances -> instances where the answer is yes.

I think you've confused yourself. Every problem, of any complexity, is a division of all possible instances into "yes" instances and "no" instances. For TSP, the "yes" instances are the maps where the salesperson can visit all the cities within the distance requirement and for co-TSP, the "yes" instances are the maps where the salesperson can't (i.e., the "no" instances of TSP).

What differs between complexity classes is the amount of resources and model of computation that are required to tell the difference between a "yes" intance and a "no" instance. For NP, we use a nondeterministic Turing machine running for a polynomial number of steps and say that the machine accepts if at least one computation path accepts, and rejects otherwise. For co-NP, we do the opposite: the machine rejects if at least one computation path rejects, and accepts otherwise.


Example of a prefix-free code I came across the following question:

A source $X$ emits symbols from the alphabet $A_x$ with $|A_x| = 8$. We want to construct a preﬁx-free source code for this source.

We want to ﬁnd a code with codeword lengths $(1,3,3,3,5,5,5,5)$. Can such a code exist? If yes, give such a code. If not, prove that.

I checked Kraft's inequality for the given set of lengths and it's fulfilled. So how can we write such a code?


Are all system calls blocking? I was reading an article that describes the switch between user-space and kernel-space that happens upon a system call. The article says

  An application expects the completion of the system call before resuming user-mode execution.

Now, until now I was assuming that some system calls are blocking, whereas others are non-blocking. With the comment above, I am now confused. Does this mean that all system calls are blocking or did I misunderstand a concept?

You seem to be overloading the term 'blocking'.

Any context switch you make to the kernel, you have to wait for it to switch back to the usermode before your application can continue. This is not what is usually called 'blocking'.

In the current kernel design, blocking calls are calls where the kernel returns only when the request is complete (or error happens). These calls usually take longer amounts of time and usually lead your process to be scheduled out. For instance, many IO calls are blocking.

There are system call which provides asynchronous IO and they are non-blocking. Note that there is still a context switch that happens here, only the application has to take care of the asynchronous nature of the call.

The paper seems to aim to do away with this context switch back and forth (exception-less system calls) and try to make all the calls asynchronous.


A continuous optimization problem that reduces to TSP Suppose I am given a  finite set of points $p_1,p_2,..p_n$ in the plane, and asked to draw a twice-differentiable curve $C(P)$ through the $p_i$'s, such that its perimeter is as small as possible. Assuming $p_i=(x_i,y_i)$ and $x_i<x_{i+1}$, I can formalize this problem as:

 Problem 1 (edited in response to Suresh's comments) Determine  $C^2$ functions $x(t),y(t)$ of a parameter $t$ such that the arclength $ L = \int_{[t \in 0,1]} \sqrt{x'^2+y'^2}dt$  is minimized, with $x(0) = x_1, x(1) = x_n$ and for all $t_i: x(t_i) = x_i$, we have $y(t_i)=y_i)$.

  How do I prove (or perhaps refute) that Problem 1 is NP-hard?

 Why I suspect NP-hardness    Suppose the $C^2$ assumption is relaxed. Evidently, the function of minimal arclength is the Travelling Salesman tour of the $p_i$'s.  Perhaps the $C^2$ constraint only makes the problem much harder?

 Context  A variant of this problem was posted on MSE. It didn't receive an answer both there and on MO. Given that it's nontrivial to solve the problem, I want to establish how hard it is.

The differentiability requirement doesn't change the nature of the problem: requiring $\mathcal{C}^0$ (continuity) or $\mathcal{C}^{\infty}$ (infinite differentiability) gives the same lower bound for the length and the same order of points, and is equivalent to solving the traveling salesman problem.

If you have a solution to the TSP, you have a $\mathcal{C}^0$ curve that goes through all the points. Conversely, suppose you have a $\mathcal{C}^0$ curve of finite length that goes through all the points, and let $p_{\sigma(1)}, \ldots, p_{\sigma(n)}$ be the order in which it traverses the points and $t_1,\ldots,t_n$ the corresponding parameters (if the curve traverses a point more than once, pick any of the possible values of $t$). Then the curve built from $n$ segments $[p_{\sigma(1)},p_{\sigma(2)}], \ldots, [p_{\sigma(n-1)},p_{\sigma(n)}], [p_{\sigma(n)},p_{\sigma(1)}]$ is shorter, because for each segment a straight line is shorter than any other curve that connects the point. Thus for every ordering of the points, the best curve is a TSP solution, and the TSP solution provides the best ordering of the points.

Let's now show that requiring the curve to be $\mathcal{C}^{\infty}$ (or $\mathcal{C}^k$ for any $k$) doesn't change the best ordering of points. For any TSP solution of total length $\ell$ and any $\epsilon > 0$, we can round every corner, i.e. build a $\mathcal{C}^{\infty}$ curve that traverses the points in the same order and has a length of at most $\ell + \epsilon$ (the explicit construction relies on algebraic functions and $e^{-1/t^2}$ to define bump functions and from those smooth connections between curve segments such as $e^{1-1/x^2} (x-e^{-1/(1-x)^2})$ which connects with $y=0$ at $x=0$ and with $y=x$ at $x=1$; it is tedious to make these explicit, but they are computable); hence, the lower bound for a $\mathcal{C}^{\infty}$ curve is the same as for a collection of segments (note that the lower bound is not reached in general).


Are single-dimentional arrays better than multi-dimentional in the GPU? I'm making simulations like Ant colony simulation, boids, and cellular automata in Go (to learn Go), but I believe this can apply to most languages.
From what I've read (this), using 1D arrays is generally better, but the post only addresses CPU processing. I want to do my simulations with the GPU and that may have some implications I'm not aware of.
In my case, a Map object is a 2D array of Cell objects.
struct Cell {...}
struct Map {
  Cell[][] cells;
}

Is it better to use 1D arrays instead of multi-dimensionals when working with the GPU?

This is likely going to be dependent on what technology and libraries you use to program the GPU (PyTorch? TensorFlow?  CUDA? BLAS? something else?), and thus seems likely to be out of scope here.  Typically the data must be transferred/copied onto the GPU anyway, so I'd expect the structure of it in RAM only affects the time to transfer to the GPU's memory, not the time to do the GPU computation once it has been copied into GPU memory in the memory layout that the GPU wants.


Regular expression generating the language $L=\{w: |w|\le 5\}$ Im trying to find a regular expression to generate the language that has words with length at most 5, over $\Sigma =\{0,1\}$
How can i represent the at most ? I know i can do it if ill just write all the $2^5$ possibilties with 'or' between them. But it seem to me not the right way.
Is it even possible to represent the state : "I've choose 0, 1, or nothing" ?

I can use only the elemntary operators : $\cup , \cdot , ^*$

Also it was easyer to find a NFA that will represent L but the algorithem to get the regex from the aotomton will give me the exponential answer.

If you are allowed to use $\epsilon$, then you can represent "0, 1, or nothing" using $0+1+\epsilon$, and using this it is easy to come up with a short regular expression.

If you are not allowed to use $\epsilon$, then you can use the fact that $L = \bigcup_{i=0}^5 \{ w : |w|=i \}$ to come up with a fairly short regular expression, though I don't know how you would match the empty string.


An algorithm for identifying a fruit with words Let's say a person picked up a fruit and wanted to identify it.

The person knows certain features about the fruit, such as its color and where it was plucked from, but not its name. They also have knowledge that's relevant for identifying the fruit, but they're not aware that it's relevant (such as the color of the soil below them).

What algorithm could you use to narrow the space of possible answers, such that you could identify the fruit with questions and facts alone?

For an example of how an algorithm/software might work:

Question One

"Is this fruit red?"

Yes / No

Question Two

"Did you find this fruit in May?"

Yes / No

Question Three

"Does this fruit taste sour?"

Yes / No

Question Four

"Does the fruit feel hard?"

Yes / No

A bit like the game of 20 Questions, except in this case, the person does not know what the answer may be—only certain characteristics of the answer.

Is there any algorithm or approach that might work to solve this problem in this particular way?

Have a look at decision trees.

You might rather quickly see a connection to your problem: think about what you should have at each node of the tree and what at each edge. Then think about what should be at the leaves (or very bottom) of the tree and how that might answer your problem.


Data addresses with ADD instruction in various architectures? How many data addresses are specified in an ADD instruction in accumulator based architecture, stack based architecture, and in the most common register-based architecture?

I'm not sure what I should look at - diagrams? Assembly code? Thank you for any help in advance!

First some terminology:

Let's consider the ADD operation that is a logically three operand operation: two sources and one target, so these 3 are the maximum that could be provided.

A (hardware) machine instruction is subdivided into fields, the main one of which is the opcode field.  The instructions can also be fixed-length or variable length.

An addressing mode is a way of specifying what memory address (i.e. data address) to use for reading or writing.  The architectures that you are asking about vary in the instructions that allow for addressing modes as fields in the instruction.  Typically, the fields associated with an addressing mode require a fair number of bits, such as 12, 16, 20 or more because they contain parts of memory addresses.

In a stack-based architecture, operations such as ADD implicitly target the stack, for both sources as well as for the target.  So, an ADD instruction has just one field, the opcode field, and will have no instruction set fields regarding source and target.  Initial operands are moved to the (expression) stack using PUSH instructions and popped of this stack using STORE (or POP) instructions.  It is the PUSH & STORE instructions that have the potential to indicate sources and targets that reference memory (e.g. data addresses).  The following accomplishes an ADD in a stack architecture.

PUSH  item1
PUSH  item2
ADD
STORE item3

item1, item2, and item3 would be considered addressing modes within those instructions, and might allow access to local variables and global variables.  Because the PUSH & STORE instructions have additional fields beyond the opcode whereas the ADD instruction does not, stack machine architectures typically use varying length instructions.  The hardware advances the PC by the right amount for each instruction so that it can execute the logically following instruction.  When several computations (multiple ADD or ADD & SUB, etc..) are combined the stack machine can use the stack to transfer intermediate computations without intervening PUSH & POP instructions.

In an accumulator-based architecture, you will typically have opcodes with one addressing mode.  The following sequence would be typical of them:

LOAD  item1
ADD   item2
STORE item3

You can see that a similar code sequence has one less instruction, and the instructions tend to be more regular.  As a result of this, accumulator machines might choose a fixed length instruction set (e.g. 16-bits).  The accumulator is implicitly sourced and targeted and does not require an instruction field.

A RISC register architecture, like MIPS will have a large number of registers (e.g. 32 or more), and support three operand instructions, though only between registers.  Memory operations will require separate LOAD and STORE instructions.

LOAD  r1, item1
LOAD  r2, item2
ADD   r3,r1,r2
STORE r3, item2

Here we have a longer sequence for the same operation; however, the RISC machine has so many registers that the idea is to use them instead of memory for local variables and such.  Thus, many of the loads and stores you might otherwise expect are eliminated.

x86, for the most part, is two operand machine.  It has more registers than your single accumulator machine, but fewer than a RISC machine.  Most instructions on x86 allow specifying a register number and an addressing mode, which might refer to another register or might refer to a memory addressing mode.

MOV AX, item1
ADD AX, item2
MOV item3, AX

Like the RISC machine, the 8 or so registers can be used for heavily used local variables, reducing the memory access.  However, will fewer registers the advantage isn't as good as with a RISC machine.

There are considerable trade-offs between these various architectural approaches to instruction set architecture.  Generally speaking, the stack machines result in smaller code space, because of their variable length instruction sets.  Code space has a huge impact on instruction cache performance, so the smaller the code, the better.  However, by comparison with RISC machines with their fixed-size instructions, the variable length instructions (and more of them) require substantially more complex decoding hardware, which either costs transistors or sacrifices performance.


How to prove that $n$ sets have maximum of $2^n-1$ disjoint subsets when you have operations $\cup , \cap , \setminus$? I just found out that you can have $2^{2^n-1}$ different subsets, made from $n$ sets, using operations $\cup , \cap , \setminus$.

That is because when $n=2$, for example, you have 3 disjoint subsets: $A\setminus B, B\setminus A,A\cap B$ and then you can union those things together in $2^3-1$ different ways (plus the empty set) to get $8$ different unequal sets.

My question is, how to prove that the number of those disjoint subsets is $2^n-1$.

Pictorial definition of what disjoint subsets are:

In the picture above I have enumerated disjoint subsets of $2$ and $3$ sets. As you can see their number is $2^n-1$.

First of all, your question is not really well-defined, or put differently, the claim is incorrect in general. Consider for example $A = B = \emptyset$, in which there is only one set which you can get, namely $\emptyset$.

There are at least two ways in which we can address this problem. The first is to assume that the starting sets are "generic", that is, they don't enjoy any "special" properties. This is a vague description, but it can be formalized by saying that in the "Venn diagram" of the sets (which I describe below), all regions are non-empty.

The second way is to do everything formally. We think of $A$ or $A \setminus B$ not as a set but as a formal expression defined in an appropriate language. We then make two expressions equal if they are equal whenever you substitute actual sets. For example, $A = A \cap A$ and $A \setminus (A \setminus B) = A \cap B$. You can also define equality syntactically if you prefer.

Another problem with your claim is that it's not clear what you mean by "the sets have $2^n-1$ non-overlapping subsets". For example, $A \cap B$ and $A \setminus B$ are non-overlapping, and this is a maximal collection of non-overlapping subsets (in general). You mean something else, and again there are several possible interpretations. This time all interpretations I can think of only serve to complicate things and make them less intuitive, so I'll just explain what is meant by the claim, and you think of an appropriate interpretation.

The Venn diagram of the sets $A_1,\ldots,A_n$ consists of the $2^n$ regions which you can get by intersecting either $A_i$ or $\overline{A_i}$ for each $i$. That is, for each $i = 1,\ldots,n$ we choose $A_i$ or $\overline{A_i}$, and then compute the intersection of these $n$ sets. You can web-search "Venn diagram" to see pictorial representations.

You can prove by induction (exercise) that any set that you can obtain from (possibly multiple copies of) $A_1,\ldots,A_n$ using $\setminus$, $\cup$ and $\cap$ is a union of regions of the Venn diagram; indeed, a union which doesn't include the region $\overline{A_1} \cap \cdots \cap \overline{A_n}$. Moreover, you can easily get any of these $2^n-1$ regions individually (exercise), and these are your "$2^n-1$ non-overlapping subsets". In total, you can get any union of these $2^n-1$ regions (exercise), and so you can "reach" $2^{2^n-1}$ different expressions.

One possible formulation of your two claims are as follows. First, the maximal number of disjoint sets that can be formed from $A_1,\ldots,A_n$ is $2^n-1$ (under the caveats described in the second paragraph); this can be proved using the exercises mentioned above. Second, the number of different sets that can be formed (again, under the same caveats) is $2^{2^n-1}$, which again follows from these exercises.


Longest common subsequence solution reconstruction during DP is wrong I've implemented longest common substring in python. I know the usual way to reconstruct the path. But, I am reading my algorithm many times, I don't understand why it doesn't work for some test-cases. I am trying to construct the solution while the longest path is being made through dynamic programming.
def lcs(s1, s2):
    n = len(s1)
    m = len(s2)

    trow = [0] * (m+1)
    table = [trow] * (n+1)

    srow = [""] * (m+1)
    solution = [srow] * (n+1)

    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                table[i][j] = table[i-1][j-1] + 1

                # Adding this character to the solution
                solution[i][j] = solution[i-1][j-1] + s1[i-1]

            elif table[i][j-1] > table[i-1][j]:
                table[i][j] = table[i][j-1]

                # Choosing the solution related to the longer path
                solution[i][j] = solution[i][j-1]

            else:
                table[i][j] = table[i-1][j]

                # Choosing the solution related to the longer path
                solution[i][j] = solution[i-1][j]

    return solution[n-1][m-1]

lcs('amin', 'kahmjiknln')
# Returns 'amin'

lcs('amin', 'aaaakahmjiknln')
# Returns 'aaaaamin'

Programming questions are off-topic here.
Anyway your matrices table and solution are not properly initialized as they contain references to the same objects. Try:
    table = [[0]*(m+1) for j in range(n+1)]
    solution = [ ["" for i in range(m+1)] for j in range(n+1) ]

Moreover, the returned string should be solution[n][m] and not solution[n-1][m-1].


Is there a general-case sweep line algorithm for line segment intersection? I'm looking for a sweep line algorithm for finding all intersections in a set of line segments which doesn't necessarily require the general position constraint of Bentley-Ottman's algorithm (taken from Wikipedia):

No two line segment endpoints or crossings have the same x-coordinate
No line segment endpoint lies upon another line segment
No three line segments intersect at a single point.

Is there any sweep line solution to this problem? If not, is there any other algorithm that solves this problem in $\mathcal{O}((n+k) \log(n))$?

Usually these algorithms can be adapted to the general case, but the details are messy and hard to get right. Another option is perturbation:

Move each line segment by some small amount in all directions.
Extend the segments slightly on both ends.

If you choose your parameters carefully (i.e., small enough), you are likely to have all the same intersections, but you will be in general position with probability 1. How small is small depends on your input, and this is a limitation of this approach, but in practice you can probably heuristically choose a small enough perturbation.

Implementing this using "virtual infinitesimals", you can come up with a version of Bentley–Ottman that doesn't require general position. The idea is to do the perturbation by some infinitesimal amount, and record the results formally (e.g. $1$ goes to $1+\epsilon$, where $\epsilon$ is an infinitesimal). When running the algorithm, you will need to compare values which involve these infinitesimals, which you can do formally (for example, $1+\epsilon < 1 + 2\epsilon$).


What hash algorithm is it? I've found a simple multiply-with-add hash function in an old Usenet post.
Can someone identify what hash algorithm is it? An algorithm name or any attribution?

size_t hash(const char* data, size_t length, size_t seed = 1)
{
    for (size_t i = 0; i < length; i++)
    {
        seed = seed * (UCHAR_MAX + 2U) + data[i];
    }

    return seed;
}

This hash function is very similar to a linear congruential generator, a type of naive pseudorandom number generator. By now there are much better hash functions out there, and I suggest not using this one.


Do real world computers use the Turing Machine mechanism? I am a high school student in the twelfth grade. I study high-level programming, and a little bit of basic computer science.

I have recently started to understand what a Turing Machine is. I wanted to ask:

I understand that a Turing Machine is a hypothetical device used to explain the mechanisms of computing.

But is a Turing Machine conceptually the actual very basis of computers? (In the most basic level). Or do real world computing mechanisms and the Turing Machine mechanism (way of calculating things) have very little in common?

Turing machines were invented by Turing in his 1936 paper on computable numbers and the halting problem. It was one of a few models floating around at that time (like Church's $\lambda$ calculus, which had been defined earlier). All these models have later been shown equivalent, so if you're only interested in computability, then the Turing machine model is as good as any other model.

Modern computers are not based on the Turing machine model. Turing machines are very slow, and don't represent the capabilities of hardware. From the software side, a modern computer is similar to the RAM machine, which allows indirect addressing and has an unlimited "alphabet" (its registers hold arbitrarily large integers), though actual machines have limited registers, and this sometimes makes a big difference (for example, when doing arithmetic on large numbers). I don't know of a good model for the hardware side; Boolean circuits, popular in theoretical computer science, model neither memory nor iterative computation.

Turing machines are polynomially equivalent to RAM machines with polynomially bounded registers. That means that both machines provide the same notion of efficient computation (polynomial time computation), a theoretical notion whose usefulness in practice is doubtful. In contrast, (bounded) RAM machines form a reasonable model for actual computation, and so complexity results for RAM machines have practical relevance. However, even this model ignores some important complexities of modern computers, such as the speed of access to different kinds of memory (disk, main memory, different caches).


How do I know which direction I should rotate a node in an AVL Tree? I'm studying AVL Trees in my programming class and we got this exercise dealing with right, left, left-right and right-left rotations as a way to check if we understand the theoretical concept of AVL Trees. We're given the numbers $100,50,25,10,37,32,200$. Creating an AVL Tree until $37$ wasn't that difficult but then I got stuck at balancing out the tree when I insert $32$. The following is my method:

Now I know that there is a conflict at $52$ but since it has 3 nodes (LRL), I don't understand how I should rotate. I think, I should get $37$ as the root node $25$ as it's left child and $52$ as it's right child but I dunno.

I think, I should get 37 as the root node 25 as it's left child and 52 as it's right child but I dunno.

You plan is correct.

What you need to do is a left-right rotation as shown in the third column of the table below. That is,  a left rotation at node 25 followed by a right rotation at 52. It is symmetric to the right-left rotation as shown in the fourth column and as explained in Wikipedia.