title: What exactly is a logic?

text:
# Question
Title: What exactly is a logic?
An apology might be in due for asking another question about prerequisites, but I was confused about the starting points. I have come across various terms such as "Modal Logic", "Temporal logic", "First -order Logic", "Second order Logic" and "Higher order logic".

What exactly does "Logic" mean in this context? How do we rigorously define the word "Logic"?

After going through the beginning pages of few books I can roughly conclude that a "Logic is a way to decide what follows from what and is significant in designing programming languages as it dictates and facilitates designing of programs to automatically reason and understand programs. I want to understand about the second point in a bit elaborated manner.

Now coming to these logics.

Are all these logics, "temporal Logic", "Modal Logic", "First order Logic", "Higher order Logic" independent of each other or we need to understand few of these logic to understand a few others in this group? In a nutshell, what will be the prerequisites for them? (It will be great if I can get suggestions on some materials also.)

P.S : Thanks a ton for your kindness

# Answer
Fundamentally, a logic consists of two things.

* **Syntax** is a set of rules that determine what is and is not a formula.
* **Semantics** is a set of rules that determine what formulae are "true" and what are "false". To a model theorist, this is expressed by relating formulas to the mathematical structures that they're true in; to a proof theorist, truth corresponds to provability from a chosen set of axioms with a chosen set of proof rules (techniques).

The difference between different logics is, most simply, in the choice of syntax and semantics. Most logics are extensions of propositional logic or first-order logic. In a sense, you can see these extensions as "adding more features" to the logic. For example, temporal logics deal with truths that can vary over time.

In general, these features could be expressed in a simpler logic, at the cost of having to write longer formulas. For example, the temporal concept "$\varphi$ is true from this point for eternity" can be expressed in a first-order way by adding a time parameter to all your propositions and saying "For all times $t$, if $t$ is greater than or equal to the current time, then $\varphi$ is true at time $t$." In a sense, you can think of these logics as adding libraries to a basic programming language so you can say things more easily.

Since pretty much all logics are based on propositional and first-order logic, I'd recommend learning about those first.
> 40 votes

# Answer
While fields such as computer science, mathematics and physics are relatively well-organized, Logic has a chaotic history. Its organization is *really* confusing so I think it's important to read some history to understand the dense structure of the field.

The path you should choose will depend on your **background** and **aims**.

# What is a logic ?

