The $\text{k-key}$ problem Given an undirected graph, I define a structure called k-key as a path containing $k$ vertices which are connected to a simple cycle which contains $k$ vertices as well.

Here's the k-key problem: given an undirected graph $G$ and a number $k$, decide whether $G$ contains k $k$-key.

I want to show that the k-key problem is a NP-complete.

I want to make a reduction from the 'Undirected Hamiltonian Cycle' problem in which the input is a graph, and the problem is to decide whether it contains a Hamiltonian path. I already know that this problem is NP-complete. The input for the reduction would be an undirected graph $G$ and the output is $G'$ graph and $k$. Can you please help me understand what manipulation I should do to the original graph in order to show this reduction? And why should it work?

You want to find a way of creating $G'$ from $G$ such that $G'$ has a $k$-key iff $G$ has a Hamiltonian path.

If a graph $G$ has $k$ vertices and a simple path of length $k$, then what can we conclude about it having a Hamiltonian path?

I'm guessing the intention is that the vertices in the path must be different from the vertices in the cycle (otherwise every ham cycle graph would contain a $k$-key and vice versa).  So just think, suppose we knew that $G$ had a ham cycle starting from some vertex. Where would we tack on some vertices to create a $G'$ that had a $k$-key using $G$'s ham cycle?


Counting circuits with constraints Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one).
In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be computed only using circuits of size $\Omega(2^n/n)$, we use a counting argument: there are at most $O(2^{k \log k})$ circuits of size $k$, and $2^{2^n}$ such functions.
Suppose that I am interested in counting circuits of size $k$ that compute different functions. The "simple" counting argument won't work since it may be possible that two "syntactically" different circuits actually compute the same function.
In other words, I want to bound the size of the set: $$F =  \{ f: \{0,1\}^n \rightarrow \{0,1\} | f \text{ can be computed using a circuit of size }k \} $$
Then $|F| < $ the number of circuits of size $k$ (since any circuit computes one function), but how can I bound $|F|$ from below? (i.e. $ x <|F|$)

In order to bound the number of functions computed by circuits of size $k$, you have at least two options:

Construct a large number of circuits of size $k$, which by construction compute different functions.
Consider a natural probability distribution on circuits of size $k$, and estimate the probability that two random circuits compute the same function.

As an example, it is known that every function on $m$ variables can be computed by a circuit of size $O(2^m/m)$. By considering functions of the form $f_1(x_1,\ldots,x_m) \lor \cdots \lor f_{n/m}(x_{n-m+1},\ldots,x_n)$, this shows that there are at least $(2^{2^m})^{n/m}$ different functions computed by circuits of size $k = O(n2^m/m^2)$. In terms of $k$, the number of functions is roughly exponential in $k\log k$, for $m \gg \log n$.


What is the time complexity of this randomized algorithm? Let's start with a problem statement:

  given an array of length $n$ with numbers $1$ through $n$ (inclusive), consider the following steps:

  Select a random number $k$ in range $[1, n]$.
  Set $a[k] = q$.
  If there exists element $p$ in $a$ such that $p \ne q$, go to step 1, otherwise end.

So, basically we are going to randomly pick elements in the array and set them to some predefined value until every element in the array is set to this value. What is the time complexity of such algorithm? please explain your answer.

This is the coupon collector's problem. You can find its analysis in introductory textbooks on probability theory, among other sources.


Classification of the complement of a language $L = \{   \langle M \rangle \mid M \text{ accepts two strings of different lengths} \}$.

What is complement of this language?

my attempt:

the complement is: $M$ accepts no two strings of same length and this can be done by dovetailing different inputs on M but we can never say IT CANNOT ACCEPT TWO STRING OF SAME LENGTH and hence its NOT RECURSIVELY ENUMERABLE?

The complement of $L$ is:

$\bar{L} = \{\langle M \rangle \mid \text{ all strings accepted by $M$ have the same length} \}$

Your intuition that $\bar{L}$ is not recursively enumerable is correct, it is in fact complete for $\Pi^0_1$ by reduction from the emptiness problem. If you only need to prove that $\bar{L}$ is not in $\textsf{RE}$, it is sufficient to observe that $L$ is undecidable (reduction from the halting problem) but $\textsf{RE}$ (trivial).


Wang tile turing machine tile placement I've read numerous links on the fact that wang tiles are turing complete, and details about them (links at end).

However there is little talk of how to actually place the tiles.  One place i read mentioned (paraphrasing) "by placing tiles only where they are uniquely able to fit, you'll evaluate the program", but I'm finding there is actually ambiguity in what tiles can fit where.

Another link mentions that they personally place tiles in a spiral pattern, and when they hit a spot that needs a tile which doesn't exist (isn't valid) they backtrack and make a different choice earlier on.

Does anyone know if there's any reliable algorithm for placing the wang tiles when simulating turing machines with wang tiles?

I first believed that i could just go tile by tile, systematically matching empty spots to tiles that would fit there, but there are times when it is ambiguous which tile should go there.

Please let me know if more information is needed, such as a specific case when it's ambiguous, and I will provide it.  Thanks!

Links I've read include:
http://www.math.oregonstate.edu/~math_reu/proceedings/REU_Proceedings/Proceedings1989/2_Michie89.pdf

https://moyix.wordpress.com/2012/04/06/computing-with-tiles/

How to convert a Turing Machine program to a tiling using Wang Tiles?

http://grahamshawcross.com/2012/10/12/wang-tiles-and-turing-machines/

https://because0fbeauty.wordpress.com/2014/02/28/wang-tiles-1/

Any proof that the Wang tiling problem is undecidable by reduction from undecidability of the halting problem of Turing machines will contain instructions on how the Wang tiles simulate the operation of the machine, and indeed a proof that a tiling exists if and only if the machine doesn't halt.

There is more than one such proof. If you look at different proofs, you will see different reductions. There is absolutely no reason to expect that different reductions correspond to the same tiling placements. Indeed, there is no canonical way of converting Turing machines to tiling problems. Therefore there is no "reliable algorithm" for the problem; any specific proof should include such an algorithm that works for the specific proof.

I suggest you try to look up a technical paper with such a proof. Perhaps you can find a university library with Berger's original paper, or one of the later papers cited in the Wikipedia article.


graph theory proof or disproving I was requested to prove or disprove the following statement
if a graph is conncted does it necessarily means that E>(V-1)(V-2)/2
v  represents vertex and E the edges
I think I need to disprove it with overall disproval but how?

If you think it's false, the easiest way to disprove it would be to find a counterexample. That is, find a graph where $E \leq \frac{1}{2}(V-1)(V-2)$. Try some easy connected graphs (e.g. a straight-line path graph) and see if you can find a suitable graph.


Is there a theorem that says when an array of numbers can be searched faster than linearly? I'm familiar with binary search, but I'm interested in when a collection of numbers can be searched faster than checking them all one by one with any algorithm. Binary search requires sorting to work, which means some knowledge of the structure of the collection, but maybe there is something else.

In general, if you know nothing about the array, then searching linearly is the best you can do (a simple adversarial argument is enough to justify this).
However, if you know more about the structure of the array, there are plenty of things you can do.
For example, imagine the array has the following property: its elements are sorted increasingly up to a certain index $i$, and sorted decreasingly after that. Can you do faster than a linear search? Yes! You can still search elements in $O(\lg n)$.
What if I ask you to search in an array $A$ that is sorted increasingly except for $1$ element, which is out of place? (you don't know which element). You can still search in $O(\lg n)$, how :)?
What if the array $A$ holds the following property: when you divide it in chunks of size $\sqrt{n}$, say $A[0..\sqrt{n}-1], A[\sqrt{n}..2\sqrt{n}-1], \ldots, A[n-\sqrt{n}..n-1]$, then each of the chunks is sorted. Can you do faster than a linear search? Yes! if you do a binary search in each chunk, then you get complexity $O(\sqrt{n}\lg n)$.
What if you know the array $A$ has only two elements, $x$ and $y$, and they both appear the same number of times? Can you find an element in less than $n$ comparisons? Yes!
In general, there are many different kinds of informations you can have about an array that speed up search, and different forms of knowledge would have different impacts on how much you can speed up.


Making an algorithm that picks a unique random number in fixed set more efficient I have been working on a project that simulates an online bank. At this point, I'm implementing the code used to create user accounts. Each account will have a sortcode and account number, I have designed an algorithm that can generate a unique number in a range then check if it isn't in the list of account numbers and then add it to the list.
My Issue is that as the number of available account numbers decreases the more times the algorithm will need to generate new numbers which will create exponential overhead. especially when generating 6+ digit long account numbers.
My solution to this problem was after x number of attempts I would run a second operation that would find all missing account numbers in the list and return one at random. This would work but leaves me with the same problem.
Flowchart of my Algorithm

Country Code is part of the user registration and each country has it's own selection of sortcodes
so the hierarchy is:
CountryCode > Sortcode > Account Number
The only other solution That I can think of that would remove the overhead issue and give me a unique random number in a set, would be to pre-generate the set of numbers in random order and then pick off the top number until the set is empty. However, I'm not sure where this list would be kept when the application isn't running and I feel generating the numbers at runtime would be more suitable.
If you need any further information I will provide.

If you want to generate a list of $n$ random codes, from a space of at least $2n$ possible codes, then simple rejection sampling is easy and efficient: choose a random code, if it is a repeat throw it away and repeat, otherwise output; and repeat.  The running time will be $O(n)$.  This is the method you have rejected in the question.
If you want to generate a list of $n$ random codes, from a space of not much more than $n$ random codes, then use a Fisher-Yates shuffle.  Create a list of all random codes (0, 1, 2, 3, ...), then randomly permute it using a Fisher-Yates shuffle, then take the first $n$ codes in the resulting list.  The running time will be $O(n \log n)$.


Reduction to longest path from longest chain of tiles We have some tiles that each tile has 2 number written on it. We can rotate each tile in order to swap the position of numbers. We want to find the longest chain of tiles starting with a certain tile so that adjacent tiles have the same number on their common endpoint. If the tiles were

 7-4, 11-8, 11-11, 4-2, 7-5, 11-10, 10-5

the longest chain starting with tile 11-8 would be:

8-11, 11-11, 11-10, 10-5, 5-7, 7-4, 4-2

I tried to reduce this problem to the longest path problem:

Consider every tile as a vertex.
If two tiles have a common number in them they are adjacent.
create a sink vertex and connect it to every other vertices.

the resulting adjacency list of graph is:

7-4  : 4-2, 7-5, sink
11-8 : 11-11, 11-10, sink
11-11: 11-8, 11-10, sink
4-2  : 7-4, sink
7-5  : 7-4, sink
11-10: 11-8, 11-11, sink
10-5 : 11-10, 7-5, sink

Now for finding the longest chain starting vertex 11-8 you simply have to find the longest simple path form 11-8 to sink which is 8-11, 11-11, 11-10, 10-5, 5-7, 7-4, 4-2.

But I am being told that in order to say that this problem is reducible to longest path problem I have to prove it the other way around. It means I have to prove that every graph can be represented by some configuration of tiles. However I know that some graphs can't be represented by tiles for example the below graph couldn't be represented by any such tiles.

A-----B
|   / |
| /   |
C-----D

So technically my approach is wrong. But I wonder, I have shown that in general you have to solve the longest path problem to find the longest chain of such tiles, why isn't it enough to show that this problem can't be solved in polynomial time? Why is it necessary to show that all the graphs can be represented by a combination of such tiles?

But I wonder, I have shown that in general you have to solve the longest path problem to find the longest chain of such tiles

Not exactly, you have given a way of finding the longest chain of tiles (transform the tiles into a graph and solve longest path). There are many other possible approaches (you can try to transform it into a boolean formula and solve a SAT instance).... how do you know that none of them is easier? You could also use undecidable problems to solve your tile question (build a turing machine that halts iff the tiles have a solution of some size), it doesn't mean that your problem is undecidable.

Reductions work the other way around. I like to see an NP-hard problem as "a tool that may be used to solve any other NP problem". So  you need to show that your tile problem is one possible tool for solving longest path. That is, you are given a graph, and you need to describe a set of tiles with the good property (the tiles have a length-k solution iff the graph has a length-k path). This way, you know that your tile problem is a new possible tool for solving longest path, and, in turn, every other NP problem.

PS: there are also errors in the reduction you describe, beside the method problem discussed here: if the same integer appears in three different tiles (say, 4-2,4-7,4-9), then theses three nodes would form a valid path in the graph, but not a valid sequence of tiles. You'll find it easier to see a tile as an edge rather than a vertex


Show that $L$ and $\overline L$ cannot be both finite Let $L$ be any language on a nonempty alphabet. Show that $L$ and $\overline L$ cannot be both finite.

This is exercise 7 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz.
My attempt: $L$ is a subset of $\Sigma^*$, so it can be either finite or infinite. If $L$ is finite, then $\overline L$ is infinite. If $L$ is infinite, that is, $L = \Sigma^*$, then $\overline L = \Sigma^* - L = \Sigma^* - \Sigma^* = \emptyset$. Therefore, $L$ and $\overline L$ cannot be both finite.
Is it correct? I tried to write a direct proof. Thanks in advance.

If $L$ and $\overline{L}$ were both finite, then so would $\Sigma^* = L \cup \overline{L}$ be, which we know is false.
This is a qualitative statement. We can make it quantitative by considering densities. Let us say that a language is dense if for infinitely many $n$, it contains at least half the words of length $n$. It is easy to check that at least one of $L,\overline{L}$ is dense.


Given an undirected graph, find an orientation such that every vertex has out-degree at least 3 Given an undirected graph $G=(V,E)$, describe an algorithm that computes an orientation of $E$ such that each vertex has out-degree at least 3.

I know how to check if a vertex $v$ has at least $k$ edge-disjoint paths to any other vertex (using Ford-Fulkerson), so I thought I may use that for $k=3$.
Would appreciate your help :)

