Finding a minimum of a noisy function I have a certain function that calculates numerically, for every $x \in [0,10]$, a value $y\geq 0$. I want to find an approximate minimum point of that function. A possible solution is to calculate $y$ for e.g. 10000 values of $x$ in the range $[0,3]$ and return the $x$ for which $y$ is smallest. I am looking for fastest solutions.

I know that the general shape of the function is like the following plot:

I.e, it is like a function with a single minimum point, but with some added random noise of bounded size. Without the noise, I could easily find the minimum point using gradient methods, but with noise gradients seem  useless. What other search algorithm can I use here?

NOTE: Naturally the approximation quality can depend on the noise size, for example, in the above plot, any answer between $\approx 0.3$ and $\approx 0.7$ would be considered good enough.

Some things you could explore are metaheuristics. The following methods don't make assumptions about the function to be optimized, and some are relatively simple to understand and implement.

Some of these mantain a population of possible solutions, recombining them to create new possible solutions and keeping the best ones.

Differential evolution
Particle Swarm
Evolutionary algorithms

There are a lot more, with a lot of published variations.

It is my understanding that they are very capable, you can expect the error to be much smaller to the error margin you mentioned and the acceptable error can be used as a parameter for the halting condition of the algorithm. If the target function is computationally cheap to evaluate these methods should be very competitive.

In particular differential evolution could be a place to start exploring. You can use an already written implementation on scipy's optimize.

There are other approaches, some of which make assumptions about the function to be optimized. You can see some examples on Wikipedia  (Computational optimization techniques section).


Classical Computation without NOT Is it possible to do universal classical computation using bits and 2-bit gates when you cannot perform a NOT operation on a single bit (hence cant do CNOT and so on). If yes, what are the possible universal sets of gates that do not utilise the NOT transformation. Thanks!

EDIT: to clarify, you can perform any set of operations you want, but if there is some sequence that you apply these operations in that is equivalent to a NOT operation then they are forbidden. For example, in quantum computing you can take the square root of a not operation, but as applying two of these gives a not operation then this would not be allowed

You're confusing classical and quantum computation, so let me ignore the quantum aspects for now. If you forbid the unary NOT gate then you can use a binary NOT gate, say $g(a,b) = \lnot a$. You can also simulate NOT using natural gates: $XOR(a,1) = \lnot a$ (and this gate can even be made reversible!). So this kind of restriction is not really meaningful.

It is more meaningful to ask what happens if all gates are monotone, that is, they satisfy $g(x_1,\ldots,x_n) \leq g(y_1,\ldots,y_n)$ whenever $x_i \leq y_i$ (here $\text{FALSE}\leq\text{TRUE}$). Such circuits are known as monotone circuits, and they can only compute monotone functions. One natural complete basis is $\{\text{AND},\text{OR}\}$. You can show that this basis is complete using DNFs.


Distributed Algorithm Problem Consider a t-resilient read-write shared memory system (0 < t < N) with initial failures only: faulty processes take no steps. How could one give a consensus algorithm in this system? I don't understand why the proof of the consensus impossibility doesn't work in this case?

There are two questions here. Let me start with the second: "I don't understand why the proof of the consensus impossibility doesn't work in this case?".

First, I do not know what proof you are talking about. I suppose you are referring to a proof that consensus is not solvable in a t-resilient SWMR system when $0<t<N$.

If $t<N-1$, the easiest way I know to prove this fact it to reduce t-resilient SWMR consensus to $(N-1)$-resilient consensus (i.e. wait-free consensus). This is done via the BG Simulation, which allows $t+1$ wait-free processors in a SWMR system to simulate a t-resilient SWMR system. The BG simulation does not work if failures are initial. Thus this is where the proof fails when $0<t<N-1$.

Now, let us consider $t=N-1$. In this case, one way to prove the impossibility of consensus is to use the critical-state argument. Let me explain why the critical-state argument does not apply if failures are initial only.

