# Question
Title: thread scheduling in multi core architecture
In multi core architecture, let us say we have M cores and N threads (N \> M) and a process once assigned to a core can't migrate to another core's ready queue. We have to design scheduling policy to balance load. I read about this area and found this -
1) Block multithreading, Interleaved multithreading and Simultaneous multithreading (https://en.wikipedia.org/wiki/Multithreading\_(computer\_architecture))
2) Round Robin, FIFO, preemptive scheduling (https://en.wikipedia.org/wiki/Scheduling\_(computing))
3) Threads inherit priority number from processes and go to relevant core
My question asks me to compute thread load before scheduling and then assign that thread to core which is less loaded. Is there any research work done in this area ? If not, is there any research work done which computes a thread's computational load at compile time ?

# Answer
> 1 votes
The *load balancing* or *multiprocessor scheduling* problem is one of the earliest NP-hard problems for which an approximation algorithm has been developed. The classic paper is:

> R.L. Graham: "Bounds for certain multiprocessing anomalies," *Bell System Technical Journal*, 45(9):1563–158, 1966.

In the load balancing problem you are given $M$ identical cores, and $N$ threads. All the threads are assumed to be available at the beginning, and all the thread run times are given before hand. Graham proved that *list scheduling*, taking the threads one-by-one and assigning each one to the machine that currently has the least load is a 2-approximation. He further proved that *Longest processing time* (or LPT) scheduling, where you sort the threads in decreasing order of running length before doing list scheduling is a 4/3-approximation algorithm. See, for example: https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/11ApproximationAlgorithms-2x2.pdf

Graham's original result has been extended over the years to cases where there are dependences between jobs (i.e., job $j$ needs to finish before job $k$ starts), and to where each job $i$ is not permitted to be scheduled before a given time $a\_i$ (known as the *arrival time*), and to where the machines have different properties, and the jobs have requirements about what machine properties are required.

In the case where the job lengths and/or arrival times are not known before hand the problem becomes much harder. This becomes an online algorithm. The main research I am aware of in this area is for the case where the jobs do have dependences between them, but the dependences are restricted to *fork-join* patterns. The work in this area started (afaik) with the paper

> Robert D. Blumofe; Charles E. Leiserson: Scheduling multithreaded computations by work stealing. *J. ACM* 46(5):720-748, 1999.

(Note that this is called "work stealing", but you should really view the work being stolen as a new, dependent, job, so it actually fits into the non-migratory requirement you specified.)

As to your other question: there has been some work in using type inference to infer program running times, but I don't know that anything practical ever came out of it. The paper I'm aware of is:

> Brian Reistad; David K. Gifford: Static Dependent Costs for Estimating Program Execution Time, *ACM Conf on Lisp and Functional Programming*, 1994.

---
Tags: computer-architecture, operating-systems, scheduling, threads
---


# Question
Title: How powerful are CFGs that allow an infinite number of rules?
I was wondering recently what would happen if we'd allow context-free grammars to have an infinite number of rules. Clearly, if we'd allow arbitrary such infinite sets of rules, every language $L$ over some alphabet $\Sigma$ could be described by a CFG $G = (\\{S\\},\Sigma,R,S)$ with $R = \\{S \rightarrow w \mid w \in L \\}$. But what if we restrict $R$ to such sets of rules that can be created by context free grammars?

For that purpose, given a set of nonterminals $N$ and terminals $\Sigma$, let us view rules not as elements of $N \times (N\cup \Sigma )^\*$, but as strings over the alphabet $R\_{(N,\Sigma)} = N \cup \Sigma \cup \\{\rightarrow\\}$. Now my question is, if we define an *infinite rule CFG* to be a tuple $G = (N, \Sigma, R, S)$ where

* $N$ is a finite set of nonterminals
* $\Sigma$ is a finite alphabet
* $R$ is a set of rules of the form $A \rightarrow w$ with $A \in N$, $w \in (N \cup \Sigma)^\*$ such that there is some CFG $G'$ over $R\_{(N,\Sigma)}$ with $R = L(G')$
* $S \in N$ is the initial nonterminal

and we define $L(G)$ for such infinite rule CFGs just like it is done for CFGs, what is the relation between the class of languages generated by infinite rule CFGs (let's call that class $irCF$), the class of context-free languages $CF$ and the class $RE$?

Obviously, we have $CF \subseteq irCF \subseteq RE$, but is $irCF$ equivalent to one of these classes (or some other class)?

# Answer
Suppose we take the metagrammar $G'$ and factor it by two-symbol prefixes. In other words, for each $A \in N$ construct $G'\_A$, the left-derivative of $G'$ over the string $A \to$. That will produce a (finite) set of (finite) metagrammars, each one producing all the (possibly infinite) productions for some $A \in N$.

Now, construct the grammar $G''$, whose rules are the union of all the rules in the $G'\_A$ grammars (with non-terminals renamed to avoid collisions), along with $A \to S\_{G'\_A}$ for each $G'\_A$, where $S\_{G'\_A}$ is the start non-terminal for $G'\_A$. The non-terminals for $G''$ include $N$ and all the non-terminals for each $G'\_A$; the start non-terminal is the start non-terminal of $G$, and the terminals for $G''$ are precisely the terminals for $G$. I assert (without proof) that $G''$ is a finite grammar for the same language, since the derivation process isn't affected by the origin of the rules; it is just a string substitution over an alphabet.

If the above proof outline is valid, $CF$ and $irCF$ are the same.

As I alluded in a comment, there are more interesting examples of two-level grammars, including Van Wijngaarden grammars and the various attempts which have been made to create more manageable formalisms without losing all of the additional power.
> 7 votes

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


# Question
Title: Why do so many 8-Puzzle solving algorithms use DFS instead of BFS?
I see so many 8 Puzzle Solvers use a stack instead of a queue. Why is that? If you are looking for the solution with the fewest number of moves, wouldn't the solution be at a shallower point in the tree, meaning that BFS would find it much quicker? Is there some subtlety to the problem that I'm forgetting that makes DFS a better approach?

I've been comparing performance times myself and it seems like BFS is consistently and significantly faster.

# Answer
If the goal is to find *the shortest solution* to the 8-puzzle, DFS is indeed a very poor method. It's not a matter of faster or slower; DFS is not correct (it finds *a* solution, but it's not guaranteed to be the shortest solution). You could use BFS and that will work fine. Even better is to use A\* or some related algorithm; it will find the shortest solution even faster than BFS.

If the goal is to find *any solution* to the 8-puzzle, without regard to how many moves the solution takes, DFS is a fine method. Actually, you could use either DFS or BFS for that. The 8-puzzle has only 181440 reachable states, so the data structures won't grow too large.
> 1 votes

---
Tags: algorithms, graphs, search-algorithms, trees, search-problem
---


# Question
Title: How to reduce C′A′B + CAB′ to C′B + CB′?
I faced this Boolean expression:

$C'(A'B+A)+C(A'+AB')$

It was solved as follows:

$C'(A'B+A)+C(A'+AB')$
$=C'(A+B)+C(A'+B') $ ...by applying absorption laws $(I)$ $=C'A+C'B+CA'+CB'$
$=(C\oplus A)+(C\oplus B)$

However somehow it did not clicked to me to apply absorption laws. So I did following:

$C'(A'B+A)+C(A'+AB')$
$=C'A'B+C'A+CA'+CAB'$ $...(II)$

Here, I can have $C'A+CA'=C\oplus A$, but I have following doubt:

What Boolean law / identity I can use to reduce $C'A'B+CAB'$ to $C'B+CB'$ (which then can be reduced to $C\oplus B$) ? Is it even possible? or I have to somehow remember to apply absorption law as shown above and their is not other way to arrive at $(C\oplus A)+(C\oplus B)$ by expanding as in step $(II)$?

# Answer
> What Boolean law / identity I can use to reduce $C'A'B+CAB'$ to $C'B+CB'$?

None. You can't reduce $C'A'B+CAB'$ to $C'B+CB'$. Those two Boolean expressions are not equivalent. For example, when $A=\text{True}$, $B=\text{True}$, and $C=\text{False}$, $C'A'B+CAB'$ becomes $\text{False}$, but $C'B+CB'$ becomes $\text{True}$.
> 1 votes

---
Tags: logic, boolean-algebra, propositional-logic
---


title: Visual Programming languages

text:
# Question
Title: Visual Programming languages
Most of us learned programming using "textual" programming languages like Basic, C/C++, and Java. I believe it is more natural and efficient for humans to think visually. Visual programming allows developers to write programs by manipulating graphical elements. I guess using visual programming should improve the quality of code and reduce programming bugs. I'm aware of a few visual languages such as App Inventor, Scratch, and LabView.

Why are there no mainstream, general-purpose visual languages for developers? What are the advantages and disadvantages of visual programming?

# Answer
> 37 votes
In general, there is a trade-off in programming language design between ease of use and expressiveness (power). Writing a simple "Hello, world" program in a beginner language, such as Scratch or App Inventor, is generally easier than writing it in a general-purpose programming language such as Java or C++, where you might have a choice of several streams to output to, different character sets, the opportunity to change the syntax, dynamic types, etc.

During the creation of App Inventor (which I was part of), our design philosophy was to make programming simple for the beginner. A trivial example was basing our array indices at 1, rather than 0, even though that makes calculations likely to be performed by advanced programmers slightly more complex.

The main way, however, that visual programming languages tend to be designed for beginners is by eliminating the possibility of syntax errors by making it impossible to create syntactically invalid programs. For example, the block languages don't let you make an rvalue the destination of an assignment statement. This philosophy tends to yield simpler grammars and languages.

When users start building more complex programs in a blocks language, they find that dragging and dropping blocks is slower than typing would be. Would you rather type "a\*x^2+b\*x+c" or create it with blocks?

Justice can't be given to this topic (at least by me) in a few paragraphs, but some of the main reasons are:

1. Block languages tend to be designed for beginners so are not as powerful by design.
2. There is no nice visual way of expressing some complex concepts, such as type systems, that you find in general-purpose programming languages.
3. Using blocks is unwieldy for complex programs.

# Answer
> 22 votes
> Why are there no mainstream, general-purpose visual languages for developers? What are the advantages and disadvantages of visual programming?

Visual languages tend to broken it three broad categories:

1. Tools non-programmers to perform basic automation tasks. Think Automator on the Mac.
2. Learning environments where it's not practical to have lots of typing, or where the structure of the program showing logical flow is important. Think Scratch, Alice, etc.
3. The problem being addressed is a data-flow problem, and the solution to the problem is well modeled by some sort of data flows between self-contained boxes that mimic the physical world. LabView and Ableton both come to mind.

The advantage to visual programming is that you get a high-level overview of system structure. This leads to the immediate problem that when you get detailed, your spaghetti code really looks like spaghetti. A common component of visual languages is some sort of code block or configuration component for the visual element. The problem is that the programmer needs to make sense of disconnected code blocks that may be interlinked in strange ways.

While there is nothing wrong with visual programming, it may be the case that it's simply not a good approach for most tasks.

# Answer
> 11 votes
There have been numerous visual programming languages, as the following two bibliographies will show: vlib.org and oregonstate.edu.

