# Question
Title: NPDA which accepts all the strings of a's and b's that have equal number of a's and b's, but do not end up with an a
I have to design an NPDA(Non-Deterministic Push Down Automata) for all the strings over $\\{a, b \\}^\*$, which have equal numbers of $a$'s and $b$'s but do not end up with an $a$.

I know how we should create an NPDA for the strings with an equal number of $a$'s and $b$'s, which its machine would be like this:

But I don't know how to add this condition to it, that it must not end up with an $a$. My idea was to a union between $2$ languages for this question.

First, all the languages which have an equal number of $a$' and $b$'s, end up with an $a$.

Second, all the languages which have an equal number of $a$'s and $b$'s, end up with a $b$. My main problem is working with my stack, and handling its contents on the edges.

How can I add this condition on the last symbol of an input?

# Answer
A simple mental model of a PDA or NPDA is **a finite state machine plus a stack**.

Both parts can be used to remember which kind has been the input taken by the automaton so far. The finite-state-machine part can remember bounded-many information. The stack can remember unbounded-many information (but for any particular moment, it is only readable/changeable at the very top).

When there is some information that cannot be remembered by the stack easily, **the finite-state-machine part can help remember**.

---

The transitions of the wanted NPDA can be as simple as the following.

\# $q\_1$ is the initial state. $Z$ denotes the bottom of the stack.
\# When next input is $a$, the state becomes $q\_a$. The subscript "${\\,}\_a$" in state "$q\_a$" means the last input symbol was an $a$.
$q\_1, a,Z\to q\_a, aZ$
$q\_1, a, a\to q\_a, aa$
$q\_a, a, a\to q\_a, aa$
$q\_1, a, b\to q\_a, \lambda$
$q\_a, a, b\to q\_a, \lambda$

\# When next input is $b$, the state becomes $q\_1$. So $q\_1$ implies the last input symbol was not an $a$. $q\_1, b,Z\to q\_1, bZ$
$q\_1, b, b\to q\_1, bb$
$q\_a, b, b\to q\_1, bb$
$q\_1, b, a\to q\_1, \lambda$
$q\_a, b, a\to q\_1, \lambda$

\# Only at state $q\_1$, the NPDA may transition to accept.
$q\_a, \lambda, Z\to q\_f, Z$
> 2 votes

---
Tags: pushdown-automata
---


# Question
Title: Why do we still use a Von Neumann Architecture in modern computers?
The Von Neumann architecture was first created in the mid 40s for use in a computing system known as ENIAC for research into the feasibility of thermonuclear weapons.

To this day the Von Neumann architeture is still primary foundation in the majority of modern computers. I have listened to a few historians and scientists mention that there is likely more efficient architectures and that Von Neumann himself didn't believe in its universal capability(unfortunately cannot remember enough to find a link).

So why do we still use this architecture in the majority of modern computing?

# Answer
> So why do we still use this architecture in the majority of modern computing?

## The assumption itself, first clause: Modern Computer \<= Von Neumann

Firstly, do note that **the Von Neumann architecture is not used *exclusively***: almost any current "Von Neumann" machine except for very small microcontrollers (which are occasionally Harvard machines) features several important extensions to the original architecture, from DMA to MMUs.

Specialized coprocessors are very popular - most notably, GPUs.

Those work very well *in conjunction to* a Von Neumann machine.

## The assumption itself, second clause: Von Neumann \<= Modern Computers

**The limitations of the Von Neumann architecture and the *need* for non-Von Neumann architectures for certain applications is well recognized** in the scientific community, most importantly whenever "\[general\] artificial intelligence" of interest, see for example this very recent paper, which continues the line of work started by Carver Mead, who envisioned one of the most radical departures from "classical" architectures in 1989, in the form of analog, time-continuous, highly parallel "neuromorphic" chips.

Your premise is thus, in a way, flawed, unless it is implied that you're referring purely to industrial applications (read on for that part).

## On the notion of efficiency

Note that Mead himself had envisioned his architecture as **complementary** to a traditional Von Neumann machine.

Why?

This brings us to another important point: you mention "more efficient architectures", but **efficient for *which sort of workload?***

Sontag and Siegelmann have famously proved that a feed forward neural network is Turing-complete, as is, of course, the Von Neumann architecture, and if we accept Church's thesis (which has never been seriously challenged in quite a while) that this amounts to the ability to compute all computable functions, they're *theoretically* interchangeable and unsurpassed in their abilities.

However, leaving aside for a moment the issue of *practicality*, they are not as efficient for the same applications.

I'm guessing that a neuromorphic chip such as Carver Mead's would make for a *terrible* Excel machine.

## So why *mostly* Von Neumann in industrial applications?

But yes: even if research *has* branched in other directions and has gotten to the status of prototypes and early industrial devices **Von Neumann architectures are still the bread and butter of industrial applications** (and a good foundation to extend with coprocessors and specialized optimizations).

It's safe to assume that the reason is **practical**:

1. They're **universal** -- i.e. "good enough" in the broadest possible sense: they are Turing complete and sufficiently close to some theoretical models such as the TM itself or the URM; it is safe to assume that the ubiquity of the Von Neumann machine has influenced developement of theory as well.
2. They're tolerably **easy to reason about** and very well understood by engineers and developers
3. They work very well for **existing industrial workloads that drive the demand for hardware R&D**; there is 60 years' worth of algorithms and software for Von Neumann machines.

## Von Neumann closed under copper cable?

Finally - and only partly tongue-in-cheek: do note that it is *very easy* to obtain a decidedly non-Von Neumann machine from off-the-shelf parts: just buy two laptops and connect them with an UTP cable and you have a very strange machine where you don't have uniform, synchronized access to a single mutable storage or a single clock.
> 7 votes

# Answer
A competing architecture needs to tick these boxes reasonably well:

### Doing stuff we want

Nobody will use it unless *nearly all* features available in popular high-level languages are supported reasonably efficiently. You can check out this paper with a provocative title: The von Neumann Architecture Is Due for Retirement. It outlines a lot of the challenges in departing from an architecture with a linear addressed memory. In particular:

> ... dynamic data structures cannot be efficiently represented in the basic dataflow model, and neither can dynamic behaviour, such as function calls, function pointers, code-as-data, and pass-by-reference. Previous attempts to overcome these limitations typically involved assuming a shared global memory and either adding `load` and `store` instructions or introducing other primitives which took advantage of the global memory (such as I-structures)

### Letting engineers get things done

The von Neumann architecture very easily (compared to other models) allows for:

* single-stepping through code
* profiling code
* graceful exception handling
* implementing compilers
* limiting compute/memory resources (i.e. CPU time and memory usage)
* intuitiveness for programmers (step-by-step is about as simple as it gets)

Another important feature is reasoning about execution time, however the von Neumann architecture doesn't make this so easy anymore. In the past it did, but now this is thwarted due to deeeep cache hierarchies, parallel processing, swap space, and various forms of optimisation. Nonetheless, sequential code and dead-simple calculation of memory usage still go a long way which is why we learn Big-O analysis.

The von Neumann model also makes it reasonably easy (in theory) for hardware designers to build CPUs, memories, and the links between them. (In practice, today the more powerful CPUs analyse sequential instructions to build a dependency graph, basically a dataflow graph, funnily enough.)

### Chicken and Egg (aka Inertia problem)

Companies won't invest billions developing new hardware if users won't flock to it. And they won't flock to it if they can't use their existing software on it. (The only reason ARM is so common on mobile platforms is because people were quite happy to only use software that they hadn't used before.)

If you look at the Intel 64-bit instruction set, it is riddled with stuff from the 16- and 32-bit days. (In fact you can run practically any software from the DOS days on a modern processor.) It will not be so easy for a radically different hardware architecture to be backwards-compatible.

The only realistic way for a competing architecture to become mainstream is if it is *really* good in some niche (like say physics simulations) and as it gains traction more and more is spent on improving its performance and generality until it starts to move to a wider domain. In a sense this is exactly what happened with graphics cards, but they are still just a glorified multiprocessor von Neumann architecture.
> 2 votes

# Answer
Hardware can be directly memory mapped as long as it obeys the logic voltage and current rules of the system and worked on live with an interpreted language such as FORTH. I have had new chips up and running in 15 minutes using a 68HC11 running FORTH and debug problems on wireless systems half a world away on the same system running the FORTH interpreter on the what remained in SRAM when a C program crashed.

Many if not most things in industry can be done using a network of simple computers that work in low latency real-time with Unix or Linux box all disk I/O, time synchronization, serving up any complex work that's needed, etc.
> 1 votes

# Answer
It's been a few years since this question, but even at the time that the question was written, we don't. As several commenters point out, the overwhelming majority of CPUs that you can buy today use a Harvard architecture, with separate instruction and data memory.

This is true from microcontrollers, which typically have read-only instruction memories implemented with flash, through to high-performance CPUs, which use a modified Harvard architecture implemented with split instruction and data caches. It is especially true of GPUs, coprocessors, and other asymmetric multiprocessors.

But general-purpose CPUs still try to maintain the illusion of a von Neumann architecture under some circumstances. Intel still has a requirement to support self-modifying code, which seems silly in the 21st century, until you realise that this is still occasionally used to support debuggers.
> 1 votes

# Answer
Just an example - Volta GPU has 5120 so-called cores. Most modern CPUs has an out-of-order execution. Any modern processor has a lot of built-in caches. Do you still consider that as von-Neumann architectures?
> -1 votes

---
Tags: computer-architecture, memory-hardware
---


title: What order B-tree is this?

text:
# Question
Title: What order B-tree is this?
I am studying B-trees and reading *Introduction to Algorithms* by Cormen et al.

Unfortunately, they have this diagram Figure 18.1 and they do not list the order of the tree.

I understand that for a B-tree of order $m$, the tree has 5 properties:

1. Every node has at most $m$ children.
2. Every internal node except the root has at least $\left\lceil \frac{m}{2}\right \rceil$ children.
3. Every non-leaf node has at least two children.
4. All leaves appear on the same level and carry no information.
5. A non-leaf node with $k$ children contains $k−1$ keys.

Based on this however, I wasn't sure if you could just tell the order of a given tree. To me, it seems this looks like it could be order 4,5, or 6. By the $\left\lceil \frac{m}{2}\right \rceil$ criteria, 6 would be the most since 6/2 = 3 and therefore anything larger would automatically mean that this criteria wouldn't be satisfied for the node with keys D,H.

Is the order of a B-tree unique? If so, what is the order of this B-tree?

# Answer
> 1 votes
Good question.

You have given the answer. A B-tree of order $4$ can also be a B-tree of order $5$ or $6$. So, "the order" of a B-tree may not be unique.

Knuth, who gave the definition of B-tree as in the question, avoids the problem of non-uniqueness by defining the order to be the maximum number of children of a node, which is one more than the maximum number of keys. \[1\]

So, according to Knuth, the order of the B-tree in the question is $4$.

\[1\] Knuth, Donald (1998), *Sorting and Searching*, *The Art of Computer Programming*, vol. 3 (Second ed.), Addison-Wesley, ISBN 0-201-89685-0. Section 6.2.4: Multiway Trees, pp. 481–491.

---
Tags: notation, b-tree
---


# Question
Title: Calculate the area of the shape created by multiple paths
I'm trying to write an algorithm to calculate the area created by multiple paths that can be overlapping or not. Here is an example:

**Basics**

* 4 separate paths (A,B,C,D) which are a collection of vertices (A1,A2,...)
* Area desired is represented by green

**Edge Cases**

* As shown with B, a path might have segments that don't contribute to a filled shape
* As shown with C, a path might be completely enclosed by other paths and therefore should basically be ignored.
* As shown with D, paths may create independent shapes
* As shown with A and B, it should be a union of all the shapes

My first question is if an algorithm for this already exists. If it does, it would save me a lot of effort :). I tried searching around but I don't even know how to describe this problem concisely.

