# Question
Title: How to find a lambda term to complete a function?
I tried to complete this exercise but i stopped... Defining a $ \lambda $-term M such that: $$(\<M,u\>)\<M,v\> \\: \simeq\_{\beta} \\: \<M,u\>$$

I chose $M=\lambda m \lambda a \lambda b \lambda p \\,((p)m)b \\:$ then i have to find a representation T of a function using M that value **true** if the sequence is empty and **false** if it's not. A sequence is defined as: $$\[\]=\lambda x\_0\lambda x\_1 \lambda z z \\ \[b\]=\lambda x\_0 \lambda x\_1 \lambda z (z) x\_b\\ \[b\_1 b\_2\]=\lambda x\_0 \lambda x\_1 \lambda z ((z)x\_{b\_1})x\_{b\_2} \\ .\\\. \\ . \\ \[b\_1 .. b\_n\]= \lambda x\_0 \lambda x\_1 \lambda z (...((z) x\_{b\_1})x\_{b\_2}...)x\_{b\_n} $$ so the sequence of exercise is : $$\[01101\]= \lambda x\_0 \lambda x\_1 \lambda z (((((z)x\_0)x\_1)x\_1)x\_0)x\_1 $$ For example T need to be: $(T)\[01101\] \simeq\_{\beta}$ **false** while $ (T) \[\]\simeq\_{\beta}$ **true**. I really find that difficult. How i can do that?

edit.

$true=λxλyx$ and $false=λxλyy$

# Answer
We can remove the dependence on what the values stored in the sequences are by assuming that we pass "the same thing" as the first two arguments. Regardless of what $b\_1, b\_2, b\_3$ are:

$$(\[b\_1b\_2b\_3\]\\,x)\\,x = \lambda f. ((f\\,x)\\,x)\\,x$$

This gives you an effective way to tell the difference between an empty sequence and a non-empty sequence :

$$((\[\]\left\<M,u\right\>)\left\<M,u\right\>)\\,(\lambda x. x) = \lambda x. x$$ $$((\[b\_1\]\left\<M,u\right\>)\left\<M,u\right\>)\\,(\lambda x. x) = \left\<M,u\right\>$$ $$((\[b\_1b\_2\]\left\<M,u\right\>)\left\<M,u\right\>)\\,(\lambda x. x) = \left\<M,u\right\>$$ $$((\[b\_1b\_2b\_3\]\left\<M,u\right\>)\left\<M,u\right\>)\\,(\lambda x. x) = \left\<M,u\right\>$$

So if $s$ is a sequence, consider this:

$$((((s\left\<M,u\right\>) \left\<M,u\right\>) (\lambda x. x))\\,\hbox{false}$$

What does it reduce to if $s$ is empty? What does it reduce to if it's non-empty?
> 1 votes

---
Tags: lambda-calculus
---


title: Maximum Subsequence Sum : Mark Weiss:

text:
# Question
Title: Maximum Subsequence Sum : Mark Weiss:
In the highlighted part below how is Weiss concluding that the array starting at an arbitrary index "p" and ending at "j" can never be larger than the array starting at "i" and ending at "p-1"?

By his own example (the inner loop of algorithm 2 shown below) this is demonstrably false.

Let i = 0, and j = 3.

Let a\[ 0 \] = -14, a\[ 1 \] = -4, a\[ 2 \] = -2, a\[ 3 \] = -1.

If p = 2, the subsequence sum from "p" to "j" is clearly bigger than "i" to "p-1".

Even more concerning is Mr. Weiss seems to pull an assumption out of thin air ("j is the first index that causes the subsequence starting at index i to become negative") when nothing in the above could possibly imply that! Indeed, Weiss only mentions "detection" of the subsequence sum being negative between index "i" and "j", but never where the source of this could only occur. Where is this coming from?

Thanks for any help!

# Answer
I think you are confused about which algorithm he is describing. His description isn't for algorithm 2 but for algorithm 4, where an imaginary index `i` in reintroduced.

Let me write this algorithm with this index to make it clear to you:

```
maxSubSum(array a):
  maxSum = 0, thisSum = 0;
  i = 0;
  for j going from 0 to length(a)-1:
    thisSum += a[j];
    if thisSum > maxSum:
      maxSum = thisSum;
    else if thisSum < 0:
      i = j+1;
      thisSum = 0;
   return maxSum;

```

Now you can see that in this algorithm, whenever thisSum \< 0, then `j` is indeed the "first index that causes the subsequence starting at index `i` to become negative", and the rest of the claim follows. Notice in particular that the example you gave cannot occur with this algorithm (you will never have `i=0` and `j=3` in that case).
> 1 votes

---
Tags: algorithms, algorithm-analysis, subsequences, maximum-subarray
---


# Question
Title: Can the same machine word sometimes be data and sometimes be code?
I have a question about machine words. We have data and a code segment in the memory which is addressed. If we take a word from it and let's say it is a code (instruction), and another one is some data. Can we have a situation that some word is sometimes code and sometimes data?

# Answer
If your question is "can one and the same sequence of bits sometimes represent a machine instruction and sometimes represent data" then the answer is definitely yes.

If your question is "can one and the same location in memory sometimes hold a machine instruction and sometimes hold data" then the answer is it depends on the machine architecture. The Harvard architecture strictly segregates instruction memory and data memory into physically separate parts of the computer memory, with separate data buses. However, the Von Neumann has a single common memory which can hold either instructions or data at any location.

If your question is "can one and the same location in memory be treated sometimes as an instruction and sometimes as data by one and the same program" then the answer in a Von Neumann architecture is yes, in principle. However, this leads to the possibility of writing self-modifying code, which is considered undesirable because such code is difficult to maintain and is a security risk. Therefore all modern operating systems make sure that the programs they are running have a strict segregation between data and instructions, and cannot modify their own code. This is usually implemented within the operating system itself rather than at the physcial memory level.

Note, however, that the distinction between data and code still depends on context - what is data to one program may be code for another program. For example, the output of an assembler, which the assembler treats as data, will be treated as machine instructions when the assembled program is actually being run.
> 1 votes

# Answer
The von Neumann architecture (more or less what all current CPUs have as a ground model) specifically stores programs in memory, where they can be manipulated as data or executed. Your compiler does write instructions to be executed later. When loading the program into memory to be executed the instructions are handled as regular data to be copied from disk. Each time you copy a program for example, you are manipulating it as inert data.

Allowing a program to fiddle with it's own (or even other program's) instructions is clearly a sure recipe for a giant mess or grievous security issues. Modern CPUs handle protection bits as part of the virtual memory machinery, allowing the operating system to mark memory areas as read-only, read-write, or execute-only. Some stack smashing attacks targeting stack overflows work exactly by overwriting a memory area with data and later tricking the program to execute it as instructions.
> 0 votes

---
Tags: operating-systems, memory-access, memory-allocation
---


# Question
Title: LP - given m constraints for 2 variables find maximal radius of circle
Given $m$ constraints for 2 variables $x\_1,x\_2$ :

$d\_ix\_1 + e\_ix\_2 \leq b\_i$ for $i = 1,...m$

need to create a linear program that finds the maximal radius of a circle such that all the points inside the circle are in the feasible range of the above constraints. The circle can be located anywhere -- not necessarily centered at the origin.

so I know the formula for distance between some $(x,y)$ and some $ax +by + c = 0$

then I have tried -

* $Maximal$ $R$ s.t
* $d\_ix\_1 + e\_ix\_2 \leq b\_i$ for every $i$
* $R \leq |d\_ix\_1 + e\_ix\_2 - b\_i| / {\sqrt{{e\_i}^2 +{d\_i}^2}}$ for every $i$
* $R \geq 0$

I know the standard linear program doesn't get absolute value function but obviously we can just have 2 inequalities to get rid of it.

I'm not sure if this is the correct answer.

furthermore, is it possible that for some constraints if will force the radius to be 0?

# Answer
You're close to the solution, but aren't there yet. Your third inequality should look like this (no absolute values!):

$$d\_i x\_1 + e\_i x\_2 + \sqrt{{e\_i}^2 +{d\_i}^2}R \le b\_i$$

And yes, the maximal inner circle radius can be zero, and even more - this circle might not exist at all. Please see the following explanation to grasp that.

---

Let's use vector notation to simplify algebraic expressions:

$$a\_i=(d\_i,e\_i)$$ $$x=(x\_1,x\_2)$$

Then your constraints can be written using Dot Product:

$$a\_i \cdot x \le b\_i, i \in \[1,m\]$$

Let's denote the inner circle center $y$ and focus on the $i$-th constraint for now. Imagine a shortest segment, connecting the point $y$ and the line $a\_i \cdot x = b\_i$. It's easy to see that this segment will be perpendicular to this line and collinear with vector $a\_i$.

Let's find the point $z\_i$, lying on the segment above, with the distance from the point $y$ equal to the $R$ (radius of the inner circle). This point is given by the following vector expression:

$$z\_i = y + \frac{a\_i}{\lVert a\_i \rVert}R$$

Now we have to make sure that all the points $z\_i$ are located in correct halfplanes:

$$a\_i \cdot z\_i \le b\_i, i \in \[1,m\]$$

Simplifying these equations using the expression for the point $z\_i$ (above) we'll get:

$$a\_i \cdot y + \lVert a\_i \rVert R \le b\_i, i \in \[1,m\]$$

So, now you have an LP problem with three variables $(y\_1, y\_2, R)$, $m$ constraints (above), an additional constraint $R \ge 0$ and optimization function, which is simply $R$.

Please see the Chebyshev Center page for more information, in particular the reference #4.
> 2 votes

# Answer
Just take the minimum of the radii you get for each restriction.

But that presumes a circle centered at the origin, and all restrictions cutting positive $x$ and $y$ axes. If that isn't the case, you'd have to clarify further.
> 0 votes

---
Tags: linear-programming
---


# Question
Title: Do we understand when metaheuristics are optimal? (gradient descent & simulated annealing in particular)
Gradient descent sometimes works better than simulated annealing and vice versa.

Are there conditions under which we can prove that, given perhaps a restriction on the set of allowed algorithms, one of these is optimal for solving an optimization problem?

I am particularly interested in those two examples, but in general interested in this question for metaheuristics for search and optimization problems.

(The no free lunch theorems show that (for certain problem statements) this is not possible in general, since for a uniform diatribution on problems, there usually isnt an optimal algorithm. However it might hold for special cases.)