The key is that, in a wait-free SWMR algorithm, there are only finitely many executions given a fixed number of processors (this is a consequence of Koenig's lemma: infinite executions are not allowed and the execution tree is finitely branching, thus the execution tree is finite). In consequence, the set of continuations of an execution prefix is finite, and thus by repeatedly increasing the length of the prefix (and thus ruling out more and more continuations) we eventually arrive at a point at which all remaining continuation have the same consensus outcome. By removing one step from this prefix we have our critical state (assuming that the outcome was not predetermined by the inputs).

If we now assume that failures are initial only, we have to allow busy loops in which a processor reads until it sees a particular processor that it saw before, or otherwise we cannot take  advantage of the fact that failures are initial only. Thus, for any n, we have executions that exceed length n (e.g. when a processors polls n times when busy-waiting for another). Thus we now have infinitely many executions, and the reasoning used above to justify the critical-state argument does not apply anymore.

Now, let me answer your first question: "How could one give a consensus algorithm in this system?"

One way to do it is to use a "doorway": take a MWMR register initialized to 0, called the doorway register, and have all processors (a) announce their participation, then (b) read the doorway register, then (c) close the doorway by setting the doorway register to 1, and then (d) announce whether they successfully entered the doorway (i.e. whether they read 0). Finally, a processor (e) takes a snapshot, (f) waits for all processors it sees are participating to announce whether they successfully entered the doorway (using a read loop), and (g) outputs the value of the processor that has the max identifier among those who entered the doorway (any other deterministic function can be used instead of max).


Multicore SAT Solver I am trying to solve a 25k clauses 5k variables SAT problem. As it has been running for an hour (precosat) and I'd like to solve bigger ones afterwards, I'm looking for a multi-core SAT-Solver.

As there seem to be many SAT-Solvers, I'm quite lost.

Could anyone point me out the best one for my case?

I'd also be happy if someone could give me the approximate time (if possible).

Have a look at the results from this years SAT 2013 competition. Based on these results, definitely give Lingeling a try. Plingeling is the parallel variant of it.

If you don't need to prove unsatisfiability (perhaps you know the instance is satisfiable, and you just need to know an assignment making it SAT), you could try local search methods, too.


Can inputs in the decision tree model be computed? The Wikipedia definition of the decision tree model says that it allows the sign functions of certain classes to be computed in constant time (and presumably also memory). My questions, still unresolved by reading the article, are:

Can those functions be fed any values computed by the algorithm (including ones of asymptotically larger magnitudes) or just ones from the input array?
Do the coefficients in the linear decision trees have to be hard-coded? The article seems to indicate that there are as many of them as elements in the input (and even more, exponential in the maximum allowed degree $d$, for algebraic decision trees), which means they cannot be hard-coded. Or is the $n$ in this fragment different and actually only sums of some fixed number of terms, independent of the input length, are allowed?
Regarding point 1, does it make a difference, i.e. can some problems be solved asymptotically faster (or in less memory) when comparisons of differences (or linear combinations, or polynomial functions) of any intermediate computed numbers are allowed? If yes, does the answer change if the numbers fed to the functions can only be $$ of those in the input array?

A decision tree is a special kind of "program" which computes a function, usual from $\{0,1\}^n$ to $\{0,1\}$. Let's take an example from Wikipedia:

A decision tree is a binary tree. Internal nodes are labeled by functions from a set $\mathcal{F}$ (more on this, later). Leaves are labeled by elements from $\{0,1\}$. Each internal node has one child labeled $0$ (the left child in the diagram) and another child labeled $1$ (the right child in the diagram). The binary tree doesn't have to be complete as in the example above.
In order to evaluate the decision tree, you start from the root, evaluate the function written there, and descend to the left child or to the right child accordingly. You continue in this fashion until reaching a leaf, at which point you output the label written there.
The cost of a decision tree is its depth, or equivalently, the maximum number of edges in a root-to-leaf path.
The most common choice for the set $\mathcal{F}$ of allowed queries is $\{x_1,\ldots,x_n\}$. Linear decision trees are decision trees in which $\mathcal{F}$ consists of all linear threshold functions. Alegbraic decision trees of degree $d$ are decision trees in which $\mathcal{F}$ consists of all polynomial threshold functions of degree $d$.
Comparison-based algorithms can also be modeled by decision trees. Here the input is an array of length $n$, the output is a permutation of the positions of the array, and the allowed queries are comparisons.
Decision trees capture some properties of algorithms, and ignore other properties. They are most often used to prove lower bounds on algorithms solving a certain problem. For example, we can represent every comparison-based sorting algorithm as a decision tree. This representation completely ignores how difficult it is to decide what comparison to do next, and how difficult it is to generate the output given the results of past comparisons. Yet the model is useful, since it shows that every comparison-based sorting algorithm must make $\Omega(n\log n)$ comparisons in the worst case, and in particular, must have running time $\Omega(n\log n)$.
Kane, Lovett and Moran constructed linear decision trees of depth $\tilde{O}(n)$ solving the 3SUM problem. In contrast, the 3SUM conjecture states that no RAM-based algorithm for 3SUM runs in time substantially better than $O(n^2)$. This is one case in which the decision tree model isn't able to capture the hardness of a problem.
The main point here is that proving lower bounds on computation time is hard. The only lower bounds we know how to prove are in restricted models, or on a specific type of resource, such as queries in the decision tree model, or communication in the communication complexity model. These models abstract away computation but capture some pertinent properties which suffice for proving meaningful lower bounds in many cases.
We can now answer your questions one by one:

The decision tree model is really a family of models, parametrized by the set $\mathcal{F}$ of allowed queries. As a user of the decision tree model, you get to decide which queries you allow.

The decision tree model is a non-uniform model. You can use whatever functions from $\mathcal{F}$ that you wish. Unless stated specifically, there is no requirement that there be an efficient procedure that constructs the decision tree for inputs of given length.

The most common measure of complexity for decision trees is depth. Another measure of complexity sometimes used is size; in this case, we sometimes allow DAGs (known in this context as branching programs) rather than just (directed) trees. Enlarging the set $\mathcal{F}$ of allowed functions can reduce the complexity.

For the specific case of linear decision trees, it is known that arbitrary weights can be reduced to polynomial weights at the cost of increasing the depth by at most 1, see Goldmann and Karpinski, Simulating threshold circuits by majority circuits. (The models are not the same, but it seems likely that the conclusion still holds.)
Another example where comparing more complicated linear functions can make a large difference is 3SUM. The decision trees constructed by Kane, Lovett and Moran have sparsity 6, while an earlier lower bound of Ailon and Chazelle (cited in [KLM]) shows that sparsity 5 cannot achieve depth $\tilde{O}(n)$.


Vertex cover of a graph by removing leaf-vertices from a DFS tree Question taken from "The Algorithm Design Manual" by Steven S. Skiena, 1997.

A vertex cover of a graph $G=(V,E)$ is a subset of vertices $V'\subseteq V$ such that every edge $e\in E$ contains at least one vertex from $V′$.

Delete all the leaves from any depth-first search tree of $G$. Must the remaining vertices form a vertex cover of $G$? Give a proof or a counterexample.

Answer given :

If the tree has more than one vertex, then yes. The remaining vertices are still the vertex
cover because for every edge e∈E incident on the leaves, their other end-point is still in the
remaining tree.

My question:

The answer is right for undirected graphs. But I think there exist counterexamples to this question using directed graphs.

For example:

If we are using DFS starting from vertex $a$ and we are traversing in alphabetical order, i.e. explore b first, then we end up with two tree edges, which are $(a,b)$ and $(a,c)$. Therefore, $b$ and $c$ are leaf-vertices.

But here if are going to delete vertices $b$ and $c$ the edge $(c,b)$ has no incident vertices which are contained in our vertex cover.

Am I right? I am confused actually.

Look at the definition of vertex cover (as provided by the book). It is strictly defined on undirected graphs. Thus, the answer doesn't apply to directed graphs, nor to any other kinds of graphs you might think of. So your counterexample is invalid, as it makes invalid assumptions (graphs are always undirected here). These invalid assumptions are the source of your confusion.

To consider directed graphs, we first need to define what a vertex cover is on a directed graph. Well, we can say it is a subset of vertices such that every arc is incident to at least one vertex in the subset. Again, the book makes no claim about such directed vertex covers. If you are now asking "does $\{ a \}$ form a (directed) vertex cover as per our definition?", the answer is NO as you correctly observed.


Polynomial Reduction 3SAT to K-Clique I am reading the reduction given by Sipser in his textbook "Introduction to the Theory of Computation," on page 303. The reduction is:

\begin{equation} 3SAT \leq_p KCLIQUE \end{equation}

I am really trying to understand everything formally -- putting everything in a strict logical notation helps me learn Math. To clarify, the content of this proof, has not helped me give other reductions because I don't understand one direction of the $\iff$ in the logic of reductions.

In this reduction, $f$ must be s.t:
\begin{equation} w\in 3SAT \iff f(w) \in KCLIQUE \end{equation}
and $f$ computes within a polynomial number of steps of the input size. The polynomial part is easy for me to understand, so no problem here!

I see that the above logical statement is equivalent to:
\begin{equation} w\in 3SAT \implies f(w) \in KCLIQUE \land w\not\in 3SAT \implies f(w) \not\in KCLIQUE\end{equation}
The above just says yes-instances map to yes-instances and no-instances map to no-instances.

It appears that Sipser shows us:
\begin{equation} w\in 3SAT \implies f(w) \in KCLIQUE \land f(w) \in KCLIQUE \implies w\in 3SAT\end{equation}

Which is also equivalent to the above by taking the contrapositive of the second implication.

Here is my understanding of the $\implies$ direction. Given a yes-instance of $3SAT$, show that the reduction $f$ gives us a yes-instance for $KCLIQUE$. This seems completely natural.

I don't really understand the other direction -- namely, given a yes-instance of KCLIQUE we are supposed to show that we get a yes-instance of $3SAT$. However since the reduction goes from $3SAT$ to $KCLIQUE$ i.e. the domain is the language $3SAT$ and the Codomain is the language $KCLIQUE$, I don't understand how we show this.

It appears that the argument is; Our reduction has provided us this graph, from which we can create a satisfying assignment from?

Please help me understand the other direction, and thanks for your time.

Your problem may be a slight misunderstanding.

  Given a yes-instance of KCLIQUE we are supposed to show that we get a yes-instance of 3SAT.

This is almost correct; check the claimed equivalence again:

$\qquad\displaystyle w \in \mathrm{3SAT} \iff f(w) \in \mathrm{KCLIQUE}\;. \tag{1}$

For the "backwards" direction, you only need to assume a yes-instance from the intersection of the image of $f$ and KCLIQUE, i.e. show that

$\qquad\displaystyle \forall w \in \operatorname{img}(f) \cap \mathrm{KCLIQUE}.\ f^{-1}(w) \in \mathrm{3SAT}$.

That means that you can assume some structure about the instances you need to prove the reverse direction for, namely that introduced by your reduction.

Another misunderstanding:

  the domain is the language 3SAT and the Codomain is the language KCLIQUE

That's not true; note that (1) is (maybe implicitly) supposed to hold for all $w \in \Sigma^*$, that is the domain of $f$ is $\Sigma^*$. All $w \not\in \mathrm{3SAT}$ must therefore map to $f(w) \not\in \mathrm{KCLIQUE}$ in order to fulfill (1), so the codomain also needs at least one value that is not a yes-instance of KCLIQUE.


What does "post-image analysis" mean in the context of formal program analysis? I am reviewing an anonymous paper about a sort of static analysis of programs that uses the phrase "post-image analysis", or "post-image operation" without defining what that is. I am guessing it is a well-known concept in formal methods, even though a Google search has not revealed anything.

I am guessing it means an analysis of the trace of a segment of a program. Basically, you run it a little bit, you collect the trace (perhaps that's a synonym for "image"), and analyse. But I am just guessing.

Can anyone tell me what that is, or give me a pointer?

When working with transition systems,  $\text{post}(s)$ is the set of states that are reachable in a single step from the state $s$; if $S$ is a set of states,

$$\text{post}(S) = \bigcup_{s \in S} \text{post}(S).$$

Also, $\text{post}^*(s)$ is the set of states that are reachable from $s$, i.e., $\text{post}^*$ is the transitive closure of $\text{post}$.


Defining function for arithmetic expressions I've got these arithmetic expressions
a  ::=  n  |  x  |  a1 + a2  |  a1 ? a2  |  a1 − a2

which are a part of language.
An undefined element is allowed ⊥ which extends the set of intergers to Z∪{⊥}.
Problem:
I need to define the function

A: Aexp → (State → Z∪{⊥})

by defining equations for each form of the arithmetic expression a.
Now I've tried to come up with an solution but I am pretty sure I am wrong and I gotta admit I am pretty stuck.
Some help understanding this problem would be great.

Hint: Here is one example

$A($ a1 - a2$, s) = minus(A($ a1$,s),A($ a2$,s))$

or alternatively

$A($ a1 - a2$) = \lambda s . minus(A($ a1$,s),A($ a2$,s))$

where $minus$ is the substraction in $\mathbb Z\cup\{\bot\}$


Is a complete code always optimal? According to wikipedia, Kraft's inequality holds with equality when a code is complete. Huffman encoding produces a complete code that is optimal. Are all complete codes optimal and vice versa?

No. If I have three symbols with probabilities A = 0.5, B = 0.25 and C = 0.25 then A=0, B=10, C=11 is complete and optimal. B=0, A=10, C=11 is complete but absolutely not optimal.

An optimal code on the other hand must be complete, because otherwise you can shorten the encoding of some symbol.


Travelling Problem with Constraints Consider a network with $N$ nodes $1,...,n$. Every node is connected to every node via a weighted edge, where the weight represents distance.

You start your travel at a given node, say $1$, and end your travel at a given node, say $12$. Your travel has $T$ time steps. At time step $t=1$ you must visit one of nodes $\{1,7,4\}$, at time step $t=2$ you must visit one of the nodes $\{7,3,45,9\}$, and so on. In other words, at a given time step, you are given a set with at minimum $1$ and at maximum $K\leq N$ nodes. Choose the nodes for all time steps such that the cumulative distance is minimized.

Am I correct, that such problem is NP hard? Given $T$ time steps and that at most $K$ nodes are possible at each time step, the complexity would be $O(K^T)$, right?

What algorithms could be applicable or useful for such a problem? In my scenario, $T$ can be very large (up to 20,000) but $K$ is rather low (10 on average, at most 100).

(Edit) - I encountered the problem in a diary of a traveller. For example, you know that a traveller started his journey at some location. For every journey entry, besides the raw text, the writer in the title writes a date  and a location name.

The problem is there often exist several different coordinates for a location name (i.e., multiple locations exists with the same name). An (I think reasonable) assumption I have come to, is that the shortest possible path (from start to finish) should approximate the travelled route quite well. I have a data set of multiple travellers with diaries like this and want to plot the routes onto a map (and hope to display a travelled route approximately in the way which in it was really travelled).

I have not yet come up with any good and general solution (besides brute-force computing the distance of every possible route, which may be impossible because there exist tons of diary entries and so many location names have multiple possible coordinates).

The problem can be solved efficiently: in $O(K^2 T \log (KT))$ time.

Build a graph where each vertex corresponds to a pair $(t,i)$, where $t$ is a time step and $i$ is one of the nodes that is allowed to be visited at time $t$.  Add edges from $(t,i)$ to $(t+1,j)$ for every $t,i,j$, with a length that corresponds to the travel time from $i$ to $j$.  Add a source node $s$ with edges from $s$ to each $(1,i)$ of length 0, and a sink node $t$ with edges from each $(T,i)$ to $t$ of length 0.  Then, find the shortest path in this graph from $s$ to $T$.

The graph has $O(KT)$ vertices and $O(K^2T)$ edges, so Dijkstra's algorithm for finding shortest paths will run in $O(K^2 T \log (KT))$ time.


Proving decidability of language Prove or disprove:
The following language $L$ is decidable:

$\{ \langle M, t\rangle: M \text{ is a Turing machine and } \forall w \in \{0,1\}^* [M(w) \text{ halts in at most } t \text{ steps} ]\}$

So for proving I need to construct a TM $U$. If it accepts $L$, so L is decidable, otherwise not.

My steps are:

$U$ = "On input $ \langle M, t\rangle$:

$i:=1$;
Simulate one step of $M$ on $w$.
If $M$ accepted $w$ then $U$ accepts.

If $M$ rejected $w$ then $U$ rejects.

If $i ≥ t$ then $U$ rejects.
Else $i:=i+1$; goto step 2."

Because $U$ is the decider machine (finite number of steps) $\longrightarrow$ $L$ is the decidable language.

Is this solution correct? Or I should do it in another way?

I have not fully understood the algorithm, as it didnt state what $w$ is.

Although, the language $L$ is decidable:

Build the TM for the following algorithm: (assuming input of form $<M,t>$)

For every $w\in\Sigma^*$ with $|w|\le t$:

Emulate $M$ on $w$ for $t$ steps. If $M$ did not halt in that time, reject.

If for all such $w$, $M$ halted within $t$ steps - accept.

This algorithm always halts - as there are a finite number of $w$ with $|w|\le t$ (and it does not simulate $M$ for more than $t$ steps)

The algorithm is right:

If $<M,t>\in L$ then $M$ will halt within $t$ steps on every $w$ we will check, therefore the algorithm will accept.
If $<M,t>\notin L$, then there is some $w\in\Sigma^*$ where $M$ doesnt halt on him within $t$ steps. Notice, that if we define $\hat w=w_{1,...,t}$ to be the first $t$ letters of $w$, then also $M$ wouldnt halt on $\hat w$ within $t$ steps, as if it would have been - then $M$ didnt read move its head right more that $t$ times - and therefore for every $y\in\Sigma^*$, $M$ halts on $\hat wy$ within $t$ and specifically $w$ too. The algorithm can find the $\hat w$ (since $|\hat w|=t$) and will reject because of it.


Does any algorithm exist for computing the state of a non-trivial cellular automaton after an arbitrary number of time steps? If have a cellular automaton, can I see the state of the board after something like $10^{{10}^{10}}$ time steps? For trivial cases, this is possible - for example, a cellular automaton where the state of the board is known to repeat after some finite period.

But are there any cellular automata (or perhaps even similar computational structures) that display chaotic behavior but can also be very quickly evaluated to extreme time steps into the future?

Two answers...

There is a trivial algorithm to do it: "Just" run the automaton for the required steps.
No, there is no general way to compress the computation. If you can prove that the automaton enters a periodic configuration, you certainly can. You can also precompute the result of a certain number of steps, and use that to skip ahead (doing several steps in one round). That is one of the ideas used to speed up finding Busy Beavers. But in general, as cellular automata are Turing-complete, to find out if you are in one of the cases where it stops or repeats is easily seen to be undecidable.


How can I derive a formula that produces a set of numbers per index? For example, assuming I am using the set of natural numbers $\mathbb{N}^* = \mathbb{N} \cup 0$ as my domain.
I want to create an algorithm such that at each index value $i$, I output a set.
For example,

$0$ maps to $\{1,2,3,4\}$
$1$ maps to $\{5,6,7,8\}$
$2$ maps to $\{9,10,11,12\}$

How might I go about deriving the function needed to produce the desired codomain?


Is there a complexity class “BQP without error”? I was wondering if there is a complexity class for problems that can be solved efficiently by a quantum computer such that it always gives the right answer? For example the Deutsch-Josza algorithm never fails. Another way of asking would be: is there a class (call it Q) such that Q is to P what BQP is to BPP?

I guess classically the question also makes sense: is there a class for problems that can be solved efficiently by a computer with access to randomness and never making an error? (I suspect this is simply equal to P?)

Yes, it's called EQP (exact quantum polynomial) and is listed in the complexity zoo:

  The same as BQP, except that the quantum algorithm must return the correct answer with probability 1, and run in polynomial time with probability 1. Unlike bounded-error quantum computing, there is no theory of universal QTMs for exact quantum computing models. In the original definition in [BV97], each language in EQP is computed by a single QTM, equivalently to a uniform family of quantum circuits with a finite gate set K whose amplitudes can be computed in polynomial time. See EQP_K. However, some results require an infinite gate set. The official definition here is that the gate set should be finite.


Arithmetic on signed 12-bit octal number stored in sign magnitude form What is 4365 − 3412 when these values represent signed 12-bit
octal numbers stored in sign-magnitude format? The result should be written in
octal. Show your work.

Octal to binary:

4365: 100 011 110 101
3412: 011 100 001 010

By recognising the role of the sign bit, we can
represent positive and negative 64-bit numbers in terms of the bit value times a
power of 2. The binary number x, where xi means the ith bit, represents the number:

(x11 * -2^11) + (x10 * 2^10) + (x9 * 2^9) + ... + (x1 * 2^1) + (x0 * 2^0)

I have used the formula given above to convert the value of octal 4365 in decimal:

(1 * -2^11) + (1 * 2^7) + 2^6 + 2^5 + 2^4 + 2^2 + 2^0 = -2048 + 245 = -1803

Similarly, the value of octal 3412 in decimal is 1802.
Having obtained the two values in decimal, I subtract (-1803 - 1802), obtaining the result -3605.
Binary representation of 3605 is 111 000 010 101.
Converting it back to octal gives 7025.

This answer is wrong. It should be octal 7777 or decimal -3777.
The concept is not clear to me. Where am I going wrong?


Location Selection Algorithm in Solar Engineering This is a practical problem in energy generation with heliostats.

We have a number of heliostats basically forming the shape of a doughnut. The facility needs to deploy hubs on those heliostats. One hub can support 12 harnesses (a kind of cable) and one harness can support 16 heliostats; namely, one hub can support 192 heliostats. The cost of deploying a hub and harness per meter are given. In other words, every harness starts from a hub and can connecting at most 16 heliostats. Deployment of a hub results in a cost. Also, the cost of harnesses result from its distance from the hub to the furthest heliostat on this harness. However, there is no distance from heliostats to its connecting harness.

Currently my approach is to use k-means to cluster the whole region and run greedy on distance from harness for each split region, though I do not think this is a good approach.

This is a pattern generated by my algorithm. As you can see, some harness only support 1 or 2 heliostats and result in a waste of harness.

Our job is to optimize the cost. In the end, the algorithm should return locations of hubs, harness topology patterns, and the total cost.

Can anyone enlighten me potential algorithms on this?

(Every point on the image is a heliostat, there are 40981 in total)

----------- Updated 14/12/2016 -----------

More details on the question, thanks D.W's suggestion:

Coordinates of heliostats are given. These coordinates correspond to real-world metrics (meters).
The placement of hubs are not constrained. However, one harness cannot be longer than 45 meters due to voltage requirement.

----------- Updated 15/12/2016 -----------

The classification on "furthest" in "the cost of harnesses result from its distance from the hub to the furthest heliostat on this harness": Furthest is in the sense of "last", not "furthest" in the sense of "having the largest Euclidean distance from the hub"

The problem looks messy, so there probably isn't a clean algorithm to
produce a globally optimal solution.  Instead, I suggest you use some
combination of heuristics to try to find a nearly-optimal solution
in a reasonable amount of time, perhaps by iteratively making small
incremental improvements.

Any candidate solution is comprised of three elements:

Location of the hubs.
Assignment of each heliostat to a hub.
Routing of the harnesses.

One way to make an incremental improvement is to repeatedly fix two
of these three and optimize the other (holding the other two fixed),
and rotate through which one you change.  You seem to have a reasonable
strategy to obtain an initial candidate solution, and you could iterate from
there.  I'll sketch in more detail each of these three optimizations,
which you could rotate through repeatedly until you cannot make any
further improvement:

Harness optimization. Hold the location of the hubs and the
assignment of which hub each heliostat is associated with fixed
(to be the same as in the current candidate solution).  The goal
is optimize the routing of the harness wiring.  For
candidate algorithms for that, see the other question.  My
suspicion is that this step is the one where there are the greatest
opportunities for improving your solution, and where it's worth
devoting the most effort to.

Hub location optimization. Hold the heliostat-to-hub assignments
and harness routing fixed.  Pick a single hub and the heliostats
associated with it.  Then it's easy to fine-tune the location
of the hub to minimize overall cost, under the assumption that you
don't change the topology/routing of the harnesses.

In particular, each
harness contributes one edge from the hub $r$ to the heliostats
$h_1,h_2,\dots,h_{12}$ it is immediately connected to.  Now we want
to find a location for $r$ that minimizes the sum of distances
$d(r,h_1)+\dots + d(r,h_{12})$.  This is a sum-of-squares problem
so it can be solved through standard sum-of-squares optimization,
or simply by solving it with gradient descent; since we're in only
2 dimensions I would expect any method to converge rapidly.
You can do this separately for each hub.

It would also be possible to try a random perturbation to the
location of the hub, re-apply harness optimization, see whether
this reduced the overall cost, and if so accept that change to the
hub location.  This might be more expensive than it is worth.

Heliostat assignment to hubs. Hold the location of hubs fixed,
and assume we're not going to make radical changes to the harness
topology.  We can try to fine-tune the assignment of heliostats to
hubs in a number of ways.

One approach is to pick a heliostat $h$ that is currently assigned to
hub $r_1$ but is relatively close to another heliostat that's wired
to a different hub $r_2$, try swapping which hub it is associated
with, and see if this leads to any reduction in cost.  To determine
whether it leads to a reduction in cost you could re-run
harness optimization from scratch in both cases (which might be slow).
Or, as a fast heuristic, you could remove $h$ from its current harness,
find the nearest heliostat $h'$ that's currently connected to $r_2$,
attach $h$ to $h'$ (splicing it into the harness for $h'$), and see
whether this reduces the cost.

Another approach would be to do a more ambitious optimization.
Pick a pair of hubs $r_1,r_2$ and the set of heliostats currently
connected to either of them.  Now try to apply joint harness optimization
to that set of heliostats and those two hubs simultaneously,
simultaneously optimizing the routing of the heliostats and also
which hub each heliostat is connected.  The methods in that other
question can be generalized to solve this problem.  When finding the
solution we may find that one or two heliostats switch which hub they
are connected to.  Now repeat this for every pair of adjacent hubs.
However, my guess is that heliostat assignment might not yield many
gains (compared to the naive method of assigning each heliostat to
the hub it is closest to), so it might not be worth implementing these
more sophisticated methods for heliostat assignment.

Overall algorithm. In summary, we start from some initial
solution (e.g., selected using the method described in the question)
and then repeatedly rotate through the following three operations:

Harness optimization: fine-tune the routing of the harnesses.
Hub location optimization: fine-tune the location of the hubs.
Heliostat re-assignment: fune-tune the assignment of heliostats to hubs.

There is no guarantee that this will lead to a global optimum, i.e.,
the absolute lowest cost possible.  This could get stuck in a local
minimum.  There are various methods for dealing with that (e.g., applying
random perturbations; re-starting from multiple randomly chosen initial
solutions), which you could experiment with as well.

Hopefully this will help you find a solution that is "good enough",
or at least, get you started on some methods to try.  Good luck!


Select signals for memory mapped into common address space I just got a hobby of studying this topic and it is quite intriguing. In one of the books, I came up with the following question:

A computing hardware is to be designed with a processor generating 32bit address for memory. It requires 2GB of RAM, 128MB of EPROM and 1MB of EEPROM, and these are mapped in the memory address space as follows.
EEPROM: 0 to (1M–1) EPROM: 128M to (256M–1) RAM: 2G to (4G–1).
Write the Boolean expressions for the signals EEPROM Select, EPROM Select, RAM Select.

I couldn't find any solution to this and there is hardly any resource on the internet too.
So can anyone explain me, how we write the Boolean expression for such questions? I am aware of boolean logic to logic gates, but I am unable to make anything out of this question.

Let's call the memory address $x$. Thus $x$ is composed of bits $x_0,\ldots,x_{31}$, where $x_0$ is the LSB and $x_{31}$ is the MSB.
A memory address belongs to the EEPROM mapped area if it is in the range $0,\ldots,2^{20}-1$. You can check that this is equivalent to the condition $x_{20} = \cdots = x_{31} = 0$, which you can translate into a Boolean expression for "EEPROM Select".
The other signals can be handled similarly.


Minimum number of scenarios to run to fully test a page I run a testing application that, using Selenium, runs testing "scenarios" each of which visits a bunch of pages on a website. Each page is modeled by a Java file that contains locators, each of which are used to locate certain elements on the page maybe to verify that they exist or, beyond that, that they work as intended. Some elements may always show up, and some may only show up depending on the scenario you are running. Let's say the page we would like to test in question is the "login" page, and we are talking about all the scenarios that visit that page.

Bear in mind, some scenarios may visit the login page, but only a small subset of those scenarios are actually intended to test the login page.

Let's say each page is modeled by a Java source file that contains a bunch of locators intended to locate elements on that page.

Each scenario is intended to test a different overall functionality on the website, but as far as the login portion of each scenario is concerned, multiple scenarios might be totally redundant (only one of these redundant scenarios need to be run to achieve the exact same level of interaction). Let's say one set of redundant scenarios only minimally enters a username/password and then clicks the log in button. So our Java page always has the exact same sets of locators locating the same elements and not locating any elements for those redundant scenarios.

Let's say 100 of your scenarios visit the login page. Let's also say you ran all 100 scenarios to fully interact with that page, but only 10 of them needed to be run to achieve the same thing, that is, only 10 needed to be run to fully test the page.

Let's say each locator in the Java file modelling the login page is marked with the scenarios where it successfully located an element on the page. Each locator could have anywhere from 1 to 100 scenarios tagged to it.

Having already run the 100 scenarios, how do you go about knowing what those 10 scenarios are for future benefit? What sort of algorithm would achieve this? Thanks!

I would approach this a little differently.

Suppose you want to test a particular piece of functionality, e.g. logging in.

You first need to navigate to the login page, which may succeed or fail. Failure doesn't mean your test is failing; it means a precondition of your test, namely, being able to navigate to the login page, is failing. That's not what you're testing in this test.

Once you've arrived on the login page, you can attempt to log in, which may succeed or fail. This is the test you want to perform. If your test is correct, the results will correctly indicate whether logging in worked or not.

This is true in general: tests may generally have preconditions that aren't part of the test, but that can be tested themselves.

I think what you're trying to say is that many different paths may cause the precondition (in this case: the login page being reached) to be fulfilled, and testing those paths really should be separated from running the test that that precondition is a precondition for.  We want to test those paths separately, and once we think they are reliable, use any of them to fulfill the precondition for the present test.

This can be formulated differently by saying: we'll assume that using the application will put us into certain consecutive states, and what we want to do is test each transition between states. Certain sequences of actions will (if they go well) bring us into a certain state, suitable as a starting point for performing the test we want to perform. The test will then perform another action, that is supposed to bring us into a certain state (the transition), and from the test we will be able to determine whether that state has actually been reached (whether the transition happened that is supposed to happen).

We can express this by modeling the behavior of the application as a state machine that contains the states the application can be in and the state transitions we want to test.

However, we also need to take input and output into account. Sometimes, state transitions depend on user input. For instance, supplying a correct combination of username and password produces the state of being logged in; supplying an incorrect combination produces the state of not being logged in. Furthermore, the output we see (the webpage being produced) may not correspond to a specific state, it may also depend on which transition was taken to arrive into that state. For instance, when a login attempt fails, we will see an error message, but the resulting state is one of not being logged in, not one of being shown an error message.

Therefore, it's a good idea to introduce input and output into the model, which turns our model into an I/O automaton.

So the idea is to specify the application's behavior using an I/O automaton, then to write tests to test each of its transitions. Given those tests, you can automatically generate a complete test suite to test the whole system, using various strategies. I even know a piece of software designed to do this: JTorX.

We'll need to add parametrization. For instance, when logged in, we're logged in as a specific user. The user we're logged in as is a parameter to the state of being logged in. We may need to check whether we're logged in by checking whether certain attributes of that user appear in certain positions on the page. So being able to parametrize the model by user may be important.

Furthermore, I'd factor the state machine into a Petri net or similar. For instance, being logged in is not really a state; it is an attribute of a state. Typically, being logged in we can do everything we can do when not logged in (except logging in), plus a couple of things we need to be logged in for. This can be modeled using Petri nets or some derivative (some sort of colored Petri net).

This approach will provide structure and meaning to your endeavor. Your 100 test scenarios will be paths in your I/O automaton transition graph. Your 10 paths are those of the 100 that lead from the initial state to the state in which you need to be in order to start the test at hand. The whole thing will be incomparably more understandable and concise than just specifying a zillion test scenarios and trying to group them afterwards.

Too bad Selenium, TestNG, or anything else I've worked with don't support this approach directly.  If I were still working in test automation, I might have written something that does by now. The JTorX software is dead, as far as I know, but it may still be usable, or alternatives may be out there that use the same approach.


Reduce Set problem to SAT So the problem is, given some set $M = \{x_1,x_2,\ldots,x_n\}$ and a set of subsets $S = \{S_1, S_2, \ldots, S_m\}$ where $S_i \subseteq M$. We want to find some set $X \subseteq M$ such that $|X| \le k$ and $X \cap S_i \neq \emptyset$ for all $S_i \in S$.

My solution, I would take some set $M = \{x_1,x_2,x_3,x_4\}$ and suppose $S_1 = \{x_1,x_2\}$, $S_2 = \{x_2,x_3\}$, $S_3 = \{x_4\}$. I would then transform this to a SAT instance to get:

$\phi = (x_1 \vee x_2) \wedge (x_2 \vee x_3) \wedge (x_4)$

Clearly if $\phi$ is satisfiable then there exists some $X \subseteq M$ however this does not guarantee that $|X| \le k$.

So my question is, how can I reduce this problem further so that $|X| \le k$ in polynomial time?

EDIT

I realized there may be an easier way to reduce this to the set-cover problem but need confirmation that my idea is correct.

Will post a new question containing this.

The final constraint you need to encode is that $k$ or fewer variables in the set ${x_1, x_2, ..., x_n}$ is set true.  There is a good reference question that outlines several methods for encoding a 1-out-of-$n$ constraint.  Those methods can be extended to fit your constraint.  Using a chain of adder circuits plus a comparison circuit seems the most straightforward method to me.


is determinism = non determinism for one counter automata? This language I think is not accepted by a deterministic one counter but accepted by a non-deterministic one counter :

$L = \{a^{i}b^{j}c^{k} \mid (i=j) \vee (j=k) \text{ such that } i\geq0, j\geq0, k\geq0\}$

But how to prove this claim?

Or is it the case that they are equivalent?

You are right: the language $L$ from your question is accepted by a (nondeterministic) one-counter automaton.

Now for the deterministic case. Counter automata are a special case of push-down automata, where one only uses a single stack symbol (apart from a bottom-of-stack). Every (deterministic) one-counter language is also a (deterministic) push-down language. So in order to demonstrate it is not a deterministic one-counter language, I show a stronger result: it is even not accepted by a deterministic PDA.

According to Ogden, in his paper introducing Ogden's Lemma, that same language $L$ is inherently ambiguous context-free, meaning that every possible context-free grammar for the language is ambiguous, i.e., it has a string with two different succesful derivation trees.
On the other hand, it is known that every deterministic PDA can be transformed into a non-ambiguous CFG. In fact I believe the standard construction PDA to CFG does the trick (but that is not obvious).
Hence as there is no non-ambiguous CF grammar for $L$ (Ogden), there can be no deterministic PDA for $L$, and in particular no deterministic one-counter automaton.

Conclusion: for one-counter automata determinism is less powerful than the general model, using your example.

(In an edit I moved info from comments into this text.)
Reference, see also Wikipedia: Ogden, W. (1968). A helpful result for proving inherent ambiguity. Math. Syst. Theory 2, 191–194.


What happens to quantum algorithms such as BB84 if P=NP Under the hypothesis that P=NP, many cryptographic protocols are no longer secure (i.e. attacks are feasible).

The BB84 algorithm is based on the idea that by observing a quantum state, one has to (in quantum theory) disturb that state. This makes them efficient against eavesdropping.

Are quantum algorithms based on BB84 also subject to the hypothesis that P=NP? Or do they remain unaffected by the hypothesis?

BB84 is simply a key exchange procedure. This procedure remains secure unless someone can figure out how to observe a quantum phenomenon without changing it, whether or not $P=NP$ will not change this. If the vulnerability of the algorithm was in key transmission, then it is safe if it uses BB84. If it is however somewhere else in the algorithm, then no matter how the key is transmitted it will be vulnerable. So really it depends on the algorithm and the exposed vulnerability. Most algorithms that could be broken by a drastic reduction in run time however are public key algorithms, private key algorithms are much more secure, however the key exchange is the risky part and usually uses some form of public key based encryption. With BB84 however the key exchange becomes relatively safe. So for the most part, the algorithms that would use BB84 are not vulnerable unless the key can be discovered, which requires breaking BB84 and therefor changing the modern understanding of physics. Unfortunately  the infrastructure is not yet in place for BB84 to be realistically implemented.


Compilers: How to see "the number of grammars where there exists a string that has at least two different left-most derivations"? Could someone tell why "G1 and G3 are ambiguous" and how to see whether a string has at least two different left-most derivations in general?

Although the problem of detecting whether a grammar is ambiguous is, in general, undecidable, for toy grammars like this it is usually pretty easy to find ambiguities by simply enumerating the possible (left-most) derivations until you derive the same sentence in two ways.
For example, $G_1$ has just three productions $S\to a S b \mid S b \mid c$, and none of them has more than one non-terminal on the right hand side. So there are only four derivations of three steps, and it's easy to see that two produce the same sentence.
$$\begin{align}S&\to a S b \to a a S b b \to a a c b b \; (P_1, P_1, P_3)\\
S&\to a S b \to a S b b \to a c b b\; (P_1, P_2, P_3) \\
S&\to S b \to a S b b \to a c b b\; (P_2, P_1, P_3) \\
S&\to S b \to S b b \to c b b\; (P_2, P_2, P_3)\\
\end{align}
$$
$G_3$ does have a production which produces two non-terminals, so there are a lot more short derivations. Even so, it shouldn't take you very long to find two derivations for the same sentence.
Proving that a grammar is not ambiguous is not so easy. One possibility is to create a conflict-free parsing table, using any standard algorithm. Not all unambiguous grammars are deterministic (and fewer are deterministic with a single lookahead) but if you do manage to find a conflict-free parser, then the grammar was definitely unambiguous.


Finding big O notation of function with two parameters I'm looking to work out the big-O notation for the following:

$$\frac{n^{s + 1} - 1}{n - 1} - 1$$

I have a feeling the result is $O\left( n^s \right)$ but I'm not sure how to prove it.

Any help greatly appreciated! :)

