title: Big O Unsure (single problem)

text:
# Question
Title: Big O Unsure (single problem)
```
    int a = 0;
    for (int i = 0; i < n*n; ++i) {
        for (int j = 0; j <= i; ++j) {
            a += j;
        }
    }

```

Could someone help prove to me that this is function is $O(N^4)$.

I remember doing this problem a while back, but now I do not see it.

I understand that the outer loop is $O(N^2)$ but I am unsure of how this would cause the inner loop to be $O(N^2)$ as well

# Answer
Consider the range of `j` in the inner loop:

* What is its maximum?
* What is its average?
* What is its average average?
> 2 votes

# Answer
What does the big-Oh notation mean ? It always gives me an **upper bound(worst case scenario)** on the running time of an algorithm.

What is the **worst-case** running time of this algorithm ? It will happen when the outer loop (where `i` is defined) reaches its **maximum value**, and so `j` is subsequently forced to follow till `i`.

This should give you your answer.
> -1 votes

---
Tags: asymptotics
---


# Question
Title: Regular expression for the second symbols from the front and the back are equal
I am practicing for an exam. I am trying to convert a language to a regular expression. The language and my solution is as follows:

$L=\\{w∈\\{a,b\\}^+│|w|≥4\ and\ the\ second\ symbols\ from \ the \ front\ and\ the\ back\ are\ equal\\}$

Solution: $(a+b)x(a+b)^\* x(a+b) \ \ where\ x=(a+b)$

Is this correct? If not, can someone correct me. also, am I allowed to use variables in regular expressions?

Thanks in advance

# Answer
You asked two questions. The usual rule on this site is to ask one question per post.

No, you're not allowed to use variables in regular expressions. Regular expressions have a formal definition. To qualify as a regular expression, you need to meet the requirements in the definition. The definition can be found on Wikipedia or in your favorite textbook, and you'll note that it does not allow "where" or "variables".

For your first question about how to find a regular expression for a language, take a look at How to prove a language is regular?.
> 1 votes

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


# Question
Title: Confusion converting BNF to regular expression
I have a Computer Science A-Level exam tomorrow and I've been trying to get this question answered by my teacher but she's not been too helpful so asking here instead.

In an exam question, I have the following BNF grammar, where `_` denotes a space.

```
<fullname> ::= <title>_<name>_<endtitle> |
               <name> |
               <title>_<name> |
               <name>_<endtitle>

<title> ::= MRS | MS | ... | SIR

<endtitle> ::= ESQUIRE | OBE | CBE

<name> ::= <word> |
           <name>_<word>

<word> ::= <char><word>

<char> ::= A | B | ... | Z

```

The mark scheme says that the first rule, fullname, can be represented with a regular expression. But I'm not really sure how you could represent it with a regular expression when it's made up of other rules that can't be represented by regular expressions themselves e.g. name which is recursive. Also I thought regular expressions were made up of just letters and symbols e.g. a\*b? . Forgive me if I don't seem too knowledgable on this because the resources we have for the A-Level are pretty awful.

# Answer
> 2 votes
There are two ways of interpreting 'the first rule can be represented with a regular expression'; you should review this 'mark scheme' to determine which applies. One possibility is that the first rule is being treated as defining a language over its own terminals and non-terminals, without ever expanding the non-terminals. I.e, think of treating the tokens 'title', 'name', and 'endtitle' *as single characters* of the 'language' of 'fullname' (along with the space-char). Then it is easy to see that *that* is a regular language - there are only four strings in it!

The other possibility is what you assumed, i.e that non-terminals are to be expanded. In this case your observation that 'name' is recursive is misplaced. The issue is not whether *the set of productions for that non-terminal* is regular, the issue is whether *the set of strings generated from that non-terminal* is regular. For 'name' the answer is yes: The set of strings generated from 'name' is seen, with a little thought, to be simply a sequence of one or more 'word'-s separated by spaces, for which a regular expression is easy to construct \[given a regular expression for 'word', of course\]. So yes, in this case 'fullname' generates a regular language.

*\[P.S. Note: Your 'word' is missing a production for a single 'char'\]*

---
Tags: context-free, regular-languages, regular-expressions
---


# Question
Title: Reducing one variant of Hamiltonian path to another
Define

$A = \\{\<G,s,t\> :G$ is un directed graph that has a Hamilton path from $s$ to $t\\}$

$B = \\{\<G\> :G$ is un directed graph that has a Hamilton path$\\}$

I would like to show that $A \le\_p B$.

My attempt:

Given $\<G,s,t\>$ , the reduction outputs $\<G'\>$ where $G'$ defines as follows:

we take $v\_s$ and $v\_t$ s.t there is an edge $e\_s$ between $s$ and$v\_s$ and an edge $e\_t$ between $v\_t$ and $t$.

Now we define $G' = (V',E')$ where $V' = V \cup \\{v\_0 , v\_1\\}$ and $E' = (E-\\{e' :e' \ne e\_s , s\in e'\\} -\\{e' :e' \ne e\_t , t\in e'\\}) \cup \\{ \\{v\_0,v \\} :\\{v,s\\} \in E \\} \cup \\{ \\{v\_1,v \\} :\\{v,t\\} \in E \\} \cup \\{ \\{v\_0,s \\}\ , \\{v\_1,t\\} \\}$.

Now, if $\<G,s,t\> \in A$ , let $s , u\_1,\dots ,u\_n ,t$ be the Hamilton path , then $s , v\_0 , u\_1 , \dots , u\_n, v\_1 ,t$ is a Hamilton path in $G'$.

The other direction does not work for me , if $G'$ has a Hamilton path then I want to say that the "end points" must be around $s,t$ but i'm not sure how to do that.

# Answer
The simplest reduction, which is similar to what you were trying but simpler, is to add two new vertices to the graph in the instance of A: a vertex $v\_s$ connected to $s$, and a vertex $v\_t$ connected to $t$. Any Hamiltonian path in the new graph will connect $v\_s$ to $v\_t$, and so will restrict to a Hamiltonian path connecting $s$ to $t$. Vice versa, any Hamiltonian path in the original graph connecting $s$ to $t$ extends to a Hamiltonian path in the new graph connecting $v\_s$ to $v\_t$.
> 1 votes

---
Tags: computability, reductions, hamiltonian-path
---


# Question
Title: What is the basic idea behind the usage of TLBs?
I know how **Translation Lookaside Buffers** work, and i also know we use them to improve the **performance of data/program access** by storing the **recent** page numbers - frame numbers in a memory cache. The problem is that i can't understand why **frequent** memory locations are acccessed in a period of time? And what was the starting point of this idea:

> "Since the same memory locations are accessed frequently, We can create a place to hold the frequent translations so that make everything happen faster."

Can someone please share the knowledge behind this concept? Thanks.

# Answer
> 1 votes
A TLB is useful for the same reason any other cache is useful: because it's very common to access the same data multiple times in quick succession. Many algorithms use the same value more than once. For example, searching requires accessing the search pattern a lot of times. Sorting a list requires comparing the same element multiple times for any (comparison-based) algorithm.

The nature of the TLB amplifies this effect because it doesn't only kick in when accessing the same data, but more generally when accessing data in the same page. This happens even when each individual bit is only accessed once. For example, consider a simple array traversal, that accesses the array elements in order. Assume that elements are smaller than one page, say $k$ elements fit in a page. Then a single MMU lookup is needed for the first element in a page, and the next $k-1$ only require a TLB lookup.

---
Tags: operating-systems, memory-hardware, performance, caching
---


# Question
Title: Updating the distances matrix after single edge was decreased
I was reading this question on how to update the distances matrix D of a graph after one edge was decreased, and I don't understand why it works:

The answer suggests that if the an edge `(a,b)` was modified - then all you have to do is iterate through every edge of the graph, and calculate: `D[u][a] + w(a,b) + D[b][v]`.

My problem is: how do you know that `D[u][a]` is correct ?

I've drawn this example:

Now `D[u][a] = 100` but, when the edge from a to b decreases:

Now `D[u][a]` should to be changed to 71 but it's not. and when I will calculate `D[u][v]` I would use a false `D[u][a]`.

What am I missing here ? is the algorithm presented in the answer linked not correct ? or am I ?

# Answer
Let me start with the setup, for the simpler case of a directed graph. We are given a weighted directed graph $G$ (with non-negative weights), and for every two vertices $s,t$, the distance $\delta(s,t)$ of a shortest directed path from $s$ to $t$. We modify $G$ to a new graph $G'$ by reducing the weight of an edge $(a,b)$, from $w(a,b)$ to $w'(a,b)$. The claim is that $$ \delta'(s,t) = \min(\delta(s,t), \delta(s,a) + w'(a,b) + \delta(b,t)). $$ (In fact, the claim we want to prove is a bit stronger, since presumably we will be updating the metric sequentially rather than in parallel, but let's leave that for the future.)

In order to prove this formula, we consider two cases.

**Case 1.** Suppose first that there exists a shortest path $p'$ from $s$ to $t$ in $G'$ which doesn't go through the edge $(a,b)$. I claim that $p'$ is also a shortest path from $s$ to $t$ in $G$, and so $\delta'(s,t) = \delta(s,t)$. If not, let $p$ be a shorter path from $s$ to $t$ in $G$. Then $w\_{G'}(p) \leq w\_G(p) \< w\_G(p') = w\_{G'}(p')$, contradicting the definition of $p'$.

It remains to show that $\delta(s,t) \leq \delta(s,a) + w'(a,b) + \delta(b,t)$. Suppose not, and take shortest paths $p\_{sa}$ from $s$ to $a$ and $p\_{bt}$ from $b$ to $t$, both in $G$. Let $p$ be the (not necessarily simple) path $p\_{sa};(a,b);p\_{bt}$, so that $w\_{G'}(p) = \delta(s,a) + w'(a,b) + \delta(b,t)$. Since $w\_{G'}(p) \< \delta(s,t) = w\_{G'}(p')$, this implies that $p'$ is not a shortest path in $G'$, contradicting its definition.

**Case 2.** Suppose next that there exists a shortest path $p'$ from $s$ to $t$ in $G'$ which goes through the edge $(a,b)$, say $p' = p'\_{sa};(a,b);p'\_{bt}$. Since $p'$ is a shortest path and all weights are non-negative, we can assume without loss of generality that $p'$ is simple, and so $p'\_{sa},p'\_{bt}$ don't go through $(a,b)$.

We claim that $p'\_{sa}$ is a shortest path from $s$ to $a$ in $G$, and so has length $\delta(s,a)$. If not, let $p\_{sa}$ be a shorter path from $s$ to $a$ in $G$. Without loss of generality, $p\_{sa}$ doesn't go through $(a,b)$, since if it did, we would have $p\_{sa} = q;(a,b);r$, and could replace $p\_{sa}$ with $q$. Since $p\_{sa}$ doesn't go through $(a,b)$, it has the same weight in $G$ and in $G'$, and so if we replace $p'\_{sa}$ with $p\_{sa}$, we would shorten $p'$ in $G'$, contradicting its definition. Similarly, $p'\_{bt}$ is a shortest path from $b$ to $t$ in $G$, and so has length $\delta(b,t)$. We conclude that $\delta'(s,t) = \delta(s,a) + w'(a,b) + \delta(b,t)$.