# Answer
In general, we definitely don't know this. In fact, it's practically always so that a-priori, we don't know how well a particular metaheuristic performs (let alone proving optimality) on a given instance (or family of instances) until we try.

It should also be noted that we usually go for metaheuristics only when the problem is so hard it seems unlikely it admits an algorithm that is always fast and correct (i.e., the problem is NP-hard). Put differently, when a problem is solvable in polynomial-time with some other methods, we don't even bother considering metaheuristics.

So if a metaheuristic is always optimal (and assuming it always runs in polynomial time), then the problem must be in P (assuming that P is not equal to NP). Of course, no one is stopping you from taking a problem that is known to be in P and applying a metaheuristic on that, but that's probably not that useful anymore.
> 1 votes

---
Tags: algorithms, optimization, search-algorithms, heuristics, search-problem
---


# Question
Title: Pushdown automaton from given code for parsing a while statement
I was preparing for my exam and have some questions that can possibly come on the test. There is a task to make pushdown automata from a given code:

```
void compile_while() {
  // while ( expression )
  if (symbol == SYM_WHILE) {
    get_symbol();

    if (symbol == SYM_LPARENTHESIS) {
      get_symbol();

      compile_expression();

      if (symbol == SYM_RPARENTHESIS) {
        get_symbol();

        // zero or more statements: { statement }
        if (symbol == SYM_LBRACE) {
          get_symbol();

          while (is_not_rbrace_or_eof())
            compile_statement();

          if (symbol == SYM_RBRACE)
            get_symbol();
          else {
            syntax_error_symbol();

            exit(EXITCODE_PARSERERROR);
          }
        } else
          // only one statement without {}
          compile_statement();
      } else
        syntax_error_symbol();
    } else
      syntax_error_symbol();
  } else
    syntax_error_symbol();
}

```

First of all, I don't understand why we need to construct PDA for it because we can do it without stack too and second, I don't understand how the pushdown automata for it would look like.

Can someone help me to understand this task and show me how the PDA for it looks like?

# Answer
> 1 votes
What you write is a snippet out of a recursive descent parser, one way of writing a program that parses a context free language. It is modelled on a PDA, specifically a LL(1) one. The stack is implicit in the recursive calls your parser does. Recursive descent is popular as it easy to write by hand (some tricks are needed to handle ambiguous constructs, like nested `if ... then ... else` and expressions, which naturally are represented by left-recursive grammars, but they are well-known) and requires no theory. More powerful parsing methods (like LALR or canonical LR) are too complex to do by hand for realistic grammars (in LL(1)/recursive descent, you can work one production at a time, other methods require considering a much larger part of the grammar). If you look at a typical (LA)LR parser generator's output (ask e.g. for `--report=all` for bison or `-r`for byacc to get a text description, or `-g` for any of them to get a graphical depiction of the PDA).

Tl;dr: Undestanding PDAs and their relation to the grammar is
useful, but not essential to use the technology.

---
Tags: formal-languages, automata, pushdown-automata, parsers
---


# Question
Title: $O(n \log n)$ algorithm to find next interval that is also disjoint
Say there are some intervals $\\{1, \ldots ,n\\}$ with starting times and ending times, and they're sorted in order of starting time from first to last in an array intervals$\[\]$. Now I want create an array next$\[\]$ such that next$\[i\]$ is the interval after interval $i$ whose starting time is as close to $i$'s ending time as possible. The notes I'm reading says it is possible to do this in $n \log n$, but I don't see how. The fastest algorithm I have come up with would iterate over intervals$\[\]$, and in each step "look ahead" until it finds a starting time after $i$'s ending time. The worst possible scenario would be when all the intervals are bunched together (none are disjoint), in which case you would have to iterate over all of $i + 1, i + 2, \ldots ,n$ at each step $i$. This would be $O(n^2)$ because the total number of checks would be $0 + 1 + \cdots + n-1$ since we make $n-1$ for first the first number, $n-2$ for the second, etc. Am I missing a way to cut it down to $O(n \log n)$?

# Answer
For interval i, you can binary search end\[i\] among the sorted array begin\[\]. Each binary search takes log n time.
> 4 votes

---
Tags: algorithms
---


# Question
Title: Can there be a language not Context free but still PDA acceptable?
Let the input alphabet be $Σ = \\{1,x,=\\}$
Let the stack alphabet be $\tau = \\{1,\\$\\}$ where $\\$$ is the initial stack symbol.

Let,
$q\_0$ be the initial state of the PDA,
$q\_f$ be the final state of PDA,
I can define a transition function for PDA like this.

$(q\_0,1,\\$)\rightarrow(\\$1,q\_1)$
$(q\_1,1,1)\rightarrow(1,q\_1)$
$(q\_1,x,1)\rightarrow(1,q\_2)$
$(q\_2,1,1)\rightarrow(1,q\_2)$
$(q\_2,=,1)\rightarrow(1,q\_3)$
$(q\_3,1,1)\rightarrow(\epsilon,q\_3)$
$(q\_3,\epsilon,\\$)\rightarrow(\\$,q\_f)$

Now the PDA can recognize language $L = \\{1^m x 1^n = 1^{mn}\\}$ But According to https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/lectures/18/Small18.pdf Slide 24 this language is not Context Free.

Assume that I am quite beginner in TOC.

