# Question
Title: How can we show that P is not closed under taking all long prefixes?
> Let P be the complexity class of languages decidable by Turing machines running in polynomial time. Say a prefix $s$ of a string $x$ is a long prefix (or an L prefix) if $|s|\ge |x|/2$. For a language $A$, let $LP(A)$ be the language of all L prefixes of strings in $A$. Show that $P$ is not closed under $LP(\cdot )$ unless $P=NP$, where NP is the class of languages with polynomial-time verifiers.

I know that for any $A\in NP, LP(A)$ is also in NP. I also know some properties about P, such as the fact that it's closed under complement, intersection, union, and concatenation. But I can't think of a language in P that's not closed under the LP operation. Intuitively, to find such a language, I think it might be useful to construct a language for which it would be very hard to efficiently determine all L prefixes. The resulting language $A$ should most likely satisfy that $LP(A)$ is an NP-complete language. If so, then if $P$ were closed under $LP(\cdot )$, $LP(A)$, an NP-complete language would be in P. Then for any language $B$ in NP, $B\in P.$ Since $NP\subseteq P,$ the result follows.

Alternatively, it might be slightly easier to show that for each $A\in NP,$ we can find some $B\in P$ so that $A\leq\_m^p LP(B)$.

# Answer
> 1 votes
In fact Yuval's hint is all the solution you need: consider instance $I$ of any $\mathsf{NP}$-complete problem (e.g. 3SAT) and its proof $c$, let the proof appear in the second half of the constructed language $L$. Then if we can decide whether $I \in \operatorname{LP}(L)$ in poly time, this also means we can decide whether there exists a valid proof $c$ for $I$ in poly time, thus $\mathsf{P} = \mathsf{NP}$.
Formally, construct language $L = \\{\left\<I, c\right\> | \text{$I \in \mathsf{3SAT}$ and $c$ is a valid proof for $I$}\\}$. WLOG we can assume $|I| \> |c|$ (or we can just use padding trick to ensure this), then $\mathsf{3SAT} \subseteq \operatorname{LP}(L)$. Moreover, by using different encoding alphabet for $I$ and $c$, we can ensure $\mathsf{3SAT} = \operatorname{LP}(L) \cap \Sigma^\*$ for some designed $\Sigma$. Thus if $\operatorname{LP}(L) \in \mathsf{P}$, $\mathsf{3SAT} = \operatorname{LP}(L) \cap \Sigma^\*$ is also in $\mathsf{P}$, leading to the conclusion that $\mathsf{P} = \mathsf{NP}$.

(This is the first time I answer a question here, please tell me if there are anything unclear. Thank you for tolerance!)

# Answer
> 0 votes
Big hint based on Yuvals Hint: Consider the language $\\{\langle S, f \rangle | S \text{ is a SAT formula and } f\text{ a satisfying assingment}\\} \in P$

---
Tags: complexity-theory, turing-machines, np, strings, polynomial-time
---


# Question
Title: What are the languages produced by context free-grammars with backspace?
If we add backspace to the output alphabet, are all the languages produced still context-free? (If not, then what are they?)

The word (a, b, c, Backspace, Backspace), for example, gets interpreted as a.

