# Question
Title: What is the range of a universal turing machine (partial function)?
I take the definition from Computability and Complexity Theory by Steven Homer and Alan L. Selman, 2011.

In their book they said that the domain of a computably enumerable (c.e.) function (f) can be the range of another partial function (p). In particular, the partial function can be the universal Turing machine. The universal Turing machine takes a machine description and input word (e, x) and effectively maps the domain (S) of the c.e. function (f).

My question is : what is the range of the universal Turing machine - shouldn't it just accept or reject ? then how could it map the domain of the c.e. function (f)....

# Answer
When you use Turing machines to compute functions, they typically write down the result on their tape and halt.

Note that recognising words from a language can be thought of as computing a function from $\Sigma^\* \rightarrow \\{0,1\\}$, so you don't have to accept via declaring some state accepting.

How exactly your TM works depends on the definition you use and you have considerable freedom to use something that fits your problem domain. It's all about communicating with your readers.
> 2 votes

---
Tags: complexity-theory, computability, turing-machines, undecidability
---


# Question
Title: How do Hard Drives Send and Recieve Data?
Ok. I know this is probably a commonly asked question. Before you refer me to a site or answer this yourself, I ask for you to please read this through. I have been into computers and electronics for quite a while. I have a pretty good understanding of electronics, and would like to become a computer hardware engineer eventually. For quite a while now, I have been searching for an answer to my question: How to hard drives send and recieve data, and in general, how do they work? Every site I find, simply explains the basics, of which I already am quite familiar with.

An example of what I am trying to figure out: Suppose you want to save a very small file (less than 1KB for simplicity) to a hard drive. Is there a site that explains exactly what information is exchanged between the hard drive and the rest of the computer? I would like to understand what is sent, and when it is sent ( down to ones and zeros ). I would eventually like to know enough information that, in theory, I could build a small storage device compatible with a modern computer. The more information, the better.

# Answer
As it stands, this isn't a Computer Science question. Actually, it's several questions, some of which could be phrased of as computer science questions.