It remains to show that $\delta(s,a) + w'(a,b) + \delta(b,t) \leq \delta(s,t)$. If not, let $p$ be a shortest path from $s$ to $t$ in $G$. Then $w\_{G'}(p) \leq w\_G(p) = \delta(s,t) \< w\_{G'}(p')$, contradicting the fact that $p'$ is a shortest path in $G'$.

---

In the undirected case, we are lowering the weights of two edges, and so the correct formula is $$ \delta'(s,t) = \min(\delta(s,t), \delta(s,a) + w'(a,b) + \delta(b,t), \delta(s,b) + w'(b,a) + \delta(a,t). $$ (Note $w'(b,a) = w'(a,b)$.)
> 5 votes

---
Tags: graphs
---


# Question
Title: Conditions for Linear Diophantine Equations to always have a solution
Given a set of $n$ linear equations in $v$ integer variables, where $v \> n$, we can say that this system of equations will always have an integer solution.

Over $\mathbb N$, is there any such constraint that guarantees that a solution always exists? Or, if not, can it be tested in polynomial time?

# Answer
Short answer: No. Most likely, no useful constraint exists; and it can't be tested in polynomial time.

---

Detailed answer, with justification: It cannot be tested in polynomial time, unless P = NP. In particular, if you could test for existence of a non-negative integer solution to such a system, you could solve integer linear programming (ILP). Here's how the reduction works:

Suppose we have an ILP instance with variables $x\_1,\dots,x\_k$. We'll modify it by introducing variables $x\_1^+,\dots,x\_k^+$ and $x\_1^-,\dots,x\_k^-$. Then we'll replace each inequality

$$c\_0 + c\_1 x\_1 + \dots + c\_k x\_k \ge 0$$

with the equality

$$c\_0 + c\_1 x\_1^+ - c\_1 x\_1^- + \dots + c\_k x\_k^+ - c\_k x\_k^- = y\_j$$

and the inequality $y\_j \ge 0$, where $y\_j$ is a fresh new variable. Thus if the original ILP instance has $k$ variables and $m$ inequalities, the new instance will have $2k+m$ variables, $m$ equalities, and $2k+m$ inequalities $x\_i^+ \ge 0$, $x\_i^- \ge 0$, $y\_j \ge 0$.

This now has the form of your problem, i.e., integer linear diophantine equations where we are looking for non-negative solutions, with $n=m$ linear equations and $v=2k+m$ variables. Note in particular that we are guaranteed to have $v\>n$, since we must have $k\>0$. Moreover, any solution to the original integer linear programming instance leads to a solution to this diophantine problem (take $x\_i^+ = \max(0,x\_i)$ and $x\_i^- = \max(0,-x\_i)$), and conversely, any solution to this diophantine problem leads to a solution to the original ILP instance (take $x\_i = x\_i^+-x\_i^-$). Therefore the derived diophantine problem is equivalent to the original ILP instance.

This reduces ILP to testing existence of a solution to a diophantine problem. Since ILP is NP-hard, it follows that testing existence of solutions to this kind of diophantine problem is NP-hard, too. That means there is not likely to be any polynomial-time algorithm to it (assuming you believe it is unlikely that P = NP).

For similar reasons, you should not expect a useful condition that is necessary and sufficient to ensure that a solution always exists: any such condition must be infeasible to check in the worst case, unless P = NP. You can pick two out of any three: necessary; sufficient; efficiently checkable -- but you can't have all three, assuming P != NP (as many expect).
> 3 votes

---
Tags: algorithm-analysis, linear-algebra, integer-programming
---


title: Two definitions of the Reed-Muller code

text:
# Question
Title: Two definitions of the Reed-Muller code
I found two definitions Reed-Muller codes being used in literature. More specifically for any $n \in \mathbb{Z}^+$ and $1 \leq d \leq n$ we define the set $RM(d,n)$ in two possible ways,

1. $RM(d,n) = \\{ f : \mathbb{F}\_2^n \rightarrow \mathbb{F}\_2 \vert $f$ \text{ is a polynomial of degree at most } $d$\\} $

2. $RM(d,n) = \\{ f: \mathbb{F}\_2^n \rightarrow \mathbb{F}\_2 \text{ s.t} f(x) = (-1)^{P(x)} \vert $P$ \text{ is a polynomial of degree at most } $d$ \text{and with integer coefficients of magnitude at most }d \\}$

* Are these the same?
* In the first definition how is "degree" defined? Is $f$ assumed to be a sum over monomials where each literal occurs with power $1$ and then the final answer of the polynomial is evaluated $mod$ $2$ or is $f$ to be thought of as a generic degree $d$ polynomial such that when its input is restricted to $\mathbb{F}\_2^n$ its output gets restricted to $\mathbb{F}\_2$?

# Answer
They are the same.

1. In the first definition, we identify $\mathbb{F}\_2$ with elements $\\{0,1\\}$, with $+$ defined to be addition modulo 2 and $\times$ defined to be multiplication modulo 2.
2. In the second definition, we identify $\mathbb{F}\_2$ with elements $\\{1,-1\\}$ and $+$ defined to be multiplication modulo 2 and $\times$ defined as $x \times y = \max(x,y)$.

Both representations of $\mathbb{F}\_2$ are isomorphic.

Degree is defined as usual for the polynomial ring $\mathbb{F}\_2\[x\_1,\dots,x\_n\]$; see your favorite math textbook for the formal definition. Do note that $f$ is a *multivariate* polynomials, not a univariate polynomial.

---

The "integer coefficients of magnitude at most $d$" is weird and doesn't belong. The definition would make more sense with that phrase omitted. Pedantically speaking, that phrase makes no sense, as a polynomial over $\mathbb{F}\_2$ by definition has coefficients in $\mathbb{F}\_2$, so it makes no sense to speak of them as "integers", and they don't have a magnitude. (Alternatively, if we interpret it loosely/informally, that phrase becomes redundant and dead and ultimately has no effect.)
> 1 votes

---
Tags: complexity-theory, combinatorics, coding-theory
---


title: How are interrupts discovered?

text:
# Question
Title: How are interrupts discovered?
In the textbook I'm reading, it states that

> If the interrupt is of a lower/equal priority to the current process then the current process continues If it is of a higher priority the CPU finishes its current Fetch-Decode-Execute cycle. The contents of the CPU’s registers are copied to a st...

In short, the CPU reacts instantly to the interrupt and either ignores/defers it or waits until the current cycle is completed before processing it.

I don't know if this is just a simplification, but this doesn't seem right...

I thought interrupts were pushed into a buffer, while the CPU is running, and after every cycle, the buffer was checked by the CPU. This makes more sense, and seems more plausible, but also contradicts the previous explanation.

Does the CPU physically get interrupted by the interrupt, or does it briefly check the buffer after every cycle?

I don't know much of the terminology, besides "an interrupt service routine."

---

Edit: Is it a mixture of both? The highlighted explanation references a process, which I realise could encompass many CPU cycles, which are ended in the check of the buffer. If the precedence is higher, the *process* is popped out, for the ISR.

# Answer
1. It would only make sense to service interrupts after a full cycle completes, not immediately, because intermediate values are only saved to the register file at the end of each cycle. Being able to service an interrupt at any point in the cycle would add a lot of complexity to a processor for very little benefit. Interrupts are time-critical, but they're typically not microseconds and nanoseconds critical.

How this happens specifically is a matter of micro-architecture, so it can vary from processor to processor, and the processor manufacturers do not share that level of implementation detail.
2. The interrupt hardware does not queue interrupts. Different hardware interrupts are asserted by electrifying pins on the processor. When an interrupt pin is sensed, the processor transfers control to a special piece of software called the *interrupt service routine* in the operating system. Thus, handling an interrupt requires many cycles at a minimum. It is possible that an interrupt could be dropped if two interrupts were to occur near-simultaneously.
3. However, modern OSes use a variety of techniques to handle interrupts efficiently, some of which might involve queuing. These techniques improve the behavior of the computer as well as essentially eliminating the possibility of dropping interrupts under normal conditions.

A classic approach used in Linux is the *top-half/bottom-half* approach. When an interrupt occurs, the physical hardware is handled by the top half, but any significant processing is deferred to the bottom half that can run at a later time. For example, suppose we're writing a driver for a network card. The top-half of the network card driver might be responsible for copying an incoming packet from the network card into the computer's memory and clearing the interrupt, while the bottom half (also called a tasklet in Linux) is responsible for processing the packet and routing it. This allows the physical interrupt to be cleared as quickly as possible by retrieving and queuing multiple packets in software, even though the processor interrupt hardware does not have any notion of queuing.

However, modern Linux has superseded all of these concepts, and now it is common to use threaded interrupt handlers, which uses a similar *deferred processing* approach as the top-half/bottom-half mechanism, but simplifies the instantiation of the bottom half in the kernel. Here, there might not be an actual queue of interrupts, but each interrupt can be handled concurrently by a different thread in the kernel.
> 4 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: Why is the undecidability of the Halting Problem useful?
**My understanding:**

The Halting Problem is undecidable for a Turing Machine, and yet it is decidable for a linear bounded automaton (a Turing Machine with finite tape). The reason is that the only way an LBA can loop is by entering a configuration it's already been in, which is easy to check. However, unlike an LBA, a Turing Machine can also loop by entering infinitely many new configurations, none of which accept. So it seems that what the Halting Problem's undecidability really means is that the problem of checking whether a Turing Machine will enter infinitely many new configurations without accepting is undecidable.

**My question:**

But real computers are LBAs, not TMs. They can't enter infinitely many new configurations. So why is the undecidability of the Halting Problem a useful result?

I've looked at the answers to this and similar questions, and invariably they go something like, "a real computer has a bazillion configurations, and so waiting until you hit a repeat one would take a bazillion years." But as I detailed above, Halting undecidability doesn't seem to tell us anything about that kind of looping; it only tells us about the infinitely-many-new-configurations kind that real computers can never engage in.

# Answer
> 3 votes
Detecting whether a Turing machine loops can be arbitrarily difficult. For example, pick any problem `P` and consider the program:

```
k = 0
done = False
while not done:
  if <k encodes a solution to P>:
    k = 0
  elif <k encodes a solution to ¬P>:
    break
  else:
    k += 1

```

This program either terminates or runs forever with repeating configurations, but in order to tell whether configurations repeat, we need to know whether `P` has a solution. Now just insert a very difficult (undecidable) `P`.

A real computer has a bazillion configurations. That number is closer to infinity than to any number we can actually comprehend. **Turing machines are a better mathematical model of real computers than finite state automata.** Something similar happens in physics: the Earth is made from finitely many molecules, but physicists use differential equations that assume matter to be continuous and smooth. That is because the extremely large finite number of molecules is better approximated with the continuum than a discrete system with bazillion states.

---
Tags: computability, undecidability, halting-problem
---


# Question
Title: Are all proof techniques which only look at black box behaviour of a TM relativizing?
I am currently working on a seminar on $\mathbf{P \stackrel{?}{=} NP}$ and one of the points I want to adress is the Relativization barrier.