Assuming one doesn't exist for this exact purpose I have to move on to figuring it out myself. I'm assuming the right data structure for the job is a graph. I'm thinking I will add points for each intersection (highlighted in red) as I insert paths into the graph.

Then "all I need" is an algorithm for tracing around the outside of each shape because calculating the area of those irregular polygons will be simple. Does something like that already exist? My primary hangups when I think about how to do this are:

* What vertex do I "start" at?
* How do I account for multiple shapes (D as well as A,B,C)?
* How do I account for the parts of shapes like formed by A1,A5,A5 where I'll be visiting that intersection point multiple times?

I'm not necessarily looking for a complete solution, I'd love thoughts on if you think I'm approaching this the best way so far and if you have any ideas/suggestions on how to achieve this.

Thanks in advance!

# Answer
> 1 votes
With the help from some of the hints on this post and elsewhere, I came up with a solution.

### The Data Structure

The data structure is relatively simple. It is a collection of *Nodes* that are connected by *Edges*.

Each node stores the coordinates of where it lies in space and each segment is represented by two directional edges, one in each direction. Each intersection of line segments is broken up with a new Node. Note the coordinates of the intersections are left off the diagram but are included in the data structure.

### The Algorithm

**Find All Cycles**

* 1. Pick any edge and choose the next edge that is closest to clockwise from the edge you entered the node on.
* 2. Record whether the angle between the connecting edges is a reflex angle (\> 180 degrees) or not.
* 3. Record the series of nodes visited
* 4. Mark the edge as *used*
* 5. Follow that new edge to the next node and repeat until reaching the first node again.

At the end, the cycle will have the points that it is composed of and a count of reflex and non-reflex angles. If there are more reflex angles, it is considered to be an *outside* cycle and is thrown out. Otherwise, it is included in a preliminary list of polygons to include in the final result.

Repeat this cycle finding process until every edge has been used.

**Filter Polygons**

Filter out any resulting polygons that are entirely inside another. This can be done by testing only the first point of one polygon to see if it's inside another. That's because we know we will never have any intersecting polygons.

**Calculate the Area of Each Remaining Polygon**

At this point, we just need to calculate the area of each polygon and add them together for our solution.

### Some Details

It's important to note that in the case where we get to a node and the only remaining edge is the returning edge, it counts as a 360 degree angle and therefore a reflex angle.

Also, it's important to note that each angle of each cycle must be counted towards the reflex and non-reflex count, including the first and last. Otherwise, a plus sign arrangement of simple paths (+) will result in a valid polygon.

### Example

All of the cycles from my original example are represented here:

For more information on my process and a walk through of the algorithm, you can see my case study.

# Answer
> 0 votes
If the polygons are overlapping, you can't spare a union algorithm that will "merge" the overlaps. https://en.wikipedia.org/wiki/Boolean\_operations\_on\_polygons. This involves the detection of intersections between the sides and a topological reorganization. Nothing really easy.

It is likely that an simpler technique is possible if you consider decomposing the domain in slices defined by horizontal lines though all vertices (this takes a sort on the vertex ordinates). Also consider the lines through the intersections. These can be obtained by a standard line intersection algorithm (https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann\_algorithm). Then the problem reduces to the union of trapezia in every slice, with no intersecting sides. It is easy to merge two overlapping trapezia into one.

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


# Question
Title: Is there an edge whose removal will extend the shortest path? - graph problem
Given an undirected and unweighted graph $G = (V, E)$ and two of its vertices $s$ and $t$. My task is to find an algorithm that checks if there exists an edge belonging to $E$ such that its removal will result in the shortest path from $s$ to $t$ being extended (and if so returns this edge). We may remove only one edge.

In practice, a graph is given as a list of lists. The $i$-th list contains the numbers of vertices adjacent to the $i$-th vertex (numbered from 0).

Example:
$G = \[ \[1,2\], \[0,2\], \[0,1\] \]$
$s = 0$
$t = 2$

The answer is an edge terminated by vertices 0 and 2 - the shortest path has been extended from 1 to 2.

How can this problem be solved in optimal time?

All I know is that the best way to find the shortest path in a basic graph like this is to just use BFS, and I guess I have to use it somehow here as well, but otherwise I have no idea how to approach this...

# Answer
#### the Idea

Find all edges that are on one of the shortest paths from $s$ to $t$. Find the bridges in the graph that consists of those edges.

#### the Approach

1. Use breadth-first-search to compute $d\_s(u)$, the distance from $s$ to $u$ for each vertex $u$. If $t$ is found not reachable from $s$, return nothing.
2. Ditto for $d\_t(v)$.
3. Collect all edges $(u,v)$ such that $d\_s(u) + d\_t(v) = d\_s(t)-1$ as graph $S$.
4. Try running a linear algorithm that finds all bridges in $S$ such as this one. As soon as one bridge has been found, return it.
5. Return nothing.

An algorithm that implements the approach above runs in linear time.
> 2 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Decision tree for searching element in sorted-array
Given the problem of having a **sorted array** $A$, an element $x$ to be searched for in the array $ A $, what is a lower-bound on the process of finding $x$ in $A$?

The answer is $ \Omega(\log n) $ because I was told that $ n $ is the number of leaves in the decision tree and so $ \log n $ will be the height of the tree.

First, without being aware of the fact that we are talking about a sorted array, I drew the tree for performing sequential-search on $A$,

But I got a height of $n$ and not $ \log n $.

Next, noticing the given array is sorted, I thought about drawing a decision tree for binary-search algorithm and I found the following link that draws the tree as I wanted, http://bcs.whfreeman.com/webpub/mathematics/gersting7e/chapter%206/section6-3/problem1/Page7.htm

( Here's an image in case you can't enter the link: )

But my teacher-assistant told me that when we want to show a lower-bound on process, we can show it by drawing a decision-tree for any algorithm that solves the process and not just a specific one. Meaning that we want to bound the decision tree's height for any algorithm that solves the specific problem.

That means, I was wrong in my analysis of having drawn both decision trees since I referred to two specific algorithms ( sequential search and binary search ) that solve the problem and not a general algorithm.

**Question:** So I wanted to know, how can one draw a decision tree for an arbitrary algorithm that solves the problem of finding $x$ in a sorted array $A$? ( It seems to me that the tree will be extremely algorithm dependent like in the two cases I've brought above and so I'm unable to seeing other wisely how the decision tree can be generalized not for specific algorithms )

**Note:** The question Doubt in the correctness of decision tree models for constructing a lower bound is similar to mine but not exactly what I asked for since I want to know how the decision tree should look like for any algorithm that solves the described problem.

Thanks in advance for help!

# Answer
You haven't really defined your computation model, so here is a suggestion.

The input to the algorithm is a sorted array $A$ of length $n$ and an element $x$.

The output is either a position $i$ such that $A\[i\] = x$, or $\bot$, which means that $x$ is not in the array.

An algorithm is a decision tree whose leaves are labeled by outputs, and whose interior nodes are labelled by indices $i \in \\{1,\ldots,n\\}$, and have three children labeled $A\[i\] \< x$, $A\[i\] = x$, $A\[i\] \> x$.

An algorithm is legal if for any sorted array $A$ and for any $x$, if we traverse the decision tree then we get the correct answer (this can be formalized more carefully).

The *running time* of the algorithm is the depth of the decision tree (maximal number of edges in any root-to-leaf path).

Every legal algorithm has at least $n + 1$ different leaves, since for any array $A$ whose elements are distinct, we can find $n+1$ inputs for which the only correct outputs are $1,\ldots,n,\bot$.

Since every internal node has fan-out $3$, a decision tree of depth $d$ has at most $3^d$ leaves. Since $3^d \geq n + 1$, we conclude that $d \geq \log\_3 (n+1)$.

This is achieved by binary search, up to a constant factor. With more work, we can show that binary search (probably defined) is strictly optimal. This requires an adversary argument.
> 2 votes

# Answer
The lower bound can be found as the minimum height of a binary tree holding $n$ leaves. A *complete tree* has this property and has a logarithmic height.
> 0 votes

---
Tags: algorithms, trees, search-algorithms, decision-tree
---


# Question
Title: Show that $\{ a^c \mid c \text{ is composite}\}$ is not regular using Dirichlet's theorem
> Let $L=\\{ a^c \mid c \text{ is composite} \\}$. Prove that $L$ is not regular using the pumping lemma. You can use Dirichlet's theorem, which states that if $(a,b) = 1$ then there are infinitely many prime numbers of the form $an+b$.

I am thinking about this question for a lot of days and I don't find it trivial, do you have any hints to give me about how to start the proof? please, I can see the connection between the pumping lemma and Dirichlet's theorem but I don't know how this is helping me, because the pumping lemma talks about a Periodicity, and Dirichlet's theorem talks about prime numbers and not composite so I will need to use the Complementary group

# Answer
Suppose towards a contradiction that $L$ is regular and let $p$ be a prime number larger than $L$'s pumping length. Since $a^{p^2} \in L$, by the pumping lemma we know that there is some $1 \le k \< p$ such that $a^{ki+p^2} \in L$ for all $i \ge -1$.

Since $k$ cannot have $p$ as a prime factor, $k$ and $p^2$ must be coprime and Dirichlet's theorem guantees the existence of some $n$ such that $kn+p^2$ is prime. The contradiction follows by choosing $i=n$.

If we replace "regular" by "context-free", the proof above shows $L$ is not context-free.
> 3 votes

# Answer
Let p be a prime. Since there are infinitely many primes, p is followed by n composite numbers for some n dependent on p, and then by another prime q.

After processing $a^p$ you are in a state S that is rejecting. In that state, if you process further a's, then the next n states are accepting, and the state after that is rejecting.