Disk-like devices (these days we'd include flash memory) do not understand the concept of a "file" or "directory". You can think of a disk as a big array of fixed-size blocks. The two basic operations are "read a block" and "write a block". Files are an abstraction on top of this implemented by the operating system.

All of this is explained in any operating systems course. But if you just want the short version, I recommend Maurice Bach's classic book The Design of the UNIX Operating System. It doesn't reflect modern operating systems or filesystems that well, but it will give you a good idea about what operating systems do and what they expect of a disk device. If that wasn't enough for you, Practical File System Design by Dominic Giampaolo is a whole book which gives an in-depth look at a more modern filesystem design.

The hardware that sits between there and the disk is a topic all by itself. On a modern system, disks can be connected to a computer using a variety of different hardware connection (e.g. USB, SATA, SCSI), and a modern operating system needs to both be able to talk to the host controller for this bus, but also be able to tell what is attached to the bus. For some busses (e.g. USB) there may be a complex topology for the operating system to discover; the disk may be connected via a hub, for example.

The final link in the chain is what lies between the bus and the storage medium itself, and this is presumably what you're interested in.

My suggestion, if hardware engineering is what you're most interested in, is to hook a simple computer (e.g. a microcontroller) up to a simple storage device (e.g. MMC) and see what you can do. You will learn a lot this way.

As a final comment, there is a book by Jan Axelson called *USB Mass Storage: Designing and Programming Devices and Embedded Hosts*. I can't recommend it because I haven't read it, but it looks like the sort of thing you might want to know. If I'm reading the table of contents correctly, it looks like it gives you everything you need to know to build a USB flash drive. That sounds like a fun project to me.
> 2 votes

# Answer
What data is exchanged between "computer" and "hard drive" is specified by the protocol that they're talking. For example SATA is a popular protocol. In general you should be able to look up the bus protocol for any connector in your computer.

It is probably also helpful to check out some open source operating system's code for talking to hard drives.
> 1 votes

---
Tags: memory-hardware, memory-access
---


# Question
Title: The sorting problem for partially ordered sets
I have two questions about sorting for posets, one easy and one hard:

Easy: Suppose we have a set of objects and a partial order. Given any two objects such that $a \leq b$, we want to delete $b$ from the set. Is there a sub-quadratic time algorithm that can accomplish this, perhaps for some suitable data structure?

Hard: suppose we actually want to sort the list by putting it into some suitable data structure (such as a directed graph). Does there exist a nice data structure leading to a sub-quadratic time sorting?

The second is the natural generalization of the sorting problem to posets. The first is an easier variant that will suffice for this application.

# Answer
Take a worst case scenario.

The set is built out of pairs of objects $a\_i, b\_i$ where $a\_i \< b\_i$ and there exists no order between $a\_i \< b\_j$ when $i\neq j$.

This means that to know whether you can delete an element you need to check it against *every other element* resulting in a quadratic general case.

The best data structure to avoid that is where each node has a direct reference to which nodes it is greater or equal to. But to build that you need a quadratic algorithm.
> 1 votes

---
Tags: algorithms, complexity-theory, sorting, partial-order, order-theory
---


# Question
Title: How do compilers implement symbolic (rather than textual) insertion?
From a programming language designer's point of view, how is "symbolic" insertion implemented as opposed to "textual" insertion using pre-processor macros?

I understand the basics of how "textual" insertion works in C and C++. That is, the pre-processor might transform:

```
#include "person.hpp"

class employee
{
    person p;
};

```

into:

```
#ifndef PERSON_HPP
#define PERSON_HPP

class person
{
public:
    uint32_t height_;
};

#endif // PERSON_HPP

class employee
{
    person p;
};

```

This is required because the size of the employee class can only be determined if the compiler knows the size of the person class. One disadvantage of this is slow compilation speed. A program consisting of a single source code file `main.cpp` might have thousands of lines inserted into it by the pre-processor before compilation begins. This can be avoided in some cases by forward declaring the class and using pointers. The employee class cannot use the person class until it is defined, (which is why the implementation file will still include "person.h") but it does remove header file dependencies and increases compilation speed.

```
class person;

class employee
{
    person* p;
};

```

For a language like Java, on the other hand, no textual insertion is required. Instead, "symbolic" insertion is performed. So the file below would not be "fleshed out" with the definitions of the dependent software modules.

```
import com.example.library.person;

class employee {
    private person p;
};

```

I can't wrap my head around how the compiler accomplishes this. I imagine that because Java is garbage collected, it doesn't need to know the size before it is declared, in much the same way as classes can be forward declared in C++ without including the entire file. But how does the compiler know that `p->some_function_that_does_not_exist(23)` is valid?

This question was originally asked on stack overflow.

# Answer
> 2 votes
The Java compiler reads the files you listed with the import statements to see the definitions. For historical reasons C compiler doesn't do this and prefers to get everything in one file, hence the preprocessor.

In the end, there is no magic. If you want to make sure at compiletime that the functions that you're calling exist, then the compiler has to see the definitions. Dynamic languages like Python don't do this check, so they have to see less of the code.

# Answer
> 2 votes
> I can't wrap my head around how the compiler accomplishes this.

The compiler processes the source files in multiple passes.

In the first pass, it gathers information about types and their members, effectively producing the information that would be contained in a header file in C++.

In the second pass, it looks at method bodies and uses information from the first pass to figure out what the members mean and whether the code is valid.

> I imagine that because Java is garbage collected, it doesn't need to know the size before it is declared

Kind of. When you write `private person p;` in Java, that declares a *reference* (basically a fancy word for "a pointer that you can't use pointer arithmetic on") to `person`, so the compiler doesn't need to know what fields `person` contains to figure out the size of the containing class.

---
Tags: programming-languages, compilers, java, c++
---


title: Another way to solve SAT. Was it known?

text:
# Question
Title: Another way to solve SAT. Was it known?
*Theorem*. If and only if SAT instance $\varphi$ is satisfiable, there is a way to negate variables in $\varphi$ and get $\varphi'$ where all clauses have at least one positive literal.

Also we can change word 'negative' by 'positive'.

For example, let we have an instance $(x\lor y\lor\overline z)\land(\overline y\lor\overline t)\land(x\lor z\lor t)\land(\overline y\lor z\lor\overline t)\land(x\lor\overline t)$

We have monotone clauses $(\overline y\lor\overline t)$ and $(x\lor z\lor t)$.

$(\overline y\lor\overline t)$ is shorter, let's modify it.

Negating $y$ gives us a formula that has no negative clauses. So, $x\overline yzt$ is positive assignment.

Let us take unsatisfiable formula $(x\lor y)\land(x\lor\overline y)\land(\overline x\lor \overline z)\land(z\lor t)\land(z\lor\overline t)$.

There is one negative clause $(\overline x\lor \overline z)$.

Flipping $x$ or $z$ will not reduce the amount of negative clauses. In fact both renamings $xy$ and $zt$ do not allow to get rid of negative or positive clauses.

In fact, this can be seen as generalization for renamable Horn SAT.

We can try to implement an algorithm that will try to reduce the amount of these clauses. Is such way to solve SAT is known?

# Answer
> 4 votes
You haven't really specified an algorithm, but a similar idea is used by random walk algorithms for SAT such as Schöning's algorithm (see for example Giurgiu's Master thesis or one of the many online lecture notes on the topic).

The same approach is also used in the heuristic algorithm WalkSAT which has recently been used to prove an algorithmic version of the Lovász local lemma.

---
Tags: satisfiability, sat-solvers
---


# Question
Title: Is $\{ w \in L : wx \in L, \textrm{for some } x \neq \epsilon\}$ a CFG language if $L$ is CFG?
Let $L$ be CFG. Is $\\{ w \in L : wx \in L, \textrm{for some } x \neq \epsilon\\}$ also CFG?

# Answer
> 3 votes
Consider the language $$ L = \\{ a^n b^m c^nd : n,m \geq 0 \\} \cup \\{ a^n b^m c^m d^2 : n,m \geq 0 \\}. $$ Then $\\{ w \in L : wx \in L \text{ for some } x \neq \epsilon \\} \cap a^\* b^\* c^\* d = \\{ a^n b^n c^n d : n \geq 0 \\}$.

Here is a similar example, showing that if $L$ is context-free then $L \cap L \Sigma^+$ is not necessarily context-free: $$ L = \\{ a^n b^n : n \geq 0 \\} \cup \\{ a^n b^m c^m : n,m \geq 0 \\}. $$ Indeed, in this case $L \cap L\Sigma^+ = \\{ a^n b^n c^n : n \geq 0 \\}$.

The situation is likely different for *deterministic* context-free languages.

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


title: Canonical form for a graph

text:
# Question
Title: Canonical form for a graph
I am trying to find a description for canonical form (labelling) for a graph. Specifically, how do we arrive at canonical form for a given graph?

# Answer
> 7 votes
*Graph canonization* is a a procedure that takes a graph $G$ and returns an isomorphic graph $C(G)$, we the promise that $C(G) = C(H)$ iff $G$ and $H$ are isomorphic. We call $C$ a *canonical form*.

One possible canonical form is the lexicographically smallest adjacency matrix. Given an ordering of the vertices, we can serialize the adjacency matrix as a binary string. Given a graph $G$, we choose the ordering leading to the lexicographically smallest such string, and then order the graph accordingly to form $C(G)$. It is not hard to check that this is a canonical form.

The algorithm, as stated, has exponential complexity, so isn't practical. There might be faster ways to compute this canonical form, or they might be other canonical forms which are easier to compute. Notice, however, that canonical forms can be used to solve graph isomorphism, and so finding an efficiently computable canonical form is hard and might be impossible (depending on the meaning of *efficient*).

It is still possible that there is an easily computable canonical form that works for most graphs, just like graph isomorphism is easy for most graphs. For more on this topic, see this question, and particularly the survey by McKay and Piperno mentioned in my answer there.

---
Tags: algorithms, graphs
---


# Question
Title: Algorithm to find individual, closed groups of lines in a large set of connected lines
I'm currently trying to write an algorithm that can find individual groups of connected lines within a larger set of lines. The images below should explain this a bit more clearly.

In the first image you can see a set of lines. What I'm trying to do is split those lines into 3 groups, as seen in the second image. The red and green groups share a line.

I can assume that each line has a start and an end coordinate, and each line can belong to one or more groups.

I'm currently trying to write a recursive function that follows each line until it reaches an end point with one or more lines it can follow. At this point the function recalls itself until it's followed the lines back round to the split point. However this is proving unsuccessful.

The output of this example, as shown in the second image, should be 3 separate groups of lines, stored in a list. I'm currently using c#, however I should be able to use a suitable algorithm in any language, including pseudocode. I know there must be an algorithm that can achieve this, however I cannot seem to work it out or find it online.

# Answer
Assuming you essentially want to partition the 2D space into pieces using the given lines **and border** where

* no two pieces overlap
* all pieces sum to the original space
* all the pieces primitive i.e. **can not be split further**

Consequently, there is a nice property that each line that actually border a polygon will be between exactly 2 polygons. This is more apparent when thinking about the notions of dual graph of plane graph

Note the outer partition piece formed with the border of the whole picture.

# Algorithm

## Initialise

Each line has 2 pointer to be pointed to the partition it borders (red dot). These pointer are initialised to empty. Our algorithm terminates when all of these pointers are non empty.

## Main

1. Pick a line with at least one still empty partition pointer.
2. Walk along the adjacent edge that makes the **least** angle from the **side** of the line that still has a free pointer. (do remember the properties of vector's cross product and dot product. These will be your tools in calculating the angle and determining the side.)
3. \[If there is no adjacent line to walk at all, you need to mark the current line as not being part of any polygon and backtrack\]
4. Once you complete a cyclic walk, update all the "sides" used and point them to a newly created "partition" object.
5. Repeat step (1) until all lines has been assigned 2 pointers to its bordering partition. (except if that line is marked as not a part of any polygon or is the border of whole picture.)
> 3 votes

# Answer
Here is an idea - something to start with.

A good first step is to use BFS/DFS (on the edges) to find the connected components of your diagram - in your case there are two. From now on we consider a single connected component.

Given a component and an edge, find a way to determine which direction is "in" and which is "out". For example, if you shoot a ray in the perpendicular direction, "in" is the direction which hits an odd number of edges on its way to infinity. Run flood fill in this direction. This should give you one shape. Find another edge which is not adjacent to a shape (if any), and repeat. Eventually you will have found all shapes.
> 0 votes

---
Tags: algorithms, graphs
---


title: Why NFA is called Non-deterministic?

text:
# Question
Title: Why NFA is called Non-deterministic?
I have this \[kind of funny\] question in mind. Why is the non-deterministic finite automaton called **non-deterministic** while we define the transitions for inputs. Well, even though there are **multiple and epsilon** transitions, **they are defined** which means that the machine is deterministic for those transitions. Which means it's deterministic.

# Answer
> 23 votes
"Deterministic" means "if you put the system in the same situation twice, it is guaranteed to make the same choice both times".

"Non-deterministic" means "not deterministic", or in other words, "if you put the system in the same situation twice, it might or might not make the same choice both times".

A non-deterministic finite automaton (NFA) can have multiple transitions out of a state. This means there are multiple options for what it could do in that situation. It is not forced to always choose the same one; on one input, it might choose the first transition, and on another input it might choose the same transition.

Here you can think of "situation" as "what state the NFA is in, together with what symbol is being read next from the input". Even when both of those are the same, a NFA still might have multiple matching transitions that can be taken out of that state, and it can choose arbitrarily which one to take. In contrast, a DFA only has one matching transition that can be taken in that situation, so it has no choice -- it will always follow the same transition whenever it is in that situation.

# Answer
> 9 votes
Take this automaton for instance, it's an NFA and it accepts the string $0110$. To be more pedantic, it accepts strings that end in $10$.

To see that we just need to check whether it reaches an accept state.

\begin{align\*} q\_0 & \rightarrow 1\\ q\_0 & \rightarrow 0\\ \color{red}{q\_1} &\rightarrow \color{red}{1}\\ q\_2 &\rightarrow 0\\ \end{align\*}

Now in the red line there was another possibility, that is when reading the second $1$ I could stay in $q\_0$ and then stay in $q\_0$ when reading the last $0$. Automata have no memory, so there's no way to 'save' a state and check later if my string ends with $10$, it's like this NFA it's making a guess whether the string ends with $10$ before branching to an acceptable state. The nondeterminism here is making lots of choices and always making the right ones.

It's easier to construct an NFA than it is to construct an DFA, the good thing is that both are equivalent.

# Answer
> 5 votes
The transition function of an NFA specifies the allowed transitions at any point in time. There could be more than one option, and the NFA chooses a transition *nondeterministically* with the goal of eventually reaching an accepting state.

Perhaps you should wait until you learn about nondeterministic Turing machines. Nondeterminism means the same thing in both cases.

# Answer
> 4 votes
Start off with a Finite Automaton. It has states and acceptance states and transitions.

Now, give it more than one trasition rule of of each state, and say that it accepts if *there exists* a set of transition rules *picked after the fact* that lead to the acceptance state given an input string.

Once you have your input string, there is a fixed set of concrete transitions and states it goes through (one at a time) to accept that string. But which transitions it picks are only chosen *at the end of the string*. While the string is being read, which path to take is not determined.

It is non-deterministic. It gets to pick its path through the graph after you give it the entire problem, not as it reads the input.

---

Now, we formalize this differently than this thought experiment, but this gives you motivation why it got that name.

This explains how it got the name in the first place. Yes, you can model NDFA in a completely deterministic way, but **names are sticky**. Once you have called something Bob, there is a communication cost to renaming it to something else as nobody knows what you are talking about when you call it Alice.

# Answer
> 1 votes
From wikipedia, the best way to think about this is to start with deterministic finite state machines(DFA). For a DFA, each transition is *uniquely* determined by the current state and the input symbol to be processed. Nondeterministic finite state machines (NFA) are simply what you get when you relax this determinism rule to permit transitions to not be uniquely defined. It's what you get when you remove the determinisim rule from DFAs.

# Answer
> 1 votes
NFA and DFA are both used to (amongst other things) recognize certain strings.

Non-deterministic finite automaton works like it had an influence on its decisions - it can "choose" to follow a path, or not.

On the image above, when we are dealing with string "00111", notice that when encountering the first "1", there are two possible ways to follow. One can stay at "p" or go to "q". If the automata was to move to the "q", it wouldn't accept the string(since there are no edges coming out of the "q"). But the string can be accepted by this automata by going to the "q" with only the last 1, while staying at "p" for everything else(and that's what's happening).

NFA makes it look like the automata "knew" what is ahead, and chooses accordingly.

Of course it doesn't. DFA and NFA are equivalent in terms of power(you can reduce NFA to DFA and make DFA (probably) simpler with use of NFA), but NFA is useful, because it has allows to define the same languages as DFA while keeping the graphs much shorter and more readable.

There is nothing random in there. The non-deterministic part puts emphasis on the fact that there is some "choice" to take, but the truth is that the automata doesn't take any decisions.

# Answer
> 0 votes
Well here is the mix of some content from book \[Introduction to Formal Languages and Automata by Peter Linz 4E\] and my understanding.

Consider a game-playing program where the machine needs to make the decision for the next move \[say for tic-tac-toe\]. Since there are multiple moves possible, we deterministically choose each move and evaluate the move and opt for the best one. Even though the selection process was deterministic and there were many possible moves, the final move made was a single one and was chose as best move while hiding all the tried move-computations from the opponent. \[Here we assume that the evaluation process of each possible move was hidden from the opponent\].

Hence only one choice was made and opponent is given a illusion such that the move was non-deterministic.

Well if you are not convinced yet by asking that the best move was the product of some deterministic calculations then you must consider the machine which makes perfectly random moves (may be machine looses but it's an NFA).

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


# Question
Title: How does CPU actually retrieve data from memory when you call a variable in a programming language?
As I have understood from all the internet sources I can get to, when you declare and initialize a variable in java, you are allocating this data, say an 8-byte float, in a particular memory cell in the RAM, with the address specified as the row and column number. Now, suppose I want to access this memory location and print the float out. As a programmer, I will clearly not write the binary representation of the memory location of this float for the CPU to process; rather, I will call the variable name I declared before. When this variable name got transformed into binary code and sent to the CPU, how does CPU know what memory location this variable is referencing to? I mean, for that to work, doesn't the memory location of the variable has to be stored directly on the CPU? Because if not, you will have to store the the memory location of the float at some memory cell as well; in other words, when you call the variable, you have to first get from the RAM what memory address is the variable representing and then use that information to go to the RAM to retrieve the float. However, for the CPU to get to the memory address of the memory address of the memory address of the float, it still either has to store it directly on the CPU or has to store it in the RAM, and the same story goes one recursively. What is really happening when you need to call a variable? How to the CPU know the memory address associated with the variable in the first place without referring to the RAM? Because if the CPU is referring to the RAM, then that means it has already gotten the memory address f

# Answer
> 8 votes
Your assumption that the variable is sent to the CPU is wrong. Every program must be compiled to some machine code (or it will be interpreted, but it roughly comes down to the same thing). The idea of compilation is to translate the human-readable code to a series of bits, which can then be read by the processor. In order to get an idea of what those series of bits do, you could also take a look at assembly which is actually not much more than an encoding of the instruction set of a CPU.

Now the trick is that the compiler builds a so-called symbol table where it keeps track of all variables that have been defined by the programmer(s). Once it knows about all of the variables, it also knows how much RAM it needs (not considering dynamic allocation of course) and thus can allocate a certain space in memory. All variables are then mapped to some piece of memory or if the compiler is smart enough, it might even map certain (temporary) variables only to registers on the CPU to save some memory (not completely sure about that last thing though). The compiler thus creates a series of bits where each variable is represented by the correct register- or memory-address and the cpu does not bother/know about any variables.

For dynamically allocated memory things get a bit trickier, but eventually it comes down to memory addresses being stored in variables which are handled by the compiler again.

I hope I understood your question correctly and did not spread too much nonsense (if I did, please correct me) as I am not an authority whatsoever in this region, but that is roughly my view on these things.

# Answer
> 2 votes
The cpu actually doesn't call the variable, but the address of the RAM. The random-access-memory has vertical (column) and transverse (row) addresses. The cpu sends the address values of vertical or transverse or both fields to a register, and the register will drive that values to the I/O variable data. But a "high-level" programmer doesn't want to remember those addresses. So the simple solution is use the compiler of another computer to function vary the name with the refer address. You're confusing between high-level reality and low-level reality logic.

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


# Question
Title: If P=NP, which two languages are NOT NP-complete?
In my last exam this question got asked and i just cant find a clear answer:

If P=NP, which two languages are NOT NP-complete?

So I assume there are two special languages, but which?

Thanks in advance

# Answer
> 3 votes
For $L$ to be $NP$-complete, every problem in $NP$ must be reducible to an instance of $L$ in polynomial time. If $P=NP$, you can solve any potential problem in $NP$ directly within polynomial time, and then just branch and output an instance known to be either in or not in $L$ (in constant time), to prove that $L$ is $NP$-complete. However, two languages lack the required pair of instances - the empty language fails to have an instance that accepts, and its complement fails to have an instance that rejects. If at least one problem in $NP$ has some instances that accept and some instances that reject, then you can't reduce it to either of these two languages, and therefore they are not $NP$-complete. To wrap up the proof, you'd need to give an example of such a problem and the instances, which should be fairly trivial.

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


# Question
Title: Why is the language of TMs that have some quadratic time bound undecidable?
The language in question is $L = \\{M : M \text{ is a Turing machine that halts in } 100n^2 + 200 \text{ time}\\}$.

# Attempt 1

Suppose $L$ is decidable. Let $M\_1, M\_2, \ldots$ be the Turing machines in $L$. Now construct a new Turing machine $M$ that works as follows:

* on input of length $n$ run $M\_n$ and output the opposite answer

On the one hand, $M \in L$ since it halts in the appropriate time. On the other hand, $M \notin L$ because it is different from every machine in $L$. Therefore $L$ is undecidable.

Is this correct?

Something that bothers me: I think I am only using the fact that there are countably many Turing machines; I never used the fact that there is some TM that decides $L$.

# Attempt 2

As suggested, here's a new Turing machine $M'$:

```
M'(M,x,1^n):
    if M is not a valid Turing machine then halt
    otherwise
        run M(x) for 100n^2+200 steps
        if it halts, then run forever
        otherwise halt

```

Ask oracle: does $M'(M,x, 1^n)$ halt on all inputs within $100n^2+200$ steps?

If yes, then $M$ doesn't halt on input $x$.

If no, then some input causes it to loop forever, which means $M$ halted on $x$ in a certain amount of time.

This would allow us to decide the halting problem, which we know is undecidable.

Is this correct? If so, I still think of the details are a bit fuzzy... For example, it's a bit unclear to me as to what happens with the inputs $M$ and $x$ are very large...

# Answer
> 3 votes
The fundamental reason for this is because your function $100n^2+200$ is $\Omega(n)$. Additionally, **this result holds for any function $f\in\Omega(n)$**.

Your problem is that you can't just "run $M\_n$". It's possible to describe a turing machine that runs a specific machine, but to have the turing machine depend on the input requires that you actually *compute* the machine you're using. This is actually equivalent to the negation of what you are trying to prove, and additionally makes $M$ take longer so that it won't halt in the correct amount of time in the case that $M\_n$ does even if you had an algorithm to find $M\_n$.

Assuming you are using $M$ in your second attempt as a general TM rather than the one for attempt one, then the problem here is the same (except it's caused by the fact that the machine has to use some extra time to compute which step it's one rather than compute the machine it will simulate). Normally, this problem wouldn't come into play if you do $O(f(n))$ analysis because your new TM $M'$ would still run within a constant time factor of the old one, but in your problem you have to be a bit more clever.

If you know a bit of complexity theory, you can do that by using the linear speedup theorem, which basically says that given a TM which runs in at least linear time $f(n)$ you can create one with a constant factor $r\>0$ as small as you'd like that runs in time $r\cdot f(n)$. The drawback is that the tape input is no longer just $0$'s and $1$'s but will also include some added symbols, but the same methods can prove this for any $f\in\Omega(n)$, so it's still a pretty neat result.

# Answer
> 0 votes
You can simply apply Rice's theorem, since the class of languages

$$\mathcal{S} = \\{ L \mid L \\; \text{is a language decided by a TM with time complexity } 100n^2 + 200 \\}$$

is non-trivial.

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


title: How to prove $n^4 = \mathcal{O}(2^n)$?

text:
# Question
Title: How to prove $n^4 = \mathcal{O}(2^n)$?
I'm new to asymptotic notations and right now I'm trying to prove that $n^4 = \mathcal{O}(2^n)$. In my current solution (written below) I used L'Hôpital's rule repeatedly, proving that the limit of $n^4/2^n$ goes to zero. Is this correct? Additionally I'm wondering whehter there is a simpler solution to this problem. I tried induction but didn't get far. If you see an easier solution I would gladly appreciate any hints.

Thanks for any answers.

$ \lim\_{n\to\infty} \frac{n^4}{2^n} = \lim\_{n\to\infty} \frac{4\*n^3}{2^n * ln(2)} = ..... = 0$

# Answer
> 2 votes
You mentioned trying induction, to no avail. However, induction does work. Let's prove by induction that for all $n \geq 6$, $$n^4 \leq \frac{81}{4} 2^n.$$ This is true for $n = 6$ (both sides are equal to 1296). Suppose that it holds for some $n \geq 6$. Then $$ (n+1)^4 = \left(\frac{n+1}{n}\right)^4 n^4 = \left(1 + \frac{1}{n}\right)^4 n^4 \leq \left(1 + \frac{1}{6}\right)^4 n^4. $$ You can calculate that $(7/6)^4 \< 2$ (equivalently, $2401 = 7^4 \< 2 \cdot 6^4 = 2592$). Therefore, using the induction hypothesis, $$ (n+1)^4 \< 2n^4 \leq 2 \frac{81}{4} 2^n = \frac{81}{4} 2^{n+1}. $$ Thus the inequality holds for $n+1$ as well, completing the proof by induction.

---
Tags: asymptotics
---


# Question
Title: Generating cyclical dependency graphs from k-way partitions of DAGs representing boolean networks
My question stems from something mentioned in the following paper\*:

Acyclic Multi-Way Partitioning of Boolean Networks by Jason Cong, Zheng Li, and Rajive Bagrodia

Given a DAG representing a Boolean network, $N$, where each node represents a logic gate, define a k-way partitioning solution as $S = (A\_1, A\_2, ..., A\_k)$ satisfying $$A\_i \cap A\_j = \emptyset \quad{\text{and,}}$$ $$\bigcup\limits\_{i=1}^{k} A\_i = N$$

Then define a dependency graph $D(S)$. This is a directed graph with $k$ nodes where each node represents a block, $A\_i$, and has an edge $(A\_i,A\_j)$ if and only if there exists an edge $(x,y)$ in $N$ such that $x \in{A\_i}$ and $y \in A\_j$ (in other words, the edges are the edges removed when forming the partition).

The authors note that it is possible to get dependency graphs that are cyclic after some k-way partition. My question is, how is this possible? I can't seem to come up with an example where partitioning a DAG would ever produce a cyclic dependency graph. As I see it, a cyclic dependency graph would require a an edge to be "reversed" somehow, which would produce a cycle in the original DAG. Perhaps it has something to do with the fact these graphs are representing boolean networks?

\*Link to pdf may be paywalled

\**Note the authors also have a balance constraint on the partitions which I didn't describe but I don't think that's relevant to my question.

# Answer
Consider the following graph on three vertices:

$$u \to v \to w$$

This is acyclic. If you set $A\_1 = \\{u,w\\}$ and $A\_2 = \\{v\\}$, you end up with a dependency graph that is cyclic: it has an edge $A\_1 \to A\_2$ (due to the edge $u \to v$) and an edge $A\_2 \to A\_1$ (due to the edge $v \to w$).
> 0 votes

---
Tags: graphs, circuits, partitions
---


# Question
Title: In how many steps Euclidean Algorithm will find the GCD for two integers
I'm trying to solve this problem for big numbers (up to $10^9$). Namely, let's define $$GCD(a,b) = GCD(a-b, b)$$

We define GCD as function that returns greates common divisor of two numbers.

In case if $b \> a$ we swap the values of $b$ and $a$. Now I want to count the number of steps when either $a$ or $b$ will be equal to $0$.

**Example**

$$a = 4, b = 17\\GCD(17, 4) = GCD(4,13)\\GCD(13,4) = GCD(4, 9)\\GCD(9,4)=GCD(5,4)\\GCD(5,4) = GCD(4, 1)\\GCD(4,1) = GCD(1,3)\\GCD(3,1) = GCD(1,2)\\GCD(2,1) = GCD(1,1)\\GCD(1,1) == GCD(0,1)$$

We have total of 8 steps, however for big values those numbers are growing super fast.

**What I tried**

I know that this is solvable with Euclidean algorithm for finding GCD, but the faster variant of Euclidean variant is $GCD(a,b) = GCD(b, a \text{ mod } b)$, and for this variant the number of steps is less that $\log\_{10}max(a,b)$. But for this variant the number of steps is big numbers, so I think that it can be only calculated with math steps.

# Answer
It can be observed that the product $ab$ drops by a factor of at least two for each iteration.

Prior to each iteration, we have the pair $(a, b)$ such that $a \< b$, which is replaced by the pair $(r, a)$ at the end of each iteration in preperation for the next, where $r = b \bmod a$. We then have $r \< a$ and $a + r ≤ b$. Hence, $b ≥ a + r \> 2r$. So, $ar \< \frac{1}{2}ab$.

Supposing it takes N steps to compute $gcd(a, b)$ using the Euclidean algorithm, we then have $ar ≤ \frac{ab}{2^N}$ after N steps. It follows that $ab ≥ 2^N$.

Hence, $N ≤ \log\_2 ab = \log\_2 a + \log\_2 b$.

Therefore, the number of steps it takes to compute $gcd(a, b)$ using the Euclidean algorithm is at most $\log\_2 a + \log\_2 b$.

Furthermore, on Wikipedia, you can observe that the worst case is $N ≤ 5 \log\_{10} a$, i.e. five times the number of (base-10) digits of $min(a, b) = a$, where $(a, b)$ is a pair of consecutive Fibonacci numbers. This relationship is useful because $gcd(F\_{n+1}, F\_{n+2}) = 1$ (i.e. all consecutive Fibonacci numbers are coprime).

Given these upper-bounds, the asymptotic computational complexity of the Euclidean algorithm can be expressed using Big-O notation as $\mathcal{O}(\log b)$.

Since,

$$\mathcal{O}(\log b) = \mathcal{O}(\log\_2 a + \log\_2 b) = \mathcal{O}(5\log\_{10} a)$$

where $b ≥ a$.
> 2 votes

# Answer
Your question is a bit vague, but here are two interpretations.

**How many steps does the algorithm take in the worst case?**

A pretty bad case is when $b=1$. The algorithm then takes roughly $a$ steps. This shows that for some inputs $a,b$, the algorithm takes roughly $a+b$ steps. On the other hand, $a+b$ is clearly an upper bound on the number of steps, since $a+b$ decreases in each iteration.

**How to efficiently calculate the number of steps the algorithm takes?**

Suppose that $a = mb + k$, where $0 \leq k \< b$. Then the algorithm will take $m$ steps to reach $k,b$. I'll let you figure out how to use this in combination with the efficient GCD algorithm to efficiently calculate the number of steps your algorithm takes.
> 1 votes

---
Tags: number-theory
---


# Question
Title: Bounded waiting and progress requirements of critical section problem solution based on exchange instruction
Atomic exchange instruction is given as follows:

```
void exchange (int *a, int *b)
{
   int temp;
   temp = *b;
   *b = *a;
   *a = temp;
}

```

Now consider the solution to critical section problem based on above instruction:

```
1   int const n = /* number of processes */;
2   int lock = 0;
3   void P(int i)
4   {
5      int key = 1; //intent to obtain lock
6      while (true)
7      {
8         do exchange (&key, &lock)
9         while (key != 0); //if lock wasn’t free
10        /* critical section */;
11        lock = 0;   //release lock, unblock
12                    //other processes
13        /* remainder */;
14     }
15  }
16  void main()
17  {
18     lock = 0;
19     parbegin (P(1), P(2), ..., P(n));
20  }

```

Now I want to analyse two properties of critical section problem solution for this algorithm: bounded waiting and progress. People online define it many ways. For example: , .

One way is as explained here:

* **Progress**: means process will eventually do some work
* **Bounded waiting**: means that the process will eventually gain control of the processor

However I feel these are incorrect (**Q.1** Am I wrong?) as this will imply lack of bounded waiting result in the lack of progress, essentially suggesting two requirements are one and the same (**Q.2** Or is it like that only?).

Galvin et al defined these requirements more verbosely in their book:

> Considering the process has following structure:

```
do
{
    //entry section (implementing some locking mechanism)
    //critical section
    //exit section (implementing some unlocking mechanism)
    //remainder section
}
while(true);

```

> **Progress**: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely.
>
> **Bounded Waiting**: There exists a bound on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

Now with the help of these definitions I want to know whether bounded waiting and progress is ensured or not.

I feel bounded waiting is not ensured in above code as process P1 can enter its critical section any number of times before P2 can enter its critical section. This can be seen in below table:

```
| Step# | P1      | P2                |
|-------|---------|-------------------|
| 1     | Line 5  |                   |
| 2     | Line 6  |                   |
| 3     | Line 8  |                   |
| 4     | Line 9  |                   |
| 5     |         | Line 5            |
| 6     |         | Line 6            |
| 7     |         | Line 8            |
| 8     |         | Line 9 //spinwait |
| 9     | Line 10 |                   |
| 10    | Line 11 |                   |
| 11    | Line 13 |                   |
| 12    | Line 5  |                   |
| 13    | Line 6  |                   |
| 14    | Line 8  |                   |
| 15    | Line 9  |                   |
| 16    |         | Line 8            |
| 17    |         | Line 9 //spinwait |

```

However this means that P1 can execute forever without letting P2 enter its critical section at all. If we consider that the progress means "process will eventually do some work" (as stated in non-book definition above), then this will also mean that progress is also not ensured.

However I am trying to deduce if this is indeed the case with Galvin's definition also. But before that I want to interpret Galvin's definition of progress as follows:

> If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section (**in other words, processes executing in their entry and exit section**) can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely.

Now in table above, at step 10, no process is executing in its critical section. Process 1 executes line `11 lock = 0;` which is essentially its exit section. Thus we can say that the decision to let process 2 enter its critical section is taken in exit section of process 1. Also in step 14, process 1 executed line `8 do exchange (&key, &lock)`, which is essentially entry section. Thus we can say that the decision to let process 2 not to enter its critical section is taken in entry section of process 1. (**Q.3**) With this interpretation, should we say that the progress is ensured?

I feel tangled with words here. Or I might be giving unnecessary importance to the concept of progress. Neverthless, I need to know whats the truth about progress requirement.

**PS:** The same confusion occurred to me while dealing with attempts made to produce Dekker's algorithm by Stallings in his book as I explained in comments to this answer.

# Answer
> 1 votes
Little late anyway...First of all

```
8         do exchange (&key, &lock)
9         while (key != 0); //if lock wasn’t free

```

The exchange instruction has to be within the while loop otherwise the value of the key will never change. Coming to the question of: 1. Progress 2. Bounded waiting

This solution guarantees progress, as some thread will definitely get the lock as the exchange is an atomic operation and there will be some work done. However, it does not guarantee bounded waiting as it may be the case that one thread which is requesting to get the lock will never get it because of contention from other threads and it can starve.

---
Tags: operating-systems, concurrency, critical-section
---


# Question
Title: Is there a difference between top-down and bottom-up dynamic programming?
Is there a fundamental difference between top-down and bottom-up dynamic programming?

In particular, is there a problem which can be solved bottom-up but not top-down? Or is the bottom-up approach just an unwinding of the recurrence in the top-down approach?

# Answer
To use the bottom up method you need to be able to efficiently determine what the "bottom" is, which usually means you need a heavily constrained problem space. If you know what the lowest level calculations are going to be and the dependency order going upward, it makes sense to iteratively do them in the proper order and store those results. Factorials, naive Fibonacci and the Euler recurrence relation for partitions are all good examples of problems suited to this approach.

Some problems don't have an easily determined bottom or dependency order for the calculations. Chess positions evaluations, for example, are usefully memoized by position, with the evaluation score stored so it need not be recalculated. Positions can recur at multiple levels of the search tree due to move transposition and repetition so saving evaluation results is worthwhile. But there's no way to know what the positions at the lowest levels of the tree are going to be without recursively descending (and taking into account intermediate pruning) so top down is really the only feasible approach.
> 32 votes

# Answer
* Top-down approach: This is the direct fall-out of the recursive formulation of any problem. If the solution to any problem can be formulated recursively using the solution to its sub-problems, and if its sub-problems are overlapping, then one can easily memoize or store the solutions to the sub-problems in a table. Whenever we attempt to solve a new sub-problem, we first check the table to see if it is already solved. If a solution has been recorded, we can use it directly, otherwise we solve the sub-problem and add its solution to the table.
* Bottom-up approach: Once we formulate the solution to a problem recursively as in terms of its sub-problems, we can try reformulating the problem in a bottom-up fashion: try solving the sub-problems first and use their solutions to build-on and arrive at solutions to bigger sub-problems. This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger sub-problems by using the solutions to small sub-problems. For example, if we already know the values of F41 and F40, we can directly calculate the value of F42.
> 6 votes

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


# Question
Title: How does a computer distinguish two separate transmissions on a wire
My basic idea of networking at the lowest layer is that one computer will send a bunch of parallel bits at a time down a cable and another computer will read these bits. For example, computer #1 sends a bunch of parallel bits to computer #2. Computer #2 then gets the bits then waits for the next bunch of bits. And so on.

I have a couple of questions about how this works and how we get around a few problems.

Problem #1: Say Computer #2 doesn't wait long enough for the next series of bits. Computer #2 may accidentally read the first set of bits twice, messing up communication.

Problem #2: Computer #2 waits too long. It doesn't read the second set of bits in time and only starts reading after the second set of bits are shown.

\[to summarize problems 1 & 2, it seems like it would be very difficult to exactly sync the rate of transmition between the two computers)

Problem #3: We can't rely on every transmission to be different. So it's not like we can just wait for the transmission to change and then store the new value.

Problem #4: Say we use a special phrase. So after every transmission computer #1 signals to computer #2 that the transmission is going to change by flashing a bunch of 1's. This is a problem because what if our data is a bunch of 1s? We won't know if the transmission changed or not.

The only solution I can think of is to have some extra bit that alternates for each transmission, bit this seems like it wouldn't work for one-bit-at-a-time transmission networks like wifi. What part of all of this am I missing? How is this problem solved in the real world?

# Answer
On a wire you encode bits by changing the voltage, for example +5V could mean 1 and -5V could mean 0. If you do this naively you get problems with long sequences of 1's or 0's. For example you mentioned clock drift, i.e. when do I know that one 1 ended and the next 1 starts? But it's also problematic to have one voltage for a long time, because charge could build up at one end that needs to be dissipated somewhere.

So instead of using a naive encoding, we use a trick. For each bit we use two clock cycles, and encode the bit as the change in voltage. This way we implicitely also transmit our clock down the wire, the receiver can synchronise their clock using the same edge detection algorithm that they use to read the bits. This scheme is called Manchester code.

If you use more voltage levels to encode multiple bits at a time, the same basic idea can be applied. Instead of encoding the bits naively, we ensure that there is enough change in the data so that we can keep the clocks synchronised and the voltage on average 0. Check the related articles in the Wikipedia, for example 8b/10b encoding.
> 2 votes

# Answer
Adrian's answer covers your problems 1 and 2.

Problems 3 and 4 are solved by transmitting data in *packets*. Essentially, the transmitter divides the data they want to send into blocks and transmits the block one at a time. The blocks are typically of some fixed size and each block starts with (at the very least) the address of the recipient and how much actual data is in the block.

You also don't mention problem 5 which is "What happens if two computers are both transmitting at the same time?" This can happen even in a point-to-point network where only two computers use any particular wire, such as the cable between your computer and a router. In this case, anyone, including the transmitters, who's listening hears garbage – probably not even a signal that corresponds to any sequence of symbols – and both transmitters try again later. Obviously, in any sane protocol, a transmitter will first listen to see if the network is being used but it can still be that two transmitters decide to start simultaneously.
> 1 votes

---
Tags: computer-networks
---


# Question
Title: Why are computable functions continuous?
I am working on writing an *easy to read* document about denotational semantics of the lambda calculus. For that I introduce CPOs, monotonicity and continuity. A CPO is a set $M$ with a partial order $\leq$ and a bottom element $\bot$, requiring $\bot$ to be the smallest element in $M$ and the existence of the least upper bound ($\bigsqcup$) for every chain $d\_0 \leq d\_1 \leq d\_2 \leq ...$ in $M$. A function $f$ between two CPOs $M$, $N$ is monotone, if for all $a, b \in M$ the following holds:

$$a \leq b \implies f(a) \leq f(b)$$

A function $f$ between two CPOs $M$, $N$ is continuous, if it is monotone and for all chains $d\_0 \leq d\_1 \leq d\_2 \leq \dots$ we have

$$f(\bigsqcup\_{i \in \mathbb{N}} d\_i) = \bigsqcup\_{i \in \mathbb{N}} f(d\_i).$$

I want to give my readers a good intuition about the meaning of these definitions. However, I don't have one I could write down. Following Glynn Winskel in his book »The Formal Semantics of Programming Languages« (1993), $a \leq b$ has to be read as $a$ approximates $b$ (page 72), meaning $b$ has at least as much information as $a$. This leads to monotone functions reflecting more information about the input in more information about the output (page 122). This is somewhat understandable for me. However, the explanation of continuity is not clear for me:

> As we shall see, that computable functions should be continuous follows from the idea that the appearance of a unit of information in the output of a computable function should only depend on the presence of finitely many units of information in the input.

(page 73)

This is still unclear to me after reading the stream example in section 8.2 (pages 121–123), or this answer.

So my final question is: How do I convince my readers that computable functions are continuous? Why is there **no** computable function which is **not** continuous?

It would be nice if you can give me answers/examples which do not require the rigorous introduction of computability or fix-point theory, since I do not want to focus on those things. Also it would be great if it is not necessary to know the lambda calculus and its denotational semantics in advance, because I want to (and have to) introduce monotonicity and continuity before them.

EDIT: By *computable* I mean Turing-computable. Please correct me if I misunderstand Winskels definition of computable on page 337, since it is not explicitly defined as Turing-computable but in an equivalent (at least in my eyes) manner.

Also I want to point out another source I found which tries to explain my problem. But still I don't understand its example, since it is basically the same as the stream example from Winskel.

EDIT 2: It would also be a good start in helping me to understand the matter to show that every computable function is monotone, i.e. there exists no non-monotone computable function.

# Answer
> 15 votes
There are several ways to explain "computable implies continuous", I shall give here two such explanations.

### Turing machines compute continuous maps

Suppose we have a Turing machine which takes possibly infinite amount of input written down on an input tape. It writes the result on an output tape, where the output cells are write-once. There are working tapes. The machine may run forever, filling up the outputs cells. This is known as a *type two* machine. (The argument for other kinds of machines is going to be similar but simpler.)

The following should be obvious: when the machine writes into an output cell, its workings up to that point only depends on a finite portion of the input tape, for the simple reason that in finitely many computation steps it could not have moved the input head past some point. Therefore, every input tape that agrees with the given one up to that point would have caused the machine to write the same answer to the same output cell.

But this is a form of continuity, if we put the correct topology on the spaces of input and output tapes.

First we put topology on the set $\Sigma$ of symbols that can be written onto tape cells. For this we just pick the discrete topology. A tape is an infinite sequence of symbols, so an element of $\Sigma^\omega$, which is a product of $\Sigma$'s. Let's put the product topology on it.

Recall that a basic open set on $\Sigma^\omega$ for the product topology is of the form $U(a\_0, \ldots, a\_n) = \\{\alpha \in \Sigma^\omega \mid \forall i \< n . \\, \alpha\_i = a\_i\\}$, where $a\_0, \ldots, a\_n \in \Sigma$. That is, a basic open set fixes an initial portion of the sequence to the given values $a\_0, \ldots, a\_n$.

Now we may check that the function $f : \Sigma^\omega \to \Sigma^\omega$ computed by the machine is indeed continuous. Take a basic open set $V = U(a\_0, \ldots, a\_n)$ and let $W = f^{-1}(V)$. We need to verify that $W$ is open. For this purpose, consider any $\alpha \in W$. If we find a basic open set $W'$ such that $\alpha \in W' \subseteq W$, then we're done.

Because $\alpha \in W$, we have $f(\alpha) \in V$. Thus on input $\alpha$ the machine produces an output tape starting with $a\_0, a\_1, \ldots, a\_n$. By the time it writes out these cells it has inspected at most the first $k$ cells of the input, for some $k \in \mathbb{N}$. We may take $W' := U(\alpha\_0, \ldots, \alpha\_k)$ and verify that $\alpha \in W' \subseteq W$. It is obvious that $\alpha \in W'$. To prove $W' \subseteq W$ take any $\beta \in W'$ and observe that $f(\alpha)$ and $f(\beta)$ agree on the first $n$ values of the output. This implies that $f(\beta) \in V$ and hence $\beta \in W$, as required.

### Computable maps are continuous as maps between algebraic $\omega$CPOs

First, let me note that what you defined is usually called "$\omega$CPO" ($\omega$ in the name indicates we only require suprema of chains).

In denotational semantics datatypes correspond to $\omega$CPOs. In fact, they correspond to *algebraic* $\omega$CPOs (is this in your thesis?), which are $\omega$CPOs for which the compact elements form a base. Here are some definitions.

**Definition:** Let $D$ be an $\omega$CPO. An element $d \in D$ is *compact* if, for every $\omega$-chain $x\_0 \leq x\_1 \leq \cdots$ such that $d \leq \bigsqcup\_i x\_i$, there exists $j$ such that $d \leq x\_j$.

**Definition:** An $\omega$CPO is *algebraic* if every $x \in D$ is the supremum of compact elements below it.

The intuition behind compact elements is that they contain "finite information". A good example is $\mathcal{P}(\mathbb{N})$, the powerset of natural numbers ordered by $\subseteq$, where the compact elements are precisely the finite subsets of $\mathbb{N}$ (exercise!). Another example: in the $\omega$CPO of continuous functions $\mathbb{N} \to \mathbb{N}\_\bot$ the compact elements are those partial functions that are equal to $\bot$ everywhere, except at finitely many arguments.

To say that an $\omega$CPO is algbraic is to say that every element is completely determined by the finite pieces of information that approximate it. It is a fact that in denotational semantics datatypes correspond to algebraic $\omega$CPOs, unless we are doing something very unusual.

We can now explain why every computable map is continuous. Suppose $D$ and $E$ are $\omega$CPOS and $f : D \to E$ computable. Suppose $x \in D$, $e \in E$, $e$ is compact, and $e \leq f(x)$. Intuitively, this say that "finite piece of information $e$ appears in the output $f(x)$". Because $f$ is computable, it must be the case that it computed the information $e$ by accessing only a finite amount of information about $x$, i.e., there is a compact $d \in D$ such that $d \leq x$ and $e \leq f(d)$. This argument should be compared to the Turing machine argument above. We have established:

**Lemma:** If $f : D \to E$ is computable and $e \leq f(x)$ for some $x \in D$ and a compact $e \in E$, then there is compact $d \in D$ such that $d \leq x$ and $e \leq f(d)$.

We can usethe lemma to show that a computable $f$ is continuous. Suppose $x\_0 \leq x\_1 \leq \cdots$ is a chain in $D$. Because $f$ is monotone, we already know that $\bigsqcup\_i f(x\_i) \leq f(\bigsqcup\_i x\_i)$, but we also need the inequality $f(\bigsqcup\_i x\_i) \leq \bigsqcup\_i f(x\_i)$. Because $E$ is algebraic, it suffices to show that, whenever $e \in E$ is compact and $e \leq f(\bigsqcup\_i x\_i)$ then $e \leq \bigsqcup\_i f(x\_i)$. So assume $e \leq f(\bigsqcup\_i x\_i)$. By the lemma there exists a compact $d \in D$ such that $d \leq \bigsqcup\_i x\_i$ and $e \leq f(d)$. Because $d$ is compact, there exists $j$ such that $d \leq x\_j$, hence by monotonicity of $f$ we have $e \leq f(d) \leq f(x\_j) \leq \bigsqcup\_i f(x\_i)$. We are done.

---
Tags: computability, denotational-semantics
---


# Question
Title: Paired resolution and $\mathsf{NP}$ vs. $\mathsf{coNP}$?
Let we resolve only two clauses at time and then get rid of them. Such resolution clearly takes $O(n)$ steps.

*Sequence* is a set of instructions in the form $(C\_{S\_1}\cup C\_{S\_2},v\cup\overline v),...$, where $S\_i$ denotes a set of merged clauses, $v\in C\_{S\_1},\overline v\in C\_{S\_2}$.

Of course such resolution taken deterministically or randomly is wrong with high probability.

For example, let's consider $\varphi=(x\oplus y)(x\oplus z)(y\oplus z)$.

Clearly this formula is unsatisfiable. But what can I get using resolution:

$(x\oplus y)\Leftrightarrow(x\lor y)\land(\overline x\lor\overline y)$.

Resolving $x$ and $\overline x$: $(y\lor\overline y)=1$.

Doing this for other clauses gives us tautology.

So, this means, that sequence $(C\_1\cup C\_2,x\cup \overline x),(C\_3\cup C\_4,x\cup \overline x),(C\_5\cup C\_6,y\cup \overline y)$ is wrong.

But there is a correct sequence:$(C\_1\cup C\_4,x\cup\overline x),(C\_2\cup C\_3,\overline x\cup x),(C\_{\\{1,4\\}}\cup C\_5,\overline z\cup z),(C\_{\\{2,3\\}}\cup C\_6,z\cup\overline z),(C\_{\\{\\{1,4\\},5\\}}\cup C\_{\\{\\{2,3\\},6\\}},y\cup\overline y)$

Showing this:

Initial formula: $(x\lor y)(\overline x\lor\overline y)(x\lor z)(\overline x\lor\overline z)(y\lor z)(\overline y\lor\overline z)$

1. $(x\lor y)(\overline x\lor\overline z)\mapsto(y\lor\overline z)$
2. $(\overline x\lor\overline y)(x\lor z)\mapsto(\overline y\lor z)$
3. $(y\lor\overline z)(y\lor z)\mapsto y$
4. $(\overline y\lor z)(\overline y\lor\overline z)\mapsto\overline y$
5. $y\land\overline y\mapsto0$

There are exponentially many sequences for any formula. Same applies for number of possible assignments.

But what I'm asking: is such type of resolution is proved not to be refutation-complete? In other words have someone proved that not every unsatisfiable formula has a sequence that results in empty clause? Or is it an open question? (Otherwise we'd know that $\mathsf{NP=coNP}$)

*P.S.* This type of resolution is sound, so only thing that I do not know is refutation-completeness.

# Answer
> 3 votes
It is known that some formulas require exponentially long Resolution proofs. Therefore Resolution cannot be used (directly) to prove that $\mathsf{NP}=\mathsf{coNP}$.

Note that the details of your procedure are completely irrelevant. The lower bounds show that *whatever* algorithm you use to create your Resolution refutations, there will be some formulas on which it will take exponential time, simply because every Resolution refutation of these formulas is exponentially long.

---
Tags: satisfiability, np
---


# Question
Title: Why Finite Automata are restricted in reading the input?
*Well, I should have posted this question before Why NFA is called Non-deterministic?. Anyways now this is pondering in my mind.*

Why people who came up with this automaton theory restricted the input format of it as a **read-only, symbol-stream tape**.

Is it not so that if we provide random accessible input tape (as in case of many computer programs) to the automaton it will be **more powerful**? (*however it is purely my intuition having no standard proofs*)

# Answer
Yes, there are things you could do to finite automata to make them more powerful. However, "with great power(er) comes great(er) responsibility."

Finite automata aren't very powerful but the languages they express – the regular languages – form a natural and important class. Furthermore, for a fixed automaton, you can decide in linear time (with respect to the input) and constant working space whether it accepts or rejects any particular string. This is true even if the automaton is nondeterministic.

OK, but lots of important languages can't be decided by finite automata. Important examples include anything that involves bracket matching, including the syntax of any sane programming language. How might you try to make automata more powerful and what would the cost be?

* Suppose we allow the machine to scan both left and right along its input. This gives a two-way automaton. Well, it turns out that two-way automata (deterministic or nondeterministic) still only accept regular languages – the same as ordinary automata. The two-way automaton might require fewer states and you can still determine whether it accepts a given input in linear time. But now there's the possibility that the automaton can loop forever, so you need to check for that, which requires a logarithmic amount of working space, instead of constant. (Since the number of steps before termination is bounded by some linear function of the length of the input, you can detect looping by counting steps and halting if the computation runs too long. The counter needs a logarithmic number of bits.)
* Suppose you allow the automaton to move backwards and forwards as well as overwrite its input, but not to use any more space than the input takes up. This does make the machine more powerful (for example, you can now detect well-matched bracketings by "crossing out" the brackets one by one) but it makes it even harder to determine whether the machine accepts its input and to check for infinite loops. Now, halting might take exponentially many steps, so you need a polynomial-length counter (linear is probably enough).
* Suppose you allow the automaton to move backwards and forward, overwrite its input and use as much additional space as it wants. Now your automaton has become a Turing machine. It can do (we think) anything that any reasonable computer can do but there's no way of determining whether it accepts its input except for running the machine and hoping it eventually stops. This could take arbitrarily long and use arbitrarily much working space.

There are plenty of other possible additions to automata (for example, stacks) but they don't fit as neatly into the discussion above.

So, yes, you might want to make automata more powerful. But doing so brings risk and expense that you might not be prepared to tolerate, if you don't need it.
> 6 votes

# Answer
The modern definition of finite automata (deterministic and nondeterministic) appears in the foundational paper of Rabin and Scott, Finite automata and their decision problems, which also introduced nondeterminism *in general*. Here is what they had to say:

> Turing machines are widely considered to be the abstract prototype of digital computers; workers in the field, however, have felt more and more that the notion of a Turing machine is too general to serve as an accurate model of actual computers. It is well known that even for simple calculations it is impossible to give an a priori upper bound on the amount of tape a Turing machine will need for any given computation. It is precisely this feature that renders Turing’s concept unrealistic.
>
> In the last few years the idea of a finite automaton has appeared in the literature. These are machines having only a finite number of internal states that can be used for memory and computation. The restriction of finiteness appears to give a better approximation to the idea of a physical machine. Of course, such machines cannot do as much as Turing machines, but the advantage of being able to compute an arbitrary general recursive function is questionable, since very few of these functions come up in practical applications.
>
> Many equivalent forms of the idea of finite automata have been published. One of the first of these was the definition of “nerve-nets” given by McCulloch and Pitts. The theory of nerve-nets has been developed by authors too numerous to mention. We have been particularly influenced, however, by the work of S. C. Kleene who proved an important theorem characterizing the possible action of such devices (this is the notion of “regular event” in Kleene’s terminology). ...

Originally, finite automata (in a very different form) were introduced as a model for neural networks in the brain (hence the name "nerve-nets"). Later on, a different motivation came up: finding a computational model which is more realistic than the much-too-strong Turing machines. Even later, regular languages were included in the Chomsky hierarchy, and it was realized that they are very useful for certain parsing tasks.

Unfortunately this history is usually skipped in introductory classes.

The name "regular language" (originally "regular event") comes from Kleene. His original RAND report "welcome\[s\] any suggestions as to a more descriptive term" (and mentions that it might be the same concept as McCulloch and Pitts' "prehensible"), but this comment was dropped in the journal version Representation of events in nerve nets and finite automata.

(Disclaimer: I'm not an expert on the history of computer science, so I might have gotten some of the facts wrong or presented them in a misleading way.)
> 5 votes

---
Tags: finite-automata
---


# Question
Title: Is this problem a variant of TSP problem? if not, what is it called?
A jet which can fly no more than R kilometers without refilling, is at location 0 and needs to fly to point N+1. There are some petrol stations on the way, some of which are ready to use, others are under construction and will be available soon. We get an array C of length N, where the value of C\[i\] describes the petrol station at location i in the following way:

* If C\[i\] = -1 there is no station.
* If C\[i\] = 0 there is a station at location i
* If C\[i\] = x there is a station at location i which will be
available at in x days.

Assume that flying from point a to point b takes no time. But if jet runs out of petrol on a point x of array, it should wait x days to refill and then continue its way. If x=-1, jet is stuck. *The task is to find the minimal number of days the jet can get from point 0 to N+1, refilling on the way when necessary.*

**Is it a TSP variant with an extra condition?** I am new to these.

P.S.The task is the same as "compute the maximum value of minimum values for each range of length R".

**UPD.** I looked at all types of dynamic programming questions, it is not close to them. I was given this problem in the university, as one in the miscellaneous set of problems.

# Answer
TSP assumes you go through a hamiltonian path.

This problem looks more like a simple a path search with some added restrictions and it's solvable with A\*.
> 1 votes

---
Tags: algorithms, optimization, time-complexity
---


title: Is it a valid graph canonical form?

text:
# Question
Title: Is it a valid graph canonical form?
This question is motivated from this post. Let $G$ be a given graph, for each vertex $v \in V$, I will label $v$ with $Triangle(v)$.

$Triangle(v) : $ means number of distinct triangles contain $v$.

Question : Is it a valid canonical form? Is computing this function easy (mean polynomial time)?

# Answer
> 3 votes
A *canonical form* of a graph is a mapping $C$ from the set of graphs to the set of graphs such that $C(G)$ is isomorphic to $G$, and $C(G) = C(H)$ iff $G$ is isomorphic to $H$. Your function doesn't map graphs to graphs, so it's not a canonical form.

A more relevant notion is a *(complete) invariant*. This is a mapping $I$ from the set of graphs to some other set such that $I(G) = I(H)$ iff $G$ is isomorphic to $H$. Your mapping, as stated, is not a graph invariant. For example, consider the graph consisting of a triangle plus an isolated vertex. Consider the graph $G$ in which the triangle vertices are $1,2,3$, and the graph $H$ in which the triangle vertices are $1,2,4$. The two graphs are isomorphic, but the vector $\mathit{Triangle}(\cdot)$ is different.

We can try to fix this problem by sorting the vector. This will ensure that the vectors corresponding to $G,H$ above are the same. However, consider $H'$, which consists of a triangle connected by an edge to a vertex. The graphs $H$ and $H'$ have the same sorted triangle vector, but are not isomorphic. So your suggestion is not even a complete invariant.

Finally, you ask how easy it is to calculate your function. There is a trivial $O(n^3)$ algorithm which goes over all triples of vertices, and this can be improved to $O(n^\omega)$ using fast matrix multiplication: if $A$ is the adjacency matrix of the graph, then $(A^3/2)\_{vv}$ is the number of triangles containing $v$.

---
Tags: graph-isomorphism
---


# Question
Title: Knuth's proof of O(1) for linear probing
I'm currently reading Knuth's proof about O(1) number of probes in linear probing. I have a small question on the page 536 (Volume 3, 2nd Edition). Knuth says

> Let $f(M, N)$ be the number of hash sequences such that position 0 of the table will be empty after the keys have been inserted using linear probing. The circular symmetry of linear probing implies that position 0 is empty just as often as any other position, so it is empty with probability $1 - \frac{N}{M}$; in other words $f(M, N) = (1 - \frac{N}{M})M^N$.

I explain to myself as follows. Each hash sequence has $M-N$ empty positions, then the total number of empty positions is $(M-N)M^N$ and -- due to the symmetry -- each position is empty for $(M-N)M^N / M = (1 - \frac{N}{M})M^N$ hash sequences. Thus, the probability of zero position to be empty is $(1 - \frac{N}{M})$.

The problem is that Knuth **first** states that the probability that 0 position is empty is $(1 - \frac{N}{M})$ and **after** says that $f(M, N) = (1 - \frac{N}{M})M^N$. I'm able to prove this only in **other way around**. Could please anybody explain how to prove the probability without showing that the total amount of empty positions is $(M-N)M^N$.

Thank you.

# Answer
> 4 votes
Let $p\_i$ be the probability that position $i$ is empty. A simple coupling (detailed below) shows that $p\_i = p\_j$ for all $i,j$, and so $Mp\_0 = p\_0 + \cdots + p\_{M-1}$. Now let $X\_i$ be the indicator for the event "$i$ is empty". Then $$p\_0 + \cdots + p\_{M-1} = \mathbb{E}\[X\_0\] + \cdots + \mathbb{E}\[X\_{M-1}\] = \mathbb{E}\[X\_0 + \cdots + X\_{M-1}\], $$ using linearity of expectation. But $X\_0 + \cdots + X\_{M-1} = M-N$, since exactly $N$ positions are full and $M-N$ are empty. Altogether, we get $$ p\_0 = \frac{p\_0 + \cdots + p\_{M-1}}{M} = \frac{M-N}{M} = 1 - \frac{N}{M}. $$

Now for the coupling argument. Let $A = a\_0,\ldots,a\_{N-1} \in \\{0,\ldots,M-1\\}^N$ be a uniformly random insertion sequence, and let $B = b\_0,\ldots,b\_{N-1}$, where $b\_t = a\_t + j-i \pmod{M}$. Denote the final resulting hashtables by $H\_A,H\_B$. You can prove by induction that $H\_A(p) = H\_B(p+j-i\bmod{m})$ for every $p \in \\{0,\ldots,m-1\\}$ (the induction is on the number of insertions), and so $H\_B(j) = H\_A(i)$. In particular, cell $i$ is empty in $H\_A$ iff cell $j$ is empty in $H\_B$. Now $H\_A$ and $H\_B$, when considered individually, are generated by a uniformly random insertion sequence, and so the probability that $H\_A(i)$ is empty is $p\_i$, and the probability that $H\_B(j)$ is empty is $p\_j$. This shows that $p\_i = p\_j$.

---
Tags: hash, hash-tables, hashing
---


# Question
Title: How to store $n$ numbers with space $O(n)$ bits and access time $O(1)$?
I want to store a subset of $\\{1,2,\dots,n\\}$ in a data structure such that the total space used is $O(n)$ bits and accessing a particular element can be done in $O(1)$ time. I have tried binary search tree and array data structures but they are too slow.

In short I need a data structure with $O\big(\frac {n } { \log \log n}\big)$ many cells and size of each cell should be $O(\log \log n)$ bits.

**Model of computation**: Input memory and a write only output memory. The computation proper takes place in a working memory of limited size. When stating a problem can be solved with in a certain bits, what we mean is that the working memory comprises that many bits. The input and working memories are divided into words of $w$ bits for a fixed parameter $w$, arithmetic and logical operations on $w$-bit words take constant time, and random access to the input and working memories is provided. In the context of inputs of $n$ words,$w= \theta(\log n)$.

**Operations**: Insert($i$), access($i$), where $i \in \[n\]$. The access operation must run in $O(1)$ time.

**Motivation**: I'd like to store the stack in DFS using this data structure.

I am looking for an deterministic approach, but to me it does not seems working, so probabilistic approach is also fine.

# Answer
> 3 votes
A simple solution is to use a $n$-bit bitvector. This is basically an array with $n$ entries, where each entry is either 0 or 1. If the $i$th entry is 1, that means that $i$ was stored in the data structure; 0 means that $i$ was not stored in the data structure. This takes $O(n)$ bits of space. The insert and access operations can be done in $O(1)$ time.

The crucial requirement that makes this solution possible is that there will be no duplicates; each number is present at most once. If you allowed duplicates, the problem would not be solvable within the space requirements you list: storing $n$ numbers from $1$ to $n$ requires at least $\Theta(n \log n)$ bits, based on information-theoretic concerns.

# Answer
> 0 votes
I'm not sure I understand the problem you are trying to solve, but how about perfect hashing? It works like a hashmap, but has at most one entry per bucket, hence access is guaranteed $O(1)$ for access. Depending on how much time you spend on finding the has function, the hashmap can have a map very (almost?) every bucket is filled and your space complexity is also close to or even equal to $O(1)$. Since you will have at most one entry per bucket, You don't need an additional data structure in each bucket to handle collisions, so all you need is an array with your data and the bits to store the hash function.

Insertion is a bit more expensive, because you may have to try out a few hashfunctions before you find a good one, but this is typically quite fast.

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


# Question
Title: How do I find maximum and minimum number of times the search loop will execute when searching through an array of 1,048,576 integers
I have tried to calculate the maximum number of times the loop will search through this large array, but I am not sure if I have that correct and I also need help with or pointers of how I can calculate the number of minimum times it will search through the array using both the binary search and sequential search. Here is what I have done so far.

Maximum Number of Times with Binary Search: Maximum: $\log\_2(1,048,576)= 20$ times Maximum Number of Times with Sequential Search: Maximum: $1,048,576 + 1 ÷ 2= 524,289$ times

But I am confused about how I can obtained a solution with Minimum number for each algorithm. Any suggestions?

# Answer
> 1 votes
I assume your input is random and your array of size $N$, $A\[1..N\]$.

In case of binary search if the number you are searching for is located at $(1+N)/2$, i.e. right in the middle of the input array then you will find it after the first if-statement.

Similarly in case of sequential search, if number your are searching for is the first element of the array then you stop after the first if-statement.

In both cases you do only one comparison.

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


# Question
Title: Convert a decimal floating-point number into a binary floating-point number
Let's say I have a decimal floating-point number, i.e. a mantissa and precision (negative exponent), both represented as integers. How do I convert this into a binary floating point number (of the sort you find in most programming languages, with only the standard operations available). This should be done with maximum precision, ideally. The naive method of simply calculating $m \cdot 10^e$, where $m$ is the mantissa and $e$ the exponent, turns out to be very imprecise when $e$ is large, unfortunately.

I was also wondering how to do the reverse. I suspect the algorithm can't simply be reversed, due to the different representations.

# Answer
I am not an expert in this area, but the following is what I know about this problem. This problem was solved in the following paper:

* William D. Clinger. How to read floating point numbers accurately, *ACM SIGPLAN Notices*, 25(6) \[*Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation*\], pages 92–101, June 1990 (A PDF, you'll find other versions online)

This is also the reference cited by Knuth in TAOCP Volume 2, Exercise 17 in 4.4 (Radix Conversion).

In a retrospective published in 2004, the author looks back and cites the following additional references:

* David Gay. Correctly rounded binary-decimal and decimal-binary conversions. Technical Report 90-10, AT&T Bell Laboratories, November 1990. At http://www.ampl.com/REFS/ (Direct link)

In particular, see function `strtod` in David Gay's `dtoa.c` available at http://www.netlib.org/fp/

---

The reverse problem (printing floating point numbers) is harder. It should probably be a separate question, but here are some references:

Popular expositions and other implementations:

Aside/Example: Even though this is a problem solved since 1990 (albeit with developments even last year), even Python until 2.6 had suboptimal printing of floating-point numbers, e.g. it would print `float('2.2')` as `'2.2000000000000002'`. It was fixed only in Python 2.7. See https://docs.python.org/2/whatsnew/2.7.html#python-3-1-features and https://docs.python.org/3/whatsnew/2.7.html#other-language-changes (specifically https://bugs.python.org/issue7117 and discussion at https://mail.python.org/pipermail/python-dev/2009-October/092958.html).
> 3 votes

# Answer
An example: 13.7 = 137 / 10. You can convert to the exact floating-point numbers 137 and 10, then divide with a floating point division, and get the correctly rounded result. There is a huge range of decimal numbers that can be converted that way.

If this fails, you can do the calculation with higher precision than required, find the best possible upper bounds for the rounding error involved, and check whether or not you can guarantee a correctly rounded result.

(For example, if I wanted a value correctly rounded to an integer, and I can calculate the result with an error \< 0.001, and I get a result of 15.4989, then I know the rounded result is 15. If I get a result of 15.4991, I don't know the correctly rouned result).

Then you have to decide what kind of rounding error is acceptable to you. Part 1 will give you in many cases (and in the majority of practical cases) the correctly rounded result very, very quickly. Part 2 will give you the proven correctly rounded result in 99% of cases if you use extended precison for a floating-point result, also quite quickly. Using quad precision you will get the proven correct result in practically all cases, but a bit slower. Conversion with infinite precision is trivial, but slow.

There is a special case: If you generated decimal numbers as good approximations to floating-point numbers (say storing floating-point numbers in a file in human readable format), then converting decimal to floating-point by using slightly higher precision will *always* be successful.
> 0 votes

---
Tags: algorithms, floating-point, base-conversion
---


# Question
Title: Maximum entropy probability distribution among Solomonoff priors
If we take Solomonoff's prior $m$, defined here and normalize it we get a probability mass function on all finite words. But, the pmf isn't completely determined until we fix a universal Turing machine (UTM) $U$. Say $m\_U$ is the normalized prior with respect to a UTM $U$. Is there a $U$ such that $m\_U$ has maximum entropy?

# Answer
All versions of Solomonoff's prior have infinite entropy. We supply a proof. Let $m: \mathbb{Z}\_+ \to \[0,1\]$ be Solomonoff's prior, where inputs are encoded as integers. Then there is $c\>0$ such that $$m(n) \geq c\frac{1}{n (\log n)^2},$$ Let $S$ be the set of all $n$ such that $$m(n) \geq \frac{1}{n}.$$ Since $\sum m(n)$ is convergent, $$\sum\_{s \in S} \frac{1}{s} \leq \sum\_n m(n) \< \infty.$$

The entropy of $m$ is $$ \begin{align\*} \sum\_n m(n) \log(1/m(n)) &\geq \sum\_n c\frac{1}{n (\log n)^2} \log(1/m(n)) \\ &\geq \sum\_{n \not\in S} c\frac{1}{n (\log n)^2} \log(1/m(n)) \\ &\geq \sum\_{n \not\in S} c\frac{1}{n \log n}. \end{align\*} $$

Now $$ \infty = \sum\_{n} c\frac{1}{n \log n} = \sum\_{n \in S} c\frac{1}{n \log n} + \sum\_{n \not\in S} c\frac{1}{n \log n}, $$ and $$\sum\_{s \in S} \frac{1}{s \log s} \leq \sum\_{s \in S} \frac{1}{s} \< \infty,$$ so $$ \sum\_{n \not\in S} c\frac{1}{n (\log n)} = \infty. $$
> 0 votes

---
Tags: turing-machines, probability-theory, entropy
---


# Question
Title: How does Hoare's quicksort work, even if the final position of the pivot after partition() is not what its position is in the sorted array?
All variable names are from Quicksort's wikipedia page's Lomuto's and Hoare's quick sorts pseudocode.

If `p` is what is returned by the `partition` function, Hoare divides his array from `lo` to `p` and from `p+1` to `hi`, while Lomuto divides his array from `lo` to `p-1` and from `p+1` to `hi`.

I may be wrong about this, but Quicksort's philosophy is...

1. Take an element in the subarray (pivot).
2. Rearrange the subarray in such a way that all elements left of the pivot are smaller than the pivot, and all the elements right of the pivot are greater than the pivot.
3. Divide the array about the pivot. Repeat the process for the two smaller sub-subarrays. Keep doing this until you encounter an array with only one or less elements, because that is already sorted.

I find Hoare's `partition` to be more simpler to understand, than Lomuto's. Hoare's partition simply instructs us to start from the left end and the right end and to keep moving towards each other. If left marker encounters an element greater than the pivot, then the left marker pauses, and waits for the right marker to find an element smaller than the pivot. Then they exchange the elements, so that the left marker has the smaller element, and the right marker has the greater element. They keep doing this until they meet. Very straightforward.

Lomuto's `partition`, can be considered as a snake, of sorts, made of two parts, a head and a tail. The pivot is fixed (I usually take the last element as the pivot for Lomuto). The snake starts from the left-hand side, and stops just before the last element. When the snakes encounters an element smaller than the pivot, that element goes to the tail and the length of the tail increases. When an element greater than the pivot is discovered, that element goes to the head of the snake. Finally, the pivot is placed between the tail and the head. It's pretty clear but not as intuitive or efficient (in some cases) as Hoare's `partition`.

What confuses me is that Hoare's partition doesn't ensure that the position of the pivot after the `partition` has run its course, will be it's position in the final, sorted array. The only pattern that I could recognise in Hoare's partition was that `i` is at the **final position** of the pivot and that `j` is either `i` or `i-1`, `j` and `i` being the right and left markers.

Lomuto's partition, however, guarantees it. So, when I step back and look at the bigger picture, it makes sense for Lomuto to divide the array from `lo` to `p-1` and from `p+1` to `hi`. But, I can't understand **how Hoare can divide his array from `lo` to `p` and from `p+1` to `hi`, make up for his partition not putting its pivot in its rightful place.**

# Answer
I've been looking into examples and sorting arrays myself via Hoare's quicksort. I think I've found another interesting pattern in Hoare's partition algo. Which may explain why Hoare's method works. Lomuto divides the array into *three* parts; elements smaller than the pivot, the pivot, elements greater than the pivot. I think Hoare looks at things differently. He divides the array into *two* parts; elements smaller than the pivot, **elements equal to or greater than the pivot**. One of the traps that I fell into was that Lomuto's partition returns the final position of the pivot, whereas Hoare's partition **returns the position just before the final position of the pivot.** This is why Lomuto then quick sorts from `lo` to `p-1`, whereas Hoare quick sorts from `lo` to `p`. Another inference that can be drawn is that if Hoare's `partition` returned `i` instead of `j`, we'd then divide the array into two parts- from `lo` to `i-1` and from `i+1` to `hi`, just like Lomuto did. And it only took me 4 hours to understand that.
> 4 votes

---
Tags: sorting, quicksort
---


title: What exactly is polynomial time?

text:
# Question
Title: What exactly is polynomial time?
I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential.

Do linear/constant/quadratic complexities count as polynomial? An answer in simple English will be appreciated :)

# Answer
First, consider a Turing machine as a model (you can use other models too as long as they are Turing equivalent) of the algorithm at hand. When you provide an input of size $n$, then you can think of the computation as a sequence of the machine's configuration after each step, i.e., $c\_0, c\_1, \ldots$ . Hopefully, the computation is finite, so there is some $t$ such $c\_0, c\_1, \ldots, c\_t$. Then $t$ is the running time of the given algorithm for an input of size $n$.

An algorithm is polynomial (has polynomial running time) if for some $k,C\>0$, its running time on inputs of size $n$ is at most $Cn^k$. Equivalently, an algorithm is polynomial if for some $k\>0$, its running time on inputs of size $n$ is $O(n^k)$. This includes linear, quadratic, cubic and more. On the other hand, algorithms with exponential running times are not polynomial.

There are things in between - for example, the best known algorithm for factoring runs in time $O(\exp(Cn^{1/3} \log^{2/3} n))$ for some constant $C \> 0$; such a running time is known as *sub-exponential*. Other algorithms could run in time $O(\exp(A\log^C n))$ for some $A \> 0$ and $C \> 1$, and these are known as *quasi-polynomial*. Such an algorithm has very recently been claimed for discrete log over small characteristics.
> 52 votes

# Answer
Running an algorithm can take up some computing time. It mainly depends on how complex the algorithm is. Computer scientists have made a way to classify the algorithm based on its behaviour of how many operations it needs to perform (more ops take up more time).

One of that class shows polynomial time complexity. Ie., operational complexity is proportional to $n^c$ while n is size of input and c is some constant. Obviously the name comes because of $n^c$ which is a polynomial.

There are other 'types' of algorithms that take up constant time irrespective of the size of the input. Some take up $2^n$ time (yes, really slllooooww most of the time).

I just over simplified it for the layman and may have introduced errors. So read more https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
> 9 votes

# Answer
In layman terms it the running time of your algorithm.

The order of algorithms (growth) can be in Big-oh (O), little-oh(o), omega (Ω) or theta(Θ).

If you are having problems calculating RR please view some questions i asked before and vote if you understand.

Say you have a for loop:

```
 for(i=1 to n)
     x++

```

The order or time complexity of this piece of code is: O(n)

Why big-oh? Because we want the worst case at which this piece of code runs.

Read here (these define the complexity of an algorithm and informs you of how algorithms are done in polynomial time):

```
 http://en.wikipedia.org/wiki/NP_(complexity)

 http://en.wikipedia.org/wiki/NP-complete

 http://en.wikipedia.org/wiki/NP-hard

```

Summary:

http://www.multiwingspan.co.uk/a23.php?page=types
> -3 votes

---
Tags: algorithms, terminology, time-complexity, runtime-analysis, polynomial-time
---


# Question
Title: Finding an element in a infinite unsorted doubly linked list
Is there any way to find an element in an unsorted doubly linked list given an element and pointer from which we can navigate? (we can't use head/tail pointers since the list is infinite)

# Answer
> 2 votes
Infinite/unbounded in both directions? Zig-zag.

---
Tags: algorithms, search-algorithms, linked-lists
---


title: Defining L(G) in set notation

text:
# Question
Title: Defining L(G) in set notation
Let G be the grammar:

S --\> ASB | λ

A --\> aAb | λ

B --\> bBa | ba

Use set notation to define L(G).

So I came across two different answers to this question, none of which are mine, and then compared them to mine. I'm wondering if they are all equivalent.

Answer 1: $L(G) = \\{a^{n\_1}b^{n\_1}...a^{n\_k}b^{n\_k}b^{m\_1}a^{m\_1}...b^{m\_l}a^{m\_l} | n\_i, m\_j \> 0, l \ge 0, k \ge 0, k \le l\\}$

Answer 2: $L(G) = \\{(a^{n}b^{n})^i(b^{m}a^{m})^i | n \ge 0, m \> 0, i \ge 0\\}$

My answer: $L(G) = \\{(a^{n}b^{n})^k(b^{m}a^{m})^l | n, k, l \ge 0, m \> 0\\}$

My answer seems similar to the second one. Are all three of these correct for this grammar?

# Answer
They are not all equivalent.

Strings in the expression $(a^nb^n)^k$ have several (i.e., $k$) copies of the *same* string $a^nb^n$, whereas in $a^{n\_1}b^{n\_1}\dots a^{n\_k}b^{n\_k}$ the number of letters in each $a^{n\_i}b^{n\_i}$ may differ.

As $aaabbbaaabbbaaabbb$ versus $aabbaaaabbbbab$.

A shorter way of denoting words with different numbers would be $\\{ a^nb^n \mid n\ge0\\}^\*$.

Now check out your three languages and the given grammar.
> 3 votes

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


# Question
Title: Analyzing time complexity for change making algorithm (Brute force)
I'm new to analyzing time complexities and I have a question. To compute the nth fibonacci number, the recurrence tree will look like so:

Since the tree can have a maximum height of 'n' and at every step, there are 2 branches, the overall time complexity (brute force) to compute the nth fibonacci number is `O(2^n)`.

Now, looking at the coin make change problem. If the coin denominations are `[1, 5, 10, 25]` and the input number to make change for is `'C'`, the recurrence tree should look something like this:

In this case, the tree can have a maximum height of `'C'` and the number of branches per step is 4 (The number of coin denominations we are given. Let's call this `'n'`). With that being the case, shouldn't the time complexity be `O(n^C)`. I read everywhere that the time complexity is `O(C^n)`. Can someone please explain?

# Answer
First, when computing the $n$-th fibonacci number $F(n)$, the number of branches (leaves) is not $2^n$, but exactly $F(n)$. But you can say it is $O(2^n)$.

As for the coin change problem it is not $O(n^C)$. $n^C$ is a polynomial, while the number of branches in the tree grows exponentially. In other words, given $n$ number of coin denominations and constant $C$, each node has no more than $C$ children, and so the number of branches/leaves is at most $C\times C\times \dots C$ ($n$ times). In fact the actual number of branches is less than $C^n$, but is definitely bounded from above by $C^n$, and so is $O(C^n)$ (recall that big-O denotes the upper bound of a function).
> 6 votes

---
Tags: algorithms, time-complexity, asymptotics, recurrence-relation, coin-change
---


# Question
Title: Best Algorithm for searching for an index in an array such that A[i] = i
Recently i got a question in one of my exams about asking for an algorithm which searches an element in a sorted array such that $A\[i\] = i$. My algorithm was based on binary search and did a $O (\log n)$ order of comparisons. The other part of question demanded to prove there exists no other algorithm which does better than this. I tried to design an adversarial argument but it didn't seem to go in the correct direction. How can one go about proving this with an adversary argument , if one exists. Other approaches to proving this are also welcome. My algorithm works as follows :

```
Search(A , start , end)
  Find mid
  if A[mid] > mid // the element with A[i] = i cannot exist in A [mid ... end]
    Search (A,start, mid-1)
  else if A[mid] < mid // the element with A[i] = i cannot exist in A [start... mid]
    Search(A,mid+1,end)
  else if(A[mid] = mid)
    return A[mid];
  else
    return false;
end

```

Edit: edit contains my algorithm. Kindly forgive any typesetting errors

# Answer
Notice that the index of the element of the array requires $\Omega(\log(n))$ bits to represent. This means that there can be no better algorithm than $O(\log(n))$ to find this index.

Edit: To elaborate a bit, what you have is a binary search algorithm which works in $O(\log(n))$. What you want to prove is that any other algorithm for the same problem will work in no less than $O(\log(n))$. The proof involves information theorethic reasoning, since storing $n$ different numbers (the indices of the array) requires each to be represented by no less than $\log(n)$ bits. Now we can see, that in order for you to output/write the solution you need $\Omega(\log(n))$ bits, and you cannot do away with less (we can apply the same reasoning to comparisons since we need to compare $\log(n)$ bits to deduce whether one number is less than the other if they are the same on all but the last bit) This means that any algorithm will need atleast $O(\log(n))$ operations to produce output.

Now, obviously, since you have produced an algorithm working in $O(\log(n))$ then the bound is sharp.

to answer your question in the comment to this answer:

```
this information of log n bits on index is valid on unsorted array as well? why do we not have an algorithm to search an unsorted array in log n time? kindly elaborate whether or not is this valid for both ordered and un-ordered arrays?

```

while this is true for both unsorted and sorted arrays, it merely specifies a lower bound on the complexity of algorithms. This means that no algorithm can do better than $O(\log(n))$. It does not guarantee that there exists one though.

In an unordered array there are extra complexities that arrise, which prevent an $O(\log(n))$ solution. So we might say that the $\Omega(\log(n))$ is not *sharp* in this case since there does not exist an $O(\log(n))$ algorithm which could solve this problem for an unsorted array.

If we were to find a sharp lower bound for the unsorted array problem then we would need to use different assumptions and conduct a different analysis.

An important thing to realise is that this is all dependent on the underlying model of computations used. Is it assumed that comparisons take $O(1)$? How about writing a number to memory? If this is not defined then estimating complexity is tricky to say the least.
> 4 votes

---
Tags: algorithms, lower-bounds, binary-search
---