# Answer
The language of a finite alphabet matched with backspaces is a Dyck language (i.e. it's equivalent to balanced parenthetic expressions); one grammar for it has the productions $L\to a\_iL \text{\<BKSP\>}$ for every $a\_i\in \Sigma$, as well as $L\to\epsilon$ and $L\to LL$.

So you can take any context-free grammar and transform it into a backspace-cancel equivalent by adding $L$ and new non-terminals $A\_i$ for each $a\_i\in \Sigma$, with productions $A\_i\to a\_i L$. Then replace every use of $a\_i$ (other than in the productions for $L$) with $A\_i$. Finally, add a new start production, $S'\to L S$.

The result will not be deterministic, of course, not even using a deterministic grammar for $L$. But it's certainly context-free.
> 4 votes

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


# Question
Title: Why do we do topological sorting to find shortest or longest path in weighted DAG?
I was wondering why do we need to do the topological sort before performing relaxing of edges.

Wouldn't it'd be better if we do : if starting vertex is "s"

```
queue.add(s)
while(the queue is not empty)
 for every adjacent vertex v of u
   if( dist[v] > dist[u] + weight(u,v) )
       dist[v] = dist[u] + weight(u,v)
       add v to the queue

```

I had intentionally left out visited\[\] array

# Answer
By using this algorithm the expected time complexity would not be `O(V+E)` as we have to visit an edge multiple times.

`queue.add(s) while(the queue is not empty) for every adjacent vertex v of u if( dist[v] > dist[u] + weight(u,v) ) dist[v] = dist[u] + weight(u,v) add v to the queue`

But by using the topological sorting, we get the order in which the vertices should be traversed so that an edge is visited exactly once. So we could have guaranteed T.C. of `O(V+E)`. ###So to solve this problem to work in `O(V+E)` we use topological sort.### *But I think this is not enough, we should also know why to use Topological ordering here and so that it helps in other problems.*

##Why Topological ordering ?## Topological ordering gives us the order like `0 1 2 3 4 5` then, once we reach a node in this ordering (let's say `4`) then we've already computed the shortest path to it (`4`) as all the edges(as well as paths) of type `u -> v` (`v = 4`) and have already been visited.
> 3 votes

# Answer
Toposort also work as a visited array and prevent from getting into a cycle where every time your distance increases.

0 ---\> 2 ---\> 0

Now, you are thinking: why don't we use a visited array instead of toposort? You can't use a visited array because you don't know when your distance will increase, but using toposort you get to know which vertices will be filled first and then later on.
> 0 votes

---
Tags: graphs, dag, stacks, queues, topological-ordering
---


title: Loops running time as function of n

text:
# Question
Title: Loops running time as function of n
Suppose I have the following code and I'd like to compute running time as function of $\ n$:

```
sum = 0
i = n
while i >= 1:
    y = 1
    while y < i:
         y = y * 2
    i = i-1

```

I think the y loop is running from $\ 1 $ to $\ \lceil \log\_2(i) \rceil +1 $ and the outsider loop is from $\ n $ to $\ 1 $ so it should be something as:

$$\ \sum\_{i=1}^n \lceil \log\_2(i) \rceil + 1$$

Not sure if correct and if it is how do I show it as function of n?

# Answer
> 1 votes
I think the inner loop executes $\lceil\log\_2(i)\rceil$ times because it iterates as long as `y < i`. Hence you have $T(n) = \sum\_{i=1}^n \lceil\log\_2(i)\rceil$. Note that $ \lceil\log\_2(i)\rceil \le \log\_2(i) + 1$, therefore:

$T(n) = \sum\_{i=1}^n \lceil\log\_2(i)\rceil \le \sum\_{i=1}^n \left( \log\_2\left(i\right) + 1\right) = \sum\_{i=1}^n \log\_2(i) + n$

Now, $\sum\_{i=1}^n \log\_2(i) = \log\_2(1) + \log\_2(2) + ... + \log\_2(n) = \log\_2(n!)$ .

Finally you have $T(n) \le \log\_2(n!) + n$, which is $O(n \log n)$ see this.

# Answer
> 1 votes
An exact solution is possible.

Assuming that $n=2^m$, an exact power of $2$, the number of executions of the inner loop equals

$$0+1+2+2+3+3+3+3+\cdots \underbrace{m+m+\cdots m}\_{2^{m-1}}$$ or

$$T:=\sum\_{i=0}^mi\\,2^{i-1}.$$

Now

$$2T:=2\sum\_{i=0}^mi\\,2^{i-1}=2\sum\_{i=1}^{m+1}(i-1)2^{i-2}=\sum\_{i=1}^{m+1}(i-1)2^{i-1}=\frac12+\sum\_{i=0}^{m}(i-1)2^{i-1}+m\\,2^m$$ and finally

$$T=\frac12-\frac{2^{m+1}-1}2+m\\,2^m=(m-1)2^m+1=mn-n+1.$$

---

Now if $n$ is not a power of $2$, consider $m=\lfloor\lg n\rfloor$ and the count is

$$0+1+2+2+3+3+3+3+\cdots \underbrace{m+1+m+1+\cdots m+1}\_{n-2^{m-1}}.$$

Then

$$T= (m-1)2^m+1+(m+1)(n-2^{m-1})=mn+n-2\cdot2^{m}+1.$$

---

$\Theta(n\log n)$.

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


# Question
Title: Calculating speedup of this parallel program
I have a sequential program that has a cost of $(\sum\_{n=1}^{N} Ti )$ Where Ti is the load time of the i-th element, so if consider $Tm = max({Ti}) $ i can approximate the sequential cost as $N\*Tm$ that has a linear cost.

Let's suppose that i have c cores and i decide to parallelize this program, i can divide the loading of these items among c cores so i have (At most)

$(\sum\_{n=1}^{N/C} Ti ) \leq Tm \cdot N/C$

So in brief:

Sequential (approx.) cost: $N\*Tm$

Parallel(approx.) cost: $\[N/c\]\*Tm$

How can i calculate the speedup? what about the efficiency?

Thank you.

# Answer
> 0 votes
Kind of application you mention seems to be I/O bound i.e., application execution time is dominated by I/O time (Ti). In this case using multiple threads is not going to be advantageous as there is only **one connection** between your I/O device (permanent storage) and CPU (having multiple cores). That **one connection** is the bottleneck. You will not observe much of a speed-up as you increase the number of threads. There may be slight gain as number of threads increase initially, as threads try to saturate and use the **maximum bandwidth** possible for the I/O connection. Gain will also depend on how much time is spend on I/O and how much on processing of read data. Both of them can run in parallel for two different threads. But your question seems to suggest that I/O time (to get data) \>\> compute time (to process data). Hence there will be limited gain by increasing the number of threads. Instead, try to optimize the I/O. Keep it sequential and read in larger blocks.

# Answer
> 0 votes
It will depend on the algorithm. Some algorithms can be split between processors, some can't. For example to find the maximum of N numbers, you can split into m groups, find the maximum of each group in O (N / m) assuming m cores, and the result is the maximum in your m numbers, taking another O (m) for a total of O (N / m + m), you can probably do better if m is very large compared to N. For small-ish m, the speed up will be a bit less than m.

Other algorithms, the i-th element can only be processed after all previous elements are processed, and you can't get any speedup at all.

The other question is whether your time to process one element is the same if you use m cores. Some processors need to slow down when they get hot, so if you use 16 cores they run slower than with one core. Or you may have one set of RAM chips that cannot supply data to 16 cores at 16 times the speed. For these cases, it's best to measure the speedup.

And there is the problem that your processing resources may be limited. If you have m cores, and want to run multiple applications, one application trying to use all m cores will slow down the others. Does this happen? In these cases, are the results of your code urgent, more urgent than others? If yes, then it may be Ok to slow others down. If not then maybe not. And a speedup of m will be fine, but a speedup of log n won't.

---
Tags: parallel-computing
---


# Question
Title: Find the placement of gates on 2D points that minimizes the total distance of all paths to be made
Suppose we have a 6 vertices graph. We also have 6 gates. Each gate is attributed a path.

For example,

Gate 'A' will have to go to 'B'- 'C' - 'D' and 'E'

Gate 'B' will have to go to 'D'

Gate 'C' will have to go to 'A' and 'B'

Gate 'D' will have to go to 'E' - 'A' and 'B'

Gate 'E' will have to go to 'C' - 'E' and 'A'

Gate 'B' will have to go to 'D'

How can I find the optimal placement of the gates on the graph, such that it makes the least distance overall, computing all the paths to be made?

For 6 gates, we could search all possible placements by brute force. However, in my current project I have 42 gates to dispatch, thus it sounds too complicated to brute force.

The following is the function used to calculate the distance between the two gates (stocked in a Pandas DataFrame)

```
import math
def calculateDistance(df, gate_a, gate_b):
    coord_a = [(x, df.columns[y]) for x, y in zip(*np.where(df.values == gate_a))][0] # GET COORDINATE OF GATE_A
    coord_b = [(x, df.columns[y]) for x, y in zip(*np.where(df.values == gate_b))][0] # GET COORDINATE OF GATE_B
    y1, x1 = coord_a[0], coord_a[1]
    y2, x2 = coord_b[0], coord_b[1]
    dist = math.sqrt((((x2 - x1) * scale_x) **2)  + ( ((y2 - y1) * scale_y) **2 ))
    return dist

calculateDistance(df, "A", "C")

```

# Answer
> 2 votes
Based on the reformulation of your problem from Bernardo Subercaseaux, your problem is NP-hard (as John L explains), so you should not expect an algorithm that will be efficient in the worst case.

That said, 42 is a fairly small number, so there is some hope. I would suggest that you formulate this as an instance of integer linear programming (ILP). Add zero-or-one boolean variables $x\_{v,i}$ for each vertex $v$ (i.e., point in the plane) and each gate $i$ (i.e., each index in $\\{1,2,\dots,n\\}$), where $x\_{v,i}=1$ means that $v$ is associated with $i$. Add constraints to enforce that this is a bijective mapping, i.e., $\sum\_v x\_{v,i}=1$ for all $i$ and $\sum\_i x\_{v,i}=1$ for all $v$. Also, for each $v,w,i,j$ let $y\_{v,i,w,j} = x\_{v,i} \land x\_{w,j}$, which can be enforced using linear inequalities as explained in Express boolean logic operations in zero-one integer linear programming (ILP). Finally, you now have an objective $\Phi$ defined as

$$\Phi = \sum\_{i,j} \sum\_v \sum\_w d(v,w) y\_{v,i,w,j}$$

where $d(v,w)$ is the distance between $v$ and $w$ (a constant), and you sum over all edges $(i,j)$ that appear in the input sequences, and you sum over all possible $v$ and $w$. This objective is a linear function, so you can use an ILP solver to find the solution that minimizes $\Phi$. You'll end up with an ILP instance with several million variables and tens of millions of inequalities, which might be small enough that an off-the-shelf ILP solver can solve it to find a decent solution.

---
Tags: algorithms, graphs, optimization, euclidean-distance
---


# Question
Title: Amortized Analysis of extract-min-operation of Fibonacci Heap
I am studying the operations of the Fibonacci heap. While going through min-extraction operation every step and its complexities are fairly clear to me. In short, it is:

> The potential before extracting the minimum node is t(H) + 2m(H), and the potential afterward is at most (D(n) + 1) + 2m(H), since at most D(n) + 1 roots remain and no nodes become marked during the operation. The amortized cost is thus at most
>
> O(D(n) + t(H)) + ((D(n) + 1) + 2m(H)) - (t(H) + 2m(H))
>
> = O(D(n)) + O(t(H)) - t(H)
>
> = O(D(n))

Source: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm

I don't understand this particular line: "**since at most D(n) + 1 roots remain**" after consolidation. How do we derive this result? Can not it happen that all of the t(H)+D(n)-1 root nodes have different degrees so all of them remain?

# Answer
> 0 votes
As D(n) denotes the max degree of any node, the highest degree of any child of the deleted node can be D(n)-1, and there can be at most D(n) children of the deleted node. Now after merging all the children of the deleted node to the root list, the highest degree of any node is D(n)-1.

Now the question is, how many roots of degree D(n)-1 are there in the root list?

The fewer number of roots having a certain degree, the fewer number of linking will occur, resulting in a heap having a larger number of roots.

So there are at least D(n) roots of degree D(n)-1 in the root list (only the children of the deleted node).

To have the maximum number of roots in the resulting heap, the original heap should have all roots of distinct degrees. Moreover, the original heap shouldn't have a root with degree D(n)-1 (otherwise an additional linking will occur).

Now the CONSOLIDATE function will start linking the D(n) roots, each having degree D(n)-1. This will result in at most `floor(log(D(n)))+1` roots.

So the maximum number of roots after consolidation should be:

```
D(n)-2+floor(log(D(n)))+1
= D(n)+floor(log(D(n)))-1

```

Though I ain't sure how this is related to D(n)+1.

# Answer
> 0 votes
Pigeonhole principle: if there were more than $D(n) + 1$ roots, some roots would have the same degree and should have been merged.

---
Tags: algorithm-analysis, amortized-analysis
---


# Question
Title: Data source for Highway autonomous driving
I am working on a object detection system for autonomous driving. I have tried it in controlled environments.

I would like to try it on videos taken from a camera in front of a car running on a highway.

I have seen some of those on a course I took a year ago. My question is directed to DL practitioners. Where can I find public repositories of data of this kind?

(If this is not the site for this type of question, kindly point me where in stack exchange is more appropriate)

# Answer
I believe that something like the KITTI dataset is what you are looking for. It is a large dataset made for Autonomous Vehicle Research. You can download after providing your email.

You can also try looking at the raw KITTI data.

Here is a paper that describes the KITTI dataset in more detail.

The bdd100k dataset from Berkley is another good source of autonomous driving data. Similar to KITTI you will need to provide your email to download.
> 1 votes

---
Tags: computer-vision
---


# Question
Title: Can this algorithm for 2-dimensional points be generalized to 3 dimensions?
There is a list of 3-dimensional points $(x\_1,y\_1,z\_1),\ldots,(x\_m, y\_m,z\_m)$, where all coordinates are non-zero integers.

I would like to decide whether there exist positive real weights $w\_x, w\_y, w\_z$ such that, for all $i$ in $1,\ldots,m$, $$ (\*) ~~~~~~~~~~~~~~ w\_x x\_i + w\_y y\_i + w\_z z\_i \geq 0. $$

---

Here is an algorithm that solves a similar problem in two dimensions (i.e., assuming $z\_i=0$ for all $i$).

1. If $x\_i\<0$ and $y\_i\<0$ for some $i$, then no positive weights satisfy (\*) for this $i$; return "no".
2. If $x\_i\>0$ and $y\_i\>0$ for some $i$, then all positive weights satisfy (\*) for this $i$; remove this pair from the list.
3. In the remaining pairs, either $x\_i\>0$ and $y\_i\<0$, or $x\_i\<0$ and $y\_i\>0$. Denote the pairs of the former type by $A\_x$ and the pairs of the latter type by $A\_y$.

* For all pairs in $A\_x$, (\*) is equivalent to: $-y\_i/x\_i \leq w\_x/w\_y$;
* For all pairs in $A\_y$, (\*) is equivalent to: $-y\_i/x\_i \geq w\_x/w\_y$.

In other words, the weights $w\_x,w\_y$ satisfy (\*) if and only if their ratio $w\_x/w\_y$ is in the following range: $$ \left\[ \max\_{i\in A\_x} (-y\_i/x\_i), \ldots, \min\_{i\in A\_y} (-y\_i/x\_i) \right\] $$

If this range is empty, then return "no". Otherwise (that is, $ \max\_{i\in A\_x} (-y\_i/x\_i) \leq \min\_{i\in A\_y} (-y\_i/x\_i) $), return any weights $w\_x,w\_y$ whose ratio is in this range.

The algorithm requires O(poly(m)) arithmetic operations.

---

QUESTION: Is there an algorithm for solving the original, 3-dimensional problem, using O(poly(m)) arithmetic operations?

# Answer
> 2 votes
In general, constant-dimension LP can be solved in a strongly polynomial time.

The easiest way is just trying all vertices. A vertex is determined by $3$ half-planes (inequalities including the non-negativity constraints). Running a Gaussian elimination on a candidate set of half-planes will give a point if the half-planes are independent. Then, check the point against all inequalities.

There are at most $\binom{m + 3}{3}$ vertices, and $O(m^4)$ arithmetic operations are required.

It is possible to do it more efficiently. Randomized algorithms for LP-type\_problem run in a linear time for a fixed dimension.

# Answer
> 1 votes
It can be solved in time polynomial in the length of the input. This is an instance of linear programming, in 3 unknowns. Linear programming can be solved in polynomial time when the dimension is fixed. This doesn't answer whether or not it can be solved in O(poly(m)) arithmetic operations.

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


# Question
Title: Are there any "fast" algorithms for defragmenting memory?
This is about memory, not files or filesystems.

So in a typical process, imagine you have a string "Hello world" that later gets changed to "Hello". Or a list of 100 objects later gets reduced to 50. Or a dynamic array, or other datastructures.

This produces wasted space in memory. It's not solved with virtual memory because that's just a remapper. Memory still has to be allocated in pages, say 64 KB large, so any reduction in the size of some object, array, string, etc., will produce more wasted space than was previously there.

I tried to hunt for an algorithm for memory defragmentation but almost every result is about filesystems, not memory. I would really like to look at some and see what is their Big O notation.

Are there any memory defrag algorithms that can do it in O(n) time? What is the best one known?

Is this sort of thing just not implemented in modern OSs because of huge constant overhead?

# Answer
> 1 votes
Most memory allocators don't do memory defragmentation at the level of individual objects. Instead, when the process next allocates new objects that are the same size or smaller, the allocator will reuse the space from some previously deallocated object. (If all objects placed a single page have been deallocated, then the page can potentially be released, but many allocators don't do that; they just reuse it for future allocations.)

Pages are typically 4K bytes, not 64 KB bytes.

To do memory defragmentation in the way you are imagining, you would have to move around objects within memory, which would change the address of those objects. So, you'd have to find all references to those objects in memory and adjust the address of each reference. This is most naturally done using garbage collection. So, for languages that don't use garbage collection (like C or C++), memory defragmentation would be very difficult (basically impossible) to implement.

---
Tags: big-o-notation, memory-management
---


title: Reduce Subset-Sum to Sat

text:
# Question
Title: Reduce Subset-Sum to Sat
Is there a reduction from SUBSET-SUM to SAT? Just general SAT, not 3-SAT. Also the given multiset S only has positive integers.

SUBSET-SUM is defined as follows: Input: a multiset S = { x1 , ... , xn } of positive integers and a positive integer t Output: accept if there exists a sub-multiset { y1, …, ym } ⊆ S such that y1 + ··· + ym = t reject otherwise

x1 , ... , xn and t are encoded in binary notation.

