# Question
Title: How to detect facial landmarks - using haar and other way?
I have done some projects using *haar cascade*(Ex.- Face-detection,Eye inside face detection,shoe detection etc), I also have some knowledge about it. I have trained my own models learning from youtube, this site etc.

Now I want to take it to the next level.

I want to detect facial landmarks, I have used different modules to do this, I have used **dLib**. But I want to learn more about it and as far as I know using multiple haar will be very much inefficient.

So how can I do this?

What I want to detect from the image :

# Answer
> 2 votes
There is a recent survey paper on exactly this topic: Wu & Ji, *Facial Landmark Detection: A Literature Survey*, International Journal of Computer Vision 127:2, February 2019, pp 115-142. That should give you pointers to everything you might want to know.

If you don't have access to Springer, here's the copy on arXiv.

# Answer
> 1 votes
Alternatively you should consider using deep learning for this. Current state-of-the-art methods in recognition (including facial landmark detection) are based on neural networks.

Several notable papers you might want to read are "OpenPose: Realtime Multi-Person 2D Pose Estimation using Part Affinity Fields" and "Simple Baselines for Human Pose Estimation and Tracking". In the given application people mostly predict human skeleton keypoints, however one can easily do it for facial landmarks too, just by changing the dataset, target and retraining.

Unfortunately dlib is not the best tool for deep learning, people mostly use keras (tensorflow) and pytorch.

---
Tags: computer-vision
---


# Question
Title: algorithm for number of subsequences containing at most k numbers with no element repeated in each of the subsequence
For e.g if the array is 2,2,3,3,5 and k=3 there are total 18 subequences 1 subequence of length 0(i.e empty subsequence) 5 subsequences of length 1

8 subsequences with length 2

4 subsequences with length 3

how to proceed?

# Answer
You can solve this using dynamic programming. Let me show instead the solution using generating functions, which can also be implemented using dynamic programming.

Suppose that there are $m$ distinct values in the array, appearing $n\_1,\ldots,n\_m$ times. The generating function $$ \prod\_{i=1}^m (1+n\_ix) $$ counts the number of subsequences with distinct values of size $k$, in the sense that this is the coefficient of $x^k$. For example, in your case $m = 3$ and $n\_1=n\_2=2,n\_3=1$. Therefore the generating function is $$ (1+2x)^2(1+x) = (1+4x+4x^2)(1+x) = 1+5x+8x^2+4x^3. $$
> 1 votes

---
Tags: combinatorics
---


# Question
Title: How to prove that in an AVL tree with height h, the depth of every leaf node is at least $\lceil h/2 \rceil$
I have an AVL tree with height h. I understand how to get h $\thickapprox$ 1.440 log N. However, I can't figure out how to calculate the minimum depth of a leaf node from root. I tried constructing a recursive formula where `d = 1 + min(dL, dR)` where dL and dR are the depths of the left and right subtree of the root. But can't get a solution of this. Can anyone help me out here?

# Answer
> 1 votes
Denote by $d(h)$ the minimum height of a leaf in an AVL tree of height $h$. One subtree of the root necessarily has height $h-1$, and the other one has height either $h-2$ or $h-1$ by the defining property of AVL trees. Therefore $$ d(h) = \min(d(h-1),d(h-2)) + 1. $$ Also, one checks that $d(0) = d(1) = 0$ (if one measures height as the maximum number of edges in a root-to-leaf path). The recurrence makes it clear that $d$ is monotone, and so $d(h) = d(h-2) + 1$. From here it's easy to calculate $d(h) = \lfloor h/2 \rfloor$.

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


# Question
Title: Maximum flow with maximum flow on specific edge
I am trying to solve the following problem:

We're given a network flow $(V,E,c,s,t)$ and an edge $(u,v)$. We have to provide an algorithm that computes the maximum flow which has maximum flow on $(u,v)$ also.

The idea that I had was, computing max flow and on the residual graph trying to compute a cycle that starts from $s$ and passes through the edge $(u,v)$ and trying to increase $(u,v)$'s flow while decreasing the flow from other edges. In other words, trying to maximize the flow of $(u,v)$ while preserving the maximum flow value. But I feel like there's a simpler way.

Can someone point me in the right direction? Is my thinking correct? If not how should I approach the problem?

Any help is appreciated! Thanks!

# Answer
I would do it kind of the other way around as you suggested.

First compute a flow that saturates $(u,v)$. This can be done with the Ford--Fulkerson algorithm. Look only for augmenting paths which contain $(u,v)$ and augment the flow until the edge is saturated.

In the second step you augment further, but avoid the edge $(u,v)$ when searching for augmenting paths in the residual network. There is no reason to desaturate $(u,v)$. If we desaturate the edge with one path and saturate it with another we can get to the same flow by augmenting with the "product" path which avoids $(u,v)$.

This is not a proof but should guide you in a possible direction how to solve this.
> 2 votes

---
Tags: network-flow
---


title: Compute highest-scoring segmentation

text:
# Question
Title: Compute highest-scoring segmentation
I have the following problem:

There is a "clean" sequence of sequences, say:

```
clean = [
    [1, 2],
    [3],
    [4, 5]
]

```

And a "noisy" sequence which is not segmented:

```
segmented = [1, 100, 2, 3, 3, 101, 4, 5]

```

I would like to partition `segmented` into exactly `len(clean)` parts such that the sum of the edit distances of each part and its clean counterpart is minimized.

For this example, one optimal solution would be:

```
optimal = [
    [1, 100, 2], # edit distance 1
    [3, 3],      # edit distance 1
    [101, 4, 5]  # edit distance 1
]                # total 3

```

It seems like a typical dynamic programming problem. My first thought was to use a similar algorithm to what TeX uses for line breaking, which brought me to SMAWK.

This is where I am stuck, because I cannot figure out the cost function. For regular line breaking, the function `cost(i,j)` is the cost of having a line go from index i to index j, like here. But for this problem, we would need a third parameter, namely which line in the clean reference to compare to.

Is this problem not conditioned correctly for SMAWK? Or is there a different cost function definition that I'm missing? Is there another, similar problem which has a more applicable solution?

# Answer
> 0 votes
I ended up finally solving this problem: I could not figure out how to use SMAWK for this, but I found a solution using the "typical" dynamic programming solution for edit distance.

The first observation was that the total edit distance of an ideal solution is equal to the edit distance of the unsegmented input and the concatenation of the clean segments. I have no mathematical proof, I just observed it.

The way I ended up doing it was storing a matrix of which edit operations were used in addition to the costs. In both matrices, `mat[i,j]` corresponds to "number of edit operations/final edit operation when using i entries of clean input and j entries of dirty input"

Then I backtrack the operations, decreasing i and j depending on which operation was taken. Whenever the i index crosses a boundary in the segmented clean input, I output one line. At the end, reverse the lines and I end up with an optimal solution.

# Answer
> 0 votes
I would suggest letting `cost(i,j,k)` be the cost of transforming \[the first `i-1` segments of `clean`, followed by the first `j` elements of the `i`th segment of `clean`\] into \[the first `k` elements of `segmented`\].

You can then write a recurrence relation that expresses `cost(i,j,k)` in terms of values of `cost(i,j-1,k)`, `cost(i,j,k-1)`, and `cost(i,j-1,k-1)` (with a convention that `cost(i,0,k) = cost(i-1,len(clean[i-1]),k)`). Then, you can use dynamic programming to fill in these values.

---
Tags: algorithms, dynamic-programming, search-algorithms
---


# Question
Title: Number of bits needed to represent an integer with a specifed base
How many bits are required to represent an integer $ x $ with base $b$?

# Answer
You could, if you wanted, encode each digit of the base $b$ representation of an integer in $\lceil \log\_2 b \rceil$ bits. This was actually done in the very early days of computing, when binary-coded decimal (BCD) encoding was used to store each digit of the decimal representation of an integer in four bits, from $0000$ for $0$ to $1001$ for $9$.

This somewhat simplifies user input and output (as long as your users always want to work in decimal). The downside is that it makes internal arithmetic more complex, and it wastes memory space. In BCD encoding one byte ($8$ bits) of memory can only store an integer between $0$ and $99$, whereas in binary encoding it can store any integer between $0$ and $255$.

All modern computers store integers internally in binary and do all their internal arithmetic in binary, and convert from or to other bases in their input and output as necessary.
> 1 votes

---
Tags: algorithms
---


title: Are computers infallible?

text:
# Question
Title: Are computers infallible?
(Not sure if this is the right place to ask this question.)

Let's say I get a computer to calculate 1+1. It should give 2, obviously. Will it always give 2? Is there any possible combination of circumstances that could cause a computer to, after finishing its calculations, give a number other than 2?

To illustrate what I'm thinking of, for humans the answer is "no" because if they're (e.g.) sufficiently drunk, they might get it wrong.

# Answer
> 2 votes
An algorithm may be infallible. Any physical computer can make an error e.g. if it is hit by a stray cosmic ray, a bolt of lightning or a large axe.

---
Tags: turing-machines
---


# Question
Title: How can mainstream OO languages support strong binary operations by classes?
Section 24.2 in *Types and Programming Languages* by Pierce compares ADT and existential objects,in terms of how well they support strong binary operations:

> Other binary operations cannot be implemented without concrete, privileged access to the representations of both abstract values. For example, suppose we are implementing an abstraction representing sets of numbers. After scouring several algorithms textbooks, we choose a concrete representation of sets as labeled trees obeying some particular complex invariant. **An eﬃcient implementation of the union operation on two sets will need to view both of them concretely,** as trees. However, we do **not want to expose this concrete representation anywhere in the public interface** to our set abstraction. So we will need to arrange for union to have privileged access to both of its arguments that is not available to ordinary client code—i.e., **the union operation must live inside the abstraction boundary**. We call such operations **strong binary operations**.

and says strong binary operations can't be expressed as methods of existential objects:

> Strong binary operations, on the other hand, cannot be expressed as methods of objects in our model. We can express their types just as we did for weak binary methods above:
>
> ```
> NatSet = {∃X, {state:X, methods: {empty:X, singleton:Nat→X,
> member:X→Nat→Bool,
> union:X→NatSet→X}}}
>
> ```
>
> . But there is **no satisfactory way to implement an object of this type**: **all we know about the second argument of the union operation** is that it provides the operations of NatSet, but these do not give us any way to ﬁnd out what its elements are so that we can compute the union.