If the prime p is followed by n composite numbers and another prime q, and the prime p' ≠ p is followed by n' composite numbers and another prime q', and n ≠ n', then after accepting $c^p$ and $c^{p'}$ you must be in different states S and S', because in one state processing n+1 c's puts you back into a rejecting state for the first time, and in the other state you switch to a rejecting state either earlier (if n' \< n) or later (if n' \> n).

Gaps between primes get arbitrary large, therefore the numbers n' get arbitrary large, therefore there must be an infinite number of different state. Therefore there is no finite state machine for your language.

Sorry, no pumping lemma and no Dirichlet's theorem used.

PS. The same argument can be used for the language $c^n$ where n is / is not element of an infinite set with arbitrary large gaps between elements. For example $n = \lfloor p \log p \rfloor$ for some prime p, or $n = k!$ for some integer k.
> 1 votes

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


# Question
Title: equivalency of some facts in $O$ notation
I misunderstanding about some logarithm property in algorithm course:

is it correct that we say following three term is equivalent?

$O(\log a + \log b)$

$O(\log (ab))$

$O(\log (a+b))$

# Answer
Let $a\>b\>0$. From $\log(a+b)=\log(a)+\log\left(1+\dfrac ba\right)$, we draw

$$\log(a)\le\log(a+b)\le \log(a)+\log(2)$$ and similarly for $b\>a$.
> 2 votes

---
Tags: algorithms, time-complexity, data-structures, asymptotics, discrete-mathematics
---


# Question
Title: Find matrix local minimum - two analysis which seem to get contradictory runtimes
Suppose you have an $n\times n$ matrix and you want to find a local minimum. To find it you scan the middle row and column and identify a minimum. If it is a local minimum, you're done; if not, you recursively search the sub-quadrant where the smaller value was found.

Now I can analyze the runtime in two different ways. In the first analysis, I can count up how many cells of the matrix the algorithm will use: $2n + n + n/2 + ... + 1$ in the worst case, which has growth $\Theta(n\lg n)$.

In the second analysis, I point out that recursively, $T(n)=T(n/2)+cn$. By the Master Theorem this has runtime $O(n)$.

I can't see any way to reconcile these two analyses.

# Answer
> 2 votes
In the first analysis note that,

$T(n) = 2n + n + \frac n 2 + \frac n 4 +... + \frac n {2^{\lg n}} \leq n (2+1+\frac 1 2 + \frac 1 4 +... ) \leq 4n =O(n) $

---
Tags: algorithms, algorithm-analysis, master-theorem
---


# Question
Title: Structural induction proof for reverse(push(as, bs)) = push(reverse(bs), reverse(as))
I need to prove:

```
reverse(push(as,bs)) = push(reverse(bs), reverse(as))

```

where:

```
def push[T](as: List[T], bs: List[T]):
  List [T] = as match {
      case Nil => bs
      case x::xs => x::push(xs, bs)
  }

def reverse[T](ls: List[T]):
  List[T] = ls match {
     case Nil => Nil
     case x::xs => push(reverse(xs), x::Nil)
  }

```

I am already stuck in the base case, since i cant figure out a lemma. The only thing I have this far is:

```
reverse(push(Nil,bs)) = reverse(bs)

```

and I'm stuck here since it felt eternity.

Does anyone have an idea for a lemma?

# Answer
> 1 votes
I think what would help a lot is proving first that `push(push(a, b), c) = push(a, push(b, c))`.

Once you have that result, you can make an induction on `as` only in the equality `reverse(push(as,bs)) = push(reverse(bs), reverse(as))`.

I will add some details if necessary.

---
Tags: programming-languages, induction, tail-recursion
---


# Question
Title: What does :: indicate in all-quantifier predicates?
Can somebody explain to me the meaning of $::$ in the following predicate?

$$(\forall i : P(i) : Q(i)) \equiv (\forall i :: P(i) \implies Q(i))$$

# Answer
> 2 votes
"::" is ":" followed by another ":", i.e., two separators.

"$\forall i :: P(i) \implies Q(i)$" is the same as "$\forall i : : P(i) \implies Q(i)$", i.e, there is no premise/second term. Or you can consider the second term as $\text{true}$ or $\top$.

This situation is similar to the slice notation for lists in Python. For a list `A`, all four notations `A[::3]`, `A[0::3]`, `A[:len(A):3]` and `A[0:len(A):3]` mean the same thing.

---
Tags: logic, first-order-logic, notation
---


# Question
Title: How to come up with combination a short-circuit evaluation table?
(a || b) || (c && d))

Given the above, how do I derive the table below:

| a | b | c | d | output |
| --- | --- | --- | --- | --- |
| T | - | - | - | TRUE |
| F | T | - | - | TRUE |
| F | F | T | T | TRUE |
| F | F | T | F | FALSE |
| F | F | F | - | FALSE |

I'm told that this is short circuit evaluation, basically, we take away some branches/paths that always lead to false or true so we don't waste time going through them. As a result we have lowered the number of conditions here greatly.

However, my brain just can't figure out how to do this. Apparently this is done via a decision tree.

Can somebody help me figure out the process?

# Answer
> 1 votes
Looking at your question again, I think you really may only need two simple rules. After reviewing these rules, then we can see how to build a table. Note that I will write

$$(a || b) = (a \lor b)$$ $$(a \\&\\& b) = (a \land b)$$

---

When you have logical or equations:

$$\tag{1}(a \lor b)$$

You should know that if one of these is true, then the whole function is true. So your table would be:

| a | b | output |
| --- | --- | --- |
| T | - | TRUE |
| F | T | TRUE |
| F | F | FALSE |

...In other words, you start with a value that leads to something true. So start with $a$ being true, and that gives the first line. Then, for the second line, assume $a$ is now false, and then $b$ must be true to give a true output. Finally, if both of these are false, then the output must be false since neither $a$ nor $b$ are true.

---

$$\tag{2}(a \land b)$$

You should know that this can be true only if both are true.

| a | b | output |
| --- | --- | --- |
| T | T | TRUE |
| F | T | FALSE |
| F | F | FALSE |

I left that one go for you to figure out. Essentially, if either of the outputs is false, then $(a \land b)$ is false.

---

Now to combine the results...

Start with the outermost parenthesis. If you have your function, which is $((a \lor b) \lor (c \land d))$, you look at the parenthesis. You have $f \lor g$, with

$$f = (a \lor b)$$ $$g = (c \land d)$$

Now you know that the function can be true if either $f$ is true or $g$ is true. We don't have to fill anything in the table yet, but this gives us the order of things and what we need. In other words, start with making $f$ true. Then $f$ false and $g$ true. Then finally both false.

So your table groups $a$ and $b$ together as $f$, and $c$ and $d$ together as $g$. Then the table will look like:

| a | b | c | d | output | parenthesis group |
| --- | --- | --- | --- | --- | --- |
| T | - | - | - | TRUE | f TRUE |
| F | T | - | - | TRUE | f TRUE |
| F | F | T | T | TRUE | f FALSE, g TRUE |
| F | F | T | F | FALSE | f FALSE, g FALSE |
| F | F | F | - | FALSE | f FALSE, g FALSE |

So what I've tried to show is that after you've figured out what the outermost parenthesis does, you go through that in order. Then you break apart the innermost functions and go through them in order.

---
Tags: logic, boolean-algebra, decision-tree
---


# Question
Title: optimal search algorithm for finding parameters and thresholds
I have the following problem:

There are $n$ variables $x\_i$, $i=1...n$, each can take integer values from 1 to $m$. For every set of values I can run a test which has a binary outcome ('Pass' or 'Fail'), and it is known that the test outcome only depends on a value of a single variable being larger than some threshold. That is, the outcome is 'Pass' if $x\_k \ge c$ and 'Fail' if $x\_k \< c$. My goal is to find $k$ and $c$ (i.e. which variable is causing the failure and what is the threshold).

My thinking so far is as follows: if I know $k$ and only need to find $c$, than I can do a binary search and find the threshold in $\log\_2 m$ steps. If I know $c$ and don't know $k$, I can similarly find it in $\log\_2 n$ steps (by setting half of the variables to a value above the threshold and the other half to a value below, thus excluding half of the possibilities, etc.).

I can also first find $c$ in a similar way using a binary search, each time setting all the variables to the same value, and afterwards find $k$ as before. This will take a total of $\log\_2 m + \log\_2 n = \log\_2 nm$ steps.

It seems however that this might not be the optimal approach. So my question is: *Is there an algorithm that can find the answer in less than $\log\_2 nm$ steps ?*

(also, if someone has a suggestion for improving the title of this question, that would be welcome)

# Answer
No, it's not possible to use fewer steps than that. Each test gives you one bit of information about the solution. There are $nm$ possible solutions, so you need $\lg(nm)$ bits of information to uniquely identify the solution -- which means you need at least $\lg(nm)$ tests.
> 2 votes

---
Tags: algorithms, search-algorithms, search-problem, binary-search
---


# Question
Title: Graph find all vertices that are part of a cycle
I was wondering how I can find all the vertices in a graph that are part of a cycle. To determine this for one vertex, I could just start a DFS from that vertex, but this seems unefficient to me when I want to know for all vertices.

Thanks for your help!

# Answer
> 3 votes
There is a duplicate question in StackOverflow. I quote the highest voted answer from Craig Gidney here.

> What you want to do is remove all of the Bridges (i.e. edges that disconnect a component when removed). The Wikipedia article gives a linear time algorithm for finding all of the bridges.
>
> Once all the bridges are gone, each node is either isolated (has degree 0) or is part of a cycle. Throw out the lonely nodes, and what's left is the nodes you want.

# Answer
> 1 votes
I just had an exam. There is the same question, we being ask to find all vertex that not part of cycle.

The function is like this (In C)

```
void HasCycle(int hasCycle[], int size, Graph g);

```

In my function, I use

1. An array to track **visit status**(Using hasCycle provided).

Then I will run DFS on the vertex has not being vsisited, and in each DFS search I kept the following

1. An array to track **parent**. For example, I visit 3 through edge 5-\>3, I will put parent\[3\] = 5.
2. An array to track **backedge**. The authentic way should be using a timeStamp, this can be found in CLRS, chapter discuss Graph DFS search. I used color. At begin of loop, I color the vertex and at the end, I decolor the vertex so that it can be visited for multiple times. And by this, each time I have a edge conenct two colored node, means there is a back edge.
3. A 2-D matrix, that track the **status of edge**. Idea is once DFS used the edge, it will be marked so won't do DFS again through that edge. In this way DFS can visit same node for several times but can't using same edge. At the end, I want to achieve, node can be visited several times but have to through different edge.

So that in the end. The time complexity will be O(V^2), for each DFS I run, it will versify the cycle in that connected component. And I will only run DFS if I havn't visit that node in previous DFS.

I am unable to proof the correctness of this algorithm. I did pass the autotest in the exam. So if there is some problem you spotted, just point it out.

---
Tags: algorithms, graphs
---


# Question
Title: Averege time complexity of open addressing
I get that it depends from the number of probes, so by how many times the hash code has to be recalculeted, and that in the best case there will only be one computation of the hash code and the complexity will be O(1) and that in the worst case the hash code will be calculated a number of times equal to the size of the hash table and the complexity will be O(n).

But what about the averege case, what would be the asymptotic notation of insert and search operations in open addressing? when solving the collisions with double hashing for example.

# Answer
Define the *load factor* of a hash table with open addressing to be $n/m$, where $n$ is the number of elements in the hash table and $m$ is the number of slots. It can be shown that the expected time for doing an insert operation is $\frac{1}{1-\alpha}$, where $\alpha$ is the load factor. If $\alpha$ is bounded to some constant less than $1$, then the expected time for an insert operation is $O(1)$.

The gist of the intuition for this result can be obtained by looking at geometric random variables. If $p$ is the probability of success in a Bernoulli trial, then the expected number of trials for the first success is $1/p$. In a hash table with open addressing, a slot that is being probed can be empty or occupied, where "empty" denotes success and "occupied" denotes failure. The success probability is the probability a slot is empty, which is $p=1-\alpha$, and so we have the desired result that the expected number of slots probed before reaching an empty slot is $\frac{1}{1-\alpha}$.

More specifically, in open addressing, if the probe sequence is completely random (i.e. all $m!$ probe sequences are equally likely) then the probability that the first slot is occupied is the failure probability $\alpha$. The probability that the first two slots being probed are both occupied is at most $\alpha^2$ (I say “at most”, not “exactly”, because if the first slot is occupied, then the probability the second slot is also occupied is smaller than $\alpha$ when the second slot is different from the first slot). You can work out these details, and we essentially get the result above, assuming completely random probe sequences.
> 1 votes

# Answer
Implementations will typically store the hash value inside the table - this will save lots of hash value calculations.