However, it is hard to find a concrete definition of a "relativizing" proof. The best defintion I have found is as follows: "A relativizing proof is any proof that is insensitive to the presence of oracles". So any proof technique that cannot tell if a TM used an oracle is relativizing.

Now my question is: Does this imply that *all* relativizing proofs only look at the black box behaviour of TMs? Moreover, are all proofs which only look at the black box behaviour of TMs also relativizing? Or are there cases where a proof is relativizing but is not looking at the black box behaviour of a TM, or vice-versa?

# Answer
> 3 votes
A theorem about an oracle Turing machine $T^A$ (where $A$ is the oracle) is *relativizing* if it is of the form $$\forall A \\,.\\, \phi(T^A)$$ We say that the statement $\phi$ *relativizes*. There is no requirement on how such a statement is proved, i.e., we do not assume that we only observe the "black box" behavior of $T$ or anything like that. In fact, it is clear that this cannot be the case, as one can easily prove a relativizing theorem about Turing machines which speaks about *how* the machine works.

Often we start with a theorem about an ordinary Turing machine, and later we ask whether the theorem relativizes. This just means that we first proved $\phi(T^\emptyset)$, and now we wonder whether the trivial oracle $\emptyset$ could be replaced with an arbitrary one $A$ so that we get $\forall A \\,.\\, \phi(T^A)$.

---
Tags: complexity-theory, turing-machines, proof-techniques, oracle-machines, relativization
---


# Question
Title: Do there exist "O(1)-complete" problems?
Many complexity classes have "complete" problems. Do complete problems exist for the complexity class of problems that can be solved in $O(1)$ time?

A complication is that this class depends on the model of computation; a problem can be solvable in $O(1)$ time in one reasonable model of computation but not another, given that "reasonable" typically means polynomial-time equivalence with a Turing machine. However, it could still be worked out for specific reasonable models.

I think it makes the most sense to look at constant-time many-one reductions. However, I'm also open to looking at other sensible reductions if there is literature on them.

Does anything like this exist, or has it been studied, for any model of computation?

# Answer
> 3 votes
Since reading the input is necessary for almost all problems, we need at least $\Omega(n)$ time for nearly all problems, where $n$ is the size of the input. Therefore, you may think of the class of linear time problems, which is already defined.

However, we still do not know any $O(n)$-complete or $O(n^2)$-complete problem. The field of fine-grained complexity has some new results in this area, but the classes are problem-based (for example, APSP is equivalent to Radius, Negative Triangle, ...).

# Answer
> 3 votes
I think that for $O(1)$ problems, all languages are complete under "constant-time reductions" except $L = \Sigma^\*$ and $L = \emptyset$

Suppose that $L, L' \in O(1)$ and $L \neq 0, L \neq \Sigma^\*$

Let $x\_Y \in L, x\_N \notin L$

This is a constant-time reduction from $L'$ to $L$:

* given $x$ solve $L'$ in $O(1)$ time
* if $x \in L'$ then output $x\_Y$, otherwise output $x\_N$

So $L$ is complete for $O(1)$ (... lazy reduction, lazy result :-)).

---
Tags: complexity-theory, time-complexity, constant-time
---


# Question
Title: Prove $T$ is a BST iff for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$
> Let $T$ be a complete binary tree. Prove that $T$ is a binary search tree if and only if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$ or it is less than or equal than the key of the right child.

To prove that if $T$ is BST then for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child I could say that from the definition of BST it follows that given a node $x$ and a node $y$ which belongs to the left sub-tree of $x$ then $key(y) \le key(x)$.

By the hypothesis if we choose any node $z$ of in the left sub-tree of $y$ then $key(z) \le key(y)$ so the relation holds true for all of the nodes of the tree.

I'm not sure how to approach the proof of the second direction: if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child then $T$ is a BST.

# Answer
> 3 votes
The second direction is not always true, in a BST **all** elements in the right subtree of a node should have a key bigger than its key and **all** elements in the left subtree of a node should have a key less than its key. for example, consider this binary tree:

`4
 / \
 2 6
 / \ / \
1 9 3 7`

it has the property that for every node x of $T$ that is not a leaf, the key of x is larger or equal than the key of the left child and less or equal than the key of the right child, but it's not a BST since 3 is in the right subtree of root but its key is less than the key of root.

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


# Question
Title: Find All permutation of String using Iteration
How to find all permutation of a String in Iterative way ?

## Code (Recursion) :

```
private void permute(String str, int l, int r)
{
    if (l == r)
        System.out.println(str);
    else
    {
        for (int i = l; i <= r; i++)
        {
            str = swap(str,l,i);
            permute(str, l+1, r);
            str = swap(str,l,i);
        }
    }
}

public String swap(String a, int i, int j)
{
    char temp;
    char[] charArray = a.toCharArray();
    temp = charArray[i] ;
    charArray[i] = charArray[j];
    charArray[j] = temp;
    return String.valueOf(charArray);
}

```

# Answer
> 1 votes
Wikipedia describes several algorithms, including:

# Answer
> 0 votes
You can use the algorithm in the link below:
http://www.geeksforgeeks.org/permutations-string-using-iteration/

---
Tags: algorithms, strings
---


# Question
Title: Finding shortest paths in undirected graphs with possibly negative edge weights
The book "Algorithms" by Robert Sedgewick and Kevin Wayne hinted that (*see the quote below*) there are efficient algorithms for finding shortest paths in undirected graphs with possibly negative edge weights (***not*** by treating an undirected edge as two directed one which means that a single negative edge implies a negative cycle). However, no references are given in the book. Are you aware of any such algorithms?

> Q. How can we find shortest paths in undirected (edge-weighted) graphs?
>
> A. For positive edge weights, Dijkstra's algorithm does the job. We just build an EdgeWeightedDigraph corresponding to the given EdgeWeightedGraph (by adding two directed edges corresponding to each undirected edge, one in each direction) and then run Dijkstra's algorithm. ***If edge weights can be negative*** (***emphasis added***), efficient algorithms are available, but they are more complicated than the Bellman-Ford algorithm.

# Answer
> 7 votes
I contacted one of the authors (Kevin Wayne; thanks) of the textbook "Algorithms, 4th Edition" and got a hint:

> Try adding "t-joins" or "perfect matching" to your web searches.

Following this, I found the following two lecture notes:

Shortest Path Algorithms Luis Goddyn, Math 408: Using Edmonds' Minimum Weight Perfect Matching Algorithm to solve shortest path problems for undirected graph with negative-weight edges, provided that $(G, d)$ is conservatively weighted, that is, if $G$ has no negative weight directed circuits (circuits $C$ whose total weight $d(C)$ is negative), then Dijkstra’s algorithm stops with a shortest path tree $T$ rooted at $s$.

$T$-joins and Applications from CS 598CSC: Combinatorial Optimization uses the $T$-join techniques.

---
Tags: algorithms, graphs, reference-request, shortest-path, weighted-graphs
---


# Question
Title: Choosing a shortest representative number from interval in arithmetic coding
In arithmetic coding a word is coded as the binary encoding of a number in a certain interval. The interval is determined from a sequence of nested intervals according to the probability distribution on the letters of the word.

This encoding and decoding process is totally clear to me, but what wonders me is how an encoder chooses the optimal number (i.e. the one with shortest length if written in binary)?

For example, in the above linked wikipedia article in the paragraph Sources of Inefficiency in the example they choose 0.538 as the message, which is not optimal as it has quite a long (way longer than 8 bits) binary expansion when written in binary, as also noted choosing 0.5390625 would be much better.

Also, if we change the probability model with a uniform distribution we get $(5/27, 6/27)$ as an interval, as shown in the paragraph the binary codings of the boundaries are quite long, much longer then the $~5$ bits, but if we choose $0.1875$ then this could be coded with $0.0011$ which requires five bits if we submit $00110$ (the final $0$ seems to be necessary for the decoder as discussed in the paragraph).

So choosing the right number in the interval is in my understand the key of the compression algorithm (also backed up with the intuitive understanding that if we have a larger interval; which is given by higher probabilites from individual tokens, then we have more possibilites to choose numbers from to find one with a short binary expansion), but every textbook or notes I find just concentrates on describing the interval nesting procedure, but not how to choose a shortest representative?

So, if my understanding is correct this seems to be an essential part? So how to achieve this?

# Answer
> 1 votes
While you are encoding symbols between the ranges, you are not choosing which to use for the specific symbol. You are narrowing down the possible chooses there are. You can arbitrarily choose them per symbol, but how would you adjust the ranges to make that the actual choice. It is true that the LAST symbol you can make a choice to make it fit within the rounding error , so long as it is within the range for that symbol.

The point of the example was that the incorrect distribution gives poor or worse compression. Choosing a better statics gives better results. Hoffman encoding is at most within 1 bit per symbol of encoding, where arithmetic coding is within a fraction of a bit per-symbol, if the correct statics are used. You can choose how accurate you do the encoding. Increasing the length of the RANGE's precision allows for more accurate representation of the given statics, thus less error. Choosing the wrong distribution for the specific message, regardless of the how accurate the encoding process is will get very poor compression or make it larger than the original message. So.. think of it is an error rate. The smaller you can make the error rate the, closer to the real limit you can achieve. choosing a "static" distribution for all text files, will never give you the smallest compressed file this specific method can give you.

JUST A NOTE: "Optimum" is misunderstood. It simple means that the best a specific method can be. Not that it is the highest compression available.

---
Tags: algorithms, information-theory, data-compression, coding-theory
---


# Question
Title: Computational Complexity of Integer Linear Program [with Fixed number of 'Pure Constants']
This is a follow up to the previous Question: Conditions for Linear Diophantine Equations to always have a solution

It was established in the above's answer that obtaining or testing for the existence of an solution of an ILP in $\mathbb N$ is an NP Hard Problem. This in turn makes obtaining solution for a (LDP) Linear Diophantine Problem (where $v$ \> $n$) in $\mathbb N$ an NP-hard Problem too.

Now given the restricted ILP Problem with an additional constraint:

The number of *unique pure constants* (i.e. ones without variables, denoted by $c\_0 below) permitted in any system has an fixed upper Bound (say 2) where equations are of the form:

$c\_0 + c\_1 x\_1 + \dots + c\_k x\_k \ge 0$

Is this restricted version of ILP still NP-hard?

# Answer
> 2 votes
Yes, it's still NP-hard. Suppose the two allowed values for $c\_0$ are 0 or 1, and that you're allowed to have equations of the form

$$c\_0 + c\_1 x\_1 + \dots + c\_k x\_k = 0$$

as well (not just inequalities). Suppose that we wish we could use the constant 17. We can introduce new variables $z\_1,\dots,z\_6$, add the equalities below, and replace all occurrences of 17 with $z\_6$.

$$\begin{align\*} 1 - z\_1 &= 0\\ 0 + 2 z\_1 - z\_2 &=0\\ 0 + 2 z\_2 - z\_3 &=0\\ 0 + 2 z\_3 - z\_4 &=0\\ 0 + 2 z\_4 - z\_5 &=0\\ 0 + z\_1 + z\_5 - z\_6 &=0 \end{align\*}$$

