Why do we consider the order of growth when analyzing algorithms? Seriously why do we consider how the computation time time increase  with the number of inputs as a measure of performance when we can easily measure such as program execution time,power consumption,memory usage etc?Because all of these facts are depends on the hardware and programming language we use in that moment and order growth is only depends on inputs?

I think the key point in time complexity analysis is it can give us a metric to measure the time independent of any hardware or software dependency directly.

Hence, we can talk about the time complexity based on inputs and outputs of the problem without considering more sophisticated or even complex cases by mentioning that we are talking about the hardware or software specifications.

However, hardware usage is mentioned in some real applications too, somewhere the time complexity can't distinguish the solutions in its abstract asymptotic definition. These kind of analysis are common in AI algorithms which have the same time complexity but have some real differences in real applications and hardware usage. For example, in real applications "Quick Sort" is better than "Merge Sort" because we have a large constant factor in "Merge Sort" time complexity, however, on the paper, in time complexity, "Merge Sort" is better than "Quick Sort" in worst cases.

In sum, time complexity base on the growth can be proper to compare algorithms independent of any hardware or software specifications, although hardware usage in real applications makes sense more!


Utilization of static evaluation functions in chess Disclaimer: I'm very new to computer science & game programming

I'm having trouble with understanding how to implement a static evaluation function in chess. The logic seems simple like just apply a weight to each piece on the board and subtract the pieces from each side, but its much more complex than that isn't it? You'd have to calculate a method of analyzing the board and each of the MULTIPLE actions that are occurring on the board at the same time (ie. Castling, checking pawns are being lost, if you're in check etc etc).

Is there a relatively simple way of implementing a static evaluation function to a chess board to "see" whats going on at each stage?

Side Note: I understand that you could implement things like Minimax (with $ \alpha - \beta$ pruning) searches onto the trees created via the static evaluation functions, so correct me if I'm wrong but whats going on is that $$ f(Board) = c_1 * (thing 1) +  c_2*(thing 2) + \cdots $$ but where do those $ \cdots$ end??? And from there, we get a number which we put in our tree then implement the minimax algorithm, to figure out the best move forward?

Are there any resources for this type of thing that I could possibly read? Thank you.

There are simple ways to do so but it may not be a very good heuristic. For example going off of current piece valuation is very simple but leads to poor aggressive behavior. There are many other things to account for in addition to piece valuation like centrality and pawn structure that when included, is subjectively simple. See https://chessprogramming.wikispaces.com/Evaluation for more notes on evaluation and for general chess programming advice.

Regarding your side note: 'Those things' end based on your heuristic function. Yes you get a board valuation that is used to determine how good a move is, guiding your game tree search.


What is the difference between quantum computing and parallel computing? Quantum computing essentially relies on the fact that qubits maintain multiple possible states simultaneously. Parallel computing too processes multiple states simultaneously. So what is the difference or how are they different?

For a parallel computer, we need to have one billion different processors. In a quantum computer, a single register can perform a  billion computations. This is known as quantum parallelism. Also a quantum computer returns a single randomly-selected correct result, while a parallel computer can directly return all valid results. That's the reason why reading results out of quantum computers generally is slow and getting all results requires running the quantum computation enough times to be relatively certain that the random sampling has seen all possible results.
Hope this helps!
See this also: differences-between-quantum-computing-and-parallelism


Are Context Sensitive Languages Turing Complete? Related questions:

Can regular languages be Turing complete?
Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
https://stackoverflow.com/questions/14589346/is-c-context-free-or-context-sensitive
https://softwareengineering.stackexchange.com/questions/132385/what-makes-a-language-turing-complete

Context-sensitivity has nothing to do with the semantics of a language. A language could have an arbitrarily complicated grammar, and still not be able to do anything useful, perhaps because it has no looping construct.

To make the above possibly clearer, here's a simple example. We know that it is possible to list all Turing machines in some order. (The proof is not difficult and comes from Alan Turing himself). That means that we can associate every positive integer with some Turing machine, in such a way that every machine has a unique index.

Now, take the language $L_1 = \{a^i \mid i > 0\}$ (where $a^i$ means a string consisting precisely of $i$ $a$s). Since any string of $a$s is in $L_1$, the language is equivalent to the regular expression $a^+$.

The semantics of a program in  $L_1$ is simple: it does whatever Turing machine number $i$ would do, where $i$ is the length of the program. That's clearly a Turing complete regular language.

Then we define $L_2 = \{a^ib^i\mid i>0\}$ and $L_3 = \{a^ib^ic^i\mid i>0\}$, with the same semantics: in each case, program $i$ executes Turing machine number $i$. So these languages are also Turing complete, but $L_2$ is context-free and $L_3$ is context-sensitive.

Now, let's redefine the semantics. We'll define three languages with exactly the same syntaxes, but instead of executing Turing machine $i$, they print out $i$ in binary and then halt. These three new languages are still regular, context-free and context-sensitive, respectively, since the syntaxes have not changes. But none of them is Turing complete.

Bottom line: What a language means and how it is expressed are completely different concepts.


What randomness really is I'm a Computer Science student and am currently enrolled in System Simulation & Modelling course. It involves dealing with everyday systems around us and simulating them in different scenarios by generating random numbers in different distributional curves, like IID, Gaussian etc. for instance. I've been working on the boids project and a question just struck me that what exactly "random" really is? I mean, for instance, every random number that we generate, even in our programming languages like via the Math.random() method in Java, essentially is generated following an "algorithm".

How do we really know that a sequence of numbers that we produce is in fact, random and would it help us, to simulate a certain model as accurately as possible?

The short answer is that no one knows what real randomness is, or if such a thing exists. If you want to quantify or measure the randomness of a discrete object, you would typically turn to Kolmogorov complexity. Before Kolmogorov complexity, we had no way of quantifying randomness of say a sequence of numbers without considering the process that spawned it.

Here's an intuitive example that was really bugging people back in the day. Consider a sequence of coin tosses. The outcome of one toss is either heads ($H$) or tails ($T$). Say we do two experiments, where we toss a coin 10 times. The first experiment $E_1$ gives us $H,H,H,H,H,H,H,H,H,H$. The second experiment $E_2$ gives us $T,T,H,T,H,T,T,H,T,H$. After seeing the outcome, you might be tempted to claim there was something wrong with the coin in $E_1$, or at least for some weird reason what you got is not random. But if you assume both $H$ and $T$ are as probable (the coin is fair), the probability of obtaining either $E_1$ or $E_2$ is equal to $(1/2)^{10}$. In fact, obtaining any specific sequence is as probable as any! Still, $E_2$ feels random, and $E_1$ does not.

In general, since Kolmogorov complexity is not computable, one can't compute how random say a sequence of numbers is, no matter what kind of claimed "totally random" process spawned it.


How can I efficiently plot the inside of an ellipse? I am given the the coefficients for an ellipse in the form:
$$Ax^2 + Bxy + Cy^2 + Dx + Ey + F=0.$$

I have a 2 dimensional array of point objects (in Python) called "pixels", and I need to give each point a "count" if they lie inside the ellipse.

I initially tried iterating through every point with a loop like:

for row in pixels:
    for pixel in rows:
        x=point.get(pixel)[0]
        z=point.get(pixel)[1]
        if a*(x)**2 + b*(x*z) + c*(z)**2 + d*(x) + e*(z) + f >0:
            pixel.addpcount()

But this is taking way too long because I have several thousand ellipses I need to do this for. Is there a way I can efficiently do this?

(If this is not the right place to ask this question, I apologize.)

