# Question
Title: Perfect matching in a bipartite regular graph in linear time
Given a $G=(V,E)$ bipartite, undirected, 4-regular graph, I would like to find a perfect matching in linear time.

It is easy to show that there is a perfect matching for the graph, by using flow and showing a flow of size $|V|/2$.

Using flow networks, we can also use Dinic's algorithm to find the max-flow which is equal to the perfect matching (thus, deriving a perfect matching) in $O(|E|\cdot\sqrt{|V|})=O(|V|^{3/2})$ (Since $E=O(|V|)$).

Can we find a perfect matching in linear time?

Thanks!

# Answer
> 5 votes
There is a classical linear time algorithm of Gabow and Kariv.

The first step is to find an Eulerian tour. You do this by starting at an arbitrary vertex and following an arbitrary path until you close a cycle. If you're not back where you started, you continue following an arbitrary path until closing a cycle, and so on. If you are back where you started, you find another vertex which has unused edges, and start a new walk from there. Eventually, you will have decomposed all edges into cycles. If you're careful, you can implement this algorithm in $O(n)$; see Wikipedia for hints.

Since the graph is bipartite, all cycles have even length. Remove from each cycle every other edge to obtain a bipartite 2-regular graph. Now repeat the same process to obtain a perfect matching.

This algorithm works more generally for $d$-regular graphs whenever $d$ is a power of 2. It runs in time $O(m)$ even for non-constant $d$ (here $m$ is the number of edges). Cole, Ost, and Shirra devised an $O(m)$ time algorithm for any value of $d$, Alon devised a simple $\tilde{O}(m)$ algorithm for the same problem, and Goel, Kapralov and Khanna gave a randomized $\tilde{O}(n)$ algorithm in the same setting.

---
Tags: algorithms, graphs, network-flow, matching, bipartite-matching
---


# Question
Title: How do I check if two if-stmt blocks are the same?
Consider the following two snipets of code:

```
If a >= 5:
   If b == 0:
     ....
   Else:
     ....
Else if a <= 5:
   ....

```

---

```
If a > 5:
   ....
Else If a >= 5 and b == 0:
   ....
Else If a >= 5:
   ....

```

Then these two constructs are logically equivalent. I am interested if there algorithms that detects if two or more constructs are the same. Papers in this field are also welcome.

# Answer
Practically speaking, you can use an SMT solver for LIA (linear integer arithmetic) or its modular version to check whether two codeblocks are reachable under exactly the same circumstances. LIA only allows linear inequalities. Indeed, if you allow polynomials then the general (non-moudlar) problem becomes undecidable, though real-life integer arithmetic is bounded and so decidable.

As a pointer to the (extensive) literature, you can check this recent paper.
> 1 votes

# Answer
(Here, I am assuming that the statements are taken from a Turing-equivalent programming language, since this is the common case in practice.)

In the general case, we know this is not feasible. That is, we know that there exists *no* algorithm (not even an inefficient one!) that, given two statements, can always output whether they are equivalent.

This is one of the standard results that can be proved using computability theory. A short proof is that, if $equiv(s\_1,s\_2)$ were decidable, then we can choose any statement $s\_{\sf fixed}$ and obtain that the set $A = \\{\langle s1 \rangle \ | \ equiv(s\_1,s\_{\sf fixed}\\}$ is decidable. Indeed, to decide that, we can simply use a decider for $equiv(-,-)$ fixing its second argument to $s\_{\sf fixed}$. However, Rice's theorem proves that $A$ is not decidable.

This can also proved without Rice, e.g. using the fact that the halting problem is not decidable, and constructing a suitable reduction.
> 1 votes

# Answer
In this case, it would be quite simple: There are three relevant cases for a: a \> 5, a = 5, a \< 5. And two relevant cases for b: b = 0, b ≠ 0. Let's call the first three cases A, B and C, and the other two cases 1 and 2.

In your first example, the three statements are executed in cases A1 and B1, A2 and B2, C1 and C2. In your second example, the tree statements are executed in cases A1 and A2, B1, and the third one in case B2. Nothing is executed in case C1 and C2.

So obviously they are not equivalent. You might find some other conditions that turn out to be equivalent.
> 0 votes

---
Tags: algorithms, complexity-theory, computability, artificial-intelligence
---


# Question
Title: Number of binary search trees with maximum possible height for n nodes
I'm using the definition of the height of a tree as the longest possible path from the root to a leaf by its number of edges, e.g. a tree of 2 nodes has a height of 1. With that in mind, what would be the number of binary search trees (don't have to be balanced) that have the maximum possible height for n-nodes?

So far, I know that the maximum height of any binary search tree of n-nodes is n-1 since we're counting edges. So for example, a binary search tree of 3 nodes has a maximum height of `h = 3-1 = 2` and there are 4 possible trees with n-nodes that have the maximum height of 2.

I also know that for n-nodes, there are (2n)!/((n+1)!n!) possible trees.

I'm able to find this manually for trees where n is small but would like to find a formula for any n.

EDIT:
The BST definition I am working with defines a Binary Search tree as a binary tree where each node has at most 2 children and does NOT need to be nearly-complete, so you could have a tree of 3 nodes with a height of 2. It also satisfies the BST property where all nodes in the left subtree of a node x has keys smaller than x's key and all nodes in the right subtree of a node x has keys larger than x's key.

# Answer
> 2 votes
The number of trees with $n$ nodes of height $n-1$ is $2^{n-1}$. Indeed, every internal node has exactly one child, which can either be the left child or the right child. Since there are $n-1$ internal nodes, this gives $2^{n-1}$ options.

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


title: Why does soundness imply consistency?

text:
# Question
Title: Why does soundness imply consistency?
I was reading the question Consistency and completeness imply soundness? and the first statement in it says:

> I understand that soundness implies consistency.

Which I was quite puzzled about because I thought soundness was a weaker statement than consistency (i.e. I thought consistent systems had to be sound but I guess its not true). I was using the informal definition Scott Aaronson was using in his 6.045/18.400 course at MIT for consistency and Soundness:

1. Soundness = A proof system is sound if all the statements it proves are actually true (everything provable is True). i.e. IF ( $\phi$ is provable) $\implies$ ($\phi$ is True). So IF (there is a path to a formula) THEN (that formula is True)
2. Consistency = a consistent system never proves A and NOT(A). So only one A or its negation can be True.

Using those (perhaps informal) definitions in mind I constructed the following example to demonstrate that there is a system that is sound but not consistent:

$$ CharlieSystem \triangleq \\{ Axioms=\\{A, \neg A \\}, InferenceRules=\\{NOT(\cdot) \\} \\}$$

The reason it's I thought it was it was a sound system is because by assumption the axioms are true. So A and not A are both true (yes I know the law of excluded middle is not included). Since the only inference rule is negation we get that we can reach both A and not A from the axioms and reach each other. Thus, we only reach True statements with respect to this system. However, of course the system is not consistent because we can prove the negation of the only statement in the system. Therefore, I have demonstrated that a sound system might not be consistent. Why is this example incorrect? What did I do wrong?

In my head this makes sense intuitively because soundness just says that once we start from and axiom and crank the inference rules we only reach at destinations (i.e statements) that are True. However, it does not really say which destination we arrive. However, consistency says that we can only reach destination that are reach either $A$ or $\neg A$ (both not both). So every consistent system must include the law of excluded middle as a axiom, which of course I did not and then just included the negation of the only axiom as the only other axiom. So it doesn't feel I did anything too clever, but somehow something is wrong?

---

I just realize it could be a problem because I am using Scott's informal definition. Even before I wrote the question I did check wikipedia but their definition didn't make sense to me. In particular the part that they say:

> with respect to the semantics of the system

their full quote is:

> every formula that can be proved in the system is logically valid with respect to the semantics of the system.

# Answer
I recommend looking into formal logic beyond vague, hand-wavy descriptions. It's interesting and highly relevant to computer science. Unfortunately, the terminology and narrow focus of even textbooks specifically about formal logic can present a warped picture of what logic is. The issue is that most of the time when mathematicians talk about "logic", they (often implicitly) mean classical propositional logic or classical first-order logic. While these are extremely important logical systems, they are nowhere near the breadth of logic. At any rate, what I'm going to say largely takes place in that narrow context, but I want to make it clear that it is happening in a particular context and need not be true outside of it.

First, if consistency is defined as not proving both $A$ and $\neg A$, what happens if our logic doesn't even have negation or if $\neg$ means something else? Clearly, this notion of consistency makes some assumptions about the logical context within which it operates. Typically, this is that we are working in classical propositional logic or some extension of it such as classical first-order logic. There are multiple presentations, i.e. lists of axioms and rules, that could be called classical propositional/first-order logic but, for our purposes, which doesn't really matter. They are equivalent in some suitable sense. Typically, when we are talking about a logical system we mean a (classical) first-order theory. This starts with the rules and (logical) axioms of classical first-order logic, to which you add given function symbols, predicate symbols, and axioms (called non-logical axioms). These first-order theories are usually what we're talking about as being consistent or inconsistent.

Next, soundness usually means soundness with respect to a semantics. Consistency is a syntactic property having to do with what formal proofs we can make. Soundness is a semantic property that has to do with how we interpret the formulas, function symbols, and predicate symbols into mathematical objects and statements. To even begin to talk about soundness, you need to give a semantics, i.e. an interpretation of the aforementioned things. Again, we have a separation between the logical connectives and logical axioms, and the function symbols, predicate symbols, and non-logical axioms. What makes connectives connectives and logical axioms logical axioms from the semantic point of view is that they get treated specially by semantics while function symbols, predicate symbols, and non-logical axioms do not. The typical semantics for classical first-order logic is to interpret formulas as set-theoretic relations on some (power of a) set called the "domain" given as part of a particular semantics, and the connectives as the more or less obvious set-theoretic analogues, e.g. $\[\\!\[\varphi\land\psi\]\\!\]=\[\\!\[\varphi\]\\!\]\cap\[\\!\[\psi\]\\!\]$ where I use $\[\\!\[\varphi\]\\!\]$ as the interpretation of the formula $\varphi$. In particular, $\[\\!\[\neg\varphi\]\\!\]=D\setminus\[\\!\[\varphi\]\\!\]$ where $D$ is the domain set. The idea is a formula is interpreted as the set of (tuples of) domain elements that satisfy the formula. A closed formula (i.e. one with no free variables) is interpreted as a nullary relation which is to say a subset of a singleton set which can only be that singleton or the empty set. A closed formula is "true" if it isn't interpreted as the empty set. Soundness is then the statement that every provable (closed) formula is "true" in the above sense.

