title: Modified Bubble Sort's time complexity

text:
# Question
Title: Modified Bubble Sort's time complexity
I have an array (of hundreds of numbers) and I need to sort them. In this case, I used Bubble Sort because of the better time complexity compared to other algorithms, $\Theta(n^2)$.

```
procedure bubbleSort(arr)
        for i=0 to n-i-1
            for j=0 to n-i-2
                if arr[j] > arr[j+1]
                    Swap arr[j] and arr[j+1]
                end if
            end for
        end for
end procedure

```

I tried a modified version of Bubble Sort, as below;

```
procedure bubbleSort(arr)
    flag = true
    for i= 0 to n-1 do
        for j=0 to n-1-i
            if leftElement > rightElement
                swap leftElement and rightElement
                flag = false
            if flag is true
                break
            end if
        end for
    end for
end procedure

```

So, adding a flag variable that is set true if a swap is made after an entire pass over the array. If no change has been made, then the list is sorted, so the algorithm can stop earlier.

But, after testing the sorting execution time, it turns out that the modified algorithm is slower in many cases.

****What am I doing wrong or what am I not understanding?****

# Answer
> 1 votes
Bubble Sort's time complexity of $\Theta(n^2)$ is not good — it is a common worst-case complexity class for simple sorting algorithms that do not use divide & conquer methods to partition the dataset. These include eg. Selection Sort and Insertion Sort, each of which generally out-performs Bubble Sort due to making far fewer unoptimal swaps. Quicksort also is in this class in the worst case, but the average case is in the much less dramatically scaling $\Theta(n \log n)$ class.

Yves' answer explains why early termination can be a bad idea. However, if you want to preserve a fast termination for nearly-sorted data, I recommend switching to Insertion Sort which overall performs better than Bubble Sort and whose performance further improves substantially for nearly-sorted or sorted data without the need for additional checks. Insertion Sort is commonly used as an optimization for standard library sorting algorithms to process small enough (sub-)arrays to be sorted due to being very performant on smaller datasets, responding well to partially-sorted inputs and being stable (it does not modify the relative order of equal-valued inputs).

# Answer
> 2 votes
Early termination can be a bad idea. Because if the condition for early termination is not met, you perform the whole processing plus testing the extra condition for nothing on every iteration.

The same holds with search in a binary tree: most implementation test for equality of the key to perform early termination. But it is easy to show that significantly early termination is so rare that on average the test is penalizing.

---
Tags: algorithms, time-complexity, sorting, arrays
---


# Question
Title: Is the bubble sort algorithm more efficient for sorting and how to implement it?
I don't know which algorithm is more efficient for sorting, but I want to use Bubble sort and how to implement this algorithm.

# Answer
No, it is not efficient at all. Its main advantage is that it is short to write, but that's all.

See here for a comparison on comparison sorts.

If you still want to implement Bubble Sort, check here for a description.
> 2 votes

# Answer
I think a good starting point is to look at a concrete sorting problem and then check the most voted solutions on LeetCode.

If you want to know how good bubble sort works on the problem you can just filter the submitted solutions for "bubble sort" and compare the runtime of it with the other (e.g. higher rated) solutions using other sort algorithms (but: you need to register to be able to run solutions and compare their runtimes)
> 0 votes

---
Tags: algorithms, sorting
---


# Question
Title: Algorithm for a modified worker-task assignment problem with groups of tasks and substitutability between tasks within groups
I'm looking for an algorithm to solve a modified version of the assignment problem. It differs from the standard assignment problem in that the modified version has groups of tasks instead of just tasks. Similarly to the standard problem, each of the *n* workers is assigned one task, and there are *n* groups of tasks; but in this modified version no two workers can assigned tasks that are in the same group, so there are certain constraints to the assignment. (The assignment is done in order to optimize an objective, i.e., minimize overall costs or maximize overall gains.)

To be more concrete, suppose we have 3 different workers, workers 1, 2, and 3, and six different tasks, tasks *a*, *b*, *m*, *n*, *x*, and *y*, where tasks *a* can substitute (or be substituted by) task *b*, and the same relation holds between tasks *m* and *n* and between *x* and *y*. In this problem, tasks can be said to belong to the set {{*a*, *b*}, {*m*, *n*}, {*x*, *y*}}, and a worker must perform one task in {*a*, *b*} or in {*m*, *n*} or in {*x*, *y*} and no other worker will perform another task in the same group. As a result of the algorithm, if, for instance, worker 1 is assigned to task *a*, then worker 2 and 3 could not be assigned to task *b*.

I tried to find an algorithm for this problem, but I haven't succeeded since I'm not familiar with these problems. I know that if had just one task in each group of tasks, I could use an implementation of the Hungarian algorithm to solve the problem. And I also found out that if there were more tasks than workers, I could use some implementation of the minimum-cost flow problem as long as there was no groups of tasks. I think that my lack of knowledge about this kind of problems prevents me from finding the appropriate algorithm by its name. (I intend to use the algorithm with some data that I'm working on. Once I know the name of the algorithm, I'll try to find an implementation of it in some data analysis software.)

What is the name of the algorithm used for solving the problem that I described above? (It would be even better if the algorithm that solves the problem allows for a varying number of tasks within groups and for more tasks than workers. The constraint then would be that no two tasks in the same groups are assigned to workers and each worker is assigned to one task.)

# Answer
> 0 votes
You can solve this problem as follows. Build a bipartite graph with one vertex per worker and one vertex per group of tasks (one vertex for the entire group; not one vertex per task). The cost of assigning worker $w$ to group $g$ is the smallest cost of assigning $w$ to some task in $g$ (i.e., for each task $t$ in $g$, look up the cost of assigning $w$ to $t$, and then take the lowest of all of those costs).

Next, solve the assignment problem in this graph. This assigns each worker to (at most) one group of tasks, and each group to (at most) one worker.

Finally, convert this into an assignment to tasks. For each worker $w$, if they are assigned to group $g$, find the lowest-cost task $t$ in $g$ (using the same procedure as above) and assign $w$ to $t$.

This will give the optimal solution to your problem.

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


# Question
Title: Time complexity of $\mathsf{NP}$ problem under assumption of $\mathsf{P} \neq \mathsf{NP}$
A simple question, but I can't find an answer in quite the form I'm looking for:

Assume $\mathsf{P} \neq \mathsf{NP}$, and thus $\mathsf{P} \subsetneq \mathsf{NP}$. If we have $L \in \mathsf{NP}$ and $L \notin \mathsf{P}$, does that imply that there is no algorithm for $L$ which runs in $O(n^k)$ steps for all inputs of size $n$ (for any fixed value $k\in\mathbb{N}$)? *I.e.*, there is no polynomial-time algorithm for $L$?

From this answer, that would imply that the time complexity of an optimal algorithm for a problem in $\mathsf{NP}$ (but not in $\mathsf{P}$) is bounded such that must run in between $O(n^k)$ and $O(2^{p(n)})$ time, correct? (Here we use that $\mathsf{NP} \subseteq \mathsf{EXPTIME}$.)

# Answer
If you look at the definition of NP, every problem in P is obviously in NP. P means “all instances can be solved in polynomial time”, NP means “instances with a yes answer and a useful hint can be solved in polynomial time”.

Since P is a subset of NP, P ≠ NP means some problems in NP cannot be solved in polynomial time. NP complete problems can by definition not be in P in that case.

Since the number of possible polynomial size hints is “only” exponential we can find answers to “yes” instance in exponential time. And if we can’t find an answer fast enough, then it must be “no”.
> 0 votes

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


# Question
Title: Do Left regular grammar describe a language containing the reverse of the strings described by the right regular grammar for another language?
Let's say that we have a regular language $L\_1$ that is described by a right regular grammar. Now, assume we have a left regular grammar, can we describe the same language $L\_1$ or would the left regular grammar produce the reverse of all strings present in $L\_1$?

My understanding is that the left regular language would produce a new language $L\_2$ containing the reverse of all strings of $L\_1$. But since we know that reverse of a language is regular, both right regular and left regular grammars are capable of describing regular languages

Is my understanding correct?

# Answer
> 2 votes
Yes, your understanding is correct:

* Reversing the rules of your right regular grammar for $L\_1$ will produce a left regular grammar for $L\_2$, the language consisting of the reverses of the strings in $L\_1$.
* Every right regular grammar can be reversed in this way to form a left regular grammar, and vice versa.
* This does not give you any way to construct a right regular grammar for $L\_1$.
* Consequently, to show that every language that can be described with a right regular grammar can also be described by a left regular one, you need a different argument.
* To show that, it is indeed sufficient to show (by different arguments) that
    + the right regular grammars can indeed describe all regular languages, and
    + the reverse of a regular language is always regular.

---
Tags: formal-grammars
---


# Question
Title: Is there an adress in the hard disk for each virtual adress?
Is it so that for each virtual adress there exists an adress in the hard disk? But the hard disk can be larger than the virtual memory?

EDIT: Or can some virtual adresses always map to physical, and some map to hard drive which then is loaded to physical adresses?

# Answer
> 3 votes
In a typical modern operating system, a page frame of RAM can essentially be one of four things:

* Free. Unallocated. Available for use at any time.
* Used by the operating system for its own internal purposes. An OS has data structures, and they need to live somewhere. Page tables might also fall under this general heading.
* A page that represents part of a memory-mapped file. As well as files memory-mapped by user programs, the the text and read-only data of running programs are invariably the executable file memory-mapped. The other main example is buffer cache, where the OS keeps commonly-used data from secondary storage around if it looks like it might be needed.
* "Anonymous memory" (this is the Unix term), which essentially means memory allocated by user programs. The reason why it's called "anonymous memory" is that it's memory that doesn't have a "name", in the sense of a file on disk. Anonymous memory includes user heap-allocated memory, call stacks, and memory shared between processes.

We'll ignore the first two for the moment, because they probably aren't relevant to your question, and just look at the last two.

If the page frame of memory represents part of a file, then it needs to be kept in sync with the copy in secondary storage. If it is a read-only mapping (which is the case for program text), then this is trivial.

If the OS needs more free page frames, and it determines that some piece of read-only file mapping is a good candidate for ejection, it can just be removed from everyone's virtual memory mapping and then freed. If it's read-write, then it may need to be written first, if it's a dirty copy.

If the page frame is anonymous memory, then there is no "file" that it is a copy of. However, all modern operating systems have support for *swap space*, where secondary storage can be used to store anonymous memory in a place other than RAM.