Notice how the above equations force $z\_1=1$, $z\_2=2$, $z\_3=4$, $z\_4=8$, $z\_5=16$, and $z\_6=17$.

Of course there's nothing special about 17; you can do this for any other number as well. In general, if you have any constant $\kappa$ you wish you could use, you can find an addition chain for $\kappa$, then use that to introduce temporary variables $z\_1,\dots,z\_t$ that force $z\_t=\kappa$, then replace all occurrences of the constant $\kappa$ with the variable $z\_t$.

In this way you can eliminate all constants other than 0 or 1 for $c\_0$. The length of the addition chain for $\kappa$ will be at most $2 \lceil \lg \kappa \rceil$, so the number of extra variables and equalities added is not too large (and in particular is polynomial in the size of the original problem), so this increases the size of the instance by at worst a polynomial factor.

---
Tags: algorithm-analysis, linear-algebra, integer-programming
---


title: Compression of Memoryless Sources

text:
# Question
Title: Compression of Memoryless Sources
Are there any compression algorithms outside of entropy encodings that yield a significant compression ratio for memoryless sources (not the Markov kind, but this kind)?

More concretely, if a million ASCII characters, each generated from the same probability distribution that is not necessarily even but where the probability of each ASCII character being chosen is non-zero, what compression algorithms outside of entropy encoders (such as arithmetic, huffman) would yield decent compression ratios?

# Answer
> 1 votes
You've eliminated entropy encoders, which is the type of data you described.

A Memory-less Markov is a contradiction of terms.

The best Compression possible for the specifically generated list of characters, might just be the program that is used to generate the deterministic data in the first place.

---
Tags: data-compression, randomness
---


# Question
Title: which of the following languages are Recursively Enumerable?
Which of the following languages are recursively enumerable?

A={⟨M⟩∣ TM M accepts at most 2 distinct inputs}

B={⟨M⟩∣ TM M accepts more than 2 distinct inputs}

For first language I think that we can enumerate all the TM's which accept at most 2 distinct inputs using dovetailing method and same is the case with B language.

But on the contrary, both languages are complement of each other so if one is R.E then other one cannot be. So I know that I am going wrong somewhere.

Can someone please explain me how to find if these languages are R.E ?

# Answer
$B$ is r.e, but $A$ is not.

You can construct a TM which takes as input $M$ and simulates $M$ on every string of $0$ and $1$ in canonical order for each step $n$. In other words, if $s\_1, s\_2,...$ are strings on $0$ and $1$ in canonical order, then starting from $n=0$ you run $M$ for $n$ steps on $s\_1, s\_2,..., s\_n$, that is, for each $n$ run $M$ on all $s\_1, s\_2,..., s\_n$ for $n$ steps (not just 1 step for $s\_1$, 2 steps on $s\_2$,... careful!). Each time just check if a string is accepted. If more than two strings are accepted then halt with accept, otherwise go on.

However we cannot use the same approach for $A$ since we cannot check infinitely many strings and say that they are not accepted except 1 or 2 certain strings IN FINITE amount of time. In other words, suppose we somehow determined that $M$ has accepted two strings, then how can we decide that the rest of infinite number of strings are not accepted by $M$ in finite amount of time?

You can also use the Rice's theorem for recursive index set. $A$ violates the **containment** property in the Rice's theorem. Namely, if $L$ is in $A$ and $L \subseteq L'$ for some r.e. $L'$, then $L'$ is in $A$. Assume $L=\\{00, 11\\}$. Then $L$ is in $A$. Let $L'=\\{00,11, 01, 10\\}$. Then $L \subseteq L'$ where $L'$ is clearly r.e. But $L' \notin A$.

**Update (upon comment)**

**Task**: We want to systematically simulate each TM on every input on $\\{0, 1\\}$.

**Solution:** First note that there is a one-to-one correspondence $f$ between the set of natural numbers $N$ and $N^3$ all 3-tuples of natural numbers. So, we can effectively convert each integer $m$ into the corresponding 3-tuple $\<i,j,k\>$. This means that if we start to count all integers then we can enumerate all possible 3-tuples, so that **each 3-tuple is eventually reachable in a finite amount of time**.

Now, assume we we have fixed enumerations of all TMs and strings on $0$ and $1$, e.g., $M\_i$'s and $s\_j$'s.

1) Set $n =0$

2) $\<i, j, k\> = f(n)$ \<= compute 3 tuple

3) Simulate the Turing machine $M\_i$ on input $s\_j$ for $k$ steps.

4) If $M\_i(s\_j)$ halts (after $k$ steps) then *do whatever you want to do*

5) increase $n$ by 1 and go to step 2)

Thus, every machine "has a chance" to run on every input for arbitrary number of steps, fair isn't it?

If some machine, say, $M\_{332}$ halts on input $s\_{12}$ then there is an integer, say, $461$, so that $M\_{332}(s\_{12})$ halts in 461 steps. So, if for example $55993$ corresponds to the 3-tuple $\<332, 12, 461\>$, then when $n$ reaches $55993$ (in the algorithm above) you detect that $M\_{332}$ halts on input $s\_{12}$.
> 3 votes

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


# Question
Title: If $NP \neq co-NP$ then no $NP-complete$ problem can be in $co-NP$
If $NP \neq co-NP$ then no $NP-complete$ problem can be in $co-NP$.

I found a proof on Wikipedia that I didn't fully get: https://en.wikipedia.org/wiki/Co-NP

In the line "from this it follows that the set of complements..". Why does it follow? It seems like the author took a complement from both sides of the equation, but that can't be right, can it?

# Answer
We will show the contrapositive: if some NP-complete problem is in coNP, then NP=coNP. Suppose that $L$ is some NP-complete problem which is in coNP. Let $A$ be any problem in NP. Then there is a polytime reduction $f$ from $A$ to $L$ (since $L$ is NP-complete), which means that $x \in A$ iff $f(x) \in L$. Since $L$ is in coNP, this shows that $A$ is in coNP. Hence NP is a subset of coNP.

Now let $B$ be any problem in coNP. Then there is a polytime reduction $f$ such that $x \in B$ iff $f(x) \in \overline{L}$ (since $L$ is NP-complete and $\overline{B}$ is in NP). Since $\overline{L}$ is in NP, this shows that $B$ is in NP, and so coNP is a subset of NP. We conclude that NP=coNP.
> 7 votes

---
Tags: complexity-theory, turing-machines, np
---


# Question
Title: determining whether a program halts or not
I have difficulty understanding the halting problem. I know that for all possible Turing machines and strings w, we don't have a Turing machine that can decide whether a TM M halts on input w. Now suppose we have a program p that, for example, solves the Hamiltonian path problem. Can we conclude from the halting problem that we can't decide whether this program halts or not?

# Answer
> 6 votes
The halting problem is the following problem:

> Given a Turing machine $M$ and an input $x$, decide whether $M$ halts on $x$.

This version of the halting problem is undecidable. For a given Turing machine $M$, the problem might well be decidable. For example, suppose that $M$ is a machine that always halts, and consider the following problem:

> Given an input $x$, decide whether $M$ halts on $x$.

This problem is decidable. Indeed, the following algorithm decides it:

> Output YES.

# Answer
> 5 votes
> In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.

The Halting problem for a specific (narrow) class of programs (Turing machines) may be decidable. But in general, for arbitrary TM $M$and input $w$, the Halting problem is undecidable.

---
Tags: np-complete, undecidability, decision-problem, halting-problem
---


# Question
Title: Running time complexity of Binary Search Trees and Big-Omega
I know that the main operations (Insert, Search, Delete) have a worst-case running time of $\mathcal{O} (h)$. But I wanted to dig into this deeper.

Basically I am having some difficulties understanding "Big-Omega" when it comes to the worst-case time complexity. I usually define them as follows:

Let $t(x)$ be the number of steps taken by an algorithm $\mathcal{A}$ on input $x$.

Let $T(n)$ be the *worst-case* running time complexity of $\mathcal{A}$.

$T(n) = max(t(x))$ where max is over all inputs x of size n.

Then $T(n) \in \mathcal{O}(g(n))$ if for every input of size $n$, $\mathcal{A}$ takes *at most* $c \cdot g(n)$ steps.

Moreover,

$T(n) \in \Omega(g(n))$ if *for some* (there exists) inputs of size $n$, $\mathcal{A}$ takes at least $c \cdot g(n)$ steps.

Returning to BSTs....

We know that for all inputs of size $n$, in the worst case, the height of the tree is $n$, which means we need to visit all $n$ nodes in the worst-case. This is the "ultimate" worst case (forgive my lack of rigour here!), meaning it cannot get any worse, and hence $\mathcal{O}(n)$ running time. But we also know that a tree may be balanced, in which case we could argue that there exists such an input (a balanced tree) such that we would take at least $\Omega(logn)$ for the running time. This is still a "worst case", but a lower bound to that worst case.

I don't feel that is quite right, nor does it make much sense. Perhaps I am just lacking an understanding of how to determine when $T(n) \in \Omega(g(n))$.

any help appreciated!

# Answer
Big $O$ and big $\Omega$ are not about running times, they are about the rate of growth of functions. If $f(n)$ is the worst-case running time of some operation on inputs of length $n$, then $f(n) = \Omega(g(n))$ means that there exists $C \> 0$ such that for *some* input of length $n$, the running time is at least $Cg(n)$. The fact that we are talking about big $\Omega$ rather than big $O$ doesn't mean that we switch from worst case to best case. On the contrary, we are estimating the very same function, but from below rather than from above.
> 5 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, landau-notation
---


# Question
Title: Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted?
Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted?
That is, each node in the topological graph should be visited once **at least** (instead of **exactly**).

Is it still NP-complete or reduced to a P problem?
How would this modification affect classical methods for solving the original TSP such as dynamic programming, mixed integer programming, meta-heuristics and maybe branch-and-cut/bound/price?

---

What I have tried:

I believe this variant might be easier to solve, but after a sketchy thought about the MIP model, I found it is hard to write the sub-tour elimination constraints.

I have checked TSP Where Vertices Can be Visited Multiple Times but it is asking for a working solution which could be a heuristic that does not guarantee the optimality and computational time. This is not what I want.

# Answer
No, it doesn't become easier. Metric TSP (the version where the distances obey the triangle inequality) is still **NP**-complete but, in this scenario, the shortest tour always visits every city exactly once. The triangle inequality guarantees that going directly to a new city is always faster than going there via somewhere you've already been.
> 9 votes

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


# Question
Title: How to solve a knapsack problem with increased weight limit?
Let us consider the knapsack problem. Given a set $P$ of $n$ items where each item has weight $w\_i$ and value $v\_i$ for all $i=1,2,\ldots,n$. We have two bins, one has a weight limit of $W$ and the other has a weight limit of $W'=2W$. Assume that we have an optimal algorithm $\texttt{OPT}$ that solves the knapsack problem.

Let $O$ denotes the value of an optimal solution when we apply $\texttt{OPT}$ to the first bin (that has a weight limit of $W$) and to the set of items $P$. Also, let $O'$ denotes the value of an optimal solution when we apply $\texttt{OPT}$ to the second bin (that has a weight limit of $W'=2W$) and to the same set of items $P$.