but then says that mainstream OO languages provide support for strong binary operations by classes (instances of which are supposedly existential objects):

> **The classes in mainstream object-oriented languages like C++ and Java are designed to allow some forms of strong binary methods**, and are actually best described as a kind of compromise between the pure objects and pure ADTs that we have seen in this chapter. In these languages, the type of an object is exactly the name of the class from which it was instantiated, and this type is considered distinct from the names of other classes, even if they provide exactly the same operations (cf. §19.3). That is, a given object type in these languages has a single implementation given by the corresponding class declaration. Moreover, subclasses in these languages can add instance variables only to those inherited from superclasses. These constraints mean that every object belonging to type C is guaranteed to have all the instance variables deﬁned by the (unique) declaration of class C (and possibly some more). **It now makes sense for a method of such an object to take another C as an argument and concretely access its instance variables, as long as it uses only instance variables deﬁned by C**. This permits strong binary operations such as set union to be deﬁned as methods.

When a method in a class has an argument which is another object of the same class, how can the method "concretely access the instance variables" of the other object?

Does the book assume that the class makes the instance variables only privately accessible, and doesn't provide public accessible methods to access the instance variables? (I guess yes, because it seems to me that the third quote has the same situation as the second quote where it be impossible for `union` method on existential objects.)

Thanks.

# Answer
I will attempt an answer, though, the discussion in comments with @yuval-filmus seems to be going in the right way.

Let's recap: The book discusses ADTs against objects in their strictest sense.

ADTs are entirely public about their unique representation. Belonging in the ADT means satisfying said representation, and so binary methods can rightfully assume that both operands have that exact representation.

Objects are entirely opaque about their non-unique representation. Belonging in the object type means satisfying its interface, with no guarantees as to how this is achieved internally, and so binary methods may only assume that the two objects can respond to the same set of messages, but are quite possibly implemented entirely differently.

Even if the interface has a getter `getFoo`, that is no guarantee that the object has a `foo` field that you could poke at directly. Maybe some mock object is faking it with a method that returns a constant `Foo`. All you know as a client is that it supports a `getFoo` call.

---

Where the class-based object approach differs from the pure object approach is that the knowledge of the type of an object (the class it belongs to) gives you some guarantees about the structure of the object, and so, allows you to partially break the abstraction barrier. Because all objects of a class must have been built with, at least, a call to the constructor of that class, you can guarantee the presence of some fields (initialized during that constructor), and so the language lets you access those directly, foregoing the mandatory message-passing of the pure object style.

This is a strength and a weakness:

* because you have access to the concrete representation, you might be able to implement operations more efficiently,
* but because you ask for a member of the class, a "mock" implementation is no longer a valid object for this operation: if you want to allow such an object, you must define an interface, and you are effectively back to a pure-object approach.

---

As in my other answer to one of your question, this paper is extremely relevant:

http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf "On Understanding Data Abstraction, Revisited", by William R. Cook

