title: Alan Perlis Epigram on Recursion

text:
# Question
Title: Alan Perlis Epigram on Recursion
So, while trying to dive into "recursion" and the like, I came across an epigram about recursion by Alan Perlis:

> Recursion is the root of computation since it trades description for time.
>
> -- Alan Perlis

Common to epigrams, this sounds like a deep insight. But I've already got stuck on "root of computation" and in which sense recursion "trades description for time".

Any explanation would be nice. : )

# Answer
> 5 votes
I can't presume to speak for Perlis, but my intuition is as follows:

* **Recursion is descriptive**

Especially at the time this was written, the specification of a recursive function seems much more descriptive than prescriptive, in the sense that a recursion describes a *mathematical property* we want the result to satisfy, rather than a series of computation steps. E.g. for mergesort

```
 sort(l) = let l1, l2 = split(l) in merge(sort(l1), sort(l2))

```
* **Recursion involves a notion of time**

But obviously recursion *also* describes a process or series of steps. In the case of mergesort:

1. Split `l` into `l1` and `l2`
    2. **then** compute `sort(l1)` and `sort(l2)` (in either order)
    3. **then** compute the `merge` of those two results
    4. the result of this is the value we wished to compute

This suggests that the *time* taken by this computation is the time of each of these individual steps, which *itself* involves a recursive equation (over integers) to compute, namely the time taken to sort the sublists `l1` and `l2`.

* **Trading description for time is the essence of computation**

One way of characterizing computation is that we want to go from an abstract mathematical "timeless" description of an object to a concrete representation which can be manipulated symbolically.

Computation can be defined as the process which goes from the abstract to the concrete, and the time which this process takes is one of the central considerations of CS as a field.

---

My last advice is that sometimes it is important not to overthink epigrams or koans, but let understanding come naturally with experience.

# Answer
> 2 votes
"Root" is being used as the thing from which everything grows, like a plant's roots. It's an allusion to the famous phrase "The love of money is the root of all evil" (1 Timothy 6:10 in the King James Bible).

I suspect that "trades description for time" means that specifying something by recursion gives a very short description at the cost of taking longer to execute, but I'm less sure of that.

---
Tags: computability, recursion
---


# Question
Title: Language of all words accepted by a TM by at most $t$ steps is regular
Let $M$ be a Turing machine, $\Sigma$ an alphabet, $t \in \mathbb{N}$

$L = \\{ w \in \Sigma^\* : w$ is accepted by $M$ by at most $t$ steps$\\}$

I want to show that $L$ is regular.

My attempt:

I'm trying to do this directly by constructing a DFA for $L$.

Let $M = (Q, \Sigma, \Gamma, \delta, q\_0, q\_{accept}, q\_{reject})$

Define $\Gamma\_0 = \Gamma \cup \\{\sqcap\\}$ where $\sqcap \notin \Gamma$.

Set $Q\_0 = Q \times \Gamma\_0^{t+1} \times \\{i\\}\_{i=1}^{t+1}$ a finite set.

For $q \in Q$, $(a\_1,..,a\_{t+1}) \in \Gamma^{t+1}$, $1 \leq i \leq t+1,$ $b \in \Sigma$:

Say that $\delta(q, b) := (q\_1, b\_0, R $ or $L)$ and that $\delta(q, a\_i) := (q\_2, a\_0, R$ or $L)$. We define $\delta\_0: Q\_0 \times \Sigma \to Q\_0$ by

$\delta\_0(q, (a\_1,..,a\_{t+1}), i) = \begin{cases} (q\_2, (a\_1,..,a\_0,..,a\_{t+1}), i+1) & \quad \text{if } R \text{ and }a\_i \in \Gamma\\ (q\_2, (a\_1,..,a\_0,..,a\_{t+1}), i-1) & \quad \text{if } L \text{ and }a\_i \in \Gamma\\ (q\_1, (a\_1,..,b\_0,..,a\_{t+1}), i+1) & \quad \text{if } R \text{ and }a\_i = \sqcap \\ (q\_2, (a\_1,..,b\_0,..,a\_{t+1}), i-1) & \quad \text{if } L \text{ and }a\_i = \sqcap\\ \end{cases} $

Where the change of letter in the $t+1$ tuple occured in the $i^{th}$ spot.

\**Edit: also make the machine loop upon entering the accept or reject states

Then consider the DFA $A = (Q\_0, \Sigma, \delta\_0, g\_0, F)$ where $g\_0 = (q\_0, (\sqcap,...,\sqcap), 1)$ and $F = \\{(q\_{accept}, x, j) : x \in \Gamma\_0^{t+1}, 1 \leq j \leq t+1\\}$

Now intuitively I think that this machine accepts $L$, but am having a hard time proving it.

So, is it true that $L(A) = L$? If so can you point some directions on how to prove it?

# Answer
> 4 votes
The language $L$ only depends on the first $t$ letters of the input (since the Turing machine never gets to any of the other letters). This implies that it is regular, since $$ L = (L \cap \Sigma^{\<t}) \cup (L \cap \Sigma^t) \Sigma^\*, $$ where $\Sigma^{\<t} = \bigcup\_{i=0}^{t-1} \Sigma^i$. The right-hand side is regular since $L \cap \Sigma^{\<t}$ and $L \cap \Sigma^t$ are both finite, and so, regular.

---
Tags: turing-machines, computability, regular-languages
---


# Question
Title: If $L = \{ a^{2^n} \mid n \ge 0 \} $ is not regular, then why there is a DFA thats accepts its language?
Let $L = \\{ a^{2^n} \mid n \ge 0 \\}$, which is a non-regular language (no proof here). Let $M = (\Sigma,Q,\delta,z\_0,F)$ be a DFA with $\Sigma = \\{a\\}$, $Q = \\{z\_0\\}$, $\delta(z\_0, a) = z\_0$ and $F = \\{z\_0\\}$. Then the DFA should accept $L$ and $L$ is therefore regular. Why is my approach wrong?

# Answer
> 3 votes
The definition of an automaton accepting a language is that it must

1. accept every string that is in the language;
2. reject every string that is not in the language.

Your automaton does 1. but not 2. – it accepts all strings of $a$s, but it's supposed to reject all the strings whose length is not a power of two.

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


# Question
Title: Resource Allocation Graph: Two processes want the same resource
In the example below, is this guaranteed to be safe? I see two processes that require the same resource. It's not a direct cycle but it seems to be a possible deadlock where P0 could get held up.

# Answer
Where is the problem here?is there a missing edge from ur graph?....As I see it : R3 could be assigned to P1 till it finishes, then to P2 (or vice verca), finally when both P1 & P2 finishes P0 could get R1,R2 (freed by now)
> 0 votes

---
Tags: graphs, resource-allocation
---


# Question
Title: Algorithms - Solving recurrence-relations/Bounds?
I'm currently in a course, and I for the life of me cannot figure out what my professor is doing. I could really use a working example, and I was hoping someone here might oblige.

Suppose we have this recurrence:

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

How would we figure out running time for this, and specifically, how would we PROVE the upper and lower bounds (ideally as tight as possible)?

I tried working through my homework with the help of a few YouTube videos, but I don't seem to be following it. In giving an explanation, please try and be careful to explain why something is a certain time, as I haven't really gotten the hang of intuiting that yet.

I have some working knowledge of induction and calculus, but it seems like I'm missing a big chunk of context somewhere and I really need to get up to speed. Thank you for any assistance.

# Answer
> 6 votes
First of all, a recurrence is not necessarily about the running time of anything. So you don't figure out "the running time", you solve the recurrence.

Second, your recurrence only possibly makes sense for powers of 2, and even then, it needs a base case. I'll assume that $T(1) = C$.

