# Question
Title: Best-case time: comparison-based sorting on a list of size n must make n-1 comparisons (reference to proof)
I am looking for a reference to a proof that for every list of size $n$ comparison-based sorting cannot make less than $n-1$ comparisons. Do you have a reference of a book that covers it (with page specification)? Or a scientific publication that covers the proof? The reference is needed for a publication.

# Answer
> 2 votes
Here is an easy argument that relies on the well-known lower-bound of $\log\_2 n!$ on the number of comparisons needed by any comparison-based sorting algorithm (which you can find in any textbook. See, for example, Theorem 8.1 in Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms - 3rd Edition."). Then it suffices to notice that: $$ \log\_2 n! \ge \log\_2 2^{n-1} = n-1. $$

Alternatively, you can prove your (weaker) lower bound from scratch. Here is a possible proof:

Suppose towards a contradiction that you have a deterministic comparison-based sorting algorithm $A$ that sorts can sort a list of $n \ge 2$ elements using at most $n-2$ comparisons. If you invoke $A$ on the list any permutation $L$ of $L^\* = \langle 1, 2, \dots, n\rangle$ with respect to the strict linear order of natural numbers, the output must be $L^\*$.

Consider then the graph $G = (\\{1, \dots, n\\},E)$ in which there is an edge $(i,j)$ iff $i$ is compared with $j$ by $A$ with input $L$. Sincere there are at most $n-2$ edges, $G$ has at least two connected components. Let $C$ be the connected component of $G$ containing vertex $1$. Given $i$ and $j$ consider the strict linear order $\prec$ such that $i \prec j$ iff one of the following conditions hold (we are essentially "moving" the elements in $C$ at the end of the order):

* $i,j \in C$ and $i\<j$; or
* $i,j \not\in C$ and $i\<j$; or
* $i \not\in C$, $j \in C$.

The output $A$ when the input is $L$ and the considered strict linear order is $\prec$ must still be $L^\*$ (since all comparisons performed by the algorithm return the same result with both $\prec$ and the linear order of the natural numbers). This contradicts the correctness of $A$.

# Answer
> 2 votes
Let us show a different bound, that will suffice for a "loose" bound of $n-1$. On this note, the answer above gives you the tight bound of $\Theta(n\log n)$, which is stronger than the one you are trying to prove.

$\textbf{claim:}$ To determine, via comparisons, $x\_m$ is the maximum in a given set $X$, every other $x\_i \in X$, for $i\neq m$ has to participate in either one of these comparisons:

* $x\_i$ has been compared to $x\_m$ and is lesser
* $x\_i$ has been compared to $x\_j$ and is lesser or equal, for some $x\_j$ s.t $x\_j\<x\_m$.

The proof is fairly straightforward; if we assume the claim is not true, we get that $x\_m$ has been "found" to be the maximum, and there must be some $x\_k$ that did not participate in either comparison as shown above. Hence, it is feasible $x\_k \> x\_m$ and we cannot decide $x\_m$ is the maximum.

Conclusion from the claim is that to find a maximum in a set of size $n$ will require at least $n-1$ comparisons.

I will leave it to you to finish the proof you need.

# Answer
> 0 votes
If $A$ is a comparison-based sorting algorithm and $L$ is any of its input lists then the comparison-graph $C\_{G}(L) = (V, E\_{L})$ has a set of vertices $V = \\{1,\ldots,n\\}$ and a set of edges $E\_{L}$ consisting of the pairs $(i,j)$ for which $L\[i\] \< L\[j\]$ is determined during the execution of $A$ on input list $L$.

The series of swaps executed by a comparison-based sorting algorithm $A$ on input list $L$ determines a permutation $\sigma\_{L}$ which sorts $L$, i.e. $\sigma\_{L}(L) = \tilde{L}$ where $\tilde{L} = \[1,\ldots,n\]$.

Assume by way of contradiction that a comparison-based sorting algorithm $A$ sorts a list $L$ of $n \geq 2$ elements in at most $n-2$ comparisons. Hence the edge set $E\_L$ of the comparison-graph $C\_{G}(L) = (V, E\_L)$ has cardinality $|E\_L| \leq n-2$. The comparison-graph $C\_G(L)$ thus can be partitioned in two non-empty parts $G\_1$ and $G\_2$ between which there exists no edge connection.

Consider vertices $k = L\[i\] \in G\_1$ and $l = L\[j\] \in G\_2$ and two extensions of $E\_L$: $E\_1 = E\_L \cup \\{(k,l)\\}$ and $E\_2 = E\_L \cup \\{(l,k)\\}$. Neither $(k,l)$ nor $(l,k)$ is in the transitive-reflexive closure $E^\*$ and thus the algorithm never executes a swap on either. Moreover, $A$ executes in exactly the same way on any input list $L\_1$ satisfying the relation $E\_1$ and on any input list $L\_2$ satisfying the relation $E\_2$. Hence their computations involve exactly the same series of swaps, i.e. $\sigma\_{L\_1} = \sigma\_{L\_2}$. This contradicts the fact that $L\_1$ and $L\_2$ are distinct (by their definition) and hence cannot both be transformed to the same sorted output $\tilde{L}$ by the same permutation. (Note that $L$ is consistent with $E\_1$ or $E\_2$, hence one of the lists $L\_1$ or $L\_2$ could be chosen to be $L$.)

---
Tags: sorting, lower-bounds, comparison
---


# Question
Title: Is sum type a disjoint or more of a multiplexer?
In Wikipedia article on "Sum Type" it is stated that sum type Curry-Howard correspondence is intuitionistic logical disjoint.

But sum type definition states that it is

> a data structure used to hold a value that could take on several different, but fixed, types. ***Only one of the types can be in use at any one time***, and a tag field explicitly indicates which one is in use.

whereas in disjunction you can have both values present at the same time.

To me it looks like sum type is more like a multiplexer than a simple "or", that is $(A\land S) \lor(A \land \lnot S)$, specially because its eliminator acts like a case statement.

I would appreciate if someone can make it clear for me.

# Answer
> 6 votes
> in disjunction you can have both values present at the same time

In classical logic, yes. But the Curry-Howard correspondence relates basic type theory to intuitionistic logic. And in intuitionistic logic, to speak intuitively, when you know that $A \vee B$ is true, you know which one is true.

The idea of intuitionistic logic is that if you can prove a proposition $P$, it doesn't mean “$P$ is true” (as it does in classical logic), but “I know how to prove $P$”. When the proposition is of the form $A \vee B$, the way to prove $A \vee B$ must either involve a proof of $A$ or a proof of $B$, plus the information of which side you chose to prove. This is not true in classical logic, which has $A \vee \neg A$ as an axiom, which doesn't tell you *which* of $A$ or $\neg A$ is true or how you'd prove it. The absence of this axiom, the excluded middle, is the defining feature of intuitionistic logic compared to classical logic.

It's possible to extend the Curry-Howard correspondence to classical logic, but this require a more complex type system, and the classical disjunction won't map to a sum type.

---
Tags: type-theory
---


# Question
Title: Is 2-SAT over Linear Real Arithmetic in P or NP?
The general boolean satisfiability problem (SAT) is NP-complete, and thus can't be solved in polynomial time (assuming $P \neq NP$). But the special case of 2-SAT is in P, and can be solved in linear time. 2-SAT formulas consist of the conjunction of clauses with two elements, e.g.,

$$ (a \lor b) \land (b \lor \lnot c) \land (a \lor c). $$

I am wondering about the case where the literals (e.g., $a$) are replaced with linear predicates (e.g., $Ax \leq b$, $x \in \mathbb{R}^n$). This transforms the SAT problem into an SMT (Satisfiability Modulo Theories) problem over the theory of Linear Real Arithmetic (LRA).

An example of a 2-SAT problem over LRA would be

$$ \text{Find } x \\ \text{such that } (P\_1 \lor P\_2) \land (P\_3 \lor P\_4) \land (P\_5 \lor P\_6), $$

where $P\_i = (A\_i x \leq b\_i)$ are linear predicates.

**Are there any polynomial-time algorithms for solving 2-SAT over LRA? Alternatively, is there any proof that 2-SAT over LRA is NP-complete?**

# Answer
> 4 votes
You can express the fact that a variable $x\_i$ is Boolean as follows: $$ (0 \leq x\_i \leq 1) \land ((x\_i \leq 0) \lor (x\_i \geq 1)). $$ You can express the condition $x\_i \lor x\_j \lor x\_k$ as $$ x\_i + x\_j + x\_k \geq 1. $$ If some of the variables are negated, you can also accommodate that, by replacing $x\_i$ with $1-x\_i$.

In total, we can express SAT as a special case of your problem, and so it is NP-hard.

Conversely, in order to show that a given "2-LRA" is feasible, it suffices to highlight which linear inequality is satisfied for each clause; checking this is linear programming, which is in P. This shows that your problem is NP-complete.

---
Tags: complexity-theory, satisfiability, constraint-satisfaction, constraint-programming, 2-sat
---


# Question
Title: Warnsdorff's rule: more errors with odd sized boards
I wrote an algorithm based on the Warnsdorff's rule to solve the knight's tour problem, where you need to create a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once.

I noticed something strange, though: **when the size of the chessboard is odd, about $50/60\\%$ of the starting positions, at least for small numbers, return a wrong path, while for even sized boards about $1\\%$ return a wrong result.**

Actually the errors increase more the board increases in size. On this plot you can see the different behaviour for even and odd sized boards:

I wonder if there is a theoretical (maybe heuristic) reason for this difference.

# Answer
**For odd-sized boards, a knight's tour must start and end on the same color as the corner squares of the board.** It follows that for about half (50%) of starting squares, there is no possible knight's tour and the search is bound to fail, explaining your error rate.

In contrast, for an even-sized board, the knight can start on either color. I didn't read your code in detail, but I can confidently conjecture that this explains the pattern you observed!

* For example, consider a 7x7 board, and assume the corner squares are black. Then there are 25 black squares, and 24 white squares. Any knight's tour alternates between black and white squares, but it must visit more black squares than white squares. So in order to visit all 49 squares, it has to start on a black square.
* On the other hand, consider a 6x6 board. There are 18 black squares, and 18 white squares. A knight's tour here alternates between black and white squares, but it my start on either color

I suspect that if you fix this and always start the knight's tour on the same color, you will see a more similar range of error rates for even- and odd-sized boards.

---

**Edit:** We can be a bit more precise about the error rate. If $n$ is odd, then $\frac{n^2 + 1}{2}$ squares are black, and $\frac{n^2 - 1}{2}$ squares are white, out of $n^2$ squares total. So the error rate for a random starting square is *at least* $$ \frac{(n^2 - 1)/2}{n^2} = \frac{1}{2} - \frac{1}{2n^2}, $$ which is actually a bit less than 50% if $n$ is small.
> 4 votes

---
Tags: algorithms, graphs, algorithm-analysis, heuristics, python
---


# Question
Title: How to efficiently see if a value is in a set
I was curious is there a really efficient way to see if a value is in a set? This question comes from me thinking about youtube views. As far as I understand youtube view count goes up for every unique view it receives (let's imagine it does if it doesn't already). There are millions or billions of viewers per video. That means to see if it a person first time seeing a video is O(1) (hash set). However, that means the set size has to be possibly millions or billions in length per video (there are a lot of videos), that's a lot of space. How can you get the same result, adding to a set of unique users without possibly using all that space? Is there a more space-efficient solution possible?

# Answer
Great question! First, I do not know how YouTube's view counting works, but I will answer the question you ask about counting unique visitors.

This problem is known as the Count-distinct problem. If you want to really count the *exact* number of unique values, then in the worst case, it can only be done if you save the entire set of values seen so far; this requires at least $\Omega(N)$ space to store whether or not you have seen $N$ different values, so it becomes infeasible if $N$ is large.

However, there are much better solutions known which are *approximation algorithms* to the true value, such as HyperLogLog. The idea of these solutions the following algorithm, which is straightforward to understand, and quite beautiful:

* For each input value, calculate $\mathsf{hash}(v)$, where $\mathsf{hash}$ is a hash function. Look at how many $0$s are at the *end* of $\mathsf{hash}(v)$ (trailing zeros), and keep track of the *maximum* number of trailing zeros seen so far, $k$. Then estimate the number of distinct elements as $2^k$.

It turns out that the estimate $2^k$ is a good approximation to the real number of unique views, and it only requires storing $k$, which takes very little space.

But there are improvements to make it even more accurate, and these are incorporated in algorithms such as HyperLogLog.
> 2 votes

---
Tags: algorithms, data-structures, sets, hash
---


title: Prove that T3SAT is NP-Complete

text:
# Question
Title: Prove that T3SAT is NP-Complete
Instance: A boolean formula f(x1, . . . , xn) in 3CNF form, with m clauses labelled C1, . . . , Cm.

Is there an assignment to x1, . . . , xn such that every third clause is False and all other clauses are True? That is, Ci is False for all i ≡ 0 (mod 3), and Ci is True for all i ≡ 1 or 2 (mod 3).

how do I prove that this is NP-Complete?

I do know the fact, that there is a way to reduce this problem to 3SAT but I couldn't prove it just by adding an extra variable, to the set of clauses. Is there any better way to go about this?

# Answer
> 0 votes
Consider $C\_i=x\_1\vee x\_2\vee x\_3$, $i\equiv 0\pmod 3$, where $x\_1,x\_2,x\_3$ do not show up in other clauses. Then the problem becomes the normal 3SAT problem.

---
Tags: np-complete, np-hard, 3-sat
---


# Question
Title: Decidability for intersection of context free and regular languages
I am wondering if the following are decidable or undecidable and why. L is a CFL and R is a regular language. How does the complement of the context-free language change the decidability of the intersection?

∩=∅ and $\bar{}$∩=∅

This is what I think but I am not sure so any help is appreciated.

For , I think this is decidable because intersection of a CFL and a regular language is a CFL so you can build CFG for it. However, it can also be undecidable as we can check membership for all elements in Σ∗ which can take forever so we don't know if there is going to be an element that'll be in this intersection.

As for $\bar{}$, this one I don't really know at all.

Please excuse me if I made mistakes or if my explanation was unclear. I am new to the topic and trying to wrap my head around it and any help is appreciated.

# Answer
The first one you have solved correctly. Emptiness of context-free languages is decidable.

For the second, we can rewrite $\bar L \cap R = \varnothing$ into $R\subseteq L$. This is undecidable (even for $R=\Sigma^\*$).
> 1 votes

---
Tags: complexity-theory, context-free, undecidability, decidability
---


# Question
Title: What could be a good loop invariant for this?
I am currently new and learning about loop invariants. I have come across this pseudocode where the goal is to shift the elements inside an array with ***N*** size in a clockwise direction by ***K*** steps.

Pseudocode:

>

Is `at every iteration, new_index is in [0,N)` a good loop invariant? I am really confused about how to pick a good one. Any help would be appreciated.

# Answer
> 0 votes
This would not be a good loop invariant, since its trivial (by the definition of modolu).

A good loop invariant here would be to assert that at step $m$, $A\_{rot}$ will contain the first $m$ elements after rotation.

This loop invariant is *not* trivial anymore (you will need to work a bit to prove it) - and using it when $m=N$ will immediately prove that the algorithm is correct.

---
Tags: algorithms, loop-invariants
---


# Question
Title: Knapsack problems with two sums and two sets
For an algorithm homework, I'm asked to give a solution for a knapsack problem. I have in input a list of products. A product is assigned a cost and a number of calories. So I have two sets, one of money and one of kcal. My goal is to choose products that give an equal sum of money and kcal.

for example if I have this input: (1, 3), (2, 4), (5, 8), (4, 5)

and the money sum equal to $m=7$ and kcal sum equal to $k=12$, I need to choose products that satisfies the two sums exactly. In my example I will choose the products (2, 4) and (5, 8). My solution only needs to return true if there exists products that match the requirement, otherwise return false. No need to return a set of products

I already wrote a solution using recursion based on the subsetsum problem, where I recall my function using the last product or not. This solution works, but it's too slow → $\Omega(2^n)$.

```
def isSubsetSum(set, n, sum, set2, sum2):
    if (sum == 0 and sum2==0):
        return True
    if (n == 0 or (sum < 0 or sum2 < 0)):
        return False

    if (set[n] > sum) or (set2[n] > sum2):              # if one of the two values (money, calories) is bigger than the sum
        return isSubsetSum(set, n-1, sum, set2, sum2)   # we avoid using this product -> recall with n-1

    inclusion = isSubsetSum(set, n-1, sum-set[n], set2, sum2-set2[n]) # we recurse includig the last product
    exclusion = isSubsetSum(set, n-1, sum, set2, sum2)  # we recurse excluding the last product

return inclusion or exclusion

```

I tried to change my subsetsum function into a dynamic programming approach, but I have difficulties in changing my function to work with the two sets (set of money and set of calories).

I talked with the teaching assistants, and they oriented me in choosing the knapsack problem instead of the subset sum problem. I saw how the knapsack dynamic programming approach is, but I have the same problems as before with subsetsum in changing the problem to work with my input.

I think I am missing something, it would be cool if you could help me understand where I'm wrong.

# Answer
> 1 votes
If you understand the subset sum algorithm, it's not very difficult to turn it into a "two-dimensional" version.

For an element $e$, let $m(e)$ be the "money" and $c(e)$ be the "calories" of $e$.

Let $\text{opt}(i, M, C)$ be true if there exists a subset of elements $S$ such that $\sum\_{e \in S}m(e) = M$ and $\sum\_{e \in S}c(e) = C$, and false otherwise. Then, simply put, $$ \text{opt}(i, w\_m, w\_c) = \bigvee \begin{cases} \text{opt}(i-1, w\_m, w\_c)\\ \text{opt}(i-1, w\_m - m(i), w\_c - c(i)). \end{cases} $$

This is pseudo-polynomial in the target weights.

---
Tags: dynamic-programming
---


title: What makes an algorithm greedy?

text:
# Question
Title: What makes an algorithm greedy?
I have a simple graph $G = (V,E)$ and each vertex has a range $\[a,b\]$. Every two vertices are connected only if $\[a\_1, b\_1\]$ and $\[a\_2, b\_2\]$ have a common subrange.

Each range of vertex is rV1 = \[0,5\] rV2 = \[1,3\] rV3 = \[2,10\] rV4 = \[4,9\] rV5 = \[6,7\] rV6 = \[8,12\] rV7 = \[11,13\]

Graph Created based on above ranges.

Based on the algorithm below i have to color the graph.

```
ranges = rV1,rV2,rV3,rV4,rV5,rV6,rV7...

COLOR_INTERVAL_GRAPH(rV1,rV2,rV3,rV4,rV5,rV6,rV7...){
if(number of rVi > 0){
 C_m  = MAXIMAL_COLOR_CLASS(rV1,rV2,rV3,rV4,rV5,rV6,rV7...);
 //paint C_m vertices with color m.
 //new_ranges <- remove C_m from rV1,rV2,rV3,rV4,rV5,rV6,rV7...
 return {C_m} U COLOR_INTERVAL_GRAPH(new_ranges)
 else:
   return []

MAXIMAL_COLOR_CLASS(new_range){
C = []
i = 1
while(i <= new_range.size()){
  C = C U {Vi}
  j = i+1
  while(j <= new_range.size() AND rVi (not common subrange with rVj)){
  j = j+1
i=j
return C

```

How i know if the above algorithm uses the greedy strategy?

My work so far:

The algorithm has the 'greedy choice property' since it paints the most each turn, by choosing the best solution to the current subproblem without caring about future problems or backtracking.(can this be improved and how)?

Graph Colored (Is the graph colored correctly?).

# Answer
Many problems can be written in the form "You start with an initial state. You make a choice what your first action should be and perform the action, getting into a new state. You make another choice for your second action and perform that action, and so on. After a limited number of actions, you will arrive at the final state. You never undo any action that you have taken, and the effort determining the next action is limited". That's a greedy algorithm.

For example, the travelling salesman problem can be handled with a greedy algorithm. You just pick the first, second, third etc. place to visit, and your last action is to return to the starting point. The "limited effort" requirement is there so you don't solve the whole problem, take the first step, and call it a "greedy algorithm".

If you're lucky, you can prove that a greedy algorithm will find the optimal solution. Or you can prove that a greedy algorithm that isn't much worse than the optimal solution. You can vary the effort to determine the next step, and that may make your greedy algorithm slower but with better results.

A "Greedy" algorithm is often not optimal when making one choice that seems a good choice now makes it impossible to make a good choice later.
> 2 votes

# Answer
**A greedy algorithm looks for an optimal solution in a restricted neighbourhood of your starting point.**

**Say you want to find the shortest path from a root to a leaf in a rooted tree** (where the edges are marked with a positive integer indicating distance).

Start at the root. Check all the edges adjacent to the vertex (leading to the children of the root). This is your restricted neighbourhood. A greedy algorithm would select a shortest edge (randomly picking one if there are several shortest choices). It then moves to the next vertex at the other end of the selected edge and repeats, looking again locally at the edges adjacent on the new vertex. Once again it selects a shortest edge.

It is easy to see that **this does not always leads to an optimal solution** for the shortest distance from the root to a leaf.

**Some greedy algorithms will however obtain an optimal solution** (if not, you can often get by with dynamic programming). ***The main point is that the algorithm is greedy in the sense that it looks for the best optimal solution in an immediate local and limited range. The algorithm never reaches a global overview of the tree, i.e. its computation proceeds purely locally.*** Needless to say, greed is not always a great strategy.

**A case where a greedy approach works very well is *the coin change problem*.**

For this problem a financial amount to be returned in coins. The greedy algorithm produces change consisting of the fewest coins so the cash register is not depleted too soon. It does this by picking the largest coin that fits the initial amount to be returned and finds out how many of these coins fit that initial amount. It subtracts the total of these coins from the initial amount and repeats the strategy on the remaining amount. Again, it looks for the largest coin fitting this amount (a local situation, determined by the amount reached).

Existing currencies are designed to make this greedy approach work, i.e. the greedy algorithm will return change using the least amount of coins. You can design imaginary currencies for which the greedy algorithm will not work.

There are more formal approaches to the greedy algorithm strategy, but I'd merely repeat standard text books on the greedy choice property etc.
> 2 votes

# Answer
"A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage." (from Wikipedia) In other words, it does not backtrack. It builds up the solution incrementally, and when it adds something to the solution-so-far, it never later removes it (or, when it makes a decision, it never later undoes that decision).

Does that describe the algorithm you are looking at?

If you want to justify that it satisfies the greedy choice property, it might help to precisely state what is the "subproblem" that is solved at each step.
> 1 votes

---
Tags: algorithms, greedy-algorithms, induction, colorings
---


title: Kinetic Data Structure

text:
# Question
Title: Kinetic Data Structure
Currently i am studying Kinetic Data Structure thesis by Julian Basch. I am feeling stuck in some points. Are there any other resources to understand it properly ??

Edit:- I am very new to this data structure. Are there any blogs or video tutorial to understand an introduction to the concept which is a bit more in depth than the Wikipedia page.

# Answer
> 1 votes
First, we should consider a *dynamic data structure*. Such a data-structure keeps some sort of record during a sequence of modifications, usually insertions and deletions. The main idea is that this data structure only needs to do a little bit of work for each insertion and deletion, and therefore is more efficient than recomputing a static data structure after each modification.

A *kinetic data structure* is a variant on a dynamic data structure, where the modifications are of a geometrical nature. Often, the underlying data is a pointset in $\mathbb{R}^d$ and the modifications correspond to small movement of these points. Again, the idea is to ensure these small modifications only require a small number of changes in the data structure, such that we are much faster than recomputing the data structure after each movement step.

---
Tags: data-structures, computational-geometry
---


# Question
Title: Iteratively enumerating all permutations of $N$ objects using a generating set
The group theory of $S\_n$ shows that all permutations of $n$ objects can be generated from the $n$-cycle $a:=(1 2 3 .. n)$ and the transposition $b:=(1 2)$. (See Theorem 2.5 at https://kconrad.math.uconn.edu/blurbs/grouptheory/genset.pdf)

One can use this fact to label and enumerate permutations. For example, this shows such an enumeration for $S\_3$ where the left hand side shows the action of the given element on $\[0 1 2 3\]$ and the right hand side shows a "labeling" representation in terms of $a$ and $b$:

```
0 1 2 3  ()
1 2 3 0  (a)
2 3 0 1  (aa)
3 0 1 2  (aaa)
0 3 1 2  (aaab)
3 1 2 0  (aaaba)
1 2 0 3  (aaabaa)
2 0 3 1  (aaabaaa)
0 2 3 1  (aaabaaab)
2 3 1 0  (aaabaaaba)
3 1 0 2  (aaabaaabaa)
1 0 2 3  (aaabaaabaaa)
1 3 0 2  (aaabaaabaaab)
3 0 2 1  (aaabaaabaaaba)
0 2 1 3  (aaabaaabaaabaa)
2 1 3 0  (aaabaaabaaabaaa)
2 0 1 3  (aaabaaabaaabaaab)
0 1 3 2  (aaabaaabaaabaaaba)
1 3 2 0  (aaabaaabaaabaaabaa)
3 2 0 1  (aaabaaabaaabaaabaaa)
1 0 3 2  (aaabaaabaaabaaabaab)
0 3 2 1  (aaabaaabaaabaaabaaba)
3 2 1 0  (aaabaaabaaabaaabaabaa)
2 1 0 3  (aaabaaabaaabaaabaabaaa)

```

Making this more precise, given any element $\sigma \in S\_n$ and a generating set G we can find some positive integer $k$ and $d\_i \in G$ for $ 1 \leq i \leq k$ such that $\sigma = \sum\_{i=1}^{k} d\_i$.

Let's say that a "labeling" is a map that sends every element $\sigma$ of $S\_n$ to a specific choice of representation $d\_{\sigma, 1}, ..., d\_{\sigma, k\_\sigma}$.

This observation leads to some interesting questions:

1. Is there a straightforward way to produce a labeling for $S\_n$ given a generating set $G$?
2. Even better, can you produce a *minimal* labeling in the sense that no element could be represented by a shorter product of elements from the generating set?
3. Is there a correspondence between this method of generating permutations and the classical solutions like backtracking, "plain changes", or Heap's method, perhaps given some other set of generating elements rather than this specific choice of $a$ and $b$? (See https://www.cs.princeton.edu/~rs/talks/perms.pdf) That is, does there exist a choice of generating set G and labeling L that would enumerate the elements in the same order as the other methods when the elements are sorted by label lexicographically?

Thanks in advance!

# Answer
> 1 votes
My suggestion would be to build up the Cayley graph for $S\_n$ with generating set $G$ iteratively, using breadth-first search to traverse the graph. This will give you a labelling for every element of $S\_n$, and moreover, because breadth-first search finds the shortest paths, it will also give you a minimal labelling.

I don't know whether there is any relationship to those other methods of enumerating permutations.

---
Tags: algorithms, combinatorics, permutations, group-theory
---


# Question
Title: Definition a Turing machine (which may or may not halt) as a function... notation?
I would like to define a Turing machine as follows.

Let Z be an alphabet, and let L be the set of all sentences of this alphabet. For instance, Z={0,1}, then L is the set of all binary sentences.

A Turing machine is a function which takes a (binary) input and produces a (binary) output:

$$ TM: L \to L $$

However, it is also possible that it doesn't halt. In this case, it is not from $L\to L $.

Initially, I was thinking of mapping $TM: L \to L \cup \nexists$. And claim if it doesn't halt, it maps to $\nexists$.

BUT, here are my concerns:

1. If TM never halts because it keeps printing symbols forever, then it does map to a sentence of L. It is just that the sentence is infinite.
2. If TM never halts because it gets stuck somewhere (after n symbols are printed), then it did produce a sentence of L, its just that it is stuck.

So I all cases it maps from L to L.

So is the right answer simply to claim from L to L (where sentences can contain infinitely many symbol) and just claim TM is either computable or non computable?

# Answer
> 2 votes
This is not the definition of a Turing machine. "Turing machine" is a term of art with a standard, accepted definition. The right answer is "none of the above" - the premise is faulty, as Turing machine already has a definition that is different from what you've written.

You seem to be attempting to come up with a way to represent the externally visible behavior of a Turing machine. And you have correctly identified reasons why your approach does not work. (It's not correct that in case 1 it does map to a sentence of $L$, because an infinite sequence is not in $L$; $L$ consists of only finite sequences.) No, your final question is not the correct approach either. A TM cannot be "computable" or "not computable"; computability is a property of a language, not a Turing machine.

---
Tags: turing-machines, notation
---


title: IEEE 754 conversion

text:
# Question
Title: IEEE 754 conversion
I'm trying to convert 3.2 into IEEE 754 format. We find that $(3)\_2=11$ and we also find that

$0.2\*2=0.4 -0$

$0.4\*2=0.8 -0$

$0.8\*2=1.6 -1$

$0.6\*2=1.2 -1$

and this cycle repeats so $.2=00110011...$

finally we find $11.00110011...$

we normalize $1.1001001...\*2^{1}$ and calculate the exponent $127+1=128=10000000$

we find that the IEEE 754 conversion is 010000000 10011001100110011001100

but all online converters give a one in the last place, or, to put it as an example, it looks like this

010000000 10011001100110011001101

Why is this so? Did I do something wrong?

# Answer
> 2 votes
You rounded down, but the online converters rounded to nearest.

Think of it this way: the "real" mantissa would be $\frac{8}{5}$. You subtracted the implicit one to get $\frac{3}{5}$, then multiplied by $2^{23}$ to get the significand field plus an "error" term:

$$\frac{67108864}{5} = 13421772 + \frac{4}{5}$$

You can see that $13421772$ in decimal is $10011001100110011001100$ in binary, but that error term is greater than $\frac{1}{2}$, so it should be rounded up.

Of course, that's not how IEEE-754 rounding is done in practice.

---
Tags: floating-point, number-formats
---


# Question
Title: Finding a hash function, so that the set of hash functions is universal
Problem:

Let $U = \\{0,1,2,3,4,5\\}$ be a universe of keys and $T = \\{0,1,2\\}$ we observe follwing 5 hash functions which map from $U$ to $T$ :

$$h\_1(x) = (x+1) \mod{3} \hspace{5mm} h\_2(x) = (x+2) \mod{3} \hspace{5mm} h\_3(x) = x \mod{2} \\ h\_4(0) = h\_4(5) = 2 \hspace{5mm} h\_4(1) = h\_4(2) = 1 \hspace{5mm} h\_4(3) = h\_4(4) = 0 \\ h\_5(0) = h\_5(1) =2 \hspace{5mm} h\_5(2) = h\_5(3) = 1 \hspace{5mm} h\_5(4) = h\_5(5) = 0 $$

Find a hash function $h\_6 : U \to T$ so that the set $\\{h\_1,h\_2,h\_3,h\_4,h\_5,h\_6\\}$ is a universal set of hash functions.

Questions:

So, I am new with the topic of universal hashing and hash functions. I am although knowledgeable enough to know, that a set of universal hash functions is composed of this following definition.

$$ \frac{|\\{h \in \mathcal{H} |h(a) = h(b)\\}|}{|\mathcal{H}|} \leq \frac{1}{t}$$

when $t = |T|$

So right now i have the idea that i should choose my hash function so, that:

$$\frac{|\\{h \in \mathcal{H} |h(a) = h(b)\\}|}{6} \leq \frac{1}{3}$$

Though i do not really understand what the set above means, or how i can manipulate it so that i can essentially get a chance of $\frac{1}{3}$ overall. Essentially choosing that $h\_6$ so that my above set is equal to $2$.

# Answer
The value $|\\{h\in \mathcal{H}\mid h(a)=h(b)\\}|$ is meant to represent: for arbitrary $a\neq b \in U$, this value is the number of hash functions for which $a$ collides with $b$.

For example, for $a=0,b=1$ we have that $h(0)=h(1)$ only when $h$ is $h\_5$ \- so this here will be $1$.

But for $a=0,b=3$ we have that $h(0)=h(3)$ when $h$ is either $h\_1$ or $h\_2$ \- thus here, the value will be $2$.

So your task is to find an $h\_6$ that will not increase this value for combinations of $a,b$ that already have a lot of collisions.
> 0 votes

---
Tags: hash
---


title: How Turing Machine Can Never Stop?

text:
# Question
Title: How Turing Machine Can Never Stop?
My professor discussed the following Turing machine M' on input (,x):

1. Generate number n
2. Run M on X, for n steps
3. If M stops, accept

I don't understand No.3

If we are running M on input X for final number of steps then there is no way for M not to stop... so why he wrote if M stops?

# Answer
Step 3 could be phrased more properly as "If M has already stopped by the time we get to N steps, accept". Does that help to clarify?
> 20 votes

# Answer
Its an informal phrasing. I think it's easiest to stay with informal wording and just use more words to clarifiy.

**M'** cannot "run **M** for *n* steps, in the most literal of notation. You instead run another Turing machine, which I will call **Mi**, where the "i" means "insturmented." This new Turing machine has a few properties

* Its input tape is initially filled with a counter (initially set to *n*) followed by *X*.
* It provably decrements this counter towards zero. After some number of decrements occur, the state of the tape is identical to the state that **M** leaves the tape in after *n* steps (this is what they mean by "simulating." It's not the same machine, but it yields the same results)
* It halts when the counter hits 0, or when it is done simulating a step of **M** that would cause **M** to halt.

It is actually reasonably trivial to construct such a machine. It is typically much slower than **M**, but Turing completeness is not concerned with that.

So what **M'** does is actually write *n* to the tape, followed by *X*. It then executes **Mi**, which, when it completes, either leaves a zero or a non-zero value in the counter. **M'** then uses that value to determine whether the simulated **M** halted, or if **Mi** had to cut it off beacuse it had run the specified number of steps.

This is, of course, one implementation. It doesn't have to be exactly that structure. But this is one structure which can be used to construct the proof your professor is using.
> 5 votes

# Answer
Revisiting the formal definition of a turing machine: https://en.wikipedia.org/wiki/Turing\_machine#Formal\_definition Here you have a set of 'final states' or 'accepting states'. These states do not have transitions to other states, so once the TM reaches an accepting state it can consider "stopped". I believe 3 is asking whether the simulated TM has reached an accepting state after N steps.
> 1 votes

---
Tags: turing-machines, computation-models, turing-completeness
---


# Question
Title: Problem with Understanding Pumping Lemma
I'm trying to solve this exercise that asks to determine whether a language is regular or not.

Following the flow of the course I figured that the exercise is a test for Pumping Lemma application. But for this particular language I'm having a problem understanding where I'm at fault.

The language given is $L\_3 = \\{1^{2k+1}0^{2j} | k\geq 1 \text{ and } j\geq 0 \\} $.

I began by assuming there's a DFA with n states that reads $L\_3$, let that number of states be n. Then, for any $z\in L\_3$ with a length $\geq n$ the PL should apply.

Let $z=1^{2n+1}0^{2j} \text{, } 2n+1+2j \> n $.

Then z would be:

$$z=1...10...0=1...11...11...0$$

where $u=1...1=1^a$, $v=1...1=1^b$ and $w=1...0$ with their respective lengths for which $a+b\leq n$ and $|w|=2n+1+2j-a-b$ are true.

Then I can take any $uv^iw$ :

$$uv^iw= 1^a1^{ib}1^{2n+1-a-b}0^{2j}= 1^{a+ib+2n+1-a-b}0^{2j}= 1^{2n+1+b(i-1)}0^{2j}$$

Let's take i=2, then:

$$uv^2w=1^{2n+b+1}0^{2j}$$

But for any b that is odd $uv^2w \notin L\_3$$.

However, considering the definition of a regular language I decided to make sure by trying to find a DFA for it; and I did. I found a DFA with 7 states that reads it. I'm quite sure that my DFA is okay, so I'm definitely making a mistake with my method above. What is that?

# Answer
> 1 votes
The language considered is indeed regular, since it can be expressed as a regular expression $111(11)^\*(00)^\*$.

Your mistake is that in the decomposition $z = 1^a1^bw$, you CANNOT chose $b$ to be odd. The pumping lemma states:

> If $L$ is regular, then there exists $n\geqslant 0$ such that for any $z\in \Sigma^\*$, $|z| \geqslant n$, there exists a decomposition $z = uvw$ such that
>
> * $|uv| \leq n$;
> * $|v| \> 0$;
> * for all $i\geqslant 0$, $uv^iw \in L$

However, you cannot chose the decomposition yourself, you just know that there exists one. In this particular language, any decomposition $uvw$ of $z = 1^{2n+1}0^{2j}$ will be such that $|v|$ is even.

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


# Question
Title: What is the relation between Topological Sort and Strongly Connected Components?
Both the Topological Sorting algorithm and the algorithm to find Strongly Connected Components build a stack whose top is the last visited vertex.

I find difficult to find an explaination because Topological Sorting algorithm is applied on DAGs, whereas the other one can be applied on any type of graph, especially cyclic.

Hope my question makes sense, thank you in advance.

# Answer
> 5 votes
## One connection could be the following:

Given a graph $G$, construct the graph $G'$ in which every connected component of $G$ is a node, and two nodes in $G'$ have a (directed) edge if there is an edge between any two nodes in the connected components they represent in $G$.

Sometimes this graph $G'$ is known as the "supergraph" of $G$.

Now, its not hard to see why $G'$ is a DAG, and hence has a topological sort, which induces a partial ordering on $G'$.

You can "extend" this partial ordering into $G$ by saying that two nodes in the same connected component will be "the same", and two nodes from different components will relate if their respective components relate in $G'$.

---
Tags: graphs, depth-first-search, connected-components, topological-ordering
---


# Question
Title: Does a simple calculator require an operating system?
I don't mean a TI-84 type calculator, and I also do not mean a simple calculator app on your phone.

Does a basic scientific calculator require an operating system?

# Answer
> 8 votes
No.

Operating systems have several purposes, such as interfacing with the hardware and, managing multiple concurrent or sequential applications and providing protection between different users. A calculator has only user and only one application so there's nothing to manage there. And the hardware is simple enough that the single application may as well just talk directly to it, rather than going through the intermediate layer of an operating system.

# Answer
> -1 votes
Of course, old 80s Calculator have OS that is written completely in c and compiled and feeded into Calculator's hardware

# Answer
> -5 votes
**yes we need a os for calculator which will manage the embedded os .purpose of os is to control hardware resources.OS by itself can not be used, it will need an embedded os for calculator**

---
Tags: operating-systems
---


# Question
Title: Examples of comparison-based algorithms that are not a sort or a search over lists
**Can you share examples of comparison-based algorithms used in practice that are not a sort or a search over lists?** *Heapify* is an example of a comparison-based algorithm that is neither a sort nor a search. Heapify is of course part of Heapsort and still operates over lists. Are there other examples of comparison-based algorithms that are not sorts or searches over lists and are used in a different context than sorting or searching or operate over different data structures?

**By comparison-based I mean the standard definition:** every basic operation (swaps, assignments, ...) need to be carried out on the basis of a series of comparisons only. This includes the transitive closures of the outcomes of comparisons (as in quicksort: a swap can be carried out on elements a and b when a \> p and p \> b has been determined, where p is the pivot. In this case no direct comparison between a and b was made, but their order is deduced based on the transitive closure of the relations). The elements to be ordered need to satisfy a linear order (total order), i.e. a \<= b or a \>= b always needs to hold (as for the case of integers, real numbers, words (lexicographical order) etc.) Put another way: these are algorithms for which the computation can be modelled via a decision tree. Their execution is the same on data that share the same relative order. In the case of lists: the execution is the same on the reverse ordered list \[4,3,1\] as on the reverse ordered list \[50,6,5\].

**I prefer examples for which the comparison-time (worst-case or average-case) has been determined, but I'm open to others examples for which this has not been done.**

It seems that the *Knuth–Morris–Pratt algorithm* and *Booth's Algorithm* may fall into this category, i.e. *string matching algorithms*.

Pseudonym suggested *priority scheduling* below (I did not check this sufficiently yet but it seems a possible fit). Any others?

# Answer
> 2 votes
I summarise some comparison-based algorithms found thanks to suggestions here and also in relation to examples I know of or found online. The Huffman algorithm may raise some eyebrows, but it seems to have all the hallmarks of a comparison-based algorithm. Do add any if you know of more examples (or share criticism on the ones listed below if you deem them not to fit). I find the usual presentation of comparison-based computation a little short on examples, so aim to use this list to show their impact beyond sorts and searches. I did not add priority scheduling yet but may add it later pending a closer look at how it goes beyond sorting.

**Min-max heap construction.** Min-max heaps combine a min-heap and a max-heap. The data structure provides constant time retrieval and logarithmic time removal of both the minimum and maximum elements. It forms a useful data structure to implement a double-ended priority queue.

**Beap construction.** A compromise between costs of searching and updating is to create a structure with the same father-son relationship as a heap, and with most nodes having two sons. The difference is that in general each node will have two parents--a beap.

**String matching.** A string-matching algorithm finds the starting index $m$ in string $s$ that matches the search word $w$. The Knuth–Morris–Pratt algorithm.

**Lexicographically minimal string rotation** Aka least circular substring is the problem of finding the rotation of a string possessing the lowest lexicographical order of all such rotations.

**Prefix order construction.** The Huffman file encoding algorithm. Huffman code is an optimal prefix code used for lossless data compression.

**Balanced k-d-trees construction.** Useful for searches involving a multidimensional search key (e.g. range searches and nearest neighbour searches) and creating point clouds.

---
Tags: algorithms, sorting, search-algorithms, comparison
---


# Question
Title: Does pattern matching require having the data on one machine?
Is it possible to use pattern matching algorithms such as FP-Trees and others on data that resides in multiple machines?

Basically when doing pattern matching do you have to have all your data on the same disk?

# Answer
> 1 votes
It depends on the algorithm. Most algorithms are designed under the assumption that all the data resides on one machine, but if the data lives on multiple machines, you could of course adapt the algorithm to that situation (potentially with a significant loss of performance).

---
Tags: distributed-systems, pattern-recognition
---


# Question
Title: Why the choice of the adjacent vertex with the least degree is a good heuristic for the hamiltonian path problem?
Even if the hamiltonian path problem is NP-hard there exist heuristics which return a correct path for many instances in linear time. In particular one of the main rules is always choosing the adjacent vertex with the least degree; there are also strategies to manage tiebreaks but I think they are even more difficult to explain.

I would like to ask: are there theoretical reasonings which explain why it's a good heuristic or is the rule just an experimental one?

# Answer
Here is the simple reason. A graph with more edges is more likely to have a Hamiltonian path.

---

Let us see how that simple reason is applied in detail.

Suppose we want to find a Hamiltonian path in $G$. Suppose we have selected made some initial choices, i.e., we have selected some path $v\_0, v\_1, \cdots, v\_k$.

Suppose we extend the path by two more vertices. There are the two ways of our concern. .

1. Select $r\_1$, the vertex of least degree among the vertices adjacent to $v\_k$, as $v\_{k+1}$. Selected some vertex $r\_2$ as $v\_{k+2}$.
2. Select $m\_1$, a vertex *not* of least degree among the vertices adjacent to $v\_k$, as $v\_{k+1}$. Selected some vertex $m\_2$ as $v\_{k+2}$.

Consider the remaining problem after we have selected $v\_{k+1}$ and $v\_{k+2}$.

In the first way, the problem is to find a Hamiltonian path in $G$ with vertices $v\_0, v\_1, \cdots, v\_k, r\_1$ removed, starting from $r\_2$.

In the second way, the problem is to find a Hamiltonian path in $G$ with vertices $v\_0, v\_1, \cdots, v\_k, m\_1$ removed, starting from $m\_2$.

Since **the remaining graph in the first way has more edges than the remaining graph in the second way**, we are more likely to succeed in the first way.

Can the difference in the starting point, $r\_2$ or $m\_2$ affect the likelihood respectively? Of course. However, it is hard to see how we can choose $m\_2$ better in the neighborhood of $m\_1$ than choose $r\_2$ in the neighborhood of $r\_1$. So, the choice of $r\_2$ and the choice of $m\_2$ is unlikely to flip the advantage of the first way.

---

This heuristic, choosing the adjacent vertex with the least degree, can be considered as an application of the principle "Most Constrained Variable first" in the domain of the problem of Constraint Satisfaction.
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis, heuristics, hamiltonian-path
---


# Question
Title: Why are graphs represented as adjacency lists instead of adjacency sets?
In answering this question, I was looking for references (textbooks, papers, or implementations) which represent a graph using a *set* (e.g. hashtable) for the adjacent vertices, rather than a list. That is, the graph is a map from vertex labels to sets of adjacent vertices:

```
graph: Map<V, Set<V>>

```

In fact, I thought that this representation was completely standard and commonly used, since it allows O(1) querying for an edge existence, O(1) edge deletion, and O(1) iterating over the elements of the adjacency set. I have always represented graphs this way both in my own implementations and teaching.

To my surprise, most algorithms textbooks do not cover this directly, and instead represent it using a *list* of labels:

```
graph: Map<V, List<V>>

```

As far as I understand, adjacency lists seem strictly worse: both representations support O(1) vertex additions and iteration over adjacent edges, but adjacency lists require O(m) for edge removal or edge existence (in the worst case).

Yet I am baffled that, for example Cormen Leiserson Rivest Stein: Introduction to Algorithms, Morin: Open Data Structures, and Wikipedia all suggest using adjacency lists. They mainly contrast adjacency lists with adjacency matrices, but the idea of storing adjacent elements as a set is only mentioned briefly in an off-hand comment as an *alternative* to the list representation, if at all. (For example, Morin mentions this on page 255, "What type of collection should be used to store each element of adj?") I must be missing something basic.

# Q: What is the advantage of using a list instead of a set for adjacent vertices?

* Is this a pedagogical choice, an aversion to hashmaps/hashsets, a historical accident, or something else?
* This question is closely related, but asks about the representation `graph: Set<(V, V)>`. The top answer suggests using my representation. Looking for a bit more context on this.
* The second answer suggests hash collisions are a problem. But if hash sets are not preferred, another representation of maps and sets can be used, and we still get great performance for edge removal with a possible additional logarithmic factor in cost.
* **Bottom line:** I don't understand why anyone would implement the edges as a list, unless all vertex degrees are expected to be small.

# Answer
In many algorithms we don't need to check whether two vertices are adjacent, like in search algorithms, DFS, BFS, Dijkstra's, and many other algorithms.

In the cases where we only need to enumerate the neighborhoods, a list/vector/array *far outperforms* typical set structures. Python's `set` uses a hashtable underneath, which is both much slower to iterate over, and uses much more memory.

If you want really efficient algorithms (and who doesn't), you take this into account.

If you *need* $O(1)$ lookup of adjacencies and don't intend to do much neighborhood enumeration (and can afford the space), you use an adjacency matrix. If *expected* $O(1)$ is good enough, you can use hashtables, sets, trees, or other datastructures with the performance you need.

---

I suspect, however, that you don't hear about this so often, is because in algorithms classes, it makes analysis much simpler to use lists, because we don't need to talk about *expected running time* and hash functions.

---

Editing in two comments from leftaroundabout and jwezorek. Many real world graphs are *very sparse* and you often see $O(1)$-sized degrees for most of the graphs. This means that *even if* you want to do lookup, looping through a list is not necessarily much slower, and can in many cases be much faster.

As a "proof", I add some statistics from the graphs from Stanford Network Analysis Platform. Out of approximately 100 large graphs, the **average degrees** are

| Avg. degree | number of graphs |
| --- | --- |
| \< 10 | 35 |
| \< 20 | 43 |
| \< 30 | 10 |
| \< 40 | 4 |
| \< 50 | 2 |
| \< 70 | 3 |
| \< 140 | 1 |
| \< 350 | 1 |
> 29 votes

# Answer
In general you are correct, however the list version is sort-of legitimate in the odd case where there can be more than one edge between two nodes. Of course it would still be more conceptually correct to represent the neighbors of each node as a mapping type between node and amount of edges.

When I say "conceptually correct" I mean that due to the fact that the neighbors of a node are not ordered, *conceptually*, using an ordered structure to represent that collection is not proper. The abstract mathematical definition of a graph represents the collection of neighbors as a set, because that's what it is. Programming close to the mathematical representation helps with clarity. If tomorrow I stumble upon a graph implementation where the collection of neighbors is an array or a list I will immediately be suspicious that neighbor *order* plays a role somewhere, which is an enormous addition on mental load.

Depending on the expected use of the graph, it can be faster to use linked lists, arrays, tree-based sets or hash-based sets to hold the neighbors of each node. In my experience (with high level languages where these collections are easy to use), sets are usually the best choice because testing for adjacency between two arbitrary nodes is what I typically happen to do a lot.

As to *why* they are represented like that in those books, I think you gave the answer already: the authors didn't think the distinction to be worth much discussion. Graphs are an ancient topic in programming courses, and it very well might be that these passages date back to a time where lists and arrays were abstractions implemented by the language itself, but not sets. And so it was much easier and less confusing to talk to students back then about the collections they could most easily get access to.
> 2 votes

# Answer
In one of the comments, Yuval mentions that the memory footprint is far lower. I'd like to expand on that point a little.

The adjacency data structure is conceptually a subset of $V$. Suppose there are $k$ edges from some vertex. Assuming the edges are independent, there are ${ \left|V\right| \choose k }$ possible subsets. So *any* representation of this adjacency collection must require at least this many bits to store:

$$\log { \left|V\right| \choose k }$$

(Note that since we're doing information theory, all logarithms are base 2.)

Let $p = \frac{k}{\left|V\right|}$ be the probability of an edge being present. Then by Stirling's approximation:

$$\begin{eqnarray\*}\log { \left|V\right| \choose k } & \approx & \left|V\right| \log \left|V\right| - k \log k - (\left|V\right|-k) \log (\left|V\right|-k) \\ & = & \left|V\right| H\_b(p)\end{eqnarray\*}$$

where $H\_b$ is the binary entropy function:

$$H\_b(p) = -p \log p - (1-p) \log (1-p)$$

When $p \approx \frac{1}{2}$, $H\_b(p) \approx 1$, so you need at least $\left|V\right|$ bits of information to represent this collection. A bit vector is optimal.

When $p \ll \frac{1}{2}$, $\log { \left|V\right| \choose k } \approx k \log \left|V\right|$, so an array of $k$ elements, each containing an integer between $1$ and $\left|V\right|$, is optimal.

(Note that when $p \> \frac{1}{2}$, it may be more space efficient to store the vertices that are *not* present.)

So in the sparse case, not only is smaller, it is an optimal representation.
> 1 votes

# Answer
Here is a different way to think about it. Let's try to represent a graph with adjacency hash tables instead of adjacency lists.

What hash function will we choose, and how large must the table be?

If there are $n$ vertices and they are already numbered $0...n-1$, then I think the most sensible choice of hash function is the identity function! And the size of each hash table will be exactly $n$. Finally, each hash table is simply a boolean vector of length $n$.

Finally, instead of an array of hash tables, we end up with a boolean matrix, called an *adjacency matrix*. Adjacency matrices have been well-suited, and in fact they are better than adjacency lists for some purposes. But worse than adjacency lists for some other purposes.

* "Iterate on the neighbours of a given vertex" is a $\Theta(d)$ operation with adjacency lists, but $Θ(n)$ operation with an adjacency matrix, where $d$ is the degree of that vertex and $n$ the total number of vertices, so lists are better for that purpose;
* "Are two given vertices neighbours?" is an $O(1)$ operation with a matrix, but $O(d)$ operation with adjacency lists;
* You can do linear algebra with a matrix, but not with lists; in particular, if $M$ is the adjacency matrix of a graph, then $M^k$ gives the number of walks of length $k$ between each pair of vertices; using fast matrix exponentiation, this can allow for much faster algorithms than adjacency lists for some problems.

Adjacency hash tables appear to be slower than adjacency lists on the first point, and slower than matrices on the last two points.
> 1 votes

---
Tags: graphs, data-structures, hash-tables
---


# Question
Title: Is the language of PSPACE Turing Machines decidable?
Let

$$L\_{\text{PSPACE}}=\\{\langle M\rangle : M \text{ is a TM using a polyspace amount of memory}\\}$$

Is $L\_{\text{PSPACE}}$ decidable?

---

I don't think we can use Rice's Theorem because this doesn't seem to be a semantic property of TMs. I also don't see any reduction from the HALT problem, or other known undecidable languages like HALTONZERO. But my instinct tells me that this seems uncomputable because it seems like there shouldn't be any way to look at the instructions of a machine and figure out how much space it will ultimately consume.

# Answer
> 1 votes
In fact, you can reduce the $\text{HALT}$ problem to deciding $L\_{\text{PSPACE}}$.

---

Suppose $U$ is a fixed universal Turing machine constructed as in a usual textbook.

Let $\langle T\rangle$ be an input to the $\text{HALT}$ problem problem, where $T$ is a Turing machine.

Construct a Turing machine $U\_T$ that is based on $U$. On an input $w$ of length $n$, $U\_T$ will try simulating $T$ on empty input for $n$ steps, and if $T$ halts before $n$ steps, read next $2^n$ cells. Note that the construction of $U\_T$ from $T$ can be specified algorithmically.

Then $T$ on empty input stops if and only if $U\_T$ belongs to $\overline{L\_{\text{PSPACE}}}$.

Since the $\text{HALT}$ problem is not decidable, neither is $\overline{L\_{\text{PSPACE}}}$.

Since the $\overline{{L\_{\text{PSPACE}}}}$ is not decidable, neither is ${L\_{\text{PSPACE}}}$.

---

**Exercises 1**. Use diagonalization to show ${L\_{\text{PSPACE}}}$ is not computably enumerable.

**Exercises 2**. Use diagonalization to show $\overline{{L\_{\text{PSPACE}}}}$ is not computably enumerable.

---

Here is a good question and answers with similar content, Are runtime bounds in P decidable? (answer: no).

---
Tags: turing-machines, undecidability, space-complexity
---


# Question
Title: What is memory model in computer organization?
I'm new to Computer Organization and even to this community. I didn't find anything which was simple, clear and up to the point. Any examples supporting the discussion is appreciated. I'm not looking for some text book answer.

Here's an example of my view to question: What is a Programmer's Model ? Programmer's model shows what the CPU has available to a programmer for the execution of computer programs. It covers the CPU resources for execution of the CPU's instruction set. (resources like state variables, AKA registers that can affect — or be affected by — the execution of instructions)

This programmer's model would NOT detail hardware, such as how the CPU's electronic circuitry works, how buses transport data or the I/O peripherals available. i.e. The underlying details of how all of that is actually accomplished are hidden from the programmer.

In other words, the programmer's model would NOT cover functions that cannot be observed by CPU instructions. \[EXCEPTION: those instructions trying to detect hardware operations, such as cache behavior, read/write variances because of varying bus delays etc are excluded\]

So, similarly I wish to know what is a Memory Model ?

# Answer
If you have a single thread program, with no memory shared with any other threads, then you essentially have a a single-CPU machine. There is only one opinion on the contents of memory, and that is yours.

When you have multiple CPUs, you have the issue that different CPUs can try to modify the same memory at the same time. If those CPUs have caches, it's possible that the caches will flushed in a different order than the original writes occurred.

This means that, if you're not careful, the contents of "memory" could look different to different CPUs. Moreover, different CPUs might see the same memory operations happen in a different order.

To see why this is important, consider what happens when you acquire or release a lock.

We will assume that acquiring a lock is just a write to memory (a spinlock really is just that). Then it's important that any memory operations which are protected by the lock happen after the acquisition occurs. Similarly, any writes to memory need to happen before the lock is released.

You can think of a memory model as a set of restrictions on how much a CPU (and a compiler, for that matter) can reorder memory operations. The way that this is usually presented is mathematically, as a set of "happens-before" relations. Memory operations protected by a lock must "happen before" the lock is released.

Apart from giving guarantees that certain things will happen before certain other things, programmers can control this by using special operations such as memory barriers. So, for example, there will typically be a memory barrier right before the store operation that releases a spinlock.

Even in CPUs with very strict memory models, you sometimes need consider the language's memory model to get multiprocessor algorithms working correctly. Many compilers have a way for you to write an "optimisation barrier", which prevents the compiler from reordering code across the barrier.

As an example, there's a good introduction to Java's memory model.
> 1 votes

# Answer
um I'm not sure if it is what you are looking for or not. I assume by memory model you mean the part in which we place input and do some calculation (**like paper which we write something to remember and calculate**).

The memory model depends on the definition of the model itself. In CS we have different kinds of computing model with different *power*. One of the simplest one is Deterministic Finite Automata and informally its memory just contains an input *string* and nothing more. One of the most powerful one is Turing machine that its memory is a *infinite tape*. There are other models between these two such as PushDown Automata and Linear Bounded Automata where loosely speaking their memories contains stack of symbols and finite tape.

Also there are other models with same *power* as Turing machine, like two stack PDA, cellular automata and etc.

So by how to define your computing model and program, your memory model details will be different.
> 0 votes

---
Tags: terminology, computer-architecture
---


# Question
Title: CTL trouble translating text into formula
I have an excercise where I have to translate verbally formulated statements into CTL formulas. I have particularly trouble with this one:

> On every path q is true at least once and p was true sometime before, after no longer. My attempt is the following: $AF q \land (EF p) AU q$

This is obvously wrong. The first part is easy, then the second is more difficult. What I've stated there implies that there exists a path to $p$ before $q$ but not that $p$ was true on the previous path, and the third part to me looks impossible. Can anyone help?

# Answer
$\newcommand{AF}{\text{AF}\\;}\newcommand{AG}{\text{AG}\\;}$Try to decode this:

For each path:

* In the future: p and
    + In the future q and
        - Always in the future not p

---

You correctly concluded that the correct formula is

$$ \AF \left( p \land \AF \left( q \land \AG \neg p \right) \right).$$

The key thing to understand about CTL is that when you evaluate things like $\AF (p \land \AF q)$ then this is true if somewhere in the future $p \land \AF q$ is true, which means that $\AF q$ is evaluated in the state where $p$ is true.
> 2 votes

---
Tags: logic, computation-tree-logic, modal-logic
---


# Question
Title: What are good alternatives to the table-driven approach to lexical analysis?
In my theoretical computer science class we learned about FSMs/lexical analysis/parsing. However, my teacher focused solely on the table-driven approach to the process for simplicity (I think, anyway), where the table is a 2D array with the row being a character and each column being a DFA state transition. The table therefore might look like this (in C++), assuming the character tabulation character is what we're scanning and assuming there are 13 states and 128 characters:

```
static const unsigned char DFA[128][13] = {
    // ...
    // Tab
    {WS, ACCEPT, ACCEPT, ERROR, ACCEPT, ERROR, ERROR, ERROR, ERROR, ACCEPT, ACCEPT, ACCEPT, ACCEPT},
    // ...
};

```

One advantage to this approach is that the lexer can be relatively simple to extend, only requiring one to modify the DFA to add new tokens (e.g. `<=`, `:=`, ...). All the lexer has to do is look up the character (row in the DFA) and the state that its currently in to transition to another state (the column) (`DFA[character_read][current_state]`) However, this is burdensome because if you want to add new tokens that aren't already scanned (e.g. a combined token like `<=` or `--`), you have to add another state and modify every row in the DFA table to accommodate the change. I can think of a few ways of circumventing this, none of which are very pleasant:

1. Make the "error" state be state `0` and use `std::array` to automatically initialize all new columns to the "error" state, and then only initialize the rows you want to actually add.
2. Parse multi-character tokens in the parser itself (definitely a bad idea because it pollutes the parser with work that should've already been completed).

These problems add up when you want to parse things like unicode characters. I can't think of any way of actually making this work using the table-driven approach, other than generating a size\_of\_ucd\*number\_of\_states 2D array, which is nearly impossible to open in most text editors because the file is so massive, and it still suffers from the above issues.

I've heard of the directly coded approach, as well as using functions like `ispunct` and `isalpha` (or matching characters to unicode character categories), but this seems just as clunky: now modifying your lexer requires you to modify how the lexer composes tokens instead of just modifying a table and not having to touch your main lexer code at all. Using a lexer generator is an option but hand-writing lexers and parsers seems like a much better way of fully understanding how your parser works, and it also requires no extra tools for the build process other than those that your build system requires already. Plus, the code can be made to be very readable, which can't be said for generated code (at least 3/4 of the time).

What are some good solutions to resolving this problem that makes the lexer easy to read and modify? I could see using character ranges as being a possible workaround, but the UCD doesn't appear to be very contiguous, which makes that difficult to do.

# Answer
Real lexical analyser generators group characters into classes that are equivalent.

Let's suppose you are trying to parse C, for example, and we will further suppose that keywords are handled via a symbol table of some kind, so we only need to recognise identifiers. A C identifier starts with an alphabetical character or underscore, and is followed by zero or more alphabetical characters, numeric characters, or underscores.

Do all alphabetical characters share the same transitions from all DFA states? Well, no. The characters `f`, `e`, and `x` (and their upper-case equivalents) play special roles in the lexical syntax of numbers. But *most* alphabetical characters are equivalent.

Similarly, all numerical characters are equivalent except for `0`, which has a special use in representing hexadecimal and octal numbers. But the others are equivalent.

So it makes sense in practice to have a single array mapping characters to character classes, and then define the DFA transitions in terms of character classes, since there are far fewer character classes than characters.

If you want to hand-write a lexical analyser, you could consider using `goto` statements for your state transitions.

Yes, seriously. Dijkstra's point was that structured code follows structured data. But more abstract models of computation, like finite state machines, might map more directly into other language constructs.

Of course, there's always real-world compiler source code that you could examine for ideas.
> 0 votes

---
Tags: lexical-analysis
---


# Question
Title: Finding the smallest amount of function operations to sort an array
Let's say we have a function shift(array\[\], int s) which swaps the position of array\[s\] to array\[0\] and shifts all other elements to the right. For example:

array = {1,2,3,4,5,6} --\> shift(array, 3) --\> array = {4,1,2,3,5,6}

If you were to sort an array consisting of numbers 1..n using only the function shift, what would be your approach in order to use shift() the least amount of times?

I've tried many solutions, but nothing which would fit all types of arrays. For an array like {3,4,2,5,1} a good idea would be marking all elements which are smaller than the element behind them as not in their place, and then shifting the biggest marked element, like this:

{3,4,2,5,1} --\> {2,3,4,5,1} --\> {1,2,3,4,5} function called 2 times.

But this algorithm would lead to a disaster when called on an array like this: {1,9,7,2,5,4,8,6,10,3}. It seems like the best solution would be simply putting the biggest element at the start of the array, and then putting the element smaller by 1 behind it, so calling the function as many times as the size of the array. There's gotta be some sort of solution which works for every type of input which I'm just not seeing?

# Answer
## The short answer

You can barely do any better than just the naive solution. To be a bit more precise, let $p\_i$ be the position of the $i$'th largest element. Then if for some $k$ we have that $p\_k\>p\_{k+1}$, but for all $m \> k$ it holds that $p\_{m}\<p\_{m+1}$ \- then you will need *exactly* $k$ function applications.

## The long answer

(Assuming you read the "short answer") Why would this be the case?

This $k$ is special - its the largest element that is not in its place. Notice that applying shift to $k+1$ will only *decrease* $p\_{k+1}$ and since we already assumed that $p\_{k}\>p\_{k+1}$ this will also hold after applying the function and hence wont fix the relative position between $k$ and $k+1$ (which needs to be fixed for the array to be sorted).

In addition, applying the function to any other value which is not $k$ or $k+1$ cannot change their relative positions (directly follows from the definition of the function).

Hence, one **must** apply the function on $k$ at some point in time. But now $p\_k=0$ and hence it has to be true that $p\_{k-1}\>p\_k$.

I believe you can see how this continues now - you will have to apply the function on $k-1$ and then on $k-2$, and so on.

This also gives you the exact order you need to apply the function in. Therefore, this exact order is the absolute best you can ever do - and will require exactly $k$ times to apply a shift.
> 1 votes

---
Tags: algorithms, sorting
---


title: Merging states in LALR parser

text:
# Question
Title: Merging states in LALR parser
I was learning LALR parsers from the dragon book (Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman) and I came across the example on page 267. I'll try my best to describe my question without needing the actual book for reference.

The book states that:

> I4 and I7 form such a pair, with core $\\{C -\> d.\\}$ . Similarly, I3 and I6 form another pair, with core $\\{C -\> c.C, C -\> .cC, C -\> .d\\}$ . There is one more pair, I8 and I9 with common core $\\{C -\> cC.\\}$ .

Here, I3 and I6 have the same set of cores $\\{C -\> c.C, C -\> .cC, C -\> .d\\}$ . My question is, should I combine I3 and I6 if I3 had the set of cores $\\{C -\> c.C, C -\> .cC\\}$ and I6 had the set of cores $\\{C -\> c.C, C -\> .cC, C -\> .d\\}$ ? That is, should the set of cores for the itemsets should be exactly the same for combining them or can one be a proper subset of the other?

Thanks in advance!

# Answer
> 2 votes
No, you can't do that. The definition of LALR parsers is that it has combined(union of lookaheads) states having the **same** cores but different lookaheads.

So what would happen if you were to combine states based on a subset/superset basis? This would basically mean modifying the grammar, also you run into the possibility of having shift/reduce conflicts. You could easily test out your theory by parsing a string using a LALR parser constructed as per your idea and a CLR parser for the same. Since they have the same parsing power, the string should be parsed by both of them. It might happen that both parsers are able to parse a particular string so you'll have to be select your string carefully.

---
Tags: compilers, lr-k
---


# Question
Title: Why is this mapping from binary to natural numbers surjective?
In my Lecture we came across something of importance for the Church-Turing-Thesis and i noticed one particular function, which confused me.

Function: Let $bin(x)$ be the injective binary extension without leading zeros. It is not surjective because of the extension without leading zeros.

$$cod := \\{0,1\\}^\* \to \mathbb{N} \hspace{2mm} x \mapsto bin^{-1}(1x)-1$$

Question:

Why is this particular map from the binaries and the natural numbers surjective ? I do not need a intricate proof, but a explanation is enough to wrap my head around this topic.

They also noted that $bin^{-1}$ can be written, because 1x is in the image of $bin$.

Injectivity is given, because $bin$ is injective and on two different strings $x$ and $y$ we get two different decimal numbers out of the function.

Thanks in advance for any awnser on this question, or any comments posted on it.

# Answer
> 1 votes
For any number $n\in\mathbb{N}$, consider $bin(n+1)$. Since $n+1\>0$, there must be at least one bit in $bin(n+1)$ in the state of "1".

Its not too hard to see why this immediately implies that there exists some $x\in \\{0,1\\}^\*$ such that $bin(n+1)=1x$ (since we can remove the trailing zeros), and hence $n+1={bin}^{-1}(1x)$, meaning that $n={bin}^{-1}(1x)-1=cod(x)$.

Therefore $cod$ is surjective by definition.

---
Tags: mathematical-foundations
---


# Question
Title: How many clock cycles are used to run my code?
Suppose that I want to know the number of the cycles of cpu clock that uses to run a specific code written with a specific programming language, like Python or others.

Can I do it?

I mean, do you have any access to count the CPU's clock cycles for your code technically?

Does this code run on any system (any minicomputer or microprocessor) with the same number of cycles of CPU clock when you're using the exactly same code, programming language and library?

Actually, if the answer to the last question is yes, if I have the number of cycles, I can calculate the code-runtime for every systems according to the clock frequency of the CPU. Then, I can find the suitable system that run the task fast enough and choose it for my project.

If you have the answer, I'll appreciate if you can provide references.

# Answer
> Assume, I want to know the number of the cycles of cpu clock that uses to run a specific code written with a specific Programming language like python or others. Can I do it?

**Short answer:** Not currently.

**Longer answer:** It is at least conceptually possible for a restricted subset of programs -- e.g., restricted to loop-free non-interactive code -- and it may be possible for more programs in the future.

**Long answer:** This is a very difficult task, and an open research question. To my knowledge, it not currently possible. There are three main barriers to accomplishing this:

1. **Predicting the compiler.** The compiled code (say, in X86 assembly) will look considerably different than the piece of code itself. Predicting this would essentially require re-implementing the compiler ourselves. One way to get around that we could just pre-compile the piece of code individually and link it to other parts of the program.
2. **Predicting loops.** The second challenge is more of a fundamental impossibility: whether looking at the source program or the compiled code, if the piece of code has *loops* (i.e. in assembly, Jump instructions), then it is very difficult to infer how many times the loops will run. It is undecidable in general, though in specific cases we might hope to use static analysis to determine the exact number of loop iterations based on context.
3. **Predicting the architecture.** Finally, there is a great deal of difference between the assembly code and the number of cycles it will take to actually run on the hardware, for a number of reasons which are only getting more complex, including for example basic architectural features like caching and branch prediction, as well as more complicated modern hardware optimizations. As you point out, this also means that the number of cycles will *depend* on the target architecture and target hardware.

Despite these barriers, I think this is a feasible goal and something that we *could* conceivably achieve in the future (and I know at least some researchers working on it). For a starters, we could look at code that is:

* Already compiled to assembly (avoiding barrier 1);
* Loop-free or consisting only of simple loops, e.g. for loops where the number of iterations is a known variable $n$ (avoiding barrier 2); and
* Does not contain any interactive operations difficult to predict at the hardware level, specifically memory accesses, system calls, and I/O.

With these three restrictions, which are admittedly rather severe, it would be *conceptually* completely possible to predict the exact number of clock cycles of a program.
> 1 votes

---
Tags: runtime-analysis, cpu
---


# Question
Title: Union of multiple overlapping sets efficiently?
I have $n$ sets, each of which overlaps heavily with the other sets, and I want the union of all of them. The obvious solution is to take the union of each set, one by one, which results in $O(n^2)$ running time, but is there a better solution?

**Clarification from the comments:** Assuming all sets have $n$ elements, so $n$ represents both the number of sets and the size of each set.

# Answer
> 2 votes
The answer to your question depends heavily on the representation of the sets. For simplicity, I am assuming that we have $n$ sets of integers, where all the integers are between $0$ and $n-1$ (conforming to your statement that the $n$ sets each have up to $n$ elements).

* If the sets are represented in **a generic set data structure such as a hash table,** as pointed out in the comments, that means even *reading* the input takes $\Omega(n^2)$ time in the worst case. This implies that it is completely impossible to avoid the $n^2$ algorithm of unioning all the sets together.
* One common compact representation of sets for practical results is using **bit-vectors.** If the length of a machine integer is 8 bytes (64 bits), then we represent a set of up to $n$ elements using a bit-vector of length $n$ which is represented as an array of $\frac{n}{64}$ integers. As bitwise xor is an $O(1)$ hardware operation, unioning two of these sets only takes $\frac{n}{64}$ time, and doing this $n$ times we have $O(\frac{n^2}{64})$ for the whole union. Still quadratic, but much better in practice.
* There are other interesting representations of sets. One representation is using **logical predicates:** a set here is a formula $\varphi(n)$ which is true exactly when $n$ is in the set. For example, the set of all integers between $1$ and $10000$ would be represented as the predicate "$1 \< n \< 10000$" (expressed as a syntax tree). Unioning this kind of predicate together *can* be much faster than unioning the sets, if the sets are of a simple structure, like ranges ("$1 \< n \< 10000$"), unions of a few different cases ("$n \< 5 \text{ or } n = 10$"), or specific elements ("$n = 5$"). When unioning, we apply simplifications to the resulting predicates (e.g., "$x \text{ or } x$" simplifies to "$x$").
* Finally, extending this, one way of representing predicates that happens to be especially effective is using a **binary decision diagram,** which is kind of like a decision tree. These structures lead to a pretty compact encoding of common sets like ranges and predicates. They can be unioned together efficiently in $O(m)$ where $m$ is the size of the BDD structure, so the total time will be $O(m \cdot n)$. For both this and the formula representation, there is a necessary assumption that the sets we are unioning together are "not too complex" and have a more compact representation than just listing out the elements. But, even in the worst case, it only takes $O(n \log n)$ space to store a set of $n$ elements explicitly as a BDD, so we aren't paying much of a cost, and in practice, the sets will often overlap significantly and we will get a more compact representation.

---
Tags: time-complexity, sets
---


title: Sorting N dimensional data

text:
# Question
Title: Sorting N dimensional data
What would be a good choice for a key to sort a complex number $(a+ib)$ or any $n$-dimensional data for that matter. Is using the magnitude of that vector a good choice rather than using any one of the dimensions, or is there any other metric which would suit this?

This was asked to me in an interview (it went like "how can one sort complex numbers?") Since then I have been thinking if I was right or wrong. So as far as this question is concerned feel free to assume any application or any data.

# Answer
The following would be natural choices for sorting complex numbers:

* **Lexicographic ordering, real first:** Sort $a + bi$ first by $a$, then by $b$. So $a + bi \< c + di$ if $a \< c$ OR if $a = c$ and $b \< d$.
* **Lexicographic ordering, complex first:** $a + bi \< c + di$ if $b \< d$ OR if $b = d$ and $a \< c$.
* **By magnitude:** $a + bi \< c + di$ if $|a + bi| \< |c + di|$.
* **By argument:** $a + bi \< c + di$ if $\text{arg } a + bi \< \text{arg } c + di$, where $\text{arg}$ is the angle of the complex number.

Of these, the first two have the advantage that they agree on the ordering of real numbers, which could often be important. The first two also have the advantage that they are **total** orderings rather than orderings where some elements are indistinguishable (for example, in the magnitude ordering, elements of the same magnitude are indistinguishable). The last two can be fixed to be total if you add a tiebreaker ordering, e.g. if two numbers have the same magnitude, then order them by argument, or vice versa.
> 3 votes

---
Tags: data-structures, sorting
---


# Question
Title: MIPS pipeline: MEM stage takes one cycle?
Apparently, each stage of the MIPS processor pipeline takes one CPU cycle. According to this, a memory write can take more than one cycle:

> 1 cycle to read a register 4 cycles to reach to L1 cache 10 cycles to reach L2 cache 75 cycles to reach L3 cache and hundreds of cycles to reach main memory.

How then can the MEM stage of the MIPS pipeline be said to take 1 cycle?

# Answer
The MEM stage takes one cycle. But the write isn’t completed at that time. It is completed4, 10, 75 or many cycles later.

If you perform another write instruction, the MEM stage may be stalled until the previous one finishes. Modern processors can queue up many incomplete write instructions. If you perform many write instructions in a row, your processor stalls. If you stop performing write instructions for a while, the incomplete ones will complete.
> 2 votes

---
Tags: cpu, cpu-pipelines, mips
---


# Question
Title: How programming languages are capable of handling generic types
How programming languages are capable of handling generics ?

Here is some context on why I got the question.

Constructs like Lists, Dictionaries and Sets in Python can handle any type of data without even specifying the type of data being added. Whereas in Java Collections require you to specify the type at the time of creating those collections objects.

Both Python and Java are originally implemented in C\C++. So the capability of Java and Python to handle Generics should had obtained from C\C++. Even Javascript engines are built on C++.

To answer my own questions I started thinking why we need to specify the type when we are creating an object, my understanding for this is because to inform the compiler the amount of memory to be allocated in order for the object to live in Memory (RAM). Thus if we are creating an ArrayList in Java of say a **MyRandomClass**, it should likely allocate an array of Memory Blocks(MB) where each MB is of the size of **MyRandomClass**

However in Python a list can hold any type of Class without even specifying the type at the time of creation.

What happens under the hood ?

# Answer
You mention Python, which is a **dynamically typed language.** The answer is that it represents the type explicitly as part of the object. You can imagine the following picture: an element of a list or a dictionary is a structure with the following fields

```
type: <string or type ID>
data: <pointer to memory>

```

This is how types are represented: as an explicit byte in memory which says what type something is.

In fact, if you're curious, in Python you can see this directly. Fire up a python shell and do `x = 3`, then `type(x)`. Python knows that `x` has type `int`. How does it know? Well check out

```
dir(x)

```

to see that there are a bunch of attributes that x has:

```
'__abs__', '__add__', '__and__', '__bool__', '__ceil__', '__class__', '__delattr__', '__dir__', '__divmod__', '__doc__', '__eq__', '__float__', '__floor__', '__floordiv__', '__format__', '__ge__', '__getattribute__', '__getnewargs__', '__gt__', '__hash__', '__index__', '__init__', '__init_subclass__', '__int__', '__invert__', '__le__', '__lshift__', '__lt__', '__mod__', '__mul__', '__ne__', '__neg__', '__new__', '__or__', '__pos__', '__pow__', '__radd__', '__rand__', '__rdivmod__', '__reduce__', '__reduce_ex__', '__repr__', '__rfloordiv__', '__rlshift__', '__rmod__', '__rmul__', '__ror__', '__round__', '__rpow__', '__rrshift__', '__rshift__', '__rsub__', '__rtruediv__', '__rxor__', '__setattr__', '__sizeof__', '__str__', '__sub__', '__subclasshook__', '__truediv__', '__trunc__', '__xor__', 'as_integer_ratio', 'bit_length', 'conjugate', 'denominator', 'from_bytes', 'imag', 'numerator', 'real', 'to_bytes'

```

and among these, there's one called `__class__`. If you do

```
x.__class__

```

then Python prints out, `<class 'int'>`.

---

This is, to a rough approximation, how basically all **dynamically typed** languages do types. In **statically typed** languages like C++ or Rust, things are different. Instead of representing the type as part of the object, the compiler figures out the type at compile-time, and uses it to construct machine code for your program, and makes sure that all the types are as expected in the machine code, a process called **type-checking.** Once the compiler is certain all the types are correct, it then throws them away so that the machine code and explicit memory don't have any types anywhere.

As to **generics,** the process is similar: in dynamically typed languages the type is part of the object, in statically typed languages like C++ or Rust, the compiler has to figure out all the generic types that you use at compile-time, generate code for each one, and then get rid of the types in the machine code.
> 1 votes

# Answer
As an example: Apple's Swift compiler will compile the required code for every type needed, then compare the various versions, and if two are identical then one of them is picked.

For example, lots of the code for an array of unsigned 32 bit integers and for an array of signed 32 bit integers may very well be identical, while the code for an array of 64 bit integers, signed or unsigned, would be different. The code for an array of *any* reference type might be different.

It's up to the language designer and to some extent the designer of the standard library to make sure not too much unnecessary code is being produced.
> 0 votes

---
Tags: programming-languages
---


title: Greedy Stays Ahead proof of "Jump Game"

text:
# Question
Title: Greedy Stays Ahead proof of "Jump Game"
(Source: https://leetcode.com/problems/jump-game-ii/)

**Consider the following problem:** Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

**For example**, if nums = \[2,3,1,1,4\] then the minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

**Greedy Algorithm:** Let $n(x)$ be the number located at index $x$. At each jump, jump to the index $j$ that maximizes $j + n(j)$. In the above example, starting at index $0$, we can jump $1$ or $2$ jumps. If we jump once to index $1$, then the objective value is $1 + n(1) = 4$. If we jump twice to index $2$, then the objective value is $2 + n(2) = 3$. Thus, we must jump once to index $1$, and so on.

**Prove that the greedy algorithm is correct.**

I am trying to prove this with greedy stays ahead. The working inductive hypothesis is that at jump $k$, $o\_k + n(o\_k) \leq g\_k + n(g\_k)$ where $o\_k$ is the index of optimal solution at jump $k$ and $g\_k$ is the index of greedy solution.

Then, at jump $k+1$, we know that $o\_{k+1} \leq o\_k + n(o\_k)$ \- this is the farthest index we can jump to - and similarly for $g\_{k+1}$.

I am struggling to finish the proof though, and cannot seem to manipulate the inequalities to conclude that $o\_{k+1} + n(o\_{k+1}) \leq g\_{k+1} + n(g\_{k+1})$ \- could someone help on this matter?

# Answer
The essential problem with your approach is that you are trying to prove a proposition that is too weak to to sustain the induction step.

Here is the proposition that we should prove:

For $k$ ranging from $1$ to the number of jumps in the greedy solution,

* $a\_k + n(a\_k) \leq g\_k + n(g\_k)$, where $a\_k$ is the index of an **arbitrary** jump sequences at jump $k$ and $g\_k$ is the index of greedy solution at jumtp $k$, and
* for all $0\leq m\le g\_k$, $m+n(m)\leq g\_k + n(g\_k)$.

I believe that you will be able to prove the proposition above using induction on $k$.
> 2 votes

---
Tags: algorithms, greedy-algorithms
---


title: Shortest path with odd weight

text:
# Question
Title: Shortest path with odd weight
Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd.

We are looking for an algorithm for finding the weight of the shortest odd path between any two vertices in the graph.

If possible, describe one algorithm that is reduction-based (that is, make some modification to the graph so that application of Floyd-Warshall, or any other "known" algorithm, and then deciphering the answer will give the result, see http://en.wikipedia.org/wiki/Reduction\_(complexity)) and one that is "direct" (that is, make some modification to Floyd-Warshall in order for it to solve this problem).

# Answer
**Direct**

I answered this here:

https://stackoverflow.com/questions/11900830/using-floyd-warshall-algorithm-to-determine-an-odd-matrix/11902296#11902296

Basically:

1. Run the algorithm twice (literally a for loop that runs 2 times around the F-W loops) because the path may be longer than the number of vertices
2. Save both the best odd and best even path costs for each pair of vertices - instead of cost\[v1\]\[v2\] I use cost\[v1\]\[v2\]\[evenness\].

Proof that running the algorithm twice is sufficient: let's assume a path in the graph has more than 2V vertices -\> at least one vertex C must appear 3 times -\> it must appear at least twice with the same evenness-of-path-up-to-this-point E. So the path is of the form (with C(E) meaning "vertex C appearing with evenness E"):

P0 - C(E) - P1 - C(E) - P2

where P0, P1 and P2 are segments of the path (perhaps empty). But this path has the same evenness, initial and final state as:

P0 - C(E) - P2

And due to non-negative weights, the former path can't be shorter. So running the algorithm twice is sufficient.

**Reduction**

From G, create G' in the following way:

1. For each vertex Vi in G, add Vi\_odd and Vi\_even to G' (a simple implementation is: i\_even := 2\*i, i\_odd := 2\*i+1, and the inverse, i = i\_either/2)
2. For each edge in G, let Vi be the source vertex, Vj the target vertex, W the weight. If W is odd, add edges (Vi\_odd, Vj\_even) and (Vi\_even, Vj\_odd) with weight W. If W is even, add edges (Vi\_even, Vj\_even) and (Vi\_odd, Vj\_odd) with weight W.

Run F-W on G'. The weight of the path from Vi\_even (initial path weight is 0 = even) to Vj\_odd in G' is the weight of the shortest odd path from Vi to Vj in G. The weight of the path from Vi\_even to Vj\_even is the shortest even path.
> 1 votes

# Answer
Homework? I start with hints. Integer values assumed.

Reduction. Make two copies of the vertices in the graph (odd and even) and rewire the graph such that each odd length edge of the graph is between the even and odd copies.

Direct. The algorithm keeps two values (for each pair of vertices): the length of the even length and odd length shortest paths. You can adapt Floyd if you realize that odd+odd = even (etc).
> 2 votes

# Answer
Sorry for digging up this old topic, but all proposed algorithms on this thread are wrong!

This problem is, in fact, NP-hard (and even NP-complete): The paper "Even Cycles in Directed Graphs" by Carsten Thomassen proves in Proposition 2.1 that the problem of finding an odd / even length directed cycle in a digraph through a given edge (!) is NP-complete. Now, we can in fact solve this problem using the algorithm described in this thread: Choose weight = 1 for every edge. Let e be the selected edge that an even cycle should pass through, say e = (v,w). Now, find an odd path from w to v. This path exists if and only if there exists an even cycle through e. This shows that this algorithm must be wrong.

I believe that the suggested algorithm does return an odd-length WALK though, but not a path (vertices may be repeated).

Please upvote this reply so people don't find false info on this thread!

For sake of completeness, I will state some info on this and similar problems: It is NP hard to find an odd or even length path in a digraph between two vertices. It is NP hard to find an odd or even length cycle going through a fixed edge in a directed graph. However, it is polynomial-time solvable to find an odd directed cycle in a digraph. The intuition behind this is the following: If we find an odd walk (repeated vertices), it must contain an odd cycle too. It's just not necessarily the case that this odd cycle runs through the edge we want it to run through. Finding a shortest odd-length cycle is also possible (algorithm can be found in the paper mentioned above). Regarding even-length cycles in digraphs: This problem is polynomial-time solvable but was, for a very long time, unsolved, see https://cstheory.stackexchange.com/questions/19703/finding-even-cycle-in-directed-graphs/19704 .
> 1 votes

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


# Question
Title: Is there a meta-analysis of this concept anywhere?
In a textbook on systems and networks, it states "Stated broadly, a program tends to access a relatively small region of memory irrespective of its actual memory footprint in any given interval of time"

Was there some kind of meta-analysis done on multiple programs to come to this conclusion?

# Answer
> 1 votes
This principle is called **cache locality,** **the locality principle,** or locality of reference. Not all programs exhibit good locality, in fact there are plenty of real-world programs which don't. For example, any large-enough hash table eventually fails to exhibit locality:

```
ngramcounter = HashTable<(String, String, String), int>
for adjacent words w1, w2, w3 in VeryLargeDocument:
    ngramcounter[(w1, w2, w3)] += 1

```

However, it has been known empirically since very early in the history of computer architecture this property often holds, and *often* is all we need for it to be worth it. An overview-style reference is Denning, *The Locality Principle.* PDF --- discusses the history of how locality became to be recognized by mainstream architectures, including some examples of meta-analyses. An excerpt:

> 1980: Denning gathers the results of over 200 virtual memory researchers and concludes that working set memory management with a single system wide window size is as close to optimal as can practically be realized.

I wasn't able to find a paper specifically focusing on a meta-analysis of cache locality in a bunch of studies, but most papers on the topic empirically validate their ideas on real-world programs and the principle is very well established. Just as one example of a possible paper to read with a lot of experimental detail, see Grunwald, Zorn, Henderson, Improving the Cache Locality of Memory Allocation. There are many others.

---
Tags: computer-architecture
---