1. The traditional point of view says that a logic is a formal system with a formal language (syntax), a semantic (external meaning, think of interpreters of programs) and a set of rules to deduce statements from other ones (think of the rules of reductions of programs). A logic is purely seen as a mere mathematical object.
2. The modern point of view, says, through the famous *Curry-Howard isomorphism* that a logic is a coherent type system (proofs are programs and types are formulas). More precisely : a system of inferences rules enjoying the cut-elimination theorem and the Church-Rosser theorem/confluence theorem implying that the underlying programming system will behave well.
3. About orders, propositional logic can be seen as a 0-order system (let's say that variables for propositions are noted $p, q$). They behave like function without arguments (constants).

* When we go to first-order logic, the variables for propositions become variable of predicates $P, Q$ and takes an *object* as argument $P(x\_1, ..., x\_n)$, $Q(x\_1, ..., x\_n)$. They behave like functions taking objects (pairs, integer, string) are arguments. Think of the *C* language.
    * In the second order logic, variable for predicates becomes kind of functions taking first-order ones. They behave like functions taking first-order functions as argument. For instance we can have predicates and quantification over predicates.
    * Same reasoning for third-order etc. Higher-order logics accept any order. Think of *Haskell* and *OCaml* which have functions taking functions of functions of functions etc as argument.
4. In general, there is no consensus about what a logic trully is. Some philosophers use systems which doesn't have a coherent underlying programming system. Actually, I would say that every field using Logic has it's own conception of logic. And most mathematicians probably don't care about what a logic is.

# The structure of the field

The history of Logic is too large so I will just give the structure of the field. The field of formal logic is splitted in : the philosophical, mathematical and computational use. Formal logic begin in the 19-20th century.

* You should study *propositional logic* and *first-order logic* first. They are the most standard ones. They were created to give a formal/mathematical account to the old logic of the time of Ancient Greece.

+ *Model theory* (semantics), study mathematical structures from the perspective of logic
    + *Proof theory* (syntax), independently, study proofs as a mathematical object.
* Second-order logic is an extension of first-order logic which is an extension of propositional logic. It is particularly interesting because arithmetics "live" in the second order (predicates on predicates with induction). Similarly, topology lives in the "third-order" (predicates on sets which can be seen as predicates themselves).
* Then came *L.E.J Brouwer* which splitted logic in two :

+ *Classical Logic* is the usual logic as defined a before. In particular, for all $A$, $A \lor \lnot A$ holds (excluded middle).
    + *Intuitionistic Logic* is a kind of logic rejecting the excluded middle and all equivalent laws (for technical and philosophical reasons I won't explain here).
* In other context, philosophers became interested in formal logic and thought it could answer philosophical questions (analystic philosophy). They made their own independent logical systems (paraconsistent logics, relevance logics, and modal logics such as deontic logics, temporal logics, epistemic logics, ...). Modal logics doesn't work with truth but with modalities such as possibility, necessity, time, knowledge. They are all independent of the above logics.
* The Curry-Howard correspondence gives a formal correspondence (isomorphism) between proofs and programs. Now a lot of logics could be seen as programming systems and vice-versa. Intuitionistic logic which was a bit ignored is now seen as a functional programming system ($\lambda$-calculus). It leads to the study of *Type Theory*. It is a currently active topic of research.
* Computer scientists wanted to verify and prove the soudness of systems in a formal way and it seems that modal logics are relevant. Today they use temporal logics and modal logics to reason on systems (see : formal methods, model checking). Systems are modelled through Automata Theory (for instance) and are verified using logical tools. It led to *Linear Temporal Logic (LTL)* and *Computational Tree Logic (CTL)*.
* In the same motivation, computer scientists wanted to verify the soundness and prove properties about programs. So we invented the *Hoare Logic* for imperative programs and more generally, *Separation Logics*.
* By studying, the Curry-Howard isomorphism, a new logic emerged : *Linear Logic* which restricts structural rules (weakening and contraction) seen as the erasure and duplication operating in proofs and programs. The potential infinity of truth are explicited. It seems that this logic is a generalization of classical and intuitionistic logic and gives a whole new conception of Logic based on computation and a procedural paradigm. It is mostly studied by computer scientists.
* Linear Logic also comes from what we call *Substructural logics* rejecting structural rules of Logic. Relevant Logic and Affine Logic are examples for such systems.

# Summary and path selection

* Any logic can be : propositional logic, first-order, second-order, third-order, ..., higher order (each extending the preceding one).
* We can add or remove rules to make variants of existing systems :

+ Remove excluded-middle : intuitionistic logic
    + Add modalities : modal logics
    + Restrict contradiction and weakening : linear logic
    + Remove contraction : affine logic
    + Remove weakening : relevant logic
    + Handle negation differently : paraconsistent logic
* Learn propositional and first order logic first and :

+ model theory, second order, higher order if you're interested in mathematics
    + proof theory, intuitionistic logic, second order, linear logic if you're interested in the foundation of computer science
    + modal logics, hoare logics, separation logics if you're interested in the verfication of systems and programs
    + modal logics, non-classical logics in general if you're interested in philosophy

# References (Books)

I personally recommend to mix references, if possible.

* **Mathematical Logic (Chiswell & Hodges)** : very concise and simple book to start with.
* **A first course in Logic (Hedman)** : a bit like the above one but give more details and take computability into account.
* **Handbook of Practical Logic and Automated Reasoning (Harrison)** : If you want to understand how some logic-related concepts are implemented in practice. More oriented to automated reasoning.
* **Logic in Computer Science (Huth & Ryan)** : very clear and oriented to computer scientists (verification of programs and systems, Hoare logic, practical use of modal logic, temporal logics, model checking).
* **Introduction to Proof Theory (Buss)** : an introduction to proof theory. It should be better to read this after some general logic.

# References (Wikipedia)
> 26 votes

# Answer
All of these logics are coming underneath of **Mathematical Logic**.

> Mathematical logic is often divided into the fields of set theory, model theory, recursion theory, and proof theory. These areas share basic results on logic, particularly first-order logic, and definability. In computer science (particularly in the ACM Classification) mathematical logic encompasses additional topics not detailed in this article; see Logic in computer science for those.

Moreover, if you want to know about the logic in general terms this article could be useful.

> Logic, originally meaning "the word" or "what is spoken", but coming to mean "thought" or "reason", is a subject concerned with the most general laws of truth, and is now generally held to consist of the systematic study of the form of valid inference. A valid inference is one where there is a specific relation of logical support between the assumptions of the inference and its conclusion.
> 0 votes

---
Tags: logic, mathematical-foundations
---


# Question
Title: Knapsack with non-overlapping rectangles
Given a large rectangle and a set $S$ of small rectangles each with a value $v\_i$. My problem is to find a collection of rectangles $T\subseteq S$ to put in the large rectangle so as to maximize the overall value $\sum\_{i\in T}v\_i$, subject to the constraint that the selected small rectangles cannot overlap with each other.

I suppose the problem is NP-hard. Can we design an approximation algorithm (PTAS or constant-factor approximation ratio) approaching the optimum?

# Answer
This problem is known as maximum disjoint set. In your case, assuming the rectangles are parallel to the axes, the problem is maximum disjoint set for axis-parallel rectangles. The problem is indeed NP-hard, but Wikipedia has an approximation algorithm with an approximation ratio of $O(\log \log n)$ if all values $v\_i$ are the same, or approximation ratio $O(\log n/\log \log n)$ for the general case where the values may differ for each rectangle. You can check out the citations there to find an entry point to the research literature.

I have not been able to find any lower bounds on what approximation ratio is achievable, so as far as I can tell, it is an open problem whether you can achieve a constant-factor approximation ratio for this problem.

If you're willing to relax the running time requirement, there is a recent result achieving an approximation ratio $1+\epsilon$, at the cost that the running time becomes larger than polynomial, namely, $2^{\text{poly}(\log \log n/\epsilon)}$. See arXiv:1307.1774 and arXiv:1608.0027.

In the case where none of the small rectangles are too small (i.e., each small rectangle has an edge whose length is at least a constant fraction of the length of corresponding edge of the large rectangle), this problem has a PTAS, i.e., $1+\epsilon$ approximation ratio is achievable. See arXiv:1703.04758.
> 1 votes

---
Tags: complexity-theory, approximation
---


# Question
Title: how can i proof $3^n$ has a greater growth than $n2^n$?
i want to prove that $3^n$ has a greater growth than $n2^n$ or $3^n = O(n2^n)$. but how can i do it mathematically? by induction or contradiction or other ways of proof.

# Answer
One simple way would be divide both sides by $2^n$ to get $n$ and $(1.5)^n$. You can simply take a limit of $l i m\_{n\to\infty} \frac{(1.5)^n}{n} = \infty$ To show that $(1.5)^n$ grows larger. This limit holds for any number larger than 1.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Is A times B of NP-complete languages A and B necessarily NP-hard?
If both $A$ and $B$ are NP-complete languages, would $A \times B$ be necessarily NP-hard? Here, $A \times B = \\{\langle u,v \rangle \mid u\in A, v\in B\\}$.

So my colleague's answer was no, it's not necessarily NP-hard because you can verify in polynomial time that $u \in A$ and the same for $v \in B$, but you see this is not the case I said, and when I tried to explain why this is wrong, I mumbled and stumbled because I suddenly came to realize that I don't really comprehend the concept to its full depth!

Any way I said if $\langle u,v \rangle$ was not NP-hard to decide, then also would the language $A$ for instance, because you can look at $A\times A$ as a reduction from $A$.

My question is, if I'm right what's my colleague's error and how to explain it, and if I'm wrong which I guess I'm not (this far I do know), then what's wrong about my theory?

# Answer
Yes, the problem remains NP-hard. Reducing to $A\times A$ doesn't exactly solve the problem, since you want to reduce to $A\times B$.

However, you can proceed as follows: since $B$ is NP-hard, then $B\neq \emptyset$. Thus, there exists $w\in B$. Fix such $w$. We now show that $A\le\_p A\times B$: given input $u$, the reduction outputs $\langle u,w \rangle$.

Clearly this can be done in polynomial time, since $w$ is fixed.

Now, since $w\in B$, then $u\in A\iff \langle u,w \rangle\in A\times B$, and we're done.

As for your question "where is my colleague wrong": you can indeed verify in polynomial time whether $\langle u,v \rangle\in A\times B$ if you are given witnesses for the membership of $u\in A$ and for $v\in B$. This shows that $A\times B\in NP$, but it has nothing to do with hardness.

Intuitively, membership in NP is an upper bound on the complexity, whereas NP-hardness is a lower bound.
> 7 votes

---
Tags: complexity-theory, np-complete, np-hard
---


# Question
Title: Why is a Fibonacci-Tree of rank 1 consolidated with one of rank n in this Fibonacci-Heap?
In the solution to problem 2 of this exercise sheet:

> The height of $n$-node Binomial Heap is always $O(\log{n})$. Show that this is not the case for Fibonacci Heaps by exhibiting, for any positive integer $n$ a sequence of Fibonacci-heap operations that creates a Fibonacci heap consisting of just one tree that is a linear chain of $n$ nodes.

it is stated that

> We obtain a chain with two elements where $x$ is the root, having degree $1$. Thus the chain of height two and the chain of height $k$ are consolidated.

However, in this presentation, it is stated that:

> Delete $\min$.
>
> * Delete $\min$; meld its children into root list; update $\min$.
> * **Consolidate trees so that no two roots have same rank**

which is not the case with $2$ and $k$.

So why are they consolidated?

# Answer
> 3 votes
Page 8 defines rank:

> rank(x) = number of children of node x

So rank is not the height of the tree. With that, each chain, regardless of its length, has rank 1 and will be consolidated with any other chain.

But in most cases, rank defines the height, so why is it different here? The Reason is, it is simpler to implement. For the number of children, you just need the size of the direct children of a node, in many cases just some `array.size`, often already saved in a field.

But for the height you'd need additional calculations and fields, which can get complicated, especially for functions like `decrease-key` (which would make it not O(1) anymore).

---
Tags: data-structures, heaps
---


# Question
Title: How does "main memory consisting of 1Gbytes", and "32 bit memory addresses" mentioned in the question below, relate to each other?
A computer system uses **32-bit memory addresses** and it has a **main memory consisting of 1Gbytes**. It has a 4K-byte cache organized in the block-set-associative manner, with 4 blocks per set and 64 bytes per block. What are the number of bits in each of the Tag, Set, and Word fields of the memory address ?

A block has 64 bytes hence the $Word/Byte$ field is 6 bits long. With 4\*64=256 bytes in a set, there are 4K/256=16 sets, requiring a $Set$ field of 4 bits.

This leaves 30-4-6=20 bits for the $Tag$ field.

# Answer
> 0 votes
A block has 64 bytes hence the $Word/Byte$ field is 6 bits long. With 4\*64=256 bytes in a set, there are 4K/256=16 sets, requiring a $Set$ field of 4 bits.

This leaves 30-4-6=20 bits for the $Tag$ field.

---
Tags: computer-architecture
---


title: Exact Analysis of the Merge Sort

text:
# Question
Title: Exact Analysis of the Merge Sort
When doing the "inexact" analysis of the Merge Sort, the literature that I have seen usually consider that the input is an array with a even quantity of numbers and the recurrence relation is:

$T(n) = 2T(n/2) + \Theta(n)$

But how I can formally prove that even if I consider any input, the complexity stays the same? While looking in the answers to the exercise **4.3-5** of the book Introduction to Algorithms on this site, he mention the recurrence for the odd sized input is as follow:

$T(n) = T((n-1)/2) + T((n+1)/2) + \Theta(n)$

And justifies that:

> However, shifting the argument in $n.log(n)$ by a half will only change the value of the function by at most $\frac{1}{2}\frac{d}{dn}(n.log(n)) = \tfrac{log(n)}{2} + 1$, but this is $o(n)$ and so will be absorbed into the $\Theta(n)$ term.

But I did not understand his justification very well. Somebody could explain to me?

(**Exercise 4.3-5**: Show that $\Theta(n.log(n))$ is the solution to the "exact" recurrence for merge sort.)

# Answer
Let us consider the recurrence $$ T(n) = \begin{cases} 1 & \text{if } n = 1, \\ T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n & \text{if } n \geq 2. \end{cases} $$ Using OEIS (A033156), we find that the exact solution to this recurrence is $$ T(n) = n(\lfloor \log\_2 n \rfloor + 3) - 2^{\lfloor \log\_2 n \rfloor + 1}. $$ Curiously, OEIS presents a different recurrence relation with the same solution: $$ T(n) = \begin{cases} 1 & \text{if } n = 1, \\ T(n-1) + \lfloor T(n-1)/(n-1) \rfloor + 2 & \text{if } n \geq 2. \end{cases} $$ The OEIS entry contains references to articles analyzing the recurrence in the context of divide-and-conquer, which you might find helpful if you want to analyze similar such recurrences.
> 5 votes

---
Tags: algorithm-analysis, runtime-analysis, sorting, mergesort
---


# Question
Title: Determining possible data structures given a set of required operations
This was an interview question that I was told is supposed to be an open ended discussion of the trade-offs. You have a collection of comparable objects and want to be able to do the following: 1. Lookup, add, delete objects 2. Get and/or extract Min, max objects 3. Objects should be unique (no duplicates)

A max-heap or min-heap almost fits the criteria except you can only have easy access to either min or max but not both. I ended up saying that if we know if one of max or min is more commonly needed, build a max or min heap.

A hash table is out of the question since the elements are un-ordered although it does have O(1) lookup.

What are the most appropriate data structure(s) in this scenario?

# Answer
* If there is no restriction on execution time or $n$ stays small then a simple unsorted array is always an option. It gives $O(n)$ execution time for all operations except adding an object and removing by swap-with-back-and-pop. As a less obvious bonus iteration over an array is very cache friendly so it will likely outperform nearly everything for small $n$.
* When you value lookup more than modification you can sort the array, lookups are now $O(\log n)$ and min and max are $O(1)$. But modifications are now $O(n)$ in all cases however they can be amortized a bit by using a small scratch array on the side that gets merged in periodically for additions and tombstone sentinels for removed elements.
* Using a min or max heap will reduce modification time to $O(\log n)$ at the cost of all other operations becoming $O(n)$ except the query for min or max depending on which it is. You can split the data into 2 using a selected pivot element where if smaller then elements get pushed into a min heap and if larger they get pushed into a max heap. Depending on the order of operation you may need to reselect the pivot element is the sizes of the heaps become too unbalanced.

Then there are the node-based solutions:

* Linked list (sorted or not) is not useful at all here, you still have $O(n)$ execution time for nearly everything like with unsorted array with additional cache miss and dependent-load costs during iteration and the only bonus you have is that insert and remove can happen in-place. I'm mentioning it here because:
* You can use a look-ahead list, essentially a sorted linked list with the addition that each node has a finger table of nodes that lets you skip ahead in the list. modifications and lookups are now $O(\log n)$. However it has an element of randomness (how large each finger table is) that can potentially screw you over and regress performance to $O(n)$ for lookups.
* A balanced search tree isn't random in that way and every operation becomes $O(\log n)$ and correct implementation of the balancing routing can be tricky.
* you already mentioned why you don't like the hashtable though the $O(1)$ modification and lookup can outweigh the $O(n)$ cost for min/max. Though keep in mind that there are various ways of implementing one each with various benefits and drawbacks.

Those are the basic data structures I'd select between for holding a set of values. If there are other requirements and performance is a big enough issue then I'll go research more exotic options.
> 1 votes

---
Tags: data-structures, sets, dictionaries
---


# Question
Title: Direct conversion from regular expression to MSO
A language $L \subseteq \Sigma^\*$ can be described by a regular expression iff it can be defined by a formula in monadic second order with words as structure $(\\{0, \dots, n-1\\}, \<, (P\_a)\_{a \in \Sigma})$. The proof I know is an indirection construction over automata, i.e. we show that DFAs and regular expressions / formulas are equivalently powerful.

However, I am interested in a *direct* transformation process to make analysis of complexity properties easier. If I remember correctly, there is a construction based on the inductive nature of regular expressions and formulas, but I cannot find it. Just a link to a paper presenting these two algorithms (reg.exp. to MSO and back) would suffice for me.

# Answer
> 7 votes
The direction from regular expressions to MSO is easy, as MSO is versatile. For a regular expressions $R$ let us construct formulae $\varphi\_R$.

$\varphi\_{\emptyset} := \bot$

$\varphi\_{\varepsilon} := \forall x\bot$

$\varphi\_a := \exists x(P\_a x \wedge \forall y(x=y))$

$\varphi\_{R\_1 | R\_2} := \varphi\_{R\_1} \vee \varphi\_{R\_2}$.

$\varphi\_{R\_1R\_2} := \exists X(\forall y\forall z((Xy \wedge \neg Xz)\to y\<z) \wedge \[\varphi\_{R\_1}\]\_{Xx} \wedge \[\varphi\_{R\_2}\]\_{\neg Xx})$

$\varphi\_{R\*} := \exists X(\forall y\forall z(\neg z\<y\wedge(\forall x((\neg x\<y \wedge \neg z\<x)\to(Xx\leftrightarrow Xy))) \wedge \forall x((x\<y\wedge(Xx\leftrightarrow Xy))\to\exists x'(x\<x'\wedge x'\<y\wedge\neg(Xx'\leftrightarrow Xy))) \wedge \forall x((z\<x\wedge(Xx\leftrightarrow Xy))\to\exists x'(z\<x'\wedge x'\<x\wedge\neg(Xx'\leftrightarrow Xy)))) \to \[\varphi\_R\]\_{\neg x\<y \wedge \neg z\<x})$

Here, $\[\varphi\]\_{\psi(x)}$ denotes the relativization of the formula $\varphi$ to the formula $\psi$.

As you can see, the translation is linear.

In the other direction, I suggest to transform MSO to regular expressions in two steps, with NFAs in between. I know this is not what you are asking for. For complexity analysis it should suffice, however: The translation from MSO to NFAs is known not to have any elementary lower bound. And a direct translation to regular expressions cannot be any better, because of the linear translation from regular expressions to NFAs.

### EDIT

Fixed a bug in $\varphi\_{R\*}$. Also, here follows some explanation of the more complex formulae.

For $\varphi\_{R\_1R\_2}$, the predicate $X$ serves to separate the domain of $R\_1$ from the domain of $R\_2$. More precisely,