You can use the master theorem to solve your recurrence, but you can also do it directly. First you expand it (for simplicity, I'm assuming the base of the logarithm is 2): $$ \begin{align\*} T(2^k) &= k + 2T(2^{k-1}) \\ &= k + 2(k-1) + 4T(2^{k-2}) \\ &= k + 2(k-1) + 4(k-2) + \cdots + 2^{k-1}(k-(k-1)) + 2^k T(1) \\ &= (1+2+\cdots+2^{k-1})+(1+2+\cdots+2^{k-2})+\cdots+(1) + 2^k C \\ &= (2^k-1)+(2^{k-1}-1)+\cdots+(2-1)+(1-1) + 2^kC \\ &= (2^k+\cdots+1)-(k+1) + 2^kC \\ &= 2^{k+1}-k-2 + 2^kC. \end{align\*} $$ If you want to be very pedantic, you can prove this by induction. In terms of $n=2^k$, this reads $$ T(n) = (2+C)n-\log n - 2 \sim (2+C) n. $$ In particular, $T(n) = \Theta(n)$. You could also get this conclusion from case 1 of the master theorem.

# Answer
> 1 votes
It's probably easier solving this using the **Master Theorem**.

T ( n ) = 2 T ( n / 2 ) \+ log  n

So in this case **A=2**, **B=2**, and **D=0** because **f(n) = log n** and n^0 * log n = log n

We of course assume the base case is a constant such that **T(1) = C**

So we can easily see that the answer for this is  **T ( n ) = Θ ( n )** , since A is greater than B to the power of D.

We can see that is true just by plugging in the values

= A \> B^D

= 2 \> 2^0

= 2 \> 1 (which is always true)

This guy on YouTube has a very nice video explaining how to solve recurrences using the Master theorem, I will leave the link here.

---
Tags: algorithms, recurrence-relation
---


title: Solve Recurrence Relation

text:
# Question
Title: Solve Recurrence Relation
I'm trying to solve the following recurrence relation. I've gotten through two iterations, but I don't see any pattern. I would appreciate any help with this.

$T(1)=1$

$T(n)=6\ T(n/6)\ +\ 2n\ +\ 3$

I've manually ran through two iterations and found the following:

$T(n/6)= 36T(n/36)+14n+21$

$T(n/36)=216(n/216)+86n+129$

The pattern that I see is:

$T(n) = 6^k(n/(6^k))+ (I\ can't\ determine\ the\ pattern\ of\ these\ terms)$

# Answer
Hint:

$$T(n)=6\ T(n/6)\ +\ 2n\ +\ 3$$

$$T(n)=6\ (6\ T(n/6^2)\ +\ 2(n/6)\ +\ 3)\ +\ 2n\ +\ 3$$

$$T(n)=6\ (6\ (6\ T(n/6^3)\ +\ 2(n/6^2)\ +\ 3)\ +\ 2(n/6)\ +\ 3)\ +\ 2n\ +\ 3$$

Distribute the 6's.
> 0 votes

# Answer
It's probably easier solving this using the **Master Theorem**.

T(n) = 6T(n/6) + 2n + 3

So in this case **A=6**, **B=6**, and **D=1** because **f(n) = 2n + 3** and 2n^1 + 3 = 2n + 3

We of course assume the base case is a constant such that **T(1) = C**

So we can easily see that the answer for this is  **T ( n ) = Θ ( n log n )** , since A is equal to B to the power of D.

We can see that is true just by plugging in the values

= A = B^D

= 6 = 6^1

= 2 \> 1 (which is always true)

This guy on YouTube has a very nice video explaining how to solve recurrences using the Master theorem, I will leave the link here.
> 1 votes

---
Tags: recurrence-relation
---


title: Detecting Hamiltonian path in a graph

text:
# Question
Title: Detecting Hamiltonian path in a graph
There are various methods to detect hamiltonian path in a graph.

1. Brute force approach. i.e. considering all permutations T(n)=O(n\*n!)
2. Backtracking T(n)=O(n!)
3. Using Dynamic programming T(n)=O(2^n * n^2)

Now, there is one another method using topological sort. Topological sort has an interesting property: that if all pairs of consecutive vertices in the sorted order are connected by edges, then these edges form a directed Hamiltonian path in the DAG. If a Hamiltonian path exists, the topological sort order is unique. Also, if a topological sort does not form a Hamiltonian path, the DAG will have two or more topological orderings.

Approximation Algorithm: Compute a topological sort and check if there is an edge between each consecutive pair of vertices in the topological order.

I have a doubt that why is it considered as an approximate algorithm? Wouldn't it give correct output every time? What are the cases when it won't give correct output?

# Answer
> 3 votes
Hamiltonian Path *in a DAG* is easy to solve: You can find the longest path in $O(|V|+|E|)$ time using the critical path algorithm: https://en.wikipedia.org/wiki/Longest\_path\_problem#Acyclic\_graphs\_and\_critical\_paths. For unweighted DAGs, this sounds like essentially the same thing as your topological sort.

Hamiltonian Path is NP-hard on digraphs with cycles, and on undirected graphs.

---
Tags: algorithms, graphs, hamiltonian-path
---


# Question
Title: Data structure optimized for merging maps on partitions
My question is a request for literature or pointers that address the following abstracted problem. If I have a finite set (ex. `{1..10}`) over which I'd like to maintain several "partition maps":

* m1 = `{1..5}=1, {6..10}=2`
* m2 = `{1..3,8..10}=3, {4..7}=4`.

Afterwards I'd like to merge (generalize the operation, but use addition for demonstration) these maps:

m1 `+` m2 = m3 = `{1..3}=4,{4,5,8..10}=5,{6,7}=6`.

If `n` is the size of universal set, and `k << n` the size of the range of the maps. How does one get performance (and space) closer to `O(k)` as opposed to `O(n)` (store an array)?

Edit (2017-11-14): I'm mainly interested in merge performance, lookup can be slow. To sharpen the question, there are a couple of approaches to this problem that don't quiet address this trade off:

Edit (2017-11-15): The application where I'm using this performs millions of merges. In the most common instance I have 4 of these maps and compute a new map. The keys are different states and the values are actually probabilities. The probabilities are discretized which is why lots of different states have the same values. It is a form of "compressed" computations. I can use an array to store these values, but this compressed form provides 100x performance currently, but I'm looking for a technique to improve upon that (I need to do billion of merges). As @D.W. described below, batched techniques would also be of interest.

# Answer
> 1 votes
I can't say that I have a fully satisfactory answer to my question. But I spent a bit of time implementing and writing about a data-structure to solve my needs here. I call the data structure a partition map. It is really just an association lists of list of integer intervals and values. The former have nicer properties, resting on top of fairly straight-forward interval comparison logic.

# Answer
> 0 votes
Assuming that partitions are composed of ranges of consecutive integers (as in your example), use an interval tree. If there are $k$ intervals in the partitions, then the data structure takes $O(k)$ space. You can perform a lookup operation in $O(\log k)$ time. Taking the union of two maps of size $k\_1,k\_2$ can be done in $O(k\_1+k\_2 \log (k\_1+k\_2))$ time.

---
Tags: data-structures, runtime-analysis
---


# Question
Title: Why don't we delete a node in adjacency list after visiting an edge in Fleury algorithm?
I was reading an article on fleury's algorithm GeeksforGeeks. In fleury's algorithm, Once an edge is processed (included in Euler tour), we remove it from the graph. To remove the edge, we replace the vertex entry with -1 in adjacency list. Note that simply deleting the node may not work as the code is recursive and a parent call may be in middle of adjacency list.

I didn't understand why we can't delete that node, the recursive calls are already built inside the implicit stack. Why will it hinder that?

# Answer
> 0 votes
"Replace the entry with -1" is not part of Fleury's algorithm; that's part of *one implementation* of Fleury's algorithm, and it's just a way to remove the edge. You'll see that the English description of the algorithm at the web page you linked talks about removing an edge, not setting it to -1. If you don't like that description, pick another source, and you'll likely find that the other source talks about removing edges, too, not about setting entries to -1.

---
Tags: algorithms, graphs
---


# Question
Title: How to find LCA in a directed acyclic graph?
Firstly, I am trying to understand the meaning of LCA in DAG. I read a definition somewhere-"Define the height of a vertex v in a DAG to be the length of the longest path from root to v. Among the vertices that are ancestors of both v and w, the one with the greatest height is an LCA of v and w."

In a graph like this 1-\>3 1-\>4 2-\>3 2-\>4, 3 and 4 will have multiple LCA's because the height of 1 and 2 would be same.

So, How can I proceed to implement this? I am thinking of applying the same approach that we used to find LCA in a binary tree by starting from root node (In this case, nodes having in\_degree=0) but due to cross edges between the nodes this approach wouldn't work.eg. 1-\>2 1-\>3 3-\>2.

So, Is there some better way to find the LCA in DAG's?

# Answer
Assume that you want to find the ancestors of x and y in a graph.

Maintain an array of vectors- **parents** (storing parents of each node).

1. Firstly do a bfs(keep storing parents of each vertex) and find all the ancestors of x (find parents of x and using **parents**, find all the ancestors of x) and store them in a vector. Also, store the depth of each parent in the vector.
2. Find the ancestors of y using same method and store them in another vector. Now, you have two vectors storing the ancestors of x and y respectively along with their depth.
3. LCA would be common ancestor with greatest depth. Depth is defined as longest distance from root(vertex with in\_degree=0). Now, we can sort the vectors in decreasing order of their depths and find out the LCA. Using this method, we can even find multiple LCA's (if there).
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: how to defend against DOS caused by SYN cookies?
i have read about SYN cookies and i understood that they help to avoid DOS .. BUt my prof wants an answer as how SYN cookies can be used to cause DOS and how can it be avoided ? any help woul dbe really appreciated.. thanks in advance

# Answer
Computing syncookies requires taking a hash of the server and client's IPs and ports... These hashes may not be inexpensive esp if they are to be cryptographically secure. One way to DOS the syncookie code is to make so many requests that the CPU of the server is exhausted. I believe that Linux uses a less expensive (and not cryptographically secure) hash function, so this is less of an issue.

You could probably also spoof sender IP and use syncookies to be sent to a victim. But that is not that useful/ interesting.
> 0 votes

---
Tags: computer-networks, security
---


# Question
Title: How does the index of a disk work in finding the desired address?
I've been trying to understand computer concepts and such recently and I've been curious to know how the process works of a processor asking for an address and sending the bits to the hard drive, as well as how the hard drive index works when it's just a bunch of magnetic specs that cooperate with a mechanical arm. What does the index say to the system? How do the processor and HDD cooperate? Hopefully I'm asking on the right website this time due to the fact that I accidentally posted this question on the Computational Science site. Thanks

-Ryan

# Answer
The index specifies the cylinder, head, and sector where the data resides. The hard drive then moves the arm/head so it is positioned over that block and reads the data stored in that block as the disk rotates under the arm. The hard drive then sends that data back to the processor. Read http://pages.cs.wisc.edu/~remzi/OSTEP/file-disks.pdf for more of an overview how hard drives work.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: If a decision problem $A \in \text{NP}$ and there exists reduction so that $A \leq_p B$, for decision problem B, what can be deduced about B?
I think that it implies that B can be solved by a non-deterministic polynomial time or worse Turing machine, but I realise that there is possibly some greater result that I'm missing.

Thanks in advance.

# Answer
$B$ cannot be the language $\emptyset$ or the language $\Sigma^\*$. Apart from that, you can conclude absolutely nothing about $B$.

So, the given condition doesn't rule out anything useful about $B$; just about everything remains possible. $B$ could be in $P$, or it could be in $NP$, it could be harder than anything in $NP$; you can't rule any of those out.
> 1 votes

# Answer
PHPNick is right.

With A being NP we can conclude that B is atleast as hard as A if B was easier that is, if a polynomial time algorithm existed for B it could be used to solve A along with polynomial time conversion of B to A

Hence B might be p(if A is P) or NP or NP-hard or NP-complete While if A is NP B has to be atleast NP or it could be NP-hard or NP-complete
> 1 votes

---
Tags: turing-machines, reductions, np, polynomial-time
---


# Question
Title: Does the Working Set Paging Algorithm use a separate page table?
I am doing research on paging algorithms. While learning about the working set algorithm from several scientific sources I was not really able to figure out where exactly the working set is defined or realized.

I can only imagine two ways of realising this. The first is to put it into the page table file with indication bits; the second is to have another page table for the working set.

To be more specific: is the Working Set a completely **different, separate list derived from the page table entries**, or is it defined **in the page table entries**?

# Answer
> 1 votes
I spoke to my professor in operating systems about this matter. He told me, that it is up to the designer of the operating system how he realises the concept of the working set.

The working set **is defined by the page table entries**. The page table consists of the part for adressing the virtual and the possibly according physical adress and some extra bits, which could differ on different operating systems. Those bits like the "dirty"-bit, the valid-bit or the read-bit help to implement the paging algorithm.

If the working set is used in an operating system, there is **an actual need of the virtual time in the page table entry**. How this entry in the page table is used is up to the designer of the operating system. The working set could be realised by scanning the page table and finding the entries which by comparing the virtual time of use of the page to the virtual time of the process. Another approach can be to create lists for the complete working set or for different parts of the working set (like read-entries, modified-entries).

# Answer
> 1 votes
Denning provides a rough definition for a working set in Section 2:

> Roughly speaking, a working set of pages is the minimum collection of pages that must be loaded in main memory for a process to operate efficiently, without "unnecessary" page faults.

And provides the precise definition in Section 3:

> We define the working set of information `W(t, r)` of a process at time `t` to be the collection of information referenced by the process during the process time interval `(t - r, t)`.
>
> Thus, the information a process has referenced during the last `r` seconds of its execution constitutes its working set (Figure 2).

The term "page" in these definitions refers to physical pages, not virtual pages. That's because only those physical pages that have resided in main memory at least once during that period of time are part of the working set of a process.

> is the Working Set a completely different, separate list derived from the page table entries, or is it defined in the page table entries?

The working set is not defined by the page table entries. These entries define the whole virtual address space of the process. Also, by only looking at the page table entires, it's not possible to determine or derive the working set. The pages that are resident in main memory in a particular period of time and that have been accessed by the process in that period constitute the working set for that period.

Even if a page table entry includes an accessed bit (like the x86 page table entries) and even if the OS supports the accessed bits, it's still not possible to determine the working set just by looking at the page table entries. That's because the same page table entry may point to multiple physical pages during a period of time. At the end of that period, there is no way to determine all of the physical pages that any page table entry has defined during that period. So some additional data structures need to be used.

---
Tags: virtual-memory, paging
---


# Question
Title: How to prove that a bounded pushdown automaton is regular?
I'm studying computer science and I want to show that a language which is accepted by a pushdown automaton with a bounded stack height is regular, but I'm totally lost... Can someone try to explain how we can prove it ?

Thank you in advance!

# Answer
If the stack has bounded height then there are only finitely many possibilities for its contents. Therefore a regular automaton can “remember” the entire contents of the stack. In other words, you can convert the PDA into an equivalent regular automaton in which each state stores both the state of the PDA and the contents of its stack.
> 4 votes

---
Tags: regular-languages, automata, pushdown-automata
---


# Question
Title: What does "order of growth decreases exponentially" mean?
I understand than function decreases exponentially, then order of growth of this function is exponential with negative exponent. But what does it mean that *order of growth decreases exponentially*?

I don't understand what should i look for in this exercise:

> **Exercise 2.33** Find a recurrence describing a sequence for which the order of growth decreases exponentially for odd-numbered terms, but increases exponentially for even-numbered terms.

Could you provide several first items of such a sequence to let me understand the exercise?

# Answer
I think it just wants a recurrence for a sequence where the even-numbered terms increase exponentially and the odd-numbered terms decrease exponentially. Talking about the order of growth changing sounds like some kind of second-derivative property but I think it’s just poor phrasing.

To be absolutely sure, you’d have to ask the person who wrote the exercise.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Can you explain in terms of logic gates how Babbage’s Analytical Engine worked?
On a recent trip to the London Science Museum I saw Babbage’s Analytical Engine.

Apparently this had an ALU (or equivalent). Is the Analytical Engine binary? I can build an ALU out of logic gates but I can’t conceptualise how to do it with gears. I’m trying to map across the concepts.

My question is: **Can you explain in terms of logic gates how Babbage’s Analytical Engine worked?**

# Answer
The documentation is quite clear they're still working out what the design was supposed to be.

Taking an approximation - they have developed a Java program to run sample programs. The logic behind the source code shows how it may have worked.
> 1 votes

---
Tags: computer-architecture
---


title: Optimal pivot selection for quick-sort

text:
# Question
Title: Optimal pivot selection for quick-sort
The actual runtime of applying quick-sort to an integer array heavily relies on the choice of pivots.

It is well known that picking a random pivot does not work as good as taking the median of three, or the ninther of the array.

Obviously, for comparison we need to fix a model of computation / cost per operation.

Assume we are working in a model where each comparison between elements costs $1$, while swapping two elements costs $\gamma$ for some $\gamma\>0$.

If we invest more effort in finding a good pivot (e.g., take the median of $k$ random samples), we might make more comparisons, but swap less elements.

> **Under this model, what is the optimal (in terms of expected cost) pivot choosing strategy (i.e., if our array is of size $n$, how many elements $k$ should we sample before deciding which pivot to use)?**

(We assume that the input might be adversarial, so taking as pivot the median of uniformly sampled elements seems like the right thing to do).

# Answer
The first thing to note specifically for integer arrays is that quicksort might not be the best choice for sorting depending on the possible range of values. A counting sort may be more appropriate, for example.

In the general case (i.e. not specific to integers), Martinez and Roura analyzed this problem for both quicksort and (single order statistic) quickselect. See "Optimal Sampling Strategies in Quicksort and Quickselect" SIAM Journal on Computing http://dx.doi.org/10.1137/S0097539700382108

The short answer is that the optimal strategy is to pick as the pivot element the median of a sample of elements, with the sample size roughly proportional to the square root of the number of elements in the array to be sorted, unless swapping is extraordinarily expensive. Specifically for simple types (e.g. integers), swapping is not expected to be expensive; it may be less costly than comparison via a function call, as in qsort.

That strategy also changes the worst-case (adversarial input) performance from quadratic to polynomial with an exponent of 1.5; see also McGeoch and Tygar "Optimal Sampling Strategies for Quicksort" Random Structures and Algorithms http://dx.doi.org/10.1002/rsa.3240070403

Instead of using the exact median of the samples, a lower-cost option is to approximate the median with a pseudomedian. One which can be scaled with sample size and which provides an increasingly accurate estimate of the median as sample size increases is the remedian as described by Rousseeuw and Bassett in "The Remedian: A Robust Averaging Method for Large Data Sets" Journal of the American Statistical Association http://amstat.tandfonline.com/doi/pdf/10.1080/01621459.1990.10475311 See also Battiato et al. "An Efficient Algorithm for the Approximate Median Selection Problem" in Proceedings of the 4th Italian Conference on Algorithms and Complexity http://dl.acm.org/citation.cfm?id=648257.753042 (it's the same remedian, "rediscovered" by the authors about a decade after Rousseeuw and Bassett).

For an even deeper dive (especially regarding the importance of ***quality*** of sampling as well as quantity), see https://github.com/brucelilly/quickselect/blob/master/lib/libmedian/doc/pub/generic/paper.pdf or the video at https://www.youtube.com/watch?v=iWmAf4RMMiM There you'll also find a way to get the adversarial performance to remain linearithmic (as opposed to going polynomial) without deterioration in non-adversarial input performance.

You say

> If we invest more effort in finding a good pivot (e.g., take the median of k random samples), we might make more comparisons, but swap less elements.

What typically happens (for uniformly distributed random input) is that a better (i.e. closer to the true median) pivot results in ***fewer*** overall comparisons during sorting but ***more*** swaps. With a pivot close to the median every time, the number of comparisons to sort (ignoring comparisons for pivot selection) is $N \log _ 2 N$ and the number of swaps (if efficiently arranged) is 1/4 $ N \log _ 2 N$. On the other hand, a randomly selected pivot element leads to 1.386 $N \log _ 2 N$ comparisons but only 1/6 $N \log _ 2 N$ swaps (more than 8 times as many comparisons as swaps). The two are related; a reduction in the number of swaps implies a lopsided partition (about 78.9%/21.1% for 1/6 $N \log _ 2 N$ swaps) and that leads to an overall increase in the number of comparisons because the problem size is reduced by less than half. The key to minimizing comparisons is using an efficient pseudomedian, one which provides a good estimate of the median with much fewer comparisons than the ~2N which are expected to find the exact median. The remedian with base 3 computed on a sample of size $\sqrt {N}$ costs about 1.5 $\sqrt{N}$ comparisons, which is much less than 2N for reasonable N.
> 3 votes

# Answer
This paper \[\] describes \`hyper-quicksort': it uses an offline learning technique to empirically determine the value of $k$ which minimizes the power consumption of quicksort against a pathological adversary \[\].

\[\] Jerry Swan and Nathan Burles. “Templar - A Framework for Template-Method Hyper-Heuristics”. In: Genetic Programming - 18th European Conference, EuroGP 2015, Copenhagen, Denmark, April 8-10, 2015, Proceedings. 2015, pp. 205–216. doi: 10.1007/978-3-319-16501-1˙17.

\[\] "A Killer Adversary for Quicksort", M. D. McIlroy. Software Practice and Experience, 1999.
> 2 votes

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


# Question
Title: Arrival Time vs Burst Time vs Priority Time? If Priority Time is the same, which process dispatch first?
```
The question is based on if we have the same Priority value when we are given:

Arrival Time = AT, Priority and Burst Time=BT.
1.Say if we a table with AT, Priority and BT. To dispatch a process it is obvious that we check the AT first since we cannot predict the future.
2.If AT= 0 for all processes, we have to check the Priority.
**3.If p1 priority = p2 priority, what do we do next?**

Because of the equal PR value, now how do we draw a Gannt-Chart based on:
-FCFS
-SJF
-Priority Non-Preemptive

If all of them go by BT first, don't they all have the same Gantt-Chart since they are Non-preemptive.

After posting this, I decided to choose pick any process (random) when they have the same Priority value but I am not sure if they are correct. Actually there is only one question that affects the rest of the sub-questions but I just need to know that problem with the same Priority values above between two processes. If that one is answered, I could do the rest properly.

Thank you.

```

# Answer
```

1. Consider the following set of processes, with the length of the CPU burst and given in milliseconds:

Process    Time    Burst     Priority

P1                0           4            3

P2                0           7            2

P3                0           2            6

P4                0           5            1

P5                0           4            2

          WT                       BT

|----------------------- |-------------------------|

AT                                                 CT

|----------------------TAT-----------------------|

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5 all at time 0.

a.) Draw four Gantt chars that illustrate the execution of these processes using the following scheduling algorithms: FCFS, SJF, Non-preemptive Priority (a smaller priority number implies a higher priority), and RR (quantum=2).

b.) What is the turnaround time of each process for each of the scheduling algorithms in part a?