Some older operating systems (e.g. 4.3BSD) did essentially the same thing with anonymous memory as it did with memory-mapped files. All allocated memory was a copy, or cache, of swap space. This meant that you needed at least as much secondary storage dedicated to swap as you had RAM. At some point in the late 80s to mid 90s, this tradeoff made a lot of sense.

Modern operating systems don't do this anymore, and can handle having less swap than RAM, including no swap at all. An operating system may still internally pretend that anonymous memory is kind of a memory-mapped page from a kind of pseudo-device called "swap", but the way its managed is different.

**EDIT**

OK, so that's the perspective of RAM. Now let's talk about the perspective of virtual memory.

Virtual memory is typically organised as a bunch of *segments*. A segment is a contiguous collection of pages which represent a contiguous region of a virtual memory "object". Different operating systems have a different idea about what a virtual memory object can be, but this *usually* means either a file, or anonymous memory.

If a user program tries to access a page which is not part of a segment, then this is what Unix famously calls a segmentation violation.

If a user program tries to access a page which *is* part of a segment, then this is a valid operation. (Assuming that the access itself is valid; you can't write to a read-only segment, for example.)

However, within a segment, a page may or may not be "valid", in the sense that its entry in the CPU's page tables currently points to a page frame of RAM. When a user program tries to access it, this causes a page fault, which traps to the operating system so it can intervene.

In the case of anonymous memory, there are lots of reasons why a page might not be valid:

* When memory is allocated by a program, the OS sets up a segment of anonymous memory, but it does *not* have to be mapped to actual RAM yet, and this can be desirable for speed. It is sufficient that enough memory (whether RAM or swap) to satisfy the allocation *exists*. All modern operating systems let user programs control this.
* The page may be swapped out. In this case, the OS will suspend the thread and read it in.
* The page may be copy-on-write. A page might be shared in such a way that if you only ever read it, you can safely share that copy, but writing to it must force a private copy to be made. I'll give a common example in a moment.
* The OS might just want to do it for its own housekeeping purposes. See this previous answer for some examples of when this might occur.

**NOTE** What follows is an explanation of one of the more common uses of copy-on-write memory. This doesn't really answer your question, but I'm including it because you might find it helpful, but feel free to skip or skim.

The use is in program executables. I'm going to go into a bit of detail as to how executable files are understood by a modern virtual memory system to make this somewhat self-contained, but if you already know this part, skip down to "read-write data".

A modern executable file (e.g. ELF, PE/COFF) is typically arranged as a bunch of segments. A typical layout is the following segments in roughly this order:

* "Text", which is executable code. This segment should be mapped as read-only and executable.
* "Read only data", which is data that the user programs shouldn't modify. This typically includes data structures generated by the compiler for its own purposes (e.g. data structures to implement virtual calls, exception handling, static initialisation, etc), or truly read-only data such as static strings. This segment should be mapped as read-only and not executable.
* "Read-write data", which is data that is initialised but user programs can write to. This segment should be mapped as read-write, not executable, but also copy-on-write. Why copy-on-write? Because writing to that data should not modify the executable file that you're running!
* "BSS", is static data that should be initialised to zero bytes and therefore doesn't need to take up any space in the executable file itself. This should be mapped as anonymous zero-fill memory.

When you run a program, this is how the operating system sets up a new virtual address space: it maps the segments from the executable in whatever way the executable requests.

By the way, the term "BSS" deserves some explanation. It was a pseudo-operation implemented on a particular assembler for the IBM 704 at some point in the mid-1950s, and it stood for "block starting symbol". By a series of historical accidents, the term has stuck and lives on today. Peter van der Linden suggested that "Better Save Space" might be a more suitable mnemonic.

# Answer
> 0 votes
The mapping process is highly dynamic. Every process utilizes some part(s) of its virtual address space, which can be mapped to RAM or to disk. Mapping tables are used to establish the connection and are constantly adjusted to optimize memory accessibility (the most "active" pages should reside in RAM).

On 32 bits OSes, the maximum address space would be 4 GB per process, much smaller than current hard disks (typically 1 TB). On 64 bits OSs, the virtual size is much larger than any available hardware, but this limit is never approached.

---
Tags: memory-management, virtual-memory
---


title: Another Game Theory Problem

text:
# Question
Title: Another Game Theory Problem
We have an array of integers of length N(even). A and B play a game where A selects a number followed by B without replacement until the array becomes empty(Both A and B select N/2 elements each). The goal is for A to have a sum (of the N/2 elements A chooses) which is (i) even, (ii) odd. In both cases, B plays against A and both players play optimally. We have to find who wins in (i) and (ii), given the array and N. How to go about solving this? I tried to build a pattern up from small values of N=2,4,6,.. but couldn't deduce anything substantial. Can anyone have a go at it, and explain how to go about solving such kinds of problems?

# Answer
As mentioned in the comments, this can be solved by dynamic programming. I'm only handling one of the two games, as the other is symmetric. (They can be solved using mutual recursion.)

Your array can be represented, via modulo 2, as simply the number of odd numbers $n\_\text{odd}$ and the number of even numbers $n\_\text{even}$.

Similarly, the state of each player can be taken modulo 2, so $\text{state}\_A \in \\{0,1\\}$ and similarly for $\text{state}\_B$.

Thus, the problem boils down to determine $\text{Winner}(\text{turn}, n\_\text{even}, n\_\text{odd}, \text{state}\_A, \text{state}\_B)$.

Now, clearly $\text{Winner}(\text{turn}, 0, 0, \text{state}\_A, \text{state}\_B)$ is completely determined by looking at $\text{state}\_A$, i.e., $A$ wins if and only if $\text{state}\_A = 1$.

Then we can recurse and find that $\text{Winner}(\text{turn}, n\_\text{even}, n\_\text{odd}, \text{state}\_A, \text{state}\_B)$ is

* $\text{Winner}(! \text{turn}, n\_\text{even} - 1, n\_\text{odd}, \text{state}\_A, \text{state}\_B)$
* **or** $\text{Winner}(! \text{turn}, n\_\text{even}, n\_\text{odd} - 1, \left( \text{state}\_A + \left\[ \text{it is $A$s turn} \right\] \right) \mod 2, \text{state}\_B)$

It can be observed that in this case, we don't even use $\text{state}\_B$, and can simplify it by removing it.

Using dynamic programming or recursion with memoization this runs in linear time $O\left( \left| \text{array} \right|\right)$.
> 1 votes

---
Tags: algorithms, time-complexity, data-structures, dynamic-programming, game-theory
---


# Question
Title: What problems of procedural programming does OOP solve in practice?
I have studied the book "C++ Demystified". Now I have started to read *"Object-Oriented Programming in Turbo C++ first edition (1st edition)"* by Robert Lafore. I do not have any knowledge of programming which is beyond these books. This book might be outdated because it's 20 years old. I do have the latest edition, I am using the old because I like it, mainly I am just studying the basic concepts of OOP used in C++ through the first edition of Lafore's book.

Lafore's book emphasizes that "OOP" is only useful for *larger* and *complex* programs. It is said in every OOP book (also in Lafore's book) that procedural paradigm is prone to errors e.g. the global data as easily vulnerable by the functions. It is said that programmer can make *honest* errors in procedural languages e.g. by making a function that accidentally corrupts the data.

Honestly speaking I am posting my question because I am not grasping the explaination given in this book: Object-Oriented Programming in C++ (4th Edition) I am not grasping these statements written in Lafore's book:

> Object-oriented programming was developed because limitations were discovered in earlier approaches to programming.... As programs grow ever larger and more complex, even the structured programming approach begins to show signs of strain... ....Analyzing the reasons for these failures reveals that there are weaknesses in the procedural paradigm itself. No matter how well the structured programming approach is implemented, large programs become excessively complex.... ...There are two related problems. First, functions have unrestricted access to global data. Second, unrelated functions and data, the basis of the procedural paradigm, provide a poor model of the real world...

I have studied the book "dysmystified C++" by Jeff Kent, I like this book very much, in this book mostly procedural programming is explained. I do not understand why procedural(structured) programming is weak!

Lafore's book explains the concept very nicely with some good examples. Also I have grasped an intuition by reading Lafore's book that OOP is better than procedural programming but I am curious to know how exactly in practice procedural programming is weaker than OOP.

I want to see myself what are the practical problems that one would face in procedural programming, how the OOP will make the programming easier. I think I will got my answer just by reading Lafore's book contemplatively but I want to see with my own eyes the problems in the procedural code, I want to see how the OOP style code of a program removes the foregoing errors that would happen if the same program were to be written using procedural paradigm.

There are many features of OOP and I understand it is not possible for someone to explain me how all these features removes the foregoing errors that would generate by writing the code in procedural style.

So, here is my question:

> Which limitations of procedural programming does OOP address and how does it effectively remove these limitations in practice?

In particular, are there examples for programs which are hard to design using the procedural paradigm but are easily designed using OOP?

<sup>P.S: Cross posted from: https://stackoverflow.com/q/22510004/3429430 </sup>

# Answer
In a procedural language you can't necessarily express restrictions that are required to prove that the caller is using a module in a supported fashion. In the absence of a compiler checkable restriction, you have to write documentation and hope that it is followed, and use unit tests to demonstrate intended uses.

Declaring Types is the most obvious declarative restriction (ie: "prove that x is a float"). Forcing data mutations to pass through a function known to be designed for that data is another. Protocol enforcement (method invoke ordering) is another partially supported restriction ie: "constructor -\> othermethods\* -\> destructor".

There are also a real benefits (and a few drawbacks) when the compiler knows about the pattern. Static typing with polymorphic types are a bit of a problem when you emulate data encapsulation from a procedural language. For example:

the type x1 is a subtype of x, t1 is a subtype of t

This is one way to encapsulate data in a procedural language to have a type t with methods f and g, and a subclass t1 that does likewise:

t\_f(t, x, y, z, ...), t\_g(t, x, y, ...) t1\_f(t1, x, y, z, ...)

In order to use this code as it is, you have to do a type check and switch on type of t before deciding the kind of f you will invoke. You could work around it like this:

type t { d : data f : function g : function }

So that you invoke t.f(x,y,z) instead, where a typecheck and switch to find the method is now replaced with just having each instance store method pointers explicitly. Now if you have a huge number of functions per type, this is a wasteful representation. You could then would use another strategy like having t point to a variable m which contains all of the member functions. If this feature is part of the language, then you can let the compiler figure out how to deal with making an efficient representation of this pattern.

