Randomized Selection The randomized selection algorithm is the following:

Input: An array $A$ of $n$ (distinct, for simplicity) numbers and a number $k\in [n]$

Output: The the "rank $k$ element" of $A$ (i.e., the one in position $k$ if $A$ was sorted)

Method:

If there is one element in $A$, return it
Select an element $p$ (the "pivot") uniformly at random
Compute the sets $L = \{a\in A : a < p\}$ and $R = \{a\in A : a > p\}$
If $|L| \ge k$, return the rank $k$ element of $L$.
Otherwise, return the rank $k - |L|$ element of $R$

I was asked the following question:

  Suppose that $k=n/2$, so you are looking for the median, and let $\alpha\in (1/2,1)$
  be a constant.  What is the probability that, at the first recursive call, the
  set containing the median has size at most $\alpha n$?

I was told that the answer is $2\alpha - 1$, with the justification "The pivot selected should lie between $1−\alpha$ and $\alpha$ times the original array"

Why? As $\alpha \in (0.5, 1)$, whatever element is chosen as pivot is either larger or smaller than more than half the original elements. The median always lies in the larger subarray, because the elements in the partitioned subarray are always less than the pivot.

If the pivot lies in the first half of the original array (less than half of them), the median will surely be in the second larger half, because once the median is found, it must be in the middle position of the array, and everything before the pivot is smaller as stated above.

If the pivot lies in the second half of the original array (more than half of the elements), the median will surely first larger half, for the same reason, everything before the pivot is considered smaller.

Example:

3 4 5 8 7 9 2 1 6 10

The median is 5.

Supposed the chosen pivot is 2. So after the first iteration, it becomes:

1 2 ....bigger part....

Only 1 and 2 are swapped after the first iteration. Number 5 (the median) is still in the first greater half (accroding to the pivot 2). The point is, median always lies on greater half, how can it have a chance to stay in a smaller subarray?

Suppose your array has $n$ elements.  As you have noted, the median is always in the bigger part after the first partition.  The bigger part has size at most $\alpha n$ if the smaller part has size at least $(1-\alpha) n$.  This happens when you pick a pivot that isn't one of the smallest or largest $(1-\alpha) n$ elements.  Because $\alpha > 1/2$, you know these are disjoint sets, so the probability of hitting one of the bad pivots is just $2 - 2\alpha$, and $1- 2 + 2\alpha=2\alpha - 1$.


Recover boolean vector from dot products Question:

I want to determine a boolean vector $b \in \{0,1\}^n$ consisting of zeros and ones, but cannot access it directly. I can only call a black-box computer code which will take the dot product of $b$ with a real-valued vector $v \in \mathbb{R}^n$ of my choosing. I.e., access to $b$ is available through evaluation of the map
$$v \mapsto b^T v.$$
How can I recover all of the entries of $b$ using as few of these dot products as possible? (maybe even just 1 dot product?)

Below I detail a couple ideas I had which might work in theory, but which don't work in practice (I think). For concreteness, one may assume that $n \approx 1 \text{ million}$, and arithmetic is done in double precision floating point format. This question arose as a subproblem in a machine learning application.

Idea 1:

One idea I had is to use a vector with fast growing entries. Say, for example, $n=9$. Then we could use the vector
$$v=\begin{bmatrix}1 & 10 & 100 & 1000 & \dots\end{bmatrix}^T.$$
One could then read off $b$ as the digits of $b^T v$. The problem with this solution is that the numbers grow so fast, that in finite precision computer arithmetic it will not work for large $n$.

Idea 2:

Another idea I had was to use a vector with entries that are algebraically independent. Then determining $b$ from $b^Tv$ is a subset sum problem.

For example, if $n=3$ and
$$v = \begin{bmatrix}\pi & e & 1\end{bmatrix}^T,$$
then $b^T v$ will take on one of a finite number of possibilities,
$$b^T v \in \{\pi,~e,~1,~\pi+e,~\pi+1,~e+1,~\pi+e+1\}.$$
We can determine which of these is the case, thereby determining $b$.

But this seems quite combinatorial, and therefore unfeasible for large $n$.

Here is an variant of the idea 1 in the question, where a factor of 2 is used to replace the original factor of 9.

Let $v=[2^0, 2^1, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots]^T$. Obtain $b^Tv$, which will determine the first 64 entries of $b$.
Let $v=[0, 0, 0, \cdots, (64 \text { zeros}),  1, 2, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots]^T$. Obtain $b^Tv$, which will determine the next 64 entries of $b$.
Let $v=[0, 0, 0, \cdots, (128 \text { zeros}),  1, 2, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots]^T$. Obtain $b^Tv$, which will determine the next 128 entries of $b$.
And so on, until we have determined all entries of $b$. There may be less than 64 positive numbers in $v$ in the last round.

The above scheme is the best possible if the number of effective bits in $b^Tv$ is 64 and we have no prior knowledge about $v$ except the number of its entries. This can be seen easily from information theory, as each query against the black box can provide at most 64 bits of information.


Are all known algorithms for solving NP-complete problems constructive? Are there any known algorithms that correctly output "yes" to an NP-complete problem without implicitly generating a certificate?

I understand that it is straightforward to turn a satisfiability oracle into a satisfying-assignment finder: just iterate over the variables, each time asking the satisfiability oracle to solve the conjunction of that variable with the original problem.

But would such a wrapper ever be useful? Do all sat solvers search over the space of possible assignments?

Or are there some types of NP-complete problems (traveling salesman, subset sum, etc.) in which the solver can, say, exploit a mathematical theorem to prove that a solution must exist? Like doing a proof by contradiction?

As I understand it, you are asking two questions: (1) are there e.g. SAT algorithms that are more clever than naive brute force, and (2) are there algorithms that simply give a YES/NO answer when solving an NP-complete problem without actually finding the solution. I'll answer both questions in this order.

(1) It is perfectly possible to solve a problem without brute force, i.e. without naively trying all possibilities. To take your example, modern complete SAT solvers can apply clever algorithms that infer or prove certain (partial) assignments can't lead to a solution, so they don't even examine that part.

More generally, even NP-hard problems often exhibit some kind of algorithmic foothold that allows us to design algorithm faster than brute force. The field of this research is exact (exponential) algorithms. Such algorithms take exponential time, but are still faster than naive algorithms. For instance, you can solve TSP in roughly $n!$ time, where $n$ is the number of cities to visit. This method won't scale to even moderate values of $n$, but there is a classic dynamic programming $O(2^nn^2)$ time algorithm due to Held & Karp. For general techniques, see e.g. branch & bound.

(2) There are "oracle algorithms" for NP-complete problems that just output YES/NO with no explicit certificate. For instance, consider the $k$-path problem:

  (The $k$-path problem) Given a graph $G$ and an integer $k$, is there a simple path in $G$ on $k$ vertices?

The above problem is easily seen to be NP-complete. An $O^*(2^k)$ algorithm for the problem is given in [1]. The algorithm itself only gives a YES/NO answer to the problem, but we can use additional tricks to construct the actual $k$-path itself. More generally, when given such an "oracle algorithm", one can use tools from combinatorial group testing for extracting the witness itself.

[1] Williams, Ryan. "Finding paths of length $k$ in $O^*(2^k)$ time." Information Processing Letters 109.6 (2009): 315-318. publisher link, PDF


What is the difference between the study of Evolutionary algorithm vs. Optimization? I have a course named "Evolutionary Algorithm". But, our teacher is always mentioning the word "Optimization" in his lectures.

I am confused. Is he actually teaching Optimization? If yes, why is the name of the course not "Optimization"?

What is the difference between the study of Evolutionary algorithm and Optimization?

Indeed, in evolutionary algorithms, you are optimizing an objective function. Hence, evolutionary algorithms are algorithms for optimization. Hence, they are the specific case of optimization methods. However, there are a vast variety of optimization methods that are not an evolutionary algorithm (such as simplex methods in OR, Lagrange methods and so on). See more about the evolutionary algorithms here:

  In artificial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation1, a generic population-based metaheuristic optimization algorithm.


Find a CFG for the set of prefixes of a CFL How do i generate grammar for Prefix  of Langauge L, SupposeG=(V,,P,S)is a context-free grammar generating a CFL L then pref(L) is defined as pref(L)={x∈∗ : ∃ y such that xy∈L}.

I understand for Suffix(L) we would do something like this .. Can someone here help me how do we do for the Prefix(L) if L is CFL.

For each variable X of G , add a new variable
X' . (X' will generate the suffixes of the language that is generated by using X as the start variable.)
Whenever X' →YZ is a rule of G , we add two new rules,X' →Y' Z and X' → Z' .
for each variable in G , we add
X' → X and X' → ε
If S is the start variable of G , we let S' be the start variable of G'.
Now the new CFG G' can generate the suffix of A , and hence context-free language is closed under the suffix operation.

If you know how to do Suffix, then you also know how to do Prefix. Explicitly, show how transform a context-free grammar for a language $L$ to a context-free grammar of its reverse $L^R = \{x^R : x \in L \}$, where $x^R$ is the word $x$ in reverse (for example, $(for)^R = rof$). Then use the fact that
$$ \mathit{Prefix}(L) = \mathit{Suffix}(L^R)^R. $$
If you unroll this definition, you will actually get a direct construction for Prefix.


Big O notation: removing big O from denominator In A First Course in the Numerical Analysis of Differential Equations (page 26) Arieh Iserles gives the following derivation:
\begin{equation}
\frac{\rho(w)}{\ln(w)}=\frac{\xi+\xi^2}{\xi-\frac{1}{2}\xi^2+\frac{1}{3}\xi^3+\mathcal{O}(\xi^{4})}=\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2}+\mathcal{O(\xi^3)}
\end{equation}
where $\xi=w-1$, $\rho(w)=w^2-w$ and $\xi\to 0$. I understand the expansion of the logarithm in the denominator, but how does the second step work? I have no idea how this big O is removed from the denominator. Can anyone explain this please?

Let's start out simple:

$${1 \over 1 + x} = 1 - x + x^2 - \cdots$$

so it follows that

$${1 \over 1 + O(x)} = 1 + O(x)$$

as $x \to 0$.