c.) What is the waiting time of each process for each of these scheduling algorithms?

Process    Time    Burst     Priority

P1                0           4            3

P2                0           7            2

P3                0           2            6

P4                0           5            1

P5                0           4            2

Complete Time = CT

Turn Around Time = TAT

Burst Time = BT

Wait Time = WT

Average Wait Time = AWT

WT = TAT - BT

TAT = CT - AT

Since they all arrived at time 0 but in order of P1, P2, P3, P4 P5. We run at P1 first down to P5 in order on FCFS disregarding the Priority
I think I got a lot of wrong here since I was not paying attention.
                                    CT-AT      TAT-BT
Process AT  Burst  Priority   CT     TAT        WT
p1      0    4         3      4       4         0
p2      0    7         2      11      11        4
p3      0    2         6      13      13        11
p4      0    5         1      18      18        13
p5      0    4         2      22      22        18

Gannt-Chart - FCFS

| p1  | p2   | p3    |   p4  |  p5  |
0     4     11      13      18      22
Needs a lot of corrections below:
AWT = (0+4+11+13+18)/5 = 46 / 5 = 9.2 ms

TAT = (4+11+13+18+22)/5 = 68/5=13.6 ms

******************

Gannt-SJF

1. Sort all the processes in increasing order according to burst time.

2. Then simply, apply FCFS.

There is a tie between P1 and P5 because Burst is 4 so two Gannt-Chart

P1 first

| p3  | p1   | p5   |   p4  |    p2 |
0     2     6      10       15     22

AWT = (0+2+6+10+15)/5 = 33/5 = 6.6 ms

TAT = (2+6+10+15+22)/5 =55/5= 11 ms

P5 first

| p3  | p5   | p1   |   p4  |    p2 |
0     2      6     10      15      22

AWT = (0+2+6+10+15)/5 = 33/5 = 6.6 ms

TAT = (2+6+10+15+22)/5 = 55/5 = 11 ms

*****************

Gannt-Chart - Non-preemptive Priority

1. Sort all the processes in increasing order according to priority

2. Then simply, apply FCFS.

There is a tie between p2 and p5 because priority is 2.

p2 first

| p4  | p2   | p5    |   p1  |    p3    |
0     5     12      16       20        22

AWT = (0+5+12+16+20)/5 = 10.6 ms

TAT =(5+12+16+20+22) /5 = 75/5 =15 ms

p5 first

| p4  | p5   | p2   |   p1  |    p3    |
0     5      9     16      20         22

AWT = (0+5+9+16+20)/5 = 10 ms

TAT = (5+9+16+20+22)/5 = 14.4 ms

*************************
Gannt-Chart Round Robin (Quantum=2)

|p1  |p2 |p3  |p4 |p5  |p1  |p2  |p4  |p5  |P2  |p4 |   p2 |
0    2   4    6   8   10    12   14   16   18   20   21   22

AWT = (8+15+4+16+14)/5 = 11.4 ms

TAT = (12+22+6+21+18)/5= 79 / 4 = 15.8 ms

```
> -1 votes

---
Tags: process-scheduling
---


title: unambiguous equivalent grammar

text:
# Question
Title: unambiguous equivalent grammar
There is a grammar G given:

```
    S->XaX
    X->aX|bX|eps