Given $G=(V,E)$, create a directed bipartite graph $H=(V+E, F)$ where there is an edge $(v,e) \in F$ iff $v \in V$ is an endpoint of $e \in E$. All these edges have capacity $1$.
Augment $H$ as follows: add two additional vertices $s$ and $t$; for each $v \in V$ add an edge $(s,v)$ with capacity $3$; for each $e \in E$ add the edge $(e, t)$ with capacity $1$.
Compute a maximum flow $\phi$ from $s$ to $t$ in the augmented version of $H$.
Your problem admits a solution if and only if the amount of flow $|\phi|$ is $3|V|$.
To see this, first observe that $3|V|$ is an upper bound on $|\phi|$. Then suppose that there exists a feasible orientation $\mathcal{O}$ and look at any partial orientation $\mathcal{O}'$ in which each vertex $v$ has exactly three outgoing edges.
A flow $\phi$ such that $|\phi|=3|V|$ is obtained by sending one unit of flow across each edge $(v,e) \in F$ such that $e$ is oriented away from $v$ in $\mathcal{O}'$, the flow across each edge $(s,v)$ is $3$, and the flow across $(e,t)$ is 1 if $e$ is oriented in $\mathcal{O}'$ and $0$ otherwise.
Suppose now that there is a flow $\phi$ such that $|\phi|=3|V|$. W.l.o.g., $\phi$ is integral. A feasible orientation is obtained by orienting each edge $e \in E$ away from the (at most one) endpoint $v$ of $e$ for which $\phi(v,e)=1$. If no such endpoint exists, then $e$ can be oriented arbitrarily. Notice that this procedure is constructive and immediately yields an algorithm for your problem.


Should I describe automata before describing grammar? Let's say I want to describe some new grammar formalism, which doesn't coincide with known grammar sets. Should I always previously describe corresponding equivalent automata and why?

In mathematics, the only thing that you absolutely must do is prove every theorem. Everything else is optional. In this case, you are asking whether every grammar formalism must be accompanied with a corresponding machine model. There is no such requirement, simply because not all grammar formalisms have a corresponding machine model which is natural. It is just a "nice to have" feature. More generally, the definition of a new class of languages is more convincing if the class can be defined in many seemingly different ways.

Another thing which you don't have to do but is "nice to have" is discussing closure properties of your class of languages, discussing the complexity of the classical decision problems for your class, and relating your class to other classes of languages. This is how people have studied language classes in the past, and so you would be expected to do it.


How is out-of-order instruction execution related to superscalar execution? How is out-of-order instruction execution related to superscalar execution?

How is data hazard detection and handling affected by superscalar execution?

Superscalar execution means that some instructions execute simultaneously.  Since the instructions under superscalar execution aren't executing in-order, supserscalar execution is one form of out-of-order execution.


How to solve T(n)=2T(√n)+log n with the master theorem? I'm trying to solve the recurrence $$T(n)=2T(\sqrt{n})+\log n$$ using the master theorem. Which case applies here?

Let us actually use the master theorem.

Define $S(n) = T(e^n)$ for all $n$. Then
  $$S(n) = T(e^n) = 2T(\sqrt{e^n}) + \log(e^n) = 2T(e^{n/2}) + n = 2S(n/2) + n$$
Now we can apply the second case of the master theorem to $S(n)$ for $a = b = 2$ and $f(n) = n$ to obtain
  $$ S(n) = \Theta(n\log n)$$
So for $n\gt0$,
  $$ T(n) = S(\log n) = \Theta(\log n \log\log n)$$


What is a "contradiction" in constructive logic? In Practical Foundations for Programming Languages, Robert Harper says

  If for a proposition to be true means to have a proof of it, what does it mean for a proposition to be false? It means that we have a refutation of it, showing that it cannot be proved. That is, a proposition is false if we can show that the assumption that it is true (has a proof) contradicts known facts.

But then, this begs the question- what is a contradiction in constructive/intuitionistic logic?

Is this meant in the sense of deriving $(\bot\text{ true})$ somehow? How would this happen in a sensible way? Would a judgment of the form $(A \supset \bot \text{ true})$ need to be introduced?

Alternatively, is it perhaps meant in the sense of the reader using their discretion to informally label something as contradictory? For example, interpreting $a = b$ and $a \neq b$ as conflicting propositions.

It is immaterial whether we speak about constructive or classical logic in this situation. If you read your questions again, you will see that they apply to boths kinds. The only difference that we need to take notice of is the presentation of negation $\lnot A$. It can be presented in several ways classically, but intuitionistically it is best to use it as an abbreviation for $A \Rightarrow \bot$ (which is precisely what Bob Harper is hinting at in the quoted paragraph). But let us not confuse negations and contradictions.

In both cases, a contradiction is a situation in which we have managed to prove falsity $\bot$. How could we derive $\bot$ in a sensible way? Well, from an inconsistent set of hypotheses, that wold be a sensible way to do it.

You have no discretion to "declare" a contradiction. You must prove that a given set of hypotheses is contradictory by deriving $\bot$. For instance, if $a = b$ and $\lnot (a = b)$ then we may use the fact that $\lnot (a = b)$ is an abbreviation for $(a = b) \Rightarrow \bot$ and conclude $\bot$ by modus ponens.


Is there really a $ O(1/n) $ algorithm? What kind of algorithm can have $O(1/n)$ complexity, where $n$ is a natural number?

Or, is there any algorithm that the time it takes decreases when the data input increases?

No algorithm really has an $O(1/n)$ running time, but that notation might be used informally for an algorithm who's running time is really $O(m/n)$ where $m$ is large and not expected to vary. Here's an example of such an algorithm:

Given an unordered set (e.g. a hash table) containing $n$ values from the integer range $0 \le x \lt m $ (for some $ m \in \Bbb{N}^* $). (Note that $ n \le m $, as a set can't contain any duplicate values.)

We want to find the minimum value in the set as efficiently as possible.

If $n$ is much smaller than $m$, then a linear scan through the values in the set is the most efficient solution ($O(n)$).

But if $n$ is greater than $\sqrt m$, it will often be more efficient to iterate over the potential values starting with $0$ and going up, testing each one to see if it's in the set. We can of course stop as soon as we find one, since it will be the smallest one.

The expected number of tests (assuming the data is randomly distributed over the range) is $m/n$. If we consider $m$ to be a constant (as in real-world applications it will often be determined by something we can't easily change like the size of our integer data type), this seems like it would be $O(1/n)$ (with a large constant factor of $m$). And that does give an accurate description of how the performance of the algorithm changes as $n$ goes from $ \sqrt m $ towards $m$ while $m$ remains the same.

But the notation is not strictly correct. Asymptotic notation is intended to describe behavior as its variable terms go towards infinity. If an $O(1 / n)$ algorithm could run for $n$ approaching infinity, its running time would tend towards zero, but the $1 / n$ term would be dominated by constant terms (and so $O(1)$ would be a better description of its performance). For an algorithm that only makes sense on a bounded $n$, it's not correct to use asymptotic notation. For a strict asymptotic analysis, you need to consider $m$ a variable too so that both $m$ and $n$ can increase towards infinity.

I suspect that if you ever see $O(1/n)$, it's being used as an informal shorthand for $O(m/n)$.


Can you apply the induction hypothesis to its outcome? Assume a well-founded relation $<$ over a set $S$ and a property $P$ on $S$ such that:

$P$ holds for all minimal elements of $S$.
For every $b \in P$ and $a < b$ we have: if $P(a)$ then there exists $c < b$ such that $P(c) \Rightarrow P(b)$.

Question: does it follow that $P(c)$ holds for all $c \in S$?

As stated, the reasoning does not make much sense to me.

You claim that, in your specific case, you have

$a < b \wedge P(a) \Longrightarrow \exists c < b$
$P(a) \wedge P(b) \Longrightarrow P(b)$

but these properties are trivial tautologies -- they tell nothing about your specific case.

In the first one, if $a < b$, we already know $\exists c<b$. We don't even need $P(a)$.

The second one is an instance of the tautology $p \land q \implies q$.

I'm not sure how these two properties help in the induction proof at all.


Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows.

Hanoi(n, src, dst, tmp):
  if n > 0
    hanoi(n-1, src, dst, tmp)
    move disk n from src to dst
    hanoi(n-1, tmp, dst, src)

And iteratively,

  If n is even, swap pegs 1 and 2.  At the ith step, make the only legal
  move that avoids peg i mod 3.  If there is no legal move, then all
  disks are on peg i mod 3, and the puzzle is solved.

 hanoi(n, s, t, d)
  pegs[s = [1,2,..,n], t, d]
  if n is even
    swap pegs[1], pegs[2]
  i <- 1
  while(pegs[d].length < n.length)
    avoid <- i mod 3
    if the top of pegs[(avoid + 1) mod 3] > the top of pegs[(avoid + 2) mod 3]
      move the top of pegs[(avoid + 1) mod 3] to pegs[(avoid + 2) mod 3]
    else
      move the top of pegs[(avoid + 2) mod 3] to pegs[(avoid + 1) mod 3]
    i++

I'm having a hard time figuring out how to put this into mathematical expressions or a recurrence-relation which I can then perform induction on to show their equivalence.

My searching has only brought me problems that deal with the complexity or correctness of algorithms, I'm interested in showing that every $i$th move the performed are identical.

Let's start with reformulating the two solutions, following Wikipedia. We use A for the source peg, B for the auxiliary peg, and C for the destination peg.

Recursive algorithm

If $n > 1$, recursively move $n-1$ discs from A to B.
Move the $n$th disk from A to C.
If $n > 1$, recursively move $n-1$ discs from B to C.

Iterative algorithm

If $n$ is even, execute repeatedly until done:

Make a legal move between A and B.
Make a legal move between A and C.
Make a legal move between B and C.

If $n$ is odd, execute repeatedly until done:

Make a legal move between A and C.
Make a legal move between A and B.
Make a legal move between B and C.

(We terminate the algorithms whenever there is no legal move.)

We will prove that both algorithms coincide, using the fact that the recursive algorithm makes exactly $2^n-1$ moves, which can easily be proved by induction. The base case is $n = 1$. In this case, the recursive algorithm moves the disk from A to C, and this is also what the iterative algorithm does.

Suppose now that we have proved the claim for $n$. We will prove it for $n+1$. There are two cases to consider, according to the parity of $n$. Suppose first that $n$ is odd.

The first step in the recursive algorithm is to move $n$ discs from A to B. We know that this is the same as running $2^n-1$ steps of the iterative algorithm for odd many disks, with B and C switched. We observe that upon switching B and C, we exactly obtain the iterative algorithm for even many disks. Therefore the first $2^n-1$ moves made by the iterative algorithm coincide with what the recursive algorithm does (this is because at any step there is a move involving one of the first $n$ disks).

Since $2^n-1 \equiv (-1)^n-1 \equiv 1 \pmod{3}$, after executing $2^n-1$ steps, the next step in the iterative algorithm is to make a legal move between A and C, which is exactly what the recursive algorithm does. We can now rephrase the remaining operation of the iterative algorithm as repeatedly executing the following moves:

Make a legal move between B and C.
Make a legal move between A and B.
Make a legal move between A and C.

This is exactly what the iterative algorithm for odd many disks looks like after switching A and B. Therefore just as before, the following $2^n-1$ steps of both algorithms coincide. The same calculation as before shows that the next move to be considered in the iterative algorithm is the one involving A and B, but there are no disks on either of these pegs, so the iterative algorithm stops. This completes the proof for odd $n$.

The proof for even $n$ is very similar. The first $2^n-1$ moves coincide since switching B and C switches the two versions of the iterative algorithm. This time $2^n-1 \equiv 0 \pmod{3}$, so the next move to be considered by the iterative algorithm involves A and C, matching the recursive algorithm. We can rephrase the operation of the iterative algorithm henceforward as repeatedly executing

Make a legal move between A and B.
Make a legal move between B and C.
Make a legal move between A and C.

This is the same as the iterative algorithm for even number of disks with A and B switched, so the following $2^n-1$ moves coincide. The next move to be considered again involves A and B, which is impossible. This completes the proof.


Interesting problems that can be solved with algorithms I need to write a blog post on a problem that can be solved algorithmically. I need to do two things:

1) I need to decide what the naive brute force method would be and touch on it's time and Space complexities.

2) I need to come up with a more elegant/ideal method to solve the problem, then discuss tradeoffs with the ideal method's time and space big O

Does anyone have ideas for an interesting topic I can cover? I'm not looking for the answers, just the topic to cover

Here is an example of something I could write about: https://medium.com/@hannahsquier/two-algorithms-for-solving-vigneres-cipher-in-ruby-77bf0b37507a#.go43z5vas

Depending on the level of sophistication of your intended audience, a simple canonical example is testing whether an input number $n$ is prime.

A brute force approach is to test, for all $d$ in the range $2,\dotsc n-1$ whether $d$ divides $n$. If you find a $d$ that divides $n$ you can stop and assert that $n$ isn't prime; if you don't find any such $d$, you can assert that $n$ is prime. That'll take about $n$ divisions if $n$ is prime.

An improvement is to try just those $d\le\sqrt{n}$ (rounding up), since it's easy to see that if $n$ has any divisors, there must be one in that range. This is a big improvement, since it reduces the number of divisions from $n$ to $\sqrt{n}$, more or less.

If you want to expand this, there are even faster ways to test for primality and if your audience is sophisticated enough, you might want to try one or more of them.


Why can't I run a mac program natively on windows? Basically, I believe that if you have something like a .dmg file the OS opens it with a certain program which takes the code behind it and does things to it. So why couldn't you then take the program that runs the .dmg file on Mac and put it on window to run the program? I know I'm probably missing some key component here that makes me wrong but I have no idea what; I'm a bit of a noob to so take it easy on me.

Think of the .dmg file as a book of short stories.

Windows and Mac OS X have different formats of books, so the gesture to open one is a bit different (think of pages turned from left to right or right to left). Less metaphorically, a .dmg file packs a bunch of files, and the format in which these files are packed isn't one that Windows supports natively. However it would be easy to write a program to unpack .dmg files on Windows, and I'm sure someone has done so.

Ok, now you have the book open and can see the pages. That doesn't necessarily mean you can read it, though. Let's say you speak English and only English… but the book is in Turkish. You aren't going to be able to understand a word of it.

A computer program contains a bunch of elementary instructions. The instruction set is like the script that the book is written in. The instruction set is determined by the type of processor that powers the computer. Modern Macs and Windows PCs have the same type of processor (one of the two x86 families, either the 32-bit one or the 64-bit one). So that step is fine — you can make out the individual letters. However, that's not enough!