It is easy from here, even from the sketch I've given, to prove that soundness implies consistency (in the context of classical first-order logics and the semantics I've sketched). $$\[\\!\[\varphi\land\neg\varphi\]\\!\]=\[\\!\[\varphi\]\\!\]\cap(D\setminus\[\\!\[\varphi\]\\!\])=\varnothing$$ If your logic is sound, then every provable formula interprets as a non-empty set, but $\[\\!\[\varphi\land\neg\varphi\]\\!\]$ is *always* interpreted as the empty set no matter what formula $\varphi$ is, and so it can't be provable, i.e. your logic is consistent.
> 17 votes

# Answer
Soundness and consistency are properties of deductive systems. Soundness can only be defined with respect to some semantics that is assumed to be given independently from the deductive system.

In the realm of semantics the two properties are related

**Definition 1**(*Soundness\[Semantics\] -- borrowed from Wikipedia*) Soundness of a deductive system is the property that any sentence that is provable in that deductive system is also true on all interpretations or structures of the semantic theory for the language upon which that theory is based.

**Definition 2**(*Consistency\[Semantics\]*) A set of sentences $A$ in the language $\mathfrak{L}$ is consistent if and only if there exist a structure of the language $\mathfrak{L}$ that satisfies all sentences in $A$. A deductive system is consistent if there exist a structure that satisfies all formulas provable in it.

With the two definitions given above it is clear that soundness implies consistency. I.e. if the set of all provable sentences holds in all structures of the language then there exists at least one structure that satisfies them.
> 3 votes

# Answer
Your proof system is neither sound nor consistent, since $A$ is not a true proposition unless $A \equiv \top$, In which case $\lnot A \equiv \bot$ is not a true proposition. This argument shows that every sound proof system is also consistent.
> 2 votes

# Answer
Often when we come up with logical systems, they are motivated by an attempt to describe a pre-existing phenomenon. For example, Peano arithmetic is an attempt to axiomatize the natural numbers along with the operations of addition and multiplication.

Soundness can only be defined relative to the phenomenon you're attempting to describe, and essentially means that your axioms and inference rules really do describe the thing in question. So, for example, Peano arithmetic is sound because its axioms and inference rules really are true of the natural numbers.

This, of course, implies that you have a concept of "natural numbers" beyond Peano's definition of them, and some notion of what is true or false for the natural numbers without having derived these truths from any particular set of axioms. Trying to explain where those truths come from or how they can be verified can land you in philosophical hot waters. But if you take it as a given that there ARE natural numbers, and there is some collection of true facts about them, then you can view the axiomatization project as simply attempting to come up with a concise formal specification from which many of the most important truths can be derived. Then an axiomatization is sound if everything it can prove actually is in the pre-specified collection of truths, that is, if its properties and consequences match up with the interpretation you have in mind.

(Note in particular that your formal specification isn't going to prove *everything* that is true about the natural numbers, and moreover will not *uniquely* describe the natural numbers in that there are other structures, different from the natural numbers, in which Peano's axioms are also true.)

In first order logic, at least, a theory is consistent iff it has any models at all. Soundness means it has the specific model you wanted: the particular structure you were attempting to describe with your theory really is a model of your theory. From this perspective, it's clear why soundness implies consistency.

As an example of a theory that is consistent but not sound: Peano arithmetic, PA, is capable of encoding logical formulae as arithmetical constructions, and in particular you can encode the sentence "PA is consistent" ("there is no proof of falsehood from the axioms of PA"). Call this sentence Con(PA). You may also be aware that (since it is sound, and therefore consistent) PA can't prove Con(PA), by Gödel's first incompleteness theorem. This also means that the theory PA + $\neg$Con(PA) can't prove a contradiction, so it must be consistent. But it's not sound: it claims there exists a natural number encoding a proof of falsehood from the axioms of PA, but there can't possibly be such a number in the "real" natural numbers, since otherwise we'd be able to extract a genuine proof of the inconsistency of PA from it.

PA + $\neg$Con(PA) has models, but they're models which must include "extra" objects, "non-standard natural numbers", including one which it claims encodes the "proof" in question. The theory is simply not equipped with the necessary tools to distinguish these non-standard elements from the genuine bona-fide members of $\mathbb N$, or to demonstrate that the proof is not a legitimate proof.

You can alternatively interpret this as: PA + $\neg$Con(PA) is a perfectly legitimate logical system -- it just doesn't accurately describe the natural numbers, and the natural numbers aren't a model of it.

One more thing: we *don't* assume that axioms are true by definition. All axioms are by definition is just the basic building blocks of proofs. They're just claims: they're only true or false when applied to particular mathematical objects. You can have false axioms, it's just pretty silly, because your system will then necessarily and immediately not be sound.
> 2 votes

# Answer
To have a **concise** (and intuitive) answer I will paraphrase what Scott Aaronson said in his 6.045/18.400 MIT lecture. He said something like this:

> Soundness means everything provable is true. Since consistency means there are no contradictions and soundness already involved the concept of truth and truth must be consistent (i.e. True != False), then its must mean Sound systems are also consistent. So Soundness implies consistency because (truly) true things don't have contradictions.

Now that I reflect I realize that I had some incorrect assumptions/ideas:

1. I didn't realize soundness was about semantics. Thus, I failed to realize that just using inference rules from the axioms is not enough to lead to true consequences (and that it doesn't guarantee it, which I thought was impossible to reach contradictory things as long as we started from the axioms and used valid inference rules).
2. I thought that as long as the axioms were true and the inference rules made sense everything that proceeded would be true. Which I now realize might not be true since if we just have a giant list of axioms and inference rules its hard to reason if everything that follows will be true. i.e. just starting from an axiom and using a valid inference rule is not enough to guarantee that the next step will be true.
3. The previous is essentially coupled with the fact that I didn't realize that there are two levels of complexity, 1) semantics 2) syntactics. Cranking the symbols crunching game may lead to contradictions.
4. I didn't realize I didn't know the proper characterization of truth, which derek made a great job in characterizing.
> 1 votes

---
Tags: terminology, logic, first-order-logic, propositional-logic, incompleteness
---


# Question
Title: Is L={0,1}* without strings that start with 00 decidable?
Say you have a language L = "{0,1}\* without strings that start with 00". How do you prove this is decidable? I'm drawing a blank on this one.

# Answer
so turns out its decidable because its the regular expression $L = 01(0|1)$\*
> -1 votes

---
Tags: complexity-theory, undecidability, decision-problem
---


# Question
Title: UV Projection of 3D shape onto 2D images
Given a 2D image of a human face and the corresponding 3D shape, how do I project the shape onto the images to extract texture patches from them to form a partial UV map?

# Answer
I've accomplished this by positioning the mesh in a known position (such as the origin), placing the image in front of it so that from the camera's point of view they align as desired. Then it's simply a matter of shooting a ray from each polygon's vertices through the image towards the camera. Wherever the ray intersects the image, that's your `(u, v)` point for that vertex.
> 1 votes

---
Tags: computer-vision, graphics
---


# Question
Title: Utilization of static evaluation functions in chess
**Disclaimer: I'm *very new* to computer science & game programming**

I'm having trouble with understanding how to implement a static evaluation function in chess. The logic seems simple like just apply a weight to each piece on the board and subtract the pieces from each side, but its much more complex than that isn't it? You'd have to calculate a method of analyzing the board and each of the MULTIPLE actions that are occurring on the board at the same time (ie. Castling, checking pawns are being lost, if you're in check etc etc).

Is there a *relatively* simple way of implementing a static evaluation function to a chess board to "see" whats going on at each stage?

Side Note: I understand that you could implement things like Minimax (with $ \alpha - \beta$ pruning) searches onto the trees created via the static evaluation functions, so correct me if I'm wrong but whats going on is that $$ f(Board) = c\_1 * (thing 1) + c\_2\*(thing 2) + \cdots $$ but where do those $ \cdots$ end??? And from there, we get a number which we put in our tree then implement the minimax algorithm, to figure out the best move forward?

Are there any resources for this type of thing that I could possibly read? Thank you.

# Answer
There are simple ways to do so but it may not be a very good heuristic. For example going off of current piece valuation is very simple but leads to poor aggressive behavior. There are many other things to account for in addition to piece valuation like centrality and pawn structure that when included, is subjectively simple. See https://chessprogramming.wikispaces.com/Evaluation for more notes on evaluation and for general chess programming advice.

Regarding your side note: 'Those things' end based on your heuristic function. Yes you get a board valuation that is used to determine how good a move is, guiding your game tree search.
> 2 votes

---
Tags: game-theory, board-games
---


# Question
Title: How to do compare-and-increment different locations with in memory MVCC?
I'm reading the paper An Empirical Evaluation of In-Memory Multi-Version Concurrency Control which is about implementations of MVCC for in-memory databases. **Section 3.3** on **Two-phase Locking (MV2PL)** says:

> To perform a read operation on a tuple `A`, the DBMS searches for a visible version by comparing a transaction’s `T-id` with the tuples’ `begin-ts` field. If it finds a valid version, then the DBMS increments that tuple’s `read-cnt` field if its `txn-id` field is equal to zero (meaning that no other transaction holds the write lock)

Here is the image in **Figure 2c**:

The confusion point is about how it actually does this operation atomically: **Read location A (`txn-id`), if its value is equal to 0 then increment location B (`read-cnt`)**

Atomic operation in C/C++ does `compare-and-swap` only for a single memory location, however, in this case we are dealing with two memory locations. Is there any other CPU intrinsic for this operation, or another trick is employed?

# Answer
I asked the question directly from paper authors, and they replied to me:

> `txn-id` and `read-cnt` are 4-bytes each (not 8 bytes as I thought before), thus it is possible to compare-and-swap in one step.
> 1 votes

---
Tags: concurrency, database-theory, databases
---


title: Edge contraction in DAG

text:
# Question
Title: Edge contraction in DAG
I have a directed acyclic graph whose vertices are either red or black. I want to perform edge contraction between pairs of red vertices only, and avoid introducing cycles. The goal is to have the fewest number of red vertices remaining (and no cycles. Note that after edge contraction, the resulting self-loop is removed, it does not violate the no-cycles rule).

In the example below, I could merge vertices 1 and 3, or I could merge vertices 3 and 4, but I can't merge all 3 together, since this would introduce a cycle with black vertex 2.

I want to merge as many red vertices as possible, to reduce the number of nodes in the graph. How can I do this efficiently? I don't necessarily need an optimal solution (where optimal =\> smallest number of remaining vertices). I potentially have 100k nodes, evenly split red and black.

