# Question
Title: When inserting into a binary tree, is there a universal agreed upon place to insert then new node to minimize complexity?
Do programmers (in real life), always insert at the top node or somewhere else? Because in my text book CLRS it is not made very clear, so the insertion process can take a best case of O(1), if you insert it just at the right place, or a worst case when you have to rebalance the entire tree.

So in practice is there a place that all new nodes are inserted?

# Answer
There are several different concepts here. Let's start from the most general. A **tree** is a data structure that consists of a root and a collection of children, each of which is a tree. A node of the tree is either the root of the tree itself of a node of the children, i.e. it's the root, or the root of a child, or the root of a child's child, etc. The nodes of a tree can contain information of any type. Here are a few examples of trees:

* One that you encounter everyday when working with computers is the filesystem¹: there's a root directory, subtrees are subdirectories, and there are subtrees which have no children and which are regular files; the children of a node are identified by a name (so it's not “first child”, “second child”, etc. but “child named `hello.txt`, child named `pictures`”, etc.).
* An example from real life is the section structure of a book: there's the book, which is divided into chapters, which are divided into sections, which are divided into subsections, etc.
* One type of tree data structure is the **trie**, which stores information indexed by a string. Each node has one child per character in the alphabet. The information corresponding to a string is located by starting from the root, going to the child corresponding to the first character of the string, then to the child of that child corresponding to the second character, etc. For example the string `abc` would be stored three levels deep, going down from the root to the `a` child, then to its `b` child, then to *its* `c` child.

You'll notice that in the filesystem and in the book sections example, information can be inserted anywhere. I can store my files in whichever directory I want; I can add a section to the chapter of my choice. In contrast, the structure of a trie is completely rigid: there's only a single place in the tree where `abc` can go.

A **binary tree** is a tree where each node happens to have at most two children. The two children are typically known as the left and right child. There is a common variation on this definition that defines a binary tree to have two types of nodes: internal nodes which must have exactly two children, and leaves which have no children.

A **binary search tree** is a type of tree data structure. Like a trie, it imposes a constraint on where the information must be stored. A trie indexes information by a string; a search tree indexes information that is ordered: it can be numbers, strings, etc. In a binary search tree, the data in the left subtree of a node is always smaller than the datum in the node itself, and the data in the right subtree of a node is always smaller than the datum in the node.

If you try to add element into an existing search tree, there's a single way to do that without changing the current structure of the tree: going down from the root, take the left child if the node is larger than the element to add, take the right child if the node is smaller, and keep going until you get to a child that doesn't exist, and create that child.

However, the structure of search trees is less rigid than the structure of tries: there are different search trees that contain the same data. For example, here are three binary search trees containing the integers 2, 4, 5, 8, 9 (there are of course many more):

```
      8            4          2
    /   \         / \          \
   4      9      2   5          4
  / \               / \          \
 2   5             8   9          5
                                   \
                                    9
                                   /
                                  8

```

In the worst case, inserting an element in a search tree requires traversing the whole height of the tree, which as the last example above show can be as much as the number of elements of the tree.

The leeway in the tree structure allows one to reshape the tree when adding or removing elements from it. This is called **balancing**. Balancing is done in order to keep the height small, which keeps operations such as search, insertion and deletion efficient. There are several variants of **balanced search trees**, where the balancing operations is designed to keep the height of the tree logarithmic in the number of elements of the tree: $h = O(\log(n))$. The basic principle of a balanced search tree is to keep some information about the height of the subtree in each node; when the height difference between the two children of a node is too large, some nodes are moved from the deeper subtree to the shallower subtree to rebalance. The rebalancing operation costs $O(1)$ at each node and is performed over the path to the element that's being inserted or removed, so its cost over the whole tree is $O(h) = O(\log n)$. This way, search, insertion and deletion in a balanced search tree cost $O(h)$ to find the target location, plus $O(h)$ to rebalance, which is $O(h) + O(h) = O(\log n)$ total.

¹ <sub> In practice filesystems can be more complex than what I'm talking about here. Filesystems with hard links aren't even trees. </sub>
> 7 votes

# Answer
There is only one place if you're using a binary search tree (also known as an ordered binary tree or sorted binary tree).

```
insert(val, node):
  if current node is null then make a new node out of val
  if val < node.val then node.left = insert(val, left)
  if val >= node.val then node.right = insert(val, right)

```

Inserting at the top is not valid for a binary search tree as it breaks the invariant of such trees, which is that all nodes in the left child are less than the parent value and all nodes in the right child are greater than the parent (or equal in some cases). Without this you just have an overly complicated list.
> 2 votes

# Answer
Interesting note from the Wikipedia article: "Note that the terminology is by no means standardized in the literature." http://en.wikipedia.org/wiki/Binary\_tree

So just by saying binary tree all that means is a tree where each node has two children, it doesn't even mean sorted. So in the most basic unsorted and unbalanced binary tree, you can put a new node at the end of any branch you like!

Now assuming you are not talking AVL or Red-Black, and just a sorted unbalanced binary tree, then if the tree is empty, then you insert at the root. Otherwise you use a method of looking at each node, starting at the root, and if your value is less than the node, go left, if it's more, go right, and when you get to the end of a branch (a leaf), put it there, left if less, right if more. (As noted in an algorithm in another answer)

Of course you say "in real life," in real life you would hardly ever use a simple unbalanced binary tree, the insertion location would be the same but then you would balance (see AVL or Red-Black tree). And in real life a n-ary btree is much more likely the data structure you would use.
> 2 votes

---
Tags: data-structures, binary-trees
---


# Question
Title: Analog computers and the Church-Turing thesis
I'd like to quote from Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, page 5 (emphasis mine):

> One class of challenges to the strong Church–Turing thesis comes from the field of analog computation. In the years since Turing, many different teams of researchers have noticed that certain types of analog computers can efficiently solve problems believed to have no efficient solution on a Turing machine. **At first glance these analog computers appear to violate the strong form of the Church–Turing thesis. Unfortunately for analog computation, it turns out that when realistic assumptions about the presence of noise in analog computers are made, their power disappears in all known instances; they cannot efficiently solve problems which are not efficiently solvable on a Turing machine.** This lesson – that the effects of realistic noise must be taken into account in evaluating the efficiency of a computational model – was one of the great early challenges of quantum computation and quantum information, a challenge successfully met by the development of a theory of quantum error-correcting codes and fault-tolerant quantum computation. Thus, unlike analog computation, quantum computation can in principle tolerate a finite amount of noise and still retain its computational advantages.

Is this a statement that noise scales faster than some power of the problem size, or can someone point me in the right direction so that I can find out more about whether these scaling limits are fundamental or merely an "engineering issue"?

To be clear, I am asking if analog computers cannot beat Turing machines in efficiency due to noise.

# Answer
> 7 votes
First of all, the authors seem to be confusing two different thesis: the Church–Turing thesis and the Cook–Karp thesis. The first concerns what is computable, and the second concerns what is computable *efficiently*.

According to the Cook–Karp thesis, all reasonable "strong" computational models are polynomially equivalent, in the sense that they all polynomially simulate each other. Equivalently, every reasonable computational model can be polynomially simulated by a Turing machine. Quantum computers are a counterexample to this thesis, since they appear to be exponentially more efficient than classical computers. However, they are not a counterexample to the Church–Turing thesis, that is, using quantum computers you can't compute anything that you can't already compute with a Turing machine. We can also formulate an updated Cook–Karp thesis, stating that all physically realizable computational models are polynomially simulated by quantum computers.

Several physical models of computations have been proposed as challenging these theses, but under scrutiny, they all seem to not violate the Church–Turing thesis, or not to be more powerful than quantum computation. Scott Aaronson proposes to consider this situation as a "law of nature". However, as far as I know there are no theoretical arguments supporting these theses other than the inductive argument that all models which have been proposed have been shown to conform to them.

# Answer
> 5 votes
that passage (written over a decade ago) is indeed key and invoking quite a bit of background knowledge and very well anticipating some future research directions. it is alluding to the field of hypercomputation which is sometimes at the fringes of TCS, because it studies models of computation that are supposedly "more powerful" than Turing machines. the interesting point about Turing machines here is that they have zero noise, so in a sense computer science is founded on this *idealization* which in some ways is physically unrealistic. and electronic systems mimic this noiselessness as a design principle, it is ever present in low level chip dynamics but very effectively abstracted away in the higher level designs that restrict all electrical signals to ideal 0/1 bits. re this:

> This lesson – that the effects of realistic noise must be taken into account in evaluating the efficiency of a computational model – was one of the great early challenges of quantum computation and quantum information, *a challenge successfully met by the development of a theory of quantum error-correcting codes and fault-tolerant quantum computation.*

it would appear that some of their assertions are looking rather prematurely optimistic in retrospect. it is true that large amounts of theory have been devised in QM error correcting codes. however, very little of it has been experimentally tested and verified. there are some scientists/ experts who suspect/ hypothesize that there may be physical laws that require noise to scale in a "bad" way for larger n-bit quantum systems. so its an area of active research and some controversy. in fact this is a key area of contention for two leading QM computing designs/ approaches, one by DWave systems and the other by the Martinis UCSB/Google group.

> To be clear, I am asking if analog computers cannot beat Turing machines in efficiency due to noise.

that is the big question isnt it? to try to answer that, consider that there are *classical analog* systems and the more recently considered *quantum* systems. for classical systems, the general consensus is as outlined by Nielsen/ Chuang, that there are theoretical models that *"seem"* more powerful but when noise is correctly taken into account, this theoretical "advantage" "melts away". in other words to propose the existence of analog computing systems "fundamentally theoretically faster" than electronic systems already built seems to nearly violate the laws of physics/ thermodynamics.