Some instructions rely only on the processor: instructions like “read the value at this memory location” or “add these two numbers” or “jump to this location in the program”. However, every time the program wants to interact with something else (access a disk file, read user input, display something, communicate over the network, etc.), the program makes a call to the operating system. And two completely different operating systems, such as Windows and Mac OS X, have completely different APIs — they offer completely different system calls. (Note that the metaphor breaks down somewhat here: the problem isn't that the arrangement of instructions has to be different, but that a few very important instructions have radically different effects.)

There's even another layer of differences: Windows and OSX even have different executable file formats (PE vs Mach-O). The executable format determines how code and data are arranged in the file and how things like dependencies on libraries are represented. Making Windows understand OSX's file format would require some work, but making Windows understand OSX's system calls would be a Herculean task.

You can't read the book because it's in Turkish. You could learn Turkish, but it would take years of effort. Similarly, making Windows able to run OSX programs would take a huge amount of programming effort.

In fact, it's simpler to simulate a processor with its peripherals, by implementing all of its instructions, than it is to simulate an operating system by implementing all of its system calls. This is called a virtual machine. You can run an operating system on an emulated machine that is in fact provided by a program running under another operating system. For example, you can run OSX on an x86 CPU emulated by Vmware which is running as a Windows application. (In the specific case of OSX, this is difficult, but not for technical reasons, rather because Apple makes it difficult for commercial reasons.)


Unrolling closures into SAT boolean formula I need to verify some assertions about the minimalist Turing-complete language Jot.

Many of the assertions I want to investigate are semi-deciable (co-recursively enumerable). So far it's been fairly straightforward to literally enumerate every Jot program via its Goedel number and testing the assertion's complement by running a Jot program with a given space/time bound.

This works great for small programs (< ~40 bits) and has allowed me to find the shortest known representations of several standard simple functions from lambda calculus.

SUCC = J(18400)
CHURCH_0 = J(154)
CHURCH_1 = J(0)
CHURCH_2 = J(588826)
IS_ZERO = J(5)
MUL = J(280)
EXP = J(18108)
S = J(8)
K = J(4)
AND_2 = J(16)
AND_3 = J(139248)
OR_2 = J(9050)

However, this is particularly inefficient for larger functions and I'd like to speed up searches using a SAT solver. To do this requires unrolling the recursion of a Jot program J(n) to a predefined hard cut-off depth as a boolean formula.

Technically the formula isn't of polynomial length, but is still practically useful due to the small constants in program length and an already known existing polynomial number of beta reductions in an equivalent (but verbose) implementation of the target J(n).

I'm used to encoding problems in SAT formulae, however the new issue for me is understanding how to encode closures (nested functions) in an efficient manner.

None of the standard tools for bounded model checking that I know of allow nested anonymous functions, so I haven't been able to study any existing encoding methods. I would greatly appreciate any hints about how to encode these closures.

Here's the Jot interpreter written in Python which I'm trying to unroll into a boolean formula:

def S(x): return lambda y: lambda z: x(z)(y(z))
def K(x): return lambda y: x
def X(x): return x(S)(K)
def B(x): return lambda y: lambda z: x(y(z))
def I(x): return x
def J(n): return (B if n & 1 else X)(J(n >> 1)) if n else I

It's important to remember that SAT can only encode problems that are in $NP$, unless you use more than polynomial-length formulas. I'm not 100% sure, but I'm doubting your problem is in $NP$.

Consider the following function:

$F = \lambda x\ y \ldotp x x (\lambda y . y y)$

Now consider evaluating $F F (\lambda z \ldotp z)$.

This clearly runs forever, but we can also see that the argument given as $y$ will grow exponentially with the number of $\beta$ reductions you do.

Now, some things that aren't clear from the question:

  non-deterministically represented candidate program

What does this mean? Is the program non-deterministic? Or its representation? What even is a non-deterministic representation?

  static once created and have a small number of predefined variables within each combinator

Again, what does this mean? My example doesn't seem to fit this, but if whatever you're dealing with us Turing Complete, my gut says your problem is likely to be $EXPTIME$-hard.


BSS-model Computational complexity of finding the roots of a polyomial I'm currently dealing with a problem for which I could show that an exact algorithm would imply a general algorithm for finding the real (but not complex) roots of an arbitrary univariate polynomial with real coefficients.

Now, what exactly are the implications for my problem?

It is well-known that there is no formula that describes the roots of a polynomial of degree $\geq 5$ and, as far as I know, there is no general algorithm that computes the roots exactly. But are there results stating that the problem is computationally intractable in general? Or is it a common assumption? My question is not aiming at existence results or approximation algorithms but at the computational complexity of the problem and possible implications for my problem.

Note: My algorithm works in the Blum-Shub-Smale model, so the possibly infinite representations of the solutions don't bother me.

It's not too hard to find the real roots of a univariate polynomial, for example by using Sturm's theorem which allows you to easily identify the number of sign changes of a real-valued polynomial between two given bounds.

I believe it's not too hard to show that this technique, coupled with a simple divide-and-conquer technique or Newton's method and an elementary bound on the absolute value of the largest root as a function of the coefficients, gives a polynomial time algorithm for finding the roots of a polynomial, in the time of the degree $n$ and the desired precision $p$ (in digits).

For more information see the wikipedia article or this mathoverflow question.

Edit: The question was clarified to ask about exact solutions in the Blum-Shub-Smale model. In this situation, it is already impossible to get square roots, in particular to get exact solutions to the equation
$$ X^2 - 2 = 0$$

This result (and a much more general one) is proven in this paper by Calvert, Kramer and Miller.


Determine the move in which a LOGO turtle crosses a point that it has already visited I was given the following problem in an test (at codility.com)

  A turtle starts at (0, 0) on a cartesian graph. We have a non-empty
  zero-indexed "moves" list that contains positive integer numbers. Each number
  represents the distance moved. The first number is the distance north,
  the second is the distance east, the third is the distance south, the
  fourth is the distance west, and so forth. Therefore
  the directions cycle every four moves.

  Find an algorithm that gives the move number that makes the turtle
  cross a point that it has already visited before.

  The move number is the index of the "moves" list.

  This algorithm should have O(n) time complexity and O(1) space complexity.

  Example:

  If given this move list: [1, 3, 2, 5, 4, 4, 6, 3, 2]

  The move number answer is then 6. (It's the 7th move).

  Draw it on a graph, the turtle will go:

  (0,0) -> (0,1) -> (3,1) -> (3,-1) -> (-2,-1) -> (-2,3) -> (2,3) ->
  (2,-3)

  At this 6 move number (7th move) it will meet (2,1) which is a point
  that the turtle has already crossed.

I have been struggling with for quite a time, because I intuitively think there's no way to meet both space and time complexity requirements, unless there's some hidden structural property in the problem I'm not noticing. For example, if the path does not cross itself it forms an spiral-like curve, and therefore each north move must be greater than the previous south move, and viceversa. The same applies to the east and west moves. Therefore, not meeting this property implies the curve will eventually cross itself, but gives no indication on which move does it.

My main problem is that I've not been able to identify the type or algorithmic problem this problem relates (e.g. sorting)

Hint: Find some constant $C$ such that if the turtle ever crosses its own path, then it must hit one of the last $C$ segments in the path. (I think that $C=5$ should work.)


What determines valid and invalid turing machines? According to my understanding, a Turing machine that's valid has to have finite steps to finish a certain step. If this is right, what else determines the validity of a turing machine?

If you are referring to what I think you are referring to then your understanding seems correct.

A Turing machine has a precise definition: It is a tuple ... see for example
http://en.wikipedia.org/wiki/Turing_machine#Formal_definition

Any system with the same components and conditions as described by the definition is indeed a Turing machine.  Anything else (which may at first glance appear to be a Turing machine) is not a Turing machine.

This distinction is to weed out some wrong intuitions.
Here is an example adopted from:
https://stackoverflow.com/questions/2435607/why-is-this-an-invalid-turing-machine

For example (given a polynomial P as input):

Start counter at 0
   Start Zero at False
   while(not Zero) {
      eval P(counter)
      if ^^ is 0 set Zero to True
   }
   Return True

Can be computed by a Turing machine (i.e. describes a valid Turing machine) while

Start list at []
   Start counter at 0
   while(true){
      add eval P(counter) to list
   }
   if any element of list is 0 return true else return false

Describes an invalid Turing machine, i.e. the code does not correspond to a Turing mahcine.

Well ^^ is all I can come up with.  Maybe it will help.


Which m numbers in the range [1, k] have sum equal to n Given the values of $n, k, m$, you have to check if there are $m$ distinct numbers in the range from 1 to $k$ have the sum $n$ or not ?

$n$ represents the required sum
$k$ represents numbers range(1,2,3,... to k).
$m$ is the number of elements in the range from 1 to $k$ that has the sum $n$.

Example: n = 12, k = 8, m = 3 ==> there are 3 numbers in the range from 1 to 8 that have the sum 12 which are 2,3,7.

The problem is taken from hackerrank and called bonetrousle.

Hint:

What is the smallest number that can be represented as the sum of $m$ distinct integers from $1$ to $k$?
What is the largest number that can be represented as the sum of $m$ distinct integers from $1$ to $k$?
Can all numbers in between be so represented?


Computation time of a Binom matlab (or C) routine I am trying to write a Matlab (or C) routine for the exact probability F of observing K or more successes when a success probability P is expected ($\sum_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k}$).
I am trying to figure out the following:

  I need to know, if it shoud work for large numbers:
  i.e. K=501000, N=10^6, P=0.5
  Is there a way to calculate how long the computation takes?

Maybe it is possible to perform a computer routine that calculates an approximation? Like Poisson Probability

If you can avoid it, you don't want to compute sums like that at all.

If you compute terms like $p^k$ directly, you'll get big errors due to floating-point precision (because your result will be almost zero).

If you haven't seen it, one common way to handle small probabilities is to apply the logarithm trick:

$\qquad \displaystyle p^k(1-p)^{n-k}\ \leadsto\ k \cdot \log p + (n-k) \cdot \log(1-p)$.
If possible, apply well-known closed forms for sums to eliminate them entirely. Computing that is less problematic, both in terms of numerical issues and running time.
Failing that, find an approximation that you can tune to the required precision.

And also:

Computing running times with an algorithm is not computable in general. You will have to apply algorithm analysis yourself. After implementing an actual algorithm, that is. See a good textbook or our reference questions for starters.


About the Max-Cut SDP The Max-Cut optimization problem on a graph $G=(V,E)$ can be written as the question of wanting to maximize the function $\frac{1}{4} \sum_{(i,j) \in E } (x_i -x_j)^2$ under the constraint $x_i^2 = 1, x_i \in \mathbb{R}, \forall i \in V$.

Now the usual SDP relaxation is to lift the $x_i$s to vectors $\vec{x_i} \in \mathbb{R}^d$ for some $d$ with the new objective function to be maximized being $\frac{1}{4} \sum_{(i,j) \in E } \vert \vert \vec{x_i} - \vec{x_j} \vert\vert _2 ^2$ under the new constraint being $\vert \vert \vec{x_i} \vert \vert _2 ^2 = 1$.

I wonder why in the usual SDP relaxation we use the $l_2$ norm. Is that just convenience or is there some optimality argument about it? Like one could have as well for any $4$ integers $p,q,r,s$ thought of,

maximizing $\sum_{(i,j) \in E } \vert \vert \vec{x_i} - \vec{x_j} \vert\vert _p ^q$ under the constraint being $\vert \vert \vec{x_i} \vert \vert _r ^s = 1$.

I believe this optimization problem would still give the max-cut?

Beyond the fact that such an optimization would probably be very hard to do, is there any fundamental reason why we do not do such a formulation of optimizing the $q^{th}$ power of the $p-norm$ under a constraint fixing the $s^{th}$-power of the $r-norm$?

(will there emerge constraints on the integers $p,q,r,s$ for this to work?)

For example,

Even before the relaxation one could have as well written the optimization question as wanting to optimize $\frac{1}{16} \sum_{(i,j) \in E } (x_i -x_j)^4$ under the constraint $x_i^2 = 1, x_i \in \mathbb{R}, \forall i \in V$. I believe this would still give the same max-cut!

And then one might have thought of its "natural" SDP relaxation to be,

maximizing $\frac{1}{16} \sum_{(i,j) \in E } \vert \vert \vec{x_i} - \vec{x_j} \vert\vert _4 ^4$ under the constraint being $\vert \vert \vec{x_i} \vert \vert _2 ^2 = 1$.

Do we know that say the above SDP won't beat the $0.878$ factor?

An SDP relaxation is not an arbitrary optimization problem; rather, it consists of optimizing a linear function over semidefinite and linear constraints. One general formulation of SDP is
$$
\begin{align*}
&\max \sum_{ij} c_{ij} x_{ij} \\
s.t. \;\;& X \succeq 0 \\
& A \mathbf{x} = \mathbf{b}
\end{align*}
$$
Here $X$ is the matrix whose entries are $x_{ij}$, and $\mathbf{x}$ is a vector whose entries are $x_{ij}$ (in some arbitrary order).

Standard accounts on semidefinite programming should explain why the SDP relaxation that you describe can indeed be formulated in this form. In short, the idea is that $x_{ij}$ is going to represent the inner product $\langle \vec{x}_i, \vec{x}_j \rangle$. The fact that $X$ is positive semidefinite is equivalent to the existence of such vectors $\vec{x}_i$. The objective function $\sum_{(i,j) \in E} \|\vec{x}_i - \vec{x}_j\|^2$ can be written as a linear combination of the $x_{ij}$, and the constraints $\|\vec{x}_i\| = 1$ can be written as linear constraints on the $x_{ij}$.

Why do we care about semidefinite programs? Because we know that they can be solved (approximately, but arbitrarily well) in polynomial time. This is not true for an arbitrary optimization problem.

There is some evidence that the Goemans–Williamson constant $0.878$ is best-possible for polynomial time algorithms. Namely, this is the case if Khot's Unique Games Conjecture holds. Under this conjecture, Raghavendra showed that SDP relaxations are optimal for a wide class of problems (constraint satisfaction problems).


Whether same output is obtained for the two queries Consider the following SQL Queries executed on the relation Employee:

Employee (Eid, Ename, sal)

Eid is the primary key
Queries:

S1:SELECT count (*) FROM Employee;
S2: SELECT count (Eid) FROM Employee;

Will these queries return the same result or different results?
According to me, these queries should return same values.
But my solution manual claims that the values returned should be different. It says that S1 will also include results where Eid field is empty.
But according to me, the primary key field can never be empty. So, there will never be a case where Eid field will be empty. As this field will never be empty, the output of S1 and S2 should be equal.
Can anyone please tell me whether I am correct? If not, please tell me what I am doing wrong.
Thanks in advance!

where Eid field is empty.

What do you mean by "empty"? Perhaps you mean 'null'?

What words exactly does your "solution manual" use? "empty" or "null"?

If the Eid field is CHAR there could easily be a row with Eid "empty" -- that is: zero length, or containing only space characters. count(*) and count(Eid) return the same value in that case.

If the Eid field is NULLABLE there could easily be a row with Eid null. count(*) will include that row, whereas count(Eid) will not.

Usually fields in keys are expected to be NOT NULL. Some vendors' implementations of the SQL standard insist on NOT NULL. But some don't. It is good practice to make key fields NOT NULL. Presumably your manual is getting you to think about why.


Glue-concatenation v.s concatenation I wanted to give the following as a homework question, but my first few attempts to solve it failed, so now I'm just curios for a solution:

For two words $x,y\in \Sigma^*$ and for a letter $\sigma\in \Sigma$ we define the glue-concatenation of $x\sigma$ and $\sigma y$ to be $g(x\sigma,\sigma y)=x\sigma y$, and for words $w,z$ such that the last letter in $w$ differs from the first letter in $z$, the glue concatenation is undefined.

For languages $A,B\subseteq \Sigma^*$, we lift the glue operator such that $g(A,B)=\{g(w\sigma,\sigma z):w\sigma \in A, \sigma z\in B\}$ (note that we only consider words for which $g$ is defined).

  The question: is it always true that $|g(A,B)|\le |A\cdot B|$?

Observe that trying to prove that if $g(x,y)\neq g(w,z)$ then $xy\neq wz$ will fail, since for example, $g(a,abb)\neq g(aab,b)$, but $a\cdot abb=aab\cdot b$.

The statement does not hold.

For $A = \{a, aaba\}$ and $B = \{a, abaa\}$ we find

$|g(A,B) = \{a, abaa, aaba, aababaa\}| = 4 > 3 = |\{aa, aabaa, aabaabaa\}|  = |A\cdot B|$.

As a sidenote, I'd say this could actually be a worthwile exercise task, once students are reasonably experienced with standard proof techniques. After all, you only really learn how to attack such problems from practising.


Deletion in min/max heaps I think I'm confused about deletion in heaps, and since I have an exam today, I'm looking for your help to correct me.

I will post photos since it will makes it a bit more clear.

Note(forget about deleting the root)

What I understand is that , heaps only deletes the root element or the top. So, I made 2 solutions and I'm kindly asking which solution is the correct one.

Q:the heapness will be violated, I will have to replace it by the rightmost element bottom down right? (32)

There's no need to bubble-up the element all the way to the root. You can replace the item to be removed with the last element in the heap. If that new element is less than its parent, then bubble it up. If it's greater than its children, bubble it down.

I implemented this in my DevSource article, A Priority Queue Implementation in C#. Full source is available at http://www.mischel.com/pubs/priqueue.zip.

See my Stack Overflow answer about this at https://stackoverflow.com/a/8706363/56778


Temporal alignment of two time series I have two series of tuples

$$
A = \{(x_0,t_{01},t_{02}),(x_1,t_{11},t_{12}),\ldots,(x_n,t_{n1},t_{n2})\} \\
B = \{(y_0,tt_{01},tt_{02}),(y_1,tt_{11},tt_{12}),\ldots,(y_m,tt_{m1},tt_{m2})\}
$$

where $m \neq n$ and $t$ and $tt$ are both time observations. $t_{i1}$ and $tt_{j1}$ are both the start of some epoch for arbitrary $i$ and $j$. $t_{i2}$ and $tt_{j2}$ are both the end of some epoch for arbitrary $i$ and $j$. $x_i$ and $y_j$ are the observations of a sensor during those epochs.

In my case $t_{i1}$ and $tt_{j1}$ are not guaranteed to match, nor are $t_{i2}$ and $tt_{j2}$. However, they do represent time epochs that overlap with each other. For instance if $t_{11}$ and $t_{12}$ stretches from 2015-01-02 to 2015-01-03 then $tt_{11}$ and $tt_{12}$ might go from 2015-01-01 to 2015-01-04.

What I'm hoping to do is align the observations $x_i$ and $y_j$ temporally into a single sequence that might look like

$$ C = \{(x_0,y_0,ttt_{01},ttt_{02}),(x_1,y_1,ttt_{11},ttt_{12}),\ldots,(x_p,y_p,ttt_{p1},ttt_{p2})\}, $$

where $p$ is the last observation in the sequence and the time observations $ttt_{k1}$ and $ttt_{k2}$ are the start and end of some epoch non-overlapping with later observations of $ttt_{\mathit{whatever}}$.

I've already looked into some of the papers available on the subject and all of the work I've seen deals with image analysis, audio overlap, kernels, and others that seem a bit off focus than what I'm looking for. Is there more basic theory available that deal specifically with the situation I'm describing here? Or is my case just a specific one covered by some of the papers that I've been reading on?

OK.  So the problem is as follows (with different notation):

Inputs: disjoint intervals $I_1,\dots,I_k$; disjoint intervals $J_1,\dots,J_m$
Output: disjoint intervals $K_1,\dots,K_n$ that are a "refinement" of the $I,J$-intervals

The $I$-intervals are not necessarily disjoint from the $J$-intervals.  We want the $K$-intervals to have the following property: if $x,y$ are in the same $K$-interval, then $x,y$ are in the same $I$-interval and $x,y$ are in the same $J$-interval.

This can be solved.  Basically, you use a 'merge' procedure vaguely akin go the merge operation from Mergesort, but adjusted to deal with intervals.    I'll assume the $I$-intervals are in sorted order, and the $J$-intervals are in sorted order (so $I_1$ is the leftmost/smallest interval of the $I$-intervals, etc.).

The algorithm considers how $I_1$ compares to $J_1$:

If $I_1$ is wholly to the left of $J_1$ (they don't overlap, and $I_1$ is smaller than $J_1$), then we output $I_1$, delete $I_1$ from the $I$-list, and continue.
If $I_1$ is wholly to the right of $J_1$ (they don't overlap, and $I_1$ is larger than $J_1$), then we output $J_1$, delete $J_1$ from the $J$-list, and continue.
If $I_1,J_1$ overlap and $I_1$ is contained in $J_1$, then do the following: if $I_1$ is the interval $[a,b]$ and $J_1$ is the interval $[c,d]$ (so $c<a<b<d$), output the interval $[c,a]$, output the interval $[a,b]$, delete $I_1$ from the $I$-list, delete $J_1$ from the $J$-list, and insert $[b,d]$ to the front of the $J$-list.
If $I_1,J_1$ overlap and $J_1$ is contained in $I_1$, do the symmetrical equivalent of the previous case.
If $I_1,J_1$ overlap but neither is wholly contained in the other, and the left endpoint of $I_1$ is to the left of the left endpoint of $J_1$, do the following: if $I_1$ is the interval $[a,b]$ and $J_1$ is the interval $[c,d]$ (so that $a<c<b<d$), output the interval $[a,c]$, output the interval $[c,b]$, delete $I_1$ from the $I$-list, delete $J_1$ from the $J$-list, and insert $[b,d]$ to the front of the $J$-list.
If $I_1,J_1$ overlap but neither is wholly contained in the other, and the left endpoint of $J_1$ is to the left of the left endpoint of $I_1$,  do the symmetrical equivalent of the previous case.

As you can see, once you've sorted the intervals, this can be handled by a linear scan using a case analysis.  The total number of intervals in the output will be at most twice the total number of intervals in the input (i.e., $n \le 2(k+m)$).


Computation Complexity of stream algorithm I want to analyze a clustering algorithm that clusters data stream.
Since the stream can be unbounded, I cannot write O(N^2), or explicitly denote the size of the stream. How can I use the arrival rate of the data for the computation complexity? Do you have any other idea for correct analysis of stream computation (for clustering problems)?

Thank's

One standard way to measure the running time of streaming algorithms is to count the amount of time taken per item that the algorithm processes.  For instance, one algorithm might take $O(1)$ time per item.

Also it is common to analyze the memory usage (space complexity) of these algorithms, as in many practical situations memory can be a limiting factor.  That is straightforward to measure.  Usually the space complexity is measured not as a function of the number of elements seen, but rather as a function of something else -- e.g., the accuracy of the answer, or the number of distinct items in the input stream, or something else that is appropriate to the application and that makes it possible to do analysis.

I suggest you read about streaming algorithms.  There's lots of work on those topics and those fields certainly measure the running time of their algorithms. See, e.g., https://en.wikipedia.org/wiki/Streaming_algorithm and textbooks on the subject.


DFA that accepts strings with last character being repeated at least 1 time before I'm trying to design a DFA in a 4 digit language, for example L(a,b,c,d) or L(1,2,3,4) that accepts strings with the last character being already repeated before.

Everyway im trying, i get so many transitions im literally lost in them...

So, for example, abbdb is accepted (because b is showed again at least 1 time) but abc is rejected since c (last char) never shows up more than 1 time.

I managed to make it work for a language with 2 DIGIT:
For example:

Which accepts for example aa or ababa but can't do for 4 DIGIT language.

I would write out a description of this machine rather than drawing it.

States ($Q$): the states of this machine are five-tuples $(\alpha, \beta, \gamma, \delta, \sigma)$: alpha, beta, gamma, and delta are in $\{0,1\}$ and record whether or not the corresponding symbol has been seen before, while sigma is in $\Sigma \cup \textrm{Nothing}$ and indicates the last symbol read.
Alphabet ($\Sigma$): the alphabet, as you specified, is $\{a,b,c,d\}$.
Start ($q_0$): the starting state is $(0,0,0,0,\textrm{Nothing})$. In other words, we've seen no symbols yet, and the previous symbol read was nothing.
Final States ($F$): a state is final if the last symbol read was seen before. For example, the state $(1,\#,\#,\#,a)$ is final, regardless of what those $\#$s in the middle are.
Transition function ($\delta$): this is the trickiest part. If we're in a state $(\alpha, \beta, \gamma, \delta, \sigma)$ and see the symbol $s$, we want to go to the state where $s$ has been seen, and where $s$ is the last symbol read. If we see $a$, for example, we go to state $(1, \beta, \gamma, \delta, a)$: we mark that $a$ has been seen, don't change $\beta$, $\gamma$, or $\delta$, and record $a$ as the most recently read symbol.


Given a Turing machine M, is there a TM that computes the number of states M has? I've seen it used but I can't think of a way to construct such TM. Would appreciate any help!

I think you are a bit confused about TMs. A Turing machine, by canonical definition (as found in textbooks like [Sipser 1996], [Papadimitriou 1982] and [Hopcroft and Ullman 1979], as well as on Wikipedia), is a 7-tuple, one of which is $Q$, the set of states. So, the set of states of a Turing machine is not  computed; it is part of the definition of a TM.

In case of a universal TM, the input to the TM is the encoding of another TM (as well as its input). If you are familiar with functional programming, this is similar to a meta-circular evaluator (it is also similar to the eval function in some programming languages).

So, an encoding of a TM should encode all 7 elements that comprise the TM. Which means that a correct encoding of a TM must encode an enumeration of the set $Q$. Now, you can construct another TM that operates on the encoding of TMs (again, if you have done FP, it is similar to higher-order functions in FP).

If you know the encoding used, it should be trivial to retrieve the set of states of the input TM. You do need to count the number of elements in that set, but that should be Turing computable (because the set of states has to be finite). Now you have a TM that computes the number of state that another TM has.


Whats the logic between MAR, MBR and Control Bus Control Unit has MAR and MBR registers. so MAR emits instruction to address bus so that the specific cell in the memory is activated. MAR also emits READ or WRITE command to control bus. MBR emit data for WRITE actions to data bus.

Question is how does the control bus communicate between MAR and MBR to know whether it is a write or read command. And once the cell is activated, how does data is being written or read?

I know CPU is smart... and computer bus is smarter... but there has to be logic to it...

The RAM typically has a input pin called MW for "memory write" (maybe with inverted logic, then written with an overbar), to distinguish between read and write operations.

Control will probably use an extra wire to the RAM. In theory, you could use an usused high address bit for that, too, but I guess that would be considered to be a very questionable design - in fact "invalid" memory addresses are used for other strange things, like talking to non-memory devices such as line printers.

An address decoder will select the appropriate memory cell.

After that, the rest will depend on the MW bit... on the writing side, if it's static RAM (SRAM), you can use MW for enabling ("gating") the flipflop S (set) pin. On the reading side, you could use a transmission gate to connect or disconnect the RAM output from the data bus (logic gates won't do here, as the RAM output has to be decoupled from the data bus, unless you are actually reading values).


Language of TMs that accept some x in less than 50 steps. Is it in co-RE? L = {M | M is a TM and there exists an input that the TM M accepts in
less than 50 steps}

I need to find a minimal
class it belongs to between R/ RE/ co-RE/ not in RE∪co-RE. I managed to show that it is in RE with a TM. I think its not in co-RE, because it has to check every input to know wheter a TM M belongs to L. and there are an infinite amount of inputs. I tried to use mapping recursion with ATM, but that failed. Would appreciate any advice, thanks.

Maybe that will help ?

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec09.pdf

Page 42
Credits : Nancy Lynch MIT

Applications of Rice’s Theorem

• Example 3: Another property that isn’t a language property and is decidable

{ M |M is a TM that runs for at most 37 steps on input 01 }

– Not a language property, not a property of a machine’s structure.

– Rice doesn’t apply.

– Obviously decidable, since, given the TM description, we can just simulate it for 37 steps.


If a user confirmed a booking or transaction on the database system, but it failed and it falls over to the replica, what if the transaction is lost? This is an overall system design and DBMS question:
If the user books a ticket or an item on a website, how do we solve the issue of confirming a ticket is sold to the user, but the main Database System breaks down, and the secondary DMBS doesn't have that information yet?
Is the most common solution just to not commit the transaction until both the master and slave DBMS has confirmed?

There is no single answer that is always used; there is a tradeoff between consistency, availability, and ability to handle failures.  Most databases ensure that the data is stored persistently on disk before reporting that the transaction is confirmed, so even if the main database fails, if it has accepted the data, then the data will be there on disk.
Of course you could avoid committing until both replicas have confirmed, but then the system would not be available if either replica cannot be reached; or you could continue as soon as the master has accepted the data, but then the secondary replica could become out of sync.  I suggest learning about the CAP theorem and fundamental tradeoffs in database systems.
There will always be some failures that we cannot or do not prevent through technical means.  So, they might be addressed by ad-hoc methods (e.g., the customer could call customer support).


True Postcondition, with true Precondition In my exam preparation I stumbled across the follwoing exercise regarding pre and postconditions:

As far as I understood the question, we need to express some condition for p, such that if that condition holds for p, then we have that {true} p {true}.

The conclusion I got to when trying to think about it intuitevely is that p could simply be a skip statement, but I found myself wondering what a {true} postcondition implies. I know a {true} precondition means that there is no restriction on inputs, what does it mean for postcondition? What would be such a suitable condition to express p?

Thanks!

A true postcondition means there is no restriction on outputs.

Think about it. The condition x > 5 means: it's true (anything goes), as long as x is greater than 5. The only way for that condition to be invalidated is when x isn't greater than 5. The condition true means: x doesn't even need to be greater than 5. There is no way to invalidate that condition at all. Anything goes.

(If you don't mind, I'll leave the rest to you.)


n-DNF boolean formula k satisfiability Given an n variable boolean DNF formula and a number k, does this formula has satisfying input combination greater than k?. (0<=k<=2^n).
Where input is infinite number of n tuples where repeating tuple is possible.
For exampl.  F(a,b) =ab + a'b. Input set is (11,00,11,01) and k=2.
Answer is 3 here so decision says yes as 3>k.
Can i define this problem in more formal way and prove that it is np/npc/ anything else. I am looking for suggestions specially for infinite number of tuples. I am aware of npc and reduction stuffs but need help to classify this problem properly.

Your problem can't be any easier than DNF-TAUTOLOGIES since that problem is produced by setting $k$ equal to $2^n$.  Therefore your problem is NP-hard, just as DNF-TAUTOLOGIES is.


Two functions which can create any computable function by composing? Do there exist two computable functions, a and b, which can construct every computable function by a finite serie of a's and b's which is function composed? Fx. let's take the serie, a,b,a,b,b,a,a,a , which function composed is the function, a∘b∘a∘b∘b∘a∘a∘a ( =a(b(a(b(b(a(a(a(x)))))))) ), this function is the function described by the serie, a,b,a,b,b,a,a,a. And I want to know if every program can be described, by such serie.

If such functions exist, can you tell a example of a and b?

Thanks.

If such functions existed, they would constitute a computable enumeration of all computable functions, which is impossible for the following reason. Suppose you had a computable enumeration $f_i$ of all computable functions. The function $g\colon i \mapsto f_i(i) + 1$ is then computable, but by definition $g \neq f_i$ for all $i$.


Counting big enough elements Let $v$ be a vector of positive integers of length $n$. I want to find the highest $k$ such as there are at least $k$ elements of $v$ that are greater or equal to $k$.

What would be the best algorithm for finding $k$?

Examples:

$v = (1, 2, 3, \ldots, 100) \rightarrow k = 50$, because there are at least 50 elements that are greater or equal to 50 (there are even 51 of those, fifty through a hundred, but that doesn’t matter); but there are only 50 (so—less than 51) elements greater or equal to 51.
$v = (100, 101, 102, 103, 104) \rightarrow k = 5$, because all five elements are greater or equal to five, and there cannot possibly be six elements greater or equal to six.
$v = (1, 1, 1, 100, 100, 100) \rightarrow k = 3$

Any ideas how to approach this?

My initial idea is this:

Sort the vector in descending order in $O(n \log n)$
Starting with the median (it seems, intuitively, as a good place to start), check if a number on a set position $i$ is greater or equal than $i$—since everything to the left of it is greater to equal to it (the vector is sorted), we know there are at least that many elements that are greater or equal to $v[i]$.
Go right or left accordingly to what was found—if we found that there are not enough values greater to $v[i]$, let’s try with the smaller-or-equal number, $v[i+1]$. If it was big enough, go the opposite direction, checking $v[i-1]$.
Our work is done when there is some $i_m$ for which the requirement holds, but it doesn’t hold for $i_{m} + 1$. That would require at most $O(n)$ checks.
Thus, the slowest part is the sort itself, making the algorithm $O(n \log n)$ total.

I’m curious if this is the best we can do, or can we possibly make it even faster.

You can do it in linear time, using an efficient selection algorithm.

Find the median, and partition the array into numbers below the median and numbers above the median.  Check whether the number you're looking for is above or below the median.  Then, recurse on the appropriate partition.

The running time satisfies the recurrence $T(n)=T(n/2)+O(n)$, since you can find the median and partition the array in $O(n)$ time.  The solution to this recurrence is $T(n)=O(n)$, so the total running time is $O(n)$.  This is faster than your $O(n \log n)$ time algorithm.


Why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$? I'm not sure how to get from the left hand side to the right. It appears in Sipser's Introduction to the Theory of Computing, in a proof of showing that a $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{O(t(n))}$ time deterministic single-tape Turing machine.

Note that for every number $x$ it holds that $x=2^{\log x}$. Using this, we can do the following:

$t(n)b^{t(n)}=2^{\log t(n)}b^{t(n)}=2^{\log t(n)}({2^{\log b}})^{t(n)}=2^{\log t(n)}2^{t(n)\log b}=2^{\log t(n)+t(n)\log b}$.
Now, assuming $t$ is non-decreasing, we have that $\log t(n)=O(t(n))$, so ${\log t(n)+t(n)\log b}=O(t(n))$, and we're done.


Trouble understanding this dynamic programming solution Here is the question:

I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K.

for example: If n=3 and k=1

and the given tree is    1---2---3

Then the total valid subtrees would be 6

{}, {1}, {3}, {1,2}, {2,3}, {1,2,3}

I know I can enumerate all 2^n trees and chack the valid ones, but is there some approach that is faster? Can I achieve polynomial time in n? Something close to O(n^3) or even O(n^4) would be nice.

for k=1 this value turns out to be 2*n

There was a solution provided for this one as:

This is a fairly typical instance of the DP-on-a-tree paradigm. Let's generalize the problem slightly by allowing the specification of a root vertex v and stratifying the counts of the small-boundary trees in two ways: whether v is included, and how many edges comprise the boundary.

The base case is easy. There are no edges and thus two subtrees: one includes v, the other excludes v, and both have no boundary edges. Otherwise, let e = {v, w} be an edge incident to v. The instance looks like this.

|\         /|
| \   e   / |
|L v-----w R|
| /       \ |
|/         \|

Compute recursively the stratified counts for L rooted at v and R rooted at w.

Subtrees that include v consist of a subtree in L that includes v, plus optionally e and a subtree in R that includes w. Subtrees that don't include v consist of either a subtree in L that doesn't include v, or a subtree in R (double counting the empty tree). This means we can obtain the stratified counts by convolving the stratified counts for L with the stratified counts for R.

Here's how this works on your example. Let's choose root 1.

  e
1---2---3

We choose e as shown and recurse.

1

The vector for includes-1 is [1], since the one subtree is {1}, with no boundary. The vector for excludes-1 is [1], since the one subtree is {}, also with no boundary.

2---3

We compute 2 and 3 as we did for 1. The vector for includes-2 is [1, 1], since {2, 3} has no boundary edges, and {2} has one. We obtained this vector by adding the includes-2 vector for 2, shifted by one because of the new boundary edge to make [0, 1], to the convolution of the includes-2 vector for 2 with the includes-3 vector for 3, which is [1, 0]. The vector for excludes-2 is [1] + [1, 1] - [1] = [1, 1], where [1, 1] is the sum of the shifted includes-3 vector and the excludes-3 vector, and the subtraction is to compensate for double-counting {}.

Now, for the original invocation, to get the includes-1 vector, we add [0, 1], the includes-1 vector for 1 shifted by one, to the convolution of [1] with [1, 1], obtaining [1, 2]. To check: {1, 2, 3} has no boundary, and {1} and {1, 2} have one boundary edge. The excludes-1 vector is [1] + [1, 2, 1] - [1] = [1, 2, 1]. To check: {} has no boundary, {2, 3} and {3} have one boundary edge, and {2} has two boundary edges.

I am unable to understand this fully. Can anyone help?

The problem is to count the subtrees of an undirected tree that have at
most k outgoing edges to the rest of the tree.

The idea of the algorithm is a divide and conquer plus dynamic programming technique. For a
tree T, you divide it into 2 subtrees, and for each you compute all
subtrees that have i outgoing edges for each i less than or equal to
k. There is however a little twist to allow the recurrence step to
work. The divide and conquer part is not really necessary, but it does allow a simpler organization.

I agree that the explanation of the algorithm that you were given is somewhat obfuscated.

small-boundary trees are what you called valid trees,  with at most
k out-going edges.

Consider your tree T.

Though in your undirected tree T all nodes are born equal, you choose
to distinguish a root v.

The idea is to count the number of subtrees for each value of the
number of outgoing edges, an also separate those that contain the root
v from those that do not.

Hence you have two vectors Tv+ and Tv--, for the subtrees including v and
for the subtrees not including root node v.
Tv+[i] is the number of subtrees including V that have i outgoing
edges.
Tv-[i] is the number of subtrees not including V that have i outgoing
edges.

The sum of these two vectors will give you the number of subtrees with i outgoing edges for each value of i less than or equal to k. At this point the distinction into two vectors has not been useful, but it is needed for the recursion.

Before using them, you have to compute these two vectors.

For that purpose, you choose an edge e={v,w}, which cuts your tree T in
two subtrees L and R, respectively rooted in v and w as shown on the figure

|\         /|
| \   e   / |
|L v-----w R|
| /       \ |
|/         \|

Suppose you have computed the vectors Lv+, Lv-, Rw+ and Rw-, then you
can use the results in those 4 vectors to compute Tv+ and Tv- as
explained in the document.

Subtrees that include v consist of a subtree in L that includes v,
plus optionally e and a subtree in R that includes w.

translates into :

Tv+[i] = Lv+[i-1] + sum (Lv+[j] * Rw+[k]) for all (j,k) such that j+k=i , for i>0

Tv+[0] = 1    Only the whole tree T contains v and has no outgoing edges.

The i-1 in Lv+[i-1]is to account for the added outgoing edge {v,w}

The sum of products is for all subtrees that include the edge {v,w}, and thus have a
part in L and another in R.

Subtrees that don't include v consist of either a subtree in L that
doesn't include v, or a subtree in R (double counting the empty tree).

translates into :

Tv-[i] = Lv-[i] + Rw+[i-1] + Rw-[i]  for i>0

Tv-[0] = 1  for th empty tree {}

The i-1 in Rw+[i-1] is for the fact that subtrees counted in Rw+ get an extra edge {v, w} in the recurrence step since v is not included

There is empty tree in Lv-[i] and another in Rw-[i], but it does not matter as empty trees are considered  in the case i=0.

hoping I did not miss anything.

Is this enough to get you started, or do you need more?

One last point. The description of the algorithm starts by saying that it will consider the count of small-boundary trees, which I believe are your valid trees. If you know in advance the value of k (defining them) that you do not wish to exceed,
then you vectors need only have length k+1. For example, if k=1, the vectors should be of length 2 (for zero edges and for 1 edge). Any subtree that exceeds k edges will be useless for the rest of the algorithm (the count cannot go down)
and can thus be forgotten.

Note that, as described, the original algorithm uses variable size arrays, only as long as needed for the subtree at hand. That is required if you do not fix k in advance. If you do, you just use length k+1 as I said.

But this is a personnal remark that you may or may not trust. It is not in the algorithm you have been given.


Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well? This relates to an answer for this question.
The opinion said that:

Personally, I don’t see much value in coding interviews. The problems I’ve seen asked as coding questions have been (for the most part):

asked by a person who has one specific solution in mind and is unable to recognise an alternative answer or even a better answer (Note: I actually faced this one time - the clown kept telling me I was wrong. For a metaphor of this, see 1 below);

Imagine a coding question to solve traveling salesman in non-polynomial time (a stupid question because it’s not realistic but I’m going for a metaphor here). Imagine, instead, you solved a different NP-complete problem in non-polynomial time and the interviewer wouldn’t accept that solving any one NP-complete problem in non-polynomial time solves them all. If the interviewer lacks the ability to grasp a great answer, then the candidate offering the great answer is filtered out.

I've read in Geeksforgeeks that:

The interesting part is, if any one of the NP complete problems can be solved in polynomial time, then all of them can be solved.

From what I understand, the interviewer gave a TSP problem, to be solved in brute-force approach. The interviewee solved a different problem of the same NP-completeness level in non-polynomial time (maybe using brute-force approach) too. And, literally what I quote from the Geeksforgeeks above.
My questions:

Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well?
Are the solutions (in non-polynomial time) for NP-complete problems universal (one solution can be used for all)?
Why would the interviewee solve another problem instead of the given problem? Or am I misunderstanding something? Is it to show that the approach is universal?

Thank you in advance for your insights.

If you solve a Problem that is NP-complete the solution to this problem can not be applied instantly to any other Problem that is NP-complete. However, the problem that you solved might be used to find a solution for other problems in NP.
For example:

If you can solve the TSP Problem your an adaption of your solution could also solve the problem of finding a hamiltonian circle in a graph
If you can solve the hamiltonian circle problem an adaption of your solution could also solve the long path problem
...

So your solution can not be directly used to solve other problems.
But if you found a solution for a problem that is NP-complete this implies that there are solutions in P for every problem that was believed to be NP-complete. This is because NP-completeness is defined as follows:

A problem P is NP-complete if it is NP-hard and the problem lies in NP
Beeing NP-hard means that every other problem P' that is NP-complete can be reduced to the problem P (meaning exactly that if you could find a solution for P you could also find oune for P')

The answer to your second question is simply "No".
The only reason for a cancidate to solve another problem that is NP-complete is that he could not find a solution for the given problem but for the other problem. And in addition he knows how to modify the problem he is abel to solve in such a way that he finds a solution for the given problem.


Is arithmetic a context free grammar? Like including parenthesis (( and )), addition, subtraction, multiplication, and division, and the Order of Operations in mind.
I tried (in Lark EBNF):
%import common.WS
%ignore WS
%import common.SIGNED_NUMBER -> NUMBER

start: exp
?exp : add
     | mul
     | sub
     | div
     | NUMBER
     | frac
     | parenthesis
?parenthesis: "(" exp ")"
add  : exp "+" exp
sub  : exp "-" exp
mul  : (exp "*" exp) | NUMBER parenthesis
div  : exp "/" exp

I wonder if the Order of Operations would make arithmetic a context-free grammar.
Originally this post

You are confusing two or three different concepts here:

Languages: these are collections of strings.
Context-free grammars: this is a specific way to describe languages.
Parsing: this is the process in which a computer "understands" input.

You haven't explained what you mean by "arithmetic"; some people think of arithmetic as the set of first-order statements about the natural numbers which are true, for example. However, it seems that by arithmetic you mean the set of well-formed arithmetic expressions (you leave out some important details, for example, what atoms are allowed, whether whitespace is allowed, and so on). Assuming this, arithmetic is most certainly not a context-free grammar, simply because arithmetic is a language, not a grammar. However, it can be described as a context-free grammar, as you demonstrate.
The next thing you are worried about is parsing ("order of operations"). Grammars describe languages, that is, sets of strings; parsing is a separate issue. It is true that context-free grammars are intimately related to parsing, via parse trees. It is possible to construct a context-free grammar for the language of arithmetic expressions that reflects "order of operations", in the sense that we can use the parse tree directly to evaluate the expressions in a recursive way (in the fashion of attribute grammars.
For example, suppose that the only atom is $n$, and that we are only interested in addition and multiplication, and allow parentheses; and furthermore, multiplication has higher priority than addition, and both associate to the left. This is reflected in the following grammar:
\begin{align}
&\mathit{EXPR} \to \mathit{EXPR} + \mathit{TERM} \mid \mathit{TERM} \\
&\mathit{TERM} \to \mathit{TERM} * \mathit{FACTOR} \mid \mathit{FACTOR} \\
&\mathit{FACTOR} \to (\mathit{EXPR}) \mid n
\end{align}
You can check that $n+n+n$ is "understood" as $[n+n]+n$, and $a+b*c$ is understood as $a+[b*c]$, for example. Moreover, this grammar is unambiguous (unless I made a mistake), that is, any word in the language has a unique parse tree.
In practice, starting with an ambiguous context-free grammar and precedence rules (including associativity), parser generators can create equivalent unambiguous context-free grammars (or more accurately, parsing algorithms).


Difference between Normative annexes and Informative annexes in ADA 95 I was reading the ADA 95 reference manual. I came across these  two words in annexes
 Normative and informative . I couldnt find the difference between those. Your help will  be much appreciated.

"Normative" means something that has to be followed, part of the standard. "Informative" is explanations meant to be understood by mere human beings, and that might be ambiguous or inaccurate. It is not to be relied on. Read it to understand, refer to the normative parts where it matters.


What are some "easy" unreasonable implications of O(1) time memory access? If you are given a memory address $n$ bits long, then you need to at least process those bits. Hence, if you have $N$ memory available, addressed by $n$ bits, it would take  $O(\mathbf{log}(N)) = O(n)$ time to access a given memory location, at best. I can see why it might be convenient to assume $O(1)$ memory access time because we don't go out of our way to abuse it in day-to-day arguments, and because $\mathbf{log}$ grows slowly. That said, what are some "easy" unreasonable implications of being able to access memory in $O(1)$?

Memory access is assumed to be constant time, because normally you access memory that is close to each other, eg. from one hard drive or one given computer. Under that assumption there is a constant maximum amount of time to retrieve that data.

You are right. If I access data randomly accross very large amounts of data, then it's nowhere near constant, but normally you can arrange the data beforehand in a way that makes it O(1), because of it fitting onto one machine or very close machines. Another reason is that, harddrives all come with their hardware. That means normally you won't be switching hard drives in and out of one machine, and each drive comes with it's own reader. Also most machines are limited to a certain amount of drives. Those technical limitation give O(1) comlexity to most pratical applications and the software perspective of things.

One easy and unreasonable implication of O(1) time memory access is violating the assumptions above by scattering data randomly, across multiple machines in an unordered fashion or switching drives in and out of machines and expecting O(1) access times. Anything relying on wrong assumption is doomed to be wrong and thus unreasonable.


How many times is a for loop executed? Consider the following code snippet:

for(int i=0;i<n;i++)

The question I have is: whether this loop is executed $n$ times or $(n+1)$ times?

According to what I understand: when $i=n$, the for loop would increment $i$ to $n+1$ and check if $i<n$ which would evaluate to false and the loop will be exited.

So the increment would be performed a total of $(n+1)$ times. Is this correct? Should we count $(n+1)$ as the number of increment operations performed during algorithm analysis?

I know this would not make any difference to the complexity since $O(n+1) = O(n)$, linear time. But I was just curious to know if my understanding is correct or not.

Consider the following code snippet:

  for(int i=0;i<n;i++)

  The question I have is: whether this loop is executed $n$ times or $(n+1)$ times?

This loop executes $n$ times, not $n+1$ times. The first iteration of the loop has $i = 0$; the second has $i = 1$, and so on, up to the last iteration of the loop $i = (n-1)$. Then let us see what happens after that:

We get to the bottom of the loop  when $i = (n-1)$.
At this point, we jump up to the top and execute i++. So now $i = n$.
Next, we check the loop condition. We see that i < n is false, so the loop condition is false. That means we exit the loop.

So in total, we executed the loop for $i = 0$, $i = 1$, $i = 2$, up to $i = n-1$. That is in total $n$ times.

Your misconception was that the loop is terminated once $i$ gets to $n + 1$; but actually it is terminated when $i = n$, because $n$ is already not less than $n$.

  I know this would not make any difference to the complexity since $O(n+1)=O(n)$, linear time.

That is correct!


How can I improve my algorithmic ingenuity? During undergrad I felt my education was mostly comprised of applying existing theory to real world problems (ie. algorithm design/analysis). I've seen derivations of many algorithms and proofs of their complexity, but I'm often left bothered by the question of how one comes to discover an algorithm. It seems daunting to imagine developing a novel algorithm given the ingenuity involved in crafting an effective approach. I'm wondering if there are ways to train that ingenuity.

My question is, how I can cultivate the skills necessary to develop original approaches to quantitative problems? Are there any resources that focus on these skills?

It seems that competitive programming might help you. Or just the "programming" part of it. If you want to hone your problem solving skills (and therefore your ability to come up with original ideas), it seems that solving competitive problems is the way to go, since they by design target this skill.

You would need two kinds of resources: problem archives and theory materials.

For problem archives I can suggest you to try out

timus.online (problems requiring some clever insights/observations start after ~270 difficulty)
codeforces.org (problemset tab, richer variety of problems, but the overall quality is somewhat lower than that on the timus)
onlinejudge.org (in uHunt there is a table with problems that cover a great variety of problems; a supplement for the book Competitive Programming 3)
urionlinejudge.com.br (has some great problems)

Also, there's atcoder.co.jp which is like codeforces but primarily targets math-related problems.

The key to finding original ideas is to know what people have come up with already. If you understand these ideas and can apply them relatively easily then you a) can come up with a clever idea by combining these older ideas in a clever way and b) you can search for fundamentally new ideas much more efficiently because you know what is not a new idea and what is not the new way of thinking to find new ideas.

If you agree with the previous paragraph, then you'll need resources where you'll be able to learn new concepts and ideas. The key with this is to not only understand the theorem or the algorithm but to understand the intuition and the proof(s) also. Proofs give explicit insight as to how to come up with and how to be sure that the idea works. Understanding the tricks and algorithms (of thinking) used in proofs is the key to come up with your own ideas.

Intuition, on the other hand, is an implicit insight, it's something that connects problems, its proofs (or a subset of proofs) and the topic of the problem in general. I say this so that you wouldn't think that intuition is something magical or that if you didn't get it when you read a proof then you wouldn't get it at all. To acquire it you have to perform these steps

Before seeing the solution, try to think on it for at least 30 minutes (for me, doodling helps a lot to come up with intuitive solutions)
Then, if you feel that some ideas that you think are going to work 100% are there but you can't quite reach them in your brain, don't give up on it and hold on to them until you go to sleep. If you won't be able to sleep thinking on the problem, then you're sure to get some insight when you wake up. (https://psychology.stackexchange.com/a/13366 + my experience).
Without any dependence on whether you have solved the problem or not after such a procedure, when you'll open the proof(s), you'll be able to absorb and analyze them much more efficiently, since you'll read not to know the ideas but to find out why your ideas weren't working, how close were you, where you have made a mistake in your thinking, what have you missed, why that thing you focused too much on wasn't that relevant, what have you had to know to solve it anyway, etc. etc.... (this is how SQ3R method works also, it makes you question the text first and only then lets you read it as a way to answer the questions; an active reading, instead of passive reading).
If you were able to extract some guideful intuition out of the proofs, congrats! Now, forget about this problem and come back after two or three days and solve another similar or a little harder problem on the same topic. This way you'll "imprint" this intuition in your brain, so to say, for a relatively long time (See, spaced repetition)
If you haven't then don't be sad. You understood more or less how the proofs work. This means that the only thing that's left is to unite them somehow with intuition. To do that just continue solving problems on the same general topic (strings, graphs, number theory, etc.). Intuition is not bound to some concrete problem (if that was, the intuition wouldn't be able to help solve other problems), if you'll understand intuitions behind other problems then naturally you'll understand the intuition behind the original problem as well!

Okay, so. With this, you'll be able to grasp the old ideas efficiently, understand the intuition and ingenuity behind them. These are plausible resources (although, I think you might already use them):

Introduction to Algorithms. Cormen
geekforgeeks.com
wikipedia.com (seriously, they have great articles on some algorithms)
visualgo.net (especially, if you're a visual learner ;)

From my experience at this point, you'll be able to come with original ideas by yourself and naturally. You'll be able to see the connections between the ideas clearly and they'll start to just pop into your head. Solving problems will sustain the neural paths in your brain and you won't forget the theoretical basis and intuition you've built. Solving problems will also build new neural connections and will bring joy when discovering new insights.

Lastly, I want to say that if your insight is nothing you've learned before, then it has value. If you combine two ideas together, even if it was simple, you'll get a new idea and it will have value. Every time you come up with such ideas, in any case, you create something valuable. If your goal would be to come up with something valuable, then you'll succeed every time. If your goal would be to come up with an "original insight", then you'll be quick to get severely demotivated, since no matter what you'll do, you'll most probably fail (at the beginning for sure). In the end, if you follow these steps or something similar, you cannot get not better! Surely, somewhen in the future, every tenth of your ideas will be a truly original one ;)


Does Amdahl's law apply to modern multi-code processors? I was reading about Amdahl's law and it state that value of Amdahl's law always lies between 0 and 1. My question is, is it still true in today's case/scenario? When we have system like core i7?

Yes, it's still true. The speedup can't be less than zero (if parallelizing your code makes it slower, just run the serial version) or more than 100% (because saving more than 100% of the runtime would make the runtime negative).

Multicore processors are essentially just a matter of terminology changing over time. If you think you have one processor with four cores, Amdahl thinks you have four processors.


Reconstructing files from binary Popular view tells us that any kind of information is just a collection of bits, that is zeroes and ones placed in a particular order. I was thus having this thought.

Suppose that I have some kind of file such as a text document, a PDF or anything else and that I also have a memory so perfect that I can remember the file exactly in its binary format, i.e. the number and place of zeroes and ones. But nothing else.

My question would then be if, in practice, it would be possible to reconstruct my initial file (without imposing any assumptions on what format it takes) from just this binary format.

Please be advised that I am not an expert in computer science and I do have only some very basic understanding. I do hope though this question fits here.

First notice that a "file" is a sequence of 0s and 1s in binary format that are stored in some kind of persistent storage (an hard disk, a CD, an USB key, ...).

According to the the type of information stored in the file (a plain text, a PDF document, an image, a video, a song,  ...) its bits (bytes) are usually arranged using standard rules and they have precise meaning: they follow a file format which specifies how information is encoded in the file.

Usually the name of the file (filename) has an extension (.mp3, .txt, .jpg, .pdf, .tex, ...) that indicates the file format i.e. how information is encoded.

Computer programs like text editors, image editors, video players, music players, ... can read a file in one (or more) format and decode the information stored in it (show the text on the screen, play it, process it, ... ).

Now suppose that you have a bunch of bytes in your head. First you can write them directly in a file using a program like a binary editor. When they are stored in a file, you need to discover its file format ...

first you can try to display it as a text file (like suggested by saadtaame in his answer): many file formats (text data, html files, xml files, ...) store the information in plain text (ASCII);
or you can change its extension (.pdf, .jpg, .mp3, .gif, .avi, ...), and try to open it with some standard programs ... if you are lucky you'll find one that opens it correctly;
or you can do something smarter. You can examine the first bytes of the file (header): they usually have a particular structure or contains specific fixed characters that allow you to quickly find the file format of the whole file.

For example the bytes 6,7,8,9 of a JPEG file are always 0x4a 0x46 0x49 0x46, which correspond to the string "JFIF" in ASCII. Windows PE executables contain the string "This program cannot ..." in the header. The first two bytes of a file in ZIP format are "PK", and so on ...

But there are thousands of file formats out there, so you can also consider using a computer program that given an unknown file can help you to find its file format automatically.

Finally don't forget that the information in a file can also be encrypted or the file format can be proprietary (and closed, i.e. undocumented); in these cases there are very little probability (zero?) to decode the information stored in the files.