Of particular interest are section 3.3 on autognosis, which hints at why binary methods in the ADT style are strong, whereas in the object style are weak, and section 5 which explains a bit the difference between what is considered a pure object approach and the more general objects available in Java. (You can program in the pure object style in Java, but you have to follow a given discipline about not breaking certain abstraction boundaries, which relates to the discussion you've had in the comments)

---

I hope this makes sense, I'm sorry you had trouble with my other answer, this is a hard topic to get your head around, but once you have fixed your misunderstandings you will see it is not that complex!
> 1 votes

---
Tags: programming-languages, type-theory, polymorphisms
---


title: Byte addressable vs Word addressable

text:
# Question
Title: Byte addressable vs Word addressable
I am trying to understand the difference between byte addressing and word addressing.

> A 4-way set-associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB.

No of sets in the cache $= (16 * 1024) / (4 * 8 * 4) = 2^7$

If word addressing is used :

Block offset $= 3 \ bits$

Since PAS is $4 \ GB$, total no of addresses = $2^{32} / 2^2 = 2^{30}$

So, total address bits $= 30\ bits$

Address structure :

Tag bits : $20 \ bits$
Set bits : $7 \ bits$
Block offset bits : $3 \ bits$

Now, suppose the CPU wants to access the 3rd byte of a particular word.

1. The cache controller will use the $7 \ bits$ set-field to index into a set and then comparing the higher $20\ bits$ tag-field with all of the $4$ blocks in the set. If a match is found, then cache hit occurs and the lower $3 \ bits$ block offset to put one of the word out of the $8$ words in one of the general purpose register. The CPU then extracts the 3rd byte from the word and perform the operation.
2. If tags are unmatched, then cache miss occurs, a memory read signal is sent and due to spatial locality of reference, a block containing the word is transferred into the cache.

If the CPU is byte addressable:

Total address bits $=32$

Address Structure : Tag bits : $20 \ bits$
Set bits : $7 \ bits$
Block offset bits : $5 \ bits$

If the CPU wants to access 3rd byte of a word:

1. Same as in Step 1 of word addressable, but the CPU now can directly address the 3rd byte of the word, using the lower $2 \ bits$ byte offset. However, I'm confused how that would happen. Since, the CPU register size has a width of 1 word, similar to the word addressing, one word out of the 8 words in the block will be transferred to the register. But how would the "byte extracting" step be easier here? And why do we call it byte addressing if still we are actually addressing a word?
2. Same as in Step 2 of word-addressing. Block of data will be transferred from the memory to the cache in case of cache miss.

Also, this answer says that physical memory is always byte addressable. Now, what is the difference between the addressablity of the memory and addressablity of the CPU architecture?

# Answer
> 0 votes
Word addressing means that, the number of lines in the address bus in the processor is lesser than the number of bits in the word itself.

Lets say we have a 4 byte word. (32 bit address space)

If this machine is byte addressable, then the address bus of the CPU will have 32 lines, which enables it to access each byte in memory.

If this machine is word addressable, then the address bus of the CPU will have 30 lines ($32 - log\_{2}4 =30$), which enables it to access memory **ONLY** in words/chunks of 4 bytes and that too from addresses which are a multiple of the wordsize.

Now if you ask the CPU to fetch a byte from a particular address, it will first drop the 2 least significant bits(by drop i mean overwrite them with 0's) of the address, fetch a word from the resulting address and return a byte using the 2 least significant bits as an offset within the fetched word.

This causes memory access time to increase, since the CPU has to spend more time modifying the address and processing the fetched word. But it also helps reduce hardware cost since the complexity of the circuits is reduced due to the reduction in address bus lines.

However, this overhead never arises in a byte addressable machine, hence 'byte extracting' is easier.

---
Tags: memory-access, cache
---


# Question
Title: With a grammar, does precedence and associativity change the accepted language?
When parsing, certainly precedence and associativity effect the AST. But, do precedence and associativity alter the set of accepted sentences? In other words, can precedence and associativity be "ignored" (defined in some random precedence all associating left, say) in the grammar, and then the AST fixed later based on (possibly dynamic) precedence and associativity conditions?

I am concerned only with LL grammars and their common variants.

# Answer
Precedence and associativity declarations are common in parser generators, but they are not part of the theory of context-free grammars. And nor are they part of the working of the LL(k) parsing algorithms (or, for that matter, the LR(k) algorithms). So there is no real way to answer that question in terms of the theory of formal languages.

On a practical level, you could perhaps look at popular parser generators and ask if the precedence and associativity declarations can alter the language recognised by the generated parser. In most cases, the answer will be "yes", but it depends considerably on how the precedence declarations are used to modify the generated parser.

I don't know enough about LL parser generators to answer that question for any of them, but it's quite clear precedence declarations for Yacc-based parser generators which use the mechanism described in the Dragon book can affect the set of recognised sentences. First, most such precedence declarations include the "nonassoc" declaration, which specifies that a particular operator cannot be used in a way which might require associativity. For example, a language in which `a < b < c` is illegal might declare `<` to be nonassociative, thereby removing the illegal construct from the language.

But even without "nonassoc", there are certainly cases in which forcing a reduction in a particular context can eliminate valid sentences. If, for example, you invert the precedence order used to resolve the "dangling else" ambiguity, you will make it impossible for the parser to recognize conditionals with "else" clauses.
> 1 votes

---
Tags: formal-grammars, parsers
---


# Question
Title: Forward edges in undirected graph using BFS
Introduction to Algorithms books claims BFS only classifies an edge for an undirected graph to be either tree or cross edge. But how about this simple example below where forward edges are naturally appearing?

Given graph with just 2 vertices A and B and 3 edges from A to B!

## exploring A adjacent vertices

(1) A-\>B (tree edge, A is now marked as an ancestor for B and B is A's descendant)

(2) A-\>B (forward edge? B is not yet processed (gray) and we found an edge to it from its ancestor(A))

(3) A-\>B forward edge using the same reasoning as in (2)!

What am I missing here?

# Answer
My example was a multigraph (multiple edges between a given pair of vertices is allowed). And in multigraph BFS does "produce" forward edges!
> 1 votes

---
Tags: graphs
---


title: How deep do neural networks need to be?

text:
# Question
Title: How deep do neural networks need to be?
My question is a bit on the philosophical side, and there is probably not one single 'correct' answer on this. Nonetheless, I'm curious to hear your opinion...

I'm currently designing a convolutional neural network to locate features in images taken by a microscope. These features are geometrically quite simple and similar to one another, with only minor contextual variations from image to image. When I look at modern general-purpose covnets, they often have tens of convolution/pooling layers, making them a bit heavy. I can imagine that one needs many layers of abstraction when detecting cars, cats, and cods all in once, which are very distinct from one another.

Returning now to my more specialist network: would it need as many conv/pool layers as a general-purpose covnet? Or should I consider a different strategy all together (like having more fully-connected nodes)?

**EDIT**: Based on the comments, I feel I should rephrase/clarify my question a bit. Recently I looked into the YOLO architecture, which seems to strike a nice balance between accuracy and speed. The original version of YOLO features 24 convolutional layers, and two fully-connected layers. When I ported this architecture into TensorFlow, I noticed my GPU was struggling memory-wise: TensorFlow would give numerous performance warnings related to an insufficient memory pool, and sometimes crash from running out of RAM on the GPU. YOLOv2 only has 9 convolutional layers, and has a smaller memory footprint.

In this paper it is claimed that YOLOv2 is more accurate than its bigger brother on various VOC test sets. However, this page says v2 actually performs a worse than its predecessor in terms of accuracy, because it has fewer layers. These contrasting claims made me wonder if more layers is really better in terms of accuracy.

Turning this question inside-out, one could ask if a deep, memory intensive architecture is really necessary if the problem is relatively simple (like detecting only a single object class, instead of one thousand), while maintaining good accuracy. Intuitively I'd say that the detection of objects defined by fewer features requires fewer layers, but when it comes to deep learning, intuition has failed me on several occasions already.

At present, I have yet to start training with either architecture, so I cannot directly perform experiments on my own input data and compare the outcomes. I had hoped there would be a general rule of thumb or general guidelines for a situation like this. The comments below seem to suggest there aren't. But perhaps after this clarification, someone could offer some more advice.

# Answer
The only way to know is to try it and see. There is no general theory that allows us to reliably predict the outcome of such experiments.

That said, I question the motivation. You say that it feels "a bit heavy", but it's not entirely clear to me what that concretely means or why it would matter. Perhaps it is worth mentioning that even with dozens of layers, neural networks can be surprisingly fast. Remember the warning about premature optimization: don't let a general fear or assumption that the simple solution might be slow tie you up in knots and lead you to overly complex solutions. Instead, in this case I suggest you try the simplest solution first, and measure how well it performs. Only if you have evidence that it fails in some concrete, measurable way would you then consider more complex approaches. This will help you avoid unnecessarily complicating your life.

Finally, remember that there are other approaches to computer vision other than deep neural networks. People were doing object detection before neural networks became popular, and there are other methods that might be effective for detecting simple geometric shapes (e.g., morphological operators, Hough transform, shape descriptors, and more). But try the simple things first, and measure.
> 4 votes

# Answer
A general rule of thumb would be: look at the most successful architectures for your given task, take it as a prior and try to vary (by retraining) the number of layers if you need a specific point in the accuracy-speed tradeoff curve.

Previously people believed that one can get more accuracy just by stacking more layers. Even though this is true in most cases, however one can also vary the number of neurons/filters as was done in Wide Resnets. In that paper the authors increased the width (filters) of the Resnet (which is one of the most widely used backbone architectures) and could get the same accuracy results with wide and shallow networks (20-50 layers) as much deeper networks (100+ layers).
> 1 votes

---
Tags: machine-learning, neural-networks
---


title: Doubts about Baker-Gill-Solovay

text:
# Question
Title: Doubts about Baker-Gill-Solovay
How am I supposed to read the P=?NP relativization proof? I am reading the classical paper Relativization of the P=?NP problem by Baker, Gill and Solovay, in particular the proof that there exist an oracle $B$ such that $\mathsf{P}^B \neq \mathsf{NP}^B$ on page 436. I have some questions and your help will be appreciated.

* The procedure does not seem to be an oracle but a deterministic algorithm.
* Is this construction a counterexample to P = NP?
* What does this mean "Run query machine $P\_i$ with oracle $B\_i$ on input $x\_i = 0^n$?" Does it mean that $P\_i$ asks

1. if $B\_i$ accepts $0^n$
    2. if $B\_i$ accepts any string of length $n$
    3. ONE BY ONE if $B\_i$ accepts a string of length $n$ from the canonical enumeration?
* I assume that the set $B$ or $B\_i$ is initially empty. Does it mean that the FIRST string of length $n$ from the canonical enumeration will always be added?

# Answer
> 2 votes
Let me answer your concrete questions:

* An oracle is a language. One way to describe a language is to give a procedure for constructing it.
* The construction is not a counterexample to P=NP. It shows that there exists an oracle relative to which P and NP are different. It also gives another oracle relative to which they are the same. Later, it was shown that P is different from NP relative to a random oracle (almost surely); recently this was extended to the entire polynomial hierarchy. The modern interpretation of such results is that diagonalizing techniques (techniques that would also work relative to an arbitrary oracle) cannot be used to settle the P vs NP question.
* "Run query machine $P\_i$ with oracle $B\_i$ on input $x\_i = 0^n$" has the following meaning. The machine $P\_i$ is an oracle machine — it is a Turing machine that has a special mechanism allowing it to access the oracle. We run $P\_i$ on the input $0^n$, i.e., the string of length $n$ consisting entirely of zeroes. Whenever $P\_i$ makes an oracle access, we answer according to $B\_i$.
* Your final question is a bit specific. I suggest trying to read the proof again, and if you fail, check a more modern account. Note that the result can be proved in several ways, so a proof appearing in a different source might be different.

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


title: Why is LinkedList useful?

text:
# Question
Title: Why is LinkedList useful?
If you implement a stack with a dynamic array-based with LinkedList you need more memory than with a dynamic array, and with dynamic array for insert in amortized cost is O(1), so the advantage of the LinkedList now is not and advantage, so why you should use a LinkedList, and why is this a useful data structure?

# Answer
> 2 votes
For a normal stack, the implementation on top of a linked list is indeed questionable. Many other uses of linked lists are disappointing in practice as well.

But consider a lock-free stack where `push` and `pop` are atomic. A singly-linked list can offer atomic prepend and atomic "remove head" using atomic Compare-and-Swap (some caveats apply). Implementing an atomic stack on top of an array is a bigger problem, one that to my knowledge has not been satisfactorally solved.

The downside that linked lists tend to weave their way somewhat randomly through memory can occasionally be turned into an advantage: elements that are in some other data structure can have a linked list weaved through them without imposing requirements on the addresses of the elements. For example, elements in a hash map can also have a linked list running through them that records their insertion order, while maintaining fast removal (a dynamic array that records the indexes of the elements in insertion order would still allow fast insertion but not fast removal since it could happen in the middle). Elements can even be in several different linked lists at the same time, an example of that is dancing links algorithm which uses linked lists for columns and rows and elements are in both a column and a row at the same time.

---
Tags: data-structures, arrays, linked-lists
---


# Question
Title: Does the distributive property apply to regular expressions?
Let $(Q,\Sigma,\delta, q\_0, F)$ be a finite automaton, does $$ (q\_1a+q\_2b)c=q\_1ac+q\_2bc $$

hold for any $q\_1,q\_2\in Q$ and $a,b,c\in \Sigma$?

Here $Sa=\\{\delta(q, a)\mid q\in S\\}$ and $qa=\\{q\\}a$ for any $S\subseteq Q$, $q\in Q$ and $a\in\Sigma$. The operation "$+$" means set union.

# Answer
since someone has edited the question, the question seems much more meaningful , and yes the above equality holds , here the equations

taking LHS of the equation

= ( $q\_1$a $+$ $q\_2$b ) c

=$\delta$ ( ( $q\_1$a $+$ $q\_2$b ) , c ) { as you defined Sa={ δ (q,a) ∣q ∈ S} }

=$\delta$ ( ( $q\_1$a ) $\bigcup$ $q\_2$b ) , c )

=$\delta$ ( ( $q\_1$a),c )) $\bigcup$ $\delta$ ( ( $q\_2$b ) , c )

=$q\_1$ ac $+$ $q\_2$bc

which is equal to RHS.
> 2 votes

# Answer
As pointed out by others your regular expression is wrong until you did not correct your definition of $q\_1$ and $q\_2$ to some input alphabets also i assume the same for a,b and c . If you correct this then your regular expression would make sense.

You first have to understand that a Regular expression is not an equation you can form from whatever (as you did by combining states and input alphabets) because regular expression denotes a "Set" in formal terms a "regular set". So any regular expression like "a + b" denotes regular set containing {a,b} as its elements .

Secondly there are specific rules to form the regular expression which accompany primitive regular expression and the operation you can define on them. Primitive are :

1. an input alphabet like "a" is a regex , in regular set it is {a}
2. an empty string "$\epsilon$" is a regex , in regular set it is {$\epsilon$}
3. a set that have no string that is "$\varphi$ ", in regular set it is empty set { }

Operation the above regular expression are : 1. union ( denoted by "+") , like " a + b " means {a ,b}

2.concatenation denoted by ( . ) , like "a . b" or simply "ab" means { ab }

3. kleene star closure of any of a regex like "$a^\*$", denotes { $\epsilon$, a, aa,aaa.....} ,also you can add an modified version of it which we say positive star closure like "$a^+$" denoting set { a, aa, aaa,aaaa,....}

so any regular expression violating above definition is not defined like "a+b+" does not convey anything . similary you are using $q\_1" as state in regex so it is not correct regular expression .

further i request you to look again your question and then ask again.
> 0 votes

# Answer
Your equation holds. Actually, more generally, for every subsets $S\_1$, $S\_2$ of $Q$ and for every words $u$, $v$ and $w$, the following equality holds $$ (S\_1u + S\_2v)w = S\_1uw + S\_2vw $$ Indeed, \begin{align} S\_1u &= \\{ p \in Q \mid \text{there is a path of the form $s\_1 \xrightarrow{u} p$ for some state $s\_1 \in S\_1$} \\} \\ S\_2v &= \\{ p \in Q \mid \text{there is a path of the form $s\_2 \xrightarrow{v} p$ for some state $s\_2 \in S\_2$} \\} \\ \end{align} Therefore \begin{align} (S\_1u + S\_2v)w &= \\{ q \in Q \mid \text{there is a path of the form $p \xrightarrow{w} q$ for some state $p \in S\_1u + S\_2v$}\\}\\ &= \\{ q \in Q \mid \text{there is a path of the form $s\_1 \xrightarrow{u} p \xrightarrow{w} q$ }\\ &\qquad\qquad\quad \text{for some state $s\_1 \in S\_1$ and some state $p \in Q$}\\} + {}\\ &\phantom{{}={}} \\{ q \in Q \mid \text{there is a path of the form $s\_2 \xrightarrow{v} p \xrightarrow{w} q$ }\\ &\qquad\qquad\quad \text{for some state $s\_2 \in S\_2$ and some state $p \in Q$}\\}\\ &= \\{ q \in Q \mid \text{there is a path of the form $s\_1 \xrightarrow{uw} q$ for some state $s\_1 \in S\_1$}\\} + {}\\ &\phantom{{}={}} \\{ q \in Q \mid \text{there is a path of the form $s\_2 \xrightarrow{vw} q$ for some state $s\_2 \in S\_2$}\\}\\ &= S\_1uw + S\_2vw \end{align} This is actually a good reason to prefer this algebraic notation to the $\delta$ notation.
> 0 votes

---
Tags: automata, finite-automata, regular-expressions
---


# Question
Title: Lexicographic Order of Expression [Automata Theory]
what will be kleene star "expansion" of expression $a^\*b^\*$ in lexicographic order? I'm confused and I really want to clear my concepts so I can proceed further

# Answer
The lexicographic order is defined on words, not on regular expressions. An interesting exercise is to describe the restriction of the lexicographic order to the language $a^\*b^\*$, assuming that $a \< b$. Note for instance that $1 \< a \< a^2 \< \dotsm \< a^n \< \dotsm$, but $\dotsm \<a^nb \<\dotsm \<a^2b \< ab \< b$.
> 2 votes

---
Tags: automata, regular-expressions, kleene-star
---


# Question
Title: Prove: If finite automata M with k states accepts a string with at least k characters, then the language L(M) is infinite
I need to prove that if finite automata $M$ with $k$ states accepts a string with at least $k$ characters, then the language $L(M)$ is infinite. I have no idea where to start. Any suggestions?

# Answer
**Hint**. Consider a word a length $\geqslant k$ accepted by $M$ and a successful path for this word. Now prove that this path goes at least twice through the same state, thus producing a loop.
> 3 votes

---
Tags: formal-languages, automata, finite-automata
---


# Question
Title: How to find all the edges shared by all diametral paths of a tree?
A *diametral path* in a graph is a shortest path whose length is equal to the diameter of the graph. Now, given a tree with $n$ nodes, I would like to find the set of edges (possibly empty) which are present in all diametral paths. Is there an efficient algorithm to do that?

I know how to do it in $O(n^3)$ which is basically to iterate over all pairs of leaf nodes, check if their distance is equal to the diameter (this can be done using LCA) and if it is then traverse the (unique) path connecting them adding 1 to a counter associated to each edge along the way, and finally count how many edges have their counters equal to the number of diameters. This should work but it's quite expensive, and for sure there must be a more efficient approach.

# Answer
An $O(n^2)$ algorithm is, for each edge, remove the edge and check the diameter of the tree (the forest now). If it did not change, then the edge is not in the set.

Finding the diameter of a tree can be done in linear time See here.

However, you can apply a greedy/dp trick for an $O(n)$ algorithm. First, root the tree at some vertex $r$. Hence, each vertex, except for $r$ gets a parent. You can then from the leaves up, find the distance from a vertex to the farthest leaf in its sub-tree. Actually, we will also keep the value of the longest path when the child having the current longest path is removed. After we compute all these values in a bottom-up manner, we go again top-down, computing for each vertex, the longest path from this vertex to a leaf not in its sub-tree. Now we can on $O(deg(v))$ compute for all edges incident to $v$ if there is a path of length equal to the maximum length and not using them.

The sum of the degrees is twice as large as the number of edges in The graph hence we get a linear total running time.
> 1 votes

---
Tags: algorithms, graphs, trees
---


title: Example of a locally trivial semigroup

text:
# Question
Title: Example of a locally trivial semigroup
I was having a look at the block product principle for finite monoids. I wanted to see the derivation of LTT = Acom$\*$LI, using an example. But I can't come up with a non-trivial example of a monoid in LI. Any help is appreciated.

# Answer
There is no nontrivial monoid in LI. LI is actually a (pseudo)-variety of finite *semigroups*: it is the class of finite semigroups $S$ such that, for every idempotent $e \in S$, $eSe = e$. If $S$ is a monoid, you can take $e = 1$, the identity of the monoid and get $S = 1S1 = 1$ so the monoid has to be trivial.
> 1 votes

---
Tags: finite-automata
---


# Question
Title: Why can System F1 a.k.a. λ → have kind `*`, but no quantification `∀`?
In *Types and Programming Languages* by Pierce, on p461 in Section 30.4 Fragments of

> 30.4.1 Deﬁnition: In System F1 , the only kind is `*` and no quantiﬁcation (∀) or abstraction (λ) over types is permitted.
>
> F1 is just our simply typed lambda-calculus, `λ →` . Its deﬁnition is super- ﬁcially more complicated than Figure 9-1 because it includes kinding and type equivalence relations, but these are both trivial: every syntactically well formed type is also well kinded, with kind `*`, and the only type equivalent to a type T is T itself

Is it correct that quantification  means universal types?

`*` is the kind of proper types, which are introduced on p442:

> The level of types contains two sorts of expressions. First, there are proper types like Nat, Nat→Nat, Pair Nat Bool, and ∀X.X→X, which are inhabited by terms. (Of course, not all terms have a type; for example (λx:Nat.x) true does not.)

So universal types such as `∀X.X→X` are proper types, and thus belong to kind `*`. Why can System F1 have kind `*`, but no universal types, i.e. quantification ?

But if System F1 could have kind `*` and quantification , then wouldn't it become the same as System F2 a.k.a. System F? Quoted from on p461:

> In System F2 , we still have only kind `*` and no lambda-abstraction at the level of types, but we allow quantiﬁcation over proper types (of kind `*`).
>
> F2 is our System F;

Thanks.

# Answer
> 1 votes
> Why can System F1 have kind `*`, but no universal types, i.e. quantification ∀?

Because "System F1 has types of kind `*`" does not mean "any types which have kind `*` in *some other system* (e.g. universal types) are allowed in F1".

---
Tags: programming-languages, type-theory, types-and-programming-languages
---


# Question
Title: Choosing which workers (limited number) to use in a binary assignment problem?
First of all, I am not completely sure whether this problem belong to the category of assignment problems so feel free to correct me in this case.

The problem:

We are given a set of $m$ workers $A = \\{ a\_1, a\_2,...a\_m \\}$ and a set of $n$ tasks $T = \\{ t\_1, t\_2,...,t\_n \\}$. Each worker either can or cannot perform any given task and there is no cost associated with a task. The set of tasks that can be performed by a single worker $a\_i$ is $T\_{a\_i} \subset T$. The set of tasks that can be performed by a subset of $s$ workers is given by the union of the tasks each individual worker can perform $\bigcup\_{i=1}^{s} T\_{a\_i}$ (not necessarily the first $s$ workers).

The problem is to select $s$ workers such that the number of task that can be performed is maximized, i.e. maximize the number of elements in $\bigcup\_{i=1}^{s} T\_{a\_i}$.

I couldn't find which category of problems this belong to, let alone any solutions. Any help in this matter would be greatly appreciated!

# Answer
Your problem is known as maximum coverage.
> 1 votes

---
Tags: algorithms, optimization, assignment-problem
---


title: Turing machines without time steps?

text:
# Question
Title: Turing machines without time steps?
In "More Is Different," an article about reductionism in science, the author makes the following off hand remark near the end:

> I find that at least one further phenomenon seems to be identifiable and either universal or remarkably common, namely, ordering (regularity or periodicity) in the time dimension... \[It\] is noteworthy that all computing machines use temporal pulsing.

As far as Turing machines go, this is true since there is a fundamental "time step" during which a symbol is read, the state is changed, and the read/write head moved. But this got me wondering: are there any non-Turing computing proposals without this fundamental time step?

# Answer
There are various models of analog computation, which embody computations which neither involve discrete states nor times. One of the more studied models is what might be called "Shannon machines" (after Claude Shannon): the General Purpose Analog Computer (GPAC).

Shannon's original formulation of GPAC could not compute certain functions, including the Gamma function. However, a 2007 paper cited in that Wikipedia article provides a reasonable reinterpretation of GPAC which turns out to be more powerful, enough so that the authors claim that "the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals."

Claude Shannon is well-known as a pioneer in digital computer design and particularly for his foundational work on information theory, but his genius and sense of whimsy led him to extraordinary achievements in other areas, and analog computation remained an interest throughout his life. One example is his mathematical analysis of juggling, including the construction of a prototype juggling robot. (See here for more information and a brief video including the robot.)
> 2 votes

# Answer
*Not* all computing machines use temporal pulsing. Turing machines don't.

What is more, not all computing machines perform all steps in order: asynchronous circuits don't. Distributed systems don't.

I believe the author is mixing up

1. computing as a discrete (stepwise) process
2. strictly sequential computing, in which no steps are executed concurrently
3. clock-based computing, in which steps happen in sync with a clock

You often have the first without the second, or the second without the third.

Modern CPUs use pipelining, in which steps do not happen in sequence. Modern software systems use pipelining in the large, in which multiple data processing units are combined into data flow networks or other types of communicating computational systems.

Strictly sequential, one-processor, one-instruction-at-a-time computing is conceptually simple and therefore attractive to theorists, educators, and people who want to build simple systems. Turing machines work that way. They are an example of the second type of system; they don't involve time, but they do perform their steps in strict sequential order.

As galdalf61 writes, the notion of algorithm is often limited to such strictly sequential computation. That doesn't mean actual computational machines or systems all work that way; they don't.

Similarly, basing everything on a clock makes digital circuitry easier to design, and it happens often, but not always.
> 0 votes

# Answer
The concept of sequentially performing one step after another seems to be inherent in our intuitive understanding of what constitutes an "algorithm", so it is present in one form or another in all useful models of digital computing. Even in a non-deterministic Turing machine, which can make multiple copies of itself at each step, each individual copy still executes its steps sequentially.

You can envisage a non-sequential "oracle" model which just "knows" the answer to every request/problem sent to it, and responds with that answer immediately - but that is not modelling what we understand an algorithm to be.
> -1 votes

---
Tags: turing-machines
---


# Question
Title: Are entities in a many-to-many relation related individually?
I know in *some* many-to-many relationships, an entity is related to other entities on *an individual basis*. But is this always the case?

For example, in the `Authorship` relationship between `author`s and `book`s. An author can write many books, and a book can have many authors. In each such connection, an author is individually connected to the book he/she authors, and vice versa, a book is individually connected to its authors.

However, in some cases, a group of things relate to another group of things. The relationship seems to be between the groups of entities rather than individual entities.

For example in the picture below, one road is drawn as two segments `i1` `i2` in one map, and three segments `j1`, `j2`, `j3` in the other map. In a sense, the two groups of segments form a one-to-one correspondence.

```
But does this situation constitutes a many-to-many correspondence in relational database theory?

```

If *yes*, this is weird, because unlike the authorship relationship, `i1` seems to have nothing to do with `j3` *individually*.

If *not* a many-to-many relationship, what is this kind of correspondence in relational database theory called? And how do we translate this to physical table design?

# Answer
> 2 votes
As far as I could understand, there are 3 entities here.

1. Map
2. Road
3. Road Segment

And the relationships between them are:

* Map M:N Road
* Road 1:N Road Segment
* Map 1:N Road Segment

A map could have multiple roads and a road could in multiple maps. A road could have multiple segments, in each map it is a part of. And a road segment would be related to one map and one road.

And to identify whether two segments are related to same road we can query the *Road Segment* entity to get which segments are related to same *roadId*.

---
Tags: database-theory, relational-algebra
---


# Question
Title: Does an ADT have multiple or only one representations/implementations?
Section 24.2 in *Types and Programming Languages* by Pierce defines ADTs in existential types:

> **A conventional abstract data type (or ADT)** consists of (1) a type name A, (2) a concrete representation type T, (3) implementations of some operations for creating, querying, and manipulating values of type T, and (4) an abstraction boundary enclosing the representation and operations. Inside this boundary, elements of the type are viewed concretely (with type T). Outside, they are viewed abstractly, with type A. Values of type A may be passed around, stored in data structures, etc., but not directly examined or changed—the only operations allowed on A are those provided by the ADT. ... We ﬁrst create an existential package containing the internals of the ADT:
>
> ```
> counterADT =
> {*Nat,
> {new = 1,
> get = λi:Nat. i,
> inc = λi:Nat. succ(i)}}
> as {∃Counter,
> {new: Counter,
> get: Counter→Nat,
> inc: Counter→Counter}};
>
> > counterADT : {∃Counter,
> {new:Counter,get:Counter→Nat,inc:Counter→Counter}}
>
> ```
>
> We can open it for example
>
> ```
> let {Counter,counter} = counterADT in
> counter.get (counter.inc counter.new);
> > 2 : Nat
>
> ```

Does the highlighted sentence in the following quote say that a ADT can have multiple representations/implementations?

> A key property of the kind of information hiding we are doing here is representation independence. **We can substitute an alternative implementation of the Counter ADT**—for example, one where the internal representation is a record containing a Nat rather than just a single Nat,
>
> ```
> counterADT =
> {*{x:Nat},
> {new = {x=1},
> get = λi:{x:Nat}. i.x,
> inc = λi:{x:Nat}. {x=succ(i.x)}}}
> as {∃Counter,
> {new: Counter, get: Counter→Nat, inc: Counter→Counter}};
>
> > counterADT : {∃Counter,
> {new:Counter,get:Counter→Nat,inc:Counter→Counter}}
>
> ```
>
> in complete conﬁdence that the whole program will remain typesafe, since we are guaranteed that the rest of the program cannot access instances of Counter except using get and inc.

Do the highlighted sentences in the following two quotes say that an ADT can have only one representation/implementation?

On p377:

> In summary, **the single representations of ADTs** directly support binary operations, while the multiple representations of objects give up binary meth- ods in return for useful ﬂexibility. These advantages are complementary; nei- ther style dominates the other.

From a reply to my previous question:

> **ADTs are entirely public about their unique representation.** Belonging in the ADT means satisfying said representation, and so binary methods can rightfully assume that both operands have that exact representation.

Why is the inconsistency?

Thanks.

# Answer
ADT is a *specification*. It can have many *implementations*. For an example, see this answer.
> 2 votes

---
Tags: programming-languages, type-theory
---


title: Perpendicular vectors out of a set

text:
# Question
Title: Perpendicular vectors out of a set
I stumbled on this problem and I wanna know if there is a better solution. There are $n$ 3d vectors with $x$, $y$, and $z$ components and I wanna find all pairs of perpendicular vectors in this set. Is there any better way than to verify all possible pairs of 3 vectors, some kind of optimization (not the obvious ones)?

# Answer
The problem can be solved in time $\tilde{O}(n^{4/3})$, using several algorithms:

There is an essentially matching lower bound due to Erickson, New lower bounds for Hopcroft's problem. See also Williams and Yu, Finding orthogonal vectors in discrete structures.
> 5 votes

---
Tags: optimization, computational-geometry
---


# Question
Title: Having a formal ISA specification - What does correctness mean?
Does this always mean that a program can be correct in regard to that spec or is there any correctness of the spec itself ?

# Answer
An ISA spec says how a processor should behave. A processor either conforms to such a spec (behaves exactly like the spec says it should), or it doesn’t (behaves differently in some situations).

ISA has nothing to do with correctness of programs. If a processor conforms to its ISA spec then all programs will behave as they should behave according to the spec, both correct and incorrect programs. If a processor does not conform to the ISA spec then programs can behave different from how they should behave.

A spec cannot be wrong, by definition. It can be nonsensical (like if the spec says that an “add” instruction should subtract, but it’s never wrong.

Reasons for having an ISA spec:

1. Instructing the team that designs the processor.
2. Instructing the team that writes test code to test the processor for conformance.
3. Instructing the team that writes a simulator for the processor which can be used before processors are available.
4. Instructing teams that write compilers for this processor.
5. Instructing support teams who handle customer complains about the processor behaviour, so they can check that the processor conforms to the spec.
> 3 votes

---
Tags: formal-methods
---


title: Coloring book. Finding region by point

text:
# Question
Title: Coloring book. Finding region by point
Let me explain what I want to achieve. I'm working on the coloring book project. On the input, I'm getting transparent images with black borders (Like this). Currently, I've created the 2D `Matrix` with colors in points. And basing on this `Matrix` I want to form an array of regions.

**Region:**

```
class Region {
    var set = Set<Point>()

    func contains(_ point: Point) -> Bool {
        return set.contains(point)
    }
}

```

The region represents points that form bordered parts(e.g. gun barrel, button, hat). My future logic will be this:

1. Users taps.
2. Get point.
3. Find the region that contains that point.
4. Color all the points in that region.

The problem is that I don't know how to form those regions :). Can you please help me solve this problem? Maybe it's some famous algorithm but I just don't know how to google it properly.

P.S. I hope this is the correct place to ask this kind of question.

# Answer
Once you get the point, you can use Flood Fill Algorithm to replace the current color in the region containing the point with the new color.

Basically, this algorithm starts from a specified point and then recursively(or iteratively) keep replacing the *current color* with the *new specified color* in the neighbouring points till it reaches the boundary of the region.

It detects the boundary by checking for points having different color(different from current and new color). So you don't have to detect/store the regions in advance.
> 3 votes

---
Tags: algorithms, matrix
---


# Question
Title: Big O analysis for problem where number of items searched is unknown
Consider this problem: you are searching an array of elements and are comparing the square of the current element to some number K. Essentially, you are looking to see if the square root of K is in the array. With this algorithm, chances are, you will not search the entire array because you will either find the square root or you will find that the square root is not in the array.

As such, you are searching only a fraction of the array, which lets say has M elements. Does this mean that the big O is still O(M), even though you are not searching all of the elements?

# Answer
> 1 votes
Big-O gives the upper bound function of any analysis. For an algorithm you could represent all (Worst, Average, Best) cases in Big-O notation.

In your case,

* **Worst case:** The required element is not present in the array (or is the last element of the array) : ***O(M)***
* **Best case:** The element is found in the first position itself: ***O(1)***
* **Average case:** Average of all possible case, i.e., the average time complexity of the cases where the element could be found at each possible position:

$$ \begin{align} = \frac{(1 + 2 + 3 + ... + M)}{M} \\ = \frac{M(M + 1)/2}{M} \\ = (M + 1)/2\\ = O(M) \end{align} $$

The average case is what you're looking for, which again ***O(M)*** only.

# Answer
> 0 votes
First, $O(M)$ means **not more** than $M$ modulo a constant factor when $M$ is large enough. So even if you find the element every time on the first try magically, $O(M)$ is still correct.

Second, suppose you meant it could be $o(M)$, which means strictly less than $M$ modul any given positive constant factor when $M$ is large enough. You are right in the following sense. The time-complexity of the best cases of this sequential search is $O(1)$.

Third, let us be interested in the average case. Since the better cases and the worse cases complement each other, the average time-complexity is $O(M/2)=O(M)$.

Lastly, the time-complexity of the worst cases is $O(M)$.

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Encoding algorithms better than or equivalent to Run Length Encoding
I have a table in which some values are repeated often as shown in the figure below. I want to encode that table such that it makes use of less memory. I have heard about run length encoding (RLE) but I would like to know if there are any other such encoding techniques or algorithms which can perform better than RLE or their performance is almost equivalent to RLE.

# Answer
There are many general-purpose compression algorithms, for example Lempel-Ziv and its many variants (used for example by `gzip`), and Burrows-Wheeler (used for example by `bzip2`). You can just try them on your input and see how well they perform. If your data has particular structure, then it is possible that a dedicated compression algorithm would perform significantly better, but it's hard to tell without knowing more about the structure.
> 3 votes

# Answer
For particular, known, and fixed data, there exist any number of custom encoding schemes (In practice, almost certainly specifically designed by the user for this purpose) to optimally represent those data under the encoding scheme. For instance, any encoding scheme for which

```
your-table => 1

```

where `1` is an unambiguous encoding would improve over a standard RLE of your data.
> 1 votes

---
Tags: algorithms, encoding-scheme
---


# Question
Title: Complexity analysis using big - O, Omega and Theta notation
I was reading a research paper and there I read the following:

$t=O\left(d^{2} \log \_{d}^{2} n\right)$ matches the lower bound $\Omega\left(d^{2} \log \_{d} n\right)$ in the regime where $d=\Theta\left(n^{\alpha}\right)$ for some $\alpha \in(0,1)$.

It also says $t=O\left(d^{2} \log n\right)$ outperforms $t=O\left(d^{2} \log \_{d}^{2} n\right)$ in the regime where $d=O(\operatorname{poly}(\log n))$

I am not sure how to verify these statements? I understand the basics of all the complexity notations, but how can we mathematically prove this?

# Answer
When $d = \Theta(n^\alpha)$, we have $\log\_d n = \Theta(1)$, and so there is no difference between $d^2\log\_d^2 n$ and $d^2\log\_d n$ (or rather, the two differ only by a constant factor).

When $d$ is polylogarithmic in $n$, $\log\_d n = \log n / \log d = \Theta(\log n/\log \log n)$, and so $\log^2\_d n = \Theta((\log n / \log\log n)^2)$ is asymptotically larger than $\log n$.

For what values of $d$ are $\log^2\_d n$ and $\log n$ asymptotically the same? We need $\log^2n/\log^2d = \Theta(\log n)$, and so $\log d = \Theta(\sqrt{\log n})$, i.e., $d = 2^{\Theta(\sqrt{\log n})}$. This is more than polylogarithmic but less than polynomial in $n$.
> 2 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, big-o-notation
---


# Question
Title: Why multiplying float number by multiple of 10 seems to preserve better precision?
It is famous that for float numbers:

```
.1 + .2 != .3

```

but

```
1+2=3

```

It seems that multiplying floats by 10 allows you to preserve more precision. To further illustrate the case, we can do this in python:

```
sum([3000000000.001]*300)
#900000000000.2957

sum([3000000000.001 * 1000]*300) / 1000
#900000000000.3

```

By multiplying each element in the list by 1000 and divide the sum of the list by 1000, I can get the "correct" answer. I am wondering: 1) why it's the case. 2) Will this always work, and 3) At what magnitude, will this method backfire, if it will.

# Answer
The only numbers that can be stored exactly are rational numbers whose denominator is a power of 2 (read any source on floating point numbers to understand why). For example, floating point numbers do satisfy $$ 1/4 + 2/4 = 3/4 $$ but do not satisfy (or rather, don't necessarily satisfy) $$ 1/3 + 2/3 = 3/3. $$ There's nothing magical about the number 10. It's just an artifact of the common decimal representation. So in general it won't help to multiply by a power of 10.
> 3 votes

# Answer
To understand that, you need to understand how floating point numbers are stored n memory.

Basically, it’s not possible to store the decimal part exactly (*precisely*). So, they are approximated to the nearest value which could be stored. Hence, they loose some precision while storing.

And hence, the above mentioned behaviour.

If you want more insight on what exactly is happening in the memory, try understanding how exactly the above mentioned numbers are getting stored, by referring to Floating-point arithmetic
> 1 votes

---
Tags: floating-point
---


# Question
Title: Minimum Path cover in a Directed Acyclic Graph
Given a weighted directed acyclic graph $G=(V,D,W)$ and a set of arcs $D'$ of $D$, where the weights of $W$ are on the vertices. The problem is to partition $G$ into a minimum number of vertex-disjoint paths that cover all the vertices of $G$ subject to the constraints that:

1. the weight of each path is at most $k$.
2. each path should include at least one edge of $D'$.

What is the complexity of this problem?

# Answer
> 1 votes
This answer shows this problem is NP-hard. Further research is needed to determine whether it belongs to APX or it is APX-hard.

Let $G$ be a complete directed acyclic graph, i.e., you can name the vertices $1,2,\ldots,n$ and there is an edge $(i,j)$ for all $i\<j$. Let $D'=D$, and $k$ is equal to half of the sum of the weights of all vertices. Now there exist 2 vertex-disjoint paths satisfying your conditions if and only if the weights can be partitioned into two subsets both with sum $k$, which is exactly the partition problem. Hence, your problem is NP-hard.

---
Tags: algorithms, complexity-theory, graphs, weighted-graphs, hamiltonian-path
---


# Question
Title: Prove that a language is bounded if and only if it's finite
Let's assume $L$ is a language. $L$ is *bounded* if for some natural number $n \in \mathbb N$ applies $|x| ≤ n$, where $|x|$ is a length of a string, with every $x \in L$. Let's also assume that $L$ lies in a finite set of alphabets $\Sigma$.

How to prove that $L$ is bounded if and only if it's finite?

# Answer
The claim holds only for languages over finite alphabets.

### Bounded $L$ $\implies$ Finite $L$

Let $\Sigma$ be the alphabet of $L$ and $L$ be bounded by some $n \in \mathbb{N}$.

The largest possible such $L$, call it $L^\\#$, is $\bigcup\_{\\,i=0}^{\\,n} \Sigma^i$ elements. $L^\\#$ is finite since $|L^\\#| = \sum\_{i=0}^{n} |\Sigma|^i$. Therefore, any $L \subseteq L^\\#$ must also be finite.

### Finite $L$ $\implies$ Bounded $L$

Let $x^\\#$ denote the longest string in $L$. Such a string must always exist since $L$ is finite.

Then, $\forall x \in L \ldotp |x| \leq |x^\\#|$ and thus, $L$ is bounded.

---

A simple counterexample to the infinite alphabet case:

Consider an infinite alphabet $\Sigma = \\{ s\_0, s\_1, ... \\}$. The language $L = \Sigma$ is bounded since $\forall x \in L \ldotp |x| \leq 1$, but is infinite.
> 1 votes

---
Tags: formal-languages, regular-languages, finite-automata
---


# Question
Title: Proof high-entropy sequences are hard to compress
When comparing random-variable sequences generated from probability distributions, what's a formal proof that a distribution with higher entropy produces a sequence that's "harder" to compress?

In background reading, I haven't come across this analysis for a general, abstract probability distribution. The information theory texts I've looked at, rather, tend to focus their analysis on comparing compression algorithms rather than comparing the distributions producing the data.

# Answer
> 1 votes
You are looking for Shannon's source coding theorem.

---
Tags: data-compression, entropy
---


title: Distributed Algorithm Problem

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

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

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

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

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

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

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

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

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

---
Tags: algorithms, distributed-systems
---


# Question
Title: Is the tree shown a valid red-black tree?
I have made a red-black tree and I think that it is not valid. Could someone please verify?

```
            B
         /    \
        /      \
       /        \
      /          \
      R           R
    /  \       /      \
   B    B     B        B
            /   \     /  \
            R    R   R    R
           / \  / \ / \  / \
          B  B  B B B  B B  B

```

As far as I know, in red-black tree we also consider the leaf nodes at the NULLS of the visible leaf nodes and these NULL nodes are considered to be black.

* If we consider the order `root->left->left->left` as black, then number of black nodes to that NULL node are 2.
* If we consider the node `root->right->right->right->right->right` as black, then number of black nodes to that NULL node are 3.

So, according to the above argument, it should not be a valid red-black tree. Am I right or am I missing some important concept?

# Answer
> 2 votes
You are correct $-$ the red-black tree you have drawn is not *balanced*.

For a balanced red-black tree, the number of black nodes between the root (including itself) and any leaf node (including itself) must be a constant. This is called the *black height* and should be a constant number that is the same regardless the path along which it is computed.

However for your tree, the path `00` results in a black height of $2$ and the path `1000` results in a black height of $3$. `0` = go left, `1` = go right.

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


# Question
Title: Finding f(x) using a BPP algorithm (optimization problem to decision problem)
Say there is a function $f:\mathcal{X} \mapsto \\{1, 2,...,n\\}$. We want to solve a specific instance of $f(x)$.

We have black box access to a BPP algorithm where it takes $T$ time to answer $\\{YES, NO\\}$ to $LessThan(x,k) := f(x) \< k$ and has error probability of $1/3$.

1) How can you solve $f(x)$ in time $O(T\log n \log \log n)$ with error probability $1/3$ using $LessThan$?

2) How can you use $LessThan(x,k)$ to implement a new algorithm called $ImprovedLessThan(x, L, H)$ where it returns:

```
    HIGH when (L+H)/2 < f(x) < H
    LOW when L < f(x) < (L+H)/2
    OUT OF RANGE when f(x) is outside of [L,H)

```

and has error probability $1/3$ and runs in $O(T)$ time.

3) How can you use $ImprovedLessThan$ to solve $f(x)$ in $O(T \log n)$ time with high probability?

**Thoughts so far:** For 1) we are using $LessThan$ to do a binary search (or, traverse a binary search tree). We start with $k = n/2$. If $LessThan$ returns $YES$, we update to $k=n/4$. Similarly, we update $k= 3n/2$ for $NO$. I understand we may traverse the the tree incorrectly and have some need to backtrack. I don't see how we end up with $O(T\log n \log \log n)$ time and how are error probability stays bounded.

For 2) it's clear to me that given inputs $L$ and $H$, we can just set $k = (L + H)/2$ and call $LessThan(x, k)$. It's also clear that we want to detect incorrect traversals as early as possible to get a better upper bound on time. Not sure where to go from there though.

For 3) I'm not sure how to get high probability guarantees. I just know that if we make $\log n$ correct moves in a row, then we will probably be at the correct answer.

Generally, I'm having a hard time turning my notions about the answer into something rigorous.

# Answer
The binary search algorithm that you describe in your answer for Question 1 will have error probability almost 1, in the worst case. Suppose that $f(x) = 1$. In order for your algorithm to be correct, it needs to make no mistake during the binary search which happens with probability $(2/3)^{\log\_2 n} = 1/n^{\log\_2(3/2)}$.