Edit:
(I don't have enough reputation to comment).
The Python is mostly irrelevant to my question at hand. I just want a better algorithm instead of iterating through every point.

In order to determine whether something is inside an ellipse, I am actually using this test https://math.stackexchange.com/questions/817130/how-to-determine-if-arbitrary-point-lies-inside-or-outside-a-conic.

The user Evil suggested using Axis Aligned Bounding Box. Does this mean finding the box which bounds an ellipse, and then testing only those points inside the box? That would seem a lot more efficient.

Greybeard, I am not sure what the Bresenham algorithm is, but I will take a look.

Following @Evil's comment, I suggest two steps. For each ellipse $E$:

(1) Computing a bounding box $B$ for $E$.

(2) For each row of pixels in $B$, walk left-to-right until a pixel $p_1$
is discovered to be inside $E$.
Then walk right-to-left until $p_2$ is in $E$.
Then all the pixels from $p_1$ to $p_2$ are in $E$
(because of convexity).

The most difficult step is computing a bounding box for the ellipse.
You likely don't need it exactly.
Here are two sources:

"How do you calculate the axis-aligned bounding box of an ellipse?."
"How do you find a tight-fitting, axis-aligned, bounding box of a rotated ellipse in AS3?."


Equivalent Colorings of Graphs Call two proper graph colorings equivalent if one can be obtained from the other by a permutation of the colors.
In other words, they are the "same" coloring.

I'm interested in finding proper non-equivalent colorings.
Of course, the decision problem of determining whether or not there is such a non-equivalent coloring given one is NP-complete.

Are there FPT, approximation, etc. algorithms for finding such a coloring if one exists?
I am currently running a randomized greedy coloring algorithm, which does often succeed in finding a proper coloring - however, I am unsure of when it actually produces a non-isomorphic one.

If it is helpful, I'm working with graphs which are essentially $k$-trees.

Many existing heuristics for graph coloring can work even if you specify the colors of a few vertices.  So, here is one plausible algorithm you could use:

We are given an existing coloring $C$.  Pick two vertices $v,w$ randomly.  We are going to assign colors for $v,w$ (in the new coloring), leave the other vertices unassigned, and use some existing graph coloring heuristic to extend this to a coloring for the whole graph.  If $C(v)=C(w)$, assign $v,w$ two different colors in the new coloring (any two, it doesn't matter which two colors you use).  If $C(v)\ne C(w)$, assign $v,w$ the same color in the new coloring (any color, it doesn't matter which you pick).  Then extend this to a coloring for the new graph.

If this finds a coloring, then you're guaranteed that the new coloring will be non-equivalent to the old one.  Moreover, if there exists a non-equivalent coloring, you're guaranteed to be able to find it with at most polynomially many invocations of this procedure.  In particular, if $C'$ is non-equivalent, there must exist some pair of vertices $v,w$ where $C(v)=C(w)$ and $C'(v) \ne C'(w)$, or where $C(v) \ne C(w)$ and $C'(v) = C'(w)$.  Therefore, if you repeat the above procedure for all pairs $v,w$ of vertices, at least one of those iterations should find a new non-equivalent coloring.

So, this might be one reasonable approach, if you want to find a new non-equivalent coloring once.  On the other hand, if you are given $m$ existing colorings and want to find a $m+1$st non-equivalent coloring, that looks more complicated.


What is meant by a full abstract model of a lambda-calculus like language? The simply typed lambda-calculus with numbers and fix has long been a favorite experimental subject for programming language researchers, since it is the simplest language in which a range of subtle semantic phenomena such as full abstraction arise.

I tried to find a definition for full-abstract model but I haven't found such. This quote is from Pierce's TAPL book. Note that there is also a related question: What is a "model" of lambda calculus? on the site that has not been answered.

In denotational semantics, you want to be able to map each of your language terms to some object in your semantic domain or model. Now, it cannot be any arbitrary domain/model as you like, but, informally speaking, something that gives a good intuition about how the language works (its computational behavior).

Milner tried to formalize what this "intuition" should be and called it full abstraction. Formally, a model is fully abstract if all observationally equivalent terms in the object language represent the same object in the model. Equationally:
$$\text{if }  ⟦t_1⟧ = ⟦t_2⟧  \text{then } t_1 \rightsquigarrow t_2 $$
where $\rightsquigarrow$ represents observational equivalence. In case of lambda-calculus observational equivalence would be $\beta\eta\alpha$ conversions and $⟦\_⟧$ is the denotation function.

There are few papers that you might want to take a look at if you are interested in seeing some full abstract models of lambda like languages:

Plotkin's paper that gives a full abstract model of the lambda like language called LCF
Mulmuley's paper gives a full abstract model of typed lambda calculus.
Hyland and Ong's papers give a full abstract model of PCF using game semantics


Bit complexity of $n$-th Fibonacci number using matrix multiplication I want to find the bit complexity of finding the $n$-th Fibonacci number using the matrix multiplication method. I know that it has complexity $O(\log n)$ if we assume that the standard operations have complexity $O(1)$, but if we now consider their true complexity, for example $O(n)$ for addition, I don't know how to calculate its true complexity. Can anyone help?

Let us recall that
$$
F_n
=
\begin{pmatrix} 0 & 1 \end{pmatrix}
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^n
\begin{pmatrix}
1 \\ 0 \end{pmatrix}.
$$
We compute the $n$-th Fibonacci number using the method of repeated squaring, applied to the $2\times 2$ matrix. The matrices encountered during this process are all of the form
$$
A_m = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^m =
\begin{pmatrix}
F_{m+1} & F_m \\ F_m & F_{m-1}
\end{pmatrix}.
$$
Repeated squaring runs in $\ell \approx \log n$ steps. In the $t$-th step, we square a matrix $A_m$ with $m = \Theta(2^t)$, and possibly multiply it by the base matrix. Since the entries of $A_m$ are $\Theta(m)$ bits long, squaring takes $\Theta(m\log m) = \Theta(2^tt)$ bit operations, and this is the dominant operation in the $t$-th step. The overall bit complexity is thus proportional to
$$
\sum_{t=1}^{\ell} 2^tt = \Theta(2^\ell \ell) = \Theta(n\log n).
$$


What is a partially sorted array? I come across this definition but it's not so clear for me !

  An array is partially sorted if the number of inversions is less or
  equal a constant times the array length. if array length is N then
  (number of inversions) <= c*N, with c constant.

For me c should be <= 1 is this what they meant ?

For more context : insertion sort running time is linear for partially sorted arrays.

The definition you quote is rather meaningless. More accurately, a sequence of arrays, one of each length $n$, is partially sorted if for some constant $c$, the number of inversions of the array of length $n$ is at most $cn$. (More succinctly, a sequence of arrays is partially sorted if the number of inversions is $O(n)$.) The running time of insertion sort on such a sequence of arrays is $O(n)$, that is, linear.

It doesn't make much sense to say that a single array is partially sorted, since we can always choose $c$ to make the definition hold. If we want to talk about a single array then we need to fix $c$ in advance. Note that $c$ doesn't have to be at most $1$.


Will such an algorithm be feasible, will it be considered a poly time algorithm? Given a p-digit number n, where p is atleast 500, if we have an algorithm whose computational complexity is in  the worst case,
$O(p\mathrm{log}(p))$,
will it be counted as a poly time algorithm ? Or since $(p\mathrm{log}(p))$ is basically the logarithm of an exponent so it will inefficient. And such an algorithm will be infeasible or intractable.
Secondly what if we can cut down the complexity in the worst case scenario to,
$O(p\mathrm{log}(p)/5)/100 )$?

Will this complexity be considered same as the worst-case complexity?

As the length of the input is $p$ and the worst case of the algorithm is $O(p\log(p))$, the algorithm is polynomial as the worst case is $O(p^2)$ and $p^2$ is polynomial.

For the second case, there is not any change in time complexity as constant values are multiplied or divided in the polynomial or logarithmic case. To scrutinize more, $p \frac{\log(p/5)}{100} = p \frac{(\log(p) - \log(5))}{100} = \frac{p\log(p) - p\log(5)}{100} = \Theta(p\log(p))$.


Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$? I am trying to analyze the running time of a bad implementation of generating the $n$th member of the fibonacci sequence (which requires generating the previous 2 values from the bottom up).

Why does this algorithm have a time complexity of $\Omega(2^{\frac{n}{2}})$? Where does the exponent come from?

Expanding on Reza's answer, every recurrence of the form $T(n) = T(n-1) + T(n-2)$, with arbitrary initial values, has a solution of the form
$$ T(n) = A \left( \frac{1+\sqrt{5}}{2} \right)^n + B \left( \frac{1-\sqrt{5}}{2} \right)^n, $$
for some $A,B$. Note that $|(1-\sqrt{5})/2| < 1$, and so the second term tends to zero as $n \longrightarrow \infty$. Assuming that $T(n)$ tends to infinity, $A > 0$ and so
$$ T(n) = \Theta\left( \left( \frac{1+\sqrt{5}}{2} \right)^n \right). $$
Now $(1+\sqrt{5})/2 > \sqrt{2}$, and so $T(n) = \Omega(2^{n/2})$.

Edit: This part is also covered in this answer (see under "A Shortcut").

More generally, for a recurrence of the form $T(n) = \sum_{i=1}^k a_i T(n-i)$, let
$$ P(t) = t^n - \sum_{i=1}^k a_i t^{n-i}. $$
If $P$ has no repeated roots and the (possibly complex) roots are $\lambda_1,\ldots,\lambda_k$, then the solution is always of the form
$$ T(n) = \sum_{i=1}^k A_i \lambda_i^n. $$
If it does have repeated roots, say the roots are $\lambda_1,\ldots,\lambda_l$ with multiplicities $m_1,\ldots,m_l$, then the solution is always of the form
$$ T(n) = \sum_{i=1}^l A_i(n) \lambda_i^n, $$
where $A_i$ is a (possibly complex) polynomial of degree smaller than $m_i$.

In our case, $P(t) = t^2-t-1$ has no repeated roots, and the two roots are $(1\pm\sqrt{5})/2$.

The $A_i$s depend on the initial values, and can be found by solving linear equations. For example, suppose we are given $T(0)$ and $T(1)$ for our recurrence. Then we can find $A,B$ by solving the system
$$
\begin{align*}
T(0) &= A + B, \\
T(1) &= \frac{1+\sqrt{5}}{2} A + \frac{1-\sqrt{5}}{2} B.
\end{align*}
$$
This works even in the case of repeated roots, and $k$ initial values always suffice. Assuming $a_k \neq 0$, $k$ initial values are also necessary.


What is an efficient way to calculate the biggest system of disjunct sets? Let $I$ be a finite set of items and $\mathcal{M} = \{M | M \subseteq I\}$ be a set of subsets of $I$.

The task is to find the biggest subset $\tilde{\mathcal{M}} \subseteq \mathcal{M}$ so that all elements of $\tilde{\mathcal{M}}$ are pairwise disjoint:

$$\text{arg } \max_{\tilde{\mathcal{M}} \subseteq \mathcal{M}} |\tilde{\mathcal{M}}| \text{ with } \bigcap_{M \in \tilde{\mathcal{M}}} M = \emptyset$$

What is an efficient algorithm to do so?

(If $|I| \approx 10\,000$ and $|\mathcal{M}| \approx 100$ )

Example

Let $I = \{a, b, c, d, e\}$ be the set of items and

$$\mathcal{M} = \{A, B, C, D\}$$

with

$$
\begin{align}
A &= \{a\}\\
B &= \{b, c\}\\
C &= \{a, c\}\\
D &= \{b, d\}
\end{align}
$$

Then $$\tilde{\mathcal{M}} = \{A, B\}$$
is one of the solutions. There is no way to have $|\tilde{\mathcal{M}}| \geq 3$.

Ideas

Brute force

M_tilde_max = None
for Mc_tilde in powerset(Mc):
    if Mc_tilde is disjunct and (M_tilde_max is None or M_tilde_max < |Mc_tilde|):
        M_tilde_max = Mc_tilde

This has complexity $\mathcal{O}(2^{|\mathcal{M}|})$.

Apriori

If a set $\tilde{\mathcal{M}}$ has only disjunct items, then all possible subsets have to be disjunct. So one can at first find all sets of size 1 which have this property (which are simply all sets), then all sets of size two, then all of size 3, ...

This has the same worst-case time complexity as brute force as in the worst case $\tilde{\mathcal{M}}$ is just equal to $\mathcal{M}$. It might in some scenarios - if one knows that it will be smaller - be much better. However, the space complexity is quite bad here.

More

I guess one could pre-compute for all $|\mathcal{M}|^2$ combinations of two sets if they are disjunct or not. After that, the table can be used and $\mathcal{M}$ and $I$ don't have to be touched at all. This is the maximum satisfiability problem. Each set $M_i \in \mathcal{M}$ is a boolean variable $x_i$. If $M_i$ and $M_j$ are disjunct, then $(x_i \lor x_j)$ is added. If not, then either $(x_i \lor \neg x_j)$ or $(\neg x_i \lor x_j)$ can be added (I think it doesn't matter which one?). This way, a conjunctive normal form can be produced. All clauses have only two elements, so I think there might be an efficient algorithm for it?

Context

This question is more a brain-teaser for me. It started with the following problem:

I would like to generate a tree of categories for Wikimedia commons. The problem is that categories in Wikimedia Commons are not disjunct. For example, for https://commons.wikimedia.org/wiki/Category:Rosa there is the category "Roses by location", "Rosa by month", "Roses by photographer" which are not what I want. However, to filter those I think just removing categories with the substring " by " might be enough. I have to check it, though.

This answer assumes that the sets in $\tilde{\mathcal{M}}$ have to be pairwise disjoint (as currently stated, you are requiring them to have empty intersection, which is a monotone condition).

The decision version of your problem is NP-complete, by reduction from independent set. Given an graph $G = (V,E)$, construct a set system with a set $S_x$ for each vertex $x \in V$, and an element $e$ for each edge $e \in E$. The set $S_x$ contains all edges incident to $x$. A family of sets is pairwise disjoint iff the corresponding vertices form an independent set.

We can also go in the other direction, following one of your suggestions. Given a set system, construct a graph in which each vertex corresponds to a set, and two vertices are connected if the sets intersect. A solution to your problem is the same as an independent set in the graph.


Problems with decidability open (for a long time) proven decidable It seems to me that problems whose dedicability remains open for a long time, if resolved, tend to end up being undecidable. A prominent example would be (e.g.) Hilbert's tenth problem, whose decidability was open 21+ years (†) until proven decidable. Is there a similiar example of a problem whose decidability was open for a long time (receiving considerable attention) but was proven, in the end, to be decidable?