Some of modifications of O described in Concrete Mathematics: Foundation for Computer Science says:

$ \qquad O(f(n)) + O(g(n)) = O(\mid f(n)\mid + \mid g(n) \mid) \qquad (9.22)\\
  \qquad O(f(n))O(g(n)) = O(f(n)g(n)) \qquad \qquad \qquad (9.26)
$

And using some basic knowledge of O notation and functions:

$
\qquad O(f(n) +c) = O(f(n)) \\
\qquad \forall_{n\in \mathbf N} \forall_{k>0} n^k > 0
$

Use those transformation you can came up with something like this:

$$\frac{n^{s+1}-1}{n-1}-1 = O\left(\frac{n^{s+1}-1}{n-1}-1\right) =
O\left(\frac{n^{s+1}-1}{n-1}\right) =
O\left(\frac{1}{n-1}\right)O\left(n^{s+1}-1\right) =
$$
$$
O\left(\frac{1}{n}\right)O\left(n^{s+1}\right) = O\left(\frac{n^{s+1}}{n}\right) = O(n^s)
$$

So your intuition was right.


Testing regular expressions algorithmically Is it possible to  test algorithmically whether the language of a given automaton is empty?

If I have a language L, could I say that L intersection with the empty set is L?

Hint: Check whether there is a path from the starting state to some accepting state.