There are 2 optimal solutions for the simple example shown. Here is one.

# Answer
> 5 votes
Here are some pointers to one possible solution, taken from Google's TensorFlow XLA compiler.

Their use case is to partition a computation graph (usually a DAG) into subgraphs and place them on different devices, while satisfying data dependencies and maximizing each subgraph. For instance, in your question, assuming nodes must either be placed on CPU (red) or GPU (black), we would compute subgraph `Node{1, 3}` on CPU, and then compute `Node{2}` on GPU, and finally `Node{4}` on CPU.

The algorithm consists of two parts:

* Union-find for keeping track of node merging
    + Start reading from here, the main loop for contracting edges
* An "incremental cycle detection" algorithm

---
Tags: graphs
---


# Question
Title: What is the best algorithm for image comparison in terms of speed?
Problem domain - I'm implementing a home monitoring system using smart phones. At regular intervals rear camera of the phone takes images and compare them for a change detection. This change detection is done inside the android app itself. Only after a change is detected, image is sent to server.

I want to know a fast algorithm to compare two images and detect whether a significant change is occurred. I want to avoid changes due to light effects and negligible changes. So far I have come up with multiple options 1. Feature matching using SIFT 2. Comparing histograms 3. Template matching

But I'm not sure which one is more appropriate to my problem domain or whether there are better options.

# Answer
> 1 votes
> I want to avoid changes due to light effects

A similarity measure based on binary descriptor can deal with this issue since it designed for multimodal images.

Also, you can try correlation coefficient since it cloud be used for real-time applications. for more information visit this page. Hence this algorithm in Matlab as a function called `corr2` to find the degree of similarity between 2 images.

# Answer
> 0 votes
Personally, I'd read up on h.264 and its algorithms and figure out how it uses the previous frame to predict the next frame - that will find all the similarities between frames that there are. It will quite easily identify both changes between frames and motion.

---
Tags: algorithms, image-processing, computer-vision
---


title: Proof that n^2 = O(logn)?

text:
# Question
Title: Proof that n^2 = O(logn)?
DEFINITION: $f = O(g)$ if positive integers c and $n\_0$ exist such that for every integer $n$ $\geq$ $n\_0$, $f(n) ≤ c·g(n)$

so:

$n^2 \leq c·log(n)$

$\frac{n^2}{log(n)} \leq c$

is this enough proof? since the fraction will grow larger and larger depending on n\>1, so its false?

# Answer
> 4 votes
This is not "enough proof". The main problem of your proof is that it just lacks words. A proof should explain what you have in your head. So the first thing is to clearly states what you want to prove.

> We want to prove that $n^2$ is not $O(\log n)$.

Then you have to explain how you will do it:

> Assume toward a contradiction that $n^2=O(\log(n))$.

So you are going to do derive a contradiction from this assumption. We just apply definitions.

> By definition, it means that there exists $c, n\_0$ such that for every $n \geq n\_0$, $n^2 \< c \log n$, that is, ${n^2 \over \log n} \< c$.

Now you need to explain why this is absurd. There are many ways of doing it depending on what you assume the reader to be familiar with. One way to go is the following:

> It is well known that $\lim\_{n \rightarrow \infty}{n^2 \over \log n} = \infty$. Thus, there exists $n\_1 \geq n\_0$ such that ${n\_1^2 \over \log n\_1} \geq c$, contradicting the initial assumption.

Now, you conclude:

> Thus, $n^2$ is not $O(\log n)$.

If you think your reader is not familiar enough with limits you can then go more into details:

> We know that for every $n \in \mathbb{N}$, $\log(n) \leq n$. Tus, $n = {n^2 \over n} \leq {n^2 \over \log n}$. Thus, $n\_1 = \max(n\_0,c)$ verifies both $n\_1 \geq n\_0$ and $c \leq n\_1 \leq {n\_1^2 \over \log n\_1}$ which contradicts the intial hypothesis.

# Answer
> 3 votes
There is no constant $c$ such that $c \geq \frac{n^2}{\log {n}}$ for every $n\geq n\_0$. Hence, $n^2 \notin O(\log n)$

---
Tags: asymptotics
---


# Question
Title: Proof: Kolmogorov complexity of string concatenation
Does there exist a universal constant $c$ such that for any strings $x, y$, we have: $$K(xy)\leq K(x) + K(y) + c$$ where $K(\cdot)$ denotes the Kolmogorov Complexity of a binary string and $xy$ means the concatenation of $x$ and $y$? I know the answer to this problem is no but I am seeking a proof for this, any hint?

Update: for reference, this is stated at the top of page 266 in Sipser's famous book "Introduction to the Theory of Computation", third edition, and is listed as Problem 6.19 in the book. I've tried to prove it but didn't succeed, just curious to know what proof technique should be used in order to prove it.

# Answer
Kolmogorov complexity = length of shortest program to generate a string. Take the program generating x, add the fixed size code that makes it continue with a second program instead of halting, then add the second program generating y.
> 2 votes

---
Tags: complexity-theory, computability, kolmogorov-complexity
---


title: Context-switch between two processes

text:
# Question
Title: Context-switch between two processes
In response to a clock interrupt, the OS saves the PC and user stack pointer of the currently executing process, and transfers control to the kernel clock interrupt handler.

**Then** the clock interrupt handler saves the rest of the registers, as well as other machine state, such as the state of the floating point registers, in the process PCB.

Why these information are saved in 2 separate moments ? And what is the purpose of "PC and user stack pointer" ?

# Answer
> the OS saves the PC and user stack pointer of the currently executing process, and transfers control to the kernel clock interrupt handler.

This is not done by the OS, since the PC is still pointing to the process code. It is the CPU that performs this step, just before jumping to the kernel interrupt handler (hence modifying PC and SP), which can then save the rest of the state in the PCB.

Since the first step is implemented at a lower level (in the CPU hardware / firmware) it should be simple so that the CPU design does not require too much effort.

Saving registers is much simpler (cheap) when done at the assembly (OS) level, which requires less effort to design/code with respect to the CPU level. Hence, usually the CPU is made to save just enough to allow the OS to save the rest.
> 1 votes

---
Tags: operating-systems
---


# Question
Title: Why this Nondeterministic Finite accept this string?
I am reading in my book that this NFA machine accept the string 10100. If we follow the execution, we will find our self in branch with the state final q0.

The only answer for me is that when we are in state q0 after 1010 and 0 is coming we can't move any more so this branch will die even it is in the final state. Am I right?

# Answer
> 2 votes
When a transition doesn't exist for current (state, input) pair, the NFA halts and the computation path rejects the input string. Or if an empty string transition is defined, it can be used to go into a garbage state for undefined transitions and the computation path rejects the string. See What does an NFA do if there's no transition with the correct symbol? for really good information.

In addition, this source that says the string is not accepted: http://people.cs.nctu.edu.tw/~wgtzeng/courses/FL2013SpringUnder/2.%20Finite%20automata.pdf slide 15.

---
Tags: finite-automata
---


# Question
Title: Global optimization algorithm based on MapReduce
In the field of the intelligent swarm, there are many algorithms can find global optimization, such as Ant Colony Optimization (ACO), particle swarm optimization (PSO).

Is there any optimization algorithm implements using MapReduce which can run at Hadoop?

# Answer
Every algorithm can be implemented using MapReduce if you want.
> 0 votes

---
Tags: optimization, mapreduce
---


# Question
Title: Is there a name for "yield first result parallel map"?
# Context

In randomized algorithms two schemes of computation are common:

* Las Vegas algorithms with random running time
* Randomized algorithms that have a probability of success, and have to be executed multiple times before getting the answer

You can also transform the latter in the former with a loop but they really don't have the same properties (like an optimal restart sequence for Las Vegas algorithms), so I want to distinguish the two. It is also possible to have randomized algorithms that can fail AND that take a random amount of time.

# Parallelization with map

When parallelizing, it is common to use a map primitive: just execute those algorithms in parallel.

However, while waiting the answers from each of the nodes at each "batch", one loses tremendous amounts of time, for example if one instance of the algorithm takes much more time than the others: most processes will be idle. Of course, it is possible to group batches to avoid this situation, but then one will have to wait for the end of the batch which will take more time.

# "Yield first result parallel map"