Can we compare $O$ and $O'$?

I guessed that $$O'\leq 2O.$$

# Answer
> 2 votes
That guess is obviously wrong. If all items have weight 666 and value 1, then you can fit 3 items into a bin of size 2000, and only one into a bin of size 1000.

If all weights are W \< $w\_i$ ≤ 2W, then O = 0 and O' = highest value of a single item.

There is very little that you can say except the obvious O ≤ O'. You might have "valuable" items with a total weight ≤ W, and all other items are worthless. Then O' is not or only very little greater than O. Or all items with weight ≤ W might be worthless with some items with weight W \< $w\_i$ ≤ 2W very valuable, then the ratio O' / O can be arbitrarily large.

---
Tags: algorithms, lower-bounds, upper-bound
---


# Question
Title: Longest AP that can be formed (with difference 1) in an unsorted array of integers
By integers, I mean a whole number.

Example:

```
Input : 2, 4, 7, 9, 3, 1, 11

Output: 1,2,3,4 forms an AP (of difference 1) with length 4.

```

An obvious solution is to sort the array with a comparison based algorithm O(nlogn) and then do a second scan through the unsorted array to find the longest sequence.

Can we have a better time complexity (at the expense of addition space)?

# Answer
If you're allowed to use hash tables, you can get a linear time algorithm.

Go over all nodes, putting the unique nodes in a hashtable, and constructing a new array only with the unique values. Now go over the new array and upgrade it to a graph $G = (V,E)$ in which $V$ are the unique values and the edges connect $i$ to $i+1$. Go over the graph, and whenever you see a vertex with no incoming edge, follow the unique path emanating from it and count its length. The answer is the maximal length of such a path.

This solution uses a hashtable to efficiently construct the graph. This suggests that you might not be able to do better than $n\log n$ if you are only allowed to use comparisons. One way to prove it would be by reduction from element uniqueness, which is known to require $n\log n$ comparisons.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Rod Cutting without using dynamic approach
## Question

I want to Implement Rod cutting Algorithm without Dynamic Programming Approach.

Let me Describe the problem statement.

> Given a rod of length $n$ inches and a table of prices $p\_{i}$ for $i=1,2,3,4,\\,.\\,.\\,.$ determine the maximum revenue $r\_n$ obtainable by cutting up the rod and selling the pieces.

In cormen, the Algorithm is implemented as -:

```
CUT-ROD (p,n)
1 if n == 0
2 return 0
3 q = - inifinity
4 for i = 1 to n
5 q =max(q, p[i]+CUT-ROD(p,n-i))
6 return q

```

I got this algorithm , i may explain it with a example-:

Say we want to determine maximum revenue for $n=4$,

and the profit associated with each inches i.e $i=1,2,3,4$is given as follows-:

$p\[1\]=1,p\[2\]=5,p\[3\]=8,p\[4\]=9$

Now Moving to the algorithm ,if we want to find maximum revenue for Length 4 inch ,we need to call CUT-ROD$(p,4)$.How will it process , i mean what will be its sequence!?i can explain-:

> CUT-ROD$(p,4)$ will be computed by
>
> maximum value of
>
> * $p\[1\]+$CUT-ROD$(p,3)$
> * $p\[2\]+$CUT-ROD$(p,2)$
> * $p\[3\]+$CUT-ROD$(p,1)$
> * $p\[4\]+$CUT-ROD$(p,0)$

for $i=1,2,3,4$ respectively.

Now when $i=1$, it will encounter CUT-ROD$(p,3)$

> CUT-ROD$(p,3)$ will be computed by
>
> maximum value of
>
> * $p\[1\]+$CUT-ROD$(p,2)$
> * $p\[2\]+$CUT-ROD$(p,1)$
> * $p\[3\]+$CUT-ROD$(p,0)$

for $i=1,2,3$ respectively.

> CUT-ROD$(p,2)$ will be computed by
>
> maximum value of
>
> * $p\[1\]+$CUT-ROD$(p,1)$
> * $p\[2\]+$CUT-ROD$(p,0)$

for $i=1,2$ respectively.

> CUT-ROD$(p,1)$ will be computed by
>
> maximum value of
>
> * $p\[1\]+$CUT-ROD$(p,0)$

for $i=1$

CUT-ROD$(p,1)$=1,CUT-ROD$(p,2)$=$max(1+1,5)=5$

CUT-ROD$(p,3)$=$max(1+5,5+1,8+0)=8$

CUT-ROD$(p,4)$=$max(1+8,5+5,8+1,9+0)=10$

## MY Doubt

I implemented the $C$ code,but it is giving wrong result.I don't know why!

I guess that the sequence of the function call is wrong .Here is the code.

```
#include<stdio.h>
int p[100];
int result=-9999;
int count=0;
int max(int x,int y)
 {
   return (x > y)? x : y;
 }
int recrsv_top_down(int sizee)
 {
   int i;
   if (sizee<=0)
   {
     return 0;
   }
   for(i=1;i<=sizee;i++)
   {
     result=max(result,(p[i]+(recrsv_top_down(sizee-i))));
   }
   return result;
 }
int main()
 {
    int size,i,result;
    printf("enter the size of rod\n");
    scanf("%d",&size);
    printf("enter the profit of assocaited length\n");
    for(i=1;i<=size;i++)
    {
     printf("enter profit assocaited with length %d \n ",i);
     scanf("%d",&p[i]);
    }
    printf("\n***************OUTPUT*****************\n");
    result=recrsv_top_down(size);
    printf("Maximum profit is %d\n",result);
    return 0;
}

```

Sorry for the long post , but i have no option!!!

Please help me out !

# Answer
In `recrsv_top_down`, declare `result = -1000` as a **local** variable.
> 2 votes

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


# Question
Title: How can I calculate the new quotient if I came to know divisor is increased by one?
If I have two number consider **a** and **b** and let their division quotient is **c**. I know the value of **c** but I don't know either value of **divided**(a) or **divisor**(b). If I came to know the value of divisor is increased by one, can I somehow calculate the new value of **quotient**(c)

I **guess**, *maybe* using some bit manipulation rules or tricks, I could get the new value of quotient **c**

Example: A / B = 50 IF B is increased by 1, can I somehow calculate the new value in quotient?

# Answer
> 1 votes
Knowing the ratio r = A / B and nothing else about the numbers A and B, there is very little we can say about for example A / (B + 1) or A / (B - 1). We have A = rB. If for example B = 1, then A = r, and A / (B + 1) = r / 2, half the value of A / B. On the other hand, if B = 1,000,000 and A = r\*1,000,000 then A / (B + 1) = r * 1,000,000 / 1,000,001 = r - r / 1,000,001, barely different from r.

In the example A / B = 50 and r = 50, when B is replaced with B + 1, the ratio r changes from 50 to 25 if B = 1, but only from 50 to about 49.999,950 if B = 1,000,000.

---
Tags: discrete-mathematics, mathematical-programming
---


# Question
Title: How to find the most unique vectors in a set?
A question bridging math and computer science, I have on the order of 10000 vectors each of a equal but high dimension, say 6 or 7 dimensions. I want to find a given number of 'unique' vectors in the set, the number generally equal to the dimension of the vectors. In math terms I believe I want to find a subset of vectors that has the biggest angle from its neighbours in that sub set. Vector length is also a factor, i.e. a unique but nearly zero length vector is less preferred than one less unique in angle but has a finite length.

An example:

1: \[1 2 4 1 5\]

2: \[1 1 2 1 3\]

3: \[1 2 4 1 4\]

...

9999: \[2 1 1 2 2\]

10000: \[4 5 4 2 1\]

vectors 1 and 3 are quite similar, 2 less so, 10000 is most different. I think the dot product and higher order 'angle' is the best measure of uniqueness, though there may be better.

Visually, collapsing the dimension down to 2, the vectors below in black represent the full set, the vectors in red are the subset of seven most unique.

**Concept update: 03/05/2018**

I have recently stumbled upon the concept of the Latin hypercube, and the higher dimensional mathematics behind it that attempt to find an even spread of higher-dimensional vectors. I don't know exactly how this could be applied, but it has been the closest concept so far. Can anyone see how it might be applicable to the problem?

# Answer
> 3 votes
I suspect your problem might be NP-hard (by reduction from Clique), so it might be hard to find an efficient algorithm for it.

One heuristic is to use the farthest-point first method, where at each stage you pick the point whose angle to the others already picked is as large as possible. In other words, suppose we have already picked a set $S$ of vectors. Now we find the vector $x$ that maximizes $\min \\{\text{angle}(x,s) : s \in S\\}$, add it to $S$, and repeat. This most likely won't give the optimal set of vectors, but it might give something that is somewhat close to optimal.

Another possible approach is to use binary search and some kind of clique-finding algorithm. Let $t$ be a threshold. Form an undirected graph $G$ where each vector is a vertex in the graph; and you have an edge $(u,v)$ if the angle between the two vectors $u,v$ is at least $t$. Then if you can find a clique of size $k$ (where $k$ is the desired size of your subset), then you've found a subset of vectors that are all at angle $\ge t$ from each other. Now repeat this, using binary search on $t$ to find the largest $t$ for which you can find a $k$-clique. In this way you might be able to take advantage of methods in the literature for finding $k$-cliques. (For instance, one simple preprocessing step you can do to reduce the size of the graph is: delete any vertex whose degree is less than $k$, and repeat until convergence.)

---
Tags: algorithms, mathematical-programming
---


# Question
Title: Not sure which NPc problem to use for NPc reduction problem,
I'm attempting to prove a problem is NPc, but I'm not sure which one would be optimal to use,

The problem is:

There are $n$ boars to be caged, and $m$ cages which each cage being able to hold $k$ boars.

Any boar can be put in in any cage, but certain pairs of boars can't be put together in the same cage.

I'm thinking of SAT or Knapsack to reduce to this problem, but not sure which. If anyone can lead me to the right direction or get me started I'd really appreciate it, thanks

# Answer
You don't need a reduction. You have a set of objects and you need to assign a number from $\\{1, \dots, k\\}$ to each object such that certain pairs of objects don't get the same number. There's already a well-known **NP**-complete problem that fits exactly this description. You're probably most familiar with the case $k=3$, but it's **NP**-complete for all fixed $k\>2$ and also when $k$ is part of the input.
> 0 votes

# Answer
Think about each boar as a node, and connect those boars that may not be put in the same cage with an edge. You will get a graph. Then try to color nodes with $m$ different colors, providing no adjacent nodes have same colors. Those boars with the same color are in the same cage. You should be familiar with $NP$ complete graph coloring problem.
> 0 votes

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


# Question
Title: How to demonstrate that a language is regular for k?
I sort of need an explanation on how can I demonstrate that a language formed by strings that are multiples of k, is a regular language

I really dont know how

# Answer
> 2 votes
Generalizing the other answer, here is a *complete* classification of regular language of this sort.