what is approach of solving MINUS on SPOJ? Link:  http://www.spoj.com/problems/MINUS/

I have an Idea, after doing n-1 operations one can see that there is just + and - coefficients before each number that matters.
For eg.
given sequence: 12 10 4 3 5  and we need to make it a mathematical expression using + and - signs only to get 4 ,one solution will be  +12-10+4+3-5 = 4 ,this expression (+12-10+4+3-5) is get by using knapsack dp, so the exact sign sequence
(+)12(-)10(+)4(+)2(-)5 i.e. +-++- is the required signs sequence and at first stage (+)12(+)10(+)4(+)3(+)5 i.e. +++++ how to get +-++- and what should be sequence of operations?

I am assuming that you have found out the sequence of $+$ and $-$ which lead to getting the final result as the required integer $m$.
One observation here is that the sequence of $+$ and $-$ of length $n$ (size of array) will always start with $+$ $-$, and remaining integers can be either $+$ or $-$. To clarify: if the array is $a_1, a_2, a_3, a_4, a_5, \ldots, a_n$ then $m= +a_1-a_2 \# a_3 \# a_4 \# \cdots \# a_n$,
where $\#$ is either $+$ or $-$.
Now to decipher the order in which operations should be carried out to get such a sequence we first look at the rightmost $-$ in the sequence.
For example, let the integers be $5,8,1,6,2,12$ and $m=6$.
One way to get this is $+5-8+1-6+2+12$.
The rightmost $-$ is near $6$.
Let's add parenthesis here to divide the problem into two smaller ones: $(5-8+1)-(6-2-12)$.
Now solve these two smaller problems individually with same idea of rightmost $-$: $(5-(8-1))-((6-2)-12)$.
We can clearly see the operation that is asked in the question.