(†) Hard to put an exact figure on how long it was open. Originally stated in 1900 and proven in 1970, but the original statement was before the modern notion of undecidability.

I suspect there are many of them.  Pick almost any recent paper that shows decidability of some problem, and I suspect chances are good you'll  have an example.  So, I doubt your heuristic that if decidability remains open for a long time, chances are that the problem is undecidable.

For example: The matrix mortality problem for non-singular 2x2 matrices was recently shown to be decidable (Decidability of the Membership Problem for 2 × 2 integer matrices, Potapov, Semukhin).


How can both |y| = 0 and y⁰ = ε hold in the Pumping lemma? There is something in the pumping lemma that I do not quite understand, namely if $s$ is at least of length $p$, then we could split it to $xyz$ such that the following conditions are met:

For each $i \geq 0$, $x(y^i)z \in A$
$|y| > 0$
$|xy| \leq p$

But if $i = 0$ then $|y|$ cannot be strictly greater than $0$. Isn't condition 1 contradicting condition 2? Isn't $y^0 = \varepsilon$?

Sure, $y^0$ is $\epsilon$, but that does not make $|y|=0$.
Consider $y=\mathit{foo}$. Here, $|y|=|\mathit{foo}|=3$, yet $(\mathit{foo})^0=\epsilon$.
No contradiction – $y$ is unchanged.


How to sample uniformly from a stream of elements, some of which are unsuited? I get values $x_t$ in an online fashion and want to buy "good" ones, where "good" means that some measure $P(x_t) >T$. Consider the following simple algorithm.

T = 0.7
N = 100 // or any value N > B
B = 20 // or any value 1 < B < N

l = 0

for t from 1 to N:
    input a new observation x_t
    let P(x_t) the probability associated to x_t

    if P(x_t) > T:
        l = l + 1
        pay 1 dollar to buy y_t the label of x_t
        output immediately the label y_t

If the condition $P(x_t) > T$ is used then we get about $l = 100-70 = 30$, this is ok since the value of $T$ is set to $0.7$.

Now if I want to add a constraint which is: additionally to the fact that elements $x_t$ for which the label $y_t$ is purchased are those for which $P(x_t) > T$, I want also that we do not buy more than $B=20$ labels (for example because we only have 20 dollars as budget).

But the problem is that, if I replace the the condition ($P(x_t) > T$) by ($P(x_t) > T \wedge l < B$), then the elements $x_t$ for which we buy a label are more likely to be among the first elements $t$ that we browse (that is, for an element $x_{95}$ for $t = 95$ for example we will never have a chance to buy its label even if its probability was $P(x_{95}) \gg T$). But I want that all the elements from $t = 1$ to $N$ will have equal chance to buy their label (not advantaging only the first elements).

Note: the condition that $P(x_t) > T$ for buying the label of a new observation $x_t$, should not be removed from my code. This is important for me: only labels of observations for which $P(x_t)$ was higher than $T$ at time $t$, are possibly purchased; and we should not purchase more than our budget $B$. Note also that a purchased label should immediately be output after we buy it, we should not wait until the end to decide if we buy it or not.

Also, note that we do not have the N elements beforehand; at each time $t$ we see just one new observation $x_t$. And note that you pay 1 dollar when you select a given $x_t$ to ask for its label and that you should output answer (label of selected $x_t$) immediately; so you can not select some $B$ elements then replace them with new selected other elements, because your budget $B$ will already be finished.

The easiest way to solve this problem might be to randomly permute the input. For example, you could compute a random permutation pi on N elements, and replace the main loop with

for s from 1 to N:
   t = pi[s]
   ...

Edit: If you want to solve this in an online fashion, here is a different suggestion. Consider first the case $B=1$ and a threshold $T$ that always holds. So given a sequence of elements, we want to select a uniformly random one in an online fashion. This is done by the following algorithm:

for t from 1 to N:
  x = input()
  with probability 1/t:
    selected = x
return selected

Now let's still assume that $B=1$, but let the threshold be arbitrary:

 count = 0
 for t from 1 to N:
   x = input()
   if P(x) > T:
     count = count + 1
     with probability 1/count:
       selected = x
 return selected

Now assume we have arbitrary $B \geq 1$, but all the elements cross the threshold:

for t from 1 to N:
  x = input()
  if t <= B:
    selected[t] = x
  else:
    with probability B/t:
      i = random({1,...,B})
      selected[i] = x
return selected

Finally, putting everything together:

count = 0
for t from 1 to N:
  x = input()
  if P(x) > T:
    count = count + 1
    if count <= B:
      selected[count] = x
    else:
      with probability B/count:
        i = random({1,...,B})
        selected[i] = x
return selected

Edit 2: Here is yet another suggestion, assuming that you know both $N$ and the number of elements crossing the threshold, let's say $M$. You choose a random subset $S$ of size $M$ of $\{1,\ldots,N\}$. You select the $k$th element crossing the threshold for each $k \in S$.

If you only have an estimate for $M$, you can try a similar algorithm in which you guess $M$ and hope for the best.

Here is pseudocode for the algorithm:

S = random subset of {1,...,N} of size M
count = 0
for t from 1 to N:
  x = input()
  if P(x) > T:
    count = count + 1
    if count in S:
      select x


Bytes and bits conversion? It is claimed in my textbook that

  In a 32-bit system, The instruction LDR r4,[r6] lets you address a
  logical space of 4GB.

I know where the 4GB comes from, It is simply 2^32 / (1024 x 1024 x 1024).

However, My question is why is it bytes and not bits ?

Why when we raise 2^32, we should talk about bits and not bytes. And so 4GB doesn't make sense to me .

For me It would make sense if it is (2^32/8)/ (1024 x 1024 x 1024)

That's because memory is usually byte-addressed.  The address that you load from is an address of a byte in memory.  Each address refers a different byte in memory.  For a 32-bit address, there are $2^{32}$ different possibilities for the address, so $2^{32}$ different bytes that the address could refer to (and no overlap among these bytes).  $2^{32}$ is equal to 4GB.

If we had a hypothetical machine where memory was bit-addressible, then it would indeed be 4Gb, i.e., 4 gigabits instead of 4 gigabytes -- but no one builds machines that way today.


Identification of Formal Language $$L = \{a^{m+n}b^{m+k}c^{n+k}\mid m,n,k\ge 1\}.$$

Is $L$ DCFL or not?

According to me it should be DCFL since we can write $L$ as $\{a^{n}a^{m}b^{m}b^{k}c^{k}c^{n}\mid m,n,k\ge1\}$. So, now after push and pop on the stack, it will be empty. So, according to me it will be DCFL but I have doubt since DPDA can't count $n$ and $m$ after reading symbol $a$ so machine can't know how many $a$'s should have to be popped. According to this logic, one stack is not enough for this language. So, it should be CSL. Please tell me whether it should be DCFL or CSL?

$L$ is CFL because there is a CFG generating it:

$$
\begin{align}
S&\rightarrow aAc\\
A&\rightarrow aAc \mid BC\\
B&\rightarrow aDb\\
C&\rightarrow bEc\\
D&\rightarrow aDb \mid \epsilon\\
E&\rightarrow bEc \mid \epsilon
\end{align}
$$

$L$ is not DCFL. To prove this, we give some lemmas firstly:

  Lemma 1.
  $$
\begin{align}
L &=\{a^x b^y c^z\mid x,y\ge 2, x+y+z\text{ is even},|x-y|+2\le z\le x+y-2\}\\
&=\{a^x b^y c^{|x-y|+2+z}\mid x,y\ge 2, z\text{ is even},0\le z\le x+y-|x-y|-4\}.
\end{align}
$$

Proof. Let $L'=\{a^x b^y c^z\mid x,y\ge 2, x+y+z\text{ is even},|x-y|+2\le z\le x+y-2\}$. Easy to see $L\subseteq L'$. Now let $a^xb^yc^z\in L'$, then we can choose $m=(x+y-z)/2, n=(x-y+z)/2, k=(y-x+z)/2$. Because $x+y+z$ is even, $m,n,k$ are all integers. Because $|x-y|+2\le z\le x+y-2$, we have $m,n,k\ge 1$, so $a^xb^yc^z\in L$. As a result, $L=L'$.

  Lemma 2. $M =\{a^x b^y c^{|x-y|+2}d^z\mid x,y\ge 2, z\text{ is even},z\le x+y-|x-y|-4\}$ is not context-free.

Proof. Suppose it is context-free, according to Odgen's lemma, there exists some $p\ge 1$ such that $s=a^{p+2}b^{p+2}c^2d^{2p}\in M$ can be written as $s=uvwrt$, such that

the number of $d$s in $vwr$ is at most $p$ (i.e. we mark all $d$s),
there is at least one $d$ in $vr$, and
for all $q\ge 0$, $uv^qwr^qt\in M$.

From condition 3, $v$ and $r$ each contains at most one character. Together with condition 2, as $q$ grows, the number of $d$s in $uv^qwr^qt$ grows infinitely. To satisfy the condition $z\le x+y-|x-y|-4=2\min\{x,y\}-4$, the number of $a$ and $b$ must both grow, i.e. $a$ and $b$ must both in $vr$. However, $vr$ contains at most two characters, while $d$ is already in it, $vr$ cannot contain both $a$ and $b$, a contradiction.

Now let's come back to $L$. Suppose there is a DPDA $D$ accepting $L$, we create two copies $D_1$ and $D_2$ of $D$ and change the input character $c$ in $D_2$ to $d$. We then construct a new PDA $P$ as follows:

The states of $P$ are the union of states of $D_1$ and $D_2$. The start state of $P$ is the start state of $D_1$. The accepting states of $P$ are the accepting states of $D_2$.
For a transition in $D_1$, if the destination is an accepting state in $D_1$, change the destination to the corresponding state in $D_2$. Other transitions keep unchanged.

Now run $P$ on a string $a^xb^yc^{|x-y|+2}d^z\in M$. According to lemma 1, after reading $a^xb^yc^{|x-y|+2}$, it enters a state in $D_2$ for the first time. Since $a^xb^yc^{|x-y|+2+z}\in L$ according to lemma 1, $P$ will finally accept.

On the other hand, if a string $s$ is accepted by $P$, let $s=s_1s_2$ where after reading $s_1$, $P$ enters a state in $D_2$ for the first time. According to lemma 1, $s_1$ must have the form $a^xb^yc^{|x-y|+2}$ ($x,y\ge 2$). Also, $s_2$ does not contain $c$, and after changing all $d$s in $s_2$ to $c$s, $s_1s_2$ belongs to $L$. This means $s$ must have the form $a^xb^yc^{|x-y|+2}d^z$ where $x+y+|x-y|+2+z$ is even (i.e. $z$ is even) and $|x-y|+2+z\le x+y-2$ (i.e. $z\le x+y-|x-y|-4$). Hence $s\in M$.

As a result, $P$ recognizes $M$, which contradicts to lemma 2.


Time complexity of dequeue function (queues) Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.