```

I just replied to the first question that was about showing that this grammar is ambiguous. The second question is to find an unambiguous equivalent grammar of this grammar given. I don't really know how to do it or from where to start. Can anyone help me?

# Answer
> 1 votes
Your language consists of all words over $\\{a,b\\}$ which contain $a$. This is a regular language, and so it has an unambiguous regular grammar - essentially a DFA - which is not so difficult to construct for this language. Regular grammars constructed from DFAs are unambiguous, so this would be an unambiguous grammar for the same language.

---
Tags: regular-languages, finite-automata, ambiguity
---


title: What does $\overline{L}^*$ signify?

text:
# Question
Title: What does $\overline{L}^*$ signify?
Suppose that $L$ is a language.

* What does $\overline{L}^\*$ signify?
* Is $\overline{L^\*}$ the same as $(\overline{L})^\*$?

# Answer
> 2 votes
For any language $L$ over alphabet $\Sigma$,

* $\overline{L} = \Sigma^\*\setminus L$ is the complement of $L$: the set of $\Sigma$-strings *not* in $L$;
* $L^\*$ is the *Kleene closure* of $L$: the set of strings $w\in\Sigma^\*$ such that we can write $w=w\_1\dots w\_k$ for some $k\geq 0$ such that each $w\_i\in L$. For example, if $L$ is the set of English words, then correcthorsebatterystaple is in $L^\*$.

Now, $\overline{L}^\*$ is something-star, where "something" is $\overline{L}$. That is, it's the Kleene closure of the complement of $L$: the set of all strings $w\in\Sigma^\*$ that can be written $w\_1\dots w\_k$ such that each $w\_i$ is *not* in $L$. Essentially, we read left-to-right, so you parse "$\overline{L}$" before you reach the star.

Conversely, $\overline{L^\*}$ is something-complement, where "something" is $L^\*$, the Kleene closure of $L$. That is, it is the set of all strings that *cannot* be written $w\_1\dots w\_k$ where each $w\_i\in L$.

These are not necessarily the same languages. For example, consider $\Sigma=\\{1\\}$ and $L=\\{11\\}$. Then $1\in\overline{L}$, so $\overline{L}^\*=\Sigma^\*$. However, $$\overline{L^\*} = \overline{\\{1^i\mid i\text{ is even}\\}} = \\{1^i\mid i\text{ is odd}\\}\neq\Sigma^\*\\,.$$

---
Tags: formal-languages, notation
---


# Question
Title: Erlang- Creating a function which only adds/subtracts positive integers
I want to create a function which allows me to input a list, and then add all of the positive numbers from the list together, leaving any that are negative.

(\[3,1,-1\]) For example only 3 and 1 would be added from this list.

Would I right in thinking the function should be recursive and have a guard?

# Answer
You don’t need recursion if you use high-order functions and/or List Comprehensions…

```
sum_positives(List) ->
  lists:sum([X || X <- List, X > 0]).

```

But you might prefer the recursive version of it…

```
sum_positives([]) -> 0;
sum_positives([X|Rest]) when X > 0 -> X + sum_positives(Rest);
sum_positives([_|Rest]) -> sum_positives(Rest).

```
> 0 votes

---
Tags: programming-languages, concurrency, functional-programming
---


# Question
Title: Can anyone give an example for worst case of quick sort if we employ median of three pivot selection?
If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also can anyone give an example including integers?

Thanks.

Note: I have searched online for quicksort's worst case, but all of them are referring to quicksort wherein the pivot is either the first element or the last element, but what I want is completely different.

# Answer
> If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also can anyone give an example including integers?

The worst case is when the selected pivot reduces the problem size by the smallest possible amount, i.e. provides as lopsided a partition as is possible. For the median of three elements, that cannot be either the largest or smallest valued element (assuming distinct values), as the definition of median ensures that in median of 3, there is one larger and one smaller element than the median.

For the rather poor but all too common case of using the median of the first, middle, and last elements (with distinct valued input), that worst case occurs when the median of the three is the second-smallest or second-largest valued element (because the largest or smallest is one of the other two of those three). That can occur when an in-order sequence of elements is rotated by just one position. Here are two examples:

1 2 3 4 5 6 7 8 0 (median of 1,5,0 is 1)

8 0 1 2 3 4 5 6 7 (median of 8,3,7 is 7)

When median of first, middle, last pivot selection is combined with most commonly used partitioning methods, the result is disastrous; each partition peels off two elements (the pivot and one extreme value) and leaves another rotated sequence remaining. The combination of first, middle, last pivot selection and a partitioning method which swaps the pivot to the first (or last) array position (rather common) is worse; it also generates rotated sequences when the input is reverse-sorted (e.g. 8 7 6 5 4 3 2 1 0).

See https://github.com/brucelilly/quickselect/blob/master/lib/libmedian/doc/pub/generic/paper.pdf and/or the video at https://www.youtube.com/watch?v=iWmAf4RMMiM for details and examples of some widely-used implementations that exhibit this behavior.

When input values are not distinct, another bad case for median of first, middle, and last elements is "organ-pipe" (bitonic) input, such as

0 1 2 3 4 3 2 1 0 (median of 0,4,0 is 0)

In the case of organ-pipe input, use of first, middle, and last elements is the worst possible choice of three elements for pivot selection!
> 9 votes

---
Tags: algorithms, time-complexity, asymptotics, quicksort
---


# Question
Title: Determining whether $L^*$ is a finite union of $L^n$ for unary regular $L$
> Give an algorithm that, given an NFA over a one-letter alphabet, determines whether the language it generates has the property that for some $n$, $$ L^\* = \bigcup\_{k=0}^n L^k. $$

I need some tips how to solve that.

# Answer
We can identify every unary regular language $L$ with the set $S = \\{ n : 1^n \in L \\}$. It is known that $S$ is eventually periodic, that is, $$ S = A \cup (B + m \mathbb{N}) = A \cup \\{ b + mn : b \in B, n \in \mathbb{N} \\} $$ for some finite $A,B$ and $m \geq 1$. Let us consider four cases:

**Case 1.** $S$ is empty. In this case, $S^\* = S^0$.

**Case 2.** $S$ is finite and non-empty. In this case, $S^\*$ is infinite but $S^0 \cup \dots \cup S^n$ is finite for all $n$.

**Case 3.** $S = B + m\mathbb{N}$ for some non-empty $B$ and $m \geq 1$. I claim that $$ B^\* \bmod{m} = (B^1 \cup \dots \cup B^\ell) \bmod{m} $$ for some finite $\ell$. Indeed, if $i \in B^\* \bmod{m}$ then $i \in B^j \bmod{m}$ by definition of $B^\*$ for some $j \geq 1$ (when $i = 0$ we can take $j = m$), so we can take $\ell$ to be the maximum of the $j$'s. It follows that $$ S^+ = \bigcup\_{i \in B^\* \bmod m} n\_i + m \mathbb{N}, \text{ where } n\_i \equiv i \pmod{m}, \\ S^1 \cup \cdots \cup S^\ell = \bigcup\_{i \in B^\* \bmod m} n'\_i + m \mathbb{N}, \text{ where } n\_i \equiv i \pmod{m}, $$ where $n'\_i \geq n\_i$. It follows that $S^\* \setminus (S^0 \cup \cdots \cup S^\ell)$ is finite, and so $S^\* = S^0 \cup \cdots \cup S^r$ for some finite $r \geq \ell$, since every element in $S^\* \setminus (S^0 \cup \cdots \cup S^\ell)$ appears in some $S^j$.

**Case 4.** $S = A \cup (B+m \mathbb{N})$ for some non-empty $A,B$ and $m \geq 1$. Let $C = A \cup B$. As before, $$ C^\* \bmod m = (C^0 \cup \cdots \cup C^\ell) \bmod m $$ for some finite $\ell$. Since $B$ is non-empty, $(B+m \mathbb{N})^m$ contains some multiple of $m$, and so all large enough multiples of $m$. Assuming $\ell \geq m$, it follows that $$ S^\* = D \cup \bigcup\_{i \in C^\* \bmod m} n\_i + m \mathbb{N}, \text{ where } n\_i \equiv i \pmod{m}, \\ S^0 \cup \cdots \cup S^\ell = D' \cup \bigcup\_{i \in C^\* \bmod m} n'\_i + m \mathbb{N}, \text{ where } n\_i \equiv i \pmod{m}, $$ where $D \supseteq D'$ are finite and $n'\_i \geq n\_i$. It follows that $S^\* \setminus (S^0 \cup \cdots \cup S^\ell)$ is finite, and so $S^\* = S^0 \cup \cdots \cup S^r$ for some finite $r \geq \ell$.

**Conclusion.** The property $S^\* = S^0 \cup \cdots \cup S^n$ holds for some finite $n$ unless $S$ is finite and non-empty. Given a finite automaton for $L$, this condition is easy to check (in linear time).
> 1 votes

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


# Question
Title: If Q1 and Q2 are countably enumerable, then is Q1\Q2 countably enumerable?
If Q1 and Q2 are countably enumerable, then is Q1\Q2 countably enumerable?

I am reading a text where they claim that this is not the case and ask the reader to come up with a counter example.

Can someone give a counter example to the claim that if both Q1 and Q2 are c.e. then so is Q1\Q2?

Since H is semi-decidable and hence also c.e., I was thinking of coming up with examples using it, but no success till now.

# Answer
First of all, notice that not all c.e. sets have a c.e. complement, i.e. there are c.e. sets like $Q$ such that $Q^c=\mathbb{N}-Q$ is not c.e. In fact the *Halting Problem* $H$ is such a c.e. set.

To see why $H^c$ is not c.e., notice that if both a set and its complement are semi-decidable, then both are also decidable. And since $H$ is not decidable, then $H^c$ should not be semi-decidable either.

Now for the counter example to your question, let $Q\_1 = \mathbb{N}$ and $Q\_2 = H$. Then $\mathbb{N} - H = H^c$, is not c.e.

---

**Edit:** Explained $H^c$ and added a simpler and more straightforward counter example.
> 1 votes

---
Tags: computability, semi-decidability
---


# Question
Title: What is the difference between a page and thread?
"Each process that is executed is divided into blocks of same size, called pages." "Thread is a part of process being executed."

Are pages and threads both part(s) of process? Whats the difference between **thread as a part of process** and **page as a part of process**?

# Answer
You're looking at very vague descriptions and asking "What's the difference between these things that haven't been described properly?" For a more detailed understanding, you should, well, look for more detail, which is widely available.

A page is a block of memory; a thread is a sequence of instructions to be executed.
> 4 votes

# Answer
Paging is something to deal with memory management and Thread is an instance of a program . When we execute a multithreaded program it may have to refer memory addresses , so a thread might use a page table to access the main memory address.
> 0 votes

---
Tags: memory-management, virtual-memory, process-scheduling, paging, threads
---


title: Using the Consequence Rule

text:
# Question
Title: Using the Consequence Rule
I have the following example that I have to prove

```
{a>7 ^ b>=0} n:=a-b {n<a ^ a+b>=0}

```

Using the Consequence Rule I assumed that the P is true

```
{true} n=a-b {n<a ^ a+b>=0}

```

so logically, the Q should be true, but I'm not sure if that'd be enough.

# Answer
> 1 votes
Here is what you need to prove:

> If $a \> 7$, $b \geq 0$ and $n = a-b$ then $n \< a$ and $a+b \geq 0$.

By the way, this is actually false, since if $b = 0$ then $n = a$. Perhaps you miscopied?

# Answer
> 1 votes
To do this systematically, with the rules of Hoare logic, proceed as follows.

First, use the assignment axiom to generate a valid Hoare triple of the form $\\{\phi\\}n \mathbin{:=}a-b\\{n\<a \land a+b\geq 0\\}$.

Then use the consequence rule to derive the Hoare triple you're after. Besides the Hoare triple we just found, this instance of the consequence rule will have a premise $a\>7 \land b\geq 0 \Rightarrow \phi$. You need to prove that it is valid, too, but that's a maths task independent of Hoare logic. As Yuval observed in his informal explanation, you will fail to prove this.

---
Tags: correctness-proof, hoare-logic
---


# Question
Title: Making a CFG for a^i b^j c^k such that i+j = 3k
I have the language $L = \\{a^i b^j c^k \mid i+j=3k\\}$, however I am struggling to convert it to a CFG.

I have made it into a PDA fairly easily, its just now getting this to the CFG which is the issue.

I have thought about dividing it into 3 cases then taking the union of them for example:

$i=0, j=3k$

$i=3k, j=0$

But this still hasn't gotten me very far

Any help would be appreciated Thanks

# Answer
I am not sure whether it is a good idea to actually provide the grammar here in an answer but since the grammar is actually fairly easy I cannot see which details I could hide in a hint, so here it is:

$G = (\\{S, A\\}, \\{a, b, c\\}, P, S)$ with $$ P = \\{S \to aaaSc \mid aabAc \mid abbAc \mid bbbAc \mid \varepsilon, A \to bbbAc \mid \varepsilon\\}.$$ You start by adding three $a$s for each $c$, after finitely many (possibly 0) applications of the first rule, you start creating three $b$s for each $c$ but one time you may actually add 2 $a$s, 1 $b$ for one $c$ or 1 $a$, 2 $b$s for one $c$ (2nd and 3rd rule, respectively).
> 2 votes

# Answer
$L = \\{a^i b^j c^k \mid i+j=3k\\}$. You need to match up two counts; this can only be done by having a middle-recursive set of rules that generate both parts in correct proportions. All you need is $X \Rightarrow^+ \alpha X \beta$, with $\alpha$ generating 3 $a$s and $b$s, $\beta$ generating 3 $c$s. This can be a single rule, and $X$ can just be the start symbol $S$, so let's start with

$S \rightarrow\epsilon \mid T S ccc$

$T$ must generate $a^ib^{3-i}$ for all $i$, a finite language, so we can just have a rule for each member:

$T \rightarrow aaa \mid aab \mid abb \mid bbb$

We can substitute $T$ into the rule for $S$ to arrive at PHPNick's answer.
> 0 votes

---
Tags: context-free, formal-grammars, pushdown-automata
---


# Question
Title: Proving the correctness of a square summing algorithm
```
int sumHelper(int n, int a) {
   if (n==0) return a;
   else return sumHelper(n-1, a + n*n);
}