(Background: I interpret $O(x)$ as representing any function $f(x)$ where $|f(x)|$ is asymptotically no larger than $x$, i.e., there exist constants $c_0,x_0$ such that $|f(x)| \le c_0 |x|$ for all $-x_0 \le x \le x_0$.  This is the likely meaning of big-O notation in this context, where we are concerned about the asymptotic behavior as $x \to 0$ and where values can be either positive and negative.   If it looks a little different from what you are used to in computer science, that's because in CS we most commonly deal with the situation where we have a function $f(n)$ where $n \to \infty$ and where all values are positive, so the definition looks a bit different in that context.)

Now suppose $v=O(1)$, and take a more complex expression:

$${1 \over 1 + v + O(x)} = {1 \over 1+v} \cdot {1 \over 1 + O(x)} = {1 \over 1+v}(1 + O(x)) = {1 \over 1+v} + O(x),$$

where I have used that $v \cdot O(x)=O(x)$, etc.

Finally, if $u=O(1)$, we can multiply both sides by $1+u$ to see that

$${1+u \over 1+v+O(x)} = {1+u \over 1+v} + O(x).$$

Now plug in $x=\xi^3$ and $u = \xi$ and $v = -\frac12 \xi + \frac13 \xi^2$, and we obtain

$$
\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2+\mathcal{O}(\xi^{3})}=\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2}+\mathcal{O(\xi^3)}
$$

which is the step of the derivation you are asking about.


Where can I read CS papers? I am a self taught programmer, with no formal degree in CS. I have read couple of papers which were recommended on some or other blog and found them interesting. Where can I read papers on computer science ? Are these papers available for free?
If not papers are there any essays on any popular blog posts?

If you have no formal degree in CS, I think what you need is textbook instead of scientific papers.

Being a self-taught programmer is a great achievement and I think you can build up on that with theory. But, reading papers require some deep knowledge in some area.

I would suggest you to buy one of these books:

Algorithms by Robert Sedgewick and Kevin Wayne

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

Data Structures and Algorithm Analysis in C++, 4th Edition
Mark A. Weiss

In these books, you can also find some references to suggested readings.


Searching for efficient method to compute $a^n \bmod p$ for large numbers I need  an efficient algorithm with clear steps to compute $a^n \bmod p$ when $n$ is large enough and $p$ also. I'm looking for something equivalent to the built-in PowerMod function in Mathematica.

The algorithm you are looking for is quick modular exponentiation.

It is based on the exponentiation property of modulus operator
:

A^B mod C = ( (A mod C)^B ) mod C

for example we need to calculate 4^8 mod 7 (let us assume for the time being 4^8 is a large number and cannot be computed by available machines.)

we can then write

=(4^ 4 * 4 ^ 4) mod 7

=(4^4 mod 7 * 4^4 mod 7 )mod 7

= (256 mod 7 * 256 mod 7) mod 7

= 2

This algorithm doesn't only work for powers of 2 it works generally . We just need to write the power in its binary representation .

example :

3^31 mod 4

can be written as

3^(16+8+4+2+1) mod 4

you can see once we apply the exponentiation property to same the computations will be quite efficient.


How come this turing machine running time is $O(n^{1+\log_2 2006}\cdot \log_2n)$ Given a deterministic Turing machine with an input tape and a work tape. The work tape is restricted to $\log_2 n+100$ cells ($n$ represents the input length) and its tape alphabet is of size $2006$. Moreover, the Turing machine has $27$  states.

I wonder how come the running time of such machine is $O(n^{1+\log_2 2006}\cdot \log_2n)$ (The answer is the correct choice for this multiple choices question out of an exam I practise)

This bound comes from the number of possible configurations. If you do more steps than you have configurations, you are in a cycle.

So let us quickly get a bound for the number of configurations. You have $100+\log n$ possible positions for the head on the work tape and $n$ positions for the head on the input tape. The work tape can contain $2006^{100+\log n}$ different words. Furthermore there are 27 states. Combining everything gives
$$
\begin{align}
27n \cdot (100+\log n) \cdot 2006^{100+\log n}&=27\cdot2006^{100}(100n+n\log n) n^{\log 2006}\\
&=O((100n+ n\log n)  n^{\log 2006})\\
&=O(\log n\cdot  n^{1+\log 2006})\\
\end{align}$$


Why is it not always possible to compute the centroid of feature vectors? Hi in the data mining and machine learning course that I'm taking there is a subject on feature spaces and there is this part about feature vector aggregation and metric spaces that I don't really understand. Now our curriculum is basically a huge presentation and the whole information about feature vector aggregation fits on one slide, anyway what I don't understand is this:

For a given sample $D$ the centroid can be computed as   $C_D = \frac{1}{|D|}\cdot\sum_{o\in D} o$

and then on the slide it says, quote:

  In a general metric space (that is, not a vector space),
  where we only have pairwise distances, it might not be
  possible to compute a centroid

I don't really think I understand what "only pairwise distance" means (my guess is it has something to do with the fact that a metric space defines the distances between all pairs of elements in its set) or why the consequence of it is that you can't always compute the centroid.

I read somewhere that metric spaces does not have to define addition or scaling and if that is the case it makes sense to me that you can not calculate the centroid. Is this what it essentially is about or am I completely misunderstanding something?

A metric space consists of a set $X$ of "points" and a metric $d\colon X \times X \to \mathbb{R}_{\geq 0}$ (giving the "distance" between any two points) which satisfies the following constraints:

Symmetry: $d(x,y) = d(y,x)$ for all $x,y \in X$.
Non-triviality: $d(x,y) = 0$ if and only if $x = y$.
Triangle inequality: $d(x,y) \leq d(x,z) + d(z,y)$ for all $x,y,z \in X$.

The definition of centroid doesn't make sense for a general metric space, since you cannot perform arithmetic on the elements of $X$.


Deterministic SAT solver I have the following question. Is the SAT solvers are deterministic?

I mean, for example, about miniSAT and DPLL algorithm. Are they completely deterministic?

If these algorithms will return unSAT it means that certainly the solution does not exist?

Core algorithms like DPLL and its refinements like CDCL are completely deterministic.

Note that non-determinism doesn't necessarily mean that an algorithm may lead to a wrong result. For example we can distinguish between

Monte Carlo algorithms, which are randomised algorithms whose output may be incorrect with some probability.
Las Vegas algorithms, which are are randomised algorithms whose output  is always correct, but the algorithms 'gamble' with the resources used in the computation, e.g. running time on identical inputs may vary.

At the other extreme are probabilistic algorithms for solving $k$-SAT such as Schöning's [ 1 ] which is Monte-Carlo, and remarkably effective in practise given its utter simplicity. Interestingly Schöning's algorithm can be completely derandomised without losing (much of) its effectiveness [ 2 ].

In practise, industrial SAT-solvers always employ some degree of randomness, so as to 'escape' from the bad (= exponential) worst-case behaviour of DPLL-based algorithms.  MiniSat is a highly configurable and evolving piece of software. That said, MiniSat is not completely deterministic: the choice of branching variable is sometimes randomised, depending on command line options. (The default is that  2% of branching variables are chosen randomly IIRC.) Likewise, MiniSAT has the option of initialising the VSIDS scores randomly. (VSIDS is a heuristic for 'measuring' the influence a variable has.)

U. Schöning, A Probabilistic Algorithm for $k$-SAT Based on Limited
Local Search and Restart.
R. A. Moser, D. Scheder, A Full Derandomization of Schöning's
$k$-SAT Algorithm.


How to prove an implication about an upper bound mentioned in the proof of master theorem? How can we prove rigorously the proposition "Suppose the if in case 1 is true, the equation 4.23 is true"?
For given constant b and j, the implication in green makes sense. If the upper bound of j was fixed, the equation 4.23 follows directly. However, when n increases, the upper bound of j also increases, though is slower. It is where I find difficult to prove there always exists a value m > 0 such that for all n >= m, equation 4.23 is true.

The statement $f = O(h)$ just states that there exists a constant $C>0$ such that $f(N) \leq Ch(N)$ for all $N$ (some variants have this hold only for large enough $N$, but in most cases there is no difference). In your case, $f(N) \leq CN^{\log_b a-\epsilon}$ for all $N$. This holds for $N = n/b^j$ in particular, and implies that
$$
g(n) \leq C \sum_{j=0}^{\log_b n-1} a^j (n/b_j)^{\log_b a-\epsilon}.
$$

As for the two different definitions of big O: suppose that $f(N) \leq CN^{\log_b a-\epsilon}$ holds only for $N \geq N_0$, and let $M = \max(C,f(1),\ldots,f(N_0))$. Then $f(N) \leq MN^{\log_b a-\epsilon}$.


Can Multiprocessor Systems Implement Both Temporal Multithreading and Simultaneous Multithreading? I am aware that multiprocessor systems often implement simultaneous multithreading in order to allow multiple threads to run on different CPUs. I am also aware that uni-core systems often implement temporal multithreading (fine-grained/preemptive or coarse-grained/cooperative) to allow for a more efficient use of the CPU through the use of context switches.

However, I am curious whether it is possible (or logical) to have a simultaneously multithreaded system also allow for the time-sharing between threads on each CPU, which is prevalent in temporal multithreading systems.

Sure.  You can simultaneously run multiple threads on different CPUs in parallel; and also a single CPU can context switch between threads (i.e., both what you are calling simultaneous multithreading + temporal multithreading).   Nothing prevents it.


How long does it take to crack a password by brute force My computer teacher says that hackers can know any password by simply writing a permutation combination program and it will take around 21 days. Is this true?

Perhaps your teacher was talking about some system where the format of passwords is restricted (e.g., where they can't be longer than whatever number of characters allows a typical computer to try all combinations in 21 days).  Or perhaps they were talking about some specific kind of password, such as words from the dictionary, maybe with c0mm0n m0d1f1c4t10n5.

In general, it's impossible to give a limit because passwords could be arbitrarily long. Indeed, even without needing crazy-long passwords, there are $62^{10}\approx 10^{18}$ possible ten-character passwords that can be made from numbers and upper-case and lower-case letters.  If you can try a billion passwords a second, it'll still take you a billion seconds to try all of these passwords, and that's about 32 years.

Note that the above discussion ignores the fact that, in reality, we don't guess passwords but, instead, guess strings that have the same hashes as passwords.  At the level we're talking about here, though, this doesn't make any real difference.


Solving the recursive equation $T(n)=T(k)+T(n-k-1)+O(n)$ The question is clear in the title. I am trying to solve this recursion as a part of showing that the worst case of quicksort algorithm occurs when $k=0$, but can't do it. I could do the following specific cases (by repeatedly using the same recursion):
1)$T(n)=T(n-1)+O(n)$
2)$T(n)=2T(\frac n2)+O(n)$
Can anybody please help me to solve this general case (or at least suggest some other way to prove that the worst case is $k=0$)?
P.S. I don't know Master's theorem, so I would appreciate a solution without using that (In case that is applicable here).