> The language $\\{ x \in \Sigma^\* : |x| \in S \\}$ is regular iff there exist $n \geq 0$ and $k \geq 1$ and sets $A \subseteq \\{0,\ldots,n-1\\}$, $B \subseteq \\{0,\ldots,k-1\\}$ such that $$ S = A \cup \\{ n+ mk + r : m \geq 0, r \in B\\}.$$

One direction follows from a direct construction (either a DFA or a regular expression), and the other from the pumping lemma (exercise) or Parikh's theorem.

# Answer
> 1 votes
I assume that you wish to demonstrate that $L = \\{ w \in \Sigma^\* \colon |w| = k, 2k, ...\\}$ for some $k \> 0$ is a regular language (correct me if I am wrong).

If that is the case, all you need to do is to construct a DFA $M$ such that $L(M) = L$:

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


# Question
Title: prove that NDFA = {< M1,M2 > | M1 and M2 are DFAs such that there is at least one string x that is accepted by neither M1 nor M2} is decidable?
How can I prove that $NDFA = \\{ \langle M\_1,M\_2 \rangle | M\_1$ and $M\_2$ are $DFA$s such that there is at least one string $x$ that is accepted by neither $M\_1$ nor $M\_2\\}$ is decidable using the fact that $ANFA = \\{\langle N \rangle | N$ is an $NFA$ with some input alphabet $\Sigma$, and $L(N) = \Sigma^\*\\}$?

# Answer
> 0 votes
We try to decide the language $NDFA$ using a language that decides $ANFA$.

If $x$ is not in neither $L(M\_1)$ or $L(M\_2)$, then it means that it's not in $L(M\_1) \cup L(M\_2)$, in other words there is at least one string $x$ which is not in $L(M\_1) \cup L(M\_2)$, thus $L(M\_1) \cup L(M\_2) \neq \Sigma^\*$ We know that we can (in finite time) construct a $NFA$, $M$ for language $L(M\_1) \cup L(M\_2)$. Now since $ANFA$ is decidable, $\overline{ANFA}$ is also decidable, so there is a $TM$ that can decide that $L(M) \neq \Sigma^\*$, therefor the original language $NDFA$ is also decidable.

---
Tags: turing-machines, finite-automata, undecidability
---


# Question
Title: Maximum cut using a 1/2 approximation greedy algorithm
I have the following greedy algorithm for max cut problem:

1. Initialization: $A \leftarrow \\{v\_1\\}$ , $B \leftarrow \\{v\_2\\}$
2. For $v \in V − \\{v\_1, v\_2\\}$ do:

if $d(v,A) \geq d(v,B)$ then $B \leftarrow B \cup \\{v\\}$,

else $A \leftarrow A \cup \\{v\\}$.
3. Output $A$ and $B$.

Here, $v\_1$ and $v\_2$ are arbitrary vertices in $G$ and $d(v,A)$ denotes the number of edges between vertex $v$ and set $A \subset V$.

To show that this is a factor 1/2 approximation algorithm, I used the upper bound that $opt \leq |E|$ and internal\_degree(v) and external\_degree(v).

But there is a problem, I can not say that when the algorithm terminates, we have external\_degree(v) $\geq$ internal\_degree(v) for all v (there is a counterexample) , of course since each vertex is check once so time complexity is O(n).

Is there any other way to show this factor?

# Answer
> 5 votes
Let us say that an edge $(v,w)$ *belongs to $v$* if when $v$ is processed, $w \in A \cup B$, and that $(v\_1,v\_2)$ belongs to $v\_2$. Denote by $N\_v$ the number of edges belonging to $v$, and by $C\_v$ the number of those edges that are cut by the algorithm. Step 2 ensures that $C\_v \geq N\_v/2$ (this clearly holds for $v = v\_2$ as well). Therefore $\sum\_v C\_v \geq \sum\_v N\_v/2$. Finally, notice that $\sum\_v N\_v$ is the number of edges in the graph, and $\sum\_v C\_v$ is the size of the cut produced by the algorithm.

Here is a sketch of another proof. At any point in time, define the *score* of an edge $(u,v)$ as follows:

* If $u,v \in A$ or $u,v \in B$, the score is 0.
* If $u \in A$ and $v \in B$ or vice versa, the score is 1.
* Otherwise the score is 1/2.

You can check that the initial score is at least half the number of edges, the score never decreases, and the final score is number of edges cut by the algorithm.

---
Tags: approximation, greedy-algorithms, max-cut
---


# Question
Title: single tape NTM to single tape DTM equivalence
I am having some trouble understanding the equivalence of DTM's and NTM's. If you have Sipser its under 7.11; where he says that any NTM $N$ that halts after $t(n)$ steps has an equivalent DTM $D$ that halts after $2^{O(t(n))}$ steps.

He says that $N$ 's "computation tree" has at most $b^{t(n)}$ leaves, where $b$ is the maximum number of choices a transition can have in $N$, and the tree is at most $t(n)$ "levels deep", since $N$ halts after $t(n)$ steps per definition.

Now if one would like to simulate $N$ with $D$ you would have to go through no more than $t(n)b^{t(n)}$ steps to halt.

Then Sipser says that $O(t(n)b^{t(n)})= 2^{O(t(n))}$ which I dont understand.

In my understanding the runtime of $D$ should be $O(b^{t(n)})$ where $b \>0$.

Can someone clear this up for me ?

Relevant pages in Sipser are 255-256.

# Answer
The claim is that for constant $b$, if $f = O(t(n) b^{t(n)})$ then $f = 2^{O(t(n))}$. Indeed, $xb^x \leq b(b+1)^x$, and so $$ Ct(n) b^{t(n)} \leq Cb (1+b)^{t(n)} = 2^{\log\_2(1+b) \cdot t(n) + \log\_2 b + \log\_2 C}. $$ From here it's not hard to check that $f = O(t(n)b^{t(n)})$ implies $f = 2^{O(t(n))}$.
> 3 votes

---
Tags: turing-machines, time-complexity, nondeterminism
---


# Question
Title: Efficiently find smallest unique substring
Let's say we have a string $s$. We define a unique substring in $s$ as a substring that occurs only once in $s$. How can we efficiently find such a substring with the smallest length in $s$?
The most obvious solution is in $O(n^3)$ by checking every substring. What if we can preprocess the string?

# Answer
You can try suffix array approach which find all suffix of a given string of length n in O(n) time. There are many algorithm to construct suffix array from a given input string.
Look at complete taxonomy here
http://www.cas.mcmaster.ca/~bill/best/algorithms/07Taxonomy.pdf

For your problem you can use suffix array couple with some additional counter to find solution.
> 2 votes

# Answer
I can suggest a simple method that will achieve this in many practical cases in linear time, for example if you examine "War and Peace", but will fail if some characters are very common.

Assume the string to be examined has n ≥ 1 characters, and there are m characters where m is not very large. Build a table which contains for every character c all positions within the string where that character c can be found. If we are lucky, some character appears only once and we have a solution. Then for each character c, and each second character d, find all locations where the string "cd" can be found - we do this preferably first for characters c that are rare. Again we might be lucky and find a two letter string occurring only once. We repeat for three, four, five character strings and so on.

If we have n characters, then the table of substrings can only have about n/2 entries (otherwise some substring must be unique). With "War and Peace" this will work quite quickly. You might add some code for the situation where the number of different substrings is very small, for example with the string "ababababab...".

I think this might run in n log n in many practical cases (the length of the shortest unique substring might grow with log n) and in quadratic time worst case with a good implementation.
> 1 votes

---
Tags: algorithms, data-structures, regular-expressions, strings, pattern-recognition
---


# Question
Title: Multi-threading : N cores = N times one core?
This question is about modern CPU architectures and multi-threading. I'm mainly interested in personal computers or servers having 2, 4, 8, 16... cores like for example an Intel core i7. I mean not a NASA supercomputer or GPU vector processing.

You have N cores.

You write an algorithm in a low level language such as C, C++, Java, C#... using essentially arithmetic (+/x/and/or...), basic for loops, floating point and arrays. It is mono threaded and your algorithm takes say 1 minute to complete.

Now you start N threads, and run the same algorithm on each of these threads INDEPENDENTLY : no lock (semaphores) or write access to common objects. Does each thread take 1 minute to complete, so that the total running time is 1 minute ?

What prevents this from being as good as it ? I know for example that if the threads write on the same parts of the memory (even without needing locks), the CPU caches of each processor need to refresh and the whole thing can be slowed down a lot.

Do you know some of the classical cases where the situation might be significantly different from "each thread one minute" and explain what about the architecture causes this ?

Note : Intel (for example) often uses hyperthreading so that 4 cores appear to be 8 logical processors. I don't want to focus on hyperthreading and I would like to simplify my question as if hyperthreading didn't exist. Imagine that each core can process the instructions of a single thread at a time.

I'm of course interested by things I might not be aware of in modern CPU architecture.

# Answer
If I understood your question correctly, you are essentially asking:

> Given a piece of *sequential* code, if we run *N* instances of it in parallel on *N* cores (on *real*, modern, typical, and not-particularly-high-end CPU models), should we expect any slowdown versus running only a single instance of that program on a single core?

As usual, the answer is: it depends. *However*, the answer will often be *yes* indeed, you should expect a slowdown. It will often take more than "one minute" per instance.

How and why? Intuitively, since *you've got shared (and limited) resources*, your threads will naturally compete for them.

For instance, main memory will be shared. Thus, if your program is bandwidth-bound (which is very common across many applications), few threads can easily fully saturate your limited memory bandwidth (essentially, they can request data from memory at a faster pace than your hardware can support) and you may notice degradation in performance (given your "one minute" measure) beyond that limit. You may want to look up the **bandwidth-wall problem**.

For another similar instance, many modern CPU models will have a shared last-level cache per chip/socket. These (typically L3) caches will often provide significantly higher bandwidth and lower latency for any thread (on the chip) accessing any cached data, in comparison to directly accessing main memory. Once threads start competing for this shared resource, the total working set size of all thread may exceed the cache capacity -- even though a single thread was running within cache. They effectively *thrash* the cache for each other.

You may want to contrast these cases to the case where the program is compute-bound and CPU-intensive yet can work with high locality in the smaller, private (i.e., not shared) caches. There are probably non-memory-hierarchy reasons as well (unlike the two above), although the reasons above are perhaps among the most obvious and most significant (or, at least, that is what I would expect).
> 5 votes

---
Tags: computer-architecture, cpu, threads
---


# Question
Title: Formal Languages - Matching this regular expression
I'm trying to write a regular expression over the alphabet {0,1,2} for the language in which every 1 is preceded by 0. For example 2200201010, 01022020102012 are strings of the language.

I've tried with this:

```
(0+2)*(01)*(0+2)*(01)*(0+2)*

```

, where '+' means {0,2,00,02,20,22,.....}. Is this reg-exp correct? Thank you

# Answer
> 1 votes
`(01+2+0)*` this may work because the string will contain any combination of given inputs and a 1 will always be preceded by a 0.

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


# Question
Title: If $L$ is NOT Turing-recognizable, does that mean that super sets with $L$ are also not?
Suppose there is a language $L$ that is not Turing-recognizable. Now suppose, for every word in $L$, you would concatenate a "0" as prefix, resulting in $L' = \\{0w | w \in L\\}$. Does this mean that $L'$ is also not Turing-recognizable?