But data encapsulation is recognition that mutable state is bad. The object oriented solution is to hide it behind methods. Ideally, all of the methods in an object would have a well defined calling order (ie: constructor -\> open -\> \[read | write\] -\> close -\> destruct); which is sometimes called a 'protocol' (research: "Microsoft Singularity"). But beyond construct and destruct, these requirements are generally not part of the type system - or well documented. In this sense, objects are concurrent instances of state machines that are transitioned by method calls; such that you might have multiple instances and use them in an arbitrarily interleaved fashion.

But in recognizing that mutable shared state is bad, it can be noted that object orientation can create a concurrency problem because the object data structure is a mutable state that many objects have a reference to. Most object oriented languages execute on the thread of the caller, which means that there are race conditions in the method invocations; let alone in non-atomic sequences of function calls. As an alternative, every object could get async messages in a queue and service them all on the object's thread (with its private methods), and respond to the caller by sending it messages.

Compare Java method calls in a multi-threaded context with Erlang processes sending messages (that only reference immutable values) to each other.

Unrestricted Object Orientation in combination with parallelism is a problem due to locking. There are techniques ranging from Software Transactional Memory (ie: ACID transactions on in memory object similar to databases) to using a "share memory by communicating (immutable data)" (functional programming hybrid) approach.

In my opinion, Object Orientation literature focuses FAR too much on inheritance and not enough on protocol (checkable method invocation ordering, preconditions, postconditions, etc.). The input that an object consumes should usually have a well defined grammar, expressible as a type.
> 10 votes

# Answer
A bit of history is in order, I think.

The era from the mid-1960s to the mid-1970s is known today as the "software crisis". I can't put it better than Dijkstra in his Turing award lecture from 1972:

> The major cause of the software crisis is that the machines have become several orders of magnitude more powerful! To put it quite bluntly: as long as there were no machines, programming was no problem at all; when we had a few weak computers, programming became a mild problem, and now we have gigantic computers, programming has become an equally gigantic problem.

This was the time of the first 32-bit computers, the first true multiprocessors and the first embedded computers, and it was clear to researchers that these were going to be important for programming in the future. It was a time in history when customer demand outpaced programmer capability for the first time.

Unsurprisingly, it was a remarkably fertile time in programming research. Before the mid-1960s, we did have LISP and AP/L, but the "main" languages were fundamentally procedural: FORTRAN, ALGOL, COBOL, PL/I and so on. From the mid 1960s to the mid 1970s, we got Logo, Pascal, C, Forth, Smalltalk, Prolog, ML, and Modula, and that's not counting DSLs like SQL and its predecessors.

It was also a time in history when many of the key techniques for *implementing* programming languages were being developed. In this period we got LR parsing, dataflow analysis, common subexpression elimination, and the first recognition that certain compiler problems (e.g. register allocation) were NP-hard, and trying to tackle them as such.

This is the context in which OOP came about. So the early-1970s answer to your question of what problems OOP solves in practice, the first answer is that it appeared to solve many of the problems (both contemporary and anticipated) that were facing programmers in that period of history. However, this is not the time when OO became mainstream. We'll get to that soon enough.

When Alan Kay coined the term "object oriented", the picture that he had in mind was that software systems would be structured like biological system. You would have something like individual cells ("objects") which interact with each other by sending something analogous to chemical signals ("messages"). You couldn't (or, at least, wouldn't) peer inside a cell; you would only interact with it via the signalling paths. Moreover, you could have more than one of each kind of cell if you needed to.

You can see that there are a few important themes here: the concept of a well-defined signalling protocol (in modern terminology, an interface), the concept of hiding implementation from the outside (in modern terminology, privacy), and the concept of having multiple "things" of the same type hanging around at the same time (in modern terminology, instantiation).

One thing you may note is missing, and that's inheritance, and there's a reason for this.

Object-oriented programming is an abstract notion, and the abstract notion can be implemented in different ways in different programming languages. The abstract concept of a "method", for example, could be implemented in C using function pointers, and in C++ using member functions, and in Smalltalk using methods (which should be unsurprising, since Smalltalk implements the abstract concept pretty much directly). This is what people mean when they point out (quite rightly) that you can "do" OOP in (almost) any language.

Inheritance, on the other hand, is a concrete programming language feature. Inheritance can be useful for implementing OOP systems. Or at least, this was the case until the early 1990s.

The time from the mid-1980s to the mid-1990s was also a time in history when things were changing. During this time, we had the rise of the cheap, ubiquitous 32-bit computer, so businesses and many homes could afford to put a computer that was almost as powerful as the lowest-end mainframes of the day on every desk. It was also the heyday of This was also the era of the rise of the modern GUI, and the networked operating system.

It was in this context that Object Oriented Analysis and Design arose.

The influence of OOAD, the work of the "three Amigos" (Booch, Rumbar and Jacobson) and others (e.g. the Shlaer–Mellor method, responsibility-driven design, etc), can't be understated. It is the reason why most of the new languages that have been developed since the early 1990s (at least, most of the ones you've heard of) have Simula-style objects.

So the 1990s answer to your question is that it supports the best (at the time) solution for domain-oriented analysis and design methodology.

Since then, because we had a hammer, we applied OOP to pretty much every problem that came up since. OOAD and the object model that it used encouraged and enabled agile and test-driven development, cluster and other distributed systems, and so on.

Modern GUIs and any operating systems that was designed in the last 20 years tends to provide its services as objects, so any new practical programming language needs, at the very least, a way to bind to the systems that we use today.

So the modern answer is: It solves the problem of interfacing to the modern world. The modern world is built on OOP for the same reason that the world of 1880 was built on steam: we understand it, we can control it, and it does the job well enough.

That's not to say that research stops here, of course, but it does strongly indicate that any new technology will need OO as a limiting case. You don't have to be OO, but you can't be fundamentally incompatible with it.
> 9 votes

# Answer
**Procedural/functional programming is in no way weaker than OOP**, even without going into Turing arguments (my language has Turing power and can do anything another will do), which do not mean much. **Actually, object oriented techniques were first experimented in languages that did not have them built-in.** In this sense **OO programming is only a specific style of procedural programming**. But **it helps enforcing specific disciplines, such as modularity, abstraction and information hiding** that are essential for program understandability and maintenance.

Some programming paradigms evolve from theoretical vision of computation. A language like Lisp evolved from lambda-calculus and the idea of meta-circularity of languages (similar to reflexivity in natural language). Horn clauses fathered Prolog and constraint programming. The Algol family also owes to lambda-calculus, but without built-in reflexivity.

Lisp is an interesting example, as it has been the testbed of much programming language innovation, that is traceable to its double genetic heritage.

However languages then evolve, often under new names. A major factor of evolution is programming practice. Users identify programming practices that improve properties of programs such as readability, maintainability, provability of correctness. Then they try to add to the languages features or constraints that will support and sometimes enforces these practices so as to improve the quality of programs.

What this means is that **these practices are already possible in older programming language, but it takes understanding and discipline to use them.** Incorporating them into new languages as primary concepts with specific syntax makes these practices easier to use and to readily understand, particularly for the less sophisticated users (i.e., the vast majority). It also makes life a bit easier for the sophisticated users.

In some way, it is to language design what a subprogram/function/procedure is to a program. Once the useful concept is identified, it is given a name (possibly) and a syntax, so that it can be readily used in all programs developed with that language. And when successful, it will be incorporated in future languages too.

**Example: recreating object orientation**

I now try to illustrate that on an example (which could certainly be further polished, given time). The purpose of the example is not to show that an object oriented program can be written in procedural programming style, possibly at the expense of lisibility and maintainability. I will rather try to show that **some languages without OO facilities can actually use higher order functions and data structure to actually create the means to mimic effectively Object Orientation**, in order to benefit from its qualities regarding program organization, **including modularity, abstraction and information hiding**.

As I said, Lisp was the testbed of much language evolution, including the OO paradigm (though what could be considered the first OO language was Simula 67, in the Algol family). Lisp is very simple, and the code for its basic interpreter is less than a page. But you can do OO programming in Lisp. All you need is higher order functions.

I will not use the esoteric Lisp syntax, but rather pseudo-code, to simplify the presentation. And I will consider a simple essential problem: **information hiding** and **modularity**. Defining a class of objects while preventing the user from accessing (most of) the implementation.

Suppose I want to create a class called vector, representing 2-dimensional vectors, with methods including: vector addition, vector size, and parallelism.

```
function vectorrec () {
  function createrec(x,y) { return [x,y] }
  function xcoordrec(v) { return v[0] }
  function ycoordrec(v) { return v[1] }
  function plusrec (u,v) { return [u[0]+v[0], u[1]+v[1]] }
  function sizerec(v) { return sqrt(v[0]*v[0]+v[1]*v[1]) }
  function parallelrec(u,v) { return u[0]*v[1]==u[1]*v[0]] }
  return [createrec, xcoordrec, ycoordrec, plusrec, sizerec, parallelrec]
  }

```

Then I can assign the created vector to actual function names to be used.

\[vector, xcoord, ycoord, vplus, vsize, vparallel\]= vectorclass ()

Why be so complicated? Because I can define in the function vectorrec intermediary constructs that I do not want to be visible to the rest of the program, so as to preserve modularity.

We can make another collection in polar coordinates

```
function vectorpol () {
  ...
  function pluspol (u,v) { ... }
  function sizepol (v) { return v[0] }
  ...
  return [createpol, xcoordpol, ycoordpol, pluspol, sizepol, parallelpol]
  }

```

But I may want to use indifferently both implementations. One way to do it is to add a type component to all values an define all the above function in the same environment: Then I can define each of the returned functions so that it will first test the type of coordinates, then apply the specific function for it.

```
function vector () {
    ...
    function plusrec (u,v) { ... }
    ...
    function pluspol (u,v) { ... }
    ...
    function plus (u,v) { if u[2]='rec' and v[2]='rec'
                            then return plusrec (u,v) ... }

    return [ ..., plus, ...]
    }

```

What have I gained: the specific functions remain invisible (because of of local identifiers scoping), and the rest of the program can only use the most abstract ones returned by the call to vectorclass.

One objection is that I could directly define each of the abstract functions in the program, and leave inside the definition of the coordinate-type dependent functions. Then would be hidden as well. That is true, but then the code for each coordinate-type would be cut in small pieces spread over the program, which is less redable and maintainable.