The boolean formula SUM should be used in the reduction.

Let a1···ak, b1···bk, c1···ck be k-bit integers.

SUM(a1, ... , ak, b1, ... , bk, c1, ... , ck) is true iff (a1···ak) + (b1···bk) = c1···ck

For example, if k = 3, sum(0, 1, 1, 1, 0, 0, 1, 1, 1) is true because 011 + 100 = 111.

Can this be done?

For example, what would the boolean formula produced by the reduction look like for S = { 010, 011, 011, 100 } t = 110

# Answer
> 2 votes
I think a direct reduction can be done by the following process: setup a enable gate $e\_i$ for each integer $x\_i$ (then we can represent each bit of $x\_i$ using $e\_i$ and $0$), add all integers (with enable gate) up using adder circuits, then compare the overall sum with goal $t$. Here we obtained a circuit with $n$ inputs $e\_1, e\_2, \ldots, e\_n$, and its output is the truth value of $t = \sum\_{e\_i = 1} x\_i$, which is a CIRCUIT-SAT problem. Moreover we can convert this circuit to FORMULA-SAT, which is trivial.

# Answer
> 0 votes
The Cook-Levin theorem demonstrates a reduction from SUBSET-SUM to SAT.

If you wanted a reduction from SAT to SUBSET-SUM, then yes, such a reduction exists; SUBSET-SUM is NP-complete, and thus the existence of such a reduction follows from the definition of NP-completeness. You should be able to take any standard proof of NP-completeness for SUBSET-SUM and chain the reductions together to get the desired reduction.

---
Tags: complexity-theory, np-complete, satisfiability, subset-sum, polynomial-time-reductions
---


# Question
Title: Showing that $(b^*a)^+.(b^*a) = (b^*a)^*$
I've been learning regular expressions as part of a class on automata and formal languages. I am still fine tuning and trying to figure out the algebra and the identities.

I am struggling with the regular expression $$ (b^\*a)^+.(b^\*a) $$ It's supposed to come out as $$(b^\*a)^\*$$ I believe I have to use some identity between Kleene star and Kleene plus.

# Answer
let A=(b\* a)+ ,B=(b\* a) and C=(b\* a)\*

we have to show that whether A.B=C

here . indicates the concatenation of strings

'+' is known as Kleene plus which means all kinds of non empty strings are accepted

A.B==\>{(b*a),(b*a)(b*a),(b*a)(b*a)(b*a)…………}.(b*a) ==\>{(b*a)(b*a),(b*a)(b*a)(b*a),(b*a)(b*a)(b*a)(b*a)}----\>(1)

C on expansion gives

let e be epsilon

C={e, b*a ,(b*a)(b*a),(b*a)(b*a)(b*a),………………}---\>(2)

clearly (2) is not same as (1)

hence A.B != C ==\> (b\* a). (b\* a)= (b\* a)\* is wrong
> 0 votes

# Answer
It is the converse.

$$X^\*X=X^+.$$

(This can be taken as a definition of the Kleene plus.)
> 0 votes

---
Tags: regular-expressions, kleene-star
---


title: Existence of some search algorithms

text:
# Question
Title: Existence of some search algorithms
The lowest time complexity of search algorithms for sorted lists is $$O(n)=logn$$.

The lowest time complexity of sorting algorithms is $$O(n) = nlogn$$

So in order to be able to use a search algorithm for sorted lists we first must sort the list which takes min of $$nlogn$$ time complexity.Since the brute force search algorithm has a time complexity of just $$n$$ why bother sorting the list to figure out if a element is inside a list since $$n\<nlogn$$.What is the use of search algorithms of a sorted list?

# Answer
> 2 votes
Your reasoning is relevant: sorting a list to perform a single search would be foolish.

The general idea of search algorithms is that you spend some time preprocessing the data structure, in such a way that the cost of the subsequent searches is lowered. But of course, the total cost after the desired number of queries should not exceed the cost of the same queries without optimization.

In your example, sorting is worth the effort if you need to perform at least $\Omega(\log n)$ queries.

# Answer
> 3 votes
Naturally, if you want to check *once* whether an element is in an unsorted list, the O(n) brute force approach is the way to go, right as you say in the question.

The effect of pre-sorting the list occurs when there are *many* queries. For example, when there is an unsorted list of length $n$, and then $q$ membership checks, the brute force approach takes $O (n q)$, whereas pre-sorting and binary search take $O (n \log n + q \log n)$. When $q = 1$, it is less efficient than brute force. But when $q = n$, it is $O (n \log n)$ versus $O (n^2)$, a pretty significant difference.

---
Tags: algorithms, time-complexity, sorting, search-algorithms
---


title: A* pseudocode problem

text:
# Question
Title: A* pseudocode problem
What is the difference between this two pseudocode and which one should i implement?

```
 function A*(start,goal)
 closedset := the empty set                 % The set of nodes already evaluated.
 openset := set containing the initial node % The set of tentative nodes to be evaluated.
 g_score[start] := 0                        % Distance from start along optimal path.
 came_from := the empty map                 % The map of navigated nodes.
 h_score[start] := heuristic_estimate_of_distance(start, goal)
 f_score[start] := h_score[start]           % Estimated total distance from start to goal through y.
 while openset is not empty
     x := the node in openset having the lowest f_score[] value
     if x = goal
         return reconstruct_path(came_from,goal)
     remove x from openset
     add x to closedset
     foreach y in neighbor_nodes(x)
         if y in closedset
             continue
         tentative_g_score := g_score[x] + dist_between(x,y)

         if y not in openset
             add y to openset

             tentative_is_better := true
         elseif tentative_g_score < g_score[y]
             tentative_is_better := true
         else
             tentative_is_better := false
         if tentative_is_better = true
             came_from[y] := x
             g_score[y] := tentative_g_score
             h_score[y] := heuristic_estimate_of_distance(y, goal)
             f_score[y] := g_score[y] + h_score[y]
 return failure

 function reconstruct_path(came_from,current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from,came_from[current_node])
         return (p + current_node)
     else
         return the empty path

```

And the second one is

```
// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
// The set of discovered nodes that may need to be (re-)expanded.
// Initially, only the start node is known.
// This is usually implemented as a min-heap or priority queue rather than a hash-set.
openSet := {start}

// For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start
// to n currently known.
cameFrom := an empty map

// For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
gScore := map with default value of Infinity
gScore[start] := 0

// For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
// how cheap a path could be from start to finish if it goes through n.
fScore := map with default value of Infinity
fScore[start] := h(start)

while openSet is not empty
    // This operation can occur in O(Log(N)) time if openSet is a min-heap or a priority queue
    current := the node in openSet having the lowest fScore[] value
    if current = goal
        return reconstruct_path(cameFrom, current)

    openSet.Remove(current)
    for each neighbor of current
        // d(current,neighbor) is the weight of the edge from current to neighbor
        // tentative_gScore is the distance from start to the neighbor through current
        tentative_gScore := gScore[current] + d(current, neighbor)
        if tentative_gScore < gScore[neighbor]
            // This path to neighbor is better than any previous one. Record it!
            cameFrom[neighbor] := current
            gScore[neighbor] := tentative_gScore
            fScore[neighbor] := tentative_gScore + h(neighbor)
            if neighbor not in openSet
                openSet.add(neighbor)

// Open set is empty but goal was never reached
return failure

function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.prepend(current)
    return total_path

```

Both seem to do the same thing but the second is simpler and I don't know which one to use.

# Answer
> 1 votes
There is only 1 real difference between them, the first explicitly excludes nodes from the neighbors that have been explored already, but that is easy enough to add in the second implementation however you can guarantee that `tentative_gScore < gScore[neighbor]` will be false if `neighbor` has already been explored. Flip a coin and pick one. If you really care you can implement both and evaluate what the exact differences are between them with benchmarks and profiling.

This tends to happen quite often, there are usually more than one equivalent way to implement things like this. However the first option you pick for implementing something is often good enough.

---
Tags: algorithms, pseudocode, a-star-search
---


title: Did I invent a new data structure?

text:
# Question
Title: Did I invent a new data structure?
I needed to implement a priority queue for a project I'm working on and had this idea. In a priority queue BST implementation wouldn't it be more efficient if the poll node pointed to its parent since it's guaranteed to not have a left child? This would make polling faster since we don't have to traverse the tree to find the poll node's parent and link it with the poll node's right child. for example:

**poll():**

when we call poll() here it'll go to the poll's parent (5) and make its left child the poll's right child, and then go to the new poll node (4) and make it point to its new parent. this is an O(1) operation.

Worst case is the poll's right child has left children of its own, in which case we'll have to traverse the leftmost node in that subtree and make it point to its parent and assign it as the poll node. Now it becomes O(log(n)) but faster than regular traversal since we're not starting from the root.

**add():**

add() is similar to a regular BST except for two optimizations.

1. If the new data is lower than the poll node's data then make it the poll node's left child and have it point to its parent (old poll node) and assign the newly added node as the poll node. this is an O(1) operation.
2. If the new data is lower than the poll node's right child's data then insert starting from that subtree. This is an O(log(n)) operation but is faster since we're not starting from the root.

Other than that insert is like a normal BST.

Does this data structure make sense to use in practice?

# Answer
> 0 votes
it's a small optimization for the purpose of puling out the left most node not enough to call it a new data structure IMO.

There are is another time when this optimization is a pessimization; If the left-most node you remove doesn't have any children then it's parent must now point to its own parent. This requires a traversal from root.

Also this doesn't help in keeping the tree balanced for which you might end up traversing back up further than your discount parent pointer can get you anyway.

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


# Question
Title: Is there any mechanism where the kernel portion of an OS in memory may also be swapped?
I'm recently learning the part of *I/O buffering* of operating system and according to the book I use,

> When a user process issues an I/O request, the OS assigns a buffer in the system portion of main memory to the operation.

I understand how this method is able to avoid the swapping problem in non-buffering situation. But is it assumed that the OS buffering created for the process will never be swapped out?

To extend my question, I was wondering if there is any mechanism where the kernel portion of an OS in memory may also be swapped?

# Answer
Indeed, it wouldn't make sense to swap out an I/O buffer. The point of that buffer is that it's in RAM. The code to perform the I/O and the code to manage swap must not be swapped out either.

Other kernel code can be swapped out, in principle. However this can be problematic for several reasons. Hardware drivers that aren't involved in swap could be swapped out, but this means the kernel had to be very careful about the whole data party to swap (which may involve a disk over some external communication bus or even the network, as well as filesystem code when swapping to a file). Furthermore a lot of driver vice is very performance-sensitive: the kernel had to read it send data when the hardware is ready and may not be able to afford the time to bring vice and data back out of swap. In addition, RAM is usually assumed to be reliable (it's acceptable for the system to crash if the RAM fails), but swap (on disks or over the network) isn't, and it's difficult to design a kernel that can recover if part of it becomes unavailable. Most kernels take the simple approach and never swap out kernel code and data.
> 6 votes

# Answer
Usually pages that are used by the kernel are marked as "forced resident" or "swappable" or "cache".

