# Question
Title: What is the connection between data structures and data types?
I have read some books and wikipedia, which seem to give not completely consistent definitions and notations. I try to understand the concepts, regardless of what they are called. Here are what I have figured (please correct me) and would like to ask :

1. a (abstract) data type is a set $D$ of values, together with some operations on it (each $n$-ary operation is a mapping $D^n \to D$). E.g. The set of all the integers with arithmetic operations on it forms a data type.
2. A data structure seems to be a data type. Or are they the same concept? What is the formal definition of a data structure?
3. I have some difficulty in understanding if a "container-like construct" is a data structure or data type, or the set of all of them is. What I mean by a "container-like construct", is some set of values, but with some relation(s) on the set, e.g. a queue, a graph, a stack, an array, a map, .....

E.g., a queue is a set of values in it, with some ordering on the values according to which value was added earlier than which. Is a queue with a fixed size and fixed elements, as a set of values in it, a data type or a data structure? Or do all the queues form a data type or a data structure? Are adding and removing elements from a queue, which obviously create new queues, viewed as operations on the set of all the queues?

Similarly, a graph is a set of vertices and has relation between the vertices being the edges. Is a graph with fixed vertices and edges a data type or a data structure, or is the set of all the graphs a data type or a data structure? Are transformations from a graph to another different graph considered to be operations on the set of all the graphs? Is searching for a vertex in a graph considered to be an operation on that single graph?

# Answer
I agree with your definition of abstract data type. (A domain of values, together with some operations on that domain.)

I typically use the term *data structure* to refer to *implementation* techniques for data types. Examples of data *structures* are things like balanced binary trees and hashtables.

For example consider the data *type* `set of integers`, with operations like `union`, `intersection`, `is_member?`, and `insert_member`.

You could implement the data type with at least three different data *structures*, each of which has advantages and disadvantages. For example, you could implement your set using a balanced binary tree (like a red-black tree, for example). Each node in the tree represents a member of the set, insertion and membership tests take $O(\log n)$. Or, if your sets are over a finite (and relatively small) universe of items you could implement it with a `bit array`. This is an array of $U$ bits (where $U$ is the size of the universe.) Inserting element $i$ just means setting the $i$th bit, testing for membership just means testing the $i$th bit. But now intersection (respectively union) requires you to take the binary-`and` (respectively `or`) of $U$ bits, which kind of stinks when you have sets with just a few elements in them. Similarly with hash table implementations, insertion and testing are nice (on average), but intersection and union can be somewhat more complicated to do efficiently.
> 7 votes

# Answer
This is a very simplified view. For a formal approach, you need to look at type theory.

**There is no real difference**. Data structures are just standardized types and type constructors (such as tuple or list), with associated primitives operations, that are convenient for building other types with usually a very direct implementation, and are predefined in the kernel of your programming language.

An abstract data type is defined as an abstract domain D, with its primitive operations, which is implemented by defining a mapping so some (more concrete?) type defined with the preexisting constructors. The primitive operations are also implemented as function using the primitive operations available for the more concrete implementation. Then there is an encapsulation mecanism so that the concrete implementation is hidden, and only the abstract part is usable in the program.

This abstract data type can be a constructor when its definition depends on some other yet unspecified type.

Then we can remark that:

* the data structure types defined by the programming languages are themselves abstractions: a domain of value and its primitive operations. It is seen as concrete because it is mapped in simple ways on the computer hardware.
* the definitition of an abstract data type may well use another previouly defined abstract data type for its implementation.

Hence there is no reason to make a difference.

However, the expression "data structure" refers generally to the types obtained with the primitive types and constructors of the programming language.

**As a reply to some comments**, and to make things clearer:

I can define a balanced tree (pick your preferred flavor) as an ADT, call it `Balanced`, implemented with the more elementary types provided by the language, possibly parameterized by the type of the data it contains (which would rather make it an ADT constructor, to use my informal terminology). Then I can used this ADT `Balanced` to build another ADT called `Set` for sets, as suggested in the answer of Wandering Logic. Then I can use the ADT `Set` to implement some other ADT `XXX`.

Note that I could be more specific and actually call my ADT `Red-Black`, with a corresponding implementation, if I want to suggest that it will have exactly all the properties of red-black trees. It will nevertheless be an ADT, since the program will be allowed to use only the given primitives, without being allowed to fiddle with the pointers of the implementation at the risk of bugging the structure.

Then people may consider that data-structures are what is used for implementation, while ADTs are the abstraction that is built with the data structure. I will not fight it as this is terminology, and it does not really matter to me (see further comments below). But, then, I will point out that `Balanced`, or `Set`, are clearly ADTs when being defined, but become data structures when looked at from the point of view of the other ADTs they are used to implement.

*This only confirms what I said. They are the same.*

I know "we eat *beef* and *pork* rather than *cow* and *pig*", but these four names cover only two species, and the difference is only in the use made of the animal. Whether an ADT is *pork* or *pig* may be convenient terminology, may indicate a difference in intent, or a difference of perspective, but not a difference in substance.

Another issue raised in that context is that of **complexity**, as if it mattered more when looking at data structure, at implementation.

An immediate consequence of what I just said is that there cannot be any difference on that basis. When I implement the ADT `Balanced`, I am of course very careful to have a good implementation. And the complexity characteristics of the functions associated with that ADT (insertion, deletion, traversal, ...) are of course part of the specification, though that is usually implicit in the program, as well as other interesting properties of the abstraction (quite often). Then I can rely on the complexity of the `Balanced` primitives to analyse the complexity of whatever is implemented using `Balanced`.

When I use the ADT `Balanced` as data structure to implement the ADT `Set`, I will again be careful to get good complexity of its primitive operations (such as union or intersection of `Set` values) which will be (possibly implicitely) part of the Set interface specification. So, when I analyse the complexity of the ADT `XXX`, I can simply rely on what I know of the complexity of `Set`.

And this is very much what we do when studying the complexity of intricate algorithms. We rely on existing, well analysed constructs, and seldom look into the way they were themselves designed and analyzed. This is the essence of abstraction, and it is only the classical way of doing Mathematics. When we use a theorem, we do not have to think about its proof (Thanks to Curry and Howard for their support in this discussion).

Now I gave my view of the use of the terminology. It may be outdated, I do not know. But I would not worry a second about it since the two expression denote the same substance anyway. The difference, if any, is in the way you want to look at that substance. My own perception is that the only concrete difference is between the fact that original data types of the language are hard-coded by the compiler and have to be taken as they are, while all others, user or library defined abstract data types, can be re-implemented if need be. As I perceive that as the only significant difference, I rather use the extra word data structure to identify that. It may be that there is a different consensus in some communities, actually shared by the answer of Wandering Logic. A justification for it is that people could use the implementation based on other types without ever abstracting it, which would support the idea of having a specific name for it (I often just use the word *implementation*).

Then, just to make things a bit more confused, the Wikipedia page for *Data Structure* talks also of *Abstract Data Structure*, wich a link to ... *Abstract Data Type*.

Somehow, I strongly doubt there is an official unified terminology for all this. Except probably when giving formal definitions using type theory.
> 3 votes

---
Tags: terminology, data-structures, type-theory
---


# Question
Title: Implementability of a (abstract) data structure/type?
1. Do people consider the implementability of a (abstract) data structure or a data type, just like people do for implementability/computability of an algorithm? By implementability, I mean if a (abstract) data structure/type can be implemented on a real computer or abstract computer model.
2. Does the implementability of a (abstract) data structure/type depend on and only on

* the computability of each of its operations implemented as algorithms, and
    * whether the space it requires to store each value is limited?
3. Does the implementability of a (abstract) data structure/type depend on in which programming language it is implemented?

Does it matter if a programming language in which it is planned to be implemented is a imperative or functional language? In other words, are the (abstract) data structures/types that can be implemented by an imperative programming language and the (abstract) data structures/types that can be implemented by a functional languages the same?

why some data structures are called "functional data structures", and even there are some books for it (e.g. https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf). Are "functional data structures" not implemented or introduced in imperative languages? Why need to distinguish between (imperative?) data structures and functional data structures?

# Answer
As I am really not sure how you define implementability, I will guess that you think of complexity of an ADT. And when I say complexity I mean time and space complexity of its operations and space complexity of the values it stores during its lifetime.

People do care that the operations are computable and preferably with low time and space overhead. Usually, there is not a single best implementation of an ADT; take a look at various implementations of a queue in a multithreaded setting. You end up with the one you assume will work best for your particular problem.

The design of a programming language can significantly influence the way ADT is implemented. For example, support for infinite streams comes built-in in Haskell, but in, say Java, you have to implement such an ADT on top of the primitives Java provides, which can be time consuming and slower than in Haskell performance wise.
> 1 votes

---
Tags: algorithms, data-structures, programming-languages
---


# Question
Title: Back invalidation to maintain inclusion in inclusive cache
For an L2 cache that is strictly inclusive of the L1 cache, if a block to be evicted is also present in L1, then back invalidation is required to maintain the inclusion property.

I am interested in some details of how back invalidation is handled.

1. When an L2 block is evicted, is back invalidation command always sent to the L1 or only sent if the block is in the L1 cache?
2. If the back invalidation is only sent when the block is in L1, how does the L2 cache maintain the information that a given L2 block is also in L1?
3. When invalidating L1 block by back invalidation, what happens if the L1 block is dirty? Is it written back to main memory bypassing L2 (assume write-back caches and L2 is the last level cache)?

# Answer
> 2 votes
There are a broad range of design choices about how back invalidation is handled. Whether the L2 knows if a cache block is in L1 (and which L1, instruction or data) is one implementation choice with three basic options: no knowledge, approximate but conservative knowledge, and perfect knowledge.

With the no knowledge, the L2 cache will always probe both L1 caches (assuming a coherent L1 instruction cache as in x86 generally and some other processors, e.g., recent POWER processors). With approximate knowledge back invalidation commands would be filtered so they are sent to the appropriate L1 only if the block is *likely* to be present. With perfect knowledge only necessary back invalidations are sent to L1.

Obviously the no knowledge option provides the most straightforward implementation since there is no choice but to send the invalidation request. This can waste request bandwidth between L2 and L1 and may interfere with the availability of L1 tags for memory accesses from the core. Replication of tags or adding a read port would solve this issue, banking of the tags would reduce the frequency of conflict, adding a filter on the L1 side would also reduce access to the complete tags.