int sumSqr(int n) {
    return sumHelper(n, 0);
}

```

I am supposed to prove this piece of code which uses tail recursion to sum up the squares of numbers. That is, I need to prove that for $n ≥ 1$, $sumsqr(n)=1^2+2^2+\dots+n^2$. I have figured out the base case but I am stuck at the induction step. Any hints or help will be appreciated.

# Answer
> 2 votes
Assuming $n ≥ 0$, let $$ P(n) \\;≡\\; ∀ a.\\, sumHelper(n, a) = a + ∑\_{i = 0}^n i² $$

Then we prove this is always true by induction on $n$.

The base case, `n = 0`:

```
  sumHelper(n, a)
={ Case n = 0 }
  sumHelper(0, a
={ Definition }
  a
={ Arithmetic }
  a + 0²
={ Arithmetic }
  a + ∑_{i = 0}^0 i²
={ Case n = 0 }
  a + ∑_{i = 0}^n i²

```

The induction step, assuming `P(n)` let us show `P(n+1)`,

```
 sumHelper(n+1, a)
={ Definition }
  if   (n+1==0) a
  else sumHelper(n+1-1, a + (n+1)*(n+1))
={ Since we assumed n ≥ 0, we have n+1 ≠ 0.
   Hence we have the else-branch. }
  sumHelper(n+1-1, a + (n+1)*(n+1))
={ Arithmetic }
  sumHelper(n, a + (n+1)*(n+1))
={ Apply the inductive hypotheis with a ≔ a + (n+1)*(n+1) }
  (a + (n+1)*(n+1))) + ∑_{i = 0}^n i²
={ Arithmetic: Bringing the `n+1` term back into the sum }
  a + ∑_{i = 0}^{n+1} i²

```

We're done :-)

# Answer
> 1 votes
The function `sumHelper` implements the recurrence

$$a\_n=a\_{n-1}+n^2,\\ a\_0=0,$$

the solution of which is

$$a\_n=\sum\_{k=1}^n k^2.$$

---
Tags: recursion, induction
---


# Question
Title: Is relation following given characteristic already in 2NF, 3NF and BCNF?
The definitions of 2NF, 3NF and BCNF goes like this:

> **2 Normal Form (NF) definition**
> A relation is in second normal form if and only if it is in first normal form and all the non-key attributes are fully functionally dependent on the candidate key.
>
> **3 NF - definition**
> A relation schema $R$ is in third normal form (3NF) if, whenever a nontrivial functional dependency $α→β$ holds in $R$, either
>
> 1. $α$ is a superkey of $R$, or
> 2. $β$ is a prime attribute of $R$.
>
> **BCNF (Boyce–Codd normal form) - definition**
> A relation schema $R$ is in BCNF, if whenever a nontrivial functional dependency $α→β$ holds in $R$, $α$ is a superkey in $R$.

Based upon these decision, I want to know if the relation having below characteristic is already in some normal form.

**All candidate keys are of single attributes:** this one is definitely in 2NF as there cannot be any partial dependency, but full functional dependency on CK. I am more confused about 3NF and BCNF. I feel its not in 3NF and BCNF since there can exist $\alpha \rightarrow \beta$, such that both $\alpha$ and $\beta$ are non key, violating 3NF and BCNF definitions.

Am I right with this?

# Answer
> 0 votes
Consider a relation schema `R(A, B, C)`, with the functional dependencies:

```
A → B
B → C

```

In this schema there is only one candidate key (`A`), and it has a unique attribute. But the schema is not in BCNF, since `B` is not a superkey, neither in 3NF, since `C` is not a prime attribute.

So your intuition is correct.

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


title: Weighted probability using Huffman Tree

text:
# Question
Title: Weighted probability using Huffman Tree
I want to produce a value from a set, where each value has an associated weight.

Eg:

```
[(1, 4), (2, 3), (3, 3)]

```

should give me a 40% chance of picking 1, and a 30% chance of picking 2 or 3 respectively.

Using a cumulative sum table and binary searching on it yields the value I want in O(logN) where N is the number of values in the set.

I was thinking of another approach to this using a huffman tree (as described here) with the combined weights of its children stored on each node.

For the above case, the tree would look like

```
    (10)
   /    \
(1, 4)  (6)
       /   \
   (2, 3) (3, 3)