Consider the recurrence
$$
T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0,
$$
which is one formalization of the worst-case running time of quicksort. Let us show by induction that the maximum is attained at $k = 0$ (or $k = n$). We will show this while at the same time showing that $T(n) = \frac{n(n+1)}{2}$.
The base case, $n=0$, is clear. Now suppose that $T(m) = \frac{m(m+1)}{2}$ for all $m \leq n$, and consider $T(n+1)$. The function $T(k)$ is convex on the interval $[0,n]$ (we extend it to real values using the same formula), and so the maximum of $T(k) + T(n-k)$ is attained at $k=0$ (or $k=n$). Therefore
$$
T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}.
$$
Instead of arguing using convexity, we can also argue directly:
$$
T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} =
\frac{n(n+1)}{2}-k(n-k),
$$
which is clearly maximized (uniquely) when $k = 0$ or $k = n$.


Does dependent type checkers need to store lambda parameter type in their core language? "Core language" refers to the exported well-typed terms that can be evaluated (or reduced).

In the core language of MiniAgda, a dependently-typed language, the parameter type of a lambda is not stored anywhere. So does in Mini-TT and Agda.

However, Idris does store lambda parameter type in its core language.

I wonder do we need/needn't to store parameter type (or, under what condition do we need/needn't to store it)?
Because according the surface syntax of all these languages, they don't have lambdas with their parameters explicitly-annotated.
For Idris here's a link showing that Idris does not have lambda with type annotation.

In general, type inference for dependent types is undecidable. This means that when checking a function, we need some way to know what type its argument has.

In the case of Idris, they simply annotate lambdas with parameter types. This is very common in type theory, since it makes your type system syntax directed in a very simple way. When you do this, you can usually view the typing judgment as having the type as an output parameter (i.e. given the input term, you can determine its type).

I don't know what MiniAgda does in particular, but the other main way is to treat the type as an input to the checking judgment. So in this case, you don't need to store the type of the function in the AST, but when typechecking, you will use the context in some way to get the type of the function (i.e. from an annotation).

Generally this is done using bidirectional typechecking. This paper and this post both give excellent overviews of how this can be done in practice.


Is call stack compile time or runtime detail? I'm sorry if the question is quite naive, but I don't understand if a call stack is a language implementation detail or it depends on OS?

What I'm trying to understand is what decides how to store local variables and parameters of a function - the language's compiler or OS while running the application? Is it possible to write a C compiler, let's say, for Windows so that it won't be stack based? Or the language syntax dictates us that it must be stack-based language?

Sorry if I say something wrong, just trying to get the basic idea how everything works.