In order to fix this, you need to boost the success probability of each step to $1-1/(3\log n)$, which you can do by repeating each comparison $O(\log \log n)$ times and taking a majority vote. Analysis (using Chernoff's bound) left to you.

Question 2 is quite simple — you just need to compare your input to $L,\frac{L+H}{2},H$, repeating the comparison $O(1)$ times to boost the success probability.

The algorithm underlying Question 3 is a bit complicated. It is described in Section 3 of Feige, Raghavan, Peleg and Upfal, Computing with noisy information. Roughly speaking, we perform binary search as usual (without boosting the success probability). Sometimes we will notice that we have made a mistake at some point in the past (this happens when we get "out of range"). We then backtrack until we no longer get "out of range". On expectation, we make progress (progress is measured as the size of the common prefix of the correct path through the decision tree underlying binary search, and the one undertaken by the algorithm). In order to boost the success probability, we continue the binary search for a few more steps even after locating the correct cell.
> 1 votes

---
Tags: algorithms, complexity-theory, decision-problem, randomized-algorithms
---


# Question
Title: Non-recursive (iterative) DFS with $O(n)$ size stack
I usually deal with traversal algorithms such as DFS and BFS, and I have to implement them iteratively. However, in case of DFS, one challenge is that the size of stack can be $O(n+m)$ in worst case.

I was wondering if there is an iterative implementation of DFS that requires an $O(n)$ size stack instead of heavy $O(n+m)$ stack. I know that this is a worst case analysis, but I am concerned with this and want this to be really bounded.

Just as a reference, I am copying the algorithm from this solution, where vertices can be pushed into stack more than once and in the worst case, the stack size can be $O(n+m)$:

```
DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)

```

# Answer
You can keep only the topmost copy of a node on the stack:

```
dfs(source):
   s <- empty stack
   visited <- {}
   on_stack <- map<node,stack element>
   s.push(source)
   on_stack.add(source,s.top())
   while s is not empty:
      current = s.pop()
      on_stack.remove(current)
      if visited.contains(current):
         continue
      # handle current
      visited.add(current)
      for v a neighbor of current:
         if on_stack.contains(v):
            stack_element <- on_stack.get(v)
            unlink stack_element from s
         stack.push(v)
         on_stack.add(v,s.top())

```

If your stack is a linked list, the asymptotic runtime stays the same. I doubt however that it will be much faster in practice unless your graphs are very dense, because the constants involved are much bigger.
> 3 votes

# Answer
You can have a look on DFS-B in http://web.cs.unlv.edu/larmore/Courses/CSC477/bfsDfs.pdf

> DFS-A can have multiple copies on the stack at the same time. However, the total number of iterations of the innermost loop of DFS-A cannot exceed the number of edges of G, and thus the size of S cannot exceed m. The running time of DFS-A is O(n + m). It is possible to write a DFS algorithm where no vertex is ever in the stack in more than one place, but it is somewhat trickier. We give such an algorithm, DFS-B, below.

```
DFS-B(G,s)
    for all v in V[G] do
        visited[v] := false
    end for

    S := EmptyStack
    visited[s] := true
    Push(S,s)

    while not Empty(S) do
        u := Pop(S)

        if there is at least one unvisited vertex in Adj[u] then
            Pick w to be any unvisited vertex in Adj[u]
            Push(S,u)
            visited[w] := true
            Push(S,w)
        end if
    end while

```
> 2 votes

# Answer
I think an even better approach is the solution on C# which I developed for similar problem - https://github.com/kostadinmarinov/scc

```
dfs(verticies, getNeighbours):
    visited <- {}

    return recursiveSelect(
        filter(verticies, (vertex): visited does not contain vertex),
        (vertex): dfsNext(vertex, visited, getNeighbours))

dfsNext(vertex, visited, getNeighbours):
    visited.add(vertex)

    for each neighbour in getNeighbours(vertex) do
        if visited does not contain neighbour then
            yield neighbour
        end if
    end for

filter(source, predicade):
    for each element in source do
        if predicade(element) then
            yield element
        end if
    end for

recursiveSelect(source, childSelector):
    stack := empty stack
    enumerator := source.getEnumerator()

    while enumerator has next OR stack is not empty do
        if enumerator has next then
            element := enumerator.current
            yield element

            stack.push(enumerator)
            enumerator := childSelector(element).getEnumerator()
        end if
        else if (stack is not empty) then
            enumerator := stack.pop()
        end if
    end while

```

The last method is taken from https://stackoverflow.com/a/30441479/7995961

Here the stack frame is automatically generated by the iterator's state machine which we just push in our stack. This implemented with that extension method is just a perfect generic transformer of recursive algorithms to iterative ones without changing the design of the algorithm.

PS: The above is a generic solution for any recursive algo. Here is a simplified version of the same workflow as the generic one for the specific case of DFS algo:

```
dfs(verticies, neighbours):
    stack := empty stack
    visited <- []

    for each entryVertex in verticies do
        if not visited[entryVertex] then
            stack.push([entryVertex, -1])

            while stack is not empty do (
                [vertex, i] := stack.pop();

                if i = -1 then
                    visited[vertex] := true
                    i := 0
                end if
            end while

            while i < neighbours[vertex].length do
                if not visited[neighbours[vertex][i]] then
                    stack.push([vertex, i])
                    stack.push([neighbours[vertex][i], -1])
                    break;
                end if

                i := i + 1
            end while
        end if
    end for

```

As you see in the stack we need to keep the state of iteration also - it could be either an enumerator object or the index of a list. This is also combined with immediate interruption of the execution for the current vertex and going into the last found not visited neighbour. The state of iteration (list index) defines also 2 more states - before the loop (i = -1) and after the loop (i = n). It's very helpful in case of steps before and visiting the neighbours.
> 1 votes

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


# Question
Title: Is "sparse subtree" an appropriate term for what I describe in this question?
Given a tree, with *some* nodes annotated, such that the annotations form another tree, I'm thinking "sparse subtree" is an appropriate term for describing the latter tree as it relates to the original tree. But I'd like to check with y'all because I plan to use the term in writing for an audience that will include CS savvy folk.

If not, I think "tree formed by the annotated subset of the nodes of the tree" will work but am hoping one of y'all will suggest something snappier than that.

# Answer
# 2021 update: "embedded subtree"

In a discussion elsewhere8, I just encountered a term of interest with its own Wikipedia page: induced subgraph. This was roughly the sort of term I was after when I asked my original question, though it doesn't nail it.

It led me to google for "induced subtree". That has 80 matches and looked more appropriate for what I was after. But it still wasn't right because it disallows ancestor-descendant pairings that aren't parent-child.

That led me to "embedded subtree" in this paper which notes:

> \[In contrast to "induced subtrees"\] Embedded subtrees ... allow not only direct parent-child edges, but also ancestor-descendant edges.

So maybe that's the right term.

On the other hand it still doesn't cover what I'm calling "annotation" -- the key notion that the nodes in the "subtree" are *paired* up with a subset of nodes in the original tree but are not actually the same nodes.

So due to that technical aspect, and for aesthetic reasons, I currently feel my original answer, which follows, remains as acceptable as it ever was. ;)