For the hash value of the key being looked up, it depends on the caller how often that value is calculated. Hash values can be cached. I might have an object with a name, address, and age. And name objects and address objects that cache their hash value, and the hash value of my complete object is calculated from the three hash values of name, address and age. In that case the second call to calculate the hash value of the same object will be quite fast. So the cost of calculating hash codes is very highly variable.

Consider this: Your implementation calculates one hashcode, then determines one or more slots where an item with this hashcode could be stored. Then every time a slot is filled you need to check first if the hash code matches, then if the item matches. The check for matching hash codes is trivial if the hashcode is stored in the table. The cost for comparing items can be high. You will have one successful comparison during a lookup or delete of an existing item, independent of load factor. You may have 0 or more unsuccessful comparisons during any operation, depending on the load factor, but with a good hash function this should happen almost never.

So assuming that calculating hash codes and comparing items are expensive, the other cost is likely quite trivial. (Why would they be expensive? For example strings are most likely Unicode strings, and Unicode strings with different representations can be equal, so comparison and calculating the hash code are not trivial. )
> 0 votes

---
Tags: time-complexity, hash, hash-tables
---


# Question
Title: Undecidability in optimal data compression
There is this certain slide in Coursera Computer Science: Algorithms, Theory, and Machines course:

I think it is saying finding the optimal size of given data is undecidable. However, I thought there is a theorem in information theory that gives the limit of the lossless compression? I think I must have misinterpreted something in this slide but I cannot tell what that is.

# Answer
The length of the shortest program to produce a given string is known as the Kolmogorov complexity of that given string. (Of course, some details are needed to give a formal definition, but this is the idea.) A proof of undecidability goes roughly as follows:

* There exist strings of arbitrary large Kolmogorov complexity by a counting argument: A program produces (at most) one string, and there are a finite number of program of length at most $N$, so a finite number of string of Kolmogorov complexity at most $N$;
* Assume that the Kolmogorov complexity of a string is computable. For any integer $N$, we can write a program that does the following: it enumerates all the strings (in some lexicographic order) until it finds one that has Kolmogorov complexity $\ge N$. The size of this program is roughly $O(\log N)$ (a constant number of instruction, and the value of $N$ hard-coded in the program).
* We conclude the string $s$ produced by the program of the preceding item satisfies two contradictory statements:
    + it has Kolmogorov complexity $\ge N$, that is the smallest program to produce it has length $\ge N$;
    + the program we describe has length $\<N$ and produces $s$.

I don't know what you have in mind exactly concerning lossless compression, but it may be related to the first part of the proof sketch: It is not possible that all strings be compressible, because to each description corresponds one string.
> 4 votes

---
Tags: turing-machines, undecidability, information-theory, data-compression
---


# Question
Title: How can I apply binary search to find two adjacent increasing elements in an unsorted array?
I need to write a function that gets an array of numbers $a$ as an input and returns an index $i$ such that $a\[i\]\<a\[i+1\]$ if it exists, if such $i$ doesn't exist return $-1$. (return any index $i$ if there are multiple).
We know that: in $a$ there are at least $2$ elements, $a$ may or may not be sorted and the first element in $a$ is less than the last element.
The solution needs to have $O(\log n)$ time-complexity and $O(1)$ space-complexity.
Example $a=\[0,-8,-8,6,1\]$, the function returns $2$ because $a\[2\]\<a\[3\]$.
**My Thoughts:**

* I need to somehow "split" the problem in half by cutting half of the numbers that I need to check in order to reach the required time complexity.
* The array isn't ordered, but I have information that the first element is less than the last, and that there are at least two elements, so I need to somehow use this extra info.

The unsorted information is not allowing me to reach anything, I can definitely start from the middle and check if it's less than the last element, if yes then an index $i$ that satisfies $a\[i\]\<a\[i+1\]$, will surely appear on the right side, but I can't just jump over half of the numbers to the right, they're unsorted, so the index $i$ might be the next one from the middle.

# Answer
> 3 votes
You are almost there. "If yes then an index $i$ that satisfies $a\[i\]\<a\[i+1\]$, will surely appear on the right side"; so continue searching on the right side. If no, continue searching on the left side.

#### Binary Search

The idea is to find two elements, the left of which is smaller than the right of which such that their positions are becoming closer and closer. In the end, they must have become adjacent.

Initially, we have pair $A\[0\]$ and $A\[n-1\]$. If $A\[0\]$ and $A\[n-1\]$ are adjacent, we are done.

Let the middle index be $m=\lfloor\frac{0+(n-1)}2\rfloor=\lfloor\frac{n-1}2\rfloor$. Consider the element in the middle, $A\[m\]$.

* If $A\[m\]\<A\[n-1\]$, we have a new pair $A\[m\]$ and $A\[n-1\]$.
* Otherwise, $A\[m\]\ge A\[n-1\]\gt A\[0\]$. We have a new pair $A\[0\]$ and $A\[m\]$.

As long as $A\[0\]$ and $A\[n-1\]$ are not adjacent, $A\[m\]$ cannot be $A\[0\]$ nor $A\[n-1\]$. So the distance between the new pair of elements must be smaller than the distance between $A\[0\]$ and $A\[n-1\]$.

Repeat the process with the new pair of elements. And so on.

Since the distance of the two elements in a pair becomes smaller and smaller by each iteration as long as the pair at the start of the iteration are not adjacent, the pair will become adjacent eventually, at which time we have obtained a wanted pair.

Well, we are applying binary search. A quick analysis shows it takes at most $\lceil\log\_2(n-1)\rceil$ iterations to reach a wanted pair.

#### Two exercises.

**Exercise 1**(easy). For pair $A\[i\]$ and $A\[j\]$, the middle element is chosen at index $\lfloor\frac{i+j}2\rfloor$ in the approach above. Explain it can be chosen at index $\lceil\frac{i+j}2\rceil$ as well.

**Exercise 2** (easy). Given an array of integers, find a peak in it by binary search. An array element is a peak if it is not smaller than its neighbours. An element may have 0, 1, 2 neighbourrs.

# Answer
> 5 votes
**Lemma:**

For any $i\<j$, if $A\[i\]\<A\[j\]$, there are certainly two neighboring elements in $A\[i..j\]$ such that $A\[k\]\<A\[k+1\]$. Otherwise, the subarray would be non-increasing and this contradicts $A\[i\]\<A\[j\]$.

**Algorithm:**

The dichotomy is based on the following rule:

* take $k$ to be the midpoint of $i$ and $j$;
* if $A\[k\]\le A\[i\]$, recurse on $A\[k..j\]$ (because $A\[k\]\<A\[j\]$);
* if $A\[j\]\le A\[k\]$, recurse on $A\[i..k\]$ (because $A\[i\]\<A\[k\]$);
* otherwise, $A\[i\]\<A\[k\]\<A\[j\]$ and you can recurse on either subarray.

---

You can also solve this in an asymmetrical but simpler way,

* if $A\[k\]\le A\[i\]$, recurse on $A\[k..j\]$ (because $A\[k\]\<A\[j\]$);
* otherwise, recurse on $A\[i..k\]$ (because $A\[i\]\<A\[k\]$).

---
Tags: algorithms, search-algorithms, arrays, binary-search
---


# Question
Title: Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?
An alternative way of deciding within a nondeterministic complexity class is to present a verifier-prover pair. To recall, let $\mathsf{L}$ be a language, and let $\mathsf{w}$ be a word. To decide whether $\mathsf{w} \in \mathsf{L}$:

* The prover, a magical machine, will immediately find a proof that $\mathsf{w} \in \mathsf{L}$ and send it to the verifier. If $\mathsf{w} \notin \mathsf{L}$, however, the proof will be a fake. (In this sense the prover is said to be **malicious**.)
* The verifier, a Turing machine (or an equivalent), having received the proof, will decide whether the proof is true.

Here, there is no time/space restriction for the verifier, meaning that our complexity class in concern is $\mathsf{RE}$.

It is well-known that $\mathsf{HALT}$, the halting problem, is in $\mathsf{RE}$. In a simple sense, the verifier-prover pair would look like this. Let $\mathsf{w}$ be the program concerned whether to halt:

* If $\mathsf{w} \in \mathsf{HALT}$, the prover will immediately know how many Turing machine iterations are needed for $\mathsf{w}$ to halt.

+ The verifier will run $\mathsf{w}$ for exactly that many Turing machine iterations, see that $\mathsf{w}$ actually halted, and accept.
* If $\mathsf{w} \notin \mathsf{HALT}$, the prover will immediately know that $\mathsf{w}$ wouldn't halt, and will send the verifier a random number.

+ The verifier will run $\mathsf{w}$ for exactly that many Turing machine iterations, see that $\mathsf{w}$ actually didn't halt, and reject.

But what about its complement, $\mathsf{\text{NOT-HALT}}$? It is well-known that it is not in $\mathsf{RE}$. As such, I presume it means there cannot be a working verifier-prover pair for $\mathsf{\text{NOT-HALT}}$. But which machine should I blame? I see several ways of interpreting this:

* There is no way of proving $\mathsf{w}$ wouldn't halt. It's the prover's fault.
* It is possible to prove that $\mathsf{w}$ wouldn't halt, but there is no way of deciding whether the proof is true. It's the verifier's fault.

# Answer
It's the prover's fault: there is no way to decide whether an arbitrary TM will halt or run forever, and so there is no certificate to prove that an arbitrary TM will run forever.

If $L$ is not recursively enumerable, then no machine can simultaneously:

1. Halt on every input $\langle w, c\rangle$ (a word and a proof that the word is in the language).
2. Always answer correctly whether $w\in L$.

If a convincing certificate $c(w)$ really did exist for every word $w$ in the language, and a verifier with these two properties existed, then the language would be recursively enumerable and here is the Turing machine to prove it:

> M(x): on input x, iterate over every possible word $c$ in increasing order of length and run the verifier on $\langle x,c\rangle$. Halt and respond YES if the verifier ever accepts, otherwise keep iterating forever.

It's not the verifier's fault. If a language is not recursively enumerable, then (equivalently) it is algorithmically impossible to confirm membership in the language. In particular, no certificate can help.
> 1 votes

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


# Question
Title: Build a 2-PDA for language accepted by Turing Machine
I saw this question on the internet and found many solutions actually but none of them really persuade me that much.

***Question:*** Given language $L$ which is accepted by a Turing machine $M$, provide a 2-PDA that describes $L$. End of the question.

***Note:*** A Turing machine is given by $M=\\{Q,\Sigma,\Gamma,\delta,q\_0,q\_{accept},q\_{reject}\\}$.

I assume that the transitions in a 2-PDA look like this:

$$\sigma, \begin{pmatrix} \gamma\_1\rightarrow\gamma\_2 \\ \gamma\_2\rightarrow\gamma\_3 \end{pmatrix}$$

Meaning when we see a letter $\sigma$ we remove $\gamma\_1$ from the first stack, insert $\gamma\_2$ to it, and remove $\gamma\_2$ from the second stack and insert $\gamma\_3$ to it.

I think there is a simple answer that for a transition $(\sigma\_1\rightarrow\sigma\_2,L/R)$ in $M$ we can replace it with a transition of the form of a 2-PDA transition but I don't really recognize what is the desired transition.

# Answer
> 1 votes
If the non-blank region of the Turing tape looks like $$ \begin{bmatrix}a\_1&a\_2& \ldots& a\_n& \check{x} &b\_1&\ldots& b\_m\end{bmatrix}$$ where $\check{x}$ denotes the current position, then the two stacks should look roughly like