The architecture of a computer is where concepts like "heap" and "call stack" originate from.  If you take a look at the C standard (http://www.iso-9899.info/wiki/The_Standard) you won't find anything about the stack or heap.

Compilers for a language like C can implement the specification in a number of ways in order to target specific architectures; even ones where memory is not organized in a stack, such as a "LISP cpu" (for example Sussman and Steele's: https://dspace.mit.edu/bitstream/handle/1721.1/5731/AIM-514.pdf?sequence=2) where memory is organized as linked lists.

Of course a language specification could define these things, but I am not aware of any language which goes so far.  (The closest I can think of is forth.)

Operating systems and libraries can abstract away some of the details of the underlying architecture via system calls and apis.


Is it possible to build regex-based-map with search asymptotically faster then hashmap? From time to time I stumble across a problem of matching hashmap keys to a regular expression. In such situations I am forced to loop through all of map's elements and try to match every single key to the regex. With regex compiled to DST it should have complexity class of O(n * m) where n is number of elements in map and m is the length of the longest key in the map. Assuming m is reasonably small, we can assume it is O(n).
Above solution to this problem, although it is reasonably good, makes me think every time - is it possible to construct a data structure that would be faster (at least in theory) in searching all the keys that match the given regex. Probably it would not be linearly dependent on the number of the keys in the data structure. Is it possible? If it is possible - what would be the main idea reducing complexity?

One possible approach is to store the keys in a trie, convert the regex to a DFA (remove all useless states from it and optionally minimize it), and then use that to search the trie.
In particular, you can construct a recursive algorithm for traversing the trie.  The root of the trie is associated with the start state of the DFA.  For each edge out of the root, you look at the letter on that edge, advance the DFA to the appropriate state, and associate that state with the corresponding child.  If it causes the DFA to reject, then you can prune exploration of that node in the trie.  In this way, each node in the trie gets associated with a state of the DFA, you recursively explore the trie, pruning when you hit dead ends, and if you hit a leaf in the trie, if the DFA is in an accept state at that point, you have found a match.
However the running time to convert a regex to a DFA can take exponential time.  Also this only works with language-theoretic regular expressions, not Perl- or POSIX-style regexps, which are more expressive and cannot be converted to a DFA.  So, whether this will be attractive might depend on your application.


Dijkstra algorithm modification with exactly one relaxation on a directed graph where the weights of outgoing edges of a node are the same Consider the standard version of Dijkstra's algorithm on directed graphs. Assume it is known that the input digraph $G = (V, E)$ has the following property: for all $v \in V$ the weight of all outgoing edges $vu$ is the same.

How can one modify Dijkstra's algorithm so that exactly one relaxation is done for every vertex $v \in V$? (i. e. decreasing of current minimal path length $d_{v}$ is done exactly once for every $v$).

In each iteration, instead of choosing the node $u$ with smallest $\mathtt{dist}[u]$ in the standard Dijkstra's algorithm, we choose the node $u$ with smallest $\mathtt{dist}[u]+w(u)$, where $w(u)$ is the weight of outgoing edges from $u$.

The proof of the correctness of this modified algorithm is almost the same as the one of the standard Dijkstra's algorithm. As shown in the proof for the standard Dijkstra's algorithm, it also holds that for each visited node $v$, $\mathtt{dist}[v]$ is the shortest distance from source to $v$.

Now consider a node $v$. Let $P$ be a shortest path from source to $v$. Suppose $\mathtt{dist}[v]$ is first updated through $u$ (i.e., it is updated to $\mathtt{dist}[u]+w(u)$), and when $\mathtt{dist}[v]$ is first updated, $x$ is the first unvisited node on $P$, then $\mathtt{dist}[x]+w(x)\le w(P)\le \mathtt{dist}[u]+w(u)$, where $w(P)$ is the shortest distance from source to $v$. Also note at this time $u$ is chosen instead of $x$, we have
$\mathtt{dist}[u]+w(u)\le \mathtt{dist}[x]+w(x)$, hence $\mathtt{dist}[x]+w(x)= w(P)= \mathtt{dist}[u]+w(u)$, i.e., $\mathtt{dist}[v]$ is first updated to the shortest distance from source to $v$, and it will not be updated any more.


Is it possible to compute -12 (decimal) in 4 bits binary This is what I have so far

1 1 0 0

Switch values by 2s Complement

0 0 1 1
+     1

0 1 0 0

No, it's not possible, at least using the standard representations. An unsigned $n$-bit number can represent any integer in the interval $[0, 2^{n} - 1]$. A signed $n$-bit number using two's complement can represent integers in the interval $[-2^{n - 1}, 2^{n - 1} - 1]$. With $n = 4$, that gives an interval of $[-8, 7]$, which obviously doesn't include $12$. One's complement can use $n$ bits to represent the interval $[-(2^{n - 1} - 1), 2^{n - 1} - 1]$, giving the interval $[-7, 7]$ for four bits, which also doesn't work. You'd have to contrive a nonstandard representation to represent $-12$ in four bits.


Interpreting probabilistic time turning machines I was trying to understand better the definition of a strong PSRG and I came across this expression which I am trying to understand better:

$$ Pr_{r \in \{0,1\}^l}[A(r) = \text{"yes"}]$$

Where r is a truly random bit string and A is a polynomial time deterministic machine.
I've been having some problems understanding what this expression means conceptually (or intuitively).

So far these are some of my thoughts and I will try to point out my doubts too.

A is just a standard TM so we can image that on l steps, it will yield $2^l$ branches. Each branch has a chance of occurring depending on which r occurs. Therefore, I was wondering if the above probability expression just mean "the fraction of branches that out yes"? Is that basically the same as the chance that A will output yes on the given random bit string? The thing that was confusing me and I was not sure how to deal with it was that, A(r) always outputs the same thing ("yes" or "no") on a given r (say it always accepts or rejects if r = 1010100 or something), it didn't seem to me that it a probabilistic sense, unless we randomly choose r. So I was wondering how the community interpreted this equation and what it mean.

Also, since this is a probability, it seems to me that A(r) is just r.v. that only takes two values (yes or no), right? So this distribution only has two probability values, the one that A outputs yes or no, right? I was wondering how that related to the string r and I was not sure how to resolve this.

As the notation implies, the probability is taken over the choice of $r$. So it's the fraction of $r$s which the machine $A$ "accepts" (answer Yes). You're right that the random variable $A(r)$ has two possible values, Yes and No, and so for example the probability to get Yes and the probability to get No add up to $1$.

We usually think of $A$ as a statistical test. For example, $A$ might test the the number of $1$s in $r$ is roughly $\ell/2$, say between $\ell/2-\sqrt{\ell\log \ell}$ and $\ell/2+\sqrt{\ell\log \ell}$, and then it accepts with probability $1-2/\ell^2$ or higher (using Chernoff's inequality).

Something you are confused about is the branching. The machine $A$ can read its input bits many times. There is always one computation branch. After $\ell$ steps, there is still only one computation branch. On the other hand, at the outset there are $2^\ell$ different computations to consider.


Compare asymptotic WC runtime with measured AC runtime I have an algorithm and I determined the asymptotic worst-case runtime, represented by Landau notation. Let's say $T(n) = O(n^2)$; this is measured in number of operations.

But this is the worst case, how about in average? I tried to run my algorithm 1000 times for each $n$ from $1$ to $1000$.I get another graph which is the average running time against $n$ but measured in real seconds.

Is there any possible way to compare these figures?

You can't, not really, for three reasons:

Number of operations and runtime do not compare well; too many factors (typically) left out in analysis influence actual runtime.
Asymptotic results (which hold in the limit) and a finite sets of observations do not compare.
Landau classes don't compare with "exact" functions. For instance, if you have $f \in O(n^3)$ and $g(n) = 3n^2$, you have no idea which grows faster.

All hope is not lost, though. With some additional work you can get to reliable statements.

Perform an (asymptotic) average-case analysis. That is, assume a random distribution on the input set and calculate the expected number of executed operations. That can be tough, but if you succeed you can compare the result to your worst-case asymptotic. (Note that you may need $\Theta$ to make meaningful statements.)
If you can, improve your analysis to yield constant factors (not only $\Theta$). That way, you can separate, say, a $2n^2 + 5n$ worst-case from $1.5n^2 - 3 \log n$ average-case.
Run the program for worst-case instances (you should know them from your WC-analysis) and compare the real measurements with the average case.

Note: This can only provide guesses for asymptotic behaviour.
Alternatively, run the program average and worst-case instances but count statements. That gives you more reliable measurements and removes platform-dependent artifacts from consideration. Still, you get only guesses for asymptotics.

Bottom line, you have to have the same "kind" of statement for both worst- and average-case if you want to compare them.


Meaning of $\triangleright$ in programming language semantics What does the symbol "$\triangleright$" mean programming language semantics?  I've seen it in the context of datatypes in and the evaluation of expressions in environments.

For example :

$$tenv \triangleright erht \implies tval $$

or

$$tenv[tval/x]\triangleright ebody\implies t\,.$$

Here, $tenv$ is an environment and $ebody$ is the body of some expression.

Most probably, in your context, ▹ is just a syntactic separator, meaning "in the environment to the left of ▹, the formula to the right of ▹ holds".

However, ▹ has no fixed meaning in general. I used it myself with completely different definitions.


Is quick sort the best algorithm in average case compared to other comparison-based sorting algorithms? I know that quick sort has an average case of O(nlogn). And I also know that the average case of comparison-based sorting algorithms are Omega of nlogn. Can we say that quick sort is the best sorting algorithm in average case compared to other comparison-based sorting algorithms? (I think the answer is yes. However, I cannot justify my answer with a convincing argument)

Depends. Quicksort is not one algorithm. Performance depends on the details. You would adjust the algorithm slightly if moving items is expensive.

You might assume that items are in random order. That is often not the case. You may be able to sort items with non-random items faster than using quicksort. For example if an array starts or ends with many items in ascending or descending order sorting in linear time may be possible.


Time Complexity of Genetic Algorithms How do you determine the Time Complexity of a Genetic Algorithm(in general)? If possible.

I have been thinking about this a lot, and all of the teaching I have had is related to determining the Time Complexity of problems that are much less stochastic in nature.

Genetic algorithms are a metaheuristic and as such there is no general analysis that applies to all genetic algorithms at once (without being super loose). In general, when you are searching for information on the run-time of genetic algorithms, you will have more luck if you use the terms "convergence time", since that is the more common terminology. A good start on some formal techniques:

Y. Rabinovich, A. Wigderson. Techniques for bounding the convergence rate of genetic algorithms. Random Structures Algorithms, vol. 14, no. 2, 111-138, 1999.

For more resources on formal treatments, consider the cstheory question: Provable statements about genetic algorithms.


Understanding Instruction Cycle? A basic instruction cycle consists of these 5 stages.

  Instruction Cycle

  IF - Instruction Fetch
  RD - Instruction Decode and Register Read
  EX - Execute
  MA - Memory Access
  WB - Write Back

I understood the function of all the stages accept the fourth (Memory access). What's the significance of this stage?

Over Internet what I've found is this

  MA(Memory Access) does following operation

  If load or store instruction, then access memory
  If branch instruction, replace PC with destination address

The second point is clear, but I'm confused by the first.

Suppose we have load and store instruction like this
$$(I) R_1 \leftarrow m[A_1]$$ $$(II) m[A_2] \rightarrow R_2$$

what will the MA stage do for the above instructions?

You have to operate on the memory to do anything useful. Reading next instruction, getting variable to operate on or saving calculated value - all that requires accessing memory.


How does CFS prevent a long sleeping task from occupying the CPU? The Completely Fair Scheduler executes the task that has so far received the least share of CPU time and is thus the most 'disadvantaged'.
So if a task sleeps for a really long time, say 3hrs, how does CFS prevent this task from being executed for the next like 3hrs (to adapt its CPU share to the much larger values of the other tasks)?

Or does CFS do so at all? Or did I get something wrong?

Thanks in advance :)

Just found it out by myself:

each time CFS places a new/old task into the rbtree it does not reuse its old runtime but rather assigns a new one:
se->vruntime = max(se->vruntime, vruntime) where vruntime is the current minimum virtual runtime.

That is basically what is expressed through "sleeper fairness": each task gets a fair share of CPU time, no matter whether it is running or not.


How to prove a bound function for a sequence of numbers? Let $G_n$ be defined by

$$G_n = \begin{cases} 1 & n=0 \\
2 & n = 1 \\
3 & n = 2 \\
4 & n = 3 \\
2G_{n-1}-2G_{n-3}+G_{n-4} & n\geq4
\end{cases}$$

How can I prove that $f(n) = n$ is a bound function (or loop variant) for the above sequence?

If you have tried, you will find that
$$\begin{aligned}
G_5&=6\\
G_6&=7\\
G_7&=8\\
G_8&=9\\
G_9&=10.\\
\end{aligned}$$

By now, you should have probably guessed that $G_{n}=n+1$. Now you can try proving it, using induction on $n$.

Once that formula has been proved, $f(n)=n$ is of course a lower bound for $G_n$.


What is the name for the comparison used in C's memcmp? The C memcmp function (and strcmp) does a comparison similar to the function below for comparing integers:

int compare(const int a, const int b) {
     if (a > b) return 1;
     if (b > a) return -1;
     return 0;
}

Microsoft information for their strcmp says:

  The strcmp function performs an ordinal comparison of string1 and string2 and returns a value that indicates their relationship.

The manual of GNU's libc describes the comparison in this way:

  Your comparison function should return a value the way strcmp does: negative if the first argument is "less" than the second, zero if they are "equal", and positive if the first argument is "greater".

But doesn't define any name for this comparison type.

What is the name for this comparison algorithm?

And why doesn't memcmp simply return say 0 if a and b the same and 1 otherwise?

The question is about a three-valued function in a situation where a boolean is often used (eg <=).  I personally refer to this as the sign or signum: the sign of the difference of the comparands.  However I have not seen a widely-used term; the best supportable answer I can give is that there is none.

In Quicksort, when a three-way partition (based on this "signum") is used instead of two-way, it's called ternary (and there are ternary search trees based on the same distinction), but that's about as specific as it gets.

My reasoning behind my naming this quantity signum is that comparison is often implemented as subtraction; the CMP instruction is essentially a SUB instruction that discards the actual result but retains the sign and zero flags.

Strings are obviously not numbers, but they have a commonly-used embedding into [0,1) that makes lexicographic comparison equivalent to subtraction and signum extraction.

As to the idea of a two-valued (==, !=) predicate, there is some precedent for this idea in contexts where the signum may not be obtainable.  Fagerbergh, Pagh et al. construct what they call a "unordered trie" on hashed string values, where the original order of the strings is obscured due to hashing, but the position where they first disagree is still known.  This practice also has some use in applying collations, where only the branching character needs to be looked up to get the collated order (the equal prefix is skipped).


Is there any better way to find the closest points' distance? The problem is:

  Suppose you're given $n$ points in the coordinate plane, and for convenience assume that no two of their $x$ or $y$ coordinates are the same. Design an algorithm that finds the shortest possible distance between a pair of these points. What is the time complexity of your algorithm?

Ofcourse there is a easy way to find the shortest distance in $\mathcal{O}(n^2)$. But, is there any better algorithm? I am out of idea.

Note: I am a Math major and not familiar with CS way to solve problems very much.

This is the well-known closest pair of points problem, and you can solve it for $n$ points in $O(n \log n)$ time by divide and conquer.

A pretty cool randomized algorithm due to Rabin is also available.


Proving Postorder Traversal's Time Complexity I am looking at the following algorithm for performing a Postorder Traversal of a binary tree

POSTORDER(root):
if root != nullthen
    POSTORDER(root.left);
    POSTORDER(root.right);
    visit root;
end if;

I am supposed to be able to demonstrate that this algorithm runs in Θ(n) time complexity when the input is a n-vertex tree. But I am not even sure where to begin with doing that.

I have looked at the following sources:

https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
https://en.wikipedia.org/wiki/Reverse_Polish_notation
https://en.wikipedia.org/wiki/Tree_traversal
https://leetcode.com/articles/introduction-to-n-ary-trees/

I understand WHAT PostOrder traversal does, and I understand WHAT a binary tree is, but I don't know how I can prove that time complexity.

Could anybody help me on this?

In order to prove the complexity of n-vertex tree, you must first understand how to analyze the time for a binary tree. So i am explaining it for a binary tree so that you can generalize it.

In postorder traversal each node in binary tree is visited:

a) 1 time if it is a leaf node.

b) 1 time if it is a node with only one child (either left or right)

c) 2 times if the node has both left and right children. 2 times because when we have to process the right child once we have finished with processing of its left child we need to check whether the node has right child or not. If it has a right child we process right child deferring the parent node so that it could be revisited again once we are finished with processing of right child as well.

So, any node in the tree is not visited more than two times. If n is the number of nodes then the worst case complexity is $O(2n)$ (in case of complete binary tree) and best case is $O(n)$ (in case of skew tree). Ignoring the constants:

Best case time : $O(n)$

Worst case time : $O(n)$

Hence, we can say algorithm is $Θ(n)$.


Text search by first order formula I am searching for substrings that satisfy a given first order formula in a moderately sized text. The formula is made out of usual $\wedge, \neg, \exists$ and predicates Equals(x, "some string"), Before(x, y) and similar, where variables are pairs indices denoting substrings.

If the text is $n$ symbols long and the formula contains $k$ quantifiers, then the brute search is $O(n^{2k+2})$. This is quite a bit of time. I ask, is there a way to significantly improve on this?

Many ranges are 'obviously' not worth iterating over, but I don't see a good way to sufficiently restrict the search space, without enumerating all the possible substrings.

The formula's you propose are very reminiscent of the operations of monadic second order logic: position variables, existence letter on position, relative order of positions, boolean operators and position quantification. As you probably know the power of this scheme equals regular languages.

The transformation from MSO to FSA seems to be horrible (negation is complementation, and existential quantification is handled using nondeterminism, hence exponential blow-up for each combination of the two).

Nevertheless, that gives a very different complexity, linear in $n$, but multiplied by a tower of 2-powers of height $k$.


What is the difference between a Transition System and a Program Graph? (model checking) As the above question says.

I'm wondering if a transition system is the same as a program graph or they are two different things?

Thank you.

You did not provide any particular resources for neither transition system nor program graph. My answer below is based on the book "Principles of Model Checking" by Christel Baier and Joost-Pieter Katoen (The MIT Press).

For completeness, I first present the definitions of both transition system and program graph in this book. (Keep the numbering of the definitions in the book.)

Definition of transition system:

  Definition 2.1 (Transition System $TS$)

  A transition system $TS$ is a tuple $(S, Act, \to, I, AP, L)$ where

  $S$ is a set of states,
  $Act$ is a set of actions,
  $\to \subseteq S \times Act \times S$ is a transition relation,
  $I \subseteq S$ is a set of initial states,
  $AP$ is a set of atomic propositions, and
  $L : S \to 2^{AP}$ is a labeling function.