* $X$ shall hold on a (possibly empty) prefix of the word (The first clause says: all places where $X$ holds come before all places where $\neg X$ holds.).
* That prefix shall belong to $R\_1$ (the second clause does this).
* The remaining (possibly empty) suffix shall belong to $R\_2$ (the third clause says this).

For $\varphi\_{R\*}$, the predicate $X$ partitions the word into subwords each of which belongs to $R$. These subwords alternatingly belong to $X$ and to $\neg X$. The longish subformula between the $\forall y\forall z$ and the $\to\[\varphi\_R\]\_{\neg x\<y\wedge\neg z\<x}$ says that $y$ and $z$ are the start and end of such a subword:

* $y\leq z$ (first clause).
* All positions between $y$ and $z$ agree on whether they belong to $X$ (second clause).
* If an even lower position also agrees, then there is an intermediate one that doesn't (third clause).
* If an even higher position also agrees, then there is an intermediate one that doesn't (fourth clause).

---
Tags: regular-languages, logic, regular-expressions
---


# Question
Title: Advantage of using generating functions in analyzing an algorithm
I'm reading through the first chapters of "Introduction to the analysis of algorithm" by Sedgewick. I wasn't familiar with the use of generating functions, and complex analysis in general to analyse algorithms. I do understand the use of the tool is in practice simple (at least it seems to me in that way from what I read so far).

I still don't get though what's the particular advantage of using a generating function over standard techniques of difference equations when analysing some recurrence extrapolated by some algorithm.

What's the benefit of using generating functions?

I can also see "analytic combinatoric" as topic, I haven't read through that yet, what's the advantage of that formalism instead? Is there some case where analysing in that way is really easy while using standard technique isn't?

# Answer
Generating functions can be used to solve recurrence relations more complicated than linear recurrence relations with constant coefficients. As an example, let us consider quicksort (credit: lecture notes of Rezaul A. Chowdhury). Let us denote by $t\_n$ the average number of comparisons performed by quicksort when the pivot is chosen at random. We have $t\_0 = 0$ and for $n \geq 1$, $$ t\_n = n-1 + \frac{1}{n} \sum\_{k=1}^n (t\_{k-1} + t\_{n-k}) = n-1 + \frac{2}{n} \sum\_{k=0}^{n-1} t\_k. $$ Some work shows that the generating function $T(z)$ of the $t\_n$ is $$ T(z) = \sum\_{n=0}^\infty t\_n z^n = \frac{2\log \frac{1}{1-z} - 2z}{(1-z)^2}. $$ From this it is not hard to extract the formula $$ t\_n = 2(n+1)H\_n - 4n. $$

In this particular case, there are more direct ways to calculate $t\_n$. However, in more sophisticated situations, such tricks might not work. Furthermore, generating functions lead to mechanical manipulations - in fact, a software package can probably convert the recurrence for $t\_n$ to the generating function, and hence to the exact expression. In this sense, generating functions generalize linear recurrence relations with constant coefficients by providing a large class of recurrences whose asymptotics can be ascertained.
> 3 votes

---
Tags: algorithms, algorithm-analysis, recurrence-relation, generating-functions
---


# Question
Title: An exact solution for biclique vertex-cover problem on a bipartite graph
The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most "k" bicliques (complete bipartite subgraphs).

It has been shown that "Biclique Vertex-Cover" is not fixed-parameter tractable unless P = NP in Covering Graphs with Few Complete Bipartite Subgraphs.