The good solution would to be able to return the result in the parent node immediately when one node finds it, hence the name "yield first result parallel map". Then there should be a way to either stop directly the children (I don't know any clean way) or be able to use the free nodes while the busy ones finish their now useless computation. Maybe one should also be able to get those calculations back in a queue if they have a result.

Another way to express it would be "getting the results of a parallel map in an asynchronous queue".

Is this concept known? Does it have another name? Is it implemented somewhere (I implemented it in MPI but was wondering whether there are other implementations)?

# Answer
You might be able to achieve this in a system for distributed promises / distributed futures.

Some systems will have an operation `any` that does what you want: if `p1,p2,..,pn` are promises, then `any(p1,p2,..,pn)` returns a new promise `q` that resolves as soon as any of the promises `p1,..,pn` do. In other words, once the first promise resolves, `q` immediately resolves (with that value), without waiting for any of the other promises to resolve. See, e.g., promise.any in Javascript Q, Promise.any in Bluebird or Promise.any? in Concurrent Ruby.

That said, this is only half the story. When one promise resolves, what happens to the other promises? Do they keep executing or get terminated? The answer will probably depend on the specific system. If you're unlucky, all the other computations keep running, eventually the other promises resolve, and then their result is just thrown away. That'd be a waste.

However, if you're lucky -- if the system supports it, and the underlying scheduler is smart enough -- then perhaps the scheduler will terminate the computations associated with the other promises as soon as it is known that they are not needed. How could that be implemented? One way is that the implementation of `any` might cancel all of the other promises as soon as one of them resolves. The system could be designed to propagate cancellation transitively, and the scheduler could be implemented to terminate any in-progress computation that exists solely to resolve a promise that has subsequently been cancelled.

Ultimately, it's likely to be system-dependent whether the other computations are terminated or not in this situation, and you might need to test individual systems to determine whether they do what you want.
> 3 votes

---
Tags: randomized-algorithms, parallel-computing, mapreduce
---


title: File systems and writing one

text:
# Question
Title: File systems and writing one
I am going through the following series of lectures on OS development .

http://www.brokenthorn.com/Resources/

In the fourth tutorial , I came across the term " OEM" parameter block that stores the windows MBR and the Boot-record information whose soul purpose is to describe the file system on the disk .

And then on moving to the following tutorial ,by taking the authors promise to explain about it at a later opportune point , I came across the term "FAT" file system . And I could see that there were few terms in the parameter block like "bpbNumberofFATS" and "bpbsectorsperFAT" . "FAT" stands for "File Allocation Table" and it is a again a "filesystem" .

This got me confused as "OEM" parameter block is used to describe the filesystem on a disk . And if "FAT" itself is a file system , then that means and surely there are other file systems ,which could have been on that disk . Why will the "OEM" block predefine the file system in terms of "FAT".

On reading a bit about other file systems , I came across statements like "FAT was written by .." . And it further piqued me to ask , what does it mean to write a filesystem ?

So , basically I am confused about :

1. What exactly is a filesystem ? (Is it a kind of coordinate system to provide information about the storage of the contents of the file ?)
2. How is a file system written ?

3. There are a lots of other file systems , OEM is used to describe the file system on a disk , so why OEM has parameters concerned about FAT's ? And who sets the filesystem of a disk and how ?

# Answer
The MBR refers to the format used by (many but not all, and slowly being replaced by GPT) disk to identity partitions. A partition is simply a contiguous range of blocks on the disk. A partition is often used to store data, in the form of files and directories. But of course a disk knows nothing about files and directories. A file system is a system that controls how your data is stored on the disk. A file system is really two things:

* it specifies how the data is organized and accessed (directories, files, links, permissions, encryption, ...): this is the logical aspect
* it specifies how this data is encoded on the disk: this is physical aspect

There exists **many** file systems: FAT, exFAT, NTFS, ext, btrfs, HFS, XFS, ISO 9660 and others. FAT is a file system invented by Microsoft. What this means is that they designed the logical and physical aspects of it, and they applied and were granted a few patents on it. They also wrote the Windows driver for FAT, but note that anyone can do that (assuming the file system is properly documented and ignoring royalties issues) and indeed linux and MacOS have their own driver which follows Windows's specification.

Now as I explained a file system specifies how the data is encoded on the disk and FAT is not exception. The first sector of a FAT partition (also known as the boot sector, or super block) is what is described in the link you gave: is starts with 3 bytes for a jump instruction and is followed by the BIOS/OEM Parameter Block (which has a different format on FAT12, FAT16 and FAT32). **This OEM block is specific to FAT** and does not exist on other file systems. Other file systems use a different format. I might add that calling this the OEM/BIOS block was very unfortunate because it really has little to do with BIOS or OEM, but that was the name Microsoft came up with. It should really be called the FAT Parameter Block.

To finish, designing a good file system is hard because they are many trade-offs to make. FAT is simple and relatively robust, but sucks at about everything else if I may say. Sadly it is also the only file system that all OSes support and so is the de facto standard for interoperability.
> 2 votes

# Answer
## **OEM Parameter block**

The OEM block not only stores data about the *filesystem*, it also contains information about the *physical hard drive geometry*, or about how files are laid out on your hard drive or SSD. This was used by older BIOSes to determine how a hard drive was set up from the manufacturer. As a good primer for explaining hard drive geometry, I can suggest this chapter on pcguide.com , and this one

Important geometry parameters I can see are:

* **bpbBytesPerSector**: Which describes the sector size. This is basically the smallest unit of data that *anything* can write to the drive. It's usually 512 bytes, but newer large drives may use 1024 byte or larger sectors.
* **bpbSectorsPerCluster**: Which indicates how large a cluster is in # of sectors. A cluster is the smallest unit of data the *filesystem* can manage
* **bpbSectorsPerTrack**: The number of sectors per physical *track* on a hard drive

This method is, however an obsolete method of determining the size of a hard drive. Since the late 90s, Logical Block Addressing has taken over, which in itself is basically a direct method of counting and mappping every sector or block on a hard drive or SSD. However BIOSes and modern OSes still use it for legacy purposes.

To answer your Question # 3, FAT is the very first filesystem written for IBM-compatible PCs. This is likely a throwback to FAT 12 and 16 and earlier implementations of the OEM parameter block specification. As with many other HDD-related quirks in the IBM/x86 family it's likely that it's been left there for legacy purposes. Earlier FAT implementations (and fat12, still) could only write a single partition to a disk. Also, FAT partitions usually contain 2 allocation tables, the main table and a backup table for integrity and error-correction purposes.

## **What is a filesystem?**

Basically a means of getting disorganized data assigned into a system that can be understood by us, as well as the computer. Your assumption of it being a "coordinate system" for files is not inaccurate.

A very basic filesystem has to do the following:

* Map a given file to a set of sectors/clusters
* Provide a way to *distinguish* one file from the next (eg. start and end address)
* Provide a way for the user to locate needed data (eg. by a *filename*)
* Provide a way for *the rest of the hardware and software* to easily understand how data is to be read and written according to hardware and OS rules (abstraction layer, API, or what you prefer to call it nowadays)
* Provide a way to *protect* data and indicate that a given section of the HDD/SSD is occupied and other basic information or limitations (eg. write protect bit, file size, file attributes)
* Provide a way to remap data, so that the medium is used most effeciently

Optionally a file system also provides extra aids for improving reliability (by saving important data in multiple places or providing error correction mechanisms), speed (eg. by using search indexes), security (encryption, permissions) or user experience (Sorting files by using folders or providing easy access by using shortcut files or symbolic links)

It is very important to know, for all intents and purposes, that the way your file manager shows you the files is NOT the way the data is actually laid out on the drive. An effecient filesystem has to be able to *remap* data. For more on that, I suggest you read up on this very informative chapter
> 2 votes

---
Tags: operating-systems, filesystems
---


title: Connectedness of points on contour

text:
# Question
Title: Connectedness of points on contour
Consider a (smooth) function \begin{align\*} F: \mathbb{R}^2 \to \mathbb{R} \end{align\*} with the contour
\begin{align\*} \mathcal{C} = \\{x \in \mathbb{R}^2 | F(x) = 0\\} \end{align\*} The function (and possibly derivatives) will be given as analytical expression, and be continuously differentiable everywhere. I am trying to find an algorithm that takes two points $x\_1, x\_2 \in \mathcal{C}$ that are numerical roots of this function and tells me, if they lie on the same connected component of $\mathcal{C}$ (or maybe some more general set). I am a little lost here. I found some info on a (pretty complicated) algorithm that seemingly would allow me to first construct a graph representing $\mathcal{C}$ with accurate topology, and then I could just check to which connected component my points belong.

However, I don't fully understand the algorithm and it seems a little overboard for what I want to do. Does anyone know of an easier/faster algorithm to achieve this? Will I have to compute the full contour to solve this?

**Edit:** In case I really have to compute the full contours (or at least trace part of them) and there is no shortcut, my question would be: How can I compute the connected components of the contour? All sources I stumble upon already require me having a graph that encapsulates the correct connectedness informations and tracing seems problematic without any reliable "test" to find out if two points (e.g. one before and after some tracing step) are indeed on the same component. Ideally I would like an algorithm that constructs a function, say $G:\mathcal{C} \to \mathbb{R}$, such that $G(a)=G(b)$ iff $a$ and $b$ lie on the same connected component.

# Answer
If $F$ is continuously differentiable and smooth, you can use the gradient to walk along the contour. In this way you could walk on the contour starting at $x\_1$ (tracing both directions of the contour) and see if you reach $x\_2$.

In particular, if you're currently at a point $x \in \mathcal{C}$ on the contour, then the gradient $\nabla F(x)$ tells you what direction to walk if you want to stay on the contour: you should walk in the direction $(\nabla F(x))^\perp$, where we define $(a,b)^\perp = (b,-a)$. (In other words, you should walk in the direction perpendicular to the gradient.) In particular, when $\epsilon$ is sufficiently small, $x + \epsilon \cdot (\nabla F(x))^\perp$ will be approximately on the contour. This is because $\nabla F(x)$ points in the direction that most increases $F$, and if we're on a contour and the contour is a line, $\nabla F(x)$ points in a direction perpendicular to that contour. (See, e.g., https://math.stackexchange.com/q/599488/14578.)

So in principle if the contour was a simple line (whether closed or open), the following would be sufficient: start at $x\_1$ and walk in one direction and see if you eventually reach $x\_1$. In parallel, start at $x\_2$ and walk in the other direction and see if you eventually reach $x\_2$.

In practice there are two complications.

First, the contour is curved, so the gradient only helps you walk in a direction that is approximately along the contour -- but maybe not exactly. So, I suggest a refined way to walk at the contour. At you're currently at the point $x$, first to the point $x' = x + \epsilon \cdot (\nabla F(x))^\perp$. The point $x'$ might not be exactly on the contour, but it'll probably be close. Next, use gradient descent starting at $x'$ to find a point on the contour that is close to $x'$. If $F$ is everywhere positive, you might do this by minimizing the objective function $\Phi(x'') = F(x'') + c \cdot \\|x''-x'\\|^2$ where $c\>0$ is a sufficiently small constant; otherwise, you can use $\Phi(x'') = F(x'')^2 + c \cdot \\|x''-x'\\|^2$. If you have a better way to find the nearest point on the contour, go ahead nad use that. Finally, walk to this point $x''$. This gives you an adjacent point on the contour, that's approximately distance $\epsilon$ away from where you started. Repeat this.

The second complication is that the contour might not be a simple line; there might be places where two or more lines meet at an intersection. At this point, $F$ won't be differentiable and the gradient might not be computable or meaningful. You'll have to figure out how to detect that situation; perhaps you can use your domain knowledge about $F$ to help you detect that. If you have no other ideas, one possibility is to pick a dozen random points in the neighborhood of $x$, project each one to the nearest point on the contour, check the gradient, and see if all of them seen consistent with a single nearly-straight line or whether their appear to be multiple lines converging. Once you detect an intersection point, you can use depth-first search (basically, explore all directions out of the intersection point) to traverse the connected component -- then it reduces to the problem of checking whether two vertices in an undirected graph are in the same connected component, and that can be done using DFS.

This uses techniques that are quite similar to that proposed in my answer to your previous question on a 3D version of this situation.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Random file access in a block based file format
I am writing a program to store, retrieve and delete "blocks" of data of varying sizes.

The way it currently works is by keeping a database storing the locations of the blocks and the locations of free space in the file.

The file is split into pages such that in each page there are no two free chunk spaces next to each other (During a delete operation, any free chunks which are adjacent are merged into one bigger chunk)

The problem with this is that I am seeing horrible IO performance when removing a bunch of blocks and inserting new ones of different sizes (blocks range from 1k to about 200k and may be written anywhere in the file provided they fit in an existing free chunk in the file. If no such free chunk is found, a new page is created at the end of the file).

Can anyone suggest a way to improve on this, or maybe point me in the right direction?

# Answer
A starting point for this would be the heap management algorithms, start perhaps here. I remember Knuth in his Art of Computer Programming has a detailed discussion, I believe in volume 1. The algorithms described are good for RAM, adding in the non-uniform access of rotating disks will be quite a challenge...

Isn't it much simpler to use a database and blobs? Your time is valuable too...
> 1 votes

# Answer
As you mention writing to a normal **HDD** in your comment to your original post, the likely factor may be the way you write or remap the data.

Ordinary hard drives are based on storing and reading data off of rotating magnetic platters. The data itself is placed in "rings" on the platters.

Due to how they work, hard drives are most efficient if data can be read or written in a *sequential* manner. When reading or writing to *random* places in a file or in a file system, performance drops drastically with hard drives, as they have to wait (up to some 6-10+ *milliseconds per query*) until the next packet of data spins by the read/write heads.

There are many likely culprits, but a few may be

* the file you are working on is *itself* heavily fragmented. Try defragmenting the hard drive.
* Your method of searching for free chunks may be inefficient (and may also generate lots of random reads for the HDD, especially if you use a parallelized/multithreaded search approach)
* Your chunk/page/block size and/or method of reading/writing these generate a lot of overhead or random reads/writes , maybe because chunk/page size is too small (thus more pages/chunks to handle)
* your method of updating your database of pages/chunks may be dragging you down
* you may have a lot of (meta)data that is processed, even though it might not need to be.

One suggestion for optimizing performance and effeciency when used on HDDs would be to allow *fragmentation* of data blocks.

While the drawback is that you will have to write a "defragmenter" program (for future maintenance) and implement a block "jump" scheme.

The advantages you get are:

* Considerably more effecient use and allocation of disk space, as large blocks can be spread over numerous smaller areas of free chunks.
* Increased IO speed, as the read/write load is adapted to the hardware in use, and kept as sequential as possible

If you have major speed problems in your deletion step, don't actually delete the data (unless you actually need to)... disable the write protection (your "deletion" step) and overwrite these chunks with new data on the next write. This is the way that most filesystems and hard drives handle file "deletion" (and I ain't talking about trashcans :o) )
> 0 votes