however the question for QM computing is much more an open question and is (as they anticipate somewhat) hinging on the nature of QM noise and whether it can actually be *experimentally/ controlled* as has been hypothesized and is under active investigation.

there is some deeper analysis of these issues in Aaronsons paper NP-complete Problems and Physical Reality. the skeptical overview can be found in Dyakonov Prospects for quantum computing: extremely doubtful.

---
Tags: computation-models, church-turing-thesis
---


title: Language equivalence proof

text:
# Question
Title: Language equivalence proof
Can anyone explain to me how the following is true for any language?

$$L^+ = LL^\* = L^\*L$$

I'm confused because $L^\*$ is the set of all words including the empty string, while $L^+$ is the set of all words excluding the empty string. I don't understand how concatenating $L^\*$ with $L$ makes it equal to $L^+$. What happens to the empty string? Thank you.

# Answer
In general, $L^\*$ is not the set of all words. $L^\*$ is the set of all words that can be made by taking any number of words from $L$, including zero, and sticking them together (concatenating them). $L^+$ is the set of all words that can be made by sticking together any *positive* number of words from $L$ (not including zero).

So, if you stick together one or more words ($L^+$), that's equivalent to taking one and then adding zero or more ($LL^\*$), and it's equivalent to taking zero or more and adding another one ($L^\*L$).
> 0 votes

---
Tags: formal-languages
---


# Question
Title: If algorithm runs $\theta(n)$ in time T, doubling input size has what effect on time T?
In other words, is there a relationship between the step size and the actual running time? Suppose that the algorithm is run on identical machine.

# Answer
There's no clear relationship, except that bigger inputs will tend to take longer. What we call the "running time" in complexity theory is the number of basic operations but we just choose some set of basic operations and assume that they all have the same cost. That's fine for asymptotic analysis but it doesn't correspond to the actual running time, as measured by a clock.

For example, imagine your algorithm consists of an initialization phase that takes one second, regardless of the input, plus a quadratic time loop that takes $n^2$ milliseconds to process $n$ items. Complexity theory just says that your algorithm has running time $\Theta(n^2)$, so doubling the size of the input multiplies the running time by four. Asymptotically, this is true but, if you double the input size from $10$ to $20$, the running time only changes from $1.1\\,\mathrm{s}$ to $1.4\\,\mathrm{s}$, which is nothing like a factor of four (it's less less than $30\\%$).

Another problem is that complexity theory doesn't model the sheer... well, complexity of modern computers. A simple example: suppose your quadratic algorithm runs in half a second on an input of length $\ell$. Great, it's going to run in just over half a second on a similar input of length $\ell+1$, right? Maybe. Or maybe it takes ten seconds because your data doesn't fit in the cache any more.
> 3 votes

# Answer
The answer that your teacher or textbook expects is that doubling the input size doubles the running time. The implicit assumption is that the running time is *exactly* of the form $T(n) = Cn$. In that case, $T(2n) = C(2n) = 2(Cn) = 2T(n)$. In practice, $T(n) = \Theta(n)$ only implies that $cn \leq T(n) \leq Cn$. Therefore all we can say is that if $n$ is multiplied by some large $D$ then $$ D \frac{c}{C} T(n) \leq cDn \leq T(Dn) \leq CDn \leq D \frac{C}{c} T(n). $$ So for large enough $D$, multiplying $n$ by $D$ multiplies the running time by some factor lying in the interval $\[(c/C)D,(C/c)D\]$.

The simple interpretation is still helpful intuitively. Under this interpretation:

* The running time is linear if doubling the input size doubles the running time.
* The running time is poylnomial if doubling the input size multiplies the running time by a constant.
* The running time is exponential if increasing the input size by a constant multiplies the running time by a constant.
* The running time is logarithmic if doubling the input size increases the running time by a constant.
* The running time is constant if it is independent of the input size.
> 2 votes

---
Tags: algorithms, asymptotics, runtime-analysis
---


title: task scheduling optimization problem

text:
# Question
Title: task scheduling optimization problem
I'm interested in such problem. I have a set of $n$ tasks ${T\_i}$ and directed acyclic graph, which nodes correspond to tasks and edges correspond to order of execution two tasks. In other words if I have edge $T\_i \rightarrow T\_j$ it means that task $T\_i$ should be executed in day which strictly before day of execution $T\_j$. All tasks should be executed within $m$ days, every task should be executed exactly once. Execution of task $T\_i$ in day $j$ costs $C\_{ij}$ dollars. There is no restriction on number of tasks executed in one day. I should minimize total cost of execution all tasks.

Can one solve this problem in polynomial time?

My idea is only to bruteforce topological sorting and dynamic programming then, but it is too slow.

**ADD:** I can solve problem, when given DAG is forest. It can be done by simple dynamic programming, where states are $(T\_i, j)$, which means that $T\_i$ is executed in day $j$ and subtree tasks are executed within constraints.

**ADD:** I've read this paper, 13.3 Layer Assignment, p. 417. Also this problem can be formulated in terms of weighted CSP, we need to minimize such value $\sum\limits\_{v \in V}C\_{v \sigma(v)} + \sum\limits\_{(u,v) \in E} D\_{\sigma(u)\sigma(v)}$, where $\sigma(v)$ is day when task $T\_v$ is executed, $D\_{ij} = \begin{cases} 0 &\mbox{if } i \< j \\ \infty & \mbox{if } i \ge j \end{cases}$.

# Answer
These kinds of problems are usually studied under the banner of Operations Research or Operational Research, and this is still an active area after several decades. See the Graham et al. survey from 1979 (doi:10.1016/S0167-5060(08)70356-X) for the standard terminology and many older references. It looks like your problem is $P|\text{prec},p\_{ij}=1|\sum\_j C\_{ij}$ which seems too general to have been studied back then.

You don't describe the kinds of task graphs you work with, but in my experience many practical task graphs from computer science lead to an explosion of chains of tasks to consider, making it hard to do dynamic programming, while task graphs from other fields often are more amenable to dynamic programming. When the structure of the task graph is "nice", then one can do better. For instance, series-parallel task graphs often lead to polynomial-time algorithms.

Without knowing more about the details of your problem, I'd say it sounds NP-hard on general task graphs due to the costs, but it may well be possible to exploit special features of the task graphs (or perhaps the costs) to design an efficient algorithm.
> 1 votes

---
Tags: algorithms, polynomial-time, scheduling
---


# Question
Title: Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?
My best attempt at a specific case of the problem where $n =$ 256:

For a specific case that a RB tree has 256 nodes, we can use the RB tree theorem to deduce that the height of the tree $h \leq 2\*lg(n+1)$ then $h\leq 16$ for $n =$ 256.

But this doesn't exactly help me deduce whether the last row is all black nodes (thereby implication the parent of these black nodes are red)

Can someone hep me carry this further?

# Answer
> 0 votes
Five rules for RB-Trees:

> 1. Every node is black or red,
> 2. Root is black,
> 3. Every leaf is black,
> 4. If a node is red then both its sons are black,
> 5. All paths from a single node to any leaf must contain an equal amount of black nodes.

A common implementation has a NIL leaf set as a parent of root and son (left and right at the same time) of all leaves - in this case the NIL is black, and so it's parents can be black or red (as NIL is the only leaf.) This is the reason for a common misconception that leaves can be any color.

I am almost sure that any RB-Tree containing at least 2 elements (except NIL) will have at least one red node. This is due to an observation of the Insert algorithm. The inserted node is always coloured red at first, but any later modifiaction (if the colouring needs to be repaired) either does not change the colour of the newly added node (so it remains red) or makes at least one other node red.

---
Tags: data-structures, trees, binary-trees, search-trees, balanced-search-trees
---


# Question
Title: Unclear about proof for unique MST given graph G with distinct weights
http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/mst.pdf

I have some trouble understanding the proof above.

I understand that we assuming two MSTs, T and T', and an edge e that is the cheapest edge of G that located in T. Then the weight of this edge is larger than any weight on T', given that T' contains (x,y), by definition of MST.

My question is why do we assume that T' passes through (x,y)? Wouldn't it natural to assume that T' is completely disjoint from T?

# Answer
The edge $e$ is not necessarily the cheapest edge of $G$ that is in $T$. Rather, it is the cheapest edge in the symmetric difference $T \triangle T'$. It could belong to either $T$ or $T'$ (but not both!), but since both cases are the same, we assume that it belongs to $T$ without loss of generality.

We don't need to separately consider the case that $T$ is disjoint from $T'$ and the case that they share some edges. All we need to know is that they are different and so their symmetric difference is not empty.
> 0 votes

---
Tags: graphs, proof-techniques, spanning-trees
---


# Question
Title: If $L$ is a $CFL$, then why isn't $L^*$ also $CFL$
I was studying closure properties of CFLs and I came across this. I want to understand why $L^\*$ is not a CFL, can anyone explain me in depth with simple examples?

# Answer
> 6 votes
In fact, if $L$ is context-free then so is $L^\*$. The easiest way to see that is using context-free grammar. Every context-free language $L$ is generated by some context-free grammar $G$ with starting symbol $S$. Now add a new starting symbol $S'$ and the productions $S' \to S'S|\epsilon$. The new grammar $G'$ is also context-free and generates $L^\*$.

---
Tags: formal-languages, context-free, closure-properties
---


# Question
Title: The significance of bounded parameters in complexity
A lot of complexity results are given with respect to bounded cases where results are more favourable.

For example, the graph isomorphism problem — which is GI-complete in general — is known to be tractable in cases where degree is bounded.

But every time I see such a result, I have a nagging voice in my head telling me that for any input graph the degree must be bounded. I find it hard to intuitively resolve the resulting cognitive dissonance.

I understand that bounding a parameter allows for considering it as a constant rather than a variable in the complexity analysis. But that seems almost like a semantic game since you can still define the bound to be arbitrarily large so long as it's fixed.

Perhaps the message to be gleaned from these bounded results is that if you assume the parameter in question to generally be small, the worst case is more favourable. But this seems rather vague to me since one can define "small" arbitrarily.

The nagging voice tells me I'm still missing something ... that something hasn't clicked.

---

To distil a question out of this: when one sees such a bounded-parameter result, what should one intuitively conclude about the problem in practice with respect to that parameter?

What is the importance of such a result?

# Answer
When you see that a parameter is bounded, you shouldn't think of the value of the parameter of a single graph, but of a class of *all* graphs that satisfy the bound on the parameter.

So, to say that graph isomorphism is in polynomial time for bounded degree graphs really means that, for every $d$, there is a polynomial time algorithm $A\_d$ that decides graph isomorphism on the class of all graphs of degree at most $d$. However, the running time of $A\_d$ depends on $d$.

And, yes, the take-home is generally that there are decent algorithms as long as the parameter is small. What counts as decent will depend on your circumstances: what sorts of inputs you need to deal with and how much computing time you have available.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: Measure two qubits, one from entangled pair, in Bell basis?
In quantum teleportation we require both sender (Alice) and receiver (Bob) to share an entangled pair of qubits in the $|\beta\_{00}\rangle$ Bell state. Then, if Alice wants to teleport a quibt $|v\rangle$ to Bob, she needs to measure $|v\rangle$ and her qubit from an entangled pair in the Bell basis. Such measurment requires her to perform a CNOT on the two qubits with $|v\rangle$ being the control qubit and then apply Hadamard transformation to $|v\rangle$.

I can't understand how can she perform the above. If we represent quantum gates as matrices, what vector would represent the input to the CNOT matrix (the pair $|v\rangle$ and Alice's qubit from an entangled pair?) In other words, how can we represent a pair that Alice wants to apply CNOT to (when performing measurement in the Bell Basis?)