Definition of program graph:

  Definition 2.13. (Program Graph $PG$)

  A program graph $PG$ over set $Var$ of typed variables is a tuple $(Loc, Act, Effect,
\hookrightarrow, Loc_0,g_0)$ where

  $Loc$ is a set of locations and $Act$ is a set of actions,
  $Effect : Act \times Eval(Var) \to Eval(Var)$ is the effect function,
  $\hookrightarrow \subseteq Loc \times Cond(Var) \times Act \times Loc$ is the conditional transition relation,
  $Loc0 \subseteq Loc$ is a set of initial locations,
  $g_0 \in Cond(Var)$ is the initial condition.

First of all, the program graph consisting of locations as nodes and conditional transitions as edges is not a transition system, since the edges are provided with conditions.

However, each program graph can be interpreted as a transition system. Particular, the underlying transition system of a program graph results from unfolding: a state of the transition system is composed of a location $l$ of the program graph and an evaluation $\eta$ of the variables. Formally,

  Definition 2.15. Transition System Semantics of a Program Graph

  The transition system $TS(PG)$ of program graph $PG = (Loc, Act, Effect, \hookrightarrow, Loc_0, g_0)$
  over set $Var$ of variables is the tuple $(S, Act, \to, I, AP, L)$ where

  $S = Loc \times Eval(Var)$
  $\to \subseteq S \times Act \times S$ is defined by the rule
  $$\frac{l \hookrightarrow^{g:\alpha} l' \land \eta \models g}{\langle l, \eta \rangle \to^{\alpha} \langle l', Effect(\alpha, \eta) \rangle}$$
  $I = \{ \langle l, \eta \rangle \mid l \in Loc_0, \eta \models g_0 \}$
  $AP = Loc \cup Cond(Var)$
  $L (\langle l, \eta \rangle) = \{ l \} \cup \{ g \in Cond(Var) \mid \eta \models g \}$.


Prove that for a general data structure - operations Extract_min() and Insert(x) cost $\Omega(\log n)$? I've been given the following problem:

Given a data structure $M$ that is based on comparisons and supports the following methods on a group of numbers $S$:

$\text{Insert}(x)$ – add $x$ to $S$
$\text{Extract_min}()$ – remove the minimal element in $S$ and return it

We can implement with a heap the above methods in $O(\log n)$, however, we're looking at
a bigger picture, a general case that we have no guarantee that $M$ is indeed a heap. Prove that
no matter what kind of data structure $M$ is, that at least one of the methods that $M$ supports must take $\Omega(\log n )$.

My solution:

Each sorting algorithm that is based on comparisons must take at the worst case at least $\Omega(n\log n)$ – we'll prove that using a decision tree: if we look at any given algorithm that is based on comparisons, as a binary tree where each vertex is a compare-method between 2 elements:

if the first is bigger than the second element – we'll go to the left child
if the second is bigger than the first element – we'll go to the right child

At the end, we'll have $n!$ leaves that are the options for sorting the elements.

The height of the tree is $h$, then:

$$2^h \ge n! \quad\Longrightarrow\quad \log(2^h) >= \log(n!) \quad\Longrightarrow\quad h \ge \log(n!) \quad\Longrightarrow\quad h = \Omega(n \log n)$$

Then, if we have a $\Omega(n \log n)$ worst case for $n$ elements, then we have a $\Omega(\log n)$ for a single element.

I'm not sure regarding this solution, so I'd appreciate for corrections or anything else
you can come up with.

I don't think your proof is valid, because it only considers trees, and a certain type of trees at that. If there were an algorithm with a smaller lower bound for what you describe, we'd have a sorting algorithm faster than $\Omega(n \log n)$ no matter which of the two operations is $\log n$. So the problem reduces to proving that sorting cannot be faster than $\Omega(n \log n)$, which is a classical proof that you can find online.


Half-SAT intractability proof I've been struggling lately with a problem that was in my last complex algorithms exam, and I can't find a solution.
The problem is as follows:

Half-SAT is a problem where C is a CNF boolean formula with n variables and m clauses, where m is even. We have to determine if there exists an interpretation that satisfies exactly half of the clauses. Prove Half-SAT intractability with a reduction from SAT.
Clues: A formula can have duplicated clauses It's possible to write clauses that are always true.

I'd be very grateful if you could give me any clue on how to approach this problem.

The clue that you got is a bit strange, since true clauses are not enough. Here is one possible solution. Given a CNF formula with $m$ clauses, let $a$ be a new variable, add the clause $a \lor \lnot a$, and add $m+1$ copies of the clause $a$. I claim that if this formula is half-satisfiable then the original formula is satisfiable.
An assignment in which $a$ is true satisfies at least $m+2$ out of the $2m+2$ clauses, which is more than half the clauses. Therefore any assignment half-satisfying the new formula must assign false to $a$, leading to the conclusion that the $m$ original clauses must all be satisfied.


synchronization (test-and-set) I have benn wondering about the following possibility: if I have multiple hardware threads on the same
core, and then someone decides to use shared register to allow fast synchronization among threads that run on the CPU, and implements test-and-set on the register instead of doing it in main memory.
Will this work? and if it works, why?

Synchronization based on test-and-set requires a shared data storage location that all the involved threads can read and modify.  Your shared register is a shared data storage location.

The reason synchronizing on a register when the threads are running on different CPUs is that the register would not be shared (not be visible) to one of the threads.  You should think of registers as memory locations with some features removed to make them faster.

In fact, something similar to your scenario was possible on SPARC processors.  The SPARC had a large register file (something like 64 or 128 registers) with 8 registers that were always visible and then 24 register "windows" into the rest of the register file.  Usually these windows were used to implement fast stack frames, but there were several experimental runtime systems that used the windows to support multiple threads.


Turn MST of G to MST of G with one new edge Given $T$, an MST of $G(V,E)$ connected and undirected.
Assume we add an edge $e'$ with weight $w(e')$.
Suggest an algorithm which takes $T$ as input, and outs $T'$ MST of $G'(V,E\cup\{e'\})$.So i thought about adding $e'$ to $T$ and removing the heaviest edge in the cycle that was formed. Can anyone suggest how to go about proving that $T'$ is indeed the MST of $G'$?

Please see my answer to the question "Updating an MST $T$ when the weight of an edge not in $T$ is decreased".

Before we add $e'$ with weight $w(e')$, let us add $e'$ with weight so large (or, for example, larger than the weight of every other existing edge) that $e'$ will not be in any $MST$. In particular, $T$ remains an MST with this addition.

Now let us change the weight of $e'$  to $w(e')$. Then this question becomes the same question in the linked answer above.


What solution to apply for finding the optimal parameters? For a study, I have a system (black-box) that requires an input in the form of an array with 4 values (input_array) and depending on their values it produces an output (response) signal.

The input_array contains 4 real values (parameters P1-4), with given and separate ranges. The output signal's quality is measured by calculating its signal-to-noise ratio (SNR). Each input_array variant can be applied to the system once every 3 seconds (not faster than 3 s).

I have to find the optimal input_array that produces the greatest SNR (preferably, in the least amount of time). That is, the combination of the 4 real values that maximizes the SNR (an optimal solution is sufficient; an absolute solution is welcomed, but not necessarily required). If helpful in finding a solution, the 4 parameters can be discretized, but their ranges would include hundreds of possible (discrete) values.

The values can be considered independent, no prior knowledge is available for them except their ranges, and their individual influence on the SNR is unknown. The SNR is a real value that is influenced by noise (thus, for the same input_array applied consecutively, it can have different (but close) values).

What solution(s) can be applied to this problem?

The simplest solution that comes to mind is to perform an
exhaustive search of the parameters domain, but it is no applicable because the time required will be too long.
Initially, I was considering of applying reinforcement learning
algorithms for continuous action spaces, by considering each
parameter a separate action and returning a positive/negative reward
when the SNR increases/decreases (e.g., +/-1). However, I think they
would require too much time; nonetheless, I can stop the learning
process at any time I consider that the input_array produces an
acceptable SNR.
After further thinking, this problem seemed like a search problem,
so I thought that (heuristic) searching algorithms may be
appropriate.

Does anybody have an idea what would be the most appropriate solution to this problem?

It appears that you have a function $f:\mathbb{R}^4 \to \mathbb{R}$ and you want to find $x$ that maximizes $f(x)$, but you cannot compute $f$ directly; you can only obtain a noisy estimate of its value.

Many optimization methods can be adapted to this setting.  A simple thing you could try would be an iterative method like gradient ascent or Newton's method, but with more iterations to account for the noise; the idea is that the noise will average out given enough iterations.

For instance, gradient ascent requires that you be able to compute the gradient $\nabla f (x)$ for any point of your choosing.  In your case, this can be done by estimating

$$\nabla f(x) = ((f(x+e_1)-f(x-e_1))/2, \dots, (f(x+e_4)-f(x-e_4))/2),$$

where $e_1=(1,0,0,0)$, $e_2=(0,1,0,0)$, and so on.  Now given the ability to compute $f$ on a point of your choice, by computing $f$ on 8 inputs, you can estimate $\nabla f(x)$ and then take a single step of gradient ascent; and repeat until convergence.

A more sophisticated approach would be to try using Bayesian optimization, such as Google Vizier.


Can Turing Machines solve non-decision problems? Since TMs are equivalent to algorithms, they must be able to perform algoriths like, say, mergesort. But the formal definition allows only for decision problems, i.e, acceptance of languages. So how can we cast the performance of mergesort as a decision problem?

Usually, Turing machines are explained to calculate functions $f:A \rightarrow B$, of which decision problems are a special case where $B = \mathbb{B}$.


The physical implementation of quantum annealing algorithm From that question about differences between Quantum annealing and simulated annealing, we found (in commets to answer) that physical implementation of quantum annealing is exists (D-Wave quantum computers).

Can anyone explain that algorithm in terms of quantum gates and quantum algorithms, or in physical terms (a part of algorithm that depends on quantum hardware)?

Does anyone have any ideas about that?
Please tell me, if you know some links related this question.

The approach to quantum computing that you are referring to is something called the adiabatic model. It's actually based on continuous time evolution of quantum systems, rather than on discretized-time models (i.e. no gates). It turns out that it is possible to approximate continuous time evolution with a discrete set of gates, and so the algorithm can be implemented in any universal model of quantum computation.

In order to understand the algorithm and how it works, you need to know some physics. A Hamiltonian, $H$, is an observable which corresponds to the total energy of the system. Any eigenstate, $\psi$, of $H$ corresponds to a configuration of the system for which there is a definite energy, $E$, equal to the corresponding eigenvalue of $H$.