# *AST*

This self answer defines the terms and acronyms I've made up to refer to what I asked about.1

The terms I've made up are general definitions of two kinds of tree data structure. I define them more precisely in later sections but in summary they are:

* ***A Sparse Tree*** aka **AST**. A sparse subset of a tree.
* ***Annotated Subset Tree*** aka **AST**. A sparse tree formed via "annotation".

Why define terms to distinguish the concepts when their acronyms eliminate the distinction? Because the mental modelling utility of eliminating the distinction is what I wanted to emphasize first and foremost, while still defining the distinction to make it clear what's going on behind the scenes.

# *AST* typically refers to *Abstract Syntax Tree*

One existing typical meaning of **AST** in the CS world is the specific context I had in mind when I posed my question.2

So now we have not two but *three* **AST**s. In the section **Why *three* ASTs?!?** below I'll return to why I'm defining three distinct tree concepts that all share the same acronym.

# *A Sparse Tree*

By ***A Sparse Tree***3 I mean a node of a tree data structure that serves as a root, plus any "well formed"4 potentially sparse *subset* tree formed of branch and leaf nodes relative to that root.

My example will be *A Sparse Tree* formed from a parse tree.5

If source code is like this:

```
foo = bar # Assign bar to identifier foo

```

And the parse tree is like this:

```
TOP
  statement                   foo = bar # Assign bar to identifier foo
    assignment                foo = bar
      identifier              foo
      assignment operator     =
      identifier              bar
    end-of-line-comment       # Assign bar to identifier foo

```

then the following represents two of many possible sparse trees based on that single parse tree:

```
# A Sparse Tree:
    assignment                foo = bar
      identifier              foo
      identifier              bar

# Another Sparse Tree:
    end-of-line-comment       # Assign bar to identifier foo

```

# *Annotated Subset Tree*

By ***Annotated Subset Tree***6 I mean *A Sparse Tree* represented/stored by *annotating* a subset of the nodes of a tree.

By "annotating" I mean hanging an additional node of data off selected nodes.

# Why *three* ASTs?!?

One abstract use case for sparse trees is forming an Abstract Syntax Tree that consists of annotations of the Parse Tree generated by a parser.

When the distinction between *A Sparse Tree*, an *Annotated Subset Tree*, and an *Abstract Syntax Tree* is moot -- which is most of the time -- just use the acronym **AST** without worrying about the ambiguity, because, by my definitions, it doesn't matter.7

That's why the terms I've coined share the same acronym: **AST** -- so they can be understood as theoretically distinct things but, for some parser implementations, the same thing in practice.

# Footnotes

1 My question was originally an attempt to find out if there was already an accepted term for what I described, generically in regard to trees, without regard for Abstract Syntax Trees. Then it became documentation of that attempt and the CS exchange community's response:

> I'm not sure there is a standard term. Feel free to make up your own.
>
> Just be sure to explain at least once in some detail what the term means.

2 I deliberately didn't state this context for my question because my original goal was to find out if there was a generic CS term about such trees.

3 A google for "sparse tree" suggests a few things, most notably a new christmas tree aesthetic and an aspect of a software feature (Emacs Org mode), as well as some genuinely CSish notions, but I didn't find any matching what I've described in this answer.

4 By "well formed" I mean that each node in the sparse/subset tree contains content from, and/or pointers to, the content of other nodes along branches proceeding in the direction of the tree's leaves from the sparse/subset tree's root node.

5 The word "sparse" is onomatopoeically reminiscent of "parse". This is a "happy mnemonic accident" given that the context for me naming these things is a sparse tree formed from a parse tree. It also reminds me of "A partridge in a pear tree" and I have fantasized that I will one day come up with and publish a worthy pun along those lines.

6 A google for "annotated subset tree" suggests a variety of CSish notions, but I didn't find any matching what I've described in this answer.

7 Of course, the usual use of the term "AST" in a CS context is an Abstract Syntax Tree. The whole point of this SO was to pick abstract terms describing a concrete approach that may be taken by parsers storing an AST. The fact that the terms all initialize to AST, with Abstract Syntax Tree being the dominant meaning of that acronym, is, of course, deliberate, and, imo, delightful.

8 A reddit.com/r/ProgrammingLanguages discussion
> 1 votes

---
Tags: terminology, trees
---


# Question
Title: What is the Time complexity of this sorting algo?
So i was trying to write an efficient sorting algorithm and i came up with this method,