```

The algorithm for `generate()` would be something like:

* Generate random number *k* in range \[0, {value of root node})
* Start at root node
* If at a leaf node, return value
* If *k* \>= {value of left child}, go right else go left
* Repeat from third step.

Now, in the case that the weights are about the same, this will take O(logN), similar to the binary search method.

However, if the weights increase in an exponential manner and the tree essentially becomes a list, the complexity becomes

$$ \sum\limits\_{i=1}^N k/2^k $$

Which tends to 2.

I'm having some difficulty coming up with an expression for the average case for generate, but it definitely has an upper bound of O(logN) and a lower bound of O(1). Of course, worst case is O(N).

What's a good approach to figuring this out, and what are the possible pitfalls of this kind of an approach?

# Answer
> 2 votes
Given a distribution $\mu$ on a finite set, let us denote by $T(\mu)$ the average depth of a leaf in a Huffman tree of $\mu$ (depth is measured by the number of edges from root to leaf); we assume that no element has zero probability. Then $$ H(\mu) \leq T(\mu) \< H(\mu)+1, $$ where $H(\mu) = \sum\_i \mu\_i \log\_2 (1/\mu\_i)$ is the entropy of $\mu$ (here $\mu\_i$ is the probability of the $i$th element).

To prove this, let us start with *Kraft's identity*. In the statement below, a *complete binary tree* is one in which every internal node has exactly two children.

**Kraft's identity.** There is a complete binary tree whose leaf depths are the multiset $\\{\ell\_1,\ldots,\ell\_n\\}$ if and only if $\sum\_{i=1}^n 2^{-\ell\_i} = 1$.

**Proof.** Let us first show that the leaf depths satisfy Kraft's identity. The proof is by induction on $n$. If $n = 1$ then $\ell\_1 = 0$, and indeed $2^{-\ell\_1} = 1$. Otherwise, arbitrarily choose two sibling leaves, and remove them. If the original depth was $\ell$, this affects the multiset of depths by removing $\ell,\ell$ and adding $\ell-1$. The induction hypothesis shows that the new multiset satisfies Kraft's identity. Since $2^\ell + 2^\ell = 2^{\ell-1}$, the original multiset also does, completing the proof.

Let us now show that if a multiset $L$ satisfies Kraft's identity, then there is a complete tree whose leaf depths are $L$. Once again, the proof is by induction on $n = |L|$. If $n = 1$, then necessarily $L = \\{0\\}$, and the tree consisting of a single leaf works. Otherwise, let $\ell = \max L$. Notice that $$ 2^\ell = \sum\_i 2^{\ell - \ell\_i}. $$ If $\ell\_i = \ell$ then $2^{\ell - \ell\_i} = 1$, and if $\ell\_i \< \ell$ then $2^{\ell - \ell\_i}$ is even. Hence the number of copies of $\ell$ in $L$ is even, and in particular there are at least two such copies. Let us form $L'$ by removing two copies of $\ell$ and replacing them by a copy of $\ell-1$. Applying the induction hypothesis, we obtain a tree $T'$ whose leaf depths are $L'$. By construction, $T'$ has a leaf of depth $\ell-1$. Adding to it two children, we obtain a tree $T$ whose leaf depths are $L$, completing the proof. $\square$

We can now prove the inequalities on $T(\mu)$, starting with $T(\mu) \geq H(\mu)$.

**Lower bound on $T(\mu)$.** Consider *any* tree whose leaves are labeled by the support of $\mu$, and suppose that element $i$ is on a leaf at depth $\ell\_i$. Let $\nu\_i = 2^{-\ell\_i}$. Kraft's identity shows that $\sum\_i \nu\_i = 1$. Since $\ell\_i = \log\_2(1/\nu\_i)$, we have $$ T(\mu) - H(\mu) = \sum\_i \mu\_i (\ell\_i - \log\_2 (1/\mu\_i)) = \sum\_i \mu\_i \log\_2 (\mu\_i/\nu\_i). $$ The function $\log\_2 (1/x)$ is convex, hence Jensen's inequality shows that $$ \sum\_i \mu\_i \log\_2 (\mu\_i/\nu\_i) = \sum\_i \mu\_i \log\_2 \frac{1}{\nu\_i/\mu\_i} \geq \log\_2 \frac{1}{\sum\_i \mu\_i (\nu\_i/\mu\_i)} = 0, $$ using $\sum\_i \nu\_i = 1$. We conclude that $T(\mu) \geq H(\mu)$. $\square$

The other direction uses Shannon–Fano coding.

**Upper bound on $T(\mu)$.** Let $\ell\_i = \lceil \log\_2 (1/\mu\_i) \rceil$. Then $$ \sum\_i 2^{-\ell\_i} \leq \sum\_i 2^{-\log\_2 (1/\mu\_i)} = \sum\_i \mu\_i = 1. $$ If $\sum\_i 2^{-\ell\_i} \< 1$, let $\ell = \max\_i \ell\_i$. Notice that $$ \sum\_i 2^{\ell-\ell\_i} \< 2^\ell, $$ where all summands are integral. If we decrement one copy of $\ell$ to $\ell-1$ then we increase the left-hand side by $2^{\ell-(\ell-1)} - 2^{\ell-\ell} = 1$, so the left-hand side is still at most $2^\ell$. Hence after the update, we still have $\sum\_i 2^{-\ell'\_i} \leq 1$, where $\ell'\_i$ are the new values. Continue doing so until the sum reaches 1; this must happen, since the decreasing process cannot continue forever (the depths keep decreasing while never dipping below zero). Denoting by $r\_i$ the new values, Kraft's identity implies that there exists a tree whose leaf depths are the $r\_i$. The average depth of a leaf in this tree is $$ \sum\_i \mu\_i r\_i \leq \sum\_i \mu\_i \ell\_i \< \sum\_i \mu\_i (\log\_2 (1/\mu\_i) + 1) = H(\mu) + 1. $$ Huffman's algorithm will find a tree which is at least as good. $\square$

Finally, let me show that for every $\epsilon\>0$ there are distributions $\mu$ for which $T(\mu) \geq H(\mu) + 1 - \epsilon$. Given $\delta\>0$, consider the distribution $\mu$ on two elements with $\mu\_1 = 1-\delta$ and $\mu\_2 = \delta$. Clearly $T(\mu) = 1$, while $\lim\_{\delta\to0} H(\mu) = 0$. Therefore we can find positive $\delta$ for which $H(\mu) \leq \epsilon$. For such $\mu$ we have $T(\mu) = 1 \geq H(\mu) + 1 - \epsilon$.

What happens if we force all probabilities to be small? Gallager, in his classic paper Variations on a theme by Huffman showed that even in this regime, there are distributions for which the gap is roughly $\log\_2 \[(2/e)\log\_2 e\] \approx 0.086$. Amazingly, this is attained by uniform distributions!

---
Tags: time-complexity, binary-trees, randomized-algorithms, average-case, huffman-coding
---


# Question
Title: Solving a variant of the Exact cover problem
I am trying to solve a variant of the Exact cover problem where every element has to be covered exactly twice instead of once ( i.e. has to be in exactly two sets that are part of the cover).

Now, it is clear to me that this is an NP-complete problem, but I wish to know if there is any hope for some pseudo-polynomial time algorithm to solve this problem.

If relevant, the context arose from trying to recreate polyhedra from their edges: given a set of edges, decide if they constitute some polyhedron, and if they do, give a set of its faces. Thus the set I wish to cover is the set of edges, and the collection of subsets I have is that of objects that can possibly be faces (each containing the edges of the corresponding "face")

# Answer
> 1 votes
There's no pseudopolynomial algorithm for exact cover (unless P=NP), so it is easy to show that this implies there is no pseudopolynomial algorithm for twice-exact-cover, either.

For instance, here's an easy reduction. Given an instance $(S,X)$ of exact cover (where $S$ is a collection of subsets of $X$), let $X' = X \cup \\{a\\}$ where $a \notin X$ is a new symbol, and $S' = S \cup \\{X', \\{a\\}\\}$. Now there is a twice-exact-cover for $(S',X')$ iff there is an exact cover for $(S,X)$. So, if you could solve twice-exact-cover in pseudopolynomial time, you could solve exact cover in pseudopolynomial time, too.

---
Tags: np-complete, computational-geometry, pseudo-polynomial
---


title: Correctness of lower bound proof

text:
# Question
Title: Correctness of lower bound proof
I am working on this exercise with the purpose of learning how to provide proper proofs and I would like to know if my proof for the following problem is correct.

> Given a sorted array $A$ (of $n$ distinct elements) and three elements $x$, $y$, and $z$, where $x \< y \< z$. The problem is to determine whether $x$, $y$, and $z$ are in $A$ or not. Prove that any comparison-based algorithm for this problem needs at least $3\log n-c$ comparisons in the worst case, where $c \> 0$ is some constant.

My current proof using a decision tree goes as follows: A comparison based algorithm must have at least 2 outcomes per a single comparison. For example: \>= or \<. It can also have 3 outcomes: \< or = or \>. But it has to have at least two.

When trying to decide whether an element is in the array or not it could be equal to any of the $n$ elements or it might not be in the array. Thus we have $n+1$ leaves in the decision tree.

Because of this the height of the decision tree is at least $\log\_2(n+1)$. This is a lower bound for deciding whether one element is in the array or not. If we want to decide if the 3 elements $x, y, z$ are in the array or not and we know that $x\< y\< z$ we can use this information to speed up the search by searching for $y$ first.

For example if the outcome of the first comparison is \< then since we know that $x \< y$ we can skip that comparison when searching for $x$ and save at least a step. Similarly, if the outcome of the first comparison is \> then since we know $y \< z$ we don’t have to redo that comparison when searching for $z$ and save at least one step.

So if the search for $y$ starts with some constant $c$ left-branches we save that many steps when searching for $x$ and if the search for $y$ starts with $c$ right-branches we save that many steps when searching for $z$.

Thus, if it takes $k$ steps in the worst case to search for the 3 elements a lower bound is: $$ k \ge 3\log\_2(n+1)-c \ge 3\log\_2 n-c, $$ where $c$ is some positive constant.

Is this a correct proof? What I am unsure about is if the last statement is ok, where I just discard the "+1". And whether this holds true for "any comparison based algorithm". Any critique or suggestions are greatly appreciated.

# Answer
The following answer works for a previous variant of the question, in which the goal is to determine which of $x,y,z$ are in $A$. It might be possible to adapt it to the current version, in which the goal is to determine whether or not *all* of $x,y,z$ are in $A$. One difficulty is that the number of trees of depth $h$ is now $\Theta(2^hh^3)$, so following the same steps would only give a lower bound of $3\log\_2 n - \Theta(\log \log n)$.

Suppose that the array $A$ is $1,\ldots,n$. Let $x = i + 1/2$, $y = j + 1/2$, $z = k + 1/2$, where $1 \leq i \< j \< k \< n$ are integers. Let us denote the resulting leaf of the algorithm by $\ell(i,j,k)$.

I claim that if $(i,j,k) \neq (i',j',k')$ then $\ell(i,j,k) \neq \ell(i',j',k')$. Indeed, suppose that $\ell(i,j,k) = \ell(i',j',k')$ although $(i,j,k) \neq (i',j',k')$. Suppose that $i \< i'$ (the other cases are similar). Since $i + 1/2 \< A\_{i+1} \< i' + 1/2$, we conclude that in this computation path, the algorithm never compares $x$ to $A\_{i+1}$. Suppose that we change $A\_{i+1}$ to $A'\_{i+1} = i + 1/2$. The new array $A'$ is still sorted, and when running the algorithm on $A',i+1/2,j+1/2,k+1/2$, it still reaches the leaf $\ell(i,j,k)$ (since the only comparison whose answer is different is $A'\_{i+1}$ and $x$). We have reached a contradiction, since $x \in A'$, and so we should have reached a different leaf.

Concluding, we have shown that the algorithm tree must have at least $\binom{n-1}{3}$ different leaves (this is the number of possible triples $(i,j,k)$). Since we are only considering runs of the algorithm in which the answers to all comparison queries are either $\<$ or $\>$, we can ignore all edges labeled $=$, and so we are left with a binary tree, whose depth must therefore be at least $\log\_2 \binom{n-1}{3}$. This is a lower bound on the number of comparisons in the worst case.

When $n \geq 4$, we have $$ \binom{n-1}{3} = \frac{(n-1)(n-2)(n-3)}{6} \geq \frac{(n-3)^6}{6} \geq \frac{(n/4)^3}{6} = \frac{n^3}{384}, $$ since $n-3 \geq n/4$. Therefore for $n \geq 4$ the number of comparisons must be at least $$ \log\_2 \frac{n^3}{384} = 3\log\_2 n - \log\_2 384. $$ When $1 \leq n \leq 3$, we must still make (say) at least one comparison, and this allows us to obtain a lower bound of $3\log\_2 n - c$ valid for all $n \geq 1$ (details left to the reader).
> 1 votes

---
Tags: algorithms, proof-techniques, correctness-proof, lower-bounds
---


# Question
Title: Are there any techniques for checking whether a clause is subsumed by another clause when adding it to a cnf formula?
When doing variable elimination on a formula in cnf form, there is created a lot of new clauses. Is there any efficient way to check if these are subsumed by other, already existing clauses?

# Answer
> 5 votes
There is a preprocessing method called *vivification*$^1$ that can be used to detect subsumed clauses. It relies on unit propagation to work.

To vivify a clause, make a partial variable assignment such that all the proposed clause's literals are false. E.g. if your proposed clause is $x\_1 \lor \lnot{x\_2} \lor x\_3 \lor \lnot{x\_4}$, assign $x\_1$ = FALSE, $x\_2$ = TRUE, $x\_3$ = FALSE, and $x\_4$ = TRUE. If while you're doing these assignments unit propagation produces a conflict, or if one of the variables is set by unit propagation and vivification later wants to set it to a different value, then the new clause is implied by the existing formula and can be discarded as redundant.

---

$^1$"Vivifying Propositional Clausal Formulae" by Cédric PIETTE, Youssef HAMADI and Lakhdar SAÏS

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


# Question
Title: does order matter when two different derivations are to be made for ambiguous grammar
E -\> E + E | E * E | (E) | a

Derivation for ( (a+a) * a)

Question : Show that the grammar is ambiguous by sparse tree method

Now, I have derived two derivation using left most derivation

but it results in like this 1st : **((a+a) * a)** 2nd : **(a * (a+a))**

is this correct or the order should also be same?

# Answer
> 0 votes
You are deriving *different* strings. The definition of ambiguity asks for the *very same string*.

In this case, that they "mean the same thing" in algebra, due to the commutative law for multiplication, is completely off topic.

---
Tags: automata
---


# Question
Title: How to remove cycles from a directed graph
I saw this from SO which led to Feedback Arc Set, which describes the problem nicely:

> In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG).

I am wondering how this is done. Given a graph such as this:

```
a -> b
b -> c
c -> d
d -> a

```

Or a for loop flattened out such as:

```
somemethod -> forloop start
forloop start -> forloop next
forloop next -> forloop result
forloop next -> forloop next // i+1
forloop next -> forloop end
forloop end -> forloop result
forloop result -> next method