The dynamics of a quantum system are determined by its Hamiltonian, and for a fixed Hamiltonian, the evolution is given by $\psi(t) = e^{-iHt/\hbar}\psi(0)$.

The adiabatic algorithm is based on the adiabatic theorem, which roughly speaking, states that if you start in the ground state (the lowest energy state of the system) of some Hamiltonian $H_0$ and slowly change the Hamiltonian as a function of time, then you will continue to remain in the ground state (or rather very close to it) of the instantaneous Hamiltonian, provided that the speed at which the Hamiltonian changes is sufficiently slow. How slow this must be depends on the minimum gap between the ground state and the next lowest energy level, and varies from one Hamiltonian to the other.

The adiabatic algorithm is simply to start in the ground state of some simple Hamiltonian, $H_0$, for which the ground state is easy to prepare, and slowly interpolate between it and some target Hamiltonian, $H_1$, which encodes in its ground state the solution to the problem you are trying to solve. Thus, the time varying Hamiltonian may look something like $H(t) = (1-t/T)H_0 + (t/T)H_1$, where $T$ is the total time for the adiabatic evolution. As long as $T$ is sufficiently large, the adiabatic theorem guarantees that the resulting state at time $T$ will be very close to the ground state of $H_1$.

It should be noted that the linear interpolation above is certainly not the only possible choice, and indeed looking for better paths between $H_0$ and $H_1$ is an active area of research, since the path determines the minimum value which can be taken by $T$. None the less, the above should give you a taste of how the algorithm works.


Finding a certain prefix of a string Let $\Sigma = \{ \sigma_1 , ..., \sigma_t \}$ and let $S$ be a string from $\Sigma^*$. Denote: $n=|S|$, that is $S$ has $n$ letters. I'd like to find the shortest prefix $T$ of $S$ such that $S$ is a prefix of $T^n$ ($T^n= T \cdot .... \cdot T$, $n$ times).

I tried to build the suffix tree for $S$, and then checking each node, by their levels - from lowest level to top level, because then the corresponding prefix will be shortest at the lowest level of the suffix tree and will get longer - and then for each node checking if this property applies for the prefix of the current suffix node I'm looking at, but that would not necessarily give me the shortest prefix, because the suffix tree may have on the same level different lengths suffices.

I'm not sure as to how I'll be able to find the shortest prefix $T$? Perhaps there is a different way of using a suffix tree?

Or maybe there is a way to solve this efficiently without using suffix trees at all?

Repetitions and periods in strings constitute one of the most fundamental
  areas of string combinatorics.1

The shortest prefix T of S where,

$S = T^k.Q , s.t: k>= 1,  Q =$ some prefix of T, then |T| is called the period of string.

  We say that string w has period p if w[i] = w[i + p] 1

Conventionally, finding T can be done by the Knuth–Morris–Pratt algorithm as well as Boyer–Moore string search algorithm.

Proving the correctness is beyond the scope of this answer.(More precisely, beyond my scope). See 1 for a better idea.

Before I came to know this, I attempted to solve this using KMP. And later, luckily, others have confirmed it. This could be helpful if one is wondering how could one possibly get an idea that KMP would work. I first tried to figure out the pattern and thought KMP could do the job.

Wondering how ? Our aim is to make $S$ a prefix of $T^n$ i.e. $TT \cdot .... \cdot T$, $n$ times. You can see that T is repeating itself, so, should some prefix of $S$ too.

E.g. take $S = abc$, the only way you can have $TTT$ and $S$ as a prefix of $TTT$ ($T^3$) is if $T = abc$, then $abc$ is a prefix of $abcabcabc$. The minimum part which is repeating is the complete string $abc$. Hence, $T = abc$.

But, if $S = aba$, then $T$ can be $ab$, and $aba$ is a prefix of $TTT$ i.e. $ababab$. The minimum part which is repeating is just the string $ab$. Hence, $T = ab$.

You're roughly getting the idea that finding that part of prefix of $S$, where it is repeating itself in the rest of $S$ and ending with some part of it.

Final e.g. would be $S = abababa$, then again $T$ would remain $ab$, i.e, the prefix which is getting repeated and ending with some part of it. We could form $S$ as $T^k.Q: s.t. k >= 1, Q =$ some prefix of $T$, here $a$.

Now your job is pretty easy. For every prefix in $S$, check if it is present in the rest of $S$ as described above. The shortest one you find would be the answer.

KMP has an essential part called "Prefix Function". Below is the code for the Prefix function in C / C++. When I ran it over a couple of strings S, I found good results.

void make_prefix_fun(char pat[], int a[], int m){
    // i is moving forward, and j is staying behind.
    a[0] = 0 ;
    for ( int i = 1, j = 0 ; i < m ; i++ ){
        while ( pat[j] != pat[i] && j > 0 )
            j = a[j-1];
        if ( pat[j] == pat[i] )
            j++;
        a[i] = j;
    }
}

Sample Cases:
aba
a b a
0 0 1
//  ^ T = S[1..(|S| - 1)]

adbashdbhabsjd
a d b a s h d b h a b s j d
0 0 0 1 0 0 0 0 0 1 0 0 0 0
// T is the complete S    ^

abcdabcda
a b c d a b c d a
0 0 0 0 1 2 3 4 5
//              ^. T = S[1..(|S| - 5)]
// Cool. Found something here.

abababababababababa
a b a b a b a b a b a b a b a b a b a
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// Cool. Found something here.              ^. T = S[1..(|S| - 17)]

abababababababababaaaa
a b a b a b a b a b a b a b a b a b a a a a
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 1 1
// Working exactly as expected.                   ^

Found a pattern? Yes, we do.

If you observe the array, after the first couple of consecutive 0s,

if we get the series, 1,2,3...x strictly upto the end, we can have our T = S[1..(|S| - x)] and the length of your required T is N - a[N] where N = |S|.
else T = entire string S.

The required T is the longest prefix of S, which is repeating itself in S, and S ends with some prefix of T or in other words T = S[1...|T|], where |T| is called the period of the string.

References:

1 - Repetitions in strings: algorithms and combinatorics, Crochemore et al.

Credits:

devnum, Mihai Calancea, Hendrik Jan.


The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy? To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with each order being equally likely. Given the fact that the lengths of sticks are not known to Py in advance. On each step, Py takes a single stick from Px. After that, he/she either picks the stick and finishes the game or discards
the stick and moves on to the next stick. Note that Py can compare relative lengths of all already
seen sticks.

Note that: The answer is considered correct if the absolute or relative error does not exceed 10e-7

Constraints: 1 <= N <= 10e5

Sample Inputs and Outputs:(n -> probability)

1 -> 1
2 -> 0.5
3 -> 0.5
10 -> 0.398690476190

Notes:
In the first test, Py chooses the first stick because it is the only one stick.
In the second test, it does not matter if he/she chooses the first or the second stick. The probability of
choosing the longest one is 0.5.
In the third example, he bypasses the first stick, because if Py chooses it the probability would be
1/3. Then if the second stick is longer than the first one he/she chooses it and if it is smaller than the first
one Py moves on to the third one.

My Attempt:
I noticed that this is a binomial distribution problem since there are n attempts and each attempt is independent. Using the formula for the binomial distribution, I can not find the answer for n = 10, x =1, p = 1 /10, I got 0.387420489. I am struggling to find a solution is there any misconception I did? How to approach to a solution?

If you tried to get the longest stick out of 10, and they were shown to you in random order, how would you proceed?
Here’s a simple strategy, based on the simple idea that it’s daft to pick a stick that isn’t the longest so far: Don’t take any of the first four sticks, then pick the first stick that is longer than the longest so far. How will this work out?
If the first four contain the longest stick, you lose. If the first four contain the second longest stick, you win because you will pick the longest. If the first four contain the third longest stick, then you will pick the longest or second longest, 50% chance to win, and so on.
Chances are 65.61% that the first four don’t contain the longest, and 40.96% that they contain neither of the two longest; that alone gives you a 24.65% chance to win because you must pick the longest stick. You can calculate your chances to win quite easily: let p(k) be probability (“None of the p largest”) - probability (“None of the p+1 largest”), then your chance to win is p(1) + p(2)/2 + p(3)/3 ...
You would also check if skipping the first three or five or any other number might be better.
If you ignore about the first n/e sticks, this will give you a winning chance around 1/e even when n is very large.


Is there C++ code that takes infinite time to compile? Is C++ as a formal language recursively enumerable? If yes, is there any invalid C++ code that takes "infinite" time to compile?

In theory this code should compile infinitely

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

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


Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent? I fail to understand why cut off value would be system dependent, and not a constant.

From Princeton University website

  Cutoff to insertion sort. As with mergesort, it pays to switch to
  insertion sort for tiny arrays. The optimum value of the cutoff is
  system-dependent, but any value between 5 and 15 is likely to work
  well in most situations.

Would it be safe to assume that optimal cut off value is equal to optimal set size for Insert sort?

Because the actual running time (in seconds) of real code on a real computer depends on how fast that computer runs the instructions and how fast it retrieves the relevant data from memory, how well it caches it and so on. Insertion sort and quicksort use different instructions and hava different memory access patterns.  So the running time of quicksort versus insertion sort for any particular dataset on any particular system will depend both on the instructions used to implement those two sorting routines and the memory access patterns of the data.  Given the different mixes of instructions, it's perfectly possible that insertion sort is faster for lists of up to ten items on one system, but only for lists up to six items on some other system.


What is average number of cycles in an undirected ordered graph of size n? What is average number of cycles in an undirected ordered graph of size $n$?
I've tried finding out sum of number of cycles in all sorts of a graph of size n but I couldn't find that out.

Hint: Suppose that there are $Z_m$ cycles of length $m$, and that $p_m$ is the probability that a specific cycle of length $m$ is in the graph. Then the expected number of cycles is
$$ \sum_{m=3}^n Z_m p_m $$
due to linearity of expectation.

Here is the entire calculation. In the $G(n,p)$ model, in which each edge is present with probability $p$ independently, clearly $p_m = p^m$. The number of ordered $m$-tuples of points is $n!/(n-m)!$. Each cycle of length $m$ is described by $2m$ such tuples: choose a starting point and an orientation. Therefore the total number of cycles of length $m$ is $n!/2m(n-m)!$, and the expected number of cycles is
$$ E = \sum_{m=3}^n \frac{n!}{2m(n-m)!} p^m. $$