Actually, i do not even need to give them a name, and I could just keep the as anonymous functional values in a data structure indexed by the type and a string representing the function name. This structure being local to the function vector would be invisible from the rest of the program.

To simplify the use, instead of returning a list of function, I can return a single function called apply taking as argument an explicitly type value and a string, and apply the function with the proper type and name. This looks very much like calling a method for an OO class.

I will stop here, in this reconstruction of an object oriented facility.

What I tried to do is to show that it is not too hard to build usable object orientation in a sufficiently powerful language, including inheritance and other such features. Metacircularity of the interpreter can help, but mostly on a syntactic level, which still is far from negligible.

The first users of object orientation did experiment the concepts that way. And that is generally true of many improvements to programming languages. Of course, theoretical analysis also has a role and helped understand or refine these concepts.

But the idea that languages that do not have OO features are doomed to fail in some projects is simply unwarranted. If need be, they can mimic the implementation of these features quite effectively. Many languages have the syntactic and semantic power to do object orientation quite effectively, even when it is not built-in. And that is more than a Turing argument.

**OOP does not address limitations of other languages, but it supports or enforces programming methodologies** that helps write better program, thus helping less experienced users to follow good practices that more advanced programmers heve been using and developping without that support.

I believe a good book to understand all this might be **Abelson & Sussman: structure and interpretation of computer programs**.
> 8 votes

# Answer
None, really. OOP doesn't really solve a problem, strictly speaking; there's nothing you can do with an object-oriented system that you couldn't do with a non object-oriented system- indeed, there's nothing you can do with either that couldn't be done with a Turing machine. It all turns into machine code eventually, and ASM is certainly not object-oriented.

What the OOP paradigm does for you is it makes it easier to organize variables and functions, and allows you to move them around together more easily.

Say I want to write a card game in Python. How would I represent the cards?

If I didn't know about OOP, I might do it this way:

```
cards=["1S","2S","3S","4S","5S","6S","7S","8S","9S","10S","JS","QS","KS","1H","2H",...,"10C","JC","QC","KC"]

```

I'd probably write some code to generate those cards instead of just writing them out by hand, but you get the point. "1S" represents the 1 of Spades, "JD" represents the Jack of Diamonds, and so on. I'd also need a code for the Joker, but we'll just pretend there's no Joker for now.

Now when I want to shuffle the deck, I need only "shuffle" the list. Then, to take a card off the top of the deck, I pop the top entry off of the list, giving me the string. Simple.

Now if I want to figure out which card I'm working with for the purposes of displaying it to the player, I'd need a function like this:

```
def card_code_to_name(code):
    suit=code[1]

    if suit=="S":
        suit="Spades"
    elif suit=="H"
        suit="Hearts"
    elif suit=="D"
        suit="Diamonds"
    elif suit=="C"
        suit="Clubs"

    value=code[0]

    if value=="J":
        value="Jack"
    elif value="Q":
        value="Queen"
    elif value="K"
        value="King"

    return value+" of "+suit

```