I would argue that $L'$ is also not Turing-recognizable:

No Turing machine recognizes $L$. So there exists no TM that recognizes all the words in $L$. That means that all the words that can not be recognized by a TM that are in L, also can not be recognized even with a "0" added before them. Because after the TM's head reads the "0", we assume that the head will read what comes after, which is a word that is not Turing-recognizable. One could argue that the head doesn't need to read the word and just go to "accept" after reading the 0, but then I can also build a TM that would just go to "accept" straight away before reading this word at all, meaning that the word was not Turing-recognizable which contradicts the initial statement.

In other words, after reading the "0", the TM will have to come across the not Turing-recognizable word, which it can't recognize. Therefore $L'$ is also not Turing-recognizable.

To generalize, I think if a not Turing-recognizable language is a subset of another language, then that language is also not Turing-recognizable.

However, I feel my explanation is shaky and I'm not convinced I am correct. Can anyone verify my claim, and either prove me wrong or give tips for a better proof?

# Answer
> 1 votes
If $L'$ were Turing-recognizable then there would be a TM $M$ which would enumerate every string in $L'$. In particular, we could construct a TM that would print on the tape every string in $L'$. Then we could easily modify this machine to enumerate the language $L$. Just do not print the first symbol on the tape (skip the initial $0$). Thus we construct a machine which enumerates $L$. But $L$ is not Turing-recognizable (not r.e.) by assumption. A contradiction.

$L'$ in your example may be expressed as a concatenation of languages $\\{0\\}$ and $L$, that is, $L' = \\{0\\}L$. However, we cannot generalize this result to arbitrary languages. For example, $\\{0,1\\}^\*L = \\{0,1\\}^\*$ is r.e. even if $L$ is not r.e. language on $0$ and $1$ containing empty string.

As for your claim "*a not Turing-recognizable language is a subset of another language, then that language is also not Turing-recognizable*", it is false too, since a not Turing-recognizable language $L$ on $0$ and $1$ is a subset of $\\{0,1\\}^\*$ which is definitely r.e., even decidable.

# Answer
> 0 votes
We know that if $L\_1 \leq\_{\mathrm m} L\_2$ and $L\_2$ is recognisable, then so $L\_1$.

We have that $L \leq\_{\mathrm m} L'$ by the simple mapping reduction

$f(w) = 0w$

It is easy to see that $w \in L$ iff $f(w) \in L'$ and $f$ is trivially computable.

Since $L\_1$ is not recognisable, we know that $L\_2$ cannot be recognisable.

Students have lots of favourite "theorems" about how language inclusion somehow preserves decidability or recognizability (or lack thereof), and none of them are true.

The student favourite

> If $L\_1$ is unrecognisable and $L\_1 \subseteq L\_2$, then $L\_2$ is also unrecognisable

falls because every language $L$ is a subset of the total language $\Sigma^\*$ which is trivially decidable.

---
Tags: turing-machines, automata
---


title: Quicksort dual pivot or single

text:
# Question
Title: Quicksort dual pivot or single
I've seen to explanations for the quick sort algorithm.

One in which a pivot is chosen, and put into place, before both sides of the pivot are recursively pivot-sorted.

Another involved a more complicated solution involving two pivots which interchanged.

What are the benefits of either solution, why was the dual-pivot solution created? Is it faster?

# Answer
Basically Dual-pivot Quicksort buys you two items: The best case running time is $\Theta(n \log\_3 n)$ instead of $\Theta(n \log\_2 n)$ since each partition is the third part of the entire current range. Also, if one pivot is not good (it is close to one of the ends of the current range), there is a good chance that the second pivot will be better.
> 1 votes

# Answer
This is a visualization of the algorithm. And this is claim

> This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.
> 0 votes

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


# Question
Title: How are variables stored in and retrieved from the program stack?
Apologies in advance for the naivety of this question. I am a 50 year old artist trying to properly understand computers really for the first time. So here goes.

I have been trying to understand how data types and variables are handled by a compiler (in a very general sense, I know there is a lot to it). I'm missing something in my understanding of the relationship between storage in "the stack" and value types, and storage on "the heap" and reference types (the quotation marks are meant to signify that I understand that these terms are abstractions and not to be taken too literally in such a simplified context as the way I am framing this question). Anyway, my simplistic idea is that types like Booleans and integers go on "the stack" because they can, because they are known entities in terms of storage space, and their scope is easily controlled accordingly.

But what I don't get is how variables on the stack are then read by an application- if I declare and assign `x` as an integer, say `x = 3`, and storage is reserved on the stack and then its value of `3` is stored there, and then in the same function I declare and assign `y` as, say `4`, and then following that I then use `x` in another expression, (say `z = 5 + x`) how can the program read `x` in order to evaluate `z` when it is below `y` on the stack? I am clearly missing something. Is it that the location on the stack is only about the lifetime/ scope of the variable, and that the whole stack is actually accessible to the program all the time? If so, does that imply there is some other index that holds the addresses only of the variables on the stack to allow the values to be retrieved? But then I thought the whole point of the stack was that values were stored in the same place as the variable address? In my puny mind it seems that if there is this other index, then we are talking about something more like a heap? I'm clearly very confused, and I'm just hoping there is a simple answer to my simplistic question.

Thanks for reading this far.

# Answer
Storing local variables on a stack is an implementation detail – basically an optimization. You can think of it this way. When entering a function, space for all local variables is allocated somewhere. You can then access all variables, since you know their location somehow (this is part of the process of allocation). When leaving a function, the space is deallocated (freed).

The stack is one way of implementing this process – you can think of it as a kind of "fast heap" which has limited size and so is only appropriate for small variables. As an additional optimization, all local variables are stored in one block. Since each local variable has known size, you know the offset of each variable in the block, and that is how you access it. This is in contrast to variables allocated on the heap, whose addresses are themselves stored in other variables.

You can think of the stack as very similar to the classical stack data structure, with one crucial difference: you are allowed to access items below the top-of-stack. Indeed, you can access the $k$th item from the top. This is how you can access all your local variables with pushing and popping. The only pushing being done is upon entering the function, and the only popping upon leaving the function.

Finally, let me mention that in practice, some of the local variables are stored in registers. This is since access to registers is faster than access to the stack. This is another way of implementing a space for local variables. Once again, we know exactly where a variable is stored (this time not via offset, but via the name of a register), and this kind of storage is only appropriate for small data.
> 28 votes

# Answer
Having `y` on the stack doesn't physically prevent `x` from being accessed, which, as you pointed out, makes computer stacks different from other stacks.

When a program is compiled, the positions of variables in the stack are also predetermined (within the context of a function). In your example, if the stack contains an `x` with a `y` "on top of" it, then the program knows *in advance* that `x` will be 1 item below the top of the stack while inside the function. Since the computer hardware can explicitly ask for 1 item below the top of the stack, the computer can get `x` even though `y` also exists.

> Is it that the location on the stack is only about the lifetime/ scope of the variable, and that the whole stack is actually accessible to the program all the time?

Yes. When you exit a function, the stack pointer moves back to its previous position, effectively erasing `x` and `y`, but technically they will still be there until the memory is used for something else. Additionally, if your function calls another function, `x` and `y` will still be there and can be accessed by intentionally going too far down in the stack.
> 26 votes

# Answer
To provide a concrete example of how a compiler manages the stack and how values on the stack are accessed, we can look at visual depictions, plus code generated by `GCC` in a Linux environment with i386 as the target architecture.

**1. Stack frames**

As you know, the stack is a location in the address space of a running process that is used by *functions*, or *procedures*, in the sense that space is allocated on the stack for variables declared locally, as well as arguments passed to the function (space for variables declared outside any function (i.e. global variables) is allocated in a different region in virtual memory). Space allocated for all of a function's data is referred to a *stack frame*. Here is a visual depiction of multiple stack frames (from Computer Systems: A Programmer's Perspective):

**2. Stack frame management and variable location**

In order for values written to the stack within a particular stack frame to be managed by the compiler and read by the program, there must be some method for calculating the positions of these values and retrieving their memory address. The registers in the CPU referred to as the stack pointer and the base pointer help with this.

The base pointer, `ebp` by convention, contains the memory address of the bottom, or base, of the stack. The positions of all of the values within the stack frame can be calculated using the address in the base pointer as a reference. This is depicted in the picture above: `%ebp + 4` is the memory address stored in the base pointer plus 4, for example.

**3. Compiler-generated code**

> But what I don't get is how variables on the stack are then read by an application- if I declare and assign x as an integer, say x = 3, and storage is reserved on the stack and then its value of 3 is stored there, and then in the same function I declare and assign y as, say 4, and then following that I then use x in another expression, (say z = 5 + x) how can the program read x in order to evaluate z when it is below y on the stack?

Let us use a simple example program written in C to see how this works:

```
int main(void)
{
        int x = 3;
        int y = 4;
        int z = 5 + x;

        return 0;
}

```

Let us examine the assembly text produced by GCC for this C source text (I cleaned it up a bit for the sake of clarity):

```
main:
    pushl   %ebp              # save previous frame's base address on stack
    movl    %esp, %ebp        # use current address of stack pointer as new frame base address
    subl    $16, %esp         # allocate 16 bytes of space on stack for function data
    movl    $3, -12(%ebp)     # variable x at address %ebp - 12
    movl    $4, -8(%ebp)      # variable y at address %ebp - 8
    movl    -12(%ebp), %eax   # write x to register %eax
    addl    $5, %eax          # x + 5 = 9
    movl    %eax, -4(%ebp)    # write 9 to address %ebp - 4 - this is z
    movl    $0, %eax
    leave

```

What we observe is that variables x, y and z are located at addresses `%ebp - 12`, `%ebp -8` and `%ebp - 4`, respectively. In other words, **the locations of the variables within the stack frame for `main()` are calculated using the memory address saved in the CPU register `%ebp`.**

**4. Data in memory beyond the stack pointer is out of scope**

> I am clearly missing something. Is it that the location on the stack is only about the lifetime/ scope of the variable, and that the whole stack is actually accessible to the program all the time? If so, does that imply there is some other index that holds the addresses only of the variables on the stack to allow the values to be retrieved? But then I thought the whole point of the stack was that values were stored in the same place as the variable address?

The stack is a region in virtual memory, whose use is managed by the compiler. The compiler generates code in such a way that values beyond the stack pointer (values beyond the top of the stack) are never referenced. When a function is called, the position of the stack pointer changes to create space on the stack deemed to be not "out of bounds", so to speak.

As functions are called and return, the stack pointer is decremented and incremented. Data written to the stack does not disappear after it is out of scope, but the compiler does not generate instructions referencing this data because there is no way for the compiler to calculate the addresses of these data using `%ebp` or `%esp`.

**5. Summary**

Code that can be directly executed by the CPU is generated by the compiler. The compiler manages the stack, stack frames for functions and CPU registers. One strategy used by GCC to track the locations of variables in stack frames in code intended to execute on i386 architecture is to use the memory address in the stack frame base pointer, `%ebp`, as a reference and write values of variables to locations in the stack frames at offsets to the address in `%ebp`.
> 15 votes