```

Wondering how you can possibly remove the cycles from a graph like that.

# Answer
There is a paper "breaking cycles in noisy hierarchies" which talks about leveraging graph hierarchy to delete cycle edges to reduce a directed graph to a DAG.

The reduced DAG will maintain the graph hierarchy of the original graph as much as possible.

The corresponding code is available on Github: https://github.com/zhenv5/breaking\_cycles\_in\_noisy\_hierarchies
> 10 votes

# Answer
You can always make a digraph acyclic by removing all edges. The goal in feedback arc set is to remove the minimum number of edges, or in the weighted case, to minimize the total weight of edges removed. In your case, you can make the graph acyclic by removing any of the edges.
> 2 votes

---
Tags: graphs
---


# Question
Title: Are there any problems in $P$ which we do not know any $P$ algorithms?
A problem in $P$ is one that can be solved in polynomial time (or faster) on a deterministic Turing machine. Now if I am correct, there is nothing here referring to the algorithms - which can themselves can be given a complexity class (necessarily greater or equal to that or the problem).

My question is: Are there any problems in $P$ for which we do not know the existence of any algorithm in $P$.

I am physicist by training so please let me know if anything doesn't make sense.

# Answer
Nice question! I think the answer is "yes", but I can't prove it.

The answer is not obvious. You might imagine that if we had a problem with a non-constructive proof that it is in $P$, we might know it is in $P$ without knowing of an algorithm for it. For instance, here is a reasonable candidate for such a problem:

$$f(n) = \begin{cases} 1 & \text{if $0^n$ occurs in the decimal representation of } \pi \\ 0 & \text{otherwise.}\end{cases}$$

The problem is to compute $f$.

We can prove that $f$ is in $P$, but as far as I know, we don't know of any *specific* polynomial-time algorithm that we can prove correctly computes $f$. In other words, we're certain that such an algorithm exists, but we can't write one down that we're sure works. In particular, we know of an infinite family of algorithms, such that all of them run in polynomial time and one of them is correct; but as far as I know, we don't know which one is correct. See How can it be decidable whether $\pi$ has some sequence of digits? for details.

So, I suspect that the answer to your question is "yes" and that $f$ is such an example.

You can find more examples at https://en.wikipedia.org/wiki/Non-constructive\_algorithm\_existence\_proofs. That page shows examples of problems where we can prove that a polynomial-time algorithm exists, but that proof is non-constructive, in the sense that it does not tell us what the algorithm is. Now that said, it's possible that this just reflects our lack of current knowledge. Maybe tomorrow someone will come up with a constructive proof that those problems are in P, i.e., maybe they will come up with a specific algorithm that they can prove is correct and runs in polynomial-time. But as it stands today, we don't know of any such algorithm.

See also https://cstheory.stackexchange.com/q/4777/5038, https://cstheory.stackexchange.com/q/12162/5038, and Is there an algorithm that provably exists although we don't know what it is?.

---

At the same time, there is a limited more limited version of the question for which the answer is "no".

If you limit yourself to problems in NP that have a known nondeterministic polynomial-time algorithm, then we can say that the answer is "no" for those problems: for every problem that is known to be in P and is known to have a nondeterministic polynomial time algorithm, we know of a polytime (deterministic) algorithm for it.

It might sound crazy, but it's true. In particular, one can use Levin universal search to write down an algorithm for such a problem. The resulting algorithm will have constant factors that make it totally impractical, but we can prove it runs in polynomial time and that it is correct. See What is a lay explanation for universal search?, Polytime algorithm for SUBSET-SUM assuming P=NP, and Is there a concept for an algorithm computing a function by first finding another algorithm?.
> 14 votes

# Answer
The classic example is the family of problems related to the Robertson-Seymour Theorem in graph theory.

This result says that any minor-closed class of graphs can be described as the graphs excluding a finite set of minors. However, the proof is non-constructive: the theorem doesn't say what those minors actually are. If we did have the finite set of minors, then the algorithm to decide whether an input graph is in a minor-closed class $C$ would be quite easy, and it is even known that it can be implemented to run in quadratic time.

So we have infinitely many classes of graphs, many quite interesting, for which we know that recognition is in $\textsf{P}$, but we currently have no idea how to construct the recognition algorithm guaranteed by the theorem.
> 12 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: Why does space(n) <= time(n) imply that TIME(f(n)) is a subset of SPACE(f(n))?
The title might be hard to understand, here's a picture of what I don't understand:

And further, why can we conclude this?

I thought about posting to theoretical CS stackexchange but it asks for research level and I don't think this will be accepted

# Answer
A machine which runs in time $f(n)$ also runs in space $f(n)$, that is, the space used by a machine is always at most the time it uses. In symbols, $\mathrm{space}\_M(n) \leq \mathrm{time}\_M(n)$.

A machine is in $\mathsf{TIME}(f(n))$ if it runs in time $O(f(n))$. Any such machine also uses space $O(f(n))$ (since the space used by a machine is at most the time it uses), and so it is in $\mathsf{SPACE}(f(n))$. In other words, $\mathsf{TIME}(f(n)) \subseteq \mathsf{SPACE}(f(n))$. This implies that $$ \mathsf{P} = \bigcup\_{k=0}^\infty \mathsf{TIME}(n^k) \subseteq \bigcup\_{k=0}^\infty \mathsf{SPACE}(n^k) = \mathsf{PSPACE}. $$ A similar calculation shows that $\mathsf{EXPTIME} \subseteq \mathsf{EXPSPACE}$.

For the remaining relation, we have to use a different fact about time and space: a machine which uses space $O(f(n))$ runs in time $O(2^{O(f(n))})$. This is because the number of configurations in a (one-tape) machine which uses space $O(f(n))$ is $|Q| f(n) |\Sigma|^{f(n)}$, where $|Q|$ is the number of states and $|\Sigma|$ is the size of the tape alphabet. You can check that this implies the remaining containment $\mathsf{PSPACE} \subseteq \mathsf{EXPTIME}$.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: A physical algorithm that finds all integer partitions of a number
If this is not the right forum for this question let me know.

I am looking for a `physical algorithm` that can be easily followed by anyone not knowing much mathematics to get integer partitions of a number.

I have come up with the following way - but there is an issue (described later).

Suppose I want to divide number 11 into all its integer partitions (order is not important).

For finding `partitions of size 2` we do following.

Take 11 coins of identical widths. Take a paper. Write `1` and `2` on it

```
1    2

```

Below the first number, keep all 11 coins one upon another to make a tower of height `11`. This is represented as -

```
1      2

11c   0c

```

Now, shift `1` coin from first column to second column.

```
1      2

10c   1c

```

Here, height of tower 1 = 10, height of tower2 = 1

Keep on doing this, only if `Height of tower 1 >= Height of tower2`

On each step of the algorithm, we get new integer partition.

* This "physical algorithm" is easy to understand by anyone knowing basic mathematics.
* Preferrably, each step in the physical algorithm must show a new partitioning way.
* There should be an end condition to the algorithm.
* When the algorithm reaches end condition, all possible partitioning ways must have been shown.

If we now want to find all partitions of size 3, the problem gets a bit tricky.

We have 3 towers, with following restrictions `Height of tower 1 >= Height of tower2 >= Height of tower3`

But thing is, there are certain positions, from which we cannot go to next stage without destroying earlier stage - what do I mean by this? See below

`Step1`

```
1      2     3

9c    1c     1c

```

`Step2`

```
1      2     3

8c    2c     1c

```

`Step3`

```
1      2     3

7c    3c     1c

```

`Alternative Step3`

```
1      2     3

7c    2c     2c

```

At `step 3` the algorithm creates two branches - people could either put new coin in tower2 or tower1. **How should the algorithm statements be written so that by the time the algorithm is finished, all partitions of size 3 are known?**

**If you could come up with a new algorithm, that's welcome too!**

# Answer
Let us aim at generating the partitions in the following order (below, for $n=6$):

$$ \begin{align\*} & 6 \\ & 5 \\, 1 \\ & 4 \\, 2 \\ & 4 \\, 1 \\, 1 \\ & 3 \\, 3 \\ & 3 \\, 2 \\, 1 \\ & 3 \\, 1 \\, 1 \\, 1 \\ & 2 \\, 2 \\, 2 \\ & 2 \\, 2 \\, 1 \\, 1 \\ & 2 \\, 1 \\, 1 \\, 1 \\, 1 \\ & 1 \\, 1 \\, 1 \\, 1 \\, 1 \\, 1 \end{align\*} $$ We start with the partition $n$.

To generate a new partition, identify the last non-1 entry in the preceding partition (if there is no such, we’re done); reduce it by 1, and delete all following entries; complete it to a partition by repeatedly adding the maximum possible number, under the constraint that the partition is non-increasing.

You can check that this indeed generates all partitions.
> 2 votes

# Answer
I have come up with following algorithm for finding partitions of size 3. It may be generalized to size `N`, but I'm not 100% sure.

**Initial Setup**

A paper with 3 numbers, 1,2 and 3 written on it.

11 coins.

1 coin in tower1, 1 coin in tower2, 9 coins in tower3.

This is represented as

```
[step1] 1 1 9

```

**Algorithm** This algorithm is a series of steps. Some of the steps are termed "starting positions". Once a starting position is reached, an operation `O1` must be performed to reach next step - while satisfying a certain condition `C0`. Then we repeat that operation multiple times. If that partular condition `C0` cannot be satisfied, we go to the next starting position via operaiton `O2`.

`Condition C0` = **Height of tower1 \<= Height of tower2 \<= Height of tower3**

`Operation O1` = **Shift one coin from last tower to second-last tower while `condition C0` is satisfied. If `C0` cannot be satisfied do operation `O2`**

`Operation O2` = **Shift one coin from last tower to first tower. Then shift coins from second-last tower to last-tower until `Height of tower1 = Height of tower2`**

`Termination condition` = **If after performing `operation O2`, `condition C0` cannot be satisfied, algorithm is terminated and that coin distribution is discarded.**

**Algorithm demonstration**

**Initial Starting position**

```
[step1] 1 1 9

```

`Condition C0` `Height of tower1 <= Height of tower2 <= Height of tower3`

`Operation O1` -\> Shift one coin from last tower to second-last tower while `condition C0` is satisfied.

```
[step2] 1 2 8
[step3] 1 3 7
[step4] 1 4 6
[step5] 1 5 5

```

Now, we can no longer perform `operation O1` without disobeying `condition C0`. So we shift to next starting position via `operation O2` which modifies coin distribution according to some conditions.

`Operation O2` \- Shift one coin from last tower to first tower Shift coins from second-last tower to last-tower until `Height of tower1 = Height of tower2`

**If `condition C0` cannot be satisfied at this stage - algorithm is terminated. Otherwise we go forward as below**

After performing `operation O2` we reach next starting position as below

```
[step6] 2 2 7

```

Now, a series of `O1` operations takes us through -

```
[step7] 2 3 6
[step8] 2 4 5

```

Now `C0` cannot be obeyed after performing `operation O1`, so we apply `operation O2`

```
[step9] 3 3 5

```

Then another `O1`

```
[step10] 3 4 4

```

Now `C0` cannot be obeyed after performing `O1`, so we apply `O2`

```
4 4 3

```

**`C0` cannot be obeyed by above distribution, so algorithm has terminated and last coin position `4 4 3` is discarded.**

Thus we get all 10 ways to partition 11 into 3 summands.
> 0 votes

---
Tags: algorithms, education, integer-partitions
---


# Question
Title: Determine if an array is divisible in pairs of equal sum
I'm currently studying the time complexity of the solution provided by my teacher to this problem, and I can't understand the logic:

> Let A be an unordered array of positive natural numbers. Write an algorithm that checks if it's possible to divide A into pairs (subsets of two elements) of equal sum.
>
> Example \[1 7 4 2 4 0 8 6\] is composed of 1+7, 4+4, 2+6 etc all of which give 8.

Now, the solution works like this: it sorts the array, and then checks if the sum of $A\[i\]$ and $A\[length-i\]$ (indexes start at 1) always give the same value.

> Example: \[0 1 2 4 4 6 7 8\] is the above array after reordering. Checks 0+8=8, then 1+7=8, then 2+6=8 etc.

So the algorithm returns `True`, since every $(n,n-i)$ pair in the array always gives the same sum.

My problem with this is that I can't understand why positioning the elements with this symmetry would give an equal sum everytime.

Why taking the $i$ and $n-i$ elements would give the same sum?

# Answer
> 1 votes
For simplicity, let's pretend there are no duplicates in your array. The answer generalizes easily to arrays containing duplicates.

If the array can be divided into pairs of equal sum, then the lowest number (on place $0$ in the sorted array) and the highest number (on place $n$ in the sorted array) has to be a pair. We can do a proof be contradiction by assuming that the lowest number ($x\_0$) and the highest number ($x\_n$) is not a pair. As all numbers in the array needs to be in a pair, this implies that $x\_0$ is in a pair with an other number $x\_j$ and likewise that $x\_n$ is in a pair with $x\_k$. As $x\_n$ is the highest number, it must be that $x\_j \lt x\_n$ and therefore, in order for $x\_o + x\_j$ to be equal to $x\_k + x\_n$ it must be that $x\_k \lt x\_0$ but this goes against our assumption that $x\_0$ is the lowest number.

Having proved that $x\_0$ and $x\_n$ is a pair, the same proof now goes for $x\_1$ and $x\_{n-1}$ and recursively for the whole array.

# Answer
> 1 votes
You sort the array in increasing order.

If you pair an element equal to the largest element with any element that is larger than the smallest element, then pairing the smallest element with any other element will give a smaller sum, and therefore a different sum.

Therefore, to find pairs that all have the same sum, you *must* pair an element equal to the largest with an element equal to the smallest, and then repeat for the remaining elements. This will give you pairs with equal sums *if it is possible*. If not possible, then of course you won't get equal sums.

---
Tags: algorithms, time-complexity, partitions, subset-sum
---


title: CFLs are inherently unambiguous?

text:
# Question
Title: CFLs are inherently unambiguous?
As reading the textbook of Introduction to the theory of computation\_third edition - Michael Sipser, which have the concept that we call a context-free language L inherently unambiguous if there does not exist an ambiguous CFG that generates L.

Do we have any CFLs are inherently unambiguous? if so, can you please give me an example?

# Answer
Every non-empty context-free language has an ambiguous grammar. Indeed, take any context-free grammar for the language, and add to it the production $S \to S$ (if it is not already there), where $S$ is the start symbol. Every word in the language has infinitely many derivations, since given a derivation, we can always come up with a longer one by adding an application of the rule $S \to S$ at the very beginning.
> 4 votes

---
Tags: context-free, ambiguity
---


# Question
Title: How to prove the existence of a number which cannot be written by any algorithm?
I have the problem:

> Show that there exists a real number for which no program exists that runs infinitely long and writes that number's decimal digits.

I suppose it can be solved by reducing it to the Halting problem, but I have no idea how to do so.

I would also appreciate links to similar problems for further practice.

# Answer
As Sebastian indicates, there are only (infintely but) countably many programs. List them to create a list of programs. The list is (infinitely but) countably long. Each program generates one number in R. From that we can create an (infinite but) countable list of numbers in R. Now we can apply Cantor's diagonal argument directly to prove that there still must be other numbers.

By the way if the algorithm has (finite) arguments, you can just rewrite that as a "longer" list of programs where each program doesn't have any arguments.

With regard to your comment "What if real numbers are allowed as argument", then the question's premise is wrong: all numbers in R can then be generated. If someone finds a number, say 皮 and claims it cannot be computed, we have the following "algorithm":

```
func(number):
    return number