IMHO they have failed to gain traction, because whilst they are good for toy examples, they fail to manage the multiple levels of abstraction, representation and granularity that large projects require. You would need to look at a system like AutoDesk Revit (a building information management system used by architects and engineers) to see how complex managing visual information can become.

Rather than looking at general purpose programming, visual programming is most likely to succeed as a configuration tool in specialised domains.

# Answer
> 9 votes
Text *is* visual.

We use all kinds of visual cues in our code. Every use of whitespace (indents, new lines, blank lines, intraline spacing) is directed towards providing visual cues for the functionality of the code. We use all kinds of different syntax to provide visual information on what code is doing. Our editors color our code to make it stand out.

Mathematics is textual. There is all kinds of notation, but in the end it comes down to basically text. They have been doing for hundreds of years.

My point: the textual representation of code is making use of the visual abilities that humans have. We can probably make better use of it, but not by abandoning text.

# Answer
> 8 votes
\[For the PDF version of this reply, the figures or diagrams are interactive and dynamic.\]

## Net Elements and Annotations: A General-Purpose Visual Programming Language

I use graphics to organize JavaScript™ programs that use the Acrobat®/JavaScript API. Each graphic object represents a Petri Net element (place, transition, input or output) or represents more than one Petri Net element. Each graphic object is actually an annotation of the corresponding net element. However, if every graphic object maps to one and only one net element it may be used to generate the net element. And if a graphic object maps to more than one net element and the mapping is well-defined then it may also be used to generate the net elements. Standard Petri Net elements are represented by certain types of graphics: a circle is a place, a square or rectangle or line is a transition, an arrow from a circle to a square is an input and an arrow from a square to a circle is an output. Furthermore, a net element that is represented by a standard graphics has a set of de-facto standard annotations associated with it.

\[The types of annotations in a "Standard Petri Net" are found in the PDF version of this reply.\]