Let's say the kernel uses some memory to cache the contents of a file or directory. The purpose is to avoid reading the file or directory again. Swapping this memory would be absolutely pointless. Just remember that it doesn't contain any cached data anymore. (Well, not 100% pointless for files on a very old and slow hard drive with swapping to a super fast SSD drive).

Your I/O buffers most likely must be in RAM while I/O happens, because the device performing the I/O will be set up to read from that RAM address, and cannot communicate with your OS at all. So if you swapped out the buffer, and allocated something else at that address, your hardware would happily keep reading/writing from that RAM address, creating absolute chaos.

Then there is everything that is needed to swap anything. For example the software that reads from the swap file. If that gets swapped out, you can't read it back in because you'd need to read it back in before you could use it to read it back in. Similar to leaving your car keys in your locked car. That kind of data would be "forced resident". And anything where some hardware thinks it must be in RAM would be "forced resident".
> 1 votes

---
Tags: operating-systems, memory-management
---


# Question
Title: If A is reducible to B, assuming A is hard, why can't "B is easy" update our belief to A is easy?
The concept of reducibility in computability theory is very confusing for me. For example, as described in Micheal Sipser's Introduction to the theory of computation, I understand that if language A is reducible to B, then solving A cannot be harder than solving B, or in other words, solving B gives a solution to A. Then it follows that if A is hard, then B has to also be hard.

But my confusion is: if A is some undecidable problem, e.g., the halting problem, and A is reducible to B, i.e., the solution to B can be used to solve A. Then is there absolutely no way that B can be decidable? Is there no chance that we could possibly discover/invent some smart way of deciding B that can prove that our previous understanding of A is wrong?

# Answer
> 1 votes
It cannot be true simultaneously that A is undecidable, A can be reduced to B, and B is decidable. Assume there are three "proofs" for each of these three facts, then at least one of the proofs is wrong. Actually, at least one of the three "facts" must be wrong. At this point we don't know which one. So we would probably look at the one that has been tested the least and find an error in its proof, or show that the fact is wrong.

If "A is undecidable" is a long "known" fact that everyone trusts, then people will first check whether A can indeed be reduced to B, and whether B is indeed decidable. If no fault in the proofs can be found, to the point where we are convinced they are correct, *then* we would try to find a fault in the proof of "A is undecidable". And if we can't find any fault in that proof, then we repeat, but we try harder. Or we give the problem to some better mathematicians. Or many better mathematicians.

# Answer
> 0 votes
Discovering that $B$ is decidable may mean one of two things:

1. There is an error somewhere: either in the proof of decidability of $B$, or in the proof of undecidability of $A$, or in the reduction from $A$ to $B$ (or, in an extreme case, in the very foundations of mathematics).
2. The algorithm used to decide $B$ does not conform to the usual notion of “algorithm” (i.e., it can’t be implemented on a Turing machine or any of the models equivalent to it). This is *theoretically* possible, although unexpected, if the Church-Turing thesis happens to be false.

In the latter case, I wouldn’t just say that our previous understanding of $A$ is wrong, but that *our very understanding of the notion of computation* was wrong (or, rather, incomplete). A whole class of problems (those that are reducible to $B$ but were previously thought to be undecidable) would become decidable under this new notion of algorithm. The very notion of “reduction” would change, since the newly discovered computation techniques would apply to it, too.

So, no, I’d say that the situation you propose is impossible, unless something *really* revolutionary happens.

---
Tags: complexity-theory, computability, computation-models
---


# Question
Title: Does order of elements in a set matter in Dijkstra's Algorithm?
When we use a set for doing **Dijkstra's Algorithm**, we use a pair of **{distance,node}** which we insert in a set. Most of the articles say that the first element of pair should be the distance , else we need to use a custom comparator, but why in the case of set if we use pair of **{node, distance}** the code still works. Another problem is that if we use a **set\<pair\<int,int\>\> s** or if we use a set of **set\<pair\<int,int\>, greater\<int,int\>\> s** then also the code works perfectly, so does that mean when we use a set while doing Dijkstra's algorithm the order doesn't actually matter unlike the case of using priority queue for Dijkstra's algo?

# Answer
> 1 votes
In general: yes. The correctness of Dijkstra's algorithm does depend on the order in which elements are extracted from the priority queue. You do need to extract them in non-decreasing order of their tentative distance (at extraction time).

Your particular question depends on the details of the STL library, so I'm not sure it's suited for this website.

That said, `std::set` is a *sorted* collection of elements and the default comparator for `std::set<T>` is `std::less<T>`. In your case `T` is `std::pair<int, int>` (where the first `int` is the node "name", and the second `int` is the node's tentative distance) and `std::pair`s are compared lexicographically.

Therefore you are extracting the node with the smallest "name", regardless of its current tentative distance. The resulting implementation of Dijkstra's algorithm is not correct, since you are breaking the property guaranteeing that, when you extract a node, it's current tentative distance in the algorithm coincides with the actual distance in the graph.

In fact, the algorithm fails even for unweighted undirected graphs and even if you relax distances towards nodes that have already been extracted (but do not re-add them to the set since, if you did, you'd be losing the time complexity guarantees of Dijkstra's algorithm). An an example consider the graph $(\\{0,1,2,3,4\\}, \\{ (0,1), (1,2), (2,3), (0,4), (4,2) \\})$ and source vertex $0$.

---
Tags: graphs, shortest-path, sets, priority-queues, dijkstras-algorithm
---


# Question
Title: There is a problem-name and/or algorithm for calculating functions which are constant on different intervals?
I frequently have to calculate this kind of function

Those functions have constant values on arbitrary (predefined) intervals

I wonder if there is an algorithm for fast calculation of it, so I can learn about, and implement.

My solution is to store the intervals in an interval tree, so I can find the value of the function in O(log(n)) time, by searching the interval, but I suspect that there must be faster algorithms, maybe using wavelets, truncating polynomials, data compression, enumerating combinations/permutations.

On the case when the function is monotonically increasing, the monotonicity should be exploitable.

It should be a common problem, with lots of applications, so it has to have common solutions, but I do not know where to search.

# Answer
> 2 votes
Unless your functions have very special properties known beforehand, $O(\log n)$ is optimal and achieved by dichotomic search (assuming sorted bounds).

Because in a comparison-based model, you need to find which interval contains the argument, and this takes the computation of at least $\lg n$ bits of information.

Faster can only be achieved by *computing* the interval index *from the argument value*. An obvious case is when the intervals have equal size, then the computation takes $O(1)$.

---

You could object that there could be methods working without knowing the interval index, by directly evaluating some functions for the value of the argument (in $O(1)$ ?) and combining them. But given that your piecewise constant functions have $2n$ degrees of freedom, I don't see how you could do without combining $n$ functions, implying at least $O(n)$ operations.

---

Also notice that if you need to evaluate the function at $m$ abscissas known together, you can

* sort the $m$ values in time $O(m\log m)$ or in no time if already sorted,
* merge the list of $m$ values and the $n$ interval bounds in time $O(n+m)$, which is the time to perform the $m$ function evaluations. This leads to $O\left(\dfrac nm\right)$ amortized time per evaluation.

# Answer
> 0 votes
$O(\log n)$ is very fast. I think it is unlikely that you will find a faster algorithm to compute such a function.

Wavelets, polynomials, data compression, and enumerating combinations/permutations do not seem relevant.

Such a function is called piecewise constant.

---
Tags: algorithms, efficiency
---


# Question
Title: Difference between a stochastic environment and non-deterministic environment
I have been reading AIMA by Russell and Norvig, where they talk about different types of environments an agent may encounter. Here, they have described stochastic and non-deterministic environments being different types of environments.

> One final note: our use of the word "stochastic" generally implies that uncertainty about outcomes is quantified in terms of probabilities; a **nondeterministic** environment is one in which actions are characterized by their *possible* outcomes, but no probabilities are attached to them.

I did not understand this line, taken from the book. I'm also thinking about other possible differences between these two types of environments, and their respective real-life examples. Any help is appreciated!

# Answer
A stochastic situation is like when you throw a fair coin. You know the probabilities of the outcomes. You may often assume that the distribution remains constant, let alone is known.

A non-deterministic situation is when you sit in front of a black box that may turn on a green or red light and you have no idea what will happen, but you need to be prepared to either outcomes.
> 1 votes

---
Tags: artificial-intelligence
---


title: Edit distance into a DCFL

text:
# Question
Title: Edit distance into a DCFL
I would like to generate helpful parser errors, telling the user how to fix their program.

Specifically I have a deterministic context-free language $L$, given in the form of an $LR(1)$ grammar. I have a syntactically invalid string $w$ (i.e. $w \not\in L$). I would like to find some $w^\* \in L$ which minimizes the edit distance $d(w, w^\*)$ between $w^\*$ and $w$, i.e. there is no $w' \in L$ such that $d(w, w') \< d(w, w^\*)$.

What are the state-of-the-art techniques for attacking this kind of problem? I can find shortest repairs in $O(n^3)$ time with a modified CYK algorithm for arbitrary grammars; I would like to make use of the fact that I have an LR(1) grammar to speed up the process, if possible.

# Answer
It would appear the language edit distance problem for the class of deterministic context-free languages requires cubic time.

