How can the VC-dimension of Turing machine be finite? The VC-dimension of a hypothesis class $\mathcal{H}$ is defined to be the size of the maximal set $C$ such that $\mathcal{H}$  cannot shutter. This paper shows that the VC-dimension of the set of all Turing Machines with $n$ states is $\Theta(n \log n)$.

However, suppose that we take the set of all such Turing machines, for $n$ sufficiently large so that the universal Turing machine is a member of $\mathcal{H}$. The result states that there exists a set $C$ (wlog, $C \subset \{0,1\}^*$) of size, say, $n^2$, such that $\mathcal{H}$ cannot shatter. To my understanding, it means that there exists a function $f : C \rightarrow \{0,1\}$ ("labeling"), such that for every $h \in \mathcal{H}$, it holds that $h \neq f$. Since the elements of $\mathcal{H}$ are Turing machines, I say that "$h$ computes $f$" when the machine $h$ implements $f$.

But $C$ is finite hence $f$ is clearly computable, thus there is some Turing machine $M_C$ which computes it, therefore $M_C$ can be simulated by the universal Turing machine, which is in $\mathcal{H}$, and this is a contradiction (since we assumed $\forall h \in \mathcal{H}, f \neq h$ ). Where is the problem with this argument?

First, let me correct your definition of VC dimension: it is the largest size of a set which can be shattered.

If the VC dimension is $d$, then this means that for every set $C$ of size larger than $d$ there exists a function $f\colon C \to \{0,1\}$ which is not compatible with any function computed by an $n$-state Turing machine.

You are attempting to refute the claim that the VC dimension is $\Theta(n\log n)$ by showing that for any set $C$ of size $n^2$ there exists a single function $f\colon C \to \{0,1\}$ which is compatible with some function computed by an $n$-state Turing machine. However, what you need to do in order to refute the claim is to give a single set $C$ of size $n^2$ (say) such that all functions $f\colon C \to \{0,1\}$ are compatible with some function computed by an $n$-state Turing machine. Note the different quantifiers: you considered all $C$ and one $f$, but in fact you should consider a single $C$ but all $f$.

Finally, suppose that $M$ is a universal Turing machine having $n$ states. This doesn't mean that $M$ can compute arbitrary functions – in fact, $M$ computes a single function. What it does mean is that for any Turing machine $T$, $M(\langle T \rangle, x) = T(x)$. That is, if $M$ is given as input the pair $(\langle T \rangle, x)$ (where $\langle T \rangle$ is the encoding of $T$), then $M$ evaluates $T$ on $x$. This is different than what you claim, since the Turing machine being simulated is part of the input, that is, part of the set $C$.

In fact, in order to show that the collection of $n$-state Turing machines shatter a set $C$, you need to exhibit $2^{|C|}$ different Turing machines. Considering just a single universal Turing machine cannot possibly work.

Since there are only $O(n)^{O(n)}$ many different Turing machines having $n$ states (assuming the alphabet is fixed), this implies that the class of $n$-state Turing machines cannot shatter any set of size larger than $\log[O(n)^{O(n)}] = O(n\log n)$. This is how you get the upper bound on the VC dimension. The lower bound looks more challenging.


Complexity Theory - Why can't you use diagonalization to seperate classes A and B when an orcale O exists under which A=B? In a recent lecture the professor stated that given two complexity classes A and B, and given the existance of an oracle O such that $$A^o=B^o$$
(As I understand, meaning that a problem in A with can be reduced to a problem in B with the oracle O), It can be shown that classes A and B can not be seperated using a diagonilization argument.

Unfortunately he did not explain much further... Can someone give the outline\thought process of the general proof (informally)? I think I understand why diagonalization fails in specific time hirearchy proof constructions (due to the existence of a cook reduction) but I can not see how to generlize this in a satisfactory way.

Thank you.

In order to explain this, you need to understand what is meant by "diagonalization argument".

In this context, we mean a proof that  only treats Turing machines as black boxes, i.e. only uses the fact that we can encode Turing machines as strings and treat them as inputs to other machines. This gives rise to the possibility of simulation, a machine $M$ can simulate some machine $M'$ without paying too much in space/time.

You can now observe that such proofs immediately generalize to the oracle model (encoding and simulation are possible), so if you could write such a proof for $A\neq B$, it would also work in the oracle model, showing $A^\mathcal{O}\neq B^{\mathcal{O}}$.

For further reading you could go to "Computational Complexity: A Modern Approach", by Arora & Barak. They have a section on limits of diagonalization.