Carl Adam Petri described most of these ideas (including the types of annotations in a "Standard Petri Net" in his doctoral dissertation (Petri, 1966). He also applied the net elements and annotations to the description of several logic circuits, such as Figure 6.

## Benefits and Challenges

A visual programing language may help a computer programmer develop computer programs (Menzies, 2002).

I have at least three reasons why I find net elements and annotations useful (advantages?).

Firs reason. The process logic can be created one element at a time. This means that a net can be extended by adding elements to the existing net (Petri, 1966). For example, a model of a controller can be divided into internal and external components. The internal component regulates the system. The external component interfaces with the environment by accepting input from the environment. Figure 1 is a Petri Net model of the internal component. It is possible to add a Petri Net model of the external component to the Petri Net model of the internal component by adding the appropriate places and transition (Figure 2).

Figure 1 A Petri Net Model of an Internal Component of a Controller (Halloway, Krogh and Giua, 1997)

Figure 2 A Petri Net Model of an Internal and External Components of a Controller (Halloway, Krogh and Giua, 1997)

Second reason. The codes associated with each net element can come from more than one “programming language” (Petri, 1973). They can come from a computer language such as JavaScript, COBOL, ADA and an assembly language. They can come from a Mathematical language such as algebraic symbols. They can come from prose encoded in English, German, French, Greek, Tagalog, Chinese, etc. Thus it may be used as a basis for communication and collaboration throughout the software or system development life cycle; and among different users, developers and stakeholders (Petri, 1973).

Third reason. It is possible to focus on certain graphics objects in the net and to write out the code or logic annotations for the related graphics objects. Consider a Petri Net model of a card game in Figure 3. If the arrow for the input P7  T4 is a standard graphics for an input in a Place/Transition Net and if m\_7 is the mark for the place P7 then the logic annotation for updating the mark of the input place is m\_7=m\_7-1. If s\_9^- is the status of the input then the logic annotation for updating the status of the input is s\_9^-=((m\_7\<1) ?false:true).

Figure 3 A Petri Net model of a card game

I have at least three reason why I find the application of Petri Nets challenging (disadvantages?)

If there are too many graphics objects then it would be difficult to create or to read the net. The difficulty may be mitigated by taking a subset of the graphics and represent them using one, two or three graphics symbol (Noe, 1973; Petri, 1966). For example, if the Petri Net model of a card game in Figure 3 is considered to have too many graphic objects in the diagram, it is possible to combine some of the graphics and still maintain enough information to map the diagram into a computer program. Consider Figure 4, a Petri Net model of the same game found in Figure 3 with high-level graphics (Chionglo, 2016a).

Figure 4 A Petri Net Model of a Card Game using High-Level Graphics (Chionglo, 2016a)

In another example, the external components of the controller in Figure 2 can be combined to create a more concise graphic representation as shown in Figure 5.

Figure 5 A Petri Net Model of a Controller with High-Level Graphics for External Components

Finally, a mutually exclusive set of places or a mutually exclusive set of transitions may also be represented using a high-level graphics object (Chionglo, 2015).

Second reason. Even with standard graphics, it can be challenging to draw and position graphics especially if one expects the final diagram to be user- or reader-friendly. Some of the decisions for making a user- or reader-friendly diagram include: the proper layout of graphics objects, the appropriate dimensions of the canvas and shapes, the curvature of arrows, the type of arrow heads, the size and font of text, and the choice of colours for graphics and text.

Third reason. It is easy to create annotations of net elements in an orderly manner because every annotation is directly or indirectly related to a net element. However displaying every annotation along with the graphics of every net element may not be a good idea because there could be too much information presented in the diagram. For example, consider a diagram of a Petri Net model of a logic circuit which includes references to all property and logic annotations (Figure 6). \[The original model included a test condition for the status of for every output (figure 31 on page 78 of (Petri, 1966)); the test condition was omitted here because it is equivalent to the original model for the given initial marking. Thus every output has one logic annotation for computing the mark of the output place.\]

Figure 6 A Place/Transition Net with annotations – based on figure 31 page 78 of an English translation of Petri’s dissertation (1966)

One way to mitigate this challenge would be to identify the types of annotations used in the model, and to define graphics objects that include annotations of these types (Petri, 1966). Thus when a Petri Net diagram is composed of graphics objects from the definitions, the interpretation of these objects should include the “invisible” annotations. Figure 7 should be interpreted as a Standard Petri Net (see Annotations of a Standard Petri Net for the definitions); therefore, the logic annotation may be omitted from the diagram.

Figure 7 A Place/Transition Net – based on figure 31 page 78 of an English translation of Petri’s dissertation (1966)

Another way to mitigate this challenge would be to use form views of the annotations to complement or supplement the diagram(s) (Chionglo, 2016b; 2014). The views may be further divided into smaller views, and each view can be displayed and hidden.

## References

Chionglo, J. F. (2016a). A Reply to “How to design a state flow for a react/redux flashcard game?” at Stack Overflow. Available at https://www.academia.edu/34059934/A\_Reply\_to\_How\_to\_design\_a\_state\_flow\_for\_a\_react\_redux\_flashcard\_game\_at\_Stack\_Overflow.

Chionglo, J. F. (2016b). Two form views of a Petri Net. Available at http://www.aespen.ca/AEnswers/CAPDissF31P78-form.pdf.

Chionglo, J. F. (2015). Reducing the number of net element graphics in a Petri Net diagram using high-level graphics. Available at http://www.aespen.ca/AEnswers/WjTpY1429533268.

Chionglo, J. F. (2014). Net Elements and Annotations for Computer Programming: Computations and Interactions in PDF. Available at https://www.academia.edu/26906314/Net\_Elements\_and\_Annotations\_for\_Computer\_Programming\_Computations\_and\_Interactions\_in\_PDF.

Halloway, L. E.; Krogh, B. H. and Giua, A. (1997). A survey of Petri Net methods for controlled discrete event systems \[electronic version\]. Discrete Event Dynamic Systems: Theory and Applications, Vol. 7. Boston: Kluwer Academic Publishers, pp. 151 – 190.

Menzies, T. (2002). Evaluation issues for visual programming languages. In S. K. Chang (Ed). Handbook of Software Engineering & Knowledge Engineering, Vol. 2 Emerging Technologies. World Scientific Publishing co. Pte. Ltd., pp. 93 – 101.

Noe, J. D. and Nutt, G. J. (1973). “Macro E-Nets for Representation of Parallel Systems”, IEEE Transactions on Computers, vol. C-22, No. 8, Aug. 1973, pp. 718 – 727.

Petri, C. A. (1973). Concepts of Net Theory. In Mathematical Foundations of Computer Science: Proc. of Symposium and Summer School, High Tatras, Sep. 3 – 8, 1973, pages 137 – 146. Math. Inst. of the Slovak Acad. of Sciences, 1973.

Petri, C. A. (1966). Communication with Automota \[trans. C.F. Greene, Jr.\]. Supplement I to Technical Report RADC-TR-65-377 (Volume I). Griffiss Air Force Base, NY: Rome Air Development Center, Research and Technology Division, Air Force Systems Command, Griffiss Air Force Base. Retrieved Aug. 31, 2011 from http://www.informatik.uni-hamburg.de/TGI/mitarbeiter/profs/petri/doc/Petri-diss-engl.pdf.

# Answer
> 2 votes
Johne Percival Hackworth:

> While there is nothing wrong with visual programming, it may be the case that it's simply not a good approach for most tasks.

Perhaps, the visual programming languages to date have just been too immature? The notion that advanced visualizations cannot be applied to software artifacts and that they are left completely up to the 'imagination' of each developer to roll their own might be a false assumption. Raising the level of abstraction in a uniform and automated way seems obvious, so as long as the ability to perform low-level abstractions and high execution performance is not sacrificed. This could ultimately lead to domain expert 'programming,' not much different than the way that spreadsheets automated the task of COBOL programmers to manipulate numbers. The primary difference here is replacing numbers with the manipulation of 'general systems.'

# Answer
> 2 votes
You can look at Programming Without Coding Technology (PWCT)

PWCT is a general purpose visual programming language that enables the development of systems and applications by generating interactive steps instead of writing code.

Here is a good place to start and is open source.

# Answer
> 2 votes
a tricky question. visual or flow-based programming has indeed become more used but it is not widely used compared with all programming languages. significant factors are maintenance and standardization. computer code can be printed on pages. it is not always so clear how to print a visual program.

in contrast to the current top answer I would argue there is definitely no inherent theoretical limitation on visual programming power vs textual languages. in fact visual programming may be seen as easier to maintain someday based on faster human conceptualization of the many layers of abstraction. so there seems to be an unmistakable element of social/cultural inertia/conservatism in its uptake.

the visual editors are probably much more complex in their code, and this is formidable considering that even just text based IDEs can be very complex eg Eclipse, note there are visual-programming oriented plugins into some IDEs such as eciplse eg for GUI building. visual programming for GUI building is fairly widespread now.

it appears to me that visual programming use is increasing in select areas and that long from now it may become more common.

lets not forget that visual programming is inherent to EE chip design for decades where it is not an abstraction and (sub)systems are laid out in 2d designs exactly as intended.

the Lego mindstorms kit, now widespread & over a decade old, has always had development software based on visual programming, now streamlined significantly over many versions.

here is an interesting recent article analyzing the history and prospects and suggesting it may become more common for web-based programming. dynamically laying out controls/widgets on a page is a variant of visual-based programming.

another key/emerging area where it is in widespread use in many tools is BPM, business process modelling.

# Answer
> 1 votes
I guess the reason why these solutions are not so popular, because in most cases they can be un-manageable and become a mess.

Almost all the visual programming tools available out there today are part of larger applications and used for a specific purpose (ex: Blueprint in UE4).

Anyway a new one I came across recently for general programming is Korduene which is really not quite general purpose, as it is more for creating windows applications.

# Answer
> 0 votes
I think @Raphael and others are wrong when they say a program is text. It isn't. It's many things. It's telling the computer what to do, or how to do it. (imperactive, declarative programming) The association of programming with text editing is historic and counterintuitive dogma. Which was created by the limited textual inputs/outputs of early computers. People are not text parsers!

While I think that people are right that a fully visual language (where you do anything visually, by connecting elements via mouse and such) is impractical a for a general purpose language, I think all current languages could be and should be moved to an intermediate level. Where language elements have a visual representation, which is saved in a binary language file. The programmer wouldn't type text like crazy, or live under the spell of lines and indentation.

But inserts elements via the most productive combination of hotkeys/commands/UI elements. And only types strings and other data and identifiers. This would make syntax errors impossible and make languages with safety and correctness in mind (eg:ADA) way more productive. And would also make others safer and less buggy, by making whole classes of common errors impossible. (Such as the ones ADA prevents by being cumbersome)

To some degree things were heading this way. By automatic indentation and syntax coloring. Sadly no-one realized (or cared enough) that it's the core concept of the "human text parser" is what's wrong. The emacs vs vim arguments are funny because both are wrong. They are "solutions" to an artificially created problem.

---
Tags: programming-languages
---


# Question
Title: Forward must problem explanation in compiler design
While studying, I came across the following statements:

A **join point** is a program point where two branches meet.

**Available expressions** is a forward, must problem.

**Forward** = Data Flow from in to out.

**Must** = At joint point, property must hold on all paths that are joined.

I get what joint point, available expression and forward is. But I am getting what exactly is meant by **MUST**.

Someone please explain what **MUST** is with **example**.

Edit: Could you please relate your statement with the following example.

# Answer
> 2 votes
I typically think of *must* as meaning *logical and*.

In the case of available expressions, when you reach a join point, the expression in question is *available* at the join point if and only if the expression is available on *all* of the input edges to the join point. That is: if the expression is available on the first input edge, *and* it is available on the second input edge, *and* it is available on the third input edge, etc.

There are other properties, such as "could be a null pointer" which are *may* properties instead of *must* properties. *May* I think of as meaning *logical or*.

---
Tags: compilers
---


# Question
Title: Does this program satisfy the postcondition?
Does the following program $P$:

```
a = 2
b = a + 3
c = a * b

```

Satisfy the following formula? $$\\{ \top \\} \\; P \\; \\{ a \< (b - 2) + c \\}$$

I want to use integers in $P$. The postcondition is satisfied, right?

# Answer
> 0 votes
Using only two properties of the weakest precondition (wp), we can prove this correct as follows.

```
   wp(a ≔ 2 ; b ≔ a + 3 ; c ≔ a * b ,  a < b - 2 + c )
≡⟨ wp on sequence ⟩
   wp(a ≔ 2 , wp (b ≔ a + 3 , wp (c ≔ a * b , a < b - 2 + c)))
≡⟨ wp on assignment ⟩
   wp(a ≔ 2 , wp (b ≔ a + 3 , a < b - 2 + a * b))
≡⟨ wp on assignment ⟩
   wp(a ≔ 2 , a + 3 < a + 3 - 2 + a * (a + 3))
≡⟨ wp on assignment ⟩
   2 + 3 < 2 + 3 - 2 + 2 * (2 + 3)
≡⟨ arithemtic ⟩
   5 < 13
≡⟨ arithemtic ⟩
   true

```

Hence,

```
{ true }   a ≔ 2 ; b ≔ a + 3 ; c ≔ a * b   { a < b - 2 + c }

```

---
Tags: logic, hoare-logic
---


# Question
Title: Is there an algorithm or shortcut for continually updating and summing sub-sections of arrays?
Let's say I have an NxN array if integers. I want to continually update it, but also continually query for the sum of an arbitrary sub-section. So example would be as follows:

We start with a 3x3 array of all 0s.

Operations:

> update 1,1 to 3
>
> update 1,2 to 1
>
> update 0,0 to 2
>
> update 2,2 to 6
>
> print sub-section starting at 1,1 going to 2,2 (should print 10)
>
> more updates...
>
> more queries...

The array looks like this at the time of first query:

```
2 0 0
0 3 0
0 1 6

```

I want to do this for much larger arrays, and much more queries in a reasonable amount of time. I believe less than O(N^2) per query is possible. Any ideas?

EDIT: I'm asking this because Hackerrank has several of these types of questions and I was banging my head against a wall trying to come up with a strategy.

# Answer
> 1 votes
The data structures you're looking for are quad trees (for linear time queries, logarithmic time updates, quadratic space) or the more complicated 2d interval trees (for logarithmic time queries, logarithmic time updates, $O(N^2 \log N)$ space).

I suspect you are trying to solve competitive programming problem, if so please state it in your question.

---
Tags: algorithms, data-structures, arrays
---


# Question
Title: BFS implementation: queue vs storing previous and next frontier
The most trivial implementation of BFS would simply store the last frontier (open list), build the new frontier, and then replace the last frontier with the new (like in the example python code below). But almost universally, the first algorithm shown for BFS in textbooks is the queue-based implementation.

What's the disadvantage of the simple frontier-storing approach? I can see it might use slightly more memory (effectively storing the new frontier while the old is still in memory), but usually textbooks only care about big-O complexity. Is there any other problem with it?

```
# example of a graph
g = {1: [2, 3], 2: [1, 3], 3: [1, 2, 4], 4: []}

def bfs(g, root):
    yield root
    boundary = [root]
    visited = {root}
    while boundary:
        new_boundary = []
        for v in boundary:
            for w in g[v]:
                if w not in visited:
                    yield w
                    visited.add(w)
                    new_boundary.append(w)
        boundary = new_boundary

```

# Answer
> 3 votes
Your analysis is correct. There is no major disadvantage of the two-list approach you outline.

One nice thing about the queue-based formulation of BFS is that it makes it easier to see the relationship to DFS and Dijkstra's algorithm. Start with the queue-based formulation, and replace the queue with a stack, and you get DFS. Replace the queue with a priority queue, and you get Dijkstra's algorithm. This similarity is aesthetically pleasing and might help understand the algorithm better.

A slight disadvantage of your two-list based scheme is that it has somewhat higher memory consumption: only a constant factor higher, so maybe not a big deal, but it is somewhat higher. This is because when you're traversing the current frontier, you keep around the items in the list that you've already traversed even after you've finished traversing them. In contrast, the queue-based method doesn't do that.

Nonetheless, in the big picture, you are absolutely right; both methods are pretty similar and there's not an overwhelming reason to prefer one over the other.

---
Tags: algorithms, graphs
---


# Question
Title: Sorting a set of $n$ elements containing only $\log n$ unique elements
We have a set of $n$ elements which contains at most $\log n$ different numbers. I want to sort this set faster than $O(n \log n)$. Is it possible?

I tried using a hash table to find the set of $\log n$ unique elements, then sort them in $O(\log n \log \log n)$, after that creating a new array of $n$ element with this array of $\log n$ elements in $O(n)$, but it is not the right answer since using hash table may fail, and the worst case still needs more than $O(n \log n)$.

Is there any algorithm faster than $O(n \log n)$?

# Answer
> 6 votes
Your solution is almost complete. Try replacing the hash table with a comparable data structure, such as a balanced binary search tree. Since the tree will only contain at most $\log n$ elements, all the operations on the tree will take time $O(\log\log n)$, and the resulting algorithm will take time $O(n\log\log n)$.

Any comparison-based algorithm for your problem takes time $\Omega(n\log\log n)$. To see that, notice that there are roughly $(\log n)^n$ different possible relative orderings for your set (the actual number is a bit smaller, but not by much). Any comparison-based decision tree must therefore have depth $\Omega(\log \[(\log n)^n\]) = \Omega(n\log\log n)$.

If you allow more general algorithms, then you can improve the complexity to randomized $O(n)$ using a hash table, along the lines that you mentioned. Since you can afford a hash table of size $O(n)$ although the occupancy is only $\log n$, the probability that your algorithm exceeds its expected running time significantly will be very, very small.

It is also possible that under a suitable computation model, you can sort you list in deterministic $O(n)$ time. Some people consider this kind of algorithm cheating, though.

# Answer
> 1 votes
You create a sorted array with the unique values. That array has size O (log n). For every array element of your original element, you use binary search in O (log log n) time to find where it belongs in the small area and add it to a linked list of elements with that value; there may be log n insertions taking (log n)^2 time. You can then create the sorted array in O (n) steps. The biggest factor is n x log log n for the binary search.

Instead of an array with binary search you could use a hash table, which is faster on average but with worse worst case. You can avoid the worst case by using a generous size for the hash table, and handle any collisions immediately in an array. This would *often* work in O (n) and still have O (n log log n) worst case.

---
Tags: algorithms, sorting
---


# Question
Title: Is P = { <M,w> | M rejects w} the complement to Atm = { <M,w> | M accepts w}?
As Atm is recognizable, its complement cannot be recognizable, due to being so Atm would be decidable.

I am trying to clarify if the problem P is the complement to Atm.

If so, how could i approach the problem without looking at Atm to prove undecidability?

My first thought was:

> H is a machine which solves P:
>
> H halts and accepts when M rejects w.
>
> H halts and rejects when M accepts w.

And from then on contradict the construct like in the proof of Atm.

# Answer
> 2 votes
The answer to the question in the title (is $P$ the complement of $A\_{tm}$) depends on several issues. To see why, let's start by computing the complement of $A\_{tm}$: $$ \overline{A\_{tm}} = \\{ \langle M,w \rangle : M \text{ does not accept } w \\} \cup \\{ x : x \text{ is not of the form } \langle M,w \rangle \\}. $$ If you choose an encoding for $\langle M,w \rangle$ for which there exist strings which are not of the form $\langle M,w \rangle$, then $P$ is definitely not the complement of $A\_{tm}$. However, there do exist encodings in which you can decode *any* string into a Turing machine and an input string. In that case, $$ \overline{A\_{tm}} = \\{ \langle M,w \rangle : M \text{ does not accept } w \\}. $$ You are asking whether this is the same as $$ P = \\{ \langle M,w \rangle : M \text{ rejects } w \\}. $$ The question is how you define acceptance and rejection. Here is one possible definition:

> A Turing machine *accepts* an input if it halts on an accepting state. It *rejects* an input if it halts on a non-accepting state.

Under this definition, there is also a third option: the Turing machine never halts. So $P$ and $A\_{tm}$ are not complements of each other. Here is another definition:

> A Turing machine *accepts* an input if it halts on the input. Otherwise it rejects it.

Under this definition, $P$ and $A\_{tm}$ are complements of each other. If you define the language of a Turing machine as the set of strings it accepts, then both definitions are equivalent (you can modify a Turing machine to fit either), but the exact choice does matter for your particular question.

# Answer
> 1 votes
It is a common misunderstanding among students that if a Turing machine does not accept its input, then it will reject it. But a Turing machine may loop forever on some inputs. On any given input $w$, a Turing machine may

* accept $w$
* reject $w$
* or loop forever

So the complement of $A\_{\mathsf{TM}}$ is

$$\overline{A\_{\mathsf{TM}}} = \\{ \langle M,w \rangle \mid M \text{ is a Turing machine that does not accept } w \\}$$

---
Tags: turing-machines
---


title: About the Identity function in Agda

text:
# Question
Title: About the Identity function in Agda
I've defined the identity function in `Agda` as follows:

```
idd : (∀ {ℓ} {A: Set ℓ}) → A → A
idd a = a

```

I want to ask you if the following reasonings are correct:

* The type of this function is `A -> A`.
* `idd` is a polymorphic function, where `(∀ {ℓ} {A: Set ℓ})` matches any type.
* Because is a polymorphic function, I can say `idd` is of dependent type.

# Answer
> 8 votes
Your code does not work. I would suggest that you forget about the universe levels for the time being (the $\ell$ thing) and focus on simpler things first. Here is working code:

```
idd : (A : Set) → A → A
idd A a = a

```

The type of `idd` is `(A : Set) → A → A`. It is a dependent product, i.e., it could be written as $\prod\_{A : \mathsf{Set}} A \to A$ in mathematical notation. If we have a type `B` then the type of `id B` is `B → B`.

You say:

> The type of this function is `A -> A`.

No. The type if `idd` is exactly what it says, namely `(A : Set) → A → A`.

> `idd` is a polymorphic function, where (∀ {ℓ} {A: Set ℓ}) matches any type.

Let us forget about . In this case the question is whether `idd` is a polymorphic function. The answer is "yes" because `A` matches any type.

> Because is a polymorphic function, I can say idd is of dependent type.

No. This is the wrong way to think. The function `idd` does *not* have a dependent type. It has the *fixed* type `(A : Set) → A → A`. However, this fixed type is a *dependent product*.

# Answer
> 1 votes
I'll use the following code for answer your questions:

```
idd : (A : Set) → A → A
idd A a = a

```

Is `idd` a polymorphic function? No. Agda (without universe polymorphism) is a monomorphic language. The `idd` function is only defined on small types, i.e. `Set`. The function is not defined on `Set1`, `Set2`, ...

Has `idd` a dependent type? Yes. I'll quote Bove and Dybjer \[2009, p. 64\]:

> Here we see a first use of dependent types: the type `A -> A` depends on the variable `A : Set` ranging over the small types.

Bove, A. and Dybjer, P. (2009). Dependent Types at Work. In: LerNet ALFA Summer School 2008. Ed. by Bove, A., Soares Barbosa, L., Pardo, A. and Sousa Pinto, J. Vol. 5520. Lecture Notes in Computer Science. Springer, pp. 57–99.

---
Tags: dependent-types
---


# Question
Title: Anyone knows an algorithm that finds minimum distance for all permutations?
Let $A$ and $B$ be two finite sets of the same size $n$. Let $P(A),P(B)$ be the set of all permutations of $A,B$ respectively. A distance function $d(a,b)$ is defined for any $a\in P(A),b\in P(B)$. We want to find $\min \\{d(a,b):a\in P(A), b\in P(B)\\}$ (note: $d$ is fixed).

For example, suppose we have two sets $\\{1,2\\}$ and $\\{3,4\\}$, and the distance $d$ is Euclidean distance, then all possible distance values are

> $d((1,2),(3,4)) = \sqrt8$
>
> $d((1,2),(4,3))=\sqrt {10}$
>
> $d((2,1),(3,4)) = \sqrt{10}$
>
> $d((2,1),(4,3)) = \sqrt{8}$

So the minimum value is $\sqrt 8$.

I think this is a very common problem so there should be some known algorithm out there. Anyone knows an efficient algorithm to solve this problem and help provide the name or reference? Thank you!

# Answer
> 7 votes
Surprisingly, if the distance is $L\_p$, or the $p$-norm induced metric, then you simply sort $A$ and $B$ respectively, and then compute their distance, and that distance will be guaranteed minimal over all permutations. That is time complexity of $O(n\log n)$ and I believe it is the most efficient one.

The key proof is done in https://math.stackexchange.com/questions/1984686/is-x-1-y-2px-2-y-1p-ge-x-1-y-1px-2-y-2p-for-any-0-le-x-1-le.

Sometimes, before setting out to find an "efficient" algorithm, it might be a good practice to first think of proving the "greedy" algorithm is not right; because if the greedy indeed works, all efforts to search for the "efficient" algorithm will be in vain.

# Answer
> 3 votes
If your weight function is just sum of pairwise distances between elements (or a monotone function of it) than this problem is reduced to the assignment problem. Most reasonable metrics (including $L\_p$ for all $p$, which, in case, include Euclidean metric) satisfy this constraint. If so, we are only interested which pairs of elements are matched.

Let $a\_{ij}$ be the cost of matching between $i$-th element of the first set and $j$-th element of the second set. Having the matrix $A$, you need select $n$ elements in it such that each column and each contain exactly one element and the sum of corresponding $a\_{ij}$.

This is a classical problem, called *assignment problem*, which is effectively solved in $O(n^3)$ with Hungarian algorithm.

As far as I know, there are faster solutions ($O(n^{2.5})$ maybe), but I'm not sure. You can search for the min-cost max-flow algorithms which solve more general task and probably are being researched wider.

---
Tags: algorithms, optimization
---


# Question
Title: CRF message passing as convolution operation
I was reading the paper \_Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials (Philipp Krähenbül and Vladen Koltun, in Proceedings of 25th Annual Conference on Neural Information Processing Systems (NIPS), 2011 pdf), and I didn't understand this equation (eq 5) in the paper:

I understand the first equation, but not the second one. If $k(f\_i,f\_j) = e^{-1\*(f\_i-f\_j)^{2}}$, then $k(f\_i,f\_j)$ would return a scalar value between 0 and 1 ; 0 if $f\_i$ and $f\_j$ are far apart in the feature space, 1 otherwise. So, $k(f\_i,f\_j)Q\_j$ adds a fraction of $Q\_j$ to $Q\_i$ . The first equation is clear. I don't understand how this leads to the 2nd equation. In the 2nd equation, the Gaussian kernel is now over $Q$ instead of being over $f\_i,f\_j$ and then multiplied by $f\_i$. Where is the $f\_j$? Can someone explain how the 2nd equation is derived from the first one?

$G \otimes Q$ would again return a value between 0 and 1, which is multiplied by $f\_i$ (which is an n-dimensional feature vector). So the result of $(G \otimes Q)(f\_i)$ would be an n-dimensional vector, and we subtract $Q\_i$ (a scalar) from that. Am I misunderstanding something here?

# Answer
I read the article. The meaning of the equation: $$\[G\otimes Q\](f\_i)$$ stand for $G$ convolution with $Q$ in the feature point $f\_i$ and not multiplied by $f\_i$.

The $f\_j$ is hidden inside the convolution operation.

The actual operation is done using cross bilateral filter. You can see more information on the Project site of the article. You can also find a source code in this site.
> 2 votes

---
Tags: machine-learning, computer-vision
---


# Question
Title: Is Functional Complete means Turing Complete?
I noticed that AND, OR, NOT those three logic gates are Functionally Complete, it means I can represent any trues table only by those three gates.

A Turing machine may halt or not in a particular input but a combinational(not sequential) logic circuit always gives an output in a particular input. You may not agree with my point on combinational circuit but a combinational circuit is just a deterministic system so I can evaluate step by step in a input until it gives an output, in other words, there is no loops in a combinational circuit, I think.

So, I want to know whether I can represent any computable function only by those three gates ?

Any way, thx!

# Answer
> 3 votes
A Turing machine defines a function over all of $\Sigma^\*$, it is a finite object which describes the operation on infinitely many inputs.

A logical circuit however, is defined over a specific number of variables, so it has a finite domain. Using boolean circuits over $n$ variables we can implement the set of all functions from $\left\\{0,1\right\\}^n$ to $\left\\{0,1\right\\}$, and no more (so no Turing completeness in the simple interpretation).

This is why, when dealing with logical circuits, the notion of non uniform computation is introduced. By non uniform, we mean that the mechanisem for processing some input $x$ might depend on $|x|$. In the context of circuits, this means that instead of talking about one circuit, were talking about a circuit family $\left\\{c\_n\right\\}\_{n\in\mathbb{N}}$, where $c\_n$ is a circuit with $n$ inputs.

We say that a circuit family $\mathcal{C}\_n$ decides some language $L$ if $\forall x\in\Sigma^\*: x\in L \iff c\_{|x|}(x)=1$. Note that non uniform computation extends the classical uniform computation, i.e. using circuit families of arbitrary size we can decide undecidable (relative to Turing machines) languages. Actually, we can decide all languages. If you want to reduce this back to the Turing model, then you must require the existence of a computable function $f$ which, given $n$, generates the circuit $c\_n$.

---
Tags: computation-models, boolean-algebra, turing-completeness
---


# Question
Title: Algorithm for solving incremental max flow problem
I am working on a project where I need to be able to compute the maximum flow between two nodes in a graph after one of the edge weights has been incremented or decremented by 1. The graph is directed and edge weights are all integers. I can find the maximum flow the first time, by Ford-Fulkerson's algorithm or some variant, but at each step thereafter it would be great if I could use a different (faster) algorithm to find the max flow. At each step, only one of the edge weights is changed, and it is only changed by a value of +1 or -1. What sort of algorithm could do this incremental update for me? It needs to be faster than recomputing the max flow from scratch. It could also be two separate algorithms (but similar I would hope): one for the incrementing case and one for the decrementing case. Thanks in advance for the help!

# Answer
You can do it in $\small \mathcal{O}(m + n)$ time where $\small m$ and $\small n$ are the # of edges and vertices respectively. Let the edge to be updated be $\small e = (u, v)$.

* If you increment the capacity of $\small e$ by $\small 1$, the maximum flow increments by at most $\small 1$. Hence, starting with the current max flow $\small f$, you only need to find an augmenting path in the residual graph one more time, which costs $\small \mathcal{O}(m + n)$ time. Recall that each augmentation increments the flow value by at least $\small 1$. Therefore, it is guaranteed after the augmentation (if any), the flow attained is maximum.
* If you decrement the capacity of $\small e$ by $\small 1$, the maximum flow decrements by at most $\small 1$. If the new capacity (after decreased by $\small 1$) $\small c(e) \geq f(e)$, where $\small f(e)$ is the current flow value of $\small e$, then nothing need to be conducted. Otherwise, we have to decrease the flow value of $\small e$. Let $\small s \rightarrow u$ be a simple path from $\small s$ to $\small u$, in which all edges have positive flow values and similarly define $\small v \rightarrow t$. We then decrease the flow values by $\small 1$ for all edges in the path $\small s \rightarrow u \rightarrow v \rightarrow t$. Finally, we again search for an augmenting path in the resultant residual graph.
> 7 votes

---
Tags: algorithms, graphs, network-flow, ford-fulkerson
---


# Question
Title: Are there adversarial inputs for randomized quicksort?
Someone recently claimed that there's an adversarial input for *randomized* quicksort; he referenced this paper. This defies my intuition because there are results that say that randomized quicksort runs in $O(n \log n)$ time with high probability. (See, for example, the book **Randomized Algorithms** by Motwani&Raghavan.) I am refering to the version of randomized quicksort that picks the pivot uniformly at random at each recursive call.

So my question is: are there indeed adversarial inputs for randomized quicksort? Please give an intuitive reason as to why such an input can exist.

**Update.** It seems to me that the adversary in the paper is granted unrealistic capabilities (generate array on the fly), which explains why it can make any quicksort perform poorly. Under reasonable assumptions I would say there is indeed no adversarial input for randomized quicksort.

# Answer
> 5 votes
The analysis of randomized quicksort is independent of the input. While there might be better inputs and worse inputs, the upper bound given by the analysis works for *every single input*.

You can go over the proof in slides of Xi Chen, for example, who proves that whatever the input, randomized quicksort runs in expected time $O(n\log n)$. (I don't know whether your high probability claim is true as well, though it sounds plausible.)

# Answer
> 8 votes
There are implementations of Quicksort (the partitioning algorithm, specifically) which deal badly with *duplicates*. No matter how much you randomize -- shuffling the input, random choice of the pivot, random choice of the pivot with sampling, ... -- if *all entries are the same* (or there are only constantly many distinct values), these bad implementations will result in worst-case behaviour, always.

You can find details e.g. here and in the literature.

*Note bene:* The reason why many TCSists would claim the opposite with a passion it that they forget that most classical analyses are performed under permutation models. That does not give the whole truth, though, particularly if you use sorting in practice. Duplicates *are* relevant, for instance if you sort lists of binary values.

# Answer
> 3 votes
The mentioned StackOverflow question actually gives the source for this claim.

The source doesn't make this very clear, but the reason for this perceived mismatch between theory and practice is that in theory your comparison function is a mathematical function given ahead of time, but in practice it is a C function that can have side-effects and depend on previous side-effects.

Note that although the adversarial comparison function is non-deterministic in the sense that there is no mathematical function chosen ahead of time it corresponds to, it is still in a sense well-behaved: for any given execution of the program, there exists an order of elements such that the comparison function is compatible with it.

# Answer
> 0 votes
The killer adversary referenced builds an input that can make any quicksort go quadratic time provided that the pivot selection process responds the SAME every time the SAME input is used. In reality, a randomized pivot selection would have progressed to a different seed in the random series, so the next time the sort is called it will not cause quadratic time. It will cause quadratic only while it's building the input.

In other words, as soon as the killer input is built, it becomes not a killer. (in the case of random pivot selection).

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


# Question
Title: If $R,F \cap R, F \cap \overline{R}$ are regular, is $F$ regular?
Let $R \in REG$. Is it true that if $F\cap R \in REG$ and $F \cap \overline{R} \in REG$ then $F \in REG$?

I took $R = \Sigma^{\ast}$ and because $F\cap R \in REG$, $F$ must be regular. Is this the right approach?

# Answer
> 2 votes
Here's a hint. First, show that for any two sets $A, B$, that $A = (A\cap B)\cup(A\cap\overline{B})$. Then use the fact that the union of two regular languages is regular.

---
Tags: formal-languages, regular-languages, closure-properties
---


title: Types and Types Systems concepts

text:
# Question
Title: Types and Types Systems concepts
**Given this definitions about Types and Type systems :**

Types are described by means of a language of type expressions:

* **Basic** or **primitive types**: Bool, Char, Int, ...
* Type **variables**: a, b, c, ...
* Type **constructors**: → (function), × (tuple), \[ \] (list), ...
* **Rules** to build type expressions:

τ ::= Bool | Char | Int | ··· | t | τ → τ | τ × τ | \[ τ \] | ···
* Types whose type expression contains no type variable are called monomorphic types or just monotypes.
* Types whose type expression contains variables are called polytypes or polymorphic types (parametric polymorphism)
* **A polymorphic type represents an infinite number of monotypes**

I'm trying to understand the last definition but i can't. A polymorphic type represents a infinite number of monoytpes, because in his type expression has a type variable ?

# Answer
Yes, exactly. Because you can instantiate the polymorphic type with an infinite amount of (mono)types.

For example, the type $a \to a$ (which is a polymrphic type) represents

* Bool $\to$ Bool
* Char $\to$ Char
* (Char $\to$ Int) $\to$ (Char $\to$ Int)
* etc...
> 4 votes

---
Tags: type-theory, types
---


# Question
Title: How to prove that the class of non-context-free languages isn't closed under intersection?
I am not sure how to approach this. L1 and L2 are using the same alphabet.

# Answer
Here's a hint. Let

$$ L\_1=\\{a^nb^nc^{2n}\mid n\ge 0\\}\text{ and } L\_2=\\{a^nb^nc^{2n+1}\mid n\ge 0\\} $$

* Show that $L\_1$ and $L\_2$ are not context-free.
* Say something about $L\_1\cap L\_2$
> 1 votes

---
Tags: computability, context-free
---


title: Does expert system use algorithms?

text:
# Question
Title: Does expert system use algorithms?
I want to build an expert system for analyzing the personality of a number of people and then distribute them in groups , each group will have members with different personalities.

I have been reading about ES a lot but I still confused , does rule-based system enough to build the system, or do I have to use matching algorithms like stable marriage or Maximum bipartite matching.

# Answer
Expert systems are called "Experts" for a reason. They are cable of doing a particular job at up most perfection. Not 100% but 99%. Now I am no expert on these systems (pun intended) but as far as these two algorithms go my answer would be to try to boil down to the exact purpose of your system. These two algorithms do two different things. All in all what I am saying is to find an concrete job that your expert system will do. Using the **Stable Marriage** algorithm you will be ranking and connecting vertices with edges accordingly to their respective weights. As for the **Maximum Matching** algorithm you will be trying to find the lone vertices and edges. At this point according to your needs I would try to find something in between or edit the **Stable Marriage** algorithm to fits your needs.

Good luck! You have chosen to tackle a very strong problem ;)
> 1 votes

---
Tags: algorithms, artificial-intelligence
---


# Question
Title: Equivalence of two definitions of substitution
### Preliminary definitions

Barendregt \[2004\] introduces the following two definitions of substitution and their equivalence:

* Ottamnn variable convention (p. 26)

> 2.1.13. Ottamnn variable convention. If $M\_1, ..., M\_n$ occur in a certain mathematical context (e.g. definition, proof), then in these terms all bound variables are chosen to be different from the free variables.

Remark 1: I'm using the name 'Ottmann variable convention' because in the 6th impression of "The Lambda Calculus. Its Syntax and Semantics", Barendregt replaced the name 'variable convention' by this name. See 'Addenda for the sixth imprinting', p. E1.
* First definition (p. 27)
* Second definition (p. 578)
* Equivalence (p. 579)

> If one observes the variable convention, then $M\[ x:= N \]$ as in definition 2.1.15 is the same substitution as in Curry's definition C.1.

### Question

Since (1) follows the Ottmann variable convention its normalisation using both definitions of substitution should be the same.

$$(λxx.x)yz \qquad \qquad (1)$$

Remark 2: I know it is silly to abstract over $x$ twice in (1), but this is not banned anywhere.

Using Definition C.1, the normalisation of (1) is $z$, but using Definition 2.1.15 I got stuck in

$$(λxx.x)yz = ((λx.x)\[ x:=y \])z$$

because Definition 2.1.15 doesn't include a clause when the bound variable and the variable to substitute are the same, that is, the missing clause is

$$λx.M\[ x:=N \] ≡ λx.M.$$

Are really both definitions the same using the Ottmann variable convention? Am I missing something when using Definition 2.1.15?

### Reference

Barendregt, H. P. (2004). The Lambda Calculus. Its Syntax and Semantics. Revised edition, 6th impression. Vol. 103. Studies in Logic and the Foundations of Mathematics. Elsevier.

# Answer
The following remark from definition 2.1.15 gives you a clue:

> In the third clause it is not needed to say "provided that $y \not \equiv x$ and $y \not \in \mathsf{FV}(N)$". By the variable convention this is the case.

Since you can't make substitutions, it means that there is some violation of the *variable convention* (§2.1.13):

> If $M\_1, ..., M\_n$ occur in a certain mathematical context (e.g. definition, proof), then in these terms all bound variables are chosen to be different from the free variables.

In the meta-level expression

$$((λx.x)\ \[ x := y \])\ z,$$

let us denote $M\_1 = (λx.x)$ and $M\_2 = x$. Notice that $x$ is bound in $M\_1$, but free in $M\_2$. That violates the variable convention, so you can't use definition 2.1.15, because it *relies* on that convention.
> 3 votes

# Answer
It is unclear to me what the precise definition of the 'Ottmann variable convention' (OVC) is, but from what I have available:

> "If $M\_{1}$, … , $M\_{n}$ occur in a certain mathematical context (e.g. definition, proof), then in these terms all bound variables are chosen to be different from the free variables." Barendregt \[2004\]

I concluded that the $\lambda$-term $((\lambda{x}.x)\[x := y\])z$ does not comply wit the definition above, since there is both a bounded (in $(\lambda{x}.x)$) and an unbounded (right brackets) occurrence of $x$ in the same term, Hence the confusion.

This is perhaps hinted by the claim in Definition 2.1.15

> In the third clause it is not needed to say “provided that $y \neq x$ and $y \notin FV (N)$”. By the Ottmann variable convention this is the case.

That implies the 'Ottmann variable convention' is sufficient to show $y \neq x$ and $y \notin FV (N)$ for any term of the form $(\lambda{y}.M)\[x := N\]$ that follow the convention. From this is possible to conclude that nested abstractions over the same variable do not follow the 'Ottmann variable convention', a quick example, assume $(\lambda{xx}.w)y$ follows the OVC

* $(\lambda{xx}.w)y = (\lambda{x}.w)\[x := y\] $ (Axiom)
* a contradiction arise with:
    + $x \neq x$ (by OVC implication)
    + $x = x$ (trivial)
* Hence $(\lambda{xx}.w)y$ does not follows the OVC

So, to answer your question:

> Are really both definitions the same using the Ottmann variable convention? \> Am I missing something when using Definition 2.1.15?

Yes, they are, but in my opinion, the definition of the 'Ottmann variable convention' provided is perhaps not concise enough to clarify this kind of silly edge cases.

PS: I have some confidence in this answer but all is really what I was able to conclude from the definition given, I can perhaps me missing something as well.
> 3 votes

---
Tags: lambda-calculus
---


# Question
Title: How to know maximum final states in a DFA?
If a NFA contains N states, then Equivalent DFA can have atmost $2^N$ states.

Is there any method or any concept to know, how many final and non-final states will be there in the equivalent DFA ?

**Take for example** : An NFA has 7 states out of which 3 are final states. Its equivalent DFA can have atmost 128 states.

Then is there any method to find maximum number of final states and non final states in converted equivalent DFA ?

# Answer
> 1 votes
The set of final states in the DFA that results from the subset construction is given by

$$F' = \\{ S \mid S \cap F \neq \emptyset\\}$$

If there are $n$ states in $Q$ and $k$ final stages in $F$, then there are $2^k-1$ nonempty subsets of $F$ and each of these can be occur together with a subset of the $n-k$ states that are not final.

---
Tags: automata, finite-automata
---


# Question
Title: Decidability of Unary Languages / One-to-One Mapping
I'm trying to prove that there exists an undecidable subset of {1}\* by showing a one-to-one correspondence between it and {0, 1}\* (which would imply a one-to-one correspondence between their power sets), but I'm struggling with how to do the one-to-one mapping. Isn't it just surjective? That is, there's one unary representation of potentially many binary strings (e.g., 1 = 01 = 0000000000001).

What am I misunderstanding here? Or am I just taking the wrong overall strategy?

(This isn't homework; I'm reviewing for a midterm, and it's a little concerning I'm getting tripped up here)

# Answer
> 5 votes
Instead of mapping the string $x\in\\{0,1\\}^\*$ to $1^{\mathrm{bin}(x)}$ (where $\mathrm{bin}(x)$ is the number denoted by interpreting $x$ as a string in binary, map it to $1^{\mathrm{bin}(1x)}$. Now every string in $\\{0,1\\}^\*$ maps to a unique number of $1$s.

# Answer
> 3 votes
The easiest approach is probably to use *unary notation*. The string $1^k$ can be thought of the natural number $k$; $\varepsilon$ is then $0$.

We then have that every unary language corresponds to a unique subset of $\mathbb{N}$ – and vice versa, for every subset of $\mathbb{N}$ we can find a unique language over the alphabet $\\{ 1 \\}$.

There are uncountably many subsets of $\mathbb{N}$, so there are uncountably many languages over the alphabet $\\{ 1 \\}$.

---
Tags: turing-machines, undecidability, uncountability, mapreduce
---


# Question
Title: How to partition a set into a given number of disjoint subsets subject to some conditions?
I am given a set $A\triangleq\\{1,\ldots,k\\}$, an integer $s\leqslant k$, and non-negative integers $a\_{ij}$. My problem is to find $s$ disjoint subsets $S\_j$ of $\\{1,\ldots,k\\}$ such that:

1. $\bigcup\_{j=1}^s S\_j=A$; and
2. $|S\_j|\leqslant a\_{ij}$ for all $i\in S\_j$ and $j=1,\ldots,s$.

How to solve this problem? Is it hard to find a feasible solution?

I think it is not easy to solve the problem because I tried some procedure that starts by some $j\in\\{1,\ldots,n\\}$ and assigns $i\in\\{1,\ldots,k\\}$ until the number of $i$ assigned to $j$ are greater than $a\_{ij}$ for some $i$ assigned. But this is not correct because I could be left of some $i$ that could not be assigned to any $j$ (because of their $a\_{ij}$ which could be not satisfied).

The brute force method, when I have to generate all subsets of $A$ and test each one, works for me ($k=8,n=3$) but very inefficient.

# Answer
> 10 votes
This problem is NP-hard by reduction from Vertex Cover.

In the Vertex Cover problem, we are given a graph $G = (V, E)$ and a number $r$, and our task is to determine whether there is some subset $U$ of at most $r$ vertices from $V$ such that every edge in $E$ is incident on at least one vertex in $U$. (Equivalently: Is it possible to kill every edge in $G$ by deleting at most $r$ vertices?)

First, partitioning $A$ into $s$ disjoint subsets is equivalent to assigning each element in $A$ exactly one of $s$ possible labels. The basic idea of the reduction is to create a label $S\_j$ for each vertex $v\_j$ in $V$, and to "allow" each edge to be assigned only one of the two labels corresponding to its endpoints, in the following sense: assigning an edge a corresponding label introduces no (genuine) constraint on what other edges can be assigned the same label, while assigning an edge to a non-corresponding label prevents any other edge being assigned the same label -- which of course has the effect of pushing up the number of distinct labels required.

To construct an instance $(A, a, s)$ of your problem from an instance $(G, r)$ of Vertex Cover:

1. Set $k$ to $|E|$, and create an element $(i, j)$ in $A$ for each edge $v\_iv\_j$ in $E$. (These pairs can be thought of as the integers $1, \dots, k$; any bijection between them will do.)
2. Set $a\_{(b, c), d}$ to $|E|$ if $d=b$ or $d=c$; otherwise, set $a\_{(b, c), d}$ to 1.
3. Set $s=r$.

If $(G, r)$ is a YES-instance of Vertex Cover, then it's easy to see that the just-constructed instance of your problem is also a YES-instance: just pick the labels $S\_j$ corresponding to the vertices $v\_j$ in any solution $U$, and for each edge $v\_bv\_c \in E$ assign the corresponding element $(b, c) \in A$ whichever one of the labels $S\_b$ or $S\_c$ was picked (choose arbitrarily if both labels were picked). This solution uses $s$ subsets, and is valid because the only $a\_{ij}$ in force are those for *corresponding* labels, which have the (non-) effect of preventing more than $|E|$ edges being assigned the same label.

It remains to show that a YES-instance $X=(A, a, s)$ of your problem implies that the original $(G, r)$ is a YES-instance of Vertex Cover. This is slightly more complicated, since a valid solution $Y$ to $X$ may in general assign an edge $(i, j)$ a *non*-corresponding label $S\_m$, i.e., $m \notin \\{i, j\\}$, meaning that we can't necessarily "read off" a valid vertex cover $U$ from a valid solution $Y$.

However, assigning a non-corresponding label has a high cost that severely limits the structure of the solution: whenever an edge $(i, j)$ is assigned such a label $S\_m$, with $m \notin \\{i, j\\}$, the fact that $a\_{(i, j), m} = 1$ ensures that it must be the *only* edge assigned this label. So, in any solution $Y$ containing such a non-correspondingly-labelled edge $(i, j) \mapsto S\_m$, we could construct an alternative solution $Y'$ as follows:

1. Arbitrarily choose the new label $S\_z$ for $(i, j)$ to be either $S\_i$ or $S\_j$.
2. Assign $(i, j)$ this new label. If this results in an invalid solution, it must be because exactly one other edge $(i', j')$, $z \notin \\{i', j'\\}$ had already been assigned the label $S\_z$. In that case, set $(i, j) = (i', j')$ and go to step 1.

The above algorithm must terminate in one of two ways: either a new label $S\_z$ is found that introduces no contradiction, or a complete cycle of vertices is found. In the former case, a valid new solution with $s-1$ sets is found, while in the latter case a valid new solution with $s$ sets is found; either way, we have constructed a valid new solution with at least one more edge assigned to a *corresponding* label. After repeating this entire process at most $|E|$ times, we will have produced a valid solution $Y''$ from which a solution to the original Vertex Cover problem *can* be read off.

This construction is clearly polynomial time, so it follows that your problem is NP-hard.

---
Tags: complexity-theory, integer-programming
---


# Question
Title: Best data structure for a queue with random reads?
Well, it's not exactly a queue if it allows for random reads. This question is about a data structure which behaves like a queue for insertions and a sorted dictionary for reads.

Imagine an algorithm that maintains a list of elements so that:

1. It reads an element from the list based on its key.
2. It then inserts that element as the last element in the list.
3. On demand it returns all entities in the order in which they were inserted.

And I am looking for a solution that is faster than a naive implementation based on a linked list, which would have complexity O(n) for all three parameters - search, insert as the last element, and return all elements in the inserted order.

Such a data structure should probably:

1. Allow for a quick lookup of the key (e.g. a tree, a hashmap)
2. Maintain the order in which elements were inserted (e.g. a list, a queue)

---

A practical example is a list of agents receiving calls. When an agent is called, it's fetched from the list, and when it finishes the call, it's put at the back of the list. Therefore the agent that is first in that list is the most idle agent (waiting for a call the longest). In other words, the list would be sorted according to agent's idleness.

---

Another example implementation could be based on two structures, one dictionary and one array, referencing each other. The dictionary would keep the index in the array as the value and the array would keep the key as the value. Then the element would be removed from the array by looking up the value/index in the dictionary and the dictionary would be updated with the new index once the element was put as the last element in the array.

# Answer
Take any dictionary data structure and *link its entries* in whichever order suits you. In essence, you retain the $\Theta$-costs from the basic structure.

In search trees, this is called *threading*. It gives you constant-time access to the first and last element, respectively, and maintaining the threading takes only constant-time overhead for each dictionary or queue operation. As a consequence, you get $\Theta(\log n)$ access by key, $O(1)$ access to front and back of the queue (without modification), and $\Theta(\log n)$ insertion and deletion.

If you use hashtables you get $O(1)$/$\Theta(n)$ (AC/WC) access by key, $O(1)$ access to front and back of the queue (without modification), and $O(1)$/$\Theta(n)$ (AC/WC) insertion and deletion. The usual caveats apply.
> 8 votes

---
Tags: data-structures, dictionaries, priority-queues
---


# Question
Title: Why does the last step of Decompression Transformation of the cited report work?
The report referred in the title is the following: A Block-sorting Lossless Data Compression Algorithm, by M. Burrows and D.J. Wheeler, SRC Research Report, 1994

The step I do not understand is step D3, on page 4:

> `for each i = 0, ... , N - 1: S[N - 1 - i] = L[T^i[I]]`

Question is: **why** does this work, i.e. why does this give us the desired result?

(To be clear, I understand, what `T` means, and how `T^i` is constructed. I even coded down the formula above in Python, and it did give me the desired result -- I know, because I coded the other steps as well. I just don't see why it works?)

The algorithm described in the report consists of a "Compression" and a "Decompression" part, my question being about the last step of the "Decompression".

In order to give more context, as requested in the comment, I'll try summarise here the two mentioned parts.

**Compression**

Input text: `S`

C1. Take all the cyclic rotations of `S`, and sort them lexicographically (result: matrix `M`). Return `M` and `I`, where `I` is the index of the first row of `M`, which is equal to `S`.

C2. Let `L` be the last column of `M`.

Output of compression: (`L`, `I`)

**Decompression**

Input: (`L`, `I`)

D1. Sort `L`. Result: `F`.

D2. Calculate vector `T`, such that

> If `L[j]` is the `k`th instance of `ch` in `L`, then `T[j] = i` where `F[i]` is the `k`th instance of `ch` in `F`.

In other words: `F[T[j]] = L[j]`

D3. Calculate `S`:

> `for each i = 0, ... , N - 1: S[N - 1 - i] = L[T^i[I]]` where `T0[x] = x`, and `T(i + 1)[x] = T[Ti[x]]`

**EDIT**: Example for further clarification, based on the answer of @KWillets.

Let's take the example `abraca` used in the paper as well.

As also shown in the paper, the suffixes are the following:

```
  F|       |L         T        T0   T1   T2   T3   T4   T5
  a|a b r a|c         4         0    4    2    5    3    1
  a|b r a c|a<--I=1   0         1    0    4    2    5    3<--I=1
  a|c a a b|r         5         2    5    3    1    0    4
  b|r a c a|a         1         3    1    0    4    2    5
  c|a a b r|a         2         4    2    5    3    1    0
  r|a c a a|b         3         5    3    1    0    4    2

```

From the answer of @KWillets:

> Think of the source string S as a (array-based) linked list, with one character per node, so that we can output S from left-to-right by traversing pointers.

I (suppose), that I understand this part. In the concrete example this would mean the following:

```
  position   0      1       2       3       4       5
  label      A -->  B  -->  R  -->  A  -->  C  -->  A
  index of   1      2       3       4       5       ? (0? "EOF"?)
  next node

```

What I'm not sure about, is if the last position (5) in this case would also have an index to item 0 (thus making a "cyclic" list, or it would just be the end of the list).

> But let's also arrange it so that the nodes are suffix sorted, ie each node is assigned a position i such the suffix that begins at that node is greater than the one at i-1, and so on.
>
> The links in this array are T \[...\]

As far as I understand, this would mean the following (i.e., making the links equal to `T`):

```
                       ________________    _________________
                       |               |  |                 |
                       |        _______________________     |
                       V       |       |  |            V    |
     position   0      1       2       3  |    4       5    |
     label      A <--- A    -> A       B<-     C       R----
     index of   4      0    |  5       1       2       3
  next node     |___________|_________________^  \
                            |____________________|

```

> (and traversing them is D3 above, and the label for each node is in F above)

Makes sense, if I traverse this list, in the sequence of T (i.e. 0-\>4-\>2-\>5-\>3-\>1), then the result will be `ACARBA`, i.e. the reverse of the original input string.

**Main question**, that I still do not understand: *why does `T` have this property*?. I.e. why will a list defined as described in D2 happen to be the correct indexes for generating the reverse of the original string?

Specific questions:

> L\[i\] is the character just to the left of suffix i.

What does it mean "the character to the left of suffix i"?

Considering the above example, would this mean that e.g. for `i=2` `L[2] = 'r'` is "to the left of" `acaabr`? Does this mean that `'r'` cyclically precedes the first `'a'` in `'acaabr'`, i.e. if from the first `'a'` we went "one step to the left", then we would get the `'r'` at the end? Also, how does this help us?

> \[...\] for instance if L\[i\]='b', that means there is some suffix starting with 'b' that T\[i\] should point to, but we don't know which one

Let's consider `'a'` instead of `'b'`, since there are more `'a'`'s. So, for `i=3`, `L[3]='a'`, that means there is a suffix starting with `'a'`, to which `T[3]` should point to. Indeed, `T[3]=1`, which is the second suffix starting with `'a'`, so it corresponds to the description of the algorithm.

What I don't understand: how does `L[i]` come into the picture? Wasn't `T` supposed to be the ordering among the `F`'s? (I guess this must have something to do with the above mentioned "the character to the left" property, but I do not see the connection, yet.)

Also, how do we know for sure that there must be such a suffix?

# Answer
First, a bit of terminology:

The BWT represents a list of suffixes in lexicographical order (I'll use the term suffix instead of block, since the string is usually terminated with a metacharacter that makes suffix and block sorting equivalent). Each index i in the L and F arrays represents a unique suffix, and it can be illustrative to make a table with both L and F side-by-side.

L\[i\] is the character just to the left of suffix i, or the last column in a cyclic shift of the string; it basically tells us for any given suffix S\[j..n\] what S\[j-1\] is.

T allows a scan of the text without certain overheads which I'll describe. The implementations I've seen use $T^{-1}$, which allows a forward scan of the text, but in D3 it's doing a backward scan.

Structure:

Think of the source string S as a (array-based) linked list, with one character per node, so that we can output S from right-to-left (using T) or left-to-right (using $T^{-1}$) by traversing pointers. But let's also arrange it so that the nodes are suffix sorted, ie each node is assigned a position i such the suffix that begins at that node is greater than the one at i-1, and so on.

The links in this array are $T$ (and traversing them is D3 above, and the label for each node is in F above). But it's a bit bulky, and there are a number of artistic ways to compress it.

The BWT is probably the most difficult way. It's a representation of the links of T, but very indirectly, since for instance if L\[i\]='b', that means there is some suffix starting with 'b' that T\[i\] should point to, but we don't know which one -- there's a run of 'b's in F that could be the right index.

To disambiguate 'b' we have to use a property of $T^{-1}$: for a range of suffixes that begin with the same character, their $T^{-1}$ pointers are in ascending order. That is, if 'bat..' and 'bug...' are suffixes, the $T^{-1}$ pointer from 'b' to 'at...' comes before the one from 'b' to 'ug...'. In other words, their order is the same as the order of their suffixes.

That means that for any given 'b' at index i in L, we can figure out which entry in the 'b' range T\[i\] points to by counting only the b's that precede i in L, ie the rank of the 'b' at i among all the b's in L. That's D2. Basically T\[i\] = the rank of L\[i\] amongst other incidences of the same character in L + the start of the range that begins with L\[i\].

Calculating ranks one i at a time is slow (although there are other data structures that make it fast), so the translation to T is done all at once, by counting and summing in a process similar to counting sort (D1 and D2). But regardless of how, the output T is an array-based linked-list structure that can be decoded much more quickly than the ambiguous back-links in L.

(Also, while traversing T to output S, we can omit the character labels at each node if we use L and output the character just preceding, and adjust everything by 1. That's the L\[...\] in D3. )
> 1 votes

---
Tags: algorithms, data-compression
---


# Question
Title: Algorithm to efficiently determine whether a magazine contains all the letters in a search string
Title pretty much states the question, I was looking for some assistance with the following:

You are given a search string and a magazine. You seek to generate all the characters in a search string by cutting them out form the magazine. Give an algorithm to efficiently determine whether a magazine contains all the letters in a search string.

I wrote: "Create a count sort which just buckets every occurrence of each specific letter in the magazine down the line. Then use that to compare vs. the search string. If the magazine contains all the letters in the search string, then great you're done; otherwise you need a new magazine."

I feel like that's not enough of an answer for this problem, can someone help? Thanks!

# Answer
If this was a real life problem, and the search string contained n letters, while the magazine contained m letters, then this would take O (n + m) in time. Typically you would assume that n is very small compared to m, so this solution would take a lot more time than needed.

I'd create a counted set of the letter in the search string. If that counted set is empty (because the search string was empty) I'm done. Then iterate through the letters in the magazine; if a letter is in the counted set then remove it and I'm done if the set became empty. Otherwise, if the iteration finishes then I have a counted set of all letters that cannot be provided by the search string.

This will usually end quite quickly, long before all the letters in the magazine are examined.
> 1 votes

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


# Question
Title: What do the terms 'Sample' and 'Sampling' mean in the discussion of Pattern Recognition and Machine Learning?
The tag sampling tells me that,

> Creating samples from a well-specified population using a probabilistic method and/or producing random numbers from a specified distribution.

Now, the question becomes: what is `population` then?

Suppose, I am implementing a classifier.

I have a set of training data in the file `train.txt`, and a set of test data in the file `test.txt`.

**What element can be termed as 'Sample', and what activity can be termed as 'Sampling' in this case?**

# Answer
> 1 votes
Suppose that you're a pollster. You're trying to understand who will win the elections in Mars. What do you do? You *sample* a few eligible voters from the voter *population*, ask them for their preferences, and tally their votes. Sampling is not trivial, however, since your sample might not be representative, and so you might need to add in some weights when you tally the votes.

Here is another example. You're trying to understand the connection between lifestyle and longevity. You *sample* a few random people from the general *population*, and give them a questionnaire. Your goal is to create a formula that predicts life expectancy given some features of the person's lifestyle, such as whether they smoke or not.

The second example demonstrates the sort of problem that machine learning algorithms solve. Hopefully these examples give you enough hints to understand what *sample* and *population* mean in your context.

---
Tags: sampling
---


# Question
Title: Is it possible to build a computer that would output $10^{10^{100}}$ symbols and halt, without using ~$10^{100}$ space?
My recent question on Programming Puzzles and Code Golf got some fair attention and showed that not only it is very easy to output $10^{100}$ symbols and halt, but actually quite convenient in many programming languages as well.

While posting it I was wondering whether I should ask for $10^{10^{100}}$ instead but decided against that because while theoretically straightforward, I think it's simply physically impossible within this universe.

Here's my reasoning: to iterate over some command $b^m$ times, one needs $O(m)$ space to maintain the counter. Physical computers of today aside, $10^{100}$ just exceeds the estimated number of particles in the known universe by many orders of magnitude.

My question is not about alternative possibilities of physical realization of memory storage but about the principle. I'm not well-grounded in restricted Turing computation. Are there some tricks towards reducing the space complexity below $O(m)$ given that the *value* of the counter is never needed, just the fact that it counts the proper number of times and then halts?

# Answer
> 7 votes
The answer really depends on your computation model. On a (fixed) Turing machine, you can count up to $n$ using no space. A better formulation of the question is like this:

> Is there a function $f\colon \mathbb{N} \to \\{0,1\\}^\*$ satisfying $|f(n)| = o(\log n)$ and a program $P$ such that $P(f(n))$ uses space $O(f(n))$ and outputs $1^n$?

It is a basic result of Kolmogorov complexity that this is impossible, even without the restriction on space. However, if you are willing to allow randomness and to incur some (multiplicative) inaccuracy, you can use the approximate counting technique of Morris and Flajolet, for which $|f(n)| = \Theta(\log \log n)$.

---
Tags: complexity-theory, space-complexity
---


title: Determine nth prime number in O(?)

text:
# Question
Title: Determine nth prime number in O(?)
If f(n) is the problem to determine the nth prime number, how fast can this be done, i.e.

* What is the fastest known algorithm to find the nth prime number?
* What are lower bounds for the time complexity?

# Answer
> 3 votes
For upper bounds, see this question on math.se. Apart from a few trivial cases, we don't know how to prove any meaningful lower bounds on general computation models, and in particular for this problem.

# Answer
> 2 votes
You can calculate π (N) = the exact number of primes ≤ N in about O (N^(2/3)), give or take a logarithm, without any really difficult mathematics (google for Lagarias Miller Odlyzko algorithm); there are faster methods that are *hard*.

Find a suitable function for estimating the value of the n-th prime, say the n-th prime is roughly around X (constant time). Count the number of primes ≤ X (roughly O (X^(2/3))) which should be some n' close to n. If n' is too far away from n then you use it to get a better estimate X'. If n' is close to n then you create a sieve that includes the number X and is big enough to include the n-th prime.

# Answer
> -1 votes
Answer of both questions depends on what kind of solution you want. That is if you want an exact solution you can use **Sieve of Eratosthenes** algorithm which has a time complexity of $O(n \log \log n)$. If you want an approximate solution then you can use an **approximation algorithm for primality testing** (see Wikipedia). This algorithm has a time complexity of $O(n/(\log n)^2)$ which is sublinear.

---
Tags: time-complexity, primes
---


# Question
Title: Is "Find a Steiner Tree of cost < K" NP-hard?
Finding the minimum Steiner tree is well known NP-hard. It seems obviois that asking "find a Steiner tree of cost \< K" has to be NP hard, because I could solve the original problem by repetedly calling an algorithm that solves the second. But is this "repeteadly call"/loop a valid reduction? There seems to be something fishy with it, isn't it exponential in the number of bits of K (like the famous knapsack DP algorithm)?

Thanks

# Answer
> 3 votes
In fact, the optimization version of minimum Steiner tree isn't NP-hard, since only decision problems can be NP-hard. When we say that a minimization problem like minimum Steiner tree is NP-hard, what we mean is that the corresponding decision version is NP-hard. The decision version is just what you wrote: given an instance of minimum Steiner tree and a number $K$, to decide whether the minimum Steiner tree has cost at most $K$.

---
Tags: np-complete, reductions, np-hard
---


title: Hadamard gate on entangled qubit

text:
# Question
Title: Hadamard gate on entangled qubit
**TL;DR:** If you have two entangled qubits in the state $|00\rangle + |11\rangle$, what is the result of applying the Hadamard gate on the second qubit, and why?

---

I am trying to understand $\text{PSPACE} \subseteq \text{QIP}(3)$ (Watrous, 2003), and have troubles understanding the following.

**Hadamard gate:** Given some qubit, one can test that it is in a uniform superposition by applying the Hadamard gate on it as it will map it to $|0\rangle$ in this case, $$H(|0\rangle + |1\rangle) = |0\rangle.$$ By measuring it, you have some probability to get a $1$ iff. the qubit was not in a perfectly uniform state.

**With entanglement:** Now, the paper claims that you can use the Hadamard gate to detect entanglement as well. Given two qubits, $x,y$, that are perfectly entangled, you can have them in the superposition $$xy = |00\rangle + |11\rangle.$$ I understand that if you measure $x$, then apply the Hadamard gate to $y$, it will not map it to $|0\rangle$ as it will be entirely determinated by the measurement made on $x$.

**What I don't understand:** They do not claim to be able to measure/collapse the qubits that are entangled with the qubits they want to test, so how does it work? If you have two entangled qubits in the state $|00\rangle + |11\rangle$, what is the result of applying the Hadamard gate on the second qubit, and why?

---

**Where is it in the paper:**

* When skecthing the protocol at the end of the introduction section (End of first paragraph, page 2):
> If there is significant correlation between the low-index prover responses and the high-index verifier-messages, the uniformity test \[Hadamard gate, measure 0s\] will fail with high probability
* When discussing the completeness of the protocol, in particular step 2. of the verifier (start of page 8):
> Next, the verifier applies the Hadamard transform to every qubit in each register of $\bar{R^u}$. If $\bar{R^u}$ now contains only 0 values, the verifier accepts, otherwise the verifier rejects. In short, the verifier is projecting the state of $\bar{R^u}$ onto the state where $\bar{R^u}$ is uniformly distributed over all possible values. It is easy to check that in the case of the honest prover the registers $\bar{R^u}$ are not entangled with any other registers, as each register of $P^u$ depends only on those of $R^u$, and are in a uniform superposition over all possible values. Thus, the verifier accepts with certainty in this case.
* Also in the proof of soundess, same page

# Answer
> 7 votes
If you mean result in terms of state, then you can compute this by applying the matrix $I \otimes H$ to the Bell state.

If you mean what happens operationally, then observe that applying a hadamard gate on each qubit of the Bell state results in no change -- the resulting state is again the Bell state. So, if you apply two hadamard gates in parallel or none at all and then you measure both qubits, you will get perfect correlations between the measurement outcomes (measurement outcomes on the qubits are guaranteed to be equal). However, if you apply a hadamard gate to either the second qubit or the first qubit and then measure both qubits, then the measurement outcomes will be completely independent of each other, that is, the measurement result of the first qubit can be $0$ or $1$ with $50\\%$ probability and the measurement result of the second qubit can be $0$ or $1$ with $50\\%$ probability, regardless of what was seen in the other measurement.

---

Algebra:

Given the state $|00\rangle + |11\rangle$, you can not compute the Hadamard gate by factoring the state and applying a Hadamard to only one qubit, as the state is entangled and cannot be factored into two independent qubits. You can, however, apply the result of $I \otimes H$, which is the operation of applying Identity gate on the first qubit and the Hadamard gate on the second. The resulting operation is, with scaling factor $s$,

$$ I \otimes H = \left\[\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\right\] \otimes \frac{1}{\sqrt{2}} \left\[\begin{matrix} 1 & 1 \\ 1 & -1 \end{matrix}\right\] = s\left\[\begin{matrix} 1 & 1 & 0 & 0 \\ 1 & -1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & -1 \\ \end{matrix}\right\]$$

For more details on this, see the question How to apply a 1-qubit gate to a single qubit from an entangled pair?.

Now, you can pass your entangled state, $ \left\[\begin{matrix} \frac{1}{\sqrt{2}} & 0 & 0 & \frac{1}{\sqrt{2}}\\ \end{matrix}\right\]^{T} $ for $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$, through the gate and get $$ s\left\[\begin{matrix} 1 & 1 & 0 & 0 \\ 1 & -1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & -1 \\ \end{matrix}\right\] \left\[\begin{matrix} \frac{1}{\sqrt{2}} \\ 0 \\ 0 \\ \frac{1}{\sqrt{2}}\\ \end{matrix}\right\] = \frac{1}{2}\left\[\begin{matrix} 1 \\ 1 \\ 1 \\ -1\\ \end{matrix}\right\] $$ Which is the state $$|00\rangle + |01\rangle + |10\rangle - |11\rangle.$$ And measurement of the first qubit or the second qubit would be 0 or 1 with equal probability, and give no information on the state of the other qubit.

# Answer
> 3 votes
You don't have to do the whole matrix multiplication to get the final result. A more intuitive way is two write

$$|00\rangle +|11\rangle = |0\rangle|0\rangle + |1\rangle|1\rangle\\,.$$

Now apply the Hadamard gate on all terms of the first qubit and keep the second untouched. Since for a single qubit we have $H|0\rangle = |0\rangle+|1\rangle$ and $H|1\rangle =|0\rangle -|1\rangle$, we can write:

\begin{align\*} \big(H|0\rangle\big)|0\rangle + \big(H|1\rangle\big)|1\rangle &= \big(|0\rangle+|1\rangle\big)|0\rangle \+ \big(|0\rangle -|1\rangle\big)|1\rangle\\ & = |0\rangle|0\rangle + |1\rangle|0\rangle + |0\rangle|1\rangle \- |1\rangle|1\rangle\\ &= |00\rangle + |01\rangle + |10\rangle -|11\rangle\\,. \end{align\*}

I have dropped the normalizations.

---
Tags: quantum-computing
---


# Question
Title: Complexity-theoretic difficulty of checking the value of $\pi(x)$?
The prime-counting function, demoted $\pi(x)$, is defined as the number of prime numbers less than or equal to $x$.

We can define a decision problem from $\pi(x)$ as follows:

> Given two numbers $x$ and $n$, written in binary, decide if $\pi(x) = n$.

A friend and I were talking about this problem earlier today. There's a pseudopolynomial-time algorithm for this problem - just count up to $x$, using trial division at each step to see how many of the numbers are prime, and check if that's equal to $n$. The problem is also in PSPACE, since the algorithm I just described can be implemented to use only polynomial auxiliary space.

However, I'm having trouble finding a way to place this problem into a lower complexity class. I can't see how to build a polynomial-time verifier for the problem, so I'm not sure whether it's in NP, and I can't think of a way to get it into the polynomial hierarchy at all.

What is the most appropriate complexity class for this problem?

Thanks!

# Answer
This is very much an open problem. I'll sketch some classes that the problem could "naturally" fit in.

Your definition is somewhat awkward to work with, the problem is hard to fit in to any existing complexity class. The language you've defined is the intersection of the languages $\\{(x,n)|\pi(x)\leq n\\}$ and $\\{(x,n)|\pi(x)\geq n\\}$. So if for instance $\\{(x,n)|\pi(x)\leq n\\}$ was in class $K$ then $\\{(x,n)|\pi(x)\geq n\\}$ would be in $coK$. This makes giving a characterization of the language you've defined hard because one would have to state "the intersection of a language in $K$ with a language in $coK$" to give the tightest bound.

The problem "Compute $\pi(X)$" is a problem in $\\#P$, where $\\#P\subseteq FPSPACE$ is the class of problems of the form "Compute the number of accepting paths of a nondeterministic, polynomial TM". Clearly we can construct a nondeterministic TM that guesses a number $q \leq x$, and then (with AKS) tests whether $q$ is prime.

A decision variant of $\\#P$ is $PP$, which is the class of languages that are of the form: "Given a nondeterministic polynomial TM, do at least half the computation paths accept?". Both $\\{(x,n)|\pi(x)\leq n\\}$ and $\\{(x,n)|\pi(x)\geq n\\}$ are probably reducible to a problem in $PP$ (by doing some fudging to the aforementioned TM to balance out the number of accepting paths).
> 11 votes

# Answer
Your problem is in C$\_=$P $\hspace{-0.06 in}\text{,}$ via the algorithm

$\\;\\;\\;$ non-deterministically guess $\big\[$an integer `m` such that $\\: 0\leq m \< 2^{\lceil \hspace{.02 in}\log\_{\hspace{.02 in}2}\hspace{-0.02 in}(x+1)\rceil}\big\]$ and a bit `b`
$\\;\\;\\;$ if `x < m` then reject
$\\;\\;\\;$ if `b=1` then:
$\\;\\;\\;\\;\\;$ if `m < n` then accept else reject
$\\;\\;\\;$ else:
$\\;\\;\\;\\;\\;$ if `m` is prime then accept else reject

.
In particular, your problem is also in PP, since PP is closed under truth-table reductions.
> 3 votes

# Answer
In practice, you may get the answer faster or slower :-(

There are reasonably good approximations for π (x). So you calculate such an approximation, and if it is too far away you know that π (x) ≠ n. For example, if n ≥ x then I know that π (x) ≠ n without calculating anything.

There is a fast algorithm which determines if π (x) is even or odd, running in O (x^(1/2)). You can run this algorithm and it may detect that the parity of n is wrong and you are done. It has a fifty chance if n is a random integer close to π (x).

Other than that, I don't know of any method that is faster than calculating π (x). Which is very inconvenient - if I write a program that is supposed to calculate π (10^25), and I get a result that isn't obviously wrong, then there is no way to check that my result is correct other than repeating the calculation. And you can't just repeat the calculation using my program, you need to write a different program, otherwise you wouldn't detect if my program has any bugs that make it calculate a slightly different function than π (x).

π (x) can be calculated reasonably easily in about O (n^(2/3)), and faster with some really deep maths.
> 2 votes

---
Tags: complexity-theory, primes
---