I know that Bell measurement does not require CNOT in general, but this is one of the ways it could be implemented (assuming we just want to get the classical 2-bit value).

My intuition is that because we need to operate on a tensor product of $|v\rangle$ and the entangled pair, we need to create a matrix representing an operation performing CNOT on $v\rangle$ and first qubit from the pair, and I on the second qubit from the pair, so it would be like $CNOT \otimes I$. Is this correct?

# Answer
I figured out that as we are operating on 3 qubits ($|v\rangle$ and $\beta\_{00}\rangle$ pair) and we want to perform CNOT on the first two (if we enumerate like 1- $|v\rangle$, 2- first from pair, 3 - second from pair) it is just like we want to perform $CNOT \otimes I$ on $|v\rangle \otimes |\beta\_{00}\rangle$.

After performing the CNOT described above we need to perform H on the $|v\rangle$ qubit, which is now entangled (as CNOT is an entangling operation), so it is like we want to perform $H \otimes I$ on the three (where $I$ is 3 x 3 identity matrix).

Beaing able to perform both steps described above we are able to perform a measurement of qubit $|v\rangle$ and the first qubit from the entangled pair $|\beta\_{00}\rangle$ in the Bell basis.
> 3 votes

---
Tags: quantum-computing
---


# Question
Title: Are all adjacency matrices represented by 0 and 1s?
Are there any cases when adjacency matrix should have entries other than 0 and 1?

# Answer
> 7 votes
Yes, because the `(i,j)`th entry simply talks about whether or not there *exists* an edge from vertex `i` to vertex `j`, and represents existence by a `1` and non-existence by a `0`.

However, many graph representations store the edge weight instead of `1`s in the matrix. This way, a single matrix can compactly represent both the edges and their weights.

---
Tags: graphs, adjacency-matrix
---


# Question
Title: Are all languages generate by Turing machines countable?
Are all languages generate by Turing machines countable? I know that the set of all TMs are countable, but what about the languages that they generate?

# Answer
Yes. All languages, not only those generated by Turing machines, are countable. This is because they are all subsets of $\Sigma^\*$, and $\Sigma^\*$ itself is countable. However, there are uncountably many languages.
> 3 votes

---
Tags: turing-machines, uncountability
---


# Question
Title: Does amortized complexity always equal to worst case complexity divided by n?
Is it true that given any operation that takes O(f(n)) amount of time, we do this n times in a process, then the amortized cost is O(f(n))/n?

I'm confused because this statement is so simple and applicable, I don't see the need for accounting method or potential method if we can just divide the worst case operation i.e. enlarging a dynamic array or multipop by the times we want the operation to be perfornmed

# Answer
> 7 votes
No, if all we know about an operation is that it takes $O(f(n))$ times, then its amortized time is also $O(f(n))$. Sometimes, however, it is the case that while the worst-case running time is $O(f(n))$, the worst case cannot happen all the time. A good example is dynamic arrays. Suppose we want to maintain an increasing array, but we don't know in advance how big the array is going to be. Therefore we use the following algorithm for inserting an element to the array; in the algorithm, $N$ is the current length the array, and $n$ is the current number of elements in the array, both initialized to $1$:

1. If $n = N$, create a new array of length $2N$, copy the old array into the new array, and free the old array.
2. Add the new element to the end of the array.

When $n \< N$, this operation takes time $O(1)$. However, when $n = N$, we need to copy the entire array, and so it takes $O(n)$. The running time of insertion is therefore not even bounded! Nevertheless, the amortized running time of insertion is $O(1)$. Intuitively, the reason is that the expensive copying operation is very rare.

Indeed, suppose we perform $m$ insertion operations. The expensive operation occurs at the first, second, 4th, 8th, 16th, and so on, insertions, and involve copying $1,2,4,8,16,\ldots,M$ elements, where $M \leq m$. The total number of elements copied is $1+2+4+8+16+\cdots+M = 2M-1 \< 2m$, and so the total running time is $O(2m) + O(m) = O(m)$, the first summand corresponding to the copying operations, the other corresponding to the cheap second step of the algorithm above. The amortized running time is therefore $O(m)/m = O(1)$.

There are several methods to prove upper bounds on the amortized running time, such as the accounting method and the potential method. These are just mathematical tricks that are supposed to help you analyze algorithms, though as the example analyzed above shows, you don't really need to use them formally in order to analyze the amortized running time; it's enough to use the definition of amortized running time. In more complicated cases these methods could be more helpful, though I feel that they are being taught mostly for historical reasons such as their inclusion in some influential textbook.

# Answer
> 1 votes
The method of $O(f(n))/n$ is often called the aggregate analysis. It is useful when we are clear about the operation sequence. The dynamic array and binary counter are typical examples of this kind.

However, sometimes (maybe usually) we don't know the operation sequence and are not able to obtain the $O(f(n))$. Then we need other techniques such as accounting method or potential method.

For the accounting method, you can refer to this post: How can I make sense of amortized accounting method?.

I am not quite familiar with the potential method. It is more sophisticated. Waiting for other answers about it.

---
Tags: amortized-analysis
---


# Question
Title: Time complexity of solving a set of 2-sat instances?
Suppose I have a set of 2-SAT instances, the set is of size $2^{3C}$ for some constant $C$. What is the time complexity of solving all instances using the fastest known 2-SAT solver?

# Answer
Although 3SAT problem is NP-complete, there is a polynomial algorithm making use of the beautiful SCC (Strongly Connected Component) directed graph algorithm.

Suppose there are $n$ variables and $m$ clauses in the 2SAT instance $\mathcal{I}$. The parameters $n$ and $m$ represent the size of $\mathcal{I}$

The 2-SAT instance is modeled by a directed graph $\mathcal{G\_I}$, with

* $2n$ vertices: for each variable $x$ in $\mathcal{I}$, there are two vertices $v\_x$ and $v\_{\bar{x}}$ (i.e., variable and its negation).
* $2m$ edges: for each clause $x \lor y$, there are two directed edges $\bar{x} \to y$ and $\bar{y} \to x$. Note that the latter two implicative forms are equivalent to $x \lor y$.

The polynomial algorithm (it is actually a linear algorithm) proceeds as follows:

1. Obtain the SCCs of $\mathcal{G\_{I}}$ in linear time $O(n + m)$;
2. Assign `True` to each literal (Notice: *not* the variable) in the destination SCC (denoted $SCC\_d$);
3. Delete $SCC\_d$ and its corresponding source SCC ($SCC\_s$). (Note the symmetry in the graph $\mathcal{G\_{I}}$);
4. Repeat (2) and (3) until $\mathcal{G\_{I}}$ is empty.

For example:

$\mathcal{I} = (x\_1 \lor x\_2) \land (\bar{x\_2} \lor x\_3) \land (\bar{x\_1} \lor \bar{x\_2}) \land (x\_3 \lor x\_4) \land (\bar{x\_3} \lor x\_5) \land (\bar{x\_4} \lor \bar{x\_5}) \land (\bar{x\_3} \lor x\_4)$

The graph $\mathcal{G\_{I}}$ is:
> 4 votes

---
Tags: algorithms, search-algorithms
---


# Question
Title: Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?
On wikipedia, there is a proof for the cycle property of the Minimum Spanning Tree as follows:

> Cycle Property: **For any cycle C in the graph, if the weight of an edge e of C is larger than the weights of all other edges of C, then this edge cannot belong to an MST.**
>
> Proof: Assume the contrary, i.e. that e belongs to an MST T1. Then deleting e will break T1 into two subtrees with the two ends of e in different subtrees. The remainder of C reconnects the subtrees, hence there is an edge f of C with ends in different subtrees, i.e., it reconnects the subtrees into a tree T2 with weight less than that of T1, because the weight of f is less than the weight of e.

Why does the proof assume that e belongs to MST? If e belongs to a cycle, and it belongs to MST, doesn't it immediately imply that the MST has a cycle and therefore is not a tree?

Please show me why I am not understanding this proof correctly. i.e. How can we have an edge e already in the tree but the tree remains acyclic?

# Answer
First off to answer your main question: there is no flaw in the proof.

The point where you are not following the reasoning of the proof is that:

* E belongs to a cycle in the graph and to the MST.
* Not every other edge of the cycle are in the MST.

If you look at your drawing, then either one of the edges towards the rest of the MST is redundant. Because not all edges of the cycle are in the graph results in that if you remove E you get two subtrees.

To answer your question about why the proof begins with assuming that e belongs to the MST: Proof by contradiction starts with assuming the opposite of what you are trying to proof. Then you reason with that assumption until you run into a contradiction. A contradiction means that your assumption must be false. If you assumption is false, then the opposite of your assumption is true.

If you just look for images and MST examples there are enough examples with a cycle. Try to follow the reasoning of the proof and you will see why it is sound.
> 10 votes

---
Tags: correctness-proof, spanning-trees
---


# Question
Title: What is the complexity of recurrence $T(n) = T(n-1) + 1/n$
What is the complexity of the follwoing recurrence? $$T(n) = T(n-1) + 1/n$$

I highly suspect the answer to be $O(1)$, because your work reduces by $1$ each time, so by the $n$th time it would be $T(n-n) = T(0)$ and your initial task reduces to 0.

# Answer
> 10 votes
By unfolding $$T(n) = T(n-1) + \frac{1}{n} = T(n-2) + \frac{1}{n} + \frac{1}{n-1} = \dots=T(0) + \sum\_{k=1}^{n} \frac{1}{k}$$ Now we can easily approximate the sum on the RHS using that $$\sum\_{k=1}^{n}\frac{1}{k} \le 1 + \int\_{1}^{n}\frac{1}{x} dx = 1+ \log{n} - \log{1} = 1+ \log{n}$$ Therefore $T(n) \equiv O(\log{n})$

# Answer
> 1 votes
## Edit

This answer assumed that the OP was looking for the time-complexity of an algorithm that would evaluate the recurrence, so it's probably wrong.

---

Whatever you do, you *have* to iterate $n$ times, whatever the base case/starting value. So as $n$ grows without bound, the number of operations also grows linearly with $n$ - implying that the recurrence is $O(n)$.

Look at it this way: To calculate $T(n)$, you need $T(n-1)$, which in turn depends on $T(n-2)$, and so on all way till $T(0)$ (or whatever the lowest allowed value of $n$ is).

Each time, you calculate $\frac{1}{k}$ and add it to the next lower value of $T(k)$, doing $O(1)$ work each time, $n$ times - which adds up to $O(n)$ complexity.

---

In fact, you can easily represent $T(n)$ in general as

$$ T(n) = T(0) + \sum^n\_{k=1}{\frac{1}{k}} $$

(which, if you're curious, is equal to $T(0) +H\_n$, where $H\_n$ is the $n$th harmonic number.)

---
Tags: time-complexity
---


title: The number of maximal independent sets

text:
# Question
Title: The number of maximal independent sets
An independent set is a set of vertices in a graph, no two of which are adjacent. A maximal independent set is an independent set that you can not add any vertex. I want to know if the number of all maximal independent set is an exponential number.

# Answer
Yes, consider the graph that consists of vertices $v\_1,\ldots,v\_{2n}$ and edges $(v\_1,v\_2),(v\_3,v\_4),\ldots,(v\_{2n-1},v\_{2n})$. This graph has exactly $2^n$ maximal independent sets, because for each $0\leq i\leq n-1$, we can either choose the vertex $v\_{2i}$ or $v\_{2i+1}$.
> 4 votes

---
Tags: graphs
---


# Question
Title: Calculating the number of unique BST generatable from n keys, why is my number so large
I want to find the number of distinct BSTs I can get with 3 unique keys (i.e. 1, 2, 3)

Here's my solution:

* In case 1, we have each node have possibility, 3, 2, 1, respectively, so 3\*2\*1 = 6 ways
* In case 2, we have the same situation, the top node can be 1, 2, 3, three choices, second node two choices, so and so forth, so I get 6 ways
* In case 3, it is same to case 2 and I get 6 ways

In the end I have 6 + 6 + 6 number of the beast = 18 different threes.

(Edited!)

Why does this answer from Stackoverflow based on so called Catalan Number only give me 5 trees?

# Answer
> 3 votes
You overcounted some of the trees and left out two other possibilities. In your Case 1, for example, there is only one possible BST of that form, namely the one with 2 in the root, 1 in the left subtree and 3 in the right subtree (the leftmost tree below). Remember that you have to maintain the binary search tree condition: a node with value $k$ must have each of the values in its left subtree less than or equal to $k$ and each of the values in the right subtree must be greater than or equal to $k$. As a consequence, a BST with node values $\\{1, 2, \dotsc,n\\}$ must have inorder traversal equal to $\langle1, 2, \dotsc,n\rangle$. When $n=3$, then, we'll have these five BSTS:

# Answer
> 1 votes
The catalan number $C\_n$ is equal to the number of binary trees with $n$ *internal* nodes, where every node has degree $0$ or $2$. It does *not* consider the keys in the nodes, it looks only at the structure.

There is an error in your calculation, namely that the result should be 6+6+6, not 6\*6\*6.

---
Tags: trees, probability-theory, permutations
---


title: How can I learn about CS?

text:
# Question
Title: How can I learn about CS?
I am an Junior in college and I have come to the realization that my school didn't to that good of a job of actually teaching real CS to the students. On my own, I have become a fairly proficient programmer, but I know I would be a lot better If I was more confident in my ability to swim on a lower level of the stack. I hardly know any C. (The syntax is easy, but I've never actually implemented anything in it besides some 100 level HW problems. I see this as a problem because so much is written in C.)

I want to be:

* better at discrete math
* More versed in algorithms
* Have a more intimate understanding of how the higher level tools that I rely on actually work.

Basically, I know how to use logic, but I have become dependent on high level tools and I don't like that.

I also suck at math. I mean I understand it conceptually, and Im comfortable with set theory, so, Python's data structures are really all I need, but I want to be better at algorithms and math is necessary for that.

Are there any websites or other resources that stress an approach like this.

# Answer
> 3 votes
Here are a few books I recommend:

**Discrete math**: *Concrete Mathematics: A Foundation for Computer Science,* Don Knuth. (http://www.amazon.com/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025).

It's very complete and also pretty approachable for someone without much of a theoretical math background.

**Algorithms:** *Algorithms,* Kevin Wayne and Bob Sedgwick. Again, very complete and presents all algorithms with motivation and extremely well-written Java code. There's also a really good website with a lot of the info available for free (http://algs4.cs.princeton.edu/home/).

**Systems:** *Computer Systems: A Programmer's Perspective,* Bryant and O'Halloran. This one is a little more dense than the two above, but it's a great resource if you know what you want to learn about (e.g. processes, floating point arithmetic). (http://www.amazon.com/Computer-Systems-Programmers-Perspective-Edition/dp/0136108040)

I've had experience with all of these at the undergrad level, so they don't require an enormous amount of experience or higher-level coursework.

---
Tags: computability, data-structures, discrete-mathematics
---


# Question
Title: Do all greedy algorithm produce just the first solution, no matter how bad it is?
In all the exampls of the greedy algorithms I've seen so far, such as activity selection problem and unit-sized set coverage problem, the algorithm is usually very simple and intuitive and returns the first set that satisfies the constrain under greedy strategy.

For example, in the activity selection problem, all we need to do is to go down the list and keep finding solution of the type $d\_i$ \> $f\_j$, and the first list that returns (even if it is near empty) is considered the greedy solution.

My question is that this strategy doesn't even take into consideration of any other case which may be better, is this the signature of greedy algorithm?

Thanks

# Answer
Yes, this is the idea of greedy algorithms, also known as myopic algorithms. There is still a lot of freedom in deciding what the myopic choice is based on. Allan Borodin has developed a theory of *priority algorithms* formalizing the notion of greedy algorithm. Such a theory can be used to analyze what greedy algorithms *cannot* do.

Sometimes greedy algorithms give good results, sometimes they don't. When they do, the corresponding algorithm is very simple and fast. When they don't, we have to use more complicated algorithms. Here *good results* doesn't necessarily mean optimal results. The greedy algorithm for maximum coverage doesn't produce optimal results, only a $1-1/e$ approxmation – but this is also the best one can do in polynomial time (in the worst case), so the greedy algorithm is optimal with respect to the worst case approximation ratio.
> 6 votes

# Answer
interestingly there are two simple greedy algorithms that produce optimal solutions, and others exist. they produce the 1st solution which is also optimal. one way to understand this is to think about global vs local optima. if there is only one global optima, it is also a local optima, and a greedy algorithm can find it.
> 2 votes

---
Tags: algorithms, greedy-algorithms
---


title: Understanding Instruction Cycle?

text:
# Question
Title: Understanding Instruction Cycle?
A basic instruction cycle consists of these 5 stages.

> ## Instruction Cycle
>
> 1. IF - Instruction Fetch
> 2. RD - Instruction Decode and Register Read
> 3. EX - Execute
> 4. MA - Memory Access
> 5. WB - Write Back

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

Over Internet what I've found is this

> MA(Memory Access) does following operation
>
> * If load or store instruction, then access memory
> * If branch instruction, replace PC with destination address

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

Suppose we have load and store instruction like this $$(I) R\_1 \leftarrow m\[A\_1\]$$ $$(II) m\[A\_2\] \rightarrow R\_2$$

what will the MA stage do for the above instructions?

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

---
Tags: computer-architecture
---


# Question
Title: Is order of bits in byte really not of concern?
What I can't wrap my head around is sentence repeated everywhere I look, that order of bits in byte is not important(not of my, as a programmer, concern). My question then is if there is possibility that it makes difference?

For example, I crate a binary file with just 0x1 in it (represented on my machine as 00000001). What keeps other machine to read the same byte as 128(10000000) ? Is there standard for msb placement in file, memory that guarantees compability or am I missing something trivial/obvious along?

EDIT: Thanks to dirk5959's answer I found out that my machine is little-endian for bytes and the same is for bits in byte. Additional question is, if it is a rule or there is some architecture that behaves different?

# Answer
Bytes are transferred from memory to disk using an I/O protocol (e.g. SCSI) that specifies the bit order of transmission in the case of a serial protocol, or for parallel protocols specifies which pin upon which each bit in a byte should be transmitted. For bytes moved from memory over the network, the network link level protocol (e.g. Ethernet) specifies the bit order. In either instance, an application programmer need not concern herself with the details; the operating system in concert with disk or network controllers will maintain the correct bit order end-to-end so that the correct values are transmitted/received or store/retrieved.

N.B.: byte order is another matter altogether.
> 9 votes

# Answer
Your sources are probably referring to the fact that, as a high-level programmer, you usually can't access the machine representation of bits in a byte. Even when you perform bitwise operations (like bitwise and or shift) you're manipulating standard binary representations of bytes, not necessarily the bit representation of bytes in your computer.

See https://stackoverflow.com/questions/16803397/can-endianness-refer-to-bits-order-in-a-byte.
> 6 votes

# Answer
Basically, if you are programming at any level higher than assembly then you do not need to care (with really few exceptions) about the order of bits. Files' structures and number representation in the CPU are separate things. In general it is CPU's (or its IO system's) job to prepare the numbers for operations and save them in a way the programmer wants it to.

Little-endian machines got quite popular as there are some bit-wise tricks that are easier to perform with such representation. However, there are many processors with other approaches. While x86 are typically little-endian, ARM processors often have the selector, so the programmer can choose if they want numbers to be represented in little or big endian.

Anyway, any level of abstraction higher than assembly takes care of converting the numbers from human-desired to CPU-understanded way and back again. And you should not mess up low-level stuff into high-level concepts unless it is absolutely necessary (and it rarely is.)
> 2 votes

---
Tags: computer-architecture, memory-access
---


# Question
Title: How to learn computer science the right way
I looked through the sites and this seems to be the best place to ask this question. I am sure it has been asked 10000 times but I am looking for a tailored answer to me and my situation. I currently work as a project manager for a startup. I have a working knowledge into many different fields ranging from HTML, CSS, PHP, JS, MySQL, Server Administration, Marketing, SEO, Etc. I have been working in the web development industry for the last 10 years, I started when I was 11. I have associates level education but no BCS. I don't have the time right now to pursue that as much as I would love to in my current situation(newborn son) and my wife is pursuing her eduction currently. I knew all these language but I don't really know them. I wanna truly understand them, why they work the way they do and how I can master them. This is more of a personal desire then one driven by money, as they most likely wont affect my career. I really would like to learn a new language.

I have about 3-5 hours every week night while I have my son and my wife is in school to study at home. I can't really afford college or guarantee that I will have that time available to make that commitment so I would like to have a no pressure solution. I have completed a lot of treehouse and didn't find much of a challenge. The courses really didnt drive into the languages either and teach me anything new.

I am looking to start learning things like computer logic, but I need some pointers of where to start and what terms to search to find this education info. After I truly understand the inner workings of a computer from the microprocessor to ram to harddrive to interpreter to etc, I would like to learn a new programming language. My current PHP skills arent great, and its more of a working knowledge then understand so treat me as a new programmer.

To sum things up

* Can I have some recommendations of key concepts to learn for new software engineers
* If anyone can provide good education sources, please do so
* I would like some recommendations of languages to learn that are in demand and are new, and arent going anywhere anytime soon. From my current research it looks like Java or C# are my best options. Anything I should know about those, any assume the previous questions apply to them.
* I am willing to pay for this

# Answer
> 1 votes
Firstly, most of the things you are talking about fall under the category of *programming*, rather than *computer science*. Programming is a useful tool for computer scientists, and indeed some computer scientists study programming, but it programming barely scratches the surface of what computer science is about.

Why not try a free online course, such as one offered by coursera? There are many many courses, from programming to theory to machine learning to software engineering. All are free and typically the standard of quality is extremely high.

# Answer
> 1 votes
Here are some things that apply to any field of programming

* Object Oriented Design and Design Patterns
* Algorithms and Data Structures

There is a wealth of free resources to learn now a days. For instance both MIT and Stanford offer free resources online where you can watch video recordings of the lectures.

---
Tags: programming-languages, software-engineering, java
---


title: Hamming and BCH codes

text:
# Question
Title: Hamming and BCH codes
Why are Hamming codes the best 1-error-correcting codes? I need references. I know that hamming codes are the best 1-error-correcting codes but I want to know why they are best?

# Answer
The Hamming codes are optimal in the sense that among all codes with the same block length and minimal distance, they contain the most number of codewords. We know this because Hamming codes are perfect codes: their number of codewords matches the Hamming bound, which is an upper bound on the number of codewords in a code with given block length and minimal distance.
> 2 votes

---
Tags: coding-theory, error-correcting-codes, hamming-code
---


# Question
Title: Why do heuristic functions only approximate the real value of the cost?
As stated in the title I'm wondering why do heuristic functions only approximate the real value of the cost? I understand it can never overestimate, but can it ensure the cost is accurate?

# Answer
If you create a heuristic that returns the exact cost for *each* node in the search tree, you can find the optimal solution easily: Start at the initial state and generate all successor states. Take the state with the best heuristic value and repeat, until you find the goal state. Because the estimated cost (from the heuristic) for each node in the search tree is equal to the actual cost, you never make a wrong decision.

Unfortunately for most problems constructing such a heuristic would mean that for each node to evaluate you calculate the solution and then return the cost of the solution. Thus you already solve your problem inside the heuristic function.
> 4 votes

---
Tags: artificial-intelligence, search-algorithms, heuristics
---


# Question
Title: Complexity Analysis for a nested loop with two methods
Hey I am studying for my intro algorithms class final and I'm not sure if I'm understanding this question correctly (its from a sample final exam). If someone could explain this to me that would be awesome.

The following code processes A which is an n-by-n matrix of ints. The method nextInt() is O(1), and the method findMax() is O(n). What is the complexity of the given code as a function of the problem size n? Show the details of your analysis.

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

    for(int j = 0; j < n; j++)
        A[i][j] = random.nextInt();

    System.out.println(findMax(A[i]));
}

```

Without the methods the for loop complexity is O(n^2). Now the random.nextInt() complexity is O(1) but it is run n^n time does this effect the complexity of this. Sorry I'm a little sleep deprive. If someone can help me answer this question that would be awesome

# Answer
> 2 votes
Here are a few hints:

1) Nothing is run n^n times (statement in the inner loop will be run O(n^2) times).

2) To figure out the complexity of an algorithm using order-of-growth (big 'Oh') notation, you just need to figure out the complexity of the highest-complexity procedure. For example, the complexity of the following is O(n^2), even though the first statement has complexity O(n).

```
System.out.println(findMax(A[i]));  <-- O(n)

for (int i = 0; i < N; i++) { <- O(N)
    for (int j = 0; j < N; j++) { <- O(N)
        System.out.println("Something useless"); <- O(1)
    }
}

```

3) Why is the "loop complexity" O(n^2)? Because you're running running an O(n) process within an O(n) process. What does the same logic tell you about the complexity of the inner loop operation (A\[i\]\[j\] = random.nextInt();); how many times is the O(1) process nextInt run?

---
Tags: algorithms, algorithm-analysis, asymptotics, runtime-analysis, loops
---


# Question
Title: Why is the CPU Involved During Keyboard Echo?
I'm currently studying for a computer science exam, and I've come across a concept that has me somewhat stumped.

> When one types a key on the keyboard, an ASCII character is transmitted to the CPU. Upon reception of this character, the CPU outputs the same character to the screen. This process is called echoing. Instead of having the CPU involved, why don’t we simply have this echoing process done within the keyboard/screen unit so that the CPU is free to do other useful work?

Now, intuitively, I feel like this is because there is no defined keyboard/screen unit, and the CPU is the device which is responsible for communicating between the screen and the keyboard, through the interconnection network. However, I feel like the fact that a keyboard/screen unit is mentioned may mean I'm missing an important concept. Is this the case? Why do we involve the CPU in the echo process?

# Answer
**Letting the computer see each character as it is typed allows programmers to make the user interface more dynamic.**

Back when a serious computer was the size of several upright refrigerators and computers operated on user input a line at a time, terminal input was handled as you described. You typed a line of text on a terminal which displayed it locally (often on paper). Only when you pressed the ENTER or RETURN key was the text sent to the mainframe or minicomputer to be processed.

But even back then, the advantage of letting the computer see the user input early was realized by the engineers of the time. Command completion, where you type the first few letters of a command and the computer fills in the rest, was invented in the mid 1960's. This feature was copied and improved through the years to where it stands today, available in all modern UNIX shells and under Windows as well.

Allowing the CPU to see each character as it is typed also allows shells to offer command line editing and history features well beyond what a dumb terminal could provide. A key can allow you to step back through a list of commands you've previously typed, choose one, and then edit it slightly before pressing RETURN to have it executed. Text can be cut and pasted between command lines, possible because the CPU has access to previous commands while the terminal does not. Filenames as well as commands can be completed based on partial input, again possible because the CPU has access to the names of files in the filesystem and the terminal does not.
> 6 votes

# Answer
**Letting the computer see each character as it is typed is NOT NECESSARILY NEEDED to make the user interface more dynamic.**

Old ASCII terminals came usually as one keyboard+screen package, or keyboard+printing head (called then often a teletype). So local echoing was possible. Input was sent as whole lines, and that is what the enter key was for (it was also called carriage-return). This was convenient when your terminal was connected through slow telephone lines to a distant computer. I still have a 300 bauds modem I used then, which is a bit less than 300 bits/second. And that was not the slowest I used. You did not want to wait for the echo.

Kyles Jones gave you a few good reasons to have the echo controled by the computer. Such as history and command line editing. But even these reasons could be overcome with local echoing. My old ascii screen terminal (bought in 1980 and which I no longer dare connect to an outlet as the capacitors must be in a sorry state) had (still has) about 12 screens (a screen is 24 lines of 80 characters) worth of history, and local editing facilities: the terminal had its own local CPU ... I am not sure that is what you had in mind. This is all from memory, so I hope it is close to truth, but searching for the manual would take me some time.

So, basically I had a user-interface computer connected to another computer. Actually, there always will be some hardware to handle the echoing, so your question is more whether it is appropriate to have sophisticated hardware to do that with a CPU or with simpler hardware (not able to do sophisticated work). The builders of my terminal thought it was appropriate, and made it a sophisticated terminal, with the dumb communication protocol with the computer that was then standard.

I first thought of saying that a good reason to go through the CPU would be that applications now use windows with all kinds of features and differents fonts, and that that requires the power of the computer to get the appropriate flexibility, that a simple screen-keyboard cannot offer.

But I recalled in time (memory is hard to recollect) that this is false. In the early 1980, people were developing bitmap graphics (that was the name for the kind of screen you are now using, though it was CRT rathed than LCD). Some of the work followed the traditional terminal view, making very sophisticated graphic terminals with multiple windoes and fonts, etc. One of these was the BLIT, that was the subject of many experiments, such as Cardelli's infamous crabs.

That does not necessarily mean that the CPU running the application did not see the characters. But it did not have to. The terminal was powerful enough to do very complex work on its own.

Computer architecture has been testing many solutions, especially as faster networks became available. You are concerned with the terminal, but at some points, it was the disk that was an issue (mostly price, I think, and also management). So we had for a time diskless work-station (i.e. personal computers). They would include CPU, screen, keyboard and RAM, but no disk. Disk space was on the network, and you just requested file space from the network. Even virtual memory swapping was done through the network.

So the conslusion is: sophisticated interface (for example), using windows, various fonts, programmable keys, command-line editing, synchronisation between input and output, and what not, does require some real processing power. Even with very weak capabilities, some hardware is needed. Then this computing power may be attached to the computer and its CPU, or may be independent from it and connected more or less remotely. The same may be true of other resources.

But everything is very relative.

Last remark. The first alphanumeric screen terminal I ever used was a Tektronix in 1974, that came with its keyboard. The screen and the keyboard were so tightly connected, that we had to pay someone to modify it by changing the circuitry with a soldering iron so that it would behave as needed. But I should stop my endless stream of stories.
> 4 votes

# Answer
How could the CPU *not* be involved? How would the computer know whether to print anything at all to the screen without the CPU being involved? How would it know where to print the character? How would it know what font to use? How would it know how to render that font?
> -1 votes

---
Tags: computer-architecture, operating-systems, user-interface
---


# Question
Title: What is the optimal strategy for filtering a large collection of items with multiple filter functions?
I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve looping over every item in the collection and applying each filter to each item. An item will be rejected early if any one of the filters fails during this process.

Each filter has a runtime that varies significantly. And, we know a-priori what percent of the collection each filter will filter out. Given this, how do I find the ordering I should apply my filters to each item with the fasted expected run-time overall?

For example, filter A runs in 5 ms and filters out 50% of the collection on average. Filter B runs in 1 ms and filters out 25% of the collection on average. From this, we know that ordering A,B gives 5 + 0.5 * 1 = 5.5 ms average runtime, and B,A gives 1 + 0.75 * 5 = 4.75 ms average runtime. So B,A is our fastest ordering.

I think this admits a dynamic programming solution (since fastest ordering is runtime of first filter + (1 - filter fraction) * (optimal ordering of the rest), but I was wondering if this problem has a name and has been studied before? Could somebody point me to any papers?

EDIT: also, I forgot that the probability of filtering and the run-times will be correlated between filters, so my analysis above is wrong and the problem is harder. I think I can solve this with enough time but I want to catch up on prior-work before I start, if there is any (it seems like it could be a common problem). I haven't had any luck finding anything so far though.

# Answer
## Independent filters

If the filters are independent, a greedy algorithm can be used to find the optimal order. Sort the filters by increasing value of $t/p$, where $t$ is the time to run the filter and $p$ is the fraction of items that are filtered out by the filter. This gives the optimal order.

To give some intuition for why this might be a plausible answer: ideally, we'd prefer filters that take less time; and ideally, we'd prefer filters that filter out a higher fraction of items. Intuitively, you can see how $t/p$ somehow incorporates both of those.

A formal proof of optimality involves an exchange argument. I won't detail the proof here, as it can be derived easily using standard techniques. For a detailed writeup of the proof, see Determine what is the best order for running filters on a dataset.

---

## Correlated filters

If there can be correlations between the filters (i.e., they are not independent), the optimal order cannot be determined from the information provided without knowledge of the correlations.

Here's an example, based on making a small modification to your example. Suppose we have two filters, filter A and filter B. Suppose filter A runs in 4.5ms and filters out 50% on average; filter B runs in 1ms and filters out 25% on average. Also suppose that anything filtered out by filter B is also filtered out by filter A. Then the optimal order is to just do filter A. Your formulas give A,B: $4.5+0.5 \times 1 = 5.0$ and B,A: $1 + 0.75 \times 4.5 = 4.375$, so your formulas might make B,A look like the best choice -- but in fact just doing A alone is even better.

---

Unfortunately, in practice I would expect that filters might often be correlated. To deal with this, you'd need to know some information about the correlation structure. If you don't have any information on the correlation structure, one possible approach is to use the greedy strategy, recognizing that it might not be optimal for your particular situation. Another possible approach is to gather data on the correlation structure and then use that additional information to try to find a better order, though this may not admit as clean of an answer.
> 4 votes

---
Tags: algorithms, optimization, combinatorics, greedy-algorithms
---


# Question
Title: Operation with same asymptotic cost on hash tables and lists
Let $x \in \\{ \log n, n, \dots , n!\\}$ some (cost) function.

Are there interesting operations with runtime in $O(x)$ on *lists* which also have runtime in $O(x)$ on *hash tables*?

# Answer
> 2 votes
Lookup (testing whether the list/table contains a particular element $v$) takes $O(n)$ time in a list and $O(n)$ time in a hash table, in the worst case. So, the worst-case running time is the same for both data structures.

---
Tags: data-structures, hash-tables, lists
---


# Question
Title: Modified Bellman Ford to find minmum cost cycle in O(E²V) time?
I'm thinking about how you can modify Bellman Ford a bit to calculate the minimum weight cycle in an undirected graph with positive weights. Note that the constraint is that the algorithm must run in $O(VE^2)$ times, and Bellman Ford runs $O(VE)$ time so we are looking at a modification that runs $O(E)$

My approach is first make a directed graph by doubling the edges in both directions, then run Bellman Ford to come up with the shortest path, then compute the strongly connected components in this graph. After you have a tree of strongly connected components, calculate the weights around the perimeter of the SCC and then compare the weights. But I'm not sure how you could calculate SCC using Bellman Ford and this algorithm is going to take too long.

Does anyone see an obvious solution?

# Answer
Some hints for you, so you can solve your own exercise:

* If the graph has a negative-weight cycle, what is the proper answer? Can you detect this situation?
* If the minimum-weight cycle has positive weight (strictly greater than zero), how could you find it? If you knew the distance between every pair of vertices, could you use that to help you find the minimum-weight cycle in this case? Does that suggest an algorithm that could handle this case?
* If the minimum-weight cycle has zero weight, can you detect this fact? What could you do in this situation?
> 1 votes

---
Tags: algorithms, graphs, search-algorithms, shortest-path
---


# Question
Title: How can I calculate tree sizes to "stretch up" a finger tree?
I've been working on implementing an efficient Cartesian product operation (actually the `<*>` operation, but it amounts to about the same thing) for sequences based on Hinze and Paterson's "Finger trees: a simple general-purpose data structure". It seems that a natural way to calculate $xs \times ys$ when $xs$ and $ys$ each has at least two elements is to (conceptually) replace each leaf $x$ in $xs$ with a 2-3 tree representing $\\{(x,y)\mid y \in ys\\}$, and then "stretch" the first and last element of the resulting tree upwards/outwards to bring the tree to the proper depth. But for efficiency and other reasons, this actually needs to be done in the opposite direction—I'd need to pull off the first and last element of $xs$, and then work my way down, calculating at each level how much of $ys$ to leave behind there, and also to check whether it's possible to represent $ys$ by a 2-3 tree of the appropriate size for that level. I'm not really sure how to get a grip on the necessary math.

# Answer
As it turns out, the best way to calculate the necessary tree sizes is *not to*. While crushing down one copy of the $ys$ finger tree (in a process reminiscent of "zipping" a Huet zipper), I can simultaneously crush down just *one side* of each of two additional copies, while pulling digits off the other sides to use *directly* (no calculation!). When I get near the bottom, I finish off the complete 2-3 tree, and then attach the two crushed half-trees to the $xs$ finger tree (once I've replaced its leaves using the complete 2-3 tree).

### Edit (March, 2015)

The code (recently simplified and cleaned up) can be found in the GitHub repository. Both the `<*>` and `*>` implementations now use this technique; the latter takes advantage of Louis Wasserman's `applicativeTree` function to obtain asymptotic reductions in time and allocation.
> 1 votes

---
Tags: data-structures, search-trees
---


# Question
Title: Fast implementation of basic addition algorithm
> Write code for a modified version of the Grade School addition algorithm that adds the integer one to an m-digit integer. Thus, this modified algorithm does not even need a second number being added. Design the algorithm to be fast, so that it avoids doing excessive work on carries of zero.

I encountered this question looking over last year's final for my algorithms course. I'm not really sure how to answer it, although it seems like it isn't a very challenging question.

# Answer
> 0 votes
To slightly expand on @greybeard's answer, here are a few hints:

1. Start adding from the right, as usual.
2. When can you stop? Obviously, when you don't have a carry. When will that happen?
3. When do you have to look at the next digit? Obviously, when you have a carry. When will that happen?

Challenge: show that the average number of steps this algorithm will take on an $m$-digit number represented in base $b$ is less than $b/(b-1)$.

# Answer
> 0 votes
In a positional number system, there is one highest digit; every other has a successor in the set of digits. At the (low-significant) end of the sequence of digits (the integer's representation), there is either one of those other digits, or a sequence of that highest one.

---
Tags: algorithms, arithmetic
---


# Question
Title: Can anybody explain intuitively why quick sort need log(n) extra space and mergesort need n?
I've searched on internet and everybody said it's stack space needed on recursion. I know log(n) extra space for quick sort happened when use in place, but still I don't get it. Anybody can explain intuitively why quick sort need log(n) extra space and mergesort need n? Thanks.

# Answer
**Quicksort:** For quicksort, your intuition about recursion requiring O(log(n)) space is correct. Since quicksort calls itself on the order of log(n) times (in the average case, worst case number of calls is O(n)), at each recursive call a new stack frame of constant size must be allocated. Hence the O(log(n)) space complexity.

**Mergesort:** Since mergesort also calls itself on the order of log(n) times, why the O(n) space requirement? The extra space comes from the merge operation. Most implementations of merge use an auxiliary array with length equal to the length of the merged result, since in-place merges are very complicated. In other words, to merge two sorted arrays of length n/2, most merges will use an auxiliary array of length n. The final step of mergesort does exactly this merge, hence the O(n) space requirement.

To see exactly how the auxiliary array is used, check out this implementation of merge.

**Summary:** The key difference between the two lies in the space requirement of the operation performed at each recursive step. The partition step used in quicksort is an in-place operation, while merging usually requires an auxiliary array.
> 14 votes

---
Tags: algorithm-analysis, sorting, space-analysis
---


# Question
Title: How to enumerate minimal covers of a set
I have a set $S$ and a set $P = \\{P\_{1},...,P\_{n}\\}$ with $\bigcup P\_{i} = S$. I want to find all the inclusion-minimal subsets of $P$ that are covers of $S$.

What is the best algorithm for enumerating all the inclusion-minimal covers of $S$ contained in a set $P$ and what is its running time?

**Additional information** : The algorithm must work in the general case. $|S|$ and $n$ can be anything. I need to enumerate the exact set of all the inclusion-minimal covers of $S$ contained in $P$. Obviously, it is possible to find the first one in polynomial time by just removing elements of $P$. The second one could be found easily by using the same method starting with the different $P\setminus \\{P\_{i}\\}$ with $P\_{i}$ an element of the first cover.

I don't really hope for a polynomial delay algorithm but I would be really happy with an incremental polynomial delay, if such a thing exists.

# Answer
The problem is equivalent to translating a monotone conjunctive normal form Boolean formula to a monotone disjunctive normal form Boolean formula (also called "monotone dualization" in the literature).

Let us for example take $P = \\{\\{x,z\\}, \\{x,a\\}, \\{y,z \\}, \\{y,c\\}\\}$. We can translate $P$ to the following boolean formula: $ \psi = (x \vee z) \wedge (x \vee a) \wedge (y \vee z) \wedge (y \vee c)$ and ask for a valuation of the variables that makes the formula valid, but has as few as possible variables set to true as possible.

If we translate $\psi$ to disjunctive normal form, we obtain: $$\psi' = (x \wedge y) \vee (x \wedge z \wedge c) \wedge (z \wedge a \wedge c)$$ It is now easy to list all ''minimal'' solutions to $\psi \equiv \psi'$.

The paper "Computational aspects of monotone dualization: A brief survey" by Thomas Eitera, Kazuhisa Makinob, and Georg Gottlob contains a nice survey on existing literature to the topic, including algorithms and complexity results.
> 1 votes

# Answer
You should not expect an asymptotically efficient solution to your problem, for two reasons:

1. As Yuval mentions, there can be exponentially many covers. Therefore, merely printing out the answer can take exponential time in the worst case.
2. Your problem is NP-hard. Finding the smallest such cover is the NP-hard set cover problem, and your problem is at least as hard as that.

Consequently, you should not expect an asymptotically efficient algorithm that is general (works correctly for all inputs).

So, you have several options: accept exponential-time algorithms; try to find some special structure in your problem instance, and look for an algorithm that exploits that structure; seek an approximation algorithm; look for a heuristic that might not give an optimal answer. The next step will depend on your problem domain, and is up to you. See, e.g., NP-complete decision problems - how close can we come to a solution?.

Note that there is a natural way to express your problem as an instance of SAT, so you could express it as SAT instance (a boolean formula $\varphi$) and then use a SAT solver to find all satisfying assignments to that formula. See, e.g., Set cover problem and the existence of such cover and Variation of Set Cover Problem: Finding a maximum-sized collection of disjoint set-covers and Maximum minimal set coverage.
> 1 votes

---
Tags: algorithms, reference-request, enumeration, set-cover
---


# Question
Title: Languages of cardinality higher than $\aleph_0$
I was studying model theory and that's how I came across formal languages. I looked around but it seems as though a language (set of strings over some alphabet) is usually treated as being finite or countable. Just wondering if languages of higher cardinality have been investigated. Any references would be nice.

Thank you!

**EDIT:** I found an answer. Infinitary logic deals with just such a question. See here. It allows formulas of infinite length, so the collection of all such formulas could be uncountable. I guess in the CS world a formula is simply a legally formed word (based on some rules). The set of all such legal formulas could be uncountable.

I'm choosing to leave this question here as it might help another beginner like myself.

**EDIT 2:** Another way maths allows uncountable languages is to allow uncountably many symbols in the signature (which would be a subset of alphabet in the CS world). So even if formulas (i.e. words) can only be finitely long, there can be uncountably many of them.

I've realized the question isn't so much about formal languages as it is about logic. It was due to my ignorance that I posted the question here. My humble apologies!

# Answer
In traditional Formal Language theory, all languages are countable. This is because they're defined as a subset of $\Sigma^\*$, so they always contain strings of finite length, meaning we can map them to integers.

We rarely deal with finite languages, since all finite languages are regular, and therefore trivially decidable.

There has been research into the computability of functions on real numbers. The difficulty here is that in practice, there's no single way to represent arbitrary real numbers. A common method is looking at, given a real-valued function $f$, inputs $\vec{x} $ and an integer $n$, can we use a Turing Machine to compute a representation $f(\vec{x})$ to $n$ digits of precision?

You could view a real number as justing being a function taking $0$ arguments, so a real number $r$ is can be seen as a function from $n$ to the first $n$ binary digits of $r$.

Interestingly, since Turing Machines are finite, the set of all Turing Machines is countable, so the set of all computable real numbers is countable, meaning there are many more uncomputable reals than computable ones.

For more info, see http://en.wikipedia.org/wiki/Computable\_number.

Note that there's also a concept of automata on infinite words, used in formal language theory and program verification. These languages can be uncountable: an infinite sequence of $0$s and $1$s is equivalent to a subset of $\mathbb{N}$ so an automaton that accepts all such words accepts an uncountable language.
> 6 votes

# Answer
The answer by jmite tells you what is being done in computer science.

The point of it is that it is primarily devoted to algorithm and computation, as ways of solving problems. Hence it is also tightly connected with proof theory, and the logical work in the late 19th and early 20th century.

To a large extent, it is a theory of syntax, as all we do in mathematics is to push symbols around according to specific rule. Of course, as you know, there is semantics behind the symbols and their assembly into sentences, but the only way to refer to the semantics is through the symbols.

In a way, it is a physical theory, as much as a mathematical one. It is about what we can express in this physical world, as human being, or using machines. It is about computation, which is also called calculus (not to be confused with differential and integral calculus), which comes from counting stones in Latin. Our first interest is then to develop what seems physically meaningful.

Of course, there are probably many ways to extend it, such as hypothesizing computable solutions to problems even though none actually exists, which is somewhat like adding an axiom that has no physical model. It is a bit like science-fiction: we can talk about the extension, and what it can do , and how that would change the world. But we cannot actually use it and do those things.

So, nearly everything we do in practice is finite, but often cannot be bounded meaningfully. Working up to denumerable infinity turned out to be the most convenient way to address efficiently that situation. We often consider "infinite" structures, but in the end they are only limits of uniformly computable finite approximations, which keeps us in the denumerable world.

The case of computable reals is interesting. They are (isomorphic to) a subset of the usual reals, but defined as computable limits, hence characterized by whatever machine computes the approximations. In the end, each is characterised by a finite definition, which makes them denumerable. The interesting point is that you can do with computable reals practically all you do with the classical ones. See for example "To what extent can the mathematics of Reals be applied to Computable Reals?"

My guess, but it is only a guess, is that the same is probably true of infinitiary logic (of which I know only what you said). If you are careful to consider only computable strings on infinite length, you will stay in the denumerable realm, but you can probably adapt all definitions to get whatever nice properties you expect from infinitiary logic. And, as a bonus, it may have physical sense.
> 5 votes

---
Tags: formal-languages
---


# Question
Title: Using A* search with different heuristic values
I am currently trying to use A\* to create cyclical routes (for plotting driving routes of set distances). I want to find a driving route from my start location that is as close to my specified length as possible. If it is bigger or smaller that is fine, just as close as possible

I have therefore adapted the heuristic function to:

```
|target distance-distance Travelled so far| + distance left to travel.

```

for example, I want to travel 20 miles, so my target distance is 20. At some point in the route i may have travelled 18. Therefore my h would be 20-18+2 = 2. I always pick the smallest h value, the idea being a route of 20 miles will be created finished where i starts.

I had 2 immediate issues with this.

1. The Start node can't be added to the closed list immediately or it will never create a cyclical route - I believe I have solved this one.
2. If the search goes into a cul-de-sac it gets stuck and the openlist becomes empty and the search terminates.

The second problem I cannot think of how to solve. It occurs because the successor node that would get the search out of the cul-de-sac is already in the closed list.

Can anyone help me come up with a general solution to my problem? Furthermore do you for see any other issues with my implementation?

would really appreciate any help you can give.

# Answer
> 2 votes
This problem is known as the **Target Value Search Problem** (TVS) and it can be succintly described as follows:

*Given a graph $G(V,E)$, two nodes $s$ and $t$ ($s, t\in V)$ and a target value $T$ find a path $P$ from $s$ to $t$ such that the cost of the path is as close as possible to $T$*

Of course, $s$ and $t$ might be the same node (as in your case). Note that the problem is not asking for paths (or, alternatively routes) whose cost equals exactly $T$ but that no path with a cost closer to $T$ exists. This is known as *solving the Target Value Search Problem optimally*. As usual, the cost of a path is defined as the sum of the costs of all edges traversed in the path.

There are different variations of this problem. All of them are described in the paper:

Carlos Linares López, Roni Stern, Ariel Felner: Target-Value Search Revisited. IJCAI 2013

The specific case that interests you most has been also investigated. You can find a short summary of results in the paper:

Carlos Linares López, Roni Stern, Ariel Felner: Solving the Target-Value Search Problem. SOCS 2014

The best solution currently known (to the best of my knowledge) consists of applying a bidirectional search. From your considerations and the notes provided by other people contributing to this thread:

1. You are right! The problem is that you'd like to come back to the same node but the route to traverse when going back is in the closed list. This problem is specifically addressed in the backwards search suggested in the algorithm $T^\*$
2. David Richerby is right also! A\* should traverse a state space which is exponential.

In fact, regarding the second comment. A very simple baseline for solving this problem consists of either using A$^\*$ or IDA$^\*$ in the *path space*. IDA$^\*$ naturally generates paths (and thus it traverses a state space which can be exponentially large); A$^\*$ can do that also if you just ignore nodes in the closed list!

In both cases, a node is never re-expanded if and only if it is an ancestor of the current node. However, it seems to me that you might find this acceptable. In that case, you are forced to expand all nodes!

Hope this helps,

---
Tags: algorithms, search-algorithms, search-problem, searching
---


# Question
Title: What kind of recurrence relations has p < 0?
By the master method, $T(n) = aT(\frac {n}{b})+\Theta(n^k\log^pn)$ where $p$ is real.

I know $\log^4n=\log(\log(\log(\log n)))$ but how do you calculate something like $\log^pn$ where $p\<0$?

# Answer
As Rick Decker mentions, in this context $\log^p n = (\log n)^p$, and so $p$ can be an arbitrary real number. If you wanted to denote composition, you would use $\log^{(p)} n$ (which in other contexts signifies the $p$th derivative!). In that case, when $p$ is a negative integer, you just need to use the inverse of $\log$, namely $\exp$: $$ \begin{align\*} \log^{(2)} x &= \log\log x \\ \log^{(1)} x &= \log x \\ \log^{(0)} x &= x \\ \log^{(-1)} x &= e^x \\ \log^{(-2)} x &= e^{e^x} \end{align\*} $$ This definition ensures that $\log^{(a)} \log^{(b)} x = \log^{(a+b)} x$ for all integers $a,b$. The natural domain of this definition is integer $p$, though it can probably be extended for fractional $p$ in such a way that the equation above still holds.
> 5 votes

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Why we need tagbits when we already have indexbit and offset?
I was watching a lecture and got confused at one point when professor said that to distinguish between two addresses having same values of offset as well as index bit we need tag.Why we need tag ? for example He was explaining that both addresses can have different values .I want to know that how can value be different when we know offset and index both as it refers to exact byte location of whole word array ? isn't it ? please check the fallowing video at 3:25 .thanks .

http://youtu.be/WW-\_i8LmgvE?t=3m25s

# Answer
Multiple memory locations hash to the same location in the memory cache. The tag array serves to disambiguate which memory location's contents are stored in each cache location. If the address in the corresponding tag array location matches the address the CPU referenced, then the cached value is from the correct memory location and can be used, otherwise the value must be retrieved from another cache or main memory. This kind of verification is necessary for all hash table applications where the hash function is surjective, i.e. many onto one rather than one to one.
> 1 votes

---
Tags: memory-management, cpu-cache, virtual-memory
---


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

# Answer
> 2 votes
I had a similar question and emailed Inman Harvey from the University of Sussex (author of Artificial Evolution: A Continuing SAGA and The Microbial Genetic Algorithm). Here is his answer (emphasis mine):

> > What is an optimum population size? Why?
>
> If, like the natural world, a trillion microbes can evolve in the sea in parallel with no cost to you, then the bigger the better. In practice, on a serial machine, 10 times the pop-size costs you 10 times the time. **Experience, with rather little theory, suggests that pop sizes of 30 to 100 minimum get you quite a lot of the advantages that GAs have over hill-climbing (ie pop of 2).** So rule of thumb is to start here.

So basically, the bigger the population the better, but realistically you often have to make compromises to reach your goal in a reasonable amount of time. When building a genetic algorithm, you have to guess what the optimal values are for a lot of parameters. There is no *good* answer. Mostly there is a lot of trial and error.

# Answer
> 5 votes
There is no minimum to population size but it has a few drawbacks when it is too low.

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

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

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

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

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

---
Tags: algorithms, optimization, randomized-algorithms, genetic-algorithms
---


# Question
Title: What is the correct representation of Master Theorem?
What I'm taught in my class -

> $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$
> where $a\geq1$, $b\>1$, $k\geq1$ and $p$ is a real number.
>
> 1. if $a\>b^k$ then, $T(n)=\theta(n^{\log\_ab})$
> 2. if $a=b^k$ then,
>     * if $p\>-1$, then $T(n)=\theta(n^{\log\_ab}\log^{p+1}n)$
>     * if $p = -1$, then $T(n)=\theta(n^{\log\_ab}\log\log n)$
>     * if $p\<-1$, then $T(n)=\theta(n^{\log\_ab})$
> 3. if $a\<b^k$, then
>     * if $p\geq 0$, then $T(n)=\theta(n^k\log^pn)$
>     * if $p\<0$, then $T(n)=O(n^k)$

On certain websites, the above representation for **Master Theorem** is slightly different as follows -

> $T(n)=aT(\frac{n}{b})+\theta(n^k(\log n)^p)$

This ambiguity creates a great confusion while solving problems such as :

> What is the value of the recurrence : $T(n)=T(\sqrt{n})+\theta(\log\log n)$

Substituting $n=2^m$, we get a new expression :

> $S(m)=S(\frac{m}{2})+\theta(\log m)$
> Here $a=1$, $b=2$, $k=0$ and $p=1$

If I apply Master Theorem as per the way I am taught in class, the result I get is :

> $T(n)=\theta(\log\log\log n)$

and if I solve using the other formula, I get the result as :

> $T(n)=\theta((\log\log n)^2)$

**Which is the correct one? This confusion is making me question every problem that I've solved.**

# Answer
By convention, the notation $log^p(x)$ is defined to be $(log(x))^p$, not $p$ iterations of the $log$ function. This is similar to the trigonometric functions, which gives us identities like $sin^2(x)+cos^2(x)=1$.
> 7 votes

---
Tags: time-complexity, asymptotics, runtime-analysis, recurrence-relation
---