Most of the work in the literature proved the hardness of the problem in general/special cases. However, *I need an exact algorithm for solving this problem on bipartite graphs*. An approximate algorithm with a guarantee is also good (I'm aware of "Clustering and the Biclique Partition Problem", but it provided an approx solution for "Biclique Vertex Partition" not vertex-cover i.e. the provided solution is for disjoint bicliques not possibly overlapped ones).

Is anyone aware of an exact algorithm for "biclique vertex-cover" problem? Potentially, with time complexity analysis?

A naive algorithm, perhaps, would be starting from the whole bipartite graph to check for a biclique that covers all vertices (covering with one biclique). If not successful, we check subsets by removing one vertex and investigate if there exist two bicliques in this set that cover all vertices (trying to cover with two bicliques), and so on (trying to cover with more bicliques until reaching "k").

# Answer
> 2 votes
If you have an exact algorithm for the partitioning problem (perhaps one is mentioned in the paper describing the approximate algorithm?), you immediately have an exact algorithm for the covering problem.

First, observe that a partition is a valid cover. Now suppose the partitioning algorithm reports an optimal partition with $k$ bicliques, and suppose to the contrary that there exists a cover $C$ with fewer than $k$ bicliques. But any cover can be turned into a partition easily: Whenever two bicliques in the cover contain the same vertex, delete the vertex from one of them. (This works because bicliques are *hereditary*: every induced subgraph of a biclique is also a biclique.most of the time, deleting a vertex from a biclique leaves another biclique; the only time where this would not be the case is when deleting the last vertex from one side of a biclique with 3 or more vertices, which would disconnect the graph. But the need to do so could only arise if some $(\\{u\\},V)$ and $(\\{u\\},W)$ are both in the cover, and in that case these two bicliques could be replaced with $(\\{u\\},V\cup W)$, contradicting optimality, so this cannot happen.) This will result in a valid cover with at most as many bicliques as there were originally (it may cause a biclique to have zero vertices: In that case, the original cover was not minimal). Repeat this vertex deletion step until all bicliques are pairwise vertex disjoint. If we apply this to the cover $C$, then because we started with strictly fewer than $k$ bicliques and never increased the number of them that we have, we now have a partition with strictly fewer than $k$ bicliques, contradicting the known optimal solution from the partition solver. Thus the optimal partition must have also been an optimal cover.

---
Tags: algorithms, graphs, approximation, set-cover, clique
---


# Question
Title: How do I find the size of Tag and line in bits?
In direct memory management, CPU references address of 15-bits. Main memory size is 512 * 8 and cache memory size is 128 * 8. What is the size of Tag and line in bits?

Block size=8=2^3

I have found the number of bits in the word field as follows, Block size=8=2^3 Therefore, word bits=3 bits

Now number of bits in line field is 7 (128=2^7) i guess.

# Answer
Main memory size of 512 doesn't make sense to me; it's too small for 15-bit addresses, and it also makes the cache of 128 appear huge being fully 1/4 of 512.

---

From the 15-bits in addresses, we subtract the 3 lowest bits because of the block size, leaving 12-bits of addresses to provide to the cache in order to lookup a byte or word.

With cache size at 2^7=128, and a block size of 2^3, the cache has 2^(7-3=4) indexes (aka elements, positions, blocks). (I take it that it is direct mapped, aka 1-way set associative).

So, out of the 12 bits provided to the cache, as 4 are index bits then remaining 8 are tag bits.
> 1 votes

---
Tags: computer-architecture
---


title: Complexity classes where $C^C = C$

text:
# Question
Title: Complexity classes where $C^C = C$
One possible motivation for studying computational complexity classes is to understand the power of different kinds of computational resources (randomness, non-determinism, quantum effects, etc.). If we look at it from this perspective, then it seems like we can obtain one plausible axiom for any attempt at characterizing which computations are feasible in some model:

* Any feasible computation can always invoke another feasible computation as a subroutine. In other words, suppose the programs $P,Q$ are considered feasible to execute. Then if we construct a new program by hooking $P$ and $Q$ up, so that $P$ makes subroutine calls to $Q$, then this new program is also feasible.

Translated into the language of complexity classes, this axiom amounts to the following requirement:

* If $C$ is a complexity class intended to capture which computations are feasible in some model, then we must have $C^C = C$.

(Here $C^C$ represents computations in $C$ that can invoke an oracle from $C$; that's an oracle complexity class.) So, let's call a complexity class $C$ *plausible* if it satisfies $C^C=C$.

My question: *What complexity classes do we know of, that are plausible (by this definition of plausible)?*

For instance, $P$ is plausible, since $P^P=P$. Do we have $BPP^{BPP} = BPP$? What about $BQP^{BQP} = BQP$? What are some other complexity classes that meet this criterion?

I suspect that $NP^{NP} \ne NP$ (or at least, that would be our best guess, even if we cannot prove it). Is there a complexity class that captures non-deterministic computation and that is plausible, under this definition? If we let $C$ denote the smallest complexity class such that $NP \subseteq C$ and $C^C \subseteq C$, is there any clean characterization of this $C$?

# Answer
$\mathrm{BQP}^{\mathrm{BQP}} = \mathrm{BQP}$ has been proved in Strengths and Weaknesses of Quantum Computing Bennett et al. (arXiv).

According to the complexity zoo, $\mathrm{ZBQP}^{\mathrm{ZBQP}} = \mathrm{ZBQP}$.
> 13 votes

# Answer
Here are some answers to some of the questions, but certainly not all of them:

Apparently, according to Wikipedia, we have $P^P=P$, $BPP^{BPP}=BPP$, $PSPACE^{PSPACE}=PSPACE$, $L^L=L$, and $\oplus P^{\oplus P} = \oplus P$. See also What is complexity class $\oplus P^{\oplus P}$, which observes that $\oplus P^{\oplus P} = \oplus P$.

Also, if $C^C=C$, then $C$ is closed under complement. Thus it is unlikely that $NP^{NP}=NP$: this would imply that $NP=\textit{co-}NP$, which seems unlikely. It looks like the smallest plausible complexity class that contains $NP$ is $PH$ (see Wikipedia).

I don't know what the situation is with $BQP$. I don't know whether there are other interesting examples of plausible complexity classes.
> 12 votes

# Answer
A complexity class $ C $ is called *self-low* precisely when $ C^C = C $. In general, "lowness" was studied a lot in the 80s and 90s -- google will uncover much for you.
> 6 votes

# Answer
This comment lists L (logspace), NC (polylog depth), P, BPP, BQP, and PSPACE as examples of self-low complexity classes.
> 4 votes

---
Tags: complexity-theory, oracle-machines
---


# Question
Title: Genetic Algorithm - Fit max circles inside box
I am using a genetic algorithm to find the best way to pack circles inside a box without each touching the others and filling as much space as possible. My doubt is if an individual from a generation must be a circle or all the circles.

Can anyone help me on how would I go from here? Thank you

# Answer
> 1 votes
In genetic algorithms, each individual should be a candidate solution to the problem. You're trying to find a packing of circles into the box, so each individual should be a complete packing that specifies the location of all the circles.

# Answer
> 0 votes
A few people hear are pointing out that in a GA, individuals should be complete solutions to the problem. That's generally true, but there are evolutionary methods that do the opposite. Within the field of Learning Classifier Systems, the two approaches corresponding to your question are called the Michigan approach (each individual is only one rule or circle) and the Pittsburgh approach (each individual encodes the entire set of rules or circles). Currently, Michigan approaches (namely XCS and its variants) dominate the field, so there is evidence that you can craft such algorithms successfully. More generally, there are coevolutionary methods that have similar ideas.

The only restrictions you really have on an evolutionary method is that you need to be able to go from genotype to fitness value in some way, and you need some ability to perform transformations on the genotype like mutation and/or recombination. Mutation and crossover don't necessarily give you trouble whether or not you have one circle per individual or one solution per individual. The only issue is how do you assign fitness to one circle? If you solve that problem, then you can build algorithms that use one individual per circle.

It's certainly easier to write a fitness function that takes the entire solution as one individual, but you can do it the other way. If this is something you want to pursue, look at how XCS works and look into cooperative coevolutionary algorithms.

---
Tags: genetic-algorithms, packing
---


# Question
Title: Is global non-convex optimization NP-complete?
Assume I have some non-convex function $f(x\_1, x\_2, ...)$ and I want to optimize it to find a global minimum. I feel like it is easy to show that this problem is in the class **NP** with the decision problem

*Is there a set of points such that f \< C?*

Where C is some constant. However, I am not sure if these problems are in the class of **NP-Complete**, and if so, what would you say the size of the input is? Complexity of the function?

Thanks!

# Answer
Yes, non-convex optimization is NP-hard. For a simple proof, consider the following reduction from Subset-Sum. The Subset-Sum problem asks whether there is a subset of the input integers $a\_1, \dots, a\_n$ which sums to zero. To reduce to non-convex programming, let $x\_1, \dots, x\_n$ be variables encoding the subset and consider the following non-convex program:

$$ \begin{align\*} \text{minimize }\quad&(a\cdot x)^2 + \sum\_{i=1}^n x\_i^2(1 - x\_i)^2\\ \text{subject to}\quad& \sum\_{i=1}^n x\_i \ge 1. \end{align\*} $$

Note that the optimum of this program is zero iff the Subset-Sum instance has a subset which sums to zero.
> 7 votes

# Answer
Quadratic programming is an example of a non-convex optimization problem that is NP-hard. See Transforming SAT to Quadratic Programming in polynomial time for a proof.
> 3 votes

---
Tags: optimization, np-complete, np, decision-problem, mathematical-programming
---


# Question
Title: Relative succinctness of NFAs and regular expressions
What is known about the succintness of NFAs, relative to regular expressions?

In order to clarify the question, let me explain what I know. The regular languages can be characterized by any of the following:

1. A language is regular iff it can be recognized by an NFA.
2. A language is regular iff it can be recognized by a DFA.
3. A language is regular iff it can be defined by an MSO formula.
4. A language is regular iff it can be described by a regular expression.

The family of languages $(\\{w\in\\{0,1\\}^\* \mid |w|\>n, w\_{|w|-1-n}=0\\})\_{n\in\omega}$ has NFAs with $n+1$ states. For DFAs, there is a lower bound of $2^n$ states. This family exemplifies that the translation from NFAs to DFAs necessarily incurs a worst-case exponential explosion of size.

In the other direction, there is no explosion, because each DFA is an NFA. Together, we can say that NFAs are *exponentially more succinct* than DFAs.

A similar result holds for the comparison of automata (either NFAs or DFAs) to MSO formulae: The formulae are non-elementarily more succinct.

I am aware that the translation from regular expressions to NFAs is linear and that there is an exponential translation in the other direction. Now to the actual question: Is it known that an exponential blowup cannot be avoided? What NFAs (or even DFAs) witness this? What techniques are used to prove non-existence of short regular expressions?

This question leads me to assume that divisibility languages are witnesses. That was what prompted the present question.

# Answer
> 5 votes
DFAs can be exponentially more succinct than regular expressions. A simple example is the language of all words over $\\{a,b\\}$ in which the number of $a$s and the number of $b$s are each divisible by $n$. This is accepted by a DFA of size $n^2$, but requires a regular expression of length $2^{\Omega(n)}$. For proof, see Example 23 in the survey From finite automata to regular expressions and back by Gruber and Holzer.

Gruber and Holzer improved this in their paper Tight bounds on the descriptional complexity of regular expressions, also mentioned in their survey (Theorem 24 of the survey). In fact, they prove an even stronger result (Theorem 8 of the paper): there is a language described by a regular expression of length $O(n)$ whose complement requires a regular expression of length $2^{2^{\Omega(n)}}$. (A regular expression of length $O(n)$ corresponds to an NFA having $O(n)$ states and so to a DFA having $2^{O(n)}$ states, whose complement has the same number of states.) The regular expression with this wondrous properties, over the alphabet $\\{0,1,\\$\\}$, is $$ (0+1)^{\geq 1} + (\epsilon + \Sigma^\*\\$)\bigl((0+1)^{\leq 4n-1}\\$ + (0+1)^{\geq 4n+1}\bigr)\Sigma^\* \\ \+ \Sigma^\*\\$(0+1)^{3n}(0+1)^\*0\Sigma^{n+1}1\Sigma^\* \\ \+ \Sigma^\*\\$(0+1)^{3n}(0+1)^\*1\Sigma^{n+1}0\Sigma^\* \\ \+ \Sigma^\*\\$(0+1)^\*0\Sigma^{2n}1\Sigma^\* \\ \+ \Sigma^\*\\$(0+1)^\*1\Sigma^{2n}0\Sigma^\* $$ We can even obtain an example over the binary alphabet $\\{a,b\\}$ using the homomorphism $$ 0 \mapsto abbb, \quad 1 \mapsto aabb, \quad \\$ \mapsto aaab. $$

The way all of these results are proved is via the concept of star height: a language of star height $h$ requires a regular expression of length $2^{\Omega(h)}$. Unfortunately lower bounds on the star height are rather difficult to establish, so instead one uses the more manageable cycle rank, a theorem of McNaughton identifying the two for a class of languages known as *bideterministic*. (For more details, consult either of the sources cited above.)

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


title: Master theorem for $T(n)=T(n-1)+O(n)$

text:
# Question
Title: Master theorem for $T(n)=T(n-1)+O(n)$
The recurrence of selection sort is $$T(n) = T(n-1)+ O(n).$$ Can we apply the master theorem to this recurrence? I am confused because the master theorem can be applied to the following recurrence

$$T(n) = aT(n/b) + f(n),$$

where $a \ge 1$ and $b \> 1$. But for selection sort, $b=1$. I am trying to apply the master theorem and stuck.

# Answer
> 7 votes
The master theorem isn't the appropriate theorem for *every* recurrence. As an example, your recurrence isn't of the type tackled by the master theorem, though it is easy to solve directly using the well-known identity $$ \sum\_{i=1}^n i = \frac{n(n+1)}{2} = \Theta(n^2). $$ You should think of the master theorem as a tool, not a liability. It is supposed to help you – use it if you need it, but feel free to use any other approach as you see fit. The only cases you absolutely *have* to apply the master theorem is when answering questions on a homework or a test that say you must use it; in the real world one tends not to limit oneself.

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Average Case Analysis for finding max and min value on an array
Given the following algorithm, to find the maximum and minimum values of an array - don't mind the language:

```
MaxMin(A[1..n])
    max = A[1];
    min = A[1];
    for (i = 2; i<=n; i++)
        if (A[i] > max)
            max = A[i];
        else if (A[i] < min)
            min = A[i];
    print(max, min);

```

I need to do a probabilistic analysis for the average case of comparisons that will be made on its execution.

So far, my solution is:

Given an indicator random variable: $$ X\_i = \begin{cases} \text{1, if max $\>$ $A\[i\]$}\\ \text{0, if max $\<$ $A\[i\]$}\\ \end{cases} $$

and assuming an uniform distribution for $A\[1..n\]$, the expected probability is: $$E\[x\] = \sum\limits\_{i=1}^{n} Pr(X\_i)$$

where $$Pr(X\_i)$$ is the probability of the *i-th* element be the $max$ element in $A\[1..n\]$. It's possible to determine that: $$Pr(x\_1) = 1, Pr(x\_2) = 1/2, Pr(x\_3) = 1/3 ,..., Pr(x\_n) = 1/n$$ and thus for an array of size $n$ the expected value can be calculated as:

$$E\[x\] = 1 + 1/2 + 1/3 + ... + 1/n = \sum\limits\_{i=1}^{n}{\frac{1}{i}} \approx \log{n}$$

And the same goes for $min$, which will give the same result $\log{n}$. (1)

My questions are: is it correct? Does the complexity for the average case of the given algorithm is $\theta(\log{n})$? Can I use the argument pointed by (1), just modifying $X\_i$ so: $$ X\_i = \begin{cases} \text{1, if min $\<$ $A\[i\]$}\\ \text{0, if min $\>$ $A\[i\]$}\\ \end{cases} $$

I already read this (unfortunately the link to the video isn't available), but it only explains for $max$ and my analysis must be for both $max$ and $min$.

# Answer
> 3 votes
First, note that the first comparison will *always* compare $n-1$ times, independent of the distribution of the input. So, what you really want to know is how many times the **second part** of the if compares. For this, you can use a indicator random variable like this:

$$ X\_i = \begin{cases} \text{1, if A\[i\] $\le$ $\max$}\\ \text{0, if A\[i\] $\>$ $\max$}\\ \end{cases} $$

So, just like you did, assuming an uniform distribution for $A\[1..n\]$, the expected probability is:

$$E\[x\] = \sum\limits\_{i=1}^{n} Pr(X\_i)$$

But we do not want $Pr(i=\max)$, we want $\overline{Pr(i=\max)}$, like we stated before. So, using your probability of the $i-th$ element to be the $max$ element:

$$Pr(i = \max) = 1/i$$

We have this complement:

$$\overline{Pr(i=\max)} = (1 - 1/i)$$

From which we can put in the expected probability:

$$E\[x\] = \sum\limits\_{i=2}^{n} (1 - 1/i) = \sum\limits\_{i=2}^{n}1 - \sum\limits\_{i=2}^{n}1/i = n - 1 - (\ln|n| - 1 + \Theta(1))$$

So, to get the total quantity of comparisons, we can just sum the number of comparisons of the two parts. Note that the $\Theta(1)$ can absorb a constant values.

$$(n - 1) + n - 1 - \ln|n| + 1 + \Theta(1) = 2n - 1 - \ln|n| + \Theta(1)$$

And we get the expected total number of comparions:

$$2n - \ln|n| + \Theta(1)$$

# Answer
> 1 votes
To answer your questions, I need to consider two cases:

**(1) You are looking for either min or max.** Then,

(1-1) is it correct? Yes, it is correct.

(1-2) Does the complexity for the average case of the given algorithm is $\Theta(logn)$? Indeed it is. My experience in practice is that it does not work that way (or at least the is a large constant involved).

(1-3) Can I use the argument pointed by (1), just modifying $X\_i$? Yes, you can do that too.

**(2) You are looking for both min and max.** Then, the scenario is different. You should have something like: $$ Z\_i = \begin{cases} \text{1, if max $\>$ $A\[i\]$ and min $\<$ A\[i\]}\\ \text{0, if max $\<$ $A\[i\]$ and min $\>$ A\[i\]}\\ \end{cases} $$

Then you can calculate $E\[Z\]$. It is also possible to calculate $E\[XY\]$, where $X$ is for max, and $Y$ is for min. Try different techniques and see which one works easier.

---
Tags: complexity-theory, algorithm-analysis, probabilistic-algorithms
---


# Question
Title: Definition of a reachable ancestor (Skiena TADM 2nd ed section 5.9.2)
In *The Algorithm Design Manual* section 5.9.2, covering graphs and articulation vertices, Steven Skiena writes

> Let reachable\_ancestor\[v\] denote the earliest reachable ancestor of vertex v, meaning the oldest ancestor of v that we can reach by a combination of tree edges and back edges.

This phrasing is ambiguous. On the errata page of his website, he clarifies:

> it is clearer to say: "denote the earliest reachable ancestor of vertex v, meaning the oldest ancestor of v that we can reach from a descendant of $v$ by using a back edge."

But to me, this phrasing is still somewhat ambiguous. Consider the following four-vertex graph G:

```
    A
    |
+ - B
|   |
|   C
|   |
+ - D

```

We conduct an alphabetical depth-first search (DB is a back edge). According to Skiena's revised definition, it would seem that A is a reachable ancestor of C as follows: D is a descendent of C, and we can reach A from D using a back edge by following the path DBA. However, execution of Skiena's code for finding articulation vertices via depth-first search on G results in reachable\_ancestor\[C\] = B, not A; therefore I don't think he intends for A to count as a reachable ancestor of C.

Might it be more accurate to say that reachable\_ancestor is the oldest ancestor of v that we can reach from a descendant of v by using a back edge but *without passing through any other ancestors of v*?

# Answer
> 1 votes
A small modification makes the definition agree with Skiena's algorithm. "Let reachable\_ancestor\[v\] denote the earliest reachable ancestor of vertex v, meaning the oldest ancestor of v that we can reach from a descendant of v by using *at most one* back edge."

If we view undirected edges as "two-way" directed edges, then to reach A from C would require two back edges: DB and BA. Thus the earliest ancestor that can be reached from C by using *at most one* back edge is B.

# Answer
> 1 votes
It seems that the term *reachable* is used in a rather confusing way. In general conception of graph theorists, *reachable* means that there is a path between two vertices; however, in this context, *reachable* means that there is a back-edge from a vertex in the subtree to one of the ancestors. The existence of such back-edge promises a loop that is free of any articulation vertex.

In my opinion, the use of *reachable* violates the general understanding of connectivity in graph theory. Therefore, Skienna must have revised this in a different way, using the right terminology.

Your reasoning is correct. I suggest you look at the algorithm in "Introduction to Algorithms", which have used "visit\_time" instead.

---
Tags: graphs
---


title: box bottom is valid

text:
# Question
Title: box bottom is valid
This question was posted to me:

What property of our relation $R$ between worlds must be true if we know that the following formula is valid?

$\square \bot$

I am completely stumped and have no idea what to do. Will appreciate any help.

# Answer
$\bot$ is false in every world. For any formula $\varphi$, the formula $\Box\\,\varphi$ is true in a world if $\varphi$ is true in every successor of that world. A formula is *valid* if it is true in every world.

So, $\Box\\,\bot$ being valid means that $\bot$ is true in every successor of every world. But $\bot$ can't be true in any successor. The only way that these two things can be true is \_________.

An alternative way to think about this is to consider that $\Box\\,\varphi$ is equivalent to $\neg\Diamond\\,\neg\varphi$.
> 1 votes

---
Tags: logic
---


# Question
Title: Regularity condition in the master Theorem in the presence of Landau notation for f
There already are many questions and answers about the importance of the regularity condition in case 3 of the Master Theorem. My question is about when can we safely assume the regularity condition is satisfied when f is only provided as a $\Theta(g(n))$, which is actually what happens most of the time when we don't want to bother detailing the exact expression for $f$.

From my understanding, I believe that nothing can be assumed without additional information on f. In the example provided on wikipedia of $T(n) = T\left(\frac{n}{2}\right) + n(2 - \cos{n})$ we have $f(n) = \Theta(n)$ since $(2 - \cos{n}) \in \[1, 3\]$. Yet $f$ does not satisfy the regularity condition and we therefore cannot deduce that that $T(n) = \Theta(n)$.

Going down the definition of $f(n) = \Theta(g(n))$, we have $n\_0 \geq 0$, $c\_0 \> 0$ and $c\_1 \> 0$ such that for every $n \geq n\_0$ $c\_0 g(n) \leq f(n) \leq c\_1 g(n)$. Let's assume $g(n) = n^c$.

Given a Master Theorem instance of $T(n) = aT\left(\frac{n}{b}\right) + \Theta(n^c)$, we are in case 3 of the Master Theorem when we have $a \< b^c$. Now to check the regularity condition we need to check that $a f\left(\frac{n}{b}\right) \leq kf(n)$ for some $k \< 1$. We therefore have that for $n \geq n\_0$ $$ \begin{aligned} af\left(\frac{n}{b}\right) &\leq a c\_1 g\left(\frac{n}{b}\right)\\ &\leq a c\_1 \frac{n^c}{b^c} \end{aligned} $$ and $$ \begin{aligned} kf(n) &\geq k c\_0 g(n)\\ &\geq k c\_0 n^c \end{aligned} $$ assuming $n \> 0$, we therefore need that $$ \begin{aligned} k c\_0 &\geq \frac{a c\_1}{b^c}\\ k &\geq \frac{c\_1}{c\_0}\frac{a}{b^c}\\ \end{aligned} $$

In the Wikipedia example, we have $\frac{c\_1}{c\_0} = 3$ and $\frac{a}{b^c} = \frac{1}{2}$. We would therefore need that $k \geq \frac{3}{2}$ which contradicts $k \< 1$.

Now when $f$ just comes out of a loop intrication without inner tests that would make the worst and best cases different, $f$ is a polynomial, and we just use its dominant power as a $\Theta$. I believe what saves us is that we can choose the $n\_0$ in the Landau notation, and by increasing it we can have $\frac{c\_1}{c\_0} \< \epsilon$ for any $\epsilon \> 1$. And since $\frac{a}{b^c} \< 1$, we can always find some $n\_0$ such that for any $n \geq n\_0$, the regularity condition is satisfied.

Is this sound ? Can we use the generalized Akra-Bazzi Theorem to just not bother ?

# Answer
Suppose that $T(n) = aT(n/b) + \Theta(f(n))$. What this means is that $T(n) = aT(n/b) + g(n)$, where $g(n) = \Theta(f(n))$, say $c\_{LB} f(n) \leq g(n) \leq c\_{UB} f(n)$. Consider now the following two recurrences: $$ T\_{LB}(n) = aT\_{LB}(n/b) + c\_{LB} f(n), \\ T\_{UB}(n) = aT\_{UB}(n/b) + c\_{UB} f(n), $$ with the same initial conditions as the initial recurrence. You can show inductively that $T\_{LB}(n) \leq T(n) \leq T\_{UB}(n)$. Assuming that the function $f(n)$ does satisfy the regularity conditions, you can use the master theorem to solve the two auxiliary recurrences, and hence to deduce the solution to the original recurrence.
> 2 votes

---
Tags: algorithms, master-theorem
---


# Question
Title: Why doesn't the C/C++ compilers create different tokens for different types of numbers?
Based on GeeksforGeeks and many other sites, the C/C++ compilers will create the same token for `float`/`int` etc.

However if we have something like this:

```
int A[10.5];

```

then will there be a parser error or semantic error?

The book that I'm reading says the parser rather than the semantic routines will detect it, but after the lexical analysis wouldn't that be converted to this:

```
A[Constants];

```

meaning the `10.5` will be converted to a `Constants` token based on that website? Therefore the parser will not notice this is an error because both of `10` and `10.5` will be `Constants`!

So which one is right? Will the parser or one of the semantic routines detects this error? Do the C/C++ compilers create the same tokens for int numbers and floats?

# Answer
This is in fact an implementation detail of the compiler. The page you referenced only shows one way of assigning types to tokens, while there are also others. The compiler **could** have a lexer that distinguishes between integral and non-integral constants and the parser then cannot match the declaration

```
int A[10.5];

```

to any rule. But giving an error message stating exactly this to the programmer is not very helpful. Modern C++ compilers have quite complex parsing and compiling routines that give more information in case of errors. As an example, GCC will yield:

```
me@my-computer:/tmp$ g++ test.cpp
test.cpp: In function ‘int main()’:
test.cpp:9:15: error: size of array ‘A’ has non-integral type ‘double’
     int A[10.5];
           ^

```

So you will get quite a good error message, and for obtaining it, some semantic interpretation was actually performed.
> 4 votes

---
Tags: compilers, parsers
---


# Question
Title: Entropy and Information Gain for multi attributes
Is there any way that for specific dataset I can measure entropy and information gain for two or more attributes together? Let's say we have the following dataset:

$\begin{array}{cccccc|c} x1 & x2 & x3 & x4 & x5 & x6 & y \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 1\\ 0 & 1 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 1 & 1\\ 1 & 1 & 1 & 0 & 0 & 0 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1\\ \end{array}$

How can I calculate the information gain for $x1,x2$ or $x1,x2,x3$ or $x1,x2,x3,x4$

# Answer
> 2 votes
You can group attributes together, but (assuming you're building some kind of decision tree) your decision tree will no longer be a binary tree, and you probably won't be any better off than just splitting by one attribute. Say for example you group $x\_1$ and $x\_2$ together, then there are 4 possible values for this new meta-attribute. You can use the same entropy calculation for this meta-attribute, and split on these four values.

But ask yourself this: why would you want to split on multiple attributes at once? Sure, it's true that $y=1$ whenever $x\_1$, $x\_2$, and $x\_3$ are 1, but once you split on this you can't split on any subset of these three (for example, observe that $y=0$ whenever $x\_2$ and $x\_3$ are zero. If we split on all three variables we'd need two identical subtrees, one for $x\_1=1, x\_2=0, x\_3=0$ and one for when they're all zero.)

---
Tags: information-theory, entropy, data-sets
---


# Question
Title: Number of elements with lower index equal to some element, for all items on an array
> Let $A$ be an array of size $n$, and $f(i, r, a\_r)$ be the number of indices $k$ such that $a\_k$ = $a\_r$ and $i \le k \le r$.

*Example to clarify:*

Imagine the array: $\[1, 2, 3, 2, 2, 3, 4, 5\]$. $f(0, 3, a\_3)$, for example, would be equal to 2, because there are 2 elements in the array that appear before $a\_3$ (which is 2) and are equal to it.

I've heard one of my colleagues talk about using a Fenwick Tree, but I don't see how that could be done.

I'd like to know if there´s a way to solve this problem in $O(n)$. By *solving it* I mean finding every value of $f$ for a fixed $i = 0$ and $r = \[0, n-1\]$

Space isn't really a problem, as long as it's polynomial.

# Answer
Do a linear scan over the array, and use a hashtable. Each time you see an element, add it to the hashtable (with a count of 1) if it's not already present, or increment the count of the item in the hashtable if it is already present. As you see each element $a\_r$, you can compute $f(0,r,a\_r)$ by looking up $a\_r$ in the hashtable and finding its count, and then record this value of $f$. This will lead to an expected running time of $O(n)$ if you use a suitable hash function.

If you want deterministic running time, use a balanced search tree instead of a hashtable; that will achieve $O(n \log n)$ worst-case running time.
> 2 votes

---
Tags: algorithms, binary-trees, arrays, searching
---


# Question
Title: Find n-th number in a number system with only 3 and 4
Given a number system with only 3 and 4. Find the nth number in the number system.

There is a solution given here but its very vague without explaining the mathematics/ concept behind it. Can someone please help me derive the logic for framing an algorithm for this question?

One approach that crosses my mind is, we can think of this number system as also a binary one ( in 3 and 4, instead of 1 and 0) Thus, we could possibly convert the nth number to its corresponding binary format and replace 0 with 3 and 1 with 4. One problem here though is that say the nth number is 333. This in the regular (0 and 1) binary system would be 000 = 0, which evidently is wrong since the nth number is not 0.

# Answer
> 2 votes
You're on the right track, it is similar to binary in a way.

The first step to coming up with an efficient solution is to recognize that to convert a number from the $3,4$ system to decimal, you can treat $3$'s like a $1$ in binary, they have a value equivalent to $2^n$ where $n$ is the position of the digit, starting from the right $n$ starting at $0$. Thus $3 \equiv 1$, $33 \equiv 3$, $333\equiv 7$, etc.

A $4$ has a value equivalent to $2^{n+1}$ starting from the right $n$ starting at $0$, so $4\equiv2$, $44 \equiv 6$, etc.

Because of the similarity to binary, we can convert our input (the decimal number) to binary, and then convert that to $3,4$. To do so, we can use the following algorithm.

Given a binary number, iterate through the digits from right to left.

1. If the digit encountered is a $1$, place a $3$ for that digit in the result.
2. If the digit encountered is a $0$, and there are more digits following, place a $4$ for this digit in the result, and for any consecutive $0$'s, place a $3$ for those digits until a $1$ is encountered. When a $1$ is encountered following a $0$ or series of $0$'s, if there are more digits following, change this $1$ to a $0$, and repeat step $2$ as if this were the first $0$ you've encountered. When a $1$ is encountered and no more digits are following it, do nothing and return the result.

This reason this works is the following

1. Step $1$ uses the fact that $3$ has the same value in $3,4$ as $1$ does in binary.
2. Step $2$ is necessary because in $3,4$ there is no $0$ value for any digit. Using the fact that $2^n = 2^{n-1} \times 2 = 2^{n-1} + 2^{n-1}$ we convert a $1$ followed by $n$ $0$'s to its equivalent form in $3,4$ of $n-2$ $3$'s followed by a $4$. The first $3$ has a value of $2^{n-1}$ and the remaining $3$'s and $4$ sum up to $2^{n-1}$.

This algorithm is roughly $O(\log n)$.

---
Tags: algorithms, number-theory, base-conversion
---


# Question
Title: 3-Col using each colour exactly $|V|/3$ times
Is the following problem in P?

Does a graph $G$ have $3$-colouring, where each colour is used exactly $|V|/3$ times?

I believe it is as we are trying to sample three sets (one for each colour) of vertices without replacement, giving a running time of $O(|V|^5)$. The first set is for three colours, the second for two and third for one col.

# Answer
No, the problem is still **NP**-complete. Suppose you want to know if $G$ is 3-colourable (with no limits on how many vertices can be each colour). Just make a new graph $G^+$ by adding $2|V(G)|$ new vertices with no edges between them, so $|V(G^+)|=3|V(G)|$. If $G$ has a 3-colouring then you can get a "balanced" 3-colouring of $G^+$ by setting the colours of the new vertices appropriately; if $G$ has no 3-colouring, then $G^+$ also has no 3-colouring, so it has no balanced 3-colouring, either.
> 6 votes

---
Tags: complexity-theory, computability, np-complete, np, decision-problem
---


# Question
Title: How to solve a recurrence relation with a sum?
How do I solve the following recurrence relation?

> $$ T(n) = 1 + \sum\_{j=0}^{n-1} T(j). $$

I thought of solving it by generating its recursion tree. I found that the height of the tree would be equal to $n$ but wasn't able to find the cost of each level.

# Answer
> 16 votes
Here are several ways to solve your recurrence relation.

**Guessing**

Anyone with enough experience in computer science might recognize your recurrence as the one satisfied by $T(n) = 2^n$. Given this guess, you can verify it by summing the appropriate geometric series: if $T(m) = 2^m$ for $m \< n$ then

$$ T(n) = 1 + \sum\_{m=0}^{n-1} T(m) = 1 + \sum\_{m=0}^{n-1} 2^m = 1 + (2^n-1) = 2^n. $$

**Computing the first few values**

Another approach which is very useful is to compute a few values of the sequence: $$ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... $$ If we're lucky, as in this case, we might spot a pattern. If not, it's always a good idea to consult the on-line encyclopedia of integer sequences. A quick search would reveal the sequence A000079.

**Creative telescoping**

In the method of creative telescoping, we try to find a combination of terms that results in major cancellation. In our case, we can try $T(n+1)-T(n)$:

$$ T(n+1)-T(n) = \sum\_{m=0}^n T(m) - \sum\_{m=0}^{n-1} T(m) = T(n), $$ and so $T(n+1) = 2T(n)$. Unrolling this rule, we deduce $T(n) = 2^n T(0) = 2^n$.

**Back-substitution**

Another way to look at the preceding trick is to try to "back-substitute" the recurrence inside itself:

$$ T(n) = 1 + \sum\_{m=0}^{n-1} T(m) = 1 + \sum\_{m=0}^{n-2} T(m) + T(n-1) = 2T(n-1), $$

from which we can proceed as before.

**Generating series**

A very general method is that of generating series. Let $G(x) = \sum\_{n=0}^\infty T(n) x^n$. Since $1/(1-x) = \sum\_{n=0}^\infty x^i$, multiplying by $1/(1-x)$ is like computing "running sums": $$ \frac{G(x)}{1-x} = \sum\_{n=0}^\infty \sum\_{m=0}^n T(m) x^n = \sum\_{n=0}^\infty (T(n+1)-1) x^n = \\ \frac{G(x)-T(0)}{x} - \sum\_{n=0}^\infty x^n = \frac{G(x)-1}{x} - \frac{1}{1-x}. $$ From this it is not hard to deduce $$ G(x) = \frac{-1/x-1/(1-x)}{1/(1-x)-1/x} = \frac{-(1-x)-x}{x-(1-x)} = \frac{1}{1-2x} = \sum\_{n=0}^\infty 2^nx^n, $$ and so $T(n) = 2^n$.

**Recursion tree**

It is also possible to deduce the value of $T(n)$ using a recursion tree. Each path in the recursion tree for $T(n)$ corresponds to a sequence of decreasing numbers $n\_0 = n, \ldots, n\_\ell$, where $n\_\ell \geq 0$ (possibly $\ell = 0$); this is because all leaves are labeled by $1$. The set of possible decreasing sequences is in one-to-one correspondence with subsets of $\\{n-1,\ldots,0\\}$, because once we know which numbers appear, we also know their order. The number of subsets of $\\{n-1,\ldots,0\\}$ is exactly $2^n$.

---
Tags: recurrence-relation, discrete-mathematics
---


# Question
Title: Armstrong's axioms more precisely 'inference rules': what's the distinction?
"more precisely 'inference rules'" is what wikipedia says twice.

Other references I've looked at (the Alice book, Ullman lecture notes cited, Maier textbook) name them as Armstrong's Axioms, use them for inference. talk about axiomatisation and decidability, etc.

Wikipedia's links to axiom vs inference rule isn't helping me. "a rule of inference's action is purely syntactic, and does not need to preserve any semantic property:" Ok I can see that for (for example) modus ponens: it wants a premise like $p \supset q$ and a premise looking like $p$.

Hmm take the Armstrong Axiom of reflexivity

> If $X$ is a set of attributes and $Y$ is a subset of $X$, then $X$ holds $Y$.
>
> > If $Y \subseteq X$ then $X \rightarrow Y$.

How to determine ***syntactically*** that $Y \subseteq X$?

So what is wikipedia trying to say? What distinguishes an axiom (which might be of the form $p \supset q$) vs an inference rule?

# Answer
First, terminologically, "axiom" and "inference rule" are often used as roughly interchangeable as they tend to serve similar purposes. There are technical distinctions, which themselves can vary slightly, but outside the study of formal logic or related systems, these distinctions aren't that important.

In the context of formal logic, an axiom is a formula of the logic that is a theorem by definition. A rule of inference is a way of deducing new theorems from old theorems. Rules are always part of the logic, while axioms are separated into logical axioms, which are viewed as part of the logic, and non-logical axioms, which are viewed as part of the particular theory you are studying within the logic. Many logical axioms can be presented as rules and vice versa. For example, the axiom $P\supset(Q\supset P)$ roughly corresponds to the rule of weakening $\cfrac{\Gamma\vdash P}{\Gamma,Q\vdash P}$.

From a meta-logical perspective, rules of inference can be viewed as (definitional) axioms *about* the logic being studied (not to be confused with the "formal" axioms *within* the logic. Philosophically, "believing" in the conclusions of a logical theory requires "believing" the rules of inference just as much as "believing" the axioms.

So are Armstrong's "Axioms" axioms or rules of inference? It depends on how you formalize them. The "axioms" strongly suggest a deductive system, i.e. a system of rules, and that deductive system is quite useful in actually calculating functional dependencies. But, we could just as well take $\to$ and $\subseteq$ as relation symbols in a first-order theory and then the "axioms" really would be non-logical axioms of that theory. This could be viewed as meta-logical axioms about the deductive system, but it can just as reasonably be viewed as axiomatizing what "functional dependency" means without any deductive system in mind.

As for how to determine if $Y\subseteq X$ if we do indeed take a deductive system view of Armstrong's Axioms, in this context $X$ and $Y$ are meta-variables that stand for sets of attributes. They would be instantiated with expressions like $\\{\mathsf{name},\mathsf{address}\\}$. So for the rule you referenced, you'd simply be able to calculate that $\\{\mathsf{name}\\}\subseteq\\{\mathsf{name},\mathsf{address}\\}$ and $\\{\mathsf{age}\\}\not\subseteq\\{\mathsf{name},\mathsf{address}\\}$. An algorithm to calculate this could be formalized as a collection of inference rules itself, but there is no reason to do this. We can just assume that it can, in fact, be calculated. Obviously it can be in the intended use-case where the "sets" are explicitly presented, finite sets of elements with decidable equality.

Even for modus ponens, we have $P$ and $Q\supset R$ and we can apply modus ponens if $P=Q$, but checking the (syntactic) equality of two formulas while not hard is not completely trivial. Indeed, weakening is often presented with a rule like $\cfrac{\Gamma\vdash P\qquad \Gamma\subseteq\Delta}{\Delta\vdash P}$ and it is just understood that you can, in fact, calculate whether one set of formulas is a subset of another. It may also be presented as $\cfrac{\Gamma\vdash P}{\Gamma\cup\Delta\vdash P}$ where, again, it is just assumed that you have some way of calculating $\Gamma\cup\Delta$.
> 5 votes

---
Tags: database-theory
---


# Question
Title: How is Rank Selection better than Random selection and RWS?
I'm having a rough time understanding the Rank Selection method for Genetic Algorithms. Here is what I think it does:

* Tour1's Fitness: 0.87
* Tour2's Fitness: 1.22
* Tour3's Fitness: 1.03
* Tour4's Fitness: 0.58

We rank them using their fitness:

* 4) Tour2 -- Highest rank (N)
* 3) Tour3
* 2) Tour1
* 1) Tour4 -- Lowest rank (1)

We generate a random number between 1 and 10 (sum of ranks), for example `X = 3`. We then loop and sum the ranks until its greater than X and we select the tour, in this example it will be **Tour2** since it's rank is 4 and `4 > 3`.

What I don't understand is how is this better than just randomly selecting a tour and why is it better than Roulette Wheel Selection? ALso please correct me if I'm missunderstanding the method.

# Answer
> 2 votes
It's about controlling selection pressure. With roulette wheel selection, there are several scaling issues. If you have two individuals p1 and p2 with fitness values 1 and 2 versus having values 1001 and 1002, roulette wheel selection behaves drastically differently. Similarly, suppose the optimal fitness value of your function is at some f(x)=100, and you generate an initial population with fitness values all around 1, and one individual at 20. Roulette wheel selection will drastically favor the one best solution, simply because it's so much better than the others. But early in a run, that's probably a mistake. The population will quickly be taken over by copies of that solution. Just being way better than bad alternatives doesn't tell me enough information to be that aggressive in selecting it.

Ranked selection just looks at the rankings and so doesn't have this problem. Whether you're a little better or a lot better, we can precisely control how aggressively to exploit those better solutions.

Darrell Whitley is generally credited with the idea of Rank-biased selection in \[1\]. He published code for performing selection using this method. I've cleaned up that code a bit below. You'd have to integrated it with your own code to properly get the population size, etc., but it should be fairly self-explanatory aside from the actual formula -- that you can just take on faith or go read Whitley's GENITOR paper for details.

```
// return the index into the population of the selected parent.
// population must be sorted by fitness first
Chromosome select_parent(Population pop)
{
    double bias = 1.5;
    int index = (int)(pop.size() * (bias - sqrt(bias*bias - 4.0*(bias-1) * rand01()))
        / 2.0 / (bias-1));
    return pop[index];
}

```

The bias term governs how strongly we want to favor higher ranked individuals. You could tweak that to increase or decrease selection pressure, though in practice, I've never changed it from the default value of 1.5 given in the Whitley paper.

The only other detail is that I invented a notation for "rand01" to mean a function that returns a random floating point number in the interval \[0.0, 1.0).

\[1\] https://www.researchgate.net/profile/Darrell\_Whitley2/publication/2527551\_The\_GENITOR\_Algorithm\_and\_Selection\_Pressure\_Why\_Rank-Based\_Allocation\_of\_Reproductive\_Trials\_is\_Best/links/5632149808ae3de9381e72c5/The-GENITOR-Algorithm-and-Selection-Pressure-Why-Rank-Based-Allocation-of-Reproductive-Trials-is-Best.pdf

# Answer
> 0 votes
It is a way of randomly selecting a tour -- but not all tours are equally likely. This method is more likely to pick a high-rank tour than a low-rank tour. Thus, it's a way of randomly selecting a tour, but biased towards the better (high-rank) tours. If you picked uniformly at random among the tours, you'd be more likely to get a lower-rank (worse) tour.

---
Tags: genetic-algorithms, selection-problem
---


# Question
Title: What is the equivalent form of full outer join in relational algebra?
Considering only basic relational algebra operations, how can we implement the full outer-join ?

# Answer
Full outer join returns null in the columns of rows from one table that don't match the other table -- that's a description of SQL.

Standard Relational Algebra doesn't have nulls. Here explains what would be the consequences.

Short answer: 'we' don't want to implement outer joins. If you think you do, think some more until you see why it leads to incoherence of queries.
> 1 votes

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


# Question
Title: Generating uniformly random bits from a stream of arbitrarily biased bits
Say we have a function called GenBiasedBit. This function returns 1 with probability p (where p is an unknown real number between 0 and 1 exclusive) and returns 0 with probability 1 − p. How could I write a Las Vegas algorithm (called GenUnbiasedBit) that returns 1 or 0 with equal (nonzero) probability, using calls from GenBiasedBit as a source of randomness? I'm not really sure how to approach this problem. Since 1 and 0 must be generated with equal chance, I'm assuming they must both have a 50/50 chance of being selected. Since this is a Las Vegas algorithm, I'm not sure how to guarantee that its output is correct, if we don't know the probability of GenBiasedBit generating a 1 or 0.

# Answer
> 3 votes
We can simulate an unbiased coin as follows. Toss a pair of coins, and repeat until they produce different outcomes. If the outcome was H,T (heads followed by tails) output heads, and if it was T,H output tails.

Conditioning on the event that the above simulation halts (i.e. at some iteration $i$ we receive different outcomes), then both H/T have equal probability. The probability of a "bad output" in a single iteration (same result from both coins) is $p^2+(1-p)^2$, which is less than $1$ for $p\in (0,1)$. Thus, the probability of "failure" after $n$ iterations is bounded by $(1-2p(1-p))^{-n}$.

---
Tags: randomized-algorithms, randomness
---


# Question
Title: Genetic algorithm - fit max circles inside box - what chromossomes?
I am using a genetic algorithm to fit the max number of circles into a box. Right now my cromossomes are both coordinates of the each circle. I am not sure how to crossover and mutate the x and y coordenates in order not for the to converge but to keep a distance.

Can someone please shed some light? Thank you

This is where I am getting at:

Now I am getting this:

But there is the last ball always overlaps. I think my problem is with the crossover.

So far and by gathering all the ideas here this is what I have reached: Given a fixed number of circles (easier to explain) this is what I am doing.

1. Create a random set of circles for each individual in the population

2. Calculate the fitness of every individual base on the overlaping area are and area outside the box.
3. I then order the individuals by their fitness
4. Do a cross over. For that I am using a cumulative sum to choose randomly but with priorities which individuals are likely to go through to the next generation based on the fitness. The fittest have a higher probability of being chosen.
5. After choosing them indivudals I am aplying the crossover to I randomly choose the chromosse to which I do the single point cross over.
6. Then repeat for n generations

I am doing this but not getting to any convergion in terms of solution.

# Answer
> 1 votes
You can define chromosome as array - coordinates of the center of a circle - \[(x1,y1), (x2, y2),..,(xn,yn)\] One required condition for every circle- no intersection between sides of rectangle and circle - the circle must be inside the rectangle.

Start from one circle (n=1) and create population with chromosomes of size 1 \[(x1,y1)\].

Your fitness function - number of intersections between circles - for n=1 fitness function always return 0.

You continue with 2 circles: and generate population of chromosomes \[(x1,y1), (x2,y2)\]. For every chromosome you calculate fitness - number of intersection between circles.

Crossover:

You can use different algorithm to generate new population:

1) Single point.