# Answer
It is proven in your nearby language theory textbook (like Hopcroft, Motwani, Ullman "Introduction to automata theory, languages, and computation" (3rd edition, Pearson) that the languages accepted by (nondeterministic) PDAs are exactly the context free languages (generated by context free grammars).
> 1 votes

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


title: Round Robin time slice(quantum time)

text:
# Question
Title: Round Robin time slice(quantum time)
In all books about this topic, I read that there is a rule of thumb is that 80% of the process execution time is lower than time slice. But how do I calculate this value? I looked at every article possible and I found like nothing. Can someone help me understand this topic?

I know that there is a topic with this question click here. I have the exact same problem, but the answer from there isn't clear to me.

Thanks in advance.

# Answer
The end of a time slice is costly (need to interrupt the running program, switch over to the kernel, stash away the running process context, restarting another process means loading it's context, cache contents of the processor are now useless and have to be reloaded). You want to do this hopefully only when forced (the running program does a system call, which forces a context switch anyway; a high-priority interruption arrives), but on the other hand you don't want any process to just monopolize the system by never yielding. So sometimes (i.e., by time slice end) you will force it. The "80%" rule of thumb is just that, it works (most of the time, for most workloads, and probably makes very little practical difference if it is 60% or 90%).

Take a look at e.g. Pabla's discussion of the Completely fair scheduler in Linux to get a feel of the problems to be solved. The history of Linux' schedulers is quite enlightening (and people have been reported to be sucked into hacking it, never to be seen again...)
> 2 votes

---
Tags: process-scheduling
---


# Question
Title: Round Robin Scheduling: No process in Ready Queue
First post here, glad I found this exchange. I am in my Operating Systems course at university learning process scheduling. In my homework assignment we have to fill out a simulated scheduling chart along with the corresponding Gant chart. The arrival time of the first process is at time 0, and it's service time is 5 seconds. The second process doesn't arrive until time 7. The time quantum is 6. How do I fill out the gant chart if nothing is in the queue?

# Answer
your first process will take time only upto 5 seconds as its service time is only upto 5 seconds and then you have to keep blank space between 5-7 and then your next process arriving at 7 would be processed,i think.
> 1 votes

# Answer
All operating systems have some sort of idle loop, twiddling it's thumbs if there is nothing else to do. If there are no ready tasks (no user tasks, and no kernel-internal tasks either), just waste time (today perhaps even power down the processor and schedule to wake up in a short while if nothing else happens).
> 0 votes

---
Tags: operating-systems, scheduling, process-scheduling
---


# Question
Title: How does the OS determine the CPU burst time of a process?
This question is related to OS. After having solved many problems in CPU scheduling I was wondering how does the CPU know the burst time of all the processes in the main memory before executing them?

Selecting a process among a pool of processes using some scheduling algorithm is done based on CPU burst of each process(SJF,SRTF etc). And I'm aware of the predictor formula. And yet I'm trying to get the whole picture as clearly as possible. How does that equation help choose which process is to be executed next?

# Answer
> 6 votes
Bursts values are needed for Shortest Job First (SJF) or Shortest Run Time First (SRTF) type scheduling. The burst is an *estimate* based on an initial starting default burst value and actual historical run values. A process is assigned a default estimated value for its first burst and after it has run the actual burst is known. The last estimated burst and the last actual burst are averaged to provide the process's next estimated burst. This next estimated value is used for the next scheduling choice. Assuming the actual bursts are roughly equal, as the process runs it's estimated burst will more closely approximate the actual value since the averaging process moves the estimated burst towards the actual value. Of course if the actual burst for the process is somewhat random then the estimated burst will end up being closer to a median of the long and short burst times for the process. As processes continue to run they will tend to move into either the long burst group of processes or the short burst group.

For example, when a process is created there is no historical information so it's burst value is set to a default of 10. If the process always has an actual burst time of 20, then after the first scheduling period the estimated burst value assigned to the process will be (10+20)/2 = 15. The second run it will get (15+20)/2 = 17.5 estimated burst and so on. Each pass will move the estimate closer to the actual time required.

I probably wouldn't choose this method for scheduling a general purpose system, preferring instead a combined priority/quantum scheduling arrangement. With SJF, a busy system with many short burst jobs could starve the longer burst CPU intensive jobs. And if a job had short previous run times then got into a compute intensive loop, even other "short" jobs could wait excessive times before getting CPU time. It can work well for systems that aren't excessively CPU bound and for systems where the process run times are reasonably consistent.

In a priority/quantum round robin based systems, jobs with the same priority are given at lease *some* CPU time, but will relinquish the CPU to other equal priority processes when it's quantum ends and will wait for its turn to come around again. If a higher priority process needs CPU time, it can preempt lower priority processes. Various priority boosting methods can prevent complete starvation of low priority jobs on busy systems.

# Answer
> 1 votes
For a discussion of scheduling algorithms in a *real* kernel (not the idealized simplifications so dear to operating system text authors) check out Pabla's "Completely fair scheduler".

---
Tags: operating-systems, process-scheduling
---


title: Two peaks finding algorithm

text:
# Question
Title: Two peaks finding algorithm
We are given an array of length N with exactly 2 peaks (a peak is an element which is no less than the left and right neighbors). Is there an algorithm to compute those peaks faster than *O(N)*, maybe similar with the single peak finding in *O(log N)*?

# Answer
> 2 votes
No. Any algorithm to locate those two peaks will take $\Omega(N)$ time, assuming that the only operation allowed is to compare two elements in the array, i.e., the comparison mode.

Otherwise, suppose algorithm $A$ do not need that much time. Let $arr\[0\], arr\[1\], \cdots, arr\[N-1\]$ be the given array. Then for some $N$ large enough, $A$ will have only checked at most $N-3$ elements before it has terminated. Suppose for all comparisons that have done by $A$, it will be found that $arr\[i\] \< arr\[j\]$ where $i\<j$.

Let $arr\[a\], arr\[b\], arr\[c\]$ be three elements that have not been checked yet, $a\<b\<c$. Whatever $A$ have done, the two peaks could be $\\{arr\[a\], arr\[N-1\]\\}$. They can be $\\{arr\[b\], arr\[N-1\]\\}$ as well. Since $A$ cannot distinguish these two cases, $A$ cannot possibly have determined the two peaks.

**Exercise.** (less than one minute) Modify the above argument so that it becomes valid in the case when a peak must have both left neighbor and right neighbor.

---
Tags: algorithms, divide-and-conquer
---


# Question
Title: Maximum set packing and minimum set cover duality
I read that the maximum set packing and the minimum set cover problems are dual of each other when formulated as linear programming problems. By the strong duality theorem, the optimal solution to the primal and dual LP problems should have the same value.

However, consider a universe $U = \\{1, 2, 3, 4, 5\\}$ and a collection of sets: $S = \\{ \\{1, 2, 3\\}, \\{3, 4, 5\\}, \\{1\\}, \\{2\\}, \\{3\\}\\}$. From what I understand, a minimum set cover would consist of the first 2 sets in set $S$, while the maximum set packing consists of the last 3 sets. These solutions aren't in accordance with the statement of the strong duality theorem.

Given that, I don't understand how the 2 problems can be dual of each other. What am I missing?

Thank you very much.

# Answer
> 1 votes
There is no contradiction. The strong duality theorem applies to the *fractional* linear programming formulations of the problems, where one is allowed to set fractional values for the variables, but these formulations are only relaxations of the two original problems. Strong duality does not apply to the *integer* linear programming formulations (as your example indeed shows).

# Answer
> 1 votes
Let $P$ be the LP relaxation for minimum set cover: $$\begin{align} \min \sum\_{S \in \mathcal{S}} x\_Sc(S) & \\ \sum\_{S: \\;e \in S} x\_S \geq 1 &\quad\quad \forall e\in U \\ x\_S \geq 0 &\quad\quad S \in \mathcal{S}\\ \end{align}$$ and $D$ be the dual LP which corresponds to the linear relaxation for maximum set packing: $$\begin{align} \max \sum\_{e \in \mathcal{U}} y\_e & \\ \sum\_{e: \\;e \in S} y\_e \leq c(S) &\quad\quad \forall S\in \mathcal{S} \\ y\_e \geq 0 &\quad\quad e \in \mathcal{U}\\ \end{align}$$ The strong duality theorem states that the optimal value of $P$ is the same as the optimum value of $D$. However, the solutions for the LPs aren't necessarily integral as in the case that you showed. Let $z^\*$ be the value of the optimal solution to $P$, it can be shown that $OPT\_I\leq H\_nz^\*$ where $OPT\_I$ is the value for the optimal integral solution of $P$.

The worst case bound of the ratio $\frac{OPT\_I}{z^\*}$ is known as the integrality gap of an LP (note that the ratio is flipped for a maximization problem).

See here for a discussion on integrality gaps and here for an analysis of the set cover primal/dual.

# Answer
> 0 votes
The dual of Set Cover is not Set Packing (as defined in Wikipedia). In Set Cover you choose sets, e.g. you have a binary variable for each set. Thus, the dual problem can't have a variable for each set as well. Instead, you have a dual variable for each element that represents how much of that element you want to pack without overpacking the sets that contain this element (see the dual LP formulation below).

$$\min \sum\_{e \in U} y\_e$$ $$ s.t. \sum\_{e: e \in s} y\_e \le \text{cost}(s) \quad\quad (s \in S)$$ $$ y\_e \ge 0 \quad\quad (e \in U)$$

# Answer
> -1 votes
The actual formulation of the dual of the set-packing problem is:

$$\min \sum\_{e \in U} y\_e$$ $$ s.t. $$ $$ \sum\_{e: e \in s} y\_e \ge w\_s \quad\quad (s \in S)$$ $$ y\_e \ge 0 \quad\quad (e \in U)$$

(Zideon's formulation is wrong, not enough reputation to reply him...)

I got the same confusion with that wiki statement some weeks ago. I will correct that article once I get the time to do it.

---
Tags: algorithms, linear-programming
---


# Question
Title: Finding often repeating substrings in multiple strings
I'm currently looking for an algorithm to find often repeating substrings in one or multiple strings. However, my search until now was not really successful. I try to illustrate the problem on the following example strings:

```
S1: ABCCCDxxxxxxABCCCDxxxxABCCCD
S2: xxxxxABCCCDxxxxABCCCDxxxxxxx
...
S10: xxABCCCDxxxxxxxxABCCCDxxxxxx

```

In the given example strings S1, S2 up to S10, the substring ABCCCD occurs multiple times, making it an often repeating substring, and thus interesting for me. However, when trying to find an algorithm that helps with finding such substrings, I often end up at the longest common substring problem, which would help me find the longest common substring between S1 and S2, however, it would ignore the repetition of the substring.

Does an algorithm exist, that can help me with this problem? Additionally, it would be quite interesting to set additional constraints, such "substring must occur at least n times" or "substring must be at least n characters" long.

# Answer
> 2 votes
Let's say you are looking for substrings that occur at least $c$ times in each string and have length at least $k$. Furthermore, lets say we're looking for *maximally* repeated substrings i.e. if $R$ is our solution set of substrings, there exists no pair $r\_i, r\_j\in R$ such that $r\_i$ is a substring of $r\_j$.

# Offline option

Construct a generalized suffix tree from all input strings. Any node at depth at least $k$ that has at least $c$ leaves from each input string (i.e. at least $c$ $\\$\_1$ leaves, at least $c$ $\\$\_2$ leaves and so on) is $blue$ and each $blue$ node with no $blue$ children is also $red$. The set of substrings represented by $red$ nodes is the set of maximally repeated substrings. This runs in time $O(mn)$ where you have $n$ input strings of length at most $m$.

# Answer
> 1 votes
Why not use a sliding window type of algorithm? Let's say you are looking for the most common substring(s) of size exactly $k$. Slide a window of size $k$ on each of your strings and use a dictionary to count how many times each substring of size $k$ appears. At the end, iterate over the dictionary and pick the substring with the highest count.

---
Tags: algorithms, substrings
---


# Question
Title: Is there a language which has a polynomial length certificate but not known to have a polynomial time verifier?
The question came to my mind while studying the NP definition. Do we know any such languages?

# Answer
For any instance of a problem, take the instance itself as the certificate. Linear size, verifiable in polynomial time for problems in P, not known for problems in NP.
> 1 votes

# Answer
Every NEXPTIME complete language has a certificate of length 0 that can be checked in time $2^{2^{n^{O(1)}}}$, but does not have polynomial length certificate that can be checked in polynomial time.
> 0 votes

---
Tags: complexity-theory, np
---


# Question
Title: How to prove the language of suffixes of a regular language is still regular?
Prove that if $ L \subseteq \Sigma^\star$ is regular, $L'$ is also regular where

$$ L' = \\{w\mid{uw \in L \mbox{ for some string }u \in \Sigma^\star}\\}$$

I'm new learning formal language and haven't proved stuff like this. But I'm sharing my thoughts here to make sure I'm on the right track. The first idea came to my mind is using close properties. Since $u$$w$ $\in$ L and $u$ $\in$ $\Sigma^\star$ so we know L is also regular. $L'$ is the concatenation of two regular languages. The regular languages are closed under concatenation thus $L'$ is also regular.

Any feedback or suggestions?

# Answer
> 0 votes
Given a DFA for $L$, let $\mathcal{Q}$ be the set of states that are reachable from the start state. Construct an NFA-$\epsilon$ by adding a new start state $S$ and adding an $\epsilon$-transition from $S$ to each state in $\mathcal{Q}$. You can see the new NFA-$\epsilon$ recognizes $L'$.

# Answer
> 0 votes
Your conclusion that $L’$ is a concatenation of two regular languages is wrong.

$L’$ is basically the set of suffixes of all the strings in $L$. Try to prove it for the prefixes and use the “closed under reverse operation” property of regular languages.

Hint for prefix language: make some special states as final state in the DFA of a regular language.

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


# Question
Title: Creating a PDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}
I didn‘t find a DPDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}, so I guess an NPDA is the only option.

NPDA are not very intuitive to me. The only solution I found online is:

I don‘t really understand how it works and also I‘m not allowed to use final states. The only way an input is accepted is by emptying the Stack (how we do it at my university).

Thanks in advance!

# Answer
> 1 votes
First of all the answer you have provided is DPDA and not NPDA. "Z" denotes that your stack is empty, so you start by taking input i.e., "a" and keep storing them in your stack, as soon as "b" arrives you start removing one "a" for every "b" that arrives (b,a|Epsilon). Now their are two possibilities (i) m\>n :- if so number of "b" are less than "a", so after all the "b" are computed only "E" will be left in the string so we reach the final state i.e., (E,a|a) (ii) n\>m:- in this case all the "a"s will be removed so only "Z" will remain in the stack, so in this case this will be the final state i.e., (b,Z|Z)

Hope this will help.

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


# Question
Title: Is there a name for a graph whose vertices consist of edges of an existing graph connected by an edge if they shared a common vertex?
I was wondering if there is a name for this construction: Take a graph $G$ and construct a new graph $G'$ in which the edges of $G$ now become vertices, and "vertices become edges" in the sense that vertices are joined by edge in $G'$ if they as edges in $G$ shared a common vertex.

More precisely: Given a graph $G=(V=\\{v\_1,v\_2,\dots,v\_n\\},E=\\{e\_1,e\_2,\dots,e\_k\\})$ where each $e\_i=\\{u,v\\}\subset V$ we define the graph $G'=(V'=\\{e\_1,e\_2,\dots,e\_k\\},E')$ so that $\\{e\_i,e\_j\\}\in E' \iff e\_i\cap e\_j\neq\emptyset$.

I don't know if this can be used for anything (my guess would be it can't) it just came to my mind and thought that perhaps this has a name.