In *Language Edit Distance Approximation via Amnesic Dynamic Programming* (Jayaram and Saha, https://rajeshjayaram.com/mainb-3.pdf), it is shown that cubic time is required for the ultralinear languages, which are exactly those recognized by some finite-turn PDA.

According to *The equivalence problem for deterministic finite-turn pushdown automata* (Valiant, https://www.sciencedirect.com/science/article/pii/S0019995874908390, either "view PDF" online or "download full issue" to use your own viewer),

> The class of finite-turn machines can be described as the intersection of the class of deterministic pushdown automata (Ginsburg and Greibach, 1966) with the class of nondeterministic finite-turn pushdown automata (Ginsburg and Spanier, 1966).

The Jayaram-Saha and Valiant papers refer to the same Ginsburg-Spanier paper (paywalled at https://epubs.siam.org/doi/10.1137/0304034), so I assume they mean the same thing.

So if cubic time is required for some (proper) subclass of deterministic languages, we cannot solve the language edit distance problem for the whole class in less than cubic time.

But we can also solve the language edit distance for arbitrary context-free languages in cubic time, so the mere fact of determinism doesn't buy us anything extra.

Disclaimer: I have not fully read the Jayaram-Saha paper. Their lower bound may be conditional on some widely-believed hypothetical lower bound.
> 1 votes

---
Tags: parsers, search-problem, edit-distance, lr-k
---


# Question
Title: Making a recursive formula for finding amount of ways to spend money on beer
So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this.

The information available is that there are $n$ different beers with different prices, the $i$th beer has a price $p\_i$. Students have $C$ amount of money

How would you make a recursive formula for the amount of ways students can spend exactly $C$ money on beer?

# Answer
> 1 votes
The $n$-the beer has price $p\_n$. You can use $k$ items of beer $n$, provided $k\cdot p\_n\le C$. The remaining money can be used for beers $1$ to $n-1$. That gives a recursive approach.

# Answer
> 0 votes
My attempt is

$$ N(C)=\left\\{ \begin{align} &0&C\<p\_{min}\\ &1&C=p\_{min}\\ &\displaystyle\sum\_i N(C-p\_i)&\text{other cases} \end{align} \right. $$

The summation part solves your problem of going through 1 to n.

Implementing this on the computer gives correct answers.

# Answer
> 0 votes
If the order matters and the $p\_k$ are distinct,

$$N(C)=\begin{cases}C=p\_1\to1\\C=p\_2\to1\\\cdots\\C=p\_n\to1\\\text{else}\to\displaystyle\sum\_{p\_k\le C}N(C-p\_k)\end{cases}$$

---
Tags: recurrence-relation, recursion
---


# Question
Title: Can all non-quantum physical systems be efficiently simulated on a classical computer?
Is it true that simulating classical physical systems is in P, i.e. can be done efficiently on Turing machines or are there known exceptions? I'm thinking of chaotic systems but I'm also curious more generally whether there are theorems or counterexamples.

# Answer
Roughly speaking, I expect the answer will be yes, this can be done efficiently, but the longer answer is that I believe it takes some care to define what you mean by simulating.

First, we must define what we mean by "classical physics". I will assume you mean (deterministic) Newtonian physics.

Second, we must define what we mean by "simulate". This is trickier than it seems, as we have to define it as an algorithmic problem. Thus, we must identify what is the input to the algorithm, and what is the desired output. A plausible first try is that the input is the state of the system at some point in time (e.g., the location and velocity of all objects), and a duration of time, and the desired output is the new state after that duration passes. However, this formulation is not solvable on a computer, because in Newtonian physics, the location of each object is a continuous real number, which cannot be represented in any finite amount of space. As a result, neither the input nor the output can be represented in finite space, so it can't be solved by any standard algorithm.

A natural way to address this is to specify the location of all objects up to a particular precision, in both the input and the output. But now this is not solvable. Knowing the original location of an object to within $\pm \epsilon$ is not enough to know its location after some time passes to within $\pm \epsilon$, because tiny changes in the original location can lead to large changes in its final location. An easy way to see this is to imagine throwing a ball aiming right at the edge of a wall. If the ball hits the wall, then it will bounce back at you. If your aim is slightly off and it misses the wall, then it will continue far past the wall. So, tiny perturbations in the input state can cause an arbitrarily large change in the output state. This means that no algorithm -- no matter how long it takes -- can accurately predict the output state, because the problem is simply information-theoretically impossible.

Perhaps this can be addressed (e.g., by giving an input state $x$, specified up to some precision $\pm \epsilon$, and asking for one possible output state that is consistent with some input state $x'$ that differs from $x$ by at most $\epsilon$), but I am not sure.

Also, you will need to ensure that the duration is specified in unary (i.e., we can build an algorithm whose running time is polynomial in the duration we want to simulate, but not one whose running time is polynomial in the log of the duration).

Finally, such a problem will not be in P, because it is not a decision problem. I do expect it can be solved in polynomial time. I don't know whether there is a precise way to formulate this problem so that there is a good definition of what it means to "simulate", but I anticipate it'll be solvable in polynomial time.

In particular, the extended Church-Turing thesis implies that yes, it is possible to simulate in polynomial time. See https://en.wikipedia.org/wiki/Church%E2%80%93Turing\_thesis#Variations.

A detail here is that many reasonable models of physics incorporate randomness (without necessarily using quantum physics). It is not known that we can simulate such randomized systems in deterministic polynomial time, i.e., in P. Instead, then, we normally indicate that they can be simulated in probabilistic polynomial time, i.e., with a polynomial-time algorithm that is allowed to use randomness. The corresponding class of decision problems is then BPP, instead of P. This may be largely a theoretical issue, as it is common to conjecture that P = BPP; but no proof of such a conjecture is known.
> 3 votes

# Answer
As far as we know, space and time are continuous and exact physical simulations are impossible.

Approximate resolution by ODE's or PDE's are in indeed in P.
> 0 votes

---
Tags: complexity-theory, complexity-classes, simulation, physics
---


# Question
Title: Are there programming languages where you import only what you need?
If all programming languages more or less compile down to the same machine code. Have there been attempts at, or is there a "field" around the concept of even more modular programming languages, where it can be built-up based on exactly what is needed? If arrays aren't handled, the language to simplify writing a program that is then compiled into machine code won't need to know what an array is. And, same with loops of different sorts, many languages have both *for*, and *while*.

I'm not a computer scientist. As a novice, there are so many different "language", but they're all mostly the same thing, and it seems like there might be a better way to organize the benefits each language gives relative to how much they actually overlap. I just watched Bjarne Stroustrup explain that C++ made managing complex data types easier, and that C should be seen as a subset of C++, but it seems like another way of doing it is to have an even more modular approach, treating the more complex abilities C++ has as modular add-ons, programs that can be imported. Since this is what is being done anyway except in a "one-size-fits-all" way. Basically, to not have a "one-size-fits-all" programming language, but construct what is needed depending on need.

If anyone understands what I'm fishing for, feel free to reply. It also seems such a language would make it easier for noobs to understand "programming languages", even if they could also have the choice to import more one-size-fits-all configuration.

# Answer
The syntactic features of computer languages only exist for the benefit of human understanding; they are abstractions that are helpful for us to conceptualize what is happening in the programs. The programs themselves are agnostic to these syntactic features and the fact that the source language uses them is not necessarily reflected in the final code. The resultant machine code doesn't care whether you used a for-loop or a while-loop; the same CPU operations may be used for both. And what is an array? For us it is a complex data-structure with many rules that we must follow in order to make it work correctly, but in the computer it is just a series of adjacent data.

To be able to add or remove syntactic features on-the-fly would make programming languages much more complex allow for more opportunity for ambiguity. Since the resultant programs aren't really changed by presence of these features, it probably isn't beneficial to have to deal with the extra complexity of allowing syntactic features to be be added or removed.

Some features that are not syntactic do have a big affect on the performance of the resultant programs. For example, the memory allocation and cleanup system used might differ from language-to-language. Some other features include runtime safety checks, like bounds-checks on arrays. A notable feature that has a significant affect on the performance of resultant code is whether the language compiles to native machine code or must be interpreted by another program in order to run.
> 3 votes

# Answer
Yes, there are minimalistic programming languages where many of the things considered "primitives" in other programming languages are built up from even simpler things.

For example, most programming languages have if-then-else, repeat-until, etc. built in.

However, assembly language, as well as a few minimalistic implementations of Forth and Lisp do not have these control structures built-in -- instead, they are built up from simpler (to the machine) primitives.

Yossi Kreinin, in "My history with Forth & stack machines", describes an implementation of Forth that doesn't even have comments built in!

Karl Lunt has a macro package that you can #INCLUDE from another PIC assembly-language file to support FOR-NEXT, SELECT-CASE, REPEAT-UNTIL, REPEAT-ALWAYS, etc. It would be pretty easy to split that up into a bunch of files, each of which implemented only one control structure, and then you could #INCLUDE only the control structures you actually use.

Assembly language even lets you custom-design new calling conventions.

People designing new instruction sets sometimes wonder about what's the minimal set of instructions that's really "necessary" -- how many different primitive instructions are necessary for a minimal instruction set computer that can do all the stuff that any other CPU can do in a "reasonable" number of primitive instructions?

Alas, trying to "simplify" the number of primitive operations to an extreme often leads to a "Turing Tarpit". Making the base language simpler by supporting very few things (so that everything else must be built up from those things) often leads to more complexity *elsewhere*. (See: "law of conservation of complexity", aka "Waterbed Theory").
> 1 votes

# Answer
Not that I know of. There's no clear value to doing that, that I can see.

Once you have a compiler that can handle all language constructs, there is no need to construct new compilers that handle only a subset of constructs. There is value to programmers of having a single language to learn, rather than many variants. And most large programs are likely to use most language constructs somewhere or other.

There is lots of work on contructing domain-specific languages (DSLs), including using functional languages like Haskell to help with that.
> 0 votes

# Answer
The problem with the idea of a modular or a-la-carte programming language (if I understand the question correctly) is that the main challenge of designing programming languages in the first place is *integrating* a wide variety of features and requirements without undue verbosity or a wild proliferation of syntactical or conceptual complexity.

It's always possible in principle to write everything from scratch in assembly language, but the volume of code that would ensue to express any given operation is itself the problem.

If a language is not already designed to provide a feature, it's very unlikely to be able to provide it without either being verbose or changing what seem to be fundamental principles.

Another thing about languages is that they are most useful when shared, and when shareable and communicable. Highly individual languages may multiply the effort of the designer, but they also require extreme design effort from the sole user. Shared languages have a community who can be engaged in design together, who can study and solve different problems with it, and devise the patterns and idioms for particular applications.
> 0 votes

# Answer
You could argue that something like Swift kind of fits into this category - because the language is actually quite small, but with a massive standard library. Not even +, -, \*, / are part of the language - the fact that they are binary or sometimes unary operators, left associative, with certain priorities is defined in the standard library (which is enough for parsing) and their implementation for many types is defined elsewhere in the standard library (so you can add int + int, or float + float). The basic types like integers, floating point, character, are all defined in the standard library.

And there are aspects of the language that allow you to write code that looks *as if* you had extended the language.

Not that you can do much of anything without pulling in most of the standard library.
> 0 votes

---
Tags: programming-languages
---


# Question
Title: Super-linear parallelism or speedup in parallel matrix multiplication algorithms
I'm reading this slides from a MIT course on parallel software performance. They introduced the concepts of Work $T\_1$, Span $T\_\infty$ and Parallelism (ratio $T\_1/T\_\infty$). What is called ''Parallelism'' here can be interpreted, according to the same authors, as *the maximum possible speedup that can be achieved on any number of processors* \[CLRS, chapter on parallel algorithms\].

Assuming an ideal machine, ignoring overheads, speedup $S\_p$ (ratio $T\_1/T\_p$) for any number of procesors $p$ is at most linear. Rare super-lineal effects can't be observed in this idealized model. This is directly expressed by the "Work Law": $ \frac{T\_1}{T\_p} \leq p$. Sometimes Parallelism is denoted by $S\_\infty$.

Now, given *any number of processors*, i suppose we can all agree Parallelism should be at most linear, because Parallelism is just in particular the maximum achievable with enough processors. However, in slides 33, 57 and 64, all the matrix parallel proposals have obscene amount of parallelism. For example, in slide 33, we have $T\_1=n^3$, $T\_\infty=\log^2 n$, and therefore $S\_\infty=\frac{n^3}{\log^2 n}$. This is way above $n$.

Also, suppose any $n$, if i give you $p=n$ processors, doesn't this mean also that $S\_p=\frac{p^3}{\log^2 p} \> p $?, which should not be possible. I feel this contradict the authors interpretation of what is or means $S\_\infty$.

At first i thought the reason is because the authors are not really using input size, i.e. $n^2$, to do the analysis but parameter $n$ instead. We could say, $N=n^2$ so $n=\sqrt{N}$, and then we actually have in terms of input size: $S\_\infty=\frac{(\sqrt{N})^3}{\log^2 (\sqrt{N})}$, but this is also super-linear.

So, now it seems i learned that ideal speedup $S\_\infty$ (aka Parallelism) is not upper bounded like $S\_p$. But somehow i feel it is just like a tricky thing coming from conflating the size of the input and the actual amount of work to do.

The question is, this matrix parallel algorithms have super-linear speedup or not?. If not, then i guess i'm misunderstanding something, but what exactly?.

# Answer
Let's start from the definitions, in order to clarify things.

The *work* of a computation executed by $p$ processors is the total number of operations performed. Ignoring the parallel overhead, the work is equal to $T\_1$ which is the time used to run the computation on a single processor.

Think about this: the work is “the total number of basic operations in the problem”, *not a parameter of the input size*. To understand why, here is an example related to your post. For a matrix problem involving $n \times n$ matrices the problem size could be $n$. But, defining the problem size like this allows the problem size itself to be interpreted differently for different problems: indeed, doubling the input size results in a eight-fold increase in serial execution time for matrix multiplication, but only a four-fold increase for matrix addition. As a consequence, the work for $n \times n$ matrix multiplication is $\Theta(n^3)$ and $\Theta(n^2)$ for addition of two $n \times n$ matrices.

The running time of a computation on $p$ processors is denoted by $T\_p$. Since a finite number $p$ of processors cannot be faster than an infinite number of processors, it follows that $T\_p \geq T\_\infty$.

Next, the *cost* of the computation is $p T\_p$; it is the total time spent by all of the processors. Of course, the cost is always at least the work: since $p$ processors can perform at most $p$ operations in parallel, it follows that $p T\_p \geq T\_1$.

The *span* (also known as *depth* or *critical path length*) of the computation is the length of the longest series of operations that have to be performed sequentially owing to dependencies. The span is denoted by $T\_\infty$ and is defined as the time spent computing using an idealized machine with an infinite number of processors. Your goal as a designer of parallel algorithms actually is to minimize the span,since it determines the shortest possible parallel execution time.

The *parallelism* represents the maximum possible speedup on any number of processor. It is defined as the ratio $\frac{T\_1}{T\_\infty}$.

Finally, the *speedup* on $p$ processors is the ratio $\frac{T\_1}{T\_p}$. Of course, it is not possible to achieve $T\_P \> \frac{T\_1}{p}$: that would mean that we did not all of the work of the parallel computation. Moreover, it's also impossible to achieve $T\_P \> T\_\infty$, we do not have an infinite number of processors really available. The best we can aim for, asymptotically, is $T\_p = O(\frac{T\_1}{p} + T\_\infty)$.

It is worth recalling here immediately that the idealized machine equipped with an infinite number of processors is just a useful abstraction. Of course, we do not have parallel supercomputers with an infinite number of processors (or cores of executions). The main insight here is that one should try to use the maximum possible number of processors that a parallel algorithm can gainfully use, but not more. Indeed, there is an optimal number of processors for each parallel computation, and trying to add additional processors not does not help, and, instead, results in worst performances. The optimal number of processors depends on the span. In turn, minimizing the span may not be easy: even assuming an infinite number of processors, there are temporal dependences that can not be avoided in some parallel computations, and these dependences will harm the performances since some of the processors will have to wait. This is because, informally speaking, time-like variables and related computations can not be parallelized (only space-like variables and computations can).

Now think about an *embarrasingly parallel computation*, i.e., a sequential computation which is made of a number $x$ of units to be computed, and each of the units can be computed in parallel by a different processor without requiring any kind of interaction. The span for this parallel computation actually is $O(1)$ so that the corresponding parallelism equals the work $T\_1$. This is the best we can hope for, and is actually realized for embarrasingly parallel computation. For general parallel computations, instead we have $T\_\infty \leq T\_p \leq T\_1$ and the speedup is usually not so great. Brent's theorem states that

$T\_p \leq T\_\infty + \frac{T\_1-T\_\infty}{p}$ or, alternatively,

$\frac{T\_1}{p} \leq T\_p \leq \frac{T\_1}{p} + T\_\infty$.

In practice, the maximum number of processors that can be gainfully used depends on the specific parallel computation, in particular on its work: one can at most assign a unit of work to a processor. If we use more, the remaining processors will be idle (they will not have anything to do) and the performances will therefore decrease. This is a theoretical upper bound, matched by embarrassingly parallel computation.

In your matrix multiplication example, you are therefore incorrect when you state that the problem size is $n$ or $n^2$. As shown, it is actually $n^3$, since this is the number of scalar multiplications required to compute the $n^2$ entries of the matrix product (assuming the ordinary sequential matrix multiplication algorithm). And yes, by using $n^3$ processors one can compute the matrix product as in the DNS (Dekel, Nassimi and Aahni) Algorithm in time $T\_p = O(\lg n)$ (this results can be even made cost-optimal by using $O(n^3/\lg n)$ processors). Of course, this is only of theoretical importance and useless in practice, owing to the huge number of processor required: even multiplying two "small" matrices of order $n = 1000000$ is impossible, the number one supercomputer on the top500 list has not that many cores of execution. In practice, we solve the problem by *scaling down* the processors, i.e., by using $p \<\< n^3$ processors. Anyway, by using the DNS algorithm you obtain an even better parallelism, namely $S\_\infty = \frac{n^3}{\lg n}$.

At the end, hopefully it should be clear that in your example there is no superlinear speedup phenomenon: it is forbidden by the theory and the analysis does not contradict the theory, since the ratio $S\_\infty = \frac{n^3}{\lg^2 n}$ does not involve $p$ and refers to an infinite number of processors. The problem is that you can not simply put $p = n$ and simultaneously maintain the *same* meaning of the ratio. To preserve the exact meaning, you must use the true problem size, i.e., you need to put $p = n^3$. But then, the ratio becomes $\frac{p}{\lg ^{2} \sqrt\[3\]{p}}=O\left(\frac{p}{\lg ^{2} p}\right)$ which, definitely, is not superlinear.
> 1 votes

# Answer
The speedup cannot be superlinear in the number of processors (because a single processor can always simulate $p$ of them with no loss of efficiency). As said by @Dmitry, $S\_\infty$ corresponds to an infinity of processors so there is no contradiction.

Now you are trying to generalize

$$S\_\infty=\frac{n^3}{\log^2n}$$ to $$S\_p=\frac{p^3}{\log^2p}$$ when $p=n$. But this does not work because $p=n\ne\infty$.
> 2 votes

# Answer
When you multiply two n x n matrices using the naive algorithm, your problem size is not n, but n^2. The number of operations is not n, but n^3.

Unless someone is more clever than I am, an infinite number of processors could calculate the product in time O (log n), since you need to add sums of n numbers and you do that by adding n/2 pairs, then n/4 sums, and so on. So the maximum speedup is n^3 / log n. The speedup is always less than the number of operations, but that number is not n. (An interesting problem: How many processors do you need to calculate the product in 2 log n steps or 3 log n steps? Should be closer to n^3 / log n than to n^3).

PS. A typical hardware multiplier on a modern processor will get the maximum speedup, doing n^2 operations in O (log n), using O(n^2) tiny processors, but limited to n ≤ 64.

PS. Sometimes the algorithm with the highest speedup for an infinite number of processors will do substantially more operations, but arranged cleverly. This might not be the best algorithm for small numbers of processors. I might have an algorithm A calculating a result with p processors using n^2 operations with a speedup of p, and an algorithm B using n^3 operations with a speedup of p^2.5. A will be faster if p \< n^1.5.
> 1 votes

---
Tags: parallel-computing, performance, matrix-multiplication
---


title: Does NP ⊆ Co-NP imply NP = Co-NP?

text:
# Question
Title: Does NP ⊆ Co-NP imply NP = Co-NP?
Does NP ⊆ Co-NP imply NP = Co-NP?

And also, does Co-NP ⊆ NP imply NP = Co-NP?

And does either statement imply P = NP?

Thank you very much in advance.

# Answer
> 0 votes
$L \in Co-NP$

$=\> \overline{L} \in NP $

$=\> \overline{L} \in Co-NP $

$=\> L \in NP $

$=\> Co-NP ⊆ NP $

$=\> NP = Co-NP $

---
Tags: complexity-theory
---


# Question
Title: How is slope error calculated for Bresenham’s Algorithm for both 2D and 3D?
I've been working with Bresenham’s Algorithm in 2D and understand it is derived from the following logic:

y = mx+c

To get the slope error at a given point, the following equation is used:

d2 is the distance from value Y to the whole integer above. d1 is the distance from value Y to the whole integer below.

d1 - d2 = \[m(xₖ+1)+c - yₖ\]-\[yₖ+1-m(xₖ+1)+c\]

* If d1 - d2 \< 0, the next pixel should be (xₖ+1, yₖ)
* If d1 - d2 \>= 0, then the next pixel should be (xₖ+1, yₖ+1)

This gets turned into and reduce to the following equation to remove the m variable.:

Pk = 2∆y(xₖ) - 2∆x(yₖ) + 2∆y + 2∆xc - ∆x

The initial value of the error is:

c = y1 - (∆y/∆x)\*x₁

With the loops step increasing this decision value by:

The actual value of next is calculated by plugging in (xₖ+1, yₖ+1) and (xₖ+1, yₖ) and subtracting Pknext - Pk. If this value is less than zero, we choose (xₖ+1, yₖ).

When (xₖ+1, yₖ+1) and (xₖ+1, yₖ) are plugged into Pknext, they end up simplifying to 2(∆y-∆x) and 2∆y.

This simplifies this logic into:

```
Constraints
x₁ < x₂
y₁ < yx₂
∆y/∆x ≤ 1
Given x₁, y₁, x₂, y₂
∆x = x₂ - x₁
∆y = y₂ - y₁
P = 2∆y - ∆x # Inital Decision value
while x ≤ x₂
    x = x+1
    IF P  < 0
        Plot(x,y)
        P  = P + 2∆y # Decision value of East
    ELSE
        Plot(x,y+1)
        P  = P + 2∆y - 2∆x # Decision value of North East

```

How is this logic applied in 3D?

I found this article by geeks for geeks: https://www.geeksforgeeks.org/bresenhams-algorithm-for-3-d-line-drawing/

But it never explained how the math is derived. We can get the value of Y by simply using mx+b and calculating the decision variable from there, but how is the decision variable done in 3D?

# Answer
I will first explain a closely related line drawing algorithm in 2D.

The parametric equation of a continuous line can be written vectorially

```
P = P0 + t.∆P

```

where `t` runs from `0` to `1`.

If we want to discretize in such a way that the pixels are contiguous, the increment of `t` must be the smallest of `1/∆x` and `1/∆y`, let `1/∆`, and we compute the points

```
Pi = P0 + i.∆P/∆.

```

Assuming that `∆=∆x`, this is

```
Pix = P0x + i
Piy = P0y + i.∆y/∆x.

```

(`i` runs from `0` to `∆x`)

For efficiency, the division of `i.∆y` by `∆x` can be done incrementally by keeping the quotient and the remainder (`i.∆y = q.∆x + r`); for a new `i`, we add `∆y` to the remainder and if it exceeds `∆x`, we fix by subtracting `∆x` and incrementing the quotient. This explains the if statement in Bresenham, which chooses between a lateral (east) or diagonal (north-east) move.

```
x+= 1 // East
r+= ∆y
if r ≥ ∆x
    r-= ∆x; y+= 1 // North

```

---

Now the generalization to 3D is immediate: choose `∆ = max(∆x, ∆y, ∆z)` and, assuming `∆=∆x`,

```
Pix = P0x + i
Piy = P0y + i.∆y/∆x
Piz = P0z + i.∆z/∆x.

```

---

A complete discussion must involve the signs of the deltas.
> 1 votes

---
Tags: algorithms, computer-graphics
---


# Question
Title: Unpacking the notion of "hardest instances" for NP-complete problems
Suppose, for the sake of argument, that it was proved that $P \not= NP$. Then, this would imply that for every $NP$-complete problem, there is a "hardest instance" of the problem that cannot be solved in polynomiall time. Then, if $P$ were to not equal $NP$, what properties would be known about the hardest instances of $NP$-complete problems?

In particular, my question is:

> If $H$ is the set of all hardest instances of some $NP$-complete problem (take subset-sum for instance), thereby not solvable in polynomial time, then do we know if $H$ would contain both "yes" and "no" instances of the problem, or only "yes" or only "no" instances? (By "yes" instance I mean the answer to the decision problem is "yes"; i.e., "yes, there is a subset of some integer set that sums to a target value").

My gut tells me the set of all hardest instances of a problem must contain at least one "yes" instance, and not necessarily a "no" instance, but I do not have a proof and am wondering if someone has one.

My general thought for a proof of why there must be "yes" instances in the hardest set is as follows:

> Suppose, for the sake of contradiction, that the set of problems that no algorithm could solve in polynomial time are all "no" instances. Then this implies there is an algorithm that can solve all "yes" instances in polynomial time, and hence for parameter $n$ is gauranteed to halt after $n^d$ iterations, where $d$ is a fixed positive integer. But then this implies that if the algorithm does not return "yes" after $n^d$ iterations, then it knows it must be a "no" instance, and hence returns "no" in polynomial time ($n^d$ iterations). But then this is an algorithm solving *all* instances of the problem in polynomial time, a contradiction.

# Answer
> 8 votes
> This would imply that for every NP-complete problem, there is a "hardest instance" of the problem that cannot be solved in polynomiall time.

No. This is incorrect. For every single instance, there is a polynomial-time algorithm that solves that instance correctly. The algorithm can hardcode a check to check for that one instance and output a hardcoded answer (the correct solution).

As this also shows, the notion of "hardest instance" is not well-defined. So, your proposal that we define $H$ to be the set of hardest instances is not well-defined. The set $H$ is not well-defined, because there is no sensible definition of what it means for a single instance to be a hardest instance.

This means that your question is not answerable because it is not meaningful/well-posed.

---

For any set of instances, if the set contains only "yes" instances it can be solved in polynomial time (simply use an algorithm that ignores its output and always outputs "yes"). Similarly, any set that contains only "no" instances can be solved in polynomial time. So, if you have a set that is not solvable in polynomial time, then it must contain both yes instances and no instances. In fact, it must contain infinitely many yes instances and infinitely many no instances.

---
Tags: complexity-theory, np-complete, decision-problem, p-vs-np
---


# Question
Title: prove that the unique language $A$ such that $AB$ is context free for all languages B is the empty set
> Prove that the unique language $A\subseteq \Sigma^\*$ such that $AB$ is context free for all languages $\subseteq \Sigma^\*$ is the empty set.

If $A$ is not the empty set, there should be a way to construct a language $B$ so that $AB$ is not context-free. I'm not sure how to generalize this for arbitrary nonempty languages $A$ however. The language $\\{0^n 1^n 0^n : n\in\mathbb{N}\\}$ is known to be non-context-free. Also, removing finitely many strings from a non-context-free language results in a non-context free language.

> Edit: perhaps modifying the language given will work.

# Answer
> 1 votes
If $AB$ is context-free, so should be the set of all its suffixes. Those include the suffixes of $B$, and if $B$ is complicated enough prefixing $A$ does not change the complexity of the set of suffixes.

Your solution $B = \\{0^n1^n0^n \mid \dots \\}$ seems to work, but if $A$ ends in $0^\*$ the reasoning becomes a little complicated. I would suggest $B' = \\{10^n1^n0^n \mid \dots \\}$.

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


# Question
Title: Is there a way to find the fixed size subsequence sum in an N by M array that is the closest to a given N-dimensional vector?
Basically, I need to solve the multivariate case of the "closest subsequence sum to a given value K" problem, which is solved with dynamic programming as far as I understand. Let's say I have M rows of integer data.

```
A = [
[a11, a12, .., a1n],
...
[ai1, ai2, .., ain],
...
[am1, am2, .., amn]
]

```

And I have a target vector K: `K = [k1, .., kn]`

In other words, I need to approximately solve the following system of linear equations:

```
w1*a11 + .. + wm*am1 = k1
...
w1*a1n + .. + wm*amn = kn

```

Where `w1..wn` can only assume values on 0 and 1, so it feels like a case of diophantine equations of sorts. I can't quite come up with a solution yet.

Another constraint is to have the closest subsequence of a fixed size, i.e. `w1+ ... + wm = S`. For example, I have 10000 rows and I want to find the 300 rows the sum of which will give me something close to my target vector K.

# Answer
This can be formulated as an instance of the closest vector problem in a lattice.

In particular, replace the vector $(a\_{i1},\dots,a\_{in})$ with the vector $(a\_{i1},\dots,a\_{in},c,0,0,\dots,K,0,\dots,0)$, where the $K$ is in the $i$th position, $K$ is a large constant, and $c$ is a small constant. Let the target vector be $(k\_1,\dots,k\_n,cS,0,0,\dots,0)$. Now look for the closest vector to the target, in the lattice spanned by the other vectors.

There are a number of algorithms for the closest vector problem, including using LLL lattice reduction to get an approximate solution.
> 0 votes

---
Tags: dynamic-programming, linear-algebra, diophantine-equation
---


title: Finding articulation points

text:
# Question
Title: Finding articulation points
I have learnt about both articulation points and bridges and I have understood the algorithm used to find the number of bridges in O(n) time which is Tarjan's algorithm. But now, can I simply say that the vertices connecting the bridges are the articulation points with the additional condition that they should have degree\>1? I tried drawing several graphs and in all of them, I found this to be true. So is this or is this not true?

# Answer
> 0 votes
Yes, an endpoint of a bridge is an articulation point iff it has degree \> 1.

Be careful, however. There could be articulation points that are not endpoints of any bridge. For example, the red vertex in the graph below is an articulations point. However, there is no bridge in the graph.

The graph above was drawn by user sorry.

An efficient algorithm that finds all articulation points is presented here on Wikipedia and here on GeeksforGeeks.

---
Tags: algorithms, graphs
---


# Question
Title: The relationship between a perfect binary tree and a complete & full binary tree
I am reading the book "*Cracking the coding interview*". In Chapter 4 they cover basic tree concepts.

It says there that a complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right. Thus, the following binary tree is complete:

```
         1
     2       3
   4   5   6

```

A full binary tree is a binary tree in which every node has either zero or two children. This is clear and self-explanatory.

Now, a perfect binary tree is the one that is both full and complete. It is said that in a perfect binary tree all leaf nodes will be at the same level, and this level has the maximum number of nodes.

However, the following binary is full and complete (according to the given definition), but it does not have all of the levels completely filled:

```
         1
     2       3
   4   5

```

Can someone experienced in this terminology clarify this point? It looks like a mistake in the definition.

# Answer
> 2 votes
Here is the relevant text on that book, sixth edition.

> Perfect Binary Trees
>
> A perfect binary tree is one that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes.

As you have observed, the statements quoted above is somewhat ambiguous and confusing if not downright wrong. While a perfect binary must be a full and complete binary tree, a full and complete binary tree is not necessarily a perfect binary tree.

The definition of a perfect binary tree can be any one of the following.

* A perfect binary tree is a full and complete binary tree where all leaf nodes are at the same level, and this level has the maximum number of nodes.
* A perfect binary tree is a complete binary tree where all leaf nodes are at the same level, and this level has the maximum number of nodes.
* A perfect binary tree is a binary tree where every level is fully filled.
* A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level. (This definition comes from Wikipedia).
* A perfect binary tree is a binary tree of level $k$ and $2^k-1$ nodes for some positive integer $k$. (Or non-negative integer $k$ if a binary tree is allowed to have no nodes.)

---
Tags: terminology, trees, binary-trees
---


# Question
Title: Argument for an $\epsilon$ free LL(1) grammar being in LR(0)?
I am trying to understand the reason as given in this answer

> If an ε-free grammar is not LR(0), then there is some state with both a shift and a reduce action. Since the grammar is ε-free, that state was reached by way of a shift or a goto. The previous state must then have had two different productions with the same FIRST set, contradicting the LL(1) condition.

I don't understand why the previous state would have two different productions with the same FIRST set. Also why would it be a shift-reduce error? Why can't it be reduce-reduce?

Here's what I figured out. The right-hand side of the two items that cause the shift-reduce or reduce-reduce error, would have a series of common terms. That would necessarily imply that

1. The two non-terminals have the same FIRST, if the RHS of the two items are the same.
2. That some non-terminal is left recursive. If the RHS of one item is part of the RHS of the other item.

Both of these would imply that the grammar is not LL(1)? Is that correct?

# Answer
> 0 votes
If $A\to\epsilon ~or~ A\to.$ is the only $\epsilon$-production in $I\_0$ state creates always shift-reduce conflict because $A\to\epsilon ~or~ A\to.$ is already reduced in $I\_0$ state and any production like $A\to.a$ in $I\_0$ creates shift-reduce conflict in initial state $I\_0.$

If more than one $\epsilon$-production $(~like~ B\to\epsilon ~or~ B\to.)$ is present in $I\_0$ state then you get redce-reduce conflict because they are already reduced in one state.

---
Tags: parsers, lr-k
---


title: Do one way function exist?

text:
# Question
Title: Do one way function exist?
I was recently going through the Wiki page List of unsolved Problems in Computer Science.

There was a problem which I do not understand

> Do one-way functions exist ? \[Is public-key cryptography possible ?\]

A *one-way function* is a function that is easy to compute on every input, but hard to invert given the image of a random input.

A one-way function that comes to mind is a *Cryptographic hash function* which is used to create message digests. Where size of the message digest is relatively small as compared to the size of the message and hence it becomes very hard to reconstruct message from the message digest.

So, why does the above problem say that these functions do not exist?

# Answer
> 8 votes
No known cryptographic hash functions are provably secure. It might seem to be hard to reconstruct an input hashing to a given hash value, but we can't prove that it is indeed very hard. We can just say that no one was able to find an algorithm accomplishing that so far, but there is no guarantee that tomorrow such an algorithm won't be found.

In cryptography there is a very exact definition of one-way functions, which implies, among else, that P$\neq$NP. While there are several specific functions which are conjectured to satisfy the definition, no one knows how to prove this. We don't even know how to prove that one-way functions exist assuming P$\neq$NP.

# Answer
> 0 votes
Your question is a loaded question. The example of the message digest doesn't prove that these functions do not exist. It only proves that there is no discernable system key from which to construct the entire message from the message digest. For example consider a system that uses check digits for license plates or social security numbers to eliminate errors or fake plates.

or suppose the message digest was the number "1" and the whole message was a larger three digit number, let's say "247"... We could get there by...

1 2 {1} 3 2 {2} 4 {3} 7 247 or a SS# with a check-digit of "0" might be recreated or confirmed possibly real... 0
11 00,11,22,33,44,55,66,77,88,99 choose 1 101
1001 32221 413134 1541251 23843501 4 {2} 6 {3} 9… etc. 469158334 the final level check

238458334 next level 4 {2} 6 {3} 9 {8} 1 {4} 5 {3} 8 {5} 3 {0} 3 {1} 4
469158334

---
Tags: cryptography, one-way-functions
---


# Question
Title: Checking for equality before calculating product of a matrix with inverse of another matrix
I have an operation that is performed many times and is thus performance sensitive where I need to calculate product of a matrix and inverse of a matrix as below. Both matrices are 4x4 and consist of floats.

```
 M3 = Inverse(M1)*M2

```

Now in this specific scenario M1 and M2 very often equal each other. Let's say 75% of the time the two matrices are equal. I'm wondering if it would be cost-effective to then compare the two matrices for equality (equal within a given epsilon because of floating point inaccuracy), and assign `M3` identity matrix if the two are equal?

Calculating an inverse is very expensive so would it make sense to do matrix comparisons which only mean 16 comparisons and 16 subtractions?

# Answer
Yes, your optimization is worthwhile.

If the cost of performing the inversion and multiplication is $c\_\times$ and the cost of comparing the two matrices is $c\_=$, then the expected cost of your optimization is $c\_= + 0.25 c\_\times$, whereas the cost of always multiplying is $c\_\times$. We can then use simple algebra to identify the condition under which your optimization is better. In particular, your optimization is better if $c\_= + 0.25 c\_\times \le c\_\times$, which happens if $c\_= \le 0.75 c\_\times$. So, if you benchmark the cost of multiplication and the cost of checking equality, you will be able to determine whether this condition holds.

In practice, testing two matrices for inequality is far faster than inverting and multiplying two matrices, so in practice the condition will surely hold, and your optimization will be worthwhile.
> 1 votes

---
Tags: linear-algebra
---


# Question
Title: construct language in ${\sf BPP \backslash (RP \cup coRP)}$ assuming $\sf RP \neq ZPP$
### Problem

This is a HW problem from CMU 15-455 (hw10, p1(a)), spring 17 by Ryan O'Donnell.

Assume $L \in {\sf RP \backslash ZPP}$. Define $$ L' = \left\\{ (x, y) : \text{either $x \in L$ and $y \notin L$, or vice versa} \right\\}, $$ Prove that $L' \notin {\sf RP} \cap {\sf coRP}$.

### My Thoughts

The path of this proof is clear: show that $L' \in {\sf RP}$ (or ${\sf coRP}$) implies $L \in {\sf coRP}$, thus $L \in {\sf ZPP}$, contradicts the assumption. Here I consider to prove $L' \in {\sf RP} \implies L \in {\sf coRP}$ first, but the following points give a conclusion that stuck me:

1. I don't know any property/information about the language $L$ itself, only a checker $A$ is given.
2. To exploit checker $B$ of $L'$, two different strings are needed. Pairs of identical strings like $(x, x)$ are not in $L'$ thus will always be rejected, gives no information b/c rejection by $B$ can stand for both valid and invalid, although error probability can be arbitrarily small (but never be 0).
3. If I want to ensure $x \notin L$ with no error, I must choose a string $y \in L$ since only acceptance by $B$ is "absolutely correct". But how can I find such $y$ in such a way that can work for every possible $L$ and for every time it runs?
4. If I look for a random string $y$ from the street, the probability of success depends on $|L \cap \Sigma^n|$, but it's unknown.

Here the only way I can imagine is to "pre-calculate" such string $y \in L$, then $L' \in {\sf RP} \implies L \in {\sf coRP}$ follows directly. But how can I sure that such $y$ can always be found, within an acceptable time complexity? I'm not sure about this point, so I asked the question How to decide complexity affected by 'magic number'? It seems that this is an acceptable solution, but I'm not sure still. So I ask this question here, and I hope you you can point out some elegant solutions that I haven't found. Thanks!

# Answer
To show $L'\notin \mathsf{RP \cup coRP}$ you can essentially follow the proof of $\mathsf{ZPP=RP\cap coRP}$.

Since $L\neq \Sigma^\*,\varnothing$ (otherwise it's in ZPP), there exist $y\_1\in L, y\_2\notin L$. Note that you don't have to find $y\_1,y\_2$ at runtime, as you can simply hardcode them into your machine for $L'$. If $L'\in RP$, then you can simultaneously run $M\_L(x)$ and $M\_{L'}(x,y\_1)$ where $M\_L,M\_{L'}$ are the RP machines for $L,L'$ correspondingly. If $L'\in coRP$ then you can simultaneously run $M\_L(x), M\_{\overline{L'}}\left(x,y\_2\right)$.
> 0 votes

---
Tags: complexity-theory, time-complexity, complexity-classes, randomness
---


# Question
Title: Expected value of Markov chain after nth steps
A Markov chain $\\{ X\_n, n \geqslant 0\\}$ with states 0, 1, 2 has the transition probability matrix $$P= \begin{bmatrix} \frac12 & \frac13 & \frac16 \\ 0 & \frac12 & \frac23 \\ \frac12 & 0 & \frac12 \end{bmatrix}$$

If $P\\{X\_0 =0 \\} = P\\{X\_0=1\\}=\frac14$ find $E\[X\_3\]$

How to answer this question?

# Answer
$E\[X\_3\] = 0\cdot P(X\_3=0) + 1\cdot P(X\_3=1) + 2\cdot P(X\_3=2)$ Hence $$E\[X\_3\]= \frac14 P^3\_{01} + \frac14P^3\_{11} + \frac12P^3\_{21} + 2\left\[ \frac14P^3\_{02} +\frac14P^3\_{12} + \frac12P^3\_{22}\right\]$$
> 1 votes

---
Tags: probability-theory, markov-chains
---


# Question
Title: P vs. NP problem and understanding "worst case complexity"
Suppose that $P \not= NP$. Then my understanding is not all instances of NP-complete problems can be *solved* in polynomial time. That is for every NP-complete problem, there are a colleciton of instances of that problem where the solution (correct certificate) cannot be determined in polynomial time (I do not mean that there is no algorithm that solves it in polynomial time, like the algorithm that just hard codes the instance and knows the correct certificate).

Is what I have said here correct? If not, what exactly does "worst case complexity" when $P \not= NP$ mean, if it does not mean there are instances of NP-complete problems that no algorithm can find a solution (correct certificate to) in polynomial time?

# Answer
> 1 votes
What you wrote isn't clear. This is a problem with using English to try to summarize mathematics: it is easy to write an English sentence that is ambiguous.

If you mean "there is a set of instances, such that there is no single algorithm that solves every instance in that set correctly", then the answer is: correct. The language itself (i.e., the set of all instances of the problem) is such a set.

If you mean "there is a set of instances, such that for every instance in that set, there is no algorithm that solves that instance correctly", then the answer is: incorrect. For every instance, there exists an algorithm that solves that one instance correctly.

---

You appear to be trying to draw some distinction between "can be determined in polynomial time" and "there is an algorithm that solves it in polynomial time", but there is no such distinction. The notion of "can be determined in polynomial time" is vague, but to the extent that it has any precise meaning, the only meaning I can imagine is that there exists an algorithm that can solve it in polynomial time.

---

Consider the following analogy. For every number, there exists a larger number. But there is no largest number (there is no number, such that every number is larger than it). The order of quantifiers matters.

---

May I suggest some quality time with a complexity theory textbook, and perhaps on discrete math and proofs?

---
Tags: complexity-theory, time-complexity, p-vs-np
---


title: Landau Notation/Big O notation

text:
# Question
Title: Landau Notation/Big O notation
In our class the following exercises/examples were given:

Compute/find $n\_0$ and c from the formal definition of each Landau symbol to show that:

$n^{2/3} \in \Omega(log^8(n))$.

Then in the Solution the following was done:

$n\_0=1$ and $c=(\frac{1}{12})^8$.

Show: for each $n\>n\_0: n^{2/3} \ge c \cdot log^8(n)$.

$n^{2/3}=(n^{\frac 1 {12}})^8$.

Then: $c \cdot log^n=log^8(n^{\frac {1}{12}})$

And because in general: $m\ge log(m)$,that implies $m^8\ge log^8(m)$.

The 2nd example was this:

$2^{100}n \in O(n^2)$

Then in the Solution the following was done:

$n\_0=2^{100}$ and $c=1$.

Show for each $n\>n\_0: 2^{100}\*n\le n^2$

It is true that: $n\_0^2=2^{100}n\_0 $ and for all $n\>2^{100}: n^2-2^{100}n\>n^2 -n \cdot n=n^2 - n^2=0$.

The thing I am the most interested in these two examples is not the solution as much as it is how exactly we evaluate $n\_0$ and $c$. I have the following question:

1. We are looking for $n\_0$ and c, but somehow we give values to them? And why those values in particular? Why can't n\_0=2? and c=34 (for the first example, or even the second)? Is there a logic behind all of this? In the class it wasn't explained, as two why we take the values that we take. I'd like to have a fundamental understanding of the problem, so that then I can be able to find a case by case solution.

I just want to mention also, that I am fully aware of the big-O and big-$\Omega$ notation (small-o and small-$\omega$ and $\theta$ as well).

# Answer
> 1 votes
If you want to show that $f(n) \in \Omega(g(n))$ then you are free to choose $n\_0$ and $c$ as long as $\forall n \ge n\_0$, $f(n) \ge c \cdot g(n)$ (Reverse the inequality for big-oh.) There is no particular reason to chose one set of values over another, except that you can sometimes make the math easier if you choose wisely.

That said, $n\_0 = 2$ and $c=34$ doesn't work in the first example since, for $n=2$:\* $$ n^{2/3} = 2^{2/3} \< 34 \cdot 1^{8} = 34 \cdot (\log 2)^8 = c \log^8 n. $$

It also doesn't work in the second example since, for $n=2$:\* $$ 2^{100} \cdot n = 2^{100} \cdot 2 = 2^{101} \> 136 = 34 \cdot 2^2 = c \cdot n^2. $$

* This still doesn't work if you require $n \> n\_0$ since you can choose, e.g., $n=3$.

---
Tags: algorithms, big-o-notation
---