> Sorting an array in ascending order by flipping (exchanging) 2 adjacent integers not in the correct order until there is no such pair.
>
> The leftmost swappable pair must be swapped first, i.e. the first pair encountered while going from left to right, which is in the opposite (descending order) should be swapped. Then the whole process should be repeated.

and the code i wrote for this is given below

```
#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;

    int a[n];

    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

        int j=0;

        //Sorting Logic

        while(j!=n)
        {
            int p=0;
            if(a[j]>a[j+1] && j!=(n-1))
            {
              int t=a[j];
              a[j]=a[j+1];
              a[j+1]=t;
              p=1;
                  }
                  if(p==0)
            j++;
            else
            j=0;

        }

        //Printing the sorted array

        for(int k=0;k<n;k++)
        {
          cout<<a[k]<<" ";
        }

}

```

In the best case it will give $O(n)$, but I am unable to figure out the worst case. What will be its worst case complexity? Is it $O(n logn)$ or $O(n^2)$?

# Answer
O(N^2). In the worst case, each iteration before while loop terminates swap n-1 times. So n\*(n-1) gives n^2 time complexity.
> 1 votes

---
Tags: algorithms, sorting
---


title: Planar regular languages

text:
# Question
Title: Planar regular languages
In my class a student asked whether all finite automata could be drawn without crossing edges (it seems all my examples did). Of course the answer is negative, the obvious automaton for the language $\\{\\; x\in\\{a,b\\}^\* \mid \\#\_a(x)+2\\#\_b(x) \equiv 0 \mod 5 \\;\\}$ has the structure of $K\_5$, the complete graph on five nodes. Yuval has shown a similar structure for a related language.

My question is the following: how do we show that *every* finite state automaton for this language is non-planar? With Myhill-Nerode like characterizations it probably can be established that the structure of the language is present in the diagram, but how do we make this precise?

And if that can be done, is there a characterization of "planar regular languages"?

# Answer
It isn't true that every DFA for this language is non-planar:

Here is a language that is truly non-planar: $$ \left\\{ x \in \\{\sigma\_1,\ldots,\sigma\_6\\}^\* \middle| \sum\_{i=1}^6 i\\#\_{\sigma\_i}(x) \equiv 0 \pmod 7 \right\\}. $$ Take any planar FSA for this language. If we remove all unreachable states, we still get a planar graph. Each reachable state has six *distinct* outgoing edges, which contradicts the known fact that every planar graph has a vertex of degree at most five.
> 36 votes

# Answer
The concept has been researched before. (Once you know the answer, google for it ...)

First there is old work by Book and Chandra, with the following abstract.

> Summary. It is shown that for every finite-state automaton there exists an equivalent nondeterministic automaton with a planar state graph. However there exist finite-state automata with no equivalent deterministic automaton with a planar state graph.

The example and argumentation given is exactly the one by Yuval in his answer!

Moreover they also consider the binary alphabet.

> There is a 35-state inherently nonplanar deterministic automaton over a 2-letter alphabet.

This work is continued rather recently by Bonfante and Deloup. They consider topological embeddings. Informally the genus of a graph is the number of holes that have to be added to embed the graph a surface without crossing edges. Graphs with genus zero are planar. Then the genus of a language is the minimal genus of the automata for the language.

> Theorem 9 (Genus-Based Hierarchy). There are regular languages of arbitrarily large genus.

In the section "State-minimal automata versus genus-minimal automata" one finds the result, the proof of which is the first example given by Yuval (ten states to make the five state K5 language planar).

> Proposition 7. There are deterministic automata with a genus strictly lower than the genus of their corresponding minimal automaton.

G.Bonfante, F.Deloup: The genus of regular languages, Mathematical Structures in Computer Science, 2018. doi 10.1017/S0960129516000037. Also ArXiv 1301.4981 (2013)

R.V. Book, A. K. Chandra, Inherently Nonplanar Automata, Acta informatica 6 (1976) doi 10.1007/BF00263745
> 28 votes

---
Tags: regular-languages, finite-automata, planar-graphs
---


# Question
Title: Language containing all unambiguous grammars
Suppose $L$ is the language of the *unambiguous grammars*. That is, a sentence $w\in{}L$ if it is a string that describes an unambiguous context-free grammar.

Considering that deciding whether a context-free grammar is ambiguous is non-decidable, would it be correct to say that $L$ exists but is not recursively enumerable?

# Answer
> 2 votes
The language $L$ clearly exists — you just defined it!

It’s not hard to check that your language is *co-r.e.*, that is, you can enumerate *ambiguous* grammars. Since it’s not recursive, it cannot be r.e.

---
Tags: formal-languages, formal-grammars, undecidability
---


# Question
Title: What are some decidable problems which cannot be solved in real life(due to time and memory constraints)?
The first line of Sipser book for the Chapter- 'Time complexity', says that:

Even when a problem is decidable and thus computationally solvable in principle, it may not be solvable in practice if the solution requires an inordinate amount of time or memory.

My question is, yes we do have limited space and time, so the above statement makes the whole P and PSPACE concept as vague, right? If it so, what are these problems? Are such huge inputs acceptable in practice?

# Answer
> 2 votes
Given an integer k, are there integers (positive or negative) x, y, z with an absolute value ≤ $10^{1000}$ such that $x^3 + y^3 + z^3 = k$?

It is believed that without the limit on the absolute values the answer is "Yes" unless $k \equiv 4 \mod 9$ or $k \equiv 5 \mod 9$. On the other hand, solutions are so rare that most likely solutions for some values k cannot be found in the lifetime of the universe.

And both the inputs, and the space needed for a computation, are tiny. The limitation on the size of x, y, z makes it decidable.

# Answer
> 1 votes
If you consider space and time limitation, it'll be safe to assume that **almost every Decidable problem** (as per the exact definition) can have version that **can be computationally not solvable.**

> That said, Turing machines are not a practical model for computing. Even in the theoretical computer science community, the more realistic RAM machines are used in the areas of algorithms and data structures. The concept of P - PSPACE are all dependent on Turing Machine, the method to classify a decidable/undecidable problem and hence must not be correlated with the practicality.

However, for sake of example:

* Solving cryptographic problems can be considered as one of the example.

Relevant Stuff:

---
Tags: time-complexity, undecidability, space-complexity
---


# Question
Title: What time complexity is more significant?
A certain algorithm executes $n$ operations of three types: insert, delete, and find. We know that $n/10$ of the operations are inserts, and the rest are deletes and finds.

You are given two implementations of the algorithm. The first one implements insert in worst case $\Theta(n)$, and the amortized cost of every operation (including insert) is $\Theta(1)$. The second implementation implements insert in worst case $\Theta(\log n)$, and the amortized cost of every operation (including insert) is $\Theta(\log n)$.

Which implementation would you recommend, and why?

# Answer
> 0 votes
You are asking for a practical answer, so you need a practical problem.

State your practical problem. Then examine what would be the effect of using one implementation vs. the other. Based on this examination, you can choose which implementation is more acceptable to you.

---
Tags: runtime-analysis, amortized-analysis
---


# Question
Title: How can I embed a Knowledge Graph in a vector space?
I am interested in embedding a Knowledge Graph in a vector space jointly with logical rules.

Through Google, the best work I have found about that is Tim Rocktäschel's paper Injecting Logical Background Knowledge into Embeddings for Relation Extraction.

The problem is that there is no throughly explanation about the matrix factorization in the paper or in Tim Rocktäschel's thesis or lectures.

My question is: What is the meaning of the rows of the matrix P x k and the columnns of k x R?

# Answer
I would encourage you to start with this survey paper by Nickel et al.: https://arxiv.org/abs/1503.00759

Recent notable models:

* **ComplEx-N3**: Lacroix et al. Canonical Tensor Decomposition for Knowledge Base Completion. 2018.
* **HypER**: Balazevic et al. Hypernetwork Knowledge Graph Embeddings. 2018.
* **TuckER**: Balazevic et al. TuckER: Tensor Factorization for Knowledge Graph Completion. 2019.
* **M3GM**: Pinter and Eisenstein. Predicting Semantic Relations using Global Graph Properties. 2018.

Regarding your particular question, the Pxk matrix contains k-dimensional row vectors, one for every entity-pair in the knowledge base (P many) and the kxR matrix contains k-dimensional column vectors, one for every binary relation in the knowledge base. Note though that the paper you referring to here is already an extension over traditional knowledge graph embedding methods in that it assumes additional first-order logic background knowledge.
> 2 votes

---
Tags: knowledge-representation
---


# Question
Title: Is following grammar has language which is inherently ambiguous?
Grammar is as follow:

$S \rightarrow aaAb | aab | A$

$A \rightarrow aaAb | aAb | \epsilon$

I think that this grammar has equivalent unambiguous grammar as follow.

Let’s first rewrite the grammar as below such that this grammar has same language as one in question:

$S \rightarrow aaSb | aSb | \epsilon$

Because this grammar generates $L = \\{a^nb^m: m \le n \le 2m\\}$

This grammer is just using two production in some order to derive string and then use null production to complete derivation.

So, idea is that we can some how order use of production such that any use of $S \rightarrow aaSb$ production does not come before use of any production of form $S \rightarrow aSb$. And following this idea it’s very easy to generate this grammar.

$S \rightarrow aSb | A$

$A \rightarrow aaAb | \epsilon$

.

Another arguments goes as follow:

Because $2k\_1 + k\_2 = n$ and $k\_1 + k\_2 = m$ for some $nonnegetive \space integer \space k\_1, k\_2$. (here $k\_1$ and $k\_2$ corresponds to number of use of production of form $S \rightarrow aSb$ and $S \rightarrow aaSb$ respectively.)

After solving the above equations we find that $k\_1 = m-n$ hence value of $k\_1$ will be unique for any perticular string. Which means that we must have to use some fix number of times the production of form $S \rightarrow aSb$. Which consequenly means that in our last rewritten grammer there is a fix point for a perticular string where you have to perform $S \rightarrow A$.

Please help me with this. I want to know whether this language is inherenly ambigous or not?

# Answer
> 1 votes
Your grammar $$\begin{eqnarray}S &\to& aSb &|& A \\ A &\to& aaAb &|& \epsilon\end{eqnarray}$$ is indeed unambiguous. The production $S \to A$ must occur precisely once in any derivation, and the productions which precede it cannot be replaced with any productions which succeed it or vice versa.

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