# Answer
> 4 votes
This is called the line graph of $G$. It actually has a wide variety of uses, as seen on that Wikipedia page, and the terminology is sufficiently standard that you should be able to mention it in a paper without defining it.

---
Tags: graphs, terminology
---


title: Is L decidable or not

text:
# Question
Title: Is L decidable or not
Let $L = \\{\lt M\gt | M$ is a $TM, L(M) = \\{1^n0^n | n\ge0\\}\\}$.
Create a reduction from $A\_{TM}$ (acceptance problem) to $L$. Is $L$ not decidable?
But isn't $L$ decidable since it is possible to make a CFG (or PDA) of that language. And if I can make a reduction, $L$ would become not decidable because of $A\_{TM}$.

# Answer
The decision problem that corresponds to $L$ deals with *the behaviour of Turing machines*, not with strings of $1$'s and $0$'s.

More precisely, the decision problem is

> Given a Turing machine $M$, is it the case that $L(M) = \\{ 1^n0^n \mid \> n \geq 0 \\}$

A decider for this decision problem would take as input the description $\langle M \rangle$ of an arbitrary Turing machine $M$ and tell us if $M$ accepted exactly those strings that are of the form $1^i0^i$ for some $i \geq 0$. A pushdown automaton that recognizes the language $\\{ 1^n0^n \mid \> n \geq 0 \\}$ is clearly not such a decider.

A reduction from $A\_{TM}$ to $L$ will, given an instance $\langle M,w \rangle$ build a description $\langle M' \rangle$ such that