Does the Working Set Paging Algorithm use a separate page table? I am doing research on paging algorithms. While learning about the working set algorithm from several scientific sources I was not really able to figure out where exactly the working set is defined or realized.

I can only imagine two ways of realising this. The first is to put it into the page table file with indication bits; the second is to have another page table for the working set.

To be more specific: is the Working Set a completely different, separate list derived from the page table entries, or is it defined in the page table entries?

Denning provides a rough definition for a working set in Section 2:

  Roughly  speaking,  a  working  set  of  pages  is  the  minimum
  collection  of  pages  that  must  be  loaded  in  main  memory  for
  a  process  to  operate  efficiently,  without  "unnecessary"  page
  faults.

And provides the precise definition in Section 3:

  We define  the  working  set  of  information  W(t,  r)  of  a
  process  at  time  t  to  be  the  collection  of  information  referenced by  the  process  during  the  process  time  interval  (t - r,  t).

  Thus,  the  information  a  process  has  referenced  during
  the  last  r  seconds  of  its  execution  constitutes  its  working
  set  (Figure  2).

The term "page" in these definitions refers to physical pages, not virtual pages. That's because only those physical pages that have resided in main memory at least once during that period of time are part of the working set of a process.

  is the Working Set a completely different, separate list derived from
  the page table entries, or is it defined in the page table entries?

The working set is not defined by the page table entries. These entries define the whole virtual address space of the process. Also, by only looking at the page table entires, it's not possible to determine or derive the working set. The pages that are resident in main memory in a particular period of time and that have been accessed by the process in that period constitute the working set for that period.

Even if a page table entry includes an accessed bit (like the x86 page table entries) and even if the OS supports the accessed bits, it's still not possible to determine the working set just by looking at the page table entries. That's because the same page table entry may point to multiple physical pages during a period of time. At the end of that period, there is no way to determine all of the physical pages that any page table entry has defined during that period. So some additional data structures need to be used.


Big O analysis trying to follow a logic Can someone please help me understand why(the derivation) "and m = 2n+1 for each n."?
I am trying to follow the logic of the solution provide while myself have a different approach. Here is my thinking (questions state below):

The inner for loop runs m times from 1 and the outer for loop runs n times from 1.  Moreover, for each inner loop, m is increased by 2 based on previously additions and m starts at 1. With all these
observations, plug in n = 1, print (j) get executed 3 times; n = 2, print(j) get executed 8 times. n = 3,print(j) get executed 15 times.  We calculate the sequence to be 3,8, 15.....  which has the closed form as 2 n +$ n^ 2$ . Or by asymptotic run time as Θ( $n^2$ )

  fun(n)
       m = 1
       for i = 1 to n
          m = m + 2
          for j = 1 to m
             Print(j)

Solution: The  assignment  m=1  takes  constant  time.  The  line  m  =  m  +  2  is  run  n  many  times,  which
takes Θ( n ) time.  The inner print statement runs m many times, and m = 2n + 1 for each n.  The total number of times the print statement runs is

Can someone please help me understand why(the derivation) "and m = 2n+1 for each n."? How can we draw the connections with "the line m = m+2 is run m many times.." and "the inner print statement runs m many times" to get "and m = 2n+1 for each n."?

Possibly it's not for each $n$, but for each $i$.

First, try to calculate $m$ for each specific $i$:

 i | m
-------
 1 | 3
 2 | 5
 3 | 7
 4 | 9
   :
 n | 2n+1

$m$ increased by two for each loop of for i = 1 to n. Therefore $m = 2i+1$ for each $i$ in the loop.

And this is repeated from $i = 1$ to $i = n$, so in total,

$$
  \sum_{i=1}^n (2i + 1) = n^2 + 2n
$$


Relation is in 2NF or not? Consider a relation R(A,B,C,D,E) and the only FDs,
ABD->C
BC->D
CD->E
These are the only 3 FDs. I want to know if the above relation is in 2NF or not.
According to the definition of 2NF, a relation to be in 2NF, it should be in 1NF and it should not have partial dependency.
But I'm not getting the partial dependency concept.
Somewhere it's written that when a proper subset of a key determines a non-prime attribute then it is partial dependency.
Somewhere it's written that when a prime attribute which is not a key determines a non-prime attribute then it is partial dependency.
Because of these 2 different definitions I'm getting confused.
Please help.

Second normal form means that each non prime attribute must not depend on a proper subset of a candidate key.
In your example, assuming that the given FDs are a cover of the FDs of the relation, you have two candidate keys, ABC and ABD. Moreover, the attribute E depends on BC, which is a proper subset of the candidate key ABC (you can verify this by computing the closure of BC, BC+, and see that E belongs to that closure).
So the relation is not in 2NF.


Find an edge that is completely visible from point outside a polygon (Convex Hull) I want to implement algorithms from this paper:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.5609&rep=rep1&type=pdf

In particular, I am currently dealing with the one in section 2.2.1. In page 4 (first paragraph), one algorithm step is as follows:

Find an edge $(v_k, v_{k+1})$ of $P_i$ ($P_i$ is a convex hull) that is completely visible from $s_i$ ($s_i$ is a point outside the convex hull).

My question is, how can I find a completely visible edge of a convex hull, that is completely visible from a point outside the convex hull?

It is not too hard. connect the point to the end-point of an edge. If none of these two segments has an intersection with convex-hull, it means you can see that edge completely (as you consider a convex polygon).

To find the intersection, you can use a binary search and find that is there any intersection or not.


Universality of $(+, \oplus)$ over $\mathbb{Z}_2^n$ Let $\mathbb{Z}_2^n$ be the field of bitvectors of length $n$ and define the xor operator $\oplus$ and the addition operator $+$ over this field, with $+$ having the usual overflow semantics (take addition modulo $2^n$).
Is it possible to express any mapping $f: \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2^n$ entirely in terms of $\oplus$ and $+$? It seems like it might be possible due to the nonlinearity of $+$.

For instance, if we were given $n=2$ and that $f(0) = 3, f(1) = 1, f(2) = 3, f(3) = 1$, then we could construct $f$ as $f(x) = x\oplus(x+3)$.

Nope.  For instance, you can't express the function $f(x)=x>>1$.  In general, the least-significant bit of $f(x)$ depends only on the least-significant bit of $x$.  You can prove that by structural induction, using the following two properties: $(a \oplus b) \bmod 2 = (a \bmod 2) \oplus (b \bmod 2)$ and $(a + b) \bmod 2 = (a \bmod 2) + (b \bmod 2) \bmod 2$.


Time complexity for concatenating strings I was going through this piece of code from an algorithms books and something doesn't look clear

Please ignore the spelling errors,

How does 0(x + 2x + nx) reduce to o(xn^2) ?

My analogy, assuming x is a constant 1 and n is 2
(x + 2x) == 3 assuming x is a constant 1

From the book
(x2^2) == 4 assuming x is a constant 1

Am i right ?

How does O(x + 2x + nx) reduce to O(xn^2) ?

O(x + 2x + nx) will be reduced to o(xn). But as your text says O(x + 2x + ... + nx) will be reduced to o(xn^2). (So if you have n = 5 for example you have the time complexity O(1x + 2x + 3x + 4x + 5x) which is equal to O(15x).) The time complexity of 1 + 2 + ... + n is O(n^2) (since 1 + 2 + ... + n = (n^2+n)/2, see my comment below). But in your case every addend in the sum must be multiplied with x, so you have O(x*n^2) as final result.


Prominent applications not suited for distributed computing In the www I can find a lot of application examples suited for and benefitting a lot from distributed computing.

Question: Are there applications which are not suited for distributed computing? If yes (which I assume) which promiment examples are out there?