What are good counter-examples when training an apple classifier? I am doing a project in order to recognize an apple. (I am using Emgucv with Visual Studio 2010 C#, if that's relevant). My project is a classification (is or is not an apple). I have 2000 images of apples but I need images for the second class.

I have read about classification using ANN but they have multiple classes but I need to recognize if image contain an apple or not. So what kind of images do I need for the second classes? I want to use background of apples like second class. Is that a good idea?

I only want that ANN recognize if a image contain a pen or not so I have 2 classes(pen and non-pen) My question is What kind of image can I use to the second class? For example My first class are images of pen and second class are images of non pen (pencil, apples, grapes, tables); is that correct?

A standard approach is to pick a standard image bank of other images that you might run into that aren't apples, and use that as your other class.  The way you figure out what kind of images you need is: figure out what kind of images your classifier might be run on, and try to make the training set as similar as possible to the kinds of images that it will be run on in production.


A general question on NP class problem I read the paper Certification-Cognizant Time-Triggered Scheduling of Mixed-Criticality Systems (Baruah and Fohler, in Proceedings of 32nd IEEE Real Time Systems Symposium, 2011; see Section 6) which proves a particular problem to be NP-hard in strong sense and in PSPACE. Then they proposed a polynomial algorithm for the same problem which is sufficient but not necessary. For this algorithm, they claim that if the algorithm finds a solution then it is correct. Does this algorithm a verifier type algorithm? I am new to the field of theoretical computer science research. If anyone may explain this concept. Thanks.

In short: no, it doesn't follow from the claims you mention that this algorithm is a verifier in a meaningful use of the term.

The paper states:

  Our attempt here is to obtain a polynomial-time algorithm for
  computing these tables that is sufficient but not necessary,
  in the following sense. Our algorithm will not be able to
  generate the scheduling tables for all TT-schedulable instances;
  however, if the algorithm does generate scheduling tables for
  an instance, then these tables are correct.

So, they claim to have a polynomial time algorithm that can provide a solution for a subset of all problem instances, but there are some cases for which this algorithm fails to provide a correct solution. Furthermore, they claim elsewhere that there is some characterization of this subset.

By contrast, a polynomial time verifier for a certain problem $X$ is an algorithm, that given an problem instance $I$ of $X$ and a certificate $C$, can prove whether the instance is a YES-instance or not in polynomial time. Usually, the certificate corresponds to some 'solution' that the verifier needs to verify correctness for.

So, the algorithm in this paper can be called a polynomial time verifier algorithm for the subset it solves in polynomial time only, as a polynomial algorithm that solves a problem is also a verifier. But, the claim that this algorithm is a verifier in this sense isn't useful, as it is a strictly weaker property (at least, if $P\neq NP$ ) than being an actual algorithm for the solution.


"higher intensity" and "high signal intensity" in images I'm newbie in Computer Vision and image processing.

I'm reading the article "Automated White Matter Hyperintensity Detection in Multiple Sclerosis Using 3D T2 FLAIR" and it said:

  2.2.4. WMH Segmentation with High Spatial Frequency Suppression

  White matter lesions have higher intensity and generally clear
  boundaries relative to the surrounding WM. Unfortunately, in the 3D T2
  FLAIR images, the GM can also present with high signal intensity,
  especially in elderly people.

What does it means "higher intensity" and "high signal intensity"?

I think it means that white matter lesions are very white but I'm not sure because I don't understand why the use the words "intensity" and "signal" when they are talking about images.

The intensity of a pixel is its value (e.g., from 0 to 255).  For instance, in a black-and-white/grayscale image, pixel intensity 0 means the pixel is black, and pixel intensity 255 means the pixel is white; intensities in between the two are shades of grey.

"White matter lesions have higher intensity" means that the pixels in the area of a white matter lesion have higher intensity values.

In this context "signal intensity" is presumably a synonym for "intensity".


Analyzing the railways network I am studying complex networks and I have a question. Is it possible to use the tools and methods of the theory of complex network to study the properties of railways network? Are there any articles or project that have done this and that you can link to me?
Thank you in advance!

Certainly it is possible. For example, in the following study the Indian railway network was analyzed.

Small-world properties of the Indian railway network.
Parongama Sen, Subinay Dasgupta, Arnab Chatterjee, P. A. Sreeram, G. Mukherjee, and S. S. Manna. Phys. Rev. E 67, 036106 – 2003

In another study, the Chinese railway network was considered.

W. Li, X. Cai, Empirical analysis of a scale-free railway network in China. Physica A: Statistical Mechanics and its Applications, Volume 382, Issue 2, 2007, Pages 693-703.

The main problem is probably obtaining good data sets. However, train time tables are public, so in principle you could use data from any available time tables to reconstruct the network topology. If you also want the spatial embedding (the geographical coordinates), those might be more difficult to obtain.


Genetic Algorithm Minimum Population Size Is there a minimum limit to a pool (population) size when using the genetic algorithm to solve an optimization problem? For example a population of size 2.

There is no minimum to population size but it has a few drawbacks when it is too low.

when it is too low your genetic algorithm is almost going to be a deterministic or greedy algorithm and besides that you are going to lose the effect of weak answers. it has been proved that even the weakest answer can move the algorithm to a good answer. The nature of genetic algorithm is randomization and bias to better answers, when the population size is too low non of these are regarded.

When the population size is too low the population is going to lose the diversity so most likely your algorithm will fall in local optimums.

When the population size is too low you will face a few problems in Replacement step. because the population size is too low you will have to reject the unfeasible answers and it is a very bad idea for more illustration, look at this picture:

Let the red color be all of the answers (feasible and unfeasible), the yellow be the space of feasible answers, the green be the space of good answers that are around the optimums and the little blue spot be an unfeasible answer. As you can see an unfeasible answer is very close to the space of good answers so may be a little variation to this unfeasible answer lead to a very good answer, yes? that is why I say when the population size is too low you are going to limit yourself in Replacement step and you will have to remove the unfeasible answers and removing such answers has the bad effect that I just explained.

If the population size is too big your algorithm will be brute force! I recommended you to read the Schema Theory to know how to provide an appropriate population size.


For what special cases does this vertex cover algorithm fail or work? I'm trying to find a polynomial time algorithm for finding the minimum vertex cover for a graph. I've written the algorithm below; I know this problem is $\mathsf{NP}$-hard, which means there are probably some graphs for which this algorithm will not work.

I need some help in finding the flaw in this algorithm and also, an indication for what restrictions should be imposed on graphs such that this algorithm works.

In the algorithm below I have a graph $G=(V,E)$. I also define the $\text{priority}(v)$ function; in rough terms, it is the number of edges that are covered by vertex $v$. The function has the property that

$$\sum_{v \in V} \text{priority}(v) = \text{number of edges}.$$

In other words, an edge is counted as covered by only one of its vertices, not both.

Define degree : V -> NaturalNumbers
degree(v) = number of edges connected to v, for all v in V

Define priority : V -> NaturalNumbers
Initialize priority(v) = 0 for all v in V

For all (u, v) in E:
    If degree(u) >= degree(v):
        priority(u) = priority(u) + 1
    Else
        priority(v) = priority(v) + 1

Define S as the solution to the vertex cover problem
Initialize S to the empty set

For all v in V:
    If priority(v) != 0:
        Add v to the set S

Output S as the solution

Trying to take "high priority" i.e. high degree vertices over their neighbors will not work in all cases. This algorithm chooses $n-1$ for $C_n$ (Cycle Graph on $n$ vertices). It should choose either $(n-1)/2$ or $n/2$ if its odd or even. It also fails for Perfect Graphs.

I'm pretty sure this gives a $O(\log n)$ approximation too. If you order vertices by degree and greedily select vertices until all edges are covered, it is basically the same greedy algorithm as $O(\log n)$ set cover.


Reducing a problem to the MST problem Let $G = (V, E)$ be a connected, undirected graph. Given a subset of distinct vertices $S = \{v_1, v_2, \ldots, v_n\} \subseteq V$, how can I find a forest in which each vertex $v \in V - S$ is connected to exactly one of the vertices of $S$ and is of minimum total length?
This is a problem from an algorithms book that I'm currently struggling with. I'm pretty sure the idea is to construct a graph $G'$ on which a minimum spanning tree algorithm could be used (but I might be wrong). I've thought about it for a while, and I'm not able to make much progress. Could someone please point me in the right direction?
I thought about only keeping edges of the form $(u, v)$ where $u$ is in $S$ and $v$ isn't and running an MST algorithm, but I'm not entirely sure if this is correct.
Thanks

Hint: Add a new vertex to your graph..
Further hint:

...with an edge connecting to each element of $S$.


Subgraph isomorphisms: does large out-expansion imply large in-expansion? Let $G$ be a directed graph, and $H$ a subgraph of $G$ that contains all the vertices of $G$. (In other words, $H$ is obtained by deleting some of the edges of $G$, but not any of the vertices of $G$.)

A subgraph isomorphism $\varphi$ from $G$ to $H$ is a graph isomorphism from some subgraph of $G$ to $H$.  In other words, it is a bijective function $\varphi:V\to V$ (where $V$ is the vertex set of $G$) such that if $(\varphi(u),\varphi(v))$ is an edge in $H$, then $(u,v)$ is an edge in $G$.

Let $\Phi$ denote the set of all subgraph isomorphisms from $G$ to $H$.  For a vertex $v \in V$, define the out-expansion of $u$ in $\Phi$ to be $|\{\varphi(v) : \varphi \in \Phi\}|$ (i.e., the number of vertices that $v$ can be mapped to, under some subgraph isomorphism), and the in-expansion of $v$ to be $|\{\varphi^{-1}(v) : \varphi \in \Phi\}|$ (i.e., the number of vertices that can map to $v$, under some subgraph isomorphism).

Consider the following proposition:

  If every vertex has out-expansion $\ge k$, then every vertex has in-expansion $\ge k$.

Is this proposition true for all $G,H$?

I haven't been able to find any reason why it should be true.  (For instance, I don't think $\Phi$ is closed under inversion: $\varphi \in \Phi$ doesn't seem to imply $\varphi^{-1} \in \Phi$.)  However, playing with a few small examples, I haven't found a counter-example yet.  That said, I only tried a few simple examples, so it's possible that more trial-and-error might give a better sense.  But I thought I'd check whether anyone here has any suggestions for how to answer this.

Motivation: this problem arises in the security analysis of a proposed scheme for obfuscating/protecting circuits.  The graph represents the circuit (actually, they use a colored graph, where each vertex is given a color, and the isomorphism has to respect the color scheme; but that can probably be ignored, for simplicity), and subgraph isomorphisms represent different possible ways that the circuit might have been hidden/obfuscated.

Yes: if each vertex maps to at least $k$ vertices by a set $S$ of bijections of a finite set, then there are at least $k$ vertices that map to each vertex by these bijections.

In fact, the in-spectrum (the sequence of in-expansions) is a permutation of the out-spectrum (the sequence of out-expansions).  Note that $f$ is a bijection iff $f^{-1}$ is a bijection.  Hence one can define a bijection between $S$ and $S^{-1} = \{f^{-1}\mid f\in S\}\ $ so the spectra are then permutations of each other.

An aside: this doesn't necessarily hold for bijections of infinite sets.  Let $f_i$ be the map $1\mapsto i, 2\mapsto 1, 3\mapsto 2, \dots, i \mapsto i-1, i+1\mapsto i+1,\dots$, and take the collection of all these maps.  Then the out-spectrum is $(\omega,2,2,\dots)$ while the in-spectrum is $(2,2,2,\dots)$.


Is properly quantified 3SAT complete for PSPACE and all PH levels? I know 3SAT is NP-complete and QSAT is PSPACE-complete. However, is it true that

$$\exists X_1 \forall X_2 \cdots Q_k X_k \colon \varphi(X_1, \ldots, X_k)$$

is complete for $\Sigma_k$, the existential side of level $k$ of the polynomial hierarchy if each clause in $\varphi$ has at most 3 literals (or some other constant size bound)? Similarly for

$$\forall X_1 \exists X_2 \cdots Q_k X_k \colon \varphi(X_1, \ldots, X_k)$$

in relation to $\Pi_k$, and the quantified version with unbounded alternation in relation to PSPACE, once again with each clause of $\varphi$ having at most 3 literals (or some other constant number)?

QSAT with only 2 literals per clause was shown to be in P back in 1979.

Since the $\Sigma_k$ and $\Pi_k$ versions of QSAT can be reduced to equisatisfiable problems with 3 literals per clause using only a slight modification the method used to transform a SAT instance to 3SAT (i.e. putting all the new variables in the innermost existential group), those limited problems continue to be complete for their levels of the polynomial hierarchy.


Graph with $\Theta(2^n)$ minimum $(s, t)$-cuts Is there any graph with $\Theta(2^n)$ minimum $(s, t)$-cuts?
Given an undirected graph $G = (V, E)$ and two distinct vertices $s$ and $t$ of $G$. A minimum $(s, t)$-cut is a $(S, T)$ cut of G which has the minimum cost over ALL cuts of G, and which also satisfies the additional requirement that $s \in S$ and $t \in T$.   A minimum $(s, t)$-cut does not neccessary have to be a global minimum cut.

If we fix the vertices $s$ and $t$ in the graph, then we can have an exponential number of $(s,t)$ min-cuts.
Following is an example of a graph that contains an exponential number of $(s,t)$-min cuts.
Let the vertex set be $V = \{s\} \cup \{u_{1},\dotsc,u_{n}\} \cup \{v_1,\dotsc,v_n\} \cup \{t\}$. Let the edges set contains the edges $(s,u_{i})$, $(u_{i},v_{i})$, and $(v_{i},t)$ for each $i \in \{1,\dotsc,n\}$. Therefore, there are total $3 n$ edges. Each edge has capacity $1$.
Let $C = (S,T)$ be a cut such that $s \in S$ and $t \in T$. Consider the vertices $u_{i}$ and $v_i$. There are four possibilities:

$u_i \in S$ and $v_i \in T$. Then edge $(u_i,v_i)$ is in the cut.
$u_i \in T$ and $v_i \in S$. Then edge $(u_i,v_i)$ is in the cut.
$u_i \in S$ and $v_i \in S$. Then edge $(v_i,t)$ is in the cut.
$u_i \in T$ and $v_i \in T$. Then edge $(s,u_i)$ is in the cut.

For every pair of $u_i$ and $v_i$ at least one edge adds to the cut. Therefore, minimum cut cost is at least $n$.
To find all the cuts of size exactly $n$, add all the vertices: $u_1,\dotsc,u_n$ to $S$. It is optional to include a vertex $v_{i}$ in the set $S$.  The remaining vertices, i.e.,  $V \setminus S$ belongs to $T$. Any such cut has a capacity $n$. Therefore, it is a min-cut. Since there are $2^n$ choices of including $v_{i}$'s, the total number of min-cuts are $2^n \in 2^{\Theta(|V|)}$. Hence, we get an exponential number of min-cuts.

Note: This is an asymptotically tight bound since the possible number of $(S,T)$ cuts are at most $2^{|V|}$.


Joining points of polygon in correct order I have a point's array of some 2d shape(polygon). The polygon could be either crossed or convex, I don't know it. And I want to join those points in the correct order.

My first thought was to take some point as an origin and start looking for the closest one and so on. But this approach doesn't work for some crossed polygons, for example: on Image1, it would go from x3 to x5 because it is closer than to x4, but what I really want is to join x1-x2-x3-x4-x5-x6.

After some thinking, I've realized that my requirement correct order is very unclear because on Image2 red lines are in the correct order too. So let's add the requirement that polygon lines shouldn't at least cross.

I really confused, can someone point me in what direction I should move? Maybe it's some famous algorithm but I just don't know how to google it properly. Thanks.

Image1:

Image2:

Start from the leftmost point $x_0$ (the one with minimum $x$-coordinate). If there are ties break them in favor of the point with minimum $y$ coordinate.

Suppose for simplicity that there are no two points that are collinear with $x_0$ (this case can be handled by suitably breaking ties).

Shoot a ray vertically at an angle of $-\frac{\pi}{2}$ radians. Sweep the plane by rotating the ray anticlockwise up to an angle of $\frac{\pi}{2}$ radians. Whenever the ray intersects a vertex, let this vertex be $x_{i+1}$ where $i$ is the number of intersected vertices so far. Connect $x_{i}$ to $x_{i+1}$.
Finally, connect the last encountered vertex back to $x_0$.

In practice this boils down to writing all points in polar coordinates from $x_0$, then sorting them by their angle, and connecting them in order.


Expressing 3-SAT in first-order logic i read that First-Order Logic is strong enough to formalise all of Set Theory and thereby virtually all of Mathematics. How would you express in First-Order Logic the theorem:
 3SAT is NP-complete?

There has been a lot of work on formalizing mathematics, and in all of this work one needs to express definitions, theorems and proofs within the logic that one is using for formalization.

This is always quite involved.

To describe the statement that 3SAT is NP-complete, we will need a version of first-order logic with a term language that will allow us to express notions of languages, time complexity, Turing machines, polynomial-time reducibility, propositional logic and conjunctive normal forms.

Once we have an appropriate term language, we will need to describe 3SAT and NP-completeness in it. This requires us to be able to express the definitions of these notions, and this in turn involves the definition of first-order predicates that correspond to these notions and the notions that were used to define them.

Let us take a brief look at a part of this construction - this should convince you that this is indeed fairly involved. A language $L$ is NP-complete if

$L \in \mathrm{NP}$
For every $L' \in \mathrm{NP}$ we have that $L'$ polynomial-time reduces to $L$

We define a predicate $NPC(x)$ which holds if the following conjunction holds for $x$

$x$ is a language in $\mathrm{NP}$
for every $y$, if $y$ is a language in $\mathrm{NP}$, then $y$ polynomial-time reduces to $x$

We therefore need a predicate $NP(x)$ that captures that $x$ is a language in $\mathrm{NP}$, and we need a predicate $PTR(x,y)$ that captures that $y$ polynomial-time reduces to $x$. If we have these, then we can define

$$ NPC(x) = NP(x) \wedge \forall y. NP(y) \Rightarrow PTR(x,y) $$

The definition $NP(x)$ must capture the following

$x$ is a language.
There exists a nondeterministic Turing machine $M$ with polynomial-time complexity such that for all $w$, $M$ will accept $w$ if and only if $w$ is an element of $x$.

And this in turn requires us to define predicates $L(x)$, which must describe that $x$ is a language, $TM(y)$ which must describe that $y$ is a nondeterministic Turing machine, $ACC(m,w)$ which must describe that $m$ is a Turing machine that accepts string $w$, $TC(x,c)$ which describes that $x$ is a Turing machine within $c$ steps and $POL(c,p,n)$ which describes that $c$ is bounded by the polynomial $p(n)$.

Once we have defined these, we may have needed to introduce and define further predicates. And once this has been done, we need to define $PTR(x,y)$. Here, we can make use of some of the predicates that we already have, but we also need to introduce some new ones as well.

I hope that this outlines that this process of formalization is a involved and not entirely trivial task, and I hope this also explains why I do not present the entire construction of the first-order formula here.


Drawbacks of adding type equality to 1ML In the 1ML – Core and Modules United (F-ing First-Class Modules) paper, the author gives the following example for why module types do not form a lattice under subtyping:

 f1 : {type t a; x : t int} → int
 f2 : {type t a; x : int} → int
 g = if condition then f1 else f2

  There are at least two possible types for g:

 g : {type t a = int; x : int} → int
 g : {type t a = a; x : int} → int

  Neither is more specific than the other, so no least upper bound
  exists. Consequently, annotations are necessary to regain principal
  types for constructs like conditionals, in order to restore any hope
  for compositional type checking, let alone inference.

At first glance, it seems like the problem can be remedied by adding in type equalities:

g : (t int ~ int) ⇒ {type t a; x : int} → int

However, this "solution" isn't discussed in the paper. So it feels like I'm overlooking some obvious drawback of this idea, apart from the one that it might not be possible to encode type equality in System Fω (which is the raison d'être for the paper). Does adding type equalities make type checking/inference even more problematic in other situations?

Your proposal is an instance of a general design pattern for type systems that some would call a design smell: whenever you are stuck on an inference constraint that you cannot solve, or cannot solve in a principal way, include it in the resulting type. "It's not a problem, it's in the solution."

This solution can be made to work, but in general it may run into several practical issues:

Constraint explosion. If those tricky problems occur more often than you would think, you can end up with many constraints (in particular if you sometimes need to introduce disjunctions of constraints; this is the end). This is problematic for user readability, and type-checking time.
Loss of abstraction. The collected constraints reveal which unifications were done in the implementation, and sometimes they reveal too much details about the implementation compared to what the user had in mind. (On the other hand, they are usually principal, so what the user has in mind is not more general.)
Delayed error. If you don't check that those delayed constraints are solvable, then you may delay error: all attempts to use the value will be an error, but there is no error as definition-site. (This gives the same usability issues as C++ templates.)

Not all instances of this "putting constraints in the solution" pattern have all these problems. In your example for example, it may be possible that the specific shape of equality constraints occurring (1) have no need for disjunction of equalities and (2) let you check solvability of constraints when they are introduced. You would have to think carefully about that.


Patriot Missile Software Bug (Range Gate Calculation) Okay so I was reading about the Patriot Missile Software Bug, where to calculate the predicted range gate the missile system relied on the time keeping, however it would convert the whole/integer time number it stored (say 3600000) to 24 bit multiplying it by 1/10 (0.00011001100110011001100) to produce the time in real format in seconds, this way 'truncating' the actual time it computed before the converstion to a 'slightly smaller number' due to insufficient precision of 24 bit limitation. My question is not about the conversion or binary manipulation but rather how was the range gate calculated after taking the new calculated/truncated time into account for the purposes of establishing a 'distance/location/space' of where to look for the coming missile? Say the missile velocity is 2km/s, the time it was detected is at 100hrs.

there is some scientific/ engineering analysis of this defect & its background by professionals eg this turned up by the SEERI institute, Software Engr Ethics Research institute, An analysis of the patriot missile system (note, some glitch with figure(s) at time of this writing). essentially the missile tracking logic is highly time dependent and relies on the clock being accurate to predict the missile location and intercept position and steering corrections. there are many other "classic" bugs in software that are related to clock logic. analysis of the failure also includes/ points to inadequate testing.

another reference cited in that article, Roundoff error and the patriot missile / Robert Skeel, SIAM News.

this particular defect is getting some attention lately as it was recently ranked in the 5 most infamous software bugs of all time and of course its related to missile defense technology, a hot topic during wars.


Triple nested loop where outer and inner loop are dependent on n I am trying to count the exact/total number of iterations these nested for-loops are executed:

procedure P (integer n);
 for (i: 1 to n)
  for (j: 1 to 10)
   for (k: n to n+5)
    x := x + 1;

I know that the first for loop runs (n-1) times, the second loop runs 10-1 (9) times, thus making the time complexity so far 9(n-1). I know that the the third loop will run n+5-n (5) times, but I am not completely sure because of the n involved. I believe with this calculation added, the total runtime will be 5(9(n-1)) which will translate to O(n). In general, I am wondering if this approach of multiplying the iterations of each loop is a good approach to solving worst case running time and big-Theta estimates. Thanks in advance.

In general, I am wondering if this approach of multiplying the iterations of each loop is a good approach to solving worst case running time and big-Theta estimates.

Basically, yes. But you don't really multiply: As explained here at length, you have nested sums. In your case,

$\qquad\displaystyle \sum_{i=1}^n \sum_{j=1}^{10} \sum_{k=n}^{n+5} 1$

(if we count the number of assignment operations) is easy to evaluate because the loops do not depend on each other. It looks like multiplication here, but if you get things like

  for i = 1 to n
      for j = 1 to i
          foo

that does not work anymore.

Note that worst-case considerations and asymptotics do not enter the picture here.


A cache memory has a line size of eight 64-bit words and a capacity of 4K words A cache memory has a line size of eight 64-bit words and a capacity of 4K words.  The main memory size that is cacheable is 1024 Mbits.  Assuming that the addressing is done at the byte level, show the format of main memory addresses using 8-way set-associative mapping.

So here's what I have understood from this question so far:
Line size = 8 words = 2^3, which means that w = 3;
Cache size = 4K = (2^3 + 2^6)/(2^3) = 2^6 lines;
8-way set associative means that each cache contains (2^6)/(2^3) = 2^3
Main memory size = 1024 Mbits = 128 M

I am stuck as to how to proceed next. Any help would be greatly appreciated.

First, I'm going to do everything in bytes.

A 64-bit word means 8 bytes.

Line size: 8 words in a line, means 8 x 8 bytes = 64 bytes in a line = 26 bytes.

Cache size: 4k words, meaning 4096 x 8 bytes = 32k total bytes.

Cache indexes: 32k total bytes / 8 way set associative = 215 / 23 = 212 index positions in the cache line-set array.

Main memory: 1024 MBits = 1024 * 220 = 230 and, 230 / 8 bits-per-byte = 227 bytes (or 128 Mbytes).

So, that means there are 27 addressing bits in total for the cacheable memory.  Those 27 bits break down into 3 parts:

+--------------------+
| tag | index | rest |
+--------------------+

The "index", which is 12-bits in width, is used to lookup into the cache array to identify one cache line set.

The tag bits are used to isolate one of the lines in the set of 8 (or determine a miss).

The "rest" bits determine which bytes in the 64-byte line are the particular bytes of interest for a given memory reference instruction.  More precisely, the rest bits indicate the first byte of interest, and the memory reference instruction encodes the number of bytes of interest (e.g. 1, 2, 4, 8).

Since the line size is 64-bytes, then the "rest" is 6 bits; these 6 bits are used after the cache lookup identifies the line (on hit).

That means that the tag, which makes up the remainder, must be 27-12-6 = 9 bits wide.  A tag of this size is stored in the each cache line in the set for comparison with the tag in the address bits.

So, the 27 bits of address break down into 9 tag bits, 12 index bits, and 6 "rest" bits.  The cache line lookup operation consumes the 9 tag bits and 12 index bits, and, after the line is identified, the rest bits (and instruction-specified length) are used to extract the bytes of interest.


How to prove transitivity of < (Software Foundations exercise)? I'm working through the "Properties of Relations" chapter of Software Foundations, but have got stuck on one of the exercises, lt_trans'':

Theorem lt_trans'' :
  transitive lt.
Proof.
  unfold lt. unfold transitive.
  intros n m o Hnm Hmo.
  induction o as [| o'].
  (* FILL IN HERE *) Admitted.

The base case for the induction is straightforward, but I'm stumped as to how to progress on the successor case. Proof state is:

  n, m, o' : nat
  Hnm : S n <= m
  Hmo : S m <= S o'
  IHo' : S m <= o' -> S n <= o'
  ============================
  S n <= S o'

To apply the induction hypothesis, I need S m <= o', but I only know that S m <= S o', and so it feels there is no way to make progress. Hoping someone can point me in the right direction as to how to solve this exercise.

Not all relations are transitive, so you're going to need to use the definition of lt and le, or some lemma that you've already proved about them.

Intuitively speaking, there are two cases: either $m = o'$ or $m \lt o'$. In the first case, Hnm says that $S(n) \le o'$, from which the conclusion is one application of le_S away. In the second case, you can apply IHo'.

This form of reasoning assumes some very well-known facts about arithmetic. (It's usually hard to formally prove something if you don't already have some intuition about the topic.) But you haven't proved them yet, so you can't directly use them. Instead, you have to make these cases appear via the construction of the data or the proof. It's very common to reason about the structure of a proof hypothesis: such-and-such hypothesis is of this form, and therefore it can only have been constructed in a certain way.

An important tactic for reasoning about the structure of a hypotheses in a non-recursive way is inversion. Roughly speaking, inversion does case analysis on a hypothesis and works out how these cases can be possible, unlike destruct which does case analysis but loses information on how the hypothesis could be possible. We want to reason about how $m \le o'$ can be possible, and there's a hypothesis that's very cloes to this: Hmo. So apply the tactic inversion Hmo.

I'll let you work out the details of the proof. If you don't care about the details, Coq will fill them in for you, but as a learning exercise you should complete these auto steps by hand.

Theorem lt_trans'' :
  forall n m o, n < m -> m < o -> n < o.
Proof.
  unfold lt.
  intros n m o Hnm Hmo.
  induction o; inversion Hmo; subst; auto.
Qed.


the maximum value for which combination of merge sort and insertion sort works more efficiently than standard merge sort? I'm totally new in algorithms and I have a hard time studying how to calculate the time complexity of algorithms.

I'm studying Introduction to Algorithms, by Cormen on my own. Iam doing an exercise and I faced a problem that I couldn't solved it. first, the book asks for the worst time complexity of combination of merge sort and insertion sort. I calculated it truly and the answer is O(nk + nlg(n/k)).

second, it says:

  Given that the modified algorithm runs in O(nk + nlg(n/k)) worst-case
  time, what is the largest value of k as a function of n for which the
  modified algorithm has the same running time as standard merge sort,
  in terms of O notation?

this is the part that I have problem. I said the answer may be obtained in this way:

worst time complexity of standard merge sort = worst time complexity of modified merge sort

nlgn = nk + nlog(n/k)
k = 2 ^ k

but this can never happen and my answer is wrong. how should I solve the problem??

Thanks in advance.

Don't forget that big O notation hides constants. We want $nk + n\log(n/k)$ to be at most $Cn\log n$ for some constant $C>0$. This means that $k + \log(n/k) \leq C \log n$, and so $k - \log k \leq (C-1)\log n$. You can check that this inequality holds (for some $C>0$) if and only if $k = O(\log n)$.


What are the disadvantages of having many registers? IA-64 is an architecture that has 128 general purpose registers, are there any disadvantages (beside being more expensive and larger instruction size) to having many registers?

The disadvantage is higher latency per instruction.  Either you need to run the processor clock slower or you need to pipeline the register file, so each instruction will take more cycles.  (Pipelining the register file is difficult, and rarely done.)  A register file is a physical thing, thus must obey the laws of physics.  (In particular, that our universe has only three spatial dimensions, and that the speed of light is a constant.)  Suppose your register file is 2 dimensional (as all are today).  Then the register bits are typically arranged in a rectangle with width $b$ (where $b$ is the number of bits stored in each register) and height $N$ (where $N$ is the number of registers.)  (This assumes that the circuit to implement the bit is approximately square.)

Here's a picture of a 3-ported 4x4 register file that I found at http://gyan.fragnel.edu.in/~surve/COA/ISA/Images/Figure4.37.jpg:

Each time you read a register you need to propagate a read-enable signal to each bit of that register across the width of the array.  If the read-enable wires are buffered then
the delay to propagate a signal down the wire is proportional to the length of the wire.  (Neither the horizontal nor vertical wires in this diagram are buffered.  Buffering the vertical wires is actually hard, because that's a many-to-1 bus, not a 1-to-many point-to-point signal, so you may not be able to do that at all.  In the case that you can't buffer a wire, the wire will have a delay proportional to something like the square of the length of the wire.)

So at best a register file access is going to take time proportional to $O(b+N)$.  (That doesn't count the time for the decoder, and assumes that you somehow figure out how to buffer all the wires.)

To sum up: the more bits you are storing, the slower the storage.


How can a spinlock progress when it's busy-waiting? I read that in spinlock, process keeps on waiting for the lock continuously in a loop until it receives signal(lock) or release(lock) from other processes. This causes busy waiting and hence CPU cycles are wasted.

My doubt is, if CPU is continuously checking the value of lock variable in loop, then how will some other process completely execute critical section and release the lock as executing critical section also needs CPU and CPU is busy checking the value of lock in other process?

There might be other CPUs in the system, if one is busy waiting, another can be doing something. Furthermore, if the OS uses preemptive scheduling, the thread doing the busy wait might be preempted and another thread will do something and release the lock for example. The signal might also come from an interrupt handler, for example if the thread is waiting for the completion of some I/O operation, and an interrupt will stop the execution of the thread temporarily, signal the lock, and resume the thread.


Assigning Balls to Bins with Constraints on Which Ball to Go to Which Bin? Let us say we have $m$ bins and $n$ balls. Every bin $i$ has capacity $c_i$ which is the number of balls that can be put into bin $i$. We have $c_i\geq1$ for all $i$. For each bin $i$, there is a collection of sets $S_i=\{X_1,X_2,\ldots,X_{k_i}\}$ for given $k_i$. Each $X_j\in S_i$ is the set of balls that can be put into bin $i$. We have $|X_j|\leq c_i$ and $\emptyset\in S_i$ for all $i$.

For example, for $m=2$ and $n=3$, with $c_1=1$ and $c_2=2$, say we have $k_1=4$ and $k_2=5$. Say we have $S_1=\{\emptyset,\{1\},\{2\},\{3\}\}$. $S_2=\{\emptyset,\{1\},\{2\},\{3\},\{2,3\}\}$. This means that ball $1$, $2$ or $3$ can be each assigned to bin $1$. Also, each ball can be assigned to bin $2$. Further, balls $2$ and $3$ can be together assigned to bin $2$. We might have an instance with $k_2=6$ and $S_2=\{\emptyset,\{1\},\{2\},\{3\},\{2,3\},\{1,2\}\}$ for example.

We want to assign the maximum number of balls into the bins. Is this easy or hard?

You can reduce the Exact Cover problem to your problem. The elements in the Exact Cover problem corresponds to the balls in your problem. For each subset $T$ in the Exact Cover problem, we construct a bin $i$ with $S_i=\{\emptyset, T\}$. Then there exists an exact cover if and only if all balls can be put into the bins. Hence, your problem is NP-hard.


Algorithmic Design to Undo Rotation of Array An array $A$ of $n$ distinct, ascending integers is rotated to the right by $k$ positions, resulting in the array $A_{k}$.

That is, the element at index $i$ in $A$ is moved to index $(i+k)\mod n$ in $A_k$.

Devise a $\Theta(\lg(n))$ algorithm to recover $k$ from $A_k$ where $\lg(n) = \log_2(n)$.

To clarify, the algorithm needs to determine what the shift $k$ applied to $A$ was which resulted in $A_k$. Thus, $A_k$ is sufficient enough for the algorithm to work with in order to determine the shift since we know that $A$ consisted of ascending integers.

Any help or insight would be greatly appreciated!

I assume this is a homework question, so I will not solve it for you. I'll just give you some hints.

The problem is basically to find the drop in $A_k$, that is the pair of consecutive elements such that the second one is smaller than the first one. Indeed, these two must be the last and first element of $A$.

Now, if you are given a subinterval of $A_k$, how can you tell whether it contains the drop? Hint: It can be done in $\Theta(1)$.


Optimizing iteration over all permutations of a bit array edited for clarity:

I have two functions–$f(x)$ which returns an integer and $T(x)$ which returns a boolean–that operate on a bit array of length $n$. I am trying to maximize $f(x)$ over all $x$ which satisfy the condition $T(x) = true$. I also know that if $b$ is a binary subset of $a$ then $f(a) > f(b)$ (e.g. $f(0b1101) > f(0b1001)$. I have no such insight about $T$. Can I avoid iterating over candidates which are subsets of inputs which satisfy $T$?

My current solution is this: beginning with $x = 1^n$ and an empty array as a cache, iterate through the various permutations in order of descending population count. Test if the next input $x$ is a subset of any values in the cache. If it is not a subset and $T(x)=true$, then compute $f(x)$ and add $x$ to the cache of supersets.

However, this strategy must search through the cache on every iteration. Instead, I am imagining a tree which (for $n=5$) looks like
$$0b11111$$
$$0b11110\qquad0b11101\qquad0b11011\qquad0b10111\qquad0b01111$$
$$...$$
The root node is $1^n$, and child nodes are created by changing a single $1$ to a $0$ so that all children are binary subsets of their parents. Iterating from the root node, when we reach a node $x$ for which $T$ is true, we could skip calculating $f$ or $T$ for all of its child nodes because they are binary subsets of $x$. Unfortunately, the tree as constructed has $n!$ nodes instead of $2^n$, and nodes begin to appear multiple times in each sub-tree, so pruning the tree is not so simple. Is there a way to realize this type of optimization?

There's no possibility of an efficient algorithm here, unless you have more information about $T$. $T$ might only return true for one input and, in the worst case, you'd have to try all $2^n$ possibilities for that input before finding the right one. Or $T$ could return true iff its input contains $n/2$ $1$'s: there are exponentially many such strings and you'd have to try all of them to maximize $f$, since none of those strings is a binary subset of any of the others, so you have no information about the behaviour of $f$ on that set of strings.


Calculating Frequency of Terms with Zipf's Law I'm studying for an exam and came across this question. I feel like it's much simpler than I am making it out to be, but I'm not sure.

Suppose we have a corpus in which Zipf’s Law holds. If the most frequent term occurs one million times, and the next most frequent term occurs 250,000 times, how often should we expect to see the third most frequent term? And the fourth most frequent term?

Wikipedia has the formula $$f\left(k,s,N\right)=\frac{\frac{1}{k^{s}}}{\sum\limits_{n=1}^{N}\frac{1}{n^{s}}},$$ We
but in this problem, $N$ (the number of terms) and $s$ (the value of the exponent characterizing the distribution) aren't given. Only $k$ (the rank) is given and the frequencies of each rank. I know that Zipf's Law says that the frequency of a term is inversely proportional to the term's rank, but I don't know what that constant factor would be in $f_{t}=c\cdot\frac{1}{k}$.

The question gives you enough information to deduce $N$ and $s$.
You are given $f(1,s,N)$ and $f(2,s,N)$. Note that
$$
\frac{f(1,s,N)}{f(2,s,N)} = \frac{1/1^s}{1/2^s} = 2^s.
$$
Hence you can find $s$. In order to calculate $f(3,s,N),f(4,s,N)$ you don't really need to find $N$, since,
$$
\frac{f(1,s,N)}{f(3,s,N)} = 3^s, \quad
\frac{f(1,s,N)}{f(4,s,N)} = 4^s,
$$
using calculations similar to what we had before.

Notice that in order to solve this exercise, we had to know absolutely nothing about the Zipf law other than the formula. Stated differently, what you need in order to solve this exercise is not knowledge (apart from the formula for $f(k,s,N)$) but rather problem solving skills. One of the main goals of the undergraduate degree is to develop such skills.


Sums of Landau terms revisited I asked a (seed) question about sums of Landau terms before, trying to gauge the dangers of abusing asymptotics notation in arithmetics, with mixed success.

Now, over here our recurrence guru JeffE does essentially this:

$\qquad \displaystyle \sum_{i=1}^n \Theta\left(\frac{1}{i}\right) = \Theta(H_n)$

While the end result is correct, I think this is wrong. Why? If we add in all the existence of constants implied (only the upper bound), we have

$\qquad \displaystyle \sum_{i=1}^n c_i \cdot \frac{1}{i} \leq c \cdot H_n$.

Now how do we compute $c$ from $c_1, \dots, c_n$? The answer is, I believe, that we can not: $c$ has to bound for all $n$ but we get more $c_i$ as $n$ grows. We don't know anything about them; $c_i$ may very well depend on $i$, so we can not assume a bound: a finite $c$ may not exist.

In addition, there is this subtle issue of which variable goes to infinity on the left-hand side -- $i$ or $n$? Both? If $n$ (for the sake of compatibility), what is the meaning of $\Theta(1/i)$, knowing that $1 \leq i \leq n$? Does it not only mean $\Theta(1)$? If so, we can't bound the sum better than $\Theta(n)$.

So, where does that leave us? It it a blatant mistake? A subtle one? Or is it just the usual abuse of notation and we should not look at $=$ signs like this one out of context? Can we formulate a (rigorously) correct rule to evalutate (certain) sums of Landau terms?

I think that the main question is: what is $i$? If we consider it constant (as it is inside the scope of the sum) we can easily build counterexamples. If it is not constant, I have no idea how to read it.

Looks right to me in the following convention:
$S_n = \sum_{k=1}^{n} \Theta(1/k)$ is convenient notation for

There is an $f(x) \in \Theta(1/x)$ (as $x \to \infty$) such that
$S_n = \sum_{k=1}^{n} f(k)$.

Thus the $c_i$ (or with the notation in this answer $c_k$) you get, are not really dependent on $k$.
Under this interpretation, it is indeed true that $S_n = \Theta(H_n)$.
In fact, in Jeff's answer, he shows that $T(k+1) = f(k) + T(k)$ where $f \in \Theta(1/k)$, so it is consistent with the above interpretation.
The confusion seems to be arising from mentally "unrolling" the $\sum$ and presuming different functions for each occurrence of $\Theta$...


Queue implemented using stacks I have this problem I'm trying to solve: Implement a queue with a constant number of stacks so that each queue operation takes a constant (worst-case) number of stack operations.

I don't want assistance with the answer, but i do need help understanding the last part of requirements - "so that each queue operation takes a constant (worst-case) number of stack operations".

Does this mean that, given such a queue with n elements and another with n+1 elements, the number of stack operations will be the same, when enqueueing or dequeueing either one?  What does "worst-case" mean when dealing with a queue?

Also, with a question like this, is it implied that queues are the only data-structures needed and one would not need to introduce any additional data structures to reach a solution?

I believe the question is asking you to implement the queue so that every time you perform a queue operation (enqueue or dequeue) your implementation does O(1) total operations on the stacks used to implement this. For example, an implementation that performed at most 137 total pushes and pops per time that the client calls enqueue or dequeue would satisfy this requirement, but an implementation that requires, say, $n$ stack operations per enqueue would not meet this requirement.


What is the set of operations of a Turing machine? From https://en.wikipedia.org/wiki/Abstract_machine

  A typical abstract machine consists of a definition in terms of
  input, output, and the set of allowable operations used to turn
  the former into the latter.

  The best-known example is the Turing
  machine.

In a Turing machine, what is its set of operations?
Is $\delta$ in the following definition of a Turing machine an
operation? (If yes, then there is only one operation in a Turing machine?) Thanks.

From https://en.wikipedia.org/wiki/Turing_machine

  a (one-tape) Turing machine can be formally defined as a 7-tuple $M=  \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$ where

  $Q$ is a finite, non-empty set of states

  $\Gamma$ is a finite, non-empty set of tape alphabet symbols

  $b \in \Gamma$ is the blank symbol (the only symbol allowed to occur
  on the tape infinitely often at any step during the computation)

  $\Sigma\subseteq\Gamma\setminus\{b\}$ is the set of input symbols

  $q_0 \in Q$ is the initial state

  $F \subseteq Q$ is the set of final or accepting states.

  $\delta: (Q \setminus F) \times \Gamma \rightarrow Q \times \Gamma
     \times \{L,R\}$ is a partial function called the transition function,
  where L is left shift, R is right shift.

The set of operations is what makes the machine work, i.e. read input
somewhere, write output somewhere, and change its internal state
(which includes anything it may change in its memory which can be a
tape or some other device).

In the case of a TM, that is done by the transition function $\delta$.

Now, as you wish, you may see the transition function (actually a
relation, when non-deterministic)) as the unique operation applied
repeatedly. Alternatively you may consider that each instance of the
(arguments, effect) pairs defined by the function, usually defined on
a finite number of possible arguments pairs (state, tape content),
each associated with a finite number of effect triples (state,tape
output,move), are as many separate instructions, the transition
relation being then the instruction set.

It is not a fundamental issue to decide whether you see it globally or
case by case.


How to find whether a grammar is ambiguous? $$S\rightarrow aAB$$
$$A\rightarrow bBb$$
$$B\rightarrow A|\epsilon$$

I'm choosing the string abbbb.

First left most derivation is the following:

$$S\Rightarrow aAB\Rightarrow abBbB\Rightarrow abebB\Rightarrow abebA\Rightarrow abebbBb\Rightarrow abebbeb = abbbb$$

Second left most derivation is the following:

$$S\Rightarrow aAB\Rightarrow abBbB\Rightarrow abAbB\Rightarrow abbBbbB\Rightarrow abbebbB\Rightarrow abbebbe = abbbb$$

Can someone tell me whether I'm correct in saying that the grammar is ambiguous?

This question has been taken from chapter 5 of "An Introduction to Formal Languages and Automata" by Peter Linz 5th Edition. The question states to prove that the grammar is unambiguous (however it is not). Hence, the aim of posting this question is to make sure that I've understood ambiguity and distinction between parse trees properly. I'm studying formal languages on my own and do not have the luxury of an instructor.

Since you are trying to prove that the grammar is ambiguous, you must simply provide an example of a string where that grammar results in more than one parse tree or derivation. (Note that this is an entirely different ordeal than trying to prove that a grammar is unambiguous.) Since the string abbbb indeed has two distinct leftmost  derivations, you have shown that the grammar is ambiguous. This proves that the grammar is not unambiguous since it is not the case that each string has at most one parse tree or derivation.


Size of order-preserving minimal perfect hash family Suppose we have a universe of $u=|U|$ elements. We called a set of $H$ function $(U,m)$ order-preserving minimal perfect hash family (OPMPHF) if  for every subset $M\subset U$ of size $m$  has at least one function $h\in H$ which is an over preserving minimal prefect hash.   It is shown in [1,2] that for every   $(U,m)$-OPMPHF $H$ obeys:

$$H=m! \cdot \left.\binom{u}{m}\middle/\left(\frac{u}{m}\right)^m\right.   $$

Thus, the program length for any order preserving minimal perfect hash function should contain at least $\log_2 |H|$ bits.

In particular, if $m=3,u=8$, we have that $|H|\geq 17.7$.

However, I think I can create as set of  $|H|=6$ functions for such family. For every $2\leq i\leq 7$ we define $f_i(x)$ to be equal $1$ if $x<i$, equal $2$ if $x=i$ and equal $3$ if $x\geq i$. Every function $f_i$ is order-preserving, and for each set $M$ with second element $i$ has a perfect function $f_i$.

Do I miss something in my analysis?

[1] Havas and Majewski, Optimal algorithms for minimal perfect hashing

[2] Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1. Springer-Verlag, Berlin Heidelberg, New York, Tokyo, 1984

Reference [1] defines order-preserving as follows:

  A hash function is order preserving if it puts entries into the hash table in a prespecified order.

In your case, this means that given any three elements $x,y,z \in \{1,\ldots,8\}$, you want there to be a hash function which maps $x$ to $1$, $y$ to $2$, $z$ to $3$.

In particular, it need not be the case that $x < y < z$.

If you add the assumption that $x < y < z$, then you can remove the $m!$ factor in the lower bound on $H$. The new lower bound states $H \geq 2.95$, that is, $H \geq 3$, which is not tight.


Is there an algorithm that can ensure everyone gets bussed to their destination on time, while minimizing the time spent on a bus? Suppose I am a bus transportation company. I have n buses. I want to change the bus routes so that the "average" commuter spends as little time on the bus as possible, while being able to arrive at as close to their final bus station at their desired time as reasonably possible.
Inputs: Origin bus stations, destination bus stations, and desired time of arrival for each passenger.
Constraints: The average commuter shall arrive no earlier than 15 minutes prior to their desired time of arrival.
As far as I am aware, no readily available (commercial or otherwise) solution exists.

This problem is NP-hard. You can reduce the Hamiltonian-Cycle problem to this problem.  Given an instance of the Hamiltonian-Cycle problem, fix a vertex $v$. Assume there is exactly one bus and $2n - 2$ passengers, where $n$ is the number of vertices in the graph. We set the passengers such that one passenger wants to travel from $v$ to each other city in the graph and one to travel from each other vertex to $v$.
Claim. The given graph admits a Hamiltonian-Cycle, if and only if the total travelled distance is $2\frac{n (n-1)}{2}$.
Proof. An optimal route is a Hamiltonian-Cycle from $v$ [try to see why]


What is the decidable language in $P/poly$ but not in $P$? Except for the undecidable unaries I have no idea if there is anything in the gap between $P/poly$ and $P$

Take a language $L$ which is not in $\mathsf{E} = \bigcup_{c=1}^\infty \mathsf{TIME}(2^{cn})$. Now consider the language
$L' = \{1^m : m \in L\}$.
Then $L'$ is clearly in $\mathsf{P/poly}$, but it's not in $\mathsf{P}$: if it were decidable in time $O(m^k)$, then we could decide $L$ in time $O((2^n)^k)$, and so $L$ would be in $\mathsf{E}$. Our decision procedure works as follows: on input $m$ of length $n = \log m$, we run the algorithm for $L'$ on the input $1^m$. This runs in time $O(m^k) = O((2^n)^k)$.

It remains to ensure that $L'$ is decidable. To that end, all we need to do is to choose some $L \notin \mathsf{E}$ which is decidable, for that makes $L'$ trivially decidable: given an input, if it's not of the form $1^m$, reject; otherwise, answer according to whether $m \in L$.

The existence of a decidable language $L \notin \mathsf{E}$ is guaranteed by the time hierarchy theorem.


What is the advantage of Randomized Quicksort? In their book Randomized Algorithms, Motwani and Raghavan open the introduction with a description of their RandQS function -- Randomized quicksort -- where the pivot, used for partitioning the set into two parts, is chosen at random.

I have been racking my (admittedly somewhat underpowered) brains over this for some time, but I haven't been able to see what advantage this algorithm has over simply picking, say, the middle element (in index, not size) each time.

I suppose what I can't see is this: if the initial set is in a random order, what is the difference between picking an element at a random location in the set and picking an element at a fixed position?

Can someone enlighten me, in fairly simple terms?

If the input array is distributed uniformly at random then (as you noted) there is no difference between always picking an element at a fixed position (for example the middle one as you suggest) or picking an element chosen at random.

If however your input array is not really in random order (which happens to be the case in  almost all practical scenarios) then one needs to either "preshufle" the array in order for the elements in it to be placed in random order, or (equivalently) always take a random element as a pivot. This ensures the partitioning phase of quicksort partitions the arrays into sub-arrays of almost equal size and hence that the expected running time remains $O(n\log n)$

So your confusion appears to come from the fact that somehow you assume a sorting algorithm can (in practice) expect the input array to always be randomly distributed.


Problem with definition of bisimilarity In my model checking class we have defined a bisimulation like this:

Let $K=(S,S_0,Act,R,L)$ and $K'=(S',S'_0,Act,R',L')$ be two kripke structures. A relation $B \subseteq S \times S'$ is called bisimulation if $\,\forall (s, s') \in B$ following points are true:

$L(s) = L(s')$
$\forall \,t \in S, a \in Act: (s,a,t) \in R => \exists \, t' \in S': (s',a,t') \in R' \, \land (t,t') \in B$
$\forall \,t' \in S', a \in Act: (s',a,t') \in R' => \exists \, t \in S: (s,a,t) \in R \, \land (t,t') \in B$

Two states $s \in S, s' \in S'$ are called bisimilar  iff. there is a bisimulation $B$ with $(s,s') \in B$.

$K$ and $K'$ are called bisimilar if:

$\forall \, s \in S_0 \, \exists \, s' \in S': s \sim s'$
$\forall \, s' \in S_0' \, \exists \, s \in S: s \sim s'$

My problem is that this definition is defined recursively. Take for example this two structures:

$\hskip2in$

Of course these structures are bisimilar since they are the same but to show that $(s_0, s'_0) \in B$ I have to show that $(t, t') \in B$ and now I'm in an endless recursion.

Have I misunderstood something about the definition?

You seem to be confusing the definition of bisimilarity with an algorithm for finding a bisimulation.

In your examples, the states are indeed bisimilar, and the relation is the set
$$\{(A,A)\}$$
It is easy to verify that it satisfies the desired properties.

This means that the structures are indeed bisimilar.

What you were trying to do is to find an algorithm for constructing a bisimulation, given the two different structures. If you try to proceed by taking the initial states, and moving through paths, then you indeed encounter a problem with cycles. (By the way, if the structures were trees, or DAGs, then your approach would work).

This is why algorithms for finding bisimulations typically take a different approach -- namely refinement: you start with a naive relation (e.g., everybody is bisimilar to everybody), and whenever you find a mismatch, you refine your relation.

Take a look at the "fixpoint" definition of bisimilarity here, and try to extract an algorithm from it.


Applications of the splittance of a graph/ Turning graphs into splitgraphs Let $G=(V,E)$ be a graph. For $C\subseteq V$ let $G[C]$ be the subgraph of $G$ induced by $C$.
A split Graph is defined as follow:

$G$ is a split graph if there exists a subset $C\subseteq V$ so that $G[C]$ is a clique and $G[V\setminus C]$ is an independant set (edges between $C$ and $V\setminus C$ do not matter).

There exists an efficient algorithm (linear time) to calculate the shortest sequence of edge insertions & deletions to turn a graph into a split graph (Important: If we also have to remove the edges between $C$ and $V-C$, then this problem turns $\textsf{NP}$-hard).
My question is: what are possible applications of this procedure?
My ideas so far:
Of course, if the distance of $G$ to a split graph is very small (compared to the number of nodes), we can probably adapt the algorithms for split graphs, and that way obtain efficient implementations for problems that would be $\textsf{NP}$-hard on general graphs.
A general situation where we (somewhat probably) have a near-split-graph would be a network to which we add a batch of random new objects, e.g. a company which just got a batch of newcomers.
Though I still wouldn't know what type of problem there is that could use the fact that the graph is a near-split-graph. Link to the complexity of some problems on split graphs

There is nothing deeper to it than what you describe: if the graph is split or it has "small" distance to being split (e.g., you can make it split by removing a small number of edges/vertices), you might be able to devise a polynomial-time algorithm for some otherwise NP-hard problem.
However, it is quite rare such procedures are applied in practice. It can take too much time to decide if the input graph has the desired properties compared to just using a state-of-the-art solver (e.g., integer programming) for the problem you care about. In fact, it is possible these solvers implicitly detect such useful structure and there is no need for this "additional" theoretical analysis.
To summarize, algorithms for split graphs and the kind of situations you describe are mostly theoretical and rarely implemented or used in practice.


Algorithm to find all paths of length k Consider the following definition of 3-friends:

person 1 is 3-friends with person 2 if they are direct friends or person 1 is friends with a friend of person 2 or  person 1 is friends with a friend of a friend of person 2.

In graph-theoretical terms, person 1 is a 3-friend with another person 2 if there is a path of length 1, 2 or 3 from vertex 1 to vertex 2.

Is there an efficient algorithm to find all the paths between say person 1 and all its 3-friends? (I.e. all the paths of length 3, all the paths of length 2, all the paths of length 1).

Or the only option is an exhaustive search?

You are asking for all paths of length 3 emanating from a given vertex. There are $O(n^3)$ of these, the worst case being a clique. If you want to actually output all of them, then exhaustive search (on the adjacency matrix) is the perfect algorithm, and it is efficient, since there are only $O(n^3)$ paths (or less).


What are the key differences between Spiking Neural Network and Deep Learning Deep Learning, now one of the most popular fields in Artificial Neural Network, has shown great promise in terms of its accuracies on data sets. How does it compare to Spiking Neural Network. Recently Qualcomm unveils its zeroth processor on SNN, so I was thinking if there are any difference if deep learning is used instead.

Short answer:

Strictly speaking, "Deep" and "Spiking" refer to two different aspects of a neural network:  "Spiking" refers to the activation of individual neurons, while "Deep" refers to the overall network architecture. Thus in principle there is nothing contradictory about a spiking, deep neural network (in fact, the brain is arguably such a system).

However, in practice the current approaches to DL and SNN don't work well together.  Specifically, Deep Learning as currently practiced typically relies on a differentiable activation function and thus doesn't handle discrete spike trains well.

Further details:

Real neurons communicate via discrete spikes of voltage.  When building hardware, spiking has some advantages in power consumption, and you can route spikes like data packets (Address Event Representation or AER) to emulate the connectivity found in the brain.  However, spiking is a noisy process;  generally a single spike doesn't mean much, so it is common in software to abstract away the spiking details and model a single scalar spike rate. This simplifies a lot of things , especially if your goal is machine learning and not biological modeling.

The key idea of Deep Learning is to have multiple layers of neurons, with each layer learning increasingly-complex features based on the previous layer.  For example, in a vision setting, the lowest level learns simple patterns like lines and edges, the next layer may learn compositions of the lines and edges (corners and curves), the next layer may learn simple shapes, and so on up the hierarchy.  Upper levels then learn complex categories (people, cats, cars) or even specific instances (your boss, your cat, the batmobile). One advantage of this is that the lowest-level features are generic enough to apply to lots of situations while the upper levels can get very specific.

The canonical way to train spiking networks is some form of Spike Timing Dependent Plasticity (STDP), which locally reinforces connections based on correlated activity. The canonical way to train a Deep Neural Network is some form of gradient descent back-propagation, which adjusts all weights based on the global behavior of the network. Gradient descent has problems with non-differentiable activation functions (like discrete stochastic spikes).

If you don't care about learning, it should be easier to combine the approaches. One could presumably take a pre-trained deep network and implement just the feed-forward part (no further learning) as a spiking neural net (perhaps to put it on a chip).  The resulting chip would not learn from new data but should implement whatever function the original network had been trained to do.


Clarification sought for definition of a cut that respects a set A of edges in Graph Theory From CLRS (3rd edition), I came have this question on page 626:

Given these definitions from the text,

DEFINITIONS:
Given an undirected graph G = (V,E),
1. A CUT (S ,V-S) of G is a partition of V,
2. A LIGHT EDGE over a cut is any edge crossing the cut with a weight smaller than or equal to any other edge crossing that cut,
3. A cut RESPECTS a set A of edges if no edge in A crosses the cut.

In every example in the text, the set A is coincident with one of the partitions of the cut but I cannot see why this must be. Given an arbitrary new vertex v', it could be added to the partition that contains A and no edge from v' to A would cross the cut. The definition of respects says that a cut cannot divide A, not that A must define the partition.

There is clearly something here I missed since that does not seem consistent with the theorems. Can anyone point out my error?

+++++++++++++++

Amendment.
Thanks for the help. I also now realize that Theorem 23.1 only says that a light-edge is a safe edge but not that such a cut is guaranteed to find every safe edge since some edges may have both vertices in the same partition as A. I see in GENERIC-MST(G) that line 3 only says to find an edge. It is not until Kruskal or Prim algorithms that the method by which we find this edge is explained and neither depend upon the partition being coincident with the set of vertices defined by the set of edges A.

I find it interesting that in Kleinberg Tardos that they take a different approach and define a cut property (4.17, pg 145) that avoids this (what I find awkward) development of the ideas.

One mistake you're making with the statement:

  In every example in the text, the set A is coincident with one of the partitions of the cut but I cannot see why this must be.

$A$ is a set of edges, while a cut is a partition of vertices: $(S, V - S)$.

Suppose, as you say, that $A$ is a subset of the set $\{(u,v): u,v \in S\}$, then $A$ respects the cut $(S,V-S)$ because none of the edges with both ends in $S$ will cross the cut.

If you add a new vertex $v'$ into $S$, and some other edges from $v'$ to other vertices $x$ in $S$, then $A$ can include ALL of these edges and still respect the cut $(S,V-S)$ because both $v'$ and the other edges from $v'$ are in $S$.


Showing that a Particular Word Problem is Decidable I need to give an algorithm to show that the word problem in the group $\langle x,y \mid \mid x^{1984} = y^{2014} = 1 \rangle$ is decidable. How do I show this? I'm not too sure where to start.

Hint: Come up with a normal form for words in this group.


Efficiently extendable hash function? I'm wondering whether there exist any good hash functions with the following property: Assume that $x$ is some string over some alphabet $A$, then given $H(x)$ we can compute in $O(1)$ time both $H(ax)$ and $H(xa)$ for any letter $a\in A$. In practice one can assume that $A$ is for example the set of $8$-bit integers.

In other words, a hash function for strings that can quickly be extended in both directions. I'm only interested in hash functions that actually distribute the data well and which are very fast to compute in practice.

Use any rolling hash, e.g., the Rabin-karp rolling hash, Buzhash, or CRC.  See also the following resources:

additive hash function
Can ropes (AVL trees) be interned?
https://crypto.stackexchange.com/q/17935/351
https://crypto.stackexchange.com/q/11420/351
the answers to https://crypto.stackexchange.com/q/1558/351


How to write an if then logical constraint given part of the input related to a decision variable? I am trying to solve an assignment problem-like from a bi-objective persepctive where I have a marketplace of vendors proposing different machines with different types and specs. The goal is to select a small number of vendors (F1) while meeting the specs of some client machines and maximizing a utility function (F2).

The first decision variable Y[j,i,v] = 1 if machine j from vendor v is candidate for machine client i, 0 otherwise.

The second one is related to the type of client machine defined as Z[i,t] = 1 if machine i is of type t, 0 otherwise.

Since the input regarding this decision variable is known I set it accordingly to the type. For instance, if machine 1 is of type 1 then Z[1,1] = 1 and so on and each machine has only one type so other values for machine 1 are set to be 0 (Z[1,2] = Z[1,3] =0, etc.).

The last decision variable is related to the selection of vendors A[v]=1 if vendor v is selected, 0 otherwise.

The input of the model is the set of machines with desired specs and types the clients want to buy, the vendors with their machines, specs and types. This is stored in different data structures.

Part of the input related to Y[j,i,v] contains the type of machines. Since the type of machines is known, I guess I do not need to include it in the definition of the decsion variable Y to be in the form of Y[j,i,v,t].
I would like to write a constraint saying that if machine client i is of type t then the machine candidate should be of the same type.

With the case of Y[j,i,v,t] it looks like : Z[i,t] <= Y[j,i,v,t].

But with the case of Y[j,i,v] I am not sure how to connect it with Z[i,t] using a constraint knowing that t is part of Z and t is a known value in Y.

Anyone can shed some light on this matter? I am using Python and Gurobi as a solver. I attached the link to my linear program format file and the output provided by gurobi (vendors and gurobi_output).

If you have two binary variables X, Y and you want to express the constraint X implies Y via a linear inequality you can use the logical equivalent statement (not X) or Y, which in linear programming translates to:
$$(1-X) + Y \geq 1$$
In Gurobi-Code this would be: model.addConstr((1-X) + Y >= 1, name="implication").


"Last Come => More Relevant" data structures As I think of data structures I studied and dealt with, they are all optimized to retrieve/put  a random element, to perform optimally based on unspoken assumption that each element has equal odds of being asked for (e.g. Red-Black trees).

By the nature of my program, I need to maintain an online dictionary of items that typically serves items that were added last.

That is, the later an item has been added, the higher the likelihood of it being retrieved back in the nearest future.

Speaking more formally, let's define a set $S$ of pair $(k_i, d_i)$, where $k_i \in K $ and $K$ has a comparison operator $\leq$ defined, $d_i \in D$. Let $p(k)$ be the probability of our need to retrieve pair $(k, d)$.

What is an efficient way to store $S$ with regard to function $p$ ?

I think of three possible options:

As mentioned before in the comments, one of my all-time favorite data structure, splay-trees. They are easy to implement and probably (assuming the Dynamic Optimality conjecture is true) roughly as good as any other dynamic search tree data structure. We already know that splay trees are as good as any static search tree. Note that there are other types of dynamic binary search trees (tango trees, zipper trees, ...), which will also perform well compared to the best dynamic search tree.
Use one or more optimal binary search tree (via dynamic programming). Since you insert/delete elements you need to rebuild the search tree form time to time. Say after a threshold value of elements that change you build the new optimal tree from scratch. This might be applicable, if you have time between the request. The rebuilding can be also be done in the background. Since building a optimal search tree is $O(n^2)$, this is not a good idea for large data sets.
Use Hashing. It might not treat the later inserted elements different, but in practice it might be as good as the other ideas.

You might think of keeping the last inserted elements in a separate data-structure (like a hash-map ) which you query first. Of course, from time to time you need to rebuilt.


Datastructure for a set of axis aligned rectangles that enables querying for point containment I am trying to find a reasonable data structure for representing a
partition of an (axis aligned) rectangular domain into a set of (axis aligned) rectangles.

I need to be able to look up for a given point which (unique) rectangle contains it.

So far I have taken a look at Quadtrees, and this seems reasonable to me - where I recursively subdivide the domain into patches.

People have also mentioned RTrees, but I do not see how these can help me in such single point queries.

Quadtrees sounds like a good choice.

How about the k-d tree of 2 dimension, which is also explained in a course note and at geeksforgeeks?

Each of the 2-dimensional versions of interval tree, range tree and segment tree may have a fair chance to solve the question efficiently.

I have used all above data structures to solve the same or similar or more complex queries. Depending on your situation, you may want to make some adjustment.

If the number of given points is much smaller than the number of possible points in the given rectangle domain, such as 22000 points in a $10^{18}$ by $10^{18}$ square, then some other choice might be even better. I once used a red-black tree, whose leaf nodes is another red-black tree and whose internal nodes of the same parent represent a partition of the contiguous rows represented by their parent into disjoint contiguous set of rows. The red-black tree at each leaf node stores the points in one particular row. In this way (and with a bit more technique), my final answer is able to run the fastest among all solution to the problem. Of course, my example may not be useful to your situation at all. Well, I hope that might encourage you to develop your own data structure that fits your situation more.


Compile a programming language with itself I'm a computer science student. I want to create my own programming language (A basic language with few instructions).

I know how to do a syntactic analyser, I already did it in Perl. In an article, I read something about the compiler, a compiler is done in itself.

For example the C compiler is written in C. How it's possible?
I can make my own language but I don't know how I could execute it? Any idea?

It's really a good question and I can write a blog the project.

The trick is bootstrapping. You first write a compiler for your language (or a subset thereof) in some other language. Then you write a compiler for your language (or a large subset of the one you can already handle) in your language. You use the former compiler to compile the new compiler, and then the new compiler can compile itself.


consistent heuristic - does it always exist? I am studying for an artificial inteligence class, and i have to classify the following sentence

"For any search space, there is always an admissable and consistent A* heuristic".

Well, i know that there is always an admissable heuristic, for example zero, since its an underestimation of the real cost (althoug this would lead to uniform cost instead of a*).

What I would like to know is if there is always a consistent heuristic, and why.

Thanks for your help

The zero heuristic is trivially admissible, as you've noted. It's also trivially consistent as long as all step-costs are non-negative: if $h(x)=0$ for all $x$ and $c(x,y)\geq 0$ for all $x$ and $y$, then
$$
h(x)\leq c(x,y) + h(y)
$$
for all $x$, $y$.


NP-complete decision problems - how close can we come to a solution? After we prove that a certain optimization problem is NP-hard, the natural next step is to look for a polynomial algorithm that comes close to the optimal solution - preferrably with a constant approximation factor.

After we prove that a certain decision problem is NP-complete, what is the natural next step? Obviously we cannot "approximate" a boolean value...

My guess is that, the next step is to look for a randomized algorithm that returns the correct solution with a high probability. Is this correct?

If so, what probability of being correct can we expect to get from such a randomized algorithm?

As far as I understand from Wikipedia, PP contains NP. This means that, if the problem is in NP, it should be easy to write an algorithm that is correct more than $0.5$ of the times.

However, it is not known whether BPP contains NP. This means that, it may be difficult (if not impossible) to write an algorithm that is correct more than $0.5+\epsilon$ of the times, for every positive $\epsilon$ independent of the size of input.

Did I understand correctly?

You made a crucial change to the question.  I've updated my answer to respond to the new question; I'll keep my original answer below for posterity as well.

To answer the latest iteration of the question: If the problem you really want to solve is a decision problem, and you've shown that it is NP-complete, then you might be in a tough spot.  Here are some candidate next steps:

Look for heuristics.  This means algorithms that work on some problem instances, but not all.  Basically, you're hoping that you only come across problem instances that are easy, not any of the worst-case problem instances.

SAT solvers are an example of this approach.  They solve a NP-complete decision problem ("does SAT formula $\varphi$ have a satisfying assignment?") using heuristics that happen to work well on many of the formulas we run into in real life, but their worst-case running time remains exponential.  Integer linear programming is another example of this.

One very powerful kind of heuristic is to formulate your problem as an instance of SAT, ILP, constraint satisfaction programming, or something like that; and then apply an off-the-shelf SAT/ILP/CSP solver to solve it.
Look for a fixed-parameter tractable algorithm.  Sometimes the complexity of a problem can be characterized by multiple parameters, and occasionally one can find an algorithm that is polynomial in one of the parameters, even if it is exponential in the length of the input (and thus is not a polynomial-time algorithm).

An example would be the knapsack problem, which takes as input an integer $W$ (the capacity of the knapsack) and some other inputs describing the items you can select from.  The knapsack problem is NP-hard.  However, there is a standard dynamic programming algorithm whose running time is $O(nW)$.  This algorithm is exponential in the length of the input (because $W$ is specified in binary, so the value of $W$ is exponential in the length of the input), and thus this does not qualify as a polynomial-time algorithm.  However, if $W$ is not too large -- as will often be the case in many practical settings -- this algorithm is efficient enough nonetheless.
Start looking at algorithms whose running time is exponential, or at least super-polynomial.  Sometimes the running time can be optimized so that the exponential running time is (just barely) tolerable.
Change the problem.  Start looking for way which you can "cheat", i.e., change the assumptions or the information given to you to make the computational problem easier.
Give up.  Accept that this is one problem you probably won't be able to solve.

These are standard strategies for coping with NP-completeness.  Many textbooks mention these options.

No, randomization alone is not going to take a NP-complete problem and make it easy to solve in polynomial time.  Everyone knows that proving $P\ne NP$ is a famous hard problem, and that most complexity theorists expect that $P \ne NP$ but just don't know how to prove it; similarly, most complexity theorists expect that $BPP \ne NP$, but they just don't know how to prove it.  Proving that $BPP \ne NP$ looks even harder than proving that $P \ne NP$.  That's why it is the $P \ne NP$ problem that is famous, not the $BPP \ne NP$ problem; if we can't prove that $P \ne NP$, we have no hope of proving that $BPP \ne NP$.

Incidentally, many complexity theorists expect that $P = BPP$, but proving that is way beyond our current knowledge.  That said, for all practical engineering purposes, you can assume that $P = BPP$.  (Complexity theorists, close your eyes here.  I'm about to use some engineering reasoning that works well enough for all engineering purposes, but will drive theorists crazy.)   If you have an efficient randomized algorithm that solves some natural real-world problem, I bet I can build a deterministic algorithm that will almost surely solve the problem, too; I won't be able to give you a proof of that fact, but I'll gladly take that bet even at \$100 to \$1 odds in your favor.  How can I be so confident?  Because if we take your randomized algorithm and, instead of feeding it truly random bits, feed it bits from the output of a cryptographic-strength pseudorandom generator, then there's no way your randomized algorithm is going to be able to tell the difference.  After all, if it could, it would have found a way to break the crypto.  If you find a way to break the crypto, there are people who will pay you a whole lot more than \$100 for the secret.  That's part of the reason why many people expect that $P = BPP$ (or some moral equivalent) is probably true.

Your original question said you wanted to find an approximate solution to a NP-complete problem, and asked what performance is possible.  Here was my answer to that question:

It depends on the problem.  Some NP-hard optimization problems have good approximation algorithms; others don't.  There's lots written in textbooks (and in Wikipedia) on approximation algorithms for NP-hard problems; this is a standard topic in undergraduate algorithms.  See, e.g., https://en.wikipedia.org/wiki/Approximation_algorithm and https://en.wikipedia.org/wiki/Polynomial_time_approximation_scheme, but make sure to read textbooks too.

BPP is not a relevant concept here.  The question of whether $NP \subseteq BPP$ would be relevant if you were looking for a randomized algorithm that produces an exact solution to the NP-complete problem.  But that's not what you're looking for.  You're looking for a randomized algorithm that produces an approximate solution to the problem.  Looking for an approximate solution is a different problem than looking for an exact solution.  If there were a polytime randomized algorithm to find an approximate solution, that wouldn't imply that there's a polytime algorithm to find an exact solution, and it wouldn't imply that $NP \subseteq BPP$.  Similarly, if there were a polytime deterministic algorithm to find an approximate solution, that wouldn't imply that there's a polytime algorithm to find an exact solution, and it wouldn't imply that $P=NP$.

Similarly, $PP$ is not very relevant here.

If you really want to relate this to complexity classes, the relevant complexity class is $APX$ (see, e.g., https://en.wikipedia.org/wiki/APX).

Incidentally, many approximation algorithms are deterministic algorithms.  Randomization is occasionally helpful but often not needed.


Using function composition to turn a function into point free one In Tacit Programming page on wikipedia, it is stated that the point free version of

p x y z = f (g x y) z is
p = ((.) f) . g

and that the point free version of

mf criteria operator list = filter criteria (map operator list) is
mf = (. map) . (.) . filter.

I can not figure out how can we get from one side to the other, in either way. Would you please show me a step by step explanation of why those equivalences hold?

Going from the point-free version to the lambda version is mechanical. Remember that composition is defined by (f . g) = (.) f g = \x. f (g x), so (f . g) x = f (g x). Remember also that (f . g) is syntactic sugar for (.) f g and f x y is shorthand for (f x) y. It's easier to follow what's going on if you apply one argument at a time.

p = ((.) f) . g
p x = (((.) f) . g) x = ((.) f) (g x) = (.) f (g x)
p x y = (p x) y = ((.) f (g x)) y = (.) f (g x) y = (f . g x) y = f (g x y)
p x y z = (p x y) z = (f (g x y)) z = f (g x y) z

To go in the other direction, arrange the function calls so that there is a single occurrence of the function's parameter in the function body, and arrange it to be at the end of the call. In addition to . for composition, this may require the use of auxiliary functions such as flip to change the order of arguments.

p x y z = f (g x y) z
p x y = f (g x y)
p x = \y. f (g x y) = \y. f ((g x) y) = \y. (f . g x) y = (f . g x) = ((.) f) (g x)
p = \x. ((.) f) (g x) = \x. ((.) f . g) x = ((.) f . g)


Misunderstanding Turing's Halting-Problem Argument I just watched a video by Computerphile on the halting problem (https://www.youtube.com/watch?v=macM_MtS_w4) .  I’m having some difficulty understanding the argument as it is made.  Let me explain it as I see it:

So that our terminology is the same, H is a (hypothetical) program which can analyze another program to see if it halts.  H+ is a modified version of H which loops forever if the analyzed program halts and halts if the analyzed program does loops forever.

In order to run H, you need to specify 2 things – a program and the input to that program.  The Input to the analyzed program is necessary because the program’s behavior will depend on its input.

According to Computerphile’s explanation of Turing’s argument, we are asked to consider what would happen if H+ were to analyze H+ with H+ as its input.  Since there are a lot of H+’s being thrown around, let’s define H+1 as the program that I am running, H+2 as the program being analyzed, and H+3 as the input to H+2.  (Of course, H+1, H+2, and H+3 have the exact same code; they are just being used in different ways.)    My question is this:  if we require H+3 as an input to H+2, then shouldn’t we require an input to H+3?  And if we continue the pattern and use H+4 as an input to H+3, then wouldn’t this mean that we require an H+5 as an input to H+4?  And so on?

If you counter by saying that Turing’s argument doesn’t require H+3 to have an input (or that its input doesn’t have to be H+), then doesn’t this break the whole symmetry of the problem?  After all, the whole point of Turing’s argument (as I currently understand it) is that if H+2 runs on H+3 and halts then it would be a contradiction to have H+1 loop forever on H+2 since H+1,H+2,and H+3 are all identical (and vice versa were H+2 to loop forever on H+3).  But the situation isn’t identical.  In one case H+2 is running on H+3.  In the other, H+1 is running on "H+2-running-on-H+3".

I guess you could say that each H+ maybe can only look one step in front of it, so that H+1 only “sees” H+2 and H+2 only sees H+3.  But then what does H+3 see?  Doesn’t it need some input of its own? After all, whether or not H+3 halts depends on the program it’s given.    If so, this brings it back to my first point (that we would need an H+4).

It seems to me this whole argument falls apart.  Either you would need an infinite stack of H+’s which can’t happen, or you have a finite stack which because of the discontinuity at the end means that the symmetry of each level doesn’t translate to the one below it.

So what am I missing?

"So what am I missing?"  Nothing.    Computerphile should have defined H++ by  H++(x) = H+(x,x) ,  and then run H++ on itself.


Is every language with a finite number of strings regular? Is every language with a finite number of strings regular?
Is the language of all strings regular?

I am new to this topic and got confused. Can any one please help me with this?

Yes. Assume the language is $L=\{w_1,w_2,\ldots, w_n\}$. then you can form the regular  expression $w_1 + w_2 + \cdots + w_n$, which describes $L$.
You can also argue with finite automata or regular grammars.

Yes, if your alphabet is $\Sigma=(a_1,\ldots,a_k)$ then the regular expression $(a_1+a_2+\cdots +a_k)^*$ describes the languages of all possible strings over $\Sigma$.


What is the advantage of seperate chaining over open addressing? Hash tables resolve collisions through two mechanisms,

separate chaining or open hashing and
open addressing or closed hashing.

Though the first method uses lists (or other fancier data structure) in hash table to maintain more than one entry having same hash values, the other uses complex ways of skipping n elements on collsion.

Since, while searching, both mechanisms requires looking up for more entries on collision and Seperate chaining may require lesser number of searches to find the match.

What kind of advantages does it have over separate chaining?

Suppose that you have a very large number of sufficiently uniform elements, $n$, that you want to hash. We want to minimize lookup time, obviously.

If we use separate chaining with $m$ linked lists, our lookup time will be, on average, $O(n/m)$ since we have $n$ elements and $m$ buckets. The actual lookup time depends on whether our input set is sufficiently uniform or not, but for the sake of simplicity we can assume that it is. What are the downsides of this? Linked lists and most other data structures that we would use to do this make heavy use of pointers. A single query takes $O(n)$ pointer dereferences.

Now consider two typical methods of open addressing: linear probing and quadratic probing. Linear probing traverses the space allot for open addressing and places the element that it is hashing at the first available memory location (at the $i^\text{th}$ step, we look at index $i$ to see if it is free). Quadratic probing traverses by incrementing the index by $i^2$ on each step. This can lead to immense speed-up due to its cache-friendliness (as mentioned in the first comment, this is called spatial locality -- I'd suggest reading this if you're unfamiliar).


Prove the language of numbers divisible by 3 is not regular using pumping lemma I have a language $L$ that I think is not regular:

$L = \{w\in \{0,1,...,9\}^* \; | \enspace w \enspace \text{is a decimal representation of a number divisible by 3}\}$

I'm using pumping lemma in my proof. My main main idea is the following. I choose $w = 3$, according to the pumping lemma $w = xyz$ with $xy^iz$ where $i \in \mathbb{N}_0$. But for $i=0$ we have $\varepsilon$ which is not in the language ($\varepsilon$ is not divisible by 3). Therefore the language is not regular.

Is my idea right?

You cannot choose any string for the pumping lemma. You have to choose one that is at least as long as the pumping distance of the language (which exists when it is regular), but you do not know which it is, so you have to assume it is some value named $p$ (or some other name) and you assume you have a well chosen string in the language that is greater than $p$.

Another point is that I would say that $\epsilon$ is not the representation of a decimal number, rather than say it is not divisible by $3$.

All this being said, modular arithmetics works pretty well with divisibility constraints, divisibility by a constant, I mean. And Finite Automata are usually friendly to modular arithmetics because it is defined on finite sets of values (or classes of numbers).


If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm? The smallest grammar problem is to find a single-string CFG.  So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each respective sample, compute an approximate smallest CFG for the language?

I want to make a parser generator that automatically detects a grammar given some samples of programming languages.

This is extremely optimistic.

The first problem you face is that an approximate smallest grammar will at best help you find strings which occur frequently. It won't distinguish keywords from names, and it won't isolate words. (Note for reference that Lempel-Ziv has a good approximation ratio. Charikar, Lehman, Liu, Panigrahy, Prabhakaran, Sahai, & Shelat (2005) The smallest grammar problem, Information Theory, IEEE Transactions on, 51(7), 2554-2576).

The second, related, problem you face is tokenisation. Programming language grammars deal in tokens, not in characters. Just the issue of tabs vs spaces in the samples is likely to mess things up. This might be finessed by making assumptions about tokenisation and then finding approximate smallest grammars over the language of tokens, but be prepared for nasty surprises. E.g. string literals in C# are definitely non-trivial, and you might not have many instances of @-strings from which to infer.

The third problem is that some languages (particularly those designed for code-golf) have unusual tokenisation and so little grammar that the tokenisation is where the real difficulty lies. E.g. identifying the tokenisation of CJam operators is going to be hard. You might do slightly better if instead of working from a grammar per sample you concatenate the samples, separated by a token which doesn't occur in any sample, and then find an approximate shortest grammar for that super-sample. At least that way you might have sufficiently many occurrences of the more common multi-character tokens to pick them out as symbols.


Explanation of a specific recurrence with respect to Master Theorem Concerning the Master Theorem. I have found the following equation as the base of analysis:

$\quad T(n) = aT(n/b) + \Theta(n^k)$

but I also found the following:

$\quad T(n) = aT(n/b) + \Theta(n^k\cdot\log_p n)$

where the base $p$ is a real number.

Can anyone explain the second equation? I understand the proof with the first equation but can not understand the second formula.

Sometimes the master theorem is only given for recursions of the form $T(n) = aT(n/b) + \Theta(n^k)$, but the Wikipedia article includes a more general version which can handle functions of the form $T(n) = aT(n/b) + \Theta(n^k(\log n)^l)$, and even more general ones when $k \neq \log_b a$. The similar Akra-Bazzi theorem handles more general situations.