```

and call func(皮)
> 18 votes

# Answer
It's actually much simpler. There's only a countable number of algorithms. Yet there are uncountably many real numbers. So if you try to pair them up, some real numbers will be left hanging.
> 17 votes

# Answer
Consider the number whose $k$th digit is $1$ if the $k$th Turing machine halts on the empty input, and $0$ if it doesn't halt. If you could generate the digits of this real number then you could solve the halting problem.
> 9 votes

# Answer
The number is an infinitelly long number which after decimal point encodes anyhow all the turing machines which don't halt. With this number, you would be able to solve halting problem.

You can "search" the TM in the number and run it in parallel. If TM halts, it halts. If not, you would "find its code in the number".

There are many modifications of the proof and you should be able to reproduce them after the very first complexity lesson :-)
> 0 votes

# Answer
A point moves in a path by the funcion y = 2x. When the abscissa is a non computable number, there is no way for the Point to compute its path, but we know it goes on. So non computable numbers can exist at all.
> -3 votes

---
Tags: algorithms, reductions, halting-problem
---


# Question
Title: Is there a more efficient stability index algorithm?
I have this assignment for a class and we're beginning to learn time complexity. I have to find create a Java program that finds the stability indices of an array. Stability index being defined as ***a\[0\] + a\[1\] + ... a\[i-1\] = a\[i+1\] + a\[i+2\]+ ... a\[n-1\]***. Essentially if you sum every element left of the index and every element right of the index(excluding the element at the index itself) and the two sums are equal, it is a stability index.

I believe its complexity is **O(n^2)** since I have nested loops both with worst case size of n. I'm having difficulty understanding how to make this more efficient. I thought perhaps there would be a way to calculate two different arrays of sequential sums. One would be increasing from index 0 and the other decreasing from the last index. Then compare the two values, but I'm not sure how to do this without nested loops.

Not looking for answers, just a push in the right direction.

**EDIT: I made an improvement to O(N)**

# Answer
> 2 votes
Assume you have the sum $a\[1\] ... a\[i - 1\]$ and $a\[i+1\] ... a\[n - 1\]$. You can directly check the "stability" for index $i$. Think of how much additional computation you need to calculate the "stability" for index i + 1. In an $O(N^2)$ solution you would need $O(N)$ additional work by just recomputing the sum again. Is there something better you can do to reduce this to $O(1)$ so that the overall runtime reduces to $O(N)$.

Basically can you reuse some information that you already calculated before?

---
Tags: algorithms, complexity-theory, data-structures, efficiency
---


# Question
Title: What will be the computational complexity of a system with two pipelined algorithms?
A system consists of two separate algorithms (operated in pipeline). `Algorithm#1` is iterated `m` times and has a time complexity of `O(m)`. `Algorithm#2` is iterated `N` times with time complexity `O(N)`. The output of `Algorithm#1` is the input of `Algorithm#2`. Hence, when `Algorithm#1` is fully run (`m` times), `Algorithm#2` is started.

```
system = Algorithm#1 + Algorithm#2

```

For example:

```
for(i=0;i<m;i++) //Algorithm#1
{y=y*i;}

x=y*x;
for (j=0;j<N;j++) //Algorithm#2
{x=x*j;}

```

Here, `*` stands for any operation.

Note that `N>>m`. What will be the final time complexity of the system in terms of Big-O notation?

Any help will be highly appreciated.

Thank you.

# Answer
I've figured out the answer to my question. The final complexity will be:

```
O(max(m,N))

```

It is because `m` and `N` are independent and the loops are not nested. In my case, since `N>>m`, the final time complexity will be `O(N)`.
> 0 votes

---
Tags: algorithms, complexity-theory, time-complexity, asymptotics
---


title: What is a space constructible function?

text:
# Question
Title: What is a space constructible function?
I've searched this and was not able to understand the answer.

What's the idea/intuition behind this? What's the purpose and why is it important?

And considering the wikipedia explaination, specifically this part:

> outputs the binary (or unary) representation of f(n), while using only O(f(n)) space

Why does it matter that the binary representation doesn't exceed O(f(n)) space?

And what does it mean to not exceed that space? Why is the function f(n) = c not space constructible?

Sorry if this has been asked before but I didn't find it.

# Answer
The *space* used by a Turing machine is the total number of cells that the head (or heads, if a multitape machine) of the Turing machine has ever visited. A function $f(n)$ is space-constructible if there is a Turing machine that on input $1^n$ outputs the binary representation of $f(n)$, and while doing so only visits $O(f(n))$ cells. Note that $O(f(n))$ is an upper bound on the visited cells, not on the length of the representation.

Whether constant functions are space-constructible or not according to this definition depends on the Turing machine model. If the input and output are on the same tape, then a Turing machine space-constructing $c$ should first erase the input $1^n$ and then write the binary representation of $c$. Unfortunately, this takes $n$ space rather than $O(c) = O(1)$ space. If, in contrast, the input is on a special read-only tape and the output is on a special write-only tape (as is the case for log-space machines), then there is absolutely no problem to (fully) space-construct $c$.
> 2 votes

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


# Question
Title: Proving time-complexity analysis for merge-sort-like algorihtm
I have this algorithm, which is exactly like merge-sort, but instead of halving the array each recursion, it actually splits it into $1/4$ and $3/4$ parts. Other then that, it does exactly the same operation as merge-sort.

The thing is, I can't understand the exact way to calculate a closed form solution to my recursive formula, which I think is: $$T(n) = T(\frac{1}{4}n) + T(\frac{3}{4}n) + O(n)$$

I've gone through the proof of the standard merge-sort implementation recursion closed-form formula (as seen in a khan academy article) and have noticed that as a way to develop intuition on how the recursive formula acts, a binary tree has been drawn. So I decided to try it for myself and the recursion formula I'm trying to prove. What I got was something like the following:

Where $(\frac{3}{4})^Hn$ is the height of the tree.

Because the tree is not complete, I'm confused on how I should calculate that $H$ value (the height of the tree), so I could use it in my worst-case merge-sort-like algorithm analysis. The confusion, in my estimation, lies in my low confidence with $log$ operations. Just can't seem to wrap my head around them. How do I start writing an induction proof for a closed form formula, and how do I even come up with one?

Help is as always, greatly appreciated. Moreover, if there is a source of further learning and something worthwhile reading that might help in this subject, please write that down for me so I could explore by myself. Thanks!

# Answer
There is no reason to calculate a closed form solution to this recurrence. Indeed, this is not even possible, due to the following reason:

* $O(n)$ is not a closed form function. It just signifies that the recurrence holds with $O(n)$ replaced by some function $f(n)$ which belongs to the class $O(n)$.
* It is not clear what happens when you plug in $n$ which is not divisible by 4.
* A related issue is that there are no initial conditions - the recurrence seemingly never bottoms out.

Any reasonable way to address the latter two concerns will lead to a recurrence which is amenable to the Akra–Bazzi method. According to this method, we first need to calculate the value of $p$ satisfying $$ (1/4)^p + (3/4)^p = 1. $$ The solution to this equation is $p = 1$. The asymptotic solution is then $$ T(n) = O\left(n\left(1 + \int\_1^n \frac{O(u)}{u^2} \\, du \right)\right) = O(n\log n). $$
> 1 votes

---
Tags: binary-trees, induction, mergesort
---


# Question
Title: Is it NP hard to partition a graph into 2 vertex sets with minimum degree of 2 and 3?
The following problem is from my algorithms class:

> Given a graph $G=(V, E)$, decide whether a partition of $V=(V\_1, V\_2)$ exists such that $\delta(G(V\_1))\ge 2 $ and $\delta(G(V\_2))\ge 3 $, where $G(V\_1)$ denotes the subgraph induced by $V\_1$ and $\delta(G(V\_1))$ denotes the minimum degree of graph $G(V\_1)$. Prove this decision problem is NP complete.

I'm trying to prove $$\text{PARTITION} \le\_p \text{This-Problem}$$ but haven't came up with a solution until now. I've never met a problem dealing with the minimum depth of a graph. Is there any theorem about it? Could anyone help me out here?

# Answer
For convenience of description, we consider the problem as a coloring problem where vertices in $V\_1$ are colored red and vertices in $V\_2$ are colored blue.

The following is a reduction from 3SAT.

For any instance of 3SAT with $n$ variables (assume $n\ge 4$ without loss of generality), construct a **complete** graph of $2n$ vertices $V=\\{v\_1^0, v\_1^1, \ldots, v\_n^0, v\_n^1\\}$ where $v\_i^0, v\_i^1$ respectively represent the positive and negative literals of the $i$th variable. We also add some additional structures. Note that only named vertices can be in more than one structure.

1. For each $i$, add the following structure (note I emit the edges among named vertices and the same below):

This structure ensures all the unnamed vertices are colored red, and at least one of $v\_i^0$ and $v\_i^1$ must be colored red.
2. For each clause $l\_1\vee l\_2\vee l\_3$, say their corresponding vertices are $u,v,w\in V$, add the following structure:

This structure ensures all the unnamed vertices are colored red, and at least one of $u,v,w$ must be colored red.
3. For each $i$, for each pair of vertices $\\{u,v\\}\subseteq V$, add the following structure:

If both $v\_i^0$ and $v\_i^1$ are colored red, then all the unnamed vertices must be colored red, and at least one of $u$ and $v$ are colored red. Note this holds for all pairs $\\{u,v\\}$, so if both $v\_i^0$ and $v\_i^1$ are colored red, there are at most one vertex colored blue, which is impossible. As a result, this structure ensures at least one of $v\_i^0$ and $v\_i^1$ is colored blue. Combined with the first type of structures, it is ensured that $v\_i^0$ and $v\_i^1$ are colored different colors.

Now if there is a proper coloring, exactly one of $v\_i^0$ and $v\_i^1$ is colored red. If it is $v\_i^0$, assign the $i$th variable 1, otherwise 0, then the assignment is a valid assignment for the 3SAT instance.

On the other hand, if there is a valid assignment for the 3SAT instance, color $v\_i^0$ red and $v\_i^1$ blue if the $i$th variable is assigned 1, otherwise color $v\_i^0$ blue and $v\_i^1$ red. Note the subgraph induced by $\\{v\_1^0, v\_1^1, \ldots, v\_n^0, v\_n^1\\}$ is a complete graph, this is a legal coloring. All unnamed vertices in the first two kinds of structures are colored red, and for a structure of the third type, if both $u$ and $v$ are colored blue, color all the three unnamed vertices blue, otherwise color them red. This is a proper coloring. Q.E.D.
> 4 votes

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