A little big, long, and inefficient, but it works (and is very unpythonic, but that's beside the point here).

Now what if I want cards to be able to move around the screen? I have to store their position somehow. I could add it on to the end of their card code, but that might be a little unwieldy. Instead, let's make another list of where each card is:

```
cardpositions=( (1,1), (2,1), (3,1) ...)

```

Then I write my code so that the index of each card's position in the list is the same as the index of the card itself in the deck.

Or at least it should be. Unless I make a mistake. Which I very well might, because my code is going to have to be rather complex to handle this setup. When I want to shuffle the cards, I have to shuffle the positions in the same order. What happens if I take a card out of the deck entirely? I'll have to take its position out as well, and put it somewhere else.

And what if I want to store even more information about the cards? What if I want to store whether each card is flipped? What if I want a physics engine of some kind, and need to know cards' velocity as well? I'll need another list entirely to store the graphics for each card! And for all of these data points, I'll need separate code to keep them all organized properly so each card maps somehow to all its data!

Now let's try this the OOP way.

Instead of a list of codes, let's define a Card class and build a list of Card objects from it.

```
class Card:

    def __init__(self,value,suit,pos,sprite,flipped=False):
        self.value=value
        self.suit=suit
        self.pos=pos
        self.sprite=sprite
        self.flipped=flipped

    def __str__(self):
        return self.value+" of "+self.suit

    def flip(self):
        if self.flipped:
            self.flipped=False
            self.sprite=load_card_sprite(value, suit)
        else:
            self.flipped=True
            self.sprite=load_card_back_sprite()

deck=[]
for suit in ("Spades","Hearts","Diamonds","Clubs"):
    for value in ("1","2","3","4","5","6","7","8","9","10","Jack","Queen","King"):
        sprite=load_card_sprite(value, suit)
        thecard=Card(value,suit,(0,0),sprite)
        deck.append(thecard)

```

Now, suddenly, everything is much simpler. If I want to move the card, I don't have to figure out where it is in the deck, then use that to get its position out of the array of positions. I just have to say `thecard.pos=newpos`. When I take the card out of the main deck list, I don't have to have to make a new list to store all that other data; when the card object moves, all its properties move with it. And if I want a card that behaves differently when its flipped, I don't have to modify the flipping function in my main code so that it detects these cards and does that different behavior; I just have to subclass Card and modify the flip() function on the subclass.

But nothing I did there couldn't have been done without OO. It's just that with an object-oriented language, the language is doing a lot of the work of keeping things together for you, meaning you have much less chance to make mistakes, and your code is shorter and easier to read and write.

Or, to summarize even more, OO allows you to write simpler-seeming programs that do the same work as more complex programs by hiding a lot of the common complexities of handling data behind a veil of abstraction.
> 6 votes

# Answer
Having written embedded C for a few years managing things like devices, serial ports, and communications packets between the serial ports, network ports, and servers; I found myself, a trained electrical engineer with limited procedural programming experience, **concocting my own abstractions from the hardware which ended up manifesting in what I later realized are what normal people call 'Object Oriented Programming'.**

When I moved over to the server side I was exposed to a factory that set up the object representation of each device in the memory on instantiation. I didn't understand the words or what was happening at first-- I just knew I went to the file named thus and such and wrote code. Later, I found myself, again, finally recognizing the value of the OOP.

**I, personally, think this is the only way to teach object orientation.** I had an Intro to OOP (Java) class my freshman year and it was completely over my head. OOP descriptions built on **classifying kitten-\>cat-\>mammal-\>alive-\>thing or leaf-\>branch-\>tree-\>garden are, in my humble opinion, absolutely ridiculous methodologies because no one is ever going to try to solve those problems,** if you could even call them problems...

I think it's easier to answer your question if you look at it in **less absolute terms-- not 'what does it solve', but more from a perspective of 'here's a problem, and here's how it makes it easier'.** In my particular serial ports case, we had a bunch of compile-time #ifdefs that added and removed code that statically opened and closed serial ports. The port open functions were called all over the place, and could be located anywhere in the 100k lines of OS code we had, and the IDE didn't grey out what wasn't defined-- you had to track that down manually, and carry it in your head. Inevitably you could **have several tasks trying to open a given serial port expecting their device on the other end, and then none of the code you just wrote works, and you can't figure out why.**

The abstraction was, although still in C, a serial port 'class' (well, just a structure datatype) that we had an array of-- one for each serial port-- and **instead of having \[the DMA equivalent in serial ports\] "OpenSerialPortA" "SetBaudRate" etc. functions called directly on the hardware from the task, we called a helper function that you passed all the communications parameters (baud, parity, etc.) to,** which first checked the structure array to see if that port had already been opened-- if so, by which task, which it would tell you as a debug printf, so that you could immediately jump to the section of code you needed to disable-- and if not, it then proceeded to set all the parameters via their HAL assembly functions, and finally opened the port.

**Of course, there are dangers to OOP, too.** When I'd finally cleaned up that codebase and made everything neat and clean-- writing new drivers for that product line was finally down a calculable, predictable science, my manager EOL'd the product specifically because it was one less project he would need to manage, and he was borderline removable middle-management. Which took a lot out of me / I found very discouraging so I quit my job. LOL.
> 3 votes

# Answer
there are many *claims* and *intentions* about what/where OOP programming has an advantage over procedural programming including by its inventors and users. but merely because a technology was *designed* for a certain purpose by its designers does not guarantee that it will *succeed* in those objectives. this is a key understanding in the field of software engineering dating to Brooks famous essay "No silver bullet" which is still relevant despite the OOP coding revolution. (see also the Gartner Hype Cycle for new technologies.)

many who have used both also have *opinions* from anecdotal experience, and this has some value, but it is known in many scientific studies that self-reported analysis can be inaccurate. there does seem to be little *quantitative analysis* of these differences or if there is, it is not cited so much. it is somewhat amazing how many computer *scientists* speak authoritatively on certain topics central to their field yet do not actually quote *scientific research* to support their views and do not realize they are actually passing on *conventional wisdom in their field* (albeit *widespread*).

since this is a *science* site/forum, here is a brief attempt to put the numerous *opinions* on firmer footing and *quantify* the actual difference. there may be other studies & hope others might point them out if they hear of any. *(zen question: if there really is a major difference, and so much massive effort in the commercial software engineering field and elsewhere has been applied/invested toward realizing it, why should scientific evidence of this be so difficult to come by? shouldnt there be some classic, highly-cited reference in the field that definitively quantifies the difference?)*

this paper employs experimental/quantitative/*scientific* analysis & specifically supports that comprehension by novice programmers is improved with OOP coding methods *in some cases but was inconclusive in other cases* (relative to program sizes). note this is only *one* of the many/major claims about OOP superiority being advanced in other answers & by OOP advocates. the study was possibly measuring a psychological element known as "cognitive load/overhead" wrt coding comprehension.

* A comparison of the comprehension of object-oriented and procedural programs by novice programmers Interacting with Computers. Susan Wiedenbeck, Vennila Ramalingam, Suseela Sarasamma, Cynthia L Corritore (1999)

> This paper reports on two experiments comparing mental representations and program comprehension by novices in the object-oriented and procedural styles. The subjects were novice programmers enrolled in a second course in programming which taught either the object-oriented or the procedural paradigm. The first experiment compared the mental representations and comprehension of short programs written in the procedural and object-oriented styles. The second experiment extended the study to a larger program incorporating more advanced language features. For the short programs there was no significant difference between the two groups with respect to the total number of questions answered correctly, but the object-oriented subjects were superior to the procedural subjects at answering questions about program function. This suggests that function information was more readily available in their mental representations of the programs and supports an argument that the object-oriented notation highlights function at the level of the individual class. For the long program a corresponding effect was not found. The comprehension of procedural subjects was superior to object-oriented subjects on all types of question. The difficulties experienced by the object-oriented subjects in answering questions in a larger program suggest that they faced problems in marshaling information and drawing inferences from it. We suggest that this result may be related to a longer learning curve for novices of the object-oriented style, as well as to features of the OO style and the particular OO language notation.

see also:
> 2 votes

# Answer
I disagree with seeing an opposition between procedural programming and object-oriented programming.

Procedural programming means that the program describes explicitly (and implicitly by means of loops and recursion) the sequence of operations to be performed. That form of programming heavily relies on program *states* represented by the successive values of the work variables. This is by contrast with pure functional programming where the order of computation is irrelevant and the computational process is stateless.

Object-oriented programming is a way to structure data by forming logical entities and enforcing "access rights" meant to protect the programmer against himself, so to say. This is an evolution of structured programming towards larger systems.

Procedural as well as non-procedural programming can be object-oriented or not.
> 2 votes

# Answer
To be concise Object Oriented Programming addresses the data security issues present in procedural programming. This is done by using the concept of encapsulating the data, allowing only the legitimate classes to inherit the data. Access modifiers facilitate achieving this goal. Hope that helps.:)
> 1 votes

# Answer
Be careful. Read the classic by R. King "My Cat is Object-Oriented" in "Object-oriented Concepts, Databases, and Applications" (Kim and Lochovsky, eds) (ACM, 1989). "Object oriented" has become more a buzz-word than a clearcut concept.

Besides, there are many variations on the theme, with little in common. There are prototype based languages (inheritance is from objects, there are no classes as such) and class based languages. There are languages which allow multiple inheritance, others which don't. Some languages have an idea like Java's interfaces (can be taken as a form of watered down multiple inheritance). There is the idea of mixins. Inheritance can be rather strict (as in C++, can't really change what you get in a subclass), or very liberally handled (in Perl the subclass can redefine almost everything). Some languages have a single root for inheritance (typically called Object, with default behaviour), others allow the programmer to create multiple trees. Some languages insist that "everything is an object", others handle objects and non-objects, some (like Java) have "most are objects, but these few types here aren't". Some languages insist on strict encapsulation of state in objects, others make it optional (C++' private, protected, public), others don't have encapsulation at all. If you squint at a language like Scheme from the right angle, you see OOP built in without any special effort (can define functions that return functions that encapsulate some local state).
> 1 votes

---
Tags: programming-languages, object-oriented, programming-paradigms
---


# Question
Title: Is a problem in NP if it runs in P time on a NDTM, verifiable in P on a DTM, but solution doesn’t halt on a DTM?
Say there was a decision problem which was solved optimally in polynomial time on a non-deterministic Turing machine, and verifiable in polynomial time on a deterministic TM, but would not halt when being solved optimally on a DTM. Would that problem be in NP, or is solution decidability on both NDTMs and DTMs a requirement?

# Answer
> 1 votes
As DTMs and NDTMs are equivalent, every problem that can be decided by a NDTM can also be decided by a DTM.

Heres a informal explanation for NP: A deterministic turing machine can run a nonterministic program (in NP) by attempting all of the possible paths of a nondeterministic turing machine successively either until it reaches an accepting state or has found every path to be denying. If the NDTM decides the problem to be true, there must be a path of length $O(n^k)$ to an accepting state. Otherwise, every path must end in $O(n^k)$ steps. The number of possible branches at each step is limited by the alphabet size which I'll call $q$. Therefore, there are at most $q^{O(n^k)}$ possible paths if the NDTM creates q branches at each of the $O(n^k)$ steps. This is a finite number which is why all the paths can be attempted by a DTM in finite number of steps. Therefore, a decision problem which can be decided on a NDTM can also be decided on a DTM.

---
Tags: complexity-theory, turing-machines, computability, np, halting-problem
---


title: Reducing BB to SMR and vice versa

text:
# Question
Title: Reducing BB to SMR and vice versa
It's often said that State Machine Replication and Byzantine broadcast are equivalent (e.g., the abstract of \[1\]), but it seems only obvious how to reduce SMR to BB. I.e., give BB one can construct an SMR by rotating the leader.

What does it even mean to reduce BB to SMR then? In SMR, there are clients and servers, but in BB there are only servers.

\[1\] https://drops.dagstuhl.de/opus/volltexte/2018/9796/pdf/LIPIcs-DISC-2018-7.pdf

# Answer
> 1 votes
It means that, given an implementation of SMR, you can implement BB. For this, have each node in BB play both the role of an SMR server and the role of an SMR client. Then use the client interface to emulate broadcasting and delivering messages.

---
Tags: distributed-systems
---


# Question
Title: When applying pumping lemma for regular languages to prove that a given language is non regular, do we show that pumping fails for all $i$ or one $i$?
***Pumping Lemma for Regular Languages***

Pumping Lemma for Regular Languages: If $A$ is a regular language, then there is a number $p$ ( the pumping length ) where if $s$ is any string in $A$ of length atleast $p$, then $s$ may be divided into three pieces, $s=xy$, satisfying the following conditions:

1. $for \ each \ i\>=xy^iz∈A$,
2. $|y|\>0$, and
3. $|xy|\<=p$

When using pumping lemma to prove that a given language is "non regular, we do the following steps:

1. Assume $L$ is regular, hence $L$ exhibits pumping lemma for regular langauges
2. Since $L$ is regular, it will have $p$ and if we choose a string that is atleast as long as $p$
3. Then that string will have decompositions satisfying all the three conditions of the lemma
4. This is where we obtain a contradiction by showing that the string will fail to satisfy condition 1 of the lemma and hence our assumption is false and the language is not regular

My question is: Do we need to show that the string fails to satisfy condition 1 for one $i$ or all $i\>=0$. I do understand that we need to show that string fails to satisfy for one $i$ but should the proof be able to extrapolate for any value of $i\>=0$?

My understanding is that: In order to have a strong valid contradiction, we need to show that our string choice and pumping of the string fails for all values of $i$ according to condition 1

But when we say "for all values of $i\>=0$", we know that for $i=1$, the pumped string does exist in the language( because we chose that string ), and sometimes it also exists in the langauge for $i=0$, so are these sort of exceptions?

# Answer
> 2 votes
Assuming the rest of the proof is formulated correctly, showing that every $xyz$ division fails to be pumped for at least a single value of $i$ is sufficient. To see this, let's inspect the formal definition of the pumping lemma, which states the following: (note the highlighted quantifiers)

For *every* regular language $L$, there *exists* an integer $p$ such that for *every* string $s \in L$ with $|s| \geq p$ there *exists* a way to partition $s$ into $xyz$ such that

* $|xy| \leq p$
* $|y| \> 0$
* $xy^iz \in L$ for *every* $i \geq 0$

We use the lemma in proofs by contradiction: hence, for all points where the lemma states that something must hold "for every" value of something, a single counter-example will be enough. Conversely, when the lemma states that something "exists", you must establish that no satisfactory value exists.

Usually, the way this is done is assuming a valid value of $p$ exists, then selecting a suitable string as we are allowed to, then examining all possible ways to partition the string and establish they fail at least one of the three conditions – usually ruling out the two first conditions, them being more trivial, and then showing each of the remaining possibilities violates the third condition for at least one value of $i$.

## Intuition

Remember the pumping lemma is based on the behavior of the automaton recognizing the regular languages, a DFA. The intuition of the lemma is that for an automaton and its language $L$, a sufficiently long string must visit one of the states twice or more when being recognized. This means there is a loop in the string's "execution trace" on the DFA, and therefore a sequence of symbols $y$ that can be repeated to re-trace the loop arbitrarily many times, end in the same state, and continue from there to the accepting state.

Imagine the state that's the start and end of the loop. Since no many how times we pass through the loop, we end up in this state, it follows that we could also execute the loop *zero* times and cut out the portion of the string that caused our string to loop even once, and not change the acceptance of our string. For any string of a regular language, we could indeed do this – but if this results in a string that no longer belongs in our language, it proves that such a loop did not exist in the first place, confirming the language's non-regularity.

---
Tags: pumping-lemma
---


# Question
Title: Why these languages are closed under union or concatenation?
This is a question in my text book that I cannot understand the solution provided for that:

In each case below, give a simple descreption of the smallest set of languages that contains all the "basic" languages $\varnothing$,$\\{\Lambda\\}$, and $\\{\sigma\\}$ (for every $\sigma \in \Sigma$) and is closed under the specefied operation.

1. Union
2. Concatenation
3. Union and Concatentation

Here are my questions about the above excersise:

* What is the meaning of

> smallest set of languages that contains all the "basic" languages $\varnothing$,$\\{\Lambda\\}$, and $\\{\sigma\\}$ (for every $\sigma \in \Sigma$)

In other words, What are the sets that I should find for the answers?

* The solution manual suggested "Every zero or one member subset of $\\{x | x\in\Sigma^\*\\}$" for closure under concatenation

I don't understand why it is closed under union? suppose $\\{\sigma\_1\\}$. Is $\sigma\_1\sigma\_1$ closed under that? No.

# Answer
We have sets in different levels here: sets of words (languages) and sets of languages. To avoid confusion I will call the latter a "family" of languages.

A family of languages $\mathcal F$ is closed under an (binary) operation $\star$ if for we apply $\star$ to any pair of languages $K,L\in \mathcal F$ also the result $K\star L$ is in $\mathcal F$.

If we start with a set of languages and some operations, then finding the *closure* of those languages under the given operations ("the smallest family closed under") is equivalent to finding which languages can be build from the starting set using the operations.

In your question we start with "basic" languages, $\varnothing$, $\\{\Lambda\\}$, $\\{a\\}$, $\\{b\\}$ when $\Sigma =\\{a,b\\}$, and three possible sets of operations.

The answer form the manual you quote is for the operation concatenation (item 2). Using concatenation I can build new languages from the basic ones: $\\{a\\}\cdot\\{a\\} =\\{aa\\}$, and then we can repeat $\\{aa\\}\cdot\\{b\\} =\\{aab\\}$. And so on.

The observation here is that in this way we always build singleton languages, i.e., consisting of a single word. Also all singleton languages over the alphabet can be obtained by repeated concatenation.

One point of possible confusion is that the *family* of languages is closed under concatenation, not each of the resulting languages. So when $L=\\{a\\}$ and $L \in \mathcal F$ we have $L\cdot L \in \mathcal F$ so $\\{aa\\} \in \mathcal F$ but *not* $a\cdot a \in L$.
> 1 votes

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


# Question
Title: Does linear programming admit a strongly polynomial-time algorithm?
The linear programming problem: find a strongly-polynomial time algorithm which for given matrix A ∈ Rm×n and b ∈ Rm decides whether there exists x ∈ Rn with Ax ≥ b.

I know that Steve Smale's lists some of the unsolved problems in mathematics. But such a linear programming problem is it until now not-solvable ?

# Answer
> 12 votes
This problem is still open. See for example Wikipedia, which while not a dependable source in general, will probably be updated if a strongly polynomial time algorithm is ever found.

# Answer
> -2 votes
The algorithm used to solve this problem is the simplex algorithm. This is an efficient algorithm which can solve linear programs in polynomial time. The algorithm starts with an initial feasible solution to the problem and then iteratively improves it until a maximum or minimum is found. This can be done by using the following steps:

1. Construct the initial feasible solution (the initial basic solution) by solving the inequality Ax ≥ b.
2. Choose a direction vector that will increase or decrease the objective function value.
3. Calculate the new basic solution by improving the current basic solution along the chosen direction vector.
4. Repeat steps 2 and 3 until an optimal solution is found.

The complexity of the simplex algorithm is O(mn2) in time and O(mn) in space, where m and n are the dimensions of the matrix A. Therefore, it can be seen that the simplex algorithm provides an efficient, strongly-polynomial time solution to the linear programming problem.

---
Tags: algorithms, polynomial-time, linear-programming
---


title: Optimality of A* algorithm

text:
# Question
Title: Optimality of A* algorithm
In the book `Artificial Intelligence a Modern Approach 4th edition`, the author claims that the A\* algorithm is cost-optimal if the heuristic function is `admissible` (never overestimates the remaining true cost).

Additionally, if the heuristic is `consistent` (obeying the triangle inequality by using a neighboring node), the first time we reach the goal state, will be the optimal solution. Consistency can be best described by a triangle inequiality: `h(n) < c(n, a, n') + h(n')`, the heuristic of going from n to the goal h(n) is less than the sum of the actual cost of going from n to n' c(n, a, n'), and the heuristic of going from n' to the goal h(n'), where "a" denotes some action that takes the agent from n to n'.

My problem statement is to find the shortest path in terms of Euclidian distances on a 2-D grid with obstacles where the agent can move to any of the 8 available adjacent cells.

My algorithm is rather straightforward:

```
Create an object `Point` to denote a path
- It contains information such as:
    1. current location
    2. list of past moves
    3. sum of total distance travelled (g)
    4. estimated future distance (h), which is the Euclidian distance between current location and the goal.
    5. f = g + h, the function to minimize, which is also what the priority queue compares Points on

Create a priority queue and put Point into it - the queue holds the best Point we have so far in terms g + h

Create a set of tuple of (row, column) pairs to mark grids as visited

In a while loop:

 - Get a Point curr from the priority queue

 - If curr is on the goal, return its path

Otherwise for all curr's successors:
- if the successor's current location hasn't been visited:
  - put the location tuple into the visited set, and put the successor into the priority queue

```

Here is an example of a path:

Clearly, this is not the optimal solution, as the path is longer than necessary. But why?

My heuristic seems standard, but it is not finding the optimal solution, let alone have the first arrival be optimal.

While debugging, I noticed that the reason it was not finding the optimal path was because the points on the optimal path were visited by "suboptimal" paths (paths that head toward the lower right before finding a way to cross the obstacle first). And this is difficult to avoid since the Euclidian distance will guide the search toward the lower right, right out the gate, which is a suboptimal path.

Euclidian distance obviously does not overestimate the cost, hence it satisfies the definition of `admissibility`.

Furthermore, I believe the heuristic is also `consistent`, as going to any neighboring point that is not on the straight line between the current point and the goal, will form a triangle, and will obey the triangle inequality. (Perhaps consistency needs to be satisfied when n' is on the straight line between n and the goal? In that case I believe it fails because h(n) = c(n, a, n') + h(n'))

I modified the algorithm by changing the `visited` set into a map where the keys are location tuples (r, c), and values are current `f` values, and I will let a successor that is on a `visited` cell enter the queue only if it has a lower `f` value than the previous `f` value on the cell, and update the `f` value to be the current lower `f` value.

The algorithm successfully finds the path for this problem.

However, this algorithm fails for another puzzle where we're moving elements in an array based on some rules. As a result, I don't believe my understanding of A\* algorithm is correct.

Could you let me know if my heuristic of Euclidian distance is admissible or consistent, and point out any other flaws that plague my reasoning?

# Answer
what is your formula for g? From your result it looks like amount of nodes visited.

That cost function will result in more extraneous diagonals. Because going diagonally down left followed by diagonally down right has the exact same cost as going down twice.

in particular at that turnaround assuming the node just before has cumulative cost of $g$ then the square just below has cost $g+1$ the node just down right has cost $g+1.4$, when both have explored their neighbors they both touch the square under the first one. The path going straight down will have cumulative cost $g + 2$ while the path with the bent will have cost $g + 2 * 1.4$. So after updating the path straight down should be the one preserved.

However if instead you scale de diagonal distance by (some approximation of) the square root of 2 compared to the orthogonal path. Then paths that avoid the zigzag diagonal will be more favorable.
> 0 votes

---
Tags: artificial-intelligence, board-games, a-star-search
---


# Question
Title: How to determine offset bits when addressing CPU cache?
I know that the offset is based off of the line size for a cache. I have seen the example: "32-btye line size would use the last 5-bits (i.e. $2^5$) off the address as the offset into the line" but I do not understand the process used to determine this.

# Answer
If you need to address a space consisting of $2^N$ values, then you need $N$ address bits.

In your example, $2^N = 32$ and $N = 5$.
> 0 votes

# Answer
The 32 addresses mapped to the cache line could be for instance

```
0b00100000010111100101100111000000
0b00100000010111100101100111000001
0b00100000010111100101100111000010
0b00100000010111100101100111000011
0b00100000010111100101100111000100
...
0b00100000010111100101100111011101
0b00100000010111100101100111011110
0b00100000010111100101100111011111

```

Only the last five bits differ, from all zeroes to all ones.
> 0 votes

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


# Question
Title: Decide whether a flow graph has a single min-cut
The problem is whether a graph (which we represent as a flow network) has a single min-cut, or there could be multiple min cuts with the same maximum flow value, I've yet to encounter a well explained algorithm for solving this problem, let alone a complexity anaylsis or proof.

I was not able to find the exact resource of information to help me answer the problem. I'm not sure where else to search, therefore I thought asking here could perhaps help me better my understanding of the problem and the algorithms that help solving them.

# Answer
Here is a simple algorithm that determines whether a flow network $G=(V, E, c)$ with source $s$ and sink $t$ has a single min-cut or not.

1. Find a maximum flow $f$ of $G$. Let $R\_f$ be the residual network of $G$ with respect to $f$.
2. Let $X$ be the set of all nodes that are reachable from $s$ in $R\_f$.
3. Let $Y$ be the set of all nodes from which $t$ is reachable or, what is equivalent, all nodes reachable from $t$ in $R\_f$ with all direction of flow capacity reversed.
4. If $X\cup Y=V$, there is a unique minimum cut (which is $(X,Y)$). Otherwise, there are more than one minimum cut.

#### Why is the algorithm above correct?

First, we know that $(X, V\setminus X)$ is a minimum cut. By symmetry, so is $(V\setminus Y, Y)$.

Suppose $(S,T)$ is an arbitrary minimum-cut of $G$ where $s\in S$ and $t\in T$. This post tells that $X$ is contained in $S$. By symmetry, $Y$ is contained in $T$. Hence, $(S,T)$ is the unique minimum-cut iff $X\cup Y=V$.

#### Time-complexity of the algorithm

It mostly depends on the complexity of the algorithm that is used to compute a maximum flow.

It takes $O(E)$ time to compute $X$ and $Y$, given the max-flow $f$.

It takes $O(V)$ time to check whether $X=Y$.
> 3 votes

# Answer
If you're talking about a certain *residual graph*, the cut is unique, but in the flow network, there can be many (exponentially, even) minimum cuts.

Consider a simple path with $n$ vertices, each edge with capacity 1. There are $n-1$ minimum cuts, one for each edge. But in the residual graph, you will always get the unique cut being the first edge.
> 1 votes

# Answer
The idea is simply find a single min-cut $(S, T)$, then increase each one (seperately) of its crossing edges' capacity by a "tiny-tiny" $\epsilon\>0$ then run min-cut algorithm again and check if there's any difference.

If there's another (let's a single one W.L.O.G) min-cut $(S', T')$, meaning (inter alia) there exists an edge $e\in (S, T)$ such that $e\notin (S', T')$, in the algorithm - when $e$'s capacity would change $c'(e)=c(e)+\epsilon$, the min-cut algorithm would detect $(S', T')\not=(S, T)$ and therefore we can conclude there existed another min-cut.

In general, notice that if $\epsilon$ was too high we could detect a different (rather than $(S, T)$) cut although it might not be a min-cut in case that $c(S', T')\<c(S, T)+\epsilon$ \- that's why we set $\epsilon$ as small as possible, I think it's pretty obvious but still wanted to mention that.

This algorithm's time complexity is $O(E\cdot M)$ where $O(M)$ is the min-cut detection algorithm's complexity.
> 1 votes

---
Tags: algorithms, network-flow, minimum-cuts
---


# Question
Title: Understanding the Strong Exponential Time Hypothesis
Let $n$ be the number of variables in the input formula and $m$ the number of clauses. Define $s\_k = \inf\\{\delta : k\text{-SAT can be solved in } 2^{\delta n} \text{ time}\\}$. The strong exponential time hypothesis says that $\lim \limits\_{k \to \infty} s\_k=1$. I have two questions here:

1. What if the input size is very large, say, $m=\Theta(3^n)$? Simply reading the input formula needs $\omega(2^n)$ time. In this case, $\lim \limits\_{k \to \infty} s\_k$ would be larger than $1$.
2. A paper in SAT Conference 2021 says, "The strong exponential time hypothesis conjectures that the SAT problem cannot be solved in time $O^\*(c^n)$ for some constant $c\<2$." I haven't found the equivalent statement in Impagliazzo and Paturi's original paper. Why is this statement equivalent to $\lim \limits\_{k \to \infty} s\_k = 1$?

# Answer
1. That can't happen. The maximum number of distinct possible clauses is $(2n)^k = O(n^k)$, which is polynomial in $n$ (since here $k$ is fixed).
2. Here I imagine that there notation $O^\*(c^n)$ probably refers to something like $O((nL)^{O(1)} c^n)$. If you could solve SAT in $O(1.5^n)$ time, then you could solve $k$-SAT in $O(1.5^n)$ time for all $k$, thus $s\_k \le \log\_2 1.5 \< 1$ for all $k$, we cannot have $s\_k \to 1$.
> 2 votes

---
Tags: algorithms, complexity-theory, np-complete, satisfiability
---


# Question
Title: How to find tangent line on a curve of unknown function?
I have x and y values to plot the curve and I need to find a tangent line of slope 1 that intersects the curve and the point at which it intersects. I was trying to do polynomial and exponential regression to model the data (\>6000 data points) and fit the curve in R but cannot get it to work. It fits a majority of the data but not the curve and I want the function of the curve to find the derivative and tangent.

I don't completely understand the math behind the modeling but all I know is that the fit is inaccurate when I plot it against my data. Is there any way I solve this mathematically or geometrically? The curve starts slightly downwards, then slopes up gradually before it goes up exponentially

If you do a density plot, most of the values are towards the lower end of y. the values of y are right skewed. This is probably why my model doesn't fit the curved region, so would one solution be to remove multiple prior points?

# Answer
If you rotate the plot by a suitable angle that makes the tangent horizontal, your problem is recast as that of finding the minimum of the curve, which is a simple problem. For better accuracy, you can fit a parabola *on a few neighbors* of the lowest point.

Anyway, notice that your axis have widly varying ranges, so that a slope of 1 is quite dubious. Better check that.
> 1 votes

# Answer
Your approach of fitting a curve and then finding the tangent to the fitted curve seems like a sensible approach.

No fitted curve will ever exactly match all of the points. If you aren't fitting all of the data, then the family of curves doesn't fully model the distribution the data actually came from. One simple approach is to choose a window of x-values (e.g., 6000...7000) that likely contains the desired point, keep only the data in that window, and fit the best curve you can to that data.
> 0 votes

---
Tags: graphs
---


# Question
Title: Amount of ways N can be written as sum of two or more non-repeating integers
For example, 5 can be written in 2 ways:

* 4 + 1
* 3 + 2

8 can be written in 5 ways:

* 7+1
* 6+2
* 5+3
* 5+2+1
* 4+3+1

How could this be determined for any positive integer N?

# Answer
> 0 votes
This is known as the number of strict partitions. Wikipedia contains a number of results on this. You can compute the number using dynamic programming.

---
Tags: algorithms
---


# Question
Title: In Kolmogorov's $ K(s) \leq |s| + c $, why is $c$ +ve?
Kolmogorov said *"It seems natural to call a chain random if it cannot be written down in a more condensed form, i.e., if the shortest program for generating it is as long as the chain itself. "* So for example (in bits & bytes):-

$$ K(\text{a thousand zeros}) \approx \log\_2(1000) \text{bits} $$

$$ K(\text{Shakespeare's works}) \approx \text{1 MB} $$

$$ K(\text{\dev\random}) = \text{| \dev\random |} $$

The second being so as his works will compress to about a megabyte. Both of the first two examples have the Kolmogorov complexity much less than the original ('chain') itself. The last example is Kolmogorov random and thus equal to the chain length.

So why is $c$ considered positive and not negative, or zero?

---

I'm refering to the old `\dev\random` when it was truly random and not as recently crippled to `\dev\urandom`.

# Answer
> 1 votes
If we had $K(s) \le |s|-1$ (for example), then that would mean that every string can be compressed to a strictly shorter one. It is known that this is impossible: see No compression algorithm can compress all input messages?.

See also https://en.wikipedia.org/wiki/Pigeonhole\_principle#Uses\_and\_applications, https://cs.stackexchange.com/a/7533/755.

Therefore, there exists a string $s$ for which $K(s) \ge |s|$. In other words, there is no constant $c\<0$ such that $K(s) \le |s|+c$ holds for all $s$.

---
Tags: kolmogorov-complexity
---


# Question
Title: Algorithm for determining an algebraic positivity property of a multivariate polynomial
I am considering multivariate polynomials with integer coefficients that can be expressed as sums of products of terms of the form $y\_i-z\_j$ for positive integers $i$ and $j$. I am trying to find an algorithm to determine if there is a way to express them in terms of these linear factors in such a way that the terms have nonnegative coefficients. I have a conjecture that this is always true for the polynomials that I am considering, and I want to do some extensive testing of it.

For example, my program outputs the following in one case (for reasons of speed, absolutely no simplification is done intermediately; computing the coefficients is at best $\\#P$-complete even when the degree of the polynomial is $0$): $$-2 (y\_2 - z\_1) (y\_1 - z\_1) + 2 (y\_1 + y\_2 - z\_1 - z\_2) (y\_1 + y\_2 - z\_1 - z\_3) - (-(y\_2 - z\_1) (y\_1 - z\_1) + (y\_1 + y\_2 - z\_1 - z\_2) (y\_1 + y\_2 - z\_1 - z\_3))$$ This is not expressed in a positive manner, but there is cancelation you can do to get $$(y\_2-z\_1)(y\_2-z\_3)+(y\_1-z\_2)(y\_1-z\_1)+(y\_1-z\_2)(y\_2-z\_3)$$ and this would pass the test.

For context, it's considered a hopelessly difficult unsolved problem to determine whether computing the degree $0$ coefficients is in $\\#P$, though the problem is known to be in $\mathrm{GapP}^+$.

When I plug this example into Maple and call simplify, I get $$y\_1^2 + (y\_2 - z\_1 - z\_2 - z\_3)\*y\_1 + y\_2^2 + (-z\_1 - z\_2 - z\_3)\*y\_2 + (z\_2 + z\_3)\*z\_1 + z\_2\*z\_3$$ which is not really very helpful.

A conjecture that would be easier to check is that, when expanded, the polynomial has nonnegative coefficients in terms of $y\_i$ and $-z\_j$, but this is not quite the same.

I am really just looking for any algorithm at all; it doesn't have to be fast.

# Answer
Here is a semi-algorithm. I don't know if it is a good one. If your conjecture is true, it always terminates. In particular, if a solution exists, it will find it; if no solution exists, it will run forever, searching for one.

Let $p(x)$ be the original polynomial; it can be expressed in the form $$p(x) = \sum\_S \alpha\_S \prod\_{(v,w) \in S} (v-w),$$ where $S$ is a set of pairs $(v,w)$ of variables (here $v$ is some $y\_i$ and $w$ is some $z\_j$). Let $q(x)$ be the re-expressed polynomial we are trying to search for. Let $k$ be an upper bound on the number of terms in the product, which might initially be set to 2. Then the general form of the non-negative polynomial is $$q(x) = \sum\_S \beta\_S \prod\_{(v,w) \in S} (v-w),$$ where the sum is over all sets $S$ of pairs, such that $|S|\le k$. We require that $p(x)=q(x)$ and $\beta\_S \ge 0$ for all $S$. Given the $\alpha$'s, our goal is to find $\beta$'s that satisfy these conditions.

Notice that we can multiply out each product above, putting $p(x)$ into the following form:

$$p(x) = \sum\_T \delta\_T \prod\_{v \in T} v,$$

where $T$ ranges over multisets of variables. Here $\delta\_T$ can be expressed as a linear function of the $\alpha\_S$'s. Since the $\alpha$'s are given, this means we can compute each $\delta\_T$ as an explicit constant. Similarly,

$$q(x) = \sum\_T \gamma\_T \prod\_{v \in T} v,$$

where $\gamma\_T$ is a known linear function of the $\beta\_S$'s. $\gamma\_T$ is not known, but it is a linear function of the $\beta$ variables.

Finally, since we want to have $p(x) = q(x)$, this means we require $\delta\_T = \gamma\_T$ for all $T$, which means we equate the known constant $\delta\_T$ to the linear function of $\beta$'s that represents $\gamma\_T$. Also, we have the inequality $\beta\_S \ge 0$ for all $S$.

Putting it together, this gives us a system of linear equalities and inequalities on the $\beta\_S$'s. We can then use linear programming to check whether there exists a solution to this linear system. If there exists a solution, then we have found a way to express $p(x)$ in the desired form.

If there is no solution, then we can increase $k$ and try again. Repeat until we find a solution. If a solution exists, we will eventually find it. The complexity will be exponential, as there can be exponentially many $S$'s and $T$'s, but it is something that can be implemented. However, if no solution exists, this will run forever.

To test your conjecture, as a heuristic, you could set an upper bound on $k$, and then any polynomial where no solution is found up to that value of $k$ is a candidate that might violate the conjecture; and if no such candidate is found, then it increases confidence in your conjecture (but of course does not prove it).
> 2 votes

---
Tags: algorithms, polynomials, computer-algebra
---


# Question
Title: Data structure to estimate the frequency of low frequency elements
I have a file with trillions of numbers and I want to get all numbers that have a frequency `<=100`. These numbers are in text format (`UInt8`s) so I first have to parse them. As this is slower than reading the bytes to a buffer I have one thread reading the data and 80 threads processing the bytes.

I could give each thread a HashMap that keeps track of the frequencies and later merges them but this will require quite a lot of RAM. As an alternative, I thought of Count-min sketch but as this (likely) overestimates it doesn't seem to suit my purpose.

* Some overestimates are fine
* I don't care about high frequency numbers at all

Is there any data structure/idea that comes to mind to tackle this? Or are hashmaps my only way to go

---

**Edit**
The numbers come from another tool that generates any number in the `UInt64` range. The amount of numbers, as well as how many unique numbers there are will depend on the output of the other tool. For our initial dataset for example, we have 25 billion numbers, of which 22M are unique, and around 18M have a frequency `<=100`.

**Distribution of number frequency**

*Since these numbers are based on DNA sequences they won't be random and likely very skewed. For this dataset for example:*

*(Note the x-axis is log10)*

**Integer range**

*As I noted they can technically be in the whole UInt64 range. Plotting this for the dataset the numbers are quite uniformly picked along the range, here stopping at around 5e8*

So to summarize:

* numbers come from the `UInt64` range, and seem to be uniform across this range
* The frequency distribution is highly skewed. In this case 75% of the numbers only occur \<= 100

# Answer
> 1 votes
For the dataset you show in the question, all numbers are in the range between 0 to about 500 million. For this dataset, there is an easy efficient algorithm. Build an array $A$ with 500M entries, initialized to zero. Read each line one at a time; when you read the number $x$, increment $A\[x\]$. At the end, output all numbers $x$ where $A\[x\] \ge 1$ and $A\[x\]\le 100$.

How much memory will this take? Based on your plot, all frequencies will fit into a 32-bit int, so you need at most 2GB of memory to store the array.

What about threading? There is something wrong with your implementation if it takes 80 parsing threads to keep up with 1 thread that reads from disk. If you implement it right, with hand-coded C tailored for this task, I expect you should be able to parse as fast as you can read from disk. Your comments indicate that the lines are tab-separated, but it is trivial to split a line by tabs, and it is trivial to convert an integer expressed in decimal to an int. So, based on the information you given I expect that you can replace your 80 parsing threads with a single thread, with proper implementation.

If you cannot, there are other simple methods. For instance, if you really need a lot of parsing threads, you can have 1 thread to read the disk, 80 parsing threads, and 1 thread to increment the array. Each parsing thread would parse numbers, accumulate the parsed numbers into a large buffer, and when that buffer gets full, pass the buffer to the array-incrementing thread.

If you are concerned that occasionally some input line might contain a value that is larger than 500M, it is easy to accommodate this as well. You can have an array A for all numbers below 500M, and a hashmap for all larger numbers. If very few numbers are above 500M, then you'll rarely need to touch the hashmap and performance will be dominated by the time to increment the array.

# Answer
> 1 votes
With unordered data spread over such a range, cache hit rate will be very low indexing a table directly or using a hash function.
One alternative is ordering the data using an algorithm with good locality.
Merge sort has been discussed for elimination of duplicates.
With an "occurrence limit" higher than 1, one would need to keep a count with each value. Encountering the same value in more than one input sequence, add the counts (using saturating arithmetic as appropriate) and add just this merged item to the output.

---

When supplying data to multiple threads from a distribution as flat as shown, see to it that *merging frequencies* is as simple as *concatenation*:
split the value range in as many ranges as threads deemed useful.

---
Tags: algorithms, data-structures, performance
---


# Question
Title: matplotlib.widget.Slider displays but isn't active when plt.show() is called outside function that created the slider. Am I missing something?
```
###################
# create_slider() #
###################
def create_slider(self, t0, t1):

    # adjust the main plot to make room for the sliders
    plt.subplots_adjust(bottom=0.25)

    slider = Slider(
        #                   left  botm   w     h
        ax      = plt.axes([0.25, 0.1, 0.65, 0.03]),
        label   = '"t"',
        valmin  = t0,
        valmax  = t1,
        valinit = t0,
        valstep = (t1-t0)/200.0,
        color   = 'lime'
    )

    slider.on_changed(self.update)

    plt.show()

##############
# __init__() #
##############
def __init__(self, p0, p1, p2, p3, t0, t1):

    self.create_curve(p0, p1, p2, p3, t0, t1)
    self.create_unit_lines(t0)
    self.create_slider(t0, t1)
    #
    # Slider INACTIVE IF CALLED HERE VS. IN create_slider
    #
    # plt.show()

```

# Answer
Found answer under button issue. Need to maintain class reference to the slider. Replace "slider" with "self.slider" works.
> 0 votes

---
Tags: graphics
---


# Question
Title: union of NP and co-NP, closure under polynomial time reduction
Is $Union = NP\cup co-NP$ closed under polynomial-time many-one reductions?

I understand that in order to be so, for $A\in Union, A \leq\_P B $ there should exist a polynomial time computable function $f$ such that: $x\in A \implies f(x) \in B$. So the function computed for an input from $Union$ is also in $Union$. It looks like a true statement for me, however I miss a formal proof. May I ask for some directions?

# Answer
Hopefully I solved it:

let $B \in Union, A \<\_p B$, then from $ B \in NP \implies A \in NP$ and from $B \in co-NP \implies B \in co-NP$, thus $A \in Union$. So $Union$ is closed under polynomial time reductuons.
> 0 votes

---
Tags: np, polynomial-time-reductions, co-np
---


# Question
Title: Is it possible to train a neural network to solve NP-complete problems?
I'm sorry if the question is not relevant, i have tried to search for articles about it but i couldn't find satisfying answers.

I'm starting to learn about machine learning, neural networks etc ... and i was wondering if making a neural network that takes a graph as input, and output the answer of an np-complete problem (e.g. the graph is hamiltonian / the graph has independant set superior to k, and other decision problems) would work ?

I haven't heard of any np complete problems being solved like this, so i guess it does not work, are there theoretical results stating that a neural network cannot learn np-complete language or something like this ?

# Answer
To answer your question, I would to point you to the field of *computational learning theory* (CLT), which applies complexity theoretic approaches to analyse machine learning.

An important concept in CLT is *probably approximately correct* (PAC) learning: in simple terms, a problem is PAC learnable if there exists an efficient algorithm which learns the data using a polynomial number of samples from the underlying distribution of the problem with an (polynomially small) error of $\epsilon$ and (polynomially small) failure probability $\delta$.

Unfortunately, there is a big disconnect between results in CLT and results in applied machine learning, so you are unlikely to find result proving or disproving the learnability of NP complete problems using deep neural networks as it is still an active area to research.

Here are some resources to computational learning theory:

https://www.cs.ox.ac.uk/people/varun.kanade/teaching/CLT-HT2018/lectures/lecture01.pdf

Section 3 defines and gradually introduces the concept of PAC learning

* Section 5.1 of these notes show how 3-COLOURABILITY can be phrased in the PAC learning framework:
* In Section 5 as well, the notes show how "3-TERM-DNF is not efficiently PAC learnable (take II) unless RP = NP"
> 3 votes

# Answer
"Neural networks" are just regular (randomized) algorithms. The same restrictions apply: If $P \ne NP$, they won't be able to solve NP-complete problems in polynomial time either. They are attractive ways to find approximate solutions, but again, there are problems for which even getting a decent approximation is still (the analogue in search problems to the decision problems') NP-complete. Again, no way around that unless $P = NP$ (it which case the exercise is pointless anyway).
> 1 votes

# Answer
So it would be a PROOF that P=NP, isn't it? IMHO worth checking and researching... Big prize ahead!
> -3 votes

---
Tags: np-complete, machine-learning
---


# Question
Title: Probability of comparison of two nodes after insertion in AVL tree
Suppose $K=a\_1\<a\_2\<\dots\<a\_n$ be a set $n$ distinct keys that inserted into an AVL tree $T$. The probability of any permutation of the order of insertion of the sequence $K$ is equal. Also we first insert $a\_{40}$ into $T$, how I can find the probability, $a\_4$ be ancestor of $a\_9$ or $a\_9$ be ancestor of $a\_4$?

Anyone can give me some hint? I try to find some hint about that.

# Answer
> 0 votes
When inserting into an AVL tree, the existing nodes are not compared with each other, so the probability of comparing $a\_4$ and $a\_9$ with each other when inserting $a\_{40}$ is $0$.

On the other hand, the probability of comparing $a\_{n}$ to both $a\_4$ and $a\_9$ is derivable asymptotically by considering how many comparisons one makes when doing an insert, which is $O(\lg n)$, making the total probability $O((\lg n/n)^2)$, which is very small - $o(1/n)$.

However, that's true only asymptotically. To get the result for $n = 40$, you have to analyze the expected number of comparisons when inserting into a tree of size $39$. That probably requires some heavier math.

To see how this can change, consider the probability of comparing $a\_3$ to both $a\_1$ and $a\_2$ when inserting $a\_3$, which I think is $2/3$.

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


# Question
Title: Ordered open-end knapsack problem optimised for minimum weight range
Given a fixed number of infinite-capacity containers and a list of items of varying weights, how can I best place the items into the containers **preserving their original order** in a way that minimises the difference between the heaviest and lightest containers?

For example, given 3 containers and 10 items with weights \[19, 7, 12, 1, 9, 11, 3, 17, 10, 8\] the optimal solution is:

1. 19, 7
2. 12, 1, 9, 11, 3
3. 17, 10, 8

Such that the difference between the heaviest and lightest containers is (12 + 1 + 9 + 11 + 3) - (19 + 7) = 10.

My current algorithm is to:

* calculate the target bin weight as the sum of all item weights divided by the number of containers
* if adding the next item to the active container would bring its weight closer to the target then add it to the active container
* otherwise move to the next container and add the item
* repeat until all items have been placed in containers

This algorithm works well for lists of items of similar weights but doesn't find the best solution when there are one or more very heavy items.

For example, with 4 containers and item weights \[3, 8, 2, 4, 8, 2, 27, 20\] the above algorithm gives:

* 3, 8, 2, 4
* 8, 2
* 27
* 20

With a weight range of 27 - (8 + 2) = 17.

However the optimal solution is in fact:

* 3, 8, 2
* 4, 8, 2
* 27
* 20

With a weight range of 27 - (3 + 8 + 2) = 14.

How can I find the optimal solution?

# Answer
> 1 votes
This can be solved with dynamic programming. Let $W\[1,\dots,n\]$ denote the weights of the items. Fix a value of $\ell$. Define the array $A\[\cdot,\cdot\]$ as

$A\[i,j\] = $ the smallest value of $h$ such that there is an allocation of the first $i$ items to the first $j$ containers where the lightest container is $\ge \ell$ and the heaviest container is $\le h$

We have the recursive relation:

$$A\[i,j\] = \min\\{\max(A\[i\_0,j-1\],W\[i\_0+1\]+\dots+W\[i\]) \mid W\[i\_0+1\]+\dots+W\[i\] \ge \ell\\}$$

This can be used to build a dynamic programming algorithm, which fills in entries of $A\[i,j\]$ in order of increasing $j$. Then $A\[n,m\]-\ell$ contains the smallest possible difference between heaviest and lightest containers, assuming the lightest container is $\ell$. Finally, we can repeat this algorithm once per value of $\ell$ (for each $\ell$ in the range $1,2,3,\dots,(W\[1\]+\dots+W\[n\])/m)$).

The overall running time will be $O(n^2 S)$, where $S=W\[1\]+\dots+W\[n\]$ is the sum of the weights. This might be fast enough if the sum of the weights is not too large. If the sum of weights is very large, you might need a different approach.

---
Tags: algorithms, optimization, knapsack-problems, packing
---