Thanks a lot for pointing me into some useful direction.

Most of the old (de)compression algorithms were not suitable for parallel or distributed computing. The variable length nature prevented decompressing later parts of the input stream before decompression of earlier parts was finished. And adaptive dictionaries often prevented compressing later parts of the input stream before compression of earlier parts was finished. Both issues can probably be avoided at reasonable cost, and maybe some modern (de)compression algorithms actually do this.
Nearly all cryptographic hashes will not be suitable for speedup by distributed computing. Any feature which could be exploited to make distributed speedup possible also risks being exploitable to weaken the cryptographic security of the hash.
Many popular black box opimization algorithms are not suitable for distributed computing in their basic form. Especially local optimization algorithms like the Nelder–Mead method or the Broyden–Fletcher–Goldfarb–Shanno algorithm are inherently sequential. But even more global algorithms like simulated annealing are local (and  sequential) in their basic form, even so it is possible to develop parallel forms for them.


Need recursive version of Conflict based backjumping I am implementing conflict directed Backjumping algorithm of prosser in java. But, the algorithm is iterative approach. How can it be built with recursive approach?

In AIMA they give the recursive version of backtracking.

function BACKTRACKING-SEARCH(csp)
  return BACKTRACKING({}, csp)

function BACKTRACK(assignment, csp)
  if assignment is complete then return assignment
  var ← SELECT-UNASSIGNED-VARIABLE(csp)
  for each value in ORDER-DOMAIN-VALUES(var, assingment, csp) do
  if value is consistent with assignment then
    add { var = value } to assignment
    inferences ← INFERENCE(csp, var, value)
    if inferences ≠ failure then
      add inferences to assignment
      result ← BACKTRACK(assignment, csp)
      if result ≠ failure then
        return result
  remove { var = value } and inferences from assignment
  return failure

They have said backjumping can be built by a little modification to this algorithm with conflict set but I don't think so.

Backtracking is just a recursive algorithm and it has to use stack stack. But,  in backjumping the stack sequence is trouble in jump. The worse is that java does not support goto statement.

So am i missing here something.
Please advice me how to get backjumping by modification of backtracking as shown in figure.

When a conflict is found during a recursive constraint satisfaction search there may be assignments and inferences in the call stack that have no connection to the conflict.  Instead of backtracking through these ineffectual assignments at exponential cost it is better to jump backward over them in the call stack directly to the most recent assignment that made the conflict inevitable.  This is backjumping.

To implement backjumping in the algorithm above, you would do three things:

Make the BACKTRACK function maintain a counter storing the depth of its call stack.
Instead of simply returning failure, have BACKTRACK also return a number representing the stack depth whose BACKTRACK function should resume execution.  This number would be determined by careful examination of the assignments and inferences that led to the conflict.
Have all calls to BACKTRACK at stack depths greater than the returned number simply return the number rather than continue iterating through ORDER-DOMAIN-VALUES.

All the ORDER-DOMAIN-VALUES assignments between the current level and the backjump target level will no longer happen. This gives exponential computational savings with a cost only linear to the size of the backjump.


How are lamport clocks implemented in real world distributed systems? Can anyone explain, how lamport clocks implementations are used in modern distributed systems?
Can you name an open source package which implements this algorithm?

Amazon's Dynamo [1] is a distributed storage system that uses vector clocks "to capture causality between different versions of the same object". Section 4.4 of the paper describes how exactly Lamport clocks are used to manage data versioning.

Some of the open source implementations of Dynamo are Riak [2] and Voldemort [3].

[1] G. DeCandia et al.: Dynamo: amazon's highly available key-value store. SOSP 2007:205-220

[2] http://basho.com/riak

[3] http://www.project-voldemort.com