$$\begin{bmatrix}a\_n\\a\_{n-1}\\a\_{n-2}\\\vdots \\ a\_1\end{bmatrix} \begin{bmatrix}x\\b\_1\\b\_{2}\\\vdots \\ b\_n\end{bmatrix}$$

When the tape head moves left, pop from the left stack and push the same symbol onto the right stack.

When the tape head moves right, pop from the right stack and push the same symbol onto the left stack.

If you move onto blank areas of the tape and run out of symbols to pop in the stack, you are allowed to push a blank symbol so that the stack behaves as if it has an inexhaustible supply of blank symbols. Equivalently, every stack can start with the symbol $\square\_\infty$ at the bottom (infinite tape here), and if you would pop it off the stack and push it onto the other stack, you instead leave it where it is and push a single blank symbol $\square$ onto the other stack.

---
Tags: turing-machines, pushdown-automata, computation-models
---


# Question
Title: Conjecture: a half of a pairing context-free language must be a regular language
If $A$ and $B$ are languages, let $A\bowtie B$ denote the set of strings made by concatenating any word from $A$ and any word from $B$ of equal length.

$$A\bowtie B \equiv \\{ ab : a\in A,\\;b\in B, |a|=|b|\\}.$$

You can prove using regular grammars that if $A$ and $B$ are regular, then $A\bowtie B$ is context free. I am wondering about the converse. Specifically, this conjecture:

> **Conjecture**: If $A\bowtie B$ is context-free, and the strings in $A$ and $B$ have the same lengths $\\{|a| : a\in A\\}=\\{|b| : b\in B\\}$, then $A$ and $B$ are regular.

The intuition behind the conjecture is that the pushdown stack can be used to ensure that $A$ and $B$ are the same length, or to generate complex internal structure within $A$ and $B$ (such as palindromes or matching character counts) but not both simultaneously.

I haven't been able to prove this, even for the simple case where $B$ is the language of all strings. Unfortunately, I've also not been able to find a counterexample.

So far I have tried:

1. Using Parikh's theorem, Odgen's lemma, and the pumping lemma for CFLs.
2. Using generating functions—regular languages have rational gfs and unambiguous cfls have algebraic gfs, but not conversely.
3. Using the Chomsky-Schutzenberger theorem and trying to catalogue parentheses based on whether their image is always in the left/right half of the derived string.
4. Showing that the conjecture holds when the alphabets are distinct. This turns out to be easy to prove (using Chomsky normal form). But I don't have any indication that if $A\bowtie B$ is context free then it is also the homomorphic image of a context free language $A^\prime \bowtie B^\prime$, where $A$ and $B$ have distinct alphabets.

Any advice is appreciated.

# Answer
No, this conjecture is not true.

Consider $A=\\{0^n1^n \mid n\geqslant0 \\}$ and $B=\\{1^{2n}\mid n\geqslant0\\}$.

We have $\\{|a| : a\in A\\}=\\{|b| : b\in B\\}=\\{2n\mid n\geqslant0\\}$ and $A\bowtie B = \\{ 0^n1^{3n}\mid n\geqslant0\\}$.

While $A\bowtie B$ is context-free, $A$ is not regular.
> 12 votes

---
Tags: regular-languages, context-free, open-problem
---


# Question
Title: What are some examples of non-enumerable languages whose complement isn't either?
What are some examples of non-enumerable languages whose complement isn't either? I.e., a language L such that L is not Turning-recognizable and L’ is not Turing-recognizable either.

Update: Found some examples:

# Answer
> 2 votes
A random language is neither recognizable nor co-recognizable almost surely.

Every language which is complete for $\Sigma\_k$ or $\Pi\_k$, for any $k \geq 2$ (these are classes in the arithmetical hierarchy), is neither recognizable nor co-recognizable. Some examples:

* The language of all oracle TMs $M$ such that $M$ halts on the empty input when given access to an oracle of the halting problem ($\Sigma\_2$-complete).
* The language of all TMs $M$ such that $M$ halts on finitely many inputs ($\Sigma\_2$-complete).
* The language of all TMs $M$ such that $M$ halts on all inputs ($\Pi\_2$-complete).
* The language of all TMs $M$ such that "$M$ halts on $x$" is decidable ($\Sigma\_3$-complete).
* The language of all TMs $M$ such that $M$ halts on all but finitely many inputs ($\Sigma\_3$-complete).

See lecture notes of Terwijn.

---
Tags: turing-machines, computability, turing-recognizable, recursively-enumerable
---


# Question
Title: Are Unit Tests Required if you have a good End to End Test?
Are Unit Tests Required if you have a good End to End Test? If you find problems, couldn't you always just update the end to end test to make it more robust?

# Answer
This isn't really a CS question, more of a Software Engineering question. Still: If you find an error in an end-to-end test, and you can then replicate it in a simpler unit test, then you definitely should create that unit test.

Unit tests have the big advantage of pinpointing *where* in your code a problem exists. End-to-end tests just tell you that something is wrong, somewhere.
> 1 votes

---
Tags: software-testing
---


# Question
Title: Are Path-systems P-complete under logspace many-one reductions?
As far as I know, the admissability of a path-system is an example of a P-complete problem.

However, I am not sure under which kind of reductions (many-one or turing-reductions? logspace or AC$^0$ reductions ... ?).

Can anyone explain me under which reductions are Path-systems P-complete, please?

# Answer
> 1 votes
Admissible path-systems are, indeed, P-complete under many-one logspace reductions.

On the paper \[1\] we can see that Cook, given a Turing Machine $M$ that runs in $T(n)$ and some input $w$, builds a path-system problem that is admissible iff $M$ accepts $w$. Hence, the reduction is many-one.

The reduction is logspace, as already claimed by Cook, since it uses log(T(n)) memory, and hence, it uses k\*log(n) memory if T(n) is $n^k$.

\[1\] Cook, Stephen A. "An observation on time-storage trade off." Proceedings of the fifth annual ACM symposium on Theory of computing. 1973.

---
Tags: complexity-theory, reductions
---


# Question
Title: What does Herb Sutter refer to in his seminal paper The free lunch is over?
In his paper The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software, Herb Sutter writes:

> The mainstream state of the art revolves around lock-based programming, which is subtle and hazardous. We desperately need a higher-level programming model for concurrency than languages offer today; I'll have more to say about that soon.

Can somebody with more knowledge about his work answer what he is referring to? Did he say more about that later?