First point - from first chromosome, second point from second chromosome.

For example, two chromosomes with coordinates:

\[(x11,y11), (x12, y12)\]

\[(x21,y21), (x22, y22)\]

Crossover - two chromosomes:

\[(x21,y21),(x12,y12)\],

\[(x11,y11),(x22,y22)\]

For n\>2:

\[(x11,y11),(x12,y12), (x13,y13),..,(x1n,y1n)\]

\[(x21,y21),(x22,y22), (x23,y23),..,(x2n,y2n)\]

Crossover:

\[(x21,y21),(x12,y12), (x13,y13),..,(x1n,y1n)\]

\[(x11,y11),(x22,y22), (x23,y23),..,(x2n,y2n)\]

etc.

See https://en.wikipedia.org/wiki/Crossover\_(genetic\_algorithm) about crossover algorithms.

Mutation:

For every chromosome from population choose randomly some circle and change coordinates.

New population:

select chromosomes with minimal fitness value.

If you found out chromosome with fitness value is 0 - increment n (number of circles) and repeat this procedure: create population with chromosomes with size n, etc.

---
Tags: genetic-algorithms, packing
---


# Question
Title: How do we define if a Turing machine goes to the right or left?
In my college course notes, we are given two examples.

> **Example 9.1.1:** $$ M(K, \Sigma, \delta, s) $$ where
>
> * $ K = \\{q\_0, q\_1\\} $
> * $\Sigma = \\{a, \\# \\}$
> * $s = q\_0$
> * $ \delta = \begin{array}{|c|c|c|c|} \hline q & \sigma & \delta(q, \sigma) \\ \hline q\_0 & a & (q\_1, \\#) \\ q\_0 & \\# & (h, \\#) \\ q\_1 & a & (q\_0, a) \\ q\_1 & \\# & (q\_0, R) \\ \hline \end{array}$
>
> Note that state $(q\_1, a)$ cannot happen if the start state is $q\_0$. This is included only for completeness (to make $\delta$ a total function).
>
> This machine will scan right, changing any $a$ that sees to a $\\#$. When it first hits a $\\#$, it will halt.

---

> **Example 9.1.2:** $$ M(K, \Sigma, \delta, s) $$ where
>
> * $ K = \\{q\_0\\} $
> * $\Sigma = \\{a, \\# \\}$
> * $s = q\_0$
> * $ \delta = \begin{array}{|c|c|c|c|} \hline q & \sigma & \delta(q, \sigma) \\ \hline q\_0 & a & (q\_0, L) \\ q\_0 & \\# & (h, \\#) \\ \hline \end{array}$
>
> This machine will scan left until it encounters $\\#$, then halt.

One TM goes to the right while the other goes to the left. Obviously this is determined by the transition rules, but how do we explicitly know/define where to start (either on the left of the string or right?).

I am asking because I have a Turing machine that works for a problem I have, but I must start from the right of the string and scan left... How do I define this?

# Answer
It's not specified in the description you gave, but absent directions to the contrary, a TM is generally understood to start at the leftmost non-blank cell.
> 4 votes

# Answer
> so therefore it must start on the rightmost non-blank cell

That doesn't follow. It can start on any cell, including the left-most one, in which case it'll just go left once and stop.

> I am asking because I have a Turing machine that works for a problem I have, but I must start from the right of the string and scan left... How do I define this?

If you have such a machine, that you can easily create one which does the same starting on any non-blank cell. Namely:

1. Start by scanning right until you hit the first blank cell.
2. Go left once (you are now at the rightmost non-blank cell).
3. Run your original machine.
> 3 votes

---
Tags: formal-languages, turing-machines
---


# Question
Title: Regular expression of a language over {a,b} which does not contain substring bbb
I want Regular Expression for language L defined over {a,b} and L does not contain substring 'bbb'. I tried something but could not get proper answer.

# Answer
We can decompose every string over $\\{a,b\\}$ as a sequence of runs: $$ a^{n\_1} b^{n\_2} a^{n\_3} b^{n\_4} \ldots \text{ or } b^{n\_2} a^{n\_3} b^{n\_4} a^{n\_5} \ldots, $$ where $n\_1,n\_2,n\_3,n\_4,\ldots \geq 1$. In our case the constraint is $n\_2,n\_4,n\_6,\ldots \leq 2$.

Let us start with the identity $$ (a+b)^\* = (a^+b^+)^\*a^\* + (b^+a^+)b^\*, $$ which corresponds to the description above.

Can you think of a way to modify it so that all powers of $b$ are at most 2?
> 2 votes

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: Calculating Frequency of Terms with Zipf's Law
I'm studying for an exam and came across this question. I feel like it's much simpler than I am making it out to be, but I'm not sure.

Suppose we have a corpus in which Zipf’s Law holds. If the most frequent term occurs one million times, and the next most frequent term occurs 250,000 times, how often should we expect to see the third most frequent term? And the fourth most frequent term?

Wikipedia has the formula $$f\left(k,s,N\right)=\frac{\frac{1}{k^{s}}}{\sum\limits\_{n=1}^{N}\frac{1}{n^{s}}},$$ We but in this problem, $N$ (the number of terms) and $s$ (the value of the exponent characterizing the distribution) aren't given. Only $k$ (the rank) is given and the frequencies of each rank. I know that Zipf's Law says that the frequency of a term is inversely proportional to the term's rank, but I don't know what that constant factor would be in $f\_{t}=c\cdot\frac{1}{k}$.

# Answer
The question gives you enough information to deduce $N$ and $s$. You are given $f(1,s,N)$ and $f(2,s,N)$. Note that $$ \frac{f(1,s,N)}{f(2,s,N)} = \frac{1/1^s}{1/2^s} = 2^s. $$ Hence you can find $s$. In order to calculate $f(3,s,N),f(4,s,N)$ you don't really need to find $N$, since, $$ \frac{f(1,s,N)}{f(3,s,N)} = 3^s, \quad \frac{f(1,s,N)}{f(4,s,N)} = 4^s, $$ using calculations similar to what we had before.

Notice that in order to solve this exercise, we had to know absolutely nothing about the Zipf law other than the formula. Stated differently, what you need in order to solve this exercise is not *knowledge* (apart from the formula for $f(k,s,N)$) but rather *problem solving skills*. One of the main goals of the undergraduate degree is to develop such skills.
> 1 votes

---
Tags: information-theory, information-retrieval
---


# Question
Title: How do I test if a polygon is monotone with respect to a line?
It's well known that monotone polygons play a crucial role in polygon triangulation.

> **Definition:** A polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $P$ at most twice.

Given a line $L$ and a polygon $P$, is there an efficient algorithm to determine if a polygon $P$ is monotone with respect to $L$?

# Answer
**Hint:** A generic simple polygon is monotone with respect to the $x$-axis if and only if it has exactly one vertex whose $x$-coordinate is smaller than its neighbors. This observation immediately suggests an $O(n)$-time algorithm, at least if no edge of your polygon is vertical.

**Spoilers ahoy:**

> ```
> IsMonotone(X[0..n-1], Y[0..n-1])
>     local_mins ← 0
>     for i ← 0 to n-1
>         if (X[i] < X[i+1 mod n]) and (X[i] < X[i-1 mod n])
>             local_mins ← local_mins + 1
>     return (local_mins = 1)
> ```

If you're worried that your polygon might have vertical edges, use the following subroutine in place of the comparison `X[i] < X[j]` to consistently break ties:

```
IsLess(X, i, j):
    return ((X[i] < X[j]) or (X[i] = X[j] and i < j))

```

Finally, if $L$ is some other line of the form $ax+by=c$, modify `IsLess` as follows:

```
IsLess(X, Y, i, j):
    Di ← a·X[i] + b·Y[i]
    Dj ← a·X[j] + b·Y[j]
    return ((Dj < Dj) or (Di = Dj and i < j))

```
> 11 votes

# Answer
Here's a more informal, high-level, and, hopefully, intuitive explanation of an algorithm to check if a polygon is "horizontally monotone", i.e. with respect to the $x$-axis.

1. Find the leftmost and rightmost vertices (i.e. the vertices of the polygon with respectively the min and max $x$-coordinate), in $\mathcal{O}(n)$ time (i.e. just iterate once the list of vertices).
2. These two vertices split the polygon's boundary into two curves: an upper chain and a lower chain.
3. Walk from left to right along each chain, verifying that the $x$-coordinates are nondecreasing. This takes $\mathcal{O}(n)$ time.
> 1 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: number of queries to recover the permutation
Imagine this game. I pick a permutation $p$ of $1..n$ and give you an oracle. When the oracle is queried with any sequence of $n$ numbers $\in 1..n$, it masks each number by applying some unknown bijection $f$ and then permutes the masked values using $p$. Your goal is to repeatedly query the oracle to recover $p$ with as few queries as possible.

A $\theta(\log(n))$ solution is obvious. First query $1, 2, 3, 4, \ldots$ and $2, 1, 4, 3, \ldots$, the second query reversing each of the $\lfloor \frac{n}{2} \rfloor$ pairs. As swapping a pair in the input swaps the corresponding pair in the output, we identify the $\lfloor \frac{n}{2} \rfloor$ pairs that they map to, albeit with unknown correspondence. (If $n$ is odd, the $n$th item is the one remaining in place so $p(n)$ is known.) Then query $1, 1, 3, 3, \ldots$ to identify which item in each output pair corresponds to the first item of an input pair. With 3 queries we have reduced the problem to one of size $\lfloor \frac{n}{2} \rfloor$ by querying from now on with identical pairs of items; recurse. We use $3\log n \pm O(1)$ queries.

Can we do better? For example, is there a strategy using $\log n \pm O(1)$ queries?

Regarding lower bounds, if $q$ queries is optimal for $\frac{n}{2}$ we can run the strategy twice in parallel, side-by-side, in $q$ queries for $n$ but we still lack information about which $\frac{n}{2}$ of the input maps to the corresponding $\frac{n}{2}$ elements of the output, suggesting we need at least one additional query for $n$. This argument *seems* to imply $\Omega(\log(n))$ query complexity - can it be made rigorous?

# Answer
> 2 votes
Suppose that my input is some permutation $\sigma$. Applying $f$ is the same as multiplying by $f$ from the left (assuming that $\alpha\beta(i) = \alpha(\beta(i))$, and then applying $p$ is the same as multiplying by $p$ from the right. In other words, we have an oracle for the function $\sigma \mapsto f\sigma p$.

Given $f\sigma p$ and $f\tau p$, we can find $(f\sigma p)^{-1} (f \tau p) = p^{-1} (\sigma^{-1} \tau) p$. In particular, using two oracle calls we can find $p^{-1} (1\\;2\\;3\\;\cdots\\;n) p = (p^{-1}(1)\\;p^{-1}(2)\\;p^{-1}(3)\\;\cdots\\;p^{-1}(n))$. Using one more oracle call, we can also find $(p^{-1}(2)\\;p^{-1}(1)\\;p^{-1}(3)\\;\cdots\\;p^{-1}(n))$ (the only difference is the first two values). From these two long cycles we can locate $p^{-1}(1)$ and so recover $p^{-1}$ (and so $p$), as well as $f$ if we so wish. In total, we used three oracle calls.

---
Tags: complexity-theory, permutations
---


# Question
Title: Limit repetitions in randomized list with each unique element occurring n times
I have a set of 3 elements and need to generate a randomized sequence containing each element n times with the condition that one element can only occur m times in a row.

So with elements \[0,1,2\] n = 4 and m = 3:
\[1, 2, 0, 0, 0, 1, 1, 2, 2, 2, 0, 1\] valid
\[1, 2, 0, 0, 0, 0, 1, 2, 2, 2, 1, 1\] invalid

The only solutions I found were to add all elements n times to a list and then shuffle until the condition is satisfied or generate the whole search space and then randomly sample from the correct solutions. Both seem possibly slow and memory intensive.
Could just be looking for the wrong terms, this has to be documented somewhere.

I came up with this approach, but am not sure about correctness.

```
E: set of elements e
n: of each element in sequence
m: maximum repetitions of one element
S = [] # empty sequence
while |S| < |E| * n:
    R = shuffled list containing each e m times
    for m:
        if s+r satisfies condition:
            S <- s+r # Extend s with r
        else:
            rotate r by one element
return the first |E| * n elements of S

```

It *seems* to produce correct results, but is it ok to sample and then rotate the subsequences R like that?
Would the time complexity be just O(|E| * n * m)?

Here is my python implementation:

```
def generate_sequence(e, n, m):
# Final sequence
s = []
# Extend s by n * len(elements) each iteration
for _ in range(n//m+1):
    r = list(e) * m
    random.shuffle(r)
    for _ in range(len(r)):
        # List of all windows of size m+1 where at least one element is from s or r.
        windows = filter(lambda x: len(x) == m + 1,
                         [s[-i:] + r[:(m + 1 - i)] for i in range(1, m + 1)])
        # check if any window contains an invalid sequence
        if not all(len(set(window)) > 1 for window in windows):
            # rotate r one to right
            r = [r[-1]] + r[:-1]
        else:
            # Valid s+r
            s.extend(r)
            break
return s[:len(list(e)) * n]

```

# Answer
I will assume that by "random" you mean you want the output will be uniformly distributed on the set of all valid arrangements, or in other words, that all valid arrangements are equally likely to be output by the algorithm.

# Simple method: rejection sampling

A simple approach is to use rejection sampling: generate a random arrangement, then check if it contains any element $m$ times in a row, and if so throw that away and repeat.

You can generate a random arrangement by starting with the list $\[0,1,2,0,1,2,0,1,2,\dots\]$ and then applying a random permutation to it, i.e., randomly shuffling it.

This will ensure the output is uniformly distributed. It will be efficient if $m$ is large and inefficient if $m$ is too small. In particular, if $m \ge \log\_3 n$, then this should be pretty efficient; the expected number of times you repeat is $O(1)$. On the other hand, if $m \ll \log\_3 m$, then this becomes highly inefficient, because you have to repeat many times.

# Sophisticated method: ranking/unranking

Here is a more sophisticated technique that will be more efficient if $m$ is small. It works by counting the number of valid arrangements using dynamic programming, and using ranking/unranking techniques.

---

Let's start by looking at how to count the number of valid arrangements. In particular, let $f(n)$ denote the number of valid arrangements of length $n$. I'll show how to compute $f(n)$ using dynamic programming.

To aid with that, let $g(n,x,r,a\_1,a\_2,a\_3)$ denote the number of valid arrangements of length $n$ that use exactly $a\_1$ 1's, $a\_2$ 2's, $a\_3$ 3's, without repeating any number $m$ times in a row, and assuming that before these $n$ you have a sequence of $r$ $x$'s in a row (e.g., if $x=3$ and $r=2$, then a valid sequence is allowed to start with up to $m-r-1$ 3's, but no more than that). Notice that

$$f(n) = g(n-1,1,1,n/3-1,n/3,n/3) + g(n-1,2,1,n/3,n/3-1,n/3) + g(n-1,3,1,n/3,n/3,n/3-1),$$

so if we can compute the $g$'s, we can compute $f$. Also there is a recursive relation among the $g$'s:

$$g(n,1,r,a\_1,a\_2,a\_3) = g(n-1,1,r+1,a\_1-1,a\_2,a\_3) + g(n-1,2,1,a\_1,a\_2-1,a\_3) + g(n-1,3,1,a\_1,a\_2,a\_3-1),$$

which is obtained by a case analysis on the first digit of the sequence, and symmetrically for other values of $x$. (Here I assume we agree on boundary conditions like $g(\cdot,\cdot,m,\cdot,\cdot,\cdot)=0$.)

Now this gives a dynamic programming algorithm for computing $g$, by memoizing, and thus an algorithm for computing $f$. What is the running time? Well, there are at most $3m(n/3)^3 = O(n^3m)$ different subproblems, and solving each one can be done in $O(1)$ time using memoization, so the total running time is $O(n^3m)$.

---

Now that we know how to count, how do we use that to generate a random valid arrangement? We'll use unranking. Since there are $f(n)$ valid arrangements, we can think of each integer in the range $1..f(n)$ as corresponding to a valid arrangement. We will construct an algorithm that can find the arrangement corresponding to a particular integer $i$; then all we need do is pick a random integer in that range, find the corresponding arrangement, and we have a random valid arrangement.

It's easy to use the recursive formula above to build an unranking procedure. Given an integer $i$, we test whether $i \le g(n-1,1,1,n/3-1,n/3,n/3)$; if yes, then the first number in the sequence is 1; if not, we test whether $i \le g(n-1,1,1,n/3-1,n/3,n/3) + g(n-1,2,1,n/3,n/3-1,n/3)$; if yes, then the first number in the sequence is 2, else it is 3. We continue from there to iteratively fill in each element of the sequence.

This lets us pick a valid sequence uniformly at random. The running time is $O(n^3 m)$, so it is efficient for all values of $m$. You can even precompute all of the $g$ values in advance, in which case the running time becomes $O(n)$ per random sequence you want to generate.
> 1 votes

# Answer
I'm pretty sure this would work. The code might not be completely correct because I haven't coded in Python for quite a while.

```
def generate_sequence(e, n, m):
    r = list(e) * m
    valid = false
    while (!valid):
        random.shuffle(r)
        for i in range(len(r)-n+1):
            if (r[i] == r[i+1] && r[i] == r[i+2] && r[i] == r[i+3]):
                fourInRow = true
                break
        if (!fourInRow) return r

```
> 0 votes

---
Tags: algorithms, complexity-theory, randomized-algorithms, correctness-proof, sampling
---