Sorting a list of strings in lexicographic order of sorted strings Let $A$ be a collection of strings over the alphabet $\{0,\ldots,m-1\}$ that in total contain $n$ symbols.
Your task is to sort each of the strings internally, and then sort the resulting strings in lexicographic order. (Your algorithm doesn't have to operate this way.)
Example:
Input: 33123 15 1 0 54215 21 12
Output: 0 1 12 12 12333 12455 15

I found a way to do it in $O(m+n)$ time and $O(mn)$ space.
The space is larger than the time because I use a smart array that allows you to create an array with size $n$ and sort of giving initial values to all of the cells in $O(1)$.
I used bucket sort in order to sort each string ($O(m+n)$ time and space) and word trees in order to sort the collection $A$ itself ($O(m+n)$ time and $O(mn)$ space). but my solution is too complicated.
Does anyone have a better solution, with $O(m+n)$ time and less space, or faster than $O(m+n)$?
The solution must be deterministic so no hash maps or other statistical algorithms

My solution:
A smart array is an array of size $m$ which we can create and "initialize" in $O(1)$:
We create three arrays the size of $m$ without initializing any of them and we also keep a single integer variable called $C$.
The first array contains the data. The second array contains  pointers to a cell in the third array. The third array contains pointers to a cell in the second array. $C$ contains the number of cells initialed so far.
Suppose we would like to set the value of cell $i$ (suppose it is the first time we are doing it on this cell). Then we will go to cell $i$ in the first array and set it to the wanted val.
Now we go to cell $i$ in the second array and set it to point at cell $C$ at the third array. Set the  cell $C$ in the third array to point at cell $i$ in the second array. Increase $C$ by 1.
Suppose we would like to know if cell $j$ is trash (That means we have yet to set anything to it).
We would go to cell $j$ in the second array and look at the cell number (in the third array) that cell $j$ (in the second array) points to – we will call it $k$.
If $k>C$ then $j$ is trash (because we have only initialized $C$ cells so far and $j$ isn't one of them).
If $k<C$ we will look at what cell $k$ (in the third array) points to. If it is not $j$ then $j$ is trash. Otherwise $j$ isn't trash
That way we can know at each step if we initialized this cell and if not initialize it. So we have created and "initialized" an array of size $m$ in $O(1)$ time.
The main trick is not to initialize the entire array at the start but to find a way to know which cells we've initialized so far and initialize a cell only when we "look" at it. In the RAM model it takes $O(1)$ time to create an array of any size without initializing it.

A word tree of order m is a generalization of a TRIE. Each node contains an array of pointers to its sons. The array size is $m$.  Each node also contains a counter to say how many sets there are that are described by this node.
Because we are using smart arrays each time we add a word $A$ (a set) it only takes $O(|A|)$ time and $O(m|A|)$ space.

You can also solve this in $O(n \log n)$ time and $O(n)$ space:

First, sort each word using mergesort.  The running time of this will be at most $O(n \log n)$, and the space usage is $O(n)$.
Then, store all the words in a word trie.  The time and space for this will be $O(n)$, if you implement the word trie properly.  In particular, at each node of the trie, you should store the set of children as a hashtable (not as an array).  In this way, the storage at a node is proportional to the number of children it has, and lookup to find a child can be done in $O(1)$ time.  Thus, the running time of this stage is $O(n)$ time and $O(n)$ space.
Finally, read out all the words from the trie.  This involves taking each hashtable and sorting its contents, say using mergesort.  All of those sorting steps will take at most $O(n \log n)$ time.

The resulting data structure seems quite simple.  It's especially simple if you implement in a language that has built-in support for hashmaps (e.g., Javascript, Python).

Alternatively, you can replace the hashmap with a balanced binary tree data structure and get a similar running time.

As a general note about "smart arrays":

You can replace your use of "smart arrays" with a hashtable.  That way you will preserve the ability to do $O(1)$ (expected) time reads and writes.  In particular, instead of setting $A[i] := v$, you store value $v$ at the key $k$ (i.e., add the mapping $k \mapsto v$ to the hashtable).  When you want to read the value of $A[i]$, you instead lookup $i$ in the hashtable and return whatever you find there.  In this way, the space usage is proportional to the number of initialized entries in the "smart array", and each access takes $O(1)$ (expected) time.


Find the coins required which sum to S Given a list of $N$ coins, their values $V_1, V_2, \cdots , V_N$, and a parameter of a total sum $S$. Find the coins the sum of which is S (we can use each coin at most once).

I was recently studying the very same problem from topcoder.com but there "we can use each coin any number of times". I am just stuck here if we can use each coin only once and not multiple times.

It will be very helpful if you can help or just give a hint. (this is not my homework quiz :P)

Hint: Dynamic programming on this subproblem: "Can I get a sum of $x$ if I can use only the $k$ smallest coins?"


Big O notation, code time complexity does appending an element to a list through a for loop work in O(1) time or O(n) time? In addition, what is the time complexity does "".join that list into a string work in?

It totally depends upon the particular implementation. In linked-lists which support circularity (where the first element, possibly a sentinel, links back to the last one) the task can indeed be achieved in $O(1)$ time, for it requires fetching a pointer to the tail of the list; on the other hand, on implementations which do not support doubly-linked elements or other fancy mechanisms, a full iteration to the back of the structure might be necessary, thus requiring $O(n)$ time.
On a side note, the term list refers to an ADT (Abstract Data Type), which is merely a type coupled with a set of operations and specifications. Thus, the term list does not inherently have to be linked to the pointer-based implementation; in fact, an ADT implementation such as Java ArrayList may be also realized on arrays, giving a random-access time complexity on any location (including the tail) in $O(1)$ time.


I want to learn algorithms I did study applied math and dealed almost exclusively with the creation of ode/pde solver code. Now, I want to increase my knowledge in some aspects and I want to learn some basic algorithms like A*, MinMax, ... (not limited to searching; I am also interested in the basics of optimization and machine learning) and their implementation.

Is there a good resource (book, online course) available for me to learn this from? Any help is appreciated. I have no other CS-related background except my math degree.

Consider the textbook (from my undergrad years, many years ago):

Bazaraa, M. S.; Jarvis, J. J.; and Sherali, H. D. (1990). Linear Programming and Network Flows. 2nd Edition. New York: John Wiley.

Consider the recent edition of the textbook too.


An Alternative Hanoi Tower problem We got tower $T_1$ with $n$ odd disks (1,3,5,...) and tower $T_2$ with $n$ even disks (2,4,6,...).
Now we want to move all $2n$ disks to tower $T_3$.
If $T(p,q)$ is a recurrence relation of minimum number of moves we make to move $p$ disks from $T_1$ and $q$ disks from $T_2$ to $T_3$, we must find $T(n,n)$.

If anyone has any idea, please share.

Let $T_n$ be the the column of disks $1:2:…:n$.

Let's start by the end:

$(T_n)()()$ is the final configuration. The only mean to get there is by moving the disk $n-1$ on the stack $(n)$, so the remaining $T_{n-2}$ should be on another stick. So we should get to:
$(n)(n-1)(T_{n-2})$ in $2^{n-2}$ steps: first move the $n-1$ disk then use $2^{n-2}-1$ steps with Hanoi maneuvers to move the $T_{n-2}$. This again is accessible from
$(n-2:n)(T_{n-3}:n-1)()$ in $2^{n-3}$ steps, which again is reachable from
$(n-4:n-2:n)(n-3:n-1)(T_{n-5})$ in $2^{n-5}$ steps, from
$(T_{n-6}:n-4:n-2:n)(n-5:n-3:n-1)()$ in $2^{n-6}$ steps...

At the end we get $2^{n-2}+2^{n-3}+2^{n-5}+2^{n-6}+… +2^{n-3i+1}+2^{n-3i}+…+c$.

Which is about $3(8^{n/3-1}+8^{n/3-2}+…)= \frac378^{n/3}$ modulo some constant depending on the remaining modulo $6$ of $n$. Testing in practice to determine the constant gives the exact formula for $n$ disks which happens to be surprisingly simple:

$$ \left\lfloor  \frac37 2^n \right\rfloor \enspace .$$

For $n∈\{1,2,3,4,5,6,7,8\}$ we get $\{0,1,3,6,13,27,54,109\}$ (the first five terms verified by hand) which happens to be OEIS's sequence A033129 which confirms that this is the fastest way.


NP-completeness of DISCONNECTED-SET I'd like to show that the language DISCONNECTED-SET, defined by $$ \{\langle G, k\rangle | \text{$G$ is an undirected graph that contains a disconnected set of size $k$}\},$$ is NP-complete. (A disconnected set $S$ is defined as a set of vertices such that for every pair of vertices $u,v \in G$, if there is no edge between $u$ and $v$, then at least one of the vertices is in $S$.)

I'm under the assumption that it could be done by reduction from CLIQUE. I've made the following observations (which I'm unable to utilize, though):

If we have a graph $G$, then the maximum disconnected set of its complement $G'$ has a size equal to the number of nodes in $G$ that belong to connected components of size at least 2 in $G$.
If we have isolated nodes in $G$, the sizes of the disconnected sets in $G'$ are unchanged.

May I just ask for a tiny tip that would get me going in the right direction, not a complete proof. Thank you.

This is just VERTEX-COVER in disguise. The reduction from CLIQUE is also simple – a set is disconnected iff its complement is a clique.


How to define function type in AGDA The "function" type $\rightarrow$ is predefined in Agda. But how would one define it if it was not predefined?  Specifically I am talking about $\rightarrow$ in:

data Nat : Set where
     zero : Nat
     Suc : Nat -> Nat

It is not possible: -> is built into the underlying logic of Agda (and most dependently typed languages).

In particular, -> is not a type constructor, because it has binding properties. Because you can define things like (n : Nat) -> Vec A n, the compiler needs to add n to the variables in scope in the right hand side of the arrow, so this can't be done.

There are ways to cheat with bindings. For example, you can define $\exists x : T \ldotp S[x]$ as ex T (\x -> S), i.e. using a lambda to represent the binding. But, that lambda is typed using ->. Having dependent functions built in is the starter that bootstraps the rest of the type system. It's the only way the language can express quantification, so it ends up being critical.


Zero-Sum Games and Halting Problem Wikipedia states on the page of the halting problem, "For any program f that might determine if programs halt, a "pathological" program g called with an input can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do."

Suppose we have 2 neural networks, approximating f and g (allowing infinite size and depth limits). Is it wrong to assume that these two NNs can participate in a zero-sum game against each other, and that the Nash equilibrium (if it exists) of these 2 NNs contains the solution to the halting problem?

Turing proved that the halting problem is undecidable.

No algorithm that you can come up with will solve the halting problem.


Are the Confabulation Theories of Thaler and Hecht-Nielsen Isomorphic? Both S. L. Thaler and R. Hecht-Nielsen have set forth neural-based theories of "confabulation" applicable to machine learning.

The essential mathematics of Hecht-Nielsen is set forth in his paper "Cogent Confabulation".  Briefly it is an inversion of Bayesian inference.  Bayesian inference is P(x|a&b&c&d...) where one is estimating the probability of x assuming a, b, c, d, etc.  Its inversion is P(a&b&c&d...|x), which RHN calls the "cogency" of x given the assumptions.

I haven't seen a similarly succinct description of Thaler's mathematics that would permit comparison to see if the theories are isomorphic.  Are they?

I don't think they map onto each other, aside from RHN's brief discussion of thalamo-cortical loops, the inspiration for SLT's so-called "Creativity Machines." In SLT's architectures, compelling/cogent solution patterns are sought within a stream of novel activation patterns (i.e., confabulations) driven by various forms of internal disturbances to biological neural nets. RHN's definition of cogency is obviously not the same. The mathematics of SLT's model are scattered over several patents and papers, but the following might provide an overview: Predicting ultra-hard binary compounds via cascaded auto- and hetero-associative neural networks, Journal of Alloys and Compounds, 279(1998), 47-59, Synaptic Perturbation and Consciousness, International Journal of Machine Consciousness, 6(2):75-107, 2014, Cycles of Insanity and Creativity within Contemplative Neural Systems, Medical Hypotheses, 94:138-147, Elsevier, 2016, and Pattern Turnover within Synaptically Perturbed Neural Systems, Procedia Computer Science, 88, Elsevier, 2016.


Expectation of $u'^t v$ = $u^t v$ I have another question with dimensionality reduction.
I have a matrix $S \in R^{k \times d}$  and S is  in {$- \frac{1}{\sqrt k}, \frac{1}{\sqrt k}$} and i have two vector $u,v \in R^d $.

I need to understand why $E[u'^T v' ]= u^Tv$ where $u'=Su$.

I just have a intution, that maybe i just prove the left(or right span vector), but the hint is compute $E[S^TS]$ that for me this expectation is expectation of E[ I ] that if i m wrong will be 0...

I m a bit lost with this stuff.

i m thinking to do this

$E[u^t v] = E[u^T \sum vi ]$

another question is about the interval ... using $1 /\sqrt k $ is the same if i use a -1,1 with scaled factor of $\sqrt k $?

The idea is that
$$
\mathbb{E}[u^{\prime T} v'] = \mathbb{E}[u^T S^T S v] = u^T \mathbb{E}[S^T S] v,
$$
due to linearity of expectation. You can take it from here.


Recursive algorithm to compute a sum of product like function I am working on a recursive formula associated with discrete mathematics which seems very difficult to compute.
The formula is as follows

$F_{i,j}(m)=\sum_{t=j}^{m}\left [ x_{ij}.\sum_{k=1}^{m}\sum_{l=j-1}^{m} F_{k,l}(m-ij) \right ]$

It's given that $F_{i,j}(m)=0$ for $m<0$.

Here  $x_{ij}$ is defined as a random number with the property that $0<x_{ij}<j$.

How do I write a recursive algorithm to compute $F_{i,j}(m)$?

Assuming we are given the $x_{ij}$'s and $i,j,m$, your formula already is a recursive algorithm to compute $F_{i,j}(m)$.  If you use dynamic programming (memoization) to avoid re-computing $F_{i',j'}(m')$ more than once for any given tuple $(i',j',m')$, the running time will be $O(m^3)$, since you only evaluate $F_{i',j'}(m')$ for tuples $(i',j',m')$ where $0 \le i',j',m' \le m$.

If the $x_{ij}$'s are not given, your question is not well-defined.  If that's what you meant, it's possible you might be asking for us to compute the distribution of $F_{i,j}(m)$, but if so, the question needs to be edited accordingly.

Either way, I suspect that there must be some additional base cases you have not provided.  As it currently stands, the solution $F_{i,j}(m)=0$ for all $i,j,m$ satisfies your equation.  I suggest you edit your question to specify the missing base cases.


What does a wedge in a graph look like? I am reading Decompositions of Triangle-Dense Graphs by Gupta et al.

On page 2, in Definition 1 what is a wedge in a graph?

I know what triangle is but I don't know what wedge is and google isn't helping!

They say it in the paper.

  Let a wedge be a two-hop path in an
  undirected graph.

So it is a path with 2 edges, like 2/3 of a triangle.


Why are all problems in FPTAS also in FPT? According to the Wikipedia article on polynomial-time approximation schemes:

  All problems in FPTAS are fixed-parameter tractable.

This result surprises me - these classes seem to be totally different from one another.  FPTAS characterizes problems by how easy they are to approximate, while FPT characterizes problems by their difficulty relative to some parameter.  Unfortunately, Wikipedia (as of the time I'm asking this question) doesn't provide a citation for this.

Is there a standard proof of this result?  Or is there a source I could consult to learn more about this connection?

There is actually a stronger result; A problem is in the class $\mathrm{FPTAS}$ if it has an fptas1: an $\varepsilon$-approximation running in time bounded by $(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$ (i.e. polynomial in both the size and the approximation factor). There's a more general class $\mathrm{EPTAS}$ which relaxes the time bound to $f(\frac{1}{\varepsilon})\cdot n^{\mathcal{O}(1)}$ - essentially an $\mathrm{FPT}$-like running time with respect to the approximation factor.

Clearly $\mathrm{FPTAS}$ is a subset of $\mathrm{EPTAS}$, and it turns out that $\mathrm{EPTAS}$ is a subset of $\mathrm{FPT}$ in the following sense:

  Theorem If an NPO problem $\Pi$ has an eptas, then $\Pi$ parameterized by the cost of the solution is fixed-parameter tractable.

The theorem and proof is given in Flum & Grohe [1] as Theorem 1.32 (pp. 23-24), and they attribute it to Bazgan [2], which puts it two years before Cai & Chen's weaker result (but in a French technical report).

I'll give a sketch of the proof, because I think it's a nice proof of the theorem. For simplicity I'll do the minimization version, just mentally do the appropriate inversions for maximization.

Proof. Let $A$ be the eptas for $\Pi$, then we can construct a parameterized algorithm $A'$ for $\Pi$ parameterized by the solution cost $k$ as follows: given input $(x,k)$, we run $A$ on input $x$ where we set $\varepsilon := \frac{1}{k+1}$ (i.e. we choose the approximation ratio bound $1+\frac{1}{k+1}$). Let $y$ be the solution, $\text{cost}(x,y)$ be the cost of $y$ and $r(x,y)$ be the actual approximation ratio of $y$ to $\text{opt}(x)$, i.e. $\text{cost}(x,y) = r(x,y)\cdot \text{opt}(x)$.

If $\text{cost}(x,y) \leq k$, then accept, as clearly $\text{opt}(x) \leq \text{cost}(x,y) \leq k$. If $\text{cost}(x,y) > k$, reject as $r(x,y) \leq 1+\frac{1}{k+1}$ as $A$ is an eptas and

$$
\text{opt}(x) = \frac{\text{cost}(x,y)}{r(x,y)} \geq \frac{k+1}{1+\frac{1}{k+1}} > k
$$

Of course you get the running time bound for $A'$ simply from $A$ being an eptas. $\Box$

Of course as Pål points out, parameterized hardness results imply the non-existence of any eptas unless there is some collapse, but there are problems in $\mathrm{FPT}$ with no eptas (or even ptas), so $\mathrm{EPTAS}$ is a strict subset of $\mathrm{FPT}$ (in the sense of the theorem).

Footnotes:

An fptas (equivalently eptas or ptas) is an approximation scheme with the running time bounded as described above. The class $\mathrm{FPTAS}$ (equiv. $\mathrm{EPTAS}$, $\mathrm{PTAS}$) is the set of problems in $\mathrm{NPO}$ that have such a scheme.

[1]: J. Flum and M. Grohe, Parameterized Complexity Theory, Springer, 2006.
[2]: C. Bazgan. Schémas d’approximation et complexité paramétrée, Rapport de
DEA, Université Paris Sud, 1995.


Meaning of Steve Wozniak's epiphany on register addition/subtraction in 1975? I just finished reading Walter Isaacson's Innovators and on page 350 there is a quote from Steve Wozniak recalling things he learned from the March 1975 Homebrew Computer Club meeting:

  A person at the meeting passed around the specification sheet for the new Intel microprocessor. "That night, I checked out the microprocessor data sheet and I saw it had an instruction for adding a location in memory to the A register," he recalled. "I thought, Wait a minute. Then it had another instruction you could use for subtracting memory from the A register. Whoa. Well, maybe this doesn't mean anything to you, but I knew exactly what these instructions meant, and it was the most exciting thing to discover ever."

Referencing the book, Intel started selling the 4004 microprocessor in 1971. By definition, I thought a microprocessor has to have registers, so did they just add functionality to the new 1975 microprocessor? Do you believe he was referencing the Intel 4040 microprocessor that came out in 1974? Also, does adding and subtracting memory allow arrays in RAM to be indexed in O(c) / constant time? Is that the significance or are there even more layers to this tale?

Thanks!

This was 1975. Microprocessors were not common knowledge. Wozniak had some experience with mainframe computers, but most likely hadn't seen a 4004 processor ever.

Reading the instruction set of the 6502 processor showed him that this wasn't a useless toy but a real computer. The original price for a 6502 was 25 dollars plus 10 dollars for the documentation (which you were encouraged to copy), compared to a 6800 for $300 including added chips that were required.

Wozniak's epiphany was realizing that you could take a $25 microprocessor and turn it into a real computer. Apple Inc. is now valued a bit over 700 billion dollars, a direct consequence of Wozniak's realisation, so this was a kind of important event.

Not that it has much to do with computer science, except that eventually it put computers into everyone's hands.


What is the best terminology for lower bound The term lower bound comes from math and applies to more than just complexity theory. What we see is that such and such is "a" lower bound. In complexity theory should this not be phrased as "the" lower bound, or better still the lowest bound. I can see where lower is a relative term, but the complexity of a given problem would seem to have exactly one minimum. Am I being overly semantic here? what I would like to say is that the lower (or lowest) bound on the complexity of SLL(k) testing is exponential.

http://www.slkpg.com/NPcoNP.html

If you want to talk about the complexity of a problem, just use "the complexity of the problem" and don't bring lower bounds into it.

GOOD: "The complexity of SLL(k) testing is exponential."

GOOD: "The complexity of SLL(k) testing is at least exponential."

GOOD: "There is an exponential lower bound on the complexity of SLL(k) testing."

GOOD: "The complexity of SLL(k) testing is in $\Omega(2^n)$."

BAD: "The lower bound of SLL(k) is exponential."  <--- Don't say this!  There's more than one valid lower bound.

BAD: ""The complexity is at least $O(2^n)$."  <--- Don't say this!  Big-O is an upper bound; it doesn't go with "at least".


Construct a computable function from non-computable funciton Let $f_1 $ and $f_2$ be two functions from $\mathbb{N} \rightarrow \mathbb{N}$.

$f_1$ is turing-computable while $f_2$ is not.

$h(i)$ is a function that returns $1$ when $f_1(i) = f_2(i)$ and $0$ else.

The challenge is to construct $f_1 $ and $f_2$ so that $h(i)$ is computable and additionally so that it is not.

My thought process is that for either scenario we have to use the computability and non-computability property and pass that forward to $h(i)$ but I am not sure how.

One thought I had to make $h(i)$ uncomputable is to define $f_2$ and $f_1$ on a for a small set of numbers and let $f_2$ be uncomputable on all other numbers. This way I cannot compute if $f_2 = f_1$ so I cannot compute wether $h(i)$ outputs $1$ or $0$.

But I dont know how to make $h(i)$ computable given the requirements that $f_2$ be uncomputable.

Can anyone nudge me in the right direction ?

There are many ways to do this, here is one example.

To make $h$ uncomputable, you can choose $f_1$ to be the constant $1$ function, and $f_2$ to be any non computable binary function, i.e. whose range is $\{0,1\}$. In that case $h=f_2$ is not computable. In fact, when $f_1,f_2$ are binary functions, $h$ is never computable (why?).

To make $h$ computable you can let $f_1$ be the constant $1$ function, and $f_2$ be any non computable function whose range is $\mathbb{N}\setminus\{1\}$. In that case $h$ is zero everywhere.


Would hypercomputation machines be capable of simulating/computing/programming everything? If uncomputable numbers existed, could this hypercomputation machines compute them? Could hypercomputation compute all types of uncomputable things? Even truly inconsistent things? Even things that cannot be described by any type of information (like a way of factorizing number 181 using classical mathematics, the mathematics we usually use, without changing nothing (without changing conditions, axioms, definitions...) of it, which it is clearly impossible)?

(I ask this because I was told by an important user in Physics Stack Exchange that this was possible for hypercomputation (if it existed), but later I spoke with other computer scientists and physicists and they told me that in no way this could happen. I can't contact the original scientist that told me that this was possible for hypercomputation, so maybe you can clear my doubts)

I think you have an important misunderstanding about what "uncomputable" means. It doesn't mean "doing something mathematically impossible", such as producing a non-trivial factorization of a prime number. There simply are no integers other than $1$ and $181$ that divide $181$ and it doesn't matter what method of computation you use, you will never find these non-existent factors because they just don't exist.  The factoring problem is not uncomputable: you can write a computer program that will correctly factorize any number that you give it. In the case of $181$, the program will just say, "The factors are $1$ and $181$ and that's all."

A problem is uncomputable if there is no Turing machine ("computer program") that can solve it. The standard example is what's called the halting problem: you have a computer program and you want to know if it will terminate, or get stuck in an infinite loop. Turing's famous result is that there is no Turing machine that will take the description of another Turing machine as input and correctly say either "this terminates" or "this loops forever".

Some models of hypercomputation can solve this problem. That is, the "hypercomputer" can decide whether given Turing machine will terminate. However, Turing's proof is very general and applies to any sufficiently powerful model of computation. So, although the hypercomputation model might be able to solve the halting problem for Turing machines, Turing's proof can be easily adapted to show that the hypercomputer cannot solve its own halting problem. That is, there is no hypercomputer program which takes as input the source code of another hypercomputer program and correctly determines whether that program will halt.

In summary, every sufficiently powerful model of computation has uncomputable problems, so no model of hypercomputation can compute everything.


If you increase the address space for an OS, does the Phys Mem used by the program increase? I am learning about the OS.

I know: that Address Space Size = # of pages x page size

So if I increase Address Space Size, then the number of pages increases:(not the page size). However, isn't the Virtual Page Number a one-for-one mapping to Physical Page Numbers(frames), so if the number of pages increases with the address space doesn't the frames and hence, the size of RAM used increase with address space increases?

Or, does bigger address space cause more physical frames so each frames physical memory size reduces as total memory is split among more frames.

No.  Due to the way virtual memory works, you can have more virtual pages than physical pages (frames).  Some virtual pages might not be mapped to any physical page.

It doesn't really make sense to talk about "if you increase the address space size, the number of pages increases".  It might be slightly more useful to think of it as "if you increase the number of pages, the address space size increases".

But really, in any given architecture, the address space size is often fixed and cannot be modified: the size of a virtual address is fixed and cannot be changed, and that determines the number of pages and thus the maximum size of the available virtual address space.


I need help in this regural expression exercises Write a regular expression for the language of words over $\{0,1,2\}$ satisfying the following requirements:

  The word has length at least 3.
  The last symbol is 2.
  The second to last symbol isn't 0.
  The combination of the last two symbols doesn’t appear anywhere else in the string.

In order to solve this exercise, we need to come up for regular expressions for two classes of words:

Words of the form $x00$, where $x \neq \epsilon$ and the only occurrence of $00$ is at the end.
Words of the form $x01$, where $x \neq \epsilon$ and the only occurrence of $01$ is at the end.

Let us start with the first class. For starters, $x$ must end with $1$ or $2$. So such words are of one of the forms $y100$ or $y200$, where $y$ doesn't contain $00$. Presumably you already know how to describe all words not containing $00$ using a regular expression.

For the second class, the only constraints on $x$ are that it is non-empty and doesn't contain $01$. If you don't like the "non-empty" constraint, you can use the following case distinction:

If $x = y0$ or $x = y2$, then the only constraint on $y$ is that it doesn't contain $01$.
If $x = y1$, then $y$ cannot end with $0$. It could be empty. If it ends with $2$, then $x$ is of the form $z21$. If it ends with $1$, then we're again in the same situation: the preceding symbol (if any) cannot be $0$. Continuing in this way, we see that either $x \in 1^+$ or $x$ is of the form $y2z$, where $y$ doesn't contain $01$ and $z = 1^n$ for some $n \geq 1$.

I'll let you figure out how to describe strings $y$ avoiding $01$ – this is very similar to the case of avoiding $00$.


Dynamic selection of cache replacement policy There are some different cache replacement policies could be implemented in CPU. As far as I know, ones have better hit ratio on specific type of code than others, but if that type changes (for example, loops and scan of long file), other replacement policy may become more effective. Did somebody try to investigate how to choose a specific replacement policy at runtime using some statistic information from previous CPU usage? What is this information? Do you know some articles or books about that?

Various processors have had instructions that affect cache operations. Some examples:

Clear cache line. This takes a memory address, allocates a cache line for it, and sets all data in the memory area contained in that cache line to values with no information content (usually all zeroes). This allows then storing data without reading the cache line.
Uncached read. This takes a memory address, reads the data, but doesn’t write it to the cache.
Prefetch: This takes a memory address and loads the data into cache without giving the results to the CPU. So when the data is needed later it’s already in the cache, no wait needed.
Streaming: Whenever data is read, the processor starts filling either the next or the previous cache line.