$$M \text{ accepts } w \iff L(M') = \\{ 1^n0^n \mid \> n \geq 0 \\}$$

Here is $M'$:

> On input $x$
>
> 1. If $x \neq 1^i0^i$ for some $i \geq 0$, *reject*
> 2. Else simulate $M$ on $w$ and answer what $M$ answered.

Clearly, if $M$ accepts $w$ then $L(M') = L$. If $M$ does not accept $w$, then $L(M') = \emptyset$.
> 1 votes

---
Tags: reductions, undecidability
---


# Question
Title: If declarative programming is possible at the instruction/action level?
I am considering what the possibilities are with declarative programming. I have a firm understanding of how to use declarative programming in practice, but, short of having examples, I don't know if it's possible to 100% use declarative programming all the way down to the machine code (theoretically).

Standard QA sites like this says stuff like:

> it means describing the problem to be solved, but not telling the programming language how to solve it

A typical example is a SQL query which uses a `where` clause to *define* the query rather than implementing the query it *step-by-step* using something like an iterative loop.

An example I am interested in is an even higher level abstraction than a SQL query: defining an HTTP server. You can define the server and all of it's GET handlers (if we just limit it to that for now) in a completely declarative way, as seen by many declarative frameworks. The declarative frameworks that do similar stuff to this are the ones like Terraform or SaltStack that define machine configurations/states. You are basically defining the state the machine should look like, and the system takes your "definition" and *makes it happen*.

For the HTTP server you can do like in React:

```
<Route path='/' component={Home}>
  <Route path='/about' component={About}>
  <Route path='/terms' component={Terms}>
  ...
</Route>

```

This then automagically gets wired up into a listening server for these changes, and renders the components (this API may not be exact, just pseudocoding it ftm).

In fact, there is a lot that can be done declaratively. HTML and CSS together form an animatable graphics display and is completely declarative. You can define servers, machines, parsers (PEG parser generators), graphics... I don't know what else.

That's mainly what my question is, what *can* be done declaratively. More specifically, **what cannot be done in a declarative fashion**. The stereotypical example I am thinking of is simply defining a step-by-step sequence of actions of some sort, but in a declarative, non-iterative way. Is it possible?

Here is my attempt.... Say we are describing some automation steps for interactively going through and clicking around a website. Here is the iterative way:

```
Visit "/"
Click on "Button 1"
Wait "2 seconds"
Click on "Button 2"
For each "Input" in "Fields"
  Type into "Input"
Click on "Button 3"
Wait "2 seconds"
...

```

This is similar to assembly instructions like `mov`. But can this be done in a declarative way (that is also readable and easy to understand)? Does functional programming offer any insight? Maybe one could show how to do this in a functional programming paradigm, or even a logic (prolog-ish) way, if that would help illuminate how it's done. My attempt at declarative is like this:

```
Current State should be "/"
Button is not clicked
Button has been clicked
2 seconds have passed
...

```

Basically, just stating the "states" before and after each step sort of thing. That makes it harder to read, and it feels like you are trying to hack around having to build some iterative code *anyways*. It's like it *has to be iterative*. Is that so? Is there any way to make this non-iterative and so it still makes sense?

To me, currently, it seems that you can use declarative programming for like 80-90% of things, but then you inevitably need "parsing" code which will take those declarative statements and *interpret* them, converting them into some iterative sequence. But what I'm left wondering is, can that 10-20% that seems to have "iteration" as a *requirement* be instead written declaratively? Can you take that 10-20% remaining iterative code and make *that* declarative too? If so, how would that look or what is the technique?

# Answer
Machine code is imperative, not declarative, so if you want your code to execute on a conventional CPU, at some point there needs to be *some* code that converts the declarative program to imperative style (e.g., a compiler), and at least some of that code needs to be written imperatively (because at least some of it needs to be written in machine code). It can't be turtles all the way down.
> 2 votes

# Answer
AFAIK, the meaning of the term “declarative vs. imperative” changed over time. The original meaning is what you cited, “how vs. what”. This distinction is philosophical, so its meaning varies from person to person. To be honest, after all these years, I failed to understand it, so I will not discuss it here.

A more specific meaning of “imperative” emerged: a programming language is imperative if it has the concept of *command* and a program written in the language defines the **order** of commands. For example, in C, commands are called *statements*, and the implementation is required to execute statements in the order that they are written and even execute **subexpressions** of an expression in the order that they are written. Hence C is considered imperative. The programming languages Haskell and Prolog (without extra-logical features), according to this definition of “imperative”, are non-imperative, in other words, declarative.

Now to your question,

> That's mainly what my question is, what can be done declaratively. More specifically, what cannot be done in a declarative fashion. The stereotypical example I am thinking of is simply defining a step-by-step sequence of actions of some sort, but in a declarative, non-iterative way. Is it possible?

In principle, the question is answered by the Turing Thesis. Since there are Turing-complete declarative languages (both Haskell and Prolog are), declarative languages can do everything that imperative languages can. Even pure lambda calculus, having only 3 syntax constructs, is Turing-complete. Haskell provides a feature for convenient translation of imperative programs into Haskell, the `IO` monad. The translated program looks almost like an original imperative one.

Probably, your real question is not about what can be written declaratively, but what can be written declaratively and **more elegantly**? Since there is no point in rewriting a program in another programming language if the result is worse. IMHO, this depends on program. Therefore, the answer to your question depends on the precise meaning of “writing declaratively” which should be made clear by referring to **specific programming languages**.
> 1 votes

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


# Question
Title: Relaxing the stack in a push down automata
Given a non-deterministic push down automata (we define "accept" here using accept states), if we assume any operation popping from the stack and checking if the top of the stack contains some symbol can succeed (i.e. "getting rid" of the stack), we get a non-deterministic finite automata.

If we convert two such PDAs, whose languages recognized are the same, and assuming *all states are reachable*, to NFAs in this fashion, are the languages recognized by the NFAs still the same?

---

Here's a simple example. Consider the language $\\{a^n b^n : n \in \mathbb{N}\\}$. Here's one simple PDA for it. The PDA has two states, $q\_0,q\_1$. When it is in state $q\_0$ and it reads the symbol $a$ on the input tape, it pushes $A$ on the stack and remains in state $q\_0$. When it reads the symbol $b$ on the input table and the stack is non-empty, it pops whatever is on the stack and moves to state $q\_1$. The PDA accepts if the stack is empty at the end of the input string. If we convert this PDA to a NFA, we get a NFA with two states $q\_0,q\_1$ and transitions $q\_0 \stackrel{a}{\to} q\_0$, $q\_0 \stackrel{b}{\to} q\_1$, $q\_1 \stackrel{b}{\to} q\_1$. This NFA accepts the language $a^\* b^\*$. There are other ways to build a PDA for the language $\\{a^n b^n : n \in \mathbb{N}\\}$; if we apply the same conversion to them, does the corresponding NFA always accept the language $a^\* b^\*$?

# Answer
I think the answer is no, even if we disallow unreachable states.

Consider the language $L$ given by the grammar $S ::= \varepsilon \mid abS \mid aSb$. In this language, every word $w \in L$ has the same number of $a$'s and $b$'s, and every prefix of $w$ has at most as many $b$'s as $a$'s. Also, if $w \in L$ is not empty, then $w$ starts with $a$ and has length $\ge 2$.

## First PDA

Here's one PDA that can recognize that grammar. It has two states $q\_0,q\_1$, and the following transitions:

$q\_0 \stackrel{a,\epsilon\to \alpha}{\to} q\_0$

$q\_0 \stackrel{b,\alpha \to \epsilon}{\to} q\_0$

$q\_0 \stackrel{\epsilon, \epsilon \to \epsilon}{\to} q\_1$.

The state $q\_1$ is the accept state, and both states are reachable.

If you convert this to a NFA, then the NFA accepts the language $(a|b)^\*$.

## Second PDA

Here's another PDA that accepts the language $L$. It has four states $q\_0,q\_1,q\_2,q\_3$, and transitions

$q\_0 \stackrel{a,\epsilon \to \alpha}{\to} q\_1$

$q\_1 \stackrel{a,\epsilon\to \alpha}{\to} q\_2$

$q\_1 \stackrel{b,\alpha \to \epsilon}{\to} q\_2$

$q\_2 \stackrel{a,\epsilon\to \alpha}{\to} q\_2$

$q\_2 \stackrel{b,\alpha \to \epsilon}{\to} q\_2$

$q\_2 \stackrel{\epsilon, \epsilon \to \epsilon}{\to} q\_3$

Here $q\_0,q\_3$ are the accepting states. All states are reachable.

If you convert this to a NFA, it accepts the language $\varepsilon | a (a|b)^\*$.
> 3 votes

# Answer
I think the general answer is no, two PDAs that recognise the same language could yield NFAs that recognise different languages.

We can construct (at least) two PDAs for the empty language (i.e. that don't recognise anything), but have unreachable states. For example, the first can have states $A$ and $B$, with one transition $A \stackrel{a,\alpha\rightarrow\varepsilon}{\longrightarrow}B$, with $B$ as the accept state. The second has states $X$ and $Y$, transition $X \stackrel{b,\alpha\rightarrow\varepsilon}{\longrightarrow}Y$ with $Y$ as an accept state. There is no transition to push $\alpha$ to the stack, so the only transition in both is unusable, so the language of both is $\emptyset$. However removal of the stack makes the transition usable, but the languages are now $\\{a\\}$ for the first machine and $\\{b\\}$ for the second.

This basic construction could be done for any language by adding an unusable transition in both that adds a new string to both that differentiates them.

So the interesting question is now do any two PDAs with no unreachable states generating the same language yield via stack removal two NFAs which have the same language?
> 2 votes

# Answer
Your own example has a stack-ignore language $a^\*b^\*$. Let me answer your question by demonstrating that *every* context-free language over alphabet $\Sigma$ has a PDA with a stack-ignore language $\Sigma^\*$, by building a *single state* PDA for it.

Start with a CFG for the language. From this we build a one-state PDA that accepts by empty stack using a standard "expand-match" technique. For $A\to \alpha$ in the grammar we add PDA "*expand*" instruction $(q,\varepsilon,A,q,\alpha)$; pop $A$ push $\alpha$. We also have "*match*" $(q,a,a,q,\varepsilon)$; read $a$ when $a$ is on top of the stack (and pop it).
> 1 votes

# Answer
You can always build a PDA with just one state for any CFL (just work through building a PDA from a grammar using top-down parsing), the result of your construction will accept essentially anything.
> 0 votes

---
Tags: formal-languages, pushdown-automata, nondeterminism
---


# Question
Title: Why is nondeterminism physically not realizable?
Why it is so hard to make a nondeterministic computer? If such a device is physically realizable then would that be a counterexample to the extended Church-Turing thesis?

# Answer
Is it possible to make a machine that when it encounters a non-deterministic step it takes an arbitrary one? Yes easily.

Will this machine be able to solve NP problems in P? No because it will most likely pick the wrong path through the execution.

Similarly for outputting a number there is no way to force the machine to match the required path needed to output said number.
> 3 votes

# Answer
Do you mean "indeterministic" in the sense of quantum mechanics? It's easy to build that kind of indeterminism into a computer, by incorporating a routine that goes and checks the state of a quantum mechanical physical source. That doesn't necessarily violate the Church-Turing thesis, since the source of quantum mechanical randomness might not be the result of an algorithmically realizable process. In that case, if it turned out that what the quantum mechanical source produced was uncomputable, this wouldn't violate a Church-Turing thesis that says that any algorithmic process can be computed by a Turing machine.

There are discussions of a variety of versions of and extensions of the original Church-Turing thesis, and discussions about whether natural processes or specially constructed experiments are ever counterexamples to these versions. Jack Copeland has useful papers on this. Not everyone agrees with him about everything--I don't think I do--but I think that papers such as his "The Church-Turing Thesis: Logical Limit or Breachable Barrier" provide good entry-points into this literature.
> 0 votes

---
Tags: turing-machines, nondeterminism, church-turing-thesis
---


# Question
Title: Are there any benefits of implementing the Fisher–Yates shuffle algorithm from tail to head instead of head to tail?
I was looking at the Fisher–Yates shuffle algorithm and followed the Python implementation for it.

Python starts from the end of the array to the start. Looking at the algorithm I didn't see any benefits in doing so compared to starting with the start and going to the end.

I was wondering, considering that looping backwards adds a thin layer of complexity, are there any benefits in doing so?

# Answer
> 1 votes
With 0-indexed arrays, and stopping the loop at the last non-trivial random selection, we have

```
for x = n to 2 step -1:
    swap A[x-1], A[uniform_random(0 inclusive to x exclusive)]

```

vs

```
for x = 0 to n-2 step 1:
    swap A[x], A[uniform_random(x inclusive to n exclusive)]

```

which would probably be implemented as

```
for x = 0 to n-2 step 1:
    swap A[x], A[x + uniform_random(0 inclusive to n-x exclusive)]

```

So the forward loop has at least as much complexity.

I would claim that the simplest version is looping backwards in a 1-indexed environment (i.e. 1-indexed arrays and random number generation):

```
for x = n to 2 step -1:
    swap A[x], A[uniform_random(1 inclusive to x inclusive)]

```

There are various other variants possible: e.g. in the first example, we could loop `x = n-1 to 1 step -1`; in the second example, we could use two loop variables instead of one; etc.

# Answer
> 0 votes
The Wikipedia link you shared also provides an implementation that works starting from the end of the list (followed by an implementation starting from the beginning).

> From wikipedia `-- To shuffle an array a of n elements (indices 0..n-1): for i from n−1 downto 1 do
>  j ← random integer such that 0 ≤ j ≤ i
>  exchange a[j] and a[i]`
>
> An equivalent version which shuffles the array in the opposite direction (from lowest index to highest) is:
>
> ```
> -- To shuffle an array a of n elements (indices 0..n-1): for i from 0 to n−2 do
>      j ← random integer such that i ≤ j < n
>      exchange a[i] and a[j]
>
> ```

Functionally, both are equivalent. Some may argue that the versions have different cache/prefetcher performance and instruction-level optimizations but I don't think that influenced the decision.

---
Tags: algorithms, python
---


# Question
Title: How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?
The HW question, on page 362 of *Data Structures and Algorithms in C++*: Fourth Editionby Mark Allen Weiss, reads as follows:

> Prove that merging two sorted arrays of *N* items requires at least 2 * *N* \- 1 comparisons. You must show that if two elements in the merged lists are consecutive and from different lists, then they must be compared

If we are trying to find the lower bound then wouldn't the number of comparisons be *N*, not 2 * *N* \- 1? If the largest element is some array *A*is smaller than the smallest element in some array *B* then at most you would only have to do N comparisons since after all of *A*'s elements are placed in the merged array then the remaining elements in *B*'s can simply be appended in to the merged array.

The lower bound has to be something that is true for every possible *N* and every possible combination of elements in both arrays, right? 2 * *N* \- 1 seems more like it would be the **upper bound** since there is no way there can be more comparisons than that.

Note: I am not asking for an answer to the HW question itself as I know that is deprecated. I am confused about the implied assertion the question is making about the lower bound

# Answer
> 12 votes
What is meant by "lower bound" in this case is a lower bound on the *worst-case* number of comparisons. In this case, it happens to also be an upper bound.

> The lower bound has to be something that is true for every possible N and every possible combination of elements in both arrays, right? 2\*N\* - 1 seems more like it would be the upper bound since there is no way there can be more comparisons than that.

No, it just needs to be true for *some* input (for infinitely many N).

For example, when we say that $\Omega(n \log n)$ is a lower bound for sorting, this does not mean that every array requires $\Omega(n\log n)$ comparisons. It just means that *some* arrays require that many comparisons, and thus there is no $o(n\log n)$-time algorithm for sorting.

---
Tags: runtime-analysis, arrays, mergesort
---


# Question
Title: Find and prove a linear algorithm that identifies all cycles and the length in a graph where each vertex has exactly one outgoing edge
> Consider a directed graph on n vertices, where each vertex has exactly one outgoing edge. This graph consists of a collection of cycles as well as additional vertices that have paths to the cycles, which we call the branches. Describe a linear time algorithm that identifies all of the cycles and computes the length of each cycle. You can assume that the input is given as an array A, where A\[i\] is the neighbor of i, so that the graph has the edge (i, A\[i\]).

I kind of have an idea of how to approach the algorithm but have no idea what to do with the proof of my algorithm. So far I'm thinking of marking the vertices I have traversed, and every time a vertex points back to the ones that I've traversed I count one cycle and move on to the next unvisited vertex.

Edit: what I ended up writing

```
For all element i of A:
    If i has not been visited (not in the map)
        Store the index i as key and order of traversal as value in a map
        Add i to an array
        Get A[i] as neighbor j
        While j is not in the map (not visited)
            Store the j as key and order of traversal as value in a map
            Add j to an array
            j’s neighbor becomes j
        Endwhile
        If resulting index j is not already part of a confirmed cycle
            Store array into confirmed cycle set
            Get j’s order of traversal of from map as o
            Output length of cycle by deducting o from array length
            Output part of the array that is the solution
            Store array from index array.size() - o to the end into solution set
        Endif
    Endif
Endfor

```

# Answer
> 1 votes
Unfortunately, your algorithm is not correct.

Let us call a directed graph where each vertex has exactly one outgoing edge a unique-outgoing graph.

### What does a unique-outgoing graph look like?

It consists of some directed tree and some directed cycles, all of which are disjoint except that every root of the trees is also a vertex of some cycle. Or, it looks like a collection of directed cycles with some directed trees attached to them.

Here is an illustration, which corresponds to the array $\[5, 12, 3, 10, 9, 2, 3, 14, 14, 7, 2, 14, 5, 11, 4\]$. There are two connected components in that graph. One component has the cycle of vertices 2, 3, 10 with two attached trees, the tree with vertices 2, 5, 0, 12, 1 and the tree with vertices 3, 6. The other component has the cycle of vertices 4, 9, 7, 14 with one attached tree, which has vertices 14, 8, 11, 13.

### A simple algorithm

Here is the pseudocode, which is about as simple as possible.

Input: Array $arr\[0\], arr\[1\], \cdots, arr\[n-1\]$, such that the graph has the edge $(i, arr\[i\])$.

Procedure:

1. $round\leftarrow 0$.
2. Create array $first\\\_visited$ of $n$ zeros, where $first\\\_visited\[i\]$ will record the round at which $arr\[i\]$ is first visited. No element is visited at round 0.
3. Loop $i$ from 0 to $n-1$:
If $first\\\_visited\[i\]$ is 0:
    1. Increase $round$ by 1.
    2. $index\leftarrow i$
    3. Loop the following as long as $first\\\_visited\[index\]$ is zero, i.e., $arr\[index\]$ is not visited.
        1. $first\\\_visited\[index\]\leftarrow round$
        2. $index \leftarrow arr\[index\]$
    4. Now $first\\\_visited\[index\]$ must be non-zero.
    If $first\\\_visited\[index\]$ is equal to $round$, a new cycle has been found! Record (or output) the cycle as well as its length by chasing the elements starting from $index$. Otherwise, do nothing.

When we run the algorithm on the aforementioned array, we will visit

* 0, 5, 2, 3, 10, 2 in round 1. The cycle 2, 3, 10 of length 3 will be recorded.
* 1, 12, 5 in round 2.
* 4, 9, 7, 14, 4 in round 3. The cycle 4, 9, 7, 14 of length 4 will be recorded.
* 6, 3 in round 4.
* 8, 14 in round 5.
* 11, 14 in round 6.
* 13, 11 in round 7.

Basically, the algorithm loops over all elements from index 0 to $n-1$. From each unvisited element, it makes an inner loop where it chases the next element via its outgoing edge, until it reaches a visited element. Each inner loop constitutes a round of chasing, during which each newly-visited element will be associated with the number of rounds happened so far.

The algorithm runs in $O(n)$ time with $O(n)$ space.

### On your algorithm

> I'm thinking of marking the vertices I have traversed, and every time a vertex points back to the ones that I've traversed I count one cycle and move on to the next unvisited vertex

You have got the basic idea. However, a new cycle might not be found when a vertex points back to a vertex that has been traversed, even if it is not part of any confirmed cycles. For example, consider the moment when your algorithm have visited 0, 5, 2, 3, 10, 2, 1, 12 and then 5 again. Vertex 5, although revisited, is not part of any cycle.

To ensure that a new cycle will be found when you revisited a vertex, the first visit to that revisited vertex must happen after the visit to the vertex `i` in your algorithm. That is why the variable $round$ is introduced in the above algorithm, which is, in fact, the only critical difference between the two algorithms.

### Exercises

Here are a couple of exercises that help prove the above algorithm is correct.

**Exercise 1.** Show that there is exactly one cycle in each connected component.

**Exercise 2.** Prove the following invariant of the above algorithm. At the start of step 3.1, all visited vertices and edges so far form a unique-outgoing graph.

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


title: Relational Algebra Queries look same

text:
# Question
Title: Relational Algebra Queries look same
Query A and Query C seem to be the same.But given answer is query A. Can someone help me to find the difference between queries A and C ?

# Answer
> 0 votes
Because the id and the name fields are produced by the inner projections, this forces the supplier supplying some red part and the supplier supplying some green part to be the same person in each case, not just any people with the same name.

This is why alternative A is correct, and alternative C is not.

---
Tags: relational-algebra
---


# Question
Title: Robust two lines/segments intersection point in 2D
Given two line segments the problem is to find an intersection point of corresponding lines (assuming that they are not parallel or coincide).

There is a Wikipedia article which gives us exact formulas, but there are two of them: one that uses `t` ratio and approaches intersection point from first line segment and the other -- uses `u` and the second line segment. How can I select which one to use in my scenario?

For example: my initial implementation which always used `t` failed on

```
first_segment = Segment(start=Point(x=-5, y=0), end=Point(x=72057594037954921, y=0))
second_segment = Segment(start=Point(x=0, y=0), end=Point(x=0, y=3))

```

gives

```
Point(x=5.921189464665284e-16, y=0.0)

```

which is incorrect, but when I switch to use `u` or change order of arguments it gives me correct

```
Point(x=0.0, y=0.0)

```

So my question is: is there robust way to calculate intersection point?

# Answer
> 2 votes
If you choose a formula with parameter $t$ you'll get the $P\_x$ value as a result of a number of operations - additions, multiplications and one division:

$$t = \frac{(x\_1-x\_3)(y\_3-y\_4)-(y\_1-y\_3)(x\_3-x\_4)}{(x\_1-x\_2)(y\_3-y\_4)-(y\_1-y\_2)(x\_3-x\_4)}$$ $$P\_x = x\_1 + t(x\_2-x\_1)$$

The number $x\_2=72057594037954921$ contains 17 significant decimal digits - so it *can't be represented exactly* using double-precision floating numbers. Apparently, a small error is introduced during some operation (most probably - the division), and this error is propagated to the result. This is a form of the Round-off error.

This bunch of calculations doesn't happen when you choose a formula with parameter $u$, because the numerator there is equal to zero.

**Conclusion**: if you need to work with numbers, containing a big number of significant digits - use floating numbers with bigger precision, or may be - with *arbitrary* precision. An example: mpmath.

---

Another option - use rational numbers. For example, *kernels*, based on rational numbers, can be found in the computational geometry library CGAL. Developers of this library have invested a lot of efforts to solve this robustness problem - please see this page for more information.

If you want to go deeper into this research area, called Exact Geometric Computation (EGC), you can start from this review. You'll need a good knowledge of Linear Algebra and Linear Systems.

---
Tags: computational-geometry, numerical-algorithms, numerical-analysis
---


# Question
Title: Find median of unsorted array in $O(n)$ time
To find the median of an unsorted array, we can make a min-heap in $O(n\log n)$ time for $n$ elements, and then we can extract one by one $n/2$ elements to get the median. But this approach would take $O(n \log n)$ time.

Can we do the same by some method in $O(n)$ time? If we can, then how?

# Answer
> 74 votes
This is a special case of a selection algorithm that can find the $k$th smallest element of an array with $k$ is the half of the size of the array. There is an implementation that is linear in the worst case.

### Generic selection algorithm

First let's see an algorithm `find-kth` that finds the $k$th smallest element of an array:

```
find-kth(A, k)
  pivot = random element of A
  (L, R) = split(A, pivot)
  if k = |L|+1, return pivot
  if k ≤ |L|  , return find-kth(L, k)
  if k > |L|+1, return find-kth(R, k-(|L|+1))

```

The function `split(A, pivot)` returns `L,R` such that all elements in `R` are greater than `pivot` and `L` all the others (minus one occurrence of `pivot`). Then all is done recursively.

This is $O(n)$ in average but $O(n^2)$ in the worst case.

### Linear worst case: the median-of-medians algorithm

A better pivot is the median of all the medians of sub arrays of `A` of size 5, by using calling the procedure on the array of these medians.

```
find-kth(A, k)
  B = [median(A[1], .., A[5]), median(A[6], .., A[10]), ..]
  pivot = find-kth(B, |B|/2)
  ...

```

This guarantees $O(n)$ in all cases. It is not that obvious. These powerpoint slides are helpful both at explaining the algorithm and the complexity.

Note that most of the time using a random pivot is faster.

# Answer
> 11 votes
There is a randomized Monte Carlo algorithm to do this. It is described in \[MU2017\]. It is a linear time algorithm that fails to produce a solution with probability at most $n^{-1/4}$. As discussed in \[MU2017\], it is significantly simpler than the deterministic $O(n)$ algorithm and yields a smaller constant factor in the linear running time.

The main idea of the algorithm is to use sampling. We have to find two elements that are close together in the sorted order of the array and that have the median lie between them. See the reference \[MU2017\] for a complete discussion.

---

\[MU2017\] Michael Mitzenmacher and Eli Upfal. "Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis," chapter 3, pages 57-62. Cambridge University Press, Second edition, 2017.

# Answer
> 8 votes
Remember the Quicksort algorithm?

The difference is that you don't need the whole array sorted, you only need the portion containing the median in the right place. If you have n elements 0 to n-1, then the median is element (n - 1)/2 if n is even, and the average of elements n/2 - 1 and n/2 if n is odd.

So you start with one quicksort partition. Then you look at the two partitions: Instead of sorting them both, you only partition the one containing the one or two elements that you are interested in, and that half gets partitioned further.

(In the unlucky case that you end up with two partitions, one ending at n/2 - 1 and one starting at n, you can just take the maximum and minimum of each side)

You can easily adapt this method to find the k largest or k smallest items, or items with index k to k' in linear time.

# Answer
> 1 votes
**I have one more solution for Find median of unsorted array in O(n) time but it will Increase Space Complexity.**

```
#include<stdio.h>
#include<conio.h>

int main()
{
    int a[11] = {10,45,35,3,24,23,78,89,33,34,11};
    int max=0,*ar,co=0,mid=0;
    for(int i=0; i<sizeof(a)/4; i++)   // O(n)
    {
        if(i==0)
            max = a[i];
        if(a[i]>max)
            max = a[i];
    }
    ar =(int*)malloc((sizeof(int)*max)+1); // O(n)
    for(int i=0; i<sizeof(a)/4; i++)
        ar[a[i]] = 1;
    for(int i=0; i<=max; i++)  // 0(n)
        if(ar[i]==1)
        {
            co++;
            if(co == ((sizeof(a)/8)+1))
                mid = i;
        }
    printf("%d",mid);
}
//Total = n+n+n = O(n)

```

---
Tags: algorithms, time-complexity
---


title: prove that log((n^2)!)= o(log((n!)^2))

text:
# Question
Title: prove that log((n^2)!)= o(log((n!)^2))
i have a question - how i can prove that:

> $\log((n^2)!) =\theta (log((n!)^2))$

i try something like that:

$\log((n^2)!) = 2\*(log(n)!)=\theta(2\*(log(n)!)=\theta(n\ log(n)) $

$\ \theta(log(n!)^2)=\theta(log(n!)\*log(n!)) = \theta(n\ log(n)) $

then we can see that is equal --\> there are $\theta(n\ log(n))$

this is true?

# Answer
$(n^2)!$ is the product of the numbers 1 to $n^2$.

$(n!)^2$ is the product of the numbers 1 to n, multiplied by the product of the numbers 1 to n again.

In the first product, we have $n^2 - n$ numbers ≥ n plus some others. In the second product we have 2n numbers ≤ n. So if we take the logarithm, the first is ≥ $(n^2 - n) log n$, the second is ≤ $2n log n$. So f(n) / g(n) ≥ (n-1)/2. Absolutely not Big-$\Theta$.
> 1 votes

# Answer
Alternatively: $(n^2)!$ is the product of $n^2$ numbers. We can split the product into n groups 1 .. n, n+1 .. 2n, 2n+1 .. 3n, $n^2-n+1$ .. $n^2$. The product of the numbers in each group is ≥ n!, actually significantly greater than n! in some cases. So $(n^2)! ≥ (n!)^n$.

If we let f(n) = $log ((n^2)!)$ and g(n) = $log((n!)^2)$, then f(n) ≥ n log(n!), while g(n) = 2 log(n!), so f(n) / g(n) ≥ n/2. So f(n) is not o (g(n)), or $\Theta(g(n))$, but g(n) = o (f(n)).
> 0 votes

---
Tags: asymptotics, factorial
---


title: A Hexastore data structure

text:
# Question
Title: A Hexastore data structure
I'm reading an article about indexing in Redis. There is a link to so-called Hexastore, it's referred to as a data structure. The link doesn't work, which makes me feel I'm missing something.

I understand from the article that

> the hexastore provides a representation for relations between objects, formed by a subject, a predicate and an object. A simple relation between objects could be
>
> antirez is-friend-of matteocollina

What are the key use cases of Hexastore as a data structure? Which indexing problems can it solve along with the quoted example above? How does it work?

There is a paper about Hexastore on the internet, which has a long explanation. Could anybody put it in a nutshell?

# Answer
I only skimmed the paper for 10 seconds, but AFAICS, the fundamental idea (and the reason why it is called the *Hexastore*) is that the relationship triple `(Subject, Relationship, Object)` is stored in all 6 of its permutations separately:

1. `(Subject, Relationship, Object)`
2. `(Subject, Object, Relationship)`
3. `(Object, Relationship, Subject)`
4. `(Object, Subject, Relationship)`
5. `(Relationship, Subject, Object)`
6. `(Relationship, Object, Subject)`

Now, you can ask any question you want and the answers will only require a prefix search on the index.

Want to know about any relationship between Anna and Billy? Search for `(A, B)` or `(B, A)` (order doesn't matter since both are stored). Want to know all of Anna's Friends? Search for `(A, f)`. Want to know about all married couples? Search for `(m)` and throw away every odd result. And so on.

Whether you are trying to find relationships between two fixed persons, finding a person that a fixed person has a fixed relationship with, finding all pairs of persons that have a particular relationship, finding all relationships a particular person has with anybody, all of that is fast because all of that is just an index search.

The paper does not actually store all six of those in the same index, rather they use six indices. (Whereas I believe the Redis article suggests to use a single index.)
> 4 votes

---
Tags: data-structures
---


# Question
Title: Developing a Context Free Grammar whilst knowing the number of terminals
I am trying to develop a CFG for the language $L$ defined by:

> $L = \\{a^{n+2}bba^{n-2} | n \> 1\\}$

The problem I am having is that I cannot develop the CFG for this language no matter what I try. The closest I can get is:

> $S \rightarrow aaaaXbbX$ (Production 1)
>
> $X \rightarrow aX | \Lambda $ (Production 2)

This *would* be right if we were somehow *forced* to substitute the same value of the non-terminal $X$ in both its appearances in production 1. However, we can substitute $X \rightarrow aX$ in its first apperance in production 1 and $X \rightarrow \Lambda$ in its second appearance in production 1, thus throwing the balance of $a's$ off as defined in the language $L$.

The first question is, is there even a CFG for this?

Well, I would say according to theory, yes there is because:

* I am asked to draw a Determinate Push Down Automata for this language; and
* According to theory, every language accepted by a PDA is context-free

Am I correct that there is a CFG to this and what is it?

# Answer
Your attempt was pretty close! But I think that this is the way to go for you

$$S \rightarrow a a a a X$$

$$X \rightarrow a X a \mid b b$$

The way that these rules come together forces there to be the four necessary $a$'s at the start and then it's a matter of matching $a$'s with $b b$ in the middle.

So after that, it's a question of making a CFG that generates $L = \\{a^n b b a^n \mid n \geq 0\\}$. That's exactly what $X$ does. Every time you see a $X$ you have to put a leading and trailing $a$ in and you can't terminate until you put the $b b$ in the middle since otherwise the $X$ gets expanded to another $X$.
> 4 votes

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


title: Max no. of keys of B-Tree of height h

text:
# Question
Title: Max no. of keys of B-Tree of height h
I am reading about B-Tree through CLRS. One of the exercise problem is to express maximum number of keys in a BTree of height $h$ and minimum degree $t$.

Properties of BTree of $t$:

* $t\ge 2$
* Min. no of keys in a node is $t-1$ and max. number of keys in a node is $2t-1$
* Max number of children a node can have is $2t$

To solve it the formula I came up with is $$\sum\_0^h (2t)^h(2t-1) $$

Does it have any convergence?

# Answer
> 2 votes
Found it (using geometric serie for the sum)

$$\sum\_{i=0}^h (2t)^i(2t-1) = (2t-1) \sum\_{i=0}^h (2t)^i = (2t-1) \frac{(2t^{h+1}-1)}{(2t-1)} = (2t)^{h+1}-1 $$

---
Tags: b-tree
---


# Question
Title: Time complexity of removing duplicates in lists
## Question

I am wondering what is the minimum time complexity of get the unique value of a array in two conditions: keep the order or not.

For example, suppose we have a original array `[3,6,1,1,2]`. I want to get `[3,6,1,2]`, this result keeps the original order and drops duplicates. If there is no need to keep the original order, `[1,2,6,3]` or `[6,2,1,3]` works fine.

I think time complexity of not keeping the order is $O(n)$ using a hashtable. Under keeping order condition, approch may have a time complexity of $O(n^2)$.

> So, Am I right? Can someone give a detailed prove the time complexity of the best in each condition?

## For more infomation:

I use Python, I find 2 python code for drop duplicates in a list.

1. How do you remove duplicates from a list whilst preserving order?
2. removing duplicates in lists

# Answer
> 3 votes
The running time is expected $O(n)$ for both problems. Simply scan over the input list, and as you examine each item, add it to the hashtable; if it wasn't already present, output it. The running time is $(n)$ because, with a suitable hash function, the expected time it takes to insert or look up an item in a hash table is $O(1)$.

The worst-case running time with this approach is $O(n^2)$, but you can make the probability of this happening exponentially small with a suitably chosen hash function.

Alternatively, if you care a lot about worst-case running time, you can replace the hashtable with a self-balancing binary tree and achieve $O(n \log n)$ worst-case running time for both problems.

---
Tags: time-complexity, arrays
---


# Question
Title: Problem with understanding two sided Matching Algorithm: maximium cardinality
I am trying to understand the maximum cardinality problem in the context of stable matching algorithm. I am reading the following article at the link:

A Two-Sided Matching Decision Model Based on Uncertain Preference Sequences

The article says that:

> In general, we can categorize two-sided matching problem into three typical kinds of models in terms of different decision objectives: stable matching, maximum cardinality matching, and maximum weight matching. In the first model, the objective is to seek a stable matching solution, and we count a solution as stable matching only when there does not exist any alternative pairing (, ) in which and are individually better off than they would be with the element currently matched. Gale and Shapley put forward an approach, also named Gale-Shapley algorithm, to get a stable matching solution in the perspective of mathematics and game theory, which symbolizes the beginning of two-sided matching research and enlightens the subsequent scholars to pay more attention to this topic. In the second model, the objective is to seek a solution in which the number of matching pairs is maximized.

I am able to understand stable matching. I can’t understand how the number of matching pair is maximized. This may occur because we have 2 sets. One of boys and other of girls. One element in one set has more than one matching in the other set. This might occur due to preference sequence. Am I right about maximum cardinality?

What I understand preference sequence as the order of preferences of elements of one set for the other. Due to maximum cardinality, it is possible that element Of one set has same preferences for multiple elements of the other set.

Am I right about preference sequences?

Somebody please guide me.

Zulfi.

# Answer
The standard definition of the stable marriage problem is, given $n$ men and $n$ women, find a stable matching that marries all of the men and women. Consequently, by definition, everyone will be matched and the number of matches will be exactly $n$ in any solution. So, no, what you mention cannot happen, if you use that as the definition of the stable marriage problem.

I'm not 100% sure what your text is referring to when it talks about maximum cardinality matching, but I suspect it's referring to find a maximum matching in a bipartite graph, which is completely separate problem. In this problem, the matching is not required to be a stable matching and it has nothing to do with the stable marriage problem.
> 1 votes

---
Tags: matching
---


title: Big-O Notation: Runtime Analysis

text:
# Question
Title: Big-O Notation: Runtime Analysis
I have a problem with an exercise, I have to analyze the following For-Loops

Then I have to write down the explicit notation, my problem is that I don't know how to get the right m. I tried this but now I have no idea how to get the m, because I thought that m defines the diffrence between i and j and so I became **m = n + 2** but that was wrong. (This is the form in which it has to be)

I would really appreciate your help thx for your efforts in advance.

Kind Regards

# Answer
Just for convenience, I'll write out the code first.

```
for(int i = 0; i <= 4 * n;  i = i + 4) {
    for(int j = 0; j <= i + 1; j++) {
        meth();
    }
}

```

and `meth()` runs in constant time $O(1)$.

Right away we can use that the outer loop runs $n+1$ times (assuming $n$ is a non-negative integer) since we are doing $0$ to $4n$ inclusive in increments of 4. The inner loop runs $i+2$ times for each iteration of the outer loop since it goes from 0 to $i+1$ inclusive in increments of 1. So we can write the total number of times the inner loop runs as

$$\sum\_{i=0}^{n} (4i+2) = \sum\_{i=0}^n4i + \sum\_{i=0}^n2 = 4\sum\_{i=0}^ni + 2(n+1) = 4\frac{n(n+1)}{2}+2(n+1) = 2(n+1)^2$$

In the arithmetic, we first break up the sum into two parts. Then we factor out the 4 in the first term and use that that we added 2 $(n+1)$ times, aka 2(n+1). Next, we use the formula $\sum\_{i=0}^n i = \frac{n(n+1)}{2}$ and then finally simplify.
> 2 votes

---
Tags: loops, big-o-notation
---


title: Example of a prefix-free code

text:
# Question
Title: Example of a prefix-free code
I came across the following question:

A source $X$ emits symbols from the alphabet $A\_x$ with $|A\_x| = 8$. We want to construct a preﬁx-free source code for this source.

We want to ﬁnd a code with codeword lengths $(1,3,3,3,5,5,5,5)$. Can such a code exist? If yes, give such a code. If not, prove that.

I checked *Kraft's inequality* for the given set of lengths and it's fulfilled. So how can we write such a code?

# Answer
0

100

101

110

11100

11101

11110

11111
> 2 votes

---
Tags: information-theory
---


# Question
Title: Given a binary tree $t$, prove that $size(t) < 2^{h(t)}$
I was able to prove that $size(t) \leq 2^{h(t)} - 1$ for any binary tree $t$, however I wasn't able to do anything reasonable with this statement.

I know it's a proof by induction and that the inductive hypothesis is the following:

$ size(l) \< 2^{h(l)} \\ size(r) \< 2^{h(r)} $

where $l$ and $r$ are the left and right subtrees of the tree $t = \langle l,v,r \rangle$. Usually what I'd do is start from $size(\langle l,v,r \rangle)$ and work my way up to $\< 2^{h(\langle l,v,r \rangle)}$. However I wasn't able.

# Answer
> 2 votes
If a binary tree has height $h$ then it has at most 1 node at depth 0, at most 2 nodes at depth 1, ..., at most $2^{h-1}$ nodes at depth $h-1$ (the maximal depth), and so at most $1+2+\cdots+2^{h-1} = 2^h-1$ nodes in total.

You can also prove this by induction. When $h=1$, the tree consists only of a root, so at most $1=2^h-1$ vertices. Given a tree of height $h$, its two subtrees have height at most $h-1$, and so together contain at most $2(2^{h-1}-1)$ vertices. Together with the root, the tree contains at most $2(2^{h-1}-1)+1=2^h-1$ vertices.

---
Tags: trees, binary
---


# Question
Title: Algorithm to compute $n^{\log k}$ in $O(\log\log k)$
I was given this exercise and I think I have to use a variation of Gauss repeated squaring, but I can not figure out how to produce $\log\log k$ in steps, like when you divide $k$ by $2$ to compute $\log k$ in steps. Any ideas?

# Answer
> 3 votes
The idea is to use *repeated squaring*. Compute $n,n^2,n^4,\ldots n^{\log k}$. To compute $n^{2^i}$ use the fact that $n^{2^i} = n^{2^{i-1}} n^{2^{i-1}}$. Note that the answer of $n^{2^{i-1}}$ will be known in the $i$th iteration.

# Answer
> 1 votes
You can calculate $n^m$ in O (log m) multiplications. You find m = log(k) and use that.

There are two problems with this: One is doing a multiplication of possibly large numbers in constant time. The other is calculating log k in O(log log k). If I write down k in base two, you’d have to count the digits of k which takes O(log k).

---
Tags: algorithms, time-complexity
---


# Question
Title: Time complexity - Algorithm to find the lowest common ancestor of all deepest leaves
This is the problem statement I came across today.

Given a binary tree, find the lowest common ancestor of all deepest leaves.

I came up with a correct algorithm, but I would like to confirm the running time of this approach.

The algorithm is as follows:

1. Traverse the tree and find the deepest level of the tree, *dmax*.
2. Traverse the tree and find all leaves at depth *dmax*.
3. Given that ***LCA(A,B,C)*** = ***LCA(LCA(A,B),C)***, traverse all nodes found at step 2 and calculate LCA.

The subroutine for ***LCA(A,B)*** is simple. Starting at *A*, go all the way up to the root and store each visited node in a hashset. Then, starting at *B*, go up until you find a node which is contained in the hashset.

I know the first two steps of the algorithm are both *O(n)*, where n corresponds to the number of nodes in the tree. However, I am uncertain about the last step.

***LCA(A,B)*** subroutine has a linear complexity. But how many nodes, in the worst scenario, can be found at step 2?.

Intuitively, I would argue that it has to be far less than n nodes.

# Answer
> 5 votes
As @Rick Decker explained, you could have $n/2$ leaves at the max depth in the one case. In this case, step 3 is $O(n\log n)$. This post shows the worst case. Consider a tree $T$ consists of a chain of $n/2$ nodes where the remaining $n/2$ nodes are attached as a balanced tree at the bottom of the chain. This gives every leaf depth $n/2+\log\_2(n)=\Theta(n)$ With $n/4$ leaves at depth $\Theta(n)$ we have $\Theta(n^2)$ runtime for step 3 in this case. This is asymptotically the worst case since we have $n$ nodes at max depth $n$.

There's a better way to do this. Lets define a function $f$

$ f(v) = \begin{cases} v & \text{if}\quad \texttt{height}(v.left) = \texttt{height}(v.right) \\ f(v.left) & \text{if}\quad \texttt{height}(v.left) \> \texttt{height}(v.right) \\ f(v.right) & \text{if}\quad \texttt{height}(v.left) \< \texttt{height}(v.right) \end{cases} $

If the heights of the children of a node $v$ are the same, then clearly $v$ is the LCA of the deepest nodes of the subtree rooted at $v$. If the left subtree is taller, then we want the LCA of the deepest nodes of the subtree rooted at $v.left$, since they are deeper than the deepest nodes in the subtree rooted at $v.right$. The same logic follows for $v.right$ when it is taller.

The values for $\texttt{height}$ and $f(v)$ can be computed in a post-order traversal of $T$ in linear time.

Calling $f(root)$ should return the LCA of the deepest nodes in the tree.

# Answer
> 0 votes
Well, I don't know what you intend by "far less than" but it's clear that you could have about $n/2$ leaves at maximum depth: take a complete binary tree, for example, with the lowest level full.

# Answer
> 0 votes
I'd write a function which for each tree calculates the lowest common ancestor of all deepest nodes, *and* the height of the tree. This is quite simple:

If the root R has no left or right branch, then the height is 1 and the common ancestor is R. If the root R has either a left or right branch, then calculate height and lowest common ancestor of that branch, and the height with root R is one higher, but the lowest common ancestor is the same.

If there is a left *and* a right branch, then calculate height and lowest common ancestor of both branches. If the heights are different, then we return (height + 1) plus the lowest ancestor of that branch. If the heights are the same, then we return (height + 1), and R as the lowest common ancestor.

That should take cN steps with a small constant c if the number of nodes is N. And since we must visit every node N (at least to know that it has no branches), this cannot be improved upon.

---
Tags: algorithms, time-complexity, binary-trees
---


# Question
Title: Relation Between Priority Queue, Heap, Tree
There are $2$ "basic"/"fundamental" data structures due to the way memory works:

1. array
2. linked list

Then there are ADT that we implement using those two, for example: stack, queue and more.

When we arrive to priority queue we first need to implement and ADT called heap which can be implement using:

1. array
2. tree (which is ADT) the can be implemented using both array and linked list

So we have

array/linked list $\subset$ tree $\subset$ priority queue?

# Answer
> 4 votes
Arrays and linked lists are indeed simple data structures, but they are not more "fundamental" than other data structures. Everything in software is built out of contiguous memory to which the CPU has random access by address. All data structures are just abstractions built on top of that foundation.

A tree data structure is not composed of arrays and linked lists in any meaningful sense. You can implement a tree data structure using contiguous memory and pointers, just as you can implement a linked list using contiguous memory and pointers. If anything, a linked list is a special case of a tree in which each node has at most one child.

Saying that a tree is built from linked lists is like saying that a dinosaur is built from birds.

* It is confusing a special case as a composition. A dinosaur is not composed of birds; a bird is a special case of dinosaur. A tree is not composed of linked lists; a linked list is a special case of tree.
* However, the special case is itself only in a technical sense. If someone casually mentions the word *dinosaur*, they probably aren't thinking of birds. If someone casually mentions the word *tree*, they probably aren't thinking of linked lists.

You are also confusing the definition of *abstract data type*. An abstract data type is one where the operations are specified but the implementation is unspecified. A priority queue is an abstract data type, for which many concrete implementations are possible. Possible implementations of a priority queue include ones based on heaps stored in tree data structures; heaps stored in implicit trees in resizable array data structures; binary search trees; and many others. A linked list is an example of a concrete data structure which can be used to implement (among other things) a list abstract data type with operations for insertion, removal, indexing, etc.

# Answer
> 1 votes
It is a matter of perspective.

**About "basic" data structures.** Indeed array and linked list are fundamental data structures, two different implementations of the linear lists, of which stack and queue can be seen as offspring.

But you should also view *array* and *links* as basic *tools* to build other data structures, and sometimes they can be combined (I think hash tables with buckets use both constructs).

**About priority queues and the-like.** The binary heap I always consider to be a data structure that exists on so many levels. Distinguishing them helps in understanding the heap, but also makes you aware of these levels when looking at other data structures. The levels match most of your diagram, but the meaning of your symbol $\subset$ needs some explanation.

(1) Top level is the *priority queue*. It is an *abstract data structure* that contains pairs of data+priority. The (main) operations are "isEmpty", "insert", and "deleteMax".

There are several implementations of the ADT priority queue, each of them motivated by better complexity of the operations, or sometimes simplifying earlier complicated constructions.

(2) The binary heap is perhaps the most well known of these implementations. It is a *complete binary tree*, where the priority values are partially ordered: nodes have larger priority than their children, but there is no order between left and right subtrees. The standard ADT operations are implemented by moving the appropriate items along the tree, swapping nodes with parents or children when they have conflicting priority values.

However, although these operations are understood as if in a tree, their actual implementation does not use pointers/links as usual.

(3) As the tree used here is complete, its nodes can be mapped onto positions in an *array*, and rather than following pointers to parent and children, we compute their address. In this level, the binary heap is linear after all.

# Answer
> 0 votes
While I'm accepting the @Rotenberg's answer,

I think instead of think of the linked-lists, go one level deep and think about this in a linked nodes (linked objects or linked memory addresses) perspective which is what the real building box here. For arrays, the building box would be indexes (which again are memory addresses with content, but not linked to each other). Although Linked List Nodes are connected to each other (Nodes have their neighbors' addresses in them as pointers), Arrays doesn't have that. In memory, the indexes are continuously back to back and they don't contain the neighbor addresses within them

In that way it would be easy to think about the relationship between these data structures.

Now, as linked lists are built from nodes, trees are also built from nodes, just having a different structure. In special cases for tree, that structure becomes the same as @Rotenberg stated above.

In this image, it's a tree with only left childs for each node. Although it looks like a linked-list, we can't say it's a linked-list, because of the content of nodes. Even though they could be null as in shown image, there are two child pointers and one parent pointer for each node in a tree where in a linked-list, it's only two pointers for each node. So technically, it's not a linked-list.

So, considering this node approach, you can't really say that linked-lists are a subset of Tree structure. Both of them are just a collection of nodes connected to each other with different policies.

But, when it comes to heap and tree, you can say that heap is a special case of tree which is when a tree is a complete tree and also you can say that a heap is a subset of tree.

---
Tags: data-structures
---