# Answer
> 2 votes
I think this question was answered in "The Trouble with Locks" (Dr. Dobb's Journal, 1 March 2005), which article indicates that his "I'll have more to say about that soon" was more about the problems of lock-based programming than about a specific proposal for improvement.

> Personally, I think that the most important sentence in ... \["The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software"\] ... was the fourth and last conclusion: "4. Finally, programming languages and systems will increasingly be forced to deal well with concurrency." Before concurrency becomes accessible for routine use by mainstream developers, we will need significantly better, still-to-be-designed, higher level language abstractions for concurrency than are available in any language on any platform. Lock-based programming is our status quo and it isn't enough; it is known to be not composable, hard to use, and full of latent races (where you forgot to lock) and deadlocks (where you lock the wrong way). Comparing the concurrency world to the programming language world, basics such as semaphores have been around almost as long as assembler and are at the same level as assembler; locks are like structured programming with goto; and we need an "OO" level of abstraction for concurrency.

**Note**: "still to be designed".

("Lock-Free Code: A False Sense of Security", 8 September 2008, and "Writing Lock-Free Code: A Corrected Queue", 29 September 2008, explored how "lock-free coding is hard even for experts".)

# Answer
> 3 votes
He's saying the clock/IPC/cache/etc. speedup of CPUs must come to an end, and with it the increasing speedup of serial code, which is relatively easy to write - the free lunch.

Therefore parallel code (= concurrency) must take over to keep that growth going, and to do that better support for concurrency, including locking primitives (because parallel code can be relatively hard to write).

My take anyway.

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


# Question
Title: How to evaluate the tightness of a bound on a function?
I recently submitted a paper where in part of the paper I derived a bound on a function (note it is an upper bound). The benefit of the bound is that it is much less complex to compute in contrast to the actual value of the function. So, the bound can be used as a cost for optimization instead of the actual value of the function. However, I received a comment that I did not include a proof for the tightness of the bound.

I'm not exactly sure what is meant by this. I did numerical experiments demonstrating how the bound is related to the actual value of the function (i.e., showing the difference between the bound and the actual value), but I understand this is specific to the experimental setup. Is there a standard procedure for evaluating the tightness of a bound on a function in general? Any suggestions would be greatly appreciated.

# Answer
> 2 votes
To evaluate tightness of a bound on a function, you need to find both the upper and lower bounds. Finding an upper bound on the function is good but it leaves the possibility that the actual function might be asymptotically better than the computed upper bound.

For example, suppose the actual function is $f(x) = n + n/2 + n/3 +\dotsc + 1$. Then, one can trivially find an upper bound on $f(x)$ as follows: $$ \begin{align} f(x) &= n + n/2 + n/3 +\dotsc + 1 \\ &\leq n + n + \dotsc + n \\ &\leq n^2 \\ &= O(n^2) \end{align} $$

Now, how would you know $f(x)$ is not $O(n)$ or $O(\sqrt{n})$ or anything better than $O(n^2)$? Therefore, you need a matching lower bound. For that you need Big Omega notation. In other words, you need to show that $f(x) = \Omega(n^2)$ so that it does not leave the possibility of $f(x)$ being $O(n)$ or $O(\sqrt{n})$, etc.

Interestingly, the upper bound of $O(n^2)$ for $f(x)$ is not tight. The tight bound in fact is $O(n \log n)$. That is, $n + n/2 + n/3 + \dotsc + 1$ can also be lower bounded by $\Omega(n \log n)$. This is beacuse the $n^{th}$ harmonic number $H\_{n}$ is lower and upper bounded by $\log n$ (see here for reference). Thus, we have $f(x) = O(n \log n)$ and $f(x) = \Omega(n \log n)$.

---
Tags: optimization, proof-techniques, lower-bounds, upper-bound
---


# Question
Title: Variation of Assignment Problem to maximize amount of agents working
I'm looking at a problem similar to an assignment problem.

There are both agents and tasks. Each agent has a list of tasks they are able to do, and cannot do any task not within that list (note that agents do not have a preference for what task they do, only a list of tasks they are able to do). A task can be assigned to multiple agents. However, the amount of agents assigned to a task must lie between a given minimum and maximum. **A task could also be assigned to no agents.** The goal is to maximize the amount of agents that are assigned to a task.

I've simplified the problem down to creating a bipartite graph with agents on one side and tasks on the other. An edge would be drawn between an agent and the tasks they are willing to do. The goal would be to take a subset of these edges that would have at most one edge from each agent node and a number of edges either at 0 or between the min/max for the task nodes.

I've thought it over, and I've got part of a possible solution. For each task node, they will be duplicated until they are at the same number as the maximum agents allowed to be on one task. Then a maximal matching could be found for that graph. After the matching is found, the duplicated nodes are all combined into one node. The problem with this is that I'm not sure how to enforce the condition that each task must have a minimum number of agents assigned to it. Ideally, we'd want to minimize the amount of tasks that are below the minimum but still have at least 1 agent. What approach should I take to enforce this goal of minimizing the tasks with an agent count between 1 and the minimum?

More progress has been made: a circular flow network almost works. The problem is my problem allows for a task to either be assigned (to at least the required minimum of agents) or be scraped (and assigned to no agents). The minimum of each edge in a circular flow network would enforce the required minimum, but make it so tasks couldn't be scraped. Any ideas how to address this?

# Answer
> 1 votes
The problem is $\mathsf{NP}$-hard via a reduction from Exact Cover by 3-sets problem. Let $(X,F)$ be an instance of Exact Cover by 3-sets problem. Then, the set $X$ corresponds to agents and the set $F$ corresponds to tasks. Each task will have an upper and lower bound of $3$. You can easily prove the following statement:

> There exists a feasible solution to $(X,F)$ if and only if the maximum number of assigned agents are $|X|$.

---
Tags: algorithms, graphs
---


# Question
Title: Number of Inversions found in Selection sort vs Exchange sort
Exchange sort is similar to selection sort, just swaps "overly eagerly" instead of finding the minimum and doing only one swap. And the swaps affect how often the `if ...` is true. For example for 8000 random numbers, in exchange sort it's true ~270 times more often:

```
        trues in      trues in
   n  exchangeSort  selectionSort  ratio
----------------------------------------
1000      244828        5368        45.6
2000     1002555       12341        81.2
4000     4017151       27691       145.1
8000    16359262       60394       270.9

```

**Why is it so much more often?** Does someone have a good explanation? I did expect *some* noticeable difference, but not this much.

**What's the expected number of trues for each?**. For exchange sort it looks quadratic, for selection sort maybe linearithmic?

Code (Try it online!):

```
def exchangeSort(nums):
    trues = 0
    for i in range(len(nums)-1):
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[i]:
                trues += 1
                nums[j], nums[i] = nums[i], nums[j]
    return trues

def selectionSort(nums):
    trues = 0
    for i in range(len(nums)-1):
        idx_min = i
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[idx_min]:
                trues += 1
                idx_min = j
        nums[idx_min], nums[i] = nums[i], nums[idx_min]
    return trues

from random import random
print('        trues in      trues in')
print('   n  exchangeSort  selectionSort  ratio')
print('----------------------------------------')
for n in 1000, 2000, 4000, 8000:
    nums = [random() for _ in range(n)]
    trues1 = exchangeSort(nums.copy())
    trues2 = selectionSort(nums.copy())
    print(f'{n}  {trues1:10}  {trues2:10}  {trues1/trues2:10.1f}')

```

This was inspired by another question, from which I also took the code.

# Answer
Interesting question! Indeed, the expected numbers are quadratic and linearithmic respectively.

#### Assumptions

For ease of analysis, assume the numbers in the given array are distinct. This assumption does not change the asymptotic nature of problems at hand.

WLOG, assume the given array is selected uniformly from all permutations of $0, 1,\cdots, n-1$.

#### Expected Number by Exchange Sort

**Claim 1.** Given array $nums$, the number of inversions found by exchange-sort is the number of inversions in $nums$.
**Proof.** It is easy to check that each swap reduces one instance of inversion. $\quad\checkmark$

Hence, the expected number of inversions found by exchanges-sort is the expected inversions in a permutation, which is $(n(n-1)/2)/2=n(n-1)/4$.

#### Expected Number by Selection Sort

**Claim 2.** The expected number of inversions found by selection-sort in the inner loop is $\frac12 + \frac13+\cdots+\frac1{n-i}$.
**Proof**. At the start of inner loop, the "comparison structure" of $nums\[i:n\]$ is uniformly random. The probability of $nums\[j\] \< nums\[idx\\\_min\]$ is the probability of the random number at index $j$ being less than all $j-i$ random numbers right before it, which is $\frac1{j-i+1}$ since the randomness here comes from sampling from distinct numbers without replacement. $\quad\quad\checkmark$

Hence, the expected number of inversions found by selection-sort is $$\begin{aligned} &\quad\sum\_{i=0}^{n-2}\sum\_{j=i+1}^{n-1}\frac1{j-i+1}\\ &=\sum\_{k=2}^{n}\sum\_{\ell=2}^{k}\frac1\ell\\ &=\sum\_{k=2}^{n}(-1+\ln k+\gamma +{\frac {1}{2k}}-\varepsilon\_k)\\ &=\ln (n!) + (n-1)(\gamma-1) +\sum\_{k=2}^{n}{\frac {1}{2k}}-\sum\_{k=2}^{n}\varepsilon\_k\\ &=\ln (n!) + (n-1)(\gamma-1) +\frac12(-1 + \ln n+\gamma + \frac1{2n}-\varepsilon\_{n})-\sum\_{k=2}^{n}\varepsilon\_k\\ &=\ln\left({\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\right)+ n(\gamma-1) + o(n)\\ &=n\log n + n(\gamma-2) + o(n)\\ &\sim n\log n \end{aligned}$$

where the second equality and the fourth equality use the growth rate of partial sums of harmonic series and the second equality from the last uses Stirling's approximation.

#### "Why is it so much more often?"

The reason is embodied in the proof of two claims above. Also see asker's wonderful and enlightening explanation.
> 4 votes

# Answer
Here's another perspective. Less mathematical, but I think also insightful. Using a fabulous sort visualizer (taken from this), here's random data and how the data looks midway through sorting with the two algorithms.

It visualizes sorting many arrays in parallel, each array is a column, index 0 is on top, and dark colors are "smaller" than bright colors. Try it yourself, select the sorting algorithms on the right, then click "Start".

For selection sort, we see what John L. said: The still-to-be-sorted part `nums[i:n]` looks completely random. And it is: It is at the very beginning, and what's done inside the outer loop keeps this property. If `nums[i]` is the smallest in `nums[i:n]`, then we don't really swap and `nums[i+1:n]` remains as it is, i.e., remains completely random. If on the other hand `nums[i]` isn't the smallest, then its value plays no role whatsoever in determining `idx_min`. That index is entirely determined by wherever the smallest element is. And since `nums[i]` plays no role for this, its relationship with all other values in `nums[i+1:n]` (other than the smallest) can be anything. Hence swapping it it to `idx_min` makes `nums[i+1:n]` completely random as well.

Look at the exchange sort visualization instead. There we see that the still-to-be-sorted bottom half already looks somewhat (reverse-)sorted. A lot of bright colors, i.e., large values, near index `i`. And getting darker going down. Why is that? Consider what the inner loop does. It goes through the remaining `nums[i:n]`, puts the smallest value at `nums[i]`, and whenever it finds an *even smaller* value, it swaps `nums[i]` there. That finds a descending subsequence in `nums[i:n]` and "rotates" it to the right. Here's an example where the descending subsequence is 30, 20, 10 (and what the other values between/after might be):

Now imagine that for example the block of numbers containing values from 31 to infinity actually contains the number 31. And that the other two later blocks similarly contain the number 21 and 11, respectively. *Before* the swaps, we see the order 30-31-20-21-10-11. So going up-down-up-down-up. But *after* the swaps, we see the order 10-31-30-21-20-11. So going up-down-down-down-down-down. The part after the 10 is all going down. We've taken the subsequence 30-20 and shifted it to the right so that it "falls more in line" (order-wise) with the rest, so that the remainder is now more sorted (descendingly) than before. And these longer descending subsequences are then found and handled in later rounds (for larger `i`), causing more work there.

So to summarize: Selection sort keeps the remainder unsorted, which is good. While exchange sort shoots itself in the foot by partially sorting the remainder in a way that's detrimental for it (causes more inversions / more work).
> 6 votes

---
Tags: algorithms, sorting, python
---


title: Decidability of a context free Grammar

text:
# Question
Title: Decidability of a context free Grammar
Say that a Context Free Grammar is red when it accepts every word of length 3 that begins with a, and extremely red when it accepts every word that begins with a.

Is redness decidable? or Semi decidable? will the algorithm go into an infinite loop when presented with certain invalid statements?

Also what about extreme redness?

# Answer
> 2 votes
"Redness" is decidable, because the alphabet of a context-free grammar is finite (by definition), and therefore the set of strings exactly three characters long starting with `a` is also finite. So you only need to try every string in that finite set.

"Extreme redness" is very different. Here, the question is whether `{a}·Σ* ⊆ L`. This is not decidable, even though `{a}·Σ*` is a regular language. The simplest proof is to start with the well-known fact that it is not decidable whether a context-free grammar recognises every string in Σ\*, and derive a contradiction.

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


# Question
Title: Is the language of words that are unbalanced in the first half context-free?
(Practice exam question in computational models)

Definition: A word $w\in \\{0,1\\}^\*$ is called balanced if it contains the same number of $0$s as $1$s.

Let $L = \\{w\in \\{0,1\\}^\*\mid |w|$ is even and the first half of $w$ is unbalanced$\\}$. Determine whether or not $L$ is context-free and prove your answer. You may do so by drawing an NPDA which recognizes $L$, using the closure properties of CFLs, or the relevant pumping lemma.

This question has been bugging me for a while; my gut tells me it isn't context-free since any PDA that recognizes it would have to check the balance of the string read thus far while simultaneously measuring its length and non-deterministically choosing an unbalanced point to validate as the middle of the word. I also haven't been able to express it as a union or concatenation of two CFLs or find a CFG which generates it.

On the other hand, I haven't been able to either find a word in the language that can't be pumped or prove that every word can be pumped.

Does anyone have any ideas on how to proceed?

# Answer
> 1 votes
(Note: this answer doesn't fully answer the question — I don't know whether the language is context-free — it merely addresses the question of whether it satisfies the pumping lemma, which was raised in the question and discussed in the comments, and is obviously relevant in that the language cannot be context-free if without satisfying the pumping lemma.)

> On the other hand, I haven't been able to either find a word in the language that can't be pumped or prove that every word can be pumped.

Every word of length ≥ 4 *can* be pumped.

To see how, we distinguish three cases:

1. If $|w|$ is not a multiple of four, then we can choose any substring of length 4, break it up however-we-want into $v$ and $x$, and pump it. This works because pumping will preserve the invariant that $|w|$ is never a multiple of four, which in turn means that the first half can never be balanced (because the first half will never have an even number of characters), so the result is necessarily in $L$.
2. If $|w|$ is a multiple of four, and there are more 0s than 1s in the first half, then the first half must contain some occurrence of the substring '00'. (It can't be something like '010101...0', because then $|w|$ wouldn't be a multiple of four.) We can take that substring, break it up however-we-want into $v$ and $x$, and pump it.
    * When $n = 0$, the length of the result is not a multiple of four, which as we saw above means it's necessarily in $L$, as desired.
    * With $n \> 0$, the first half of the result will continue to have more 0s than 1s, because incrementing *n* adds two 0s and causes at most one 0 to be "lost" to the second half, so the number of 0s in the first half strictly increases and the number 1s in the first half never increases. So the result is in $L$, as desired.
3. If $|w|$ is a multiple of four, and there are more 1s than 0s in the first half, then . . . well, no need to write it all out, it's perfectly symmetric to case #2.

---

So the language does satisfy the pumping lemma, but as I'm sure you already know, that doesn't prove that the language is context-free. :-(

# Answer
> 0 votes
Perhaps it can be proved using *Ogden's Lemma* and its generalization by *Bader and Moura*, this is a rather informal sketch of the proof.

First restrict $L$ to strings of length $4n$ and apply to it the following homomorphism between $\Sigma = \\{ 0,1 \\}$ and $\Sigma' = \\{ a, b, c\\}$:

$h(11) \to a$
$h(00) \to b$
$h(01) \to c$
$h(10) \to c$

If $L$ is CF then also the new language $L'$ obtained is CF by closure properties.

Informally $L'$ contains an unbalanced number of $a$ and $b$ in the first half and the number/occurences of $c$ doesn't matter.

Further restrict $L'$ by intersecting it with the regular language $R = \\{ a^\* (c^\* b^\*)^\* \\}$; let $L'' = R \cap L'$

For example the string

$a a c b | cccc \in L''$ corresponds to $11\\;11\\;10\\;00\\; |\\; 10\\;10\\;10\\;10 \in L$ ($|$ is used to mark the half of the string for better readability)

$a b c c | cccc \notin L''$ corresponds to $11\\;00\\;10\\;10\\;|\\;10\\;10\\;10\\;10 \notin L$

Suppose that $L''$ is CF, and $p$ is its pumping length. Build $w \in L''$ concatenating these four parts:

1. $(\\;a^p\\;)$ leading $a$'s
2. $(\\;c^j\\;)$ a sequence of $c$s, we'll fix $j$ below
3. $(\\;c^{p} \\;b\\;)$ repeated $p + p!$

If $n$ is the constant of the Bader-Moura's condition, then we pick $j$ large enough to exclude all the symbols in part 1 and 3: $j \geq n^{p+(p+1)(p+p!)+1}$

4. $(c^k)$ where $k$ is large enough to be pumped exluding all previous symbols: $k \geq n^{p + j + (p+1)(p+p!)+1}$

$w = a^{p} \\; c^j \\; (c^{p} \\;b )^{p+p!} \\; c^{k} $

Now we mark the first $a$ sequence as distinguished, the string $vx$ must contain $0 \< q \leq p$ distinguished positions ($\\#a\_{vx} = q$) by Ogden's lemma; $vx$ can also contain one $b$ (not more than one because the $b$s are spaced with more than $p$ symbols $c$) and $0 \leq r \< p$ symbols $c$ ($\\#c\_{vx} = r$).

1. if $vx$ is such that $\\#a\_{vx}=q$, $\\#b\_{vx}=0$, $\\#c\_{vx}=r$:

then we can pump $i = p! / q $ times and we obtain the same number of $a$s and $b$s; if after the pump some $b$s fall after the half of the string, we can pump the final $c^k$ independently from the rest of the string and we can "push" all $a$s and $b$s back in the first half (and $\\#a\_{w'} = \\#b\_{w'} = p + p!$), so the pumped string $w'$ is not in $L''$

2. if $vx$ is such that $\\#a\_{vx}=q$, $\\#b\_{vx}=1$, $\\#c\_{vx}=r$:

then each time we pump we increase the number of $a$s and $b$s, but we cannot guarantee that we reach the same number (e.g. in the case $\\#a\_{vx}=q=1\\#b\_{vx}$). But in this case the derivation tree "isolate" the $c^j$ part of the string from the final part $c^k$, so we can pump them independently.

We can pump $c^j$ as many time as needed to "push" $p!$ symbols $b$s to the second half of the string. Suppose that the pumping length of $c^j$ is $s$ (that must be even), the half of the string is shifted towards the $b$s by $s/2$. We have $s \leq p$ so after each pump at most one $b$ is "pushed" to the second half, because the "distance" between $b$s is $p$. So also in this case we get a string $w'$ not in $L''$

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


# Question
Title: Getting a "sub-polytope" of a concave d-dimensional polytope, given some one dimensional inequality
The question will be hard to understand without an example, so let's given an example first: Let's say I have a 2 dimensional concave polytope, defined by a **circular sequence** of its vertices:

$(0,0), (1, 4), (2, 0) (1, 1), (0, 0)$

Let's say I wanted to find the polytope I get if I considered only points s.t. $y\>=0.5$, which means:

In this example, we would get the polytope with vertices:

$(0.125, 0.5), (1, 4), (1.875, 0.5), (1.5, 0.5), (1, 1), (0.5, 0.5), (0.125, 0.5) $

What would be the way to do this computationally? Generally, for $d$ dimensions, given a $d$ dimensional concave polytope defined by a **circular sequence** of its vertices (s.t. if I were to "travel" along the sequence of vertices, I'd get on every single edge of the polytope, and end where I started), and given an equation $x\_i \>= c$ for some constant c and for $i \in \[0, d - 1\]$, where $x\_i$ is the coordinate, what would be the way to return a concave polytope which is defined by "cutting" the given polytope in the way I described in my example?

# Answer
> 0 votes
When $d\>2$, I believe a sequence of vertices does not uniquely determine a non-convex polytope, so it looks to me like your representation has some issues and your 2D example is misleading.

But assuming an appropriate representation of a (non-convex) polytope: If $d$ is not too large, the following works: Enumerate all the faces. For each face, if it intersects with the plane $x\_i=c$, then intersect the face with $x\_i\ge c$ (and discard everything with $x\_i\<c$), and add vertices for each intersection with the plane $x\_i=c$ that is on the perimeter of that face, and discard any vertices for which $x\_i\<c$.

---
Tags: computational-geometry, linear-algebra
---


# Question
Title: Why is a recurrence of $2N_{h-2}$ equal to $2^{h/2}$?
I was watching video *7. Binary Trees, Part 2: AVL*, where professor Erik Demaine stated that $$2N\_{h-2} = 2^{h/2\text{ (or maybe with floor or something... maybe it's ceiling)}}$$ where $N$ stands for the number of nodes in a subtree of height $h-2$. Can someone explain me in more detail why this recursion can be solved like this?

# Answer
In the lecture it was shown that $N\_h \geq 2N\_{h-2}$. You can obtain the bound of $2^{h/2} $ for this recurrence by continued expansion of the r.h.s., also called unrolling the recurrence. E.g. :

$N\_h \geq 2N\_{h-2} = 2 * (2N\_{h-4}) = 2\*(2\*(2N\_{h-6})) = 2(2(2(...(2N\_0)...)))$.

This expansion will continue until you reach $N\_0$, which is 1, I think since the tree with height 0 has only the root. The number of times you can subtract 2 from $h$ is at most $\lceil h/2\rceil$, which is also the number of 2's in the expansion. Thus you have $N\_h \geq 2^{\lceil h/2\rceil}$.
> 1 votes

# Answer
Let $N\_h$ denote the minimum number of nodes in a height-balanced tree of height $h$. Given a height-balanced tree of height $h$, without loss of generality assume the left child of the root has height $h-1$. The right child must have height $h-1$ or $h-2$, and to get the smallest possible values (the worst-case), assume it has height $h-2$. Then, the number of nodes in the given tree is at least $N\_{h-1} + N\_{h-2} + 1$, because there are at least $N\_{h-1}$ nodes in the left subtree of the root, at least $N\_{h-2}$ nodes (in the worst case) in the right subtree of the root, and the root itself contributes 1 to the count of number of nodes.

Thus, we get that $N\_h \ge N\_{h-1} + N\_{h-2} + 1$. One can pay attention to constants and show the terms $N\_1, N\_2, \ldots$ grow at least as fast as the Fibonacci sequence. The $h$th term of the Fibonacci sequence is at least $c \psi^h$ for some constant $c$ and the golden ratio $\psi$. Hence, the terms of the sequence grow exponentially fast. This can be shown to imply that $h$ is at most $1.44 \log n$, and so we get that $h=O(\log n)$ for a height-balanced tree with height $h$ and $n$ nodes.

But, in asymptotic analysis, you can be "sloppy" and ignore constants, and it suffices to use the fact that $N\_{h-1}+1 \> N\_{h-2}$ to get that $N\_h \ge N\_{h-1}+N\_{h-2}+1 \> N\_{h-2}+N\_{h-2}$. Thus, we have $N\_h \> 2N\_{h-2}$. This means the terms of the sequence $N\_1, N\_2,\ldots$ grow fast enough that they at least double every two terms: $N\_3 \> 2N\_1$, $N\_5 \> 2N\_3 \> 4N\_1$, and in general, $N\_h \> N\_1 2^{h/2} = N\_1 (\sqrt{2})^h$. This implies that $h \< 2 \log n$, and so $h = O(\log n)$.

In general, to show $h=O(\log n)$ for a height-balanced tree, it suffices to show that the number of nodes $n$ grows exponentially with $h$. The crude analysis given above is good enough to obtain this result.
> 1 votes

---
Tags: recursion, binary-trees, subtree
---


# Question
Title: Why is $a^{\log_b n}$ the same as $n^{\log_b a}$?
I was watching video *Lec 2 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005*, where professor Erik Demaine said that $a^{\log\_b n}$ is the same as $n^{\log\_b a}$. Can someone please explain me why bringing "the $n$ downstairs" and "the $a$ upstairs" is possible?

# Answer
Take $\log\_b$, and you get $\log\_b n \cdot \log\_b a$ on both sides.
> 3 votes

# Answer
We can say some number $a = b^{\log\_b(a)}$, because $\log\_b(a)$ tells us to how much power we need to raise $x$ to get $a$ and then we actually raise it to get $a$.

Then, $$a^k = (b^{\log\_b(a)})^k = b^{k\log\_b(a)}$$

If $k = \log\_b(n)$, then $$a^{\log\_b(n)} = b^{\log\_b(n)\log\_b(a)}$$

Notice that $n = b^{\log\_b(n)}$, then:

$$a^{\log\_b(n)} = (b^{\log\_b(n)})^{\log\_b(a)} = n^{\log\_b(a)}$$ $$a^{\log\_b(n)} = n^{\log\_b(a)}$$
> 3 votes

# Answer
$$p^{\log(q)}=e^{\log(p)\log(q)}=q^{\log(p)}$$ holds (also for other bases).
> 1 votes

# Answer
The first result that will be useful is $\ln x^r = r \ln x$, where $\ln$ is the natural logarithm. When the base of the logarithm changes to a different number $a$, the logarithm can be rewritten as a ratio natural logarithms: $\log\_a x = \frac{\ln x}{\ln a}$. This can be proved by starting with $y=\log\_a x$, or its equivalent equation $x=a^y$ and taking the natural logarithm of both sides. We get $\ln x = \ln a^y$, and applying the first result above gives $\ln x=y \ln a$, from which we get $y = \frac{\ln x}{\ln a}$, i.e. that $\log\_a x = \frac{\ln x}{\ln a}$.

To show that $a^{\log\_b n}$ and $n^{\log\_b a}$ are equal, we show their natural logarithms are equal. After taking logarithms, we can apply the first result above. We get that the logarithm of the first expression is $\log\_b n \ln a = \frac{\ln n }{\ln b} \ln a$. The logarithm of the second expression is $\log\_b a \ln n = \frac{\ln a }{\ln b} \ln n$. These two ratios are both equal to $\frac{\ln a \ln n}{\ln b}$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Is $\frac{opt}{c}(1-\epsilon)$ for some constant c >0 considered a PTAS?
So I am studying PTAS algorithms. For a maximazation problem the difinition says that an algorithm that has value A , is a ptas if :
$A \geq opt(1-\epsilon) \\; ,\forall \epsilon \> 0$
(and I guess also $\epsilon \< 1$ (?) )

Obviously for any constant $c\>0 : opt(1-\epsilon) \geq \frac{opt}{c}(1-\epsilon)$
So when I proved : $A \geq \frac{opt}{c}(1-\epsilon)$ I proved somethhing weaker.
Can this still be consired a ptas algorithm or the definition strictly wants the approximation factor for maximazation to be at least $(1-\epsilon)$

# Answer
> 1 votes
The condition is trivially true for $\epsilon \ge 1$, so you don't need to require that.

That said, the condition $A \ge \frac{\text{opt}}{c} \cdot (1-\varepsilon) \\; \forall \varepsilon \>0$ is equivalent to $A \ge \text{opt} \cdot (1-\varepsilon') \\; \forall \varepsilon' \> \frac{c-1}{c}$ since we can relate $\varepsilon$ and $\varepsilon'$ as follows: $\varepsilon' = (c-1)/c+ \varepsilon/c$.

You must have $c\>1$ (otherwise you either fall back to the original definition, or no algorithm can meet the condition), which means that $\frac{c-1}{c} \> 0$. Therefore this doesn't meet the definition of PTAS.

---
Tags: complexity-theory, algorithm-analysis, approximation
---


# Question
Title: Finding Median value given a tuple (value, frequency) in O(n) worst case time complexity
> An accountant in a big firm would like to find the median of the salaries of all employees. The data they received is a list of size n containing the tuples $\left\\{s\_{i\ },f\_{i\ }\right\\}\_{i=1}^{n}$, where the number $s\_i$ is the salary and the integer $f\_i$ is the number of employees that got salary $s\_i$ in the firm.
>
> Suggest an algorithm that gets the list as input and returns the median salary of the employees at the firm in time O(n) in the worst case, and justify why this is the running time of your algorithm. For example for the input (8000, 4),(20000, 1),(10000, 2) the output should be 8000 since the full, sorted list of salaries is: 8000, 8000, 8000, 8000, 10000, 10000, 20000. Remark: $\sum\_{ }^{ }f\_{i\ }$ (i.e. the number of employees) may be way bigger than n so you are not expected to write the expanded list of salaries.

Hi, I was given this question and was stuck on it for a while. It seems no matter what I try to do I will exceed the $O(n)$ worst time restriction.. The direction I was going with is to somehow try to unzip the tuples into a list and use a simple run of $MedianOfMedians$ algorithm to find the median, but as the question states, we can't just create a single list of all salaries as the size of the new list will exceed $n$. I feel like it has something to do with manipulation the values according to the total number of employees or maximum salary, etc, but no matter what kind of value manipulation I've tried it seems to fail.

I'm a bit lost as to how I am supposed to solve this, considering we've only learned very basic algorithms so far, such as selection and linear sorting algorithms in addition to some basic data strcuture such as trees, heaps, etc..

There is probably some trick involved which I am not getting, but what is it?

# Answer
> 4 votes
I think you can still use the linear time selection algorithm (median of medians) here. Let's call this algorithm $Select$ and let the median position be $m$, which is initially equal to $n/2$.Recall that the algorithm has 3 phases:

1. Group by 5 and select median of each group
2. Choose partition element $p$, by applying $Select$ to find the median of the medians.
3. Partition the elements around $p$. If $p$ is the true median, return it otherwise recursively apply $Select$ to one side of the partition.

Observe first that it is possible that the frequency of each tuple is 1, which reduces the problem to the original median selection.

Below we describe $Select'$ a modification of $Select$ that allows values with frequencies greater than 1:

1. Group by 5 and select median of each group based only on the value, ignoring the frequency.
2. Choose $p$ by applying the $Select$ algorithm to find the median of the medians. Since the original $Select$ algorithm is being used, the frequencies of the medians are not considered in the selection.
3. Partition the tuples around $p$. During the partition, sum-up the frequency of each tuple that ends up on the left side of $p$. Call this sum $l$. If $l \geq m$, recursively apply $Select'$ to the left partition. Else, if ($l + p.frequency) \geq m$, then $p$ is the median and we are done. Otherwise, update $m$ to $m - (l+p.frequency)$ and recursively apply $Select', $ on the right partition.

The reason why we ignore the frequency on steps 1 and 2, is to guarantee that on step 3, the number of elements removed after partition is similar to what is expected from the original $Select$ algorithm. The additional step of accumulating the frequencies to get $l$, increases the running time of the partition step by a constant factor only, hence it has no significant effect on the asymptotic running-time of the algorithm. Therefore, the running-time of $Select'$ is also $O(n) $.

# Answer
> 1 votes
If the pairs are given ordered by increasing salary, it suffices to compute the prefix sum of the frequencies $F\_k:=\sum\_{i=1}^k f\_k$ and find the sum closest to the half of the total.

If the pairs are not ordered, you are stuck.

---
Tags: time-complexity, sorting, selection-problem
---


# Question
Title: When is a grammar ambiguous or When is a grammar not ambiguous?
I was looking at an example of grammar from the website: grammer example

which is as follows:

S → aB / bA

S → aS / bAA / a

B → bS / aBB / b

I believe they forgot to write: A -\> a

Next, we are going to derive the string: aaabbabbba

I did it by myself and found the following:

Left derivation:

S -\> aB

-\> aaBB

-\> aaaBBB

-\> aaabBB

-\> aaabbB

-\> aaabbaBB

-\> aaabbabB

-\> aaabbabbS

-\> aaabbabbbA

-\> aaabbabbba

Right Most Derivation:

S -\> aB

-\> aaBB

-\> aaBbS

-\> aaBbbA

-\> aaBbba

-\> aaaBBbba

-\> aaaBbbba

-\> aaabSbbba

-\> aaabbAbbba

-\> aaabbabbba

And the left most derivation tree:

Right most derivation tree:

Now, if the website says the grammer is "unambiguous" then shouldn't the parse trees of left most derivation and right most derivation be the same? am i correct or is the website correct?

Also, when is a grammer ambiguous? I feel it is when:

(1) It has more than 1 left most derivation tree for the same string

(2) It has more than 1 right most derivation tree for the same string

(3) It has different left most and right most derivation tree for the same string

In the above rules i mean the shape of the parse / derivation tree, not the actual substitution

Am i correct?

# Answer
That grammar as presented (with the addition of the production $A\to a$) is certainly ambiguous, regardless of what the site you copied it from says. Your work demonstrates that, and it can easily be verified using a parser generator or CFG analyzer. (See below for what they probably meant.)

A grammar is ambiguous if it has more than one leftmost derivations for a sentence. That's equivalent to saying that it had more than one rightmost derivation for the same sentence because the is a one-to-one correspondence between leftmost and rightmost derivations. Every leftmost derivation can be mechanically transformed into a unique rightmost derivation, and vice versa. (And that transformation preserves parse trees.)

You might find it useful to do that for your derivations; you will see that you can find two leftmost derivations and two corresponding rightmost derivations. (And two parse trees, which you already drew.)

I think you did not correctly guess the typo in that webpage. It's not that one production for $A$ is missing. Rather, the second line of the grammar should have read: $$A\to a S \mid b A A \mid a$$ instead of $S\to…$. You might also want to try using that version of the grammar.
> 1 votes

---
Tags: automata, context-free, formal-grammars, theory, derivation
---


# Question
Title: Maximum subarray sum of given length range
Can anyone please help me solve this better than $O(|a-b| \cdot n)$?

Given an array of both negative and positive numbers, we want to find the maximum sum of the elements in contiguous subarray having a length **between** $a$ and $b$.

Example

Input:

8 1 2

-1 13 -2 5 13 -5 2 2

Output: 18

Here a = 1 , b = 2

Although Maximum sum is 29, Max sum of length between \[1-2\] is 18

Prob : https://cses.fi/problemset/task/1644

# Answer
> 2 votes
This answer explains an $O(n)$-time algorithm.

### Basic Ideas

The ideas are classic.

* "Sum of the elements in subarray" -- prefix sums.
* "Length between `a`and `b`" -- window of size `b-a+1`.
* "Maximum" -- maximum queue for the window

We will compute the array of prefix sums `prefix_sums` first. Then for each index `s`, we will compute the maximum elements of `prefix_sums[s+a..s+b]`. The difference between `prefix_sum[s]` and that maximum element is the maximum sum of a subarray that starts at index `s + 1` and of length between `a` and `b`.

To compute the maximum element of `prefix_sums[s+a..s+b]`, we will keep a dequeue of elements like `(prefix_sums[i], i)`, decreasing in the `pref_sums[i]` part but increasing in the `i` part. When `s` is increased by 1, we will remove `(prefix_sums[s+a-1], s+a-1)` from the front of the dequeue if that element is in the dequeue, as well as append `(prefix_sums[s+b], s+b)` to the dequeue, popping out all previous elements with no greater prefix\_sum-part from the back of the dequeue. Hence the maximum element of the queue will always be at its very front element.

### Implementation in Python

```
from collections import deque
from itertools import accumulate

# 1 <= a <= b <= n
n, a, b = map(int, input().split(" "))
prefix_sums = list(accumulate(map(int, input().split(" ")), initial=0))

d = b - a
# elements like `(pre_sums[i], i)`,  decreasing in the
# `pref_sums[i]` part but increasing in the `i` part.
deq = deque()
answer = -1 << 63
for i in range(a, n + d + 1):
    if deq and deq[0][1] < i - d:
        deq.popleft()
    if i <= n:
        while deq and deq[-1][0] <= prefix_sums[i]:
            deq.pop()
        deq.append((prefix_sums[i], i))
    if i >= b:
        # deq[0][0] is the maximum elements of pre_sums[i-d..min(n, i)]
        answer = max(answer, deq[0][0] - prefix_sums[i - b])

print(answer)

```

#### Complexity analysis

Prefix sums is computed in $O(n)$ time.
The outer `for` loop executes less than $2n$ iterations. Each prefix sum will be put into the dequeue once and popped out at most once.
Hence, the algorithm runs in $O(n)$ time. $O(n)$-space is used; however, it can be reduced to $O(b-a+1)$ easily if input and processing are done by streaming.

# Answer
> 2 votes
By augmenting an AVL tree you can implement a data structure that maintains a multi-set $S$ under the following $O(\log |S|)$-time operations:

* Add($S, x$): Add number $x$ to $S$.
* Offset($S, x$): Increase the value of all element in $S$ by number $x$.
* Delete($S,x$): Delete (one copy of) number $x$ from $S$
* Max($S$): Return the maximum element of $S$.

Let $n$ be the number of elements in the input array, and call $a\_i$ the $i$-th element. Let $\beta$ be a parameter, and define $\sigma\_i$ as the maximum sum of the elements of a subarray that ends with $a\_i$ and has length between $1$ and $\beta$. You can compute all values $\sigma\_1, \dots, \sigma\_n$ in time $O(n \log(1+\beta))$ as follows:

* Initialize $S=\emptyset$, and $\ell=0$.
* For $i=1, \dots,n$:
    + If $i \> \beta$:
        - Delete($S$, $\ell$)
        - Decrement $\ell$ by $a\_{i-\beta}$
    + Offset($S, a\_i$)
    + Add($S, a\_i$)
    + Increment $\ell$ by $a\_i$
    + Set $\sigma\_i$ to Max($S$)

At the end of the generic $i$-th iteration, the multi-set $S$ contains the sum of the elements of the contiguous (non-empty) subarrays ending with $a\_i$ and having length at most $\beta$, while $\ell$ is the sum of the elements in the subarray ending with $a\_i$ and having length $\min\\{\beta,i\\}$.

To solve your problem it suffices to compute all $\sigma\_i$ for $\beta=b-a+1$ in time $O(\log (b-a+1))$ and return: $$ \max\_{i=a,\dots,n} \left\\{ \sigma\_{i-a+1} + \sum\_{j=i-a+2}^{i} a\_j \right\\}. $$ Notice that, once the values $\sigma\_i$ are known, this latter maximum can be evaluated in time $O(n)$ (since each sum can be found in constant time by updating the value of the previous sum). The overall time complexity is therefore $O(n \log (b-a+1))$.

---
Tags: arrays, greedy-algorithms, maximum-subarray
---