Approximate knowledge can substantially reduce the number of probes needed and reduces the amount of information that must be stored with the L2 cache and makes communication about L1 evictions less critical. The latter factor can be exploited to schedule communication of the information to minimize overhead, including interference with required communication. Since back invalidation probes are filtered, their interference with normal operation of the core is reduced giving less reason to increase the number of tag reads supported.

An approximate filter could use per L2 block information (where techniques similar to those used to compression coherence directory entries could be used) or could use a separate filter (like a Bloom filter).

Perfect knowledge (or a very close approximation) avoids unnecessary invalidation requests to L1, but effectively requires the equivalent of a directory coherence entry for each L2 cache block and every eviction from L1 must be quickly communicated to L2. A simple implementation might use one bit per L1 cache to track the presence of the block in that cache (e.g., tracking the presence in a single core's L1 instruction and data caches would use two bits per L2 block).

Another, not entirely implausible option for an L2 much larger than the L1 caches would be replicating the entire L1 cache tags, possibly in a compressed format that used the L2 set and way (excluding the bits used for indexing the L1 cache) for the replicated L1 tags.

The information can be kept current by communicating to L2 the address (or in the case of the replicated L1 tags located with L2 just the set and way could be communicated) of every L1 eviction. To include this information in the message requesting the data replacing the evicted block, the victim would have to be selected quickly. While this is not a substantial problem, it treats an L1 victim as if it was immediately replaced (i.e., an access to the victim block before the L2 cache has supplied the new block would be treated as a miss even though the data is still present).

This miss could be made merely conceptual by changing the victim choice in the rare case that the victim is accessed during this small window between victim selection and the response from L2 filling the L1 entry, but in that case an additional message must be sent to the inform L2 of the change in victim.

When the back invalidated block is dirty in L1, this block typically would be written back to memory (or sent to the requesting cache for a coherence invalidation caused by another cache attempting a write to that address; in that case whether it is also sent to memory is another implementation choice). However, when the eviction is not coherence-related, it would be quite possible to change the victim choice. In this case, the L2 might retain the dirty block, possibly requiring another back invalidation if the new victim is (or might be) in L1. Obviously, this same strategy could be used if the L1 informed the L2 cache that the block is a poor replacement choice (e.g., being more recently used than most other blocks in its L1 set).

Note that it is also possible to communicate information about L1 accesses back to the L2 cache so that an LRU-oriented L2 replacement policy would less often choose a block that is still in L1. While doing this for every L1 access or even every L1 access that influences replacement (with LRU replacement an access of the most recently used block will not change the state), would be excessively expensive, partial information could be sent when convenient. E.g., extra information could be included with a miss handling request or extra messages could be sent to L2 when the interface is otherwise idle (using a separate queue of replacement policy update information from which entries can be dropped if the interface is busy when more information is added to a full queue).

Since back-invalidations are relatively rare, the cost of unnecessary invalidation requests (i.e., when the block is not actually in a particular L1 cache) might be lower than the cost of reducing or completely avoiding them. On the other hand, with L2 cache potentially shared among several L1 caches (e.g., an L2 cache shared by two cores might include four L1 caches), avoiding the need to broadcast the invalidation to all the included L1 caches would have some attraction.

These implementation details do not appear to be documented in general, so the above is derived from reasoning about the tradeoffs.

---
Tags: cpu-cache, memory-hardware
---


# Question
Title: Can the Euclidean distance function be computed using only XOR's
The Eulidean distance function $d$ of $x$ and $y$ is given by:

$ d(x,y)=\sqrt{x^2-y^2} $

Let us assume that $x$ and $y$ are fixed-point numbers, or $x,y$ are element of some subfield $f\_n$ of $F\_p$. We could even assume that $x,y$ have precision $n$ decimal digits. Any facilitating representations of rational or real values $x,y$ that carries "enough" information is good. $x,y$ could also be assumed to be only positive.

Can the Euclidean distance function be computed using only XOR's? If this cannot be achieved, what other boolean functions would be needed?

# Answer
> 5 votes
No. It's not possible. Any function that can be computed using just XOR's is affine over $GF(2)$. However, the Euclidean distance is not affine over $GF(2)$, so there is no hope of representing it with just XOR's.

Recall that $GF(2)$ denotes the finite field with two elements; you might also see it indicated by $\mathbb{F}\_2$, and it is the field $(\\{0,1\\},\oplus,\times)$, where $\oplus$ represents the XOR operation (i.e., addition modulo two) and $\times$ represents the AND operation (i.e., multiplication modulo two).

Recall that a function $f$ is linear if it can be expressed as a linear map, i.e., $f(x+y)=f(x)+f(y)$ holds. More specifically, suppose we have a function $f:GF(2)^n \to GF(2)^m$ that maps from a vector space over $GF(2)$ to a vector space over $GF(2)$. Then $f$ is linear if $f(x \oplus y)=f(x) \oplus f(y)$ for all $x,y$, where $\oplus$ denotes element-wise XOR. Equivalently, $f$ is linear if there is a $m\times n$ matrix $M$ whose elements are in $GF(2)$ (i.e., all of whose elements are 0 or 1), such that $f(x) = Mx$.

A function $g$ is affine if it is of the form $g(x)=f(x)+c$, where $f$ is linear and $c$ is an arbitrary constant. In our case, $g$ is affine if there is a $m\times n$ matrix $M$ whose elements are in $GF(2)$ (i.e., all of whose elements are 0 or 1) and a constant $c \in GF(2)^n$, such that $g(x) = Mx+c$. See, e.g., this Wikipedia article for more.

The XOR operation is linear. Also, because the set of $GF(2)$-affine transformations is closed under composition (this follows because $(\\{0,1\\},\oplus)$ is a group), it is easy to see that any circuit built solely out of XOR's must be $GF(2)$-affine. (Why affine, rather than linear? Because a circuit can contain constants: it can take an input and XOR it with the constant 1. That makes it affine, rather than linear.)

Now it is easy to verify that the Euclidean distance is not $GF(2)$-affine, just by looking at a few values: e.g., you can look at $d(0,0)$, $d(0,1)$, $d(1,0)$, $d(1,1)$. If $d$ were affine, we would have the relationship

$$d(0,0) \oplus d(0,1) \oplus d(1,0) \oplus d(1,1) = 0.$$

Since this relationship does not in fact hold, $d$ is not $GF(2)$-affine.

And since $d$ is not an affine function of its inputs, this means it cannot be expressed using only XORs.

Certainly NAND gates would be sufficient, as they are universal. It could also be expressed using just XORs and ANDs, as those two are also universal. There are many other options.

---
Tags: arithmetic, boolean-algebra, euclidean-distance
---


# Question
Title: Algorithm for designing a binary code with predefined distance
Suppose I have a matrix $A$ with its entry $A\_{ij}$ denoting some kind of distance between class $i$ and $j$, is there a feasible algorithm for computing a binary coding for all the classes, such that the Hamming distance between code word for $i$ and $j$ is (roughly) proportional to $A\_{ij}$?

A related question is that given a set of points, design a binary code where the Hamming distance is (roughly) proportional to the Euclidean distance.

# Answer
> 1 votes
This is known as an *embedding* into $\\{0,1\\}^n$. Your matrix $A$ defines a weighted graph, and you want an embedding into the hypercube.

I suggest you examine the literature on low-distortion graph embeddings, which have been studied in great depth in the computer science literature. You might find some existing constructions on this topic. I'm not deeply familiar with that literature myself and I don't know whether you will find anything directly applicable.

---
Tags: algorithms, coding-theory
---


# Question
Title: Error-correction code for transmission only with bit-flipping from 0 to 1
I am using a transmission system that uses a Bloom filter (this part is out of my control). I want to send a small amount of data (32 bits) using this system.

For each bit \[0,31\], I add its index to the Bloom filter if the corresponding bit is set. The Bloom filter is then transmitted without error and the recipient tests the Bloom filter for each index \[0,31\] to reconstruct the 32 bits of data.

One problem is that the Bloom filter can have false positives, making it look like some bits are set when they shouldn't be. Another problem is that the Bloom filter may already have other entries in it, further making it look like more bits are set.

I wondered if error-correction codes could help here. The general idea would be to add more bits (\[32,35\] for example) the recipient could use to figure out the original 32 bits despite Bloom filter collisions.

---

After a little research I learned that Z-channels (or binary asymmetric channels) flip bits in one direction. Also I found that linear error-correction codes for Z-channels are often applicable to symmetric channels as well. So to exploit the asymmetry, the codes likely need to be non-linear. More info on the state of the art is appreciated (hoping for a simple algorithm...).

# Answer
This is not possible. There's no free lunch. You are looking for a compression scheme that is guaranteed to compress 32 bits down to less than 32 bits. That's not possible in general, unless you have prior knowledge that lets you rule out some of the possible 32-bit values.

In particular, if you want to send 32 bits of information, and all $2^{32}$ possibilities are equally likely, and errors are not allowed, you'll have to send at least 32 bits over the communication channel. This is a basic theorem of information theory. No amount of error-correcting codes will get you past this.

If you want to avoid this, you'll either need prior knowledge on the 32-bit value (e.g., to rule out some as impossible, or less likely than others), or you'll need to accept lossy compression (where the recipient's received string might not exactly match what the sender wanted to send).
> 3 votes

---
Tags: information-theory, coding-theory, error-correcting-codes
---


title: $L \in RE$ Question

text:
# Question
Title: $L \in RE$ Question
I see a sentence in one final exam on automaton course.

> I have one problem: if we want to have a TM that halts for all word in L, it's enough to have L be R.E? or we should have R be R.E and Complement of R be R.E?

Note: (Recursive Enumerable = R.E).

# Answer
> 4 votes
This answer is based on what I thought an earlier version of the question meant.

It's the hypothesis of a theorem: **if** $L$ and its complement are R.E., **then** $L$ is recursive. At least, that is the theorem one would expect to see. In fact, the theorem seems to be "If $L$ and its complement are R.E., then $L$ is R.E.", which is vacuously true.

And, yes, there are plenty of languages $L\in\mathrm{RE}$ for which the complement of $L$ is not in $\mathrm{RE}$.

---
Tags: computability, turing-machines
---


# Question
Title: Relationship between message entropy and complexity of the best algorithm
Is it possible to estimate number of steps in best possible algorithm for classification of messages, using entropy of messages?

E.g. linear search problem. We have an ordered set of incomparable elements (no \< and \>, equivalence only) of length $N$, and element for search – A, which could be in set maximum once. Set could be represented as sequence like 00001000, length $N$, where 1/0 means that element here equals A/not equals A. Algorithm parses the message and responds "not contains" (for one message 00000...0 ) and "contains" (all other messages). For uniform probability of being equal A for each position, entropy of responses equals: $$H=-\frac{1}{N+1}\cdot \log\_2\left(\frac{1}{N+1}\right) - \frac{N }{N+1} \cdot \log\_2\left(\frac{N}{N+1}\right)$$ $H$ goes to zero quickly:

We also know that $\lfloor\text{entropy}\rfloor+1$ equals the mean message length in case of best coding (Shannon's source coding theorem for symbol codes). That means we could index any message with binary string, and it will take us only one symbol – one step in algorithm!

But existing codes for linear search (e.g. brute force) require $\frac{N+1}{2}\>1$ steps, and all improved techniques require comparability (e.g. binary search).

This suggests that entropy of message does not equal the number of step in best possible algorithm of problem solution (=message classification).

But then what is the link between both? Is there any relationship between the number of steps for the abstract "best code" and the entropy of message?

# Answer
I believe you are looking for *algorithmic information theory*. This *defines* the information contained in a string as proportional to the size of the smallest program that produces that string. The metric is called *Kolmogorov (Колмогоров) complexity*.

The problem with normal Shannon entropy, is that it is defined *relative* to your assumed model of the producer of the information stream. Shannon entropy really only deals with models that produce infinite and stationary random streams. When you know that the producer is deterministic then the Shannon entropy of the stream is 0 (even though you don't know the algorithm of the producer.) You can often model a deterministic stream as some kind of Markov process, but there will always be a Markov process with more states that models the deterministic stream and in which the entropy is smaller.
> 1 votes

---
Tags: search-algorithms, information-theory, entropy
---


# Question
Title: Space complexity analysis of binary recursive sum algorithm
I was reading page 147 of Goodrich and Tamassia, *Data Structures and Algorithms in Java*, 3rd Ed. (Google books). It gives example of linear sum algorithm which uses linear recursion to calculate sum of all elements of the array:

```
Algorithm linearSum (arr , n)
    if (n == 1)
        return arr[0]
    else
        return linearSum (arr , n-1) + arr[n-1]
end linearSum

```

And the binary sum algorithm which uses binary recursion to calculate sum of all elements of the array:

```
Algorithm binarySum (arr, i, n)
    if (n == 1)
        return arr[i]
    return binarySum (arr, i, ⌈n/2⌉) + binarySum (arr, i+⌈n/2⌉, ⌊n/2⌋)
end binarySum

```

It further says:

> The value of parameter $n$ is halved at each recursive call `binarySum()`. Thus, the depth of the recursion, that is, the maximum number of method instances that are active at the same time, is $1 + \log\_2 n$. Thus the algorithm `binarySum()` uses $O(\log n)$ additional space. This is big improvement over $O(n)$ needed by the `linearSum()` algorithm.

I did not understood how the maximum number of method instances that are active at the same time, is $1 + \log\_2n$.

For example consider the below calls to method with method parameters given in rounded box:

Then in two recursive calls of second row from top, $n = 8$. So, $1 + \log\_2 8 = 4$. Now I dont get what maximum limit this 4 represent?

# Answer
> 6 votes
* In a given tree, all the vertices of this tree correspond to `binarySum()` calls.
* The value of parameter `n` to `binarySum()` is halved at each recursive call.
* Also, each recursive call finishes *after* all its children finish. Thus at each recursive call, number of active calls include all the ancestor calls in call sequence.
* Thus when any `binarySum()` call corresponding to leaves in above call tree is active, its parent, grandparent and so on are still active as well.
* Thus, the depth of the recursion, that is, the maximum number of method instances that are active at the same time, which is always equal to the height of the recursive calls tree is 1 + log$\_2$n.
* For example in `binarySum()` recursive calls tree above, with n = 8, at any of the calls correspnding to leaves,

Why does the depth of recursion affect the space, required by an algorithm? Each recursive function call usually needs to allocate some additional memory (for temporary data) to process its arguments. At least, each such a call has to store some information about its parent call - just to know where to return after finishing. Let's imagine you are performing a task, and you need to perform a sub-task *inside* this first task - so you need to remember (or write down on a paper) where you stopped in the first task to be able to continue it after you finish the sub-task. And so on, sub-sub-task inside a sub-task... So, a recursive algorithm will require space `O(depth of recursion)`.

@randomA mentioned the Call Stack, which is normally used when a function invokes another function (including itself). The call stack *is* the part of the computer memory, where a recursive algorithm allocates its temporary data.

---
Tags: algorithm-analysis, space-complexity, recursion
---


title: How to construct a DFA for this?

text:
# Question
Title: How to construct a DFA for this?
Let $C = shuffle(A, B)$ denote the shuffle $C$ of two languages $A$ and $B$, it consists of all strings $w$ of the form $w = a\_1b\_1a\_2b\_2....a\_kb\_k$, for $k \> 0$, with $a\_1a\_2 ··· a\_k \in A$ and $b\_1b\_2 ··· b\_k \in B$. Show that if A and B are regular then so is $C = shuffle(A, B).$

# Answer
> 4 votes
Suppose $A$ and $B$ are regular. Let $M\_A$ and $M\_B$ be DFAs for $A$ and $B$, respectively. We know $M\_A$ and $M\_B$ exists since every regular language is accepted by some $DFA$.

Let $M\_A = (\Sigma, Q, q\_0, A, \delta)$ and $M\_B = (\Sigma', Q', q\_0', A', \delta')$.

We define $M\_C = (\Sigma'', Q'', q\_0'', A'', \delta'')$ such that $L(M\_C) = shuffle(A,B)$.

First, let $\Sigma'' = \Sigma \cup \Sigma'$.

Next, choose $Q'' = \\{0, 1\\} \times Q \times Q'$.

Now, choose $A'' = \\{(0, q, q') \mid q \in A, q' \in A' \\}$.

Let $q\_0'' = (0, q\_0, q\_0')$.

Now the fun part: what is the transition function? Here's what it's going to do:

1. If $q'' = (0, q, q')$, then $\delta''(\sigma, q'') = (1, \delta(\sigma, q), q')$ if $\delta(\sigma, q)$ is defined, or undefined otherwise (we're going to get an NFA, but that's OK).
2. If $q'' = (1, q, q')$, then $\delta''(\sigma, q'') = (0, q, \delta'(\sigma, q'))$ if $\delta'(\sigma, q')$ is defined, or undefined otherwise (again, we're going to get an NFA, but that's good enough for establishing regularity).

Basically, we're using the state to encode whether the last symbol we saw was from a word in $A$ or from a word in $B$. We can only accept if the last symbol we saw was from a word in $B$, hence our set of accepting states requiring that we have 0 for the parity. Furthermore, we can only accept if we've seen a complete word from both $A$ and $B$, which is why we require the other components to be accepting states in their respective automata.

You can think of this as two simultaneous DFAs produced from the Cartesian-Product construction for the intersection of the languages. After evaluating each step, we jump to the other machine. The first machine accepts input corresponding to the language $A$, and the second machine accepts input corresponding to the language $B$.

The full proof that this construction yields a correct automaton is left as an exercise.

Note that this construction technically allows $k = 0$, which is not allowed by the language in the question. To complete the exercise, argue that the NFA obtained above can be converted to a DFA by a standard construction, and that intersecting the resulting DFA with a DFA for the language of positive-length strings gives a DFA for the desired language.

---
Tags: automata, finite-automata, closure-properties
---


# Question
Title: Karnaugh map with don't care: increasing the number of groups instead of simplifying
```
              AB
        00  01  11  10
    00 | x | 1 | 0 | 1 |
CD  01 | 0 | 1 | x | 0 |
    11 | 1 | x | x | 0 |
    10 | x | 0 | 0 | x |

```

The answer to the above Karnaugh map is $F(ABCD) = B D + \bar B \bar D + \bar A \bar C \bar D + \bar A C D$ according to my book and the K-map solvers online.

But what I don't get is that I can further reduce the terms in this answer: $F(ABCD) = \bar B \bar D + \bar A CD + \bar A B \bar C$ also covers all the min terms in lesser groups.

The answer in my book just has a bigger group covering additional don't cares. Since they are optional shouldn't my answer be correct?

# Answer
> 1 votes
Your answer is correct. It is also more reduced. The reason your book and the solver give you a bigger equation is because they use a greedy algorithm that attempts to match bigger groups (groups with less variable in them). This will have an optimal behavior if the map has no "don't cares" \[reference needed\].

To have optimal behavior with "don't care", you have to consider that an X can be either a 1 or a 0. That means that for each X, you have two versions of you map. So, if you have $N$ "don't cares", you will have to reduce the $2^N$ versions of the map and choose the smallest reduced operation from the results.

**Extra**

If you have lots of those maps to reduce, i suggest you use Logic Friday or a similar equation reducer.

---
Tags: computer-architecture, boolean-algebra, digital-circuits, karnaugh-map
---


# Question
Title: Why does binary search take $O(\log n)$ time?
My question seems like an elementary question, but it's really not.

Suppose I have one million cars in a line sorted in alphabetical order by license plate. I am standing at the top of the line with the car with license plate AAA111. I want to find the car with license plate ZZZ999. I could do binary search to find the car with license plate ZZZ999, but I'm still going to have to walk the distance of one million cars, not a distance on the order of $\log 10^6$.

So this is why I'm asking how or why did computer scientists come up with the idea that binary search takes $O(\log n)$ time?

# Answer
> 4 votes
This is only possible in data structures which allow random access like **arrays and vectors**.

So if you already know that you have to access the last car , then you can do it in **O(1)** time. Data structures like linked lists won't allow you to perform a binary search in **O(logn)**

The example you have mentioned is similar to using binary search on a linked list. So it will need **O(n)** time as you will need to traverse all the nodes to reach the last node in the worst case.

So your argument that you cannot reach the middle car in no time is valid in your example but not in data structures which offer such properties.

# Answer
> 1 votes
Binary search is done by reaching the middle of the sorted array in O(1) time which is done through indexing .The case which you are telling is not exactly how binary search work.

Its because computer can reach the middle element in no time and you have to linearly go to the center point in case of your car plate example.

---
Tags: complexity-theory, history
---


title: Why BFS is source vertex specific?

text:
# Question
Title: Why BFS is source vertex specific?
Take a graph $G=(V,E)$ .

As we know both DFS and BFS are graph search algorithms .

But why the algorithm for BFS is designed in such a way that it does not cares about the vertices that are not connected to the source vertex $s$ but DFS takes care about all vertices in $V$.

I mean if $G$ has $l$ connected components and a vertex $s$ is in one of the connected component among $l$ , then if $s$ is the source vertex for BFS , then BFS performs only traversal on the only one connected component (which contains $s$).

If $G$ is input for BFS , it constructs one BFS tree (for component which contains $s$).

But in case of DFS , it constructs a DFS forest with $l$ DFS trees.

Why no BFS forest and it is restricted to a specifc component (containing $s$)? Any reason involved ?

For Bfs algorithm page # 595 and for Dfs algorithm page # 604 from here

# Answer
Both BFS and DFS are algorithms for exploring a *single* connected component, and there are also several others. All such algorithms can be extended to explore all connected components in a graph.
> 3 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Compute sums of all subsets of some words
We have $16$ words of given length, let's say $W\_1,...,W\_{16}$ and I want to make an one dimensional matrix that will contain all the possible sums of $W\_i$'s, for example:

$W\_1,W\_2,...,W\_{16}$

$W\_1+W\_2,W\_1+W\_3,...,W\_1+W\_{16}$

$W\_2+W\_3,...,W\_2+W\_{16}$

and so on, all the pair sums...

then all the three sums

$W\_1+W\_2+W\_3,...,W\_1+W\_2+W\_{16}$

then all the four sums

until the sums which is all sixteen

$W\_1+W\_2+...+W\_{16}$.

Is there a faster way than, for example, using a triple `for` to make all the possible triplet sums and in general $n$ `for` loops to make all the $n$-tuple sums?

# Answer
If you think that there are much fewer than $2^{16} $ sums, you can try the following approach. Iteratively compute a sorted list of all partial sums of the first $k$ values. Given this list for some $k$, add to all sums in the list $W\_{k+1} $, and then merge the two lists like in Mergesort, removing duplicates. The total complexity should be asymptotic to the number of distinct partial sums.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Finding number of numbers <= N, containing atleast one of the digits 2,4,6,8
Given an integer $N$, I want to find the number of numbers $\le N$, that contain at least one of the digits from the set $\\{2, 4, 6, 8\\}$. How do I go about solving this problem? I was thinking of constructing all possible numbers that fit into the integer size of the language that I am using, through a recursive procedure, but I am not sure how to do that. It seems complicated. Is there an alternative solution apart from taking some of the digits from the given set and constructing numbers?

# Answer
This is much easier than inclusion–exclusion. Compute the number of natural numbers smaller than $N$ that contain none of the digits 2, 4, 6, 8 and subtract that from $N$ (or $N+1$ if you're including zero). To compute the number of naturals that contain none of 2, 4, 6, 8, observe that, if $M\leq N$ (padded with zeroes so $M$ also has $d$ digits) then $M$ and $N$ must agree on their first $i$ digits (for some $0\leq i\leq d$), then the $(i+1)$st digit of $M$ must be less than the $(i+1)$st digit of $N$ and the $(i+2)$nd, ..., $d$th digits of $M$ can be any of 0, 1, 3, 5, 7, 9.
> 2 votes

# Answer
This is really a math question. The idea is to use the inclusion-exclusion principle. For every given position, it is possible (with some effort) to count the number of integers at most $n$ which contain one of 2,4,6,8 in that position. With more effort, you can do this for several positions at once. Now you can use the inclusion-exclusion formula to determine the quantity you are after.
> -1 votes

---
Tags: combinatorics, recursion, discrete-mathematics
---


title: Problem with my proof that NP = coNP?

text:
# Question
Title: Problem with my proof that NP = coNP?
Is there a problem with this proof that NP = coNP?

It suffices to show that Satisfiability can be solved efficiently with at most a polynomial number of queries to an oracle for Tautology. The algorithm for a problem P is, pick a variable X in P and fix it to T to obtain a problem P'. Submit ~P' to the oracle for Tautology. If ~P' is a tautology, then X is a "no go" for the problem P. If the oracle accepts ~P', then fix X to T in the result, otherwise fix X to F. Then proceed to the next variable. This requires linear queries in the size of the problem. An analogous result reduces Tautology to Satisfiability. Therefore NP = coNP.

My only doubt is that maybe when you're using an oracle you only get to find out if it accepts, not if it rejects. That would block this proof.

# Answer
> 4 votes
You are confusing Turing reductions with mapping reduction, in a sense. The problem with your argument is that if you allow an oracle $O$ to an NP-complete (or coNP-complete) problem, you immediately get that $P^O=co-P^O$. That is, if you already have an oracle for coNP, then you cannot distinguish NP from coNP (but that does not mean that they are equal!).

Here is a shorter version of your argument, to make things clear: suppose we have an oracle for Tautology. It is true that $\phi$ is satisfiable iff $\neg \phi$ is not a tautology. Thus, in order to test if $\phi$ is satisfiable, just run the oracle on $\neg \phi$, and *invert the answer*. But this only shows that $NP\subseteq P^{coNP}$. Your assumption that $P^{coNP}=coNP$ is incorrect (or at least, it's an open question).

---
Tags: complexity-theory, p-vs-np
---


# Question
Title: Execution time of NP and NP-Complete algorithms
For P algorithms, we say that the execution time can be logarithmic O(log n), lineal O(n), quadratic O(n^2), etc.

For NP and NP-Complete algorithms is there a way to represent the execution time? Or is there a 'standard' way of doing it?

# Answer
Asymptotic (/Big-Oh/Landau) notation is not special to polynomial time algorithms, or indeed any class of algorithm. It *is* the standard way of communicating (asymptotic) running times, amongst other resources.

So we say that binary search runs in time $O(\log n)$ because that is what its asymptotic running time is, and hence the **Searching** *problem* in $\mathrm{P}$, but not it is in $\mathrm{P}$ and hence we can get some $O(\cdot)$ expression for it. The Tower of Hanoi problem has an $O(2^{n})$ algorithm for example (in fact $\Theta(2^{n})$), this happens to put it in the class $\mathrm{EXP}$, but the asymptotic expression is still an evaluation of the running time, regardless of which class it is in.

Note the distinction here between problems an algorithms as well. A *problem* is in a complexity class, and *algorithm* has a running time. By extension we say that the problem can be solved in time "blah" *because it has an algorithm runnning in that time*. So we can't have an $\mathrm{NP}$-complete algorithm, only an $\mathrm{NP}$-complete problem. We can abuse the language a small amount an say we have and $\mathrm{NP}$ algorithm, but what we mean is that we have a nondeterministic polynomial time algorithm, i.e. an algorithm that demonstrates that whatever problem it's for is in $\mathrm{NP}$, just as binary search is a polynomial time algorithm that demonstrates that **Searching** (the formally defined problem) is in $\mathrm{P}$. Then David Richerby's answer applies - they're just polynomial but on a nondeterministic machine, i.e. $O(n^{c})$ for some fixed $c$.

On the flip side, we can have an algorithm for an $\mathrm{NP}$ problem that is not the one that shows that the problem is in $\mathrm{NP}$. For example, there's an algorithm for the **Travelling Salesman Problem** that just tries all the possibilities. This algorithm has running time $O(n!)$. It's not the best algorithm, but it is an algorithm for an $\mathrm{NP}$-complete problem, and that's its running time expressed asymptotically.

Finally, $\mathrm{P}$ is a subclass of $\mathrm{NP}$, so all those "P algorithms" are also "NP algorithms" - they just don't use the nondeterminism.
> 4 votes

# Answer
An **NP** algorithm is, by definition, one that runs in polynomial time on a nondeterministic Turing machine.
> 3 votes

---
Tags: complexity-theory, np
---


# Question
Title: LSD and MSD sorting - which requires fixed length keys?
I am studying these sorts, but it is still unclear to me which one of these two would require fixed length keys?

# Answer
> 4 votes
MSD(Most Significant Digit) radix sort needs fixed length keys as input.

Reason :

LSD(Most Significant Digit) radix sort first sorts the integers based on the least significant digits and then proceeds sorting for most significant digits . So, there is no problem if the keys are of non-equal length because of the reason that MSD has more weight-age.

MSD(Most Significant Digit) radix sort starts with most significant digits and then proceeds sorting to least significant digits , if the given keys are of unequal length , we have to place required number of 0's infront of them to make equal length. Then only we can sort based on most significant digits .

If you are still unclear , then remember the following

'LSD first sorts least significant digits and then sorts the keys with same length in lexicographical order'

"MSD sorts the keys in lexicographical order"

Lexicographical ordering comparison always between keys of same length.

You can remember it by their running times too ,

Running time of LSD is $\ O(n\*k\_{avg})$ and for MSD is $\ O(n\*k)$

where $n=$ # keys to be sorted , $k\_{avg}=$average length of keys , $k=$length of a key

So , it shows that LSD assumes each key may have different lengths , so the tme complexity takes average of length's ($k\_{avg}$) but MSD assumes each key must be of length '$k$', so its $\ O(k)$ .

Simple example : let us take integers in which one of them has different length and then we try to sort them .

Keys = $23,165,104$

LSD : 1) $2\underline{3},16\underline{5},10\underline{4}$ (compares unit's digits)$\implies 2\underline{3},10\underline{4},16\underline{5}$

2) $\underline{2}3,1\underline{6}5,1\underline{0}4$ (compares ten's digits)$\implies 1\underline{0}4, \underline{2}3,1\underline{6}5$

3) $\underline{1}04,23,\underline{1}65$ (compares hundred's digits)$\implies 23,\underline{1}04, \underline{1}65$

If we do the same for MSD (with out making them equal length by adding 0's in front of them), then the elements will not be sorted :

1) $\underline{2}3,\underline{1}65,\underline{1}04$ (compares MSD's)$\implies \underline{1}65,\underline{1}04,\underline{2}3$

2) $1\underline{6}5,1\underline{0}4,2\underline{3}$ (compares next MSD's )$\implies 1\underline{0}4, 2\underline{3},1\underline{6}5$

3) $10\underline{4},23,16\underline{5}$ (compares hundred's digits)$\implies 10\underline{4}, 16\underline{5},23$

There is no problem if we assume the MSD of an integer as 0 but not in the case of LSD (which leads to error as above)

If we do the same for MSD (After making them equal length by adding 0's in front of them), then the elements will be sorted in correct order:

1) $\underline{0}23,\underline{1}65,\underline{1}04$ (compares MSD's)$\implies \underline{0}23,\underline{1}65,\underline{1}04$

2) $0\underline{2}3,1\underline{6}5,1\underline{0}4$ (compares next MSD's )$\implies 1\underline{0}4, 0\underline{2}3,1\underline{6}5$

3) $10\underline{4},02\underline{3},16\underline{5}$ (compares hundred's digits)$\implies 02\underline{3},10\underline{4}, 16\underline{5}$

---
Tags: algorithms, sorting
---


title: Board cutting problem

text:
# Question
Title: Board cutting problem
To cut a wooden board, a sawmill charges proportional to the length of the board. The cost of cutting a single board into many smaller boards will thus depend on the order of the cuts. As an example, lets say cutting a $10m$ board into two pieces costs $10$. Then to cut a $10m$ long board at marked positions $3m$ and $5m$ costs $10+7=17$ if it is ﬁrst cut at position $3m$ and then at $5m$. On the other hand, if it is cut at $5m$ position ﬁrst, and then at $3m$, it would cost $10+5=15$. As input, you are given a board of length $n$ with $k$ marks on it. You need to give an algorithm that, given an input length $n$ and a set of $k$ desired cut points along the board, will produce a cutting order with minimal cost in $O(k^c)$ time, for some constant $c$

I'm getting $O(k!)$ complexity :(

# Answer
To me, the way the cutting cost analogy is unnatural. I'm going to work with an equivalent problem instead. Additionally, I'll think about the task in *reverse*, combining pieces instead of cutting.

An equivalent problem:

> Given a sequence of integers $s\_0,s\_1,\ldots,s\_k$. We want to find the order of adding up all the integers such that the cost of this process is minimize. The add operation only works on each adjacent pair in the sequence and will replace the pair with its sum. The cost of each add operation is the resulting sum.

I'll think about the problem of finding lowest cost first. The order of adding can be traced back if you have the algorithm to find the lowest cost.

Define $M(i,j)$ to be the *lowest* cost of this process on the *subsequence*

> $s\_i,s\_{i+1},s\_{i+2}\ldots,s\_{j-2},s\_{j-1},s\_j$

where $0 \le i \le j \le k$

We can then formulate $M(i,j)$ in terms of smaller problems as follows:

> $M(i,j) = \Sigma\_{y=i}^{j} s\_y + \min\limits\_{x \ldotp i \leq x \< j} \\{M(i,x) + M(x+1,j) \\}$

for the case that $j-i\>2$

I'll leave the base case of $j-i \le 2$ and the order of which $M(i,j)$ to calculate first for reader to work out.

---

The algorithm has to calculate $M(i,j)$ for every $0 \le i \le j \le k$ and each time it does that, it has to iterate over $x$. Thus, the time complexity is $O(k^3)$
> 3 votes

---
Tags: algorithms, optimization
---


# Question
Title: How can I compute the average weight of an undirected graph?
Given a weighted, undirected graph $G = (V,E)$, how can I compute the average weight of edges?
It seems an easy problem (divide the total weight to the number of edges!) but I couldn't manage to find the sum of the edge weights since each edge can be counted several times while iterating through the vertices.

# Answer
> 4 votes
If $w(i,j)$ is the weight of edge $ij$ then:

$avg = \frac{1}{2|E|}\sum\_{i\neq j}w(i,j)$.

Why $2E$ ? Because when traversing vertices you will calculate both edges $ij$ and $ji$. Since it's the same edge, you are adding its weight twice, so you need to remove this redundancy by dividing by 2.

# Answer
> 2 votes
Alternatively, without dividing by $2$, I would write:

$avg = \frac{1}{|E|} \sum\_{i} \sum\_{j\<i} w(i,j)$

as two `for` loops in code.

---
Tags: algorithms, graphs
---


# Question
Title: What is the difference between symbol and enumerated datatypes?
I wonder what differences and relations are between symbol and enumerated types?

> A symbol is a primitive datatype whose instances have a unique human-readable form
>
> an enumerated type is a data type consisting of a set of named values called elements, members or enumerators of the type.

Since a data type is a set of values, what exactly is the data type "symbol", and the data type "enumerated"?

It seems to me that a value in an enumerated type is just a symbol.

But the first quote says that "A symbol" is a data type, which contradicts with my thought that a symbol is a value.

# Answer
This is again much a question about terminology, without only history as a possible authority to determine "what is right".

These two kinds of values are very similar in the sense that they should be considered as atomic entities, distinguished only by their representation as a string of character over some alphabet, possibly with some minor constraints regarding the use of some characters (e.g., should start with alphabetic character,). These constraint are really immaterial, since what matters mainly is whether two symbols are the same or are different.

A **major difference** is that **the set of symbol is potentially infinite** (like the set of strings meeting the constraints) though actually limited by the implementation of the language, like anything else.

An enumerated type, is defined by giving explicitly an enumeration of the values of that type, which also have a representation as a string of characters. Since the enumeration is explicit, **there is only a finite number of values in an enumeration type**. Languages often consider that these values are ordered in by the order of the definition. Thus these **enumerated value can be compared for equality, of for order**.

**Symbols can only be compared for equality**. Sometimes, an arbitrary (alphabetical ?) ordering may be provided as it may help for some algorithms. But there is no semantics attached to it.

In a language, You usually have only one type for symbols. However, it is easy to make more when you have data abstraction available. Symbols are usually implemented like identifier tables in interpreted languages, and can actually stand for identifiers in meta-circular interpreters.

Enumerated types are defined by the programmer, and he may define several such types. One source of problems is that he may (at least in some languages) use the same name for different enumerated values, not in the same type of course, but in different enumerated types.

```
type month = (January, February, March, April, ...)
type girl = (Mary, April, Nancy, Ann, ...)
type city = (London, Paris, Nancy, Roma, ...)
type writer = (Hemingway, London, ...)

```

Of course, I am abbreviating illegally, since the list must be completely enumerated.

But if I use the identifier `Nancy` in the program, I may not know which is meant, the `girl` or the `city`. This can be resolved by various means (scoping, casting, etc.)

You do not usually get this problem with symbols, as there is only one type and a specific syntax for its values.

If you can define more by abstraction, then you usually have to use different syntaxes for the values. But this is getting into other issues.

For more specific points.

Your quote would be more accurate if it said "*Symbol is a primitive datatype ...*" A symbol is a value in that datatype.

It is likely that some people will talk of *symbols* for values of an enumerated type. Another word is *token*. But these two words have so many uses... Again, I do not wish to enter a terminology dispute. It is moderately constructive.
> 1 votes

---
Tags: terminology, programming-languages
---


# Question
Title: Sorting when there are only O(log n) many different numbers
We have $n$ integers with lot's of repeated numbers. In this list, the number of distinct elements is $O(\log n)$. What's the best asymptotic number of comparisons for sorting this list?

Any idea or hint or pseudo code? In fact I want to learn pseudo code.

# Answer
> 15 votes
Because you asked for minimum number of comparisons, so I assume the algorithm can only compare the numbers.

The idea is to extend the sorting lower bound argument. Assume you want to sort $n$ elements knowing there exist at most $k$ distinct values. There are $n!$ ways to permute the elements, but many of them are equivalent. If there are $n\_i$ element of the $i$th values. Each permutation is equivalent to $\prod\_{i=1}^k n\_i!$ other permutations. So the total number of distinct permutations is

$$\frac{n!}{\prod\_{i=1}^k n\_i!}$$

The number of required comparisons is bounded below by $$ \log\_2 \left( n!/\min \\{ \prod\_{i=1}^k n\_i! \big| \sum\_{i=1}^k n\_i = n, n\_i\geq 0\text{ for all } i\\} \right)$$

Good thing that minimization part can be easily shown by extend factorial to the continuous domain. $\min \\{ \prod\_{i=1}^k n\_i! \big| \sum\_{i=1}^k n\_i = n, n\_i\geq 0\text{ for all } i\\}$ is attained when $n\_i=n/k$. (note the $\log$ in the next computation is base $e$ for convenience)

$$ \log \left( n!/{(n/k)!^k} \right) = \log (n!) - k \log ((n/k)!) = n\log(n) - n\log(n/k) + O(\log n)= n(\log(n)-\log(n)+\log(k)) + O(\log n) = \Omega(n\log k) $$

$\log(n!) = n\log n - n + O(\log n)$ is Ramanujan's approximation.

To get an upper bound. Just consider storing the unique values in a binary search tree, and each insert we either increase the number of occurrence of an element in the BST, or insert a new element into the BST. Finally, print the output from the BST. This would take $O(n\log k)$ time.

Since both the lower bound and upper bound works for all $k$, the algorithm would take $O(n\log \log n)$ time for your problem.

**Addendum:**

I just figured out from @Pseudonym's comment that this proof also proves that we need at least $nH$ comparisons where $H$ is the entropy of the alphabet, so I might as well add this to the answer.

Let $c = \log 2$ and $p\_i = n\_i/n$. The entropy of the alphabet where the $i$th letter appears $n\_i$ time is $H=-\sum p\_i \log\_2 p\_i$. $nH = -\sum n\_i (\log\_2(n\_i)-\log\_2(n)) = \sum n\_i (\log\_2(n) - \log\_2(n\_i)) = c \sum n\_i (\log(n) - \log(n\_i))$.

\begin{align\*} \log\_2 \left( n!/\prod\_{i=1}^k n\_i! \right) &= \log\_2(n!)-\sum\_{i=1}^k \log\_2(n\_i!) \\ &= \log\_2(n!)-\sum\_{i=1}^k \log\_2(n\_i!) \\ &= c (\log(n!)-\sum\_{i=1}^k \log(n\_i!)) \\ &= c (n \log n-n + O(\log n) - \sum\_{i=1}^k n\_i \log(n\_i)-n\_i+O(\log n\_i)) \\ &\geq c (n \log n-n - \sum\_{i=1}^k n\_i \log(n\_i)-n\_i) \\ &= c (-n + \sum\_{i=1}^k n\_i(\log(n) - \log(n\_i))+n\_i) \\ &= c (\sum\_{i=1}^k n\_i(\log(n) - \log(n\_i))) \\ &= nH \end{align\*}

---
Tags: algorithms, sorting
---


# Question
Title: Algorithm to find most nodes in distinct cycles
I am trying to design a program where people trade objects within a fixed set of objects. They offer a single product, and designate a set of products they are willing to accept for that product. The job of the program is to involve as many people in a trade as possible.

To do this, I create a directed graph, where each edge points from a person who will give a product to a person who wants that product.

I want to find the distinct cycles (they don't share a node) that cover the largest subset.

How would I do that?

# Answer
Your problem is NP-complete (formulated as a decision problem), by reduction from SAT. For simplicity, I describe a reduction that uses self-loops, but they can easily be avoided.

Given an instance of SAT, create nodes for each variables and each clause. For each assignment of each variables, add directed cycles connecting the variable node with clause nodes satisfied by this assignment, for all possible such subsets (the empty subset corresponds to a self-loop). Since there are no parallel edges, we can also think of these cycles as resulting from a single cycle going through all satisfied clauses by taking all possible shortcuts not avoiding the variable node.

In the resulting graph, it is possible to cover all nodes of and only if the formula is satisfiable, completing the proof.

In practice, it might be possible to find good solutions heuristically, but that could depend on the nature of your instances.
> 1 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Is computation expression the same as monad?
I'm still learning functional programming (with f#) and I recently started reading about computation expressions. I still don't fully understand the concept and one thing that keeps me unsure when reading all the articles regarding monads (most of them are written basing on Haskell) is the relation between computation expressions and monads.

Having written all that, here's my question (two questions actually):

Is every F# computation expression a monad? Can every monad be expressed with F# computation expression?

*I've read this post of Tomas Petricek and if I understand it well, it states that computation expressions are more than monads, but I'm not sure if I interpret this correctly.*

# Answer
> 24 votes
First of all, *computation expressions* are a language feature, while *monads* are mathematical abstractions, so from this point of view, they are completely different *things*.

But that would not be a very useful answer :-). Computation expressions are a language feature that gives you a syntax which can be used for programming with computations (or data types) that have the monadic structure, but they can be also used with other structures. You can read my F# computation expression zoo paper for more details, but computation expressions can be used with:

* Monads, but also additive monads (what Haskellers call `MonadPlus` or `MonadOr`)
* Composed computations (what Haskellers call monad transformers)
* Computations that are monadic, but support other F# constructs like exception handling
* Monoids (and a couple of variations without monadic bind)
* Applicative functors (though this is only implemented in a research extension)

So, computation expressions are certainly closely linked to monads, but they are not linked to them that closely. This is in contrast e.g. with Haskell's `do` notation, which is much more closely linked to monads (although even that can be used with computations that are not strictly mathematically monads).

# Answer
> 7 votes
You can use computation expressions to express monads. There is an example here. Also, as you noted, you can use computation expressions for a lot more than just monads. There is an extended explanation about how they are different here. There isn't space here to explain the difference properly, but computation expressions are different from monads in that they reuse normal F# syntax and have the ability to add additional abstractions. A limitation is that its non-idiomatic (and difficult) to write a computation expression which is polymorphic over the type of computation.

---
Tags: functional-programming
---


# Question
Title: what would be the drawbacks of lecturing two programming languages simultaneously?
One colleage came with the idea/comment that it would be useful to lecture two programming languages, eg. Java and Scheme, at the same time while lecturing an Introduction to Programming course aimed for first term undergraduates.

I have my doubts that approach could stuck some students in learning the syntax of the programming language instead of the logic on how-to-program. Also I believe that some of them will get in their minds that Computer Science careers are equal to being a hardcore software developer.

While I have found some academic references about the last point I mentioned (that CS!=programming), I have not found any academic sustainable research that could prove wrong to teach two programming languages for an initial course, apart of discussions of lecturers against that idea in public forums. In ACM there is a paper in which they tried to lecture Python and Java at the same time, but the authors make so many assumptions and also mention a lot of pitfalls on their research, that I hardly believe it is a good article to be based on.

Has anybody found or read any article that mentions the advantages/disadvantages of that approach?

# Answer
> 5 votes
Avoid technical minutiae at all costs. Devote your focus to the big concepts you want to teach. I understand the desire to make the point that there is an underlying similarity between all programming languages, but I (personally) don't think the first course is the place to make that point. Rather, I would focus on problem solving using real-life applications.

I don't have any references to studies that would confirm or refute your specific hypothesis.

Here is an article by Lenore Blum (CMU) on what CMU has done to increase women's enrollment in computer science. CMU's experience with their introductory classes is discussed on page 8.

http://www.cs.cmu.edu/~lblum/PAPERS/women\_in\_computer\_science.pdf

And here are several newspaper articles about the changes they have been making at Tufts and Harvey Mudd (both of which have had significant increases in the number of women graduating from their CS programs.)

http://www.boston.com/news/education/higher/articles/2005/12/18/in\_computer\_science\_a\_growing\_gender\_gap/

http://www.nytimes.com/2012/04/03/science/giving-women-the-access-code.html

Here are several analogies that come to mind. See if you think any of them make any sense.

"We are going to teach Physics 101 by alternating lectures between MKS and cgs (or British Imperial Units). This will open the students minds to thinking more abstractly."

"We are going to be teaching our high-school students driving *safety* by having them drive a variety of different vehicles, including a sports car with a manual transmission, a large moving van with an automatic transmission, and an off-road four-wheel drive pickup truck. This is the only way we can get them to *generalize* the basic safety concepts from one vehicle to another."

"We've got a group of exchange students arriving from southeast asia that speak very little english. So we're going to teach their intro calculus class half in German and half in Russian, since so much of the research literature from the early 20th century is in those two languages."

"I'm going to post a few of your assignments on the web. But I'll also send a few to your university email address. And you should friend me on Facebook and follow me on Twitter and Instagram, because I'll post at least one of your assignments on each of those platforms. You need to learn these technologies sooner or later, so better sooner than later!"

"By the time a student graduates they need to be proficient at touch-typing on a keyboard. But we're not a vocational school, we're a university, so we're going to teach the *foundations* of touch-typing. Thus we alternate classes between the traditional QWERTY keyboard and the Dvorak layout, because we want the students to focus on the principles, not the details of one keyboard or another."

# Answer
> 1 votes
I know two professors who actually organized their programming course around two languages: ADA and CAML (CAML is the former version of OCAML, a version of ML used in Europe). That was in the 1990's, possibly a bit earlier. It lasted at least 10 or 15 years with great success. They even wrote a book for that course: Concepts et outils de programmation – December 1, 1997 by Thérèse Accart Hardin, Véronique Donzeau-Gouge Viguié.

The book is in French. It was supposed to be translated to English, but I think it finally did not happen.

All I know is that the course was very succesful, taught by both the authors in their respective institutions, and I do not recall ever hearing of any drawbacks, though I had several opportunities to discuss it. The two languages have very different syntax (but then, so do Scheme and Java). The idea was to compare and contrast the two languages, emphasizing imperative and functional style, while also showing the corresponding features of these two languages. The point was precisely to help student understand the logic of languages.

I should mention that both teachers were theoretician, specialized in formal semantics, with a good knowledge of language design.

It was probably used by other teachers, but I never thought of checking that.

I do not know whether they wrote a paper on their experience with that course.

It certainly shows that this can be done quite successfully.

AFAIK, both authors are now retired. But you can probably ask them about it by e-mail.

---
Tags: reference-request, programming-languages, education, didactics
---


title: Neural Network Weights per input nodes

text:
# Question
Title: Neural Network Weights per input nodes
Sorry, I'm really new to neural networks and this question is probably pretty obvious. If you have any resource that can help clarify these concepts to me it would be much appreciated.

The way I understand neural networks is that each input node, x i  goes to each hidden layer. Is there a unique weight for each input that goes into each hidden node?

with xi being inputs, h being hidden layers, and O being the output. Would the weight from x1 to h1 be different from the weight from x1 to h2? If I'm not on the right track, please correct me!

# Answer
Yes, each input value is weighted before being fed into the nodes in the next layer. Each input/output pair of "neurons" has its own weight and it is these weights that are adjusted by the neural network training process. The initial weights are typically random values before training begins.
> 2 votes

---
Tags: neural-networks
---


# Question
Title: tightest upper bound on binary search tree insertion?
The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced What will be the tighter upper bound on this,will it become O(logn) I have read that tighter upper and lower bounds are often equivalent to the Theta notation.

# Answer
For a binary search tree of $n$ nodes ,

Maximum height $=h\_{max}=n-1 = \Theta (n) =O(n)$

which happens in the case of skewed binary search tree as below if all elements of a binary search are either right-skewed or left-skewed

So in worse case , to add a new node in to an existing skewed binary search tree , it takes $n$ comparisons (comparison at each level).

So, time taken $= h\_{max}+1=n=\Theta\ O(n)$

---

Minimum height = $h\_{min}=\lceil \log\_2{(n+1)}\rceil-1=\Theta(\log(n))=O(\log(n))$

which happens in the case of complete binary search tree as below if all levels contains all elements except last level (Last level may be not contain all elements).

Now, number of comparisons $= h\_{min}+1=\lceil \log\_2{(n+1)}\rceil=\Theta(\log(n))=\ O(\log\_2(n))$

Which may be the tightest upper bound you are asking for .

So, you can use either $\Theta$ or $\ O$ notation here. $\Theta$ is tighter .

Whenever you use $\Theta$ you can replace it with $\ O$ but not viceversa .
> 0 votes

---
Tags: complexity-theory, algorithm-analysis, time-complexity, runtime-analysis, binary-trees
---


# Question
Title: The image of a recursive language under a computable function
Let $f:\Sigma^{\*}\to\Sigma^{\*}$ be a computable function and let $L$ be a recursive language. Is $f(L):=\left \\{{f(w)|w\in L} \right\\}$ recursive?

Here, I see clearly, that $f^{-1}(L)$ is recursive (simply by applying $f$ on an input $w$, and then see if $f(w)$ belongs to $L$).

My intuition tells me that $f(L)$ should also be recursive. For an input $w$, we should verify if there exists $x\in \Sigma^{\*}$ such that $f(x)=w$. We can apply $f$ on every word lexicographically. Surely, if $w\in f(L)$, the machine accepts. But otherwise, the machine does not halt. So maybe my intuition is wrong?

# Answer
> 5 votes
Inspired by this question, I have come up with the following.

Assume that $\langle\cdot\rangle$ is an encoding for TM's, for which the encoding of one Turing machine is never a prefix of the encoding of another.

Let $f$ be defined as the identity on an input which does not contain a TM enconding as a prefix. If the input contains such a prefix, $f$ returns this prefix.

$f$ is computable and it is well defined due to the encoding property.

Let $L=\left\\{ \langle M\rangle n \mid \text{$M$ halts on the empty input after $n$ steps} \right\\}$.

Then $L$ is recursive but $f(L)=\left\\{ \langle M\rangle \mid \text{ $M$ halts on the blank tape} \right\\}$ which is not recursive.

# Answer
> 4 votes
Here's an approach to this problem that doesn't involve imagination. $\\{f(w) \mid w \in L\\}$ is strongly reminiscent of the definition of a recursively enumerable set — specifically, a non-empty set $S$ is r.e. iff there exists some function $f$ such that $S = f(\Sigma^\*)$. If $f(L)$ was recursive for all total recursive $f$ and recursive $L$, it would mean that all r.e. sets would be recursive.

So let $S$ be a subset of $\Sigma^\*$ that is recursively enumerable but not recursive, e.g. the set of encodings of halting Turing machines. Its enumeration function $f$ is a total recursive function with the property that $f(\Sigma^\*)$ is not recursive even though $\Sigma^\*$ is.

---
Tags: computability, undecidability, closure-properties
---


title: Generalised 3SUM (k-SUM) problem?

text:
# Question
Title: Generalised 3SUM (k-SUM) problem?
The 3SUM problem tries to identify 3 integers $a,b,c$ from a set $S$ of size $n$ such that $a + b + c = 0$.

It is conjectured that there is not better solution than quadratic, i.e. $\mathcal{o}(n^2)$. Or to put it differently: $\mathcal{o}(n \log(n) + n^2)$.

So I was wondering if this would apply to the generalised problem: Find integers $a\_i$ for $i \in \[1..k\]$ in a set $S$ of size $n$ such that $\sum\_{i \in \[1..k\]} a\_i = 0$.

I think you can do this in $\mathcal{o}(n \log(n) + n^{k-1})$ for $k \geq 2$ (it's trivial to generalise the simple $k=3$ algorithm).
But are there better algorithms for other values of $k$?

# Answer
> 37 votes
$k$-SUM can be solved more quickly as follows.

* **For even $k$:** Compute a sorted list $S$ of all sums of $k/2$ input elements. Check whether $S$ contains both some number $x$ and its negation $-x$. The algorithm runs in $O(n^{k/2}\log n)$ time.
* **For odd $k$:** Compute the sorted list $S$ of all sums of $(k-1)/2$ input elements. For each input element $a$, check whether $S$ contains both $x$ and $-a-x$, for some number $x$. (The second step is essentially the $O(n^2)$-time algorithm for 3SUM.) The algorithm runs in $O(n^{(k+1)/2})$ time.

Both algorithms are optimal (except possibly for the log factor when $k$ is even and bigger than $2$) for any constant $k$ in a certain weak but natural restriction of the linear decision tree model of computation. For more details, see:

# Answer
> 15 votes
$d$-SUM requires time $n^{\Omega(d)}$ unless k-SAT can be solved in $2^{o(n)}$ time for any constant k. This was shown in a paper by Mihai Patrascu and Ryan Williams(1).

In other words, assuming the exponential time hypothesis, your algorithm is optimal up to a constant factor in the exponent (a polynomial factor in $n$)

(1) Mihai Patrascu and Ryan Williams. *On the Possibility of Faster SAT Algorithms.* Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA2010)

# Answer
> 5 votes
Here are a few simple observations.

For $k=1$, you can do it in $\Theta(n)$ time by scanning the array for a zero. For $k=2$, you can do it without hashing in $\Theta(n \log n)$ time. Sort the array and then scan it. For each element $i$ do a binary search for $-i$. This results in total complexity of $\Theta(n \log n)$. For the case $k=n$ you can do it in $\Theta(n)$ time by accumulating the array and checking the result.

For some more references, see The Open Problems Project page for 3SUM.

# Answer
> 0 votes
See http://arxiv.org/abs/1407.4640

A new algorithm for solving the rSUM problem Valerii Sopin

Abstract:

A determined algorithm is presented for solving the rSUM problem for any natural r with a sub-quadratic assessment of time complexity in some cases. In terms of an amount of memory used the obtained algorithm has also a sub-quadratic order. The idea of the obtained algorithm is based not considering integer numbers, but rather k∈N successive bits of these numbers in the binary numeration system. It is shown that if a sum of integer numbers is equal to zero, then the sum of numbers presented by any k successive bits of these numbers must be sufficiently "close" to zero. This makes it possible to discard the numbers, which a fortiori, do not establish the solution.

It's something new in this issue.

---
Tags: complexity-theory, combinatorics, complexity-classes, subset-sum
---


# Question
Title: Proving Quicksort has a worst case of O(n²)
I am sorting the following list of numbers which is in descending order. I am using QuickSort to sort and it is known that the worst case running time of QuickSort is $O(n^2)$

```
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class QuickSort
{
    static int pivotversion;
    static int datacomparison=0;
    static int datamovement=0;

    public static void main(String args[])
    {
        Vector<Integer> container = new Vector<Integer>();

        String userinput = "data2.txt";
        Scanner myScanner = new Scanner("foo"); // variable used to read file
        Scanner scan = new Scanner(System.in);

        System.out.println("Enter 1 to set pivot to be first element");
        System.out.println("Enter 2 to set pivot to be median of first , middle , last element of the list");
        System.out.println("Your choice : ");
        //pivotversion = scan.nextInt();

        try
        {

            File inputfile = new File("C:\\Users\\8382c\\workspace\\AdvanceAlgorithmA3_Quicksort\\src\\" + userinput);
             myScanner = new Scanner(inputfile);

        }
        catch(FileNotFoundException e)
        {
            System.out.println("File cant be found");
        }

         String line = myScanner.nextLine(); //read 1st line which contains the number of numbers to be sorted

         while(myScanner.hasNext())
         {
             container.add(myScanner.nextInt());
         }

        System.out.println(line);

        quickSort(container,0,container.size()-1);

        for (int i =0;i<container.size();i++)
        {
            System.out.println(container.get(i));
        }

        System.out.println("=========================");
        System.out.println(datamovement);
        System.out.println(datacomparison);

    }

    public static int partition(Vector<Integer> container, int left, int right)
    {
          int i = left, j = right;
          int tmp;

          int pivot= 0 ;
          pivot = container.get(left);

          boolean maxarraybound = false;

          i++;

          while (i <= j)
          {
                while ( container.get(i) < pivot && maxarraybound == false)
                {
                      if ( i == container.size()-1 )
                      {
                          maxarraybound = true;
                      }
                      else
                      {
                          i++;
                          datacomparison++;
                      }
                }
                while ( container.get(j) > pivot)
                {
                      j--;
                      datacomparison++;
                }
                if (i <= j)
                {
                      tmp =  container.get(i);// considered data movement??

                      container.set(i, container.get(j));
                      datamovement++;

                      container.set(j, tmp);
                      datamovement++;

                      i++;
                      j--;
                }
          };

          tmp = container.get(left);

          container.set(left, container.get(i-1));
          datamovement++;

          container.set(i-1, tmp);
          datamovement++;

          return i-1;

    }

    public static void quickSort(Vector<Integer> container, int left, int right)
    {
          int index = partition(container, left, right);
          if (left < index - 1)
                quickSort(container, left, index - 1);
          if (index+1 < right)
                quickSort(container, index+1, right);

    }

}

```

I am trying to prove to myself that the worst-case running time of QuickSort is indeed $O(n^2)$ by summing up the total number of **data comparisons** and **data movements** in the algorithm.

In my current situtation, I have an input of 10000 numbers.

I would expect a total sum of data comparison and data movement to be around 100 million.

I am only getting a total sum of data comparsion and data movement of around 26 million.

> I am sure I have miss out some "data movement" and "data comparsion" in my algorithm, can someone point out to me where as I have no clue?

# Answer
> 5 votes
Asymptotic bounds don't so much tell you how long to expect an algorithm to take, or how many operations it might perform, on a fixed input. Rather, the goal is to characterize how the time taken (or operations performed) by the algorithm grows for inputs of sufficient size. What $O(n^2)$ means is that the worst-case is bounded by some function that increases quadratically; that is, if you give your algorithm a worst-case input of size $n$ and then a worst-case input of size $2n$, you should expect your algorithm to take four times as long on the larger input (since $\frac{(2n)^2}{n^2} = \frac{4n^2}{n^2} = 4$) You might try a worst-case list of around 20,000 numbers and expect to see around 104 million operations.

Why do asymptotic notations work this way? Well, mathematics aside, it's useful for understanding how programs work. Different computers can execute at different clock frequencies, so absolute time measurements wouldn't be helpful for evaluating algorithms cross-platform (unless some reference architecture was used, which is also done, but bear with me). Code compiled for different architectures may perform more or fewer elementary operations, so an exact count of operations isn't really very useful in practice. Asymptotic growth, however, which tells you how an algorithm *scales*, and what to expect by way of comparison when you change the input size, is a pretty reliable indicator of how programs actually scale on any given system. You could compile your Quicksort for my x86, my friend's AMD64, my dad's ARM, and my grandpa's MIPS and you'd be able to observe the expected scaling behavior. Good luck getting the same number of operations for the same algorithm and input across those platforms!

# Answer
> 4 votes
Your question demonstrates some confusion regarding what asymptotic notations such as $O(n^2)$ and expressions such as “worst case” mean. I recommend reading the definitions and some examples. If you have a textbook, work through its exercises. Browse through our questions as well. Understanding comes from experience, so whatever you do, do work out some cases for yourself.

### Asymptotic behavior

> In my current situtation, I have an input of 10000 numbers.
>
> I would expect a total sum of data comparison and data movement to be around 100 million.
>
> I am only getting a total sum of data comparsion and data movement of around 26 million.

Asymptotic notation such as big oh counts up to a multiplicative factor. When we say that a running time is e.g. $\Theta(n^2)$, it doesn't mean that the running time is $n^2$ — that would lack a unit (is it $n^2$ clock cycles? $n^2$ seconds? …). It means that there is a multiplicative constant $C$ (which you can think of as a unit of measurement) such that the running time is about $C \\, n^2$. (Furthermore, this is the case only for large enough $n$, but here the data size is large enough.)

With a single point of measurement, you can't tell anything. Asymptotic notations don't give a value, they give a shape. If the running time of an algorithm is $\Theta(n^2)$, then for large enough $n$, if you plot the running time against the data size, the shape is (approximately) a parabola. This parabola could be at any scale. When you get a number of operations $T(n) \approx 26 \times 10^6$ for an input size $n = 10,000$, if it is indeed the case that $T(n) \in \Theta(n^2)$ and the input size is into the “asymptotic zone”, this tells you that the constant $C$ such that $T(n) \approx C \\, n^2$ satisfies $26 \times 10^6 \approx C \times (10^4)^2$. Note that the constant $C$ has a unit: it's a number of elementary operations.

If you want to test experimentally whether the running time is indeed $\Theta(n^2)$, you need to **test with multiple input data sizes**. Calculate the constant $C$ for each data size; if the hypothesis of $\Theta(n)$ behavior is correct, then you should get approximately the same value for large enough inputs. In other words, plot the running time against the data size, and check whether the shape does look like the expected parabola.

### Worst case vs upper bound

The notation $T(n) \in O(n^2)$ means that $T(n)$ is *at most* $n^2$, up to a scaling factor (multiplicative constant), for large $n$. The big oh gives an **upper bound**; it's possible that the function is in fact less than this upper bound (i.e. the upper bound is not optimal). For example, $n \in O(n^2)$ (because for all $n \ge 1$, $n \le 1 \times n^2$). The time complexity of quicksort is $O(n^2)$; it's also $O(n^3)$ and $o(42^n)$, but those statements are weaker and thus less useful.

The worst case of quicksort is $O(n^2)$ (and also $O(n^3)$, etc.). It is true that for most choices of pivot, the worst case is $\Theta(n^2)$. What this means, using $T(V)$ to denote the number of operations for the input $A$, is that
there exists $N$, $C\_1$ and $C\_2$ such that
for every $n \ge N$,
there exists an input $A$ of size $n$
such that $C\_1 n^2 \le T(A) \le C\_2 n^2$
and for all inputs $A'$ of size $n$, $T(A') \le T(A)$.

If you show that quicksort is $O(n^2)$ (i.e. at most $n^2$ for large $n$, up to a scaling factor), that obviously tells you that the worst case is $O(n^2)$, but there may be a better bound. If you want to prove that the worst case is $\Theta(n^2)$, i.e. that quicksort for large enough $n$ is sometimes approximately $C \\, n^2$ but never more for some $C$, it's enough to know that quicksort in general is $O(n^2)$ and that there is some input distribution (for every $n$) that's $\Omega(n^2)$, i.e. at least $C\_1 n^2$ for large enough $n$.

> I am sorting a list of numbers which are in descending order , should't it be a worst case scenario already???

There is no intrinsic relationship between the original order of the elements and the difficulty of sorting them. Sorting numbers that start out in descending order is not intrinsically harder than any other order. With quicksort, what input distribution constitutes the worst case depends on how the pivot is chosen. For example, if you always pick the first element as the pivot, input that is in ascending order and input that is in descending order both reach the $\Theta(n^2)$ worst case. If you always pick the middle element as the pivot, these two input distributions do not reach the worst case — an example worst case would be with the smallest element in the middle (position $\frac{1}{2} n$ rounded to an integer), the next smallest at position $\frac{1}{4} n$, the next at $\frac{3}{4} n$, the next four at $\frac{1}{8} n$, $\frac{3}{8} n$, $\frac{5}{8} n$, $\frac{7}{8} n$, and so on.

# Answer
> 1 votes
To answer your question directly, In the worst case, there will be `n-1` comparisons in the first recursion, `n-2` comparisons in the second recursion, `n-3` comparisons in the third, and so and so on, so actually, with `n = 10000`, I would expect the number of comparisons to be closer to 50,000,000.

As for the actual code, I think you need an additional `datacomparison++` after the `while ( container.get(i) < pivot && maxarraybound == false)` loop, as well as an additional `datacomparison++` after the `while ( container.get(j) > pivot)` loop. If you think about how `while` loops work, you will realize that an additional comparison is performed for the `while` loop to exit, which you are not counting.

I think with the above two changes, you may get something quite close to 50 million comparisons.

# Answer
> 0 votes
here is a writeup for an NYU CS lecture containing info/reasoning on why quicksort is $O(n^2)$ in worst case even with any choice of pivot algorithm, skip to section "Worst case of quicksort". others have pointed out why $O(f(n))$ notation is not really a formula for individual datapoints. as for finding $O(n^2)$ in practice, ie via empirical experiment/ exercise as you seem interested in, try writing code that repeatedly runs Quicksort on worst case inputs (previously sorted ascending or descending) of size $n..m$ and graph the results, and fit it to a function.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sorting
---


# Question
Title: Exponential-size numbers in NP completeness reduction
In the proof of Theorem 4 in \[GS'12\], the authors reduce an instance of PARTITION to their problem. Therefore, they create for each element $a\_i$ in the instance of PARTITION a number $2^{c \cdot a\_i}$ for a suitable constant $c$, which is later used in the reduction. They argue, that the instance remains of polynomial size since these exponential-size numbers can be encoded implicitly. Nevertheless, can we really work with those numbers in polynomial time? What if we add such two numbers $2^{c \cdot a\_i}$ and $2^{c \cdot a\_j}$ for $a\_i \neq a\_j$ in the course of the algorithm, then the resulting number cannot be encoded in this way any longer. Is this reduction valid?

\[GS'12\]: Martin Groß and Martin Skutella, "Generalized maximum flows over time", 2012.

# Answer
> 2 votes
Changing the encoding of the inputs changes the problem. When inputs are given succinctly the problem can become much harder. On the surface of what you are saying they are proving the NP-hardness of a succinct version of the problem, not the original problem.

You can also think of it as a reduction from Partition where numbers are given in unary to the original problem. The unary version of Partition is in P. So does not show the problem is NP-hard. (It might be possible to use 3-Partion in place of Partition which remains NP-hard even when numbers in the input are encoded in unary.)

The issue is that it is not clear what are the inputs to the problem. They seem to be working with a version of the problem where $\gamma$s are not part of the input to the problem but are determined from $\tau\_e$ which is part of the input. In the theorem it seems that $\gamma\_e$ is fixed to be $2^{c\tau\_e}$ (where $c$ is a fixed constant) and are not part of the input. If $\gamma$ is not part of the input and fixed to be determined from $\tau$ as stated then it doesn't matter that they are exponentially large.

In summery, the paper is not very clear in its treatment of the issue. It seems that in the theorem they are considering those numbers as not being part of the input to the problem (determined from $\tau\_e$). Or that they are given in a succinct form of $a2^e$. The paragraph after the theorem where they say that it is open whether the results holds in case the usual binary encoding of numbers is used seems to support that. So they are not proving that the problem where $\gamma$ is part of the input and encoded as normal binary numbers is NP-hard. That is still open according to them. They are proving that variants of the problem mentioned above are NP-hard.

# Answer
> 0 votes
As the authors mentioned, these numbers can be encoded using logarithmic orders. Therefore, whatever the power of this exponential is, it can be used and stored polynomially.

---
Tags: complexity-theory, reductions, np-hard
---


# Question
Title: Why comparison is dominant time consumption for comparison-based sorting algorithms?
Comparison-based sorting algorithms does a number of different operations to accomplish the sorting, why comparisons are the dominant time consumption? While I understand the standard analyses of asymptotical behavior of number of comparison operations, I don't quite understand why other costs of other types of operations are negligible.

\[Edit 2014-08-26\]

If I run the same mergesort implementation on two different computers (with possibly different architecture etc.), how to argue that running time of mergesort divided by the number of compares will approach (possibly different) constants as the problem size increases?

# Answer
> 1 votes
It mostly has to do with the nature of the algorithm. In selection or insertion sort, for example, the important work is the number of comparisons: the extra loop overheads are subsumed in the calculations. In essence, as @bellpeace noted, you add a loop operation with each comparison, so in the long run you're only adding a constant multiple to the work done. This would be different if you were considering, say, radix sort, where you aren't comparing elements but rather their bit values, which you can do without comparisons (more or less).

# Answer
> 1 votes
Because the number of comparisons dominates the number of other operations. Since costs of all operations are usually pretty much the same (within a constant factor), costs of non-comparison operations get eaten by constants in the asymptotic measure.

---
Tags: algorithm-analysis, sorting, comparison
---


# Question
Title: Complexity of Linear Diophantine equations
My question is simply, can linear Diophantine equations be solved in polynomial time? Specifically, I am looking at equations of the form $a\_1 x\_1+a\_2 x\_2 + ... + a\_n x\_n = k$, where $a\_i,x\_i,k$ are all integers, and solving for $x\_i$. The algorithm I am using is based off of the following journal article:

http://www.jstor.org/stable/3620787 .

The algorithm I derived from the article is roughly as follow:

1. Find a minimum coefficient (there could be many, just pick the any of them).
2. Take every coefficient that is not the one you picked in the modulus of coefficient you picked.
3. Check if any coefficients are 1, if so, go to 5.
4. Go to 1.
5. Back-substitute to find solution.

Currently, I have an incomplete argument that the algorithm is indeed polynomial time. My argument is as follows:

Suppose we choose the $a\_j$ that such that it minimizes the number of bits all of the coefficients are reduced by, thereby maximizing the number of iterations. Then, after we compute ${a^{'}\_{{i} \neq {j}} = a\_{{i} \neq {j}}} \mod {a\_j}$ we know that $a^{'}\_{{i} \neq {j}} \< {{a\_{{i} \neq {j}}} \over {2}}$, because if it were not, then $a\_j$ could go into $a\_{{i} \neq {j}}$ another time. On the next iteration, the previous minimum $a\_j$ cannot be the new minimum, since every other coefficient is less. Thus, the previous minimum will necessarily be reduced by one bit. Hence, all of the coefficients are reduced by at least 1 bit every 2 iterations. Thus, the maximum number of iterations is twice the maximum number of bits for a coefficient $2\log\_2(\max {a\_i})$, the back-substitution takes exactly the same number of steps, thus I estimate the algorithm is $O(\log(\max {a\_i}))$, which is polynomial time with respect to the number of bits in the coefficient representation.

Am I missing something or is this correct? Please let me know if there is anything I need to clarify.

# Answer
> 8 votes
Yes, this class of equations can be solved in polynomial time. In particular, there exists a solution if and only $\gcd(a\_1,\dots,a\_n)$ divides $k$. That condition can be tested in polynomial time, since there are polynomial-time algorithms to compute the gcd. In addition, if a solution exists, one can be found using the extended Euclidean algorithm.

---
Tags: complexity-theory, time-complexity, polynomial-time, integers
---


# Question
Title: Grammars: is there some connection between non-terminals $S$ and $S'$?
Given a grammar such as the following, does $S'$ have some special meaning or does it just denote another non-terminal like $B$, $A$, $P$, $Q$ etc.?

$$\begin{align\*} S &\to aBS'\\ B &\to b\\ S'&\to bA \end{align\*}$$

# Answer
$S'$ is just another nonterminal.

The reason $S'$ is used instead of, say, $T$, is that $S$ has been established as standard for the start symbol of a grammar. Now, if you are talking about an algorithm that transforms a grammar (e.g. into a normal form), you will need to distinguish between the start symbol of the original grammar and that of the transformed grammar. In order to indicate that both are start symbols, it has become the norm to use $S'$ for one of them (usually the latter).
> 4 votes

---
Tags: terminology, context-free, formal-grammars
---