---
Tags: efficiency, databases, filesystems
---


title: Why this division algorithm works?

text:
# Question
Title: Why this division algorithm works?
I found this problem on an algorithmic book. I have solve the requestments about time (O(n^2)) but I can't figure out how it works.

Input: Two n-bit integers x and y, where y ≥ 1

Output: The quotient and remainder of x divided by y

```
function divide(x, y)

    if x = 0:
        return (q, r) = (0, 0)

    (q, r) = divide(floor(x/2), y)

    q = 2 · q
    r = 2 · r

    if x is odd:
        r = r + 1

    if r ≥ y:
        r = r − y
        q = q + 1

    return (q, r)

```

# Answer
For even $a$ and $b \ne 0$ and integral division $$ \frac{a}{b} = \frac{2a}{2b} = 2 \cdot \frac{( a / 2 )}{b} $$ Similarly for the remainder $$a = 2 \cdot \frac{a}{2} \space (mod \space b)$$ Effectively transforming your problem of division of number with `n` bits into division of a number with `n-1` bits (half as big number).

The algorithm uses integral division in the `floor(x\2)` part and there you might lose `1` if `x` was odd. You're giving it back with the `if x is odd:` block to the remainder and since this might make your reminder the same size as `y` you need to check if that happened and change the values accordingly. (Notice that `r > y` can never happen and there could be just as fine `if r == y:`.)

You just do this `n` times where `n` is the number of bits of `x`.

Finally the algorithm is not $O(n^2)$ but rather $O(n)$ in the number of bits of `x`. That's assuming the `floor(x/2)` part does **not** call the `divide` function, because that would end in infinite loop (you would need e.g. compute `a/2` to compute `a/b` which would in turn need again computation of `a/2`. This can be avoided by using `a>>1` instead of `a/2` which also authomatically floors the result).
> 1 votes

---
Tags: algorithms
---


# Question
Title: Can proof by contradiction work without the law of excluded middle?
I was recently thinking about the validity of proof by contradiction. I’ve read for the past few days things on intuitionistic logic and Godel’s theorems to see if they would provide me answers to my questions. Right now I still have questions lingering (perhaps related to the new material I read) and was hoping to get some answers

(**WARNING**: you are about to proceed to read content with very confused foundations in logic, take everything with a grain of salt, its suppose to be a question and not an answer, there are many misunderstandings in it).

I think my main question is, once we showed that not A leads to some contradiction, so not A must be false, then we go and conclude that A must be true. That part sort of makes sense (especially if I accept the law of excluded middle as something that makes sense) but what bothers me is sort of how proof by contradiction actually occurs. First we start with not A and then we just apply axioms and rules of inferences (say mechanically) and see where that takes us. It usually reaches a contradiction (say A is true or $\neg \varphi$ and $\phi$ is true). The we conclude that not A must be false, so A is true. Thats fine. But my question is, what sort of guarantees do formal systems have that **if I applied the same process but started with A that I would not also get a contradiction there**? I think that there is some hidden assumption going on in proof by contradictions that **if similarly did the same process in A one would not reach a contradiction**, what sort of guarantees do we have that would not happen? Is there a proof that’s impossible? In other words if I had a Turning Machine (TM) (or super TM) that went forever, that tried all the logical steps from every axiom starting from the supposedly true statement $A$, what guarantees that it does NOT HALT due to finding a contradiction?

I then made some connections with my past question with Godel’s incompleteness theorem that goes something like this:

> A formal system F that con express arithmetic cannot prove its own consistency (within F).

This basically made it clear to me that if thats true then consistency i.e. guaranteeing that A and not A won’t happen is impossible. Therefore, it made it seem to be that proof by contradiction just implicitly assumes that consistency is guaranteed somehow (otherwise why would it just go ahead and conclude that A is true by proving not A is not possible if it didn’t already know that consistency and contradiction where fine, for any pair of statement A and not A)? Is this incorrect or did I miss something?

Then I thought, ok lets just include in our axioms the rule of excluded middle and then all problems are solved. But then I realized, wait if we do that we are just defining the problem away instead of dealing with it. If I just force my system to be consistent by definition that doesn’t necessarily mean it actually is consistent…right? I’m just trying to make sense of these ideas and I am not quite sure what to do but this is what I am realizing after a few days of reading stuff and watching videos in nearly every aspect of these concepts, contradiction, exclusive middle, intuitionist logic, Godel’s completeness and incompleteness theorems…

Related to this, it seems that its essentially impossible to actually directly prove that something is false without the rule of excluded middle (or contradiction). It seems that proof systems are good at proving true statements but to my understanding are incapable of directly showing that things are false. Perhaps the way they do it is more indirectly with contradiction (where they show something must be false or bad things happen), or excluded middle (where knowing the truth value of only one A or not A gives us the truth of the other) or providing counter examples (which basically shows that the opposite is true so indirectly uses law of excluded middle). I guess perhaps I really want a constructive proof that something is false?

I think if I could know that if I prove not A is false (say I accept contradiction) then that it really is ok and I don’t need to apply all the inference rules and axioms infinitely on A and I am guaranteed that A won’t reach a contradiction. If that were true then I think I could accept proof by contradiction more easily. **Is this true or do Godel’s second incompleteness guarantee I can’t have this?** If I can’t have this then, what puzzles me is how its even possible of so many years of mathematicians doing maths that we have not found a inconsistency? Do I need to rely on empirical evidence of consistency? Or for example, I prof F is consistent by showing superF proves F but since I will never actually need superF and just F, then I can’t be content that truly works?

---

I just noticed that my complaint also generalizes to direct proofs. Ok so if I did a direct proof of A then I know A is true...but how do I know that if I did a direct proof of not A that I wouldn't also get a correct proof? Seems the same question just slightly different emphasis....

# Answer
You asked (I am making your question a bit crisper): "What formal guarantee is there that it cannot happen that both $\lnot p$ and $p$ lead to a contradiction?" You seem to worry that if logic is inconsistent, then proof by contradiction is problematic. But this is not the case at all.

If logic is inconsistent then proof by contradiction is still very much a valid rule of reasoning, but so is its negation, and the rule which says that from $1 + 1 = 2$ we can conclude that you are the next pope. An inconsistency in logic does not invalidate anything: quite the opposite, it validates *everything*!

There is another possible source of confusion: the title of your question may be read as implying that the law of excluded middle says that logic is consistent. That is incorrect. Consistency of logic amounts to “it is not the case that both a statement and its negation have proofs”, while excluded middle is the rule which allows us to prove statements of the form $p \lor \lnot p$.

---

**Supplemental:** I do not understand why this question is generating so much discussion. I have trouble understanding what the dilemma actually is, and as far as I can tell, the question arises from some sort of misunderstanding. If someone can elucidate the question, I will be grateful. Also, I would just like to draw attention to the following points:

1. Proof by contradiction and excluded middle are equivalent to each other, and so the title, as written, is non-sensical. Of course we cannot have one without the other, they are equivalent.
2. From what I can understand from the lengthy discussion in the question, the OP seems to be saying, or worrying, that an inconsistency in logic invalidates a proof. This is false, as I pointed out above. I would appreciate some sort of a response from the OP: can the OP see how an inconsistency in logic (i.e., being able to prove everything) does not invalidate any proofs?
3. I find it likely, but cannot really tell for sure, that the OP thinks that the law of excluded middle states that it is impossible for both $p$ and $\lnot p$ to hold (with a formula: $\lnot (p \land \lnot p)$). This is not excluded middle. It is sometimes called the law of non-contradiction, and it is provable (without excluded middle).
4. The OP thinks it is "impossible to directly prove that something is false without excluded middle". He is confusing proof of negation and proof by contradiction, which are not the same thing. The linked post has plenty of examples of constructive proofs that something is false. In fact, most proofs that something is false found in textbooks are already constructive.
5. Gödel's incompleteness is dragged in for a reason that I can discern. Gödel's incompleteness provides a sentence $G$ such that neither $G$ nor $\lnot G$ is provable. This *does not* imply that $G \lor \lnot G$ is unprovable (it is, by a simple application of excluded middle)! Neither does it imply that $\lnot G \land \lnot\lnot G$ holds, or some such. So how is Gödel's incompleteness relevant here?

P.S. I apologize for the previous version of the supplemental which was rude.
> 30 votes

# Answer
There are many interesting philosophical points that your post touches on.

## Consistency of Boolean logic

The issue of consistency of proof theory in classical logic isn't as dire as you make it out to be. It basically reduces to the following:

> We can define Boolean logic as a collection of logical operations functions on the truth values `1` and `0`. But how do we know that `0≠1`?

(note that I'm simply using `0` and `1` as abstract symbols for the two truth values; in particular, I am not assuming any notion of integer here)

We, of course, don't *know* that `0` and `1` are different. But Boolean logic is so ridiculously simple that rejecting this possibility is an *extreme* level of skepticism.

But classical propositional logic reduces to this. Recall that we can assign Boolean values to the atomic propositions in any fashion, and this extends to assigning a value to all propositions that can be constructed from the atomic ones.

The statement "from `P` you can deduce `Q`" is literally just an ordering relation; it means the same thing as the claim that "`v(P) ≤ v(Q)` holds for every function `v` assigning truth values to the atomic propositions".

The rules of inference for propositional logic are precisely the properties for working with the ordering . Proof by contradiction, in particular, is the observation that if `P ≤ 0`, then `P = 0`.

And going back to your issue... if we knew both `P ≤ 0` and `¬P ≤ 0`,t hen after plugging in truth values we would ultimately conclude that `0=1`; that true and false mean the same thing.

So, if you have confidence that "true" and "false" mean different things, then you should have similar confidence in the consistency of Boolean logic.

## Proof by contradiction in intuitionistic logic

One should take careful note that proof by contradiction is better formulated as:

* If you can derive contradiction from `P`, then conclude `¬P`

In fact, one might outright *define* negation to be the connective with this property. E.g. in Heyting algebra you will usually see ¬P defined to mean P→0.

Note, in particular, the special case

* If you can derive contradiction from `¬P`, then conclude `¬¬P`

What you described as "proof by contradiction" comes from identifying `¬¬P` with `P`. Intuitionistic logic does not assume these are equivalent.

## Consistency as a formal contract

There are more computational formalisms for encoding logic; see simply typed lambda calculus, dependent types, and in particular the "propositions as types" paradigm.

Without going into detail, contradiction is basically treated as formal contract. There is a type, which I will call `0`, and there is the contract "these functions cannot be used to construct an element of type `0`".

If such a system is so bold as to allow you to construct a function `T → 0`, then if it is really holding to the contract, it means it is similarly impossible to construct any objects of type `T`. This is a computational viewpoint on what a proof by contradiction means.

Ultimately this isn't much different than, for example, a C function that returns a pointer promising not to return a null pointer, or a C++ function promising not to throw an exception.

And going full circle, back to classical logic, that's really what we're doing.

We are offered formal contracts, such as "from Peano's axioms, the rules of inference will not allow you to derive a contradiction". If this contract really is upheld, then if you were able to show that `¬P` implies a contradiction, then `P` cannot also imply a contradiction.

And if it were possible to violate the contract, we would simply say "Peano's axioms are inconsistent".
> 8 votes

# Answer
I think your question boils down to "when doing formal verification with some sort of formal logic, what sort of guarantee do I have that the logic is consistent?". And the answer is: none. That's something you have to assume. Formal verification doesn't eliminate all assumptions; it just helps you be clearer about what you are assuming, and maybe helps you ensure that you start from assumptions that seem reasonable.

If you work within a standard logic, generally most people are happy to assume the logic is consistent, even if they don't have a proof of that fact. It's true that we might someday discover that the logic is actually inconsistent... but most people believe this is not very likely.

In some cases one can prove that a logic is consistent, but that requires using another more powerful logic, where we have to assume that the second logic is consistent, so we still are left having to make some assumptions (assume that *some* logic is consistent). This could be taken as evidence that the first logic is likely consistent, if you believe that the second logic is likely consistent, but the reasoning has to bottom out somewhere -- there are some things we have to just assume, and cannot prove.

See, e.g., Hilbert's second problem and this discussion of the consistency of ZFC (and this and this and this and probably many more).
> 7 votes

# Answer
When used to guarantee the truth of a formal statement, all proofs implicitly assume the consistency of the system that they're based in. This is because if the system is inconsistent, the entirety of the system is broken, and all the work we did in that system is basically trash.

Because we can't prove that any system (or at least any complex system) is consistent within the confines of that system, we have to take it as an empirical truth rather than a formally provable truth. Basically, if mathematicians spend a long time working with a formal system and no contradiction is ever discovered, then that is empirical evidence in favor of the consistency of the system. In addition, we may use a more powerful system to prove the consistency of the system we're working with (although the consistency of this more powerful system would still be empirical - the buck stops somewhere).

At it's core, the situation in mathematics is identical to that of science. We build mathematics based off theories that seem correct based on all the information we have available about those theories, and like in science, you can't prove that a theory is correct; you can only prove it incorrect.

When we first started trying to base mathematics in set theory, we actually discovered that our first formulations of set theory were inconsistent because they allowed things like "let $S$ be the set of all sets that do not contain themselves." We had to throw out these formulations.

No matter which system of axioms we choose to base math on, there's always a danger that we'll discover a contradiction in that system. This is exactly why mathematicians don't introduce new axioms into mathematics: each new axiom has a chance of being incompatible with the axioms already in use, and all work that uses the new axiom would have to be completely re-evaluated.

**Addendum:** When I talk about a statement being true for a given system I mean that it cannot be disproven within that system if that system is consistent.
> 1 votes

---
Tags: logic, first-order-logic, propositional-logic, incompleteness
---


# Question
Title: Why the overall architecture of Android OS is a stack and why not any other data structure?
The overall architecture of the Android OS is a Stack. What specifically justifies Stack to design the overall architecture of Android? Are all mobile OS like Windows Mobile, iPhone OS developed as software stacks? If yes then why? Why not a queue, tree, graph, heap, etc.?

For more information and clarity to my question: The Android Software Stack

# Answer
> 1 votes
That's not what they mean by "stack". They don't mean a stack data structure. Rather, they are talking about a "software stack", which is an architecture for a system that is composed of multiple layers.

---
Tags: data-structures, stacks
---


# Question
Title: Checking if there is a single path that visits all nodes in a directed graph
```
Given a directed acyclic graph G, give a linear time algorithm to determine if the
graph has a directed path that visits every vertex.

```

You can assume you are given a list of nodes and two adjacency lists: Enter\[v\] which contains all the edges entering node v, and Exit\[v\] which contains all the edges leaving node v.

I was thinking that I could pick a node that doesn't have edges entering it and run DFS on it. During DFS, every time I get to a node with no children, I check if all the nodes have been visited. If not, I backtrack and explore a different path each time. If I make it back to the original node or if I hit a node with no children, I can check if I have seen all the nodes. If not, I return that there is no such path, else I have found a path.

Would this work?

# Answer
The problem is how to deal with visited vertex.

If you keep following, the time complexity is not linear because of repeated visiting. Otherwise, your algorithm will fail in the following simple example:

```
1 --> 2 -----------> 3 --> 4
        \         /
         --> 5 -->

```

The first search find `1-2-3-4`, then it goes back to `2` and find `1-2-5-3`. Now because `3` is visited, the search stops, and thus finally fails.

A hint (or answer) to solve the problem: performing a topological ordering firstly.
> 4 votes

---
Tags: graphs
---


# Question
Title: What do we call a greedy algorithm that tracks the best $n > 1$ solutions?
A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima.

To avoid this problem, we may keep track of the best $n \> 1$ solutions (instead of the best only). What is the name(s) of this algorithm?

Surprisingly, I can't seem to find the answer from Google. It'd be great if you could also list some resources on extensions to the naive greedy algorithm.

# Answer
You might be interested in beam search, which could be viewed as working in more or less this way.
> 1 votes

---
Tags: algorithms, optimization, terminology, greedy-algorithms
---


# Question
Title: Proving ambiguity of this Context Free Grammar
I ran into this exercise problem from ***Introduction To The Theory Of Computation*** by Sipser. Given a context free grammar:

$ S \rightarrow SS \ | \ T \\ T \rightarrow aTb \ | \ ab $

I have to show that the grammar is ambiguous. So I have to find at least two leftmost derivation of a string. I have tried a lot but have failed to come up with a counter-example. I think T describes the following grammar:

$ L = {\\{a^nb^n} \ | \ n \> 0 \\} $

But if I take $SS$, it is equivalent to taking $TT$, then it generates the strings like $ a^n b^n a^nb^n $, which is entirely different from L. So how can I come up with a string that has two leftmost derivation in this grammar. Any sort of help would be appreciated!

Below is the picture from the exercise.

# Answer
> 1 votes
The string $ababab$ has two different parse trees. In one of them the first two $ab$'s are grouped together, and in the other one, the last two $ab$'s are grouped together.

Stated differently, one parse tree corresponds to a derivation $S \Rightarrow SS \Rightarrow^\* ababS \Rightarrow^\* ababab$, and the other one to a derivation $S \Rightarrow SS \Rightarrow^\* Sabab \Rightarrow^\* ababab$. If you draw the parse trees for both derivations, you'll see that you get different parse trees.

Finally, here are actual two different leftmost derivations of $ababab$:

1. $S \Rightarrow SS \Rightarrow SSS \Rightarrow TSS \Rightarrow abSS \Rightarrow abTS \Rightarrow ababS \Rightarrow ababT \Rightarrow ababab$.
2. $S \Rightarrow SS \Rightarrow TS \Rightarrow abS \Rightarrow abSS \Rightarrow abTS \Rightarrow ababS \Rightarrow ababT \Rightarrow ababab$.

As an aside, an equivalent unambiguous grammar replaces the production $S \to SS$ by the production $S \to ST$ (or by the production $S \to TS$).

---
Tags: automata, context-free
---


title: Run Time of Nested Loop

text:
# Question
Title: Run Time of Nested Loop
In the following loop

```
for i = 1 to n
    doSomething O(1)
    for j = 1 to k
        doSomething O(1)

```

Is the runtime still $O(nk)$ even with the expression in the outer loop? Because if I change the order of the loops and $n \neq k$ then doSomething is executed a different amount of times.

# Answer
> 0 votes
The running time is $O(n+nk) = O(nk)$, where we are making the implicit assumption that $n,k \geq 1$. This is usually a reasonable assumption.

If we do allow $n$ and $k$ to be zero then the running time becomes $O(nk + n + 1)$.

Let me comment that there are several different definitions of big O, which are usually but not always equivalent. Here I am using the following definition: *$f(x\_1,\ldots,x\_m) = O(g(x\_1,\ldots,x\_m))$ if there exists a constant $C\>0$ such that for all integers $x\_1,\ldots,x\_m \geq 0$, it holds that $0 \leq f(x\_1,\ldots,x\_m) \leq C g(x\_1,\ldots,x\_m)$*.

---
Tags: loops
---


# Question
Title: Intuitive proof for Floyd's cycle detection algorithm
I am trying to understand Floyd's cycle detection algorithm. I can see why the algorithm works.

> When the Hare moves twice as fast as Tortoise, if there is cycle, they will meet definitely at some point in the cycle.

Is there any proof that proves the above point? I mean, without assuming that Hare and Tortoise meet at some point when Hare moves twice the speed of Tortoise and then proving.

In the wiki, I can understand the following paragraph.

> The key insight in the algorithm is that, for any integers $i ≥ μ$ and $k ≥ 0, x\_i = x\_{i + kλ}$, where λ is the length of the loop to be found and μ is the index of the first element of the cycle

But it is followed by the following point which I could not understand.

> in particular, **$i = kλ ≥ μ$, if and only if $x\_i = x\_{2i}$**. Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that is a multiple of λ

How does the author come to conclusion that **$i = kλ ≥ μ$, if and only if $x\_i = x\_{2i}$**

Can somebody please help me in understanding this?

# Answer
By definition, $x\_0,\ldots,x\_{\mu+\lambda-1}$ are all distinct, and for $i \geq \mu$, we have $x\_{i+\lambda} = x\_i$. Now let us prove the claim:

> Let $i \geq 1$. Then $x\_i = x\_{2i}$ if and only if $i \geq \mu$ and $i = k\lambda$ for some $k \geq 1$.

$\Longleftarrow$ Suppose that $i \geq \mu$ and $i = k\lambda$. Since $i \geq \mu$, we have $x\_{i+t\lambda} = x\_i$ for all $t \geq 0$. In particular, choosing $t := k$, we get $x\_{2i} = x\_{i+k\lambda} = x\_i$.

$\Longrightarrow$ Suppose that $x\_i = x\_{2i}$. If $i \< \mu$ then $x\_j = x\_i$ if and only if $j = i$. Since $2i \neq i$ (as $i \neq 0$), this contradicts the assumption $x\_i = x\_{2i}$, showing that $i \geq \mu$.

Since $i \geq \mu$, $x\_i = x\_{\mu + \[(i-\mu) \bmod \lambda\]}$. Similarly, $x\_{2i} = x\_{\mu + \[(2i-\mu) \bmod \lambda\]}$. Since $x\_\mu,\ldots,x\_{\mu+\lambda-1}$ are all distinct, it follows that $i-\mu \bmod \lambda = 2i-\mu \bmod \lambda$, and so $i$ is a multiple of $\lambda$.
> 3 votes

# Answer
The idea is to find the multiples of λ (the cycle length). if index i=kλ is the first node of the cycle or inside the cycle for some k≥0, Then any number of cycles after that will just get you to that same point. i.e a faster pointer will make mkλ loops. m being the ration of hare to tortoise speed.

m=2 is optimal as it makes least number of rounds. Tortoise will end up at index i=kλ and hare ends up at 2kλ, the same point.

Here is a good post https://ivanyu.me/blog/2013/11/24/finding-a-cycle-in-a-linked-list/
> 1 votes

---
Tags: algorithms, graphs, correctness-proof
---


# Question
Title: Given a regular language $U$, when does there exist $V$ such that $U^\omega$ = $\lim V$?
What I know is that $W = \lim V$ for some $V$ if and only if $W$ is the language of some deterministic buchi automata, namely that of $V$.

So, to attack this problem I tried to come up with some language of the form $U^\omega$ which cannot be determinized. But I keep failing trying to come up with something like this.

Is it true in general that given regular $U$, there is some regular $V$ such that $U^\omega$ = $\lim V$?

# Answer
Consider the language $$U = U\_1 \mid U\_2 = a\Sigma^\* \mid (\Sigma \setminus \\{c\\})^\* b$$ for the alphabet $\Sigma = \\{a,b,c,d\\}$.

Let $\mathcal{A}$ be a deterministic Büchi automaton for the language $U^\omega$ with $n$ states. For every $n \in \mathbb{N}$, the word $w\_1 = a(b^n c)^\omega$ should not be accepted, but the word $w\_2 = a(b^n c)^m b^\omega$ should be accepted for every $m \in \mathbb{N}$.

The word $w\_1$ should not be accepted because $U\_1$ can only be used once (as there is only one $a$ in $w\_1$), so in order for $w\_1$ to be be accepted by $U^\omega$, a subword match with $U\_2$ has to occur infinitely often -- but $U\_2$ cannot accept subwords with a $c$.

The word $w\_2$ should be accepted because $U\_1$ accepts $a(b^n c)^\*$, and $(U\_2)^\omega$ accepts $b^\omega$.

Now by a pumping argument, we can see that from a prefix trace for a, when reading $b^n$, an accepting state in the Buchi automaton should be visited at least once, as otherwise we have a rejecting loop for the word $ab^\omega$. But then an accepting state is visited at least once for $ab^nc$. By an induction argument, we can then show that for every $m \in \mathbb{N}$, a trace for $a(b^nc)^m$ needs to visit accepting states at least $m$ times. Similarly, a trace for $a(b^nc)^\omega$ visits an accepting state infinitely often, even though this word is not in $U^\omega$. Hence, the assumption that $U^\omega$ can be represented as a deterministic Büchi automaton is false.
> 1 votes

---
Tags: regular-languages, buchi-automata
---


# Question
Title: Finding the smallest string that contains a given set of substrings
The algorithm I am looking for has the following requirements: Input is a set of strings. You are looking for a string containing all input strings. The resulting string should be as short as possible. At least shorter than just concatenating all input strings if possible.

Examples:

```
Input: a ab bc
Output: abc

Input: abcd bcde ef
Output: abcdef

```

Is there a name for this problem with which it is better to search for solutions?

# Answer
This problem is called *shortest superstring problem*. John Gallant, David Maier and James Astorer proved it is NP-hard in 19791.

Given two strings $A$ and $B$, let $|A|$ denote the length of $A$, and let $S(A,B)$ denote the shortest superstring of $A$ and $B$ where $A$ occurs before $B$. It is easy to reduce this problem to travelling salesman problem, where nodes represent strings, and the distance from string $A$ to $B$ is $|S(A,B)|-|A|-|B|$. So you can use known algorithms for travelling salesman problem to solve this problem.

There are several polynomial approximation algorithms. The best known approximation factor is $2\frac{11}{23}$, and the corresponding algorithm is proposed by Marcin Mucha in 20132.

---

1Gallant, J., Maier, D., & Astorer, J. (1980). On finding minimal length superstrings. *Journal of Computer and System Sciences*, *20*(1), 50-58.

2Mucha, M. (2013, January). Lyndon words and short superstrings. In *Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms* (pp. 958-972). Society for Industrial and Applied Mathematics.
> 7 votes

---
Tags: algorithms, strings, substrings
---


title: Problems in Complexity Theory

text:
# Question
Title: Problems in Complexity Theory
I'm studying Complexity Theory. Many times i found written that in complexity theory every problem come in pair, that is a **search** version and **verification** version. But why this happens ? What establish this ?

# Answer
I'm not really sure what you refer to, but there is a basic translation between *function problems* and *decision problems*. In a function problem, we are given an input $x$ and our goal is to compute a function $f(x)$. In a decision problem, we are given an input $x$ and our goal is to determine whether $x$ belongs to some set $S$.

Given a function problem $f$, we can define an associated decision problem in which the input is a pair $(x,y)$, and the goal is to determine whether $y = f(x)$ (i.e., whether $(x,y)$ belongs to the set $\\{(x,f(x))\\}$.)

In the other way, any decision problem is a function problem whose output is True or False.
> 1 votes

# Answer
Every time somebody sets you some homework – "Find the answer to this question" – you hand in your answers saying, "I think the answer is this. Am I right?"
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Resolving NP problem with a deterministic turing machine
Im studying Complexity Theory and i have a question. What principle establishes that every NP problem can be solved by a deterministic turing machine in a exponential time ?

# Answer
> 1 votes
Transforming non-deterministic moves from a NDTM to deterministic moves in a DTM, needs exponential states to be explained. For example, a non-deterministic move can be done in $2$ different possibilities. Hence, the different combination of $n$ non-deterministic moves needs $2^n$ different deterministic computation path to be explained, as an instance.

# Answer
> 1 votes
Let's consider the problem of SAT:

> Given a propositional formula, determine whether it has a satisfying assignment.

SAT can be solved in exponential time by checking all possible truth assignment.

The Cook–Levin theorem shows that every problem in NP can be reduced to SAT in polynomial time, and this shows that every problem in NP can be decided deterministically in time $2^{O(n^C)}$ for some constant $C$ which depends on the problem.

Alternatively, we can think of a nondeterministic Turing machine as a deterministic Turing machine with an auxiliary input of polynomial length which tells it which computation path to choose. The original machine accepts an input if there exists an auxiliary input which causes the new machine to accept. We can generalize the exponential algorithm for SAT to this more general situation, by going over all possible auxiliary inputs. Since the auxiliary input has polynomial length, and since the deterministic machine runs in polynomial time, overall we obtain an exponential time algorithm.

---
Tags: complexity-theory
---


title: Complexity of a loop

text:
# Question
Title: Complexity of a loop
> If the body of a simple for loop has time complexity $O(n)$ and it is executed $n-1$ times what is the time complexity of the complete loop?

I am trying to figure out the correct answer to this question for my upcoming exam. My reasoning is that if the body of the loop is executed $n-1$ times and its complexity is $n$ then the complete loop should have time complexity of $O(n \times (n-1)) = O(n^2 - 2) = O(n^2)$.

However, the correct answer given to us is $O(n^3)$. Am I missing something or is it just a mistake in the answers?

**Edit**: It turns out that the answer given to us was just wrong...

# Answer
> 0 votes
As mentioned, the body of the simple loop is run in $O(n)$. As a loop iterates over the body $n$ time (probably), the time complexity of the loop is $O(n^2)$. When you run the loop $n-1$ times, the time complexity would be $O(n^3)$.

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


# Question
Title: Is there a contradiction between "set-theoretic" and "formal" definition of "Big-O"?
* $O(n) = \\{n, n^{2}, n^{1000000}, 2^{n}, ...\\}$ \[Source A\], \[Source B\]
* Say $t\_{n} \in O(n)$
* By formal definition $t\_{n} \leq k \cdot n$ \[Source C\]

But how can this be? Say $t\_{n}$ is actually $n^{2}$, then $t\_{n} \leq k \cdot n$ is just false. Would it not be more logical to have $t\_{n} \geq k \cdot n$ as a formal definition acompanying $O(n)$?

# Answer
> 3 votes
The first statement you made is not correct. $O(n)$ is the set of all functions $f(n)$ that are bounded above by some constant multiple of $n$ for sufficiently large $n$. The functions you have listed all belong to the set $\Omega(n)$ which is almost like $O(n)$ but instead of being bounded above by $k\cdot n$, this is the set of functions that are bounded *below* by $k\cdot n$ for sufficiently large $n$.

So, there is no contradiction. But you do need to look at your definitions a bit more carefully.

---
Tags: time-complexity, asymptotics, landau-notation
---


# Question
Title: Meaning of # in descriptions of languages
This is a very simple question, but I cannot find the answer anywhere, mostly because I don't know how else to ask about what I'm looking for. I have a homework assignment that has to do with pumping lemma, which asks me to use the pumping lemma to prove that the language given is not regular.

{x₁#x₂#x₃|x₁, x₂, x₃ ∈ {a, b}\* and x₂ = x₃ᴿ}.

My only question is this — what does the # mean? My teacher is currently unavailable, so I'm unable to ask him.

If someone has a link to a list of notations and their descriptions, I'd very much appreciate it, but if you're only able to tell me what # means, that's fine as well.

# Answer
> 3 votes
It's just a symbol in the alphabet, so the alphabet is $\\{a,b,\\#\\}$ and the language is the set of strings that:

* contain exactly two $\\#$'s and
* the string after the second $\\#$ is the reverse of the string between the two $\\#$'s.

---
Tags: formal-languages, regular-languages, pumping-lemma
---


title: Portfolio allocation with a few twists

text:
# Question
Title: Portfolio allocation with a few twists
*A similar question has been asked here, but this one is more complicated and has more constraints.*

I'm trying to find an algorithm to solve the following (real-life) problem:

A customer has $M$ amount of money each month that he wants to invest according to her preferred asset allocation. Example

* 60% stocks
* 20% bonds
* 20% REITs

She has a list of "favourite" financial instruments and a preferred allocation in each of the asset classes, e.g.:

* Stocks: C (60%) and AAPL (40%)
* Bonds: AGG (70%) and LQD (30%)
* REITs: VNQI (100%)

Now, the algorithm would provide an investment advice (how many units and what financial instruments to buy) according to the following constraints:

1. Total sum of purchases with fees cannot exceed $M$ (amount of money).
2. Units are integer and indivisible, you can buy either one or two stocks but not 1.5. Since the customer ivests small(-ish) sums, this constraint becomes important. Example: $M$ is \\$500 and AAPL is \\$173 per unit!
3. Main goal is fee minimisation (again, since the sum invested is not large, fees become relatively large). Instruments have different fees that not flat-rate. E.g.: fees for buying C are "\\$1 if transaction sum is \<\\$100, 0.30% otherwise", but for VNQI they're "\\$10 if sum \< \\$2000, 0.40% otherwise".
4. Second goal is allocation that is *approximately* close to the "model allocation" above. Note that the model is concerned with asset classes, not individual instruments. That means the customer can buy only C or only AAPLto attain the desired 60% in Stocks. However, remember that there's also a preferred allocation *within* an asset class; if we decide not to buy C this month, then we'll need buy more of it next time to keep the stocks in balance.
5. Fee minimisation can be attained by limiting the number of transactions. That means we can decide to buy, e.g., C, AGG and VNQI only, and think about buying AAPL and LQD next month. We can go even further and decide not to buy a whole asset class at all if the first solution has fees that are too high (above some pre-determined limit). In that case we'll remember that decision and buy more of it next month.

Now, I've been thinking about this for some time; I had my CS lessons over fifteen years ago, so had to rack my brain :) My first thought was of Bin packing problem. Nah. Doesn't really fit.
Then I remembered about Multi-dimensional unbounded knapsack. Again, not what I was looking for.
Considered Quadratic programming and Dantzig's simplex algorithm for linear programming. Not exactly fitting...

Maybe there is a special algorithm / special case for this kind of problem? Or shall I invent a new one? :)

# Answer
> 1 votes
I'd suggest using integer linear programming (ILP). You need to buy an integer number of stocks, so you can use integer variables to represent the amount of each stock you buy. ILP can express constraints (requirements that must be true). The main limitation is that the objective function you are trying to minimize must be a linear function of the variables, but that can often be accomodated with auxiliary variables. For instance, your rules about the fees for buying different stocks can be expressed with ILP.

You'll have to figure out how you want to quantify and formalize "allocation that is approximately close to the model", as currently that is rather vague. Also note that anytime you say you have two goals, you aren't ready to formulate this as an optimization problem, because that leaves open how you plan to trade off the goals. You need to identify a single objective function you want to minimize, which means you'll need to think how you want to combine fee minimization with approximate model allocation. We can't tell you how to do that as that is a matter of what you want to achieve. One way would be to sum up the absolute value of the deviations from the model, and require this to be no more than a certain maximum. Another way would be to sum up the absolute value of the deviations, and add that to the objective function as an extra penalty.

---
Tags: optimization, combinatorics, integer-programming, resource-allocation
---


title: Big O notation for recursive algorithm

text:
# Question
Title: Big O notation for recursive algorithm
In order to find Big O for a recursive algorithm, it is needed to know the stopping criteria of that algorithm. For the recursive algorithm to find Factorial of a number it is very easy to find the stopping criteria.

```
int fact(int n)
{
    if((n==1)||(n==0)) return 1;
    else retrun n*fact(n-1);
}

```

And we can make a mathematical definition of this problem as follow:

$ fact(n)= \begin{cases} 1,& \text{if } n = 1 \vee n=0\\ n\*fact(n-1), &{otherwise} \end{cases} \tag{1} $

Now my question is how is the correct mathematical definition for this algorithm:

```
void func(int n)
{
    if(n>0)
    {
        func(n-1);
    }
    else
    {
        print(n)
    }
}

```

Also, for the same algorithm if I change it as follow what is the stopping criteria and the mathematical definition of it?

```
int n = 5;
int rnd; // Random number between 0 and n
void func(n)
{
    if(n>rnd)
    {
        func(n-1);
    }
    else
    {
        print(n)
    }
}

```

Now the stopping criteria is random? So how can I define this in order to find Big O?

# Answer
For the first algorithm, you get the recurrence $$ T(0) = \Theta(1), \quad T(n) = T(n-1) + \Theta(1) \text{ for $n \> 0$}, $$ whose solution is $T(n) = \Theta(n)$.

For the second algorithm, the recurrence depends on $rnd$: $$ T(rnd) = \Theta(1), \quad T(n) = T(n-1) + \Theta(1) \text{ for $n \> rnd$}. $$ The solution to this recurrence is $T(n) = \Theta(n-rnd+1)$. The expected value of $T(n)$ (if $rnd$ is chosen uniformly at random) is $\Theta(n)$, since $\mathbb{E}\[rnd\] = \frac{n}{2}$.
> 0 votes

# Answer
Each recursive function should have some initial values to stop the computation. For the last two recursive functions, the program will not be stopped and trapped in an infinite loop or it has no meaning (for case 2, what is the value of $f(1)$?). Also, for the last case, if we have a random initial value, we can compute the complexity in average: $$\frac{1}{n}(n + (n-1) +\cdots+1)=O(n)$$ As Probability of each random value between $1$ to $n$ is $\frac{1}{n}$, the average complexity is $O(n)$, as shown in the above.
> 1 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, recursion
---


# Question
Title: Wrong DFA from NFA. String Does not contains 110
I am doing problem 1.g. My Approach is to first create a NFA that accepts this string i.e. all strings having 110. Then converting it into DFA and then complementing it. I have the answer what should I get however my NFA to DFA conversion doesn't work. I don't know why. Can anyone guide me. Thanks. Here is my NFA. Note this is not full answer as there is complement left to be done. But I am stuck in between.

Then I converted it into FSA

This is What I got

I know there is a mistake that there should be self loop of 1 on the AC state but from my above NFA, I am unable to obtain it. Is my NFA wrong? Or I have done some mistake in conversion.

# Answer
> 3 votes
Your third state is wrong. From state (AB) on input 1, the next state is not (AC), it is (ABC). Think about it - if you are in state A -or- B, on 1 you can go from A to A, from A to B, or from B to C.

# Answer
> 3 votes
I don't think you did the conversion correctly. You don't show your steps so I can't tell where you went wrong, but check your work again. If the NFA is in state A and it receives a 1, what states might it go to? If the NFA is in state C and it receives a 1, what states might it go to? So what state should the DFA (FSA) go to if it is in state AC and receives a 1?

There appear to be multiple errors in the conversion. For instance, the edge out of AB also looks incorrect.

Try applying the standard algorithm and running it by hand, one step at a time.

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


# Question
Title: timed automata - advance only in certain states
I am currently looking into timed automata for a project. I am thinking about a timed automaton where a clock only advances when the automaton is in a certain state. However, my little knowledge in the domain makes me wonder whether somebody already defined timed automata like that.

As an example: I.e. I have a timed automaton with two states: *L0* and *L1*.
My clock is *c* \- the total time that the automaton spent in time L1.

The clock *c* should only advance when the automaton is in state *L1*.

(see upper part of drawing)

**Solution with my existing knowledge (not very elegant):**

I can see a way where I could use event-clock automata (1) to achieve this, by triggering an event *a* and on entering *L1* the value of *c* is set to:
*c* := *c* \- xa
where *xa* is the time since event *a*. (See lower part of the drawing)

However, I'm not convinced of this solution as it is inelegant, further I'm not sure whether timed automata allow for the *setting* of clocks. So far I only read about *reset* to zero.

(1) http://pub.ist.ac.at/~tah/Publications/a\_determinizable\_class\_of\_timed\_automata.pdf

# Answer
So, after looking deeper into the subject I found the solution. Posting in case somebody else needs an answer and is unfamiliar with the subject.

What I was looking for is called a Stopwatch Automaton (SWA) and allows the time to stop or advance (by specifying the derivative of a clock `c' = {0, 1}`).
Reference: The Impressive Power of Stopwatches. Franck Cassez, Kim Larsen
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.669&rep=rep1&type=pdf

Further I discovered that Hourglass automata also allow time to stop, but additionally also to reverse: `c' = {-1, 0, 1}`. They however require the specification of a maximum clock value after which "all the sand passed through the hourglass" and the clock does not advance further.
Reference: Hourglass Automata. Yuki Osada, Tim French, Mark Reynolds, Harry Smallbone
https://arxiv.org/abs/1408.5965
> 2 votes

---
Tags: automata, real-time
---