MultiDequeue(Q){
     m = k
     while ((Q is not empty) and (m > 0))
     { Dequeue(Q)
       m = m – 1
      }
}

What is the worst case time complexity of a sequence of n queue operations on an initially full
queue having n elements.?

(A) $\Theta(n) $

(B) $\Theta(n+k)$

(C) $\Theta(nk)$

(D) $\Theta(n^2)$

Here suppose we do one dequeue operation, then the loop will run for min(n,k) times. Now remaining 1 operation can be 1 enqueue operation which will take O(1) time so total complexity in this case will be O(min(n,k)).

Suppose we have k=1 and do (n-1) dequeue operations then it will take k*(n-1) time for multideqeue function and remaining one enqueue operation will take O(1) time . So in total we are getting O(kn) time in this case.

I am confused on how to handle 'k' parameter when we are calculating complexity.

NOTE :- n queue operations can be any combination of enqueue/dequeue/multi-dequeue(as defined) operation.

Any help would be appreciated.

It's $\Theta(n)$. Observe that if you are limited by $n$ operations, the total number of elements that ever enter the queue is less than or equal to $n$. Furthermore, every element is processed at most twice: once when it enters the queue, and once when it leaves the queue, therefore the total time is at most a constant times $n$.


Why is "accepted by Turing Machine with even number of states" a trivial property? $$
L = \left\{ \left< M \right>~\middle|~
\small{
\begin{array}{l}
L(M)\text{ is recognized by a Turing Machine} \\
\text{having even number of states}
\end{array}
}
\right\}.
$$

Isn't $L$ same as asking if $L\left(M\right)$ is recursively enumerable (RE)?  How is it trivial?

I know what it means for a property to be trivial, but I don't understand how the above property is trivial and decidable.

All recognisable languages are recognised by a TM with an even number of states, so the property is trivial.

If a language is recognisable, there is (by definition) a TM that recognises it. If it happens to have an even number of states, then you're done. If it has an odd number of states, add another state that doesn't do anything (or duplicates an existing state), then you have a new TM with an even number of states, and are done.


Compute lebesgue measure of set of intervals Let $S = \{ [x_1, y_1], [x_2, y_2], \dots, [x_n, y_n] \}$ be a set of not necessarily disjoint intervals on $\mathbb{R}$. Is there an efficient way to compute the lebesgue measure of the union
$\displaystyle \bigcup_{i = 1}^n [x_i, y_i]$ ?

I present my ideas and approaches as following.

If all intervals of $S$ are disjoint (special case), the problem is trivial and may be solved in time $\mathcal{O}(n)$. The solution is obviously
$\sum_{i = 1}^n y_i - x_i$ .

In the general case, we can remove intersections as long as possible. After this procedure, we apply the special case described above. There raise up two questions:

How to find and remove intersections?
How efficient is this solution in terms of runtime complexity?

Another approach is to sort the intervals of $S$ by $x_i$ or $y_i$. It seems to be a good way to simplify the problem, but does it really help and how? There are several cases we must consider: disjoint intervals, overlappings, intervals completely contained in another, ...

It should be noticed that I am interested in an efficient solution. Can we do in time $\mathcal{O}(n)$ and why or why not?

I appreciate hints and references for further reading as well as solutions.

You can solve this in $O(n \log n)$ time.  Here is an algorithm.  Sort the intervals by their left endpoint ($x$-value), in increasing value.  At each stage, if the first interval is disjoint from the second interval, remove the first interval and add its width to the running total so far.  If they're not disjoint, replace the first two intervals by their union.


Time - Complexity Convex Optimization and Eigen Decomposition Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be?  Is the improvement in speed by many factors!?

Minimizing a convex function $L(X)$ in one matrix variable with orthogonality constraints over the matrix-essentially in my case this ends up to solving an eigen-decomposition.
Minimizing the same convex function $L(X)$ with linear constraints in $X$.

I know that 2.) should be faster. But what is the direction of work I need to do- to compare the improvement in speed-especially in terms of using the fastest available eigen solver for 1.)-what would be the corresponding fastest approach to solve 2.)?

Regarding the eigen-decomposition, often it is enough to just compute the first few eigenvalue/eigenvector pairs. In the case, Krylow-subspace methods can be blazingly fast.

For the convex minimization under linear constraints, the (preconditioned) Uzawa iteration is a typical Krylow-subspace method, which is often not bad. There exist probably more advanced algorithms for this problem now, but http://scicomp.stackexchange.com would be a better place to ask about these.  Also Schur-complement methods, or just parameterization of the linear sub-space might work fine too. And in case the linear constraints is actually a bunch of linear inequalities, a state of the art linear/convex programming solver might be the way to go.


What is a non-contrived example of static type-checking being too conservative? In Concepts in Programming Languages, John Mitchell writes that static type checking is necessarily conservative (overly strict) because of the Halting Problem.  He gives as an example:

if (complicated-expression-that-could-run-forever)
   then (expression-with-type-error)
   else (expression-with-type-error)

Can someone provide a non-contrived answer that would really be a practical concern?

I understand that Java allows dynamically-checked casts for cases like this:

if (foo instanceof Person) {
    Person p = (Person) foo;
    :
}

but I consider the necessity of that more a Java language/compiler deficiency than a cross-language issue.

I've always viewed it more as a matter of convenience, than about whether an algorithm can or can not be expressed at all.  If I really wanted to run programs like Mitchell's contrived one, I'd just write the appropriate Turing Machine simulator in my statically typed language.

The trick with a static type system is to offer the right kinds of flexibility just for the cases where the flexibility allows you to write code that is more easily maintainable.

Here's some examples of program structuring techniques that are sometimes thought to be easier to manage in dynamically than statically typed languages.

Generics and Containers

In statically typed languages before ML (c. 1973) and CLU (c. 1974) it was not difficult to create a red-black tree of strings, a red-black tree of integers, a red-black tree of floats, or a red-black tree of elements of specific type Foo.  It was, however, difficult (maybe impossible) to create a single implementation of a red-black tree that was both statically checked and which could handle any one of these data types.  The ways around the problem were (1) to break out of the type system completely (for example: by using void * in C), (2) to write yourself some kind of macro preprocessor and then write macros that produce the code for each specific type you want or (3) use the Lisp/Smalltalk (and Java) approach of checking the type of the extracted object dynamically.

ML and CLU introduced the notion of, respectively, inferred and explicitly declared (static) parameterized types, which allow you to write generic, statically typed, container types.

Subtype Polymorphism

In statically typed languages before Simula67 (c. 1967) and Hope (c. 1977) it was not possible to both do dynamic dispatch and statically check that you had covered the case for every subtype.  Many languages had some form of tagged unions, but it was the responsibility of the programmer to make sure that their case or switch statements, or their jump tables, covered every possible tag.