In order to estimate this number, let's find the largest term. The ratio of two successive terms is roughly
$$ \frac{p^{m+1}}{(n-m-1)!} \frac{(n-m)!}{p^m} = (n-m)p. $$
When $p$ is constant, we see that the most important term corresponds to $m = n$, namely $n! p^n/(2n)$, and we deduce that for large enough $n$, the expected number of cycles satisfies
$$ 2(n-1)! p^n \leq E \leq 2n! p^n. $$


Understanding proof for Busy Beaver being uncomputable I found this proof on http://jeremykun.com/2012/02/08/busy-beavers-and-the-quest-for-big-numbers/ and have highlighted the part I don't understand in bold.

(BB(n) is defined as the number of steps made by n-state Busy Beavers.)

  Theorem: BB(n) is uncomputable. That is, there is no Turing machine
  that can take as input n and computes BB(n).

  Proof: Suppose to the contrary that such a machine existed, and call
  it T. We will use T to construct a machine which solves the halting
  problem as follows:

  On input < T, w >, a description of a Turing
  machine and its associated input, we can determine in finite time the
  number of states that T has (it is encoded in the description of T).

  Now simply compute BB(n), where n is the number of states in T, and
  simulate T on input w, counting its steps as it proceeds.
  Eventually the simulation of T either halts, or makes more steps than BB(n).

  In the former case, we may stop the computation and declare that T halts.
  In the latter, we know that BB(n) is the maximal number of steps that
  can occur for any Turing machine with n states that eventually halts.
  Therefore, if T had not halted on the input w, it must never halt.

  We may stop our computation there, proclaim an infinite loop, and thereby solve the halting problem.

  This is a contradiction, so the sequence BB(n) cannot be computable.

If we assume that T can calculate BB(n) for any n, don't we also have to assume that it does halt, and therefore that it will not exceed the steps of BB(n)? (That would also mean that using T to solve the halting problem does not work)

Just for the completeness, I will present my proof that shows uncomputability of BB function.
The structure of a correct proof would look something like the following.

Construct a universal Turing machine U that simulates any other Turing machines but writes ‘1’ on the output tape for every step of the simulation.
For any Turing machine M, there is an encoding 〈M〉for U. We create a new Turing machine by adding new states in U which first writes〈M〉on its input tape and runs it on U. Call this new Turing machine UM.
Let n be the number of states in UM, and m be the number of states in M. We can see that BB(n) upper-bounds the number of 1’s outputted by UM and also upper-bounds the maximal number of steps run by the halting Turing machine with m states. Hence, S(m) <= BB(n), where S(m) is the maximal number of steps run by a halting Turing machine with m states.
Given a Turing machine of size m, we can always determine corresponding value for n.
If there is any function that always upper bounds S, it is uncomputable as it will contradict with the result from the halting problem. (Run a Turing machine that many steps to determine whether it halts or not)


Branch Prediction question My question relates to a video I watched on YouTube.

The pipeline is a 5-stage pipeline which include fetch, decode, ALU, Mem (data), and Write.

It mentions that nothing is fetched until we're sure what to fetch. How can that be though? Won't you need to fetch and decode an instruction first to know what to fetch?

He mentions that the ADDI instruction gets fetched, but then goes in a bubble since it's not a branch. I really do not understand what is happening here and why the CPI for each instruction are ADDI=2, ADD=2, and BNEZ=3.

Can any explain to me what's going on here? Maybe a table with cycle iteration would be helpful.

Here's the video link: Branch Prediction question

I figured out what he means: fetch the instruction and decode it, but do not fetch the next instruction until you've determined whether it's a branch or non-branch instruction.

For the non-branch instructions, it will fetch next instruction after the decode stage. But for the branch instruction, it will require an extra cycle to determine it should stay in the loop or not.

The CPI does add up if I do follow through with what I've mentioned. I've added a picture to give you a better picture of what's happening at each cycle.


Proving NP hardness about graph creation I have graph creation problem.

Given a set of nodes of graph, and node constraints such as given every node's number of neighbors and number of neighbors of neighbors and so on. I want to create a graph that can satisfy all these constraints (# of constraints is polynomial in n).

I have formulated the problem as an integer programming wherein I am trying to create possible edges by assigning them random variables $z_{i,j} \in $ $\{0, 1\}$ and then trying to satisfy the constraints of # neighbors, # neighbors of neighbors and so on (k steps). However I am not sure if this is a NP complete problem because the constraints are non-linear.

If you are given just the degree sequence (the number of neighbors of each vertex), then the Havel–Hakimi algorithm is an efficient algorithm that constructs a graph conforming to the degree sequence, if possible, and alerts you otherwise. If you are given the second-order degree sequence (the number of vertices at distance 1 and at distance 2 from each vertex), then the problem of determining whether such a graph exists becomes NP-complete, as shown by Erdős and Miklós in their paper Not all simple looking degree sequence problems are
easy.


Correctness of algorithm to find maximum in array I want to show correctness of "Algorithm to find maximum element in array" using induction and contradiction.

ans=-infinity
for (i=0; i<n; i++)
    ans= max(ans, A[i])

where A[0:n-1] is array and max is the function to return maximum of its two arguments.

What I am doing:

Base case: i=0, ans= max(-infinity,A[0])=A[0], as only one element has been processsed, it is maximum.

Induction Hypothesis: i=k<n-1, assume the algorithm correctly find maximum upto k iterations.

Inductive Step: i=k+1, let ans_{i} denote maximum element obtained by algorithm upto i steps and let ans'_{i} denote another maximum element from array A[0:i-1].

Then from induction hypothsis, ans_{k} = ans'_{k}

Now, for the sake of contradiction, assume ans_{k+1} < ans'_{k+1}

Now, how should I proceed to show this contradiction ?

Any suggestion? Should I change this approach ?

Tip: It's usually easy to proof by contradiction. Ignore the rest if you liked the suggestion.

Suppose you found some ans using your algorithm and ans is not the biggest.

If it's not the biggest, it means at some point, your ans was compared to a value X that's bigger than ans and max(ans, X) returned you ans.

Since max returns only the maximum value and X is bigger than ans, it's a contradiction.

By induction in the size n of the array, it's quite easy:

Base case: n = 1

the algorithm will run and return the only element who is also the biggest [OK]

Hypohtesis: The algorithm works for any n

Inductive Step: It works for n+1

Let's say you runned the first n elements of the array and you have your ans.
Now you will just compare ans with the last element and you will return the biggest.
As ans was the biggest from the first n elements (by hypothesis, we can find the biggest between n elements) and ans will be the maximum between ans and the last element, ans will be the maximum of the full array. [OK]

hope it helps.


Can the subset sum problem work with an undefined set? To give a brief outline of my actual problem, I'm attempting to identify possible impurities in proteins. I have a theoretical mass and an experimental mass, and the difference between the two would in theory be caused by any impurities present in the proteins. Impurities could take the form of an amino acid insertion, an amino acid deletion, an amino acid substitution, or an amino acid modification (modifications can both add and subtract mass).

Every impurity can be associated to a known change in mass, so I want to use the subset sum problem to get all subsets of impurities that add up to the delta mass. My issue is that I'm working with an undefined set. I know what impurities I can have, but I don't know how many of each I can have.

Is it possible to get the subset sum problem to work with an undefined set such as this? Is there a better algorithm I could implement to solve the issue?

If you only have extra impurities, then the DECOMP program described in the following paper will efficiently solve the problem -- even if you only have an approximate mass difference $d$ to work with:

DECOMP--from interpreting Mass Spectrometry peaks to solving the Money Changing Problem (Böcker S., Lipták Z., Martin M., Pervukhin A., Sudek H. 2008)

The paper cites earlier papers by the same authors that describe the underlying Round Robin algorithm -- a very nice and fast algorithm based on Frobenius numbers for solving a problem that people previously resorted to tables computed using brute-force to solve.

To deal with "negative impurities" (components that should be present but are absent from the experimental sample), I think your best option is to try all possible "missing mass" values $a$ in a small range that includes zero, and for each such value $a$, use DECOMP to solve two problems: One that finds all possible combinations of "missing" components that solves for $a$, and one that finds all possible combinations of "extra" components that solves for $d+a$.  Every pair of (missing, extra) component multisets is then a solution for the chosen $a$.

Bear in mind that, if there is a subset of components that sums to zero, then there will be an infinite number of solutions, since it is always possible to add another copy of this component subset to a solution to get another valid solution.


Unordered pairs in Homotopy Type Theory It's conceptually simple to state what an "unordered pair" is supposed to be in set theory. Yet, in homotopy type theory I have trouble formalizing this. A first naive try in agda syntax:

data UPair (A : Type ℓ) : Type ℓ where
  mkpair : (x y : A) → UPair A
  uswap : ∀ a b → mkpair a b ≡ mkpair b a

This fails, since there are actually two different paths between e.g. mkpair 1 2 and mkpair 2 1, that is we have uswap 1 2 and sym (uswap 2 1). Again, these can be forced equal by a one-higher path constructor, but one would have to continue for ever.

Obviously, if A is an n-truncated type, we can stop at some point. Generally truncating at some level fails because it might forget some non-trivial paths in A. Take for example the set-truncation of the above type and A = S¹, the circle, then the path i. mkpair (loop i) base is lost and identified with refl (mkpair base base).

Can we generally write down the type of unordered pairs of a parameter A : Type ℓ? Can the resulting type live inside the universe ℓ?

Clarification:

Let A· = (A , a) be a pointed type. Define UPA· = (UPair A, mkpair a a) as a pointed type. I would then expect Ωₜ UPA· ≡ UPair (Ωₜ A·). These correspond to singleton sets.

Let A∙ = (A, a, b) be a bipointed type with a ≢ b. Then I expect that the map (a ≡ a) × (b ≡ b) → mkpair a b ≡ mkpair b a given by (pa , pb) → (λ i → mkpair (pa i) (pb i)) ∙ uswap a b is an equivalence.

The type of unordered pairs in a type $A$ is defined to be $$\sum_{(X:\mathcal{U})}\sum_{(H:\|X\simeq \mathsf{bool}\|)}A^X.$$ In other words, an undordered pair in $A$ is simply a map $X\to A$ from a type $X$ that merely has two elements.

Note that in general, this is not a set, because the type of 2-element types is not a set but a 1-type. The way to think about this is that unordered pairs have some symmetries (swapping the order of the elements in the unordered pairs) that should be taken into account in homotopy type theory.

Note that the type of unordered pairs can also be used to define the type of fully coherent commutative binary operations on a type $A$. This type is simply $$\Big(\sum_{(X:\mathcal{U})}\sum_{(H:\|X\simeq\mathsf{bool}\|)}A^X\Big)\to A.$$
In other words, a fully coherent commutative binary operation on $A$ is an operation on the unordered pairs of $A$.