# Answer
There are two special registers: ESP (stack pointer) and EBP (base pointer). When a procedure is invoked the first two operations are usually

```
push        ebp
mov         ebp,esp

```

The first operation saves the value of the EBP on the stack, and the second operation loads the value of the stack pointer into the base pointer (to access the local variables). So, EBP points to the same location as ESP does.

Assembler translates variables names into EBP offsets. For example, if you have two local variables `x,y`, and you have something like

```
  x = 1;
  y = 2;
  return x + y;

```

then it may be translated into something like

```
   push        ebp
   mov         ebp,esp
   mov  DWORD PTR [ ebp + 6],  1   ;x = 1
   mov  DWORD PTR [ ebp + 14], 2   ;y = 2
   mov  eax, [ ebp + 6 ]
   add  [ ebp + 14 ], eax          ; x + y
   mov  eax, [ ebp + 14 ]
   ...

```

Offset values 6 and 14 are computed at compile time.

This is roughly how it works. Refer to a compiler book for details.
> 9 votes

# Answer
You are confused because the local variables stored in stack are not accessed with the access rule of stack: First In Last Out, or just *FILO*.

The thing is that the FILO rule applies to function call sequences and *stack frames*, rather than to local variables.

### What is a stack frame?

When you enter a function, it is given some amount of memory on the stack, called stack frame. Local variables of the function are stored in the stack frame. You can imagine that the size of stack frame varies from function to function since each function has different numbers and sizes of local variables.

How local variables are stored in the stack frame has nothing to do with FILO. (Even the order of appearance of your local variables in your source code does not ensure that local variables will be stored in that order.) As you properly deduced in your question, "there is some other index that holds the addresses only of the variables on the stack to allow the values to be retrieved". The addresses of local variables are typically calculated with a *base address*, such as the boundary address of the stack frame, and *offset values* specific to each local variable.

### So when does this FILO behavior appear?

Now, what happens if you call another function? The callee function must have its own stack frame, *and it is this stack frame that is **pushed** in the stack*. That is, the callee function's stack frame is placed on top of the caller function's stack frame. And if this callee function calls another function, then its stack frame will be pushed, again, on the top of the stack.

What happens if a function returns? When a callee function returns to the caller function, the callee function's stack frame is **popped** out from the stack, freeing space for future use.

So from your question:

> Is it that the location on the stack is only about the lifetime/scope of the variable, and that the whole stack is actually accessible to the program all the time?

you are quite correct here because the local variable values on the stack frame are not really erased when the function returns. The value just stays there, although the memory location where it is stored doesn't belong to any function's stack frame. The value is erased when some other function gains its stack frame which includes the location and writes over some other value to that memory location.

### Then what differenciates stack from heap?

Stack and heap are same in the sense that they are both names that refer to some space on memory. Since we can access any location on memory with its address, you can access any location in stack or heap.

The difference comes from the promise that the computer system makes about how it's going to use them. As you said, heap is for reference type. Since the values in heap have no relation to any specific stack frame, the scope of the value is not tied to any function. A local variable, however, is scoped within a function, and although you *can* access any local variable value that is located out of current function's stack frame, the system will try to make sure that this kind of behavior doesn't happen, by using stack frames. This gives us some kind of illusion that the local variable is scoped to a specific function.
> 9 votes

# Answer
There are many ways to implement local variables by a language runtime system. Using a stack is a common efficient solution, used in many practical cases.

Intuitively, a stack pointer `sp` is kept around at runtime (in a fixed address, or in a register -- it does really matter). Assume that every "push" increments the stack pointer.

At compile time, the compiler determines the address of each variable as `sp - K` where `K` is a constant which only depends on the scope of the variable (hence can be computed at compile time).

Note that we are using the word "stack" here in a loose sense. This stack is not accessed only through push/pop/top operations, but is also accessed using `sp - K`.

For instance consider this pseudocode:

```
procedure f(int x, int y) {
  print(x,y);    // (1)
  if (...) {
    int z=x+y; // (2)
    print(x,y,z);  // (3)
  }
  print(x,y); // (4)
  return;
}

```

When the procedure is called, arguments `x,y` can be passed on the stack. For simplicity, assume the convention is the the caller pushes `x` first, then `y`.

Then, the compiler at point (1) can find `x` at `sp - 2` and `y` at `sp - 1`.

At point (2), a new variable is brought in scope. The compiler generates code that sums `x+y`, i.e. what's pointed by `sp - 2` and `sp - 1`, and pushes the result of the sum on the stack.

At point (3), `z` is printed. The compiler knows it is the last variable in scope, so it's pointed by `sp - 1`. This is no longer `y`, since `sp` changed. Still, to print `y` the compiler knows that it can find it, in this scope, at `sp - 2`. Similarly, `x` is now found at `sp - 3`.

At point (4), we exit the scope. `z` is popped, and `y` is again found at address `sp - 1`, and `x` is at `sp - 2`.

When we return, either `f` or the caller pops `x,y` from the stack.

So, computing `K` for the compiler is a matter of counting how many variable are in scope, roughly. In the real world, this is actually more complex since not all variables have the same size, so the computation of `K` is slightly more complex. Sometimes, the stack also contains the return address for `f`, so `K` must "skip over" that as well. But these are technicalities.

Note that, in some programming languages, things can become even more complex if more complex features must be handled. E.g. nested procedures require a very careful analysis, since `K` now has to "skip over" many return addresses, especially if the nested procedure is recursive. Closures / lambdas / anonymous functions also require some care to handle "captured" variables. Still, the above example should illustrate the basic idea.
> 4 votes

# Answer
The easiest idea is to think of variables as fix *names for addresses* in memory. Indeed, some assemblers display machine code that way ("store value 5 in address `i`", where `i` is a variable name).

Some of these addresses are "absolute", like global variables, some are "relative", like local variables. Variables (i.e. addresses) in functions are relative to some place on the "stack" which is different for every function invocation; that way the same name can refer to different actual objects, and circular calls to the same function are independent invocations working on independent memory.
> 3 votes

# Answer
Data items that can go on the stack are put on the stack - Yes! It is a premium space. Also, Once we pushed `x` into stack and then pushed `y` into the stack, ideally we cannot access `x` until `y` is there. We need to pop `y` to access `x`. You got them correct.

**The stack is not of variables, but of `frames`**

Where you got it wrong is about the stack itself. On the stack it is not the data items that are directly pushed. Rather, on the stack something called `stack-frame` is pushed. This stack-frame *contains* the data items. While you cannot access the frames deep within the stack, you can access the top frame and all data items contained within it.

Lets say we have our data items bundled in two stack frames `frame-x` and `frame-y`. We pushed them one after the other. Now as long as `frame-y` sits on top of `frame-x`, you cannot ideally access any data item inside `frame-x`. Only `frame-y` is visible. BUT given that `frame-y` is visible, you can access all the data-items bundled in it. The whole of the frame is visible exposing all the data items contained within.

**End of answer. More (rant) on these frames**

During compilation, a list of all functions in the program is made. Then for each function a list of *stackable* data items is made. Then for each function a `stack-frame-template` is made. This template is a data structure which contains all those chosen variables, space for function's input data, output data etc. Now during runtime, whenever a function is called, a copy of this `template` is put on stack - along with all the input and intermediate variables. When this function calls some other function, then a fresh copy of *that* function's `stack-frame` is put on stack. Now as long as *that* function is running, *this* function's data items are preserved. Once *that* function ends, its stack-frame is popped out. Now *this* stack-frame is active and this function can access all its variables.

Do note that the structure and composition of a stack-frame varies from programming language to programming language. Even within a language there could be subtle differences in different implementations.

---

*Thank you for considering CS. I am a programmer now a days taking piano lessons :)*
> 2 votes

---
Tags: programming-languages, memory-allocation
---


title: Is the following CFG ambiguous?

text:
# Question
Title: Is the following CFG ambiguous?
I was given the following CFG :

$S \rightarrow A\ |\ B$

$A\rightarrow aAa\ |\ abAb\ |\ bAc\ |\ aca\ |\ abcb\ |\ bcc$

$B \rightarrow bBa\ |\ aBb\ |\ babBc\ |\ bca\ |\ acb\ |\ babcc$

And I have to show if it is ambiguous by giving two leftmost derivations for the same word.

I am pretty sure that there are two leftmost derivations but I can not find them.

I do not need the solution, just a tip where to start with would be enough.

# Answer
> -1 votes
Is unambiguous because there is no string of rule A which is a string or substring of B. And viceversa.

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: What is a good approach to symbol identification/recognition given a path, instead of raster data
Excuse any mistakes in my description as I'm new to ML. But I have an application that takes user input to generate paths/curves (All symbols are single paths) and I would then like to attempt identification. This seems, generally, to be a pretty well studied problem, and there is a lot of reference I can find.

However everything I've found so far starts with some sort of raster format, which makes sense given that often recognition comes in initially in that format. But given my particular set of constraints it seems that there may be additional useful data given that I have paths.

So my question is are there any good techniques for doing identification without first rasterizing my paths that may be well suited for my particular instance, or is rasterizing to a grid particularly well suited to the problem, and should I just raster and solve this problem more classically?

# Answer
What you are looking for is called "on-line recognition". I have written my Bachelors thesis about this:

> Thoma, Martin. "On-line Recognition of Handwritten Mathematical Symbols." arXiv preprint arXiv:1511.09030 (2015).

And I've created the online service write-math.com as a part of it.

As a short introduction, you might be interested in my presentations.

> Are there any good techniques for doing identification without first rasterizing my paths that may be well suited for my particular instance?

Yes. You can on the one hand make it a fixed-length sequence, on the other hand you can use recurrent neural networks (I didn't try that in my bachelors thesis)

> Is rasterizing to a grid particularly well suited to the problem, and should I just raster and solve this problem more classically?

This works astonishingly well. I achieved better results with the rasterized version (in my master thesis which isn't published yet due to bureaucracy problems at my university) than with fixed-length sequence techniques. But I guess the way to go is to do both.
> 4 votes

---
Tags: machine-learning, classification, pattern-recognition
---


# Question
Title: Design PDA or CFG for the following language
$L = \\{wtw' \mid w,w' \in \\{a, b\\}^\*, \hspace{0.3cm} |w|\_a = |w'|\_a, \hspace{0.3cm} |w|\_b=2|w'|\_b, \hspace{0.3cm} t\in\\{c\\}^\* \\}$.

> Note : $|w|\_a$ means the number of $a$ in substring $w$.

To substring $w$, the number of symbol $a$ and $b$ is not relevant to each other.

It's also applied to substring $w'$.

To make matters worse, order of $a$ and $b$ (in both $w$ and $w'$) is not defined. So order can be anyway... It makes the problem harder for me.

I designed several PDAs but they resulted in contradiction.

So I tried to construct a CFG. But designing a CFG is more difficult for me.

Could you give me some hints to design PDA or CFG for the above language?

# Answer
There is no such grammar: the language is not context-free.

$L\cap a^\*b^\*ca^\*b^\* = \\{a^nb^{2m}ca^nb^m\mid m,n\ge 1\\}$.
> 1 votes

---
Tags: automata
---