Languages following the Simula model (C++, Java, C#, Eiffel) provide abstract classes with subclassing where the compiler can check that each subclass has implemented all the methods declared by the parent class.  Languages following the Hope model (all the ML variants, from SML/NJ through Haskell) have algebraic subtypes where the compiler can check that every typecase statement covers all the subtypes.

Monkey Patching and Aspect Oriented Programming

Dynamic type systems make a variety of prototyping techniques much easier.  In languages where types are represented by hash maps from strings to functions (e.g., Python, Javascript, Ruby) it is quite easy to globally change the behavior of every module that relies on a particular type, simply by dynamically modifying the hash map representing that type.

While there are obvious ways in which monkey patching can be used to make programs harder to maintain, there are also ways in which it can actually be used for "good" rather than "evil".  In particular with aspect oriented programming one can use monkey-patching like techniques to do things like modify the file type to point to a virtualized file system, permitting the construction of unit-testing infrastructures for "free", or modify simple exception types so they print log messages every time they are caught for better debuggability.

Unlike Generics and Subtype Polymorphism where the key static checking ideas were available in the 1970s, static checking for aspect oriented programming is (I think) an active research area.  I don't know much about it except that there's a language called AspectJ since about 2001.


Size of a context-free grammar Is there a formal definition for a size of a context-free grammar? The only definition I have seen so far is on this wiki page:

  The size of a grammar is the sum of the sizes of its production rules, where the size of a rule is one plus the length of its right-hand side.

So, how does one define the size of a production rule's RHS?

For example, if I define my CFG as:

S : A
A : 'a' B | A
B : 'b'

What is the size of the production rule A?

What is your intended application.  The article you cited does give a definition of size.  A production rule

T -> R

has size |R|+1, where |R| is the number of symbols in R.  A more precise definition can be found on page 9 of this document.

This notion of size is meant to compare different grammars that produce the same language.  In particular, in the article you cited, the notion of size is used to see that under grammar transformations, the size of the grammar can explode.


Big-O complexity of sqrt(n) I'm trying to backfill missing CS knowledge and going through the MIT 6.006 course.

It asks me to rank functions by asymptotic complexity and I want to understand how they should be reduced rather than just guessing. The question is to reduce this to big-O notation, then rank it:

$$f(n) = n \cdot \sqrt{n}$$

I see in this answer that $\sqrt{n} \gt \log{n}$

I don't understand how to think about the complexity of $\sqrt{n}$.

What is the complexity class of $\sqrt{n}$?

What is the relationship between $\sqrt{n}$ and $\log{n}$?

$\sqrt{n}$ belongs to the class of sublinear polynomials since $\sqrt{n}=n^{1/2}$.

From Wikipedia (beware of the difference between Little-o and Big-O notations):

  An algorithm is said to run in sublinear time if $T(n) = o(n)$

Note that constant factors do matter when they are part of the exponent; therefore, we can consider $O(n^{1/2})$ to be different from (and less than) $O(n)$.

With respect to the relationship between $log(n)$ and $\sqrt{n}$, you can find here a discussion about why $\log(n) = O(\sqrt{n})$.


Given a regular language, calculate its equivalence classes I was given the following regular language:

For any $n$, the language $L_{n}$ consists of all words over $Σ = \{0, 1\}$ whose $n$th character
from the end is 1.

I know it's regular because it can be expressed as a regular expression ($\Sigma^{*}1\Sigma^{n-1}$), and I constructed a DFA and an NFA for it. I need to calculate its equivalence classes. I thought that the equivalence classes will be words that have 1 in the same place later in the word - for example one of the classes will be $L(\Sigma^{*}1\Sigma^{n-2})$, because no matter what digit will be added to all these words, the new words will belong to the original language. But I'm not sure I'm on the right track. I would love it if I could understand the process of thinking on this kind of question.

Whether a word and its extensions belongs to $L_n$ or not depends on its final $n$ letters (we'll see later what happens if a word is shorter than $n$ letters). Indeed, we can "probe" all of these letters using the following: for $i=1,\ldots,n$, we have $w1^{n-i} \in L_n$ iff the $i$th letter from the end is $1$. This shows that if two words have different length-$n$ suffixes, then they definitely belong to different equivalence classes.

In contrast, we can check that any two words with the same length-$n$ suffix are equivalent. Indeed, suppose $x,y$ are such words, and consider a word $z$. If $|z| \leq n-1$ then $xz \in L_n$ if the $n-i$'th letter from the end of $x$ is $1$. Since $x,y$ have the same length $n$ suffixes, the condition for $yz \in L_n$ is identical. If $|z| \geq n$, then whether $xz \in L_n$ or not only depends on $z$, and in particular holds just as well for $yz \in L_n$.

Finally, what about words which are shorter than $n$ letters? Recall the test we had above: $w1^{n-i} \in L_n$ iff the $i$th letter from the end is $1$. If $|w| < i$ then $w1^{n-i} \notin L_n$, and so $w$ behaves as if the $i$th letter from the end is $0$. Pursuing this route, we find that the equivalence class of $w$ depends on the length-$n$ suffix of $0^nw$, and this definition works whether $|w| \geq n$ or not.


Finite languages are Turing decidable - contradiction Let's say that I define the language $L$ over the alphabet $\{0, 1\}$ to be a language containing only one word, $w$, where:

$$ w =
 \begin{cases}
      1 & \text{if the continuum hypothesis is true}\\
      0 & \text{otherwise.}
  \end{cases}
$$

$L$ is finite, therefore there is a Turing Machine which can decide whether or not the word $1$ is in $L$. On contrary, continuum hypothesis is independent of $ZFC$, which means that it cannot be proven nor disproved from the standard Zermelo–Fraenkel set theory. As a consequence, we cannot know if $1$ or $0$ is in $L$. Then, how can we build a Turing Machine which can decide $L$?

This has been asked before in various guises. The answer is very simple.

If the continuum hypothesis holds, then here is pseudocode for a Turing machine accepting $L$:

Accept if the input equals 1.

If the continuum hypothesis doesn't hold, then here is pseudocode for a Turing machine accepting $L$:

Accept if the input equals 0.

In both cases, we have shown that there exists a Turing machine that decides $L$.

If you're confused, here is a slightly more formal version of your theorem:

  There exists a Turing machine $T$ such that if CH holds, $L(T) = \{1\}$, and if CH doesn't hold, $L(T) = \{0\}$.

Since CH either holds or doesn't hold, one of the following machines accepts $L$: the machine accepting only $1$, and the machine accepting only $0$. In particular, there exists a Turing machine whose language satisfies the requirements.

Perhaps you're confused about the incompleteness result. It states that there is no proof in ZFC of the continuum hypothesis or of its negation. Nevertheless, the continuum hypothesis is either true or false.

More formally, we can think of it in the following way. We live in a "model" of ZFC (model is actually a formal term!), in which every statement (more accurately, every first-order statement in the language of ZFC) has a definite truth value. In particular, in our model either the continuum hypothesis is true or it is false, and we know for sure that one of the possibilities holds, even if we cannot prove either possibility (and so we don't know which one holds).

If you don't like this sort of reasoning, I suggest looking into constructive mathematics and intuitionism, which is what logicians who didn't like this kind of reasoning came up with.


Why can't we sort an Array in O(n) using Fibonacci Heap? If we can insert to a Fibonacci Heap in O(1), and increase-key and find-min in the same W.C time complexity, then why can't we sort an array in time complexity O(n)?

Given an array with n elements:

Find the maximum of the array (largest key) in O(n).
Build a Fibonacci Heap of the elements in O(n), emptying the array in the proccess.
Use find-min and add the result to the now empty array.
Use increase-key on the element you found in step 3, and increase it by the maximum of the old array + 1 (making it now larger than any element of the old array)
Reapet steps 3 and 4, n times. Each time a new element from the old array is added, because all added elements are larger than max+1.

Increase-key is not a $O(1)$ operation on Fibonacci heaps. You're thinking of decrease-key.

Exercise: Why can't increase-key be a $O(1)$ operation on this data structure?


Can all Turing-computable problems be solved with a machine with finite tape and infinite controls? We know all computer computable problems can be solved using the infinite tape and finite control system of the turing machine. Now think something different, let the tape is finite but the control system is infinite. Now can we solve the same set of problems with this machines?

Assuming the tape is always made long enough to hold the input, then infinite control allows you to decide any language at all. The infinite control can just contain one state for each possible string that's been read so far. When it reaches the end of the input, it can accept or reject as appropriate.


How to determine if a regular language L* exists I'm trying to make sense of regular languages, operations on them, and Kleene operations.

Let's say I define a language with the alphabet {x, y}. Let's further say that I place the restriction that there can be no string in the language that contains the substring 'xx'. Thus, my language could be expressed as L = {y, xy, yx}, since that language conforms to the definition.

Could I then argue that there is no language L* since L* could contain LL? That is, can a particular but arbitrarily chosen finite language that conforms to the definition exist, but since LL can't be in L*, L* cannot exist? Or must any L necessarily omit anything preventing L* from existing?

$L^*$ always exists. ${}^*$ is an operation on languages, just like ${}^2$ is an operation on numbers – whenever you have a number $x$, there is a number $x^2$ and, similarly, whenever you have a language $L$, there is a language $L^*$.  Specifically, $L^*$ is the language of all strings that can be made by concatenating zero or more strings from $L$.  That's well-defined for any language $L$.

What you've observed is that $L^*$ might have different properties from $L$.  If we take your example of $L = \{y,yx,xy\}$, we see that no string in $L$ has $xx$ as a substring ($L$ is not the only language with this property but that's beside the point).  On the other hand, $L^*$ includes the string $yxxy$, which does have $xx$ as a substring. That doesn't mean that $L^*$ doesn't exist; it just means that it doesn't have some property that $L$ has. Well, that's no surprise because $L$ and $L^*$ are often different languages, in which case they can't have exactly the same properties.


What are the design issue with today's micro processor I'm just getting started with cs. In school I heard about that modern micro processor are not perfect. So what are the issues? Are does problems related to energy(power draw)/ time /speed(clock speed)? Or is the design faulty?
So if you could design the perfect cpu what would it look like?

There are inherent tradeoffs in targeting a given use. An implementation optimized for one workload, power budget, and cost (at a particular volume of sales) will necessarily be less than optimal for some other use.

Binary compatibility places another constraint on optimization. An ISA which is a good/easy compiler target and which is not strongly tied to a particular set of implementation techniques and technologies will be less than optimal for a given implementation technology (i.e., some optimizations are hindered by the abstraction presented in the ISA) and will sacrifice some benefits in performance, energy-efficiency, etc. for these other goals.

(Redesigning the ISA for every implementation is not a solution, even when using an intermediate-level software distribution format to provide compatibility. The cost and delay of ISA design (including developing an optimizing compiler for the software distribution format) constrains how extensively changes can be made to optimize for particular targets. Even microarchitectures are typically extensively reused because of development costs, including time to market and risk.)

Time to market also constrains optimization. High performance designs targeting new manufacturing processes begin work years before the process characteristics are defined. (This also applies to application targets. Algorithms and use patterns change.) There is also a limited amount of design effort that can be reasonably applied. Even if the value of optimizations could justify the development costs, worse but available products can establish market momentum.


Why is string concatenation not distributive over intersection? Background: This is to be seen in the context of formal languages, very beginner-level.

My professor claims that concatenation is not distributive over intersection, meaning that $L \circ (L_1 \cap L_2) \neq (L \circ L_1) \cap (L \circ L_2)$ and $(L_1 \cap L_2) \circ L \neq (L_1 \circ L) \cap (L_2 \circ L)$.

While it seems silly of me to doubt what he says, I personally have trouble explaining this to myself and am looking for a counter example.

If I concatenate only with the intersection of $L_1, L_2$ it ought to be the same as concatenating first and then finding the duplicates, so to speak.

When we say that concatenation doesn't distribute over intersection, we don't mean that $L(L_1\cap L_2) \neq LL_1 \cap LL_2$ for all languages $L,L_1,L_2$, but rather that this inequality holds for some $L,L_1,L_2$. Here is one example:
$$
L = \{a,aa\}, L_1 = \{a\}, L_2 = \{aa\}.
$$
In this case $L(L_1 \cap L_2) = \emptyset$ but $LL_1 \cap LL_2 = \{aaa\}$.


Is it possible to simulate a CPU with software? I know it sounds a bit silly, but I got really curious. Is it possible to simulate a CPU in, let's say, Python? Some have argued that Minecraft, for instance, allows one to build turing-complete machines, but has some real research been made on this idea? Nested computers? How efficient could that be if made on assembly level? What about a computer matrix?

Yes, its possible to simulate a CPU with software.  A CPU is just an electronic implementation of a large, but finite, number of rules of the form "If this condition is true, modify the state like this" and software can certainly do that. Wouldn't it be surprising if it couldn't? CPUs are designed to support the sorts of things we want to do with software, so it would be very strange if they were radically different.

Indeed any system that has a finite state (i.e., can be described with a finite amount of data) and is manipulated by a finite set of rules can be simulated in software. Going further, I don't think there is any known physical process that can't, at least in principle, be simulated in software.


Solving a modified Travelling Salesman Problem(TSP) I am trying to solve a modified version of the TSP. In my version, multiple visits to a city are allowed, as long as the path is the shortest, and also, only subset of the cities are compulsory to visit, as in, you can go through other cities to visit all the subset cities if path is shorter, but if not, the other cities can be ignored. For simplicity, starting city is fixed. Also, all cities are not connected to others directly. I know approx. solutions for the traditional TSP, but, I have trouble solving this one. A naive approach can be to find all possible combinations of the subset cities and check which has the shortest total path length, but that solution will have a n^2 complexity for trying each combination, plus the complexity for finding shortest path for each two cities. So, what should I use to solve this problem?

As mentioned in the comments, you can compute APSP (All-Pairs Shortest Paths) at first and build the matrix $$D:=\left(d_{ij}\right)_{i,j\in[n]}$$, where $d_{ij}$ is the length of a shortest path from the vertex $i$ to the vertex $j$. By solving the usual travelling sales man on the graph $G'$ where $D$ is the adjacency matrix, you get a solution for your version of the problem. Try to see why this works as an exercise.

Your case is actually mentioned in the Wikipedia page under metrics.

Note that $D$ defines a metric and metric TSP admits a polynomial time 1.5-approximation. The same Wikipedia article contains more information about this algorithm under the section "Constructive heuristics".


An argument for error accumulation during complex DFT I am doing FFT-based multiplication of polynomials with integer coefficients (long integers, in fact). The coefficients have a maximum value of $BASE-1, \quad BASE \in \mathbb{n},\quad BASE > 1$.

I would like to put forward a formal argument that if we use complex DFT for computing a convolution on a physical machine, it will yield incorrect results at some transform length $n\in \mathbb{N}$.

What was easy to prove was the fact that at some big $n$ computing the convolution with DFT will not at all be possible, since, for example, the following difference of primitive roots modulo $n$:  $\omega_n^1 - \omega_n^2 \rightarrow 0$ when $n \rightarrow \infty$, and if we are restricted by some machine epsilon $\epsilon$, at some $n$ it will make the values indistinguishable and interpolation impossible.

But the boundary I've received using such an argument was way too big: only for $n=2^{60}$ I've received $\omega_n^1 - \omega_n^2$ that had both components, $Re$ and $Im$, less than representable by $double$-precision type. This certainly is a boundary, but not very practical one.

What I would like to show (if it is possible), is that much earlier than interpolation becomes theoretically impossible, the round-off errors will start to give wrong coefficients in the convolution, so that

$$a\cdot b \neq IDFT(DFT(a)\times DFT(b)),$$

where $DFT$ and $IDFT$ are algorithm implementations that I use to calculate the Fourier transform.

Maybe it is possible to make use of the fact that the value of the primitive root modulo $n$, $\omega_n = \exp(-2\pi i / n)$, is an irrational number for the majority of $n$'s. It will thereby be computed with inevitable error $\psi$, defined as the value needed to "round off" everything that's less than the machine epsilon $\epsilon$. Thus all the values used for DFT,

$$\omega_n^0, \omega_n^1, ..., \omega_n^{n-1},$$

except for $\omega_n^0$ will also be computed with errors.

Since I'm not a good mathematician at all, I don't know if and how I could use this fact to prove that the situation is going to worsen with increasing $n$ and that eventually the convolution is going to be computed incorrectly.

I would also like to have and argument for OR against the following claim: for fixed $n$, the maximal error will be produced when all the coefficients of both polynomials are $BASE-1$.

Thank you very much in advance!

Since the fourier coefficients might in general be complex numbers $xi + y$ with $x$ or $y$ or both irrational, a standard finite precision computer of course will not output the exact fourier coefficients. However, if you want to claim that you cannot get a good approximation, you are wrong.

Look at this answer. Markus shows that if you want to compute DFT of a vector of length $n$ up to $b$ bits of precision, then you need floating point numbers with $m$ bits where $m = \log n + \log \log n + b + C$ for $C$ some fixed constant. This is a fairly good bound. Also, there is no reason why the double type of the C language should be any hard limitation if you care about precision: there are libraries for high-precision arithmethic, and it's not even all that hard to code your own procedures to multiply and add floating point numbers of fixed high (higher than that of double) precision. Markus's answer shows that you won't lose much in running time: the running time will be roughly $n \log n (b/\log n)$ (for $b > \log n$) arithmetic operations on standard C types.


Maximizing the weighted average value of a set of items by doubling the weight of a subset of items Given a set of $n$ items, each represented by $t_i=(w_i,v_i)$ for $1 \le i \le n$, the weighted average value of those items is defined as:
$$
\frac{\sum_{i=1}^{n}v_iw_i}{\sum_{i=1}^nw_i}
$$

The goal is to find a subset of items to double their weight, such that the weighted average value is maximized.

For example, suppose you have the following set of items, where $t_i = (w_i,v_i)$:

$$
t_1 = (12, 1100000)\\
t_2 = (12, 1000000)\\
t_3 = (12, 850000)\\
t_4 = (10, 800000) \\
t_5 = (8, 1200000)
$$
The weighted average value is 981,481. The best solution is to double the weight of items 1 and 5, which leads to a new weighted average of 1,024,324.

I am trying to come up with an algorithm to find the best subset of items to double, and so far I've tried using bruteforce. For each item, you can choose to either double it, or leave it as it is. This means that there are a total of $2^n$ possibilities to explore, which means exponential complexity. I've also tried a greedy algorithm to pick the highest value-to-weight ratio items, and determine the best number of items to pick, however this solution is not always optimal.

I am wondering, what is the most efficient algorithm to find the best subset of items to double their weight?

Thanks in advance.

This can be solved in polynomial time.

Hint: consider the decision version of the problem.

   Suppose I gave you a value $\alpha$ and asked you whether it's possible to find a subset of items so that the weighted average is at least $\alpha$.

Could you solve that version of the problem?  Does this give you any ideas about how to solve the original problem?

Alternate hint:

   Keep trying other greedy strategies.  You've tried one greedy algorithm, but there might be other plausible greedy algorithms.


Decision Tree Learning Deviation - Russell and Norvig I am working through the Russell and Norvig AI book and came across the following on the top of page 706.

The section concerns Decision Tree pruning and testing a given attribute against the null hypothesis. The example at hand deals with a binary decision tree and $p_k$ denotes the number of positive ("yes") responses in the training data and $n_k$ the number of negative ("no") responses in the training data with respect to the training examples that are in the subset of values that took on the value $v_k$ associated with the $k$th attribute of a vector $\vec{x}$ of length $n \times 1$. Furthermore $p$ and $n$ simply denote the number of positive and negative outputs of the training data.

The authors state the following:

  We can measure the deviation by comparing the actual numbers of positive and negative examples in each subset $p_k$ and $n_k$ with the expected numbers
  $\hat{p}_k$ and $\hat{n}_k$, assuming true irrelevance:

  \begin{align*}
\hat{p}_k&=p\times \frac{p_k+n_k}{p+n}\\
\hat{n}_k&=n\times \frac{p_k+n_k}{p+n}\,.
\end{align*}

  A convenient measure of the total deviation is given by

  $$\Delta = \sum_{k=1}^d \frac{(p_k-\hat{p}_k)^2}{\hat{p}_k} + \frac{(n_k-\hat{n}_k)^2}{\hat{n}_k}\,.$$

My questions:

I think I understand the use of the estimators. We are basically assuming a uniform distribution on $p$ and $n$ and so within each subset of training examples that have the attribute value $A_k$ equal to $v_k$ we simply scale the overall $p$ and $n$ by the total proportion of samples in that set. In essence, we are assuming that, for instance, if $p=10$ and $n=5$, then those proportions hold in our subsets, and so the expected value of $\hat{p}_k$ is simply scaled by the size of the subset.

This leads me to also understanding the numerator of the measure of deviation $\Delta$. We use the squared deviation of the expectation from the observed value. My question then is why do the estimators appear in the denominator? This seems very close to an equation for variance, and I assume that the estimators are somehow scaling $\Delta$, but how can we justify that?

TL;DR: They are basically doing a chi-squared test to compare the distributions.

In more detail: Let's break this down into two parts, $\Delta = \Delta_1 + \Delta_2$ where

$$\begin{align*}
\Delta_1 &= \sum_{k=1}^d \frac{(p_k-\hat{p}_k)^2}{\hat{p}_k}\\
\Delta_2 &= \sum_{k=1}^d \frac{(n_k-\hat{n}_k)^2}{\hat{n}_k}.
\end{align*}$$

Then $\Delta_1$ is the test statistic for a chi-squared test of the goodness of fit between the two distributions $p_k$ and $\hat{p}^k$.  Similarly, $\Delta_2$ is the test statistic for the goodness of fit between $n_k$ and $\hat{n}_k$.

If the distribution $p_k$ is similar to $\hat{p}_k$, and $n_k$ is similar to $\hat{n}_k$, then $\Delta$ will be small (the former means that $\Delta_1$ will be small, and the latter means that $\Delta_2$ will be small).  Conversely, if $p_k$ is not similar to $\hat{p}_k$, or $n_k$ is not similar to $\hat{n}_k$, then $\Delta$ will be large (in the former case, $\Delta_1$ will be large; in the latter case,  $\Delta_2$ will be large).

So this is a convenient measure of the total deviation between these distributions: a convenient way to get a single number to help us measure the extent to which both $p_k$ is similar to $\hat{p}_k$  and $n_k$ is similar to $\hat{n}_k$.

The chi-squared test is a standard test for goodness of fit, so its test statistic is a reasonable choice here.  As for why the chi-squared test  is a good test for measuring goodness of fit, you can read the standard literature on the chi-squared test.


Time Complexity of Basic Primality Test Algorithm The algorithm I'm referring to is one of the most fundamental primality checks: For a number, $n$, check if it is divisible by some odd number, $k$, less than or equal to $\sqrt{n}$. Assume $n$ is a fixed size and that all basic arithmetic operations (add, subtract, multiply, divide, remainder) run in $O(1)$. I don't see why this algorithm will not be $O(\sqrt{n})$, but apparently it's not since PRIMES was considered an NP problem up until the AKS primality check.

The problem with your statement is that you assume that all the basic arithmetic operations are $O(1)$ and that the amount of numbers you will have to check is $O(\sqrt{n})$, relative to the size of the input.

This is wrong because $\text{PRIMES}$ is the language of all the prime numbers, given in a binary format. So an input of length $n$ will be a number of size $O(2^n)$. Then, if the input is some number $x$, in order to check all the numbers up to $\sqrt x$ you will have to go over $O(\sqrt{2^n})$ numbers, which is $O(2^{n/2})$ numbers. Even with $O(1)$ operations this will not take a polynomial amount of time.


Linear Regression using a Neural Network I am trying to create a regression model using a Neural Network. I am currently learning how to work with neural networks (deeplearning.ai) and so the model is not implemented using any existing frameworks like keras.

Based on what I have learned,

the model is configured to use no activation function in the output
layer (which, obviously, has only one node).
Input is images of fashion articles (shirt, jackets etc).
output predicts prices for input article images.
Hidden layers all use ReLU.
Random initialization is done for all weights.
Cost function is Mean Squared Error:
$$J = \frac{1}{2m}\sum_{i=1}^m (a^{(i)} - y^{(i)})^2$$

Based on the formula for backpropogation, the last layer should get the error based on cost function. For a single example, we have:
$$ \mathcal L =  \frac{1}{2}(a - y)^2 $$
$$ error = \frac{d\mathcal L}{da} = (a - y) $$

where L is the loss function, a is the predicted value and y is the actual price of the article.

For the entire training set, we have (vectorized):
$$ error = \frac{d\mathcal L}{dA} = (A - Y) $$
where m is the number of examples,  A, Y are (1 * m) vectors where each value corresponds to each single example. A contains m predictions and Y has all the m prices.

Is this error value correct?

My problem is that the model converges to a what appears to be a local minima. The error after a few 100 iterations gets stuck. The error is also not very small (~ 0.0005). I am not sure if I have the equations right.

No.  This is not the correct way to train such a network.  To update the network, we want to update the weights of the network.  Thus instead of using $\frac{d\mathcal L}{dA}$ to update the weights, you should be using $\frac{d\mathcal L}{dW}$, where $W$ are the weights.  This could be computed as

$$\frac{d\mathcal L}{dW} = \frac{d\mathcal L}{dA} \times \frac{d\mathcal A}{dW},$$

where $\frac{d\mathcal L}{dA}$ is computed using the formula you obtained ($\frac{d\mathcal L}{dA} = A-Y$ is correct), and where $\frac{d\mathcal A}{dW}$ is computed using backpropagation through the network.

Or, better yet, use an existing framework that performs automatic differentiation for you (e.g., Keiras, Tensorflow), and save yourself a lot of effort.


Is it possible to modify the linux assembler in order to modify what fuctions do? I was wondering if it were possible to modify the linux assembler in order to change the function of "-" to "+" and vice versa.
I was also wondering if this would affect the whole system making it collapse. I apologize if this question is not appropriate here. Please explain why if it is the case.

E.g:
2+2 = 0
2-2 = 4

My objective is to see what applications this could have for a potential computer virus (I hope this is allowed here).

While this is trivially possible, the fundamental flaw in your idea is that assemblers are not interpreters. Python programs are run by the Python interpreter, Swapping - and + in the Python interpreter would likely crash all Python programs. But normal programs are executed directly by the CPU. The assembler is not involved in their execution.


Find the longest contigous subsequence where each pair's difference is at most p Given input sequence $x_1,...,x_n$, find the longest contigous subsequence $x_i,... x_l$ where each pair $(x_j,x_k)$ satisfies that $|x_j - x_k| \le p$.

I have come up with simple $\mathcal{O}(n^2)$ solution.

I'm sure there is a better way so I'm looking for $\mathcal{O}(n)$ or at least $\mathcal{O(n \log n)}$ solution. Thanks for any help!

You can solve this in $O(n\log n)$ using a Range Minimum Query data structure. This is a data structure that given two indices $i \leq j$ return $\min(x_i,\ldots,x_j)$. We can construct a data structure that answers such queries in $O(1)$ time using $O(n\log n)$ preprocessing. The idea is to compute $\min(x_i,\ldots,x_j)$ for every pair $i \leq j$ such that $j-i+1$ is a power of 2. This can be accomplished in time $O(n\log n)$ using the identity
$$\min(x_i,\ldots,x_{i+2^{\ell+1}-1}) = \min\bigl(\min(x_i,\ldots,x_{i+2^\ell-1}),\min(x_{i+2^\ell},\ldots,x_{i+2^\ell+2^{\ell}-1})\bigr). $$
Using this information, we can compute each range minimum query as follows. Given $i\leq j$, let $2^\ell$ be the largest power of 2 such that $2^\ell \leq j-i+1$; we assume that we can compute $\ell = \lceil \log_2 (j-i+1) \rceil$ in constant time. Then
$$
\min(x_i,\ldots,x_j) = \min\bigl(\min(x_i,\ldots,x_{i+2^\ell-1}), \min(x_{j-2^\ell+1},\ldots,x_j)\bigr).
$$

For each $i$, we use binary search to compute in time $O(\log n)$ the maximal $\ell \leq i$ such that $\min(x_\ell,\ldots,x_i) \geq x_i-p$ and the minimal $r \geq i$ such that $\min(x_i,\ldots,x_r) \geq x_i-p$. Thus $x_\ell,\ldots,x_r$ is the largest interval satisfying your constraint in which $x_i$ is the maximal point. Taking the maximum of $r-\ell+1$ over all $i$ reveals the solution to your task.


How can a one-counter machine accept $a^n b^n c^n$? It is mentioned in Which languages are recognized by one-counter machines?
that a one-counter machine can accept $\{a^n b^n c^n\mid n\geq 0\}$. Can someone please explain how this is done?

Be careful where the hyphens are! One counter-machine can recognize $a^n b^n c^n$, but a one-counter machine cannot.

From the answer you linked to:

  Languages recognized by one[-]counter automata form a proper subset of the context free languages.

(There's a proof for this, but it's long and boring, so I'm going to leave it out; you can find it online if you're interested.)

Since $a^n b^n c^n$ is not context-free, it cannot be recognized by a one-counter automaton.

It can, however, be recognized by a two-counter machine (a machine with two counters). The basic structure goes something like this:

When you see an $a$, increment $X$, increment $Y$
When you see a $b$, decrement $X$
When you see a $c$, decrement $Y$
Accept iff the letters are in the right order (a trivial state machine), AND $X = 0$, AND $Y = 0$

This is "one counter-machine" (in the sense that it's a single machine using counters). But you need at least two counters to do it.


Bottom-Up Parser With Leftmost Derivation I'm reading the book Parsing Techniques by Dick Grune et al. and in section 3.1.3 "Linearization of the Parse Tree" they introduce the notion of linearization:

  [...] a parser can produce a list of rule numbers instead, which means that it linearizes the parse tree. There are three main ways to linearize a tree, prefix, postfix and infix.

Those are explained using the following grammar:

and this particular production tree (the grammar is spuriously ambiguous):

(The numbers at the nodes are semantic attributes.)

Prefix notation is explained first:

  In prefix notation, each node is listed by listing its number followed by prefix listings of the subnodes in left-to-right order; this gives us the leftmost derivation [...]:

  leftmost: 2 2 1 3c 1 3e 1 3a

Postfix notation follows:

  In postfix notation, each node is listed by listing in postfix notation all the subnodes in left-to-right order, followed by the number of the rule in the node itself; this gives us the rightmost derivation [...]:

  rightmost: 3c 1 3e 1 2 3a 1 2

Before the linearizations, there is a "leftmost" and "rightmost," respectively. Does that mean prefix notation only works with top-down and postfix notation with bottom-up parsing? But then why? If we start from the rightmost non-terminal and build the parsing tree from the top down, wouldn't the linearization with the "leftmost" in front be the result? Aren't the notations semantically independent?

Furthermore, I've read about LL and LR parsers, which yield a leftmost or rightmost derivation and use a top-down or bottom-up algorithm, respectively. Does that mean a bottom-up parser can only work with a rightmost derivation? Why not with a leftmost one? I don't see the problem with that, similarly to how prefix notation seems to imply a leftmost derivation.

"Linearizing" here is equivalent to superimposing a total ordering on what is a partial order. If your grammar is context-free, this partial order can always be conveniently represented by a tree. Other types of grammars will be able to produce derivations orders that are not tree-like, and that is why we generally avoid them.

This total order is meant to allow for sequential algorithms to be written, because the input will be read sequentially. That's all, no magic here.

What happens is that different criteria for linearization will serve different algorithms: if you are going to reduce the input, you will go "from the bottom up", metaphorically, so the linear order that suits you (if you are reading the input left-to-right - because your language has an indo-european flavor), is postfix. If not, prefix.


Finding the perimeter of a simplex I hope this question is close enough to CS to be posted here. I need to write a method that will compute the perimeter of a simplex
https://en.wikipedia.org/wiki/Simplex in any dimension given only the coordinates of its vertices. Is such a function even possible? I have tried going for it, but ended up with loads of nested loops and nothing functional. Right now I have a class named Point and a class named Simplex which constructs a Simplex from an array of these points. Any help is appreciated.

Solved it, my question was badly formulated, I had only coordinates of points not the vertices themselves, I have calculated the perimeter using the euclidean distance formula.


Closure of regular languages to shuffle using closure operations Given a language:
$L = \{\; a_1b_1a_2b_2a_3b_3\dots a_nb_n \mid \forall i: a_i,b_i \in \Sigma,  a_1\dots a_n \in L_1\ ,  b_1\dots b_n \in L_2 \;\}$

Also $L_1, L_2$ are regular languages.

Using closure only (homomorphism) prove that L is also regular language.

I think there can be a mapping $h\colon (L_1 \cup L_2) \to \Sigma$, then use $h^{-1}(\Sigma)$  in order to show regularity. I'm a bit stuck over here.

The idea is to create two copies of the alphabet $\Sigma$, say $\Sigma_1,\Sigma_2$; each $\sigma \in \Sigma$ corresponds to $\sigma^{(i)} \in \Sigma_i$. You now show that the following languages are regular:
$$
\begin{align*}
\tilde{L}_1 &= \{a_1^{(1)}b_1^{(2)}\ldots a_n^{(1)}b_n^{(2)} : a_1 \ldots a_n \in L_1 \}, \\
\tilde{L}_2 &= \{a_1^{(1)}b_1^{(2)}\ldots a_n^{(1)}b_n^{(2)} : b_1 \ldots b_n \in L_2 \},
\end{align*}
$$
where in both cases only some of the letters are constrained. Now take $\tilde{L}_1 \cap \tilde{L}_2$ and transform it to $L$.

I leave the rest of the details for you to complete.


Can you create a deterministic PDA for non-palindomes? Using non-determinism to create a PDA to recognize non-palindromes is easy.

My first instinct was to say yes, but it would be extremely complicated. After thinking about it, I don't think you could.

The language of palindromes isn't DCFL, see for example this question, which proves this for the closely related language of even length palindromes. Since DCFL are closed under complementation, it follows that your language is not DCFL.


Computational Complexity of Integer Linear Program [with Fixed number of 'Pure Constants'] This is a follow up to the previous Question: Conditions for Linear Diophantine Equations to always have a solution

It was established in the above's answer that obtaining or testing for the existence of an solution of an ILP in $\mathbb N$ is an NP Hard Problem. This in turn makes obtaining solution for a (LDP) Linear Diophantine Problem (where $v$ > $n$) in $\mathbb N$ an NP-hard Problem too.

Now given the restricted ILP Problem with an additional constraint:

The number of unique pure constants (i.e. ones without variables, denoted by $c_0 below) permitted in any system has an fixed upper Bound (say 2) where equations are of the form:

$c_0 + c_1 x_1 + \dots + c_k x_k \ge 0$

Is this restricted version of ILP still NP-hard?

Yes, it's still NP-hard.  Suppose the two allowed values for $c_0$ are 0 or 1, and that you're allowed to have equations of the form

$$c_0 + c_1 x_1 + \dots + c_k x_k = 0$$

as well (not just inequalities).  Suppose that we wish we could use the constant 17.  We can introduce new variables $z_1,\dots,z_6$, add the equalities below, and replace all occurrences of 17 with $z_6$.

$$\begin{align*}
1 - z_1 &= 0\\
0 + 2 z_1 - z_2 &=0\\
0 + 2 z_2 - z_3 &=0\\
0 + 2 z_3 - z_4 &=0\\
0 + 2 z_4 - z_5 &=0\\
0 + z_1 + z_5 - z_6 &=0
\end{align*}$$

Notice how the above equations force $z_1=1$, $z_2=2$, $z_3=4$, $z_4=8$, $z_5=16$, and $z_6=17$.

Of course there's nothing special about 17; you can do this for any other number as well.  In general, if you have any constant $\kappa$  you wish you could use, you can find an addition chain for $\kappa$, then use that to introduce temporary variables $z_1,\dots,z_t$ that force $z_t=\kappa$, then replace all occurrences of the constant $\kappa$ with the variable $z_t$.

In this way you can eliminate all constants other than 0 or 1 for $c_0$.  The length of the addition chain for $\kappa$ will be at most $2 \lceil \lg \kappa \rceil$, so the number of extra variables and equalities added is not too large (and in particular is polynomial in the size of the original problem), so this increases the size of the instance by at worst a polynomial factor.


What is the complement of a language? If given any language L, how do I find the complement of said language?

I lack the basic understanding required to determine if a language is co-recognizable. I understand that a language, $L$, is co-recognizable if the complement of that language, $\overline{L}$, is recognizable.

But given a specific language, I have a hard time figuring out what the actual complement is, and can thus not figure out if that complement is recognizable. An example problem is:

  Is the following language co-recognizable?
  $L$ = {$<M>$ | $M$ is a
  turing machine, and $1010 \notin{L(M)}$}

Remember that a language is defined as a set of strings. The complement of a language is thus the complement of that set, defined in the usual way: everything not in the set.

In practice, when talking about the complement of a language, there's usually a particular alphabet you're interested in (which you can infer from context). If all else fails, assume $\{0,1\}$.

So in this case, the complement of that language is:

  The set of all binary strings $s$, such that either $s$ isn't a valid encoded Turing machine, or the machine encoded by $s$ accepts $1010$.

Hint: the problem of whether a string $s$ is a valid encoded Turing machine or not is known to be decidable. So you only need to worry about the second clause.


How are binary trees represented on disk Assume I have a word document, the contents in it are stored on the disk as bits. Nothing so complex here. When the word processor reads those bits, it just knows how to display on screen.

But what about binary trees. They are just not data, they have route node, child nodes. How are they actually represented on disk?

I tried searching using this term "binary trees representation on disk". But I didn't find anything useful.

Let me know if I am not clear

Update:
I was looking for details on how actually they are stored on disk. Given this simple binary tree:

Any data is stored in bits on disk. How are these stored?

This may not be an exact answer but some information of interest related to your question

Other answers have mentioned various ways in which the binary data structure can be represented and you might want to use one of them but mostly when using databases the Adjacency List Model and Nested Set Model are used for representing Binary Trees.

Binary Trees are mostly not used for storing data on disk and some alternatives are usually preferred.If you are interested in optimized data access, search,insertion and deletion  on disk then you may want to consider these alternatives

B-Tree data structure is one of the alternatives used for storage on disk.It provides search, sequential access, insert, and delete  operations in logarithmic time and is optimized for disk storage.

B-Tree data structure was created by Rudolf Bayer and Ed McCreight in 1972 to  overcome a shortfall of Binary Tree i.e. using too many disk reads.B-Tree reduces the number of disk reads by allowing more keys in a single node ( typically making a B-tree node as large as the sector minimizes the number of access times).

SQL Server uses a further optimized extension of B-Tree data structure known as B+Tree in which only the leaf nodes hold the actual data and the rest of the nodes are pointers.

According to Wikipedia B+Trees are also used for storing directory structures by some filesystems:

  The ReiserFS, NSS, XFS, JFS, ReFS, and BFS filesystems all use this
  type of tree for metadata indexing; BFS also uses B+ trees for storing
  directories. NTFS uses B+ trees for directory and security-related
  metadata

Update
How will a tree be represented as bits on the disk?

Trees can be represented by using static data structures like arrays  in a  fashion similar to this,consider each row tag as an array

//Node A can be represented as

[row 1][node A data in bits][separator bits]
[pointer to B i.e row 2][separator bits]
[pointer to C i.e. row 3][row1end]

//Node B can be represented as

[row 2][node B data in bits] [separator bits]
[no child flag][separator bits][no child flag][row2end]

//Node C can be represented as

[row 3][node C data in bits] [separator bits]
[no child flag][separator bits][no child flag][row3end]

I'd recommend studying some file formats so that you know how to represent logical data in a file, this also might be helpful

dcs.gla.ac.uk/Keith/Chapter.4/Ch.4.html


Number of solutions to linear system of equations over GF(2) Linear systems of equations over the reals have either 0, 1 or infinitely many solutions. However, when applied to finite fields (specifically GF(2)), infinitely many is not an option.

Is there a fast general method to calculate the number of distinct solutions to a linear system of equations over GF(2)?

You can assume that Gaussian elimination has already been performed, so an example augmented matrix would be:

$$ \left[
    \begin{array}{ccccccccc|c}1&0&0&0&1&1&1&0&0&1\\
0&1&0&0&1&0&1&0&1&1\\
0&0&1&0&0&1&1&1&0&0\\
0&0&0&1&1&1&1&1&1&1\\
0&0&0&0&0&0&0&0&0&0\\
0&0&0&0&0&0&0&0&0&0\\
0&0&0&0&0&0&0&0&0&0\\
0&0&0&0&0&0&0&0&0&0\\
0&0&0&0&0&0&0&0&0&0\\
    \end{array}
\right] $$

You can take any subset of the free variables, and then correct any resulting sum using the fixed variables.

Thus, after Gaussian elimination the total number of solutions is  $2^f$ where $f$ is the number of free variables.


How is PowerPoint Turing complete? From my understanding, Turing complete means that the program or machine can complete any computation that a Turing machine can complete, which to me means any computation. So how can something like HTML or PowerPoint be Turing complete?

Some system is Turing complete if you can simulate every Turing machine inside of it. Powerpoint is Turing complete because its animation features can be used to simulate a Turing machine. This video explains the proof for Powerpoint. You can read the proceedings from the 2017 SIGBOVIK for a written explanation.


How to find the minimum number of vertices whose removal make the graph disjoint Given a graph $G = (V,E)$.

Is there any algorithm which finds the minimum number of vertices to be removed from $G$ so that every vertex in the graph becomes disjoint, i.e., every vertex is disconnected from every other vertex?

This problem is known as vertex cover.  The minimum vertex cover of a graph is the smallest number of vertices adjacent to every edge.  The complement of a vertex cover is an independent set.

Given a graph $G = (V,E)$ and $k \in \mathbb{N}$, the problem of finding whether $G$ has a vertex cover of size at most $k$ is NP-complete.  However, it admits a polynomial kernel and is thus fixed-parameter tractable.  It also admits a quite easy and nice $2^k n^{O(1)}$ branching algorithm:

Pick any edge $e = vu$:  Either $v$ goes to the vertex cover, or $u$ goes to the vertex cover.  Make a recursive algorithm which picks $e$, removes $v$ from the graph and calls itself recursively with $k-1$ as parameter.  If that fails, proceed by removing $u$.  If that fails as well, can conclude that there is no such vertex cover.

There are also nice 2-approximation algorithms for this problem.

Ps.  this is maybe one of the "easier" NP-hard problems.  So if you want to implement it, you're in good luck despite the hardness.

Pps.  if you want to find an independent set (also known as stable set) of size at least $k$, you are out of luck, as that problem is $W[1]$-complete, see the W-hierarchy.  However, there is an $O(2^{0.288n})$ exact algorithm solving independent set using Measure and Conquer by Fomin et al. (SODA 2006) (doi=10.1.1.79.831).  A quick caveat here:  Many are confused upon first reading why a trivial reduction does not show that independent set is in FPT as well.  The answer here lies in the fact that a reduction will set the new parameter $k' = O(n-k)$, i.e., the new parameter will depend on $n$ as well.


Mergesort with $O(n^2 \log n)$ runtime I have a task where i need to find a problem in which mergesort has to have a runtime of $O(n^2 \log n)$. In our lecture we said that the runtime is $O(n \log n)$ assuming that every comparison is $O(1)$. I think that I have to work with comparison-complexity but I dont know how to create a runtime of $O(n^2 \log n)$ since mergesort has best and worst-case complexity of $O(n \log n)$. Could anybody help me out creating a problem to achieve a runtime of $O(n^2 \log n)$ ?

Remember what $O(\cdot)$ means. You don't need to do anything. Mergesort has a running time of $O(n\log n)$ which is already $O(n^2 \log n)$, $O(2^n)$ and $O(\text{any larger function you want})$.


Max subarray product Is it possible to solve the max sub-array product problem using divide and conquer?

Given an integer array numbers, find the contiguous sub-array within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Yes, you can obviously solve it like that.

If you are dividing the array into two parts, than the maximal sub-array can be completely in the left half, completely in the right half, of it starts in the left and ends in the right half.
The first two cases you will find using the recursive calls.
For the third case, you have to do a little bit of work:

In that case the maximal subarray consists of two parts, a suffix from the left half of the array, and a prefix of the right half of the array. Either both products are positive, or both negative. It's obvious that you want their absolute value as big as possible, therefore you need to know the largest and smallest suffix from the left half, and the largest and smallest prefix from the right half. You can compute both in $O(n)$ time, which gives you the recurrence relation $T(n) = 2 T(\frac{n}{2}) + O(n)$ which gives you $T(n) = O(n \log n)$ by the master theorem.

Notice, you can also compute these values during the recursive calls, which gives you $T(n) = 2 T(\frac{n}{2}) + O(1)$, and this gives you the final complexity $T(n) = O(n)$.


Deriving lower and upper bounds for T(n) = T(n-1) + T(n-2) + 10 The solution is to find the upper and lower bounds from:

2T(n-2) < T(n) < 2T(n-1) + 10

So I have to find

T(n) > 2T(n-2)

and

T(n) < 2T(n-1) + 10

My question about this solution method is not how to solve those recurrence relations. It's about why this method can be used in the first place. I thought solving a recurrence relation is about finding the precise runtime and not about finding the approximate runtime between its lower and upper bounds. Is there a way to solve the recurrence relation without using this method and finding out the precise runtime?

The goal of a recurrence relation is to make a complicated problem easier to think about, which is very general. It allows us to express a function in terms of itself, but still reason about what the value of the function for an input is.

Sometimes you care about the exact value of the function, in which case you'd prefer to rewrite it in an exactly equivalent way (or just plug in a number and follow the recursion chain until you have your answer).

Other times, you're just worried about the extreme "if my worst enemy plugged a value into this function, what would it do?" case.

Rewriting the equation as an inequality let's us remove an entire recursive call of the function, which makes doing substitutions to figure out an easier to reason about form of the function a more achievable goal.

So yes, $T(N) = T(N-1) + T(N-2) + 10$, may exactly describe the run time of your program, or the amount of money in my bank account after $N$ days (I wish), but we don't care about that precision, because $T(N) < 2T(N-1) + 10$ is an upperbound, and we just want to know that our program will finish before the heat death of the universe, or that I have enough money in my bank account for dinner.

Note the benefit here. Perhaps because your algorithm had a recursive nature to it, it might have been really easy to come up with the $T(N) = T(N-1) + T(N-2) + 10$ description of the run time. Easy to come up with, but hard to think about what the function actually means. So now that we have this building block, we come up with an upper bound (that we know is true), but has less recursion (which our brains don't like). This is nice on its own, but it also let's us continue to expand the recursive definition until we understand the underlying pattern, and can remove the recursion completely.


Number of distinct substrings in a string From what I have come to understand, the best way to implement it is to use the suffix  array $S$ of the string $w$ and its LCP-array (Longest Common Prefix) $L$.

The answer can be obtained by

$$ \sum_{i=1}^{|w|} \left( |S[i]| -L[i-1] \right).$$

What I don't get is how and why is this working?

I would be very grateful if someone explained this.

Instead of a formal proof, I want to give some intuition behind the formula. The suffix array contains all the suffixes of the string $w$. A substring is nothing else than a prefix of a suffix. So if you count $\sum_i |S[i]|$, you will get all the substrings, but of course you overcount the number of different substrings.

Let's have a closer look. Assume the $S[i-1]=xyz$ and $S[i]=xyxyz$. By the above counting method the entry $S[i-1]$ counted the substrings $x,xy$ and $xyz$ and the entry $S[i]$ counted $x,xy,xyx,xyxy,xyxyz$. You will notice that since the prefixes of length 2 of both entries are the same we have double counted $x,xy$. But the length of the longest common prefix is stored in $L[i]$ so we subtract it to compensate for the overcounting.