Showing two Turing machines decide different languages I want to figure out how two languages are different. If we have TM M and TM N, how would I figure out if the languages are different? My intuition is that if a M accepts an input a and N does not then that would prove the languages are different, right?

I'm not too sure if I'm thinking of this correctly.

Languages are just sets (of strings). As with any pair of sets, you show that they're different by showing that one set contains an element that's not in the other. Note that, in general, the problem of determining whether two Turing machines decide the same language is undecidable, so there's no algorithm you can use to generate such a string, in general. But, for any two given Turing machines, you can still try to figure it out.


Knapsack Greedy Approximation: Worst Case I am currently studying approximation algorithms and I have run into an issue with a study problem.

The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, where it sorts by the value/weight ratio, and picks the first item in this list that pushes the weight over the limit, and then picks either all the previous items or this particular item, whichever has a greater value.

The claim is that there is at least one case where this algorithm provides a value half that of the optimal value, but after many fruitless attempts I don't see a way to do this.

I have tried many value/weight pairs of 1/1 with a last pair of 5/6, resulting in a ratio of 5/9. Close, but even if I continue this process I am only going to approach a ratio of 1/2, but never achieve it.

Any hints as to how to proceed?

The approximation ratio is always strictly larger than $1/2$. Let $p_1,\ldots,p_{k-1}$ be the values of the items picked by algorithm, and let $p_k$ be the value of the next item which would have been picked had it fit. Let $\alpha$ be the fraction of $p_k$ that does fit – so $\alpha < 1$. These lecture notes (Claim 2) show that
$$ p_1 + \cdots + p_{k-1} + \alpha p_k \geq OPT, $$
where $OPT$ is the optimal solution. In particular,
$$ p_1 + \cdots + p_{k-1} + p_k > OPT. $$
The algorithm picks either items $1,\ldots,k-1$ or only item $k$, and there is some choice that results in strictly more than $OPT/2$.


Why does a reduction from a P-problem to an NP-complete problem not show that P=NP? Consider the following problem, called BoxDepth:

  Given a set of $n$ axis-aligned rectangles in the plane, how big is the largest subset of these rectangles that contain a common point?

Say we proved these two statements:

There is a a polynomial-time reduction from BoxDepth to MaxClique.
There is a polynomial-time algorithm for BoxDepth with $O(n^3)$ runtime.

Why don’t these two results imply that P=NP?

Part 1 shows how to solve BoxDepth using MaxClique.

Part 2 shows how to solve BoxDepth directly.

None of the parts says anything about solving MaxClique.


Is the set of Gödel numbers of computable constant functions recursively enumerable? I've been working on the following exercise:

  $S = \{ x | f_x  \text{ is constant} \}$. Is $S$ recursively enumerable?

Here, $fx$ is the function computed by the $\text{x-th TM}$. So it is a computable function.

Intuitively, I think that to check if $S$ is constant, I would have to check if $f_x$ stops for every input. That procedure would run forever.

Important: Same thing about $\overline{S}$, if some $f_x$ is undefined for every input $y$ (it would not be constant, as far as I understand, it is constant if it has the same image for all input values) then I would not be able to list $f_x$ in an enumeration of $\overline{S}$.

In fact, suppose $\forall x,fx$ is undefined. This $f_x$ is computable - a TM can be constructed that loops forever. How can you determine that $f_x$ is not constant? There will be no input for which $f_x$ halts. Therefore, we cannot check for equality of $x_1$ and $x_2$ to determine that is not constant. Then, we can't list this $TM_x$ in the enumeration.

A solution in which this $f_x$ was put at the beginning of the enumeration was suggested. But there are infinitely many $TMs$ that are undefined for all inputs. Consequently, I can't put them at the beginning of the enumeration as other $TMs$ won't be enumerated.

I tried to reduce the Halting Problem to this problem without success. I believe that both $S$ and $\overline{S}$ are not r.e. (see my intuitive thoughts above).

How would you solve this problem?

Your intuition is good: checking whether $x \in S$ is stronger than checking $x \in K$ ($K$ the halting problem, i.e. $K = \{ x \mid f_x(x) \text{ halts}\}$). In other words,

$\qquad\displaystyle \langle \operatorname{sgn} \circ f\rangle \in S \implies f \in K$.

However, the reverse does not hold and no similar implication works for $\overline{K}$, the reduction partner we really want (as it's not semi-decidable).

A small interlude: the title you chose does not actually fit the question! The set of all constant functions is in fact recursively enumerable, e.g. by

$\qquad\displaystyle \varphi_i(x) = i$

which is clearly a computable function. Many sets of functions are enumerable like this, but not all.

What you are really asking is: given a Gödel numbering (e.g. an encoding of all Turing machines), what about the set of all indices (read: programs) that compute this here set of functions? That's another thing entirely because of the properties such a Gödel numbering has. The distinction is important, see e.g. here.

The basic idea for a reduction is always this: build a function that depends on $x$ and whose encoding is in $S$ if and only if $x \in \overline{K}$ -- then we got a deal.

So, consider

$\qquad\displaystyle g_x(n) =
    \begin{cases}
        n, &f_x(x) \text{ halts after at most $n$ steps } \\
        1, &\text{else}
    \end{cases}
$

which is clearly computable. Note furthermore that given $x$, we can compute $y$ with $f_y = g_x$; such compilation is possible because we have (or can assume) a Gödel numbering. Now, clearly

$\qquad \langle g_x \rangle \in S \iff x \in \overline{K}$

holds; thus $S$ can't be semi-decidable since $\overline{K}$ would then be semi-decidable, too, contradicting what we know.


NP completeness proof of a spanning tree problem I am looking for some hints in a question asked by my instructor.

So I just figured out this decision problem is $\sf{NP\text{-}complete}$:

In a graph $G$, is there a spanning tree in $G$ that contain an exact set of $S=\{x_1, x_2,\ldots, x_n\}$ as leafs. I figured out we can prove that it is $\sf{NP\text{-}complete}$ by reducing Hamiltonian path to this decisions problem.

But my instructor also asked us in class:

  would it also be $\sf{NP\text{-}complete}$ if instead of "exact set of $S$", we do

  "include the whole set of $S$ and possibly other leafs" or
     "subset of $S$"

I think "subset of S" would be $\sf{NP\text{-}complete}$, but I just can't prove it, I don't know what problem I can reduce it to this. As for "include the set of $S$..." I think it can be solved in polynomial time.

In short, your guesses are correct.  For the purpose of this answer, let’s call the three problems in question as follows:

Equality version: Given a graph $G = (V, E)$ and a set $S \subseteq V$, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is equal to $S$.  As you stated, this is NP-complete by a reduction from the Hamiltonian path problem.
Subset version: Given $G$ and $S$ as above, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is a subset of $S$.
Superset version: Given $G$ and $S$ as above, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is a superset of $S$.

To prove that the subset version is NP-complete, you can still reduce the Hamitonian path problem to it.  Try to modify the proof of the NP-completeness of the equality version.

To prove that the superset version can be solved in polynomial time, try to find a necessary and sufficient condition for such a tree $T$ to exist.

Both versions (as well as some other problems about spanning trees) are studied in [SK05].  But I guess that it is better if you try to solve the problems by yourself before looking at the proofs in the paper, because looking at the paper can be a big spoiler.  Unfortunately I had looked at the paper before trying to find a polynomial-time algorithm for the superset version!

[SK05] Mohammad Sohel Rahman and Mohammad Kaykobad.  Complexities of some interesting problems on spanning trees.  Information Processing Letters, 94(2):93–97, April 2005.  [doi] [author copy]


Is "lazy evaluation" part of the compilation process or a run-time feature? I'm studing the Clean functional programming language, and like other functional PL it uses Lazy Evaluation.

The thing that I can't get is when a PL that using that kind of evaluation evaluates the needed parameters.
Does the compiler recognize which parameters are used and generate the code for evaluating them? or maybe some run-time mechanism takes responsibility to evaluate the parameters?

My question is about the concept of Lazy Evaluation in general, not just about this particular language.

Thanks in advance!

I am not familiar with Clean; this answer addresses Lazy Evaluation in general.

Lazy evaluation happens at runtime.

The most fundamental form of lazy evaluation is leftmost reduction in lambda calculus. I will not burden this answer with a full introduction to lambda calculus. The intuition is that terms in lambda calculus consist of function definitions and function applications (and little to nothing else). Runtime of a program (which is a term) means evaluating the term. For an application term (which you can think of as $f(a)$), both $f$ and $a$ are also terms. Evaluating $f(a)$ may entail evaluating $f$ and/or $a$. The principle of leftmost reduction (lazy evaluation) means that $f$ is evaluated before $a$. Let us say $f$ is the function defined by $f(x)=x+x$ and $a$ is the term $1+2$. Then, lazy evaluation proceeds with the following steps:

$f(a)$
$a+a$
$(1+2)+a$
$(1+2)+(1+2)$

(At least if $+$ does not have a definition of its own. If it has, then after 2. the definition of $+$ will be expanded.)

If, on the other hand, $f$ is defined by $f(x)=0$, the evaluation is

$f(a)$
$0$

You notice that $a$ is not evaluated (because it is not needed), hence the connection to lazy evaluation. One final comment on this part: Lambda terms are in prefix notation, so "leftmost" actually means "outermost" when you think in terms of nested function applications.

In the second example above, lazy evaluation led to a speedup, because the term $a$ was not evaluated. In the first example, it led to a slowdown, because $a$ was evaluated twice. Actual lazily evaluated functional programming languages usually (again, I am not familiar with Clean) make the following optimization: Terms are not stored as syntax trees but as syntax dags. That is, in the first example, the two $a$ in term 2 would be the same node, also shared among all other positions of all other terms into which $a$ might have been copied. As soon as lazy evaluation dictates that $a$ is evaluated, the result is stored in place of the node $a$, becoming immediately available at all other occurences of $a$. The effect is a bit like memoization.


How to calculate information gain in ID3? I am trying to implement a decision tree classifier using ID3 algorithm. According to Aritificial Intelligence - A Modern Approach, information gain of attribute A is given by:

Gain(A) = B(p/p+n) - Remainder(A)

where B is the entropy of a Boolean random variable and p and n are the number of positive and negative examples in the training set.

My question is:

do p and n always refer to examples in the full dataset, or the remaining examples in current partition of the set?

If the former applied, the value of B would remain fixed throughout the training procedure. Is this correct?

It's important to use the current partition.  See, e.g., the pseudocode in Wikipedia: https://en.wikipedia.org/wiki/ID3_algorithm#Pseudocode

Typically, this is implemented as a recursive algorithm.  When you recurse, you don't recurse on the entire training set; you  recurse on the subset of examples that reach the tree node you're trying to build.